[LoopInterchange] Fix phi node ordering miscompile.

[dmgreen]

Summary

It appears that the way that splitInnerLoopHeader splits blocks requires that the induction PHI will be the first PHI in the inner loop header. This makes sure that is actually the case when there are both IV and reduction phis.

[fhahn]

test/Transforms/LoopInterchange/phi-ordering.ll

14 ↗

(On Diff #118192)

Could you add a few more checks, making sure the loop structure is what we expect?

[dmgreen]

Hello.

Good suggestion, I've updated the test.

test/Transforms/LoopInterchange/phi-ordering.ll

14 ↗

(On Diff #118192)

This depends on what we expect the loop structure to be :)

I originally had this compiling on thumbv6m, where the interchange here is almost certainly going to end up making things slower. The load/store to c would no longer be able to be pulled out of the inner loop. Hence the weak test check that would work even if the performance model here was fixes, and the interchange no longer done.

I've changed this test to v7a where I think vectorisation will make this interchange profitable, and added the loop structure checks you suggested.

[aemerson]

Can you not pass the -loop-interchange-threshold option to force the cost model to always interchange? If this isn't possible with the current code then it seems like a major oversight.

[fhahn]

LGTM, this is looks like a reasonable fix addressing a FIXME. Please use -loop-interchange-threshold in the test as suggested by @aemerson to ensure the test is always interchanged and hold off committing for a day or so, to give people in other timezones a chance to raise objections.

lib/Transforms/Scalar/LoopInterchange.cpp

1219 ↗

(On Diff #119073)

It might be helpful to keep a comment documenting the need for the induction phi to be the first PHI node here (without the FIXME of course)

[dmgreen]

I've updated the test to one that will always be profitable to interchange, as the vectoriser can then kick in.

lib/Transforms/Scalar/LoopInterchange.cpp

1219 ↗

(On Diff #119073)

Good idea.

llvm/trunk/lib/Transforms/Scalar/LoopInterchange.cpp

if (!InductionPHI) {
       return false;
     }
 
     if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
       InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
     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.
     // TODO: This splitting logic may not work always. Fix this.
     splitInnerLoopLatch(InnerIndexVar);
     DEBUG(dbgs() << "splitInnerLoopLatch done\n");
 
     // Splits the inner loops phi nodes out into a separate basic block.
     splitInnerLoopHeader();

 }
 
 void LoopInterchangeTransform::splitInnerLoopHeader() {
   // Split the inner loop header out. Here make sure that the reduction PHI's
   // stay in the innerloop body.
   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
   if (InnerLoopHasReduction) {
-    // FIXME: Check if the induction PHI will always be the first PHI.
+    // Note: The induction PHI must be the first PHI for this to work
     BasicBlock *New = InnerLoopHeader->splitBasicBlock(
         ++(InnerLoopHeader->begin()), InnerLoopHeader->getName() + ".split");
     if (LI)
       if (Loop *L = LI->getLoopFor(InnerLoopHeader))
         L->addBasicBlockToLoop(New, *LI);
 
     // Adjust Reduction PHI's in the block.
     SmallVector<PHINode *, 8> PHIVec;

llvm/trunk/test/Transforms/LoopInterchange/phi-ordering.ll

+; 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 = "armv8--linux-gnueabihf"
+
+; Function Attrs: norecurse nounwind
+define void @test(i32 %T, [90 x i32]* noalias nocapture %C, i16* noalias nocapture readonly %A, i16* noalias nocapture readonly %B) local_unnamed_addr #0 {
+entry:
+  %cmp45 = icmp sgt i32 %T, 0
+  br i1 %cmp45, label %for.body3.lr.ph.preheader, label %for.end21
+
+for.body3.lr.ph.preheader:                        ; preds = %entry
+  br label %for.body3.lr.ph
+
+for.body3.lr.ph:                                  ; preds = %for.body3.lr.ph.preheader, %for.inc19
+  %i.046 = phi i32 [ %inc20, %for.inc19 ], [ 0, %for.body3.lr.ph.preheader ]
+  %mul = mul nsw i32 %i.046, %T
+  br label %for.body6.lr.ph
+
+for.body6.lr.ph:                                  ; preds = %for.inc16, %for.body3.lr.ph
+  %j.043 = phi i32 [ 0, %for.body3.lr.ph ], [ %inc17, %for.inc16 ]
+  %arrayidx14 = getelementptr inbounds [90 x i32], [90 x i32]* %C, i32 %i.046, i32 %j.043
+  %arrayidx14.promoted = load i32, i32* %arrayidx14, align 4
+  br label %for.body6
+
+for.body6:                                        ; preds = %for.body6, %for.body6.lr.ph
+  %add1541 = phi i32 [ %arrayidx14.promoted, %for.body6.lr.ph ], [ %add15, %for.body6 ]
+  %k.040 = phi i32 [ 0, %for.body6.lr.ph ], [ %inc, %for.body6 ]
+  %add = add nsw i32 %k.040, %mul
+  %arrayidx = getelementptr inbounds i16, i16* %A, i32 %add
+  %0 = load i16, i16* %arrayidx, align 2
+  %conv = sext i16 %0 to i32
+  %mul7 = mul nsw i32 %k.040, %T
+  %add8 = add nsw i32 %mul7, %j.043
+  %arrayidx9 = getelementptr inbounds i16, i16* %B, i32 %add8
+  %1 = load i16, i16* %arrayidx9, align 2
+  %conv10 = sext i16 %1 to i32
+  %mul11 = mul nsw i32 %conv10, %conv
+  %add15 = add nsw i32 %mul11, %add1541
+  %inc = add nuw nsw i32 %k.040, 1
+  %exitcond = icmp eq i32 %inc, %T
+  br i1 %exitcond, label %for.inc16, label %for.body6
+
+for.inc16:                                        ; preds = %for.body6
+  %add15.lcssa = phi i32 [ %add15, %for.body6 ]
+  store i32 %add15.lcssa, i32* %arrayidx14, align 4
+  %inc17 = add nuw nsw i32 %j.043, 1
+  %exitcond47 = icmp eq i32 %inc17, %T
+  br i1 %exitcond47, label %for.inc19, label %for.body6.lr.ph
+
+for.inc19:                                        ; preds = %for.inc16
+  %inc20 = add nuw nsw i32 %i.046, 1
+  %exitcond48 = icmp eq i32 %inc20, %T
+  br i1 %exitcond48, label %for.end21.loopexit, label %for.body3.lr.ph
+
+for.end21.loopexit:                               ; preds = %for.inc19
+  br label %for.end21
+
+for.end21:                                        ; preds = %for.end21.loopexit, %entry
+  ret void
+}
+
+
+; CHECK-LABEL: test
+; CHECK: entry:
+; CHECK:   br i1 %cmp45, label %for.body6.preheader, label %for.end21
+; CHECK: for.body3.lr.ph.preheader:
+; CHECK:   br label %for.body3.lr.ph
+; CHECK: for.body3.lr.ph:
+; CHECK:   br label %for.body6.lr.ph.preheader
+; CHECK: for.body6.lr.ph.preheader:
+; CHECK:   br label %for.body6.lr.ph
+; CHECK: for.body6.lr.ph:
+; CHECK:   br label %for.body6.split1
+; CHECK: for.body6.preheader:
+; CHECK:   br label %for.body6
+; CHECK: for.body6:
+; CHECK:   br label %for.body3.lr.ph.preheader
+; CHECK: for.body6.split1:
+; CHECK:   br label %for.inc16
+; CHECK: for.body6.split:
+; CHECK:   add nuw nsw i32 %k.040, 1
+; CHECK:   br i1 %exitcond, label %for.end21.loopexit, label %for.body6
+; CHECK: for.inc16:
+; CHECK:   br i1 %exitcond47, label %for.inc19, label %for.body6.lr.ph
+; CHECK: for.inc19:
+; CHECK:   br i1 %exitcond48, label %for.body6.split, label %for.body3.lr.ph
+; CHECK: for.end21: