Polaris: deadcode.cc Source File

deadcode.cc Go to the documentation of this file. /// /// /// \file deadcode.cc /// /// #include "../Collection/Map.h" #include "../Collection/Iterator.h" #include "../Collection/Mutator.h" #include "../ProgramUnit.h" #include "../Statement/Statement.h" #include "../Directive/Assertion.h" #include "../utilities/switches_util.h" #include "../utilities/expression_util.h" #include "../utilities/equivalence_util.h" #include "../Data.h" #include "../IntElem.h" #include "../IntSet.h" #include "../Array.h" #include "../Boolean.h" #include "../Timer.h" #include "../p-assert.h" #include "../macros.h" #include "DeadCodeElimWS.h" #include "deadcode.h" #include "../Range/range.h" #include "../Range/AIRangeDict.h" #include "../Range/ControlRangeDict.h" #include "../Range/RangeAccessor.h" #include "../Range/RangeExpr.h" #include "../Range/range.h" #include "../Range/range_util.h" #include <set> static unsigned int _pass_tag; /// ... Pass tag associated with this pass static int _debug_level = 0; /// 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 ProgramUnit &pgm, Map<Symbol,IntElem> &candidates, Array<Symbol *> &tag_to_candidate, DCE_ARRAY_BOOL deadcode_arrays) { DictionaryIter<Symbol> sym_iter = pgm.symtab().iterator(); int tag = 0; tag_to_candidate.resize(pgm.symtab().entries()); for ( ; sym_iter.valid(); ++sym_iter) { Symbol &symbol = sym_iter.current(); switch(symbol.sym_class()) { case VARIABLE_CLASS: if (! symbol.is_array() || deadcode_arrays == DEADCODE_ARRAYS) { tag_to_candidate[tag] = &symbol; candidates.ins(symbol, new IntElem(tag++)); } break; default: continue; } } tag_to_candidate.resize(tag); p_assert(tag == candidates.entries(), "Error in Map<Symbol,IntElem>::entries()."); } /// init_workspaces /// Initialize the workspaces for each statement in the program. /// Note: A lot of the initialization for eliminate_dead_code are hidden /// in the constructor for DeadCodeElimWS. static void _init_workspaces(ProgramUnit &pgm, const Map<Symbol,IntElem> &candidates) { Iterator<Statement> iter = pgm.stmts().iterator(); for ( ; iter.valid(); ++iter) { DeadCodeElimWS *my_ws = new DeadCodeElimWS(_pass_tag, iter.current(), candidates); iter.current().work_stack().push(my_ws); } } /// get_workspace /// Get the workspace for the given statement. static DeadCodeElimWS & _get_workspace(const Statement &stmt) { WorkSpace *ws = stmt.work_stack().top_ref(_pass_tag); p_assert(ws, "Statement doesn't have a DeadCodeElimWS."); return * (DeadCodeElimWS *) ws; } /// dump_workspaces /// Dump out the data inside all of the workspaces of the program static void _dump_workspaces(ostream &o, const ProgramUnit &pgm, const Array<Symbol *> &tag_to_candidate) { Iterator<Statement> iter = pgm.stmts().iterator(); for ( ; iter.valid(); ++iter) { iter.current().structures_OK(); o << iter.current().tag() << ": "; iter.current().print_debug(o, 0); o << endl; _get_workspace(iter.current()).pretty_print(o, tag_to_candidate); } } /// _init_non_local_vars /// Initialize the sets of non-local and live-end variables. static void _init_non_local_vars(IntSet &non_local_vars, IntSet &live_end_vars, const ProgramUnit &pgm, const Map<Symbol,IntElem> &candidates, const Array<Symbol *> &tag_to_candidate) { /// ... Determine all variables that are contained in DATA statements. RefSet<Symbol> data_vars; Iterator<Data> data_iter = pgm.data(); for ( ; data_iter.valid(); ++data_iter) { Iterator<Expression> data_var_iter = data_iter.current().variable_list().arg_list(); for ( ; data_var_iter.valid(); ++data_var_iter) { Symbol *var = data_var_iter.current().base_variable_ref(); if (var) data_vars.ins(*var); } } for (int sym_tag = 0; sym_tag < tag_to_candidate.entries(); ++sym_tag) { Symbol &var = *tag_to_candidate[sym_tag]; switch (var.sym_class()) { case VARIABLE_CLASS: if (var.common_ref()) { non_local_vars.ins(sym_tag); live_end_vars.ins(sym_tag); /// ... Mark any variables aliased to the non-local variable /// ... as also non-local and live-end RefSet<Symbol> *aliases = equiv_aliases(var); if (aliases) { Iterator<Symbol> alias_iter = *aliases; for ( ; alias_iter.valid(); ++alias_iter) { const IntElem *alias_elem = candidates.find_ref(alias_iter.current()); if (alias_elem) { non_local_vars.ins(alias_elem->value()); live_end_vars.ins(alias_elem->value()); } } delete aliases; } } else if (var.formal() == IS_FORMAL || var.saved() == IS_SAVED || data_vars.member(var)) { live_end_vars.ins(sym_tag); /// ... Mark any variables aliased to the live-end variable /// ... as also live-end RefSet<Symbol> *aliases = equiv_aliases(var); if (aliases) { Iterator<Symbol> alias_iter = *aliases; for ( ; alias_iter.valid(); ++alias_iter) { const IntElem *alias_elem = candidates.find_ref(alias_iter.current()); if (alias_elem) live_end_vars.ins(alias_elem->value()); } delete aliases; } } break; default: continue; } } } /// _make_nonlocals_used_at_calls /// Make all non-local variables be marked as potentially used for all /// call statements and all statements containing function calls. static void _make_nonlocals_used_at_calls(StmtList &stmts, const IntSet &non_local_vars) { Iterator<Statement> iter = stmts.iterator(); for ( ; iter.valid(); ++iter) { Statement &stmt = iter.current(); if (stmt.stmt_class() == CALL_STMT || contains_func_call(stmt)) { DeadCodeElimWS &ws = _get_workspace(stmt); ws.use_set |= non_local_vars; ws.kill_set -= non_local_vars; } } } /// _compute_private_kill_sets /// Compute the set of array variables to kill for do loop bodies because /// they are private to the loop's body. static void _compute_private_kill_sets(StmtList &stmts, const Map<Symbol,IntElem> &candidates) { Iterator<Statement> stmt_iter = stmts.stmts_of_type(DO_STMT); for ( ; stmt_iter.valid(); ++stmt_iter) { Statement &stmt = stmt_iter.current(); RefSet<Symbol> private_vars; Iterator<Assertion> asrt_iter = stmt.assertions(); for ( ; asrt_iter.valid(); ++asrt_iter) { if (asrt_iter.current().type() == AS_PRIVATE) { Iterator<Expression> item_iter = asrt_iter.current().arg_list_guarded(); for ( ; item_iter.valid(); ++item_iter) { Symbol *var = item_iter.current().base_variable_ref(); if (var && var->is_array()) private_vars.ins(*var); } } } for (asrt_iter.reset(); asrt_iter.valid(); ++asrt_iter) { if (asrt_iter.current().type() == AS_FIRSTVALUE) { Iterator<Expression> item_iter = asrt_iter.current().arg_list_guarded(); for ( ; item_iter.valid(); ++item_iter) { Symbol *var = item_iter.current().base_variable_ref(); if (var && var->is_array() && private_vars.member(*var)) private_vars.del(*var); } } } if (private_vars.entries() > 0) { IntSet *my_private_kill_set = new IntSet(candidates.entries()); Iterator<Symbol> priv_iter = private_vars; for ( ; priv_iter.valid(); ++priv_iter) { const IntElem *elem = candidates.find_ref(priv_iter.current()); if (elem) my_private_kill_set->ins(elem->value()); } _get_workspace(stmt).private_kill_set(my_private_kill_set); } } } /// _calc_toporder /// Calculate toporder for the flow graph. Essentially, this algorithm /// performs a topological sort on the flow graph, ignoring back /// edges. static void _calc_toporder1(Statement &stmt, int &toporder) { DeadCodeElimWS &my_ws = _get_workspace(stmt); if (! my_ws.visited()) { my_ws.visited(1); Iterator<Statement> pred_iter = stmt.pred(); for ( ; pred_iter.valid(); ++pred_iter) _calc_toporder1(pred_iter.current(), toporder); my_ws.toporder(toporder--); } } static void _calc_toporder(ProgramUnit &pgm, Array<Statement *> &toporder_to_stmt) { /// ... Calculate the topological order for each statement int toporder = pgm.stmts().entries() - 1; if (toporder >= 0) { Iterator<Statement> exit_iter = pgm.stmts().stmts_of_type(FLOW_EXIT_STMT); for ( ; exit_iter.valid(); ++exit_iter) _calc_toporder1(exit_iter.current(), toporder); p_assert(toporder >= -1, "_calc_toporder visited a stmt more than once."); } /// ... Initialize toporder_to_stmt toporder_to_stmt.resize(pgm.stmts().entries()); for (int i = 0; i <= toporder; ++i) toporder_to_stmt[i] = 0; Iterator<Statement> iter = pgm.stmts().iterator(); for ( ; iter.valid(); ++iter) { int stmt_toporder = _get_workspace(iter.current()).toporder(); if (stmt_toporder >= 0) toporder_to_stmt[stmt_toporder] = &iter.current(); } } /// put_pred_on_work_list /// Put all of my predecessors on the work list. static void _put_pred_on_work_list(IntSet &work_list, Statement &stmt) { Iterator<Statement> pred_iter = stmt.pred(); for ( ; pred_iter.valid(); ++pred_iter) work_list.ins(_get_workspace(pred_iter.current()).toporder()); } /// iterate_to_fixed_point /// Propagate the constants contained in the statement's const_maps until /// a fixed point is reached. static void _iterate_to_fixed_point(ProgramUnit &pgm, const Array<Statement *> &toporder_to_stmt, const Map<Symbol,IntElem> & /* candidates */, const Array<Symbol *> &tag_to_candidate, const IntSet &flow_exit_vars) { /// ... List of statements that need to be updated. IntSet work_list(toporder_to_stmt.entries()); /// ... Mark all variables for entry statements as non-const and put all /// ... entries on the work list. Iterator<Statement> exit_iter = pgm.stmts().stmts_of_type(FLOW_EXIT_STMT); for ( ; exit_iter.valid(); ++exit_iter) work_list.ins(_get_workspace(exit_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); DeadCodeElimWS &curr_ws = _get_workspace(curr); curr_ws.incr_num_visits(); Boolean changed = False; /// ... Generate the new live variable set for the end of the statement. IntSet new_live_vars(tag_to_candidate.entries()); if (curr.stmt_class() == FLOW_EXIT_STMT) { if (pgm.pu_class() != PROGRAM_PU_TYPE) new_live_vars = flow_exit_vars; } else if (curr_ws.private_kill_set()) { p_assert(curr.stmt_class() == DO_STMT, "Only DO statements can have a non-NULL private_kill_set field."); const DeadCodeElimWS &body_ws = _get_workspace(*curr.next_ref()); if (body_ws.num_visits() > 0) { new_live_vars = body_ws.out_live_vars; new_live_vars -= *curr_ws.private_kill_set(); } const DeadCodeElimWS &exit_ws = _get_workspace(*curr.follow_ref()->next_ref()); if (exit_ws.num_visits() > 0) new_live_vars |= exit_ws.out_live_vars; } else { Iterator<Statement> succ_iter = curr.succ(); for ( ; succ_iter.valid(); ++succ_iter) { const DeadCodeElimWS &succ_ws = _get_workspace(succ_iter.current()); if (succ_ws.num_visits() > 0) new_live_vars |= succ_ws.out_live_vars; } } if (curr_ws.num_visits() == 1 || new_live_vars != curr_ws.in_live_vars) { /// ... New entering live variable set differs from the old /// ... one. So update the entering and exiting live variable /// ... sets for the statement. if (_debug_level >= 20) { cout << "! Statement "; curr.print_debug(cout, 0); cout << " was visited and updated.\n"; } curr_ws.in_live_vars = new_live_vars; changed = curr_ws.update_out_live_vars(); if (changed || curr_ws.num_visits() == 1) { /// ... Exiting live var set has changed, so place /// ... the statement's predecessors on the work list so /// ... that they can update their live variable sets /// ... with my live var set. _put_pred_on_work_list(work_list, curr); } if (_debug_level >= 30) curr_ws.pretty_print(cout, tag_to_candidate); } } } } /// remove_assertion /// Remove all assertions of the given type with the given variable. static void _remove_assertion(const Symbol &var, Statement &stmt, AssertionType atyp) { for (Iterator<Assertion> dirs = stmt.assertions(); dirs.valid(); ++dirs) { Assertion & ass = dirs.current(); if (ass.type() == atyp) { Mutator<Expression> items = ass.arg_list_guarded(); for ( ; items.valid(); ++items) if (items.current().base_variable_ref() == &var) items.del(); if (ass.arg_list_guarded().entries() == 0) stmt.assertions().del(ass); } } } /// _are_vars_in_expr /// Return true if the given expression uses any of the variables in the /// given set. static Boolean _are_vars_in_expr(const Expression &e, const RefSet<Symbol> &vars) { if (e.op() == ID_OP) return vars.member(e.symbol()); else { Iterator<Expression> iter = e.arg_list(); for ( ; iter.valid(); ++iter) if (_are_vars_in_expr(iter.current(), vars)) return True; } return False; } /// delete_dead_code /// Delete all dead code from a program unit. static void _delete_dead_code(ProgramUnit &pgm, const Array<Symbol *> tag_to_candidate, const IntSet &non_local_vars) { Iterator<Statement> stmt_iter = pgm.stmts().iterator(); IntSet pgm_live_vars = non_local_vars; for ( ; stmt_iter.valid(); ++stmt_iter) { Statement &stmt = stmt_iter.current(); const DeadCodeElimWS &ws = _get_workspace(stmt); pgm_live_vars |= ws.in_live_vars; if (! ws.is_dead_code() && stmt.stmt_class() != BLOCK_ENTRY_STMT) pgm_live_vars |= ws.kill_set; /// ... Delete all dead LAST VALUE assertions. if (stmt.stmt_class() == DO_STMT) { /// ... Look at the workspace of the statement after the DO loop's /// ... ENDDO statement. const DeadCodeElimWS &follow_ws = _get_workspace(*stmt.follow_ref()->next_ref()); for (int sym_tag = 0; sym_tag < tag_to_candidate.entries(); ++sym_tag) if (! follow_ws.out_live_vars[sym_tag]) { _remove_assertion(*tag_to_candidate[sym_tag], stmt, AS_LASTVALUE); _remove_assertion(*tag_to_candidate[sym_tag], stmt, AS_DYNLASTVALUE); } } /// ... Delete the statement if it is dead code. if (ws.is_dead_code()) { if (_debug_level >= 5) { cout << "! Deleted stmt: "; stmt.print_debug(cout, 0); cout << endl; } pgm.stmts().del(stmt); } } /// ... Compute the set of variables that are dead for the entire program RefSet<Symbol> dead_vars; for (int sym_tag = 0; sym_tag < tag_to_candidate.entries(); ++sym_tag) if (! pgm_live_vars[sym_tag]) dead_vars.ins(*tag_to_candidate[sym_tag]); /// ... Delete all assertions containing any of the dead variables. for (stmt_iter.reset() ; stmt_iter.valid(); ++stmt_iter) { Statement &stmt = stmt_iter.current(); Iterator<Assertion> dirs = stmt.assertions(); for ( ; dirs.valid(); ++dirs) { Assertion & ass = dirs.current(); if (ass.arg_list_valid() && (ass.arg_list_guarded().entries() != 0)) { Mutator<Expression> items = ass.arg_list_guarded(); for ( ; items.valid(); ++items) if (_are_vars_in_expr(items.current(), dead_vars)) items.del(); if (ass.arg_list_guarded().entries() == 0) stmt.assertions().del(ass); } } } /// ... Delete all dead variables from the symbol table. if (_debug_level >= 5) { cout << "! Dead symbols: {"; Iterator<Symbol> dead_iter = dead_vars; for ( ; dead_iter.valid(); ++dead_iter) cout << dead_iter.current().name_ref() << ", "; cout << "}\n"; } pgm.clean(); } void dfs_stmts(Statement& stmt, set<Statement*>& visited){ if (visited.find(&stmt)!=visited.end()){ /// ... Already visited. return; } else { /// ... First occurence visited.insert(&stmt); for(Iterator<Statement> stit=stmt.succ(); stit.valid(); ++stit){ dfs_stmts(stit.current(), visited); } } } /// silvius: eliminate all statements that cannot be reached from any entry. void eliminate_unreachable_statements(ProgramUnit& pgm){ set<Statement*> visited; Iterator<Statement> stit=pgm.stmts().stmts_of_type(ENTRY_STMT); for(; stit.valid(); ++stit){ dfs_stmts(stit.current(), visited); } RefSet<Statement> todel; for(Statement* ps=pgm.stmts().first_ref(); ps!=0; ps=ps->next_ref()){ if (visited.find(ps)==visited.end()){ /// ... Make sure we are not removing the flow entry. if (ps->stmt_class()!=FLOW_ENTRY_STMT){ /// ... Unreachable. todel.ins(*ps); } } } pgm.stmts().del(todel); pgm.stmts().build_all_refs(); } /// eliminate_dead_code /// Delete all dead code from a program unit. void eliminate_dead_code(ProgramUnit &pgm, DCE_ARRAY_BOOL deadcode_arrays GIV(DONT_DEADCODE_ARRAYS), int debug GIV(0)) { /// ... Set of all variables that are candidates for dead code elimination. Map<Symbol,IntElem> candidates; /// ... An array that maps integers to variable candidates. Array<Symbol *> tag_to_candidate; /// ... An array that maps integers to statements. Array<Statement *> toporder_to_stmt; _debug_level = debug; Timer tot_timer; Timer timer; /// ... Initialize _collect_candidates(pgm, candidates, tag_to_candidate, deadcode_arrays); _pass_tag = create_pass_tag(); _init_workspaces(pgm, candidates); IntSet non_local_vars(candidates.entries()); IntSet live_end_vars(candidates.entries()); _init_non_local_vars(non_local_vars, live_end_vars, pgm, candidates, tag_to_candidate); if (non_local_vars.first() != -1) _make_nonlocals_used_at_calls(pgm.stmts(), non_local_vars); if (deadcode_arrays == DEADCODE_ARRAYS) _compute_private_kill_sets(pgm.stmts(), candidates); _calc_toporder(pgm, toporder_to_stmt); if (_debug_level > 0) { cout << "! Initialization: " << timer << endl; timer.reset(); } /// ... Iteratively propagate the constants throughout the program until a /// ... fixed point is reached. _iterate_to_fixed_point(pgm, toporder_to_stmt, candidates, tag_to_candidate, live_end_vars); if (_debug_level > 0) { cout << "! Iterating to fixed point: " << timer << endl; timer.reset(); } /// ... Delete all dead code from the program unit. _delete_dead_code(pgm, tag_to_candidate, live_end_vars); if (_debug_level > 0) cout << "! Deleting dead code: " << timer << endl; if (_debug_level >= 10) _dump_workspaces(cout, pgm, tag_to_candidate); /// ... Clean up pgm.clean_workspace(_pass_tag); if (_debug_level > 0) { cout << "! Total time: " << tot_timer << endl; cout << "! Number of statements: " << pgm.stmts().entries() << endl; cout << "! Number of candidate variables: " << candidates.entries() << endl; } /// ... silvius: eliminate_unreachable_statements(pgm); /// ... This test is a kluge. This causes the code below to run /// ... before privatization and not after. When this is done /// ... permanently, we'll figure out a better way. /// ... The stuff below eliminates IF statements whose conditions are /// ... found (through range propagation) to be constant, either .TRUE. /// ... or .FALSE. . The IF itself and the appropriate side of the IF are /// ... removed. /// if (deadcode_arrays == DONT_DEADCODE_ARRAYS) { /// AIRangeDict *ranges = new AIRangeDict ( pgm ); /// /// Iterator<Statement> if_iter = pgm.stmts().stmts_of_type (IF_STMT); /// /// for (; if_iter.valid(); ++if_iter) { /// Statement & ifstmt = if_iter.current(); /// RangeAccessor if_ranges ( *ranges, ifstmt ); /// /// Expression *ifcondition = ifstmt.expr().clone(); /// if_ranges.eliminate_vars (ifcondition, NULL); /// /// if (ifcondition->op() == LOGICAL_CONSTANT_OP) { /// if (ifcondition->str_data() == ".TRUE.") { /// } else { /// } /// } /// } /// } }

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