RFR: 8325674: Constant fold across compares [v2]

[Emanuel Peter]

On Fri, 23 Feb 2024 23:23:20 GMT, Joshua Cao <duke at openjdk.org> wrote:

>> For example, `x + 1 < 2` -> `x < 2 - 1` iff we can prove that `x + 1` does not overflow and `2 - 1` does not overflow. We can always fold if it is an `==` or `!=` since overflow will not affect the result of the comparison.
>> 
>> Consider this more practical example:
>> 
>> 
>> public void foo(int[] arr) {
>>   for (i = arr.length - 1; i >= 0; --i) {
>>     blackhole(arr[i]);
>>   }
>> }
>> 
>> 
>> C2 emits a loop guard that looks `arr.length - 1 < 0`. We know `arr.length - 1` does not overflow because `arr.length` is positive. We can fold the comparison into `arr.length < 1`. We have to compute `arr.length - 1` computation if we enter the loop anyway, but we can avoid the subtraction computation if we never enter the loop. I believe the simplification can also help with stronger integer range analysis in https://bugs.openjdk.org/browse/JDK-8275202.
>> 
>> Some additional notes:
>> * there is various overflow checking code across `src/hotspot/share/opto`. I separated about the functions from convertnode.cpp into `type.hpp`. Maybe the functions belong somewhere else?
>> * there is a change in Parse::do_if() to repeatedly apply GVN until the test is canonical. We need multiple iterations in the case of `C1 > C2 - X` -> `C2 - X < C1` -> `C2 < X` -> `X > C2`.  This fails the assertion if `BoolTest(btest).is_canonical()`. We can avoid this by applying GVN one more time to get `C2 < X`.
>> * we should not transform loop backedge conditions. For example, if we have `for (i = 0; i < 10; ++i) {}`, the backedge condition is `i + 1 < 10`. If we transform it into `i < 9`, it messes with CountedLoop's recognition of induction variables and strides.r
>> * this change optimizes some of the equality checks in `TestUnsignedComparison.java` and breaks the IR checks. I removed those tests.
>
> Joshua Cao has updated the pull request with a new target base due to a merge or a rebase. The incremental webrev excludes the unrelated changes brought in by the merge/rebase. The pull request contains three additional commits since the last revision:
> 
>  - Modify tests to work with -XX:-TieredCompilation
>  - Merge branch 'master' into cmpconstantfold
>  - 8325674: Constant fold across compares

Just did a quick style check before lunch ;)

Not reviewed the logic yet.

src/hotspot/share/opto/parse2.cpp line 1498:

> 1496:       btest = tst->as_Bool()->_test._test;
> 1497:       while (!BoolTest(btest).is_canonical()) {
> 1498:         // Reverse edges until the test is canonical

Can you say why it is necessary to loop here?

src/hotspot/share/opto/subnode.cpp line 1537:

> 1535:   }
> 1536: 
> 1537:   // Fold cmp(add(X, C1), C2) into cmp(X, sub(C2, C1))

use lower-case, just like the variables below

src/hotspot/share/opto/subnode.cpp line 1543:

> 1541:     Node* c1 = cmp1->in(2);
> 1542:     if ((c1->Opcode() == Op_ConI || c1->Opcode() == Op_ConL) &&
> 1543:         !is_cloop_condition(this)) {

`is_cloop_condition` requires an explanation

src/hotspot/share/opto/subnode.cpp line 1551:

> 1549:         bool add_no_overflow = !x_type->can_overflow(cmp1_op, c1_type);
> 1550:         bool cons_no_overflow =
> 1551:             !c2_type->can_overflow(bt == T_INT ? Op_SubI : Op_SubL, c1_type);

Suggestion:

        bool cons_no_overflow = !c2_type->can_overflow(bt == T_INT ? Op_SubI : Op_SubL, c1_type);

src/hotspot/share/opto/subnode.cpp line 1555:

> 1553:             _test._test == BoolTest::eq || _test._test == BoolTest::ne) {
> 1554:           cmp =
> 1555:               CmpNode::make(x, phase->transform(SubNode::make(cmp2, c1, bt)), bt);

Suggestion:

          cmp = CmpNode::make(x, phase->transform(SubNode::make(cmp2, c1, bt)), bt);

src/hotspot/share/opto/subnode.cpp line 1580:

> 1578:             _test._test == BoolTest::eq || _test._test == BoolTest::ne) {
> 1579:           cmp = CmpNode::make(phase->transform(SubNode::make(c1, cmp2, bt)), x,
> 1580:                               bt);

Suggestion:

          cmp = CmpNode::make(phase->transform(SubNode::make(c1, cmp2, bt)), x, bt);

-------------

Changes requested by epeter (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/17853#pullrequestreview-1900684276
PR Review Comment: https://git.openjdk.org/jdk/pull/17853#discussion_r1502493106
PR Review Comment: https://git.openjdk.org/jdk/pull/17853#discussion_r1502495625
PR Review Comment: https://git.openjdk.org/jdk/pull/17853#discussion_r1502498483
PR Review Comment: https://git.openjdk.org/jdk/pull/17853#discussion_r1502499638
PR Review Comment: https://git.openjdk.org/jdk/pull/17853#discussion_r1502500980
PR Review Comment: https://git.openjdk.org/jdk/pull/17853#discussion_r1502501422