Page MenuHomePhabricator

[IndVars] Invalidate SCEV when IR is changed in rewriteLoopExitValue.
ClosedPublic

Authored by fhahn on Oct 9 2021, 8:49 AM.

Details

Summary

At the moment, rewriteLoopExitValue forgets the current phi node in the
loop that collects phis to rewrite. A few lines after the value is
forgotten, SCEV is used again to analyze incoming values and
potentially expand SCEV expression. This means that another SCEV is
created for PN, before the IR is actually updated in the next loop.

This leads to accessing invalid cached expression in combination with

PN should only be changed once the actual incoming exit value is set in
the next loop. Moving invalidation there should ensure that PN is
invalidated in all relevant cases.

Diff Detail

Event Timeline

fhahn created this revision.Oct 9 2021, 8:49 AM
fhahn requested review of this revision.Oct 9 2021, 8:49 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 9 2021, 8:49 AM
nikic added a subscriber: nikic.Oct 9 2021, 9:10 AM

This looks like basically the same change as D82799, though there I thought this was just a compile-time optimization, not a correctness fix. In that patch, I also added an extra forgetValue() call in IV widening to prevent the elim-extend.ll test change.

Agreed, change in test's behavior looks suspicious. Looks like something else is missing.

fhahn added a comment.Oct 11 2021, 2:57 AM

This looks like basically the same change as D82799, though there I thought this was just a compile-time optimization, not a correctness fix. In that patch, I also added an extra forgetValue() call in IV widening to prevent the elim-extend.ll test change.

Thanks for sharing the patch, I completely missed that one! Happy to got with this one, it just looks like it's been marked as changes-planned for a while with a mention of adding something. But it seems like it would be good to go in as is, potentially with the test case in llvm/test/Transforms/IndVarSimplify/invalidate-modified-lcssa-phi.ll? (I can also commit that test separately).

Agreed, change in test's behavior looks suspicious. Looks like something else is missing.

yeah, it still seems correct but potentially can be fixed by the additional change in D82799

The very fact that invalidation or non-invalidation in SCEV changes behavior (even if the transforms are correct) is worrysome. It introduces more non-determinism in our compilations...

The very fact that invalidation or non-invalidation in SCEV changes behavior (even if the transforms are correct) is worrysome. It introduces more non-determinism in our compilations...

Yeah, but also widespread unfortunately. Whenever we have a case where an analysis is not precise or we have two equally precise states, we have that problem. We don't really have a great way to address this in general.

This looks like basically the same change as D82799, though there I thought this was just a compile-time optimization, not a correctness fix. In that patch, I also added an extra forgetValue() call in IV widening to prevent the elim-extend.ll test change.

Thanks for sharing the patch, I completely missed that one! Happy to got with this one, it just looks like it's been marked as changes-planned for a while with a mention of adding something. But it seems like it would be good to go in as is, potentially with the test case in llvm/test/Transforms/IndVarSimplify/invalidate-modified-lcssa-phi.ll? (I can also commit that test separately).

Happy to go with your patch, just wanted to point out the additional forgetValue() call. I never had the time to fully investigate the binary changes, though I think they were of the harmless sort (different but equivalent SCEV expressions).

The very fact that invalidation or non-invalidation in SCEV changes behavior (even if the transforms are correct) is worrysome. It introduces more non-determinism in our compilations...

Yeah, but also widespread unfortunately. Whenever we have a case where an analysis is not precise or we have two equally precise states, we have that problem. We don't really have a great way to address this in general.

This may be misleading when we make a change in SCEV and think that it really makes difference, when the only thing it does is caches differently. :(

As for the patch, I'm also fine with that. I don't have strong opinion whether we really want 2nd forget if we know for sure that the results with and without it are both functionally correct. Might be nice to have it anyways just for the sole purpose of consevatism. :)

mkazantsev accepted this revision.Oct 19 2021, 8:20 AM
This revision is now accepted and ready to land.Oct 19 2021, 8:20 AM