This is an archive of the discontinued LLVM Phabricator instance.

[IRCE] Add tests for conservative bound check
ClosedPublic

Authored by jaykang10 on Apr 23 2021, 9:04 AM.

Details

Summary

Prevent cases in which the start value of IV is bigger than bound for increasing or the start value of IV is smaller than bound for decreasing.

Diff Detail

Event Timeline

jaykang10 created this revision.Apr 23 2021, 9:04 AM
jaykang10 requested review of this revision.Apr 23 2021, 9:04 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 23 2021, 9:04 AM

Hi,

I think this looks fine to me, and now I'm trying to remember what the difference was which these functions and cannotBe[Min/Max]InLoop. Have you looked into using these?

Hi,

I think this looks fine to me, and now I'm trying to remember what the difference was which these functions and cannotBe[Min/Max]InLoop. Have you looked into using these?

Hi Sam,

For increasing, it looked the cannotBeMinInLoop checks bound > min and isSafeIncreasingBound checks start < bound < limit.

For Decreasing, the cannotBeMaxInLoop checks bound < max and isSafeDecreasingBound checks limit < bound < start.

They check different thing such as lower bound/upper bound and vice versa.

I thought it is ok to keep the two functions.

If I missed something, please let me know.

Okay, thanks. Could you just add a couple more tests then, so that we cover steps other than one. Also, if they don't exist already, a couple of tests where the start value is already at the limit.

jaykang10 updated this revision to Diff 340502.Apr 26 2021, 6:39 AM

Following comments of @samparker, added test cases.

@samparker I have added more tests. Please check it.

jaykang10 updated this revision to Diff 340513.Apr 26 2021, 7:11 AM

Fixed typo

samparker accepted this revision.Apr 27 2021, 1:12 AM

Thanks, LGTM

This revision is now accepted and ready to land.Apr 27 2021, 1:12 AM
fhahn added a subscriber: fhahn.Apr 27 2021, 1:18 AM
fhahn added inline comments.
llvm/test/Transforms/IRCE/variable-loop-bounds.ll
366

I personally find tests with a lot of numbered BBs and instructions quite hard to read. IMO it would improve readability & maintainability of those tests if the blocks and instructions would have descriptive labels :)

fhahn added inline comments.Apr 27 2021, 1:20 AM
llvm/test/Transforms/IRCE/variable-loop-bounds.ll
358

Also, should we have tests checking the actual IR, at least the important bits like most other test do here?

jaykang10 added inline comments.Apr 27 2021, 2:30 AM
llvm/test/Transforms/IRCE/variable-loop-bounds.ll
358

Yep, I will update it.

366

Yep, I will update it.

Thanks, LGTM

Thanks @samparker! After updating tests following comments of @fhahn , I will push this change.

Won't this regress old-pm, or break again if/when new-pm is switched to populate loops in the other direction?

Won't this regress old-pm, or break again if/when new-pm is switched to populate loops in the other direction?

IRCE pass has not been enabled in the pipeline of old-pm and new-pm. The previous bound check was ok but it was a bit too conservative and it blocked for IRCE pass to handle loops which can be handled by the pass. The population order of loops affects SCEV and the SCEV blocks the IRCE pass. I think this change is fine. As next step, I will start to discussion to enable IRCE pass in the pipeline of new-pm.

Won't this regress old-pm, or break again if/when new-pm is switched to populate loops in the other direction?

IRCE pass has not been enabled in the pipeline of old-pm and new-pm.

Yes, i know.

The previous bound check was ok but it was a bit too conservative and it blocked for IRCE pass to handle loops which can be handled by the pass.
The population order of loops affects SCEV and the SCEV blocks the IRCE pass. I think this change is fine.

I think you didn't answer the question though.

As next step, I will start to discussion to enable IRCE pass in the pipeline of new-pm.

lebedev.ri added inline comments.Apr 27 2021, 3:36 AM
llvm/test/Transforms/IRCE/variable-loop-bounds.ll
370

This doesn't make sense.
%8 is -1 then: https://alive2.llvm.org/ce/z/SeYHXr

I think you didn't answer the question though.

From my opinion, it will not regress old-pm and it will not be affected by the population order of loops in new-pm. This change just relieves the bound check for new loop. If it is not proper answer for your question, please let me know.

With the order, if there are sibling loops, the target loop's predecessor could be located in previously processed loop which has complex CFG from optimization. From this situation, it is not easy to expect isLoopEntryGuardedByCond returns true.

I'm having a hard time parsing your messages :/
What does "is not easy" mean?
Is there some particular pattern that SCEV doesn't handle?
Perhaps it can be easily taught about it.

I think you didn't answer the question though.

From my opinion, it will not regress old-pm and it will not be affected by the population order of loops in new-pm. This change just relieves the bound check for new loop. If it is not proper answer for your question, please let me know.

Okay. So am i understanding correctly that we simply don't need that other check, and we don't have correctness problems when omitting it?

No further comments from me, thanks.

llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
715 ↗(On Diff #340513)

Does this need a SE.isKnownPositive(Step), like one in isSafeDecreasingBound()?

@samparker @fhahn @lebedev.ri. I am so sorry for spending your time. I have found several regressions which cause redundant loops. It looks the conservative bound check is needed in order to avoid it. I will close this review. I am sorry again.

nikic added a subscriber: nikic.Apr 27 2021, 9:16 AM

@jaykang10 Maybe you can add a test for the problem you encountered, to make sure it's not broken in the future?

lebedev.ri requested changes to this revision.Apr 27 2021, 9:57 AM
This revision now requires changes to proceed.Apr 27 2021, 9:57 AM
jaykang10 abandoned this revision.Apr 27 2021, 10:29 AM

@jaykang10 Maybe you can add a test for the problem you encountered, to make sure it's not broken in the future?

Yep, let me add the test cases.

jaykang10 retitled this revision from [IRCE] Relieve bound check on isSafeIncreasingBound and isSafeDecreasingBound to [IRCE] Add tests for conservative bound check.
jaykang10 edited the summary of this revision. (Show Details)

Added tests which causes redundant loops with this change.

lebedev.ri accepted this revision.Apr 28 2021, 2:51 AM

If they reproduce the miscompile then please proceed :)

This revision is now accepted and ready to land.Apr 28 2021, 2:51 AM

If they reproduce the miscompile then please proceed :)

Thanks @lebedev.ri!

Even though the test cases have weird loops, I think the pass needs to detect it. Let me push it.

This revision was automatically updated to reflect the committed changes.