[LoopInterchange] Enable loop interchange with multiple inner loop indvars

[congzhe]

Summary

This is a feature patch.

Currently loop interchange only supports loops with one inner loop induction variable. This patch adds support for transformation with more than one inner loop induction variables.

Related patch: https://reviews.llvm.org/D114916

[bmahjour]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

315

[nit] InnerInductionVar -> InnerInductionVars

622

suggestion: Inductions ->InnerInductions

670–672

suggestion: Value *V -> const Value *V

671–672

suggestion: use llvm::is_contained()

690

What if we have a loop condition like this:

for (...)
  for (; i < j; i++, j--)

I'm not sure if this would be legal to interchange (need to think about it more). I would have expected we return false if both left and right are functions of inner-ivs, to be conservatively correct.

Should have a test for this case also.

850–851

why do we need this copy?

1296

use llvm::is_contained()

1305

use llvm::is_contained()

1624

Why did we need to check OuterInnerReductions before and not anymore?

llvm/test/Transforms/LoopInterchange/interchangeable-innerloop-multiple-indvars.ll

17

The loop latch in the IR only uses one IV anyway, so can we simplify this to only use one IV for the condition?
Please also add a test where more than one IV is used in the latch.

[congzhe]

@bmahjour

Thanks for the review! While I am almost ready to post the next version that has attempted to address your comments, I found another piece of code that can be improved in interchange. It might be easier that I post that improvement patch first and rebase this patch.

To be specific, I'm thinking that the current limtation that there should be no instruction between induction variable increment and branch can be entirely removed. The limitation was there initially because we split the inner latch at the point of induction variable increment hence all instructions after induction variable increment will be moved to the block that is split. However, later the pass is improved such that we only split at the inner latch branch instruction and we properly move instructions to the new block as needed.

I'll do more testing and if it looks fine, I'll post a patch that removes that limitation. Removal of that limitation can also simplify this patch, that's why I'm thinking to post that first and rebase this patch.

[congzhe]

In D114917#3175486, @congzhe wrote:

@bmahjour

Thanks for the review! While I am almost ready to post the next version that has attempted to address your comments, I found another piece of code that can be improved in interchange. It might be easier that I post that improvement patch first and rebase this patch.

To be specific, I'm thinking that the current limtation that there should be no instruction between induction variable increment and branch can be entirely removed. The limitation was there initially because we split the inner latch at the point of induction variable increment hence all instructions after induction variable increment will be moved to the block that is split. However, later the pass is improved such that we only split at the inner latch branch instruction and we properly move instructions to the new block as needed.

I'll do more testing and if it looks fine, I'll post a patch that removes that limitation. Removal of that limitation can also simplify this patch, that's why I'm thinking to post that first and rebase this patch.

Posted https://reviews.llvm.org/D115238 that did what I mentioned above. I will update and rebase this patch on top of https://reviews.llvm.org/D115238.

[congzhe]

Comments addressed with minor refactoring

[congzhe]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

622

Thank you for the comment, the code is now refactored and this argument is not needed.
We'll use the member variable LoopInterchangeLegality::InnerLoopInductions directly in LoopInterchangeLegality::isLoopStructureUnderstood().

670–672

Thanks, updated accordingly.

671–672

Thanks, updated accordingly.

690

Thank you, after consideration I would propose this loop can be interchanged. I added a corresponding test case (test3 in /Transforms/LoopInterchange/interchangeable-innerloop-multiple-indvars.ll) that shows what the loop looks like after transformation.

Following the transformation steps in the pass, I would not think this loop is much of a difference -- the phi nodes of i and j will be split out from the inner header (and formed into the new outer header) and the indvar increments will be split out from the inner latch (and formed into the new outer latch).

850–851

The bulky removal starting from line 891 is from patch https://reviews.llvm.org/D115238.

It would be easier to just incorporate D115238 in this patch, meaning this patch will be rebased on top of D115238.

850–851

Thanks, InnerLoopInductions will be later used in the transformation phase, thus we keep a copy in class LoopInterchangeLegality and will use it later.

1296

Thanks, udpate accordingly.

1305

Thanks, udpate accordingly.

1624

Thanks, this is due to difference in downstream and upstream repos. I've updated as per upstream.

llvm/test/Transforms/LoopInterchange/interchangeable-innerloop-multiple-indvars.ll

17

Thanks, added what you suggested as test2() where all inner loop indvars are used in the inner latch.

I kept test1() as is, although we could simplify it to use one IV it would be serve as an example of multiple IVs anymore if I simplified it.

[congzhe]

The build bot test case failures are expected, and will be fixed after merging https://reviews.llvm.org/D115238.

[congzhe]

Patch updated:

1. Rebased on https://reviews.llvm.org/D115238.

2. Reworked on test cases to make them more canonical and more straightforward, by removing unnecessary instructions and variables, etc.

3. Created a new function findInductions() such that we initialize InnerLoopInductions early, hence removed a potential order constraint.

[congzhe]

Trival update in test cases.

[bmahjour]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

670–672

suggestion: rename to IsPathToInnerIndVar

llvm/test/Transforms/LoopInterchange/interchangeable-innerloop-multiple-indvars.ll

22

please add check lines for all the BBs to show the control flow....and please use CHECK-NEXT.

97

same comment as above

179

same comment as above

[congzhe]

Addressed comments: renamed to "isPathToInnerIndvar"; updated test cases by using "CHECK-NEXT".

[bmahjour]

LGTM

[congzhe]

Removed a function getInductionVariable() that becomes unused, in order to avoid build bot sanitizer failures.

getInductionVariable() becomes unused since we now use getInnerLoopInductions() to return the vector of inner indvars, instead of returning a single inner indvar from getInductionVariable().

Does it look fine to you? @bmahjour

[bmahjour]

In D114917#3242112, @congzhe wrote:

Removed a function getInductionVariable() that becomes unused, in order to avoid build bot sanitizer failures.

getInductionVariable() becomes unused since we now use getInnerLoopInductions() to return the vector of inner indvars, instead of returning a single inner indvar from getInductionVariable().

Does it look fine to you? @bmahjour

Yep, makes sense to remove it.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

while (!Vec->empty()) {
     LoopList.push_back(CurrentLoop);
     CurrentLoop = Vec->front();
     Vec = &CurrentLoop->getSubLoops();
   }
   LoopList.push_back(CurrentLoop);
   return LoopList;
 }
 
-static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) {
-  PHINode *InnerIndexVar = L->getCanonicalInductionVariable();
-  if (InnerIndexVar)
-    return InnerIndexVar;
-  if (L->getLoopLatch() == nullptr || L->getLoopPredecessor() == nullptr)
-    return nullptr;
-  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
-    PHINode *PhiVar = cast<PHINode>(I);
-    Type *PhiTy = PhiVar->getType();
-    if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
-        !PhiTy->isPointerTy())
-      return nullptr;
-    const SCEVAddRecExpr *AddRec =
-        dyn_cast<SCEVAddRecExpr>(SE->getSCEV(PhiVar));
-    if (!AddRec || !AddRec->isAffine())
-      continue;
-    const SCEV *Step = AddRec->getStepRecurrence(*SE);
-    if (!isa<SCEVConstant>(Step))
-      continue;
-    // Found the induction variable.
-    // FIXME: Handle loops with more than one induction variable. Note that,
-    // currently, legality makes sure we have only one induction variable.
-    return PhiVar;
-  }
-  return nullptr;
-}
-
 namespace {
 
 /// LoopInterchangeLegality checks if it is legal to interchange the loop.
 class LoopInterchangeLegality {
 public:
   LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
                           OptimizationRemarkEmitter *ORE)
       : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
 
   /// Check if the loops can be interchanged.
   bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
                            CharMatrix &DepMatrix);
 
+  /// Discover induction PHIs in the header of \p L. Induction
+  /// PHIs are added to \p Inductions.
+  bool findInductions(Loop *L, SmallVectorImpl<PHINode *> &Inductions);
+
   /// Check if the loop structure is understood. We do not handle triangular
   /// loops for now.
-  bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
+  bool isLoopStructureUnderstood();
 
   bool currentLimitations();
 
   const SmallPtrSetImpl<PHINode *> &getOuterInnerReductions() const {
     return OuterInnerReductions;
   }
 
+  const SmallVectorImpl<PHINode *> &getInnerLoopInductions() const {
+    return InnerLoopInductions;
+  }
+
 private:
   bool tightlyNested(Loop *Outer, Loop *Inner);
   bool containsUnsafeInstructions(BasicBlock *BB);
 
   /// Discover induction and reduction PHIs in the header of \p L. Induction
   /// PHIs are added to \p Inductions, reductions are added to
   /// OuterInnerReductions. When the outer loop is passed, the inner loop needs
   /// to be passed as \p InnerLoop.
   bool findInductionAndReductions(Loop *L,
                                   SmallVector<PHINode *, 8> &Inductions,
                                   Loop *InnerLoop);
 
   Loop *OuterLoop;
   Loop *InnerLoop;
 
   ScalarEvolution *SE;
 
   /// Interface to emit optimization remarks.
   OptimizationRemarkEmitter *ORE;
 
   /// Set of reduction PHIs taking part of a reduction across the inner and
   /// outer loop.
   SmallPtrSet<PHINode *, 4> OuterInnerReductions;
+
+  /// Set of inner loop induction PHIs
+  SmallVector<PHINode *, 8> InnerLoopInductions;
 };
 
 /// LoopInterchangeProfitability checks if it is profitable to interchange the
 /// loop.
 class LoopInterchangeProfitability {
 public:
   LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
                                OptimizationRemarkEmitter *ORE)
bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
   if (containsUnsafeInstructions(InnerLoopExit))
     return false;
 
   LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n");
   // We have a perfect loop nest.
   return true;
 }
 
-bool LoopInterchangeLegality::isLoopStructureUnderstood(
-    PHINode *InnerInduction) {
-  unsigned Num = InnerInduction->getNumOperands();
+bool LoopInterchangeLegality::isLoopStructureUnderstood() {
   BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
+  for (PHINode *InnerInduction : InnerLoopInductions) {
+    unsigned Num = InnerInduction->getNumOperands();
     for (unsigned i = 0; i < Num; ++i) {
       Value *Val = InnerInduction->getOperand(i);
       if (isa<Constant>(Val))
         continue;
       Instruction *I = dyn_cast<Instruction>(Val);
       if (!I)
         return false;
       // TODO: Handle triangular loops.
       // e.g. for(int i=0;i<N;i++)
       //        for(int j=i;j<N;j++)
       unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
       if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
               InnerLoopPreheader &&
           !OuterLoop->isLoopInvariant(I)) {
         return false;
       }
     }
+  }
 
   // TODO: Handle triangular loops of another form.
   // e.g. for(int i=0;i<N;i++)
   //        for(int j=0;j<i;j++)
   // or,
   //      for(int i=0;i<N;i++)
   //        for(int j=0;j*i<N;j++)
   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
if (CmpInst *InnerLoopCmp =
     // in "for(int j=0;j<i;j++)", LHS is j and RHS is i.
     Value *Left = nullptr;
     Value *Right = nullptr;
 
     // Check if V only involves inner loop induction variable.
     // Return true if V is InnerInduction, or a cast from
     // InnerInduction, or a binary operator that involves
     // InnerInduction and a constant.
-    std::function<bool(Value *)> IsPathToIndVar;
-    IsPathToIndVar = [&InnerInduction, &IsPathToIndVar](Value *V) -> bool {
-      if (V == InnerInduction)
+    std::function<bool(Value *)> IsPathToInnerIndVar;
+    IsPathToInnerIndVar = [this, &IsPathToInnerIndVar](const Value *V) -> bool {
+      if (llvm::is_contained(InnerLoopInductions, V))
         return true;
       if (isa<Constant>(V))
         return true;
-      Instruction *I = dyn_cast<Instruction>(V);
+      const Instruction *I = dyn_cast<Instruction>(V);
       if (!I)
         return false;
       if (isa<CastInst>(I))
-        return IsPathToIndVar(I->getOperand(0));
+        return IsPathToInnerIndVar(I->getOperand(0));
       if (isa<BinaryOperator>(I))
-        return IsPathToIndVar(I->getOperand(0)) &&
-               IsPathToIndVar(I->getOperand(1));
+        return IsPathToInnerIndVar(I->getOperand(0)) &&
+               IsPathToInnerIndVar(I->getOperand(1));
       return false;
     };
 
-    if (IsPathToIndVar(Op0) && !isa<Constant>(Op0)) {
+    // In case of multiple inner loop indvars, it is okay if LHS and RHS
+    // are both inner indvar related variables.
+    if (IsPathToInnerIndVar(Op0) && IsPathToInnerIndVar(Op1))
+      return true;
+
+    // Otherwise we check if the cmp instruction compares an inner indvar
+    // related variable (Left) with a outer loop invariant (Right).
+    if (IsPathToInnerIndVar(Op0) && !isa<Constant>(Op0)) {
       Left = Op0;
       Right = Op1;
-    } else if (IsPathToIndVar(Op1) && !isa<Constant>(Op1)) {
+    } else if (IsPathToInnerIndVar(Op1) && !isa<Constant>(Op1)) {
       Left = Op1;
       Right = Op0;
     }
 
     if (Left == nullptr)
       return false;
 
     const SCEV *S = SE->getSCEV(Right);
ORE->emit([&]() {
                                       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;
   if (!findInductionAndReductions(OuterLoop, Inductions, InnerLoop)) {
     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(),
ORE->emit([&]() {
                                       InnerLoop->getStartLoc(),
                                       InnerLoop->getHeader())
              << "Only inner loops with induction or reduction PHI nodes can be"
                 " interchange currently.";
     });
     return true;
   }
 
-  // TODO: Currently we handle only loops with 1 induction variable.
-  if (Inductions.size() != 1) {
-    LLVM_DEBUG(
-        dbgs() << "We currently only support loops with 1 induction variable."
-               << "Failed to interchange due to current limitation\n");
-    ORE->emit([&]() {
-      return OptimizationRemarkMissed(DEBUG_TYPE, "MultiInductionInner",
-                                      InnerLoop->getStartLoc(),
-                                      InnerLoop->getHeader())
-             << "Only inner loops with 1 induction variable can be "
-                "interchanged currently.";
-    });
-    return true;
-  }
-  InnerInductionVar = Inductions.pop_back_val();
-
   // TODO: Triangular loops are not handled for now.
-  if (!isLoopStructureUnderstood(InnerInductionVar)) {
+  if (!isLoopStructureUnderstood()) {
     LLVM_DEBUG(dbgs() << "Loop structure not understood by pass\n");
     ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedStructureInner",
                                       InnerLoop->getStartLoc(),
                                       InnerLoop->getHeader())
              << "Inner loop structure not understood currently.";
     });
     return true;
   }
 
   return false;
 }
 
+bool LoopInterchangeLegality::findInductions(
+    Loop *L, SmallVectorImpl<PHINode *> &Inductions) {
+  for (PHINode &PHI : L->getHeader()->phis()) {
+    InductionDescriptor ID;
+    if (InductionDescriptor::isInductionPHI(&PHI, L, SE, ID))
+      Inductions.push_back(&PHI);
+  }
+  return !Inductions.empty();
+}
+
 // We currently only support LCSSA PHI nodes in the inner loop exit, if their
 // users are either reduction PHIs or PHIs outside the outer loop (which means
 // the we are only interested in the final value after the loop).
 static bool
 areInnerLoopExitPHIsSupported(Loop *InnerL, Loop *OuterL,
                               SmallPtrSetImpl<PHINode *> &Reductions) {
   BasicBlock *InnerExit = OuterL->getUniqueExitBlock();
   for (PHINode &PHI : InnerExit->phis()) {
for (Instruction &I : BB->instructionsWithoutDebug())
                                           CI->getDebugLoc(),
                                           CI->getParent())
                  << "Cannot interchange loops due to call instruction.";
         });
 
         return false;
       }
 
+  if (!findInductions(InnerLoop, InnerLoopInductions)) {
+    LLVM_DEBUG(dbgs() << "Cound not find inner loop induction variables.\n");
+    return false;
+  }
+
   if (!areInnerLoopLatchPHIsSupported(OuterLoop, InnerLoop)) {
     LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in inner loop latch.\n");
     ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerLatchPHI",
                                       InnerLoop->getStartLoc(),
                                       InnerLoop->getHeader())
              << "Cannot interchange loops because unsupported PHI nodes found "
                 "in inner loop latch.";
void LoopInterchangeTransform::restructureLoops(
 
   // Tell SE that we move the loops around.
   SE->forgetLoop(NewOuter);
   SE->forgetLoop(NewInner);
 }
 
 bool LoopInterchangeTransform::transform() {
   bool Transformed = false;
-  Instruction *InnerIndexVar;
 
   if (InnerLoop->getSubLoops().empty()) {
     BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
     LLVM_DEBUG(dbgs() << "Splitting the inner loop latch\n");
-    PHINode *InductionPHI = getInductionVariable(InnerLoop, SE);
-    if (!InductionPHI) {
+    auto &InductionPHIs = LIL.getInnerLoopInductions();
+    if (InductionPHIs.empty()) {
       LLVM_DEBUG(dbgs() << "Failed to find the point to split loop latch \n");
       return false;
     }
 
-    if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
-      InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
+    SmallVector<Instruction *, 8> InnerIndexVarList;
+    for (PHINode *CurInductionPHI : InductionPHIs) {
+      if (CurInductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
+        InnerIndexVarList.push_back(
+            dyn_cast<Instruction>(CurInductionPHI->getIncomingValue(1)));
       else
-      InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0));
-
-    // Ensure that InductionPHI is the first Phi node.
-    if (&InductionPHI->getParent()->front() != InductionPHI)
-      InductionPHI->moveBefore(&InductionPHI->getParent()->front());
+        InnerIndexVarList.push_back(
+            dyn_cast<Instruction>(CurInductionPHI->getIncomingValue(0)));
+    }
 
     // Create a new latch block for the inner loop. We split at the
     // current latch's terminator and then move the condition and all
     // operands that are not either loop-invariant or the induction PHI into the
     // new latch block.
     BasicBlock *NewLatch =
         SplitBlock(InnerLoop->getLoopLatch(),
                    InnerLoop->getLoopLatch()->getTerminator(), DT, LI);
 
     SmallSetVector<Instruction *, 4> WorkList;
     unsigned i = 0;
-    auto MoveInstructions = [&i, &WorkList, this, InductionPHI, NewLatch]() {
+    auto MoveInstructions = [&i, &WorkList, this, &InductionPHIs, NewLatch]() {
       for (; i < WorkList.size(); i++) {
         // Duplicate instruction and move it the new latch. Update uses that
         // have been moved.
         Instruction *NewI = WorkList[i]->clone();
         NewI->insertBefore(NewLatch->getFirstNonPHI());
         assert(!NewI->mayHaveSideEffects() &&
                "Moving instructions with side-effects may change behavior of "
                "the loop nest!");
         for (Use &U : llvm::make_early_inc_range(WorkList[i]->uses())) {
           Instruction *UserI = cast<Instruction>(U.getUser());
           if (!InnerLoop->contains(UserI->getParent()) ||
-              UserI->getParent() == NewLatch || UserI == InductionPHI)
+              UserI->getParent() == NewLatch ||
+              llvm::is_contained(InductionPHIs, UserI))
             U.set(NewI);
         }
         // Add operands of moved instruction to the worklist, except if they are
         // outside the inner loop or are the induction PHI.
         for (Value *Op : WorkList[i]->operands()) {
           Instruction *OpI = dyn_cast<Instruction>(Op);
           if (!OpI ||
               this->LI->getLoopFor(OpI->getParent()) != this->InnerLoop ||
-              OpI == InductionPHI)
+              llvm::is_contained(InductionPHIs, OpI))
             continue;
           WorkList.insert(OpI);
         }
       }
     };
 
     // FIXME: Should we interchange when we have a constant condition?
     Instruction *CondI = dyn_cast<Instruction>(
         cast<BranchInst>(InnerLoop->getLoopLatch()->getTerminator())
             ->getCondition());
     if (CondI)
       WorkList.insert(CondI);
     MoveInstructions();
+    for (Instruction *InnerIndexVar : InnerIndexVarList)
       WorkList.insert(cast<Instruction>(InnerIndexVar));
     MoveInstructions();
 
     // Splits the inner loops phi nodes out into a separate basic block.
     BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
     SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI);
     LLVM_DEBUG(dbgs() << "splitting InnerLoopHeader done\n");
   }
 
bool LoopInterchangeTransform::adjustLoopBranches() {
   // replaced by Inners'.
   OuterLoopLatchSuccessor->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
 
   auto &OuterInnerReductions = LIL.getOuterInnerReductions();
   // Now update the reduction PHIs in the inner and outer loop headers.
   SmallVector<PHINode *, 4> InnerLoopPHIs, OuterLoopPHIs;
   for (PHINode &PHI : InnerLoopHeader->phis())
     if (OuterInnerReductions.contains(&PHI))
-      InnerLoopPHIs.push_back(cast<PHINode>(&PHI));
+      InnerLoopPHIs.push_back(&PHI);
+
   for (PHINode &PHI : OuterLoopHeader->phis())
     if (OuterInnerReductions.contains(&PHI))
       OuterLoopPHIs.push_back(&PHI);
 
   // Now move the remaining reduction PHIs from outer to inner loop header and
   // vice versa. The PHI nodes must be part of a reduction across the inner and
   // outer loop and all the remains to do is and updating the incoming blocks.
   for (PHINode *PHI : OuterLoopPHIs) {
     LLVM_DEBUG(dbgs() << "Outer loop reduction PHIs:\n"; PHI->dump(););
     PHI->moveBefore(InnerLoopHeader->getFirstNonPHI());
     assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node");
   }
   for (PHINode *PHI : InnerLoopPHIs) {
+    LLVM_DEBUG(dbgs() << "Inner loop reduction PHIs:\n"; PHI->dump(););
     PHI->moveBefore(OuterLoopHeader->getFirstNonPHI());
     assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node");
   }
 
   // Update the incoming blocks for moved PHI nodes.
   OuterLoopHeader->replacePhiUsesWith(InnerLoopPreHeader, OuterLoopPreHeader);
   OuterLoopHeader->replacePhiUsesWith(InnerLoopLatch, OuterLoopLatch);
   InnerLoopHeader->replacePhiUsesWith(OuterLoopPreHeader, InnerLoopPreHeader);

llvm/test/Transforms/LoopInterchange/interchangeable-innerloop-multiple-indvars.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -basic-aa -loop-interchange -verify-dom-info -verify-loop-info -verify-scev -verify-loop-lcssa -S | FileCheck %s
+
+@b = common dso_local local_unnamed_addr global [200 x [200 x i32]] zeroinitializer, align 4
+@a = common dso_local local_unnamed_addr global i32 0, align 4
+
+;; int a, c, d, e;
+;; int b[200][200];
+;; void fn1() {
+;;   for (c = 0; c < 100; c++) {
+;;     for (d = 5, e = 5; d > 0, e > 0; d--, e--)
+;;       a |= b[d][c + 9];
+;;   }
+;; }
+;
+; There are multiple inner loop indvars and only one
+; of them is used in the loop exit condition at the
+; inner loop latch.
+;
+define void @test1() {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    br label [[FOR_BODY3_PREHEADER:%.*]]
+; CHECK:       for.body.preheader:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[INDVARS_OUTER:%.*]] = phi i64 [ [[INDVARS_OUTER_NEXT:%.*]], [[FOR_INC7:%.*]] ], [ 0, [[FOR_BODY_PREHEADER:%.*]] ]
+; CHECK-NEXT:    [[OR_REDUCTION_INNER:%.*]] = phi i32 [ [[OR:%.*]], [[FOR_INC7]] ], [ [[OR_REDUCTION_OUTER:%.*]], [[FOR_BODY_PREHEADER]] ]
+; CHECK-NEXT:    [[INDEX:%.*]] = add nsw i64 [[INDVARS_OUTER]], 9
+; CHECK-NEXT:    br label [[FOR_BODY3_SPLIT1:%.*]]
+; CHECK:       for.body3.preheader:
+; CHECK-NEXT:    br label [[FOR_BODY3:%.*]]
+; CHECK:       for.body3:
+; CHECK-NEXT:    [[INDVAR0:%.*]] = phi i64 [ [[TMP0:%.*]], [[FOR_BODY3_SPLIT:%.*]] ], [ 5, [[FOR_BODY3_PREHEADER]] ]
+; CHECK-NEXT:    [[INDVAR1:%.*]] = phi i32 [ [[TMP1:%.*]], [[FOR_BODY3_SPLIT]] ], [ 5, [[FOR_BODY3_PREHEADER]] ]
+; CHECK-NEXT:    [[OR_REDUCTION_OUTER]] = phi i32 [ [[OR_LCSSA:%.*]], [[FOR_BODY3_SPLIT]] ], [ [[A]], [[FOR_BODY3_PREHEADER]] ]
+; CHECK-NEXT:    br label [[FOR_BODY_PREHEADER]]
+; CHECK:       for.body3.split1:
+; CHECK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds [200 x [200 x i32]], [200 x [200 x i32]]* @b, i64 0, i64 [[INDVAR0]], i64 [[INDEX]]
+; CHECK-NEXT:    [[LOAD_VAL:%.*]] = load i32, i32* [[ARRAYIDX5]], align 4
+; CHECK-NEXT:    [[OR]] = or i32 [[OR_REDUCTION_INNER]], [[LOAD_VAL]]
+; CHECK-NEXT:    [[INDVAR0_NEXT:%.*]] = add nsw i64 [[INDVAR0]], -1
+; CHECK-NEXT:    [[INDVAR1_NEXT:%.*]] = add nsw i32 [[INDVAR1]], -1
+; CHECK-NEXT:    [[TOBOOL2:%.*]] = icmp eq i32 [[INDVAR1_NEXT]], 0
+; CHECK-NEXT:    br label [[FOR_INC7]]
+; CHECK:       for.body3.split:
+; CHECK-NEXT:    [[OR_LCSSA]] = phi i32 [ [[OR]], [[FOR_INC7]] ]
+; CHECK-NEXT:    [[TMP0]] = add nsw i64 [[INDVAR0]], -1
+; CHECK-NEXT:    [[TMP1]] = add nsw i32 [[INDVAR1]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    br i1 [[TMP2]], label [[FOR_COND_FOR_END8_CRIT_EDGE:%.*]], label [[FOR_BODY3]]
+; CHECK:       for.inc7:
+; CHECK-NEXT:    [[INDVARS_OUTER_NEXT]] = add nsw i64 [[INDVARS_OUTER]], 1
+; CHECK-NEXT:    [[INDVARS_OUTER_NEXT_TRUNC:%.*]] = trunc i64 [[INDVARS_OUTER_NEXT]] to i32
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[INDVARS_OUTER_NEXT_TRUNC]], 100
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[FOR_BODY3_SPLIT]], label [[FOR_BODY]]
+; CHECK:       for.cond.for.end8_crit_edge:
+; CHECK-NEXT:    [[OR_LCSSA_LCSSA:%.*]] = phi i32 [ [[OR_LCSSA]], [[FOR_BODY3_SPLIT]] ]
+; CHECK-NEXT:    store i32 [[OR_LCSSA_LCSSA]], i32* @a, align 4
+; CHECK-NEXT:    br label [[FOR_END8:%.*]]
+; CHECK:       for.end8:
+; CHECK-NEXT:    ret void
+;
+
+entry:
+  %a = load i32, i32* @a
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.inc7
+  %indvars.outer = phi i64 [ 0, %entry ], [ %indvars.outer.next, %for.inc7 ]
+  %or.reduction.outer = phi i32 [ %a, %entry ], [ %or.lcssa, %for.inc7 ]
+  %index = add nsw i64 %indvars.outer, 9
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body, %for.body3
+  %or.reduction.inner = phi i32 [ %or.reduction.outer, %for.body ], [ %or, %for.body3 ]
+  %indvar0 = phi i64 [ 5, %for.body ], [ %indvar0.next, %for.body3 ]
+  %indvar1 = phi i32 [ 5, %for.body ], [ %indvar1.next, %for.body3 ]
+  %arrayidx5 = getelementptr inbounds [200 x [200 x i32]], [200 x [200 x i32]]* @b, i64 0, i64 %indvar0, i64 %index
+  %load.val = load i32, i32* %arrayidx5, align 4
+  %or = or i32 %or.reduction.inner, %load.val
+  %indvar0.next = add nsw i64 %indvar0, -1
+  %indvar1.next = add nsw i32 %indvar1, -1
+  %tobool2 = icmp eq i32 %indvar1.next, 0
+  br i1 %tobool2, label %for.inc7, label %for.body3
+
+for.inc7:                                         ; preds = %for.body3
+  %or.lcssa = phi i32 [ %or, %for.body3 ]
+  %indvars.outer.next = add nsw i64 %indvars.outer, 1
+  %indvars.outer.next.trunc = trunc i64 %indvars.outer.next to i32
+  %tobool = icmp eq i32 %indvars.outer.next.trunc, 100
+  br i1 %tobool, label %for.cond.for.end8_crit_edge, label %for.body
+
+for.cond.for.end8_crit_edge:                      ; preds = %for.inc7
+  %or.lcssa.lcssa = phi i32 [ %or.lcssa, %for.inc7 ]
+  store i32 %or.lcssa.lcssa, i32* @a
+  br label %for.end8
+
+for.end8:                                         ; preds = %for.cond.for.end8_crit_edge, %entry
+  ret void
+}
+
+;; int a, c, d, e;
+;; int b[200][200];
+;; void fn1() {
+;;   for (c = 0 ; c < 100; c++) {
+;;     for (d = 5, e = 6; d + e > 0; d--, e = e - 2)
+;;       a |= b[d][c + 9];
+;;   }
+;; }
+;
+; All inner loop indvars are used in the inner latch.
+;
+define void @test2() {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    br label [[FOR_BODY3_PREHEADER:%.*]]
+; CHECK:       for.body.preheader:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[INDVARS_OUTER:%.*]] = phi i64 [ [[INDVARS_OUTER_NEXT:%.*]], [[FOR_INC7:%.*]] ], [ 0, [[FOR_BODY_PREHEADER:%.*]] ]
+; CHECK-NEXT:    [[OR_REDUCTION_INNER:%.*]] = phi i32 [ [[OR:%.*]], [[FOR_INC7]] ], [ [[OR_REDUCTION_OUTER:%.*]], [[FOR_BODY_PREHEADER]] ]
+; CHECK-NEXT:    [[INDEX:%.*]] = add nsw i64 [[INDVARS_OUTER]], 9
+; CHECK-NEXT:    br label [[FOR_BODY3_SPLIT1:%.*]]
+; CHECK:       for.body3.preheader:
+; CHECK-NEXT:    br label [[FOR_BODY3:%.*]]
+; CHECK:       for.body3:
+; CHECK-NEXT:    [[INDVAR0:%.*]] = phi i64 [ [[TMP2:%.*]], [[FOR_BODY3_SPLIT:%.*]] ], [ 5, [[FOR_BODY3_PREHEADER]] ]
+; CHECK-NEXT:    [[INDVAR1:%.*]] = phi i32 [ [[TMP0:%.*]], [[FOR_BODY3_SPLIT]] ], [ 6, [[FOR_BODY3_PREHEADER]] ]
+; CHECK-NEXT:    [[OR_REDUCTION_OUTER]] = phi i32 [ [[OR_LCSSA:%.*]], [[FOR_BODY3_SPLIT]] ], [ [[A]], [[FOR_BODY3_PREHEADER]] ]
+; CHECK-NEXT:    br label [[FOR_BODY_PREHEADER]]
+; CHECK:       for.body3.split1:
+; CHECK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds [200 x [200 x i32]], [200 x [200 x i32]]* @b, i64 0, i64 [[INDVAR0]], i64 [[INDEX]]
+; CHECK-NEXT:    [[LOAD_VAL:%.*]] = load i32, i32* [[ARRAYIDX5]], align 4
+; CHECK-NEXT:    [[OR]] = or i32 [[OR_REDUCTION_INNER]], [[LOAD_VAL]]
+; CHECK-NEXT:    [[INDVAR0_NEXT:%.*]] = add nsw i64 [[INDVAR0]], -1
+; CHECK-NEXT:    [[INDVAR1_NEXT:%.*]] = add nsw i32 [[INDVAR1]], -2
+; CHECK-NEXT:    [[INDVAR1_NEXT_EXT:%.*]] = sext i32 [[INDVAR1_NEXT]] to i64
+; CHECK-NEXT:    [[INDVARS_ADD:%.*]] = add nsw i64 [[INDVAR0_NEXT]], [[INDVAR1_NEXT_EXT]]
+; CHECK-NEXT:    [[TOBOOL2:%.*]] = icmp eq i64 [[INDVARS_ADD]], 0
+; CHECK-NEXT:    br label [[FOR_INC7]]
+; CHECK:       for.body3.split:
+; CHECK-NEXT:    [[OR_LCSSA]] = phi i32 [ [[OR]], [[FOR_INC7]] ]
+; CHECK-NEXT:    [[TMP0]] = add nsw i32 [[INDVAR1]], -2
+; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[TMP0]] to i64
+; CHECK-NEXT:    [[TMP2]] = add nsw i64 [[INDVAR0]], -1
+; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i64 [[TMP2]], [[TMP1]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i64 [[TMP3]], 0
+; CHECK-NEXT:    br i1 [[TMP4]], label [[FOR_COND_FOR_END8_CRIT_EDGE:%.*]], label [[FOR_BODY3]]
+; CHECK:       for.inc7:
+; CHECK-NEXT:    [[INDVARS_OUTER_NEXT]] = add nsw i64 [[INDVARS_OUTER]], 1
+; CHECK-NEXT:    [[INDVARS_OUTER_NEXT_TRUNC:%.*]] = trunc i64 [[INDVARS_OUTER_NEXT]] to i32
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[INDVARS_OUTER_NEXT_TRUNC]], 100
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[FOR_BODY3_SPLIT]], label [[FOR_BODY]]
+; CHECK:       for.cond.for.end8_crit_edge:
+; CHECK-NEXT:    [[OR_LCSSA_LCSSA:%.*]] = phi i32 [ [[OR_LCSSA]], [[FOR_BODY3_SPLIT]] ]
+; CHECK-NEXT:    store i32 [[OR_LCSSA_LCSSA]], i32* @a, align 4
+; CHECK-NEXT:    br label [[FOR_END8:%.*]]
+; CHECK:       for.end8:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %a = load i32, i32* @a
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.inc7
+  %indvars.outer = phi i64 [ 0, %entry ], [ %indvars.outer.next, %for.inc7 ]
+  %or.reduction.outer = phi i32 [ %a, %entry ], [ %or.lcssa, %for.inc7 ]
+  %index = add nsw i64 %indvars.outer, 9
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body, %for.body3
+  %or.reduction.inner = phi i32 [ %or.reduction.outer, %for.body ], [ %or, %for.body3 ]
+  %indvar0 = phi i64 [ 5, %for.body ], [ %indvar0.next, %for.body3 ]
+  %indvar1 = phi i32 [ 6, %for.body ], [ %indvar1.next, %for.body3 ]
+  %arrayidx5 = getelementptr inbounds [200 x [200 x i32]], [200 x [200 x i32]]* @b, i64 0, i64 %indvar0, i64 %index
+  %load.val = load i32, i32* %arrayidx5, align 4
+  %or = or i32 %or.reduction.inner, %load.val
+  %indvar0.next = add nsw i64 %indvar0, -1
+  %indvar1.next = add nsw i32 %indvar1, -2
+  %indvar1.next.ext = sext i32 %indvar1.next to i64
+  %indvars.add = add nsw i64 %indvar0.next, %indvar1.next.ext
+  %tobool2 = icmp eq i64 %indvars.add, 0
+  br i1 %tobool2, label %for.inc7, label %for.body3
+
+for.inc7:                                         ; preds = %for.body3
+  %or.lcssa = phi i32 [ %or, %for.body3 ]
+  %indvars.outer.next = add nsw i64 %indvars.outer, 1
+  %indvars.outer.next.trunc = trunc i64 %indvars.outer.next to i32
+  %tobool = icmp eq i32 %indvars.outer.next.trunc, 100
+  br i1 %tobool, label %for.cond.for.end8_crit_edge, label %for.body
+
+for.cond.for.end8_crit_edge:                      ; preds = %for.inc7
+  %or.lcssa.lcssa = phi i32 [ %or.lcssa, %for.inc7 ]
+  store i32 %or.lcssa.lcssa, i32* @a
+  br label %for.end8
+
+for.end8:                                         ; preds = %for.cond.for.end8_crit_edge, %entry
+  ret void
+}
+
+;; int a, c, d, e;
+;; int b[200][200];
+;; void fn1() {
+;;   for (c = 0 ; c < 100; c++) {
+;;     d = 5;
+;;     e = 49;
+;;     for (; d != e; d++, e--)
+;;       a |= b[d][c + 9];
+;;   }
+;; }
+;
+; Two inner loop indvars are involved in the inner loop exit
+; condition as LHS and RHS.
+define void @test3() {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    br label [[FOR_BODY3_PREHEADER:%.*]]
+; CHECK:       for.body.preheader:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[INDVARS_OUTER:%.*]] = phi i64 [ [[INDVARS_OUTER_NEXT:%.*]], [[FOR_INC7:%.*]] ], [ 0, [[FOR_BODY_PREHEADER:%.*]] ]
+; CHECK-NEXT:    [[OR_REDUCTION_INNER:%.*]] = phi i32 [ [[OR:%.*]], [[FOR_INC7]] ], [ [[OR_REDUCTION_OUTER:%.*]], [[FOR_BODY_PREHEADER]] ]
+; CHECK-NEXT:    [[INDEX:%.*]] = add nsw i64 [[INDVARS_OUTER]], 9
+; CHECK-NEXT:    br label [[FOR_BODY3_SPLIT1:%.*]]
+; CHECK:       for.body3.preheader:
+; CHECK-NEXT:    br label [[FOR_BODY3:%.*]]
+; CHECK:       for.body3:
+; CHECK-NEXT:    [[INDVAR0:%.*]] = phi i32 [ [[TMP1:%.*]], [[FOR_BODY3_SPLIT:%.*]] ], [ 5, [[FOR_BODY3_PREHEADER]] ]
+; CHECK-NEXT:    [[INDVAR1:%.*]] = phi i32 [ [[TMP0:%.*]], [[FOR_BODY3_SPLIT]] ], [ 49, [[FOR_BODY3_PREHEADER]] ]
+; CHECK-NEXT:    [[OR_REDUCTION_OUTER]] = phi i32 [ [[OR_LCSSA:%.*]], [[FOR_BODY3_SPLIT]] ], [ [[A]], [[FOR_BODY3_PREHEADER]] ]
+; CHECK-NEXT:    br label [[FOR_BODY_PREHEADER]]
+; CHECK:       for.body3.split1:
+; CHECK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds [200 x [200 x i32]], [200 x [200 x i32]]* @b, i64 0, i32 [[INDVAR0]], i64 [[INDEX]]
+; CHECK-NEXT:    [[LOAD_VAL:%.*]] = load i32, i32* [[ARRAYIDX5]], align 4
+; CHECK-NEXT:    [[OR]] = or i32 [[OR_REDUCTION_INNER]], [[LOAD_VAL]]
+; CHECK-NEXT:    [[INDVAR0_NEXT:%.*]] = add nsw i32 [[INDVAR0]], 1
+; CHECK-NEXT:    [[INDVAR1_NEXT:%.*]] = add nsw i32 [[INDVAR1]], -1
+; CHECK-NEXT:    [[TOBOOL2:%.*]] = icmp eq i32 [[INDVAR0_NEXT]], [[INDVAR1_NEXT]]
+; CHECK-NEXT:    br label [[FOR_INC7]]
+; CHECK:       for.body3.split:
+; CHECK-NEXT:    [[OR_LCSSA]] = phi i32 [ [[OR]], [[FOR_INC7]] ]
+; CHECK-NEXT:    [[TMP0]] = add nsw i32 [[INDVAR1]], -1
+; CHECK-NEXT:    [[TMP1]] = add nsw i32 [[INDVAR0]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], [[TMP0]]
+; CHECK-NEXT:    br i1 [[TMP2]], label [[FOR_COND_FOR_END8_CRIT_EDGE:%.*]], label [[FOR_BODY3]]
+; CHECK:       for.inc7:
+; CHECK-NEXT:    [[INDVARS_OUTER_NEXT]] = add nsw i64 [[INDVARS_OUTER]], 1
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[INDVARS_OUTER_NEXT]], 100
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[FOR_BODY3_SPLIT]], label [[FOR_BODY]]
+; CHECK:       for.cond.for.end8_crit_edge:
+; CHECK-NEXT:    [[OR_LCSSA_LCSSA:%.*]] = phi i32 [ [[OR_LCSSA]], [[FOR_BODY3_SPLIT]] ]
+; CHECK-NEXT:    store i32 [[OR_LCSSA_LCSSA]], i32* @a, align 4
+; CHECK-NEXT:    br label [[FOR_END8:%.*]]
+; CHECK:       for.end8:
+; CHECK-NEXT:    ret void
+;
+
+entry:
+  %a = load i32, i32* @a
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.inc7
+  %indvars.outer = phi i64 [ 0, %entry ], [ %indvars.outer.next, %for.inc7 ]
+  %or.reduction.outer = phi i32 [ %a, %entry ], [ %or.lcssa, %for.inc7 ]
+  %index = add nsw i64 %indvars.outer, 9
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body, %for.body3
+  %or.reduction.inner = phi i32 [ %or.reduction.outer, %for.body ], [ %or, %for.body3 ]
+  %indvar0 = phi i32 [ 5, %for.body ], [ %indvar0.next, %for.body3 ]
+  %indvar1 = phi i32 [ 49, %for.body ], [ %indvar1.next, %for.body3 ]
+  %arrayidx5 = getelementptr inbounds [200 x [200 x i32]], [200 x [200 x i32]]* @b, i64 0, i32 %indvar0, i64 %index
+  %load.val = load i32, i32* %arrayidx5, align 4
+  %or = or i32 %or.reduction.inner, %load.val
+  %indvar0.next = add nsw i32 %indvar0, 1
+  %indvar1.next = add nsw i32 %indvar1, -1
+  %tobool2 = icmp eq i32 %indvar0.next, %indvar1.next
+  br i1 %tobool2, label %for.inc7, label %for.body3
+
+for.inc7:                                         ; preds = %for.body3
+  %or.lcssa = phi i32 [ %or, %for.body3 ]
+  %indvars.outer.next = add nsw i64 %indvars.outer, 1
+  %tobool = icmp eq i64 %indvars.outer.next, 100
+  br i1 %tobool, label %for.cond.for.end8_crit_edge, label %for.body
+
+for.cond.for.end8_crit_edge:                      ; preds = %for.inc7
+  %or.lcssa.lcssa = phi i32 [ %or.lcssa, %for.inc7 ]
+  store i32 %or.lcssa.lcssa, i32* @a
+  br label %for.end8
+
+for.end8:                                         ; preds = %for.cond.for.end8_crit_edge, %entry
+  ret void
+}