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

[dneilson]

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.

[dneilson]

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]

lib/Analysis/ScalarEvolution.cpp

4486 ↗

(On Diff #113106)

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

4507 ↗

(On Diff #113106)

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.

[dneilson]

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]

lib/Analysis/ScalarEvolution.cpp

4509 ↗

(On Diff #113106)

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]

Addressing some reviewer comments.

[mkazantsev]

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

lib/Analysis/ScalarEvolution.cpp

4478 ↗

(On Diff #113420)

Please align this comment.

4487 ↗

(On Diff #113420)

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

4516 ↗

(On Diff #113420)

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

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

4516 ↗

(On Diff #113420)

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]

lib/Analysis/ScalarEvolution.cpp

4516 ↗

(On Diff #113420)

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

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

4516 ↗

(On Diff #113420)

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]

lib/Analysis/ScalarEvolution.cpp

4516 ↗

(On Diff #113420)

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]

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

[mkazantsev]

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

lib/Analysis/ScalarEvolution.cpp

4516 ↗

(On Diff #113551)

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

unittests/Analysis/ScalarEvolutionTest.cpp

1149 ↗

(On Diff #113551)

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

[dneilson]

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.

2. FYI @dorit This fixes a bug in code you introduced in D30041

[dorit]

2. 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]

In D37265#861418, @dneilson wrote:

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

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
     if (i != FoundIndex)
       Ops.push_back(Add->getOperand(i));
   const SCEV *Accum = getAddExpr(Ops);
 
   // The runtime checks will not be valid if the step amount is
   // varying inside the loop.
   if (!isLoopInvariant(Accum, L))
     return None;
-  
   // *** Part2: Create the predicates 
 
   // Analysis was successful: we have a phi-with-cast pattern for which we
   // can return an AddRec expression under the following predicates:
   //
   // P1: A Wrap predicate that guarantees that Trunc(Start) + i*Trunc(Accum)
   //     fits within the truncated type (does not overflow) for i = 0 to n-1.
   // P2: An Equal predicate that guarantees that 
ScalarEvolution::createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI) {
   //   = (Ext ix (Trunc iy ((Start + (i-1)*Accum) + Accum) to ix) to iy) 
   //     + Accum                            :: from P1: Ext(x)+Ext(y)=>Ext(x+y)
   //
   //   = (Ext ix (Trunc iy (Start + i*Accum) to ix) to iy) + Accum
   //   = (Ext ix (Trunc iy (Expr(i)) to ix) to iy) + Accum 
   //
   // By induction, the same applies to all iterations 1<=i<n:
   //
-  
   // Create a truncated addrec for which we will add a no overflow check (P1).
   const SCEV *StartVal = getSCEV(StartValueV);
-  const SCEV *PHISCEV = 
+  const SCEV *PHISCEV =
       getAddRecExpr(getTruncateExpr(StartVal, TruncTy),
-                    getTruncateExpr(Accum, TruncTy), L, SCEV::FlagAnyWrap); 
-  const auto *AR = cast<SCEVAddRecExpr>(PHISCEV);
+                    getTruncateExpr(Accum, TruncTy), L, SCEV::FlagAnyWrap);
 
+  // PHISCEV can be either a SCEVConstant or a SCEVAddRecExpr.
+  // ex: If truncated Accum is 0 and StartVal is a constant, then PHISCEV
+  // will be constant.
+  //
+  //  If PHISCEV is a constant, then P1 degenerates into P2 or P3, so we don't
+  // add P1.
+  if (const auto *AR = dyn_cast<SCEVAddRecExpr>(PHISCEV)) {
     SCEVWrapPredicate::IncrementWrapFlags AddedFlags =
         Signed ? SCEVWrapPredicate::IncrementNSSW
                : SCEVWrapPredicate::IncrementNUSW;
     const SCEVPredicate *AddRecPred = getWrapPredicate(AR, AddedFlags);
     Predicates.push_back(AddRecPred);
+  } else
+    assert(isa<SCEVConstant>(PHISCEV) && "Expected constant SCEV");
 
   // Create the Equal Predicates P2,P3:
-  auto AppendPredicate = [&](const SCEV *Expr) -> void {
+
+  // It is possible that the predicates P2 and/or P3 are computable at
+  // compile time due to StartVal and/or Accum being constants.
+  // If either one is, then we can check that now and escape if either P2
+  // or P3 is false.
+
+  // Construct the extended SCEV: (Ext ix (Trunc iy (Expr) to ix) to iy)
+  // for each of StartVal and Accum
+  auto GetExtendedExpr = [&](const SCEV *Expr) -> const SCEV * {
     assert(isLoopInvariant(Expr, L) && "Expr is expected to be invariant");
     const SCEV *TruncatedExpr = getTruncateExpr(Expr, TruncTy);
     const SCEV *ExtendedExpr =
         Signed ? getSignExtendExpr(TruncatedExpr, Expr->getType())
                : getZeroExtendExpr(TruncatedExpr, Expr->getType());
+    return ExtendedExpr;
+  };
+
+  // Given:
+  //  ExtendedExpr = (Ext ix (Trunc iy (Expr) to ix) to iy
+  //               = GetExtendedExpr(Expr)
+  // Determine whether the predicate P: Expr == ExtendedExpr
+  // is known to be false at compile time
+  auto PredIsKnownFalse = [&](const SCEV *Expr,
+                              const SCEV *ExtendedExpr) -> bool {
+    return Expr != ExtendedExpr &&
+           isKnownPredicate(ICmpInst::ICMP_NE, Expr, ExtendedExpr);
+  };
+
+  const SCEV *StartExtended = GetExtendedExpr(StartVal);
+  if (PredIsKnownFalse(StartVal, StartExtended)) {
+    DEBUG(dbgs() << "P2 is compile-time false\n";);
+    return None;
+  }
+
+  const SCEV *AccumExtended = GetExtendedExpr(Accum);
+  if (PredIsKnownFalse(Accum, AccumExtended)) {
+    DEBUG(dbgs() << "P3 is compile-time false\n";);
+    return None;
+  }
+
+  auto AppendPredicate = [&](const SCEV *Expr,
+                             const SCEV *ExtendedExpr) -> void {
     if (Expr != ExtendedExpr &&
         !isKnownPredicate(ICmpInst::ICMP_EQ, Expr, ExtendedExpr)) {
       const SCEVPredicate *Pred = getEqualPredicate(Expr, ExtendedExpr);
       DEBUG (dbgs() << "Added Predicate: " << *Pred);
       Predicates.push_back(Pred);
     }
   };
-  
-  AppendPredicate(StartVal);
-  AppendPredicate(Accum);
-  
+  AppendPredicate(StartVal, StartExtended);
+  AppendPredicate(Accum, AccumExtended);
   // *** Part3: Predicates are ready. Now go ahead and create the new addrec in
   // which the casts had been folded away. The caller can rewrite SymbolicPHI
   // into NewAR if it will also add the runtime overflow checks specified in
   // Predicates.  
   auto *NewAR = getAddRecExpr(StartVal, Accum, L, SCEV::FlagAnyWrap);
 
   std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
       std::make_pair(NewAR, Predicates);

llvm/trunk/unittests/Analysis/ScalarEvolutionTest.cpp

auto *NewCond = Builder.CreateICmp(
       ICmpInst::ICMP_SLT, Add, ConstantInt::get(T_int64, 2000), "new.cond");
   Builder.CreateCondBr(NewCond, L, Post);
   const SCEV *NewEC = SE.getBackedgeTakenCount(Loop);
   EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewEC));
   EXPECT_TRUE(isa<SCEVConstant>(NewEC));
   EXPECT_EQ(cast<SCEVConstant>(NewEC)->getAPInt().getLimitedValue(), 1999u);
 }
 
+TEST_F(ScalarEvolutionsTest, SCEVAddRecFromPHIwithLargeConstants) {
+  // Reference: https://reviews.llvm.org/D37265
+  // Make sure that SCEV does not blow up when constructing an AddRec
+  // with predicates for a phi with the update pattern:
+  //  (SExt/ZExt ix (Trunc iy (%SymbolicPHI) to ix) to iy) + InvariantAccum
+  // when either the initial value of the Phi or the InvariantAccum are
+  // constants that are too large to fit in an ix but are zero when truncated to
+  // ix.
+  FunctionType *FTy =
+      FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false);
+  Function *F = cast<Function>(M.getOrInsertFunction("addrecphitest", FTy));
+
+  /*
+    Create IR:
+    entry:
+     br label %loop
+    loop:
+     %0 = phi i64 [-9223372036854775808, %entry], [%3, %loop]
+     %1 = shl i64 %0, 32
+     %2 = ashr exact i64 %1, 32
+     %3 = add i64 %2, -9223372036854775808
+     br i1 undef, label %exit, label %loop
+    exit:
+     ret void
+   */
+  BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
+  BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F);
+  BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F);
+
+  // entry:
+  BranchInst::Create(LoopBB, EntryBB);
+  // loop:
+  auto *MinInt64 =
+      ConstantInt::get(Context, APInt(64, 0x8000000000000000U, true));
+  auto *Int64_32 = ConstantInt::get(Context, APInt(64, 32));
+  auto *Br = BranchInst::Create(
+      LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), LoopBB);
+  auto *Phi = PHINode::Create(Type::getInt64Ty(Context), 2, "", Br);
+  auto *Shl = BinaryOperator::CreateShl(Phi, Int64_32, "", Br);
+  auto *AShr = BinaryOperator::CreateExactAShr(Shl, Int64_32, "", Br);
+  auto *Add = BinaryOperator::CreateAdd(AShr, MinInt64, "", Br);
+  Phi->addIncoming(MinInt64, EntryBB);
+  Phi->addIncoming(Add, LoopBB);
+  // exit:
+  ReturnInst::Create(Context, nullptr, ExitBB);
+
+  // Make sure that SCEV doesn't blow up
+  ScalarEvolution SE = buildSE(*F);
+  SCEVUnionPredicate Preds;
+  const SCEV *Expr = SE.getSCEV(Phi);
+  EXPECT_NE(nullptr, Expr);
+  EXPECT_TRUE(isa<SCEVUnknown>(Expr));
+  auto Result = SE.createAddRecFromPHIWithCasts(cast<SCEVUnknown>(Expr));
+}
+
 }  // end anonymous namespace
 }  // end namespace llvm