This is an archive of the discontinued LLVM Phabricator instance.

[ScalarEvolution] Re-enable Predicate implication from operations
ClosedPublic

Authored by mkazantsev on Mar 22 2017, 5:23 AM.

Details

Summary

The patch rL298481 was reverted due to crash on clang-with-lto-ubuntu build.
The reason of the crash was type mismatch between either a or b and RHS in the following situation:

LHS = sext(a +nsw b) > RHS.

This is quite rare, but still possible situation. Normally we need to cast all {a, b, RHS} to their widest type.
But we try to avoid creation of new SCEV that are not constants to avoid initiating recursive analysis that
can take a lot of time and/or cache a bad value for iterations number. To deal with this, in this patch we
reject this case and will not try to analyze it if the type of sum doesn't match with the type of RHS. In this
situation we don't need to create any non-constant SCEVs.

This patch also adds an assertion to the method IsProvedViaContext so that we could fail on it and not
go further into range analysis etc (because in some situations these analyzes succeed even when the passed
arguments have wrong types, what should not normally happen).

Another problem was connected to overprotective assertion that assumes that the types of operands
of ADD always match. This is not always true: SCEV can use this instruction for adding a value to a
pointer.

The patch also contains a fix for a problem with too narrow scope of the analysis caused by wrong
usage of predicates in recursive invocations.

The regression test on the said failure: test/Analysis/ScalarEvolution/implied-via-addition.ll

Diff Detail

Event Timeline

mkazantsev created this revision.Mar 22 2017, 5:23 AM
mkazantsev planned changes to this revision.Mar 22 2017, 5:43 AM

I need to add some tests on addition.

mkazantsev added inline comments.Mar 23 2017, 2:13 AM
lib/Analysis/ScalarEvolution.cpp
8690

Should use SGT predicate for IsProvedViaContext only, because isImpliedViaOperations never hits for SLE.

mkazantsev updated this revision to Diff 92779.Mar 23 2017, 3:34 AM
mkazantsev marked an inline comment as done.
mkazantsev edited the summary of this revision. (Show Details)

Fixed an issue with wrong predicates, added a regression test to the problem that happened in buildbot.

sanjoy accepted this revision.Mar 23 2017, 2:52 PM

lgtm with minor comments (i.e. fix these and check in without further review).

lib/Analysis/ScalarEvolution.cpp
8576

How about asserting here that

  • The types of LHS and RHS match
  • The types of FoundLHS and FoundRHS match

?

8590

There is one enhancement possible here, please add that as a TODO: if S is a SCEVConstant then too you can cheaply "strip" the sext off the constant in some cases.

8613

Another TODO here would be that we can also do RHS = GetOpFromSExt(RHS) earlier to catch more cases.

8675

The code is correct, but the comment is wrong. We only have the implication one way: (FoundRHS > Denominator - 2) => (Denominator - 1 <= FoundRHS), since if Denominator is INT_SMAX + 2 then Denominator - 2 = INT_SMAX, but Denominator - 1 = INT_SMIN. For any FoundRHS, this means Denominator - 1 <= FoundRHS is true, but FoundRHS > Denominator - 2 is false.

Secondly, the comment would be more readable if you write the comment with FoundRHS on the same side on both the antecedent and the consequent.

8688

I think the issue mentioned for the previous comment above applies here as well.

test/Analysis/ScalarEvolution/scev-division.ll
3 ↗(On Diff #92779)

I should have noticed in the previous iteration of the patch, but we should call these test files something more specific -- like implied-via-division.ll or something. Also: the scev- prefix is redundant since we're in the ScalarEvolution directory (though I do see it used in a few other tests).

This revision is now accepted and ready to land.Mar 23 2017, 2:52 PM
mkazantsev added inline comments.Mar 23 2017, 9:45 PM
lib/Analysis/ScalarEvolution.cpp
8576

This assertion actually fails on test Transforms/IndVarSimplify/2011-11-01-lftrptr.ll even if placed to the beginning of isImpliedCondOperandsHelper method (and ViaOperations stuff is disabled). I am not certain for 100% is it a bug or not, but potentially it is. Even if so, its reason lies outside this patch. I will try to investigate it.

Currently we do not require the match of these types for our code here (yet I assumed that they do match). All required type conversions within isImpliedViaOperations are done explicitly. So let us not do it here. Instead, I will try to understand whether the failure on this assertion on those test is a bug, and if it is, I will add them with the fix patch.

mkazantsev marked 5 inline comments as done.

Only comments and test file names changed. No functional changes. Found (potential) issue with assertions exists without this patch and will be checked separately.

mkazantsev edited the summary of this revision. (Show Details)Mar 23 2017, 11:07 PM
mkazantsev reopened this revision.Mar 24 2017, 12:18 AM

Surprisingly, this still causes (different) failures on clang build. Need to investigate them.

This revision is now accepted and ready to land.Mar 24 2017, 12:18 AM
mkazantsev planned changes to this revision.Mar 24 2017, 12:18 AM
mkazantsev added inline comments.Mar 24 2017, 12:35 AM
lib/Analysis/ScalarEvolution.cpp
8616

This is not entirely correct, because the type lf ADD is defined by the type of its last argument. It may not match with the type of the 1st argument. The problem is that one of the operands is sometimes a reference.

So we run into "assert(S1->getType() == S2->getType() && "Proving for wrong types?");" failure in this case.

mkazantsev added inline comments.Mar 24 2017, 1:46 AM
lib/Analysis/ScalarEvolution.cpp
8576

The reason of this failure is that this kind of assertions is overprotective. We should check only type size match to allow comparisons between integers and pointers.

8616

Actually this is valid, but the assert is overprotective. We should not check the types match, only width match.

mkazantsev updated this revision to Diff 92905.Mar 24 2017, 2:23 AM
mkazantsev marked 3 inline comments as done.

Fixed overprotective assertions and added a regression test on the newly detected crash related to pointers.

This revision is now accepted and ready to land.Mar 24 2017, 2:23 AM
mkazantsev edited the summary of this revision. (Show Details)Mar 24 2017, 2:25 AM
mkazantsev updated this revision to Diff 92906.Mar 24 2017, 2:27 AM
mkazantsev updated this revision to Diff 92915.Mar 24 2017, 3:34 AM

Lossened checks on addition (since we now only require size match) and reduced the depth to avoid hurting compile time too much.

mkazantsev requested review of this revision.Mar 28 2017, 1:10 PM
mkazantsev edited edge metadata.

The changes with pointers need review, please take a look.

sanjoy accepted this revision.Mar 30 2017, 12:47 PM

lgtm with nits inline.

lib/Analysis/ScalarEvolution.cpp
8652

Minor, but I'd drop the "This is a sad thing." -- I don't think that observation adds anything here. :)

8663

I'd drop this "Make sure ..." comment and also the one below -- the code is descriptive enough to tell you what you're doing and the comment does not add much.

If possible add a line on _why_ you care about these things, but if that's going to be too verbose, then I'd say just remove this comment and the one below.

8667

s/FoundLHs/FoundLHS/

8676

The correct fix here is to use getEffectiveSCEVType for DTy, FRHSTy etc. instead of just calling getType() on the Value.

However, for a first pass what you have here is fine. But please add a TODO.

This revision is now accepted and ready to land.Mar 30 2017, 12:47 PM
sanjoy added inline comments.Mar 30 2017, 12:49 PM
lib/Analysis/ScalarEvolution.cpp
8676

I meant to say, please add a TODO for now, and then fix in a subsequent change. Same for the other TODOs in this patch, except perhaps the "// TODO: Extend to ICMP_UGT?" one.

mkazantsev updated this revision to Diff 93620.Mar 31 2017, 5:07 AM
mkazantsev marked 5 inline comments as done.

Some comment fixed, no functional changes.

This revision was automatically updated to reflect the committed changes.