AIRangeDict.cc File Reference
Go to the source code of this file.
|
Functions |
| template ostream & | operator<< (ostream &, const Database< String, StmtRanges > &) |
| static void | _init_workspaces (StmtList &stmts) |
| | init_workspaces Initialize the workspaces for each statement in the program.
|
| static PropRangeWS & | _get_workspace (const Statement &stmt) |
| | get_workspace Get the workspace for the given statement.
|
| static void | _dump_workspaces (ostream &o, const StmtList &stmts) |
| | dump_workspaces Dump out the data inside all of the workspaces of the program
|
| static void | _collect_stats (const StmtList &stmts, float &avg_visits, float &avg_cd_entries) |
| | colect_stats Collect various statistics about the pass.
|
| static void | _make_nonlocals_modified_at_calls (ProgramUnit &pgm) |
| | _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 | _add_flow_edges (StmtList &stmts) |
| | add_flow_edges Add flow edges to all of the workspace objects
|
| static void | _patch_flow_graph (StmtList &stmts) |
| | patch_flow_graph Add flow edges from all ENDDO statements in the flow graph to the statement following the ENDDO.
|
| static void | _calc_toporder1 (PropRangeWS &my_ws, int &toporder) |
| | _calc_toporder Calculate toporder for the flow graph.
|
| static void | _calc_toporder (StmtList &stmts, Array< Statement * > &toporder_to_stmt) |
| static void | _set_needs_widening (StmtList &stmts) |
| | set_needs_widening Initialize the needs_widener field for all statement's workspaces.
|
| static void | _calc_loop_variants (StmtList &stmts) |
| static void | _put_succ_on_work_list (IntSet &work_list, PropRangeWS &my_ws) |
| | put_succ_on_work_list Put all of my successors on the work list.
|
| static bool | _use_widening_operator (PropRangeWS &curr_ws) |
| | use_widening_operator The given workspace's constraint dictionary needs the use of the widening operator if this method returns true.
|
| static Boolean | is_ARRAY_OP (const Expression &expr) |
| static void | _add_subscript_constraints_to_ranges (Statement &stmt, StmtRanges &ranges) |
| | _add_subscript_constraints_to_ranges Intersect any relation assertions for the given statement with the given constraint dictionary.
|
| static void | _add_asserts_to_ranges (const Statement &stmt, StmtRanges &ranges) |
| | add_asserts_to_ranges Intersect any relation assertions for the given statement with the given constraint dictionary.
|
| static Expression * | _invert_expr (const Expression &rhs, const Symbol &lhs_var) |
| | invert_expr Given an expression of the form "lhs_var = rhs", where rhs is an expression of the form "<expr>*lhs_var + ...", calculate the expression to map the old value of lhs to its new value.
|
| static bool | _update_assign_succs (Statement &stmt, StmtRanges *out_ranges) |
| | update_assign_succs Update the output ranges and possibly the successors of the given assignment statement.
|
| static bool | _update_if_succs (Statement &stmt, StmtRanges *out_ranges) |
| | update_if_succs Update the output ranges and possibly the successors of the given IF statement.
|
| static Expression * | _exit_range (const Statement &do_loop, EXPR_SIGN step_sign) |
| | exit_range Compute the exit range for the index variable of the given loop.
|
| static bool | _update_do_succs (Statement &stmt, StmtRanges *out_ranges) |
| | update_do_succs Update the output ranges and possibly the successors of the given DO statement.
|
| static bool | _update_enddo_succs (Statement &stmt, StmtRanges *out_ranges) |
| | update_enddo_succs Update the output ranges and possibly the successors of the given ENDDO statement.
|
| static void | _update_succ_edges (Statement &stmt) |
| | update_succ_edges Update the constraint dictionaries of the successor edges of the given statement.
|
| static void | _iterate_to_fixed_point_phase (ProgramUnit &pgm, const Array< Statement * > &toporder_to_stmt, const IntSet &start_stmts, bool widening_phase) |
| | iterate_to_fixed_point_phase 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) |
| | iterate_to_fixed_point Propagate the constants contained in the statement's const_maps until a fixed point is reached.
|
| static void | _calc_loop_range (const Statement &do_loop, const StmtList &stmts, Database< String, StmtRanges > &stmt_ranges, Database< String, StmtRanges > &loop_ranges) |
| | calc_loop_range Determine the contraints that hold for the body of the given loop.
|
| void | determine_loop_ranges (const StmtList &stmts, Database< String, StmtRanges > &stmt_ranges, Database< String, StmtRanges > &loop_ranges) |
| | determine_loop_ranges Print out all of the ranges for the given statement list
|
Variables |
| static unsigned int | _pass_tag |
| | The maximum number of visits to this node in which the selective widening of ranges will be allowed.
|
| static int | _debug_level = 0 |
| | ... Pass tag associated with this pass
|
| static int | _refine_ranges = -1 |
Detailed Description
Definition in file AIRangeDict.cc.
Function Documentation
| static void _init_workspaces |
( |
StmtList & |
stmts |
) |
[static] |
|
| static void _dump_workspaces |
( |
ostream & |
o, |
|
|
const StmtList & |
stmts |
|
) |
[static] |
|
| static void _collect_stats |
( |
const StmtList & |
stmts, |
|
|
float & |
avg_visits, |
|
|
float & |
avg_cd_entries |
|
) |
[static] |
|
| static void _make_nonlocals_modified_at_calls |
( |
ProgramUnit & |
pgm |
) |
[static] |
|
|
|
_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.
... Calculate the set of non-local variables.
... Also place any aliased variables in the set.
... Add the non-local variables to the mod_set of all statements that ... are either call statements or contain function calls.
Definition at line 139 of file AIRangeDict.cc.
References _get_workspace(), Statement::act_refs(), ASSIGNMENT_STMT, Expression::base_variable_ref(), CALL_STMT, Symbol::common_ref(), contains_func_call(), Iterator< T >::current(), DictionaryIter< T >::current(), Type::data_type(), RefSet< T >::del(), equiv_aliases(), Symbol::formal(), RefSet< T >::ins(), INTEGER_TYPE, IS_FORMAL, Statement::lhs(), PropConstWS::mod_set, Statement::stmt_class(), stmt_maymods(), Symbol::sym_class(), symbol(), Symbol::type(), Iterator< T >::valid(), KeyIterator< String, T >::valid(), and VARIABLE_CLASS. |
| static void _add_flow_edges |
( |
StmtList & |
stmts |
) |
[static] |
|
| static void _patch_flow_graph |
( |
StmtList & |
stmts |
) |
[static] |
|
| static void _calc_toporder1 |
( |
PropRangeWS & |
my_ws, |
|
|
int & |
toporder |
|
) |
[static] |
|
| static void _set_needs_widening |
( |
StmtList & |
stmts |
) |
[static] |
|
| static void _calc_loop_variants |
( |
StmtList & |
stmts |
) |
[static] |
|
| static void _put_succ_on_work_list |
( |
IntSet & |
work_list, |
|
|
PropRangeWS & |
my_ws |
|
) |
[static] |
|
| static bool _use_widening_operator |
( |
PropRangeWS & |
curr_ws |
) |
[static] |
|
| static void _add_subscript_constraints_to_ranges |
( |
Statement & |
stmt, |
|
|
StmtRanges & |
ranges |
|
) |
[static] |
|
|
|
_add_subscript_constraints_to_ranges Intersect any relation assertions for the given statement with the given constraint dictionary.
Definition at line 427 of file AIRangeDict.cc.
References apply_limits(), Expression::arg_list(), Expression::array(), RefSet< T >::clear(), Expression::clone(), constant(), Iterator< T >::current(), Symbol::dim(), List< T >::entries(), is_ARRAY_OP(), ArrayBounds::lower_exists(), ArrayBounds::lower_guarded(), Expression::subscript(), Expression::symbol(), ArrayBounds::upper_exists(), ArrayBounds::upper_guarded(), and Iterator< T >::valid().
Referenced by _iterate_to_fixed_point_phase(). |
|
|
invert_expr Given an expression of the form "lhs_var = rhs", where rhs is an expression of the form "<expr>*lhs_var + ...", calculate the expression to map the old value of lhs to its new value.
For example, if the expression is of the form "i = 2*i + 1", this function returns "(i-1)/2". If the arguments cannot be fitted into the above form, this method returns 0.
... Remove the single multiplicative term containing lhs_var from the ... the other terms in the expression
... Break the lhs_term into the lhs variable and its factor.
... Generate and return the inverted expression
Definition at line 511 of file AIRangeDict.cc.
References add(), ADD_OP, Expression::arg_list(), Expression::clone(), constant(), Iterator< T >::current(), div(), DIV_OP, List< T >::grab(), Mutator< T >::grab(), Expression::grab_left(), Expression::grab_right(), ID_OP, INTEGER_CONSTANT_OP, is_var_in_expr(), Expression::left_guarded(), Expression::member_ref(), mul(), MULT_OP, Expression::op(), Expression::right_guarded(), simplify(), sub(), Expression::symbol(), Iterator< T >::valid(), and Expression::value().
Referenced by _update_assign_succs(). |
|
|
update_do_succs Update the output ranges and possibly the successors of the given DO statement.
Return true if the successors is updated.
... Expression *exit_range = _exit_range(stmt, step_sign); ... exit_edge->ranges(out_ranges); ... exit_edge->ranges_ref()->set_range(stmt.index().symbol(), exit_range);
Definition at line 742 of file AIRangeDict.cc.
References _get_workspace(), contains_func_call(), List< T >::entries(), BaseStmtRanges::extract_ranges(), List< T >::first_ref(), ge(), INTEGER_TYPE, List< T >::last_ref(), le(), POS_EXPR, POS_NEG_EXPR, PropRangeEdge::ranges(), PropRangeEdge::ranges_ref(), StmtRanges::set_range(), Expression::sign(), simplify(), PropRangeEdge::succ(), and PropRangeWS::succ().
Referenced by _update_succ_edges(). |
|
|
update_enddo_succs Update the output ranges and possibly the successors of the given ENDDO statement.
Return true if the successors is updated.
Definition at line 799 of file AIRangeDict.cc.
References _exit_range(), _get_workspace(), contains_func_call(), List< T >::entries(), List< T >::first_ref(), Statement::index(), List< T >::last_ref(), POS_NEG_EXPR, PropRangeEdge::ranges(), Expression::sign(), Statement::step(), PropRangeEdge::succ(), PropRangeWS::succ(), and Expression::symbol(). |
| static void _update_succ_edges |
( |
Statement & |
stmt |
) |
[static] |
|
|
|
update_succ_edges Update the constraint dictionaries of the successor edges of the given statement.
... First, discard any ranges belonging to possibly modified variables
... Now, update the successors constraint dictionaries.
... already_updated_succs = _update_enddo_succs(stmt, out_ranges);
... Do nothing
... If the previous functions did not update the constraint dictionaries of ... my successor edges, do so now.
Definition at line 839 of file AIRangeDict.cc.
References _add_asserts_to_ranges(), _get_workspace(), _update_assign_succs(), _update_do_succs(), _update_if_succs(), ASSIGNMENT_STMT, BLOCK_ENTRY_STMT, BLOCK_EXIT_STMT, StmtRanges::clear(), Iterator< T >::current(), StmtRanges::del_range(), DO_STMT, ELSEIF_STMT, ENDDO_STMT, BaseStmtRanges::get_range_ref(), IF_STMT, PropRangeWS::mod_set(), PropRangeEdge::ranges(), PropRangeWS::ranges_ref(), BaseStmtRanges::subst_in_ranges(), PropRangeWS::succ(), switch_value(), and Iterator< T >::valid().
Referenced by _iterate_to_fixed_point_phase(). |
| static void _iterate_to_fixed_point_phase |
( |
ProgramUnit & |
pgm, |
|
|
const Array< Statement * > & |
toporder_to_stmt, |
|
|
const IntSet & |
start_stmts, |
|
|
bool |
widening_phase |
|
) |
[static] |
|
|
|
iterate_to_fixed_point_phase Propagate the constants contained in the statement's const_maps until a fixed point is reached.
... Read switch value first time through
... List of statements that need to be updated. ... Iterate until there are no more elements on the work list
... Optimization to decrease number of StmtRanges copies.
... Add ranges from any array subscripting in the statement
Definition at line 928 of file AIRangeDict.cc.
References _add_subscript_constraints_to_ranges(), _debug_level, _get_workspace(), _put_succ_on_work_list(), _refine_ranges, _update_succ_edges(), _use_widening_operator(), Iterator< T >::current(), IntSet::del(), RefSet< T >::entries(), IntSet::entries(), IntSet::first(), PropRangeEdge::grab_ranges(), PropRangeWS::incr_num_visits(), PropRangeWS::loop_variants_ref(), BaseStmtRanges::narrow_ranges(), PropRangeWS::needs_widening(), IntSet::next(), PropRangeWS::num_visits(), PropRangeWS::pred(), BaseStmtRanges::pretty_print(), PropRangeWS::ranges(), PropRangeEdge::ranges_ref(), PropRangeWS::ranges_ref(), switch_value(), BaseStmtRanges::union_ranges(), Iterator< T >::valid(), BaseStmtRanges::widen_ranges(), BaseStmtRanges::widen_some_ranges(), and Statement::write().
Referenced by _iterate_to_fixed_point(). |
|
|
iterate_to_fixed_point Propagate the constants contained in the statement's const_maps until a fixed point is reached.
... Widening phase: ... This phase iterates to a fixed point, applying the widening operator ... on the constraint dictionaries of all statements with back edges. ... The widening operator makes an overly conservative estimate of the ... fixed point value, so as to guarrantee convergence.
... Narrowing phase: ... This phase iterates to a fixed point, applying the narrowing operator ... on the constraint dictionaries of all statements with back edges. ... The narrowing operator attempts to regain some of the information ... lost by the widening operator.
Definition at line 1033 of file AIRangeDict.cc.
References _debug_level, _get_workspace(), _iterate_to_fixed_point_phase(), Iterator< T >::current(), PropRangeWS::needs_widening(), PropRangeWS::toporder(), and Iterator< T >::valid(). |
Variable Documentation
|
|
The maximum number of visits to this node in which the selective widening of ranges will be allowed.
This bound is a hack to allow selective widening yet preventing the pass from going into an infinite loop in rare cases. This hack can be justified because the selective widening operator is itself a hack to avoid the loss of information because of unnecessary widenings.
Definition at line 40 of file AIRangeDict.cc.
Referenced by _get_workspace(), and _init_workspaces(). |
|