[SLP] Use SCEV to sort memory accesses

[mkuper]

Summary

This generalizes memory access sorting to use SCEVs instead of relying on constant offsets.

I'm not entirely sure my use of SCEV here is sane, both in terms of using the cache (if it's ok to rely on the cache, I can get rid of the map and simplify the whole thing), and in terms of expecting "SCEV.getMinusSCEV(X,Y) returns a constant" to be transitive. @sanjoy , I'll really appreciate feedback on both.

[mkuper]

Now, with correct test.

[ABataev]

lib/Analysis/LoopAccessAnalysis.cpp

1064 ↗

(On Diff #86717)

You can make OffValPairs.reserve(VL.size()) and Sorted.reserve(VL.size()) to avoid possible resize

1083 ↗

(On Diff #86717)

Better to use OffValPairs.emplace_back(SE.getSCEV(Ptr), Val);

[mssimpso]

lib/Analysis/LoopAccessAnalysis.cpp

1093–1095 ↗

(On Diff #86717)

Do we require constant differences? If not, you could also ask SCEV about the range:

return SE.isKnownPositive(SE.getMinusSCEV(Right.first, Left.first))

[efriedma]

lib/Analysis/LoopAccessAnalysis.cpp

1071 ↗

(On Diff #86717)

The SCEV cache is reasonably fast, but it's obviously faster not to do a hashtable lookup at all.

1095 ↗

(On Diff #86717)

std::sort requires your comparator to produce a strict weak ordering; otherwise, it has undefined behavior.

[mkuper]

Thanks for the comments!

lib/Analysis/LoopAccessAnalysis.cpp

1064 ↗

(On Diff #86717)

Right, thanks.

1071 ↗

(On Diff #86717)

I know, but using the cache would simplify the code even more, so I wonder if the penalty for a cache lookup is worth it. I mean, a SCEV cache lookup is basically a hash lookup, right?

1083 ↗

(On Diff #86717)

Sure.

1093–1095 ↗

(On Diff #86717)

@mssimpso : right, I think this should work, thanks! I was stuck thinking about constants because if the differences are non-constant we won't be able to do anything with the sorted array anyway. But this is nicer assuming I can actually use it as a comparator (see answer to Eli).

@efriedma : I know. That's why I've wanted sanjoy to comment on whether we can rely on SCEV to give transitive results. I mean, this comparator is obviously irreflexive, and I'm rather sure it's antisymmetric. So it comes down to whether we can rely on isKnownPositive(getMinus(A,B)) and isKnownPositive(getMinus(B,C)) implying that isKnownPositive(getMinus(A,C)) (or the equivalent for the version I have now).
If not, then I see two options:
(a) roll my own sort that bails if two values are incomparable.
(b) do something like: take one of the pointers, compute the difference vs. all the others, if one of the differences is non-constant bail, otherwise compare based on the diffs.

I guess (b) would be the simplest and safest option.

[efriedma]

lib/Analysis/LoopAccessAnalysis.cpp

1093–1095 ↗

(On Diff #86717)

I don't think we can rely on SCEV being transitive? At least, I wouldn't want to rely on it, then crash in some obscure case.

Anyway, your comparator has worse problems: currently, you can prove 0 == A == 1 with it.

[mkuper]

lib/Analysis/LoopAccessAnalysis.cpp

1093–1095 ↗

(On Diff #86717)

I don't think we can rely on SCEV being transitive? At least, I wouldn't want to rely on it, then crash in some obscure case.

That worries me too, that's why I wanted a stamp of approval/disapproval from sanjoy :-)
Maybe I'll just go with (b) and avoid this can of worms.

Anyway, your comparator has worse problems: currently, you can prove 0 == A == 1 with it.

I don't see why. I mean, for {0, 1, A} the strict weak order is "0 < 1, A is incomparable with both 0 and 1". The only comparison that evaluates to true is cmp(0,1), and this should be fine.

[mkuper]

lib/Analysis/LoopAccessAnalysis.cpp

1093–1095 ↗

(On Diff #86717)

Er, wait, you're right, that's not strict. But I think it still satisfies the explicit requirements for a comparator.

[efriedma]

lib/Analysis/LoopAccessAnalysis.cpp

1093–1095 ↗

(On Diff #86717)

C++ [alg.sorting]p3; "For algorithms [...] to work correctly, comp has to induce a strict weak ordering on the values."

[mkuper]

lib/Analysis/LoopAccessAnalysis.cpp

1093–1095 ↗

(On Diff #86717)

Ok, so "strict" has two possible meanings. One is irreflexivity (which holds for this order), the other is transitivity of incomparability (which doesn't).
The standard uses it to mean the first one: [alg.sorting]p4: "The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x),"
So I think, if transitivity holds, this is fine.

Anyway, it's a moot point, I'm going to change this not rely on SCEV transitivity.

[mkuper]

Updated not to rely on SCEV transitivity.
Also addressed other comments, except for the suggestion to use SE.isKnownPositive(), which won't work with this comparator.

[mssimpso]

lib/Analysis/LoopAccessAnalysis.cpp

1081 ↗

(On Diff #86902)

Hi Michael,

I must have missed this the first time around, but this looks a little confusing to me. If the accesses aren't sortable, why are we adding them to Sorted? I would think the caller would need some signal that sorting was unsuccessful - either an empty Sorted or a returned bool. Am I missing something obvious?

[mkuper]

lib/Analysis/LoopAccessAnalysis.cpp

1081 ↗

(On Diff #86902)

No, you're not missing anything.

It's just that the API currently doesn't allow for the possibility of failure, so the callers blindly use the "sorted" array. This made sense for the previous version because it did not explicitly fail (it would just produce a meaningless order in cases where things weren't really sortable), and I didn't notice this when reviewing the original patch.
I was planning to fix the API up in a follow-up patch, but if you want to see it in the review, I can update it with that.

[mssimpso]

lib/Analysis/LoopAccessAnalysis.cpp

1081 ↗

(On Diff #86902)

A follow-on is perfectly fine - I just wanted to make sure I wasn't confusing myself. Thanks for the clarification!

[mssimpso]

I had a comment for the test case, otherwise this looks good to me.

test/Transforms/SLPVectorizer/X86/jumbled-load.ll

8 ↗

(On Diff #86902)

It looks like the changes in this test are unrelated to the patch. Probably left-overs from the update script?

[mkuper]

test/Transforms/SLPVectorizer/X86/jumbled-load.ll

8 ↗

(On Diff #86902)

Yes, it looks like the update script decided to pattern-match the first uses of function arguments instead of matching their names. :-S

[sanjoy]

Going back a couple of diffs, I don't think SCEV can guarantee beyond "best effort" that f(A, B) = isKnownPositive(getMinus(A, B)) (or the variant of this that you had) is transitive. This is because there are places where SCEV gives up on canonicalization after a certain cutoff point (e.g. around large (x + y) * (a + b + c) like cases) and so it is possible that while both B - A and C - B simplify to a constant, C - A does not (PR25170 is a more extreme version of this issue, for instance).

However, what you have now looks fine to me.

include/llvm/Analysis/LoopAccessAnalysis.h

696 ↗

(On Diff #86902)

I don't know general LAA conventions, but this contract seem weird -- why not return an error.

[edit: I noticed you've already answered this]

lib/Analysis/LoopAccessAnalysis.cpp

1096 ↗

(On Diff #86902)

Do you need the std::make_pair? Can't you do emplace_back(Diff->getAPInt().getSExtValue(), Val)?

[mkuper]

Thanks!

lib/Analysis/LoopAccessAnalysis.cpp

1096 ↗

(On Diff #86902)

Ugh, right, thanks!

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

 /// If necessary this method will version the stride of the pointer according
 /// to \p PtrToStride and therefore add further predicates to \p PSE.
 /// The \p Assume parameter indicates if we are allowed to make additional
 /// run-time assumptions.
 int64_t getPtrStride(PredicatedScalarEvolution &PSE, Value *Ptr, const Loop *Lp,
                      const ValueToValueMap &StridesMap = ValueToValueMap(),
                      bool Assume = false, bool ShouldCheckWrap = true);
 
-/// \brief Saves the sorted memory accesses in vector argument 'Sorted' after
-/// sorting the jumbled memory accesses.
+/// \brief Try to sort an array of loads / stores.
+///
+/// If all pointers refer to the same object, and the differences between all
+/// pointer operands are known to be constant, the array is sorted by offset,
+/// and returned in \p Sorted.
+/// 
+/// If those conditions do not hold, the output array is an arbitrary
+/// permutation of the input.
 void sortMemAccesses(ArrayRef<Value *> VL, const DataLayout &DL,
                      ScalarEvolution &SE, SmallVectorImpl<Value *> &Sorted);
 
 /// \brief Returns true if the memory operations \p A and \p B are consecutive.
 /// This is a simple API that does not depend on the analysis pass. 
 bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
                          ScalarEvolution &SE, bool CheckType = true);
 

llvm/trunk/lib/Analysis/LoopAccessAnalysis.cpp

 static unsigned getAddressSpaceOperand(Value *I) {
   if (LoadInst *L = dyn_cast<LoadInst>(I))
     return L->getPointerAddressSpace();
   if (StoreInst *S = dyn_cast<StoreInst>(I))
     return S->getPointerAddressSpace();
   return -1;
 }
 
-/// Saves the memory accesses after sorting it into vector argument 'Sorted'.
 void llvm::sortMemAccesses(ArrayRef<Value *> VL, const DataLayout &DL,
                          ScalarEvolution &SE,
                          SmallVectorImpl<Value *> &Sorted) {
-  SmallVector<std::pair<int, Value *>, 4> OffValPairs;
+  SmallVector<std::pair<int64_t, Value *>, 4> OffValPairs;
+  OffValPairs.reserve(VL.size());
+  Sorted.reserve(VL.size());
+
+  // Walk over the pointers, and map each of them to an offset relative to
+  // first pointer in the array.
+  Value *Ptr0 = getPointerOperand(VL[0]);
+  const SCEV *Scev0 = SE.getSCEV(Ptr0);
+  Value *Obj0 = GetUnderlyingObject(Ptr0, DL);
+
   for (auto *Val : VL) {
-    // Compute the constant offset from the base pointer of each memory accesses
-    // and insert into the vector of key,value pair which needs to be sorted.
     Value *Ptr = getPointerOperand(Val);
-    unsigned AS = getAddressSpaceOperand(Val);
-    unsigned PtrBitWidth = DL.getPointerSizeInBits(AS);
-    Type *Ty = cast<PointerType>(Ptr->getType())->getElementType();
-    APInt Size(PtrBitWidth, DL.getTypeStoreSize(Ty));
 
-    // FIXME: Currently the offsets are assumed to be constant.However this not
-    // always true as offsets can be variables also and we would need to
-    // consider the difference of the variable offsets.
-    APInt Offset(PtrBitWidth, 0);
-    Ptr->stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
-    OffValPairs.push_back(std::make_pair(Offset.getSExtValue(), Val));
+    // If a pointer refers to a different underlying object, bail - the
+    // pointers are by definition incomparable.
+    Value *CurrObj = GetUnderlyingObject(Ptr, DL);
+    if (CurrObj != Obj0) {
+      Sorted.append(VL.begin(), VL.end());
+      return;
+    }
+
+    const SCEVConstant *Diff =
+        dyn_cast<SCEVConstant>(SE.getMinusSCEV(SE.getSCEV(Ptr), Scev0));
+
+    // The pointers may not have a constant offset from each other, or SCEV
+    // may just not be smart enough to figure out they do. Regardless,
+    // there's nothing we can do.
+    if (!Diff) {
+      Sorted.append(VL.begin(), VL.end());
+      return;
     }
+
+    OffValPairs.emplace_back(Diff->getAPInt().getSExtValue(), Val);
+  }
+
   std::sort(OffValPairs.begin(), OffValPairs.end(),
-            [](const std::pair<int, Value *> &Left,
-               const std::pair<int, Value *> &Right) {
+            [](const std::pair<int64_t, Value *> &Left,
+               const std::pair<int64_t, Value *> &Right) {
               return Left.first < Right.first;
             });
 
   for (auto& it : OffValPairs)
     Sorted.push_back(it.second);
 }
 
 /// Returns true if the memory operations \p A and \p B are consecutive.

llvm/trunk/test/Transforms/SLPVectorizer/X86/jumbled-load.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -S -mtriple=x86_64-unknown -mattr=+avx -slp-threshold=-10 -slp-vectorizer | FileCheck %s
 
-
+@total = common global i32 0, align 4
 
 define i32 @jumbled-load(i32* noalias nocapture %in, i32* noalias nocapture %inn, i32* noalias nocapture %out) {
 ; CHECK-LABEL: @jumbled-load(
-; CHECK-NEXT:    [[IN_ADDR:%.*]] = getelementptr inbounds i32, i32* %in, i64 0
+; CHECK-NEXT:    [[IN_ADDR:%.*]] = getelementptr inbounds i32, i32* [[IN:%.*]], i64 0
 ; CHECK-NEXT:    [[GEP_1:%.*]] = getelementptr inbounds i32, i32* [[IN_ADDR]], i64 3
 ; CHECK-NEXT:    [[GEP_2:%.*]] = getelementptr inbounds i32, i32* [[IN_ADDR]], i64 1
 ; CHECK-NEXT:    [[GEP_3:%.*]] = getelementptr inbounds i32, i32* [[IN_ADDR]], i64 2
 ; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i32* [[IN_ADDR]] to <4 x i32>*
 ; CHECK-NEXT:    [[TMP2:%.*]] = load <4 x i32>, <4 x i32>* [[TMP1]], align 4
 ; CHECK-NEXT:    [[TMP3:%.*]] = shufflevector <4 x i32> [[TMP2]], <4 x i32> undef, <4 x i32> <i32 1, i32 3, i32 2, i32 0>
-; CHECK-NEXT:    [[INN_ADDR:%.*]] = getelementptr inbounds i32, i32* %inn, i64 0
+; CHECK-NEXT:    [[INN_ADDR:%.*]] = getelementptr inbounds i32, i32* [[INN:%.*]], i64 0
 ; CHECK-NEXT:    [[GEP_4:%.*]] = getelementptr inbounds i32, i32* [[INN_ADDR]], i64 2
 ; CHECK-NEXT:    [[GEP_5:%.*]] = getelementptr inbounds i32, i32* [[INN_ADDR]], i64 3
 ; CHECK-NEXT:    [[GEP_6:%.*]] = getelementptr inbounds i32, i32* [[INN_ADDR]], i64 1
 ; CHECK-NEXT:    [[TMP4:%.*]] = bitcast i32* [[INN_ADDR]] to <4 x i32>*
 ; CHECK-NEXT:    [[TMP5:%.*]] = load <4 x i32>, <4 x i32>* [[TMP4]], align 4
 ; CHECK-NEXT:    [[TMP6:%.*]] = shufflevector <4 x i32> [[TMP5]], <4 x i32> undef, <4 x i32> <i32 0, i32 1, i32 3, i32 2>
 ; CHECK-NEXT:    [[TMP7:%.*]] = mul <4 x i32> [[TMP3]], [[TMP6]]
-; CHECK-NEXT:    [[GEP_7:%.*]] = getelementptr inbounds i32, i32* %out, i64 0
-; CHECK-NEXT:    [[GEP_8:%.*]] = getelementptr inbounds i32, i32* %out, i64 1
-; CHECK-NEXT:    [[GEP_9:%.*]] = getelementptr inbounds i32, i32* %out, i64 2
-; CHECK-NEXT:    [[GEP_10:%.*]] = getelementptr inbounds i32, i32* %out, i64 3
+; CHECK-NEXT:    [[GEP_7:%.*]] = getelementptr inbounds i32, i32* [[OUT:%.*]], i64 0
+; CHECK-NEXT:    [[GEP_8:%.*]] = getelementptr inbounds i32, i32* [[OUT]], i64 1
+; CHECK-NEXT:    [[GEP_9:%.*]] = getelementptr inbounds i32, i32* [[OUT]], i64 2
+; CHECK-NEXT:    [[GEP_10:%.*]] = getelementptr inbounds i32, i32* [[OUT]], i64 3
 ; CHECK-NEXT:    [[TMP8:%.*]] = bitcast i32* [[GEP_7]] to <4 x i32>*
 ; CHECK-NEXT:    store <4 x i32> [[TMP7]], <4 x i32>* [[TMP8]], align 4
 ; CHECK-NEXT:    ret i32 undef
 ;
   %in.addr = getelementptr inbounds i32, i32* %in, i64 0
   %load.1 = load i32, i32* %in.addr, align 4
   %gep.1 = getelementptr inbounds i32, i32* %in.addr, i64 3
   %load.2 = load i32, i32* %gep.1, align 4
;
   store i32 %mul.2, i32* %gep.8, align 4
   %gep.9 = getelementptr inbounds i32, i32* %out, i64 2
   store i32 %mul.3, i32* %gep.9, align 4
   %gep.10 = getelementptr inbounds i32, i32* %out, i64 3
   store i32 %mul.4, i32* %gep.10, align 4
 
   ret i32 undef
 }
+
+; Make sure we can sort loads even if they have non-constant offsets, as long as
+; the offset *differences* are constant and computable by SCEV.
+define void @scev(i64 %N, i32* nocapture readonly %b, i32* nocapture readonly %c) {
+; CHECK-LABEL: @scev(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP_OUTER:%.*]] = icmp sgt i64 [[N:%.*]], 0
+; CHECK-NEXT:    br i1 [[CMP_OUTER]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_END:%.*]]
+; CHECK:       for.body.preheader:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[I_P:%.*]] = phi i64 [ [[ADD21:%.*]], [[FOR_BODY]] ], [ 0, [[FOR_BODY_PREHEADER]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = phi <4 x i32> [ [[TMP14:%.*]], [[FOR_BODY]] ], [ zeroinitializer, [[FOR_BODY_PREHEADER]] ]
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i64 [[I_P]]
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[C:%.*]], i64 [[I_P]]
+; CHECK-NEXT:    [[ADD3:%.*]] = or i64 [[I_P]], 1
+; CHECK-NEXT:    [[ARRAYIDX4:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[ADD3]]
+; CHECK-NEXT:    [[ARRAYIDX6:%.*]] = getelementptr inbounds i32, i32* [[C]], i64 [[ADD3]]
+; CHECK-NEXT:    [[ADD9:%.*]] = or i64 [[I_P]], 2
+; CHECK-NEXT:    [[ARRAYIDX10:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[ADD9]]
+; CHECK-NEXT:    [[ARRAYIDX12:%.*]] = getelementptr inbounds i32, i32* [[C]], i64 [[ADD9]]
+; CHECK-NEXT:    [[ADD15:%.*]] = or i64 [[I_P]], 3
+; CHECK-NEXT:    [[ARRAYIDX16:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[ADD15]]
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i32* [[ARRAYIDX]] to <4 x i32>*
+; CHECK-NEXT:    [[TMP2:%.*]] = load <4 x i32>, <4 x i32>* [[TMP1]], align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = shufflevector <4 x i32> [[TMP2]], <4 x i32> undef, <4 x i32> <i32 2, i32 1, i32 0, i32 3>
+; CHECK-NEXT:    [[TMP4:%.*]] = bitcast i32* [[ARRAYIDX]] to <4 x i32>*
+; CHECK-NEXT:    [[TMP5:%.*]] = load <4 x i32>, <4 x i32>* [[TMP4]], align 4
+; CHECK-NEXT:    [[TMP6:%.*]] = shufflevector <4 x i32> [[TMP5]], <4 x i32> undef, <4 x i32> <i32 2, i32 1, i32 0, i32 3>
+; CHECK-NEXT:    [[ARRAYIDX18:%.*]] = getelementptr inbounds i32, i32* [[C]], i64 [[ADD15]]
+; CHECK-NEXT:    [[TMP7:%.*]] = bitcast i32* [[ARRAYIDX1]] to <4 x i32>*
+; CHECK-NEXT:    [[TMP8:%.*]] = load <4 x i32>, <4 x i32>* [[TMP7]], align 4
+; CHECK-NEXT:    [[TMP9:%.*]] = shufflevector <4 x i32> [[TMP8]], <4 x i32> undef, <4 x i32> <i32 2, i32 1, i32 0, i32 3>
+; CHECK-NEXT:    [[TMP10:%.*]] = bitcast i32* [[ARRAYIDX1]] to <4 x i32>*
+; CHECK-NEXT:    [[TMP11:%.*]] = load <4 x i32>, <4 x i32>* [[TMP10]], align 4
+; CHECK-NEXT:    [[TMP12:%.*]] = shufflevector <4 x i32> [[TMP11]], <4 x i32> undef, <4 x i32> <i32 2, i32 1, i32 0, i32 3>
+; CHECK-NEXT:    [[TMP13:%.*]] = add <4 x i32> [[TMP3]], [[TMP0]]
+; CHECK-NEXT:    [[TMP14]] = add <4 x i32> [[TMP13]], [[TMP12]]
+; CHECK-NEXT:    [[ADD21]] = add nuw nsw i64 [[I_P]], 4
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[ADD21]], [[N]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
+; CHECK:       for.end.loopexit:
+; CHECK-NEXT:    br label [[FOR_END]]
+; CHECK:       for.end:
+; CHECK-NEXT:    [[TMP15:%.*]] = phi <4 x i32> [ zeroinitializer, [[ENTRY:%.*]] ], [ [[TMP14]], [[FOR_END_LOOPEXIT]] ]
+; CHECK-NEXT:    [[TMP16:%.*]] = extractelement <4 x i32> [[TMP15]], i32 0
+; CHECK-NEXT:    [[TMP17:%.*]] = extractelement <4 x i32> [[TMP15]], i32 1
+; CHECK-NEXT:    [[ADD22:%.*]] = add nsw i32 [[TMP17]], [[TMP16]]
+; CHECK-NEXT:    [[TMP18:%.*]] = extractelement <4 x i32> [[TMP15]], i32 2
+; CHECK-NEXT:    [[ADD23:%.*]] = add nsw i32 [[ADD22]], [[TMP18]]
+; CHECK-NEXT:    [[TMP19:%.*]] = extractelement <4 x i32> [[TMP15]], i32 3
+; CHECK-NEXT:    [[ADD24:%.*]] = add nsw i32 [[ADD23]], [[TMP19]]
+; CHECK-NEXT:    store i32 [[ADD24]], i32* @total, align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp.outer = icmp sgt i64 %N, 0
+  br i1 %cmp.outer, label %for.body.preheader, label %for.end
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %a4.p = phi i32 [ %add20, %for.body ], [ 0, %for.body.preheader ]
+  %a3.p = phi i32 [ %add2, %for.body ], [ 0, %for.body.preheader ]
+  %a2.p = phi i32 [ %add8, %for.body ], [ 0, %for.body.preheader ]
+  %a1.p = phi i32 [ %add14, %for.body ], [ 0, %for.body.preheader ]
+  %i.p = phi i64 [ %add21, %for.body ], [ 0, %for.body.preheader ]
+  %arrayidx = getelementptr inbounds i32, i32* %b, i64 %i.p
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx1 = getelementptr inbounds i32, i32* %c, i64 %i.p
+  %1 = load i32, i32* %arrayidx1, align 4
+  %add = add i32 %0, %a3.p
+  %add2 = add i32 %add, %1
+  %add3 = or i64 %i.p, 1
+  %arrayidx4 = getelementptr inbounds i32, i32* %b, i64 %add3
+  %2 = load i32, i32* %arrayidx4, align 4
+  %arrayidx6 = getelementptr inbounds i32, i32* %c, i64 %add3
+  %3 = load i32, i32* %arrayidx6, align 4
+  %add7 = add i32 %2, %a2.p
+  %add8 = add i32 %add7, %3
+  %add9 = or i64 %i.p, 2
+  %arrayidx10 = getelementptr inbounds i32, i32* %b, i64 %add9
+  %4 = load i32, i32* %arrayidx10, align 4
+  %arrayidx12 = getelementptr inbounds i32, i32* %c, i64 %add9
+  %5 = load i32, i32* %arrayidx12, align 4
+  %add13 = add i32 %4, %a1.p
+  %add14 = add i32 %add13, %5
+  %add15 = or i64 %i.p, 3
+  %arrayidx16 = getelementptr inbounds i32, i32* %b, i64 %add15
+  %6 = load i32, i32* %arrayidx16, align 4
+  %arrayidx18 = getelementptr inbounds i32, i32* %c, i64 %add15
+  %7 = load i32, i32* %arrayidx18, align 4
+  %add19 = add i32 %6, %a4.p
+  %add20 = add i32 %add19, %7
+  %add21 = add nuw nsw i64 %i.p, 4
+  %cmp = icmp slt i64 %add21, %N
+  br i1 %cmp, label %for.body, label %for.end.loopexit
+
+for.end.loopexit:                                 ; preds = %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.end.loopexit, %entry
+  %a1.0.lcssa = phi i32 [ 0, %entry ], [ %add14, %for.end.loopexit ]
+  %a2.0.lcssa = phi i32 [ 0, %entry ], [ %add8, %for.end.loopexit ]
+  %a3.0.lcssa = phi i32 [ 0, %entry ], [ %add2, %for.end.loopexit ]
+  %a4.0.lcssa = phi i32 [ 0, %entry ], [ %add20, %for.end.loopexit ]
+  %add22 = add nsw i32 %a2.0.lcssa, %a1.0.lcssa
+  %add23 = add nsw i32 %add22, %a3.0.lcssa
+  %add24 = add nsw i32 %add23, %a4.0.lcssa
+  store i32 %add24, i32* @total, align 4
+  ret void
+}