Index: lib/Transforms/Scalar/LoopInterchange.cpp
===================================================================
--- lib/Transforms/Scalar/LoopInterchange.cpp
+++ lib/Transforms/Scalar/LoopInterchange.cpp
@@ -555,12 +555,6 @@
     else
       LoopNestExit = OuterMostLoopLatchBI->getSuccessor(0);
 
-    if (isa<PHINode>(LoopNestExit->begin())) {
-      DEBUG(dbgs() << "PHI Nodes in loop nest exit is not handled for now "
-                      "since on failure all loops branch to loop nest exit.\n");
-      return false;
-    }
-
     unsigned SelecLoopId = selectLoopForInterchange(LoopList);
     // Move the selected loop outwards to the best possible position.
     for (unsigned i = SelecLoopId; i > 0; i--) {
@@ -771,8 +765,6 @@
   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
-  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
-  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
 
   PHINode *InnerInductionVar;
   SmallVector<PHINode *, 8> Inductions;
@@ -863,20 +855,7 @@
 
   // TODO: We only handle LCSSA PHI's corresponding to reduction for now.
   BasicBlock *LoopExitBlock =
-      getLoopLatchExitBlock(OuterLoopLatch, OuterLoopHeader);
-  if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, true)) {
-    DEBUG(dbgs() << "Can only handle LCSSA PHIs in outer loops currently.\n");
-    ORE->emit([&]() {
-      return OptimizationRemarkMissed(DEBUG_TYPE, "NoLCSSAPHIOuter",
-                                      OuterLoop->getStartLoc(),
-                                      OuterLoop->getHeader())
-             << "Only outer loops with LCSSA PHIs can be interchange "
-                "currently.";
-    });
-    return true;
-  }
-
-  LoopExitBlock = getLoopLatchExitBlock(InnerLoopLatch, InnerLoopHeader);
+      getLoopLatchExitBlock(InnerLoopLatch, InnerLoopHeader);
   if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, false)) {
     DEBUG(dbgs() << "Can only handle LCSSA PHIs in inner loops currently.\n");
     ORE->emit([&]() {
@@ -962,6 +941,33 @@
   return false;
 }
 
+// We currently support PHI nodes in the outer loop exit, if their incoming
+// values either
+// * come from outside the outer loop
+// * come from the inner loop, ignoring LCSSA PHI nodes.
+// In the latter case, the value from the inner loop will only be available
+// if both outer and inner loop conditions are true, which will still be true
+// after interchanging.
+static bool areLoopExitPHIsSupported(Loop *OuterLoop, Loop *InnerLoop) {
+  BasicBlock *LoopNestExit = OuterLoop->getUniqueExitBlock();
+  for (PHINode &PHI : LoopNestExit->phis()) {
+    for (unsigned i = 0; i < PHI.getNumIncomingValues(); i++) {
+      if (!OuterLoop->contains(PHI.getIncomingBlock(i)))
+        continue;
+
+      PHINode *LatchPHI = dyn_cast<PHINode>(PHI.getIncomingValue(i));
+      if (!LatchPHI || LatchPHI->getParent() != OuterLoop->getLoopLatch() ||
+          LatchPHI->getNumIncomingValues() != 1)
+        return false;
+
+      Instruction *LV = dyn_cast<Instruction>(LatchPHI->getIncomingValue(0));
+      if (!LV || !InnerLoop->contains(LV->getParent()))
+        return false;
+    }
+  }
+  return true;
+}
+
 bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
                                                   unsigned OuterLoopId,
                                                   CharMatrix &DepMatrix) {
@@ -1032,6 +1038,17 @@
     return false;
   }
 
+  if (!areLoopExitPHIsSupported(OuterLoop, InnerLoop)) {
+    DEBUG(dbgs() << "Found unsupported PHI nodes in outer loop exit.\n");
+    ORE->emit([&]() {
+      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
+                                      OuterLoop->getStartLoc(),
+                                      OuterLoop->getHeader())
+             << "Found unsupported PHI node in loop exit.";
+    });
+    return false;
+  }
+
   return true;
 }
 
Index: test/Transforms/LoopInterchange/current-limitations-lcssa.ll
===================================================================
--- test/Transforms/LoopInterchange/current-limitations-lcssa.ll
+++ /dev/null
@@ -1,76 +0,0 @@
-; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
-;; We test the complete .ll for adjustment in outer loop header/latch and inner loop header/latch.
-
-target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
-target triple = "x86_64-unknown-linux-gnu"
-
-@A = common global [100 x [100 x i32]] zeroinitializer
-@C = common global [100 x [100 x i32]] zeroinitializer
-
-;; FIXME:
-;; Test for interchange when we have an lcssa phi. This should ideally be interchanged but it is currently not supported.
-;;     for(gi=1;gi<N;gi++)
-;;       for(gj=1;gj<M;gj++)
-;;         A[gj][gi] = A[gj - 1][gi] + C[gj][gi];
-
-@gi = common global i32 0
-@gj = common global i32 0
-
-define void @interchange_07(i32 %N, i32 %M){
-entry:
-  store i32 1, i32* @gi
-  %cmp21 = icmp sgt i32 %N, 1
-  br i1 %cmp21, label %for.cond1.preheader.lr.ph, label %for.end16
-
-for.cond1.preheader.lr.ph:
-  %cmp218 = icmp sgt i32 %M, 1
-  %gi.promoted = load i32, i32* @gi
-  %0 = add i32 %M, -1
-  %1 = sext i32 %gi.promoted to i64
-  %2 = sext i32 %N to i64
-  %3 = add i32 %gi.promoted, 1
-  %4 = icmp slt i32 %3, %N
-  %smax = select i1 %4, i32 %N, i32 %3
-  br label %for.cond1.preheader
-
-for.cond1.preheader:
-  %indvars.iv25 = phi i64 [ %1, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next26, %for.inc14 ]
-  br i1 %cmp218, label %for.body3, label %for.inc14
-
-for.body3:
-  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 1, %for.cond1.preheader ]
-  %5 = add nsw i64 %indvars.iv, -1
-  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %5, i64 %indvars.iv25
-  %6 = load i32, i32* %arrayidx5
-  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %indvars.iv, i64 %indvars.iv25
-  %7 = load i32, i32* %arrayidx9
-  %add = add nsw i32 %7, %6
-  %arrayidx13 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv25
-  store i32 %add, i32* %arrayidx13
-  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
-  %lftr.wideiv = trunc i64 %indvars.iv to i32
-  %exitcond = icmp eq i32 %lftr.wideiv, %0
-  br i1 %exitcond, label %for.inc14, label %for.body3
-
-for.inc14:
-  %inc.lcssa23 = phi i32 [ 1, %for.cond1.preheader ], [ %M, %for.body3 ]
-  %indvars.iv.next26 = add nsw i64 %indvars.iv25, 1
-  %cmp = icmp slt i64 %indvars.iv.next26, %2
-  br i1 %cmp, label %for.cond1.preheader, label %for.cond.for.end16_crit_edge
-
-for.cond.for.end16_crit_edge:
-  store i32 %inc.lcssa23, i32* @gj
-  store i32 %smax, i32* @gi
-  br label %for.end16
-
-for.end16:
-  ret void
-}
-
-; CHECK-LABEL: @interchange_07
-; CHECK: for.body3:                                        ; preds = %for.body3.preheader, %for.body3
-; CHECK:   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 1, %for.body3.preheader ]
-; CHECK:   %5 = add nsw i64 %indvars.iv, -1
-; CHECK:   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %5, i64 %indvars.iv25
-; CHECK:   %6 = load i32, i32* %arrayidx5
-; CHECK:   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %indvars.iv, i64 %indvars.iv25
Index: test/Transforms/LoopInterchange/lcssa.ll
===================================================================
--- /dev/null
+++ test/Transforms/LoopInterchange/lcssa.ll
@@ -0,0 +1,125 @@
+; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
+;; We test the complete .ll for adjustment in outer loop header/latch and inner loop header/latch.
+
+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 i32 0
+
+;; FIXME:
+;; Test for interchange when we have an lcssa phi. This should ideally be interchanged but it is currently not supported.
+;;     for(gi=1;gi<N;gi++)
+;;       for(gj=1;gj<M;gj++)
+;;         A[gj][gi] = A[gj - 1][gi] + C[gj][gi];
+
+@gi = common global i32 0
+@gj = common global i32 0
+
+define void @lcssa_01(i32 %N, i32 %M){
+entry:
+  store i32 1, i32* @gi
+  %cmp21 = icmp sgt i32 %N, 1
+  br i1 %cmp21, label %for.cond1.preheader.lr.ph, label %for.end16
+
+for.cond1.preheader.lr.ph:
+  %cmp218 = icmp sgt i32 %M, 1
+  %gi.promoted = load i32, i32* @gi
+  %0 = add i32 %M, -1
+  %1 = sext i32 %gi.promoted to i64
+  %2 = sext i32 %N to i64
+  %3 = add i32 %gi.promoted, 1
+  %4 = icmp slt i32 %3, %N
+  %smax = select i1 %4, i32 %N, i32 %3
+  br label %for.cond1.preheader
+
+for.cond1.preheader:
+  %indvars.iv25 = phi i64 [ %1, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next26, %for.inc14 ]
+  br i1 %cmp218, label %for.body3, label %for.inc14
+
+for.body3:
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 1, %for.cond1.preheader ]
+  %5 = add nsw i64 %indvars.iv, -1
+  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %5, i64 %indvars.iv25
+  %6 = load i32, i32* %arrayidx5
+  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %indvars.iv, i64 %indvars.iv25
+  %7 = load i32, i32* %arrayidx9
+  %add = add nsw i32 %7, %6
+  %arrayidx13 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv25
+  store i32 %add, i32* %arrayidx13
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %0
+  br i1 %exitcond, label %for.inc14, label %for.body3
+
+for.inc14:
+  %inc.lcssa23 = phi i32 [ 1, %for.cond1.preheader ], [ %M, %for.body3 ]
+  %indvars.iv.next26 = add nsw i64 %indvars.iv25, 1
+  %cmp = icmp slt i64 %indvars.iv.next26, %2
+  br i1 %cmp, label %for.cond1.preheader, label %for.cond.for.end16_crit_edge
+
+for.cond.for.end16_crit_edge:
+  store i32 %inc.lcssa23, i32* @gj
+  store i32 %smax, i32* @gi
+  br label %for.end16
+
+for.end16:
+  ret void
+}
+; CHECK-LABEL: @lcssa_01
+; CHECK: for.body3:                                        ; preds = %for.body3.preheader, %for.body3
+; CHECK:   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 1, %for.body3.preheader ]
+; CHECK:   %5 = add nsw i64 %indvars.iv, -1
+; CHECK:   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %5, i64 %indvars.iv25
+; CHECK:   %6 = load i32, i32* %arrayidx5
+; CHECK:   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %indvars.iv, i64 %indvars.iv25
+
+; In this test case, the value %X.to.save used in the outer loop exit is
+; created in the outer loop latch. Currently we do not support this case, as
+; after interchanging, the outer loop latch is only executed if the inner loop
+; condition is true.
+define void @lcssa_02(i32 %N) {
+entry:
+  %cmp16 = icmp sgt i32 %N, 1
+  br i1 %cmp16, label %for.body7.lr.ph, label %for.end8
+
+for.body7.lr.ph:                                  ; preds = %entry, %for.cond1.for.inc6_crit_edge
+  %indvars.iv18 = phi i64 [ %indvars.iv.next19, %for.cond1.for.inc6_crit_edge ], [ 1, %entry ]
+  %X.promoted = load i32, i32* @X
+  br label %for.body7
+
+for.body7:                                        ; preds = %for.body7, %for.body7.lr.ph
+  %indvars.iv = phi i64 [ 1, %for.body7.lr.ph ], [ %indvars.iv.next, %for.body7 ]
+  %add15 = phi i32 [ %X.promoted, %for.body7.lr.ph ], [ %add, %for.body7 ]
+  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv18
+  %0 = load i32, i32* %arrayidx5
+  %add = add nsw i32 %add15, %0
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %N
+  br i1 %exitcond, label %for.cond1.for.inc6_crit_edge, label %for.body7
+
+for.cond1.for.inc6_crit_edge:                     ; preds = %for.body7
+  %X.to.save = add i32 %X.promoted, 1
+  store i32 %X.to.save, i32* @X
+  %indvars.iv.next19 = add nuw nsw i64 %indvars.iv18, 1
+  %lftr.wideiv20 = trunc i64 %indvars.iv.next19 to i32
+  %exitcond21 = icmp eq i32 %lftr.wideiv20, %N
+  br i1 %exitcond21, label %for.end8, label %for.body7.lr.ph
+
+for.end8:                                         ; preds = %for.cond1.for.inc6_crit_edge, %entry
+  %X.to.save.phi = phi i32 [ %X.to.save, %for.cond1.for.inc6_crit_edge], [ 0, %entry ]
+  store i32 %X.to.save.phi, i32* @Y
+
+  ret void
+}
+
+; CHECK-LABEL: @lcssa_02
+; CHECK: for.body7:                                        ; preds = %for.body7.preheader, %for.body7
+; CHECK: %indvars.iv = phi i64 [ %indvars.iv.next, %for.body7 ], [ 1, %for.body7.preheader ]
+; CHECK: %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+; CHECK: br i1 %exitcond, label %for.cond1.for.inc6_crit_edge, label %for.body7
+; CHECK-LABEL:  for.cond1.for.inc6_crit_edge:                     ; preds = %for.body7
+; CHECK: br i1 %exitcond21, label %for.end8.loopexit, label %for.body7.lr.ph
Index: test/Transforms/LoopInterchange/reductions.ll
===================================================================
--- test/Transforms/LoopInterchange/reductions.ll
+++ test/Transforms/LoopInterchange/reductions.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
+; RUN: opt < %s -basicaa -loop-interchange -S -verify-dom-info | FileCheck %s
 
 @A = common global [500 x [500 x i32]] zeroinitializer
 @X = common global i32 0
@@ -233,3 +233,53 @@
 ; CHECK:  for.body6:                                        ; preds = %for.body6.preheader, %for.body6
 ; CHECK:    %indvars.iv = phi i64 [ %indvars.iv.next, %for.body6 ], [ 1, %for.body6.preheader ]
 ; CHECK:    %add925 = phi i32 [ %add9, %for.body6 ], [ %Y.promoted, %for.body6.preheader ]
+
+;;  for( int i=1;i<N;i++)
+;;    for( int j=1;j<N;j++)
+;;      X+=A[j][i];
+;;  Y = X
+
+define void @reduction_05(i32 %N) {
+entry:
+  %cmp16 = icmp sgt i32 %N, 1
+  br i1 %cmp16, label %for.body7.lr.ph, label %for.end8
+
+for.body7.lr.ph:                                  ; preds = %entry, %for.cond1.for.inc6_crit_edge
+  %indvars.iv18 = phi i64 [ %indvars.iv.next19, %for.cond1.for.inc6_crit_edge ], [ 1, %entry ]
+  %X.promoted = load i32, i32* @X
+  br label %for.body7
+
+for.body7:                                        ; preds = %for.body7, %for.body7.lr.ph
+  %indvars.iv = phi i64 [ 1, %for.body7.lr.ph ], [ %indvars.iv.next, %for.body7 ]
+  %add15 = phi i32 [ %X.promoted, %for.body7.lr.ph ], [ %add, %for.body7 ]
+  %arrayidx5 = getelementptr inbounds [500 x [500 x i32]], [500 x [500 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv18
+  %0 = load i32, i32* %arrayidx5
+  %add = add nsw i32 %add15, %0
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %N
+  br i1 %exitcond, label %for.cond1.for.inc6_crit_edge, label %for.body7
+
+for.cond1.for.inc6_crit_edge:                     ; preds = %for.body7
+  store i32 %add, i32* @X
+  %indvars.iv.next19 = add nuw nsw i64 %indvars.iv18, 1
+  %lftr.wideiv20 = trunc i64 %indvars.iv.next19 to i32
+  %exitcond21 = icmp eq i32 %lftr.wideiv20, %N
+  br i1 %exitcond21, label %for.end8, label %for.body7.lr.ph
+
+for.end8:                                         ; preds = %for.cond1.for.inc6_crit_edge, %entry
+  %add.res = phi i32 [ %add, %for.cond1.for.inc6_crit_edge], [ 0, %entry ]
+  store i32 %add.res, i32* @Y
+
+  ret void
+}
+
+; CHECK: @reduction_05
+; CHECK:  for.body7:                                        ; preds = %for.body7.preheader, %for.body7.split
+; CHECK:    %indvars.iv = phi i64 [ %indvars.iv.next, %for.body7.split ], [ 1, %for.body7.preheader ]
+; CHECK:    br label %for.body7.lr.ph.preheader
+; CHECK:    %add = add nsw i32 %X.promoted
+
+; CHECK-LABEL: for.end8: ; preds = %for.end8.loopexit, %entry
+; CHECK: %add.res = phi i32 [ 0, %entry ], [ %add.lcssa.lcssa, %for.end8.loopexit ]
+; CHECK:  store i32 %add.res, i32* @Y