Branch removal

[Vladimir Kozlov]

Hi, Patrick

The first step I would do is to find why current code in conditional_move() does 
not work for you and modify it so it works.

The main reason we not always convert such branches into cmoves is higher 
registers pressure. Also if hardware predict branch correctly it is almost nop.

 > My questions are:
 > * How can I assure my transformation leaves a consistent graph?
 > I found PhaseIdealLoop::verify(), is this appropriate?

-XX:+VerifyGraphEdges

 > * Is there already functionality implemented which removes code
 > unreachable from above but reachable from below?

It happened during call to replace_node() or subsume_node().
You need iteration in IGVN to clean graph after transformations (and don't 
forget to put modified/new nodes on igvn worklist).

 > * 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?

No. Phi is only associated with Region.

 > * Would you suggest to place the transformation not at the end of high
 > level optimizations but elsewhere, e.g. before optimizations?

I would suggest to add your transformation into 
PhaseIdealLoop::build_and_optimize(), look how superword code is invoked.

 > * Are Java annotations parsed by C2? If so, how to access them?

Annotations are parsed during class parsing, see classFileParser.cpp.

 > * Is it possible to disable uncommon traps (completely or just for one
 > method)?

No.

Regards,
Vladimir

Patrick Metzler wrote:
> 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