[LoopInterchange] Only skip PHIs with incoming values from the inner loop.

[fhahn]

Summary

Currently we have limited support for outer loops with multiple basic
blocks after the inner loop exit. But the current checks for creating
PHIs for loop exit values only assumes the header and latches of the
outer loop. It is better to just skip incoming values defined in the
original inner loops. Those are handled earlier.

[efriedma]

LGTM

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1410

Comment wrapping?

[fhahn]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1410

Thanks Eli, I've fixed that. It seems like clang-format does not re-flow comments that do not exceed the maximum length.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

if (BI->getSuccessor(i) == OldBB) {
       break;
     }
   }
 }
 
 // Move Lcssa PHIs to the right place.
 static void moveLCSSAPhis(BasicBlock *InnerExit, BasicBlock *InnerHeader,
                           BasicBlock *InnerLatch, BasicBlock *OuterHeader,
-                          BasicBlock *OuterLatch, BasicBlock *OuterExit) {
+                          BasicBlock *OuterLatch, BasicBlock *OuterExit,
+                          Loop *InnerLoop, LoopInfo *LI) {
 
   // Deal with LCSSA PHI nodes in the exit block of the inner loop, that are
   // defined either in the header or latch. Those blocks will become header and
   // latch of the new outer loop, and the only possible users can PHI nodes
   // in the exit block of the loop nest or the outer loop header (reduction
   // PHIs, in that case, the incoming value must be defined in the inner loop
   // header). We can just substitute the user with the incoming value and remove
   // the PHI.
for (PHINode *P : LcssaInnerExit)
     P->moveBefore(InnerLatch->getFirstNonPHI());
 
   // If the inner loop latch contains LCSSA PHIs, those come from a child loop
   // and we have to move them to the new inner latch.
   for (PHINode *P : LcssaInnerLatch)
     P->moveBefore(InnerExit->getFirstNonPHI());
 
   // Deal with LCSSA PHI nodes in the loop nest exit block. For PHIs that have
-  // incoming values from the outer latch or header, we have to add a new PHI
+  // incoming values defined in the outer loop, we have to add a new PHI
   // in the inner loop latch, which became the exit block of the outer loop,
   // after interchanging.
   if (OuterExit) {
     for (PHINode &P : OuterExit->phis()) {
       if (P.getNumIncomingValues() != 1)
         continue;
-      // Skip Phis with incoming values not defined in the outer loop's header
-      // and latch. Also skip incoming phis defined in the latch. Those should
+      // Skip Phis with incoming values defined in the inner loop.
+      // Those should
       // already have been updated.
       auto I = dyn_cast<Instruction>(P.getIncomingValue(0));
-      if (!I || ((I->getParent() != OuterLatch || isa<PHINode>(I)) &&
-                 I->getParent() != OuterHeader))
+      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);
       NewPhi->insertBefore(InnerLatch->getFirstNonPHI());
       P.setIncomingValue(0, NewPhi);
     }
bool LoopInterchangeTransform::adjustLoopBranches() {
   updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch,
                   DTUpdates);
 
   DT->applyUpdates(DTUpdates);
   restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader,
                    OuterLoopPreHeader);
 
   moveLCSSAPhis(InnerLoopLatchSuccessor, InnerLoopHeader, InnerLoopLatch,
-                OuterLoopHeader, OuterLoopLatch, InnerLoop->getExitBlock());
+                OuterLoopHeader, OuterLoopLatch, InnerLoop->getExitBlock(),
+                InnerLoop, LI);
   // For PHIs in the exit block of the outer loop, outer's latch has been
   // replaced by Inners'.
   OuterLoopLatchSuccessor->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
 
   // Now update the reduction PHIs in the inner and outer loop headers.
   SmallVector<PHINode *, 4> InnerLoopPHIs, OuterLoopPHIs;
   for (PHINode &PHI : drop_begin(InnerLoopHeader->phis(), 1))
     InnerLoopPHIs.push_back(cast<PHINode>(&PHI));

llvm/test/Transforms/LoopInterchange/pr43797-lcssa-for-multiple-outer-loop-blocks.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -loop-interchange -verify-loop-lcssa -S %s | FileCheck %s
+
+; Tests for PR43797.
+
+@wdtdr = external dso_local global [5 x [5 x double]], align 16
+
+define void @test1() {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[INNER_HEADER_PREHEADER:%.*]]
+; CHECK:       outer.header.preheader:
+; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
+; CHECK:       outer.header:
+; CHECK-NEXT:    [[OUTER_IDX:%.*]] = phi i64 [ [[OUTER_IDX_INC:%.*]], [[OUTER_LATCH:%.*]] ], [ 0, [[OUTER_HEADER_PREHEADER:%.*]] ]
+; CHECK-NEXT:    [[ARRAYIDX8:%.*]] = getelementptr inbounds [5 x [5 x double]], [5 x [5 x double]]* @wdtdr, i64 0, i64 0, i64 [[OUTER_IDX]]
+; CHECK-NEXT:    br label [[INNER_HEADER_SPLIT:%.*]]
+; CHECK:       inner.header.preheader:
+; CHECK-NEXT:    br label [[INNER_HEADER:%.*]]
+; CHECK:       inner.header:
+; CHECK-NEXT:    [[INNER_IDX:%.*]] = phi i64 [ [[TMP3:%.*]], [[INNER_LATCH_SPLIT:%.*]] ], [ 0, [[INNER_HEADER_PREHEADER]] ]
+; CHECK-NEXT:    br label [[OUTER_HEADER_PREHEADER]]
+; CHECK:       inner.header.split:
+; CHECK-NEXT:    [[TMP0:%.*]] = load double, double* [[ARRAYIDX8]], align 8
+; CHECK-NEXT:    store double undef, double* [[ARRAYIDX8]], align 8
+; CHECK-NEXT:    br label [[INNER_LATCH:%.*]]
+; CHECK:       inner.latch:
+; CHECK-NEXT:    [[INNER_IDX_INC:%.*]] = add nsw i64 [[INNER_IDX]], 1
+; CHECK-NEXT:    br label [[INNER_EXIT:%.*]]
+; CHECK:       inner.latch.split:
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i64 [ [[OUTER_V:%.*]], [[OUTER_LATCH]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i64 [ [[OUTER_IDX_INC]], [[OUTER_LATCH]] ]
+; CHECK-NEXT:    [[TMP3]] = add nsw i64 [[INNER_IDX]], 1
+; CHECK-NEXT:    br i1 false, label [[INNER_HEADER]], label [[OUTER_EXIT:%.*]]
+; CHECK:       inner.exit:
+; CHECK-NEXT:    [[OUTER_V]] = add nsw i64 [[OUTER_IDX]], 1
+; CHECK-NEXT:    br label [[OUTER_LATCH]]
+; CHECK:       outer.latch:
+; CHECK-NEXT:    [[OUTER_IDX_INC]] = add nsw i64 [[OUTER_IDX]], 1
+; CHECK-NEXT:    br i1 false, label [[OUTER_HEADER]], label [[INNER_LATCH_SPLIT]]
+; CHECK:       outer.exit:
+; CHECK-NEXT:    [[EXIT1_LCSSA:%.*]] = phi i64 [ [[TMP1]], [[INNER_LATCH_SPLIT]] ]
+; CHECK-NEXT:    [[EXIT2_LCSSA:%.*]] = phi i64 [ [[TMP2]], [[INNER_LATCH_SPLIT]] ]
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %outer.header
+
+outer.header:                                         ; preds = %for.inc27, %entry
+  %outer.idx = phi i64 [ 0, %entry ], [ %outer.idx.inc, %outer.latch ]
+  %arrayidx8 = getelementptr inbounds [5 x [5 x double]], [5 x [5 x double]]* @wdtdr, i64 0, i64 0, i64 %outer.idx
+  br label %inner.header
+
+inner.header:                                        ; preds = %for.inc, %for.body
+  %inner.idx = phi i64 [ 0, %outer.header ], [ %inner.idx.inc, %inner.latch]
+  %0 = load double, double* %arrayidx8, align 8
+  store double undef, double* %arrayidx8, align 8
+  br label %inner.latch
+
+inner.latch:                                          ; preds = %for.body6
+  %inner.idx.inc = add nsw i64 %inner.idx, 1
+  br i1 undef, label %inner.header, label %inner.exit
+
+inner.exit:                                          ; preds = %for.inc
+  %outer.v = add nsw i64 %outer.idx, 1
+  br label %outer.latch
+
+outer.latch:                                        ; preds = %for.end
+  %outer.idx.inc = add nsw i64 %outer.idx, 1
+  br i1 undef, label %outer.header, label %outer.exit
+
+outer.exit:                                        ; preds = %for.inc27
+  %exit1.lcssa = phi i64 [ %outer.v, %outer.latch ]
+  %exit2.lcssa = phi i64 [ %outer.idx.inc, %outer.latch ]
+  ret void
+}
+
+define void @test2(i1 %cond) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[INNER_HEADER_PREHEADER:%.*]], label [[OUTER_EXIT:%.*]]
+; CHECK:       outer.header.preheader:
+; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
+; CHECK:       outer.header:
+; CHECK-NEXT:    [[OUTER_IDX:%.*]] = phi i64 [ [[OUTER_IDX_INC:%.*]], [[OUTER_LATCH:%.*]] ], [ 0, [[OUTER_HEADER_PREHEADER:%.*]] ]
+; CHECK-NEXT:    [[ARRAYIDX8:%.*]] = getelementptr inbounds [5 x [5 x double]], [5 x [5 x double]]* @wdtdr, i64 0, i64 0, i64 [[OUTER_IDX]]
+; CHECK-NEXT:    br label [[INNER_HEADER_SPLIT:%.*]]
+; CHECK:       inner.header.preheader:
+; CHECK-NEXT:    br label [[INNER_HEADER:%.*]]
+; CHECK:       inner.header:
+; CHECK-NEXT:    [[INNER_IDX:%.*]] = phi i64 [ [[TMP3:%.*]], [[INNER_LATCH_SPLIT:%.*]] ], [ 0, [[INNER_HEADER_PREHEADER]] ]
+; CHECK-NEXT:    br label [[OUTER_HEADER_PREHEADER]]
+; CHECK:       inner.header.split:
+; CHECK-NEXT:    [[TMP0:%.*]] = load double, double* [[ARRAYIDX8]], align 8
+; CHECK-NEXT:    store double undef, double* [[ARRAYIDX8]], align 8
+; CHECK-NEXT:    br label [[INNER_LATCH:%.*]]
+; CHECK:       inner.latch:
+; CHECK-NEXT:    [[INNER_IDX_INC:%.*]] = add nsw i64 [[INNER_IDX]], 1
+; CHECK-NEXT:    br label [[INNER_EXIT:%.*]]
+; CHECK:       inner.latch.split:
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i64 [ [[OUTER_IDX_INC]], [[OUTER_LATCH]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i64 [ [[OUTER_V:%.*]], [[OUTER_LATCH]] ]
+; CHECK-NEXT:    [[TMP3]] = add nsw i64 [[INNER_IDX]], 1
+; CHECK-NEXT:    br i1 false, label [[INNER_HEADER]], label [[OUTER_EXIT_LOOPEXIT:%.*]]
+; CHECK:       inner.exit:
+; CHECK-NEXT:    [[OUTER_V]] = add nsw i64 [[OUTER_IDX]], 1
+; CHECK-NEXT:    br label [[OUTER_LATCH]]
+; CHECK:       outer.latch:
+; CHECK-NEXT:    [[OUTER_IDX_INC]] = add nsw i64 [[OUTER_IDX]], 1
+; CHECK-NEXT:    br i1 false, label [[OUTER_HEADER]], label [[INNER_LATCH_SPLIT]]
+; CHECK:       outer.exit.loopexit:
+; CHECK-NEXT:    [[OUTER_IDX_INC_LCSSA:%.*]] = phi i64 [ [[TMP1]], [[INNER_LATCH_SPLIT]] ]
+; CHECK-NEXT:    [[OUTER_V_LCSSA:%.*]] = phi i64 [ [[TMP2]], [[INNER_LATCH_SPLIT]] ]
+; CHECK-NEXT:    br label [[OUTER_EXIT]]
+; CHECK:       outer.exit:
+; CHECK-NEXT:    [[EXIT1_LCSSA:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_V_LCSSA]], [[OUTER_EXIT_LOOPEXIT]] ]
+; CHECK-NEXT:    [[EXIT2_LCSSA:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[OUTER_IDX_INC_LCSSA]], [[OUTER_EXIT_LOOPEXIT]] ]
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %cond, label %outer.header, label %outer.exit
+
+outer.header:                                         ; preds = %for.inc27, %entry
+  %outer.idx = phi i64 [ 0, %entry ], [ %outer.idx.inc, %outer.latch ]
+  %arrayidx8 = getelementptr inbounds [5 x [5 x double]], [5 x [5 x double]]* @wdtdr, i64 0, i64 0, i64 %outer.idx
+  br label %inner.header
+
+inner.header:                                        ; preds = %for.inc, %for.body
+  %inner.idx = phi i64 [ 0, %outer.header ], [ %inner.idx.inc, %inner.latch]
+  %0 = load double, double* %arrayidx8, align 8
+  store double undef, double* %arrayidx8, align 8
+  br label %inner.latch
+
+inner.latch:                                          ; preds = %for.body6
+  %inner.idx.inc = add nsw i64 %inner.idx , 1
+  br i1 undef, label %inner.header, label %inner.exit
+
+inner.exit:                                          ; preds = %for.inc
+  %outer.v = add nsw i64 %outer.idx, 1
+  br label %outer.latch
+
+outer.latch:                                        ; preds = %for.end
+  %outer.idx.inc = add nsw i64 %outer.idx, 1
+  br i1 undef, label %outer.header, label %outer.exit
+
+outer.exit:                                        ; preds = %for.inc27
+  %exit1.lcssa = phi i64 [ 0, %entry ], [ %outer.v, %outer.latch ]
+  %exit2.lcssa = phi i64 [ 0, %entry ], [ %outer.idx.inc, %outer.latch ]
+  ret void
+}