RFR(M): 8200303: C2 should leverage profiling for lookupswitch/tableswitch

[Vladimir Kozlov]

Thank you, Roland, for contributing this.

Changes look reasonable. I will start testing including performance.

Thanks,
Vladimir

On 3/27/18 7:35 AM, Roland Westrelin wrote:
> 
> http://cr.openjdk.java.net/~roland/8200303/webrev.00/
> 
> Over in the Shenandoah project, Aleksey found that:
> 
> 1) a counted loop with a switch:
> 
> for (...) {
>    switch (..) {
>      ...
>      default:
>        throw SomeException();
>    }
> }
> 
> where some cases break out of the loop would not perform as well when
> loop strip mining is enabled, even if the cases that exit the loop are
> never taken in practice.
> 
> Because C2 gives all branches out of a JumpNode the same probability,
> exiting the loop has a non null probability and GCM computes (wrongly)
> that scheduling the loop strip mining book keeping logic in the loop is
> cheaper than out of the loop.
> 
> 2) Shenandoah write barriers in some of the cases should be hoisted but
> are not because C2 can't tell that only a single case of the switch is
> ever hit.
> 
> http://mail.openjdk.java.net/pipermail/shenandoah-dev/2017-December/004535.html
> 
> In the Shenandoah repo, we have a change that makes C2 leverage
> profiling for switch. Experiments showed that 1) and 2) above are fixed
> and that some common benchmarks run with parallel gc benefit as well
> (~+7% on Serial):
> 
> http://mail.openjdk.java.net/pipermail/shenandoah-dev/2018-February/004886.html
> 
> The patch I'm proposing here is based on the patch we've been using for
> a couple months in Shenandoah:
> 
> - it fixes profile collection in c1 for lookupswitch/tableswitch
> 
> - it sets profiling information on IfNodes and JumpNodes emitted from
>    lookupswitch/tableswitch and propagate it after matching so GCM can
>    take advantage of it
> 
> - it takes advantage of profiling to find never taken cases and trim
>    down the cases (or ranges as they're called in the code). A never
>    taken range can now cause an uncommon trap.
> 
> and also has some improvements:
> 
> - if some ranges are a lot more common than others, it might pay off to
>    check for them one after the other before going to the binary
>    search. The patch has some logic to evaluate the number of steps in
>    the binary search and determine whether checking for the most common
>    case upfront would pay off (from profile data)
> 
> - the binary search doesn't always keep the tree balanced but instead
>    picks a mid point that split frequencies in half
> 
> Roland.
>