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]

SSA vs cross jumping/tail merging

I've run into an interesting performance issue with conversion from SSA
form back to normal form.  I'm hoping that the updated cross jump code
might be able to handle this situation.  Else I'll have to submit a
little hack I've got to avoid the issue.

Consider a loop which starts with an unconditional jump to the exit
test and which contains one or more "continue" statements which translate
into conditional jumps to the exit test.

Let's assume for this discussion that we have 5 incoming edges to the loop
exit test.  #1 is the edge from the unconditional jump.  #2 is a fallthru
edge from the loop body and #3, #4 and #5 are conditional jumps from
continue statements.

Let's further assume translation from SSA to normal form requires that
edges #2, #4 and #5 have a copy instruction on them -- the copy instructions
are identical.  Edges #1 and #3 require no copy instructions.

Also note that edges #2, #3, #4 and #5 are all critical edges (which can
be derived from the information above, but better to be explicit).

To implement the required copies we'll have to split edges #2, #4 and #5.

Splitting of edges #4 and #5 will result in those paths requiring an 
additional jump to reach the loop exit test (edge #4 will jump to a new
block, which has a copy, when then jumps to the loop exit test, similarly
for edge #5).  The split of edge #2 requires no additional jumps on its path
since the new block will have its copy insn, then fall into the loop exit

A smarter implementation would split edge #2 and simply redirect edges #4
and #5 to the newly created basic block.  This eliminates the number of
static copies (1 instead of 3), but more importantly it eliminates an
unnecessary jump when we traverse edges #4 and #5 to get to the loop exit

This is really just a cross jump/tail merging optimization.  Since I'm working
from a slightly outdated tree, I've written up a hack which optimizes this
code in the manner stated above.

However, I'm hoping that the new CFG based cross jumping code will handle
this issue in a reasonable way.  Jan -- you probably know the code better
than anyone.  Any chance you could speculate as to whether or not the 
current code will handle this situation in the desired way?  Is the new
cross jumping code safe to run at any time during compilation (like
just after converting from SSA back to normal form)?


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