[LoopInterchange] Support reductions across inner and outer loop.

[fhahn]

Summary

This patch adds logic to detect reductions across the inner and outer
loop by following the incoming values of PHI nodes in the outer loop. If
the incoming values take part in a reduction in the inner loop or come
from outside the outer loop, we found a reduction spanning across inner
and outer loop.

With this change, ~10% more loops are interchanged in the LLVM
test-suite + SPEC2006.

Fixes https://bugs.llvm.org/show_bug.cgi?id=30472

[fhahn]

Rebased, simplified and moved parts to D46198. This patch now only contains the code to detect reduction PHIs across inner and outer loops.

[fhahn]

ping

[fhahn]

Move PHI handling for reductions across inner and outer loop to this patch from D46198 and add an additional test case

[fhahn]

ping

[fhahn]

ping

[fhahn]

ping. I would very much appreciate any feedback on the overall approach of following LCSSA nodes and classification of PHI nodes across inner & outer loop. Maybe there is some existing infrastructure for that, which I missed?

[fhahn]

ping

[xbolva00]

In D43245#1187495, @fhahn wrote:

ping

@efriedma @hfinkel ?

Maybe you can try to write a RFC to llvm-dev

[fhahn]

In D43245#1195421, @xbolva00 wrote:

Maybe you can try to write a RFC to llvm-dev

I would be happy to write something, but I am not sure if that would make it easier to review this.

I think it is a fairly small change (thanks to Eli reviewing some patches leading up to this :)) and it would be great to get some feedback on whether this approach makes sense overall.

[fhahn]

ping :)

[efriedma]

lib/Transforms/Scalar/LoopInterchange.cpp

826

Given you're deleting this, is there some check that disallows interchanging if a PHI is a reduction in the outer loop, but not the inner loop? Something like:

for( int i=1;i<N;i++) {
  for( int j=1;j<N;j++) {
    A[i][j]++;
  }
  X += j;
}

1538–1539

one kind?

1557

Checking isa<PHINode>() here seems sort of confusing... is this supposed to be checking for a PHI node from the outer loop? If so, is there some guarantee it isn't a PHI node from somewhere else?

[fhahn]

Thanks Eli!

lib/Transforms/Scalar/LoopInterchange.cpp

826

Right! We should keep the check and could just not add PHIs across inner and outer loop there I think

1557

Yeah, it seems like inner loop reductions are not handled properly to start with. I will look into that first. It might be helpful to keep track of reduction/induction phis after the initial checks and use that info here (and other places, rather than recomputing)

[xbolva00]

How this patch now interacts with LoopInterchange as LoopPass?

[fhahn]

In D43245#1248907, @xbolva00 wrote:

How this patch now interacts with LoopInterchange as LoopPass?

The change to being a loop pass should not really impact this patch. It needs a small change to work with the preserved LCSSA phis now (which I have locally), but before updating the patch, I need to find some time to improve the PHI handling in general and address Eli's comment properly.

[fhahn]

Updated based on D53027, to keep sets PHIs that are part of inner loop only and across the inner and outer loop. This makes the checks during transform trivial. It also ensures that we do not deal with unclassified PHIs.

[fhahn]

Sorry for the delay Eli! I've restructured the code a bit to fix inner loop only reductions (D53027) and to keep 2 sets for reduction PHIs we can use to find out which kind of PHI we are dealing with.

lib/Transforms/Scalar/LoopInterchange.cpp

1557

The code now just checks OuterInnerReductions and InnerReductions.

[fhahn]

Updated after removing support for inner loop only reductions in D53027. The code is now slightly simpler. What do you think?

[fhahn]

lib/Transforms/Scalar/LoopInterchange.cpp

826

With the new structure, those kinds of loops are ruled out, because reductions in the outer loop need to have a corresponding reduction in the inner loop. I've added test/Transforms/LoopInterchange/outer-only-reductions.ll, which should show this case.

[fhahn]

ping. Eli it would be great if you could have another look now that the patch removing support for inner loop only reductions is committed and this patch is simpler.

[efriedma]

lib/Transforms/Scalar/LoopInterchange.cpp

785

I think "PHI.getNumIncomingValues() == 2" must be true? If it weren't true, it would imply the loop header had more than two predecessors (and I think you disallow that elsewhere).

[fhahn]

Turned check into assertion, added a comment explaining the if (!InnerLoop) {} block and another comment to findInductionAndReductions.

[fhahn]

lib/Transforms/Scalar/LoopInterchange.cpp

785

Yep, I turned it into an assertion.

[efriedma]

LGTM

[fhahn]

Thank you very much for all the reviews, 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; }
+  const SmallPtrSet<PHINode *, 4> &getInnerReductions() const {
+    return InnerReductions;
+  }
+
+  const SmallPtrSet<PHINode *, 4> &getOuterInnerReductions() const {
+    return OuterInnerReductions;
+  }
 
 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,
-                                  SmallPtrSet<PHINode *, 8> &Reductions);
+                                  Loop *InnerLoop);
 
   Loop *OuterLoop;
   Loop *InnerLoop;
 
   ScalarEvolution *SE;
 
   /// Interface to emit optimization remarks.
   OptimizationRemarkEmitter *ORE;
 
   bool InnerLoopHasReduction = false;
+
+  SmallPtrSet<PHINode *, 4> InnerReductions;
+  SmallPtrSet<PHINode *, 4> OuterInnerReductions;
 };
 
 /// LoopInterchangeProfitability checks if it is profitable to interchange the
 /// loop.
 class LoopInterchangeProfitability {
 public:
   LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
                                OptimizationRemarkEmitter *ORE)

 };
 
 /// LoopInterchangeTransform interchanges the loop.
 class LoopInterchangeTransform {
 public:
   LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
                            LoopInfo *LI, DominatorTree *DT,
                            BasicBlock *LoopNestExit,
-                           bool InnerLoopContainsReductions)
+                           const LoopInterchangeLegality &LIL)
       : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
-        LoopExit(LoopNestExit),
-        InnerLoopHasReduction(InnerLoopContainsReductions) {}
+        LoopExit(LoopNestExit), InnerReductions(LIL.getInnerReductions()),
+        OuterInnerReductions(LIL.getOuterInnerReductions()) {}
 
   /// 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;
+  SmallPtrSet<PHINode *, 4> InnerReductions;
+  SmallPtrSet<PHINode *, 4> OuterInnerReductions;
 };
 
 // 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());
+    LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, LoopNestExit,
+                                 LIL);
     LIT.transform();
     LLVM_DEBUG(dbgs() << "Loops interchanged.\n");
     LoopsInterchanged++;
     return true;
   }
 };
 
 } // end anonymous namespace
if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
             InnerLoopPreheader &&
         !OuterLoop->isLoopInvariant(I)) {
       return false;
     }
   }
   return true;
 }
 
+// If SV is a LCSSA PHI node with a single incoming value, return the incoming
+// value.
+static Value *followLCSSA(Value *SV) {
+  PHINode *PHI = dyn_cast<PHINode>(SV);
+  if (!PHI)
+    return SV;
+
+  if (PHI->getNumIncomingValues() != 1)
+    return SV;
+  return followLCSSA(PHI->getIncomingValue(0));
+}
+
+// Check V's users to see if it is involved in a reduction in L.
+static PHINode *findInnerReductionPhi(Loop *L, Value *V) {
+  for (Value *User : V->users()) {
+    if (PHINode *PHI = dyn_cast<PHINode>(User)) {
+      if (PHI->getNumIncomingValues() == 1)
+        continue;
+      RecurrenceDescriptor RD;
+      if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD))
+        return PHI;
+      return nullptr;
+    }
+  }
+
+  return nullptr;
+}
+
 bool LoopInterchangeLegality::findInductionAndReductions(
-    Loop *L, SmallVector<PHINode *, 8> &Inductions,
-    SmallPtrSet<PHINode *, 8> &Reductions) {
+    Loop *L, SmallVector<PHINode *, 8> &Inductions, Loop *InnerLoop) {
   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)) {
+    else if (!InnerLoop && RecurrenceDescriptor::isReductionPHI(&PHI, L, RD)) {
+      if (OuterInnerReductions.find(&PHI) != OuterInnerReductions.end())
+        return true;
       // Detect inner loop reductions across promoted values. We allow reduction
       // PHIs in the inner loop, if they have an incoming value, that is loaded
       // in the preheader and the result of the reduction is stored to the same
       // location in the exit block. Other uses of the reduction result outside
       // the outer loop are fine. We do not allow other stores in the inner
       // exit block, so there is no need to check for stores overwriting the
       // reduction result.
       int PHInd = PHI.getBasicBlockIndex(L->getLoopPreheader());
else if (!InnerLoop && RecurrenceDescriptor::isReductionPHI(&PHI, L, RD)) {
           }
         }
       }
 
       // Need both a load and a store to the same address.
       if (!LI || !SI || SI->getOperand(1) != LI->getOperand(0))
         return false;
 
-      Reductions.insert(&PHI);
+      InnerReductions.insert(&PHI);
+    } else if (InnerLoop && PHI.getNumIncomingValues() == 2) {
+      // Check if we have a PHI node in the outer loop that has a reduction
+      // result from the inner loop as an incoming value.
+      Value *V = followLCSSA(PHI.getIncomingValueForBlock(L->getLoopLatch()));
+      PHINode *InnerRedPhi = findInnerReductionPhi(InnerLoop, V);
+      if (!InnerRedPhi ||
+          !llvm::any_of(InnerRedPhi->incoming_values(),
+                        [&PHI](Value *V) { return V == &PHI; })) {
+        LLVM_DEBUG(
+            dbgs()
+            << "Failed to recognize PHI as an induction or reduction.\n");
+        return false;
+      }
+      OuterInnerReductions.insert(&PHI);
+      OuterInnerReductions.insert(InnerRedPhi);
     } else {
       LLVM_DEBUG(
           dbgs() << "Failed to recognize PHI as an induction or reduction.\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));
ORE->emit([&]() {
                 " interchange currently.";
     });
     return true;
   }
 
   PHINode *InnerInductionVar;
   SmallVector<PHINode *, 8> Inductions;
   SmallPtrSet<PHINode *, 8> Reductions;
-  if (!findInductionAndReductions(InnerLoop, Inductions, Reductions)) {
+
+  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(),
+                                      OuterLoop->getHeader())
+             << "Only outer loops with induction or reduction PHI nodes can be"
+                " interchanged 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())
+             << "Only outer loops with 1 induction variable can be "
+                "interchanged currently.";
+    });
+    return true;
+  }
+
+  Inductions.clear();
+  if (!findInductionAndReductions(InnerLoop, Inductions, nullptr)) {
     LLVM_DEBUG(
         dbgs() << "Only inner loops with induction or reduction PHI nodes on"
                   " promoted values 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)) {
-    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())
-             << "Only outer loops with 1 induction variable can be "
-                "interchanged currently.";
-    });
-    return true;
-  }
 
   // TODO: Triangular loops are not handled for now.
   if (!isLoopStructureUnderstood(InnerInductionVar)) {
     LLVM_DEBUG(dbgs() << "Loop structure not understood by pass\n");
     ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedStructureInner",
                                       InnerLoop->getStartLoc(),
                                       InnerLoop->getHeader())
bool LoopInterchangeTransform::adjustLoopBranches() {
   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.
+  // We have to deal with two kinds of PHI nodes:
+  //  1) PHI nodes that are part of a reduction in the outer loop
+  //  2) PHI nodes that are part of inner loop-only reductions.
+  // For 1) we only have to move the PHI node and update the incoming blocks.
+  // For 2) we can replace the PHI node with the value coming from outside the
   for (PHINode *PHI : InnerLoopPHIs) {
     PHI->moveBefore(OuterLoopHeader->getFirstNonPHI());
+    if (OuterInnerReductions.find(PHI) != OuterInnerReductions.end())
+      continue;
+    assert(InnerReductions.find(PHI) != InnerReductions.end() &&
+           "Unexpected PHI node!");
     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;
     }
   }
 
   // Update the incoming blocks for moved PHI nodes.
   updateIncomingBlock(OuterLoopHeader, InnerLoopPreHeader, OuterLoopPreHeader);
   updateIncomingBlock(OuterLoopHeader, InnerLoopLatch, OuterLoopLatch);

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:     -verify-dom-info -verify-loop-info -verify-loop-lcssa 2>&1 | FileCheck -check-prefix=IR %s
 ; RUN: FileCheck --input-file=%t %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: --- !Passed
 ; CHECK-NEXT: Pass:            loop-interchange
 ; CHECK-NEXT: Name:            Interchanged
 ; CHECK-NEXT: Function:        reduction_01
 
 ; IR-LABEL: @reduction_01(
 ; IR: for.body3.split
 

 ;; 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.
+;; Loop is interchanged check that the phi nodes are split and the promoted value is used instead of the reduction phi.
 
 ; CHECK: --- !Passed
 ; CHECK-NEXT: Pass:            loop-interchange
 ; CHECK-NEXT: Name:            Interchanged
 ; CHECK-NEXT: Function:        reduction_02
 
 ; IR-LABEL: @reduction_02(
 ; IR: for.body6.split

test/Transforms/LoopInterchange/lcssa.ll

-; RUN: opt < %s -basicaa -loop-interchange -pass-remarks-missed='loop-interchange' -verify-loop-lcssa -pass-remarks-output=%t
-; RUN: cat %t |  FileCheck --check-prefix REMARK %s
+; RUN: opt < %s -basicaa -loop-interchange -pass-remarks-missed='loop-interchange' -verify-loop-lcssa -pass-remarks-output=%t -S
+; RUN: FileCheck --input-file %t --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

test/Transforms/LoopInterchange/reductions-across-inner-and-outer-loop.ll

+; RUN: opt < %s -basicaa -loop-interchange -pass-remarks-missed='loop-interchange' -pass-remarks-output=%t -S \
+; RUN:     -verify-dom-info -verify-loop-info -verify-loop-lcssa -stats 2>&1 | FileCheck %s
+; RUN: FileCheck --input-file=%t --check-prefix=REMARKS %s
+
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; REMARKS: --- !Passed
+; REMARKS-NEXT: Pass:            loop-interchange
+; REMARKS-NEXT: Name:            Interchanged
+; REMARKS-NEXT: Function:        test1
+
+define i64 @test1([100 x [100 x i64]]* %Arr) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR2_PREHEADER:%.*]]
+; CHECK:       for1.header.preheader:
+; CHECK-NEXT:    br label [[FOR1_HEADER:%.*]]
+; CHECK:       for1.header:
+; CHECK-NEXT:    [[INDVARS_IV23:%.*]] = phi i64 [ [[INDVARS_IV_NEXT24:%.*]], [[FOR1_INC:%.*]] ], [ 0, [[FOR1_HEADER_PREHEADER:%.*]] ]
+; CHECK-NEXT:    [[SUM_INNER:%.*]] = phi i64 [ [[SUM_INC:%.*]], [[FOR1_INC]] ], [ [[SUM_OUTER:%.*]], [[FOR1_HEADER_PREHEADER]] ]
+; CHECK-NEXT:    br label [[FOR2_SPLIT1:%.*]]
+; CHECK:       for2.preheader:
+; CHECK-NEXT:    br label [[FOR2:%.*]]
+; CHECK:       for2:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT_3:%.*]], [[FOR2_SPLIT:%.*]] ], [ 0, [[FOR2_PREHEADER]] ]
+; CHECK-NEXT:    [[SUM_OUTER]] = phi i64 [ [[SUM_INC_LCSSA:%.*]], [[FOR2_SPLIT]] ], [ 0, [[FOR2_PREHEADER]] ]
+; CHECK-NEXT:    br label [[FOR1_HEADER_PREHEADER]]
+; CHECK:       for2.split1:
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* [[ARR:%.*]], i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV23]]
+; CHECK-NEXT:    [[LV:%.*]] = load i64, i64* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[SUM_INC]] = add i64 [[SUM_INNER]], [[LV]]
+; CHECK-NEXT:    br label [[FOR1_INC]]
+; CHECK:       for2.split:
+; CHECK-NEXT:    [[SUM_INC_LCSSA]] = phi i64 [ [[SUM_INC]], %for1.inc ]
+; CHECK-NEXT:    [[INDVARS_IV_NEXT_3]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[EXIT1:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT_3]], 100
+; CHECK-NEXT:    br i1 [[EXIT1]], label [[FOR1_LOOPEXIT:%.*]], label [[FOR2]]
+; CHECK:       for1.inc:
+; CHECK-NEXT:    [[INDVARS_IV_NEXT24]] = add nuw nsw i64 [[INDVARS_IV23]], 1
+; CHECK-NEXT:    [[EXIT2:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT24]], 100
+; CHECK-NEXT:    br i1 [[EXIT2]], label [[FOR2_SPLIT]], label [[FOR1_HEADER]]
+; CHECK:       for1.loopexit:
+; CHECK-NEXT:    [[SUM_INC_LCSSA2:%.*]] = phi i64 [ [[SUM_INC_LCSSA]], [[FOR2_SPLIT]] ]
+; CHECK-NEXT:    ret i64 [[SUM_INC_LCSSA2]]
+;
+entry:
+  br label %for1.header
+
+for1.header:                                         ; preds = %for1.inc, %entry
+  %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for1.inc ]
+  %sum.outer = phi i64 [ 0, %entry ], [ %sum.inc.lcssa, %for1.inc ]
+  br label %for2
+
+for2:                                        ; preds = %for2, %for1.header
+  %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %for2 ]
+  %sum.inner = phi i64 [ %sum.outer, %for1.header ], [ %sum.inc, %for2 ]
+  %arrayidx = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv23
+  %lv = load i64, i64* %arrayidx, align 4
+  %sum.inc = add i64 %sum.inner, %lv
+  %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
+  %exit1 = icmp eq i64 %indvars.iv.next.3, 100
+  br i1 %exit1, label %for1.inc, label %for2
+
+for1.inc:                                ; preds = %for2
+  %sum.inc.lcssa = phi i64 [ %sum.inc, %for2 ]
+  %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
+  %exit2 = icmp eq i64 %indvars.iv.next24, 100
+  br i1 %exit2, label %for1.loopexit, label %for1.header
+
+for1.loopexit:                                 ; preds = %for1.inc
+  %sum.inc.lcssa2 = phi i64 [ %sum.inc.lcssa, %for1.inc ]
+  ret i64 %sum.inc.lcssa2
+}
+
+; In this test case, the inner reduction PHI %inner does not involve the outer
+; reduction PHI %sum.outer, do not interchange.
+; REMARKS: --- !Missed
+; REMARKS-NEXT: Pass:            loop-interchange
+; REMARKS-NEXT: Name:            UnsupportedPHIOuter
+; REMARKS-NEXT: Function:        test2
+
+define i64 @test2([100 x [100 x i64]]* %Arr) {
+entry:
+  br label %for1.header
+
+for1.header:                                         ; preds = %for1.inc, %entry
+  %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for1.inc ]
+  %sum.outer = phi i64 [ 0, %entry ], [ %sum.inc.lcssa, %for1.inc ]
+  br label %for2
+
+for2:                                        ; preds = %for2, %for1.header
+  %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %for2 ]
+  %inner = phi i64 [ %indvars.iv23, %for1.header ], [ %sum.inc, %for2 ]
+  %arrayidx = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv23
+  %lv = load i64, i64* %arrayidx, align 4
+  %sum.inc = add i64 %inner, %lv
+  %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
+  %exit1 = icmp eq i64 %indvars.iv.next.3, 100
+  br i1 %exit1, label %for1.inc, label %for2
+
+for1.inc:                                ; preds = %for2
+  %sum.inc.lcssa = phi i64 [ %sum.inc, %for2 ]
+  %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
+  %exit2 = icmp eq i64 %indvars.iv.next24, 100
+  br i1 %exit2, label %for1.loopexit, label %for1.header
+
+for1.loopexit:                                 ; preds = %for1.inc
+  %sum.inc.lcssa2 = phi i64 [ %sum.inc.lcssa, %for1.inc ]
+  ret i64 %sum.inc.lcssa2
+}
+
+; Check that we do not interchange if there is an additional instruction
+; between the outer and inner reduction PHIs.
+; REMARKS: --- !Missed
+; REMARKS-NEXT: Pass:            loop-interchange
+; REMARKS-NEXT: Name:            UnsupportedPHIOuter
+; REMARKS-NEXT: Function:        test3
+
+define i64 @test3([100 x [100 x i64]]* %Arr) {
+entry:
+  br label %for1.header
+
+for1.header:                                         ; preds = %for1.inc, %entry
+  %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for1.inc ]
+  %sum.outer = phi i64 [ 0, %entry ], [ %sum.inc.lcssa, %for1.inc ]
+  %so = add i64 %sum.outer, 10
+  br label %for2
+
+for2:                                        ; preds = %for2, %for1.header
+  %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %for2 ]
+  %sum.inner = phi i64 [ %so, %for1.header ], [ %sum.inc, %for2 ]
+  %arrayidx = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv23
+  %lv = load i64, i64* %arrayidx, align 4
+  %sum.inc = add i64 %sum.inner, %lv
+  %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
+  %exit1 = icmp eq i64 %indvars.iv.next.3, 100
+  br i1 %exit1, label %for1.inc, label %for2
+
+for1.inc:                                ; preds = %for2
+  %sum.inc.lcssa = phi i64 [ %sum.inc, %for2 ]
+  %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
+  %exit2 = icmp eq i64 %indvars.iv.next24, 100
+  br i1 %exit2, label %for1.loopexit, label %for1.header
+
+for1.loopexit:                                 ; preds = %for1.inc
+  %sum.inc.lcssa2 = phi i64 [ %sum.inc.lcssa, %for1.inc ]
+  ret i64 %sum.inc.lcssa2
+}