[SCEV] Fix for PR31847: Assertion failed: (isLoopInvariant(Operands[i], L) && "SCEVAddRecExpr operand is not loop-invariant!")

[ABataev]

Summary

Sometimes during folding loop invariants the resulting add recurrence may become non-invariant. This may lead to crash during next folding of recurrences expected to be invariants, which are not.

[sanjoy]

Hi Alexey,

I did not understand the premise of this change -- how can the sum of two loop invariant values be a loop varying value? Can you give a specific isolated example? Or did I not misunderstand?

[ABataev]

In D29585#668537, @sanjoy wrote:

Hi Alexey,

I did not understand the premise of this change -- how can the sum of two loop invariant values be a loop varying value? Can you give a specific isolated example? Or did I not misunderstand?

Hi Sanjoy, there is something has changed in LLVM and I can't reproduce the bug anymore. So I'm abandoning it

lib/Analysis/ScalarEvolution.cpp

for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
     // added together.  If so, we can fold them.
     for (unsigned OtherIdx = Idx+1;
          OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
          ++OtherIdx)
       if (AddRecLoop == cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()) {
         // Other + {A,+,B}<L> + {C,+,D}<L>  -->  Other + {A+C,+,B+D}<L>
         SmallVector<const SCEV *, 4> AddRecOps(AddRec->op_begin(),
                                                AddRec->op_end());
+        bool AllLoopInvariants = true;
         for (; OtherIdx != Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
              ++OtherIdx)
           if (const auto *OtherAddRec = dyn_cast<SCEVAddRecExpr>(Ops[OtherIdx]))
             if (OtherAddRec->getLoop() == AddRecLoop) {
               for (unsigned i = 0, e = OtherAddRec->getNumOperands();
                    i != e; ++i) {
                 if (i >= AddRecOps.size()) {
                   AddRecOps.append(OtherAddRec->op_begin()+i,
                                    OtherAddRec->op_end());
                   break;
                 }
                 AddRecOps[i] = getAddExpr(AddRecOps[i],
                                           OtherAddRec->getOperand(i));
+                if (AllLoopInvariants)
+                  AllLoopInvariants = isLoopInvariant(AddRecOps[i], AddRecLoop);
               }
               Ops.erase(Ops.begin() + OtherIdx); --OtherIdx;
             }
         // Step size has changed, so we cannot guarantee no self-wraparound.
-        Ops[Idx] = getAddRecExpr(AddRecOps, AddRecLoop, SCEV::FlagAnyWrap);
+        Ops[Idx] = AllLoopInvariants
+                       ? getAddRecExpr(AddRecOps, AddRecLoop, SCEV::FlagAnyWrap)
+                       : getAddExpr(AddRecOps);
         return getAddExpr(Ops);
       }
 
     // Otherwise couldn't fold anything into this recurrence.  Move onto the
     // next one.
   }
 
   // Okay, it looks like we really DO need an add expr.  Check to see if we

test/Transforms/SLPVectorizer/X86/vectorize-crash-geps-with-scev.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -mtriple=i386 -mcpu=haswell -slp-vectorizer -slp-vectorize-hor -slp-vectorize-hor-store -S < %s | FileCheck %s
+
+%struct.WaveformContext = type { i32, [0 x i32] }
+
+@b = common local_unnamed_addr global i32 0, align 4
+@d = common local_unnamed_addr global %struct.WaveformContext zeroinitializer, align 4
+@g = common local_unnamed_addr global i32 0, align 4
+@e = common local_unnamed_addr global i32 0, align 4
+@h = common local_unnamed_addr global i8* null, align 4
+@c = common local_unnamed_addr global i32* null, align 4
+@a = common local_unnamed_addr global i32 0, align 4
+@f = common local_unnamed_addr global i32 0, align 4
+
+; Fix for PR31847: Assertion failed: (isLoopInvariant(Operands[i], L) && "SCEVAddRecExpr operand is not loop-invariant!")
+define i32 @fn1() local_unnamed_addr {
+; CHECK-LABEL: @fn1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[DOTPRE:%.*]] = load i8*, i8** @h, align 4
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i8* [ [[ADD_PTR46:%.*]], [[FOR_COND]] ], [ [[DOTPRE]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* @b, align 4
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* @g, align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* @e, align 4
+; CHECK-NEXT:    [[REM:%.*]] = srem i32 1, [[TMP3]]
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[REM]], [[TMP2]]
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* getelementptr inbounds (%struct.WaveformContext, %struct.WaveformContext* @d, i32 1, i32 0), i32 [[ADD]]
+; CHECK-NEXT:    [[TMP4:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[SHR:%.*]] = ashr i32 [[TMP1]], [[TMP4]]
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i8, i8* inttoptr (i32 1 to i8*), i32 [[SHR]]
+; CHECK-NEXT:    [[TMP5:%.*]] = load i8, i8* [[ARRAYIDX1]], align 1
+; CHECK-NEXT:    [[REM17:%.*]] = srem i32 2, [[TMP3]]
+; CHECK-NEXT:    [[ADD18:%.*]] = add nsw i32 [[REM17]], [[TMP2]]
+; CHECK-NEXT:    [[ARRAYIDX19:%.*]] = getelementptr inbounds i32, i32* getelementptr inbounds (%struct.WaveformContext, %struct.WaveformContext* @d, i32 1, i32 0), i32 [[ADD18]]
+; CHECK-NEXT:    [[TMP6:%.*]] = load i32, i32* [[ARRAYIDX19]], align 4
+; CHECK-NEXT:    [[SHR20:%.*]] = ashr i32 [[TMP1]], [[TMP6]]
+; CHECK-NEXT:    [[ARRAYIDX21:%.*]] = getelementptr inbounds i8, i8* inttoptr (i32 1 to i8*), i32 [[SHR20]]
+; CHECK-NEXT:    [[TMP7:%.*]] = load i8, i8* [[ARRAYIDX21]], align 1
+; CHECK-NEXT:    [[TMP8:%.*]] = insertelement <2 x i8> undef, i8 [[TMP7]], i32 0
+; CHECK-NEXT:    [[TMP9:%.*]] = insertelement <2 x i8> [[TMP8]], i8 [[TMP5]], i32 1
+; CHECK-NEXT:    [[TMP10:%.*]] = zext <2 x i8> [[TMP9]] to <2 x i32>
+; CHECK-NEXT:    [[TMP11:%.*]] = add nsw <2 x i32> <i32 -128, i32 -128>, [[TMP10]]
+; CHECK-NEXT:    [[TMP12:%.*]] = icmp sgt <2 x i32> [[TMP11]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[TMP13:%.*]] = sub nsw <2 x i32> zeroinitializer, [[TMP10]]
+; CHECK-NEXT:    [[TMP14:%.*]] = select <2 x i1> [[TMP12]], <2 x i32> [[TMP11]], <2 x i32> [[TMP13]]
+; CHECK-NEXT:    [[TMP15:%.*]] = extractelement <2 x i32> [[TMP14]], i32 0
+; CHECK-NEXT:    [[TMP16:%.*]] = extractelement <2 x i32> [[TMP14]], i32 1
+; CHECK-NEXT:    [[ADD44:%.*]] = add nsw i32 [[TMP15]], [[TMP16]]
+; CHECK-NEXT:    [[IDX_NEG:%.*]] = sub nsw i32 0, [[ADD44]]
+; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds i8, i8* [[TMP0]], i32 [[IDX_NEG]]
+; CHECK-NEXT:    [[TMP17:%.*]] = bitcast i8* [[ADD_PTR]] to i32*
+; CHECK-NEXT:    store i32 0, i32* [[TMP17]], align 4
+; CHECK-NEXT:    [[ADD_PTR45:%.*]] = getelementptr inbounds i8, i8* [[TMP0]], i32 [[ADD44]]
+; CHECK-NEXT:    [[TMP18:%.*]] = bitcast i8* [[ADD_PTR45]] to i32*
+; CHECK-NEXT:    store i8* [[ADD_PTR45]], i8** bitcast (i32** @c to i8**), align 4
+; CHECK-NEXT:    [[NOT_TOBOOL:%.*]] = icmp eq i8* [[ADD_PTR45]], null
+; CHECK-NEXT:    [[DOTSINK:%.*]] = zext i1 [[NOT_TOBOOL]] to i32
+; CHECK-NEXT:    store i32 [[DOTSINK]], i32* [[TMP18]], align 4
+; CHECK-NEXT:    [[ADD_PTR46]] = getelementptr inbounds i8, i8* [[TMP0]], i32 1
+; CHECK-NEXT:    store i8* [[ADD_PTR46]], i8** @h, align 4
+; CHECK-NEXT:    br label [[FOR_COND]]
+;
+entry:
+  %.pre = load i8*, i8** @h, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.cond, %entry
+  %0 = phi i8* [ %add.ptr46, %for.cond ], [ %.pre, %entry ]
+  %1 = load i32, i32* @b, align 4
+  %2 = load i32, i32* @g, align 4
+  %3 = load i32, i32* @e, align 4
+  %rem = srem i32 1, %3
+  %add = add nsw i32 %rem, %2
+  %arrayidx = getelementptr inbounds i32, i32* getelementptr inbounds (%struct.WaveformContext, %struct.WaveformContext* @d, i32 1, i32 0), i32 %add
+  %4 = load i32, i32* %arrayidx, align 4
+  %shr = ashr i32 %1, %4
+  %arrayidx1 = getelementptr inbounds i8, i8* inttoptr (i32 1 to i8*), i32 %shr
+  %5 = load i8, i8* %arrayidx1, align 1
+  %conv = zext i8 %5 to i32
+  %sub = add nsw i32 %conv, -128
+  %cmp = icmp sgt i32 %sub, -1
+  %sub16 = sub nsw i32 0, %conv
+  %cond = select i1 %cmp, i32 %sub, i32 %sub16
+  %rem17 = srem i32 2, %3
+  %add18 = add nsw i32 %rem17, %2
+  %arrayidx19 = getelementptr inbounds i32, i32* getelementptr inbounds (%struct.WaveformContext, %struct.WaveformContext* @d, i32 1, i32 0), i32 %add18
+  %6 = load i32, i32* %arrayidx19, align 4
+  %shr20 = ashr i32 %1, %6
+  %arrayidx21 = getelementptr inbounds i8, i8* inttoptr (i32 1 to i8*), i32 %shr20
+  %7 = load i8, i8* %arrayidx21, align 1
+  %conv22 = zext i8 %7 to i32
+  %sub23 = add nsw i32 %conv22, -128
+  %cmp24 = icmp sgt i32 %sub23, -1
+  %sub41 = sub nsw i32 0, %conv22
+  %cond43 = select i1 %cmp24, i32 %sub23, i32 %sub41
+  %add44 = add nsw i32 %cond43, %cond
+  %idx.neg = sub nsw i32 0, %add44
+  %add.ptr = getelementptr inbounds i8, i8* %0, i32 %idx.neg
+  %8 = bitcast i8* %add.ptr to i32*
+  store i32 0, i32* %8, align 4
+  %add.ptr45 = getelementptr inbounds i8, i8* %0, i32 %add44
+  %9 = bitcast i8* %add.ptr45 to i32*
+  store i8* %add.ptr45, i8** bitcast (i32** @c to i8**), align 4
+  %not.tobool = icmp eq i8* %add.ptr45, null
+  %.sink = zext i1 %not.tobool to i32
+  store i32 %.sink, i32* %9, align 4
+  %add.ptr46 = getelementptr inbounds i8, i8* %0, i32 1
+  store i8* %add.ptr46, i8** @h, align 4
+  br label %for.cond
+}
+