[LoopInterchange] Remove support for inner-only reductions.

[fhahn]

Summary

Inner-loop only reductions require additional checks to make sure they
form a load-phi-store cycle across inner and outer loop. Otherwise the
reduction value is not properly preserved. This patch disables
interchanging such loops for now, as it causes miscompiles in some
cases and it seems to apply only for a tiny amount of loops. Across the
test-suite, SPEC2000 and SPEC2006, 61 instead of 62 loops are
interchange with inner loop reduction support disabled. With
-loop-interchange-threshold=-1000, 3256 instead of 3267.

See the discussion and history of D53027 for an outline of how such legality
checks could look like.

[efriedma]

This analysis seems very fragile.

lib/Transforms/Scalar/LoopInterchange.cpp

655

I'm pretty sure the "PHInd == -1 || IncInd == -1" check is unnecessary, given the PHI is in the loop header.

671

What happens if SI is non-null before we enter here?

674

What happens if there are mutiple stores using the PHI?

681

Could any operations between the load and store alias them? Does it matter?

[fhahn]

In D53027#1268066, @efriedma wrote:

This analysis seems very fragile.

Agreed, it is not ideal and I think alternatively we could just drop support for such loops as it is unlikely they will be profitable (we are moving loads/stores from outer loops to inner loops). Unfortunately I did not find any existing analysis that could be re-used for those checks, but I think they are quite conservative.

It would be great if you could let me know which option you prefer. If we go with this patch, I'll address the code comments and also add a comment in line with my responses. The underlying problem is that loops like the one below are miscompiled if they are interchanged, if y is a global variable.

for (unsigned i = 0; i < N; i++) {
  y = 0;
  for (unsigned j = 0; j < N; j++) {
    A[i][j] += 1;
    y += A[i][j];
  }
}

lib/Transforms/Scalar/LoopInterchange.cpp

674

We could just support a single store in the exit block for now I think.

681

I don't think aliasing operations between them (in the inner loop body) should be a problem. The store in the exit makes sure we write the correct value after the inner loop has been executed, and the load makes sure the inner loop uses the right values.

Having multiple load - reduction - stores which alias shouldn't be a problem either. As long as each chain forms a cycle, the results should be properly be preserved between inner loop executions and we do not change the relative order of the loads/stores. If we would have multiple stores that alias, it would mean we reduce multiple chains to a single one.

[efriedma]

If you aren't finding real loops where this matters, simply rejecting loops with a reduction like this seems fine.

[fhahn]

In D53027#1277836, @efriedma wrote:

If you aren't finding real loops where this matters, simply rejecting loops with a reduction like this seems fine.

I've updated the patch to remove support for inner-loop only reductions and updated the description with some numbers across the test-suite, SPEC2k and SPEC2k6. Given the simplification and the minor practical impact, I think it would make sense to just remove it. What do you think? I've also added a comment referring back to the discussion and patches here, in case we want to add the analysis described here later on.

It also simplifies the code to support reductions across inner & outer loops.

[efriedma]

LGTM

[fhahn]

Thanks Eli!

lib/Transforms/Scalar/LoopInterchange.cpp

bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
                            CharMatrix &DepMatrix);
 
   /// Check if the loop structure is understood. We do not handle triangular
   /// loops for now.
   bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
 
   bool currentLimitations();
 
-  bool hasInnerLoopReduction() { return InnerLoopHasReduction; }
-
 private:
   bool tightlyNested(Loop *Outer, Loop *Inner);
-  bool containsUnsafeInstructionsInHeader(BasicBlock *BB);
-  bool areAllUsesReductions(Instruction *Ins, Loop *L);
-  bool containsUnsafeInstructionsInLatch(BasicBlock *BB);
-  bool findInductionAndReductions(Loop *L,
-                                  SmallVector<PHINode *, 8> &Inductions,
-                                  SmallVector<PHINode *, 8> &Reductions);
+  bool containsUnsafeInstructions(BasicBlock *BB);
+  bool findInductions(Loop *L, SmallVector<PHINode *, 8> &Inductions);
 
   Loop *OuterLoop;
   Loop *InnerLoop;
 
   ScalarEvolution *SE;
 
   /// Interface to emit optimization remarks.
   OptimizationRemarkEmitter *ORE;
 
-  bool InnerLoopHasReduction = false;
 };
 
 /// LoopInterchangeProfitability checks if it is profitable to interchange the
 /// loop.
 class LoopInterchangeProfitability {
 public:
   LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
                                OptimizationRemarkEmitter *ORE)
private:
   OptimizationRemarkEmitter *ORE;
 };
 
 /// LoopInterchangeTransform interchanges the loop.
 class LoopInterchangeTransform {
 public:
   LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
                            LoopInfo *LI, DominatorTree *DT,
-                           BasicBlock *LoopNestExit,
-                           bool InnerLoopContainsReductions)
+                           BasicBlock *LoopNestExit)
       : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
-        LoopExit(LoopNestExit),
-        InnerLoopHasReduction(InnerLoopContainsReductions) {}
+        LoopExit(LoopNestExit) {}
 
   /// Interchange OuterLoop and InnerLoop.
   bool transform();
   void restructureLoops(Loop *NewInner, Loop *NewOuter,
                         BasicBlock *OrigInnerPreHeader,
                         BasicBlock *OrigOuterPreHeader);
   void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
 
 private:
   void splitInnerLoopLatch(Instruction *);
   void splitInnerLoopHeader();
   bool adjustLoopLinks();
   void adjustLoopPreheaders();
   bool adjustLoopBranches();
 
   Loop *OuterLoop;
   Loop *InnerLoop;
 
   /// Scev analysis.
   ScalarEvolution *SE;
 
   LoopInfo *LI;
   DominatorTree *DT;
   BasicBlock *LoopExit;
-  bool InnerLoopHasReduction;
 };
 
 // Main LoopInterchange Pass.
 struct LoopInterchange : public LoopPass {
   static char ID;
   ScalarEvolution *SE = nullptr;
   LoopInfo *LI = nullptr;
   DependenceInfo *DI = nullptr;
bool processLoop(LoopVector LoopList, unsigned InnerLoopId,
     ORE->emit([&]() {
       return OptimizationRemark(DEBUG_TYPE, "Interchanged",
                                 InnerLoop->getStartLoc(),
                                 InnerLoop->getHeader())
              << "Loop interchanged with enclosing loop.";
     });
 
     LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT,
-                                 LoopNestExit, LIL.hasInnerLoopReduction());
+                                 LoopNestExit);
     LIT.transform();
     LLVM_DEBUG(dbgs() << "Loops interchanged.\n");
     LoopsInterchanged++;
     return true;
   }
 };
 
 } // end anonymous namespace
 
-bool LoopInterchangeLegality::areAllUsesReductions(Instruction *Ins, Loop *L) {
-  return llvm::none_of(Ins->users(), [=](User *U) -> bool {
-    auto *UserIns = dyn_cast<PHINode>(U);
-    RecurrenceDescriptor RD;
-    return !UserIns || !RecurrenceDescriptor::isReductionPHI(UserIns, L, RD);
+bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB) {
+  return any_of(*BB, [](const Instruction &I) {
+    return I.mayHaveSideEffects() || I.mayReadFromMemory();
   });
 }
 
-bool LoopInterchangeLegality::containsUnsafeInstructionsInHeader(
-    BasicBlock *BB) {
-  for (Instruction &I : *BB) {
-    // Load corresponding to reduction PHI's are safe while concluding if
-    // tightly nested.
-    if (LoadInst *L = dyn_cast<LoadInst>(&I)) {
-      if (!areAllUsesReductions(L, InnerLoop))
-        return true;
-    } else if (I.mayHaveSideEffects() || I.mayReadFromMemory())
-      return true;
-  }
-  return false;
-}
-
-bool LoopInterchangeLegality::containsUnsafeInstructionsInLatch(
-    BasicBlock *BB) {
-  for (Instruction &I : *BB) {
-    // Stores corresponding to reductions are safe while concluding if tightly
-    // nested.
-    if (StoreInst *L = dyn_cast<StoreInst>(&I)) {
-      if (!isa<PHINode>(L->getOperand(0)))
-        return true;
-    } else if (I.mayHaveSideEffects() || I.mayReadFromMemory())
-      return true;
-  }
-  return false;
-}
-
 bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
 
   LLVM_DEBUG(dbgs() << "Checking if loops are tightly nested\n");
 
   // A perfectly nested loop will not have any branch in between the outer and
   // inner block i.e. outer header will branch to either inner preheader and
   // outerloop latch.
   BranchInst *OuterLoopHeaderBI =
       dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
   if (!OuterLoopHeaderBI)
     return false;
 
   for (BasicBlock *Succ : successors(OuterLoopHeaderBI))
     if (Succ != InnerLoopPreHeader && Succ != InnerLoop->getHeader() &&
         Succ != OuterLoopLatch)
       return false;
 
   LLVM_DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch\n");
   // We do not have any basic block in between now make sure the outer header
   // and outer loop latch doesn't contain any unsafe instructions.
-  if (containsUnsafeInstructionsInHeader(OuterLoopHeader) ||
-      containsUnsafeInstructionsInLatch(OuterLoopLatch))
+  if (containsUnsafeInstructions(OuterLoopHeader) ||
+      containsUnsafeInstructions(OuterLoopLatch))
     return false;
 
   LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n");
   // We have a perfect loop nest.
   return true;
 }
 
 bool LoopInterchangeLegality::isLoopStructureUnderstood(
if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
             InnerLoopPreheader &&
         !OuterLoop->isLoopInvariant(I)) {
       return false;
     }
   }
   return true;
 }
 
-bool LoopInterchangeLegality::findInductionAndReductions(
-    Loop *L, SmallVector<PHINode *, 8> &Inductions,
-    SmallVector<PHINode *, 8> &Reductions) {
+bool LoopInterchangeLegality::findInductions(
+    Loop *L, SmallVector<PHINode *, 8> &Inductions) {
   if (!L->getLoopLatch() || !L->getLoopPredecessor())
     return false;
   for (PHINode &PHI : L->getHeader()->phis()) {
     RecurrenceDescriptor RD;
     InductionDescriptor ID;
     if (InductionDescriptor::isInductionPHI(&PHI, L, SE, ID))
       Inductions.push_back(&PHI);
-    else if (RecurrenceDescriptor::isReductionPHI(&PHI, L, RD))
-      Reductions.push_back(&PHI);
     else {
-      LLVM_DEBUG(
-          dbgs() << "Failed to recognize PHI as an induction or reduction.\n");
+      LLVM_DEBUG(dbgs() << "Failed to recognize PHI as an induction.\n");
       return false;
     }
   }
   return true;
 }
 
 static bool containsSafePHI(BasicBlock *Block, bool isOuterLoopExitBlock) {
   for (PHINode &PHI : Block->phis()) {
     // Reduction lcssa phi will have only 1 incoming block that from loop latch.
     if (PHI.getNumIncomingValues() > 1)
       return false;
     Instruction *Ins = dyn_cast<Instruction>(PHI.getIncomingValue(0));
     if (!Ins)
       return false;
     // Incoming value for lcssa phi's in outer loop exit can only be inner loop
     // exits lcssa phi else it would not be tightly nested.
     if (!isa<PHINode>(Ins) && isOuterLoopExitBlock)
       return false;
   }
   return true;
 }
 
 // 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 *InnerLoopLatch = InnerLoop->getLoopLatch();
 
   // transform currently expects the loop latches to also be the exiting
   // blocks.
   if (InnerLoop->getExitingBlock() != InnerLoopLatch ||
       OuterLoop->getExitingBlock() != OuterLoop->getLoopLatch() ||
       !isa<BranchInst>(InnerLoopLatch->getTerminator()) ||
       !isa<BranchInst>(OuterLoop->getLoopLatch()->getTerminator())) {
     LLVM_DEBUG(
         dbgs() << "Loops where the latch is not the exiting block are not"
                << " supported currently.\n");
     ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "ExitingNotLatch",
                                       OuterLoop->getStartLoc(),
                                       OuterLoop->getHeader())
              << "Loops where the latch is not the exiting block cannot be"
                 " interchange currently.";
     });
     return true;
   }
 
   PHINode *InnerInductionVar;
   SmallVector<PHINode *, 8> Inductions;
-  SmallVector<PHINode *, 8> Reductions;
-  if (!findInductionAndReductions(InnerLoop, Inductions, Reductions)) {
+  if (!findInductions(InnerLoop, Inductions)) {
     LLVM_DEBUG(
         dbgs() << "Only inner loops with induction or reduction PHI nodes "
                << "are supported currently.\n");
     ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIInner",
                                       InnerLoop->getStartLoc(),
                                       InnerLoop->getHeader())
              << "Only inner loops with induction or reduction PHI nodes can be"
ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "MultiInductionInner",
                                       InnerLoop->getStartLoc(),
                                       InnerLoop->getHeader())
              << "Only inner loops with 1 induction variable can be "
                 "interchanged currently.";
     });
     return true;
   }
-  if (Reductions.size() > 0)
-    InnerLoopHasReduction = true;
 
   InnerInductionVar = Inductions.pop_back_val();
-  Reductions.clear();
-  if (!findInductionAndReductions(OuterLoop, Inductions, Reductions)) {
+  if (!findInductions(OuterLoop, Inductions)) {
     LLVM_DEBUG(
         dbgs() << "Only outer loops with induction or reduction PHI nodes "
                << "are supported currently.\n");
     ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIOuter",
                                       OuterLoop->getStartLoc(),
                                       OuterLoop->getHeader())
              << "Only outer loops with induction or reduction PHI nodes can be"
                 " interchanged currently.";
     });
     return true;
   }
 
-  // Outer loop cannot have reduction because then loops will not be tightly
-  // nested.
-  if (!Reductions.empty()) {
-    LLVM_DEBUG(dbgs() << "Outer loops with reductions are not supported "
-                      << "currently.\n");
-    ORE->emit([&]() {
-      return OptimizationRemarkMissed(DEBUG_TYPE, "ReductionsOuter",
-                                      OuterLoop->getStartLoc(),
-                                      OuterLoop->getHeader())
-             << "Outer loops with reductions cannot be interchangeed "
-                "currently.";
-    });
-    return true;
-  }
   // TODO: Currently we handle only loops with 1 induction variable.
   if (Inductions.size() != 1) {
     LLVM_DEBUG(dbgs() << "Loops with more than 1 induction variables are not "
                       << "supported currently.\n");
     ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "MultiIndutionOuter",
                                       OuterLoop->getStartLoc(),
                                       OuterLoop->getHeader())
bool LoopInterchangeTransform::adjustLoopBranches() {
   restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader,
                    OuterLoopPreHeader);
 
   moveLCSSAPhis(InnerLoopLatchSuccessor, InnerLoopLatch, OuterLoopLatch);
   // For PHIs in the exit block of the outer loop, outer's latch has been
   // replaced by Inners'.
   updateIncomingBlock(OuterLoopLatchSuccessor, OuterLoopLatch, InnerLoopLatch);
 
-  // Now update the reduction PHIs in the inner and outer loop headers.
-  SmallVector<PHINode *, 4> InnerLoopPHIs, OuterLoopPHIs;
-  for (PHINode &PHI : drop_begin(InnerLoopHeader->phis(), 1))
-    InnerLoopPHIs.push_back(cast<PHINode>(&PHI));
-  for (PHINode &PHI : drop_begin(OuterLoopHeader->phis(), 1))
-    OuterLoopPHIs.push_back(cast<PHINode>(&PHI));
-
-  for (PHINode *PHI : OuterLoopPHIs)
-    PHI->moveBefore(InnerLoopHeader->getFirstNonPHI());
-
-  // Move the PHI nodes from the inner loop header to the outer loop header.
-  // We have to deal with one kind of PHI nodes:
-  //  1) PHI nodes that are part of inner loop-only reductions.
-  // We only have to move the PHI node and update the incoming blocks.
-  for (PHINode *PHI : InnerLoopPHIs) {
-    PHI->moveBefore(OuterLoopHeader->getFirstNonPHI());
-    for (BasicBlock *InBB : PHI->blocks()) {
-      if (InnerLoop->contains(InBB))
-        continue;
-
-      assert(!isa<PHINode>(PHI->getIncomingValueForBlock(InBB)) &&
-             "Unexpected incoming PHI node, reductions in outer loop are not "
-             "supported yet");
-      PHI->replaceAllUsesWith(PHI->getIncomingValueForBlock(InBB));
-      PHI->eraseFromParent();
-      break;
-    }
-  }
+  // Make sure we have no other PHIs.
+  auto InnerPhis = drop_begin(InnerLoopHeader->phis(), 1);
+  auto OuterPhis = drop_begin(OuterLoopHeader->phis(), 1);
+  assert(begin(InnerPhis) == end(InnerPhis) && "Unexpected PHIs in inner loop");
+  assert(begin(OuterPhis) == end(OuterPhis) && "Unexpected PHis in outer loop");
 
   // Update the incoming blocks for moved PHI nodes.
   updateIncomingBlock(OuterLoopHeader, InnerLoopPreHeader, OuterLoopPreHeader);
   updateIncomingBlock(OuterLoopHeader, InnerLoopLatch, OuterLoopLatch);
   updateIncomingBlock(InnerLoopHeader, OuterLoopPreHeader, InnerLoopPreHeader);
   updateIncomingBlock(InnerLoopHeader, OuterLoopLatch, InnerLoopLatch);
 
   return true;

test/Transforms/LoopInterchange/inner-only-reductions.ll

+; RUN: opt < %s -basicaa -loop-interchange -pass-remarks-missed='loop-interchange' -pass-remarks-output=%t -S \
+; RUN:     -verify-dom-info -verify-loop-info 2>&1 | FileCheck -check-prefix=IR %s
+; RUN: FileCheck --input-file=%t %s
+
+; Inner loop only reductions are not supported currently. See discussion at
+; D53027 for more information on the required checks.
+
+@A = common global [500 x [500 x i32]] zeroinitializer
+@X = common global i32 0
+@B = common global [500 x [500 x i32]] zeroinitializer
+@Y = common global i32 0
+
+;; global X
+
+;;  for( int i=1;i<N;i++)
+;;    for( int j=1;j<N;j++)
+;;      X+=A[j][i];
+
+; CHECK: --- !Missed
+; CHECK-NEXT: Pass:            loop-interchange
+; CHECK-NEXT: Name:            UnsupportedPHI
+; CHECK-NEXT: Function:        reduction_01
+
+; IR-LABEL: @reduction_01(
+; IR-NOT: split
+
+define void @reduction_01(i32 %N) {
+entry:
+  %cmp16 = icmp sgt i32 %N, 1
+  br i1 %cmp16, label %for.body3.lr.ph, label %for.end8
+
+for.body3.lr.ph:                                  ; preds = %for.cond1.for.inc6_crit_edge, %entry
+  %indvars.iv18 = phi i64 [ %indvars.iv.next19, %for.cond1.for.inc6_crit_edge ], [ 1, %entry ]
+  %X.promoted = load i32, i32* @X
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body3, %for.body3.lr.ph
+  %indvars.iv = phi i64 [ 1, %for.body3.lr.ph ], [ %indvars.iv.next, %for.body3 ]
+  %add15 = phi i32 [ %X.promoted, %for.body3.lr.ph ], [ %add, %for.body3 ]
+  %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.body3
+
+for.cond1.for.inc6_crit_edge:                     ; preds = %for.body3
+  %add.lcssa = phi i32 [ %add, %for.body3 ]
+  store i32 %add.lcssa, 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.body3.lr.ph
+
+for.end8:                                         ; preds = %for.cond1.for.inc6_crit_edge, %entry
+  ret void
+}
+
+;; Not tightly nested. Do not interchange.
+;;  for( int i=1;i<N;i++)
+;;    for( int j=1;j<N;j++) {
+;;      for( int k=1;k<N;k++) {
+;;        X+=A[k][j];
+;;      }
+;;      Y+=B[j][i];
+;;    }
+
+;; Not tightly nested. Do not interchange.
+;; Not interchanged hence the phi's in the inner loop will not be split.
+
+; CHECK: --- !Missed
+; CHECK-NEXT: Pass:            loop-interchange
+; CHECK-NEXT: Name:            UnsupportedPHIOuter
+; CHECK-NEXT: Function:        reduction_03
+
+; IR-LABEL: @reduction_03(
+; IR-NOT: split
+
+define void @reduction_03(i32 %N) {
+entry:
+  %cmp35 = icmp sgt i32 %N, 1
+  br i1 %cmp35, label %for.cond4.preheader.lr.ph, label %for.end19
+
+for.cond4.preheader.lr.ph:                        ; preds = %for.cond1.for.inc17_crit_edge, %entry
+  %indvars.iv41 = phi i64 [ %indvars.iv.next42, %for.cond1.for.inc17_crit_edge ], [ 1, %entry ]
+  %Y.promoted = load i32, i32* @Y
+  br label %for.body6.lr.ph
+
+for.body6.lr.ph:                                  ; preds = %for.cond4.for.end_crit_edge, %for.cond4.preheader.lr.ph
+  %indvars.iv37 = phi i64 [ 1, %for.cond4.preheader.lr.ph ], [ %indvars.iv.next38, %for.cond4.for.end_crit_edge ]
+  %add1334 = phi i32 [ %Y.promoted, %for.cond4.preheader.lr.ph ], [ %add13, %for.cond4.for.end_crit_edge ]
+  %X.promoted = load i32, i32* @X
+  br label %for.body6
+
+for.body6:                                        ; preds = %for.body6, %for.body6.lr.ph
+  %indvars.iv = phi i64 [ 1, %for.body6.lr.ph ], [ %indvars.iv.next, %for.body6 ]
+  %arrayidx8 = getelementptr inbounds [500 x [500 x i32]], [500 x [500 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv37
+  %0 = load i32, i32* %arrayidx8
+  %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.cond4.for.end_crit_edge, label %for.body6
+
+for.cond4.for.end_crit_edge:                      ; preds = %for.body6
+  %arrayidx12 = getelementptr inbounds [500 x [500 x i32]], [500 x [500 x i32]]* @B, i64 0, i64 %indvars.iv37, i64 %indvars.iv41
+  %1 = load i32, i32* %arrayidx12
+  %add13 = add nsw i32 %add1334, %1
+  %indvars.iv.next38 = add nuw nsw i64 %indvars.iv37, 1
+  %lftr.wideiv39 = trunc i64 %indvars.iv.next38 to i32
+  %exitcond40 = icmp eq i32 %lftr.wideiv39, %N
+  br i1 %exitcond40, label %for.cond1.for.inc17_crit_edge, label %for.body6.lr.ph
+
+for.cond1.for.inc17_crit_edge:                    ; preds = %for.cond4.for.end_crit_edge
+  %add13.lcssa = phi i32 [ %add13, %for.cond4.for.end_crit_edge ]
+  store i32 %add13.lcssa, i32* @Y
+  %indvars.iv.next42 = add nuw nsw i64 %indvars.iv41, 1
+  %lftr.wideiv43 = trunc i64 %indvars.iv.next42 to i32
+  %exitcond44 = icmp eq i32 %lftr.wideiv43, %N
+  br i1 %exitcond44, label %for.end19, label %for.cond4.preheader.lr.ph
+
+for.end19:                                        ; preds = %for.cond1.for.inc17_crit_edge, %entry
+  ret void
+}

test/Transforms/LoopInterchange/lcssa.ll

for.body3:                                        ; preds = %for.body3, %outer.header
   %add = add nsw i32 %vA, %vC
   store i32 %add, i32* %ptr1
   %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:                                        ; preds = %for.body3, %outer.header
   %sv = phi i64 [ 0, %outer.header ], [ 1, %for.body3 ]
-  store i64 %sv, i64* %ptr
   %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:                                         ; preds = %outer.inc
   %sv.lcssa = phi i64 [ %sv, %outer.inc ]
   store i64 %sv.lcssa, i64* @Y
   br label %for.end16

test/Transforms/LoopInterchange/phi-ordering.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -loop-interchange -verify-dom-info -verify-loop-info -verify-scev -verify-loop-lcssa -S 2>&1 | FileCheck %s
+; RUN: opt < %s -loop-interchange -verify-dom-info -verify-loop-info -verify-scev -verify-loop-lcssa -loop-interchange-threshold=-1000 -S 2>&1 | FileCheck %s
 ;; Checks the order of the inner phi nodes does not cause havoc.
 ;; The inner loop has a reduction into c. The IV is not the first phi.
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
 target triple = "armv8--linux-gnueabihf"
 
 
 
 ; Function Attrs: norecurse nounwind
 define void @test(i32 %T, [90 x i32]* noalias nocapture %C, i16* noalias nocapture readonly %A, i16* noalias nocapture readonly %B) local_unnamed_addr #0 {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR3_PREHEADER:%.*]]
 ; CHECK:       for1.header.preheader:
 ; CHECK-NEXT:    br label [[FOR1_HEADER:%.*]]
 ; CHECK:       for1.header:
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INC20:%.*]], [[FOR1_INC19:%.*]] ], [ 0, [[FOR1_HEADER_PREHEADER:%.*]] ]
 ; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[I]], 90
 ; CHECK-NEXT:    br label [[FOR2_HEADER_PREHEADER:%.*]]
 ; CHECK:       for2.header.preheader:
 ; CHECK-NEXT:    br label [[FOR2_HEADER:%.*]]
 ; CHECK:       for2.header:
 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ [[INC17:%.*]], [[FOR2_INC16:%.*]] ], [ 0, [[FOR2_HEADER_PREHEADER]] ]
-; CHECK-NEXT:    [[ARRAYIDX14:%.*]] = getelementptr inbounds [90 x i32], [90 x i32]* [[C:%.*]], i32 [[I]], i32 [[J]]
-; CHECK-NEXT:    [[ARRAYIDX14_PROMOTED:%.*]] = load i32, i32* [[ARRAYIDX14]], align 4
 ; CHECK-NEXT:    br label [[FOR3_SPLIT1:%.*]]
 ; CHECK:       for3.preheader:
 ; CHECK-NEXT:    br label [[FOR3:%.*]]
 ; CHECK:       for3:
 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ [[INC:%.*]], [[FOR3_SPLIT:%.*]] ], [ 1, [[FOR3_PREHEADER]] ]
 ; CHECK-NEXT:    br label [[FOR1_HEADER_PREHEADER]]
 ; CHECK:       for3.split1:
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[K]], [[MUL]]
 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i16, i16* [[A:%.*]], i32 [[ADD]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i16, i16* [[ARRAYIDX]], align 2
-; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[TMP0]] to i32
-; CHECK-NEXT:    [[ADD15:%.*]] = add nsw i32 [[CONV]], [[ARRAYIDX14_PROMOTED]]
+; CHECK-NEXT:    [[ADD15:%.*]] = add nsw i16 [[TMP0]], 1
+; CHECK-NEXT:    store i16 [[ADD15]], i16* [[ARRAYIDX]]
 ; CHECK-NEXT:    br label [[FOR2_INC16]]
 ; CHECK:       for3.split:
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[K]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 90
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR1_LOOPEXIT:%.*]], label [[FOR3]]
 ; CHECK:       for2.inc16:
-; CHECK-NEXT:    store i32 [[ADD15]], i32* [[ARRAYIDX14]], align 4
 ; CHECK-NEXT:    [[INC17]] = add nuw nsw i32 [[J]], 1
 ; CHECK-NEXT:    [[EXITCOND47:%.*]] = icmp eq i32 [[INC17]], 90
 ; CHECK-NEXT:    br i1 [[EXITCOND47]], label [[FOR1_INC19]], label [[FOR2_HEADER]]
 ; CHECK:       for1.inc19:
 ; CHECK-NEXT:    [[INC20]] = add nuw nsw i32 [[I]], 1
 ; CHECK-NEXT:    [[EXITCOND48:%.*]] = icmp eq i32 [[INC20]], 90
 ; CHECK-NEXT:    br i1 [[EXITCOND48]], label [[FOR3_SPLIT]], label [[FOR1_HEADER]]
 ; CHECK:       for1.loopexit:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for1.header
 
 for1.header:                                  ; preds = %entry
   %i = phi i32 [ %inc20, %for1.inc19 ], [ 0, %entry ]
   %mul = mul nsw i32 %i, 90
   br label %for2.header
 
 for2.header:                                  ; preds = %for2.inc16, %for1.header
   %j = phi i32 [ 0, %for1.header ], [ %inc17, %for2.inc16 ]
-  %arrayidx14 = getelementptr inbounds [90 x i32], [90 x i32]* %C, i32 %i, i32 %j
-  %arrayidx14.promoted = load i32, i32* %arrayidx14, align 4
   br label %for3
 
 for3:                                        ; preds = %for3, %for2.header
-  %add1541 = phi i32 [ %arrayidx14.promoted, %for2.header ], [ %add15, %for3 ]
   %k = phi i32 [ 1, %for2.header ], [ %inc, %for3 ]
   %add = add nsw i32 %k, %mul
   %arrayidx = getelementptr inbounds i16, i16* %A, i32 %add
   %0 = load i16, i16* %arrayidx, align 2
-  %conv = sext i16 %0 to i32
-  %add15 = add nsw i32 %conv, %add1541
+  %add15 = add nsw i16 %0, 1
+  store i16 %add15, i16* %arrayidx
   %inc = add nuw nsw i32 %k, 1
   %exitcond = icmp eq i32 %inc, 90
   br i1 %exitcond, label %for2.inc16, label %for3
 
 for2.inc16:                                        ; preds = %for.body6
-  %add15.lcssa = phi i32 [ %add15, %for3 ]
-  store i32 %add15.lcssa, i32* %arrayidx14, align 4
   %inc17 = add nuw nsw i32 %j, 1
   %exitcond47 = icmp eq i32 %inc17, 90
   br i1 %exitcond47, label %for1.inc19, label %for2.header
 
 for1.inc19:                                        ; preds = %for2.inc16
   %inc20 = add nuw nsw i32 %i, 1
   %exitcond48 = icmp eq i32 %inc20, 90
   br i1 %exitcond48, label %for1.loopexit, label %for1.header
 
 for1.loopexit:                               ; preds = %for1.inc19
   br label %exit
 
 exit:                                        ; preds = %for1.loopexit
   ret void
 }

test/Transforms/LoopInterchange/reductions.ll

-; REQUIRES: asserts
-; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -verify-loop-info -verify-loop-lcssa -S -debug 2>&1 | FileCheck %s
-
-@A = common global [500 x [500 x i32]] zeroinitializer
-@X = common global i32 0
-@B = common global [500 x [500 x i32]] zeroinitializer
-@Y = common global i32 0
-
-;;  for( int i=1;i<N;i++)
-;;    for( int j=1;j<N;j++)
-;;      X+=A[j][i];
-
-;; Loop is interchanged check that the phi nodes are split and the promoted value is used instead of the reduction phi.
-; CHECK: Loops interchanged.
-
-define void @reduction_01(i32 %N) {
-entry:
-  %cmp16 = icmp sgt i32 %N, 1
-  br i1 %cmp16, label %for.body3.lr.ph, label %for.end8
-
-for.body3.lr.ph:                                  ; preds = %for.cond1.for.inc6_crit_edge, %entry
-  %indvars.iv18 = phi i64 [ %indvars.iv.next19, %for.cond1.for.inc6_crit_edge ], [ 1, %entry ]
-  %X.promoted = load i32, i32* @X
-  br label %for.body3
-
-for.body3:                                        ; preds = %for.body3, %for.body3.lr.ph
-  %indvars.iv = phi i64 [ 1, %for.body3.lr.ph ], [ %indvars.iv.next, %for.body3 ]
-  %add15 = phi i32 [ %X.promoted, %for.body3.lr.ph ], [ %add, %for.body3 ]
-  %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.body3
-
-for.cond1.for.inc6_crit_edge:                     ; preds = %for.body3
-  %add.lcssa = phi i32 [ %add, %for.body3 ]
-  store i32 %add.lcssa, 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.body3.lr.ph
-
-for.end8:                                         ; preds = %for.cond1.for.inc6_crit_edge, %entry
-  ret void
-}
-
-;; Test for more than 1 reductions inside a loop.
-;;  for( int i=1;i<N;i++)
-;;    for( int j=1;j<N;j++)
-;;      for( int k=1;k<N;k++) {
-;;        X+=A[k][j];
-;;        Y+=B[k][i];
-;;      }
-
-;; Loop is interchanged check that the phi nodes are split and the promoted value is used instead of the reduction phi.
-; CHECK: Loops interchanged.
-
-define void @reduction_02(i32 %N) {
-entry:
-  %cmp34 = icmp sgt i32 %N, 1
-  br i1 %cmp34, label %for.cond4.preheader.preheader, label %for.end19
-
-for.cond4.preheader.preheader:                    ; preds = %for.inc17, %entry
-  %indvars.iv40 = phi i64 [ %indvars.iv.next41, %for.inc17 ], [ 1, %entry ]
-  br label %for.body6.lr.ph
-
-for.body6.lr.ph:                                  ; preds = %for.cond4.for.inc14_crit_edge, %for.cond4.preheader.preheader
-  %indvars.iv36 = phi i64 [ %indvars.iv.next37, %for.cond4.for.inc14_crit_edge ], [ 1, %for.cond4.preheader.preheader ]
-  %X.promoted = load i32, i32* @X
-  %Y.promoted = load i32, i32* @Y
-  br label %for.body6
-
-for.body6:                                        ; preds = %for.body6, %for.body6.lr.ph
-  %indvars.iv = phi i64 [ 1, %for.body6.lr.ph ], [ %indvars.iv.next, %for.body6 ]
-  %add1331 = phi i32 [ %Y.promoted, %for.body6.lr.ph ], [ %add13, %for.body6 ]
-  %add30 = phi i32 [ %X.promoted, %for.body6.lr.ph ], [ %add, %for.body6 ]
-  %arrayidx8 = getelementptr inbounds [500 x [500 x i32]], [500 x [500 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv36
-  %0 = load i32, i32* %arrayidx8
-  %add = add nsw i32 %add30, %0
-  %arrayidx12 = getelementptr inbounds [500 x [500 x i32]], [500 x [500 x i32]]* @B, i64 0, i64 %indvars.iv, i64 %indvars.iv40
-  %1 = load i32, i32* %arrayidx12
-  %add13 = add nsw i32 %add1331, %1
-  %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.cond4.for.inc14_crit_edge, label %for.body6
-
-for.cond4.for.inc14_crit_edge:                    ; preds = %for.body6
-  %add.lcssa = phi i32 [ %add, %for.body6 ]
-  %add13.lcssa = phi i32 [ %add13, %for.body6 ]
-  store i32 %add.lcssa, i32* @X
-  store i32 %add13.lcssa, i32* @Y
-  %indvars.iv.next37 = add nuw nsw i64 %indvars.iv36, 1
-  %lftr.wideiv38 = trunc i64 %indvars.iv.next37 to i32
-  %exitcond39 = icmp eq i32 %lftr.wideiv38, %N
-  br i1 %exitcond39, label %for.inc17, label %for.body6.lr.ph
-
-for.inc17:                                        ; preds = %for.cond4.for.inc14_crit_edge
-  %add.lcssa.lcssa = phi i32 [ %add.lcssa, %for.cond4.for.inc14_crit_edge ]
-  %indvars.iv.next41 = add nuw nsw i64 %indvars.iv40, 1
-  %lftr.wideiv42 = trunc i64 %indvars.iv.next41 to i32
-  %exitcond43 = icmp eq i32 %lftr.wideiv42, %N
-  br i1 %exitcond43, label %for.end19, label %for.cond4.preheader.preheader
-
-for.end19:                                        ; preds = %for.inc17, %entry
-  %res1 = phi i32 [ 0, %entry ], [ %add.lcssa.lcssa, %for.inc17 ]
-  store i32 %res1, i32* @X
-  ret void
-}
-
-;; Not tightly nested. Do not interchange.
-;;  for( int i=1;i<N;i++)
-;;    for( int j=1;j<N;j++) {
-;;      for( int k=1;k<N;k++) {
-;;        X+=A[k][j];
-;;      }
-;;      Y+=B[j][i];
-;;    }
-
-;; Not tightly nested. Do not interchange.
-;; Not interchanged hence the phi's in the inner loop will not be split.
-; CHECK: Outer loops with reductions are not supported currently.
-
-define void @reduction_03(i32 %N) {
-entry:
-  %cmp35 = icmp sgt i32 %N, 1
-  br i1 %cmp35, label %for.cond4.preheader.lr.ph, label %for.end19
-
-for.cond4.preheader.lr.ph:                        ; preds = %for.cond1.for.inc17_crit_edge, %entry
-  %indvars.iv41 = phi i64 [ %indvars.iv.next42, %for.cond1.for.inc17_crit_edge ], [ 1, %entry ]
-  %Y.promoted = load i32, i32* @Y
-  br label %for.body6.lr.ph
-
-for.body6.lr.ph:                                  ; preds = %for.cond4.for.end_crit_edge, %for.cond4.preheader.lr.ph
-  %indvars.iv37 = phi i64 [ 1, %for.cond4.preheader.lr.ph ], [ %indvars.iv.next38, %for.cond4.for.end_crit_edge ]
-  %add1334 = phi i32 [ %Y.promoted, %for.cond4.preheader.lr.ph ], [ %add13, %for.cond4.for.end_crit_edge ]
-  %X.promoted = load i32, i32* @X
-  br label %for.body6
-
-for.body6:                                        ; preds = %for.body6, %for.body6.lr.ph
-  %indvars.iv = phi i64 [ 1, %for.body6.lr.ph ], [ %indvars.iv.next, %for.body6 ]
-  %add31 = phi i32 [ %X.promoted, %for.body6.lr.ph ], [ %add, %for.body6 ]
-  %arrayidx8 = getelementptr inbounds [500 x [500 x i32]], [500 x [500 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv37
-  %0 = load i32, i32* %arrayidx8
-  %add = add nsw i32 %add31, %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.cond4.for.end_crit_edge, label %for.body6
-
-for.cond4.for.end_crit_edge:                      ; preds = %for.body6
-  %add.lcssa = phi i32 [ %add, %for.body6 ]
-  store i32 %add.lcssa, i32* @X
-  %arrayidx12 = getelementptr inbounds [500 x [500 x i32]], [500 x [500 x i32]]* @B, i64 0, i64 %indvars.iv37, i64 %indvars.iv41
-  %1 = load i32, i32* %arrayidx12
-  %add13 = add nsw i32 %add1334, %1
-  %indvars.iv.next38 = add nuw nsw i64 %indvars.iv37, 1
-  %lftr.wideiv39 = trunc i64 %indvars.iv.next38 to i32
-  %exitcond40 = icmp eq i32 %lftr.wideiv39, %N
-  br i1 %exitcond40, label %for.cond1.for.inc17_crit_edge, label %for.body6.lr.ph
-
-for.cond1.for.inc17_crit_edge:                    ; preds = %for.cond4.for.end_crit_edge
-  %add13.lcssa = phi i32 [ %add13, %for.cond4.for.end_crit_edge ]
-  store i32 %add13.lcssa, i32* @Y
-  %indvars.iv.next42 = add nuw nsw i64 %indvars.iv41, 1
-  %lftr.wideiv43 = trunc i64 %indvars.iv.next42 to i32
-  %exitcond44 = icmp eq i32 %lftr.wideiv43, %N
-  br i1 %exitcond44, label %for.end19, label %for.cond4.preheader.lr.ph
-
-for.end19:                                        ; preds = %for.cond1.for.inc17_crit_edge, %entry
-  ret void
-}
-
-;; Multiple use of reduction not safe. Do not interchange.
-;;  for( int i=1;i<N;i++)
-;;    for( int j=1;j<N;j++)
-;;      for( int k=1;k<N;k++) {
-;;        X+=A[k][j];
-;;        Y+=X;
-;;      }
-
-;; Not interchanged hence the phi's in the inner loop will not be split.
-; CHECK: Only inner loops with induction or reduction PHI nodes are supported currently.
-
-define void @reduction_04(i32 %N) {
-entry:
-  %cmp28 = icmp sgt i32 %N, 1
-  br i1 %cmp28, label %for.cond4.preheader.preheader, label %for.end15
-
-for.cond4.preheader.preheader:                    ; preds = %for.inc13, %entry
-  %i.029 = phi i32 [ %inc14, %for.inc13 ], [ 1, %entry ]
-  br label %for.body6.lr.ph
-
-for.body6.lr.ph:                                  ; preds = %for.cond4.for.inc10_crit_edge, %for.cond4.preheader.preheader
-  %indvars.iv30 = phi i64 [ %indvars.iv.next31, %for.cond4.for.inc10_crit_edge ], [ 1, %for.cond4.preheader.preheader ]
-  %X.promoted = load i32, i32* @X
-  %Y.promoted = load i32, i32* @Y
-  br label %for.body6
-
-for.body6:                                        ; preds = %for.body6, %for.body6.lr.ph
-  %indvars.iv = phi i64 [ 1, %for.body6.lr.ph ], [ %indvars.iv.next, %for.body6 ]
-  %add925 = phi i32 [ %Y.promoted, %for.body6.lr.ph ], [ %add9, %for.body6 ]
-  %add24 = phi i32 [ %X.promoted, %for.body6.lr.ph ], [ %add, %for.body6 ]
-  %arrayidx8 = getelementptr inbounds [500 x [500 x i32]], [500 x [500 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv30
-  %0 = load i32, i32* %arrayidx8
-  %add = add nsw i32 %add24, %0
-  %add9 = add nsw i32 %add925, %add
-  %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.cond4.for.inc10_crit_edge, label %for.body6
-
-for.cond4.for.inc10_crit_edge:                    ; preds = %for.body6
-  %add.lcssa = phi i32 [ %add, %for.body6 ]
-  %add9.lcssa = phi i32 [ %add9, %for.body6 ]
-  store i32 %add.lcssa, i32* @X
-  store i32 %add9.lcssa, i32* @Y
-  %indvars.iv.next31 = add nuw nsw i64 %indvars.iv30, 1
-  %lftr.wideiv32 = trunc i64 %indvars.iv.next31 to i32
-  %exitcond33 = icmp eq i32 %lftr.wideiv32, %N
-  br i1 %exitcond33, label %for.inc13, label %for.body6.lr.ph
-
-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 = %for.cond1.for.inc6_crit_edge, %entry
-  %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
-  %add.lcssa = phi i32 [ %add, %for.body7 ]
-  store i32 %add.lcssa, 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.lcssa, %for.cond1.for.inc6_crit_edge ], [ 0, %entry ]
-  store i32 %add.res, i32* @Y
-  ret void
-}