[SCEV] Ensure ScalarEvolution::createAddRecFromPHIWithCastsImpl is working with an add expression.

[dneilson]

Summary

In ScalarEvolution::createAddRecFromPHIWithCastsImpl() with the added test we get to the cast below, and then throw an assert because the PHISCEV is not actually a SCEVAddRecExpr -- getAddRecExpr seems to have simplified it down to a constant -7.

 const SCEV *PHISCEV =
    getAddRecExpr(getTruncateExpr(StartVal, TruncTy),
                  getTruncateExpr(Accum, TruncTy), L, SCEV::FlagAnyWrap);
const auto *AR = cast<SCEVAddRecExpr>(PHISCEV);

The test is:

define void @foo() {                                                                                                                                                                                     
bb:
  br label %bb1                                                                                                                                                                                             
bb1:
  %tmp = phi i64 [ -7, %bb ], [ %tmp4, %bb1 ]
  %tmp2 = shl i64 %tmp, 32
  %tmp3 = ashr exact i64 %tmp2, 32
  %tmp4 = xor i64 %tmp3, -9223372036854775808
  br i1 undef, label %bb5, label %bb1                                                                                                                                                                                      
bb5:
  unreachable
}

With this test, we end up with the back-edge value (BEValueV) being the %tmp4 = xor... This strikes me as odd that we would try to reason about an 'add' that is actually an xor, so this patch bails out early if we identify that the back-edge value that we have is anything other than an add.

I'm not entirely sure this is the 100% correct way to approach this fix. I'm adding this patch as a starting point to figure out how to tackle this.

[dneilson]

• Add 'RUN' line to test.

[reames]

lib/Analysis/ScalarEvolution.cpp

4387

I think you've misdiagnosed the bug here. getSCEV is supposed to always return a SCEV for a value when requested. It may return SCEVUnknown, but that's still a valid SCEV. As such, the check for AddRec just below this should prevent the xor flowing through. I suspect you're actual issue is that getSCEV has return nullptr.

p.s. I suggest chatting with Max or Sanjoy to confirm everything I just said. I'm not SCEV expert.

[dneilson]

lib/Analysis/ScalarEvolution.cpp

4387

That doesn't mesh with what I was seeing here. What I was seeing with the added test case is that we get all the way down to line 4479, and blow up there. PHISCEV appears to be a constant value of -7 rather than any sort of AddRec, so the cast on that line ends up failing.

When I dump the intermediate values I find that BEValueV is the xor in the loop (%tmp4 = xor i64 %tmp3, -9223372036854775808). This method seems to be written assuming that BEValueV is an add operator -- the RHS is even cast to a SCEVAddExpr on line 4392. It seems pretty clear that an SCEVAddRec is for the addition operator, and constructing one from any other operator is just asking for trouble; hence the patch as written...

Also, the if directly before this one returns 'None' to signify an early bail-out, so it seems to me that's the expected behaviour of this method.

[dneilson]

Got some more info... changing the xor into an add in the test also results in the same assert firing. So, more digging needed.

lib/Analysis/ScalarEvolution.cpp

for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
     } else if (StartValueV != V) {
       StartValueV = nullptr;
       break;
     }
   }
   if (!BEValueV || !StartValueV)
     return None;
 
+  // Make sure that the expression that updates the PHI is an Add
+  if (auto *Op = dyn_cast<BinaryOperator>(BEValueV)) {
+    if (Op->getOpcode() != Instruction::BinaryOps::Add)
+      return None;
+  }
+
   const SCEV *BEValue = getSCEV(BEValueV);
 
   // If the value coming around the backedge is an add with the symbolic
   // value we just inserted, possibly with casts that we can ignore under
   // an appropriate runtime guard, then we found a simple induction variable!
   const auto *Add = dyn_cast<SCEVAddExpr>(BEValue);
   if (!Add)
     return None;
 

test/Analysis/ScalarEvolution/loop-xor.ll

+; opt -S -loop-vectorize < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
+target triple = "x86_64-unknown-linux-gnu"
+
+; This test is here to make sure that the SCEV predicate rewriter
+; does not attempt to create a SCEVAddRec from a loop expression
+; that isn't actually an add. If it does try, then this test
+; will likely cause it to blow up.
+define void @foo() {
+; CHECK-LABEL: @foo
+
+; CHECK-LABEL: bb:
+; CHECK: br label %bb1
+bb:
+  br label %bb1
+
+; CHECK-LABEL: bb1:
+; CHECK:  %tmp = phi i64 [ -7, %bb ], [ %tmp4, %bb1 ]
+; CHECK:  %tmp2 = shl i64 %tmp, 32
+; CHECK:  %tmp3 = ashr exact i64 %tmp2, 32
+; CHECK:  %tmp4 = xor i64 %tmp3, -9223372036854775808
+; CHECK:  br
+bb1:
+  %tmp = phi i64 [ -7, %bb ], [ %tmp4, %bb1 ]
+  %tmp2 = shl i64 %tmp, 32
+  %tmp3 = ashr exact i64 %tmp2, 32
+  %tmp4 = xor i64 %tmp3, -9223372036854775808
+  br i1 undef, label %bb5, label %bb1
+
+; CHECK-LABEL: bb5:
+; CHECK: unreachable
+bb5:
+  unreachable
+}