[LoopInterchange] Fix interchanging contents of preheader BBs

[alexey.zhikhar]

Summary

Previously LCSSA was getting broken by placing instructions into the
(newly) inner *header* instead of the *pre*header.

Fixes PR43474

[alexey.zhikhar]

CFG before the patch, LCSSA broken:

CFG after the patch, LCSSA preserved:

[fhahn]

Thanks for the patch! It mostly looks good, just a few small comments inline.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

558

The assertions here might be a bit over-conservative. I think isLCSSAForm can potentially be expensive, so I would be slightly in favor of dropping them.

1334

I think this could just be something like
SmallVector<Instruction *, 4> TempInstrs(BB1->begin(), std::prev(BB1->end()); // Save all non-terminator instructions.

1340

nit: drop unneeded {

1348

nit: drop unneeded {

1609–1610

With adjustLoopPreheaders being so short now, please inline it directly into adjustLoopLinks.

llvm/test/Transforms/LoopInterchange/lcssa-preheader.ll

2

Please update the test to check the IR to ensure the pre-headers are swapped correctly. It would probably be good to check the whole structure. I think you should be able to also reduce the inner loop body a bit (one load/store should be enough).

6

Please drop the target triple. Otherwise the test will fail when LLVM is built without the X86 backend. And it should not be required for the test.

18

not needed.

19

please drop the un-needed things like dso_local, local_unnamed_addr and #0.

[alexey.zhikhar]

Addressed part of Florian's comments.

[alexey.zhikhar]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

558

I saw them in LICM so I thought that there's no harm in adding them to loop interchange. When I first saw the error that this patch aims to fix, it was an assertion in LICM that runs after loop interchange, which was misleading.

1334

That would be nice but it doesn't seem to work, I'm getting error: cannot convert ‘llvm::Instruction’ to ‘llvm::Instruction*’ in initialization.
Instead, I replaced the for-each loop with explicit iterators and stop before when the terminator is encountered.

1340

This is a small thing but it's something that I thought about before and I would appreciate your input. I personally prefer adding braces even when there's only one statement in a loop/if condition since this way it is both easier and less error-prone to add new statements. I also don't see the LLVM guidelines mentioning anything in this regard but, of course, I'll fix this nit if you insist.

[fhahn]

LGTM, with the remaining comments, thanks!

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

558

Yes, the assertions after we do the transformations (lines 586 and 588) are very beneficial and should guard against similar error in the future. The ones here mean an earlier pass violated LCSSA and I think it would be slightly preferable to remove them; other passes are responsible for that (and -verify-lcssa can be used to catch those).

1334

Ah right, this is unfortunate.for the iterator version, you could use something like for (auto &I : make_range(BB->begin(), std::prev(BB-end)))

If you use make_early_inc_range, it should be safe to merge the loops adding to TempInstrs and removing I.

Or you could use map_range to get an iterator range that returns Instruction * instead Instruction& like below.

+  auto Iter = map_range(*BB1, [](Instruction &I) { return &I });
+  SmallVector<Instruction *, 4> TempInstrs(Iter.begin(), std::prev(Iter.end()));
+  for (Instruction &I : TempInstrs)
+    I.removeFromParent();

Any of the options is fine by me.

1340

I don't think this is explicitly spelled out in the coding standard, but not using unnecessary braces is *very very* common (at least in llvm/ from my experience). IMO this falls under use the style that is already being used so that the source is uniform and easy to follow which is mentioned in the beginning of https://llvm.org/docs/CodingStandards.html#golden-rule

As far as I'm aware, the existing code in LoopInterchange.cpp does not use trivial braces (and if it does it's probably by accident) and IMO it would be good for the sake of consistency to keep it like that.

[fhahn]

I think it would be good to update the title to highlight the details of the patch, something like: [LoopInterchange] Fix interchanging contents of preheader BBs.

[alexey.zhikhar]

Addressed the rest of Florian's comments.

[alexey.zhikhar]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

558

Oh, I see now. Fixed.

1334

Thanks, I didn't know about these utils. I ended up with using map_range().

[fhahn]

Looks good, thanks! Please let me know if you need me to commit this on your behalf.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

public:
   bool transform();
   void restructureLoops(Loop *NewInner, Loop *NewOuter,
                         BasicBlock *OrigInnerPreHeader,
                         BasicBlock *OrigOuterPreHeader);
   void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
 
 private:
   bool adjustLoopLinks();
-  void adjustLoopPreheaders();
   bool adjustLoopBranches();
 
   Loop *OuterLoop;
   Loop *InnerLoop;
 
   /// Scev analysis.
   ScalarEvolution *SE;
 
#endif
   bool processLoop(LoopVector LoopList, unsigned InnerLoopId,
                    unsigned OuterLoopId, BasicBlock *LoopNestExit,
                    std::vector<std::vector<char>> &DependencyMatrix) {
     LLVM_DEBUG(dbgs() << "Processing Inner Loop Id = " << InnerLoopId
                       << " and OuterLoopId = " << OuterLoopId << "\n");
     Loop *InnerLoop = LoopList[InnerLoopId];
     Loop *OuterLoop = LoopList[OuterLoopId];
 
+    assert(InnerLoop->isLCSSAForm(*DT) && "Inner loop is not in LCSSA form.");
+    assert(OuterLoop->isLCSSAForm(*DT) && "Outer loop is not in LCSSA form.");
+
     LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE);
     if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
       LLVM_DEBUG(dbgs() << "Not interchanging loops. Cannot prove legality.\n");
       return false;
     }
     LLVM_DEBUG(dbgs() << "Loops are legal to interchange\n");
     LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE, ORE);
     if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) {
       LLVM_DEBUG(dbgs() << "Interchanging loops not profitable.\n");
       return false;
     }
 
     ORE->emit([&]() {
       return OptimizationRemark(DEBUG_TYPE, "Interchanged",
                                 InnerLoop->getStartLoc(),
                                 InnerLoop->getHeader())
              << "Loop interchanged with enclosing loop.";
     });
 
     LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, LoopNestExit,
                                  LIL);
     LIT.transform();
     LLVM_DEBUG(dbgs() << "Loops interchanged.\n");
     LoopsInterchanged++;
+
+    assert(InnerLoop->isLCSSAForm(*DT) &&
+           "Inner loop not left in LCSSA form after loop interchange!");
+    assert(OuterLoop->isLCSSAForm(*DT) &&
+           "Outer loop not left in LCSSA form after loop interchange!");
+
     return true;
   }
 };
 
 } // end anonymous namespace
 
 bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB) {
   return any_of(*BB, [](const Instruction &I) {

 static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
   auto &ToList = InsertBefore->getParent()->getInstList();
   auto &FromList = FromBB->getInstList();
 
   ToList.splice(InsertBefore->getIterator(), FromList, FromList.begin(),
                 FromBB->getTerminator()->getIterator());
 }
 
+/// Swap instructions between \p BB1 and \p BB2 but keep terminators intact.
+static void swapBBContents(BasicBlock *BB1, BasicBlock *BB2) {
+  // Save all non-terminator instructions of BB1 into TempInstrs and unlink them
+  // from BB1 afterwards.
+  SmallVector<Instruction *, 4> TempInstrs;
+  for (auto It = BB1->begin(); It != std::prev(BB1->end()); ++It) {
+    TempInstrs.push_back(&*It);
+  }
+  for (Instruction *I : TempInstrs) {
+    I->removeFromParent();
+  }
+
+  // Move instructions from BB2 to BB1.
+  moveBBContents(BB2, BB1->getTerminator());
+
+  // Move instructions from TempInstrs to BB2.
+  for (Instruction *I : TempInstrs) {
+    I->insertBefore(BB2->getTerminator());
+  }
+}
+
 // Update BI to jump to NewBB instead of OldBB. Records updates to the
 // dominator tree in DTUpdates. If \p MustUpdateOnce is true, assert that
 // \p OldBB  is exactly once in BI's successor list.
 static void updateSuccessor(BranchInst *BI, BasicBlock *OldBB,
                             BasicBlock *NewBB,
                             std::vector<DominatorTree::UpdateType> &DTUpdates,
                             bool MustUpdateOnce = true) {
   assert((!MustUpdateOnce ||
bool LoopInterchangeTransform::adjustLoopBranches() {
   // Update the incoming blocks for moved PHI nodes.
   OuterLoopHeader->replacePhiUsesWith(InnerLoopPreHeader, OuterLoopPreHeader);
   OuterLoopHeader->replacePhiUsesWith(InnerLoopLatch, OuterLoopLatch);
   InnerLoopHeader->replacePhiUsesWith(OuterLoopPreHeader, InnerLoopPreHeader);
   InnerLoopHeader->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
 
   return true;
 }
 
-void LoopInterchangeTransform::adjustLoopPreheaders() {
+bool LoopInterchangeTransform::adjustLoopLinks() {
+  // Adjust all branches in the inner and outer loop.
+  bool Changed = adjustLoopBranches();
+  if (Changed) {
     // We have interchanged the preheaders so we need to interchange the data in
-  // the preheader as well.
-  // This is because the content of inner preheader was previously executed
-  // inside the outer loop.
+    // the preheaders as well. This is because the content of the inner
+    // preheader was previously executed inside the outer loop.
     BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
     BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
-  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
-  BranchInst *InnerTermBI =
-      cast<BranchInst>(InnerLoopPreHeader->getTerminator());
-
-  // These instructions should now be executed inside the loop.
-  // Move instruction into a new block after outer header.
-  moveBBContents(InnerLoopPreHeader, OuterLoopHeader->getTerminator());
-  // These instructions were not executed previously in the loop so move them to
-  // the older inner loop preheader.
-  moveBBContents(OuterLoopPreHeader, InnerTermBI);
+    swapBBContents(OuterLoopPreHeader, InnerLoopPreHeader);
   }
-
-bool LoopInterchangeTransform::adjustLoopLinks() {
-  // Adjust all branches in the inner and outer loop.
-  bool Changed = adjustLoopBranches();
-  if (Changed)
-    adjustLoopPreheaders();
   return Changed;
 }
 
 char LoopInterchange::ID = 0;
 
 INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange",
                       "Interchanges loops for cache reuse", false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
 
 INITIALIZE_PASS_END(LoopInterchange, "loop-interchange",
                     "Interchanges loops for cache reuse", false, false)
 
 Pass *llvm::createLoopInterchangePass() { return new LoopInterchange(); }

llvm/test/Transforms/LoopInterchange/lcssa-preheader.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -basicaa -loop-interchange -pass-remarks-missed='loop-interchange' -verify-loop-lcssa -S | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; void foo(int n, int m) {
+;   int temp[16][16];
+;   int res[16][16];
+;   for(int i = 0; i < n; i++) {
+;     for(int j = 0; j < m; j++)
+;       res[j][i] = temp[j][i];
+;   }
+; }
+
+define void @lcssa_08(i32 %n, i32 %m) {
+; CHECK-LABEL: @lcssa_08(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TEMP:%.*]] = alloca [16 x [16 x i32]], align 4
+; CHECK-NEXT:    [[RES:%.*]] = alloca [16 x [16 x i32]], align 4
+; CHECK-NEXT:    [[CMP24:%.*]] = icmp sgt i32 [[N:%.*]], 0
+; CHECK-NEXT:    br i1 [[CMP24]], label [[INNER_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]
+; CHECK:       outer.preheader:
+; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[M:%.*]] to i64
+; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
+; CHECK:       outer.header:
+; CHECK-NEXT:    [[INDVARS_IV27:%.*]] = phi i64 [ 0, [[OUTER_PREHEADER:%.*]] ], [ [[INDVARS_IV_NEXT28:%.*]], [[OUTER_LATCH:%.*]] ]
+; CHECK-NEXT:    [[CMP222:%.*]] = icmp sgt i32 [[M]], 0
+; CHECK-NEXT:    br i1 [[CMP222]], label [[INNER_FOR_BODY_SPLIT1:%.*]], label [[OUTER_CRIT_EDGE:%.*]]
+; CHECK:       inner.preheader:
+; CHECK-NEXT:    [[WIDE_TRIP_COUNT29:%.*]] = zext i32 [[N]] to i64
+; CHECK-NEXT:    br label [[INNER_FOR_BODY:%.*]]
+; CHECK:       inner.for.body:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[INNER_PREHEADER]] ], [ [[TMP1:%.*]], [[INNER_FOR_BODY_SPLIT:%.*]] ]
+; CHECK-NEXT:    br label [[OUTER_PREHEADER]]
+; CHECK:       inner.for.body.split1:
+; CHECK-NEXT:    [[ARRAYIDX6:%.*]] = getelementptr inbounds [16 x [16 x i32]], [16 x [16 x i32]]* [[TEMP]], i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV27]]
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[ARRAYIDX6]], align 4
+; CHECK-NEXT:    [[ARRAYIDX8:%.*]] = getelementptr inbounds [16 x [16 x i32]], [16 x [16 x i32]]* [[RES]], i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV27]]
+; CHECK-NEXT:    store i32 [[TMP0]], i32* [[ARRAYIDX8]], align 4
+; CHECK-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
+; CHECK-NEXT:    br label [[INNER_CRIT_EDGE:%.*]]
+; CHECK:       inner.for.body.split:
+; CHECK-NEXT:    [[TMP1]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i64 [[TMP1]], [[WIDE_TRIP_COUNT]]
+; CHECK-NEXT:    br i1 [[TMP2]], label [[INNER_FOR_BODY]], label [[OUTER_CRIT_EDGE]]
+; CHECK:       inner.crit_edge:
+; CHECK-NEXT:    br label [[OUTER_LATCH]]
+; CHECK:       outer.latch:
+; CHECK-NEXT:    [[INDVARS_IV_NEXT28]] = add nuw nsw i64 [[INDVARS_IV27]], 1
+; CHECK-NEXT:    [[EXITCOND30:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT28]], [[WIDE_TRIP_COUNT29]]
+; CHECK-NEXT:    br i1 [[EXITCOND30]], label [[OUTER_HEADER]], label [[INNER_FOR_BODY_SPLIT]]
+; CHECK:       outer.crit_edge:
+; CHECK-NEXT:    br label [[FOR_COND_CLEANUP]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %temp = alloca [16 x [16 x i32]], align 4
+  %res = alloca [16 x [16 x i32]], align 4
+  %cmp24 = icmp sgt i32 %n, 0
+  br i1 %cmp24, label %outer.preheader, label %for.cond.cleanup
+
+outer.preheader:                        ; preds = %entry
+  %wide.trip.count29 = zext i32 %n to i64
+  br label %outer.header
+
+outer.header:                              ; preds = %outer.preheader, %outer.latch
+  %indvars.iv27 = phi i64 [ 0, %outer.preheader ], [ %indvars.iv.next28, %outer.latch ]
+  %cmp222 = icmp sgt i32 %m, 0
+  br i1 %cmp222, label %inner.preheader, label %outer.latch
+
+inner.preheader:                                  ; preds = %outer.header
+  ; When inner.preheader becomes the outer preheader, do not move
+  ; %wide.trip.count into the inner loop header lest LCSSA break
+  ; (if %wide.trip.count gets moved, its use is now outside the inner loop).
+  %wide.trip.count = zext i32 %m to i64
+  br label %inner.for.body
+
+inner.for.body:                                        ; preds = %inner.preheader, %inner.for.body
+  %indvars.iv = phi i64 [ 0, %inner.preheader ], [ %indvars.iv.next, %inner.for.body ]
+  %arrayidx6 = getelementptr inbounds [16 x [16 x i32]], [16 x [16 x i32]]* %temp, i64 0, i64 %indvars.iv, i64 %indvars.iv27
+  %0 = load i32, i32* %arrayidx6, align 4
+  %arrayidx8 = getelementptr inbounds [16 x [16 x i32]], [16 x [16 x i32]]* %res, i64 0, i64 %indvars.iv, i64 %indvars.iv27
+  store i32 %0, i32* %arrayidx8, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count
+  br i1 %exitcond, label %inner.for.body, label %inner.crit_edge
+
+inner.crit_edge:            ; preds = %inner.for.body
+  br label %outer.latch
+
+outer.latch:                                ; preds = %inner.crit_edge, %outer.header
+  %indvars.iv.next28 = add nuw nsw i64 %indvars.iv27, 1
+  %exitcond30 = icmp ne i64 %indvars.iv.next28, %wide.trip.count29
+  br i1 %exitcond30, label %outer.header, label %outer.crit_edge
+
+outer.crit_edge:              ; preds = %outer.latch
+  br label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %outer.crit_edge, %entry
+  ret void
+}