RFR: 8261308: C2: assert(inner->is_valid_counted_loop(T_INT) && inner->is_strip_mined()) failed: OuterStripMinedLoop should have been removed

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

RFR: 8261308: C2: assert(inner->is_valid_counted_loop(T_INT) && inner->is_strip_mined()) failed: OuterStripMinedLoop should have been removed

Roland Westrelin-4
The inner counted loop of the test case starts at 1 and stops at 1 so
runs for one iteration. A counted loop is created for it. The iv Phi
is found to be the constant 1 and its type is set by:

l->phi()->as_Phi()->set_type(l->phi()->Value(&_igvn));

in PhaseIdealLoop::is_counted_loop() but it's not replaced by the
constant 1 yet so the counted loop's shape is preserved.

IdealLoopTree::do_one_iteration_loop() runs but doesn't optimize the
loop because the trip count is not set to 1. The loop contains a range
check and range check elimination is applied. That causes the loop
exit test to be adjusted with a MinI(..) expression. When IGVN runs
next, the phi is replaced with 1 but because the exit test was
changed, IGVN can't prove it always fails. So the loop is not removed
which causes the assert failure as loop opts progress.

The fix I propose is for IdealLoopTree::do_one_iteration_loop() to
remove the 1 iteration loop. The reason it doesn't happen is that
IdealLoopTree::compute_trip_count() doesn't set the trip count because
it finds a zero trip count: limit - init = 1 - 1 = 0. All loops, once
entered execute at least once. So I think, it's safe to set the trip
count to 1 in those cases.

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

Commit messages:
 - whitespaces
 - test
 - fix

Changes: https://git.openjdk.java.net/jdk/pull/2529/files
 Webrev: https://webrevs.openjdk.java.net/?repo=jdk&pr=2529&range=00
  Issue: https://bugs.openjdk.java.net/browse/JDK-8261308
  Stats: 66 lines in 2 files changed: 65 ins; 0 del; 1 mod
  Patch: https://git.openjdk.java.net/jdk/pull/2529.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/2529/head:pull/2529

PR: https://git.openjdk.java.net/jdk/pull/2529
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261308: C2: assert(inner->is_valid_counted_loop(T_INT) && inner->is_strip_mined()) failed: OuterStripMinedLoop should have been removed

Christian Hagedorn-3
On Thu, 11 Feb 2021 16:11:50 GMT, Roland Westrelin <[hidden email]> wrote:

> The inner counted loop of the test case starts at 1 and stops at 1 so
> runs for one iteration. A counted loop is created for it. The iv Phi
> is found to be the constant 1 and its type is set by:
>
> l->phi()->as_Phi()->set_type(l->phi()->Value(&_igvn));
>
> in PhaseIdealLoop::is_counted_loop() but it's not replaced by the
> constant 1 yet so the counted loop's shape is preserved.
>
> IdealLoopTree::do_one_iteration_loop() runs but doesn't optimize the
> loop because the trip count is not set to 1. The loop contains a range
> check and range check elimination is applied. That causes the loop
> exit test to be adjusted with a MinI(..) expression. When IGVN runs
> next, the phi is replaced with 1 but because the exit test was
> changed, IGVN can't prove it always fails. So the loop is not removed
> which causes the assert failure as loop opts progress.
>
> The fix I propose is for IdealLoopTree::do_one_iteration_loop() to
> remove the 1 iteration loop. The reason it doesn't happen is that
> IdealLoopTree::compute_trip_count() doesn't set the trip count because
> it finds a zero trip count: limit - init = 1 - 1 = 0. All loops, once
> entered execute at least once. So I think, it's safe to set the trip
> count to 1 in those cases.

That's reasonable to do. Looks good to me!

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

Marked as reviewed by chagedorn (Reviewer).

PR: https://git.openjdk.java.net/jdk/pull/2529
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261308: C2: assert(inner->is_valid_counted_loop(T_INT) && inner->is_strip_mined()) failed: OuterStripMinedLoop should have been removed

Vladimir Kozlov-2
In reply to this post by Roland Westrelin-4
On Thu, 11 Feb 2021 16:11:50 GMT, Roland Westrelin <[hidden email]> wrote:

> The inner counted loop of the test case starts at 1 and stops at 1 so
> runs for one iteration. A counted loop is created for it. The iv Phi
> is found to be the constant 1 and its type is set by:
>
> l->phi()->as_Phi()->set_type(l->phi()->Value(&_igvn));
>
> in PhaseIdealLoop::is_counted_loop() but it's not replaced by the
> constant 1 yet so the counted loop's shape is preserved.
>
> IdealLoopTree::do_one_iteration_loop() runs but doesn't optimize the
> loop because the trip count is not set to 1. The loop contains a range
> check and range check elimination is applied. That causes the loop
> exit test to be adjusted with a MinI(..) expression. When IGVN runs
> next, the phi is replaced with 1 but because the exit test was
> changed, IGVN can't prove it always fails. So the loop is not removed
> which causes the assert failure as loop opts progress.
>
> The fix I propose is for IdealLoopTree::do_one_iteration_loop() to
> remove the 1 iteration loop. The reason it doesn't happen is that
> IdealLoopTree::compute_trip_count() doesn't set the trip count because
> it finds a zero trip count: limit - init = 1 - 1 = 0. All loops, once
> entered execute at least once. So I think, it's safe to set the trip
> count to 1 in those cases.

I think we need a test which verifies one_iteration loop optimization with different variations of init, limit and stride values to make sure `trip_count` formula is correct.

src/hotspot/share/opto/loopTransform.cpp line 126:

> 124:     jlong limit_con = (stride_con > 0) ? limit_type->_hi : limit_type->_lo;
> 125:     int stride_m = stride_con - (stride_con > 0 ? 1 : -1);
> 126:     jlong trip_count = (limit_con - init_con + stride_m)/stride_con;

Does it mean that before we execute do_one_iteration_loop() optimization for loops which do 2 trips?
This seems wrong. Can you check?
I agree that loop body executed at least once since it is exit check. But it means we have to generally adjust `trip_count` with `+1` and not do what you suggested.

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

PR: https://git.openjdk.java.net/jdk/pull/2529
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261308: C2: assert(inner->is_valid_counted_loop(T_INT) && inner->is_strip_mined()) failed: OuterStripMinedLoop should have been removed

Roland Westrelin-4
On Tue, 23 Feb 2021 19:13:22 GMT, Vladimir Kozlov <[hidden email]> wrote:

>> The inner counted loop of the test case starts at 1 and stops at 1 so
>> runs for one iteration. A counted loop is created for it. The iv Phi
>> is found to be the constant 1 and its type is set by:
>>
>> l->phi()->as_Phi()->set_type(l->phi()->Value(&_igvn));
>>
>> in PhaseIdealLoop::is_counted_loop() but it's not replaced by the
>> constant 1 yet so the counted loop's shape is preserved.
>>
>> IdealLoopTree::do_one_iteration_loop() runs but doesn't optimize the
>> loop because the trip count is not set to 1. The loop contains a range
>> check and range check elimination is applied. That causes the loop
>> exit test to be adjusted with a MinI(..) expression. When IGVN runs
>> next, the phi is replaced with 1 but because the exit test was
>> changed, IGVN can't prove it always fails. So the loop is not removed
>> which causes the assert failure as loop opts progress.
>>
>> The fix I propose is for IdealLoopTree::do_one_iteration_loop() to
>> remove the 1 iteration loop. The reason it doesn't happen is that
>> IdealLoopTree::compute_trip_count() doesn't set the trip count because
>> it finds a zero trip count: limit - init = 1 - 1 = 0. All loops, once
>> entered execute at least once. So I think, it's safe to set the trip
>> count to 1 in those cases.
>
> src/hotspot/share/opto/loopTransform.cpp line 126:
>
>> 124:     jlong limit_con = (stride_con > 0) ? limit_type->_hi : limit_type->_lo;
>> 125:     int stride_m = stride_con - (stride_con > 0 ? 1 : -1);
>> 126:     jlong trip_count = (limit_con - init_con + stride_m)/stride_con;
>
> Does it mean that before we execute do_one_iteration_loop() optimization for loops which do 2 trips?
> This seems wrong. Can you check?
> I agree that loop body executed at least once since it is exit check. But it means we have to generally adjust `trip_count` with `+1` and not do what you suggested.

Thanks for the comments.
A CountedLoopNode/CountedLoopEndNode is this in pseudo code:
int i = init;
do {
  i += stride;
} while (i < limit);
for stride > 0
We always enter the loop body so execute it at least once.
If limit > init, it's executed: (limit - init) / stride times if (limit - init) is a multiple of stride.
if (limit - init) is not a multiple of stride then it's executed (limit - init) / stride + 1.
That matches the formula in the source code AFAICT.
In what case do you think we compute 1 for the trip count when it's actually 2?
How would you compute the trip count?

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

PR: https://git.openjdk.java.net/jdk/pull/2529
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261308: C2: assert(inner->is_valid_counted_loop(T_INT) && inner->is_strip_mined()) failed: OuterStripMinedLoop should have been removed

Vladimir Kozlov-2
On Wed, 24 Feb 2021 14:57:15 GMT, Roland Westrelin <[hidden email]> wrote:

>> src/hotspot/share/opto/loopTransform.cpp line 126:
>>
>>> 124:     jlong limit_con = (stride_con > 0) ? limit_type->_hi : limit_type->_lo;
>>> 125:     int stride_m = stride_con - (stride_con > 0 ? 1 : -1);
>>> 126:     jlong trip_count = (limit_con - init_con + stride_m)/stride_con;
>>
>> Does it mean that before we execute do_one_iteration_loop() optimization for loops which do 2 trips?
>> This seems wrong. Can you check?
>> I agree that loop body executed at least once since it is exit check. But it means we have to generally adjust `trip_count` with `+1` and not do what you suggested.
>
> Thanks for the comments.
> A CountedLoopNode/CountedLoopEndNode is this in pseudo code:
> int i = init;
> do {
>   i += stride;
> } while (i < limit);
> for stride > 0
> We always enter the loop body so execute it at least once.
> If limit > init, it's executed: (limit - init) / stride times if (limit - init) is a multiple of stride.
> if (limit - init) is not a multiple of stride then it's executed (limit - init) / stride + 1.
> That matches the formula in the source code AFAICT.
> In what case do you think we compute 1 for the trip count when it's actually 2?
> How would you compute the trip count?

I looked on history and before your 8256655 changes we did not create counted loop for such case:
https://github.com/openjdk/jdk/blob/f504f419d3b377f0ccfd458026a2b57a9704bdff/src/hotspot/share/opto/loopnode.cpp#L1376
That is why we did not hit this issue before. After 8256655 we allow counted loops with `init >= limit`. Got it.

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

PR: https://git.openjdk.java.net/jdk/pull/2529
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261308: C2: assert(inner->is_valid_counted_loop(T_INT) && inner->is_strip_mined()) failed: OuterStripMinedLoop should have been removed

Vladimir Kozlov-2
In reply to this post by Roland Westrelin-4
On Thu, 11 Feb 2021 16:11:50 GMT, Roland Westrelin <[hidden email]> wrote:

> The inner counted loop of the test case starts at 1 and stops at 1 so
> runs for one iteration. A counted loop is created for it. The iv Phi
> is found to be the constant 1 and its type is set by:
>
> l->phi()->as_Phi()->set_type(l->phi()->Value(&_igvn));
>
> in PhaseIdealLoop::is_counted_loop() but it's not replaced by the
> constant 1 yet so the counted loop's shape is preserved.
>
> IdealLoopTree::do_one_iteration_loop() runs but doesn't optimize the
> loop because the trip count is not set to 1. The loop contains a range
> check and range check elimination is applied. That causes the loop
> exit test to be adjusted with a MinI(..) expression. When IGVN runs
> next, the phi is replaced with 1 but because the exit test was
> changed, IGVN can't prove it always fails. So the loop is not removed
> which causes the assert failure as loop opts progress.
>
> The fix I propose is for IdealLoopTree::do_one_iteration_loop() to
> remove the 1 iteration loop. The reason it doesn't happen is that
> IdealLoopTree::compute_trip_count() doesn't set the trip count because
> it finds a zero trip count: limit - init = 1 - 1 = 0. All loops, once
> entered execute at least once. So I think, it's safe to set the trip
> count to 1 in those cases.

src/hotspot/share/opto/loopTransform.cpp line 127:

> 125:     int stride_m = stride_con - (stride_con > 0 ? 1 : -1);
> 126:     jlong trip_count = (limit_con - init_con + stride_m)/stride_con;
> 127:     trip_count = MAX2(trip_count, (jlong)1);

Add comment here explaining this case (one trip when init >= limit).

BTW, this optimization seems only works for INT iv loops and not LONG. Do you plan to implement for LONG?

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

PR: https://git.openjdk.java.net/jdk/pull/2529
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261308: C2: assert(inner->is_valid_counted_loop(T_INT) && inner->is_strip_mined()) failed: OuterStripMinedLoop should have been removed

Roland Westrelin-4
On Wed, 24 Feb 2021 19:43:14 GMT, Vladimir Kozlov <[hidden email]> wrote:

> Add comment here explaining this case (one trip when init >= limit).

Ok. Do you still think we need extra tests?

> BTW, this optimization seems only works for INT iv loops and not LONG. Do you plan to implement for LONG?

I thought about it but it's not straightforward because the current code uses long to avoid overflow. I would also like to rework the parallel iv code so it works with LONG loops. I don't have time right now, thought.

Note also, that because of the iv phi Value(), I would expect some of the single iteration loops to be optimized even without a working IdealLoopTree::compute_trip_count(). That would be true for in and long loops.

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

PR: https://git.openjdk.java.net/jdk/pull/2529
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261308: C2: assert(inner->is_valid_counted_loop(T_INT) && inner->is_strip_mined()) failed: OuterStripMinedLoop should have been removed

Vladimir Kozlov-2
In reply to this post by Roland Westrelin-4
On Thu, 11 Feb 2021 16:11:50 GMT, Roland Westrelin <[hidden email]> wrote:

> The inner counted loop of the test case starts at 1 and stops at 1 so
> runs for one iteration. A counted loop is created for it. The iv Phi
> is found to be the constant 1 and its type is set by:
>
> l->phi()->as_Phi()->set_type(l->phi()->Value(&_igvn));
>
> in PhaseIdealLoop::is_counted_loop() but it's not replaced by the
> constant 1 yet so the counted loop's shape is preserved.
>
> IdealLoopTree::do_one_iteration_loop() runs but doesn't optimize the
> loop because the trip count is not set to 1. The loop contains a range
> check and range check elimination is applied. That causes the loop
> exit test to be adjusted with a MinI(..) expression. When IGVN runs
> next, the phi is replaced with 1 but because the exit test was
> changed, IGVN can't prove it always fails. So the loop is not removed
> which causes the assert failure as loop opts progress.
>
> The fix I propose is for IdealLoopTree::do_one_iteration_loop() to
> remove the 1 iteration loop. The reason it doesn't happen is that
> IdealLoopTree::compute_trip_count() doesn't set the trip count because
> it finds a zero trip count: limit - init = 1 - 1 = 0. All loops, once
> entered execute at least once. So I think, it's safe to set the trip
> count to 1 in those cases.

Good.

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

Marked as reviewed by kvn (Reviewer).

PR: https://git.openjdk.java.net/jdk/pull/2529
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261308: C2: assert(inner->is_valid_counted_loop(T_INT) && inner->is_strip_mined()) failed: OuterStripMinedLoop should have been removed

Vladimir Kozlov-2
In reply to this post by Roland Westrelin-4
On Thu, 25 Feb 2021 09:49:31 GMT, Roland Westrelin <[hidden email]> wrote:

> > Add comment here explaining this case (one trip when init >= limit).
>
> Ok. Do you still think we need extra tests?

Yes, would be nice to have tests for 0,1,2 iterations and all 3 types of loops: `for() {}`, `while() {}`, `do {} while()` to verify that they are converted to straight code. It could be done as separate RFE.

>
> > BTW, this optimization seems only works for INT iv loops and not LONG. Do you plan to implement for LONG?
>
> I thought about it but it's not straightforward because the current code uses long to avoid overflow. I would also like to rework the parallel iv code so it works with LONG loops. I don't have time right now, thought.
>
> Note also, that because of the iv phi Value(), I would expect some of the single iteration loops to be optimized even without a working IdealLoopTree::compute_trip_count(). That would be true for in and long loops.

Got it. Thank you.

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

PR: https://git.openjdk.java.net/jdk/pull/2529
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261308: C2: assert(inner->is_valid_counted_loop(T_INT) && inner->is_strip_mined()) failed: OuterStripMinedLoop should have been removed

Roland Westrelin-4
On Thu, 25 Feb 2021 18:08:42 GMT, Vladimir Kozlov <[hidden email]> wrote:

> Yes, would be nice to have tests for 0,1,2 iterations and all 3 types of loops: `for() {}`, `while() {}`, `do {} while()` to verify that they are converted to straight code. It could be done as separate RFE.

I filed https://bugs.openjdk.java.net/browse/JDK-8262721
Sounds like a good candidate for the new testing framework that allows pattern matching on the IR.

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

PR: https://git.openjdk.java.net/jdk/pull/2529
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261308: C2: assert(inner->is_valid_counted_loop(T_INT) && inner->is_strip_mined()) failed: OuterStripMinedLoop should have been removed [v2]

Roland Westrelin-4
In reply to this post by Christian Hagedorn-3
On Tue, 23 Feb 2021 16:44:02 GMT, Christian Hagedorn <[hidden email]> wrote:

>> Roland Westrelin has updated the pull request incrementally with one additional commit since the last revision:
>>
>>   comment
>
> That's reasonable to do. Looks good to me!

@chhagedorn @vnkozlov thanks for the reviews

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

PR: https://git.openjdk.java.net/jdk/pull/2529
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8261308: C2: assert(inner->is_valid_counted_loop(T_INT) && inner->is_strip_mined()) failed: OuterStripMinedLoop should have been removed [v2]

Roland Westrelin-4
In reply to this post by Roland Westrelin-4
> The inner counted loop of the test case starts at 1 and stops at 1 so
> runs for one iteration. A counted loop is created for it. The iv Phi
> is found to be the constant 1 and its type is set by:
>
> l->phi()->as_Phi()->set_type(l->phi()->Value(&_igvn));
>
> in PhaseIdealLoop::is_counted_loop() but it's not replaced by the
> constant 1 yet so the counted loop's shape is preserved.
>
> IdealLoopTree::do_one_iteration_loop() runs but doesn't optimize the
> loop because the trip count is not set to 1. The loop contains a range
> check and range check elimination is applied. That causes the loop
> exit test to be adjusted with a MinI(..) expression. When IGVN runs
> next, the phi is replaced with 1 but because the exit test was
> changed, IGVN can't prove it always fails. So the loop is not removed
> which causes the assert failure as loop opts progress.
>
> The fix I propose is for IdealLoopTree::do_one_iteration_loop() to
> remove the 1 iteration loop. The reason it doesn't happen is that
> IdealLoopTree::compute_trip_count() doesn't set the trip count because
> it finds a zero trip count: limit - init = 1 - 1 = 0. All loops, once
> entered execute at least once. So I think, it's safe to set the trip
> count to 1 in those cases.

Roland Westrelin has updated the pull request incrementally with one additional commit since the last revision:

  comment

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

Changes:
  - all: https://git.openjdk.java.net/jdk/pull/2529/files
  - new: https://git.openjdk.java.net/jdk/pull/2529/files/5f9ac283..42c864ec

Webrevs:
 - full: https://webrevs.openjdk.java.net/?repo=jdk&pr=2529&range=01
 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=2529&range=00-01

  Stats: 2 lines in 1 file changed: 2 ins; 0 del; 0 mod
  Patch: https://git.openjdk.java.net/jdk/pull/2529.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/2529/head:pull/2529

PR: https://git.openjdk.java.net/jdk/pull/2529
Reply | Threaded
Open this post in threaded view
|

Integrated: 8261308: C2: assert(inner->is_valid_counted_loop(T_INT) && inner->is_strip_mined()) failed: OuterStripMinedLoop should have been removed

Roland Westrelin-4
In reply to this post by Roland Westrelin-4
On Thu, 11 Feb 2021 16:11:50 GMT, Roland Westrelin <[hidden email]> wrote:

> The inner counted loop of the test case starts at 1 and stops at 1 so
> runs for one iteration. A counted loop is created for it. The iv Phi
> is found to be the constant 1 and its type is set by:
>
> l->phi()->as_Phi()->set_type(l->phi()->Value(&_igvn));
>
> in PhaseIdealLoop::is_counted_loop() but it's not replaced by the
> constant 1 yet so the counted loop's shape is preserved.
>
> IdealLoopTree::do_one_iteration_loop() runs but doesn't optimize the
> loop because the trip count is not set to 1. The loop contains a range
> check and range check elimination is applied. That causes the loop
> exit test to be adjusted with a MinI(..) expression. When IGVN runs
> next, the phi is replaced with 1 but because the exit test was
> changed, IGVN can't prove it always fails. So the loop is not removed
> which causes the assert failure as loop opts progress.
>
> The fix I propose is for IdealLoopTree::do_one_iteration_loop() to
> remove the 1 iteration loop. The reason it doesn't happen is that
> IdealLoopTree::compute_trip_count() doesn't set the trip count because
> it finds a zero trip count: limit - init = 1 - 1 = 0. All loops, once
> entered execute at least once. So I think, it's safe to set the trip
> count to 1 in those cases.

This pull request has now been integrated.

Changeset: ddd550ae
Author:    Roland Westrelin <[hidden email]>
URL:       https://git.openjdk.java.net/jdk/commit/ddd550ae
Stats:     68 lines in 2 files changed: 67 ins; 0 del; 1 mod

8261308: C2: assert(inner->is_valid_counted_loop(T_INT) && inner->is_strip_mined()) failed: OuterStripMinedLoop should have been removed

Reviewed-by: chagedorn, kvn

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

PR: https://git.openjdk.java.net/jdk/pull/2529