Branch removal (original) (raw)

Vladimir Kozlov vladimir.kozlov at oracle.com
Thu Sep 20 14:45:14 PDT 2012

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:

-XX:+VerifyGraphEdges

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).

No. Phi is only associated with Region.

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

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

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::conditionalmove 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

More information about the hotspot-compiler-dev mailing list