Bug ID: JDK-8058192 compiler ignores lookupswitch and tableswitch branch profile numbers

Type: Enhancement
Component: hotspot
Sub-Component: compiler
Affected Version: 9,10

Priority: P4
Status: Resolved
Resolution: Not an Issue

Submitted: 2014-09-11
Updated: 2018-03-28
Resolved: 2018-03-28

JDK 11
11Resolved

Parse::jump_switch_ranges takes a set of switch-range data derived from lookupswitch and tableswitch bytecodes, and generates a decision tree and/or jump tables for the switch.

It should also accept MethodData branch profile information (if available) and apply that profile information appropriately.  At least it should use the data in each call to jump_if_true_fork to push an estimated branch frequency into the IfNode, as Parse::do_if does.  Better yet, it should use frequency data (when uneven) to balance the decision tree, so that, along each likely trace, each test-and-branch produces as much of a bit of information as possible.

Note that low-tier code *produces* branch frequency information; this bug says that high-tier code does not *use* it.

Graal is doing the right thing and only generating code for the E.FOUR case: 0x00007f886626aa53: cmp $0xa,%eax 0x00007f886626aa56: jae 0x00007f886626aa80 ;tableswitch {reexecute=0 rethrow=0 return_oop=0} ; - M::getInt@8 (line 8) 0x00007f886626aa5c: cmp $0x4,%eax 0x00007f886626aa5f: jne 0x00007f886626aa9e 0x00007f886626aa65: mov $0x4,%eax ;ireturn {reexecute=0 rethrow=0 return_oop=0} ; - M::getInt@73 (line 13) 0x00007f886626aa6a: mov 0x10(%rsp),%rbp 0x00007f886626aa6f: add $0x18,%rsp 0x00007f886626aa73: mov 0x80(%r15),%rcx 0x00007f886626aa7a: test %eax,(%rcx) ; {poll_return} 0x00007f886626aa7c: vzeroupper 0x00007f886626aa7f: retq
28-03-2018
By inspection, Graal seems to take key probabilities into account in org/graalvm/compiler/lir/SwitchStrategy.java and also has special optimizations for enums.
08-03-2018
A couple questions: 1) In the example from 2014, why isn't "getInt(E.FOUR)" completely inlined into "4"? Is it because E.FOUR isn't considered a constant? 2) I can see how we can recover if we predict one key at 100% and everything else at 0%, using uncommon trap, but if we instead generate an unbalanced tree based on more complicated probabilities, how do we detect and recover if the actual key probabilities change (we start seeing keys with low predicted probability being used with high probability)?
07-03-2018
We will not do it in C2! But we need to look if it is needed in Graal.
06-05-2016
ILW=Performance loss, always, none=LHH=P4
15-09-2014
This is the thread where the issue was reported publicly: http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/2014-September/015488.html (I think I recall parser programmers asking about this a few years ago.) The current code produces a well-balanced decision tree under the assumption that all cases are equally likely. If cases are give different probabilities (or weights), then a greedy Huffman-like algorithm should suffice to drive a decision tree quickly to test for the most probable case values or case value ranges. In particular, in the extreme scenario reported publicly (one case value gets 100% of profile ticks) a weight-wise subdivision should select exactly that case value as a test key. Furthermore, as is done with ordinary branches, unreached successors should be pruned as eagerly as possible. If this is done, then the extreme scenario will boil down to: if (key != HUNDRED_PERCENT_KEY) goto uncommon_trap(); // case HUNDRED_PERCENT_KEY code continues here: This should all fall out naturally if we adapt the IR generation for branches to cover decision tree branches also.
11-09-2014

Relates :	JDK-8143859 - branch nests testing for intervals should be converted to internal switch ranges and rebalanced
Relates :	JDK-8024327 - Possible improvement of the Lookup Switch implementation in C2
Relates :	JDK-8200303 - C2 should leverage profiling for lookupswitch/tableswitch