Branch removal

[Patrick Metzler]

Hi,

my plan is to write an additional pass/transformation for the server 
compiler; now I have some problems implementing it.  The transformation 
should delete certain branchings and make use of the conditional move 
instruction on Intel platforms, hence do /some sort of/ branch 
predication.  To be clear: it is not intended to make the code faster or 
smaller; I just want to see whether it is possible to compile branching 
in Java byte code into native code without branching (in the context of 
my computer science thesis).

For example, I want the if/else statement in the following Java method:

Object m( Object o1, Object o2, int n) {
   Object r;
   if (n == 0)
     r = o1;
   else
     r = o2;
   return r;
}

be compiled into native code like this:

... method entry ...
testl   RCX, RCX
cmovz   RBX, RAX
... method exit ...

assuming that EAX, EBX and ECX hold parameters o1, o2 and n, 
respectively, and that the value of EAX is returned.

It is fine for me if the emitted code contains branchings as long as 
they do not correspond to the if/else statement.  (I expect that it 
would be infeasible avoiding any branching anyway, due to, e.g., 
exceptions during allocation.)  It is also fine for me to restrict the 
Java programs the transformation would support; e.g., the transformation 
could only consider if statements containing no method calls, if 
statements with empty else branches, ...

Of course, the transformation should not be applied globally, but only 
on certain branchings.  I plan to mark them using Java annotations, 
possibly indicating the bytecode index, although I don't know whether 
this is easy to evaluate inside the compiler.

So far, I've tried out two things:  First, I borrowed some code from 
PhaseIdealLoop::conditional_move in order to replace a Region node and 
corresponding If / projection nodes with CMov nodes.  I inserted the 
transformation at the end of Compile::Optimize().  This works fine for a 
simple method, but gives me an error for a method using objects:

COMPILE SKIPPED: late schedule failed: incorrect graph (not retryable)

Second, I considered an example containing an if statement with an empty 
else statement inside a loop.  Here is a sketch of the Java source code:

MyObject a, aSwap;
// ... code left out here ...
for (E e : arrayList) {
   aSwap = a.getCopy();
   aSwap.do();
   if (e.condition())
     a = aSwap;
}

After high level optimizations, the else branch (which I expected to be 
empty) contained some basic blocks, so I changed the transformation such 
that it deletes the If node and the else branch, but not necessarily 
deletes the corresponding Region node (as it turned out to be the Loop 
node).  But I was not able to remove the else branch correctly and it 
gave me (I think because of CreateEx node I didn't remove):

COMPILE SKIPPED: infinite loop (not retryable)

I still need to figure out how to find the Phi nodes referenced in the 
if branch I now want to execute always, in order to replace them by CMov 
nodes.

My questions are:
* How can I assure my transformation leaves a consistent graph?
I found PhaseIdealLoop::verify(), is this appropriate?
* Is there already functionality implemented which removes code 
unreachable from above but reachable from below?
* Is it possible to associate a Phi node with a specific Bool node, in 
cases where a Region node has multiple If nodes as predecessors?
* Would you suggest to place the transformation not at the end of high 
level optimizations but elsewhere, e.g. before optimizations?
* Are Java annotations parsed by C2? If so, how to access them?
* Is it possible to disable uncommon traps (completely or just for one 
method)?


I would be glad if someone had some time to consider my questions.

Patrick