Polaris: ControlRangeDict.cc Source File

ControlRangeDict.cc Go to the documentation of this file. /// /// /// \file ControlRangeDict.cc /// #include "../Program.h" #include "../ProgramUnit.h" #include "../Statement/Statement.h" #include "../Symbol/Symbol.h" #include "../Symtab.h" #include "../Expression/Expression.h" #include "../Directive/Assertion.h" #include "../utilities/switches_util.h" #include "../utilities/expression_util.h" #include "../utilities/equivalence_util.h" #include "../Array.h" #include "../IntSet.h" #include "../Timer.h" #include "../p-assert.h" #include "ControlRangeDict.h" #include "PropCtrlRangeWS.h" #include "RangeExpr.h" #include "range_util.h" #include "range_dict_util.h" //#include "PropCtrlRangeWS.cc" static unsigned int _pass_tag; /// ... Pass tag associated with this pass static int _debug_level = 0; /// init_workspaces /// Initialize the workspaces for each statement in the program. /// Note: A lot of the initialization for eliminate_dead_code are hidden /// in the constructor for PropCtrlRangeWS. static void _init_workspaces(ProgramUnit &pgm) { Iterator<Statement> iter = pgm.stmts().iterator(); for ( ; iter.valid(); ++iter) { PropCtrlRangeWS *my_ws = new PropCtrlRangeWS(_pass_tag, iter.current()); iter.current().work_stack().push(my_ws); } } /// get_workspace /// Get the workspace for the given statement. static PropCtrlRangeWS & _get_workspace(const Statement &stmt) { WorkSpace *ws = stmt.work_stack().top_ref(_pass_tag); p_assert(ws, "Statement doesn't have a PropCtrlRangeWS."); return * (PropCtrlRangeWS *) ws; } /// dump_workspaces /// Dump out the data inside all of the workspaces of the program static void _dump_workspaces(ostream &o, const ProgramUnit &pgm) { Iterator<Statement> iter = pgm.stmts().iterator(); for ( ; iter.valid(); ++iter) { iter.current().structures_OK(); o << iter.current().tag() << ": "; iter.current().print_debug(o, 0); o << endl; _get_workspace(iter.current()).print(o); o << endl; } } /// _make_nonlocals_modified_at_calls /// Make all non-local variables be marked as potentially modified for all /// call statements and all statements containing function calls. static void _make_nonlocals_modified_at_calls(ProgramUnit &pgm) { /// ... Calculate the set of non-local variables. RefSet<Symbol> non_local_set; DictionaryIter<Symbol> sym_iter = pgm.symtab().iterator(); for ( ; sym_iter.valid(); ++sym_iter) { Symbol &symbol = sym_iter.current(); if (symbol.sym_class() == VARIABLE_CLASS && (symbol.formal() == IS_FORMAL || symbol.common_ref())) { if (symbol.type().data_type() == INTEGER_TYPE) non_local_set.ins(symbol); /// ... Also place any aliased variables in the set. RefSet<Symbol> *aliases = equiv_aliases(symbol); if (aliases) { Iterator<Symbol> alias_iter = *aliases; for ( ; alias_iter.valid(); ++alias_iter) { Symbol &alias_symbol = alias_iter.current(); if (alias_symbol.type().data_type() == INTEGER_TYPE) non_local_set.ins(alias_symbol); } delete aliases; } } } /// ... Add the non-local variables to the mod_set of all statements that /// ... are either call statements or contain function calls. Iterator<Statement> stmt_iter = pgm.stmts().iterator(); for ( ; stmt_iter.valid(); ++stmt_iter) { Statement &stmt = stmt_iter.current(); if (stmt.stmt_class() == CALL_STMT || contains_func_call(stmt)) { RefSet<Symbol> &mod_set = _get_workspace(stmt).mod_set; RefSet<Symbol> *maymods = stmt_maymods(stmt); if (maymods) { Iterator<Expression> act_iter = stmt.act_refs(); for ( ; act_iter.valid(); ++act_iter) { Symbol *var_ref = act_iter.current().base_variable_ref(); if (var_ref) mod_set.del(*var_ref); } if (stmt.stmt_class() == ASSIGNMENT_STMT) { Symbol *var_ref = stmt.lhs().base_variable_ref(); if (var_ref) mod_set.ins(*var_ref); } Iterator<Symbol> nl_iter = *maymods; for ( ; nl_iter.valid(); ++nl_iter) mod_set.ins(nl_iter.current()); delete maymods; } else { Iterator<Symbol> nl_iter = non_local_set; for ( ; nl_iter.valid(); ++nl_iter) mod_set.ins(nl_iter.current()); } } } } /// _calc_toporder /// Calculate toporder for the flow graph. Essentially, this algorithm /// performs a topological sort on the flow graph, ignoring back /// edges. static void _calc_toporder1(Statement &stmt, int &toporder) { PropCtrlRangeWS &my_ws = _get_workspace(stmt); if (! my_ws.visited()) { my_ws.visited(1); Iterator<Statement> succ_iter = stmt.succ(); for ( ; succ_iter.valid(); ++succ_iter) _calc_toporder1(succ_iter.current(), toporder); my_ws.toporder(toporder--); } } static void _calc_toporder(ProgramUnit &pgm, Array<Statement *> &toporder_to_stmt) { /// ... Calculate the topological order for each statement int toporder = pgm.stmts().entries() - 1; if (toporder >= 0) { Iterator<Statement> entry_iter = pgm.stmts().iterate_entry_points(); for ( ; entry_iter.valid(); ++entry_iter) _calc_toporder1(entry_iter.current(), toporder); p_assert(toporder >= -1, "_calc_toporder visited a stmt more than once."); } /// ... Initialize toporder_to_stmt toporder_to_stmt.resize(pgm.stmts().entries()); for (int i = 0; i <= toporder; ++i) toporder_to_stmt[i] = 0; Iterator<Statement> iter = pgm.stmts().iterator(); for ( ; iter.valid(); ++iter) { int stmt_toporder = _get_workspace(iter.current()).toporder(); if (stmt_toporder >= 0) toporder_to_stmt[stmt_toporder] = &iter.current(); } } /// is_else_branch /// Return true if the control flow edge between statements pred and succ /// corresponds to the else branch of an IF statement. /// Note: the exit branch of a DO statement is assumed to be an else /// branch. static bool _is_else_branch(const Statement &pred, const Statement &succ) { return ((pred.stmt_class() == IF_STMT || pred.stmt_class() == ELSEIF_STMT || pred.stmt_class() == DO_STMT) && pred.succ().entries() == 2 && pred.next_ref() != &succ); } /// intersect_range_maps /// Intersect the ranges of the two variable to range set maps. void _intersect_range_maps(Map< Symbol, RefSet<Expression> > &range_map, const Map< Symbol, RefSet<Expression> > &inter_map) { KeyIterator<Symbol, RefSet<Expression> > rmap_iter = range_map; RefSet<Symbol> dead_vars; for ( ; rmap_iter.valid(); ++rmap_iter) { const RefSet<Expression> *inter_ranges = inter_map.find_ref(rmap_iter.current_key()); if (! inter_ranges) rmap_iter.current_data().clear(); else { Mutator<Expression> ranges_iter = rmap_iter.current_data(); for ( ; ranges_iter.valid(); ++ranges_iter) if (! inter_ranges->member(ranges_iter.current())) ranges_iter.del(); } if (rmap_iter.current_data().entries() == 0) dead_vars.ins(rmap_iter.current_key()); } Iterator<Symbol> dead_iter = dead_vars; for ( ; dead_iter.valid(); ++dead_iter) range_map.del(dead_iter.current()); } /// range_maps_equal /// Return true if the two range maps are equal static bool _range_maps_equal(const Map< Symbol, RefSet<Expression> > &range_map1, const Map< Symbol, RefSet<Expression> > &range_map2) { if (range_map1.entries() != range_map2.entries()) return false; KeyIterator<Symbol, RefSet<Expression> > rmap_iter = range_map1; for ( ; rmap_iter.valid(); ++rmap_iter) { const RefSet<Expression> *var_ranges2 = range_map2.find_ref(rmap_iter.current_key()); if (! var_ranges2 || ! (rmap_iter.current_data() == *var_ranges2)) return false; } return true; } /// put_succ_on_work_list /// Put all of my successors on the work list. static void _put_succ_on_work_list(IntSet &work_list, Statement &stmt) { Iterator<Statement> succ_iter = stmt.succ(); for ( ; succ_iter.valid(); ++succ_iter) work_list.ins(_get_workspace(succ_iter.current()).toporder()); } /// iterate_to_fixed_point /// Propagate the constants contained in the statement's const_maps until /// a fixed point is reached. static void _iterate_to_fixed_point(ProgramUnit &pgm, const Array<Statement *> &toporder_to_stmt) { /// ... List of statements that need to be updated. IntSet work_list(toporder_to_stmt.entries()); /// ... Mark all variables for entry statements as non-const and put all /// ... entries on the work list. Iterator<Statement> entry_iter = pgm.stmts().iterate_entry_points(); for ( ; entry_iter.valid(); ++entry_iter) work_list.ins(_get_workspace(entry_iter.current()).toporder()); /// ... Iterate until there are no more elements on the work list while (work_list.entries() > 0) { /// ... Visit each statement in the work list, in topological order for (int stmt_num = work_list.first(); stmt_num != -1; stmt_num = work_list.next(stmt_num)) { Statement &curr = *toporder_to_stmt[stmt_num]; work_list.del(stmt_num); PropCtrlRangeWS &curr_ws = _get_workspace(curr); curr_ws.incr_num_visits(); bool changed = false; /// ... Generate the new live variable set for the end of the statement. Map< Symbol, RefSet<Expression> > new_ranges; Iterator<Statement> pred_iter = curr.pred(); bool is_first_pred = true; for ( ; pred_iter.valid(); ++pred_iter) { PropCtrlRangeWS &pred_ws = _get_workspace(pred_iter.current()); if (pred_ws.num_visits() > 0) if (is_first_pred) { is_first_pred = false; if (_is_else_branch(pred_iter.current(), curr)) new_ranges = pred_ws.out_else_ranges; else new_ranges = pred_ws.out_ranges; } else if (_is_else_branch(pred_iter.current(), curr)) _intersect_range_maps(new_ranges, pred_ws.out_else_ranges); else _intersect_range_maps(new_ranges, pred_ws.out_ranges); } if (curr_ws.num_visits() == 1 || ! _range_maps_equal(new_ranges, curr_ws.in_ranges)) { /// ... New entering live variable set differs from the old /// ... one. So update the entering and exiting live variable /// ... sets for the statement. if (_debug_level >= 20) { cout << "! Statement "; curr.print_debug(cout, 0); cout << " was visited and updated.\n"; } curr_ws.in_ranges = new_ranges; changed = curr_ws.update_out_ranges(); if (changed || curr_ws.num_visits() == 1) { /// ... Exiting live var set has changed, so place /// ... the statement's predecessors on the work list so /// ... that they can update their live variable sets /// ... with my live var set. _put_succ_on_work_list(work_list, curr); } if (_debug_level >= 30) { curr_ws.print(cout); cout << endl; } } } } } /// _add_safe_cond_ranges /// Add any SafeCondition ranges to the PropCtrlRangeWS in_ranges on each statement /// within a loop body. void ControlRangeDict::_add_safe_cond_ranges(const ProgramUnit &pgm) { Iterator<Statement> iter = pgm.stmts().iterator(); for ( ; iter.valid(); ++iter) { Statement &stmt = iter.current(); if (stmt.stmt_class() == DO_STMT) { Iterator<Assertion> assert_iter = stmt.assertions(); for ( ; assert_iter.valid(); ++assert_iter) { const Assertion &assert = assert_iter.current(); if (assert.type() == AS_SAFE_CONDITION) { for (Iterator<Statement> do_iter = pgm.stmts().iterate_loop_body(&stmt); do_iter.valid(); ++do_iter) { Statement & body_stmt = do_iter.current(); PropCtrlRangeWS &ws = _get_workspace(body_stmt); Iterator<Expression> arg_iter = assert.arg_list_guarded(); for ( ; arg_iter.valid(); ++arg_iter) { Map< Symbol, Set<Expression> > *assert_ranges = extract_ranges(arg_iter.current()); KeyIterator<Symbol, Set<Expression> > ar_iter = *assert_ranges; for ( ; ar_iter.valid(); ++ar_iter) { const Symbol &var = ar_iter.current_key(); RefSet<Expression> *var_ranges = ws.in_ranges.find_ref(var); if (! var_ranges) { RefSet<Expression> *set = new RefSet<Expression>; for (Iterator<Expression> eiter = ar_iter.current_data(); eiter.valid(); ++eiter) { set->ins(eiter.current()); } ws.in_ranges.ins(var, set); } else { Iterator<Expression> range_iter = ar_iter.current_data(); for ( ; range_iter.valid(); ++range_iter) var_ranges->ins(range_iter.current()); } } } } } } } } } /// generate_map /// Generate the mapping from statement/variable pairs to ranges from /// the range information contained in my WorkSpaces. void ControlRangeDict::_generate_map(const ProgramUnit &pgm) { Iterator<Statement> iter = pgm.stmts().iterator(); for ( ; iter.valid(); ++iter) { Statement &stmt = iter.current(); PropCtrlRangeWS &ws = _get_workspace(stmt); RefMap<Symbol, Expression> *stmt_ranges = _pgm_ranges.find_ref(stmt.tag()); if (! stmt_ranges) { stmt_ranges = new RefMap<Symbol, Expression>; _pgm_ranges.ins(stmt.tag(), stmt_ranges); } PropCtrlRangeWS *prev_ws = 0; if (stmt.prev_ref()) prev_ws = &_get_workspace(*stmt.prev_ref()); if (prev_ws && _range_maps_equal(prev_ws->in_ranges, ws.in_ranges)) { /// ... Optimization. If my input range map is identical to the /// ... previous statement's input range map, then my computed /// ... variable to range map would be identical to the previous /// ... statement's. So, in such a case, I can just copy the /// ... previous statement's variable to range map. *stmt_ranges = _pgm_ranges[stmt.prev_ref()->tag()]; } else { StmtRanges ranges(symtab()); KeyIterator<Symbol, RefSet<Expression> > rmap_iter = ws.in_ranges; for ( ; rmap_iter.valid(); ++rmap_iter) { if (rmap_iter.current_data().entries() > 0) { Iterator<Expression> range_iter = rmap_iter.current_data(); Expression *range_expr = range_iter.current().clone(); ++range_iter; if (range_iter.valid()) { /// ... Intersect all the ranges in the given set to form /// ... a single range. RangeExpr *range = convert_to_range(range_expr); for ( ; range_iter.valid(); ++range_iter) { RangeExpr *inter_range = convert_to_range(range_iter.current().clone()); range->lb(max_expr(range->grab_lb(), inter_range->grab_lb(), symtab())); range->ub(min_expr(range->grab_ub(), inter_range->grab_ub(), symtab())); delete inter_range; } if (range->has_lb() && range->lb() == range->ub()) { range_expr = range->grab_lb(); delete range; } else range_expr = range; } range_expr = simplify(range_expr); ranges.set_range(rmap_iter.current_key(), range_expr); } } ranges.simplify_min_max(); /// ... Insert the computed ranges into stmt_ranges. for (rmap_iter.reset(); rmap_iter.valid(); ++rmap_iter) { if (rmap_iter.current_data().entries() > 0) { Expression *range_expr = ranges.grab_range(rmap_iter.current_key()); p_assert(range_expr, "ControlRangeDict:_generate_ranges(): Lost a range."); /// ... Add the given range to range_values, making sure /// ... that there are no duplicate expressions in range_values. const Expression &range_ref = _range_values.ins(range_expr); // Add the range to the statement/variable to range map. stmt_ranges->ins(rmap_iter.current_key(), range_ref); } } } } } /// ControlRangeDict ControlRangeDict::ControlRangeDict(ProgramUnit &pgm, int debug GIV(0)) : RangeDict(pgm.symtab()) { if (switch_value("range_off") > 1) return; /// ... An array that maps integers to statements. Array<Statement *> toporder_to_stmt; _debug_level = debug; Timer tot_timer; Timer timer; /// ... Initialize remove_min_max_var_conflicts(pgm.symtab()); ::_pass_tag = create_pass_tag(); _init_workspaces(pgm); if (switch_value("pc_call_mods") != 1) _make_nonlocals_modified_at_calls(pgm); _calc_toporder(pgm, toporder_to_stmt); if (_debug_level > 0) { cout << "! Initialization: " << timer << endl; timer.reset(); } /// ... Iteratively propagate the constants throughout the program until a /// ... fixed point is reached. _iterate_to_fixed_point(pgm, toporder_to_stmt); if (_debug_level > 0) { cout << "! Iterating to fixed point: " << timer << endl; timer.reset(); } /// ... Dump ranges from the SafeCondition assertions into the PropCtrlRangeWS /// ... on each statement of a loop body. This may change in the future with /// ... the demand-driven structure. We may want to keep the SafeCondition /// ... assertions separate, and use them only if we can't prove a loop parallel /// ... with the "known" ranges. _add_safe_cond_ranges(pgm); /// ... Build the map of variable assertions for each statement.. _generate_map(pgm); if (_debug_level > 0) cout << "! Generating stmt_ranges: " << timer << endl; if (_debug_level >= 10) _dump_workspaces(cout, pgm); /// ... Clean up pgm.clean_workspace(::_pass_tag); if (_debug_level > 0) { cout << "! Total time: " << tot_timer << endl; cout << "! Number of statements: " << pgm.stmts().entries() << endl; } } /// Destructor ControlRangeDict::~ControlRangeDict() { /// ... nothing to do } /// set_range void ControlRangeDict::_set_range(const Symbol & /* var */, const Statement &/* stmt */, Expression * /* range */) { p_abort("Ranges cannot be modified in a ControlRangeDict object."); } /// del_range void ControlRangeDict::_del_range(const Symbol & /* var */, const Statement & /* stmt */) { p_abort("Ranges cannot be modified in a ControlRangeDict object."); } /// get_range_ref const Expression * ControlRangeDict::_get_range_ref(const Symbol &var, const Statement &stmt) { RefMap<Symbol, Expression> *stmt_ranges = _pgm_ranges.find_ref(stmt.tag()); if (stmt_ranges) return stmt_ranges->find_ref(var); return 0; } /// print void ControlRangeDict::print(ostream & o) const { o << "{"; o << "_range_values={" << _range_values << "}"; o << "_pgm_ranges={"; KeyIterator< String, RefMap<Symbol, Expression> > stmt_iter = _pgm_ranges; for ( ; stmt_iter.valid(); ++stmt_iter) { o << stmt_iter.current_key() << ": {"; KeyIterator<Symbol, Expression> var_iter = stmt_iter.current_data(); for ( ; var_iter.valid(); ++var_iter) o << var_iter.current_key().name_ref() << var_iter.current_data() << ", "; o << "}, "; } o << "}}"; } /// pretty_print void ControlRangeDict::pretty_print(ostream & o, const Statement &stmt) const { const RefMap<Symbol, Expression> *stmt_ranges = _pgm_ranges.find_ref(stmt.tag()); if (! stmt_ranges) o << "{}"; else { RefList<Symbol> sorted_keys; KeyIterator<Symbol, Expression> c_iter = *stmt_ranges; for ( ; c_iter.valid(); ++c_iter) sorted_keys.ins_last(c_iter.current_key()); sort_sym_list(sorted_keys); Iterator<Symbol> key_iter = sorted_keys; bool first = true; o << "{"; for ( ; key_iter.valid(); ++key_iter) { if (! first) o << ", "; else first = false; const Symbol &var = key_iter.current(); const Expression &value = (* stmt_ranges)[var]; pretty_print_range(o, value, var); } o << "}"; } } /// listable_clone Listable * ControlRangeDict::listable_clone(void) const { return 0; } /// structures_OK int ControlRangeDict::structures_OK() const { return (_range_values.structures_OK() && _pgm_ranges.structures_OK()); }

© 1995-2005 University of Illinois, Urbana-Champaign. All rights reserved.  Fri Mar 25 23:05:43 2005