[LoopVectorizer] Fixed a bug in memory conflict run-time check

[delena]

Summary

The bug is in Low <-> High boundaries calculation. The High boundary should be "last memory access pointer + element size".

(It may be "last memory access pointer + element size -1", since we use "<=" in bounds condition)

[Ayal]

../lib/Analysis/LoopAccessAnalysis.cpp

202

Worth commenting that this is needed when pointers are not naturally aligned (as in your "*(reinterpret_cast<long long*>(op)) = *(reinterpret_cast<const long long*>(src))" case of i8*'s discussed re: D20789), or a pair of pointers point to elements of distinct sizes.

Put differently, we can do w/o adding this size to ScEnd if all pointers point to naturally aligned data of same size (as in number-of-memchecks.ll below).

(It may be "last memory access pointer + element size -1", since we use "<=" in bounds condition)

So, want to subtract 1 from EltSize?

[anemet]

Did you forget to add the test?

../lib/Analysis/LoopAccessAnalysis.cpp

202

or use < instead of <=. I remember wondering about why we were using <=

I would also be good to finally have the full mathematical formula in comment somewhere.

[delena]

In D23176#506572, @anemet wrote:

Did you forget to add the test?

No, I didn't. I fixed the existing lit tests that explore the change. Do you want one more lit test?
The test case that triggered the bug will not be vectorized without the second patch https://reviews.llvm.org/D20789.

[anemet]

In D23176#506707, @delena wrote:

In D23176#506572, @anemet wrote:

Did you forget to add the test?

No, I didn't. I fixed the existing lit tests that explore the change. Do you want one more lit test?
The test case that triggered the bug will not be vectorized without the second patch https://reviews.llvm.org/D20789.

Yes, please. I would certainly like to have the testcase included in the patch that triggers the bug with an explanation why. You should be able to construct a testcase by checking the memcheck part of the output of LAA.

Once the other bug is fixed you can add an additional RUN line for -loop-vectorize and then check the compares directly.

[delena]

1. Added a test that triggers the bug.
2. Added a comment that explains how the bounds are being calculated.
3. Changed condition from ( abs(p1 - p2) >= bound ) to ( abs(p1 - p2) > bound ).

[anemet]

../lib/Analysis/LoopAccessAnalysis.cpp

205

Touched is way too loose, how about EltSizeSCEV or something.

I also like Ayal's idea about the comment talking about mentioning misaligned here.

You also need to change the comment in the LAA.h:

/// Holds the pointer value at the end of the loop.
const SCEV *End;

This should say something about a holding a pointer one past the last byte of the last element accessed.

1888–1898

Can you please include the formula in a comment here?

../test/Analysis/LoopAccessAnalysis/memcheck-off-by-one-error.ll

4

Elaborate more how exactly this was failing before. You could for example explain it in terms of the actual pointer values you were debugging with.

[delena]

Added more explanations to the code according to Adam's remarks.

[Ayal]

../include/llvm/Analysis/LoopAccessAnalysis.h

337–338

Instead of "Holds the pointer value at the beginning of the loop." suggest:

"Holds the smallest byte address accessed by the pointer throughout all iterations of the loop."

340–341

Instead of "Holds the pointer one past the last byte of the last element accessed." suggest:

"Holds the largest byte address accessed by the pointer throughout all iterations of the loop, plus 1."

../lib/Analysis/LoopAccessAnalysis.cpp

163

can add:

"which is clearly the complement of having the intervals disjoint/ordered:
= !((P2.Start >= P1.End) || (P1.Start >= P2.End))"

166

Suggest to rephrase as follows (think of accessing doubles and floats, where the first float overlaps the "2nd half" of the last double):

"The addition of SizeOfElt may be omitted when all accesses share the same element size and are all naturally aligned. In this case '<=' should be used instead of '<'."

196

while we're here fixing comments: "but the we" >> "but we"

1889

"[A|B].End points to the last accessed byte, plus one."

1893

Instead of "Since one of the "bounds" is always true, the conflict happens when the both are true:" suggest:

"At-least one of the "bounds" is always true; conflict happens when the other is too."

[delena]

Added/fixed some comments.

[delena]

May I commit this patch? Thank you.

[delena]

Changed comments in the header file.

[anemet]

I am happy with this now with the comments addressed as long as Ayal also likes it. Thanks for the fix!

../lib/Analysis/LoopAccessAnalysis.cpp

165–167

I am not sure there is value in saying whether it can be omitted. Just say why we need it.

1890–1891

Add it that the code actually checks the inverse of this, i.e. B.Start < A.End && A.Start < B.End.

../include/llvm/Analysis/LoopAccessAnalysis.h

 
 /// \brief Holds information about the memory runtime legality checks to verify
 /// that a group of pointers do not overlap.
 class RuntimePointerChecking {
 public:
   struct PointerInfo {
     /// Holds the pointer value that we need to check.
     TrackingVH<Value> PointerValue;
-    /// Holds the pointer value at the beginning of the loop.
+    /// Holds the smallest byte address accessed by the pointer throughout all
+    /// iterations of the loop.
     const SCEV *Start;
-    /// Holds the pointer value at the end of the loop.
+    /// Holds the largest byte address accessed by the pointer throughout all
+    /// iterations of the loop, plus 1.
     const SCEV *End;
     /// Holds the information if this pointer is used for writing to memory.
     bool IsWritePtr;
     /// Holds the id of the set of pointers that could be dependent because of a
     /// shared underlying object.
     unsigned DependencySetId;
     /// Holds the id of the disjoint alias set to which this pointer belongs.
     unsigned AliasSetId;

../lib/Analysis/LoopAccessAnalysis.cpp

DEBUG(dbgs() << "LAA: Replacing SCEV: " << *OrigSCEV << " by: " << *Expr
                  << "\n");
     return Expr;
   }
 
   // Otherwise, just return the SCEV of the original pointer.
   return OrigSCEV;
 }
 
+/// Calculate Start and End points of memory access.
+/// Let's assume A is the first access and B is a memory access on N-th loop
+/// iteration. Then B is calculated as:  
+///   B = A + Step*N . 
+/// Step value may be positive or negative.
+/// N is a calculated back-edge taken count:
+///     N = (TripCount > 0) ? RoundDown(TripCount -1 , VF) : 0
+/// Start and End points are calculated in the following way:
+/// Start = UMIN(A, B) ; End = UMAX(A, B) + SizeOfElt,
+/// where SizeOfElt is the size of single memory access in bytes.
+///
+/// There is no conflict when the intervals are disjoint:
+/// NoConflict = (P2.Start >= P1.End) || (P1.Start >= P2.End)
+///
+/// The addition of SizeOfElt may be omitted when all accesses are aligned on
+/// size of element boundary. (In this case '<=' should be used instead of '<'.)
 void RuntimePointerChecking::insert(Loop *Lp, Value *Ptr, bool WritePtr,
                                     unsigned DepSetId, unsigned ASId,
                                     const ValueToValueMap &Strides,
                                     PredicatedScalarEvolution &PSE) {
   // Get the stride replaced scev.
   const SCEV *Sc = replaceSymbolicStrideSCEV(PSE, Strides, Ptr);
   ScalarEvolution *SE = PSE.getSE();
 
else {
     const SCEV *Step = AR->getStepRecurrence(*SE);
 
     // For expressions with negative step, the upper bound is ScStart and the
     // lower bound is ScEnd.
     if (const auto *CStep = dyn_cast<SCEVConstant>(Step)) {
       if (CStep->getValue()->isNegative())
         std::swap(ScStart, ScEnd);
     } else {
-      // Fallback case: the step is not constant, but the we can still
+      // Fallback case: the step is not constant, but we can still
       // get the upper and lower bounds of the interval by using min/max
       // expressions.
       ScStart = SE->getUMinExpr(ScStart, ScEnd);
       ScEnd = SE->getUMaxExpr(AR->getStart(), ScEnd);
     }
+    // Add the size of the pointed element to ScEnd.
+    unsigned EltSize =
+      Ptr->getType()->getPointerElementType()->getScalarSizeInBits() / 8;
+    const SCEV *EltSizeSCEV = SE->getConstant(ScEnd->getType(), EltSize);
+    ScEnd = SE->getAddExpr(ScEnd, EltSizeSCEV);
   }
 
   Pointers.emplace_back(Ptr, ScStart, ScEnd, WritePtr, DepSetId, ASId, Sc);
 }
 
 SmallVector<RuntimePointerChecking::PointerCheck, 4>
 RuntimePointerChecking::generateChecks() const {
   SmallVector<PointerCheck, 4> Checks;
for (const auto &Check : ExpandedChecks) {
     Type *PtrArithTy0 = Type::getInt8PtrTy(Ctx, AS0);
     Type *PtrArithTy1 = Type::getInt8PtrTy(Ctx, AS1);
 
     Value *Start0 = ChkBuilder.CreateBitCast(A.Start, PtrArithTy0, "bc");
     Value *Start1 = ChkBuilder.CreateBitCast(B.Start, PtrArithTy1, "bc");
     Value *End0 =   ChkBuilder.CreateBitCast(A.End,   PtrArithTy1, "bc");
     Value *End1 =   ChkBuilder.CreateBitCast(B.End,   PtrArithTy0, "bc");
 
-    Value *Cmp0 = ChkBuilder.CreateICmpULE(Start0, End1, "bound0");
+    // [A|B].Start points to the first accessed byte under base [A|B].
+    // [A|B].End points one byte after the last accessed byte, plus one.
+    // There is no conflict when the intervals are disjoint:
+    // NoConflict = (B.Start >= A.End) || (A.Start >= B.End)
+    //
+    // bound0 = (B.Start < A.End)
+    // bound1 = (A.Start < B.End)
+    //  IsConflict = bound0 & bound1
+    Value *Cmp0 = ChkBuilder.CreateICmpULT(Start0, End1, "bound0");
     FirstInst = getFirstInst(FirstInst, Cmp0, Loc);
-    Value *Cmp1 = ChkBuilder.CreateICmpULE(Start1, End0, "bound1");
+    Value *Cmp1 = ChkBuilder.CreateICmpULT(Start1, End0, "bound1");
     FirstInst = getFirstInst(FirstInst, Cmp1, Loc);
     Value *IsConflict = ChkBuilder.CreateAnd(Cmp0, Cmp1, "found.conflict");
     FirstInst = getFirstInst(FirstInst, IsConflict, Loc);
     if (MemoryRuntimeCheck) {
       IsConflict =
           ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict, "conflict.rdx");
       FirstInst = getFirstInst(FirstInst, IsConflict, Loc);
     }

../test/Analysis/LoopAccessAnalysis/memcheck-off-by-one-error.ll

+; RUN: opt -analyze --loop-accesses %s | FileCheck %s
+
+; This test verifies run-time boundary check of memory accesses.
+; The original loop:
+;   void fastCopy(const char* src, char* op) {
+;     int len = 32;
+;     while (len > 0) {
+;       *(reinterpret_cast<long long*>(op)) = *(reinterpret_cast<const long long*>(src));
+;       src += 8;
+;       op += 8;
+;       len -= 8;
+;     }
+;   }
+; Boundaries calculations before this patch:
+; (Low: %src High: (24 + %src))
+; and the actual distance between two pointers was 31,  (%op - %src = 31)
+; IsConflict = (24 > 31) = false -> execution is directed to the vectorized loop.
+; The loop was vectorized to 4, 32 byte memory access ( <4 x i64> ),
+; store a value at *%op touched memory under *%src.
+
+;CHECK: Printing analysis 'Loop Access Analysis' for function 'fastCopy'
+;CHECK: (Low: %op High: (32 + %op))
+;CHECK: (Low: %src High: (32 + %src))
+
+define void @fastCopy(i8* nocapture readonly %src, i8* nocapture %op) {
+entry:
+  br label %while.body.preheader
+
+while.body.preheader:                             ; preds = %entry
+  br label %while.body
+
+while.body:                                       ; preds = %while.body.preheader, %while.body
+  %len.addr.07 = phi i32 [ %sub, %while.body ], [ 32, %while.body.preheader ]
+  %op.addr.06 = phi i8* [ %add.ptr1, %while.body ], [ %op, %while.body.preheader ]
+  %src.addr.05 = phi i8* [ %add.ptr, %while.body ], [ %src, %while.body.preheader ]
+  %0 = bitcast i8* %src.addr.05 to i64*
+  %1 = load i64, i64* %0, align 8
+  %2 = bitcast i8* %op.addr.06 to i64*
+  store i64 %1, i64* %2, align 8
+  %add.ptr = getelementptr inbounds i8, i8* %src.addr.05, i64 8
+  %add.ptr1 = getelementptr inbounds i8, i8* %op.addr.06, i64 8
+  %sub = add nsw i32 %len.addr.07, -8
+  %cmp = icmp sgt i32 %len.addr.07, 8
+  br i1 %cmp, label %while.body, label %while.end.loopexit
+
+while.end.loopexit:                               ; preds = %while.body
+  br label %while.end
+
+while.end:                                        ; preds = %while.end.loopexit, %entry
+  ret void
+}

../test/Analysis/LoopAccessAnalysis/number-of-memchecks.ll

 ; CHECK-NEXT:   Check 1:
 ; CHECK-NEXT:     Comparing group ({{.*}}[[ZERO]]):
 ; CHECK-NEXT:       %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
 ; CHECK-NEXT:       %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
 ; CHECK-NEXT:     Against group ([[TWO:.+]]):
 ; CHECK-NEXT:       %arrayidxB = getelementptr inbounds i16, i16* %b, i64 %ind
 ; CHECK-NEXT:   Grouped accesses:
 ; CHECK-NEXT:    Group {{.*}}[[ZERO]]:
-; CHECK-NEXT:       (Low: %c High: (78 + %c))
+; CHECK-NEXT:       (Low: %c High: (80 + %c))
 ; CHECK-NEXT:         Member: {(2 + %c)<nsw>,+,4}
 ; CHECK-NEXT:         Member: {%c,+,4}
 ; CHECK-NEXT:     Group {{.*}}[[ONE]]:
-; CHECK-NEXT:       (Low: %a High: (40 + %a))
+; CHECK-NEXT:       (Low: %a High: (42 + %a))
 ; CHECK-NEXT:         Member: {(2 + %a)<nsw>,+,2}
 ; CHECK-NEXT:         Member: {%a,+,2}
 ; CHECK-NEXT:     Group {{.*}}[[TWO]]:
-; CHECK-NEXT:       (Low: %b High: (38 + %b))
+; CHECK-NEXT:       (Low: %b High: (40 + %b))
 ; CHECK-NEXT:         Member: {%b,+,2}
 
 define void @testg(i16* %a,
                i16* %b,
                i16* %c) {
 entry:
   br label %for.body
 

 ; CHECK-NEXT:   Check 1:
 ; CHECK-NEXT:     Comparing group ({{.*}}[[ZERO]]):
 ; CHECK-NEXT:         %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
 ; CHECK-NEXT:         %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
 ; CHECK-NEXT:     Against group ([[TWO:.+]]):
 ; CHECK-NEXT:         %arrayidxB = getelementptr i16, i16* %b, i64 %ind
 ; CHECK-NEXT:   Grouped accesses:
 ; CHECK-NEXT:     Group {{.*}}[[ZERO]]:
-; CHECK-NEXT:       (Low: %c High: (78 + %c))
+; CHECK-NEXT:       (Low: %c High: (80 + %c))
 ; CHECK-NEXT:         Member: {(2 + %c)<nsw>,+,4}
 ; CHECK-NEXT:         Member: {%c,+,4}
 ; CHECK-NEXT:     Group {{.*}}[[ONE]]:
-; CHECK-NEXT:       (Low: %a High: (40 + %a))
+; CHECK-NEXT:       (Low: %a High: (42 + %a))
 ; CHECK-NEXT:         Member: {(2 + %a),+,2}
 ; CHECK-NEXT:         Member: {%a,+,2}
 ; CHECK-NEXT:     Group {{.*}}[[TWO]]:
-; CHECK-NEXT:       (Low: %b High: (38 + %b))
+; CHECK-NEXT:       (Low: %b High: (40 + %b))
 ; CHECK-NEXT:         Member: {%b,+,2}
 
 define void @testh(i16* %a,
                i16* %b,
                i16* %c) {
 entry:
   br label %for.body
 

 ; CHECK-NEXT:       %arrayidxA1 = getelementptr i16, i16* %a, i64 %ind
 ; CHECK-NEXT:   Check 1:
 ; CHECK-NEXT:     Comparing group ({{.*}}[[ZERO]]):
 ; CHECK-NEXT:       %storeidx = getelementptr inbounds i16, i16* %a, i64 %store_ind
 ; CHECK-NEXT:     Against group ([[TWO:.+]]):
 ; CHECK-NEXT:       %arrayidxA2 = getelementptr i16, i16* %a, i64 %ind2
 ; CHECK-NEXT:   Grouped accesses:
 ; CHECK-NEXT:     Group {{.*}}[[ZERO]]:
-; CHECK-NEXT:       (Low: ((2 * %offset) + %a)<nsw> High: (9998 + (2 * %offset) + %a))
+; CHECK-NEXT:       (Low: ((2 * %offset) + %a)<nsw> High: (10000 + (2 * %offset) + %a))
 ; CHECK-NEXT:         Member: {((2 * %offset) + %a)<nsw>,+,2}<nsw><%for.body>
 ; CHECK-NEXT:     Group {{.*}}[[ONE]]:
-; CHECK-NEXT:       (Low: %a High: (9998 + %a))
+; CHECK-NEXT:       (Low: %a High: (10000 + %a))
 ; CHECK-NEXT:         Member: {%a,+,2}<%for.body>
 ; CHECK-NEXT:     Group {{.*}}[[TWO]]:
-; CHECK-NEXT:       (Low: (20000 + %a) High: (29998 + %a))
+; CHECK-NEXT:       (Low: (20000 + %a) High: (30000 + %a))
 ; CHECK-NEXT:         Member: {(20000 + %a),+,2}<%for.body>
 
 define void @testi(i16* %a,
                    i64 %offset) {
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry

../test/Analysis/LoopAccessAnalysis/reverse-memcheck-bounds.ll

 ;   for (i = 0; i < 10000; i++) {
 ;     B[i] = A[15000 - i] * 3;
 ;   }
 
 target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64--linux-gnueabi"
 
 ; CHECK: function 'f':
-; CHECK: (Low: (20000 + %a) High: (60000 + %a)<nsw>)
+; CHECK: (Low: (20000 + %a) High: (60004 + %a))
 
 @B = common global i32* null, align 8
 @A = common global i32* null, align 8
 
 define void @f() {
 entry:
   %a = load i32*, i32** @A, align 8
   %b = load i32*, i32** @B, align 8

 
 ;   for (i = 0; i < 10000; i++) {
 ;     B[i] = A[15000 - step * i] * 3;
 ;   }
 
 ; Here it is not obvious what the limits are, since 'step' could be negative.
 
 ; CHECK: Low: (-1 + (-1 * ((-60001 + (-1 * %a)) umax (-60001 + (40000 * %step) + (-1 * %a)))))
-; CHECK: High: ((60000 + %a)<nsw> umax (60000 + (-40000 * %step) + %a))
+; CHECK: High: (4 + ((60000 + %a)<nsw> umax (60000 + (-40000 * %step) + %a)))
 
 define void @g(i64 %step) {
 entry:
   %a = load i32*, i32** @A, align 8
   %b = load i32*, i32** @B, align 8
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry

../test/Transforms/LoopVectorize/runtime-check-readonly.ll

 ; RUN: opt < %s  -loop-vectorize -force-vector-interleave=1 -force-vector-width=4 -dce -instcombine -S | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.8.0"
 
 ;CHECK-LABEL: @add_ints(
 ;CHECK: br
 ;CHECK: br
 ;CHECK: getelementptr
 ;CHECK-DAG: getelementptr
-;CHECK-DAG: icmp uge
-;CHECK-DAG: icmp uge
-;CHECK-DAG: icmp uge
-;CHECK-DAG: icmp uge
+;CHECK-DAG: icmp ugt
+;CHECK-DAG: icmp ugt
+;CHECK-DAG: icmp ugt
+;CHECK-DAG: icmp ugt
 ;CHECK-DAG: and
 ;CHECK-DAG: and
 ;CHECK: br
 ;CHECK: ret
 define void @add_ints(i32* nocapture %A, i32* nocapture %B, i32* nocapture %C) {
 entry:
   br label %for.body
 

../test/Transforms/LoopVectorize/tbaa-nodep.ll

 ; CHECK: vector.body:
 
 ; CHECK: load <4 x float>, <4 x float>* %{{.*}}, align 4, !tbaa
 ; CHECK: store <4 x i32> %{{.*}}, <4 x i32>* %{{.*}}, align 4, !tbaa
 
 ; CHECK: ret i32 0
 
 ; CHECK-NOTBAA-LABEL: @test1
-; CHECK-NOTBAA: icmp uge i32*
+; CHECK-NOTBAA: icmp ugt i32*
 
 ; CHECK-NOTBAA: load <4 x float>, <4 x float>* %{{.*}}, align 4, !tbaa
 ; CHECK-NOTBAA: store <4 x i32> %{{.*}}, <4 x i32>* %{{.*}}, align 4, !tbaa
 
 ; CHECK-NOTBAA: ret i32 0
 }
 
 ; Function Attrs: nounwind uwtable

 
 for.end:                                          ; preds = %for.body
   ret i32 0
 
 ; This test is like the first, except here there is still one runtime check
 ; required. Without TBAA, however, two checks are required.
 
 ; CHECK-LABEL: @test2
-; CHECK: icmp uge float*
-; CHECK: icmp uge float*
+; CHECK: icmp ugt float*
+; CHECK: icmp ugt float*
 ; CHECK-NOT: icmp uge i32*
 
 ; CHECK: load <4 x float>, <4 x float>* %{{.*}}, align 4, !tbaa
 ; CHECK: store <4 x float> %{{.*}}, <4 x float>* %{{.*}}, align 4, !tbaa
 
 ; CHECK: ret i32 0
 
 ; CHECK-NOTBAA-LABEL: @test2
-; CHECK-NOTBAA: icmp uge float*
-; CHECK-NOTBAA: icmp uge float*
-; CHECK-NOTBAA-DAG: icmp uge float*
-; CHECK-NOTBAA-DAG: icmp uge i32*
+; CHECK-NOTBAA: icmp ugt float*
+; CHECK-NOTBAA: icmp ugt float*
+; CHECK-NOTBAA-DAG: icmp ugt float*
+; CHECK-NOTBAA-DAG: icmp ugt i32*
 
 ; CHECK-NOTBAA: load <4 x float>, <4 x float>* %{{.*}}, align 4, !tbaa
 ; CHECK-NOTBAA: store <4 x float> %{{.*}}, <4 x float>* %{{.*}}, align 4, !tbaa
 
 ; CHECK-NOTBAA: ret i32 0
 }
 
 attributes #0 = { nounwind uwtable }
 
 !0 = !{!1, !1, i64 0}
 !1 = !{!"float", !2, i64 0}
 !2 = !{!"omnipotent char", !3, i64 0}
 !3 = !{!"Simple C/C++ TBAA"}
 !4 = !{!5, !5, i64 0}
 !5 = !{!"int", !2, i64 0}
 

../test/Transforms/LoopVersioningLICM/loopversioningLICM1.ll

 ; RUN: opt < %s  -O1  -S -loop-versioning-licm -licm -debug-only=loop-versioning-licm 2>&1 | FileCheck %s
 ; REQUIRES: asserts
 ;
 ; Test to confirm loop is a candidate for LoopVersioningLICM.
 ; It also confirms invariant moved out of loop.
 ;
 ; CHECK: Loop: Loop at depth 2 containing: %for.body3<header><latch><exiting>
 ; CHECK-NEXT:   Loop Versioning found to be beneficial
 ;
 ; CHECK: for.body3:
-; CHECK-NEXT: %add86 = phi i32 [ %arrayidx7.promoted, %for.body3.ph ], [ %add8, %for.body3 ]
+; CHECK-NEXT: %[[induction:.*]] = phi i32 [ %arrayidx7.promoted, %for.body3.ph ], [ %add8, %for.body3 ]
 ; CHECK-NEXT: %j.113 = phi i32 [ %j.016, %for.body3.ph ], [ %inc, %for.body3 ]
 ; CHECK-NEXT: %idxprom = zext i32 %j.113 to i64
 ; CHECK-NEXT: %arrayidx = getelementptr inbounds i32, i32* %var1, i64 %idxprom
 ; CHECK-NEXT: store i32 %add, i32* %arrayidx, align 4, !alias.scope !6, !noalias !6
-; CHECK-NEXT: %add8 = add nsw i32 %add86, %add
+; CHECK-NEXT: %add8 = add nsw i32 %[[induction]], %add
 ; CHECK-NEXT: %inc = add nuw i32 %j.113, 1
 ; CHECK-NEXT: %cmp2 = icmp ult i32 %inc, %itr
-; CHECK-NEXT: br i1 %cmp2, label %for.body3, label %for.inc11.loopexit.loopexit5, !llvm.loop !7
+; CHECK-NEXT: br i1 %cmp2, label %for.body3, label %for.{{.*}}.loopexit
 define i32 @foo(i32* nocapture %var1, i32* nocapture readnone %var2, i32* nocapture %var3, i32 %itr) #0 {
 entry:
   %cmp14 = icmp eq i32 %itr, 0
   br i1 %cmp14, label %for.end13, label %for.cond1.preheader.preheader
 
 for.cond1.preheader.preheader:                    ; preds = %entry
   br label %for.cond1.preheader