Intergerate Loop Peeling into Loop Fusion

[sidbav]

Summary

This patch adds the ability to peel off iterations of the first loop in loop fusion. This can allow for both loops to have the same trip count, making it legal for them to be fused together.

Here is a simple scenario peeling can be used in loop fusion:

for (i = 0; i < 10; ++i)
  a[i] = a[i] + 3;
for (j = 1; j < 10; ++j)
  b[j] = b[j] + 5;

Here is we can make use of peeling, and then fuse the two loops together. We can peel off the 0th iteration of the loop i, and then combine loop i and j for i = 1 to 10.

a[0] = a[0] +3;
for (i = 1; i < 10; ++i) {
  a[i] = a[i] + 3;
  b[i] = b[i] + 5;
}

Currently peeling with loop fusion is only supported for loops with constant trip counts and a single exit point. Both unguarded and guarded loops are supported.

This patch is a followup to D80580. In that patch I separate the peeling specific parameters in the UnrollingPreferences struct and form a new struct called PeelingPreferences.

The diff of this patch was created assuming that D80580 is merged.

EDIT: I removed the Loop Peeling files since it is unrelated to fusion. The Loop Peeling changes revision is here: D83056

[Meinersbur]

Could you update the patch with context (git diff -U999999)?

[Meinersbur]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

704

[style] Function names should start with a lower case letter.

712

Is it possible to return {false, None}? The pair type should be deducible by the compiler and it immediately shows that it returns.

727

Did you consider assigning it to a variable with a meaningful name first such as SameTripCount, then return {SameTripCount, diff}?

749

[style] Local variable name should start with a capital letter.

766

[style] Function names should start with a lower case letter

777

The call result is only used when asserts are enabled, please use #ifndef NDEBUG around the call.

790

[typo] exectue

953–955

[nit] Please avoid such spurious changes in the Differential

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

166 ↗

(On Diff #274664)

[nit] Please avoid unrelated changes

llvm/lib/Transforms/Utils/CMakeLists.txt

38 ↗

(On Diff #274664)

Did you consider making this rename a separate patch? It adds a lot of noise to this one.

[sidbav]

Address @Meinersbur comments. Remove the Loop Peeling files since it is unrelated to fusion. The Loop Peeling changes revision is here: D83056

[bmahjour]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

124

We only really need one option to control peeling for loop fusion. You can remove loop-fusion-peel and change the default for this threshold to 0. I don't know what others feel about this, but I'd rather have shorter commands when possible.

754

nit: Loop -> loop

762

nit: Peel Loop -> peel loop.

810

nit: Peeled -> peeled

864

nit: comments should be full sentences ending with a period.

865

is able to be peeled -> can be peeled

866

the different -> different

870

Please change this to give up on such loops instead of asserting.

1258–1259

This function no longer does what this comment says. Please update the comment.

1565

moveInstructionsToTheBeginning(FC0.Peeled ? *FC0ExitBlockSuccessor : *FC0.ExitBlock, *FC1.ExitBlock, DT, PDT, DI);

1587–1589

BasicBlock *BBToUpdate = FC0.Peeled ? FC0ExitBlockSuccessor : FC0.ExitBlock;
BBToUpdate->getTerminator()->replaceUsesOfWith(FC1GuardBlock, FC1.Header);

[sidbav]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

124

I agree with this idea, setting up the option like this will allow for this option to serve both purposes, of enabling peeling for fusion, and specifying the max value for fusion.

[sidbav]

Address Bardia's comments, major change is removing the loop-fusion-peel option.

[bmahjour]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

864

we are checking that the user specifies...

867

I don't think we should check for occurrence of the option on the command line. It suffices to just compare TCDifference against the FusionPeelMaxCount. When the option is not specified the value of FusionPeelMaxCount will be the default, which is currently zero and would prevent peeling).

Similarly FusionPeelMaxCount != 0 is redundant.

[sidbav]

Address Bardia's comments.

[sidbav]

Ping @ reviewers! Thanks!

[bmahjour]

Added some minor comments. Overall looks good to me. I'll approve if there are no objections by EOD today.

llvm/lib/Transforms/Scalar/LoopFuse.cpp

1564

to the to the -> to the

llvm/test/Transforms/LoopFusion/guarded_peel.ll

20

CHECK -> CHECK-NEXT

24

CHECK -> CHECK-NEXT

26

CHECK -> CHECK-NEXT

27

Add: CHECK: for.first.entry.peel.newph

There are also a number of empty basic blocks that make the test less readable. One way to make it more readable is to put a CHECK-NEXT (instead of a CHECK) right after the CHECK for the label to indicate that there is no code in the basic block.

llvm/test/Transforms/LoopFusion/peel.ll

31

Please use CHECK-NEXT for all branches that immediately follow the label.

[sidbav]

Address Bardia's comments

[rupprecht]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

394–396

FYI, the comment here explains why PDT should not be extracted to a var, which this patch did. Perhaps a previous version of this patch needed it? Fixed in 1ee1da1ea5728c2fe07bbf18bb25728ac3512e92.

[1075/3350] Building CXX object lib/Transforms/Scalar/CMakeFiles/LLVMScalarOpts.dir/LoopFuse.cpp.o
/home/rupprecht/src/llvm-project/llvm/lib/Transforms/Scalar/LoopFuse.cpp:390:30: warning: unused variable 'PDT' [-Wunused-variable]
    const PostDominatorTree *PDT = LHS.PDT;

[MaskRay]

I am sorry but I reverted this in 8a268bec1b02dd446fbc36e20d0a9af45d764f67.

3 check-llvm-transforms-loopfusion tests failed in an ASAN build.

BTW, your git commit contains extra Phabricator tags. You can drop Reviewers: Subscribers: Tags: and the text Summary: from the git commit with the following script:

arcfilter () {
        arc amend
        git log -1 --pretty=%B | awk '/Reviewers:|Subscribers:/{p=1} /Reviewed By:|Differential Revision:/{p=0} !p && !/^Summary:$/ {sub(/^Summary: /,"");print}' | git commit --amend --date=now -F -
}

Reviewed By: is considered important by some people. Please keep the tag. (--date=now is my personal preference (author dates are usually not useful. Using committer dates can make log almost monotonic in time))

llvm/utils/git/pre-push.py can validate the message does not include unneeded tags. Please clean up tags for future commits (arc land does not seem to work). Thanks.

llvm/lib/Transforms/Scalar/LoopFuse.cpp

795

This line may operate on a deleted BB.

[MaskRay]

llvm/test/Transforms/LoopFusion/guarded_unsafeblock_peel.ll

2

file-name.ll is more common than file_name.ll

11

Add some spaces after ; CHECK: so that they align with ; CHECK-NEXT:
I usually indent instructions more than labels.

; CHECK:      for.first.preheader:
; CHECK-NEXT:   br label %for.first

llvm/test/Transforms/LoopFusion/peel.ll

4

This tests or just Test

[MaskRay]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

730

Consider const if not mutable

751

The full stop can usually be omitted.

http://llvm.org/docs/CodingStandards.html#error-and-warning-messages

778

No need to add too many new lines in this function. It actually harms readability (people can't see too many lines in a screen)

1353

Rationale for an increase? Large inline count can consume more stack space.

[MaskRay]

llvm/test/Transforms/LoopFusion/guarded_unsafeblock_peel.ll

10

Function names are unique. Use ; CHECK-LABEL: -> they improve FileCheck output when some instructions below don't match CHECK lines.

llvm/test/Transforms/LoopFusion/nonadjacent_peel.ll

56

The comments are not aligned.

[sidbav]

Address the ASAN build failures (major change is around line 795 in LoopFuse.cpp file). Also address some issues @MaskRay pointed out in lit tests.

[sidbav]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

1353

Initially was planning to have the logic from lines 795-805 in this block, which is why I increased from 8 -> 16, but I forgot to change it back.

llvm/test/Transforms/LoopFusion/guarded_unsafeblock_peel.ll

2

The Loop Fusion lit tests follow the file_name.ll convention, so I will keep the files names like this.

[bmahjour]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

804

Predecessors -> predecessors

806

Please use range-based for loops whenever possible.

[MaskRay]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

806

LLVM style uses ++i (http://llvm.org/docs/CodingStandards.html )

llvm/test/Transforms/LoopFusion/peel.ll

21

It is usually more robust if you include ( - when you have multiple functions named function*, void @function( will still work.

107

Delete trailing empty line

[sidbav]

Address review comments

[sidbav]

Missed one comment from Bardia, address that comment.

[MaskRay]

LGTM.

llvm/lib/Transforms/Scalar/LoopFuse.cpp

 /// This implementation currently does not make any modifications to remove
 /// conditions for fusion. Code transformations to make loops conform to each of
 /// the conditions for fusion are discussed in more detail in the document
 /// above. These can be added to the current implementation in the future.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/LoopFuse.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #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/UnrollLoop.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");
static cl::opt<FusionDependenceAnalysisChoice> FusionDependenceAnalysis(
     cl::values(clEnumValN(FUSION_DEPENDENCE_ANALYSIS_SCEV, "scev",
                           "Use the scalar evolution interface"),
                clEnumValN(FUSION_DEPENDENCE_ANALYSIS_DA, "da",
                           "Use the dependence analysis interface"),
                clEnumValN(FUSION_DEPENDENCE_ANALYSIS_ALL, "all",
                           "Use all available analyses")),
     cl::Hidden, cl::init(FUSION_DEPENDENCE_ANALYSIS_ALL), cl::ZeroOrMore);
 
+static cl::opt<unsigned> FusionPeelMaxCount(
+    "loop-fusion-peel-max-count", cl::init(0), cl::Hidden,
+    cl::desc("Max number of iterations to be peeled from a loop, such that "
+             "fusion can take place"));
+
 #ifndef NDEBUG
 static cl::opt<bool>
     VerboseFusionDebugging("loop-fusion-verbose-debug",
                            cl::desc("Enable verbose debugging for Loop Fusion"),
                            cl::Hidden, cl::init(false), cl::ZeroOrMore);
 #endif
 
 namespace {
struct FusionCandidate {
   /// Vector of instructions in this loop that read from memory
   SmallVector<Instruction *, 16> MemReads;
   /// Vector of instructions in this loop that write to memory
   SmallVector<Instruction *, 16> MemWrites;
   /// Are all of the members of this fusion candidate still valid
   bool Valid;
   /// Guard branch of the loop, if it exists
   BranchInst *GuardBranch;
+  /// Peeling Paramaters of the Loop.
+  TTI::PeelingPreferences PP;
+  /// Can you Peel this Loop?
+  bool AbleToPeel;
+  /// Has this loop been Peeled
+  bool Peeled;
 
   /// Dominator and PostDominator trees are needed for the
   /// 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.
   const DominatorTree *DT;
   const PostDominatorTree *PDT;
 
   OptimizationRemarkEmitter &ORE;
 
   FusionCandidate(Loop *L, const DominatorTree *DT,
-                  const PostDominatorTree *PDT, OptimizationRemarkEmitter &ORE)
+                  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()), DT(DT), PDT(PDT), ORE(ORE) {
+        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
     // the memory reads and writes If any instructions that prevent fusion are
     // found, invalidate this object and return.
     for (BasicBlock *BB : L->blocks()) {
       if (BB->hasAddressTaken()) {
         invalidate();
struct FusionCandidate {
   /// the preheader of the loop.
   BasicBlock *getEntryBlock() const {
     if (GuardBranch)
       return GuardBranch->getParent();
     else
       return Preheader;
   }
 
+  /// After Peeling the loop is modified quite a bit, hence all of the Blocks
+  /// need to be updated accordingly.
+  void updateAfterPeeling() {
+    Preheader = L->getLoopPreheader();
+    Header = L->getHeader();
+    ExitingBlock = L->getExitingBlock();
+    ExitBlock = L->getExitBlock();
+    Latch = L->getLoopLatch();
+    verify();
+  }
+
   /// Given a guarded loop, get the successor of the guard that is not in the
   /// loop.
   ///
   /// This method returns the successor of the loop guard that is not located
   /// within the loop (i.e., the successor of the guard that is not the
   /// preheader).
   /// This method is only valid for guarded loops.
   BasicBlock *getNonLoopBlock() const {
     assert(GuardBranch && "Only valid on guarded loops.");
     assert(GuardBranch->isConditional() &&
            "Expecting guard to be a conditional branch.");
+    if (Peeled)
+      return GuardBranch->getSuccessor(1);
     return (GuardBranch->getSuccessor(0) == Preheader)
                ? GuardBranch->getSuccessor(1)
                : GuardBranch->getSuccessor(0);
   }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   LLVM_DUMP_METHOD void dump() const {
     dbgs() << "\tGuardBranch: ";
struct FusionCandidateCompare {
   /// IF RHS dominates LHS and LHS post-dominates RHS, return false;
   bool operator()(const FusionCandidate &LHS,
                   const FusionCandidate &RHS) const {
     const DominatorTree *DT = LHS.DT;
 
     BasicBlock *LHSEntryBlock = LHS.getEntryBlock();
     BasicBlock *RHSEntryBlock = RHS.getEntryBlock();
 
     // Do not save PDT to local variable as it is only used in asserts and thus
     // will trigger an unused variable warning if building without asserts.
     assert(DT && LHS.PDT && "Expecting valid dominator tree");
 
     // Do this compare first so if LHS == RHS, function returns false.
     if (DT->dominates(RHSEntryBlock, LHSEntryBlock)) {
       // RHS dominates LHS
       // Verify LHS post-dominates RHS
       assert(LHS.PDT->dominates(LHSEntryBlock, RHSEntryBlock));
       return false;
     }
private:
   DomTreeUpdater DTU;
 
   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)
+            OptimizationRemarkEmitter &ORE, const DataLayout &DL,
+            AssumptionCache &AC, const TargetTransformInfo &TTI)
       : LDT(LI), DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy), LI(LI),
-        DT(DT), DI(DI), SE(SE), PDT(PDT), ORE(ORE) {}
+        DT(DT), DI(DI), SE(SE), PDT(PDT), ORE(ORE), AC(AC), TTI(TTI) {}
 
   /// This is the main entry point for loop fusion. It will traverse the
   /// specified function and collect candidate loops to fuse, starting at the
   /// outermost nesting level and working inwards.
   bool fuseLoops(Function &F) {
 #ifndef NDEBUG
     if (VerboseFusionDebugging) {
       LI.print(dbgs());
return ::isControlFlowEquivalent(*FC0.getEntryBlock(), *FC1.getEntryBlock(),
                                      DT, PDT);
   }
 
   /// Iterate over all loops in the given loop set and identify the loops that
   /// are eligible for fusion. Place all eligible fusion candidates into Control
   /// Flow Equivalent sets, sorted by dominance.
   void collectFusionCandidates(const LoopVector &LV) {
     for (Loop *L : LV) {
-      FusionCandidate CurrCand(L, &DT, &PDT, ORE);
+      TTI::PeelingPreferences PP =
+          gatherPeelingPreferences(L, SE, TTI, None, None);
+      FusionCandidate CurrCand(L, &DT, &PDT, ORE, PP);
       if (!CurrCand.isEligibleForFusion(SE))
         continue;
 
       // Go through each list in FusionCandidates and determine if L is control
       // flow equivalent with the first loop in that list. If it is, append LV.
       // If not, go to the next list.
       // If no suitable list is found, start another list and add it to
       // FusionCandidates.
#endif
   bool isBeneficialFusion(const FusionCandidate &FC0,
                           const FusionCandidate &FC1) {
     return true;
   }
 
   /// Determine if two fusion candidates have the same trip count (i.e., they
   /// execute the same number of iterations).
   ///
-  /// Note that for now this method simply returns a boolean value because there
-  /// are no mechanisms in loop fusion to handle different trip counts. In the
-  /// future, this behaviour can be extended to adjust one of the loops to make
-  /// the trip counts equal (e.g., loop peeling). When this is added, this
-  /// interface may need to change to return more information than just a
-  /// boolean value.
-  bool identicalTripCounts(const FusionCandidate &FC0,
-                           const FusionCandidate &FC1) const {
+  /// This function will return a pair of values. The first is a boolean,
+  /// stating whether or not the two candidates are known at compile time to
+  /// have the same TripCount. The second is the difference in the two
+  /// TripCounts. This information can be used later to determine whether or not
+  /// peeling can be performed on either one of the candiates.
+  std::pair<bool, Optional<unsigned>>
+  haveIdenticalTripCounts(const FusionCandidate &FC0,
+
     const SCEV *TripCount0 = SE.getBackedgeTakenCount(FC0.L);
     if (isa<SCEVCouldNotCompute>(TripCount0)) {
       UncomputableTripCount++;
       LLVM_DEBUG(dbgs() << "Trip count of first loop could not be computed!");
-      return false;
+      return {false, None};
     }
 
     const SCEV *TripCount1 = SE.getBackedgeTakenCount(FC1.L);
     if (isa<SCEVCouldNotCompute>(TripCount1)) {
       UncomputableTripCount++;
       LLVM_DEBUG(dbgs() << "Trip count of second loop could not be computed!");
-      return false;
+      return {false, None};
     }
+
     LLVM_DEBUG(dbgs() << "\tTrip counts: " << *TripCount0 << " & "
                       << *TripCount1 << " are "
                       << (TripCount0 == TripCount1 ? "identical" : "different")
                       << "\n");
 
-    return (TripCount0 == TripCount1);
+    if (TripCount0 == TripCount1)
+      return {true, 0};
+
+    LLVM_DEBUG(dbgs() << "The loops do not have the same tripcount, "
+                         "determining the difference between trip counts\n");
+
+    // Currently only considering loops with a single exit point
+    // and a non-constant trip count.
+    const unsigned TC0 = SE.getSmallConstantTripCount(FC0.L);
+    const unsigned TC1 = SE.getSmallConstantTripCount(FC1.L);
+
+    // If any of the tripcounts are zero that means that loop(s) do not have
+    // a single exit or a constant tripcount.
+    if (TC0 == 0 || TC1 == 0) {
+      LLVM_DEBUG(dbgs() << "Loop(s) do not have a single exit point or do not "
+                           "have a constant number of iterations. Peeling "
+                           "is not benefical\n");
+      return {false, None};
+    }
+
+    Optional<unsigned> Difference = None;
+    int Diff = TC0 - TC1;
+
+    if (Diff > 0)
+      Difference = Diff;
+    else {
+      LLVM_DEBUG(
+          dbgs() << "Difference is less than 0. FC1 (second loop) has more "
+                    "iterations than the first one. Currently not supported\n");
+    }
+
+    LLVM_DEBUG(dbgs() << "Difference in loop trip count is: " << Difference
+                      << "\n");
+
+    return {false, Difference};
+  }
+
+  void peelFusionCandidate(FusionCandidate &FC0, const FusionCandidate &FC1,
+                           unsigned PeelCount) {
+    assert(FC0.AbleToPeel && "Should be able to peel loop");
+
+    LLVM_DEBUG(dbgs() << "Attempting to peel first " << PeelCount
+                      << " iterations of the first loop. \n");
+
+    FC0.Peeled = peelLoop(FC0.L, PeelCount, &LI, &SE, &DT, &AC, true);
+    if (FC0.Peeled) {
+      LLVM_DEBUG(dbgs() << "Done Peeling\n");
+
+#ifndef NDEBUG
+      auto IdenticalTripCount = haveIdenticalTripCounts(FC0, FC1);
+
+      assert(IdenticalTripCount.first && *IdenticalTripCount.second == 0 &&
+             "Loops should have identical trip counts after peeling");
+#endif
+
+      FC0.PP.PeelCount += PeelCount;
+
+      // Peeling does not update the PDT
+      PDT.recalculate(*FC0.Preheader->getParent());
+
+      FC0.updateAfterPeeling();
+
+      // In this case the iterations of the loop are constant, so the first
+      // loop will execute completely (will not jump from one of
+      // the peeled blocks to the second loop). Here we are updating the
+      // branch conditions of each of the peeled blocks, such that it will
+      // branch to its successor which is not the preheader of the second loop
+      // in the case of unguarded loops, or the succesors of the exit block of
+      // the first loop otherwise. Doing this update will ensure that the entry
+      // block of the first loop dominates the entry block of the second loop.
+      BasicBlock *BB =
+          FC0.GuardBranch ? FC0.ExitBlock->getUniqueSuccessor() : FC1.Preheader;
+      if (BB) {
+        SmallVector<DominatorTree::UpdateType, 8> TreeUpdates;
+        SmallVector<Instruction *, 8> WorkList;
+        for (BasicBlock *Pred : predecessors(BB)) {
+          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) {
+          BasicBlock *Succ = CurrentBranch->getSuccessor(0);
+          if (Succ == BB)
+            Succ = CurrentBranch->getSuccessor(1);
+          ReplaceInstWithInst(CurrentBranch, BranchInst::Create(Succ));
+        }
+
+        DTU.applyUpdates(TreeUpdates);
+        DTU.flush();
+      }
+      LLVM_DEBUG(
+          dbgs() << "Sucessfully peeled " << FC0.PP.PeelCount
+                 << " iterations from the first loop.\n"
+                    "Both Loops have the same number of iterations now.\n");
+    }
   }
 
   /// Walk each set of control flow equivalent fusion candidates and attempt to
   /// fuse them. This does a single linear traversal of all candidates in the
   /// set. The conditions for legal fusion are checked at this point. If a pair
   /// of fusion candidates passes all legality checks, they are fused together
   /// and a new fusion candidate is created and added to the FusionCandidateSet.
   /// The original fusion candidates are then removed, as they are no longer
for (auto &CandidateSet : FusionCandidates) {
                  "Should not have removed loops in CandidateSet!");
 
           LLVM_DEBUG(dbgs() << "Attempting to fuse candidate \n"; FC0->dump();
                      dbgs() << " with\n"; FC1->dump(); dbgs() << "\n");
 
           FC0->verify();
           FC1->verify();
 
-          if (!identicalTripCounts(*FC0, *FC1)) {
+          // Check if the candidates have identical tripcounts (first value of
+          // pair), and if not check the difference in the tripcounts between
+          // the loops (second value of pair). The difference is not equal to
+          // None iff the loops iterate a constant number of times, and have a
+          // single exit.
+          std::pair<bool, Optional<unsigned>> IdenticalTripCountRes =
+              haveIdenticalTripCounts(*FC0, *FC1);
+          bool SameTripCount = IdenticalTripCountRes.first;
+          Optional<unsigned> TCDifference = IdenticalTripCountRes.second;
+
+          // Here we are checking that FC0 (the first loop) can be peeled, and
+          // both loops have different tripcounts.
+          if (FC0->AbleToPeel && !SameTripCount && TCDifference) {
+            if (*TCDifference > FusionPeelMaxCount) {
+              LLVM_DEBUG(dbgs()
+                         << "Difference in loop trip counts: " << *TCDifference
+                         << " is greater than maximum peel count specificed: "
+                         << FusionPeelMaxCount << "\n");
+            } else {
+              // Dependent on peeling being performed on the first loop, and
+              // assuming all other conditions for fusion return true.
+              SameTripCount = true;
+            }
+          }
+
+          if (!SameTripCount) {
             LLVM_DEBUG(dbgs() << "Fusion candidates do not have identical trip "
                                  "counts. Not fusing.\n");
             reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
                                                        NonEqualTripCount);
             continue;
           }
 
           if (!isAdjacent(*FC0, *FC1)) {
             LLVM_DEBUG(dbgs()
                        << "Fusion candidates are not adjacent. Not fusing.\n");
             reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1, NonAdjacent);
             continue;
           }
 
           // Ensure that FC0 and FC1 have identical guards.
           // If one (or both) are not guarded, this check is not necessary.
           if (FC0->GuardBranch && FC1->GuardBranch &&
-              !haveIdenticalGuards(*FC0, *FC1)) {
+              !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,
for (auto &CandidateSet : FusionCandidates) {
             reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,
                                                        InvalidDependencies);
             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.
 
           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)
+            peelFusionCandidate(FC0Copy, *FC1, *TCDifference);
+
           // Report fusion to the Optimization Remarks.
           // Note this needs to be done *before* performFusion because
           // performFusion will change the original loops, making it not
           // possible to identify them after fusion is complete.
-          reportLoopFusion<OptimizationRemark>(*FC0, *FC1, FuseCounter);
+          reportLoopFusion<OptimizationRemark>((Peel ? FC0Copy : *FC0), *FC1,
+                                               FuseCounter);
 
-          FusionCandidate FusedCand(performFusion(*FC0, *FC1), &DT, &PDT, ORE);
+          FusionCandidate FusedCand(
+              performFusion((Peel ? FC0Copy : *FC0), *FC1), &DT, &PDT, ORE,
+              FC0Copy.PP);
           FusedCand.verify();
           assert(FusedCand.isEligibleForFusion(SE) &&
                  "Fused candidate should be eligible for fusion!");
 
           // Notify the loop-depth-tree that these loops are not valid objects
           LDT.removeLoop(FC1->L);
 
           CandidateSet.erase(FC0);
bool haveIdenticalGuards(const FusionCandidate &FC0,
     // The compare instructions are identical.
     // Now make sure the successor of the guards have the same flow into/around
     // the loop
     if (FC0.GuardBranch->getSuccessor(0) == FC0.Preheader)
       return (FC1.GuardBranch->getSuccessor(0) == FC1.Preheader);
     else
       return (FC1.GuardBranch->getSuccessor(1) == FC1.Preheader);
   }
 
-  /// Simplify the condition of the latch branch of \p FC to true, when both of
-  /// its successors are the same.
+  /// Modify the latch branch of FC to be unconditional since successors of the
+  /// branch are the same.
   void simplifyLatchBranch(const FusionCandidate &FC) const {
     BranchInst *FCLatchBranch = dyn_cast<BranchInst>(FC.Latch->getTerminator());
     if (FCLatchBranch) {
       assert(FCLatchBranch->isConditional() &&
              FCLatchBranch->getSuccessor(0) == FCLatchBranch->getSuccessor(1) &&
              "Expecting the two successors of FCLatchBranch to be the same");
-      FCLatchBranch->setCondition(
-          llvm::ConstantInt::getTrue(FCLatchBranch->getCondition()->getType()));
+      BranchInst *NewBranch =
+          BranchInst::Create(FCLatchBranch->getSuccessor(0));
+      ReplaceInstWithInst(FCLatchBranch, NewBranch);
     }
   }
 
   /// Move instructions from FC0.Latch to FC1.Latch. If FC0.Latch has an unique
   /// successor, then merge FC0.Latch with its unique successor.
   void mergeLatch(const FusionCandidate &FC0, const FusionCandidate &FC1) {
     moveInstructionsToTheBeginning(*FC0.Latch, *FC1.Latch, DT, PDT, DI);
     if (BasicBlock *Succ = FC0.Latch->getUniqueSuccessor()) {
Loop *performFusion(const FusionCandidate &FC0, const FusionCandidate &FC1) {
     moveInstructionsToTheEnd(*FC1.Preheader, *FC0.Preheader, DT, PDT, DI);
 
     // Fusing guarded loops is handled slightly differently than non-guarded
     // loops and has been broken out into a separate method instead of trying to
     // intersperse the logic within a single method.
     if (FC0.GuardBranch)
       return fuseGuardedLoops(FC0, FC1);
 
-    assert(FC1.Preheader == FC0.ExitBlock);
+    assert(FC1.Preheader ==
+           (FC0.Peeled ? FC0.ExitBlock->getUniqueSuccessor() : FC0.ExitBlock));
     assert(FC1.Preheader->size() == 1 &&
            FC1.Preheader->getSingleSuccessor() == FC1.Header);
 
     // Remember the phi nodes originally in the header of FC0 in order to rewire
     // them later. However, this is only necessary if the new loop carried
     // values might not dominate the exiting branch. While we do not generally
     // test if this is the case but simply insert intermediate phi nodes, we
     // need to make sure these intermediate phi nodes have different
     // predecessors. To this end, we filter the special case where the exiting
     // block is the latch block of the first loop. Nothing needs to be done
     // anyway as all loop carried values dominate the latch and thereby also the
     // exiting branch.
     SmallVector<PHINode *, 8> OriginalFC0PHIs;
     if (FC0.ExitingBlock != FC0.Latch)
       for (PHINode &PHI : FC0.Header->phis())
         OriginalFC0PHIs.push_back(&PHI);
 
     // Replace incoming blocks for header PHIs first.
     FC1.Preheader->replaceSuccessorsPhiUsesWith(FC0.Preheader);
     FC0.Latch->replaceSuccessorsPhiUsesWith(FC1.Latch);
 
     // Then modify the control flow and update DT and PDT.
     SmallVector<DominatorTree::UpdateType, 8> TreeUpdates;
 
     // The old exiting block of the first loop (FC0) has to jump to the header
     // of the second as we need to execute the code in the second header block
     // regardless of the trip count. That is, if the trip count is 0, so the
     // back edge is never taken, we still have to execute both loop headers,
     // especially (but not only!) if the second is a do-while style loop.
     // However, doing so might invalidate the phi nodes of the first loop as
     // the new values do only need to dominate their latch and not the exiting
     // predicate. To remedy this potential problem we always introduce phi
     // nodes in the header of the second loop later that select the loop carried
     // value, if the second header was reached through an old latch of the
     // first, or undef otherwise. This is sound as exiting the first implies the
     // second will exit too, __without__ taking the back-edge. [Their
     // trip-counts are equal after all.
     // KB: Would this sequence be simpler to just just make FC0.ExitingBlock go
     // to FC1.Header? I think this is basically what the three sequences are
     // trying to accomplish; however, doing this directly in the CFG may mean
     // the DT/PDT becomes invalid
+    if (!FC0.Peeled) {
       FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC1.Preheader,
                                                            FC1.Header);
       TreeUpdates.emplace_back(DominatorTree::UpdateType(
           DominatorTree::Delete, FC0.ExitingBlock, FC1.Preheader));
       TreeUpdates.emplace_back(DominatorTree::UpdateType(
           DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
+    } else {
+      TreeUpdates.emplace_back(DominatorTree::UpdateType(
+          DominatorTree::Delete, FC0.ExitBlock, FC1.Preheader));
+
+      // Remove the ExitBlock of the first Loop (also not needed)
+      FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC0.ExitBlock,
+                                                           FC1.Header);
+      TreeUpdates.emplace_back(DominatorTree::UpdateType(
+          DominatorTree::Delete, FC0.ExitingBlock, FC0.ExitBlock));
+      FC0.ExitBlock->getTerminator()->eraseFromParent();
+      TreeUpdates.emplace_back(DominatorTree::UpdateType(
+          DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
+      new UnreachableInst(FC0.ExitBlock->getContext(), FC0.ExitBlock);
+    }
 
     // The pre-header of L1 is not necessary anymore.
     assert(pred_begin(FC1.Preheader) == pred_end(FC1.Preheader));
     FC1.Preheader->getTerminator()->eraseFromParent();
     new UnreachableInst(FC1.Preheader->getContext(), FC1.Preheader);
     TreeUpdates.emplace_back(DominatorTree::UpdateType(
         DominatorTree::Delete, FC1.Preheader, FC1.Header));
 
for (PHINode *LCPHI : OriginalFC0PHIs) {
 
       LCPHI->setIncomingValue(L1LatchBBIdx, L1HeaderPHI);
     }
 
     // Replace latch terminator destinations.
     FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header);
     FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header);
 
-    // Change the condition of FC0 latch branch to true, as both successors of
+    // Modify the latch branch of FC0 to be unconditional as both successors of
     // the branch are the same.
     simplifyLatchBranch(FC0);
 
     // If FC0.Latch and FC0.ExitingBlock are the same then we have already
     // performed the updates above.
     if (FC0.Latch != FC0.ExitingBlock)
       TreeUpdates.emplace_back(DominatorTree::UpdateType(
           DominatorTree::Insert, FC0.Latch, FC1.Header));
 
     TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Delete,
                                                        FC0.Latch, FC0.Header));
     TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Insert,
                                                        FC1.Latch, FC0.Header));
     TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Delete,
                                                        FC1.Latch, FC1.Header));
 
     // Update DT/PDT
     DTU.applyUpdates(TreeUpdates);
 
     LI.removeBlock(FC1.Preheader);
     DTU.deleteBB(FC1.Preheader);
+    if (FC0.Peeled) {
+      LI.removeBlock(FC0.ExitBlock);
+      DTU.deleteBB(FC0.ExitBlock);
+    }
+
     DTU.flush();
 
     // Is there a way to keep SE up-to-date so we don't need to forget the loops
     // and rebuild the information in subsequent passes of fusion?
     // Note: Need to forget the loops before merging the loop latches, as
     // mergeLatch may remove the only block in FC1.
     SE.forgetLoop(FC1.L);
     SE.forgetLoop(FC0.L);
#endif
   Loop *fuseGuardedLoops(const FusionCandidate &FC0,
                          const FusionCandidate &FC1) {
     assert(FC0.GuardBranch && FC1.GuardBranch && "Expecting guarded loops");
 
     BasicBlock *FC0GuardBlock = FC0.GuardBranch->getParent();
     BasicBlock *FC1GuardBlock = FC1.GuardBranch->getParent();
     BasicBlock *FC0NonLoopBlock = FC0.getNonLoopBlock();
     BasicBlock *FC1NonLoopBlock = FC1.getNonLoopBlock();
+    BasicBlock *FC0ExitBlockSuccessor = FC0.ExitBlock->getUniqueSuccessor();
 
     // Move instructions from the exit block of FC0 to the beginning of the exit
-    // block of FC1.
-    moveInstructionsToTheBeginning(*FC0.ExitBlock, *FC1.ExitBlock, DT, PDT, DI);
+    // block of FC1, in the case that the FC0 loop has not been peeled. In the
+    // case that FC0 loop is peeled, then move the instructions of the successor
+    // of the FC0 Exit block to the beginning of the exit block of FC1.
+    moveInstructionsToTheBeginning(
+        (FC0.Peeled ? *FC0ExitBlockSuccessor : *FC0.ExitBlock), *FC1.ExitBlock,
+        DT, PDT, DI);
 
     // Move instructions from the guard block of FC1 to the end of the guard
     // block of FC0.
     moveInstructionsToTheEnd(*FC1GuardBlock, *FC0GuardBlock, DT, PDT, DI);
 
     assert(FC0NonLoopBlock == FC1GuardBlock && "Loops are not adjacent");
 
     SmallVector<DominatorTree::UpdateType, 8> TreeUpdates;
 
     ////////////////////////////////////////////////////////////////////////////
     // Update the Loop Guard
     ////////////////////////////////////////////////////////////////////////////
     // The guard for FC0 is updated to guard both FC0 and FC1. This is done by
     // changing the NonLoopGuardBlock for FC0 to the NonLoopGuardBlock for FC1.
     // Thus, one path from the guard goes to the preheader for FC0 (and thus
     // executes the new fused loop) and the other path goes to the NonLoopBlock
     // for FC1 (where FC1 guard would have gone if FC1 was not executed).
     FC1NonLoopBlock->replacePhiUsesWith(FC1GuardBlock, FC0GuardBlock);
     FC0.GuardBranch->replaceUsesOfWith(FC0NonLoopBlock, FC1NonLoopBlock);
-    FC0.ExitBlock->getTerminator()->replaceUsesOfWith(FC1GuardBlock,
-                                                      FC1.Header);
+
+    BasicBlock *BBToUpdate = FC0.Peeled ? FC0ExitBlockSuccessor : FC0.ExitBlock;
+    BBToUpdate->getTerminator()->replaceUsesOfWith(FC1GuardBlock, FC1.Header);
 
     // The guard of FC1 is not necessary anymore.
     FC1.GuardBranch->eraseFromParent();
     new UnreachableInst(FC1GuardBlock->getContext(), FC1GuardBlock);
 
     TreeUpdates.emplace_back(DominatorTree::UpdateType(
         DominatorTree::Delete, FC1GuardBlock, FC1.Preheader));
     TreeUpdates.emplace_back(DominatorTree::UpdateType(
         DominatorTree::Delete, FC1GuardBlock, FC1NonLoopBlock));
     TreeUpdates.emplace_back(DominatorTree::UpdateType(
         DominatorTree::Delete, FC0GuardBlock, FC1GuardBlock));
     TreeUpdates.emplace_back(DominatorTree::UpdateType(
         DominatorTree::Insert, FC0GuardBlock, FC1NonLoopBlock));
 
+    if (FC0.Peeled) {
+      // Remove the Block after the ExitBlock of FC0
+      TreeUpdates.emplace_back(DominatorTree::UpdateType(
+          DominatorTree::Delete, FC0ExitBlockSuccessor, FC1GuardBlock));
+      FC0ExitBlockSuccessor->getTerminator()->eraseFromParent();
+      new UnreachableInst(FC0ExitBlockSuccessor->getContext(),
+                          FC0ExitBlockSuccessor);
+    }
+
     assert(pred_begin(FC1GuardBlock) == pred_end(FC1GuardBlock) &&
            "Expecting guard block to have no predecessors");
     assert(succ_begin(FC1GuardBlock) == succ_end(FC1GuardBlock) &&
            "Expecting guard block to have no successors");
 
     // Remember the phi nodes originally in the header of FC0 in order to rewire
     // them later. However, this is only necessary if the new loop carried
     // values might not dominate the exiting branch. While we do not generally
Loop *fuseGuardedLoops(const FusionCandidate &FC0,
     }
 
     // Update the latches
 
     // Replace latch terminator destinations.
     FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header);
     FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header);
 
-    // Change the condition of FC0 latch branch to true, as both successors of
+    // Modify the latch branch of FC0 to be unconditional as both successors of
     // the branch are the same.
     simplifyLatchBranch(FC0);
 
     // If FC0.Latch and FC0.ExitingBlock are the same then we have already
     // performed the updates above.
     if (FC0.Latch != FC0.ExitingBlock)
       TreeUpdates.emplace_back(DominatorTree::UpdateType(
           DominatorTree::Insert, FC0.Latch, FC1.Header));
assert(pred_begin(FC1GuardBlock) == pred_end(FC1GuardBlock) &&
            "FC1GuardBlock has predecessors!!");
 
     // Update DT/PDT
     DTU.applyUpdates(TreeUpdates);
 
     LI.removeBlock(FC1GuardBlock);
     LI.removeBlock(FC1.Preheader);
     LI.removeBlock(FC0.ExitBlock);
+    if (FC0.Peeled) {
+      LI.removeBlock(FC0ExitBlockSuccessor);
+      DTU.deleteBB(FC0ExitBlockSuccessor);
+    }
     DTU.deleteBB(FC1GuardBlock);
     DTU.deleteBB(FC1.Preheader);
     DTU.deleteBB(FC0.ExitBlock);
     DTU.flush();
 
     // Is there a way to keep SE up-to-date so we don't need to forget the loops
     // and rebuild the information in subsequent passes of fusion?
     // Note: Need to forget the loops before merging the loop latches, as
struct LoopFuseLegacy : public FunctionPass {
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequiredID(LoopSimplifyID);
     AU.addRequired<ScalarEvolutionWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<PostDominatorTreeWrapperPass>();
     AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
     AU.addRequired<DependenceAnalysisWrapperPass>();
+    AU.addRequired<AssumptionCacheTracker>();
+    AU.addRequired<TargetTransformInfoWrapperPass>();
 
     AU.addPreserved<ScalarEvolutionWrapperPass>();
     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 =
+        getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
     const DataLayout &DL = F.getParent()->getDataLayout();
-    LoopFuser LF(LI, DT, DI, SE, PDT, ORE, DL);
+
+    LoopFuser LF(LI, DT, DI, SE, PDT, ORE, DL, AC, TTI);
     return LF.fuseLoops(F);
   }
 };
 } // namespace
 
 PreservedAnalyses LoopFusePass::run(Function &F, FunctionAnalysisManager &AM) {
   auto &LI = AM.getResult<LoopAnalysis>(F);
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &DI = AM.getResult<DependenceAnalysis>(F);
   auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
   auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
   auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
-
+  auto &AC = AM.getResult<AssumptionAnalysis>(F);
+  const TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(F);
   const DataLayout &DL = F.getParent()->getDataLayout();
-  LoopFuser LF(LI, DT, DI, SE, PDT, ORE, DL);
+
+  LoopFuser LF(LI, DT, DI, SE, PDT, ORE, DL, AC, TTI);
   bool Changed = LF.fuseLoops(F);
   if (!Changed)
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<PostDominatorTreeAnalysis>();
   PA.preserve<ScalarEvolutionAnalysis>();
   PA.preserve<LoopAnalysis>();
   return PA;
 }
 
 char LoopFuseLegacy::ID = 0;
 
 INITIALIZE_PASS_BEGIN(LoopFuseLegacy, "loop-fusion", "Loop Fusion", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
+INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_END(LoopFuseLegacy, "loop-fusion", "Loop Fusion", false, false)
 
 FunctionPass *llvm::createLoopFusePass() { return new LoopFuseLegacy(); }

llvm/test/Transforms/LoopFusion/guarded_peel.ll

+; RUN: opt -S -loop-fusion -loop-fusion-peel-max-count=3 < %s | FileCheck %s
+
+; Tests if we are able to fuse two guarded loops which have constant but
+; different trip counts. The first two iterations of the first loop should be
+; peeled off, and then the loops should be fused together.
+
+@B = common global [1024 x i32] zeroinitializer, align 16
+
+; CHECK-LABEL: void @main(i32* noalias %A)
+; CHECK-NEXT:  entry:
+; CHECK:         br i1 %cmp4, label %for.first.entry, label %for.end
+; CHECK:       for.first.entry
+; CHECK-NEXT:    br label %for.first.peel.begin
+; CHECK:       for.first.peel.begin:
+; CHECK-NEXT:    br label %for.first.peel
+; CHECK:       for.first.peel:
+; CHECK:         br label %for.first.peel.next
+; CHECK:       for.first.peel.next:
+; CHECK-NEXT:    br label %for.first.peel2
+; CHECK:       for.first.peel2:
+; CHECK:         br label %for.first.peel.next1
+; CHECK:       for.first.peel.next1:
+; CHECK-NEXT:    br label %for.first.peel.next11
+; CHECK:       for.first.peel.next11:
+; CHECK-NEXT:    br label %for.first.entry.peel.newph
+; CHECK:       for.first.entry.peel.newph:
+; CHECK:         br label %for.first
+; CHECK:       for.first:
+; CHECK:         br i1 %cmp3, label %for.first, label %for.second.exit
+; CHECK:       for.second.exit:
+; CHECK:         br label %for.end
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+
+define void @main(i32* noalias %A) {
+entry:
+  %cmp4 = icmp slt i64 0, 45
+  br i1 %cmp4, label %for.first.entry, label %for.second.guard
+
+for.first.entry:                                 ; preds = %entry
+  br label %for.first
+
+for.first:                                       ; preds = %for.first.entry, %for.first
+  %i.05 = phi i64 [ %inc, %for.first ], [ 0, %for.first.entry ]
+  %sub = sub nsw i64 %i.05, 3
+  %add = add nsw i64 %i.05, 3
+  %mul = mul nsw i64 %sub, %add
+  %rem = srem i64 %mul, %i.05
+  %conv = trunc i64 %rem to i32
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %i.05
+  store i32 %conv, i32* %arrayidx, align 4
+  %inc = add nsw i64 %i.05, 1
+  %cmp = icmp slt i64 %inc, 45
+  br i1 %cmp, label %for.first, label %for.first.exit
+
+for.first.exit:                                  ; preds = %for.first
+  br label %for.second.guard
+
+for.second.guard:                                ; preds = %for.first.exit, %entry
+  %cmp31 = icmp slt i64 2, 45
+  br i1 %cmp31, label %for.second.entry, label %for.end
+
+for.second.entry:                                ; preds = %for.second.guard
+  br label %for.second
+
+for.second:                                      ; preds = %for.second.entry, %for.second
+  %i1.02 = phi i64 [ %inc14, %for.second ], [ 2, %for.second.entry ]
+  %sub7 = sub nsw i64 %i1.02, 3
+  %add8 = add nsw i64 %i1.02, 3
+  %mul9 = mul nsw i64 %sub7, %add8
+  %rem10 = srem i64 %mul9, %i1.02
+  %conv11 = trunc i64 %rem10 to i32
+  %arrayidx12 = getelementptr inbounds [1024 x i32], [1024 x i32]* @B, i64 0, i64 %i1.02
+  store i32 %conv11, i32* %arrayidx12, align 4
+  %inc14 = add nsw i64 %i1.02, 1
+  %cmp3 = icmp slt i64 %inc14, 45
+  br i1 %cmp3, label %for.second, label %for.second.exit
+
+for.second.exit:                                 ; preds = %for.second
+  br label %for.end
+
+for.end:                                         ; preds = %for.second.exit, %for.second.guard
+  ret void
+}

llvm/test/Transforms/LoopFusion/guarded_unsafeblock_peel.ll

+; RUN: opt -S -loop-fusion -loop-fusion-peel-max-count=3 < %s | FileCheck %s
+
+; Tests that we do not fuse two guarded loops together.
+; These loops do not have the same trip count, and the first loop meets the
+; requirements for peeling. However, the exit block of the first loop makes the
+; loops unsafe to fuse together.
+; The expected output of this test is the function as below.
+
+; CHECK-LABEL: void @unsafe_exitblock(i32* noalias %A, i32* noalias %B)
+; CHECK:       for.first.guard
+; CHECK:         br i1 %cmp3, label %for.first.preheader, label %for.second.guard
+; CHECK:       for.first.preheader:
+; CHECK-NEXT:    br label %for.first
+; CHECK:       for.first:
+; CHECK:         br i1 %cmp, label %for.first, label %for.first.exit
+; CHECK:       for.first.exit:
+; CHECK-NEXT:    call void @bar()
+; CHECK-NEXT:    br label %for.second.guard
+; CHECK:       for.second.guard:
+; CHECK:         br i1 %cmp21, label %for.second.preheader, label %for.end
+; CHECK:       for.second.preheader:
+; CHECK-NEXT:    br label %for.second
+; CHECK:       for.second:
+; CHECK:         br i1 %cmp2, label %for.second, label %for.second.exit
+; CHECK:       for.second.exit:
+; CHECK-NEXT:    br label %for.end
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+
+define void @unsafe_exitblock(i32* noalias %A, i32* noalias %B) {
+for.first.guard:
+  %cmp3 = icmp slt i64 0, 45
+  br i1 %cmp3, label %for.first.preheader, label %for.second.guard
+
+for.first.preheader:                             ; preds = %for.first.guard
+  br label %for.first
+
+for.first:                                       ; preds = %for.first.preheader, %for.first
+  %i.04 = phi i64 [ %inc, %for.first ], [ 0, %for.first.preheader ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %i.04
+  store i32 0, i32* %arrayidx, align 4
+  %inc = add nsw i64 %i.04, 1
+  %cmp = icmp slt i64 %inc, 45
+  br i1 %cmp, label %for.first, label %for.first.exit
+
+for.first.exit:                                  ; preds = %for.first
+  call void @bar()
+  br label %for.second.guard
+
+for.second.guard:                                ; preds = %for.first.exit, %for.first.guard
+  %cmp21 = icmp slt i64 2,45
+  br i1 %cmp21, label %for.second.preheader, label %for.end
+
+for.second.preheader:                            ; preds = %for.second.guard
+  br label %for.second
+
+for.second:                                      ; preds = %for.second.preheader, %for.second
+  %j.02 = phi i64 [ %inc6, %for.second ], [ 2, %for.second.preheader ]
+  %arrayidx4 = getelementptr inbounds i32, i32* %B, i64 %j.02
+  store i32 0, i32* %arrayidx4, align 4
+  %inc6 = add nsw i64 %j.02, 1
+  %cmp2 = icmp slt i64 %inc6, 45
+  br i1 %cmp2, label %for.second, label %for.second.exit
+
+for.second.exit:                                 ; preds = %for.second
+  br label %for.end
+
+for.end:                                         ; preds = %for.second.exit, %for.second.guard
+  ret void
+}
+
+declare void @bar()

llvm/test/Transforms/LoopFusion/nonadjacent_peel.ll

+; RUN: opt -S -loop-fusion -loop-fusion-peel-max-count=3 < %s | FileCheck %s
+
+; Tests that we do not fuse these two loops together. These loops do not have
+; the same tripcount, and the first loop is valid candiate for peeling; however
+; the loops are not adjacent, hence they are not valid to be fused (after
+; peeling).
+; The expected output of this test is the function below.
+
+; CHECK-LABEL: void @function(i32* noalias %arg)
+; CHECK-NEXT:  for.first.preheader:
+; CHECK-NEXT:    br label %for.first
+; CHECK:       for.first:
+; CHECK:         br label %for.first.latch
+; CHECK:       for.first.latch:
+; CHECK:         br i1 %exitcond4, label %for.first, label %for.first.exit
+; CHECK:       for.first.exit:
+; CHECK-NEXT:    br label %for.next
+; CHECK:       for.next:
+; CHECK-NEXT:    br label %for.second.preheader
+; CHECK:       for.second.preheader:
+; CHECK:         br label %for.second
+; CHECK:       for.second:
+; CHECK:         br label %for.second.latch
+; CHECK:       for.second.latch:
+; CHECK:         br i1 %exitcond, label %for.second, label %for.end
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+
+@B = common global [1024 x i32] zeroinitializer, align 16
+
+define void @function(i32* noalias %arg) {
+for.first.preheader:
+  br label %for.first
+
+for.first:                                       ; preds = %for.first.preheader, %for.first.latch
+  %.014 = phi i32 [ 0, %for.first.preheader ], [ %tmp15, %for.first.latch ]
+  %indvars.iv23 = phi i64 [ 0, %for.first.preheader ], [ %indvars.iv.next3, %for.first.latch ]
+  %tmp = add nsw i32 %.014, -3
+  %tmp8 = add nuw nsw i64 %indvars.iv23, 3
+  %tmp9 = trunc i64 %tmp8 to i32
+  %tmp10 = mul nsw i32 %tmp, %tmp9
+  %tmp11 = trunc i64 %indvars.iv23 to i32
+  %tmp12 = srem i32 %tmp10, %tmp11
+  %tmp13 = getelementptr inbounds i32, i32* %arg, i64 %indvars.iv23
+  store i32 %tmp12, i32* %tmp13, align 4
+  br label %for.first.latch
+
+for.first.latch:                                 ; preds = %for.first
+  %indvars.iv.next3 = add nuw nsw i64 %indvars.iv23, 1
+  %tmp15 = add nuw nsw i32 %.014, 1
+  %exitcond4 = icmp ne i64 %indvars.iv.next3, 100
+  br i1 %exitcond4, label %for.first, label %for.first.exit
+
+for.first.exit:                                  ; preds: %for.first.latch
+  br label %for.next
+
+for.next:                                        ; preds = %for.first.exit
+  br label %for.second.preheader
+
+for.second.preheader:                            ; preds = %for.next
+  br label %for.second
+
+for.second:                                      ; preds = %for.second.preheader, %for.second.latch
+  %.02 = phi i32 [ 0, %for.second.preheader ], [ %tmp28, %for.second.latch ]
+  %indvars.iv1 = phi i64 [ 3, %for.second.preheader ], [ %indvars.iv.next, %for.second.latch ]
+  %tmp20 = add nsw i32 %.02, -3
+  %tmp21 = add nuw nsw i64 %indvars.iv1, 3
+  %tmp22 = trunc i64 %tmp21 to i32
+  %tmp23 = mul nsw i32 %tmp20, %tmp22
+  %tmp24 = trunc i64 %indvars.iv1 to i32
+  %tmp25 = srem i32 %tmp23, %tmp24
+  %tmp26 = getelementptr inbounds [1024 x i32], [1024 x i32]* @B, i64 0, i64 %indvars.iv1
+  store i32 %tmp25, i32* %tmp26, align 4
+  br label %for.second.latch
+
+for.second.latch:                                ; preds = %for.second
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv1, 1
+  %tmp28 = add nuw nsw i32 %.02, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 100
+  br i1 %exitcond, label %for.second, label %for.end
+
+for.end:                                         ; preds = %for.second.latch
+  ret void
+}

llvm/test/Transforms/LoopFusion/peel.ll

+; RUN: opt -S -loop-fusion -loop-fusion-peel-max-count=3 < %s | FileCheck %s
+
+; Tests whether we can fuse two loops together if they have constant but a
+; different tripcount.
+; The first three iterations of the first loop should be peeled, and then the
+; two loops should be fused together in this example.
+
+; C Code
+;
+; int B[1024];
+;
+; void function(int *arg) {
+;   for (int i = 0; i != 100; ++i)
+;     arg[i] = ((i - 3)*(i+3)) % i;
+;
+;   for (int i = 3; i != 100; ++i)
+;     B[i] = ((i-6)*(i+3)) % i;
+; }
+
+; CHECK-LABEL: void @function(i32* noalias %arg)
+; CHECK-NEXT:  for.first.preheader:
+; CHECK-NEXT:    br label %for.first.peel.begin
+; CHECK:       for.first.peel.begin:
+; CHECK-NEXT:    br label %for.first.peel
+; CHECK:       for.first.peel:
+; CHECK:         br label %for.first.latch.peel
+; CHECK:       for.first.latch.peel:
+; CHECK:         br label %for.first.peel.next
+; CHECK:       for.first.peel.next:
+; CHECK-NEXT:    br label %for.first.peel2
+; CHECK:       for.first.peel2:
+; CHECK:         br label %for.first.latch.peel10
+; CHECK:       for.first.latch.peel10:
+; CHECK:         br label %for.first.peel.next1
+; CHECK:       for.first.peel.next1:
+; CHECK-NEXT:    br label %for.first.peel15
+; CHECK:       for.first.peel15:
+; CHECK:         br label %for.first.latch.peel23
+; CHECK:       for.first.latch.peel23:
+; CHECK:         br label %for.first.peel.next14
+; CHECK:       for.first.peel.next14:
+; CHECK-NEXT:    br label %for.first.peel.next27
+; CHECK:       for.first.peel.next27:
+; CHECK-NEXT:    br label %for.first.preheader.peel.newph
+; CHECK:       for.first.preheader.peel.newph:
+; CHECK-NEXT:    br label %for.first
+; CHECK:       for.first:
+; CHECK:         br label %for.first.latch
+; CHECK:       for.first.latch:
+; CHECK:         br label %for.second.latch
+; CHECK:       for.second.latch:
+; CHECK:         br i1 %exitcond, label %for.first, label %for.end
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+
+@B = common global [1024 x i32] zeroinitializer, align 16
+
+define void @function(i32* noalias %arg) {
+for.first.preheader:
+  br label %for.first
+
+for.first:                                       ; preds = %for.first.preheader, %for.first.latch
+  %.014 = phi i32 [ 0, %for.first.preheader ], [ %tmp15, %for.first.latch ]
+  %indvars.iv23 = phi i64 [ 0, %for.first.preheader ], [ %indvars.iv.next3, %for.first.latch ]
+  %tmp = add nsw i32 %.014, -3
+  %tmp8 = add nuw nsw i64 %indvars.iv23, 3
+  %tmp9 = trunc i64 %tmp8 to i32
+  %tmp10 = mul nsw i32 %tmp, %tmp9
+  %tmp11 = trunc i64 %indvars.iv23 to i32
+  %tmp12 = srem i32 %tmp10, %tmp11
+  %tmp13 = getelementptr inbounds i32, i32* %arg, i64 %indvars.iv23
+  store i32 %tmp12, i32* %tmp13, align 4
+  br label %for.first.latch
+
+for.first.latch:                                 ; preds = %for.first
+  %indvars.iv.next3 = add nuw nsw i64 %indvars.iv23, 1
+  %tmp15 = add nuw nsw i32 %.014, 1
+  %exitcond4 = icmp ne i64 %indvars.iv.next3, 100
+  br i1 %exitcond4, label %for.first, label %for.second.preheader
+
+for.second.preheader:                            ; preds = %for.first.latch
+  br label %for.second
+
+for.second:                                      ; preds = %for.second.preheader, %for.second.latch
+  %.02 = phi i32 [ 0, %for.second.preheader ], [ %tmp28, %for.second.latch ]
+  %indvars.iv1 = phi i64 [ 3, %for.second.preheader ], [ %indvars.iv.next, %for.second.latch ]
+  %tmp20 = add nsw i32 %.02, -3
+  %tmp21 = add nuw nsw i64 %indvars.iv1, 3
+  %tmp22 = trunc i64 %tmp21 to i32
+  %tmp23 = mul nsw i32 %tmp20, %tmp22
+  %tmp24 = trunc i64 %indvars.iv1 to i32
+  %tmp25 = srem i32 %tmp23, %tmp24
+  %tmp26 = getelementptr inbounds [1024 x i32], [1024 x i32]* @B, i64 0, i64 %indvars.iv1
+  store i32 %tmp25, i32* %tmp26, align 4
+  br label %for.second.latch
+
+for.second.latch:                                ; preds = %for.second
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv1, 1
+  %tmp28 = add nuw nsw i32 %.02, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 100
+  br i1 %exitcond, label %for.second, label %for.end
+
+for.end:                                        ; preds = %for.second.latch
+  ret void
+}