Sinking or hoisting instructions between loops before fusion

[aaronkintel]

Summary

Instructions between two adjacent loops will be hoisted above the first loop, or sunk below the second to facilitate loop fusion. Hoisting will be attempted for an instruction that dominates the first loop. Otherwise, sinking this instructions will be attempted.

Instructions with side effects will not be considered for sinking or hoisting. Hoisting/sinking of any instructions between loops will only be performed if all the instructions can be moved. As well, sinking/hoisting is considered for each instruction in isolation, without taking into account sinking/hoisting decisions for other instructions in the preheader.

[aaronkintel]

Fixed clang-format

[aaronkintel]

Can someone please provide feedback for this review?

[jcranmer-intel]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

71–75

Nit: these include lines should be sorted as appropriate in the main include block above.

974–976

This will unconditionally do the code motion even if (future) profitability checks decide that it's not beneficial to fuse the loops. I think it would be better to hold off on doing so until after we've checked fusion profitability, especially because not doing so means we would get the changed flag wrong in some cases.

1057–1058

I'm convinced this check isn't correct, although I am still trying to figure out which check is the correct one.

1074–1077

Nevertheless, the specific checks you used above generally does not comport with these checks. The first set of checks bans all memory instructions from being checked, and if you drill into canSinkOrHoistInst, almost all of the checks in there are about verifying correctness of memory instructions, with the residual checks of call instructions in large part anyways not being what you wanted anyways, given your choice to override its decision point for DbgInfoIntrinsic.

Offhand, isSafeToSpeculativelyExecute feels like it's the best *starting* point for correctness checks for hoisting. This doesn't cover the dependency checking or domination checks, but you can look at isSafeToMoveBefore in CodeMoverUtils.cpp to understand the general basis for the decision point. If we had a isSafeToMoveAfter, I'd outright just say that using a combination of isSafeToMoveBefore and isSafeToMoveAfter is the best way to go, but we don't, so it would be worth digging into isSafeToMoveBefore anyways to understand its machinery.

[aaronkintel]

Responding to comments.

[aaronkintel]

The build failures are all different, and are evidently unrelated to this change.

llvm/lib/Transforms/Scalar/LoopFuse.cpp

1057–1058

Let me know what you thi

1074–1077

I have taken a different approach here by using domination for hoisting and checking the users for sinking. Is this satisfactory?

[aaronkintel]

Can someone please provide feedback for this review? Thanks!

[jcranmer-intel]

There's two more tests I would like to see here:

• One test that checks that an intrinsically unmovable instruction (e.g., call to an unknown function) in the preheader blocks hoisting/sinking.
• Another test (in the same file as above is possible) checks that a memory dependency blocks hoisting/sinking.

llvm/lib/Transforms/Scalar/LoopFuse.cpp

954–955

I don't think this variable is necessary, since if it's false, you've already stopped looking at this loop and have continued to the next one.

1048–1049

Nit: As a general style guidelines, C++11 universal initializer syntax is generally disfavored, as is auto.

The rough guideline I use for auto is that you generally want types to appear exactly once, so when you're assigning the result of a cast (especially the dyn_cast checks), then you go ahead and use auto, but otherwise, you generally stay away from it.

1071

Nit: This probably meant should be named CanHoistInst.

1074–1075

You should be able to replace this with bool OpHoisted = is_contained(SafeTohoist, OpInst); (may need to include STLExtras.h).

1078

Nit: OpHoisted should precede the dominator check.

1093–1095

The first half of the or statement here subsumes the second half, does it not?

1339–1341

You mean += here, not =.

llvm/test/Transforms/LoopFusion/no_sink_hoist.ll

3–5

For negative fusion checks, I think a test along the lines of llvm/test/Transforms/LoopFusion/cannot_fuse.ll is more appropriate.

llvm/test/Transforms/LoopFusion/no_sink_hoist_inner_barier.ll

1 ↗

(On Diff #426995)

Nit: Too many semicolons.

Also, the file's name should be "no_sink_hoist_inner_barrier.ll"

llvm/test/Transforms/LoopFusion/sink_preheader.ll

2

For this test, I'd strongly prefer to see update_test_checks.py-style checks.

[aaronkintel]

Responding to reviewer comments.

[aaronkintel]

Can someone please provide feedback for this review? Thanks!

llvm/test/Transforms/LoopFusion/sink_preheader.ll

2

Is this what you mean by "update_test_checks.py-style"?

[aaronkintel]

Build failures unrelated to change.

[jcranmer-intel]

I'd still like to see two more tests:

• One test that checks that an intrinsically unmovable instruction (e.g., call to an unknown function) in the preheader blocks hoisting/sinking.
• Another test (in the same file as above is possible) checks that a memory dependency blocks hoisting/sinking.

Other than that, and the nit I'm seeing, looking good.

llvm/lib/Transforms/Scalar/LoopFuse.cpp

1074

I'd still like to see this and the later if statement not using C++11 universal initialization.

[aaronkintel]

Responding to comments. Fixed initialization of variable and added lit tests for ensuring that mem insts and undefined functions are not moved from the preheader of the second loop.

[jcranmer-intel]

llvm/test/Transforms/LoopFusion/no_sink_hoist_store.ll

26

The alloca should be in the entry block for this test, should it not?

[aaronkintel]

Moving alloca to preheader in no_sink_hoist_store.ll

[aaronkintel]

Can someone please provide feedback for this review?

llvm/test/Transforms/LoopFusion/no_sink_hoist_store.ll

26

Do you mean it should be:
pre1:

%ptr = alloca i32

....
pre2:

store i32 3, i32* %ptr

What is the reason for this?

[jcranmer-intel]

llvm/test/Transforms/LoopFusion/no_sink_hoist_store.ll

26

alloca instructions are generally expected to occur at the beginning of the function's entry block; if they're not, then they're a dynamic alloca block, which can have unexpected impacts on other optimizations. Unless there's a good reason for the alloca not to live in the entry block, then they should be generated in the entry block.

llvm/lib/Transforms/Scalar/LoopFuse.cpp

 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/CodeMoverUtils.h"
 #include "llvm/Transforms/Utils/LoopPeel.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-fusion"
 
 STATISTIC(FuseCounter, "Loops fused");
 STATISTIC(NumFusionCandidates, "Number of candidates for loop fusion");
 STATISTIC(InvalidPreheader, "Loop has invalid preheader");
 STATISTIC(InvalidHeader, "Loop has invalid header");
 STATISTIC(InvalidExitingBlock, "Loop has invalid exiting blocks");
 STATISTIC(InvalidExitBlock, "Loop has invalid exit block");
 STATISTIC(InvalidLatch, "Loop has invalid latch");
 STATISTIC(InvalidLoop, "Loop is invalid");
 STATISTIC(AddressTakenBB, "Basic block has address taken");

 STATISTIC(NonIdenticalGuards, "Candidates have different guards");
 STATISTIC(NonEmptyExitBlock, "Candidate has a non-empty exit block with "
                              "instructions that cannot be moved");
 STATISTIC(NonEmptyGuardBlock, "Candidate has a non-empty guard block with "
                               "instructions that cannot be moved");
 STATISTIC(NotRotated, "Candidate is not rotated");
 STATISTIC(OnlySecondCandidateIsGuarded,
           "The second candidate is guarded while the first one is not");
+STATISTIC(NumHoistedInsts, "Number of hoisted preheader instructions.");
+STATISTIC(NumSunkInsts, "Number of hoisted preheader instructions.");
 
 enum FusionDependenceAnalysisChoice {
   FUSION_DEPENDENCE_ANALYSIS_SCEV,
   FUSION_DEPENDENCE_ANALYSIS_DA,
   FUSION_DEPENDENCE_ANALYSIS_ALL,
 };
 
 static cl::opt<FusionDependenceAnalysisChoice> FusionDependenceAnalysis(
struct FusionCandidate {
   /// FusionCandidateCompare function, required by FusionCandidateSet to
   /// determine where the FusionCandidate should be inserted into the set. These
   /// are used to establish ordering of the FusionCandidates based on dominance.
   DominatorTree &DT;
   const PostDominatorTree *PDT;
 
   OptimizationRemarkEmitter &ORE;
 
-  FusionCandidate(Loop *L, DominatorTree &DT,
-                  const PostDominatorTree *PDT, OptimizationRemarkEmitter &ORE,
-                  TTI::PeelingPreferences PP)
+  FusionCandidate(Loop *L, DominatorTree &DT, const PostDominatorTree *PDT,
+                  OptimizationRemarkEmitter &ORE, TTI::PeelingPreferences PP)
       : Preheader(L->getLoopPreheader()), Header(L->getHeader()),
         ExitingBlock(L->getExitingBlock()), ExitBlock(L->getExitBlock()),
         Latch(L->getLoopLatch()), L(L), Valid(true),
         GuardBranch(L->getLoopGuardBranch()), PP(PP), AbleToPeel(canPeel(L)),
         Peeled(false), DT(DT), PDT(PDT), ORE(ORE) {
 
     // Walk over all blocks in the loop and check for conditions that may
     // prevent fusion. For each block, walk over all instructions and collect
private:
 
   LoopInfo &LI;
   DominatorTree &DT;
   DependenceInfo &DI;
   ScalarEvolution &SE;
   PostDominatorTree &PDT;
   OptimizationRemarkEmitter &ORE;
   AssumptionCache &AC;
-
   const TargetTransformInfo &TTI;
 
 public:
   LoopFuser(LoopInfo &LI, DominatorTree &DT, DependenceInfo &DI,
             ScalarEvolution &SE, PostDominatorTree &PDT,
             OptimizationRemarkEmitter &ORE, const DataLayout &DL,
             AssumptionCache &AC, const TargetTransformInfo &TTI)
       : LDT(LI), DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy), LI(LI),
#endif
           if (Pred != FC0.ExitBlock) {
             WorkList.emplace_back(Pred->getTerminator());
             TreeUpdates.emplace_back(
                 DominatorTree::UpdateType(DominatorTree::Delete, Pred, BB));
           }
         }
         // Cannot modify the predecessors inside the above loop as it will cause
         // the iterators to be nullptrs, causing memory errors.
-        for (Instruction *CurrentBranch: WorkList) {
+        for (Instruction *CurrentBranch : WorkList) {
           BasicBlock *Succ = CurrentBranch->getSuccessor(0);
           if (Succ == BB)
             Succ = CurrentBranch->getSuccessor(1);
           ReplaceInstWithInst(CurrentBranch, BranchInst::Create(Succ));
         }
 
         DTU.applyUpdates(TreeUpdates);
         DTU.flush();
for (auto &CandidateSet : FusionCandidates) {
               !haveIdenticalGuards(*FC0, *FC1) && !TCDifference) {
             LLVM_DEBUG(dbgs() << "Fusion candidates do not have identical "
                                  "guards. Not Fusing.\n");
             reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
                                                        NonIdenticalGuards);
             continue;
           }
 
-          if (!isSafeToMoveBefore(*FC1->Preheader,
-                                  *FC0->Preheader->getTerminator(), DT, &PDT,
-                                  &DI)) {
-            LLVM_DEBUG(dbgs() << "Fusion candidate contains unsafe "
-                                 "instructions in preheader. Not fusing.\n");
-            reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
-                                                       NonEmptyPreheader);
-            continue;
-          }
-
           if (FC0->GuardBranch) {
             assert(FC1->GuardBranch && "Expecting valid FC1 guard branch");
 
             if (!isSafeToMoveBefore(*FC0->ExitBlock,
                                     *FC1->ExitBlock->getFirstNonPHIOrDbg(), DT,
                                     &PDT, &DI)) {
               LLVM_DEBUG(dbgs() << "Fusion candidate contains unsafe "
                                    "instructions in exit block. Not fusing.\n");
for (auto &CandidateSet : FusionCandidates) {
           // violate them.
           if (!dependencesAllowFusion(*FC0, *FC1)) {
             LLVM_DEBUG(dbgs() << "Memory dependencies do not allow fusion!\n");
             reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
                                                        InvalidDependencies);
             continue;
           }
 
+          // If the second loop has instructions in the pre-header, attempt to
+          // hoist them up to the first loop's pre-header or sink them into the
+          // body of the second loop.
+          SmallVector<Instruction *, 4> SafeToHoist;
+          SmallVector<Instruction *, 4> SafeToSink;
+          // At this point, this is the last remaining legality check.
+          // Which means if we can make this pre-header empty, we can fuse
+          // these loops
+          if (!isEmptyPreheader(*FC1)) {
+            LLVM_DEBUG(dbgs() << "Fusion candidate does not have empty "
+                                 "preheader.\n");
+
+            // If it is not safe to hoist/sink all instructions in the
+            // pre-header, we cannot fuse these loops.
+            if (!collectMovablePreheaderInsts(*FC0, *FC1, SafeToHoist,
+                                              SafeToSink)) {
+              LLVM_DEBUG(dbgs() << "Could not hoist/sink all instructions in "
+                                   "Fusion Candidate Pre-header.\n"
+                                << "Not Fusing.\n");
+              reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
+                                                         NonEmptyPreheader);
+              continue;
+            }
+          }
+
           bool BeneficialToFuse = isBeneficialFusion(*FC0, *FC1);
           LLVM_DEBUG(dbgs()
                      << "\tFusion appears to be "
                      << (BeneficialToFuse ? "" : "un") << "profitable!\n");
           if (!BeneficialToFuse) {
             reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
                                                        FusionNotBeneficial);
             continue;
           }
           // All analysis has completed and has determined that fusion is legal
           // and profitable. At this point, start transforming the code and
           // perform fusion.
 
+          // Execute the hoist/sink operations on preheader instructions
+          movePreheaderInsts(*FC0, *FC1, SafeToHoist, SafeToSink);
+
           LLVM_DEBUG(dbgs() << "\tFusion is performed: " << *FC0 << " and "
                             << *FC1 << "\n");
 
           FusionCandidate FC0Copy = *FC0;
           // Peel the loop after determining that fusion is legal. The Loops
           // will still be safe to fuse after the peeling is performed.
           bool Peel = TCDifference && *TCDifference > 0;
           if (Peel)
for (auto &CandidateSet : FusionCandidates) {
 
           Fused = true;
         }
       }
     }
     return Fused;
   }
 
+  /// Collect instructions in the \p FC1 Preheader that can be hoisted
+  /// to the \p FC0 Preheader or sunk into the \p FC1 Body
+  bool collectMovablePreheaderInsts(
+      const FusionCandidate &FC0, const FusionCandidate &FC1,
+      SmallVector<Instruction *, 4> &SafeToHoist,
+      SmallVector<Instruction *, 4> &SafeToSink) const {
+    BasicBlock *FC1Preheader = FC1.Preheader;
+    for (Instruction &I : *FC1Preheader) {
+      // Can't move a branch
+      if (&I == FC1Preheader->getTerminator())
+        continue;
+      // If the instruction has side-effects, give up.
+      // TODO: The case of mayReadFromMemory we can handle but requires
+      // additional work with a dependence analysis so for now we give
+      // up on memory reads.
+      if (I.mayHaveSideEffects() || I.mayReadFromMemory()) {
+        LLVM_DEBUG(dbgs() << "Inst: " << I << " may have side-effects.\n");
+        return false;
+      }
+
+      LLVM_DEBUG(dbgs() << "Checking Inst: " << I << "\n");
+
+      // First check if can be hoisted
+      // If the operands of this instruction dominate the FC0 Preheader
+      // target block, then it is safe to move them to the end of the FC0
+      const BasicBlock *FC0PreheaderTarget =
+          FC0.Preheader->getSingleSuccessor();
+      assert(FC0PreheaderTarget &&
+             "Expected single successor for loop preheader.");
+      bool CanHoistInst = true;
+      for (Use &Op : I.operands()) {
+        if (auto *OpInst = dyn_cast<Instruction>(Op)) {
+          bool OpHoisted = is_contained(SafeToHoist, OpInst);
+          // Check if we have already decided to hoist this operand. In this
+          // case, it does not dominate FC0 *yet*, but will after we hoist it.
+          if (!(OpHoisted || DT.dominates(OpInst, FC0PreheaderTarget))) {
+            CanHoistInst = false;
+            break;
+          }
+        }
+      }
+      if (CanHoistInst) {
+        SafeToHoist.push_back(&I);
+        LLVM_DEBUG(dbgs() << "\tSafe to hoist.\n");
+      } else {
+        LLVM_DEBUG(dbgs() << "\tCould not hoist. Trying to sink...\n");
+
+        for (User *U : I.users()) {
+          if (auto *UI{dyn_cast<Instruction>(U)}) {
+            // Cannot sink if user in loop
+            // If FC1 has phi users of this value, we cannot sink it into FC1.
+            if (FC1.L->contains(UI)) {
+              // Cannot hoist or sink this instruction. No hoisting/sinking
+              // should take place, loops should not fuse
+              LLVM_DEBUG(dbgs() << "\tCould not sink.\n");
+              return false;
+            }
+          }
+        }
+        SafeToSink.push_back(&I);
+        LLVM_DEBUG(dbgs() << "\tSafe to sink.\n");
+      }
+    }
+    LLVM_DEBUG(
+        dbgs() << "All preheader instructions could be sunk or hoisted!\n");
+    return true;
+  }
+
   /// Rewrite all additive recurrences in a SCEV to use a new loop.
   class AddRecLoopReplacer : public SCEVRewriteVisitor<AddRecLoopReplacer> {
   public:
     AddRecLoopReplacer(ScalarEvolution &SE, const Loop &OldL, const Loop &NewL,
                        bool UseMax = true)
         : SCEVRewriteVisitor(SE), Valid(true), UseMax(UseMax), OldL(OldL),
           NewL(NewL) {}
 
bool isAdjacent(const FusionCandidate &FC0,
                   const FusionCandidate &FC1) const {
     // If the successor of the guard branch is FC1, then the loops are adjacent
     if (FC0.GuardBranch)
       return FC0.getNonLoopBlock() == FC1.getEntryBlock();
     else
       return FC0.ExitBlock == FC1.getEntryBlock();
   }
 
+  bool isEmptyPreheader(const FusionCandidate &FC) const {
+    return FC.Preheader->size() == 1;
+  }
+
+  /// Hoist \p FC1 Preheader instructions to \p FC0 Preheader
+  /// and sink others into the body of \p FC1.
+  void movePreheaderInsts(const FusionCandidate &FC0,
+                          const FusionCandidate &FC1,
+                          SmallVector<Instruction *, 4> &HoistInsts,
+                          SmallVector<Instruction *, 4> &SinkInsts) const {
+
+    // All preheader instructions except the branch must be hoisted or sunk
+    assert(HoistInsts.size() + SinkInsts.size() == FC1.Preheader->size() - 1 &&
+           "Attempting to sink and hoist preheader instructions, but not all "
+           "the preheader instructions are accounted for.");
+
+    NumHoistedInsts += HoistInsts.size();
+    NumSunkInsts += SinkInsts.size();
+
+    LLVM_DEBUG(if (VerboseFusionDebugging) {
+      if (!HoistInsts.empty())
+        dbgs() << "Hoisting: \n";
+      for (Instruction *I : HoistInsts)
+        dbgs() << *I << "\n";
+      if (!SinkInsts.empty())
+        dbgs() << "Sinking: \n";
+      for (Instruction *I : SinkInsts)
+        dbgs() << *I << "\n";
+    });
+
+    for (Instruction *I : HoistInsts) {
+      assert(I->getParent() == FC1.Preheader);
+      I->moveBefore(FC0.Preheader->getTerminator());
+    }
+    // insert instructions in reverse order to maintain dominance relationship
+    for (Instruction *I : reverse(SinkInsts)) {
+      assert(I->getParent() == FC1.Preheader);
+      I->moveBefore(&*FC1.ExitBlock->getFirstInsertionPt());
+    }
+  }
+
   /// Determine if two fusion candidates have identical guards
   ///
   /// This method will determine if two fusion candidates have the same guards.
   /// The guards are considered the same if:
   ///   1. The instructions to compute the condition used in the compare are
   ///      identical.
   ///   2. The successors of the guard have the same flow into/around the loop.
   /// If the compare instructions are identical, then the first successor of the
void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addPreserved<LoopInfoWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<PostDominatorTreeWrapperPass>();
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
+
     auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     auto &DI = getAnalysis<DependenceAnalysisWrapperPass>().getDI();
     auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
     auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
     auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
     auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     const TargetTransformInfo &TTI =

llvm/test/Transforms/LoopFusion/hoist_preheader.ll

+; RUN: opt -S -loop-fusion < %s | FileCheck %s
+
+define void @hoist_preheader(i32 %N) {
+
+; CHECK:pre1:
+; CHECK-NEXT:  %hoistme = add i32 1, %N
+; CHECK-NEXT:  %hoistme2 = add i32 1, %hoistme
+; CHECK-NEXT:  br label %body1
+pre1:
+  br label %body1
+
+; CHECK: body1:
+; CHECK-NOT:  %hoistme
+body1:  ; preds = %pre1, %body1
+  %i = phi i32 [%i_next, %body1], [0, %pre1]
+  %i_next = add i32 1, %i
+  %cond = icmp ne i32 %i, %N
+  br i1 %cond, label %body1, label %pre2
+
+pre2:
+  %hoistme = add i32 1, %N
+  %hoistme2 = add i32 1, %hoistme
+  br label %body2
+
+body2:  ; preds = %pre2, %body2
+  %i2 = phi i32 [%i_next2, %body2], [0, %pre2]
+  %i_next2 = add i32 1, %i2
+  %cond2 = icmp ne i32 %i2, %N
+  br i1 %cond2, label %body2, label %exit
+
+exit:
+  ret void
+}

llvm/test/Transforms/LoopFusion/no_sink_hoist.ll

+; RUN: opt -S -loop-simplify -loop-fusion -debug-only=loop-fusion < %s 2>&1 | FileCheck %s
+; REQUIRES: asserts
+; CHECK: Could not hoist/sink all instructions
+
+define void @sink_preheader(i32 %N) {
+; CHECK:pre1:
+; CHECK-NEXT:  br label %body1
+pre1:
+  br label %body1
+
+; CHECK:body1: 
+; CHECK-NOT:  %stay =
+body1:  ; preds = %pre1, %body1
+  %i = phi i32 [%i_next, %body1], [0, %pre1]
+  %i_next = add i32 1, %i
+  %cond = icmp ne i32 %i, %N
+  %barrier = add i32 1, %N
+  br i1 %cond, label %body1, label %pre2
+
+; CHECK:pre2:
+; CHECK: %stay =
+pre2:
+  %stay = add i32 1, %barrier
+  br label %body2
+
+; CHECK: body2:
+; CHECK-NOT: %stay =
+body2:  ; preds = %pre2, %body2
+  %i2 = phi i32 [%i_next2, %body2], [0, %pre2]
+  %i_next2 = add i32 1, %i2
+  %cond2 = icmp ne i32 %i2, %N
+  %barrier2 = add i32 1, %stay
+  br i1 %cond2, label %body2, label %exit
+
+; CHECK: exit:
+; CHECK-NOT: %stay =
+exit:
+  ret void
+}

llvm/test/Transforms/LoopFusion/no_sink_hoist_inner_barrier.ll

+; RUN: opt -S -loop-fusion -debug-only=loop-fusion < %s 2>&1 | FileCheck %s
+; REQUIRES: asserts
+
+; CHECK: Could not hoist/sink all instructions
+
+define void @sink_preheader(i32 %N) {
+; CHECK:pre1:
+; CHECK-NEXT:  br label %body1
+pre1:
+  br label %body1
+
+; CHECK:body1: 
+; CHECK-NOT: %no_hoist =
+; CHECK-NOT: %no_hoist_sink =
+; CHECK-NOT: %no_sink =
+body1:  ; preds = %pre1, %body1
+  %i = phi i32 [%i_next, %body1], [0, %pre1]
+  %i_next = add i32 1, %i
+  %cond = icmp ne i32 %i, %N
+  %barrier = add i32 1, %N
+  br i1 %cond, label %body1, label %pre2
+
+; CHECK:pre2:
+; CHECK: %no_hoist =
+; CHECK: %no_hoist_sink =
+; CHECK: %no_sink =
+pre2:
+  %no_hoist = add i32 1, %barrier
+  %no_hoist_sink = add i32 1, %no_hoist
+  %no_sink = add i32 1, %no_hoist_sink
+  br label %body2
+
+; CHECK: body2:
+; CHECK-NOT: %no_hoist =
+; CHECK-NOT: %no_hoist_sink =
+; CHECK-NOT: %no_sink =
+body2:  ; preds = %pre2, %body2
+  %i2 = phi i32 [%i_next2, %body2], [0, %pre2]
+  %i_next2 = add i32 1, %i2
+  %cond2 = icmp ne i32 %i2, %N
+  %barrier2 = add i32 1, %no_sink
+  br i1 %cond2, label %body2, label %exit
+
+; CHECK: exit:
+; CHECK-NOT: %stay =
+exit:
+  ret void
+}

llvm/test/Transforms/LoopFusion/no_sink_hoist_store.ll

+; RUN: opt -S -loop-simplify -loop-fusion -debug-only=loop-fusion < %s 2>&1 | FileCheck %s
+; REQUIRES: asserts
+; CHECK: have side-effects.
+; CHECK: Could not hoist/sink all instructions
+
+@A = common global [100 x i32] zeroinitializer, align 16
+define void @sink_preheader(i32 %N) {
+; CHECK:pre1:
+; CHECK-NEXT:  %ptr = alloca i32, align 4
+; CHECK-NEXT:  br label %body1
+pre1:
+  %ptr = alloca i32
+  br label %body1
+
+; CHECK:body1: 
+; CHECK-NOT:  %stay =
+body1:  ; preds = %pre1, %body1
+  %i = phi i32 [%i_next, %body1], [0, %pre1]
+  %i_next = add i32 1, %i
+  %cond = icmp ne i32 %i, %N
+  br i1 %cond, label %body1, label %pre2
+
+; CHECK:pre2:
+; CHECK-NEXT: store i32 3, i32* %ptr
+pre2:
+  store i32 3, i32* %ptr
+  br label %body2
+
+; CHECK: body2:
+; CHECK-NOT: %stay =
+body2:  ; preds = %pre2, %body2
+  %i2 = phi i32 [%i_next2, %body2], [0, %pre2]
+  %i_next2 = add i32 1, %i2
+  %cond2 = icmp ne i32 %i2, %N
+  br i1 %cond2, label %body2, label %exit
+
+; CHECK: exit:
+; CHECK-NOT: %stay =
+exit:
+  ret void
+}

llvm/test/Transforms/LoopFusion/no_sink_hoist_unknown_function.ll

+; RUN: opt -S -loop-simplify -loop-fusion -debug-only=loop-fusion < %s 2>&1 | FileCheck %s
+; REQUIRES: asserts
+; CHECK: may have side-effects
+; CHECK: Could not hoist/sink all instructions
+
+declare void @unknown_func()
+
+define void @sink_preheader(i32 %N) {
+; CHECK:pre1:
+; CHECK-NEXT:  br label %body1
+pre1:
+  br label %body1
+
+; CHECK:body1: 
+; CHECK-NOT:  %stay =
+body1:  ; preds = %pre1, %body1
+  %i = phi i32 [%i_next, %body1], [0, %pre1]
+  %i_next = add i32 1, %i
+  %cond = icmp ne i32 %i, %N
+  br i1 %cond, label %body1, label %pre2
+
+; CHECK:pre2:
+; CHECK-NEXT: call void @unknown_func()
+pre2:
+  call void @unknown_func()
+  br label %body2
+
+; CHECK: body2:
+; CHECK-NOT: %stay =
+body2:  ; preds = %pre2, %body2
+  %i2 = phi i32 [%i_next2, %body2], [0, %pre2]
+  %i_next2 = add i32 1, %i2
+  %cond2 = icmp ne i32 %i2, %N
+  br i1 %cond2, label %body2, label %exit
+
+; CHECK: exit:
+; CHECK-NOT: %stay =
+exit:
+  ret void
+}

llvm/test/Transforms/LoopFusion/simple.ll

for.second:
   %cmp.j = icmp slt i64 %inc.j, 100
   br i1 %cmp.j, label %for.second, label %for.second.exit
 
 for.second.exit:
   ret i32 %add
 }
 
 ; Test that `%add` cannot be moved to basic block entry, as it uses %i, which
-; defined after basic block entry. And the two loops for.first and for.second
-; are not fused.
+; defined after basic block entry. It also cannot be moved to for.second.exit 
+; since it is used in for.second. Check also that the two loops for.first and
+; for.second are not fused.
 
 define i64 @unsafe_preheader(i32* %A, i64 %x) {
 ; CHECK-LABEL: @unsafe_preheader(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_FIRST:%.*]]
 ; CHECK:       for.first:
 ; CHECK-NEXT:    [[I:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INC_I:%.*]], [[FOR_FIRST]] ]
 ; CHECK-NEXT:    [[AI:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[I]]
 ; CHECK-NEXT:    store i32 0, i32* [[AI]], align 4
 ; CHECK-NEXT:    [[INC_I]] = add nsw i64 [[I]], 1
 ; CHECK-NEXT:    [[CMP_I:%.*]] = icmp slt i64 [[INC_I]], 100
 ; CHECK-NEXT:    br i1 [[CMP_I]], label [[FOR_FIRST]], label [[FOR_FIRST_EXIT:%.*]]
 ; CHECK:       for.first.exit:
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i64 [[X:%.*]], [[I]]
 ; CHECK-NEXT:    br label [[FOR_SECOND:%.*]]
 ; CHECK:       for.second:
-; CHECK-NEXT:    [[J:%.*]] = phi i64 [ 0, [[FOR_FIRST_EXIT]] ], [ [[INC_J:%.*]], [[FOR_SECOND]] ]
+; CHECK-NEXT:    [[J:%.*]] = phi i64 [ [[ADD]], [[FOR_FIRST_EXIT]] ], [ [[INC_J:%.*]], [[FOR_SECOND]] ]
 ; CHECK-NEXT:    [[AJ:%.*]] = getelementptr inbounds i32, i32* [[A]], i64 [[J]]
 ; CHECK-NEXT:    store i32 2, i32* [[AJ]], align 4
 ; CHECK-NEXT:    [[INC_J]] = add nsw i64 [[J]], 1
 ; CHECK-NEXT:    [[CMP_J:%.*]] = icmp slt i64 [[INC_J]], 100
 ; CHECK-NEXT:    br i1 [[CMP_J]], label [[FOR_SECOND]], label [[FOR_SECOND_EXIT:%.*]]
 ; CHECK:       for.second.exit:
 ; CHECK-NEXT:    ret i64 [[ADD]]
 ;
 entry:
   br label %for.first
 
 for.first:
   %i = phi i64 [ 0, %entry ], [ %inc.i, %for.first ]
   %Ai = getelementptr inbounds i32, i32* %A, i64 %i
   store i32 0, i32* %Ai, align 4
   %inc.i = add nsw i64 %i, 1
   %cmp.i = icmp slt i64 %inc.i, 100
   br i1 %cmp.i, label %for.first, label %for.first.exit
 
 for.first.exit:
   %add = add nsw i64 %x, %i
   br label %for.second
 
 for.second:
-  %j = phi i64 [ 0, %for.first.exit ], [ %inc.j, %for.second ]
+  %j = phi i64 [ %add, %for.first.exit ], [ %inc.j, %for.second ]
   %Aj = getelementptr inbounds i32, i32* %A, i64 %j
   store i32 2, i32* %Aj, align 4
   %inc.j = add nsw i64 %j, 1
   %cmp.j = icmp slt i64 %inc.j, 100
   br i1 %cmp.j, label %for.second, label %for.second.exit
 
 for.second.exit:
   ret i64 %add
 }

llvm/test/Transforms/LoopFusion/sink_preheader.ll

+; RUN: opt -S -loop-fusion < %s | FileCheck %s
+
+define void @sink_preheader(i32 %N) {
+; CHECK-LABEL: @sink_preheader(
+; CHECK-NEXT:  pre1:
+; CHECK-NEXT:    br label [[BODY1:%.*]]
+; CHECK:       body1:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[BODY1]] ], [ 0, [[PRE1:%.*]] ]
+; CHECK-NEXT:    [[I2:%.*]] = phi i32 [ [[I_NEXT2:%.*]], [[BODY1]] ], [ 0, [[PRE1]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add i32 1, [[I]]
+; CHECK-NEXT:    [[COND:%.*]] = icmp ne i32 [[I]], [[N:%.*]]
+; CHECK-NEXT:    [[BARRIER:%.*]] = add i32 1, [[N]]
+; CHECK-NEXT:    [[I_NEXT2]] = add i32 1, [[I2]]
+; CHECK-NEXT:    [[COND2:%.*]] = icmp ne i32 [[I2]], [[N]]
+; CHECK-NEXT:    br i1 [[COND2]], label [[BODY1]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[SINKME:%.*]] = add i32 1, [[BARRIER]]
+; CHECK-NEXT:    [[SINKME2:%.*]] = add i32 1, [[BARRIER]]
+; CHECK-NEXT:    [[SINKME3:%.*]] = add i32 1, [[SINKME2]]
+; CHECK-NEXT:    ret void
+;
+pre1:
+  br label %body1
+
+body1:  ; preds = %pre1, %body1
+  %i = phi i32 [%i_next, %body1], [0, %pre1]
+  %i_next = add i32 1, %i
+  %cond = icmp ne i32 %i, %N
+  %barrier = add i32 1, %N
+  br i1 %cond, label %body1, label %pre2
+
+pre2:
+  %sinkme = add i32 1, %barrier
+  %sinkme2 = add i32 1, %barrier
+  %sinkme3 = add i32 1, %sinkme2
+  br label %body2
+
+body2:  ; preds = %pre2, %body2
+  %i2 = phi i32 [%i_next2, %body2], [0, %pre2]
+  %i_next2 = add i32 1, %i2
+  %cond2 = icmp ne i32 %i2, %N
+  br i1 %cond2, label %body2, label %exit
+
+exit:
+  ret void
+}