[LoopInterchange] Allow some loops with PHI nodes in the exit block.

[fhahn]

Summary

We currently support LCSSA PHI nodes in the outer loop exit, if their
incoming values do not come from the outer loop latch or if the
outer loop latch has a single predecessor. In that case, the outer loop latch
will be executed only if the inner loop gets executed. If we have multiple
predecessors for the outer loop latch, it may be executed even if the inner
loop does not get executed.

This is a first step to support the case described in
https://bugs.llvm.org/show_bug.cgi?id=30472

[fhahn]

pingh

[fhahn]

ping

[fhahn]

ping

[efriedma]

Can you given an example which isn't safe to interchange due to a PHI node in the outer loop's exit block? I'm not following the logic here.

[fhahn]

Thank you very much for having a look Eli. PHI nodes in the outer loop exit block are used as a proxy for uses of values produced in the loop nest. As we are doing interchanging ATM, I think it is only safe to interchange, if the values used outside of the loop nest are produced in the inner loop. Before and after interchanging, the inner loop block will be executed if both inner and outer loop conditions are true.

The same might not be true for values produced in the outer loop I think. For example, if the inner loop body is never executed. Consider the example below, where the outer loop induction variable is returned. In case br i1 undef, label %for.body4, label %for.cond.cleanup3 is always false, we would execute the outer loop latch 1024 times and return 1024. In the interchanged version, we would never execute the outer loop latch, and it is not clear what the values the PHI node should use I think.

Please let me know if that makes sense :)

define i64 @no_deps_interchange([1024 x i32]* nocapture %Arr, i32 %k, i64 %B) {
entry:
  br label %for.body

for.body:                                         ; preds = %entry, %for.cond.cleanup3
  %indvars.iv19 = phi i64 [ 0, %entry ], [ %indvars.iv.next20, %for.cond.cleanup3 ]
  br i1 undef, label %for.body4, label %for.cond.cleanup3

for.body4:                                        ; preds = %for.body, %for.body4
  %indvars.iv = phi i64 [ 0, %for.body ], [ %indvars.iv.next, %for.body4 ]
  %arrayidx6 = getelementptr inbounds [1024 x i32], [1024 x i32]* %Arr, i64 %indvars.iv, i64 %indvars.iv19
  store i32 0, i32* %arrayidx6, align 4
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %exitcond = icmp ne i64 %indvars.iv.next, %B
  br i1 %exitcond, label %for.body4, label %for.cond.cleanup3

for.cond.cleanup3:                                ; preds = %for.body4
  %indvars.iv.next20 = add nuw nsw i64 %indvars.iv19, 1
  %exitcond21 = icmp ne i64 %indvars.iv.next20, 1024
  br i1 %exitcond21, label %for.body, label %for.cond.cleanup


for.cond.cleanup:                                 ; preds = %for.cond.cleanup3
  ret i64 %indvars.iv.next20
}

Which, given we allow PHI nodes with values produced in the outer loop latch, produces the following code after interchanging

define i64 @no_deps_interchange([1024 x i32]* nocapture %Arr, i32 %k, i64 %B) {
entry:
  br label %for.body4.preheader

for.body.preheader:                               ; preds = %for.body4
  br label %for.body

for.body:                                         ; preds = %for.body.preheader, %for.cond.cleanup3
  %indvars.iv19 = phi i64 [ %indvars.iv.next20, %for.cond.cleanup3 ], [ 0, %for.body.preheader ]
  br i1 undef, label %for.body4.split1, label %for.cond.cleanup

for.body4.preheader:                              ; preds = %entry
  br label %for.body4

for.body4:                                        ; preds = %for.body4.preheader, %for.body4.split
  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body4.split ], [ 0, %for.body4.preheader ]
  br label %for.body.preheader

for.body4.split1:                                 ; preds = %for.body
  %arrayidx6 = getelementptr inbounds [1024 x i32], [1024 x i32]* %Arr, i64 %indvars.iv, i64 %indvars.iv19
  store i32 0, i32* %arrayidx6, align 4
  br label %for.cond.cleanup3.loopexit

for.body4.split:                                  ; preds = %for.cond.cleanup3
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %exitcond = icmp ne i64 %indvars.iv.next, %B
  br i1 %exitcond, label %for.body4, label %for.cond.cleanup

for.cond.cleanup3.loopexit:                       ; preds = %for.body4.split1
  br label %for.cond.cleanup3

for.cond.cleanup3:                                ; preds = %for.cond.cleanup3.loopexit
  %indvars.iv.next20 = add nuw nsw i64 %indvars.iv19, 1
  %exitcond21 = icmp ne i64 %indvars.iv.next20, 1024
  br i1 %exitcond21, label %for.body, label %for.body4.split

for.cond.cleanup:                                 ; preds = %for.body4.split, %for.body
  %indvars.iv.next20.lcssa = phi i64 [ %indvars.iv.next20, %for.body4.split ]  ; invalid PHI node
  ret i64 %indvars.iv.next20.lcssa
}

[efriedma]

So the problem is specifically with values produced in the loop latch? That makes sense, I guess, but it seems like you could check for that more directly. (It might also be possible to hoist the instruction out of the latch, but I guess that's complicated in general.)

[fhahn]

In D43237#1035200, @efriedma wrote:

So the problem is specifically with values produced in the loop latch? That makes sense, I guess, but it seems like you could check for that more directly. (It might also be possible to hoist the instruction out of the latch, but I guess that's complicated in general.)

Yes, I think currently only values produced in the outer loop latch can be a problem, because the outer loop latch must be the inner loop exit block at the moment IIRC. Although if we loosen that restriction at some point, values in other blocks of the outer loop could become problematic as well.

I guess we could simplify the check by just checking if any incoming values to the phis in the exit block are non-phi nodes in the outer loop latch and prevent interchanging in that case. That way, we would also allow values produced in the outer loop header, which should be fine. With some assertions, ensuring the outer loop latch's predecessors are only blocks exiting the inner loop or the outer loop header. Is that along the lines you were thinking?

There's potential follow-up work to loosen that restriction if we know that the inner loop body gets executed at least once or if we can hoist the offending statements.

[efriedma]

I guess, something like that, yes.

[fhahn]

Made check slightly more direct. I went ahead and limited it loop latches with a single predecessor, because we need additional logic to update the PHI nodes in that case. The LI tests also changed a bit after D35430, so I updated the tests this patch touches.

[efriedma]

LGTM

[fhahn]

Thank you very much for having a look Eli! I have submitted D45207 and D45206 for review, to restore most of the loop interchange test coverage after D35430 when in. I will commit this change after the test changes went in

[fhahn]

After the recent changes I committed, the test-suite passes with loopinterchange enabled + LTO. It looks like this patch breaks a few benchmarks again. I will look into that before submitting it

[fhahn]

Sorry for the delay! Rebased after recent LoopInterchange changes.

There has been a minor change to fix a compilation issue with the test suite: floating point LCSSA phi nodes are not supported, as they currently are the only way to detect FP reductions.

I plan to commit this tomorrow, in case there are no further objections.

lib/Transforms/Scalar/LoopInterchange.cpp

 #endif
 
     BasicBlock *OuterMostLoopLatch = OuterMostLoop->getLoopLatch();
     BranchInst *OuterMostLoopLatchBI =
         dyn_cast<BranchInst>(OuterMostLoopLatch->getTerminator());
     if (!OuterMostLoopLatchBI || OuterMostLoopLatchBI->getNumSuccessors() != 2)
       return false;
 
-    // Since we currently do not handle LCSSA PHI's any failure in loop
-    // condition will now branch to LoopNestExit.
-    // TODO: This should be removed once we handle LCSSA PHI nodes.
-
     // Get the Outermost loop exit.
     BasicBlock *LoopNestExit;
     if (OuterMostLoopLatchBI->getSuccessor(0) == OuterMostLoop->getHeader())
       LoopNestExit = OuterMostLoopLatchBI->getSuccessor(1);
     else
       LoopNestExit = OuterMostLoopLatchBI->getSuccessor(0);
 
-    if (isa<PHINode>(LoopNestExit->begin())) {
-      DEBUG(dbgs() << "PHI Nodes in loop nest exit is not handled for now "
-                      "since on failure all loops branch to loop nest exit.\n");
-      return false;
-    }
-
     unsigned SelecLoopId = selectLoopForInterchange(LoopList);
     // Move the selected loop outwards to the best possible position.
     for (unsigned i = SelecLoopId; i > 0; i--) {
       bool Interchanged =
           processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix);
       if (!Interchanged)
         return Changed;
       // Loops interchanged reflect the same in LoopList

 }
 
 // This function indicates the current limitations in the transform as a result
 // of which we do not proceed.
 bool LoopInterchangeLegality::currentLimitations() {
   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
-  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
-  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
 
   PHINode *InnerInductionVar;
   SmallVector<PHINode *, 8> Inductions;
   SmallVector<PHINode *, 8> Reductions;
   if (!findInductionAndReductions(InnerLoop, Inductions, Reductions)) {
     DEBUG(dbgs() << "Only inner loops with induction or reduction PHI nodes "
                  << "are supported currently.\n");
     ORE->emit([&]() {
ORE->emit([&]() {
                                       InnerLoop->getHeader())
              << "Inner loop structure not understood currently.";
     });
     return true;
   }
 
   // TODO: We only handle LCSSA PHI's corresponding to reduction for now.
   BasicBlock *LoopExitBlock =
-      getLoopLatchExitBlock(OuterLoopLatch, OuterLoopHeader);
-  if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, true)) {
-    DEBUG(dbgs() << "Can only handle LCSSA PHIs in outer loops currently.\n");
-    ORE->emit([&]() {
-      return OptimizationRemarkMissed(DEBUG_TYPE, "NoLCSSAPHIOuter",
-                                      OuterLoop->getStartLoc(),
-                                      OuterLoop->getHeader())
-             << "Only outer loops with LCSSA PHIs can be interchange "
-                "currently.";
-    });
-    return true;
-  }
-
-  LoopExitBlock = getLoopLatchExitBlock(InnerLoopLatch, InnerLoopHeader);
+      getLoopLatchExitBlock(InnerLoopLatch, InnerLoopHeader);
   if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, false)) {
     DEBUG(dbgs() << "Can only handle LCSSA PHIs in inner loops currently.\n");
     ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "NoLCSSAPHIOuterInner",
                                       InnerLoop->getStartLoc(),
                                       InnerLoop->getHeader())
              << "Only inner loops with LCSSA PHIs can be interchange "
                 "currently.";
ORE->emit([&]() {
                                       InnerLoop->getHeader())
              << "Did not find the induction variable.";
     });
     return true;
   }
   return false;
 }
 
+// We currently support LCSSA PHI nodes in the outer loop exit, if their
+// incoming values do not come from the outer loop latch or if the
+// outer loop latch has a single predecessor. In that case, the value will
+// be available if both the inner and outer loop conditions are true, which
+// will still be true after interchanging. If we have multiple predecessor,
+// that may not be the case, e.g. because the outer loop latch may be executed
+// if the inner loop is not executed.
+static bool areLoopExitPHIsSupported(Loop *OuterLoop, Loop *InnerLoop) {
+  BasicBlock *LoopNestExit = OuterLoop->getUniqueExitBlock();
+  for (PHINode &PHI : LoopNestExit->phis()) {
+    for (unsigned i = 0; i < PHI.getNumIncomingValues(); i++) {
+     Instruction *IncomingI = dyn_cast<Instruction>(PHI.getIncomingValue(i));
+     if (!IncomingI || IncomingI->getParent() != OuterLoop->getLoopLatch())
+       continue;
+
+     // The incoming value is defined in the outer loop latch. Currently we
+     // only support that in case the outer loop latch has a single predecessor.
+     // This guarantees that the outer loop latch is executed if and only if
+     // the inner loop is executed (because tightlyNested() guarantees that the
+     // outer loop header only branches to the inner loop or the outer loop
+     // latch).
+     // FIXME: We could weaken this logic and allow multiple predecessors,
+     //        if the values are produced outside the loop latch. We would need
+     //        additional logic to update the PHI nodes in the exit block as
+     //        well.
+     if (OuterLoop->getLoopLatch()->getUniquePredecessor() == nullptr)
+       return false;
+    }
+  }
+  return true;
+}
+
 bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
                                                   unsigned OuterLoopId,
                                                   CharMatrix &DepMatrix) {
   if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
     DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
                  << " and OuterLoopId = " << OuterLoopId
                  << " due to dependence\n");
     ORE->emit([&]() {
ORE->emit([&]() {
                                       InnerLoop->getStartLoc(),
                                       InnerLoop->getHeader())
              << "Cannot interchange loops because they are not tightly "
                 "nested.";
     });
     return false;
   }
 
+  if (!areLoopExitPHIsSupported(OuterLoop, InnerLoop)) {
+    DEBUG(dbgs() << "Found unsupported PHI nodes in outer loop exit.\n");
+    ORE->emit([&]() {
+      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
+                                      OuterLoop->getStartLoc(),
+                                      OuterLoop->getHeader())
+             << "Found unsupported PHI node in loop exit.";
+    });
+    return false;
+  }
+
   return true;
 }
 
 int LoopInterchangeProfitability::getInstrOrderCost() {
   unsigned GoodOrder, BadOrder;
   BadOrder = GoodOrder = 0;
   for (BasicBlock *BB : InnerLoop->blocks()) {
     for (Instruction &Ins : *BB) {

test/Transforms/LoopInterchange/current-limitations-lcssa.ll

-; REQUIRES: asserts
-; RUN: opt < %s -basicaa -loop-interchange -S -debug 2>&1 | FileCheck %s
-
-target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
-target triple = "x86_64-unknown-linux-gnu"
-
-@A = common global [100 x [100 x i32]] zeroinitializer
-@C = common global [100 x [100 x i32]] zeroinitializer
-
-;; FIXME:
-;; Test for interchange when we have an lcssa phi. This should ideally be interchanged but it is currently not supported.
-;;     for(gi=1;gi<N;gi++)
-;;       for(gj=1;gj<M;gj++)
-;;         A[gj][gi] = A[gj - 1][gi] + C[gj][gi];
-
-; CHECK: PHI Nodes in loop nest exit is not handled for now since on failure all loops branch to loop nest exit.
-
-@gi = common global i32 0
-@gj = common global i32 0
-
-define void @interchange_07(i32 %N, i32 %M){
-entry:
-  store i32 1, i32* @gi
-  %cmp21 = icmp sgt i32 %N, 1
-  br i1 %cmp21, label %for.cond1.preheader.lr.ph, label %for.end16
-
-for.cond1.preheader.lr.ph:
-  %cmp218 = icmp sgt i32 %M, 1
-  %gi.promoted = load i32, i32* @gi
-  %0 = add i32 %M, -1
-  %1 = sext i32 %gi.promoted to i64
-  %2 = sext i32 %N to i64
-  %3 = add i32 %gi.promoted, 1
-  %4 = icmp slt i32 %3, %N
-  %smax = select i1 %4, i32 %N, i32 %3
-  br label %for.cond1.preheader
-
-for.cond1.preheader:
-  %indvars.iv25 = phi i64 [ %1, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next26, %for.inc14 ]
-  br i1 %cmp218, label %for.body3, label %for.inc14
-
-for.body3:
-  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 1, %for.cond1.preheader ]
-  %5 = add nsw i64 %indvars.iv, -1
-  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %5, i64 %indvars.iv25
-  %6 = load i32, i32* %arrayidx5
-  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %indvars.iv, i64 %indvars.iv25
-  %7 = load i32, i32* %arrayidx9
-  %add = add nsw i32 %7, %6
-  %arrayidx13 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv25
-  store i32 %add, i32* %arrayidx13
-  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
-  %lftr.wideiv = trunc i64 %indvars.iv to i32
-  %exitcond = icmp eq i32 %lftr.wideiv, %0
-  br i1 %exitcond, label %for.inc14, label %for.body3
-
-for.inc14:
-  %inc.lcssa23 = phi i32 [ 1, %for.cond1.preheader ], [ %M, %for.body3 ]
-  %indvars.iv.next26 = add nsw i64 %indvars.iv25, 1
-  %cmp = icmp slt i64 %indvars.iv.next26, %2
-  br i1 %cmp, label %for.cond1.preheader, label %for.cond.for.end16_crit_edge
-
-for.cond.for.end16_crit_edge:
-  store i32 %inc.lcssa23, i32* @gj
-  store i32 %smax, i32* @gi
-  br label %for.end16
-
-for.end16:
-  ret void
-}

test/Transforms/LoopInterchange/lcssa.ll

+; RUN: opt < %s -basicaa -loop-interchange -pass-remarks-missed='loop-interchange' -pass-remarks-output=%t
+; RUN: cat %t |  FileCheck --check-prefix REMARK %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@A = common global [100 x [100 x i32]] zeroinitializer
+@C = common global [100 x [100 x i32]] zeroinitializer
+@X = common global i32 0
+@Y = common global i64 0
+
+; We cannot interchange this loop at the moment, because iv.outer.next is
+; produced in the outer loop latch and used in the loop exit block. If the inner
+; loop body is not executed, the outer loop latch won't be executed either
+; after interchanging.
+; REMARK: UnsupportedExitPHI
+; REMARK-NEXT: lcssa_01
+
+define void @lcssa_01(){
+entry:
+  %cmp21 = icmp sgt i64 100, 1
+  br i1 %cmp21, label %outer.ph, label %for.end16
+
+outer.ph:
+  %cmp218 = icmp sgt i64 100, 1
+  br label %outer.header
+
+outer.header:
+  %iv.outer= phi i64 [ 1, %outer.ph ], [ %iv.outer.next, %outer.inc ]
+  br i1 %cmp218, label %for.body3, label %outer.inc
+
+for.body3:
+  %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
+  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
+  %vA = load i32, i32* %arrayidx5
+  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
+  %vC = load i32, i32* %arrayidx9
+  %add = add nsw i32 %vA, %vC
+  store i32 %add, i32* %arrayidx5
+  %iv.inner.next = add nuw nsw i64 %iv.inner, 1
+  %exitcond = icmp eq i64 %iv.inner.next, 100
+  br i1 %exitcond, label %outer.inc, label %for.body3
+
+outer.inc:
+  %iv.outer.next = add nsw i64 %iv.outer, 1
+  %cmp = icmp eq i64 %iv.outer.next, 100
+  br i1 %cmp, label %outer.header, label %for.exit
+
+for.exit:
+  store i64 %iv.outer.next, i64 * @Y
+  br label %for.end16
+
+for.end16:
+  ret void
+}
+
+; REMARK: UnsupportedExitPHI
+; REMARK-NEXT: lcssa_02
+define void @lcssa_02(){
+entry:
+  %cmp21 = icmp sgt i64 100, 1
+  br i1 %cmp21, label %outer.ph, label %for.end16
+
+outer.ph:
+  %cmp218 = icmp sgt i64 100, 1
+  br label %outer.header
+
+outer.header:
+  %iv.outer= phi i64 [ 1, %outer.ph ], [ %iv.outer.next, %outer.inc ]
+  br i1 %cmp218, label %for.body3, label %outer.inc
+
+for.body3:
+  %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
+  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
+  %vA = load i32, i32* %arrayidx5
+  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
+  %vC = load i32, i32* %arrayidx9
+  %add = add nsw i32 %vA, %vC
+  store i32 %add, i32* %arrayidx5
+  %iv.inner.next = add nuw nsw i64 %iv.inner, 1
+  %exitcond = icmp eq i64 %iv.inner.next, 100
+  br i1 %exitcond, label %outer.inc, label %for.body3
+
+outer.inc:
+  %iv.inner.end = phi i64 [ 0, %outer.header ], [ %iv.inner.next, %for.body3 ]
+  %iv.outer.next = add nsw i64 %iv.outer, 1
+  %cmp = icmp eq i64 %iv.outer.next, 100
+  br i1 %cmp, label %outer.header, label %for.exit
+
+for.exit:
+  store i64 %iv.inner.end, i64 * @Y
+  br label %for.end16
+
+for.end16:
+  ret void
+}
+
+
+; REMARK: Interchanged
+; REMARK-NEXT: lcssa_03
+define void @lcssa_03(){
+entry:
+  br label %outer.header
+
+outer.header:
+  %iv.outer= phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
+  br label %for.body3
+
+for.body3:
+  %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
+  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
+  %vA = load i32, i32* %arrayidx5
+  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
+  %vC = load i32, i32* %arrayidx9
+  %add = add nsw i32 %vA, %vC
+  store i32 %add, i32* %arrayidx5
+  %iv.inner.next = add nuw nsw i64 %iv.inner, 1
+  %exitcond = icmp eq i64 %iv.inner.next, 100
+  br i1 %exitcond, label %outer.inc, label %for.body3
+
+outer.inc:
+  %iv.outer.next = add nsw i64 %iv.outer, 1
+  %cmp = icmp eq i64 %iv.outer.next, 100
+  br i1 %cmp, label %outer.header, label %for.exit
+
+for.exit:
+  store i64 %iv.inner, i64 * @Y
+  br label %for.end16
+
+for.end16:
+  ret void
+}
+
+define void @lcssa_04(i1 %cc){
+entry:
+  br label %outer.header
+
+outer.header:
+  %iv.outer= phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
+  br label %for.body3
+
+for.body3:
+  %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
+  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
+  %vA = load i32, i32* %arrayidx5
+  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
+  %vC = load i32, i32* %arrayidx9
+  %add = add nsw i32 %vA, %vC
+  store i32 %add, i32* %arrayidx5
+  %iv.inner.next = add nuw nsw i64 %iv.inner, 1
+  %exitcond = icmp eq i64 %iv.inner.next, 100
+  br i1 %exitcond, label %bb2, label %for.body3
+
+bb2:
+  br i1 %cc, label %outer.inc, label %for.exit
+
+outer.inc:
+  %iv.outer.next = add nsw i64 %iv.outer, 1
+  %cmp = icmp eq i64 %iv.outer.next, 100
+  br i1 %cmp, label %outer.header, label %for.exit
+
+for.exit:
+  br label %for.end16
+
+for.end16:
+  ret void
+}

test/Transforms/LoopInterchange/reductions.ll

 for.inc13:                                        ; preds = %for.cond4.for.inc10_crit_edge
   %inc14 = add nuw nsw i32 %i.029, 1
   %exitcond34 = icmp eq i32 %inc14, %N
   br i1 %exitcond34, label %for.end15, label %for.cond4.preheader.preheader
 
 for.end15:                                        ; preds = %for.inc13, %entry
   ret void
 }
+
+;;  for( int i=1;i<N;i++)
+;;    for( int j=1;j<N;j++)
+;;      X+=A[j][i];
+;;  Y = X
+; CHECK: Loops interchanged.
+define void @reduction_05(i32 %N) {
+entry:
+  %cmp16 = icmp sgt i32 %N, 1
+  br i1 %cmp16, label %for.body7.lr.ph, label %for.end8
+
+for.body7.lr.ph:                                  ; preds = %entry, %for.cond1.for.inc6_crit_edge
+  %indvars.iv18 = phi i64 [ %indvars.iv.next19, %for.cond1.for.inc6_crit_edge ], [ 1, %entry ]
+  %X.promoted = load i32, i32* @X
+  br label %for.body7
+
+for.body7:                                        ; preds = %for.body7, %for.body7.lr.ph
+  %indvars.iv = phi i64 [ 1, %for.body7.lr.ph ], [ %indvars.iv.next, %for.body7 ]
+  %add15 = phi i32 [ %X.promoted, %for.body7.lr.ph ], [ %add, %for.body7 ]
+  %arrayidx5 = getelementptr inbounds [500 x [500 x i32]], [500 x [500 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv18
+  %0 = load i32, i32* %arrayidx5
+  %add = add nsw i32 %add15, %0
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %N
+  br i1 %exitcond, label %for.cond1.for.inc6_crit_edge, label %for.body7
+
+for.cond1.for.inc6_crit_edge:                     ; preds = %for.body7
+  store i32 %add, i32* @X
+  %indvars.iv.next19 = add nuw nsw i64 %indvars.iv18, 1
+  %lftr.wideiv20 = trunc i64 %indvars.iv.next19 to i32
+  %exitcond21 = icmp eq i32 %lftr.wideiv20, %N
+  br i1 %exitcond21, label %for.end8, label %for.body7.lr.ph
+
+for.end8:                                         ; preds = %for.cond1.for.inc6_crit_edge, %entry
+  %add.res = phi i32 [ %add, %for.cond1.for.inc6_crit_edge], [ 0, %entry ]
+  store i32 %add.res, i32* @Y
+
+  ret void
+}