[ARM] Loop Strength Reduction crashes when targeting ARM or Thumb.

[labrinea]

Summary

Scalar Evolution asserts when not all the operands of an Add Recurrence Expression are loop invariants. Loop Strength Reduction should only create affine Add Recurrences, so that both the start and the step of the expression are loop invariants.

A corresponding bug has been raised here: https://llvm.org/bugs/show_bug.cgi?id=30325

[efriedma]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

329

"SE.isLoopInvariant(AR->getStepRecurrence(SE), AR->getLoop())" is always true; if you try to build an AddRec with non-invariant operands, you'll hit the assertion you pointed out.

581

It would be more clear to check "SE.isLoopInvariant(RHS, AR->getLoop())".

3206

Again, useless check.

[labrinea]

The test I have added is a reproducer that triggers the assertion in the absence of these checks. What would be a proper fix if these checks are useless?

[efriedma]

Err, hang on, I must be missing something... ignore me for the moment; taking another look.

[efriedma]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

329

Ah, right, my previous comment was wrong. "AR->isAffine()" would be a more clear way to write this check. (A non-affine AddRec always has a step which is not invariant, and an affine AddRec always has a step which is invariant.)

581

(Ignore my previous comment here.)

3206

(Ignore my previous comment here.)

[labrinea]

An Affine AddRec always has a Step which is invariant. This is the right thing to check instead of the Step itself.

[labrinea]

Accidentally uploaded a diff with too few context. Uploaded again.

[efriedma]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

581

Please move this check into the earlier if statement.

3205

Please move this check earlier (maybe the same place as the "AR->getStart()->isZero()" check).

test/Transforms/LoopStrengthReduce/ARM/addrec-is-loop-invariant.ll

4

This issue has nothing to do with LCSSA, as far as I can tell.

[labrinea]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

571

Like this:

-    if (IgnoreSignificantBits || isAddRecSExtable(AR, SE)) {
+    if ((IgnoreSignificantBits || isAddRecSExtable(AR, SE)) && AR->isAffine()) {

?

3194

Something like:

-    if (AR->getStart()->isZero())
+    if (AR->getStart()->isZero() || !AR->isAffine())

?

test/Transforms/LoopStrengthReduce/ARM/addrec-is-loop-invariant.ll

18

Here, %c.0 is used outside of loop0, where it is defined. Adding a PHI node for it prevents the issue. That's why I am mentioning the LCSSA form.

[efriedma]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

571

Yes.

3194

Yes.

test/Transforms/LoopStrengthReduce/ARM/addrec-is-loop-invariant.ll

18

Oh, LCSSA hides the issue because SCEV doesn't look through LCSSA PHI nodes. That doesn't really mean the lack of LCSSA is causing the problem, though... you could probably trigger this with IR in LCSSA form by messing with the loop nest (for example, make loop1 a subloop of loop0).

[labrinea]

Ping @efriedma

[efriedma]

LGTM. (I'm not exactly an LSR expert, but this change is simple enough that I feel comfortable approving it anyway.)

[atrick]

Thanks @efriedma.

lib/Transforms/Scalar/LoopStrengthReduce.cpp

static void DoInitialMatch(const SCEV *S, Loop *L,
   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
     for (const SCEV *S : Add->operands())
       DoInitialMatch(S, L, Good, Bad, SE);
     return;
   }
 
   // Look at addrec operands.
   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
-    if (!AR->getStart()->isZero()) {
+    if (!AR->getStart()->isZero() && AR->isAffine()) {
       DoInitialMatch(AR->getStart(), L, Good, Bad, SE);
       DoInitialMatch(SE.getAddRecExpr(SE.getConstant(AR->getType(), 0),
                                       AR->getStepRecurrence(SE),
                                       // FIXME: AR->getNoWrapFlags()
                                       AR->getLoop(), SCEV::FlagAnyWrap),
                      L, Good, Bad, SE);
       return;
     }
 
if (const SCEVConstant *C = dyn_cast<SCEVConstant>(LHS)) {
     const APInt &RA = RC->getAPInt();
     if (LA.srem(RA) != 0)
       return nullptr;
     return SE.getConstant(LA.sdiv(RA));
   }
 
   // Distribute the sdiv over addrec operands, if the addrec doesn't overflow.
   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS)) {
-    if (IgnoreSignificantBits || isAddRecSExtable(AR, SE)) {
+    if ((IgnoreSignificantBits || isAddRecSExtable(AR, SE)) && AR->isAffine()) {
       const SCEV *Step = getExactSDiv(AR->getStepRecurrence(SE), RHS, SE,
                                       IgnoreSignificantBits);
       if (!Step) return nullptr;
       const SCEV *Start = getExactSDiv(AR->getStart(), RHS, SE,
                                        IgnoreSignificantBits);
       if (!Start) return nullptr;
       // FlagNW is independent of the start value, step direction, and is
       // preserved with smaller magnitude steps.
       // FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
       return SE.getAddRecExpr(Start, Step, AR->getLoop(), SCEV::FlagAnyWrap);
     }
     return nullptr;
   }
 
   // Distribute the sdiv over add operands, if the add doesn't overflow.
   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(LHS)) {
     if (IgnoreSignificantBits || isAddSExtable(Add, SE)) {
       SmallVector<const SCEV *, 8> Ops;
if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
     for (const SCEV *S : Add->operands()) {
       const SCEV *Remainder = CollectSubexprs(S, C, Ops, L, SE, Depth+1);
       if (Remainder)
         Ops.push_back(C ? SE.getMulExpr(C, Remainder) : Remainder);
     }
     return nullptr;
   } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
     // Split a non-zero base out of an addrec.
-    if (AR->getStart()->isZero())
+    if (AR->getStart()->isZero() || !AR->isAffine())
       return S;
 
     const SCEV *Remainder = CollectSubexprs(AR->getStart(),
                                             C, Ops, L, SE, Depth+1);
     // Split the non-zero AddRec unless it is part of a nested recurrence that
     // does not pertain to this loop.
     if (Remainder && (AR->getLoop() == L || !isa<SCEVAddRecExpr>(Remainder))) {
       Ops.push_back(C ? SE.getMulExpr(C, Remainder) : Remainder);
       Remainder = nullptr;
     }
     if (Remainder != AR->getStart()) {
       if (!Remainder)
         Remainder = SE.getConstant(AR->getType(), 0);
       return SE.getAddRecExpr(Remainder,
                               AR->getStepRecurrence(SE),
                               AR->getLoop(),
                               //FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
                               SCEV::FlagAnyWrap);
     }
   } else if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {

test/Transforms/LoopStrengthReduce/ARM/addrec-is-loop-invariant.ll

+; RUN: llc -mtriple=armv8-eabi -verify-machineinstrs %s -o /dev/null
+
+; This test ensures that Loop Strength Reduction will
+; not create an Add Reccurence Expression if not all
+; its operands are loop invariants.
+
+define void @add_rec_expr() {
+entry:
+  br label %loop0
+
+loop0:
+  %c.0 = phi i32 [ 0, %entry ], [ %inc.0, %loop0 ]
+  %inc.0 = add nuw i32 %c.0, 1
+  br i1 undef, label %loop0, label %bb1
+
+bb1:
+  %mul.0 = mul i32 %c.0, %c.0
+  %gelptr.0 = getelementptr inbounds i16, i16* undef, i32 %mul.0
+  br label %loop1
+
+loop1:
+  %inc.1 = phi i32 [ %inc.2, %bb4 ], [ 0, %bb1 ]
+  %mul.1 = mul i32 %inc.1, %c.0
+  br label %bb3
+
+bb3:
+  %add.0 = add i32 undef, %mul.1
+  %gelptr.1 = getelementptr inbounds i16, i16* %gelptr.0, i32 %add.0
+  store i16 undef, i16* %gelptr.1, align 2
+  br label %bb4
+
+bb4:
+  %inc.2 = add nuw i32 %inc.1, 1
+  br label %loop1
+}