[LoopInterchange] Handle lcssa PHIs with multiple predecessors

[congzhe]

Summary

This is a bugfix in the transformation phase.

If the original outer loop header branches to both the inner loop (header) and the outer loop latch, and if there is an lcssa PHI node outside the loop nest, then after interchange the new outer latch will have an lcssa PHI node inserted which has two predecessors, i.e., the original outer header and the original outer latch. Currently the transformation assumes it has only one predecessor (the original outer latch) and crashes, since the inserted lcssa PHI node does not take both predecessors as incoming BBs.

[congzhe]

gentle ping @bmahjour @Whitney @fhahn

[congzhe]

Just to better clarify, for the test case added in this patch, this is the IR after loop interchange (with this patch):

define i64 @lcssa_08([100 x [100 x i64]]* %Arr) {
entry:
  br label %for2.preheader

for1.header.preheader:                            ; preds = %for2
  br label %for1.header

for1.header:                                      ; preds = %for1.header.preheader, %for1.inc
  %indvars.iv23 = phi i64 [ %indvars.iv.next24, %for1.inc ], [ 0, %for1.header.preheader ]
  br i1 undef, label %for2.split1, label %for2.split

for2.preheader:                                   ; preds = %entry
  br label %for2

for2:                                             ; preds = %for2.preheader, %for2.split
  %indvars.iv = phi i64 [ %1, %for2.split ], [ 0, %for2.preheader ]
  br label %for1.header.preheader

for2.split1:                                      ; preds = %for1.header
  %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
  %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
  %exit1 = icmp eq i64 %indvars.iv.next.3, 100
  br label %for1.inc.loopexit

for2.split:                                       ; preds = %for1.inc, %for1.header
  %0 = phi i64 [ %indvars.iv23, %for1.inc ], [ %indvars.iv23, %for1.header ]
  %1 = add nuw nsw i64 %indvars.iv, 1
  %2 = icmp eq i64 %1, 100
  br i1 %2, label %for1.loopexit, label %for2

for1.inc.loopexit:                                ; preds = %for2.split1
  br label %for1.inc

for1.inc:                                         ; preds = %for1.inc.loopexit
  %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
  %exit2 = icmp eq i64 %indvars.iv.next24, 100
  br i1 %exit2, label %for2.split, label %for1.header

for1.loopexit:                                    ; preds = %for2.split
  %indvars.outer.lcssa = phi i64 [ %0, %for2.split ]
  ret i64 %indvars.outer.lcssa
}

Without this patch the compiler currently crashes with the following info:

PHINode should have one entry for each predecessor of its parent basic block!
  %0 = phi i64 [ %indvars.iv23, %for1.inc ]
in function lcssa_08
LLVM ERROR: Broken function found, compilation aborted!

[Whitney]

Approve with minor comment.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1475

for (auto *Pred : predecessors(InnerLatch))

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

for (PHINode &P : OuterExit->phis()) {
       // already have been updated.
       auto I = dyn_cast<Instruction>(P.getIncomingValue(0));
       if (!I || LI->getLoopFor(I->getParent()) == InnerLoop)
         continue;
 
       PHINode *NewPhi = dyn_cast<PHINode>(P.clone());
       NewPhi->setIncomingValue(0, P.getIncomingValue(0));
       NewPhi->setIncomingBlock(0, OuterLatch);
+      // We might have incoming edges from other BBs, i.e., the original outer
+      // header.
+      for (auto *Pred : predecessors(InnerLatch)) {
+        if (Pred == OuterLatch)
+          continue;
+        NewPhi->addIncoming(P.getIncomingValue(0), Pred);
+      }
       NewPhi->insertBefore(InnerLatch->getFirstNonPHI());
       P.setIncomingValue(0, NewPhi);
     }
   }
 
   // Now adjust the incoming blocks for the LCSSA PHIs.
   // For PHIs moved from Inner's exit block, we need to replace Inner's latch
   // with the new latch.

llvm/test/Transforms/LoopInterchange/lcssa.ll

 for.exit:                                         ; preds = %outer.inc
   %iv.inner.lcssa.lcssa = phi i64 [ %iv.inner.lcssa, %outer.inc ]
   store i64 %iv.inner.lcssa.lcssa, i64* @Y
   br label %for.end16
 
 for.end16:                                        ; preds = %for.exit
   ret void
 }
+
+; Should not crash when the outer header branches to
+; both the inner loop and the outer latch, and there
+; is an lcssa phi node outside the loopnest.
+; REMARK: Interchanged
+; REMARK-NEXT: lcssa_08
+define i64 @lcssa_08([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 ]
+  br i1 undef, label %for2, label %for1.inc
+
+for2:                                        ; preds = %for2, %for1.header
+  %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %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
+  %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, %for1.header
+  %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.outer.lcssa = phi i64 [ %indvars.iv23, %for1.inc ]
+  ret i64 %sum.outer.lcssa
+}
+