Polaris: constant.cc Source File

constant.cc Go to the documentation of this file. /// /// /// \file constant.cc /// #include "../ProgramUnit.h" #include "../Statement/Statement.h" #include "../Statement/GotoStmt.h" #include "../Statement/AssignmentStmt.h" #include "../Symbol/Symbol.h" #include "../Collection/Map.h" #include "../Collection/Iterator.h" #include "../Collection/Mutator.h" #include "../utilities/switches_util.h" #include "../utilities/removegotos_util.h" #include "../utilities/expression_util.h" #include "../utilities/equivalence_util.h" #include "../IntElem.h" #include "../IntSet.h" #include "../Array.h" #include "../Boolean.h" #include "../Timer.h" #include "../p-assert.h" #include "../macros.h" #include "../p-setjmp.h" #include "../interface.h" #include "../Range/range_dict_util.h" #include "PropConstWS.h" #include "PropConstMap.h" #include "IPCPProcData.h" #include "constant.h" static unsigned int _pass_tag; /// ... Pass tag associated with this pass static int _debug_level = 0; static Boolean _substituted_var = False; /// ... True if expand_substituted substituted /// ... a variable. static Boolean _stmt_substituted_var = False; /// ... True if expand_substituted substituted /// ... a variable for the current statement. /// substitutable_type /// Returns true if the given type may be legally substituted static inline Boolean _substitutable_type(EXPR_TYPE type, PC_REAL_BOOL subst_reals) { if (type == INTEGER_TYPE || type == LOGICAL_TYPE || (subst_reals == SUBST_REALS && (type == REAL_TYPE || type == DOUBLE_PRECISION_TYPE || type == COMPLEX_TYPE))) return True; return False; } /// add_refs - /// Add the given set of references to the given variable set. static void _add_refs(RefSet<Symbol> &vars, const RefSet<Expression> &refs) { Iterator<Expression> iter = refs; for ( ; iter.valid(); ++iter) if (iter.current().base_variable_ref()) vars.ins(*iter.current().base_variable_ref()); } /// filter_vars - /// Filter out all variables from the given set that are disallowed by /// my switch values. static void _filter_vars(RefSet<Symbol> &vars, PC_REAL_BOOL subst_reals, PC_ARRAY_BOOL subst_arrays) { Mutator<Symbol> iter = vars; for ( ; iter.valid(); ++iter) { const Symbol &var = iter.current(); if (var.sym_class() != VARIABLE_CLASS || ! _substitutable_type(var.type().data_type(), subst_reals) || (subst_arrays != SUBST_ARRAYS && var.is_array())) iter.del(); } } /// init_candidates - /// Initialize def_candidates and use_candidates to be mappings from /// elements in def_vars or use_vars to integers. Also initialize /// tag_to_candidates to be a reverse mapping of def_candidates and /// use_candidates. Variables in use_candidates and in def_candidates /// will be assigned the same integer for both data structures. /// Variables in def_candidates are assigned the smallest numbers. /// It is assumed that use_candidates is a superset of def_candidates. static void _init_candidates(const RefSet<Symbol> &def_vars, const RefSet<Symbol> &use_vars, Map<Symbol,IntElem> &def_candidates, Map<Symbol,IntElem> &use_candidates, Array<Symbol *> &tag_to_candidate) { int tag = 0; tag_to_candidate.resize(use_vars.entries()); /// ... Initialize def_candidates. Iterator<Symbol> def_iter = def_vars; for ( ; def_iter.valid(); ++def_iter) { Symbol &var = def_iter.current(); tag_to_candidate[tag] = &var; def_candidates.ins(var, new IntElem(tag++)); } p_assert(tag == def_candidates.entries(), "Error in Map<Symbol,IntElem>::entries()."); /// ... Initialize use_candidates. Iterator<Symbol> use_iter = use_vars; for ( ; use_iter.valid(); ++use_iter) { Symbol &var = use_iter.current(); IntElem *var_tag = def_candidates.find_ref(var); if (var_tag) use_candidates.ins(var, new IntElem(var_tag->value())); else { tag_to_candidate[tag] = &var; use_candidates.ins(var, new IntElem(tag++)); } } p_assert(tag == use_candidates.entries(), "Error in Map<Symbol,IntElem>::entries()."); } /// collect_candidates - /// Determine all the variables that are candidates for forward substitution /// and initialize the _candidates and _tag_to_candidates data structures /// to contain these variables. static void _collect_candidates(const RefSet<Symbol> &def_vars, const StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt, Map<Symbol,IntElem> &def_candidates, Map<Symbol,IntElem> &use_candidates, Array<Symbol *> &tag_to_candidate) { RefSet<Symbol> use_vars = def_vars; Iterator<Statement> stmt_iter = stmts.iterator(first_stmt, last_stmt); for ( ; stmt_iter.valid(); ++stmt_iter) { const Statement &stmt = stmt_iter.current(); if (stmt.stmt_class() == ASSIGNMENT_STMT && stmt.lhs().op() == ID_OP && def_vars.member(stmt.lhs().symbol())) _add_refs(use_vars, stmt.in_refs()); } _init_candidates(def_vars, use_vars, def_candidates, use_candidates, tag_to_candidate); } static void _collect_candidates(const StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt, Map<Symbol,IntElem> &def_candidates, Map<Symbol,IntElem> &use_candidates, Array<Symbol *> &tag_to_candidate, PC_REAL_BOOL subst_reals, PC_ARRAY_BOOL subst_arrays) { RefSet<Symbol> def_vars; RefSet<Symbol> use_vars; Iterator<Statement> stmt_iter = stmts.iterator(first_stmt, last_stmt); for ( ; stmt_iter.valid(); ++stmt_iter) { const Statement &stmt = stmt_iter.current(); if (stmt.stmt_class() == ASSIGNMENT_STMT && stmt.lhs().op() == ID_OP && stmt.rhs().is_side_effect_free()) { const Symbol &var = stmt.lhs().symbol(); if (var.sym_class() == VARIABLE_CLASS && ! var.is_array() && _substitutable_type(var.type().data_type(), subst_reals)) { def_vars.ins(var); use_vars.ins(var); _add_refs(use_vars, stmt.in_refs()); } } } _filter_vars(use_vars, subst_reals, subst_arrays); _init_candidates(def_vars, use_vars, def_candidates, use_candidates, tag_to_candidate); } /// create_data_assigns - /// Create a list of pseudo assignment statements which assign all variables /// in the program unit's data statements to their constant values. static List<Statement> * _create_data_assigns(ProgramUnit &pgm, const RefSet<Symbol> *candidates, PC_REAL_BOOL subst_reals) { List<Statement> *data_assigns = new List<Statement>; Iterator<Data> data_iter = pgm.data(); for ( ; data_iter.valid(); ++data_iter) { Data &data = data_iter.current(); if (data.variable_list().arg_list().entries() == data.value_list().arg_list().entries()) { Iterator<Expression> var_iter = data.variable_list().arg_list(); Iterator<Expression> val_iter = data.value_list().arg_list(); for ( ; var_iter.valid(); ++var_iter, ++val_iter) { Symbol *var = var_iter.current().base_variable_ref(); if (var && ! var->is_array() && _substitutable_type(var->type().data_type(), subst_reals) && (! candidates || candidates->member(*var))) { Statement *data_assign = new AssignmentStmt(pgm.stmts().new_tag(), var_iter.current().clone(), val_iter.current().clone()); data_assigns->ins_last(data_assign); } } } } return data_assigns; } /// add_data_assigns - /// Add a list of pseudo assignment statements at the beginning of a program /// unit which assign all variables in the program unit's data statements /// to their constant values. A RefList of these statements is returned for /// future deletion. This function will only add such assignments if the /// program unit is the main program. static void _add_data_assigns(ProgramUnit &pgm, const RefSet<Symbol> *candidates, PC_REAL_BOOL subst_reals, RefSet<Statement> &pseudo_stmts) { if (pgm.pu_class() == PROGRAM_PU_TYPE) { List<Statement> *data_assigns = _create_data_assigns(pgm, candidates, subst_reals); if (data_assigns->entries() > 0) { Iterator<Statement> assign_iter = *data_assigns; for ( ; assign_iter.valid(); ++assign_iter) pseudo_stmts.ins(assign_iter.current()); Iterator<Statement> entry_iter = pgm.stmts().iterate_entry_points(); p_assert(entry_iter.valid(), "Main program does not have any entries."); pgm.stmts().ins_after(data_assigns, &entry_iter.current()); ++entry_iter; p_assert(! entry_iter.valid(), "Main program has multiple entries."); } else delete data_assigns; } } /// add_control_assigns - /// Add a list of pseudo assignment statements at the start of the loop /// bodies of IF statements that represent constants derived from the /// conditional statement of the IF statement. A RefList of these statements /// is returned for future deletion. static void _add_control_assigns(StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt, const RefSet<Symbol> *candidates, RefSet<Statement> &pseudo_stmts) { Iterator<Statement> stmt_iter = stmts.iterator(first_stmt, last_stmt); for ( ; stmt_iter.valid(); ++stmt_iter) { Statement &stmt = stmt_iter.current(); if (stmt.stmt_class() == IF_STMT && stmt.follow_ref()->stmt_class() != ELSEIF_STMT && (stmt.expr().op() == ID_OP || (stmt.expr().op() == NOT_OP && stmt.expr().expr_guarded().op() == ID_OP) || stmt.expr().op() == EQ_OP || stmt.expr().op() == NE_OP)) { /// ... Make sure that we have an ELSE clause. if (stmt.follow_ref()->stmt_class() == ENDIF_STMT) { Statement *last_then_stmt = stmt.follow_ref()->prev_ref(); if (last_then_stmt->stmt_class() == IMPLIED_GOTO_STMT) last_then_stmt = last_then_stmt->prev_ref(); stmts.ins_ELSE_after(&stmt, last_then_stmt); pseudo_stmts.ins(*stmt.follow_ref()); } p_assert(stmt.follow_ref()->stmt_class() == ELSE_STMT, "IF statement does not have an ELSE clause."); Expression *logical_var_expr = &stmt.expr(); if (logical_var_expr->op() == NOT_OP) logical_var_expr = &logical_var_expr->expr_guarded(); if (logical_var_expr->op() == ID_OP && logical_var_expr->symbol().type().data_type() == LOGICAL_TYPE && (! candidates || candidates->member(logical_var_expr->symbol()))) { /// ... Handle IF (FLAG) THEN ... or IF (.NOT. FLAG) THEN ... Statement *true_assign = new AssignmentStmt(stmts.new_tag(), logical_var_expr->clone(), constant(".TRUE.")); Statement *false_assign = new AssignmentStmt(stmts.new_tag(), logical_var_expr->clone(), constant(".FALSE.")); if (stmt.expr().op() == NOT_OP) { stmts.ins_after(false_assign, &stmt); stmts.ins_after(true_assign, stmt.follow_ref()); } else { stmts.ins_after(true_assign, &stmt); stmts.ins_after(false_assign, stmt.follow_ref()); } pseudo_stmts.ins(*true_assign); pseudo_stmts.ins(*false_assign); } else if (stmt.expr().op() == EQ_OP || stmt.expr().op() == NE_OP) { /// ... Handle IF (X .EQ. 1) THEN ... or IF (X .NE. 1) THEN ... Expression *var_expr = 0; Expression *const_expr = 0; if (stmt.expr().left_guarded().op() == ID_OP) { var_expr = &stmt.expr().left_guarded(); const_expr = &stmt.expr().right_guarded(); } else { var_expr = &stmt.expr().right_guarded(); const_expr = &stmt.expr().left_guarded(); } if (var_expr->op() == ID_OP && var_expr->symbol().type().data_type() == INTEGER_TYPE && const_expr->op() == INTEGER_CONSTANT_OP && (! candidates || candidates->member(var_expr->symbol()))) { Statement *const_assign = new AssignmentStmt(stmts.new_tag(), var_expr->clone(), const_expr->clone()); if (stmt.expr().op() == EQ_OP) stmts.ins_after(const_assign, &stmt); else stmts.ins_after(const_assign, stmt.follow_ref()); pseudo_stmts.ins(*const_assign); } } } } } /// 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, const Statement &first_stmt, const Statement &last_stmt, const Map<Symbol,IntElem> &def_candidates, const Map<Symbol,IntElem> &use_candidates, const Array<Symbol *> &tag_to_candidate) { Iterator<Statement> iter = stmts.iterator(first_stmt, last_stmt); for ( ; iter.valid(); ++iter) { PropConstWS *my_ws = new PropConstWS(_pass_tag, iter.current(), def_candidates, use_candidates, tag_to_candidate); iter.current().work_stack().push(my_ws); } } /// get_workspace /// Get the workspace for the given statement. static PropConstWS & _get_workspace(const Statement &stmt) { WorkSpace *ws = stmt.work_stack().top_ref(_pass_tag); p_assert(ws, "Statement doesn't have a ConstPropWS."); return * (PropConstWS *) ws; } /// dump_workspaces /// Dump out the data inside all of the workspaces of the program static void _dump_workspaces(ostream &o, const StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt) { Iterator<Statement> iter = stmts.iterator(first_stmt, last_stmt); for ( ; iter.valid(); ++iter) { iter.current().structures_OK(); o << iter.current().tag() << ": "; iter.current().print_debug(o, 0); o << endl; _get_workspace(iter.current()).pretty_print(o); } } /// _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(StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt, const Map<Symbol,IntElem> &use_candidates, const Array<Symbol *> &tag_to_candidate) { /// ... Calculate the set of non-local variables. IntSet non_local_set(tag_to_candidate.entries()); if (switch_value("pc_call_mods") != 1) { for (int sym_tag = 0; sym_tag < tag_to_candidate.entries(); ++sym_tag) { Symbol &var = *tag_to_candidate[sym_tag]; if (var.formal() == IS_FORMAL || var.common_ref()) { non_local_set.ins(sym_tag); /// ... Mark any variables aliased to the non-local variable /// ... as also non-local. RefSet<Symbol> *aliases = equiv_aliases(var); if (aliases) { Iterator<Symbol> alias_iter = *aliases; for ( ; alias_iter.valid(); ++alias_iter) { const IntElem *alias_elem = use_candidates.find_ref(alias_iter.current()); if (alias_elem) non_local_set.ins(alias_elem->value()); } 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> iter = stmts.iterator(first_stmt, last_stmt); for ( ; iter.valid(); ++iter) { Statement &stmt = iter.current(); PropConstWS &ws = _get_workspace(stmt); if (ws.unknown_call) { PropConstMap &const_map = ws.out_const_map; 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) { const IntElem *tag_elem = use_candidates.find_ref(*var_ref); if (tag_elem) ws.mod_set.del(tag_elem->value()); } } if (stmt.stmt_class() == ASSIGNMENT_STMT) { Symbol *var_ref = stmt.lhs().base_variable_ref(); if (var_ref) { const IntElem *tag_elem = use_candidates.find_ref(*var_ref); if (tag_elem) ws.mod_set.ins(tag_elem->value()); } } Iterator<Symbol> nl_iter = *maymods; for ( ; nl_iter.valid(); ++nl_iter) { const IntElem *tag_elem = use_candidates.find_ref(nl_iter.current()); if (tag_elem) { int sym_tag = tag_elem->value(); if (sym_tag != ws.lhs_tag()){ const_map[sym_tag].non_const(stmt); const_map.int_non_const(sym_tag); } } } delete maymods; } else { ws.mod_set |= non_local_set; for (int sym_tag = non_local_set.first(); sym_tag != -1; sym_tag = non_local_set.next(sym_tag)) { const_map[sym_tag].non_const(stmt); const_map.int_non_const(sym_tag); } } } } } /// 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, const Statement &first_stmt, const Statement &last_stmt) { Iterator<Statement> iter = stmts.iterator(first_stmt, last_stmt); for ( ; iter.valid(); ++iter) { Statement &curr = iter.current(); if (curr.stmt_class() == ENDDO_STMT) { Statement &next = * (Statement *) curr.next_ref(); if (next.work_stack().top_ref(_pass_tag) != 0) { _get_workspace(curr).succ.ins(next); _get_workspace(next).pred.ins(curr); } } } } /// num_stmts_in_block /// Return the number of statements in the given block. static int _num_stmts_in_block(const StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt) { int entries = 0; if (stmts.first_ref() == &first_stmt && stmts.last_ref() == &last_stmt) entries = stmts.entries(); else { Iterator<Statement> iter = stmts.iterator(first_stmt, last_stmt); for ( ; iter.valid(); ++iter) ++entries; } return entries; } /// determine_entry_points. /// Determine all the entry statements for the given block of statements. /// Simultaneously, delete all predecessors and successor edges entering/ /// exiting the block. static void _determine_entry_points(StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt, RefSet<Statement> &entry_points) { RefList<Statement> stmts_in_block; Boolean entire_stmt_list = (stmts.first_ref() == &first_stmt && stmts.last_ref() == &last_stmt); if (! entire_stmt_list) { Iterator<Statement> iter = stmts.iterator(first_stmt, last_stmt); for ( ; iter.valid(); ++iter) stmts_in_block.ins_last(iter.current()); } Iterator<Statement> iter = stmts.iterator(first_stmt, last_stmt); for ( ; iter.valid(); ++iter) { Statement &stmt = iter.current(); if (stmt.stmt_class() == ENTRY_STMT || stmt.stmt_class() == FLOW_ENTRY_STMT) entry_points.ins(stmt); else if (! entire_stmt_list) { PropConstWS &ws = _get_workspace(stmt); Mutator<Statement> pred_iter = ws.pred; for ( ; pred_iter.valid(); ++pred_iter) if (! stmts_in_block.member(pred_iter.current())) { entry_points.ins(stmt); pred_iter.del(); } Mutator<Statement> succ_iter = ws.succ; for ( ; succ_iter.valid(); ++succ_iter) if (! stmts_in_block.member(succ_iter.current())) succ_iter.del(); } } } /// _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(PropConstWS &my_ws, int &toporder) { my_ws.visited(1); Iterator<Statement> succ_iter = my_ws.succ; for ( ; succ_iter.valid(); ++succ_iter) { PropConstWS &succ_ws = _get_workspace(succ_iter.current()); if (! succ_ws.visited()) _calc_toporder1(succ_ws, toporder); } my_ws.toporder(toporder--); } static void _calc_toporder(StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt, const RefSet<Statement> &entry_points, Array<Statement *> &toporder_to_stmt) { /// ... Calculate the topological order for each statement int num_stmts = _num_stmts_in_block(stmts, first_stmt, last_stmt); int toporder = num_stmts - 1; if (toporder >= 0) { Iterator<Statement> entry_iter = entry_points; for ( ; entry_iter.valid(); ++entry_iter) { PropConstWS &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(num_stmts); for (int i = 0; i <= toporder; ++i) toporder_to_stmt[i] = 0; Iterator<Statement> iter = stmts.iterator(first_stmt, last_stmt); for ( ; iter.valid(); ++iter) { int stmt_toporder = _get_workspace(iter.current()).toporder(); if (stmt_toporder >= 0) toporder_to_stmt[stmt_toporder] = &iter.current(); } } /// _annotate_expr /// Annotate the substituted field of variables of the given expression with /// their constant values. If certain constant values must be substituted, /// this algorithm will perform the substitution. If any of the variables /// that must be substituted in the given expression is non-constant, this /// function will return NULL. static Expression * _annotate_expr(Expression *expr, const PropConstMap &orig_const_map, const PropConstMap &curr_const_map, const Map<Symbol,IntElem> &use_candidates) { if (! expr) return expr; if (expr->op() == ID_OP) { if (! expr->substituted_valid()) { const IntElem *tag_elem = use_candidates.find_ref(expr->symbol()); Expression *subst_expr = 0; if (tag_elem) { int sym_tag = tag_elem->value(); if (orig_const_map.int_state(sym_tag) == CONST) { int int_const = orig_const_map.int_const_val(sym_tag); if (expr->symbol().type().data_type() == LOGICAL_TYPE) if (int_const == 0) subst_expr = constant(".FALSE."); else subst_expr = constant(".TRUE."); else subst_expr = constant(int_const); } else { PropConstElem &curr_const = curr_const_map[sym_tag]; Boolean var_is_poisoned = False; if (curr_const.state() == CONST) { PropConstWS &subst_ws = _get_workspace(*curr_const.last_mod()); var_is_poisoned = subst_ws.poisoned_vars[sym_tag]; if (! var_is_poisoned) { subst_ws.poisoned_vars.ins(sym_tag); subst_expr = curr_const.expr().clone(); clear_substituted(*subst_expr); subst_expr = _annotate_expr(subst_expr, orig_const_map, subst_ws.in_const_map, use_candidates); subst_ws.poisoned_vars.del(sym_tag); } } PropConstElem &orig_const = orig_const_map[sym_tag]; if (var_is_poisoned || orig_const.last_mod() != curr_const.last_mod() || orig_const.state() != curr_const.state()) { /// ... We must substitute the constant value of /// ... the variable because either an earlier /// ... substitution poisoned the variable or the /// ... definition point of that variable for the /// ... given expression differs from the /// ... definition point of that variable for the /// ... statement being annotated. delete expr; return subst_expr; } } } expr->substituted(subst_expr); } else { /// ... Expression already has a filled substituted field. expr->substituted(_annotate_expr(expr->grab_substituted(), orig_const_map, curr_const_map, use_candidates)); } } else { Mutator<Expression> iter = expr->arg_list(); for ( ; iter.valid(); ++iter) { Assign<Expression> eas(iter.assign()); Expression *new_expr = _annotate_expr(iter.pull(), orig_const_map, curr_const_map, use_candidates); if (! new_expr) { delete expr; return 0; } else eas = new_expr; } } return expr; } /// _annotate_expr /// Annotate the substituted field of variables of the given expression with /// their constant values. static Expression * _annotate_expr(Expression *expr, const PropConstMap &const_map, const Map<Symbol,IntElem> &use_candidates) { Expression *new_expr = _annotate_expr(expr, const_map, const_map, use_candidates); p_assert(new_expr, "Internal Error: _annotate_expr failed for root expression."); return new_expr; } Expression * _annotate_expr(Expression *expr, const Statement &stmt, const Map<Symbol,IntElem> &use_candidates) { PropConstWS &my_ws = _get_workspace(stmt); PropConstMap &const_map = my_ws.out_const_map; return _annotate_expr(expr, const_map, use_candidates); } /// _annotate_assert /// Annotate assertions of the given statement with the calculated constant /// expressions static void _annotate_assert(Statement &stmt, const PropConstMap &const_map, const Map<Symbol,IntElem> &use_candidates) { Iterator<Assertion> ass_iter = stmt.assertions(); for ( ; ass_iter.valid(); ++ass_iter) { if (ass_iter.current().arg_list_valid()) { Mutator<Expression> aexpr_iter = ass_iter.current().arg_list_guarded(); for ( ; aexpr_iter.valid(); ++aexpr_iter) if (aexpr_iter.current().op() != ID_OP) { Assign<Expression> eas(aexpr_iter.assign()); eas = _annotate_expr(aexpr_iter.pull(), const_map, use_candidates); } } } } /// _annotate_stmt /// Annotate expressions the given statement with the calculated constant /// expressions static void _annotate_stmt(Statement &stmt, const Map<Symbol,IntElem> &use_candidates) { if (_debug_level >= 5) { cout << "! Before: "; stmt.print_debug(cout, 0); cout << endl; } /// ... Create a copy of my entering constants, where all variables /// ... modified by myself is marked as non-constant. PropConstWS &my_ws = _get_workspace(stmt); PropConstMap unmodified_const_map(my_ws.in_const_map); for (int sym_tag = my_ws.mod_set.first(); sym_tag != -1; sym_tag = my_ws.mod_set.next(sym_tag)) { unmodified_const_map[sym_tag].non_const(stmt); unmodified_const_map.int_non_const(sym_tag); } /// ... Annotate all the expressions in myself. if (stmt.stmt_class() == ASSIGNMENT_STMT && stmt.rhs().is_side_effect_free()) { Mutator<Expression> iter = stmt.iterate_expressions(); /// ... Update lhs. Assign<Expression> eas(iter.assign()); eas = _annotate_expr(iter.pull(), unmodified_const_map, use_candidates); /// ... Update rhs, ignoring the modification to the lhs variable. ++iter; Assign<Expression> eas2(iter.assign()); eas2 = _annotate_expr(iter.pull(), my_ws.in_const_map, use_candidates); } else { Mutator<Expression> iter = stmt.iterate_expressions(); for ( ; iter.valid(); ++iter) { Assign<Expression> eas3(iter.assign()); eas3 = _annotate_expr(iter.pull(), unmodified_const_map, use_candidates); } } _annotate_assert(stmt, unmodified_const_map, use_candidates); if (_debug_level >= 5) { cout << "! After: "; stmt.print_debug(cout, 0); cout << endl; } } /// annotate_stmts /// Annotate each statement of the given block of statements with its /// calculated constant expressions. static void _annotate_stmts(StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt, const Map<Symbol,IntElem> &use_candidates) { Iterator<Statement> iter = stmts.iterator(first_stmt, last_stmt); for ( ; iter.valid(); ++iter) _annotate_stmt(iter.current(), use_candidates); } /// kill_bad_join_consts /// Kill any constant expressions formed by the join of two or more /// reaching definitions, whose constant expression is no longer /// valid for one of these definitions. That is, one of the variables /// used by the constant expression was modified somewhere along a /// control flow path from the definition to the current statement. void _kill_bad_join_consts(Statement &stmt, PropConstMap &const_map) { PropConstWS &curr_ws = _get_workspace(stmt); if (curr_ws.pred.entries() < 2) return; for (int sym_tag = 0; sym_tag < const_map.entries(); ++sym_tag) { PropConstElem &const_elem = const_map[sym_tag]; if (const_elem.state() == CONST && const_elem.last_mod() == &stmt && const_elem.use_set().entries() > 0) { /// ... We have a join of two or more definitions of a constant /// ... symbolic expression. /// ... Test each of its reaching definitions. Boolean has_modified_use = False; Iterator<Statement> pred_iter = curr_ws.pred; for ( ; pred_iter.valid() && ! has_modified_use; ++pred_iter) { PropConstWS &pred_ws = _get_workspace(pred_iter.current()); if (pred_ws.num_visits() > 0) { PropConstMap &pred_map = pred_ws.out_const_map; PropConstElem &pred_elem = pred_map[sym_tag]; if (pred_elem.state() != MAY_BE_CONST) { p_assert(pred_elem.state() == CONST, "Predecessor of constant expression is a non-constant."); PropConstMap &last_mod_map = _get_workspace(*pred_elem.last_mod()).out_const_map; /// ... Test each of its uses. for (int use_tag = pred_elem.use_set().first(); use_tag != -1 && ! has_modified_use; use_tag = pred_elem.use_set().next(use_tag)) if (last_mod_map[use_tag].last_mod() != pred_map[use_tag].last_mod()) has_modified_use = True; } } } if (has_modified_use) const_elem.non_const(stmt); } } } /// _const_if_took_then /// Return true if I am an IF statement with a constant conditional /// expression that took only the THEN clause. static Boolean _const_if_took_then(const Statement &stmt) { if (stmt.stmt_class() != IF_STMT && stmt.stmt_class() != ELSEIF_STMT) return False; const PropConstWS &ws = _get_workspace(stmt); if (ws.num_visits() == 0 || ! ws.const_cond) return False; return (_get_workspace(*stmt.next_ref()).num_visits() > 0); } /// _const_if_succ /// If I am a constant IF statement, return my single successor. Otherwise /// return NULL. Statement * _const_if_succ(Statement &stmt, const Map<Symbol,IntElem> &use_candidates) { if (stmt.stmt_class() != IF_STMT && stmt.stmt_class() != ELSEIF_STMT && stmt.stmt_class() != ARITHMETIC_IF_STMT) return 0; int cond_result; const PropConstWS &ws = _get_workspace(stmt); Statement *succ = 0; if (int_const_val(stmt.expr(), ws.in_const_map, use_candidates, cond_result)) { if (stmt.stmt_class() == IF_STMT || stmt.stmt_class() == ELSEIF_STMT) { if (cond_result == 0) succ = stmt.follow_ref(); else succ = stmt.next_ref(); } else { if (cond_result < 0) succ = &stmt.label_list()[0]; else if (cond_result == 0) succ = &stmt.label_list()[1]; else succ = &stmt.label_list()[2]; } } return succ; } /// 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, const Map<Symbol,IntElem> &use_candidates) { PropConstWS &ws = _get_workspace(stmt); if (ws.const_cond) { const Statement *succ = _const_if_succ(stmt, use_candidates); if (! succ) ws.const_cond = False; else { if (_debug_level >= 5) { cout << "! Statement: "; stmt.print_debug(cout, 0); cout << " has a constant conditional\n"; } work_list.ins(_get_workspace(*succ).toporder()); } } if (! ws.const_cond) { Iterator<Statement> succ_iter = ws.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(StmtList & /* stmts */, const Statement & /* first_stmt */, const Statement & /* last_stmt */, const RefSet<Statement> &entry_points, const Array<Statement *> &toporder_to_stmt, const Map<Symbol,IntElem> &use_candidates, const Array<Symbol *> &tag_to_candidate, const Map<Symbol, Expression> &entering_constants) { /// ... List of statements that need to be updated. IntSet work_list(toporder_to_stmt.entries()); /// ... Put all entries on the work list. Iterator<Statement> entry_iter = 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); PropConstWS &curr_ws = _get_workspace(curr); curr_ws.incr_num_visits(); Boolean changed = False; /// ... Generate the new constant mapping entering the statement. PropConstMap new_in_const_map(use_candidates.entries(), tag_to_candidate); if (entry_points.member(curr)) { new_in_const_map.all_non_const(curr); curr_ws.add_consts(entering_constants); } else { Iterator<Statement> pred_iter = curr_ws.pred; for ( ; pred_iter.valid(); ++pred_iter) { PropConstWS &pred_ws = _get_workspace(pred_iter.current()); if (pred_ws.num_visits() > 0 && (curr.stmt_class() != ENDIF_STMT || ! _const_if_took_then(pred_iter.current()))) new_in_const_map.intersect(pred_ws.out_const_map, curr); } } _kill_bad_join_consts(curr, new_in_const_map); if (curr_ws.num_visits() == 1 || new_in_const_map != curr_ws.in_const_map) { /// ... New entering constant mapping differs from the old /// ... one. So update the entering and exiting constant /// ... mappings for the statement. if (_debug_level >= 20) { cout << "! Statement "; curr.print_debug(cout, 0); cout << " was visited and updated.\n"; } curr_ws.in_const_map = new_in_const_map; changed = curr_ws.update_out_const_map(); if (! changed && curr_ws.const_cond && _const_if_succ(curr, use_candidates) == 0) { curr_ws.const_cond = False; changed = True; } if (_debug_level >= 30) curr_ws.pretty_print(cout); if (changed || curr_ws.num_visits() == 1) { /// ... Exiting constant map has changed, so place /// ... the statements successors on the work list so /// ... that they can update their constant mappings /// ... with my new constant mapping. _put_succ_on_work_list(work_list, curr, use_candidates); } } } } } /// is_block_unreachable /// Return True if the block fo code between the given pair of statements /// is unreachable code. static Boolean _is_block_unreachable(const StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt) { /// ... Note: implied goto statements must be ignored because the /// ... insertion and deletion of the pseudo-ELSEs may leave visited /// ... implied gotos. Boolean is_block_unreachable = True; Iterator<Statement> iter = stmts.iterator(first_stmt, last_stmt); for ( ; iter.valid() && is_block_unreachable; ++iter) if (iter.current().stmt_class() != IMPLIED_GOTO_STMT && _get_workspace(iter.current()).num_visits() > 0) is_block_unreachable = False; return is_block_unreachable; } /// remove_unreachable /// Remove any dead code in the program. static void _remove_unreachable(StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt, const Map<Symbol,IntElem> &use_candidates) { Boolean deleted_a_stmt = False; /// ... Delete all IF statements where only one branch is taken. Iterator<Statement> iter = stmts.iterator(first_stmt, last_stmt); for ( ; iter.valid(); ++iter) if (iter.current_valid()) { Statement &stmt = iter.current(); if ((stmt.stmt_class() == IF_STMT || stmt.stmt_class() == ELSEIF_STMT || stmt.stmt_class() == ARITHMETIC_IF_STMT) && _get_workspace(stmt).num_visits() > 0 && _get_workspace(stmt).const_cond) { if (_debug_level >= 5) { cout << "! If statement: "; stmt.print_debug(cout, 0); cout << " is constant. Attempting to remove it.\n"; } Statement *target = _const_if_succ(stmt, use_candidates); p_assert(target, "IF statement does not have a constant conditional."); if (stmt.stmt_class() == ARITHMETIC_IF_STMT) { /// ... Replace the arithmetic if with a goto to its single /// ... successor. Statement *goto_target = new GotoStmt(stmts.new_tag(), target); goto_target->work_stack().push( new PropConstWS(_get_workspace(stmt))); stmts.modify(stmt, goto_target); } else if (stmt.stmt_class() == ELSEIF_STMT) { /// ... Currently, don't allow ELSEIF stmts to be deleted. } else if (stmt.stmt_class() == IF_STMT && stmt.follow_ref()->stmt_class() == ELSEIF_STMT && target == stmt.follow_ref()) { /// ... Delete the IF part of an IF () THEN ... ELSEIF statement /// ... Currently, do nothing. } else { /// ... Delete the IF statement only if none of the statements /// ... in the not-taken branch is reachable. if ((target == stmt.next_ref() && _is_block_unreachable(stmts, *stmt.follow_ref(), *stmt.matching_endif_ref()->prev_ref())) || (target == stmt.follow_ref() && _is_block_unreachable(stmts, *stmt.next_ref(), *stmt.follow_ref()->prev_ref()))) stmts.del(stmt); else { /// ... Make sure that the ELSE or ELSEIF part of IF /// ... statement isn't deleted by marking it as reachable. if (target == stmt.next_ref() && stmt.follow_ref()->stmt_class() != ENDIF_STMT) _get_workspace(*stmt.follow_ref()).incr_num_visits(); } } deleted_a_stmt = True; } } /// ... Delete all unreachable code. RefSet<Statement> unreachable_stmts; for (iter.reset(); iter.valid(); ++iter) if (iter.current().stmt_class() != FLOW_ENTRY_STMT && _get_workspace(iter.current()).num_visits() == 0) unreachable_stmts.ins(iter.current()); deleted_a_stmt = deleted_a_stmt || unreachable_stmts.entries() > 0; /// ... Check for the case of an ENDDO statement being unreachable. /// ... In this case, if the associated DO is reachable, /// ... then DO will be deleted when the ENDDO is deleted, /// ... so we must place an assignment statement for the loop index, /// ... assigning the initial value of the index, /// ... plus the loop-entry test. /// ... If the associated DO is not reachable either, then don't /// ... insert the assignment or the IF at all (and the /// ... whole loop should vanish). for (Iterator<Statement> st_iter = unreachable_stmts; st_iter.valid(); ++st_iter) { Statement & stmt = st_iter.current(); if (stmt.stmt_class() == ENDDO_STMT) { Statement * dostmt = stmt.follow_ref(); if (!unreachable_stmts.member(*dostmt)) { AssignmentStmt *assign = new AssignmentStmt(stmts.new_tag(), dostmt->index().clone(), dostmt->init().clone()); stmts.ins_before(assign, dostmt); /// ... Statement &newif = stmts.ins_IF_after ( ge(dostmt->limit().clone(), dostmt->index().clone()), assign, &stmt); } } } stmts.del(unreachable_stmts); if (deleted_a_stmt) { stmts.create_flow_graph(); /// ... remove_trivial_gotos(pgm); } } /// propagate_constants1 - /// Main routine of propagate_constants. /// Perform forward substitution of scalar variables throughout given /// statement block. static void _propagate_constants1(StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt, Map<Symbol,IntElem> &def_candidates, Map<Symbol,IntElem> &use_candidates, Array<Symbol *> &tag_to_candidate, RefSet<Statement> &pseudo_stmts, PC_UNREACH_BOOL remove_unreachable, int debug) { /// ... Set of entry points into the given block of statements. RefSet<Statement> entry_points; /// ... An array that maps integers to statements. Array<Statement *> toporder_to_stmt; _debug_level = debug; Timer tot_timer; Timer timer; /// ... Initialize /// ... clear_substituted_var(); _pass_tag = create_pass_tag(); _init_workspaces(stmts, first_stmt, last_stmt, def_candidates, use_candidates, tag_to_candidate); _make_nonlocals_modified_at_calls(stmts, first_stmt, last_stmt, use_candidates, tag_to_candidate); _patch_flow_graph(stmts, first_stmt, last_stmt); _determine_entry_points(stmts, first_stmt, last_stmt, entry_points); _calc_toporder(stmts, first_stmt, last_stmt, entry_points, 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. Map<Symbol,Expression> entering_constants; _iterate_to_fixed_point(stmts, first_stmt, last_stmt, entry_points, toporder_to_stmt, use_candidates, tag_to_candidate, entering_constants); if (_debug_level > 0) { cout << "! Iterating to fixed point: " << timer << endl; timer.reset(); } /// ... Annotate all the expressions in the program with the calculated /// ... constant values _annotate_stmts(stmts, first_stmt, last_stmt, use_candidates); if (_debug_level > 0) cout << "! Annotating pgm with constants: " << timer << endl; if (_debug_level >= 10) _dump_workspaces(cout, stmts, first_stmt, last_stmt); /// ... Remove any deadcode from the program, if desired. if (remove_unreachable == REMOVE_UNREACH_CODE) { stmts.del(pseudo_stmts); _remove_unreachable(stmts, first_stmt, last_stmt, use_candidates); if (_debug_level > 0) { cout << "! Removing unreachable code: " << timer << endl; timer.reset(); } } /// ... Clean up Iterator<Statement> stmt_iter = stmts.iterator(first_stmt, last_stmt); for ( ; stmt_iter.valid(); ++stmt_iter) stmt_iter.current().work_stack().pop(_pass_tag); if (_debug_level > 0) { int num_stmts = _num_stmts_in_block(stmts, first_stmt, last_stmt); cout << "! Total time: " << tot_timer << endl; cout << "! Number of statements: " << num_stmts << endl; cout << "! Number of candidate variables: " << use_candidates.entries() << endl; } } /// propagate_constants_all_vars /// Perform constant propagation for all variables in the given statement /// block. static void _propagate_constants_all_vars(StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt, RefSet<Statement> &pseudo_stmts, PC_REAL_BOOL subst_reals, PC_ARRAY_BOOL subst_arrays, PC_UNREACH_BOOL remove_unreachable, int debug) { /// ... Set of all variables that are candidates for forward substitution Map<Symbol,IntElem> def_candidates; /// ... Set of all variables that may be in the constant symbolic values /// ... for a variable in def_candidates. Map<Symbol,IntElem> use_candidates; /// ... An array that maps integers to variable candidates. Array<Symbol *> tag_to_candidate; if (remove_unreachable == REMOVE_UNREACH_CODE) _add_control_assigns(stmts, first_stmt, last_stmt, 0, pseudo_stmts); _collect_candidates(stmts, first_stmt, last_stmt, def_candidates, use_candidates, tag_to_candidate, subst_reals, subst_arrays); _propagate_constants1(stmts, first_stmt, last_stmt, def_candidates, use_candidates, tag_to_candidate, pseudo_stmts, remove_unreachable, debug); } /// propagate_constants_all_vars /// Perform constant propagation for only the variables in candidates for /// the given statement block. static void _propagate_constants_some_vars(StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt, const RefSet<Symbol> &candidates, RefSet<Statement> &pseudo_stmts, PC_UNREACH_BOOL remove_unreachable, int debug) { /// ... Set of all variables that are candidates for forward substitution Map<Symbol,IntElem> def_candidates; /// ... Set of all variables that may be in the constant symbolic values /// ... for a variable in def_candidates. Map<Symbol,IntElem> use_candidates; /// ... An array that maps integers to variable candidates. Array<Symbol *> tag_to_candidate; if (remove_unreachable == REMOVE_UNREACH_CODE) _add_control_assigns(stmts, first_stmt, last_stmt, &candidates, pseudo_stmts); _collect_candidates(candidates, stmts, first_stmt, last_stmt, def_candidates, use_candidates, tag_to_candidate); _propagate_constants1(stmts, first_stmt, last_stmt, def_candidates, use_candidates, tag_to_candidate, pseudo_stmts, remove_unreachable, debug); } /// propagate_constants - /// Perform forward substitution of scalar variables throughout pgm. void propagate_constants(StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt, PC_REAL_BOOL subst_reals, PC_ARRAY_BOOL subst_arrays, PC_UNREACH_BOOL remove_unreachable, int debug GIV(0)) { RefSet<Statement> pseudo_stmts; _propagate_constants_all_vars(stmts, first_stmt, last_stmt, pseudo_stmts, subst_reals, subst_arrays, remove_unreachable, debug); } void propagate_constants(ProgramUnit &pgm, PC_REAL_BOOL subst_reals, PC_ARRAY_BOOL subst_arrays, PC_UNREACH_BOOL remove_unreachable, int debug GIV(0)) { if (pgm.stmts().entries() <= 0) return; StmtList &stmts = pgm.stmts(); const Statement &first_stmt = *stmts.first_ref(); const Statement &last_stmt = *stmts.last_ref(); RefSet<Statement> pseudo_stmts; _add_data_assigns(pgm, 0, subst_reals, pseudo_stmts); _propagate_constants_all_vars(stmts, first_stmt, last_stmt, pseudo_stmts, subst_reals, subst_arrays, remove_unreachable, debug); if (remove_unreachable == REMOVE_UNREACH_CODE) remove_trivial_gotos(pgm); } void propagate_constants(StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt, const RefSet<Symbol> &candidates, PC_UNREACH_BOOL remove_unreachable, int debug GIV(0)) { RefSet<Statement> pseudo_stmts; _propagate_constants_some_vars(stmts, first_stmt, last_stmt, candidates, pseudo_stmts, remove_unreachable, debug); } void propagate_constants(ProgramUnit &pgm, const RefSet<Symbol> &candidates, PC_UNREACH_BOOL remove_unreachable, int debug GIV(0)) { if (pgm.stmts().entries() <= 0) return; StmtList &stmts = pgm.stmts(); const Statement &first_stmt = *stmts.first_ref(); const Statement &last_stmt = *stmts.last_ref(); RefSet<Statement> pseudo_stmts; _add_data_assigns(pgm, &candidates, SUBST_REALS, pseudo_stmts); _propagate_constants_some_vars(stmts, first_stmt, last_stmt, candidates, pseudo_stmts, remove_unreachable, debug); if (remove_unreachable == REMOVE_UNREACH_CODE) remove_trivial_gotos(pgm); } /// propagate_constants_pu extern "C" int propagate_constants_pu(char **data, int *len) { P_ASSERT_HANDLER(0); external_interface_init(); ProgramUnit *pgm = external_program_unit( data, len ); p_assert( pgm, "not a program unit" ); propagate_constants(*pgm, (PC_REAL_BOOL) switch_value("pc_real"), (PC_ARRAY_BOOL) switch_value("pc_array"), (PC_UNREACH_BOOL) switch_value("pc_unreach")); return setup_to_return_handle( pgm->pu_tag_ref(), data, len); } /// init_ipcp_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_ipcp_workspaces(StmtList &stmts, const IPCPProcData &proc_data, const Map<Symbol,IntElem> &def_candidates, const Map<Symbol,IntElem> &use_candidates, const Array<Symbol *> &tag_to_candidate) { Iterator<Statement> iter = stmts.iterator(); for ( ; iter.valid(); ++iter) { const Statement &stmt = iter.current(); PropConstWS *my_ws; const IPCPCallData *call_data = proc_data.call_data(stmt); if (call_data && call_data->data_ref()) { my_ws= new PropConstWS(_pass_tag, stmt, stmt, *call_data->data_ref(), proc_data, True, def_candidates, use_candidates, tag_to_candidate); stmt.work_stack().push(my_ws); ++iter; const Statement &call_succ = iter.current(); p_assert(call_succ.stmt_class() == LABEL_STMT, "Couldn't find dummy label statement after procedure call."); my_ws= new PropConstWS(_pass_tag, call_succ, stmt, *call_data->data_ref(), proc_data, False, def_candidates, use_candidates, tag_to_candidate); call_succ.work_stack().push(my_ws); } else { my_ws= new PropConstWS(_pass_tag, stmt, def_candidates, use_candidates, tag_to_candidate); stmt.work_stack().push(my_ws); } } } /// _build_modified_vars. /// Build and return the set of variables modified by the program, /// ignoring the side-effect of the given statements. static RefSet<Symbol> * _build_modified_vars(const StmtList &stmts, const RefSet<Statement> &ignorable_stmts, const Array<Symbol *> &tag_to_candidate) { RefSet<Symbol> *modified_vars = new RefSet<Symbol>; Iterator<Statement> stmt_iter = stmts.iterator(); for ( ; stmt_iter.valid(); ++stmt_iter) { Statement &stmt = stmt_iter.current(); PropConstWS &ws = _get_workspace(stmt); if (! ignorable_stmts.member(stmt) && ws.num_visits() > 0) { for (int sym_tag = ws.mod_set.first(); sym_tag != -1; sym_tag = ws.mod_set.next(sym_tag)) modified_vars->ins(*tag_to_candidate[sym_tag]); } } return modified_vars; } /// alias_consts /// Compute the set of actual parameters that are aliased to formal /// parameters, where it is safe to replace the actual parameters with /// the formal parameters. /// static void _alias_consts(RefSet<Symbol> &alias_consts, RefMap<Symbol,Symbol> &alias_const_map, const RefList<Symbol> &formals, const List<Expression> &actuals, const RefSet<Symbol> &keepable_vars) { p_assert(formals.entries() == actuals.entries(), "JumpFunction::new_values(): The number of formals does not equal the number of actuals."); Iterator<Symbol> formal_iter = formals; Iterator<Expression> actual_iter = actuals; for ( ; formal_iter.valid(); ++formal_iter, ++actual_iter) { const Symbol &formal = formal_iter.current(); if (actual_iter.current().op() == ID_OP) { Symbol &actual = actual_iter.current().symbol(); if (! actual.is_array() && ! keepable_vars.member(actual) && ! alias_consts.member(actual) && actual.type() == formal.type()) { alias_consts.ins(actual); alias_const_map.ins(actual, formal); } } } } /// rename_alias_consts /// Rename all variables in the given mapping to their mapped values. static void _rename_alias_consts(Expression &expr, const RefMap<Symbol,Symbol> &alias_const_map) { if (expr.op() == ID_OP) { const Symbol *val = alias_const_map.find_ref(expr.symbol()); if (val) expr.symbol(*val); } else { Iterator<Expression> arg_iter = expr.arg_list(); for ( ; arg_iter.valid(); ++arg_iter) _rename_alias_consts(arg_iter.current(), alias_const_map); } } /// _remove_local_effects_from_expr /// Given an expression and a constant map, eliminate all locally modified /// variables form the expression, so that the final expression would /// be in terms of the initial values of the subroutine. static Expression * _remove_local_effects_from_expr1(Expression *expr, const PropConstMap &const_map, const Map<Symbol,IntElem> &candidates) { if (! expr) return expr; if (expr->op() == ID_OP) { const IntElem *tag_elem = candidates.find_ref(expr->symbol()); p_assert(tag_elem || expr->symbol().sym_class() != VARIABLE_CLASS, "_remove_local_effects_from_expr1(): Expression contains a var not in candidates."); if (tag_elem) { int sym_tag = tag_elem->value(); PropConstElem &curr_const = const_map[sym_tag]; p_assert(curr_const.last_mod(), "_remove_local_effects_from_expr1(): Expression contains a var with an undefined constant value."); if (curr_const.last_mod()->stmt_class() != FLOW_ENTRY_STMT && curr_const.last_mod()->stmt_class() != ENTRY_STMT) { Expression *subst_expr = 0; if (curr_const.state() == CONST) { PropConstWS &subst_ws = _get_workspace(*curr_const.last_mod()); if (! subst_ws.poisoned_vars[sym_tag]) { subst_ws.poisoned_vars.ins(sym_tag); subst_expr = curr_const.expr().clone(); subst_expr = _remove_local_effects_from_expr1(subst_expr, subst_ws.in_const_map, candidates); subst_ws.poisoned_vars.del(sym_tag); if (subst_expr && subst_expr->base_variable_ref()) subst_expr = paren(subst_expr); } } delete expr; expr = subst_expr; } } } else { Mutator<Expression> iter = expr->arg_list(); for ( ; iter.valid(); ++iter) { Assign<Expression> eas(iter.assign()); Expression *new_expr = _remove_local_effects_from_expr1(iter.pull(), const_map, candidates); if (! new_expr) { delete expr; return 0; } else eas = new_expr; } } return expr; } static Expression * _remove_local_effects_from_expr(Expression *expr, const PropConstMap &const_map, const Map<Symbol,IntElem> &candidates) { Expression *new_expr = _remove_local_effects_from_expr1(expr, const_map, candidates); if (! new_expr) new_expr = omega(); return new_expr; } /// _create_old_const_mods /// Create a mapping from old constants to new constants. static Map<Symbol, Expression> * _create_old_const_mods(const Map<Symbol,IntElem> &candidates, const PropConstMap &const_map, const RefSet<Symbol> &keepable_vars, const RefSet<Symbol> *modified_vars_ref) { Map<Symbol, Expression> *var_mods = new Map<Symbol, Expression>; KeyIterator<Symbol,IntElem> cand_iter = candidates; for ( ; cand_iter.valid(); ++cand_iter) { Symbol &var = cand_iter.current_key(); if (keepable_vars.member(var)) { Expression *var_mod = _remove_local_effects_from_expr(id(var), const_map, candidates); if ((var_mod->op() == ID_OP && &var_mod->symbol() == &var) || (var_mod->op() == OMEGA_OP && modified_vars_ref && ! modified_vars_ref->member(var))) delete var_mod; else var_mods->ins(var, var_mod); } } return var_mods; } /// subst_unkeepable_vars /// Substitute all unkeepable variables. static Expression * _subst_unkeepable_vars(Expression *expr, const RefSet<Symbol> &keepable_vars) { if (! expr) return expr; else if (expr->op() == ID_OP) { if (expr->symbol().sym_class() == VARIABLE_CLASS) { Expression *subst_expr = 0; if (expr->substituted_valid()) { subst_expr = _subst_unkeepable_vars(expr->grab_substituted(), keepable_vars); if (subst_expr && subst_expr->base_variable_ref()) subst_expr = paren(subst_expr); } if (subst_expr || ! keepable_vars.member(expr->symbol())) { delete expr; return subst_expr; } } } else { Mutator<Expression> iter = expr->arg_list(); for ( ; iter.valid(); ++iter) { Assign<Expression> eas(iter.assign()); Expression *new_arg = _subst_unkeepable_vars(iter.pull(), keepable_vars); if (new_arg) eas = new_arg; else { delete expr; return 0; } } } return expr; } /// _create_new_consts /// Create a set of newly generated symbolic constants. static Map<Symbol, Expression> * _create_new_consts(const Map<Symbol,IntElem> &candidates, const PropConstMap &const_map, const RefSet<Symbol> &keepable_vars) { Map<Symbol, Expression> *var_mods = new Map<Symbol, Expression>; KeyIterator<Symbol,IntElem> cand_iter = candidates; for ( ; cand_iter.valid(); ++cand_iter) { Symbol &var = cand_iter.current_key(); if (keepable_vars.member(var)) { Expression *var_expr = _annotate_expr(id(var), const_map, candidates); Expression *new_const = var_expr->grab_substituted(); delete var_expr; new_const = _subst_unkeepable_vars(new_const, keepable_vars); if (new_const) var_mods->ins(var, new_const); } } return var_mods; } /// call_arg_list /// Return a reference to the argument list of the given call site. static const List<Expression> & _call_arg_list(const Statement &call_site) { const List<Expression> *args = NULL; if (call_site.stmt_class() == CALL_STMT) args = &call_site.parameters_guarded().arg_list(); else if (call_site.stmt_class() == ASSIGNMENT_STMT && call_site.rhs().op() == FUNCTION_CALL_OP) args = &call_site.rhs().parameters_guarded().arg_list(); else p_abort("_call_arg_list(): Given statement is not a call statement or function call."); return *args; } /// contains_non_candidate_vars /// Return true if the expression contains a variable not in /// cadidates. static Boolean _contains_non_candidate_vars(const Expression &expr, const Map<Symbol, IntElem> &candidates) { if (expr.op() == ID_OP) { return (expr.symbol().sym_class() == VARIABLE_CLASS && ! candidates.member(expr.symbol())); } else { Iterator<Expression> arg_iter = expr.arg_list(); for ( ; arg_iter.valid(); ++arg_iter) if (_contains_non_candidate_vars(arg_iter.current(), candidates)) return True; } return False; } /// create_new_actual_consts /// Build a set of new actual expressions. static List<Expression> * _create_new_actual_consts(const Map<Symbol, IntElem> &candidates, const Statement &stmt, const IPCPProcData & /* proc_data */, const IPCPProcData &call_proc_data, const RefSet<Symbol> &keepable_vars) { PropConstWS &ws = _get_workspace(stmt); const RefList<Symbol> &call_formals = call_proc_data.param_list(); const List<Expression> &call_actuals = _call_arg_list(stmt); /// ... Compute the set of variable that are allowable in the actual /// ... expressions. RefSet<Symbol> alias_consts; RefMap<Symbol, Symbol> alias_const_map; _alias_consts(alias_consts, alias_const_map, call_formals, call_actuals, keepable_vars); RefSet<Symbol> *my_keepable_vars = new RefSet<Symbol>(keepable_vars); Iterator<Symbol> aconst_iter = alias_consts; for ( ; aconst_iter.valid(); ++aconst_iter) my_keepable_vars->ins(aconst_iter.current()); /// ... Compute the list of constant actuals. List<Expression> *actuals = new List<Expression>; p_assert(call_formals.entries() == call_actuals.entries(), "JumpFunction::new_values(): The number of formals does not equal the number of actuals."); Iterator<Symbol> formal_iter = call_formals; Iterator<Expression> actual_iter = call_actuals; for ( ; formal_iter.valid(); ++formal_iter, ++actual_iter) { const Symbol &formal = formal_iter.current(); Expression *actual_expr = actual_iter.current().clone(); if (_contains_non_candidate_vars(*actual_expr, candidates)) { delete actual_expr; actual_expr = omega(); } else { actual_expr = _annotate_expr(actual_expr, ws.in_const_map, candidates); actual_expr = _subst_unkeepable_vars(actual_expr, *my_keepable_vars); if (actual_expr) { _rename_alias_consts(*actual_expr, alias_const_map); if (actual_expr->base_variable_ref() == &formal) { delete actual_expr; actual_expr = omega(); } } else actual_expr = omega(); } actuals->ins_last(actual_expr); } delete my_keepable_vars; return actuals; } /// build_call_jump_function /// Build a jump function for each call site. static void _build_call_jump_functions(ProgramUnit &pgm, IPCPProcData &proc_data, const Map<Symbol, IntElem> &candidates, const RefSet<Symbol> *modified_vars_ref) { RefSet<Symbol> keepable_params; Iterator<Expression> param_iter = proc_data.entry().parameters_guarded().arg_list(); for ( ; param_iter.valid(); ++param_iter) keepable_params.ins(param_iter.current().symbol()); Iterator<Statement> stmt_iter = pgm.stmts().iterator(); for ( ; stmt_iter.valid(); ++stmt_iter) { const Statement &stmt = stmt_iter.current(); if (stmt.stmt_class() == CALL_STMT || (stmt.stmt_class() == ASSIGNMENT_STMT && stmt.rhs().op() == FUNCTION_CALL_OP)) { PropConstWS &ws = _get_workspace(stmt); if (ws.num_visits() > 0) { const IPCPCallData *c_data = proc_data.call_data(stmt); if (c_data && c_data->data_ref()) { const IPCPProcData &call_proc_data = *c_data->data_ref(); RefSet<Symbol> *keepable_vars = proc_data.local_vars(call_proc_data.usable_global_vars()); *keepable_vars += keepable_params; proc_data.create_jump_function( stmt, _create_old_const_mods(candidates, ws.in_const_map, *keepable_vars, modified_vars_ref), _create_new_consts(candidates, ws.in_const_map, *keepable_vars), _create_new_actual_consts(candidates, stmt, proc_data, call_proc_data, *keepable_vars)); delete keepable_vars; } } } } } /// ipcp_compute_constants /// Compute the constants for single procedure for interprocedural /// constant propagation. static void _ipcp_compute_constants(ProgramUnit &pgm, IPCPProcData &proc_data, const Map<Symbol,IntElem> &def_candidates, const Map<Symbol,IntElem> &use_candidates, Array<Symbol *> &tag_to_candidate, const Map<Symbol, Expression> &entering_constants) { /// ... Set of entry points into the given block of statements. RefSet<Statement> entry_points; /// ... An array that maps integers to statements. Array<Statement *> toporder_to_stmt; StmtList &stmts = pgm.stmts(); const Statement &first_stmt = *stmts.first_ref(); const Statement &last_stmt = *stmts.last_ref(); Timer timer; _pass_tag = create_pass_tag(); _init_ipcp_workspaces(stmts, proc_data, def_candidates, use_candidates, tag_to_candidate); _make_nonlocals_modified_at_calls(stmts, first_stmt, last_stmt, use_candidates, tag_to_candidate); _patch_flow_graph(stmts, first_stmt, last_stmt); _determine_entry_points(stmts, first_stmt, last_stmt, entry_points); _calc_toporder(stmts, first_stmt, last_stmt, entry_points, 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(stmts, first_stmt, last_stmt, entry_points, toporder_to_stmt, use_candidates, tag_to_candidate, entering_constants); if (_debug_level > 0) { cout << "! Iterating to fixed point: " << timer << endl; timer.reset(); } if (_debug_level >= 10) _dump_workspaces(cout, stmts, first_stmt, last_stmt); } /// ipcp_build_jump_functions /// Build the jump functions for the given proc_data object. void _ipcp_build_jump_functions(ProgramUnit &pgm, IPCPProcData &proc_data, const RefSet<Symbol> &def_vars, const RefSet<Symbol> &use_vars, const Map<Symbol, Expression> &entering_constants, int debug GIV(0)) { /// ... Set of all variables that are candidates for forward substitution Map<Symbol,IntElem> def_candidates; /// ... Set of all variables that may be in the constant symbolic values /// ... for a variable in def_candidates. Map<Symbol,IntElem> use_candidates; /// ... An array that maps integers to variable candidates. Array<Symbol *> tag_to_candidate; /// ... Set of pseudo statements inserted to represent constants from control /// ... flow. RefSet<Statement> pseudo_stmts; StmtList &stmts = pgm.stmts(); const Statement &first_stmt = *stmts.first_ref(); const Statement &last_stmt = *stmts.last_ref(); _debug_level = debug; Timer tot_timer; Timer timer; /// ... Initialize _add_control_assigns(pgm.stmts(), first_stmt, last_stmt, 0, pseudo_stmts); _init_candidates(def_vars, use_vars, def_candidates, use_candidates, tag_to_candidate); /// ... Compute my constants. _ipcp_compute_constants(pgm, proc_data, def_candidates, use_candidates, tag_to_candidate, entering_constants); /// ... If some pseudo-statements were added to the program, compute the /// ... set of variables modified by the program, ignoring pseudo-statements /// ... and unreachable statements. RefSet<Symbol> *modified_vars = 0; if (pseudo_stmts.entries() > 0) modified_vars = _build_modified_vars(pgm.stmts(), pseudo_stmts, tag_to_candidate); /// ... Build the jump functions. _build_call_jump_functions(pgm, proc_data, use_candidates, modified_vars); p_assert(last_stmt.stmt_class() == FLOW_EXIT_STMT, "Last statement of program is not a flow-exit statement."); PropConstWS &flow_exit_ws = _get_workspace(last_stmt); RefSet<Symbol> *keepable_vars = proc_data.local_vars(proc_data.usable_global_vars()); proc_data.create_return_jump_function( _create_old_const_mods(use_candidates, flow_exit_ws.in_const_map, *keepable_vars, modified_vars), _create_new_consts(use_candidates, flow_exit_ws.in_const_map, *keepable_vars)); delete keepable_vars; if (modified_vars) delete modified_vars; if (_debug_level > 0) { cout << "! Building jump functions: " << timer << endl; timer.reset(); } /// ... Clean up pgm.stmts().del(pseudo_stmts); if (_debug_level > 0) { cout << "! Removing pseudo-statements: " << timer << endl; timer.reset(); } Iterator<Statement> stmt_iter = stmts.iterator(first_stmt, last_stmt); for ( ; stmt_iter.valid(); ++stmt_iter) stmt_iter.current().work_stack().pop(_pass_tag); if (_debug_level > 0) { int num_stmts = _num_stmts_in_block(stmts, first_stmt, last_stmt); cout << "! Total time: " << tot_timer << endl; cout << "! Number of statements: " << num_stmts << endl; cout << "! Number of candidate variables: " << use_candidates.entries() << endl; } } /// ipcp_propagate_constants /// Propagate constants within a single procedure for interprocedural /// constant propagation. void _ipcp_propagate_constants(ProgramUnit &pgm, IPCPProcData &proc_data, const RefSet<Symbol> &def_vars, const RefSet<Symbol> &use_vars, PC_UNREACH_BOOL remove_unreachable, const Map<Symbol, Expression> &entering_constants, int debug GIV(0)) { /// ... Set of all variables that are candidates for forward substitution Map<Symbol,IntElem> def_candidates; /// ... Set of all variables that may be in the constant symbolic values /// ... for a variable in def_candidates. Map<Symbol,IntElem> use_candidates; /// ... An array that maps integers to variable candidates. Array<Symbol *> tag_to_candidate; /// ... Set of pseudo statements inserted to represent constants from control /// ... flow. RefSet<Statement> pseudo_stmts; StmtList &stmts = pgm.stmts(); const Statement &first_stmt = *stmts.first_ref(); const Statement &last_stmt = *stmts.last_ref(); _debug_level = debug; Timer tot_timer; Timer timer; /// ... Initialize _add_control_assigns(pgm.stmts(), first_stmt, last_stmt, 0, pseudo_stmts); _init_candidates(def_vars, use_vars, def_candidates, use_candidates, tag_to_candidate); /// ... Compute my constants. _ipcp_compute_constants(pgm, proc_data, def_candidates, use_candidates, tag_to_candidate, entering_constants); /// ... Annotate all the expressions in the program with the calculated /// ... constant values _annotate_stmts(stmts, first_stmt, last_stmt, use_candidates); if (_debug_level > 0) cout << "! Annotating pgm with constants: " << timer << endl; /// ... Remove any deadcode from the program, if desired. pgm.stmts().del(pseudo_stmts); if (remove_unreachable == REMOVE_UNREACH_CODE) _remove_unreachable(stmts, first_stmt, last_stmt, use_candidates); if (_debug_level > 0) { cout << "! Removing unreachable code: " << timer << endl; timer.reset(); } /// ... Clean up Iterator<Statement> stmt_iter = stmts.iterator(first_stmt, last_stmt); for ( ; stmt_iter.valid(); ++stmt_iter) stmt_iter.current().work_stack().pop(_pass_tag); if (_debug_level > 0) { int num_stmts = _num_stmts_in_block(stmts, first_stmt, last_stmt); cout << "! Total time: " << tot_timer << endl; cout << "! Number of statements: " << num_stmts << endl; cout << "! Number of candidate variables: " << use_candidates.entries() << endl; } } /// _assert_clear_substituted /// Remove all constant subexpression annotations from all expressions in /// all assertions of the given statement. static void _assert_clear_substituted(Statement &stmt) { Iterator<Assertion> ass_iter = stmt.assertions(); for ( ; ass_iter.valid(); ++ass_iter) { if (ass_iter.current().arg_list_valid()) { Mutator<Expression> aexpr_iter = ass_iter.current().arg_list_guarded(); for ( ; aexpr_iter.valid(); ++aexpr_iter) clear_substituted(aexpr_iter.current()); } } } /// clear_substituted /// Remove all constant subexpression annotations from all expressions in /// the given object. This object may be a ProgramUnit, a Statement or an /// Expression. Ain't polymorphism grand. void clear_substituted(ProgramUnit &pgm) { if (pgm.stmts().entries()) clear_substituted(pgm.stmts(), *pgm.stmts().first_ref(), *pgm.stmts().last_ref()); } void clear_substituted(StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt) { Iterator<Statement> iter = stmts.iterator(first_stmt, last_stmt); for ( ; iter.valid(); ++iter) clear_substituted(iter.current()); } void clear_substituted(Statement &stmt) { Iterator<Expression> iter = stmt.iterate_expressions(); for ( ; iter.valid(); ++iter) clear_substituted(iter.current()); _assert_clear_substituted(stmt); } void clear_substituted(Expression &expr) { if (expr.op() == ID_OP) expr.substituted(0); else { Iterator<Expression> iter = expr.arg_list(); for ( ; iter.valid(); ++iter) clear_substituted(iter.current()); } } extern "C" int clear_substituted_pu(char **data, int *len) { P_ASSERT_HANDLER(0); external_interface_init(); ProgramUnit *pgm = external_program_unit( data, len ); p_assert( pgm, "not a program unit" ); clear_substituted(*pgm); return setup_to_return_handle( pgm->pu_tag_ref(), data, len); } /// substituted_var /// Return True if expand_substituted substituted at least one variable. Boolean substituted_var() { return _substituted_var; } /// clear_substituted_var /// Set the substituted_var flag to false (0). void clear_substituted_var() { _substituted_var = False; } /// _assert_expand_substituted /// Replace some variables with their precomputed constant expressions for /// all expressions in all assertions of the given statement. /// Do this for all assertions except INDUCTION, FIRSTVALUE, RANGEWRITTEN assertions static void _assert_expand_substituted(Statement &stmt, Boolean (* expr_filter)(const Expression &), Boolean (* const_filter)(const Expression &)) { Iterator<Assertion> ass_iter = stmt.assertions(); for ( ; ass_iter.valid(); ++ass_iter) { /// ... Don't expand in INDUCTION assertions if ((ass_iter.current().type() == AS_INDUCTION) || (ass_iter.current().type() == AS_FIRSTVALUE) || (ass_iter.current().type() == AS_RANGEWRITTEN)) continue; if (ass_iter.current().arg_list_valid()) { Mutator<Expression> aexpr_iter = ass_iter.current().arg_list_guarded(); for ( ; aexpr_iter.valid(); ++aexpr_iter) { Assign<Expression> eas(aexpr_iter.assign()); eas = expr_expand_substituted(aexpr_iter.pull(), expr_filter, const_filter); } } } } /// call_args_expand_substituted /// Expand all constants in the given list of expressions, except for /// those constants at the top level. This function is used to /// make sure that potentially aliased subroutine or function arguments /// are not removed by constant propagation. static void _call_args_expand_substituted(Expression &comma_expr, Boolean (* expr_filter)(const Expression &), Boolean (* const_filter)(const Expression &)) { p_assert(comma_expr.op() == COMMA_OP, "Parameters to subroutine or function call is not a comma expression."); Mutator<Expression> arg_iter = comma_expr.arg_list(); for ( ; arg_iter.valid(); ++arg_iter) if (arg_iter.current().op() == ID_OP) arg_iter.current().substituted(0); else { Assign<Expression> eas(arg_iter.assign()); eas = expr_expand_substituted(arg_iter.pull(), expr_filter, const_filter); } } /// expand_substituted /// Replace some variables with their precomputed constant expressions for /// all expressions in the given object. This method requires two filter /// functions to determine whether a certain variable is to be substituted. /// The first filter function tests a subexpression of the current expression /// whose variables are being substituted. If it returns false, none of the /// variables inside this subexpression will substituted. The second function /// tests the constant expression associated with a variable to be /// substituted. If this function returns false, the variable is not /// substituted with that expression. void expand_substituted(ProgramUnit &pgm, Boolean (* expr_filter)(const Expression &) GIV(0), Boolean (* const_filter)(const Expression &) GIV(0)) { if (pgm.stmts().entries()) expand_substituted(pgm.stmts(), *pgm.stmts().first_ref(), *pgm.stmts().last_ref(), expr_filter, const_filter); } void expand_substituted(StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt, Boolean (* expr_filter)(const Expression &) GIV(0), Boolean (* const_filter)(const Expression &) GIV(0)) { Iterator<Statement> iter = stmts.iterator(first_stmt, last_stmt); for ( ; iter.valid(); ++iter) expand_substituted(iter.current(), expr_filter, const_filter); } void expand_substituted(Statement &stmt, Boolean (* expr_filter)(const Expression &) GIV(0), Boolean (* const_filter)(const Expression &) GIV(0)) { _assert_expand_substituted(stmt, expr_filter, const_filter); _stmt_substituted_var = False; if (stmt.stmt_class() == CALL_STMT) { if (stmt.parameters_valid()) _call_args_expand_substituted(stmt.parameters_guarded(), expr_filter, const_filter); } else { Mutator<Expression> iter = stmt.iterate_expressions(); for ( ; iter.valid(); ++iter) { Assign<Expression> eas(iter.assign()); eas = simplify(expr_expand_substituted(iter.pull(), expr_filter, const_filter)); } } if (_stmt_substituted_var) stmt.build_refs(); stmt.simplify_expressions(); } extern "C" int expand_substituted_pu(char **data, int *len) { P_ASSERT_HANDLER(0); external_interface_init(); ProgramUnit *pgm = external_program_unit( data, len ); p_assert( pgm, "not a program unit" ); expand_substituted(*pgm); return setup_to_return_handle( pgm->pu_tag_ref(), data, len); } /// is_constant_expr /// Return True if the given expression would simplify down to an integer /// constant or logical constant. static Boolean _is_constant_expr(const Expression &expr) { if (expr.arg_list().entries() == 0) return (expr.op() == INTEGER_CONSTANT_OP || expr.op() == LOGICAL_CONSTANT_OP); else if (expr.op() == INTRINSIC_CALL_OP) return _is_constant_expr(expr.parameters_guarded()); else { Iterator<Expression> iter = expr.arg_list(); for ( ; iter.valid(); ++iter) if (! _is_constant_expr(iter.current())) return False; } return True; } /// expr_expand_substituted /// Acts similarly to the method expand_substituted() except that it applies /// to only a single expression. This method modifies the given expression /// and returns the result. Expression * expr_expand_substituted(Expression *expr, Boolean (* expr_filter)(const Expression &) GIV(0), Boolean (* const_filter)(const Expression &) GIV(0)) { if (! expr) return expr; Expression *result = expr; if (! expr_filter || expr_filter(*expr)) { if (expr->op() == ID_OP) { if (expr->substituted_valid()) { expr->substituted(expr_expand_substituted(expr->grab_substituted(), expr_filter, const_filter)); if (_is_constant_expr(expr->substituted_guarded())) expr->substituted(simplify(expr->grab_substituted())); if (! const_filter || const_filter(expr->substituted_guarded())) { result = expr->grab_substituted(); delete expr; _substituted_var = True; _stmt_substituted_var = True; } } } else if (expr->op() == FUNCTION_CALL_OP) { if (expr->parameters_valid()) _call_args_expand_substituted(expr->parameters_guarded(), expr_filter, const_filter); } else { Mutator<Expression> iter = expr->arg_list(); for ( ; iter.valid(); ++iter) { Assign<Expression> eas(iter.assign()); eas = expr_expand_substituted(iter.pull(), expr_filter, const_filter); } } } return result; } /// expand_linear_substituted /// Expand the variables whose constant expressions are linear for all /// expressions in the object. An expression is considered linear if it /// is made up of only additive and multiplicative operators. static inline Boolean _is_expr_top_linear(const Expression &expr) { switch(expr.op()) { case INTEGER_CONSTANT_OP: /// ... Let the leaf expressions be linear case REAL_CONSTANT_OP: case HOLLERITH_CONSTANT_OP: case LOGICAL_CONSTANT_OP: case COMPLEX_OP: case ARRAY_REF_OP: case ID_OP: case OMEGA_OP: case NOT_OP: /// ... Let the logical operations be linear case EQ_OP: case NE_OP: case LT_OP: case LE_OP: case GT_OP: case GE_OP: case OR_OP: case AND_OP: case EQV_OP: case NEQV_OP: case U_PLUS_OP: case U_MINUS_OP: case PAREN_OP: case SUB_OP: case ADD_OP: case MULT_OP: case COMMA_OP: return True; default: return False; } return False; } static Boolean _linear_const_filter(const Expression &expr) { if (! _is_expr_top_linear(expr)) return False; else { Iterator<Expression> iter = expr.arg_list(); for ( ; iter.valid(); ++iter) if (! _linear_const_filter(iter.current())) return False; } return True; } void expand_linear_substituted(ProgramUnit &pgm) { expand_substituted(pgm, &_is_expr_top_linear, &_linear_const_filter); } void expand_linear_substituted(StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt) { expand_substituted(stmts, first_stmt, last_stmt, &_is_expr_top_linear, &_linear_const_filter); } void expand_linear_substituted(Statement &stmt) { expand_substituted(stmt, &_is_expr_top_linear, &_linear_const_filter); } Expression * expr_expand_linear_substituted(Expression *expr) { return expr_expand_substituted(expr, &_is_expr_top_linear, &_linear_const_filter); } /// expand_small_substituted /// Expand the variables whose constant expressions are ID expressions /// or integer or logical constant expressions. static Boolean _is_constant_expr_filter(const Expression &expr) { if (expr.op() == ID_OP) return (expr.substituted_valid() && _is_constant_expr_filter(expr.substituted_guarded())); else if (expr.arg_list().entries() == 0) return (expr.op() == INTEGER_CONSTANT_OP || expr.op() == LOGICAL_CONSTANT_OP); else if (expr.op() == INTRINSIC_CALL_OP) return _is_constant_expr_filter(expr.parameters_guarded()); else { Iterator<Expression> iter = expr.arg_list(); for ( ; iter.valid(); ++iter) if (! _is_constant_expr_filter(iter.current())) return False; } return True; } static Boolean _small_const_filter(const Expression &expr) { return (expr.op() == ID_OP || _is_constant_expr_filter(expr)); } void expand_small_substituted(ProgramUnit &pgm) { expand_substituted(pgm, 0, &_small_const_filter); } void expand_small_substituted(StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt) { expand_substituted(stmts, first_stmt, last_stmt, 0, &_small_const_filter); } void expand_small_substituted(Statement &stmt) { expand_substituted(stmt, 0, &_small_const_filter); } Expression * expr_expand_small_substituted(Expression *expr) { return expr_expand_substituted(expr, 0, &_small_const_filter); } /// has_param_in_expr /// Return true if the given expression has a parameter variable /// contained within it. static Boolean _has_param_in_expr(const Expression &expr) { if (expr.op() == ID_OP) { return (expr.symbol().sym_class() == SYMBOLIC_CONSTANT_CLASS); } else { Iterator<Expression> iter = expr.arg_list(); for ( ; iter.valid(); ++iter) if (_has_param_in_expr(iter.current())) return True; } return False; } /// _assert_substitute_parameters /// Substitute all precomputed values for PARAMETER constants in all /// assertions of the given statement. static void _assert_substitute_parameters(Statement &stmt, PC_REAL_BOOL subst_reals) { Iterator<Assertion> ass_iter = stmt.assertions(); for ( ; ass_iter.valid(); ++ass_iter) { if (ass_iter.current().arg_list_valid()) { Mutator<Expression> aexpr_iter = ass_iter.current().arg_list_guarded(); for ( ; aexpr_iter.valid(); ++aexpr_iter) { Assign<Expression> eas(aexpr_iter.assign()); eas = expr_substitute_parameters(aexpr_iter.pull(), subst_reals); } } } } static void substitute_parameters_data(ProgramUnit &pgm, PC_REAL_BOOL subst_reals){ for(Iterator<Data> dit=pgm.data(); dit.valid(); ++dit){ Expression* values=dit.current().value_list().clone(); values=expr_substitute_parameters(values, subst_reals); dit.current().value_list((CommaExpr*)values); } } /// substitute_parameters /// Substitute all precomputed values for PARAMETER constants. void substitute_parameters(ProgramUnit &pgm, PC_REAL_BOOL subst_reals) { substitute_parameters(pgm.symtab(), subst_reals); /// ... silvius: must substitute them in DATA expressions. substitute_parameters_data(pgm, subst_reals); if (pgm.stmts().entries()) substitute_parameters(pgm.stmts(), *pgm.stmts().first_ref(), *pgm.stmts().last_ref(), subst_reals); } void substitute_parameters(Symtab &symtab, PC_REAL_BOOL subst_reals) { DictionaryIter<Symbol> sym_iter = symtab.iterator(); /// ... Substitute all parameters contained inside other parameters and /// ... simplify them down. for ( ; sym_iter.valid(); ++sym_iter) { Symbol &symbol = sym_iter.current(); if (symbol.sym_class() == SYMBOLIC_CONSTANT_CLASS && _has_param_in_expr(*symbol.expr_ref())) { Expression *new_expr = expr_substitute_parameters(symbol.expr_ref()->clone(), subst_reals); new_expr = simplify(new_expr); symbol.expr(new_expr); } } /// ... Substitute all parameters found in the bounds of arrays. for ( sym_iter.reset(); sym_iter.valid(); ++sym_iter) if (sym_iter.current().sym_class() == VARIABLE_CLASS) { Iterator<ArrayBounds> bound_iter = sym_iter.current().dim(); for ( ; bound_iter.valid(); ++bound_iter) { ArrayBounds &bound = bound_iter.current(); if (bound.lower_exists() && bound.lower_ref()->op() != INTEGER_CONSTANT_OP) { Expression *new_lower = expr_substitute_parameters(bound.lower_ref()->clone(), subst_reals); new_lower = simplify(new_lower); bound.lower(new_lower); } if (bound.upper_exists() && bound.upper_ref()->op() != INTEGER_CONSTANT_OP) { Expression *new_upper = expr_substitute_parameters(bound.upper_ref()->clone(), subst_reals); new_upper = simplify(new_upper); bound.upper(new_upper); } } } } void substitute_parameters(StmtList &stmts, const Statement &first_stmt, const Statement &last_stmt, PC_REAL_BOOL subst_reals) { Iterator<Statement> iter = stmts.iterator(first_stmt, last_stmt); for ( ; iter.valid(); ++iter) substitute_parameters(iter.current(), subst_reals); } void substitute_parameters(Statement &stmt, PC_REAL_BOOL subst_reals) { _assert_substitute_parameters(stmt, subst_reals); Mutator<Expression> iter = stmt.iterate_expressions(); _stmt_substituted_var = False; for ( ; iter.valid(); ++iter) { Assign<Expression> eas(iter.assign()); eas = expr_substitute_parameters(iter.pull(), subst_reals); } if (_stmt_substituted_var) stmt.build_refs(); } /// expr_substitute_parameters /// Acts similarly to the method substitute_parameters() except that it /// applies to only a single expression. This method modifies the given /// expression and returns the result. Expression * expr_substitute_parameters(Expression *expr, PC_REAL_BOOL subst_reals) { if (! expr) return 0; Expression *result = expr; if (expr->op() == ID_OP) { if (expr->symbol().sym_class() == SYMBOLIC_CONSTANT_CLASS && _substitutable_type(expr->symbol().type().data_type(), subst_reals)) { result = expr->symbol().expr_ref()->clone(); delete expr; result = expr_substitute_parameters(result, subst_reals); _stmt_substituted_var = True; } else if (expr->substituted_valid()) expr->substituted(expr_substitute_parameters( expr->grab_substituted(), subst_reals)); } else { Mutator<Expression> iter = expr->arg_list(); for ( ; iter.valid(); ++iter) { Assign<Expression> eas(iter.assign()); eas = expr_substitute_parameters(iter.pull(), subst_reals); } } return result; } extern "C" int substitute_parameters_pu(char **data, int *len) { P_ASSERT_HANDLER(0); external_interface_init(); ProgramUnit *pgm = external_program_unit( data, len ); p_assert( pgm, "not a program unit" ); substitute_parameters(*pgm, (PC_REAL_BOOL) switch_value("sp_real")); return setup_to_return_handle( pgm->pu_tag_ref(), data, len); }

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