Index: lib/Transforms/Scalar/LoopInterchange.cpp
===================================================================
--- lib/Transforms/Scalar/LoopInterchange.cpp
+++ lib/Transforms/Scalar/LoopInterchange.cpp
@@ -1181,6 +1181,11 @@
     else
       InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0));
 
+    // Ensure that InductionPHI is the first Phi node as required by
+    // splitInnerLoopHeader
+    if (&InductionPHI->getParent()->front() != InductionPHI)
+      InductionPHI->moveBefore(&InductionPHI->getParent()->front());
+
     //
     // Split at the place were the induction variable is
     // incremented/decremented.
@@ -1216,7 +1221,6 @@
   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
   if (InnerLoopHasReduction) {
-    // FIXME: Check if the induction PHI will always be the first PHI.
     BasicBlock *New = InnerLoopHeader->splitBasicBlock(
         ++(InnerLoopHeader->begin()), InnerLoopHeader->getName() + ".split");
     if (LI)
Index: test/Transforms/LoopInterchange/phi-ordering.ll
===================================================================
--- /dev/null
+++ test/Transforms/LoopInterchange/phi-ordering.ll
@@ -0,0 +1,81 @@
+; RUN: opt < %s -loop-interchange -S | FileCheck %s
+;; Checks the order of the inner phi nodes does not cause havoc.
+;; The inner loop has a reduction into c. The IV is not the first phi.
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "thumbv7a-none-none-eabi"
+
+@a = hidden global [2 x [3 x i32]] [[3 x i32] [i32 0, i32 1, i32 2], [3 x i32] [i32 3, i32 4, i32 5]], align 4
+@b = hidden global [3 x [4 x i32]] [[4 x i32] [i32 0, i32 1, i32 2, i32 3], [4 x i32] [i32 4, i32 5, i32 6, i32 7], [4 x i32] [i32 8, i32 9, i32 10, i32 11]], align 4
+@c = hidden global [2 x [4 x i32]] zeroinitializer, align 4
+
+define i32 @test() local_unnamed_addr #0 {
+
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.inc15
+  %i.033 = phi i32 [ 0, %entry ], [ %inc16, %for.inc15 ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body, %for.inc12
+  %j.032 = phi i32 [ 0, %for.body ], [ %inc13, %for.inc12 ]
+  %arrayidx11 = getelementptr inbounds [2 x [4 x i32]], [2 x [4 x i32]]* @c, i32 0, i32 %i.033, i32 %j.032
+  %arrayidx11.promoted = load i32, i32* %arrayidx11, align 4
+  br label %for.body6
+
+for.body6:                                        ; preds = %for.body3, %for.body6
+  %0 = phi i32 [ %arrayidx11.promoted, %for.body3 ], [ %add, %for.body6 ]
+  %k.031 = phi i32 [ 0, %for.body3 ], [ %inc, %for.body6 ]
+  %arrayidx7 = getelementptr inbounds [2 x [3 x i32]], [2 x [3 x i32]]* @a, i32 0, i32 %i.033, i32 %k.031
+  %1 = load i32, i32* %arrayidx7, align 4
+  %arrayidx9 = getelementptr inbounds [3 x [4 x i32]], [3 x [4 x i32]]* @b, i32 0, i32 %k.031, i32 %j.032
+  %2 = load i32, i32* %arrayidx9, align 4
+  %mul = mul nsw i32 %2, %1
+  %add = add nsw i32 %0, %mul
+  %inc = add nsw i32 %k.031, 1
+  %cmp5 = icmp slt i32 %k.031, 2
+  br i1 %cmp5, label %for.body6, label %for.inc12
+
+for.inc12:                                        ; preds = %for.body6
+  %add.lcssa = phi i32 [ %add, %for.body6 ]
+  store i32 %add.lcssa, i32* %arrayidx11, align 4
+  %inc13 = add nsw i32 %j.032, 1
+  %cmp2 = icmp slt i32 %j.032, 3
+  br i1 %cmp2, label %for.body3, label %for.inc15
+
+for.inc15:                                        ; preds = %for.inc12
+  %inc16 = add nsw i32 %i.033, 1
+  %cmp = icmp slt i32 %i.033, 1
+  br i1 %cmp, label %for.body, label %for.end17
+
+for.end17:                                        ; preds = %for.inc15
+  ret i32 0
+}
+
+; CHECK-LABEL: test
+; CHECK: entry:
+; CHECK:   br label %for.body6.preheader
+; CHECK: for.body.preheader:
+; CHECK:   br label %for.body
+; CHECK: for.body:
+; CHECK:   br label %for.body3.preheader
+; CHECK: for.body3.preheader:
+; CHECK:   br label %for.body3
+; CHECK: for.body3:
+; CHECK:   br label %for.body6.split1
+; CHECK: for.body6.preheader:
+; CHECK:   br label %for.body6
+; CHECK: for.body6:
+; CHECK:   br label %for.body.preheader
+; CHECK: for.body6.split1:
+; CHECK:   br label %for.inc12
+; CHECK: for.body6.split:
+; CHECK:   add nsw i32 %k.031, 1
+; CHECK:   br i1 %cmp5, label %for.body6, label %for.end17
+; CHECK: for.inc12:
+; CHECK:   br i1 %cmp2, label %for.body3, label %for.inc15
+; CHECK: for.inc15:
+; CHECK:   br i1 %cmp, label %for.body, label %for.body6.split
+; CHECK: for.end17:
+