[ScalarEvolution] Re-enable Predicate implication from operations

[mkazantsev]

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

[mkazantsev]

I need to add some tests on addition.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

8690

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

[mkazantsev]

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

[sanjoy]

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).

[mkazantsev]

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]

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]

Closed by http://llvm.org/viewvc/llvm-project?view=revision&revision=298690

[mkazantsev]

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

[mkazantsev]

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]

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]

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

[mkazantsev]

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

[mkazantsev]

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

[sanjoy]

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.

[sanjoy]

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]

Some comment fixed, no functional changes.

lib/Analysis/ScalarEvolution.cpp

static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE,
   llvm_unreachable("covered switch fell through?!");
 }
 
 bool ScalarEvolution::isImpliedViaOperations(ICmpInst::Predicate Pred,
                                              const SCEV *LHS, const SCEV *RHS,
                                              const SCEV *FoundLHS,
                                              const SCEV *FoundRHS,
                                              unsigned Depth) {
+  assert(getTypeSizeInBits(LHS->getType()) ==
+             getTypeSizeInBits(RHS->getType()) &&
+         "LHS and RHS have different sizes?");
+  assert(getTypeSizeInBits(FoundLHS->getType()) ==
+             getTypeSizeInBits(FoundRHS->getType()) &&
+         "FoundLHS and FoundRHS have different sizes?");
   // We want to avoid hurting the compile time with analysis of too big trees.
   if (Depth > MaxSCEVOperationsImplicationDepth)
     return false;
   // We only want to work with ICMP_SGT comparison so far.
   // TODO: Extend to ICMP_UGT?
   if (Pred == ICmpInst::ICMP_SLT) {
     Pred = ICmpInst::ICMP_SGT;
     std::swap(LHS, RHS);
     std::swap(FoundLHS, FoundRHS);
   }
   if (Pred != ICmpInst::ICMP_SGT)
     return false;
 
   auto GetOpFromSExt = [&](const SCEV *S) {
     if (auto *Ext = dyn_cast<SCEVSignExtendExpr>(S))
       return Ext->getOperand();
     // TODO: If S is a SCEVConstant then you can cheaply "strip" the sext off
     // the constant in some cases.
     return S;
   };
 
   // Acquire values from extensions.
   auto *OrigFoundLHS = FoundLHS;
   LHS = GetOpFromSExt(LHS);
   FoundLHS = GetOpFromSExt(FoundLHS);
 
   // Is the SGT predicate can be proved trivially or using the found context.
   auto IsSGTViaContext = [&](const SCEV *S1, const SCEV *S2) {
-    assert(S1->getType() == S2->getType() && "Proving for wrong types?");
     return isKnownViaSimpleReasoning(ICmpInst::ICMP_SGT, S1, S2) ||
            isImpliedViaOperations(ICmpInst::ICMP_SGT, S1, S2, OrigFoundLHS,
                                   FoundRHS, Depth + 1);
   };
 
   if (auto *LHSAddExpr = dyn_cast<SCEVAddExpr>(LHS)) {
     // We want to avoid creation of any new non-constant SCEV. Since we are
     // going to compare the operands to RHS, we should be certain that we don't
     // need any type conversions for this. So let's decline all cases when the
     // types of LHS and RHS do not match.
     // TODO: Maybe try to get RHS from sext to catch more cases?
     if (LHSAddExpr->getType() != RHS->getType())
       return false;
 
     // Should not overflow.
if (auto *LHSAddExpr = dyn_cast<SCEVAddExpr>(LHS)) {
     using namespace llvm::PatternMatch;
     if (match(LHSUnknownExpr->getValue(), m_SDiv(m_Value(LL), m_Value(LR)))) {
       // Rules for division.
       // We are going to perform some comparisons with Denominator and its
       // derivative expressions. In general case, creating a SCEV for it may
       // lead to a complex analysis of the entire graph, and in particular it
       // can request trip count recalculation for the same loop. This would
       // cache as SCEVCouldNotCompute to avoid the infinite recursion. This is a
       // sad thing. To avoid this, we only want to create SCEVs that are
       // constants in this section. So we bail if Denominator is not a constant.
       if (!isa<ConstantInt>(LR))
         return false;
 
       auto *Denominator = cast<SCEVConstant>(getSCEV(LR));
 
       // We want to make sure that LHS = FoundLHS / Denominator. If it is so,
       // then a SCEV for the numerator already exists and matches with FoundLHS.
       auto *Numerator = getExistingSCEV(LL);
 
       // Make sure that it exists and has the same type.
       if (!Numerator || Numerator->getType() != FoundLHS->getType())
         return false;
 
       // Make sure that the numerator matches with FoundLHs and the denominator
       // is positive.
       if (!HasSameValue(Numerator, FoundLHS) || !isKnownPositive(Denominator))
         return false;
 
+      auto *DTy = Denominator->getType();
+      auto *FRHSTy = FoundRHS->getType();
+      if (DTy->isPointerTy() != FRHSTy->isPointerTy())
+        // One of types is a pointer and another one is not. We cannot extend
+        // them properly to a wider type, so let us just reject this case.
+        return false;
+
       // Given that:
       // FoundLHS > FoundRHS, LHS = FoundLHS / Denominator, Denominator > 0.
-      auto *Ty2 = getWiderType(Denominator->getType(), FoundRHS->getType());
-      auto *DenominatorExt = getNoopOrSignExtend(Denominator, Ty2);
-      auto *FoundRHSExt = getNoopOrSignExtend(FoundRHS, Ty2);
+      auto *WTy = getWiderType(DTy, FRHSTy);
+      auto *DenominatorExt = getNoopOrSignExtend(Denominator, WTy);
+      auto *FoundRHSExt = getNoopOrSignExtend(FoundRHS, WTy);
 
       // Try to prove the following rule:
       // (FoundRHS > Denominator - 2) && (RHS <= 0) => (LHS > RHS).
       // For example, given that FoundLHS > 2. It means that FoundLHS is at
       // least 3. If we divide it by Denominator < 4, we will have at least 1.
-      auto *DenomMinusTwo = getMinusSCEV(DenominatorExt, getConstant(Ty2, 2));
+      auto *DenomMinusTwo = getMinusSCEV(DenominatorExt, getConstant(WTy, 2));
       if (isKnownNonPositive(RHS) &&
           IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
         return true;
 
       // Try to prove the following rule:
       // (FoundRHS > -1 - Denominator) && (RHS < 0) => (LHS > RHS).
       // For example, given that FoundLHS > -3. Then FoundLHS is at least -2.
       // If we divide it by Denominator > 2, then:
       // 1. If FoundLHS is negative, then the result is 0.
       // 2. If FoundLHS is non-negative, then the result is non-negative.
       // Anyways, the result is non-negative.
-      auto *MinusOne = getNegativeSCEV(getOne(Ty2));
+      auto *MinusOne = getNegativeSCEV(getOne(WTy));
       auto *NegDenomMinusOne = getMinusSCEV(MinusOne, DenominatorExt);
       if (isKnownNegative(RHS) &&
           IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
         return true;
     }
   }
 
   return false;

test/Analysis/ScalarEvolution/implied-via-addition.ll

 ; CHECK: call void @use(i1 true)
   call void @use(i1 %c)
   %be = icmp slt i8 %idx.inc, 42
   br i1 %be, label %loop, label %exit
 
  exit:
   ret void
 }
+
+define void @test_02(i8 %t) {
+; CHECK-LABEL: test_02
+ entry:
+  %t.ptr = inttoptr i8 %t to i8*
+  %p.42 = inttoptr i8 42 to i8*
+  %cmp1 = icmp slt i8* %t.ptr, %p.42
+  call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
+  br label %loop
+
+ loop:
+; CHECK-LABEL: loop
+  %idx = phi i8* [ %t.ptr, %entry ], [ %snext, %loop ]
+  %snext = getelementptr inbounds i8, i8* %idx, i64 1
+  %c = icmp slt i8* %idx, %p.42
+; CHECK: call void @use(i1 true)
+  call void @use(i1 %c)
+  %be = icmp slt i8* %snext, %p.42
+  br i1 %be, label %loop, label %exit
+
+ exit:
+  ret void
+}