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

582

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

3208

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

582

(Ignore my previous comment here.)

3208

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

3206

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()) {

?

3195

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.

3195

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

 
   // 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),

       // 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);
+      if (AR->isAffine())
+        return SE.getAddRecExpr(Start, Step, AR->getLoop(), SCEV::FlagAnyWrap);
     }
     return nullptr;
   }

       Ops.push_back(C ? SE.getMulExpr(C, Remainder) : Remainder);
       Remainder = nullptr;
     }
-    if (Remainder != AR->getStart()) {
+    if (Remainder != AR->getStart() && AR->isAffine()) {
       if (!Remainder)
         Remainder = SE.getConstant(AR->getType(), 0);
       return SE.getAddRecExpr(Remainder,

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

+; RUN: llc -mtriple=armv8-eabi -verify-machineinstrs %s -o /dev/null
+
+; This test checks that when the IR is not under LCSSA form,
+; 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
+}