Polaris: AIRangeDict.cc Source File

AIRangeDict.cc Go to the documentation of this file. /// /// /// \file AIRangeDict.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/invariant_util.h" #include "../utilities/expression_util.h" #include "../Dictionary.h" #include "../utilities/equivalence_util.h" #include "../Array.h" #include "../IntSet.h" #include "../Timer.h" #include "../Traverser.h" #include "../p-assert.h" #include "AIRangeDict.h" #include "PropRangeWS.h" #include "PropRangeEdge.h" #include "RangeExpr.h" #include "range_util.h" #include "range_dict_util.h" //#include "PropRangeWS.cc" #define MAX_SELECTIVE_WIDENING 6 /// 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. static unsigned int _pass_tag; /// ... Pass tag associated with this pass static int _debug_level = 0; static int _refine_ranges = -1; /// Template instantiations template class TypedBaseMap<String,StmtRanges>; template class ProtoDatabase<String,StmtRanges>; template class Database<String,StmtRanges>; template ostream & operator << (ostream &, const Database<String,StmtRanges> &); template class KeyIterator<String,StmtRanges>; /// init_workspaces /// Initialize the workspaces for each statement in the program. /// Note: A lot of the initialization for propagate_constants are hidden /// in the constructor for PropConstWS. static void _init_workspaces(StmtList &stmts) { Iterator<Statement> iter = stmts.iterator(); for ( ; iter.valid(); ++iter) { PropRangeWS *my_ws = new PropRangeWS(_pass_tag, iter.current()); iter.current().work_stack().push(my_ws); } } /// get_workspace /// Get the workspace for the given statement. static PropRangeWS & _get_workspace(const Statement &stmt) { WorkSpace *ws = stmt.work_stack().top_ref(_pass_tag); p_assert(ws, "Statement doesn't have a RangeWS."); return * (PropRangeWS *) ws; } /// dump_workspaces /// Dump out the data inside all of the workspaces of the program static void _dump_workspaces(ostream &o, const StmtList &stmts) { Iterator<Statement> iter = stmts.iterator(); for ( ; iter.valid(); ++iter) { iter.current().structures_OK(); o << iter.current().tag() << ": "; int zero = 0; iter.current().fortran_write(o, zero); o << "\n "; _get_workspace(iter.current()).print(o); o << endl; } } /// colect_stats /// Collect various statistics about the pass. These statistics are the /// average number of visits to a node, and the weighted average number of /// entries in the constraint dictionaries. static void _collect_stats(const StmtList &stmts, float &avg_visits, float &avg_cd_entries) { int num_visits = 0; int num_cd_entries = 0; int weighted_stmt_entries = 0; Iterator<Statement> iter = stmts.iterator(); for ( ; iter.valid(); ++iter) { PropRangeWS &ws = _get_workspace(iter.current()); num_visits += ws.num_visits(); if (ws.ranges_ref()) num_cd_entries += ws.num_visits() * ws.ranges_ref()->entries(); weighted_stmt_entries += ws.num_visits(); } avg_visits = (float) num_visits / (float) stmts.entries(); avg_cd_entries = (float) num_cd_entries / (float) weighted_stmt_entries; } /// _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()); } } } } /// add_flow_edges /// Add flow edges to all of the workspace objects static void _add_flow_edges(StmtList &stmts) { Iterator<Statement> stmt_iter = stmts.iterator(); for ( ; stmt_iter.valid(); ++stmt_iter) { Statement &stmt = stmt_iter.current(); PropRangeWS &curr_ws = _get_workspace(stmt); Iterator<Statement> succ_iter = stmt.succ(); for ( ; succ_iter.valid(); ++succ_iter) { Statement &succ = succ_iter.current(); PropRangeEdge *edge = new PropRangeEdge(stmt, succ); curr_ws.succ().ins_last(edge); _get_workspace(succ).pred().ins(*edge); } } } /// patch_flow_graph /// Add flow edges from all ENDDO statements in the flow graph to the /// statement following the ENDDO. These edges are added so to allow constant /// information calculated inside a DO loop to be propagated to statements /// after a DO loop in the same iteration. Without these additional edges, /// constant information calculated inside a loop can affect statements /// after the loop only on the successive iteration. This would mean that /// the the number of iterations required will be a multiple of the depth of /// the maximum loop nesting of the program. static void _patch_flow_graph(StmtList &stmts) { Iterator<Statement> iter = stmts.stmts_of_type(ENDDO_STMT); for ( ; iter.valid(); ++iter) { Statement &curr = iter.current(); Statement &next = * (Statement *) curr.next_ref(); PropRangeEdge *enddo_edge = new PropRangeEdge(curr, next); _get_workspace(curr).succ().ins_last(enddo_edge); _get_workspace(next).pred().ins(*enddo_edge); } } /// _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(PropRangeWS &my_ws, int &toporder) { my_ws.visited(1); Iterator<PropRangeEdge> succ_iter = my_ws.succ(); for ( ; succ_iter.valid(); ++succ_iter) { PropRangeWS &succ_ws = _get_workspace(succ_iter.current().succ()); if (! succ_ws.visited()) _calc_toporder1(succ_ws, toporder); } my_ws.toporder(toporder--); } static void _calc_toporder(StmtList &stmts, Array<Statement *> &toporder_to_stmt) { /// ... Calculate the topological order for each statement int toporder = stmts.entries() - 1; if (toporder >= 0) { Iterator<Statement> entry_iter = stmts.iterate_entry_points(); for ( ; entry_iter.valid(); ++entry_iter) { PropRangeWS &entry_ws = _get_workspace(entry_iter.current()); if (! entry_ws.visited()) _calc_toporder1(entry_ws, toporder); } p_assert(toporder >= -1, "_calc_toporder visited a stmt more than once."); } /// ... Initialize toporder_to_stmt toporder_to_stmt.resize(stmts.entries()); for (int i = 0; i <= toporder; ++i) toporder_to_stmt[i] = 0; Iterator<Statement> iter = 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(); } } /// set_needs_widening /// Initialize the needs_widener field for all statement's workspaces. /// A statement's constraint dictionary eventually needs the widening /// operator if it has any back-edges. static void _set_needs_widening(StmtList &stmts) { Iterator<Statement> stmt_iter = stmts.iterator(); for ( ; stmt_iter.valid(); ++stmt_iter) { PropRangeWS &curr_ws = _get_workspace(stmt_iter.current()); int stmt_toporder = curr_ws.toporder(); Iterator<PropRangeEdge> pred_iter = curr_ws.pred(); for ( ; pred_iter.valid(); ++pred_iter) if (stmt_toporder <= _get_workspace( pred_iter.current().pred()).toporder()) { curr_ws.needs_widening(true); break; } } } static void _calc_loop_variants(StmtList &stmts) { Iterator<Statement> stmt_iter = stmts.stmts_of_type(DO_STMT); for ( ; stmt_iter.valid(); ++stmt_iter) { Statement &do_loop = stmt_iter.current(); RefSet<Symbol> *loop_variants = loop_variant_vars(stmts, do_loop); p_assert(loop_variants, "Internal error: loop_variant_vars() returned NULL."); _get_workspace(do_loop).loop_variants(loop_variants); } } /// put_succ_on_work_list /// Put all of my successors on the work list. static void _put_succ_on_work_list(IntSet &work_list, PropRangeWS &my_ws) { Iterator<PropRangeEdge> succ_iter = my_ws.succ(); for ( ; succ_iter.valid(); ++succ_iter) work_list.ins(_get_workspace(succ_iter.current().succ()).toporder()); } /// use_widening_operator /// The given workspace's constraint dictionary needs the use of the widening /// operator if this method returns true. static bool _use_widening_operator(PropRangeWS &curr_ws) { if (curr_ws.needs_widening()) if (curr_ws.use_widener()) return true; else { bool preds_have_ranges = true; Iterator<PropRangeEdge> pred_iter = curr_ws.pred(); for ( ; pred_iter.valid(); ++pred_iter) if (! pred_iter.current().ranges_ref()) { preds_have_ranges = false; break; } curr_ws.use_widener(preds_have_ranges); } return false; } static Boolean is_ARRAY_OP (const Expression & expr) { if (expr.op() == ARRAY_REF_OP) { return True; } else { return False; } } /// _add_subscript_constraints_to_ranges /// Intersect any relation assertions for the given statement with the /// given constraint dictionary. static void _add_subscript_constraints_to_ranges(Statement &stmt, StmtRanges &ranges) { Iterator<Expression> expr_iter = stmt.iterate_expressions(); for ( ; expr_iter.valid(); ++expr_iter) { Traverser trav (expr_iter.current(), is_ARRAY_OP); for ( ; trav.valid(); ++trav) { const Expression &expr = trav.current(); Iterator<Expression> subscr_iter = expr.subscript().arg_list(); Iterator<ArrayBounds> declare_iter = expr.array().symbol().dim(); int num_dims = expr.array().symbol().dim().entries(); for (int which_dim = 0; subscr_iter.valid() && declare_iter.valid(); ++subscr_iter,++declare_iter,++which_dim) { Expression & expr = subscr_iter.current(); ArrayBounds & bounds = declare_iter.current(); Expression * upper = 0; if (bounds.upper_exists() && (which_dim < num_dims-1)) { upper = bounds.upper_guarded().clone(); } Expression * lower; if (bounds.lower_exists()) { lower = bounds.lower_guarded().clone(); } else { lower = constant(1); } RefSet<Symbol> symset; apply_limits(expr, lower, upper, ranges, symset); symset.clear(); if (lower) { apply_limits(*lower, 0, upper, ranges, symset); symset.clear(); } if (upper) { apply_limits(*upper, lower, 0, ranges, symset); } } } } } /// add_asserts_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) { Iterator<Assertion> assert_iter = stmt.assertions(); for ( ; assert_iter.valid(); ++assert_iter) { const Assertion &assert = assert_iter.current(); if (assert.type() == AS_RELATION) { Iterator<Expression> arg_iter = assert.arg_list_guarded(); for ( ; arg_iter.valid(); ++arg_iter) ranges.extract_ranges(arg_iter.current()); } } } /// 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. static Expression * _invert_expr(const Expression &rhs, const Symbol &lhs_var) { /// ... Remove the single multiplicative term containing lhs_var from the /// ... the other terms in the expression Expression *terms = rhs.clone(); Expression *lhs_term = 0; if (terms->op() == ID_OP || terms->op() == MULT_OP || terms->op() == DIV_OP) { lhs_term = terms; terms = 0; } else if (terms->op() == ADD_OP) { Mutator<Expression> iter = terms->arg_list(); for ( ; iter.valid(); ++iter) if (is_var_in_expr(iter.current(), lhs_var)) if (! lhs_term) lhs_term = iter.grab(); else { delete lhs_term; delete terms; return 0; } } if (! lhs_term) { delete terms; return 0; } /// ... Break the lhs_term into the lhs variable and its factor. Expression *lhs_expr = 0; Expression *factor = 0; Expression *divisor = 0; if (lhs_term->op() == ID_OP) lhs_expr = lhs_term; else if (lhs_term->op() == MULT_OP) { lhs_expr = lhs_term->member_ref(&lhs_var); if (lhs_expr) { lhs_term->arg_list().grab(*lhs_expr); if (is_var_in_expr(*lhs_term, lhs_var)) { delete lhs_expr; lhs_expr = 0; } else factor = lhs_term; } } else if (lhs_term->op() == DIV_OP && lhs_term->left_guarded().op() == ID_OP && &lhs_term->left_guarded().symbol() == &lhs_var && lhs_term->right_guarded().op() == INTEGER_CONSTANT_OP) { lhs_expr = lhs_term->grab_left(); divisor = lhs_term->grab_right(); delete lhs_term; } if (! lhs_expr) { if (terms) delete terms; if (lhs_term) delete lhs_term; if (factor) delete factor; if (divisor) delete divisor; return 0; } /// ... Generate and return the inverted expression Expression *inverted_expr = lhs_expr; if (terms) inverted_expr = sub(inverted_expr, terms); if (factor) inverted_expr = div(inverted_expr, factor); if (divisor) { int max_abs_mod; if (divisor->value() >= 0) max_abs_mod = divisor->value() - 1; else max_abs_mod = 1 - divisor->value(); inverted_expr = mul(divisor, inverted_expr); inverted_expr = new RangeExpr(inverted_expr, add(inverted_expr->clone(), constant(max_abs_mod))); } inverted_expr = simplify(inverted_expr); return inverted_expr; } /// update_assign_succs /// Update the output ranges and possibly the successors of the given /// assignment statement. Return true if the successors is updated. static bool _update_assign_succs(Statement &stmt, StmtRanges *out_ranges) { /// PropRangeWS &curr_ws = _get_workspace(stmt); const Symbol *lhs_name = stmt.lhs().base_variable_ref(); if (lhs_name) { const Expression *old_lhs_range = out_ranges->get_range_ref(*lhs_name); if (is_int_scalar(*lhs_name) && stmt.rhs().is_side_effect_free() && stmt.rhs().type().data_type() == INTEGER_TYPE) { Expression *assign_expr = stmt.rhs().clone(); if (is_var_in_expr(*assign_expr, *lhs_name)) { Expression *inverted_assign = _invert_expr(*assign_expr, *lhs_name); if (inverted_assign) { out_ranges->subst_in_ranges(*lhs_name, inverted_assign); delete inverted_assign; } else out_ranges->subst_in_ranges(*lhs_name, old_lhs_range); assign_expr = out_ranges->subst_var_and_simplify( assign_expr, *lhs_name, old_lhs_range); } else { out_ranges->subst_in_ranges(*lhs_name, old_lhs_range); assign_expr = simplify(assign_expr); } out_ranges->set_range(*lhs_name, assign_expr); } else { out_ranges->subst_in_ranges(*lhs_name, old_lhs_range); out_ranges->del_range(*lhs_name); } } return false; } /// update_if_succs /// Update the output ranges and possibly the successors of the given /// IF statement. Return true if the successors is updated. static bool _update_if_succs(Statement &stmt, StmtRanges *out_ranges) { if (! stmt.expr().is_side_effect_free()) return false; PropRangeWS &curr_ws = _get_workspace(stmt); p_assert(curr_ws.succ().entries() == 2, "If statement does not have two flow successors."); PropRangeEdge *then_edge = NULL, *else_edge = NULL; if (stmt.next_ref() == &curr_ws.succ().first_ref()->succ()) { then_edge = curr_ws.succ().first_ref(); else_edge = curr_ws.succ().last_ref(); } else if (stmt.next_ref() == &curr_ws.succ().last_ref()->succ()) { then_edge = curr_ws.succ().last_ref(); else_edge = curr_ws.succ().first_ref(); } else p_abort("Internal Error in _update_succ_edges"); then_edge->ranges(new StmtRanges(*out_ranges)); then_edge->ranges_ref()->extract_ranges(stmt.expr(), false); else_edge->ranges(out_ranges); else_edge->ranges_ref()->extract_ranges(stmt.expr(), true); return true; } /// exit_range /// Compute the exit range for the index variable of the given loop. static Expression * _exit_range(const Statement &do_loop, EXPR_SIGN step_sign) { Expression *exit_range; if (step_sign == POS_EXPR) { if (do_loop.step().op() == INTEGER_CONSTANT_OP && do_loop.step().value() == 1) exit_range = add(do_loop.limit().clone(), constant(1)); else exit_range = new RangeExpr(add(do_loop.limit().clone(), constant(1)), add(do_loop.limit().clone(), do_loop.step().clone())); } else { if (do_loop.step().op() == INTEGER_CONSTANT_OP && do_loop.step().value() == -1) exit_range = add(do_loop.limit().clone(), constant(-1)); else exit_range = new RangeExpr(add(do_loop.limit().clone(), do_loop.step().clone()), add(do_loop.limit().clone(), constant(-1))); } exit_range = simplify(exit_range); return exit_range; } /// update_do_succs /// Update the output ranges and possibly the successors of the given /// DO statement. Return true if the successors is updated. static bool _update_do_succs(Statement &stmt, StmtRanges *out_ranges) { EXPR_SIGN step_sign = out_ranges->sign(stmt.step()); if (step_sign == POS_NEG_EXPR || contains_func_call(stmt) || stmt.index().type().data_type() != INTEGER_TYPE) return false; PropRangeWS &curr_ws = _get_workspace(stmt); p_assert(curr_ws.succ().entries() == 2, "Do statement does not have two flow successors."); PropRangeEdge *body_edge = NULL, *exit_edge = NULL; if (stmt.next_ref() == &curr_ws.succ().first_ref()->succ()) { body_edge = curr_ws.succ().first_ref(); exit_edge = curr_ws.succ().last_ref(); } else if (stmt.next_ref() == &curr_ws.succ().last_ref()->succ()) { body_edge = curr_ws.succ().last_ref(); exit_edge = curr_ws.succ().first_ref(); } else p_abort("Internal Error in _update_succ_edges"); Expression *bound_cond, *index_range; if (step_sign == POS_EXPR) { bound_cond = le(stmt.init().clone(), stmt.limit().clone()); index_range = new RangeExpr(stmt.init().clone(), stmt.limit().clone()); } else { bound_cond = ge(stmt.init().clone(), stmt.limit().clone()); index_range = new RangeExpr(stmt.limit().clone(), stmt.init().clone()); } index_range = simplify(index_range); body_edge->ranges(new StmtRanges(*out_ranges)); body_edge->ranges_ref()->extract_ranges(*bound_cond); body_edge->ranges_ref()->set_range(stmt.index().symbol(), index_range); delete bound_cond; /// ... Expression *exit_range = _exit_range(stmt, step_sign); /// ... exit_edge->ranges(out_ranges); /// ... exit_edge->ranges_ref()->set_range(stmt.index().symbol(), exit_range); exit_edge->ranges(out_ranges); exit_edge->ranges_ref()->del_range(stmt.index().symbol()); return true; } /// update_enddo_succs /// Update the output ranges and possibly the successors of the given /// ENDDO statement. Return true if the successors is updated. static bool _update_enddo_succs(Statement &stmt, StmtRanges *out_ranges) { Statement &matching_do = *stmt.follow_ref(); EXPR_SIGN step_sign = out_ranges->sign(matching_do.step()); if (step_sign == POS_NEG_EXPR || contains_func_call(matching_do)) return false; PropRangeWS &curr_ws = _get_workspace(stmt); p_assert(curr_ws.succ().entries() == 2, "Enddo statement does not have two flow successors."); PropRangeEdge *back_edge = NULL, *exit_edge = NULL; if (&curr_ws.succ().first_ref()->succ() == &matching_do) { back_edge = curr_ws.succ().first_ref(); exit_edge = curr_ws.succ().last_ref(); } else if (&curr_ws.succ().last_ref()->succ() == &matching_do) { back_edge = curr_ws.succ().last_ref(); exit_edge = curr_ws.succ().first_ref(); } else p_abort("Internal Error in _update_succ_edges"); back_edge->ranges(new StmtRanges(*out_ranges)); Expression *exit_range = _exit_range(matching_do, step_sign); exit_edge->ranges(out_ranges); exit_edge->ranges_ref()->set_range(matching_do.index().symbol(), exit_range); return true; } /// update_succ_edges /// Update the constraint dictionaries of the successor edges of the given /// statement. static void _update_succ_edges(Statement &stmt) { PropRangeWS &curr_ws = _get_workspace(stmt); /// ... First, discard any ranges belonging to possibly modified variables p_assert(curr_ws.ranges_ref(), "Internal Error: Workspace has NULL StmtRanges pointer."); StmtRanges *out_ranges = new StmtRanges(*curr_ws.ranges_ref()); if (stmt.stmt_class() == DO_STMT) out_ranges->subst_in_ranges(stmt.index().symbol(), 0); Iterator<Symbol> mod_iter = curr_ws.mod_set(); for ( ; mod_iter.valid(); ++mod_iter) if (stmt.stmt_class() != ASSIGNMENT_STMT || ! stmt.lhs().base_variable_ref() || stmt.lhs().base_variable_ref() != &mod_iter.current()) { const Expression *range = out_ranges->get_range_ref(mod_iter.current()); out_ranges->subst_in_ranges(mod_iter.current(), range); out_ranges->del_range(mod_iter.current()); } _add_asserts_to_ranges(stmt, *out_ranges); /// ... Now, update the successors constraint dictionaries. bool already_updated_succs = false; switch (stmt.stmt_class()) { case ASSIGNMENT_STMT: already_updated_succs = _update_assign_succs(stmt, out_ranges); break; case IF_STMT: case ELSEIF_STMT: already_updated_succs = _update_if_succs(stmt, out_ranges); break; case DO_STMT: already_updated_succs = _update_do_succs(stmt, out_ranges); break; case ENDDO_STMT: /// ... already_updated_succs = _update_enddo_succs(stmt, out_ranges); break; case BLOCK_ENTRY_STMT: case BLOCK_EXIT_STMT: if (switch_value("range_block") > 0) out_ranges->clear(); break; default: /// ... Do nothing break; } /// ... If the previous functions did not update the constraint dictionaries of /// ... my successor edges, do so now. if (! already_updated_succs) { Iterator<PropRangeEdge> succ_iter = curr_ws.succ(); if (succ_iter.valid()) { succ_iter.current().ranges(out_ranges); ++succ_iter; for ( ; succ_iter.valid(); ++succ_iter) succ_iter.current().ranges(new StmtRanges(*out_ranges)); } else delete out_ranges; } } /// 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_phase(ProgramUnit &pgm, const Array<Statement *> &toporder_to_stmt, const IntSet &start_stmts, bool widening_phase) { /// ... Read switch value first time through if (_refine_ranges == -1) { _refine_ranges = switch_value("refine_ranges"); } IntSet work_list(start_stmts); /// ... List of statements that need to be updated. /// ... Iterate until there are no more elements on the work list while (work_list.entries() > 0) { 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); PropRangeWS &curr_ws = _get_workspace(curr); curr_ws.incr_num_visits(); StmtRanges *new_ranges = 0; Iterator<PropRangeEdge> pred_iter = curr_ws.pred(); if (curr_ws.pred().entries() == 1) { /// ... Optimization to decrease number of StmtRanges copies. new_ranges = pred_iter.current().grab_ranges(); p_assert(! curr_ws.needs_widening(), "Internal Error: Stmts with single predecesors should never need to be widened."); p_assert(new_ranges || ! curr_ws.ranges_ref(), "Internal Error: Constraint information was lost."); } else { for ( ; pred_iter.valid(); ++pred_iter) { PropRangeEdge &pred_edge = pred_iter.current(); StmtRanges *pred_ranges = pred_edge.ranges_ref(); if (pred_ranges) if (new_ranges) new_ranges->union_ranges(*pred_ranges); else new_ranges = new StmtRanges(*pred_ranges); } } if (! new_ranges) new_ranges = new StmtRanges(pgm.symtab()); /// ... Add ranges from any array subscripting in the statement if (_refine_ranges && (curr_ws.num_visits() == 1)) { _add_subscript_constraints_to_ranges(curr, *new_ranges); } if (curr_ws.ranges_ref() && curr_ws.needs_widening()) { StmtRanges &old_ranges = *curr_ws.ranges_ref(); if (widening_phase) { if (_use_widening_operator(curr_ws)) if (curr_ws.loop_variants_ref() && curr_ws.num_visits() <= MAX_SELECTIVE_WIDENING) { new_ranges->widen_some_ranges(old_ranges, *curr_ws.loop_variants_ref()); } else new_ranges->widen_ranges(old_ranges); } else new_ranges->narrow_ranges(old_ranges); } if (! curr_ws.ranges_ref() || *new_ranges != *curr_ws.ranges_ref()) { curr_ws.ranges(new_ranges); if (_debug_level >= 20) { int zero = 0; curr.write(cout, zero); cout << " "; curr_ws.ranges_ref()->pretty_print(cout); cout << endl; } _update_succ_edges(curr); _put_succ_on_work_list(work_list, curr_ws); } else delete new_ranges; } } } /// 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) { /// ... 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. if (_debug_level >= 20) cout << "\nWidening Phase:\n"; IntSet entry_stmts(toporder_to_stmt.entries()); Iterator<Statement> entry_iter = pgm.stmts().iterate_entry_points(); for ( ; entry_iter.valid(); ++entry_iter) { PropRangeWS &ws = _get_workspace(entry_iter.current()); entry_stmts.ins(ws.toporder()); } _iterate_to_fixed_point_phase(pgm, toporder_to_stmt, entry_stmts, true); /// ... 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. if (_debug_level >= 20) cout << "\nNarrowing Phase:\n"; IntSet widened_stmts(toporder_to_stmt.entries()); Iterator<Statement> stmt_iter = pgm.stmts().iterator(); for ( ; stmt_iter.valid(); ++stmt_iter) { PropRangeWS &ws = _get_workspace(stmt_iter.current()); if (ws.toporder() >= 0 && ws.needs_widening()) widened_stmts.ins(ws.toporder()); } _iterate_to_fixed_point_phase(pgm, toporder_to_stmt, widened_stmts, false); } /// _add_safe_cond_ranges /// Add any SafeCondition ranges to the PropRangeWS ranges on each statement /// within a loop body. void AIRangeDict::_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(); PropRangeWS &ws = _get_workspace(body_stmt); Iterator<Expression> arg_iter = assert.arg_list_guarded(); for ( ; arg_iter.valid(); ++arg_iter) { if (ws.ranges_ref()) { ws.ranges_ref()->extract_ranges(arg_iter.current()); } } } } } } } } /// generate_map /// Generate the mapping between variables and ranges. void AIRangeDict::_generate_map(const ProgramUnit &pgm) { Iterator<Statement> iter = pgm.stmts().iterator(); for ( ; iter.valid(); ++iter) { Statement &stmt = iter.current(); PropRangeWS &ws = _get_workspace(stmt); if (ws.ranges_ref()) _stmt_ranges.ins(stmt.tag(), ws.grab_ranges()); else _stmt_ranges.ins(stmt.tag(), new StmtRanges(pgm.symtab())); } } /// AIRangeDict AIRangeDict::AIRangeDict(ProgramUnit &pgm, int debug GIV(0)) : RangeDict(pgm.symtab()) { #ifdef CLASS_INSTANCE_REGISTRY register_instance(AIRANGE_DICT, sizeof(AIRangeDict), this); #endif if (switch_value("range_off") > 0) return; /// ... Silvius: force insertion of ranges according to the Fortran 77 /// ... standard for the following case: /// ... DIMENSION A(m,n:p,*) /// ... DO i=1,k /// ... DO j=h,100 /// ... A(i,j,...)=... /// ... In this case, since the access on A must be within bounds we /// ... will add to the dictionary the following ranges: /// ... k=[1,m] and h=[n:p]. /// ... Silvius: since I do not want to get to the guts of the AIRangeDict, /// ... we will force the insertionof the ranges by inserting some guards in /// ... the code, such as: /// ... IF (1.LE.k.AND.k.LE.m) THEN /// ... DO i=1,k RefList<Statement> new_ifs; enforce_standard_within_bounds(pgm, new_ifs); /// ... An array that maps integers to statements. Array<Statement *> toporder_to_stmt; _debug_level = debug; Timer tot_timer; Timer timer; float avg_visits, avg_cd_entries; /// ... Initialize remove_min_max_var_conflicts(pgm.symtab()); ::_pass_tag = create_pass_tag(); _init_workspaces(pgm.stmts()); if (switch_value("pc_call_mods") != 1) _make_nonlocals_modified_at_calls(pgm); _add_flow_edges(pgm.stmts()); /// ... _patch_flow_graph(pgm.stmts()); _calc_toporder(pgm.stmts(), toporder_to_stmt); _set_needs_widening(pgm.stmts()); _calc_loop_variants(pgm.stmts()); 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; _collect_stats(pgm.stmts(), avg_visits, avg_cd_entries); timer.reset(); } /// ... Dump ranges from the SafeCondition assertions into the PropRangeWS /// ... 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); /// ... Generate the mapping between statements and ranges _generate_map(pgm); if (_debug_level > 0) cout << "! Generating stmt_ranges: " << timer << endl; if (_debug_level >= 10) _dump_workspaces(cout, pgm.stmts()); /// ... Clean up pgm.clean_workspace(::_pass_tag); clean_after_standard_enforcement(pgm, new_ifs); if (_debug_level > 0) { cout << "! Total time: " << tot_timer << endl; cout << "! Number of statements: " << pgm.stmts().entries() << endl; cout << "! Average num visits: " << avg_visits << endl; cout << "! Average StmtRanges entries (weighted): " << avg_cd_entries << endl; } } AIRangeDict::AIRangeDict(const AIRangeDict &other) : RangeDict(other) { #ifdef CLASS_INSTANCE_REGISTRY register_instance(AIRANGE_DICT, sizeof(AIRangeDict), this); #endif *this = other; } /// Destructor AIRangeDict::~AIRangeDict() { #ifdef CLASS_INSTANCE_REGISTRY unregister_instance(AIRANGE_DICT, this); #endif /// ... nothing to do } /// operator = AIRangeDict & AIRangeDict::operator = (const AIRangeDict &other) { if (this != &other) { RangeDict::operator=(other); _stmt_ranges = other._stmt_ranges; } return *this; } /// range_vars /// /// Return the set of symbols in the range dictionary for a given statement /// If no symbols exist for a statement, return 0. RefSet<Symbol> * AIRangeDict::range_vars( const String & tag ) const { const StmtRanges * ranges = _stmt_ranges.find_ref(tag); if (ranges) { return ranges->range_vars( ); } else { return 0; } } /// elim_known_facts Expression * AIRangeDict::elim_known_facts( const String & tag, Expression * expr) { StmtRanges * ranges = _stmt_ranges.find_ref(tag); return ::elim_known_facts (expr, *ranges); } /// set_range void AIRangeDict::_set_range(const Symbol &var, const Statement &stmt, Expression *range) { StmtRanges *ranges = _stmt_ranges.find_ref(stmt.tag()); if (! ranges) { ranges = new StmtRanges(symtab()); _stmt_ranges.ins(stmt.tag(), ranges); } ranges->set_range(var, range); } /// del_range void AIRangeDict::_del_range(const Symbol &var, const Statement &stmt) { StmtRanges *ranges = _stmt_ranges.find_ref(stmt.tag()); if (ranges) ranges->del_range(var); } /// get_range_ref const Expression * AIRangeDict::_get_range_ref(const Symbol &var, const Statement &stmt) { StmtRanges *ranges = _stmt_ranges.find_ref(stmt.tag()); if (ranges) return ranges->get_range_ref(var); return 0; } /// print void AIRangeDict::print(ostream & o) const { KeyIterator<String, StmtRanges> iter = _stmt_ranges; for ( ; iter.valid(); ++iter) o << iter.current_key() << ": " << iter.current_data() << endl; } /// pretty_print void AIRangeDict::pretty_print(ostream & o, const Statement &stmt) const { const StmtRanges *ranges = _stmt_ranges.find_ref(stmt.tag()); if (ranges) ranges->pretty_print(o); else o << "{}"; } /// listable_clone Listable * AIRangeDict::listable_clone(void) const { return new AIRangeDict(*this); } /// structures_OK int AIRangeDict::structures_OK() const { return _stmt_ranges.structures_OK(); } /// Return a reference to the StmtRanges object associated with /// the given statement tag. StmtRanges & AIRangeDict::_s_ranges(const String & tag) { return _stmt_ranges[tag]; } #if 0 /// calc_loop_range /// Determine the contraints that hold for the body of the given loop. static void _calc_loop_range(const Statement &do_loop, const StmtList &stmts, Database<String,StmtRanges> &stmt_ranges, Database<String,StmtRanges> &loop_ranges) { StmtRanges *result = 0; const Statement *stmt = stmts.next_ref(do_loop); while (stmt && stmt != do_loop.follow_ref()) { if (stmt->pred().entries() > 0) { StmtRanges *ranges = stmt_ranges.find_ref(stmt->tag()); if (ranges) if (result) result->union_ranges(*ranges); else result = new StmtRanges(*ranges); } if (stmt->stmt_class() == DO_STMT) { _calc_loop_range(*stmt, stmts, stmt_ranges, loop_ranges); result->union_ranges(*loop_ranges.find_ref(stmt->tag())); stmt = stmt->follow_ref(); } else stmt = stmts.next_ref(*stmt); } loop_ranges.ins(do_loop.tag(), result); } /// determine_loop_ranges /// Print out all of the ranges for the given statement list void determine_loop_ranges(const StmtList &stmts, Database<String,StmtRanges> &stmt_ranges, Database<String,StmtRanges> &loop_ranges) { const Statement *stmt = stmts.first_ref(); while (stmt) { if (stmt->stmt_class() == DO_STMT) { _calc_loop_range(*stmt, stmts, stmt_ranges, loop_ranges); stmt = stmt->follow_ref(); } else stmt = stmts.next_ref(*stmt); } } #endif

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