This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Ensure ScalarEvolution::createAddRecFromPHIWithCastsImpl properly handles out of range truncations of the start and accum values
ClosedPublic

Authored by dneilson on Aug 29 2017, 10:04 AM.

Details

Summary

When constructing the predicate P1 in ScalarEvolution::createAddRecFromPHIWithCastsImpl() it is possible
for the PHISCEV from which the predicate is constructed to be a SCEVConstant instead of a SCEVAddRec. If
this happens, then the cast<SCEVAddRec>(PHISCEV) in the code will assert.

Such a PHISCEV is possible if either the start value or the accumulator value is a constant value
that not equal to its truncated value, and if the truncated value is zero.

This patch adds tests that demonstrate the cast<> assertion, and fixes this problem by checking
whether the PHISCEV is a constant before constructing the P1 predicate; if it is, then P1 is
equivalent to one of P2 or P3. Additionally, if we know that the start value or accumulator
value are constants then we check whether the P2 and/or P3 predicates are known false at compile
time; if either is, then we bail out of constructing the AddRec.

Event Timeline

dneilson created this revision.Aug 29 2017, 10:04 AM

Note: I'm not sure how resource management works in SCEV. There are some SCEVs being created here before the bail-out (return None) that are not explicitly deleted. Do we need to delete these, or is there some sort of SCEV resource management thing going on under the hood?

mkazantsev requested changes to this revision.Aug 30 2017, 10:22 PM
mkazantsev added a subscriber: mkazantsev.
mkazantsev added inline comments.
lib/Analysis/ScalarEvolution.cpp
4517

Assert that otherwise it is a SCEVConstant, or you expect it being something else?

4537

Please write a comment what this function is supposed to do. Semantically it looks like you mean isKnownNonEqual.

test/Analysis/ScalarEvolution/overflow-addrec.ll
1 ↗(On Diff #113106)

I don't think that -loop-vectorize is the best way to test SCEV (even though we have a couple of such files in this folder). Is there a way to see the impact of your changes using opt -analyze -scalar-evolution? You can keep this test set (e.g. in vectorization), but in test/Analysis/ScalarEvolution I'd rather see something that checks SCEVs.

18 ↗(On Diff #113106)

Please rename blocks into something like entry/loop/exit to make it more understandable.

28 ↗(On Diff #113106)

You may add a comment that this value is INT64_MIN.

This revision now requires changes to proceed.Aug 30 2017, 10:22 PM
dneilson added inline comments.Aug 31 2017, 7:33 AM
test/Analysis/ScalarEvolution/overflow-addrec.ll
1 ↗(On Diff #113106)

I don't know the SCEV code very well -- I'm not really that sure how else this patched function is used/triggered. If there's a way to get at the changed method using just opt -analyze -scalar-evolution, then that'd be great. I'm open to suggestions...

dneilson added inline comments.Aug 31 2017, 7:34 AM
lib/Analysis/ScalarEvolution.cpp
4539

Any thoughts on which option we should go with for this check? Should we limit to just the constant case (option 1), or go for more general (& expensive) with isKnownPredicate()?

dneilson updated this revision to Diff 113420.Aug 31 2017, 9:36 AM
dneilson edited edge metadata.

Addressing some reviewer comments.

dneilson marked 3 inline comments as done.Aug 31 2017, 9:36 AM
mkazantsev requested changes to this revision.Aug 31 2017, 9:42 PM

Code part looks ok for me (with comments addressed). I propose you to add a C++ unit test.

lib/Analysis/ScalarEvolution.cpp
4509

Please align this comment.

4518
assert(isa<SCEVConstant>(PHISCEV) && ...)
4544

For me, this option looks more reasonable.

return Expr != ExtendedExpr &&
       isKnownPredicate(ICmpInst::ICMP_NE, Expr, ExtendedExpr);
test/Analysis/ScalarEvolution/overflow-addrec.ll
1 ↗(On Diff #113106)

If you know a code example in which running opt -analyze scalar-evolution produces different output with and without your patch, you can just add it and check that the changes have happened. But most likely that your function does not affect construction of SCEVs and is only used by other passes as an auxiliary method. In this case I'd propose writing a C++ unit test (see unittests/Analysis/ScalarEvolutionTest.cpp). You can construct IR similar to your .ll examples and then directly invoke your function and check that the result is what you expect to have with your patch (or it just doesn't crash on attempt).

This revision now requires changes to proceed.Aug 31 2017, 9:42 PM
mkazantsev added inline comments.Aug 31 2017, 9:51 PM
lib/Analysis/ScalarEvolution.cpp
4544

By the way. I grew hesitant about the Expr != ExtendedExpr condition. If two SCEVs don't match pointer-wise, it doesn't mean that they are not equal. For example, constant 2 and 2 which is load from a field are equal, but you will have a SCEVConstant in one case and a SCEVUnknown in another case. I think that the correct option would be

return isKnownPredicate(ICmpInst::ICMP_NE, Expr, ExtendedExpr);
mkazantsev added inline comments.Aug 31 2017, 9:53 PM
lib/Analysis/ScalarEvolution.cpp
4544

It's not the case in your situation, though. So maybe it's OK, but using just isKnownPredicate looks more safe.

mkazantsev added inline comments.Aug 31 2017, 9:57 PM
lib/Analysis/ScalarEvolution.cpp
4544

Scratch this, I've re-read the code and realised that what I wrote is bizzare.

return Expr != ExtendedExpr &&
       isKnownPredicate(ICmpInst::ICMP_NE, Expr, ExtendedExpr);

is ok.

dneilson added inline comments.Sep 1 2017, 9:21 AM
lib/Analysis/ScalarEvolution.cpp
4544

The pointer comparison seemed odd to me as well, but I was matching the idiom used in other parts of the code that does the same thing. I'm guessing that there's some sort of SCEV caching thing going on behind the scenes, and it's possible to get the same SCEV object from different queries.

dneilson edited the summary of this revision. (Show Details)Sep 1 2017, 9:29 AM
dneilson updated this revision to Diff 113551.Sep 1 2017, 10:02 AM
dneilson edited edge metadata.

Address minor nicks. Change test from a LIT test to a unittest.

mkazantsev accepted this revision.Sep 1 2017, 3:03 PM

LGTM with nits: use isa for boolean type checks, not dyn_cast.

lib/Analysis/ScalarEvolution.cpp
4516

Use assert(isa<SCEVConstant>(PHISCEV) && ...)

unittests/Analysis/ScalarEvolutionTest.cpp
1149

Use EXPECT_TRUE(isa<SCEVUnknown>(Expr)), as in the function above.

This revision is now accepted and ready to land.Sep 1 2017, 3:03 PM
This revision was automatically updated to reflect the committed changes.
dneilson added a subscriber: dorit.Sep 5 2017, 12:58 PM

A couple of quick notes:

  1. The SCEV owner (Sanjoy) added a reviewer after this review was given the thumbs up by another reviewer. I am interpreting this addition of a reviewer an an 'FYI' for the added reviewer. If this is not the correct interpretation, then please feel free to revert the change in trunk.
  1. FYI @dorit This fixes a bug in code you introduced in D30041
dorit added a comment.Sep 6 2017, 4:40 AM
  1. FYI @dorit This fixes a bug in code you introduced in D30041

Thanks! (good to know that this code got triggered :-))
Thanks for the fix,

Dorit

sanjoy edited edge metadata.Sep 7 2017, 9:41 AM

A couple of quick notes:

  1. The SCEV owner (Sanjoy) added a reviewer after this review was given the thumbs up by another reviewer. I am interpreting this addition of a reviewer an an 'FYI' for the added reviewer.

Yes, that's what I meant (there is no need to revert).