32 public grapht<cfg_base_nodet<T, unsigned> >
42 const auto &method=args.first;
43 const auto &amap=args.second;
44 for(
const auto &inst : amap)
49 (*this)[entry_map[inst.first]].PC=inst.first;
52 for(
const auto &inst : amap)
54 for(
auto succ : inst.second.successors)
59 for(
const auto &table_entry : method.exception_table)
61 auto findit=amap.find(table_entry.start_pc);
64 "Exception table entry doesn't point to an instruction?");
65 for(; findit->first<table_entry.end_pc; ++findit)
71 if(succit==amap.end())
73 const auto &thisinst=findit->second;
74 if(thisinst.successors.size()==1 &&
75 thisinst.successors.back()==succit->first)
78 entry_map.at(findit->first),
87 return args.second.begin()->first;
92 return (--args.second.end())->first;
97 return args.second.empty();
132 std::set<local_variable_with_holest *> >
145 auto findit=
order.find(a);
146 if(findit==
order.end())
148 return findit->second.count(b)>0;
162 std::set<local_variable_with_holest*> &result)
164 if(!result.insert(start).second)
166 auto findit=predecessor_map.find(start);
167 if(findit==predecessor_map.end())
169 for(
const auto pred : findit->second)
183 if(!(prevstatement.size()>=1 && prevstatement.substr(1, 5)==
"store"))
186 unsigned storeslotidx;
187 if(inst.
args.size()==1)
190 const auto &arg=inst.
args[0];
198 prevstatement[6]==
'_' && prevstatement.size()==8,
199 "expected store instruction looks like store_0, store_1...");
200 std::string storeslot(1, prevstatement[7]);
202 isdigit(storeslot[0]),
203 "store_? instructions should end in a digit");
206 return storeslotidx==slotidx;
220 var.
holes.push_back({from, to-from});
231 local_variable_table_with_holest::iterator firstvar,
232 local_variable_table_with_holest::iterator varlimit,
233 std::vector<local_variable_with_holest *> &live_variable_at_address)
235 for(
auto it=firstvar, itend=varlimit; it!=itend; ++it)
237 if(it->var.start_pc+it->var.length>live_variable_at_address.size())
238 live_variable_at_address.resize(it->var.start_pc+it->var.length);
240 for(
unsigned idx=it->var.start_pc,
241 idxlim=it->var.start_pc+it->var.length;
245 INVARIANT(!live_variable_at_address[idx],
"Local variable table clash?");
246 live_variable_at_address[idx]=&*it;
275 local_variable_table_with_holest::iterator firstvar,
276 local_variable_table_with_holest::iterator varlimit,
277 const std::vector<local_variable_with_holest *> &live_variable_at_address,
283 for(
auto it=firstvar, itend=varlimit; it!=itend; ++it)
289 it->var.index==firstvar->var.index,
290 "all entries are for the same local variable slot");
299 msg.
debug() <<
"jcm: ppm: processing var idx " << it->var.index
300 <<
" name '" << it->var.name <<
"' start-pc " 301 << it->var.start_pc <<
" len " << it->var.length
306 unsigned end_pc=it->var.start_pc+it->var.length;
307 auto amapit=amap.find(end_pc);
309 amapit!=amap.begin(),
310 "current bytecode shall not be the first");
311 auto old_amapit=amapit;
313 if(old_amapit==amap.end())
316 end_pc>amapit->first,
317 "Instruction live range doesn't align to instruction boundary?");
325 unsigned new_start_pc=it->var.start_pc;
326 for(; amapit->first>=it->var.start_pc; --amapit)
328 for(
auto pred : amapit->second.predecessors)
336 (pred<live_variable_at_address.size() ?
337 live_variable_at_address[pred] :
353 auto inst_before_this=amapit;
355 inst_before_this!=amap.begin(),
356 "we shall not be on the first bytecode of the method");
358 if(amapit->first!=it->var.start_pc || inst_before_this->first!=pred)
363 msg.
warning() <<
"Local variable table: ignoring flow from " 364 <<
"out of range for " << it->var.name <<
' ' 365 << pred <<
" -> " << amapit->first
370 *(inst_before_this->second.source),
373 msg.
warning() <<
"Local variable table: didn't find initializing " 374 <<
"store for predecessor of bytecode at address " 375 << amapit->first <<
" (" 376 << amapit->second.predecessors.size()
377 <<
" predecessors)" << msg.
eom;
378 throw "local variable table: unexpected live ranges";
386 if(pred_var->var.name!=it->var.name ||
387 pred_var->var.descriptor!=it->var.descriptor)
392 msg.
warning() <<
"Local variable table: ignoring flow from " 393 <<
"clashing variable for " 394 << it->var.name <<
' ' << pred <<
" -> " 400 predecessor_map[&*it].insert(pred_var);
407 it->var.length+=(it->var.start_pc-new_start_pc);
408 it->var.start_pc=new_start_pc;
421 const std::set<local_variable_with_holest*> &merge_vars,
426 unsigned first_pc=UINT_MAX;
427 for(
auto v : merge_vars)
429 if(v->var.start_pc<first_pc)
430 first_pc=v->var.start_pc;
433 std::vector<unsigned> candidate_dominators;
434 for(
auto v : merge_vars)
436 const auto &dominator_nodeidx=
438 const auto &this_var_doms=
439 dominator_analysis.
cfg[dominator_nodeidx].dominators;
440 for(
const auto this_var_dom : this_var_doms)
441 if(this_var_dom<=first_pc)
442 candidate_dominators.push_back(this_var_dom);
444 std::sort(candidate_dominators.begin(), candidate_dominators.end());
449 for(
auto domit=candidate_dominators.rbegin(),
450 domitend=candidate_dominators.rend();
456 while(domit!=domitend && *domit==dom)
461 assert(repeats<=merge_vars.size());
462 if(repeats==merge_vars.size())
466 throw "variable live ranges with no common dominator?";
479 const std::set<local_variable_with_holest *> &merge_vars,
480 unsigned expanded_live_range_start)
482 std::vector<local_variable_with_holest *> sorted_by_startpc(
483 merge_vars.begin(), merge_vars.end());
484 std::sort(sorted_by_startpc.begin(), sorted_by_startpc.end(),
lt_startpc);
488 expanded_live_range_start,
489 sorted_by_startpc[0]->var.start_pc);
490 for(std::size_t idx=0; idx<sorted_by_startpc.size()-1; ++idx)
494 sorted_by_startpc[idx]->var.start_pc+sorted_by_startpc[idx]->
var.
length,
495 sorted_by_startpc[idx+1]->var.start_pc);
508 const std::set<local_variable_with_holest *> &merge_vars,
510 std::ostream &debug_out)
516 unsigned found_dominator=
526 for(
auto v : merge_vars)
528 if(v->var.start_pc+v->var.length>last_pc)
529 last_pc=v->var.start_pc+v->var.length;
534 merge_into.
var.
length=last_pc-found_dominator;
537 debug_out <<
"Merged " << merge_vars.size() <<
" variables named " 538 << merge_into.
var.
name <<
"; new live range " 544 for(
auto &v : merge_vars)
561 local_variable_table_with_holest::iterator firstvar,
562 local_variable_table_with_holest::iterator varlimit,
569 std::vector<local_variable_with_holest *> live_variable_at_address;
579 live_variable_at_address,
588 for(
auto &kv : predecessor_map)
590 std::set<local_variable_with_holest *> closed_preds;
592 kv.second=std::move(closed_preds);
597 std::vector<local_variable_with_holest *> topsorted_vars;
598 for(
auto it=firstvar, itend=varlimit; it!=itend; ++it)
599 topsorted_vars.push_back(&*it);
601 std::sort(topsorted_vars.begin(), topsorted_vars.end(), comp);
604 for(
auto merge_into : topsorted_vars)
607 if(merge_into->var.length==0)
610 auto findit=predecessor_map.find(merge_into);
612 if(findit==predecessor_map.end())
615 const auto &merge_vars=findit->second;
616 INVARIANT(merge_vars.size()>=2,
"merging requires at least 2 variables");
634 local_variable_table_with_holest::iterator &it1,
635 local_variable_table_with_holest::iterator &it2,
636 local_variable_table_with_holest::iterator itend)
645 auto index=it2->var.index;
646 while(it2!=itend && it2->var.index==index)
663 std::sort(vars.begin(), vars.end(),
lt_index);
667 auto it1=vars.begin();
669 auto itend=vars.end();
679 std::vector<local_variable_with_holest> &vars_with_holes)
682 for(
size_t i=0; i<(vars_with_holes.size()-toremove); ++i)
684 auto &v=vars_with_holes[i];
689 if(i!=vars_with_holes.size()-toremove)
690 std::swap(v, vars_with_holes[vars_with_holes.size()-toremove]);
697 vars_with_holes.resize(vars_with_holes.size()-toremove);
713 dominator_analysis(dominator_args);
716 debug() <<
"jcm: setup-local-vars: m.is_static " 718 debug() <<
"jcm: setup-local-vars: lv arg slots " 720 debug() <<
"jcm: setup-local-vars: lvt size " 727 std::vector<local_variable_with_holest> vars_with_holes;
742 catch(
const char *message)
744 warning() <<
"Bytecode -> codet translation error: " << message <<
eom 745 <<
"This is probably due to an unexpected LVT, " 746 <<
"falling back to translation without LVT" <<
eom;
761 for(
const auto &v : vars_with_holes)
767 debug() <<
"jcm: setup-local-vars: merged variable: idx " << v.var.index
768 <<
" name " << v.var.name <<
" v.var.descriptor '" 769 << v.var.descriptor <<
"' holes " << v.holes.size() <<
eom;
775 std::ostringstream id_oss;
776 id_oss <<
method_id <<
"::" << v.var.start_pc <<
"::" << v.var.name;
779 result.set(ID_C_base_name, v.var.name);
785 auto &newv=
variables[v.var.index].back();
787 newv.start_pc=v.var.start_pc;
788 newv.length=v.var.length;
789 newv.holes=std::move(v.holes);
793 new_symbol.
name=identifier;
797 new_symbol.
mode=ID_java;
820 size_t length=var.length;
821 if(address>=start_pc && address<(start_pc+length))
823 bool found_hole=
false;
824 for(
auto &hole : var.holes)
825 if(address>=hole.start_pc && address<(hole.start_pc+hole.length))
839 size_t list_length=var_list.size();
840 var_list.resize(list_length+1);
841 var_list[list_length].start_pc=0;
842 var_list[list_length].length=std::numeric_limits<size_t>::max();
843 return var_list[list_length];
The type of an expression.
irep_idt name
The unique identifier.
static void merge_variable_table_entries(local_variable_with_holest &merge_into, const std::set< local_variable_with_holest *> &merge_vars, const java_cfg_dominatorst &dominator_analysis, std::ostream &debug_out)
See above.
java_bytecode_convert_methodt::address_mapt address_mapt
A generic directed graph with a parametric node type.
JAVA Bytecode Language Conversion.
const std::string & id2string(const irep_idt &d)
void find_initializers(local_variable_table_with_holest &vars, const address_mapt &amap, const java_cfg_dominatorst &doms)
See find_initializers_for_slot above for more detail.
std::pair< const methodt &, const address_mapt & > method_with_amapt
irep_idt method_id
Fully qualified name of the method under translation.
irep_idt mode
Language mode.
unsigned get_last_node(const method_with_amapt &args) const
static void maybe_add_hole(local_variable_with_holest &var, unsigned from, unsigned to)
See above.
static unsigned get_common_dominator(const std::set< local_variable_with_holest *> &merge_vars, const java_cfg_dominatorst &dominator_analysis)
Used to find out where to put a variable declaration that subsumes several variable live ranges...
java_bytecode_convert_methodt::method_with_amapt method_with_amapt
void setup_local_variables(const methodt &m, const address_mapt &amap)
See find_initializers_for_slot above for more detail.
irep_idt pretty_name
Language-specific display name.
Symbol table entry.This is a symbol in the symbol table, stored in an object of type symbol_tablet...
#define CHECK_RETURN(CONDITION)
static mstreamt & eom(mstreamt &m)
bool is_parameter(const local_variablet &v)
Returns true iff the slot index of the local variable of a method (coming from the LVT) is a paramete...
std::map< unsigned, converted_instructiont > address_mapt
expanding_vectort< variablest > variables
static bool is_store_to_slot(const java_bytecode_convert_methodt::instructiont &inst, unsigned slotidx)
See above.
#define INVARIANT(CONDITION, REASON)
mstreamt & warning() const
std::vector< local_variable_with_holest > local_variable_table_with_holest
unsigned get_first_node(const method_with_amapt &args) const
unsigned nodes_empty(const method_with_amapt &args) const
typet java_type_from_string(const std::string &src, const std::string &class_name_prefix)
Transforms a string representation of a Java type into an internal type representation thereof...
static void walk_to_next_index(local_variable_table_with_holest::iterator &it1, local_variable_table_with_holest::iterator &it2, local_variable_table_with_holest::iterator itend)
Walk a vector, a contiguous block of entries with equal slot index at a time.
std::vector< holet > holes
java_bytecode_convert_methodt::holet holet
static void gather_transitive_predecessors(local_variable_with_holest *start, const predecessor_mapt &predecessor_map, std::set< local_variable_with_holest *> &result)
See above start: Variable to find the predecessors of predecessor_map: Map from local variables to se...
static void populate_live_range_holes(local_variable_with_holest &merge_into, const std::set< local_variable_with_holest *> &merge_vars, unsigned expanded_live_range_start)
See above.
std::map< local_variable_with_holest *, std::set< local_variable_with_holest * > > predecessor_mapt
procedure_local_cfg_baset()
#define PRECONDITION(CONDITION)
static bool lt_startpc(const local_variable_with_holest *a, const local_variable_with_holest *b)
const constant_exprt & to_constant_expr(const exprt &expr)
Cast a generic exprt to a constant_exprt.
static void populate_variable_address_map(local_variable_table_with_holest::iterator firstvar, local_variable_table_with_holest::iterator varlimit, std::vector< local_variable_with_holest *> &live_variable_at_address)
See above.
java_bytecode_convert_methodt::local_variable_with_holest local_variable_with_holest
unsigned safe_string2unsigned(const std::string &str, int base)
java_bytecode_convert_methodt::java_cfg_dominatorst java_cfg_dominatorst
typet type
Type of symbol.
message_handlert & get_message_handler()
static void cleanup_var_table(std::vector< local_variable_with_holest > &vars_with_holes)
See above.
std::vector< variablet > variablest
bool operator()(local_variable_with_holest *a, local_variable_with_holest *b) const
mstreamt & result() const
mstreamt & status() const
irep_idt base_name
Base (non-scoped) name.
const variablet & find_variable_for_slot(size_t address, variablest &var_list)
See above.
void add_edge(node_indext a, node_indext b)
void find_initializers_for_slot(local_variable_table_with_holest::iterator firstvar, local_variable_table_with_holest::iterator varlimit, const address_mapt &amap, const java_cfg_dominatorst &doms)
Given a sequence of users of the same local variable slot, this figures out which ones are related by...
symbol_table_baset & symbol_table
Expression to hold a symbol (variable)
static bool lt_index(const local_variable_with_holest &a, const local_variable_with_holest &b)
local_variable_tablet local_variable_table
bool add(const symbolt &symbol)
Add a new symbol to the symbol table.
is_predecessor_oft(const predecessor_mapt &_order)
unsigned slots_for_parameters
Number of local variable slots used by the JVM to pass parameters upon invocation of the method under...
std::map< unsigned, unsigned > entry_mapt
static void populate_predecessor_map(local_variable_table_with_holest::iterator firstvar, local_variable_table_with_holest::iterator varlimit, const std::vector< local_variable_with_holest *> &live_variable_at_address, const address_mapt &amap, predecessor_mapt &predecessor_map, message_handlert &msg_handler)
Populates the predecessor_map with a graph from local variable table entries to their predecessors (t...
java_bytecode_convert_methodt::local_variable_table_with_holest local_variable_table_with_holest
void push_back(const T &t)
void operator()(const method_with_amapt &args)
const predecessor_mapt & order