This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Jump Bypass Optimization

 In message <>, Roger 
Sayle writes:

 > The current constrant propagation pass of GCC is able to convert
 > conditional jumps into unconditional jumps using the available
 > expressions calculated using standard PRE.  With this methodology
 > a conditional jump is optimized if it depends upon a value that
 > has a known value at the point the jump is evaluated.
 > Consider the common case of a basic block that starts with a
 > conditional jump, that has multiple incoming edges.  The current
 > cprop transformation only applies if the value is known and has
 > the same value on all incoming branches.  The "jump bypass"
 > optimization considers the situation where the value is known
 > over some subset of the incoming edges.  If the condition is
 > known to be satisfied the edge is redirected to the appropriate
 > target.
Right.  In theory all you have to do is get the available expression
from each incoming edge, see if it allows for optimization of the 
conditional and if it does, clean up the incoming edge to bypass
the conditional.

Note this is not the same as sparse conditional constant propagation,
though there is some overlap between the two.

 > where immediately after "done = true" the edge can be redirected out
 > of the loop.  Hopefully, if "done" isn't used elsewhere live analysis
 > will clean up the assignment, effectively turning it into a break.
Correct.  If "done" isn't a memory location life analysis will zap it;
if "done" is in a memory location, then it's much hard to eliminate.

 > Common subexpression elimination is handled by two separate passes
 > within GCC, CSE and GCSE.  In theory, the constant propagation
 > transformations available to both should be the same, but with
 > different scopes.  CSE should clean-up basic blocks and extended
 > basic-blocks, whilst GCSE cprop should apply interblock.
IMHO, CSE must go.  It's a freaking mess and the slowest of our
RTL optimizers.  Long term it's easily replaced with dominator based
optimization on an ssa form, but, well, that work has stalled.  In
the short term we might consider doing CSE on blocks in the dominator
tree to at least remove its insane compile time complexity on complex
flow graphs.

 > One notable difference is the "pseudo-assignments" created by
 > conditional branches.  In the code "if (x == 2) A; else B;"
 > CSE is able to assert that x has the value 2 when A is executed, the
 > condition effectively behaving as an assignment down one edge.
 > Unfortunately, these "pseudo-assignments" aren't currently handled
 > by PRE.
Correct.  Conceptually it's easy to add, but the structure of gcse makes
it difficult.

Conceptually the conditional will add two expressions -- one for the true
arm, one for the else arm.  Those expressions need to be made available on
the appropriate edge.   You can't made them unconditionally available at the
end of the block with the conditional or at the start of the target blocks.

Unfortunately, I don't see a good way to do this in gcse.  Expressions are
associated with blocks, not edges.

 > It should be simple enough to modify the PRE data flow equations to
 > allow a virtual "gen" on each edge.
Possibly.  Depends on the implementation.  From a maintenance standpoint
we really want to keep the dataflow solvers clean as they're shared.

This may mean we need to move to a model where local properties are associated
with edges rather than blocks.  Once we've got that model it becomes a lot
easier to insert new expressions into the table that are associated with a
particular edge.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]