#include "config.h"#include "system.h"#include "coretypes.h"#include "tm.h"#include "tree.h"#include "gimple-pretty-print.h"#include "basic-block.h"#include "gimple.h"#include "gimple-ssa.h"#include "tree-cfg.h"#include "tree-phinodes.h"#include "ssa-iterators.h"#include "tree-ssanames.h"#include "tree-ssa-loop-niter.h"#include "tree-into-ssa.h"#include "tree-dfa.h"#include "tree-pass.h"#include "flags.h"#include "cfgloop.h"#include "tree-scalar-evolution.h"
Data Structures | |
| struct | stmt_stats |
Macros | |
| #define | STMT_NECESSARY GF_PLF_1 |
Variables | |
| static struct stmt_stats | stats |
| static vec< gimple > | worklist |
| static sbitmap | processed |
| static sbitmap | last_stmt_necessary |
| static sbitmap | bb_contains_live_stmts |
| static control_dependences * | cd |
| static sbitmap | visited_control_parents |
| static bool | cfg_altered |
| static bitmap | visited = NULL |
| static unsigned int | longest_chain = 0 |
| static unsigned int | total_chain = 0 |
| static unsigned int | nr_walks = 0 |
| static bool | chain_ovfl = false |
Macro Definition Documentation
| #define STMT_NECESSARY GF_PLF_1 |
Function Documentation
|
static |
Return true for PHI nodes with one or identical arguments can be removed.
|
static |
Eliminate unnecessary statements. Any instruction not marked as necessary contributes nothing to the program, and can be deleted.
Walking basic blocks and statements in reverse order avoids releasing SSA names before any other DEFs that refer to them are released. This helps avoid loss of debug information, as we get a chance to propagate all RHSs of removed SSAs into debug uses, rather than only the latest ones. E.g., consider: x_3 = y_1 + z_2; a_5 = x_3 - b_4;
DEBUG a => a_5
If we were to release x_3 before a_5, when we reached a_5 and tried to substitute it into the debug stmt, we'd see x_3 there, but x_3's DEF, type, etc would have already been disconnected. By going backwards, the debug stmt first changes to:
DEBUG a => x_3 - b_4
and then to:
DEBUG a => y_1 + z_2 - b_4
as desired.
Remove dead statements. We can mark a call to free as not necessary if the
defining statement of its argument is an allocation
function and that is not necessary itself. If GSI is not necessary then remove it.
When LHS of var = call (); is dead, simplify it into
call (); saving one operand. Avoid doing so for allocation calls which we
did not mark as necessary, it will confuse the
special logic we apply to malloc/free pair removal. Since we don't track liveness of virtual PHI nodes, it is possible that we rendered some PHI nodes unreachable while they are still in use. Mark them for renaming.
Delete all unreachable basic blocks in reverse dominator order.
Speed up the removal of blocks that don't
dominate others. Walking backwards, this should
be the common case. ??? Do we need to recompute
dominators because of cfg_altered? Rearrangements to the CFG may have failed
to update the dominators tree, so that
formerly-dominated blocks are now
otherwise reachable. Remove dead PHI nodes.
|
static |
Find obviously necessary statements. These are things like most function calls, and stores to file level variables.
If EL is NULL, control statements are conservatively marked as necessary. Otherwise it contains the list of edges used by control dependence analysis.
PHI nodes are never inherently necessary.
Check all statements in the block.
Pure and const functions are finite and thus have no infinite loops in them.
Prevent the empty possibly infinite loops from being removed.
|
static |
Forward edge E to respective POST_DOM_BB and update PHIs.
If edge was already around, no updating is necessary.
We are sure that for every live PHI we are seeing control dependent BB.
This means that we can pick any edge to duplicate PHI args from. PHIs for virtuals have no control dependency relation on them.
We are lost here and must force renaming of the symbol. Dead PHI do not imply control dependency.
The resulting PHI if not dead can only be degenerate.
References dump_file, print_gimple_stmt(), and TDF_SLIM.
|
static |
References execute(), and tree_ssa_cd_dce().
| gimple_opt_pass* make_pass_cd_dce | ( | ) |
| gimple_opt_pass* make_pass_dce | ( | ) |
| gimple_opt_pass* make_pass_dce_loop | ( | ) |
|
static |
References gimple_assign_lhs(), and ref_may_be_aliased().
|
static |
Worker for the walker that marks reaching definitions of REF, which is based on a non-aliased decl, necessary. It returns true whenever the defining statement of the current VDEF is a kill for REF, as no dominating may-defs are necessary for REF anymore. DATA points to the basic-block that contains the stmt that refers to REF.
All stmts we visit are necessary.
If the stmt lhs kills ref, then we can stop walking.
The assignment is not necessarily carried out if it can throw
and we can catch it in the current function where we could inspect
the previous value.
??? We only need to care about the RHS throwing. For aggregate
assignments or similar calls and non-call exceptions the LHS
might throw as well. We can get MEM[symbol: sZ, index: D.8862_1] here,
so base == refd->base does not always hold. For a must-alias check we need to be able to constrain
the accesses properly. Or they need to be exactly the same.
Make sure there is no induction variable involved
in the references (gcc.c-torture/execute/pr42142.c).
The simplest way is to check if the kill dominates
the use. But when both are in the same block we cannot
easily tell whether we came from a backedge
unless we decide to compute stmt UIDs
(see PR58246). Otherwise keep walking.
References ao_ref_s::max_size, and ao_ref_s::offset.
|
static |
References dump_file, print_gimple_stmt(), and TDF_SLIM.
Worker for the walker that marks reaching definitions of REF, which is not based on a non-aliased decl. For simplicity we need to end up marking all may-defs necessary that are not based on a non-aliased decl. The only job of this walker is to skip may-defs based on a non-aliased decl.
We have to skip already visited (and thus necessary) statements to make the chaining work after we dropped back to simple mode.
We want to skip stores to non-aliased variables.
We want to skip statments that do not constitute stores but have a virtual definition.
|
static |
Mark control dependent edges of BB as necessary. We have to do this only once for each basic block so we set the appropriate bit after we're done.
When IGNORE_SELF is true, ignore BB in the list of control dependences.
|
static |
Mark the last statement of BB as necessary.
We actually mark the statement only if it is a control statement.
References ENTRY_BLOCK_PTR, EXECUTE_IF_SET_IN_BITMAP, EXIT_BLOCK_PTR, gcc_assert, control_dependences::get_edge(), control_dependences::get_edges_dependent_on(), basic_block_def::index, and edge_def::src.
|
inlinestatic |
Mark the statement defining operand OP as necessary.
Referenced by ref_may_be_aliased().
|
static |
Mark STMT as necessary if it obviously is. Add it to the worklist if it can make other statements necessary.
If AGGRESSIVE is false, control statements are conservatively marked as necessary.
With non-call exceptions, we have to assume that all statements could throw. If a statement could throw, it can be deemed necessary.
Statements that are implicitly live. Most function calls, asm and return statements are required. Labels and GIMPLE_BIND nodes are kept because they are control flow, and we have no way of knowing whether they can be removed. DCE can eliminate all the other statements in a block, and CFG can then remove the block and labels.
Most, but not all function calls are required. Function calls that
produce no result and have no side effects (i.e. const pure
functions) are unnecessary. Debug temps without a value are not useful. ??? If we could
easily locate the debug temp bind stmt for a use thereof,
would could refrain from marking all debug temps here, and
mark them only if they're used. Fall through.
If the statement has volatile operands, it needs to be preserved. Same for statements that can alter control flow in unpredictable ways.
References BUILT_IN_NORMAL, DECL_BUILT_IN_CLASS, DECL_FUNCTION_CODE, EDGE_COUNT, gcc_assert, gimple_assign_lhs(), gimple_assign_rhs1(), gimple_call_fndecl(), gimple_call_lhs(), gimple_debug_bind_get_var(), gimple_debug_bind_has_value_p(), gimple_debug_bind_p(), gimple_has_side_effects(), mark_stmt_necessary(), NULL_TREE, simple_goto_p(), TREE_CLOBBER_P, and TREE_CODE.
|
inlinestatic |
If STMT is not already marked necessary, mark it, and add it to the worklist if ADD_TO_WORKLIST is true.
Referenced by mark_stmt_if_obviously_necessary().
|
static |
Main routine to eliminate dead code.
AGGRESSIVE controls the aggressiveness of the algorithm. In conservative mode, we ignore control dependence and simply declare all but the most trivially dead branches necessary. This mode is fast. In aggressive mode, control dependences are taken into account, which results in more dead code elimination, but at the cost of some time.
FIXME: Aggressive mode before PRE doesn't work currently because the dominance info is not invalidated after DCE1. This is not an issue right now because we only run aggressive DCE as the last tree SSA pass, but keep this in mind when you start experimenting with pass ordering.
Preheaders are needed for SCEV to work. Simple lateches and recorded exits improve chances that loop will proved to be finite in testcases such as in loop-15.c and loop-24.c
Compute control dependence.
We do not update postdominators, so free them unconditionally.
If we removed paths in the CFG, then we need to update dominators as well. I haven't investigated the possibility of incrementally updating dominators.
Debugging dumps.
|
static |
Print out removed statement statistics.
|
static |
Propagate necessity using the operands of necessary statements. Process the uses on each statement in the worklist, and add all feeding statements which contribute to the calculation of this value to the worklist.
In conservative mode, EL is NULL.
Take STMT from worklist.
Mark the last statement of the basic blocks on which the block
containing STMT is control dependent, but only if we haven't
already done so. We do not process virtual PHI nodes nor do we track their
necessity. PHI nodes are somewhat special in that each PHI alternative has
data and control dependencies. All the statements feeding the
PHI node's arguments are always necessary. In aggressive mode,
we also consider the control dependent edges leading to the
predecessor block associated with each PHI alternative as
necessary. For PHI operands it matters from where the control flow arrives
to the BB. Consider the following example:
a=exp1;
b=exp2;
if (test)
;
else
;
c=PHI(a,b)
We need to mark control dependence of the empty basic blocks, since they
contains computation of PHI operands.
Doing so is too restrictive in the case the predecestor block is in
the loop. Consider:
if (b)
{
int i;
for (i = 0; i<1000; ++i)
;
j = 0;
}
return j;
There is PHI for J in the BB containing return statement.
In this case the control dependence of predecestor block (that is
within the empty loop) also contains the block determining number
of iterations of the block that would prevent removing of empty
loop in this case.
This scenario can be avoided by splitting critical edges.
To save the critical edge splitting pass we identify how the control
dependence would look like if the edge was split.
Consider the modified CFG created from current CFG by splitting
edge B->C. In the postdominance tree of modified CFG, C' is
always child of C. There are two cases how chlids of C' can look
like:
1) C' is leaf
In this case the only basic block C' is control dependent on is B.
2) C' has single child that is B
In this case control dependence of C' is same as control
dependence of B in original CFG except for block B itself.
(since C' postdominate B in modified CFG)
Now how to decide what case happens? There are two basic options:
a) C postdominate B. Then C immediately postdominate B and
case 2 happens iff there is no other way from B to C except
the edge B->C.
There is other way from B to C iff there is succesor of B that
is not postdominated by B. Testing this condition is somewhat
expensive, because we need to iterate all succesors of B.
We are safe to assume that this does not happen: we will mark B
as needed when processing the other path from B to C that is
conrol dependent on B and marking control dependencies of B
itself is harmless because they will be processed anyway after
processing control statement in B.
b) C does not postdominate B. Always case 1 happens since there is
path from C to exit that does not go through B and thus also C'. Propagate through the operands. Examine all the USE, VUSE and
VDEF operands in this statement. Mark all the statements
which feed this statement's uses as necessary. If this is a call to free which is directly fed by an
allocation function do not mark that necessary through
processing the argument. If the pointer we free is defined by an allocation
function do not add the call to the worklist. If we dropped to simple mode make all immediately
reachable definitions necessary. For statements that may load from memory (have a VUSE) we
have to mark all reaching (may-)definitions as necessary.
We partition this task into two cases:
1) explicit loads based on decls that are not aliased
2) implicit loads (like calls) and explicit loads not
based on decls that are not aliased (like indirect
references or loads from globals)
For 1) we mark all reaching may-defs as necessary, stopping
at dominating kills. For 2) we want to mark all dominating
references necessary, but non-aliased ones which we handle
in 1). By keeping a global visited bitmap for references
we walk for 2) we avoid quadratic behavior for those. Calls to functions that are merely acting as barriers
or that only store to memory do not make any previous
stores necessary. Calls implicitly load from memory, their arguments
in addition may explicitly perform memory loads. If this is a load mark things necessary.
A return statement may perform a load.
Inputs may perform loads.
The beginning of a transaction is a memory barrier.
??? If we were really cool, we'd only be a barrier
for the memories touched within the transaction. If we over-used our alias oracle budget drop to simple
mode. The cost metric allows quadratic behavior
(number of uses times number of may-defs queries) up to
a constant maximal number of queries and after that falls back to
super-linear complexity. Linear in the number of may-defs.
Linear in the number of uses.
|
static |
Return true if REF is based on an aliased base, otherwise false.
References gimple_get_lhs(), gimple_has_lhs(), mark_operand_necessary(), SSA_NAME_DEF_STMT, and TREE_CODE.
Referenced by mark_aliased_reaching_defs_necessary().
|
static |
Remove dead PHI nodes from block BB.
We do not track necessity of virtual PHI nodes. Instead do very simple dead PHI removal here.
Virtual PHI nodes with one or identical arguments
can be removed.
|
static |
Remove dead statement pointed to by iterator I. Receives the basic block BB containing I so that we don't have to look it up.
If we have determined that a conditional branch statement contributes nothing to the program, then we not only remove it, but we also change the flow graph so that the current block will simply fall-thru to its immediate post-dominator. The blocks we are circumventing will be removed by cleanup_tree_cfg if this change in the flow graph makes them unreachable.
If edge is already there, try to use it. This avoids need to update
PHI nodes. Also watch for cases where post dominator does not exists
or is exit block. These can happen for infinite loops as we create
fake edges in the dominator tree. The edge is no longer associated with a conditional, so it does
not have TRUE/FALSE flags. The lone outgoing edge from BB will be a fallthru edge.
Remove the remaining outgoing edges.
If this is a store into a variable that is being optimized away, add a debug bind stmt if possible.
References gimple_assign_rhs1(), gimple_build_debug_bind, gsi_insert_after(), GSI_SAME_STMT, and unshare_expr().
|
static |
Cleanup after this pass.
|
static |
Initialization for this pass. Set up the used data structures.
|
static |
Referenced by gate_dce().
|
static |
Pass entry points.
|
static |
Variable Documentation
|
static |
Vector indicating that BB contains statements that are live.
|
static |
Before we can determine whether a control branch is dead, we need to compute which blocks are control dependent on which edges.
We expect each block to be control dependent on very few edges so we use a bitmap for each block recording its edges. An array holds the bitmap. The Ith bit in the bitmap is set if that block is dependent on the Ith edge.
Referenced by same_phi_alternatives_1().
|
static |
TRUE if this pass alters the CFG (by removing control statements). FALSE otherwise.
If this pass alters the CFG, then it will arrange for the dominators to be recomputed.
|
static |
Vector indicating that the last statement of a basic block has already been marked as necessary.
|
static |
|
static |
|
static |
Vector indicating an SSA name has already been processed and marked as necessary.
|
static |
|
static |
|
static |
Vector indicating that a basic block has already had all the edges processed that it is control dependent on.
