[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

815

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;
}

1483

one kind?

1498

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

815

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

1498

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

1498

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

815

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

762

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

762

Yep, I turned it into an assertion.

[efriedma]

LGTM

[fhahn]

Thank you very much for all the reviews, Eli!

lib/Transforms/Scalar/LoopInterchange.cpp

 
 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);
+                                  SmallVector<PHINode *, 8> &Reductions,
+                                  Loop *InnerLoop);
 
   Loop *OuterLoop;
   Loop *InnerLoop;
 
   ScalarEvolution *SE;
   LoopInfo *LI;
   DominatorTree *DT;
   bool PreserveLCSSA;
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)) {
+      RecurrenceDescriptor RD;
+      if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD))
+        return PHI;
+      return nullptr;
+    }
+  }
+
+  return nullptr;
+}
+
 bool LoopInterchangeLegality::findInductionAndReductions(
     Loop *L, SmallVector<PHINode *, 8> &Inductions,
-    SmallVector<PHINode *, 8> &Reductions) {
+    SmallVector<PHINode *, 8> &Reductions, Loop *InnerLoop) {
   if (!L->getLoopLatch() || !L->getLoopPredecessor())
     return false;
   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
     RecurrenceDescriptor RD;
     InductionDescriptor ID;
     PHINode *PHI = cast<PHINode>(I);
     if (InductionDescriptor::isInductionPHI(PHI, L, SE, ID))
       Inductions.push_back(PHI);
     else if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD))
       Reductions.push_back(PHI);
-    else {
+    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; })) {
+        DEBUG(
+            dbgs() << "Failed to recognize PHI as an induction or reduction.\n");
+        return false;
+      }
+      Reductions.push_back(PHI);
+    } else {
       DEBUG(
           dbgs() << "Failed to recognize PHI as an induction or reduction.\n");
       return false;
     }
   }
   return true;
 }
 
 static bool containsSafePHI(BasicBlock *Block, bool isOuterLoopExitBlock) {
   for (auto I = Block->begin(); isa<PHINode>(I); ++I) {
     PHINode *PHI = cast<PHINode>(I);
     // Reduction lcssa phi will have only 1 incoming block that from loop latch.
     if (PHI->getNumIncomingValues() > 1)
       return false;
ORE->emit([&]() {
                 " interchange currently.";
     });
     return true;
   }
 
   PHINode *InnerInductionVar;
   SmallVector<PHINode *, 8> Inductions;
   SmallVector<PHINode *, 8> Reductions;
-  if (!findInductionAndReductions(InnerLoop, Inductions, Reductions)) {
+  if (!findInductionAndReductions(InnerLoop, Inductions, Reductions, nullptr)) {
     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"
                 " interchange currently.";
if (Inductions.size() != 1) {
     });
     return true;
   }
   if (Reductions.size() > 0)
     InnerLoopHasReduction = true;
 
   InnerInductionVar = Inductions.pop_back_val();
   Reductions.clear();
-  if (!findInductionAndReductions(OuterLoop, Inductions, Reductions)) {
+  if (!findInductionAndReductions(OuterLoop, Inductions, Reductions,
+                                  InnerLoop)) {
     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()) {
-    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) {
     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())
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 2 different kind 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
   //  inner loop.
   for (PHINode *PHI : InnerLoopPHIs) {
     PHI->moveBefore(OuterLoopHeader->getFirstNonPHI());
     for (BasicBlock *InBB : PHI->blocks()) {
       if (InnerLoop->contains(InBB) ||
           isa<PHINode>(PHI->getIncomingValueForBlock(InBB)))
         continue;
 
       PHI->replaceAllUsesWith(PHI->getIncomingValueForBlock(InBB));
       PHI->eraseFromParent();
       break;
     }
   }
 
   // Update the incoming blocks for moved PHI nodes.
   updateIncomingBlock(OuterLoopHeader, InnerLoopPreHeader, OuterLoopPreHeader);
   updateIncomingBlock(OuterLoopHeader, InnerLoopLatch, OuterLoopLatch);
   updateIncomingBlock(InnerLoopHeader, OuterLoopPreHeader, InnerLoopPreHeader);
   updateIncomingBlock(InnerLoopHeader, OuterLoopLatch, InnerLoopLatch);

test/Transforms/LoopInterchange/lcssa.ll

-; RUN: opt < %s -basicaa -loop-interchange -pass-remarks-missed='loop-interchange' -pass-remarks-output=%t
-; RUN: cat %t |  FileCheck --check-prefix REMARK %s
+; RUN: opt < %s -basicaa -loop-interchange -pass-remarks-missed='loop-interchange' -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 -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]], [[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:    [[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]], [[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
+}

test/Transforms/LoopInterchange/reductions.ll

-; REQUIRES: asserts
-; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -verify-loop-info -S -debug 2>&1 | FileCheck %s
+; 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
 
 @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.
+
+; CHECK: --- !Passed
+; CHECK-NEXT: Pass:            loop-interchange
+; CHECK-NEXT: Name:            Interchanged
+; CHECK-NEXT: Function:        reduction_01
+
+; IR-LABEL: @reduction_01(
+; IR: for.body3.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 = %entry, %for.cond1.for.inc6_crit_edge
   %indvars.iv18 = phi i64 [ %indvars.iv.next19, %for.cond1.for.inc6_crit_edge ], [ 1, %entry ]

 ;;  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.
+
+; CHECK: --- !Passed
+; CHECK-NEXT: Pass:            loop-interchange
+; CHECK-NEXT: Name:            Interchanged
+; CHECK-NEXT: Function:        reduction_02
+
+; IR-LABEL: @reduction_02(
+; IR: for.body6.split
 
 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 = %entry, %for.inc17
   %indvars.iv40 = phi i64 [ %indvars.iv.next41, %for.inc17 ], [ 1, %entry ]

 ;;      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.
+
+; CHECK: --- !Missed
+; CHECK-NEXT: Pass:            loop-interchange
+; CHECK-NEXT: Name:            NotTightlyNested
+; 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 = %entry, %for.cond1.for.inc17_crit_edge
   %indvars.iv41 = phi i64 [ %indvars.iv.next42, %for.cond1.for.inc17_crit_edge ], [ 1, %entry ]

 ;;  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.
+
+; CHECK: --- !Missed
+; CHECK-NEXT: Pass:            loop-interchange
+; CHECK-NEXT: Name:            UnsupportedPHI
+; CHECK-NEXT: Function:        reduction_04
 
 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 = %entry, %for.inc13
   %i.029 = phi i32 [ %inc14, %for.inc13 ], [ 1, %entry ]

 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.
+
+; CHECK: --- !Passed
+; CHECK-NEXT: Pass:            loop-interchange
+; CHECK-NEXT: Name:            Interchanged
+; CHECK-NEXT: Function:        reduction_05
+
+; IR-LABEL: @reduction_05(
+; IR: for.body7.split
+
 define void @reduction_05(i32 %N) {
 entry:
   %cmp16 = icmp sgt i32 %N, 1
   br i1 %cmp16, label %for.body7.lr.ph, label %for.end8
 
 for.body7.lr.ph:                                  ; preds = %entry, %for.cond1.for.inc6_crit_edge
   %indvars.iv18 = phi i64 [ %indvars.iv.next19, %for.cond1.for.inc6_crit_edge ], [ 1, %entry ]
   %X.promoted = load i32, i32* @X