31 public grapht<cfg_base_nodet<T, unsigned> >
41 const auto &method=args.first;
42 const auto &amap=args.second;
43 for(
const auto &inst : amap)
46 entry_map[inst.first]=this->
add_node();
48 (*this)[entry_map[inst.first]].PC=inst.first;
51 for(
const auto &inst : amap)
53 for(
auto succ : inst.second.successors)
54 this->
add_edge(entry_map.at(inst.first), entry_map.at(succ));
58 for(
const auto &table_entry : method.exception_table)
60 auto findit=amap.find(table_entry.start_pc);
61 assert(findit!=amap.end() &&
62 "Exception table entry doesn't point to an instruction?");
63 for(; findit->first<table_entry.end_pc; ++findit)
69 if(succit==amap.end())
71 const auto &thisinst=findit->second;
72 if(thisinst.successors.size()==1 &&
73 thisinst.successors.back()==succit->first)
76 entry_map.at(findit->first),
77 entry_map.at(table_entry.handler_pc));
85 return args.second.begin()->first;
89 return (--args.second.end())->first;
93 return args.second.empty();
128 std::set<local_variable_with_holest *> >
141 auto findit=order.find(a);
142 if(findit==order.end())
144 return findit->second.count(b)>0;
158 std::set<local_variable_with_holest*> &result)
160 if(!result.insert(start).second)
162 auto findit=predecessor_map.find(start);
163 if(findit==predecessor_map.end())
165 for(
const auto pred : findit->second)
179 if(!(prevstatement.size()>=1 && prevstatement.substr(1, 5)==
"store"))
182 unsigned storeslotidx;
183 if(inst.
args.size()==1)
186 const auto &arg=inst.
args[0];
193 assert(prevstatement[6]==
'_' && prevstatement.size()==8);
194 std::string storeslot(1, prevstatement[7]);
195 assert(isdigit(storeslot[0]));
198 return storeslotidx==slotidx;
212 var.
holes.push_back({from, to-from});
223 local_variable_table_with_holest::iterator firstvar,
224 local_variable_table_with_holest::iterator varlimit,
225 std::vector<local_variable_with_holest *> &live_variable_at_address)
227 for(
auto it=firstvar, itend=varlimit; it!=itend; ++it)
229 if(it->var.start_pc+it->var.length>live_variable_at_address.size())
230 live_variable_at_address.resize(it->var.start_pc+it->var.length);
232 for(
unsigned idx=it->var.start_pc,
233 idxlim=it->var.start_pc+it->var.length;
237 assert((!live_variable_at_address[idx]) &&
"Local variable table clash?");
238 live_variable_at_address[idx]=&*it;
258 local_variable_table_with_holest::iterator firstvar,
259 local_variable_table_with_holest::iterator varlimit,
260 const std::vector<local_variable_with_holest *> &live_variable_at_address,
266 for(
auto it=firstvar, itend=varlimit; it!=itend; ++it)
269 if(it->var.start_pc==0)
273 unsigned end_pc=it->var.start_pc+it->var.length;
274 auto amapit=amap.find(end_pc);
275 assert(amapit!=amap.begin());
276 auto old_amapit=amapit;
278 if(old_amapit==amap.end())
281 end_pc>amapit->first &&
282 "Instruction live range doesn't align to instruction boundary?");
286 unsigned new_start_pc=it->var.start_pc;
287 for(; amapit->first>=it->var.start_pc; --amapit)
289 for(
auto pred : amapit->second.predecessors)
292 (pred<live_variable_at_address.size() ?
293 live_variable_at_address[pred] :
305 auto inst_before_this=amapit;
306 assert(inst_before_this!=amap.begin());
308 if(amapit->first!=it->var.start_pc || inst_before_this->first!=pred)
313 msg.
warning() <<
"Local variable table: ignoring flow from " 314 <<
"out of range for " << it->var.name <<
' ' 315 << pred <<
" -> " << amapit->first
320 *(inst_before_this->second.source),
323 throw "local variable table: didn't find initialising store";
329 if(pred_var->var.name!=it->var.name ||
330 pred_var->var.signature!=it->var.signature)
335 msg.
warning() <<
"Local variable table: ignoring flow from " 336 <<
"clashing variable for " 337 << it->var.name <<
' ' << pred <<
" -> " 343 predecessor_map[&*it].insert(pred_var);
350 it->var.length+=(it->var.start_pc-new_start_pc);
351 it->var.start_pc=new_start_pc;
364 const std::set<local_variable_with_holest*> &merge_vars,
367 assert(!merge_vars.empty());
369 unsigned first_pc=UINT_MAX;
370 for(
auto v : merge_vars)
372 if(v->var.start_pc<first_pc)
373 first_pc=v->var.start_pc;
376 std::vector<unsigned> candidate_dominators;
377 for(
auto v : merge_vars)
379 const auto &dominator_nodeidx=
381 const auto &this_var_doms=
382 dominator_analysis.
cfg[dominator_nodeidx].dominators;
383 for(
const auto this_var_dom : this_var_doms)
384 if(this_var_dom<=first_pc)
385 candidate_dominators.push_back(this_var_dom);
387 std::sort(candidate_dominators.begin(), candidate_dominators.end());
392 for(
auto domit=candidate_dominators.rbegin(),
393 domitend=candidate_dominators.rend();
399 while(domit!=domitend && *domit==dom)
404 assert(repeats<=merge_vars.size());
405 if(repeats==merge_vars.size())
409 throw "variable live ranges with no common dominator?";
422 const std::set<local_variable_with_holest *> &merge_vars,
423 unsigned expanded_live_range_start)
425 std::vector<local_variable_with_holest *> sorted_by_startpc(
426 merge_vars.begin(), merge_vars.end());
427 std::sort(sorted_by_startpc.begin(), sorted_by_startpc.end(),
lt_startpc);
431 expanded_live_range_start,
432 sorted_by_startpc[0]->var.start_pc);
433 for(
unsigned idx=0; idx<sorted_by_startpc.size()-1; ++idx)
437 sorted_by_startpc[idx]->var.start_pc+sorted_by_startpc[idx]->
var.
length,
438 sorted_by_startpc[idx+1]->var.start_pc);
451 const std::set<local_variable_with_holest *> &merge_vars,
453 std::ostream &debug_out)
459 unsigned found_dominator=
469 for(
auto v : merge_vars)
471 if(v->var.start_pc+v->var.length>last_pc)
472 last_pc=v->var.start_pc+v->var.length;
477 merge_into.
var.
length=last_pc-found_dominator;
480 debug_out <<
"Merged " << merge_vars.size() <<
" variables named " 481 << merge_into.
var.
name <<
"; new live range " 487 for(
auto &v : merge_vars)
504 local_variable_table_with_holest::iterator firstvar,
505 local_variable_table_with_holest::iterator varlimit,
512 std::vector<local_variable_with_holest *> live_variable_at_address;
522 live_variable_at_address,
525 get_message_handler());
531 for(
auto &kv : predecessor_map)
533 std::set<local_variable_with_holest *> closed_preds;
535 kv.second=std::move(closed_preds);
540 std::vector<local_variable_with_holest *> topsorted_vars;
541 for(
auto it=firstvar, itend=varlimit; it!=itend; ++it)
542 topsorted_vars.push_back(&*it);
544 std::sort(topsorted_vars.begin(), topsorted_vars.end(), comp);
547 for(
auto merge_into : topsorted_vars)
550 if(merge_into->var.length==0)
553 auto findit=predecessor_map.find(merge_into);
555 if(findit==predecessor_map.end())
558 const auto &merge_vars=findit->second;
559 assert(merge_vars.size()>=2);
577 local_variable_table_with_holest::iterator &it1,
578 local_variable_table_with_holest::iterator &it2,
579 local_variable_table_with_holest::iterator itend)
588 auto index=it2->var.index;
589 while(it2!=itend && it2->var.index==index)
606 std::sort(vars.begin(), vars.end(),
lt_index);
610 auto it1=vars.begin();
612 auto itend=vars.end();
615 find_initialisers_for_slot(it1, it2, amap, dominator_analysis);
622 std::vector<local_variable_with_holest> &vars_with_holes)
625 for(
size_t i=0; i<(vars_with_holes.size()-toremove); ++i)
627 auto &v=vars_with_holes[i];
632 if(i!=vars_with_holes.size()-toremove)
633 std::swap(v, vars_with_holes[vars_with_holes.size()-toremove]);
640 vars_with_holes.resize(vars_with_holes.size()-toremove);
656 dominator_analysis(dominator_args);
660 std::vector<local_variable_with_holest> vars_with_holes;
662 vars_with_holes.push_back({v, {}});
665 find_initialisers(vars_with_holes, amap, dominator_analysis);
678 for(
const auto &v : vars_with_holes)
680 if(v.var.start_pc==0)
684 std::ostringstream id_oss;
685 id_oss << method_id <<
"::" << v.var.start_pc <<
"::" << v.var.name;
688 result.set(ID_C_base_name, v.var.name);
690 variables[v.var.index].push_back(
variablet());
691 auto &newv=variables[v.var.index].back();
692 newv.symbol_expr=result;
693 newv.start_pc=v.var.start_pc;
694 newv.length=v.var.length;
695 newv.holes=std::move(v.holes);
698 new_symbol.
name=identifier;
702 new_symbol.
mode=ID_java;
707 symbol_table.add(new_symbol);
725 size_t length=var.length;
726 if(address>=start_pc && address<(start_pc+length))
728 bool found_hole=
false;
729 for(
auto &hole : var.holes)
730 if(address>=hole.start_pc && address<(hole.start_pc+hole.length))
744 size_t list_length=var_list.size();
745 var_list.resize(list_length+1);
746 var_list[list_length].start_pc=0;
747 var_list[list_length].length=std::numeric_limits<size_t>::max();
748 return var_list[list_length];
void find_initialisers_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...
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)
std::pair< const methodt &, const address_mapt & > method_with_amapt
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_initialisers_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)
std::map< unsigned, converted_instructiont > address_mapt
static bool is_store_to_slot(const java_bytecode_convert_methodt::instructiont &inst, unsigned slotidx)
See above.
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)
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()
static bool lt_startpc(const local_variable_with_holest *a, const local_variable_with_holest *b)
void find_initialisers(local_variable_table_with_holest &vars, const address_mapt &amap, const java_cfg_dominatorst &doms)
See find_initialisers_for_slot above for more detail.
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.
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
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)
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
is_predecessor_oft(const predecessor_mapt &_order)
std::map< unsigned, unsigned > entry_mapt
const constant_exprt & to_constant_expr(const exprt &expr)
Cast a generic exprt to a constant_exprt.
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)
Usually a live variable range begins with a store instruction initialising the relevant local variabl...
java_bytecode_convert_methodt::local_variable_table_with_holest local_variable_table_with_holest
void operator()(const method_with_amapt &args)
const predecessor_mapt & order