1 files changed, 0 insertions, 820 deletions

diff --git a/contrib/llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp b/contrib/llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
deleted file mode 100644
index ff49d83f25c5..000000000000
--- a/contrib/llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
+++ /dev/null
@@ -1,820 +0,0 @@
-//===-- LoopUnrollAndJam.cpp - Loop unrolling utilities -------------------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-// This file implements loop unroll and jam as a routine, much like
-// LoopUnroll.cpp implements loop unroll.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/Analysis/AssumptionCache.h"
-#include "llvm/Analysis/DependenceAnalysis.h"
-#include "llvm/Analysis/InstructionSimplify.h"
-#include "llvm/Analysis/LoopAnalysisManager.h"
-#include "llvm/Analysis/LoopIterator.h"
-#include "llvm/Analysis/LoopPass.h"
-#include "llvm/Analysis/OptimizationRemarkEmitter.h"
-#include "llvm/Analysis/ScalarEvolution.h"
-#include "llvm/Analysis/ScalarEvolutionExpander.h"
-#include "llvm/Analysis/Utils/Local.h"
-#include "llvm/IR/BasicBlock.h"
-#include "llvm/IR/DataLayout.h"
-#include "llvm/IR/DebugInfoMetadata.h"
-#include "llvm/IR/Dominators.h"
-#include "llvm/IR/IntrinsicInst.h"
-#include "llvm/IR/LLVMContext.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/raw_ostream.h"
-#include "llvm/Transforms/Utils/BasicBlockUtils.h"
-#include "llvm/Transforms/Utils/Cloning.h"
-#include "llvm/Transforms/Utils/LoopSimplify.h"
-#include "llvm/Transforms/Utils/LoopUtils.h"
-#include "llvm/Transforms/Utils/SimplifyIndVar.h"
-#include "llvm/Transforms/Utils/UnrollLoop.h"
-using namespace llvm;
-
-#define DEBUG_TYPE "loop-unroll-and-jam"
-
-STATISTIC(NumUnrolledAndJammed, "Number of loops unroll and jammed");
-STATISTIC(NumCompletelyUnrolledAndJammed, "Number of loops unroll and jammed");
-
-typedef SmallPtrSet<BasicBlock *, 4> BasicBlockSet;
-
-// Partition blocks in an outer/inner loop pair into blocks before and after
-// the loop
-static bool partitionOuterLoopBlocks(Loop *L, Loop *SubLoop,
-                                     BasicBlockSet &ForeBlocks,
-                                     BasicBlockSet &SubLoopBlocks,
-                                     BasicBlockSet &AftBlocks,
-                                     DominatorTree *DT) {
-  BasicBlock *SubLoopLatch = SubLoop->getLoopLatch();
-  SubLoopBlocks.insert(SubLoop->block_begin(), SubLoop->block_end());
-
-  for (BasicBlock *BB : L->blocks()) {
-    if (!SubLoop->contains(BB)) {
-      if (DT->dominates(SubLoopLatch, BB))
-        AftBlocks.insert(BB);
-      else
-        ForeBlocks.insert(BB);
-    }
-  }
-
-  // Check that all blocks in ForeBlocks together dominate the subloop
-  // TODO: This might ideally be done better with a dominator/postdominators.
-  BasicBlock *SubLoopPreHeader = SubLoop->getLoopPreheader();
-  for (BasicBlock *BB : ForeBlocks) {
-    if (BB == SubLoopPreHeader)
-      continue;
-    Instruction *TI = BB->getTerminator();
-    for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
-      if (!ForeBlocks.count(TI->getSuccessor(i)))
-        return false;
-  }
-
-  return true;
-}
-
-// Looks at the phi nodes in Header for values coming from Latch. For these
-// instructions and all their operands calls Visit on them, keeping going for
-// all the operands in AftBlocks. Returns false if Visit returns false,
-// otherwise returns true. This is used to process the instructions in the
-// Aft blocks that need to be moved before the subloop. It is used in two
-// places. One to check that the required set of instructions can be moved
-// before the loop. Then to collect the instructions to actually move in
-// moveHeaderPhiOperandsToForeBlocks.
-template <typename T>
-static bool processHeaderPhiOperands(BasicBlock *Header, BasicBlock *Latch,
-                                     BasicBlockSet &AftBlocks, T Visit) {
-  SmallVector<Instruction *, 8> Worklist;
-  for (auto &Phi : Header->phis()) {
-    Value *V = Phi.getIncomingValueForBlock(Latch);
-    if (Instruction *I = dyn_cast<Instruction>(V))
-      Worklist.push_back(I);
-  }
-
-  while (!Worklist.empty()) {
-    Instruction *I = Worklist.back();
-    Worklist.pop_back();
-    if (!Visit(I))
-      return false;
-
-    if (AftBlocks.count(I->getParent()))
-      for (auto &U : I->operands())
-        if (Instruction *II = dyn_cast<Instruction>(U))
-          Worklist.push_back(II);
-  }
-
-  return true;
-}
-
-// Move the phi operands of Header from Latch out of AftBlocks to InsertLoc.
-static void moveHeaderPhiOperandsToForeBlocks(BasicBlock *Header,
-                                              BasicBlock *Latch,
-                                              Instruction *InsertLoc,
-                                              BasicBlockSet &AftBlocks) {
-  // We need to ensure we move the instructions in the correct order,
-  // starting with the earliest required instruction and moving forward.
-  std::vector<Instruction *> Visited;
-  processHeaderPhiOperands(Header, Latch, AftBlocks,
-                           [&Visited, &AftBlocks](Instruction *I) {
-                             if (AftBlocks.count(I->getParent()))
-                               Visited.push_back(I);
-                             return true;
-                           });
-
-  // Move all instructions in program order to before the InsertLoc
-  BasicBlock *InsertLocBB = InsertLoc->getParent();
-  for (Instruction *I : reverse(Visited)) {
-    if (I->getParent() != InsertLocBB)
-      I->moveBefore(InsertLoc);
-  }
-}
-
-/*
-  This method performs Unroll and Jam. For a simple loop like:
-  for (i = ..)
-    Fore(i)
-    for (j = ..)
-      SubLoop(i, j)
-    Aft(i)
-
-  Instead of doing normal inner or outer unrolling, we do:
-  for (i = .., i+=2)
-    Fore(i)
-    Fore(i+1)
-    for (j = ..)
-      SubLoop(i, j)
-      SubLoop(i+1, j)
-    Aft(i)
-    Aft(i+1)
-
-  So the outer loop is essetially unrolled and then the inner loops are fused
-  ("jammed") together into a single loop. This can increase speed when there
-  are loads in SubLoop that are invariant to i, as they become shared between
-  the now jammed inner loops.
-
-  We do this by spliting the blocks in the loop into Fore, Subloop and Aft.
-  Fore blocks are those before the inner loop, Aft are those after. Normal
-  Unroll code is used to copy each of these sets of blocks and the results are
-  combined together into the final form above.
-
-  isSafeToUnrollAndJam should be used prior to calling this to make sure the
-  unrolling will be valid. Checking profitablility is also advisable.
-
-  If EpilogueLoop is non-null, it receives the epilogue loop (if it was
-  necessary to create one and not fully unrolled).
-*/
-LoopUnrollResult llvm::UnrollAndJamLoop(
-    Loop *L, unsigned Count, unsigned TripCount, unsigned TripMultiple,
-    bool UnrollRemainder, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT,
-    AssumptionCache *AC, OptimizationRemarkEmitter *ORE, Loop **EpilogueLoop) {
-
-  // When we enter here we should have already checked that it is safe
-  BasicBlock *Header = L->getHeader();
-  assert(L->getSubLoops().size() == 1);
-  Loop *SubLoop = *L->begin();
-
-  // Don't enter the unroll code if there is nothing to do.
-  if (TripCount == 0 && Count < 2) {
-    LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; almost nothing to do\n");
-    return LoopUnrollResult::Unmodified;
-  }
-
-  assert(Count > 0);
-  assert(TripMultiple > 0);
-  assert(TripCount == 0 || TripCount % TripMultiple == 0);
-
-  // Are we eliminating the loop control altogether?
-  bool CompletelyUnroll = (Count == TripCount);
-
-  // We use the runtime remainder in cases where we don't know trip multiple
-  if (TripMultiple == 1 || TripMultiple % Count != 0) {
-    if (!UnrollRuntimeLoopRemainder(L, Count, /*AllowExpensiveTripCount*/ false,
-                                    /*UseEpilogRemainder*/ true,
-                                    UnrollRemainder, /*ForgetAllSCEV*/ false,
-                                    LI, SE, DT, AC, true, EpilogueLoop)) {
-      LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; remainder loop could not be "
-                           "generated when assuming runtime trip count\n");
-      return LoopUnrollResult::Unmodified;
-    }
-  }
-
-  // Notify ScalarEvolution that the loop will be substantially changed,
-  // if not outright eliminated.
-  if (SE) {
-    SE->forgetLoop(L);
-    SE->forgetLoop(SubLoop);
-  }
-
-  using namespace ore;
-  // Report the unrolling decision.
-  if (CompletelyUnroll) {
-    LLVM_DEBUG(dbgs() << "COMPLETELY UNROLL AND JAMMING loop %"
-                      << Header->getName() << " with trip count " << TripCount
-                      << "!\n");
-    ORE->emit(OptimizationRemark(DEBUG_TYPE, "FullyUnrolled", L->getStartLoc(),
-                                 L->getHeader())
-              << "completely unroll and jammed loop with "
-              << NV("UnrollCount", TripCount) << " iterations");
-  } else {
-    auto DiagBuilder = [&]() {
-      OptimizationRemark Diag(DEBUG_TYPE, "PartialUnrolled", L->getStartLoc(),
-                              L->getHeader());
-      return Diag << "unroll and jammed loop by a factor of "
-                  << NV("UnrollCount", Count);
-    };
-
-    LLVM_DEBUG(dbgs() << "UNROLL AND JAMMING loop %" << Header->getName()
-                      << " by " << Count);
-    if (TripMultiple != 1) {
-      LLVM_DEBUG(dbgs() << " with " << TripMultiple << " trips per branch");
-      ORE->emit([&]() {
-        return DiagBuilder() << " with " << NV("TripMultiple", TripMultiple)
-                             << " trips per branch";
-      });
-    } else {
-      LLVM_DEBUG(dbgs() << " with run-time trip count");
-      ORE->emit([&]() { return DiagBuilder() << " with run-time trip count"; });
-    }
-    LLVM_DEBUG(dbgs() << "!\n");
-  }
-
-  BasicBlock *Preheader = L->getLoopPreheader();
-  BasicBlock *LatchBlock = L->getLoopLatch();
-  BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator());
-  assert(Preheader && LatchBlock && Header);
-  assert(BI && !BI->isUnconditional());
-  bool ContinueOnTrue = L->contains(BI->getSuccessor(0));
-  BasicBlock *LoopExit = BI->getSuccessor(ContinueOnTrue);
-  bool SubLoopContinueOnTrue = SubLoop->contains(
-      SubLoop->getLoopLatch()->getTerminator()->getSuccessor(0));
-
-  // Partition blocks in an outer/inner loop pair into blocks before and after
-  // the loop
-  BasicBlockSet SubLoopBlocks;
-  BasicBlockSet ForeBlocks;
-  BasicBlockSet AftBlocks;
-  partitionOuterLoopBlocks(L, SubLoop, ForeBlocks, SubLoopBlocks, AftBlocks,
-                           DT);
-
-  // We keep track of the entering/first and exiting/last block of each of
-  // Fore/SubLoop/Aft in each iteration. This helps make the stapling up of
-  // blocks easier.
-  std::vector<BasicBlock *> ForeBlocksFirst;
-  std::vector<BasicBlock *> ForeBlocksLast;
-  std::vector<BasicBlock *> SubLoopBlocksFirst;
-  std::vector<BasicBlock *> SubLoopBlocksLast;
-  std::vector<BasicBlock *> AftBlocksFirst;
-  std::vector<BasicBlock *> AftBlocksLast;
-  ForeBlocksFirst.push_back(Header);
-  ForeBlocksLast.push_back(SubLoop->getLoopPreheader());
-  SubLoopBlocksFirst.push_back(SubLoop->getHeader());
-  SubLoopBlocksLast.push_back(SubLoop->getExitingBlock());
-  AftBlocksFirst.push_back(SubLoop->getExitBlock());
-  AftBlocksLast.push_back(L->getExitingBlock());
-  // Maps Blocks[0] -> Blocks[It]
-  ValueToValueMapTy LastValueMap;
-
-  // Move any instructions from fore phi operands from AftBlocks into Fore.
-  moveHeaderPhiOperandsToForeBlocks(
-      Header, LatchBlock, SubLoop->getLoopPreheader()->getTerminator(),
-      AftBlocks);
-
-  // The current on-the-fly SSA update requires blocks to be processed in
-  // reverse postorder so that LastValueMap contains the correct value at each
-  // exit.
-  LoopBlocksDFS DFS(L);
-  DFS.perform(LI);
-  // Stash the DFS iterators before adding blocks to the loop.
-  LoopBlocksDFS::RPOIterator BlockBegin = DFS.beginRPO();
-  LoopBlocksDFS::RPOIterator BlockEnd = DFS.endRPO();
-
-  if (Header->getParent()->isDebugInfoForProfiling())
-    for (BasicBlock *BB : L->getBlocks())
-      for (Instruction &I : *BB)
-        if (!isa<DbgInfoIntrinsic>(&I))
-          if (const DILocation *DIL = I.getDebugLoc()) {
-            auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(Count);
-            if (NewDIL)
-              I.setDebugLoc(NewDIL.getValue());
-            else
-              LLVM_DEBUG(dbgs()
-                         << "Failed to create new discriminator: "
-                         << DIL->getFilename() << " Line: " << DIL->getLine());
-          }
-
-  // Copy all blocks
-  for (unsigned It = 1; It != Count; ++It) {
-    std::vector<BasicBlock *> NewBlocks;
-    // Maps Blocks[It] -> Blocks[It-1]
-    DenseMap<Value *, Value *> PrevItValueMap;
-
-    for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
-      ValueToValueMapTy VMap;
-      BasicBlock *New = CloneBasicBlock(*BB, VMap, "." + Twine(It));
-      Header->getParent()->getBasicBlockList().push_back(New);
-
-      if (ForeBlocks.count(*BB)) {
-        L->addBasicBlockToLoop(New, *LI);
-
-        if (*BB == ForeBlocksFirst[0])
-          ForeBlocksFirst.push_back(New);
-        if (*BB == ForeBlocksLast[0])
-          ForeBlocksLast.push_back(New);
-      } else if (SubLoopBlocks.count(*BB)) {
-        SubLoop->addBasicBlockToLoop(New, *LI);
-
-        if (*BB == SubLoopBlocksFirst[0])
-          SubLoopBlocksFirst.push_back(New);
-        if (*BB == SubLoopBlocksLast[0])
-          SubLoopBlocksLast.push_back(New);
-      } else if (AftBlocks.count(*BB)) {
-        L->addBasicBlockToLoop(New, *LI);
-
-        if (*BB == AftBlocksFirst[0])
-          AftBlocksFirst.push_back(New);
-        if (*BB == AftBlocksLast[0])
-          AftBlocksLast.push_back(New);
-      } else {
-        llvm_unreachable("BB being cloned should be in Fore/Sub/Aft");
-      }
-
-      // Update our running maps of newest clones
-      PrevItValueMap[New] = (It == 1 ? *BB : LastValueMap[*BB]);
-      LastValueMap[*BB] = New;
-      for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end();
-           VI != VE; ++VI) {
-        PrevItValueMap[VI->second] =
-            const_cast<Value *>(It == 1 ? VI->first : LastValueMap[VI->first]);
-        LastValueMap[VI->first] = VI->second;
-      }
-
-      NewBlocks.push_back(New);
-
-      // Update DomTree:
-      if (*BB == ForeBlocksFirst[0])
-        DT->addNewBlock(New, ForeBlocksLast[It - 1]);
-      else if (*BB == SubLoopBlocksFirst[0])
-        DT->addNewBlock(New, SubLoopBlocksLast[It - 1]);
-      else if (*BB == AftBlocksFirst[0])
-        DT->addNewBlock(New, AftBlocksLast[It - 1]);
-      else {
-        // Each set of blocks (Fore/Sub/Aft) will have the same internal domtree
-        // structure.
-        auto BBDomNode = DT->getNode(*BB);
-        auto BBIDom = BBDomNode->getIDom();
-        BasicBlock *OriginalBBIDom = BBIDom->getBlock();
-        assert(OriginalBBIDom);
-        assert(LastValueMap[cast<Value>(OriginalBBIDom)]);
-        DT->addNewBlock(
-            New, cast<BasicBlock>(LastValueMap[cast<Value>(OriginalBBIDom)]));
-      }
-    }
-
-    // Remap all instructions in the most recent iteration
-    for (BasicBlock *NewBlock : NewBlocks) {
-      for (Instruction &I : *NewBlock) {
-        ::remapInstruction(&I, LastValueMap);
-        if (auto *II = dyn_cast<IntrinsicInst>(&I))
-          if (II->getIntrinsicID() == Intrinsic::assume)
-            AC->registerAssumption(II);
-      }
-    }
-
-    // Alter the ForeBlocks phi's, pointing them at the latest version of the
-    // value from the previous iteration's phis
-    for (PHINode &Phi : ForeBlocksFirst[It]->phis()) {
-      Value *OldValue = Phi.getIncomingValueForBlock(AftBlocksLast[It]);
-      assert(OldValue && "should have incoming edge from Aft[It]");
-      Value *NewValue = OldValue;
-      if (Value *PrevValue = PrevItValueMap[OldValue])
-        NewValue = PrevValue;
-
-      assert(Phi.getNumOperands() == 2);
-      Phi.setIncomingBlock(0, ForeBlocksLast[It - 1]);
-      Phi.setIncomingValue(0, NewValue);
-      Phi.removeIncomingValue(1);
-    }
-  }
-
-  // Now that all the basic blocks for the unrolled iterations are in place,
-  // finish up connecting the blocks and phi nodes. At this point LastValueMap
-  // is the last unrolled iterations values.
-
-  // Update Phis in BB from OldBB to point to NewBB
-  auto updatePHIBlocks = [](BasicBlock *BB, BasicBlock *OldBB,
-                            BasicBlock *NewBB) {
-    for (PHINode &Phi : BB->phis()) {
-      int I = Phi.getBasicBlockIndex(OldBB);
-      Phi.setIncomingBlock(I, NewBB);
-    }
-  };
-  // Update Phis in BB from OldBB to point to NewBB and use the latest value
-  // from LastValueMap
-  auto updatePHIBlocksAndValues = [](BasicBlock *BB, BasicBlock *OldBB,
-                                     BasicBlock *NewBB,
-                                     ValueToValueMapTy &LastValueMap) {
-    for (PHINode &Phi : BB->phis()) {
-      for (unsigned b = 0; b < Phi.getNumIncomingValues(); ++b) {
-        if (Phi.getIncomingBlock(b) == OldBB) {
-          Value *OldValue = Phi.getIncomingValue(b);
-          if (Value *LastValue = LastValueMap[OldValue])
-            Phi.setIncomingValue(b, LastValue);
-          Phi.setIncomingBlock(b, NewBB);
-          break;
-        }
-      }
-    }
-  };
-  // Move all the phis from Src into Dest
-  auto movePHIs = [](BasicBlock *Src, BasicBlock *Dest) {
-    Instruction *insertPoint = Dest->getFirstNonPHI();
-    while (PHINode *Phi = dyn_cast<PHINode>(Src->begin()))
-      Phi->moveBefore(insertPoint);
-  };
-
-  // Update the PHI values outside the loop to point to the last block
-  updatePHIBlocksAndValues(LoopExit, AftBlocksLast[0], AftBlocksLast.back(),
-                           LastValueMap);
-
-  // Update ForeBlocks successors and phi nodes
-  BranchInst *ForeTerm =
-      cast<BranchInst>(ForeBlocksLast.back()->getTerminator());
-  BasicBlock *Dest = SubLoopBlocksFirst[0];
-  ForeTerm->setSuccessor(0, Dest);
-
-  if (CompletelyUnroll) {
-    while (PHINode *Phi = dyn_cast<PHINode>(ForeBlocksFirst[0]->begin())) {
-      Phi->replaceAllUsesWith(Phi->getIncomingValueForBlock(Preheader));
-      Phi->getParent()->getInstList().erase(Phi);
-    }
-  } else {
-    // Update the PHI values to point to the last aft block
-    updatePHIBlocksAndValues(ForeBlocksFirst[0], AftBlocksLast[0],
-                             AftBlocksLast.back(), LastValueMap);
-  }
-
-  for (unsigned It = 1; It != Count; It++) {
-    // Remap ForeBlock successors from previous iteration to this
-    BranchInst *ForeTerm =
-        cast<BranchInst>(ForeBlocksLast[It - 1]->getTerminator());
-    BasicBlock *Dest = ForeBlocksFirst[It];
-    ForeTerm->setSuccessor(0, Dest);
-  }
-
-  // Subloop successors and phis
-  BranchInst *SubTerm =
-      cast<BranchInst>(SubLoopBlocksLast.back()->getTerminator());
-  SubTerm->setSuccessor(!SubLoopContinueOnTrue, SubLoopBlocksFirst[0]);
-  SubTerm->setSuccessor(SubLoopContinueOnTrue, AftBlocksFirst[0]);
-  updatePHIBlocks(SubLoopBlocksFirst[0], ForeBlocksLast[0],
-                  ForeBlocksLast.back());
-  updatePHIBlocks(SubLoopBlocksFirst[0], SubLoopBlocksLast[0],
-                  SubLoopBlocksLast.back());
-
-  for (unsigned It = 1; It != Count; It++) {
-    // Replace the conditional branch of the previous iteration subloop with an
-    // unconditional one to this one
-    BranchInst *SubTerm =
-        cast<BranchInst>(SubLoopBlocksLast[It - 1]->getTerminator());
-    BranchInst::Create(SubLoopBlocksFirst[It], SubTerm);
-    SubTerm->eraseFromParent();
-
-    updatePHIBlocks(SubLoopBlocksFirst[It], ForeBlocksLast[It],
-                    ForeBlocksLast.back());
-    updatePHIBlocks(SubLoopBlocksFirst[It], SubLoopBlocksLast[It],
-                    SubLoopBlocksLast.back());
-    movePHIs(SubLoopBlocksFirst[It], SubLoopBlocksFirst[0]);
-  }
-
-  // Aft blocks successors and phis
-  BranchInst *Term = cast<BranchInst>(AftBlocksLast.back()->getTerminator());
-  if (CompletelyUnroll) {
-    BranchInst::Create(LoopExit, Term);
-    Term->eraseFromParent();
-  } else {
-    Term->setSuccessor(!ContinueOnTrue, ForeBlocksFirst[0]);
-  }
-  updatePHIBlocks(AftBlocksFirst[0], SubLoopBlocksLast[0],
-                  SubLoopBlocksLast.back());
-
-  for (unsigned It = 1; It != Count; It++) {
-    // Replace the conditional branch of the previous iteration subloop with an
-    // unconditional one to this one
-    BranchInst *AftTerm =
-        cast<BranchInst>(AftBlocksLast[It - 1]->getTerminator());
-    BranchInst::Create(AftBlocksFirst[It], AftTerm);
-    AftTerm->eraseFromParent();
-
-    updatePHIBlocks(AftBlocksFirst[It], SubLoopBlocksLast[It],
-                    SubLoopBlocksLast.back());
-    movePHIs(AftBlocksFirst[It], AftBlocksFirst[0]);
-  }
-
-  // Dominator Tree. Remove the old links between Fore, Sub and Aft, adding the
-  // new ones required.
-  if (Count != 1) {
-    SmallVector<DominatorTree::UpdateType, 4> DTUpdates;
-    DTUpdates.emplace_back(DominatorTree::UpdateKind::Delete, ForeBlocksLast[0],
-                           SubLoopBlocksFirst[0]);
-    DTUpdates.emplace_back(DominatorTree::UpdateKind::Delete,
-                           SubLoopBlocksLast[0], AftBlocksFirst[0]);
-
-    DTUpdates.emplace_back(DominatorTree::UpdateKind::Insert,
-                           ForeBlocksLast.back(), SubLoopBlocksFirst[0]);
-    DTUpdates.emplace_back(DominatorTree::UpdateKind::Insert,
-                           SubLoopBlocksLast.back(), AftBlocksFirst[0]);
-    DT->applyUpdates(DTUpdates);
-  }
-
-  // Merge adjacent basic blocks, if possible.
-  SmallPtrSet<BasicBlock *, 16> MergeBlocks;
-  MergeBlocks.insert(ForeBlocksLast.begin(), ForeBlocksLast.end());
-  MergeBlocks.insert(SubLoopBlocksLast.begin(), SubLoopBlocksLast.end());
-  MergeBlocks.insert(AftBlocksLast.begin(), AftBlocksLast.end());
-  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
-  while (!MergeBlocks.empty()) {
-    BasicBlock *BB = *MergeBlocks.begin();
-    BranchInst *Term = dyn_cast<BranchInst>(BB->getTerminator());
-    if (Term && Term->isUnconditional() && L->contains(Term->getSuccessor(0))) {
-      BasicBlock *Dest = Term->getSuccessor(0);
-      BasicBlock *Fold = Dest->getUniquePredecessor();
-      if (MergeBlockIntoPredecessor(Dest, &DTU, LI)) {
-        // Don't remove BB and add Fold as they are the same BB
-        assert(Fold == BB);
-        (void)Fold;
-        MergeBlocks.erase(Dest);
-      } else
-        MergeBlocks.erase(BB);
-    } else
-      MergeBlocks.erase(BB);
-  }
-
-  // At this point, the code is well formed.  We now do a quick sweep over the
-  // inserted code, doing constant propagation and dead code elimination as we
-  // go.
-  simplifyLoopAfterUnroll(SubLoop, true, LI, SE, DT, AC);
-  simplifyLoopAfterUnroll(L, !CompletelyUnroll && Count > 1, LI, SE, DT, AC);
-
-  NumCompletelyUnrolledAndJammed += CompletelyUnroll;
-  ++NumUnrolledAndJammed;
-
-#ifndef NDEBUG
-  // We shouldn't have done anything to break loop simplify form or LCSSA.
-  Loop *OuterL = L->getParentLoop();
-  Loop *OutestLoop = OuterL ? OuterL : (!CompletelyUnroll ? L : SubLoop);
-  assert(OutestLoop->isRecursivelyLCSSAForm(*DT, *LI));
-  if (!CompletelyUnroll)
-    assert(L->isLoopSimplifyForm());
-  assert(SubLoop->isLoopSimplifyForm());
-  assert(DT->verify());
-#endif
-
-  // Update LoopInfo if the loop is completely removed.
-  if (CompletelyUnroll)
-    LI->erase(L);
-
-  return CompletelyUnroll ? LoopUnrollResult::FullyUnrolled
-                          : LoopUnrollResult::PartiallyUnrolled;
-}
-
-static bool getLoadsAndStores(BasicBlockSet &Blocks,
-                              SmallVector<Value *, 4> &MemInstr) {
-  // Scan the BBs and collect legal loads and stores.
-  // Returns false if non-simple loads/stores are found.
-  for (BasicBlock *BB : Blocks) {
-    for (Instruction &I : *BB) {
-      if (auto *Ld = dyn_cast<LoadInst>(&I)) {
-        if (!Ld->isSimple())
-          return false;
-        MemInstr.push_back(&I);
-      } else if (auto *St = dyn_cast<StoreInst>(&I)) {
-        if (!St->isSimple())
-          return false;
-        MemInstr.push_back(&I);
-      } else if (I.mayReadOrWriteMemory()) {
-        return false;
-      }
-    }
-  }
-  return true;
-}
-
-static bool checkDependencies(SmallVector<Value *, 4> &Earlier,
-                              SmallVector<Value *, 4> &Later,
-                              unsigned LoopDepth, bool InnerLoop,
-                              DependenceInfo &DI) {
-  // Use DA to check for dependencies between loads and stores that make unroll
-  // and jam invalid
-  for (Value *I : Earlier) {
-    for (Value *J : Later) {
-      Instruction *Src = cast<Instruction>(I);
-      Instruction *Dst = cast<Instruction>(J);
-      if (Src == Dst)
-        continue;
-      // Ignore Input dependencies.
-      if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
-        continue;
-
-      // Track dependencies, and if we find them take a conservative approach
-      // by allowing only = or < (not >), altough some > would be safe
-      // (depending upon unroll width).
-      // For the inner loop, we need to disallow any (> <) dependencies
-      // FIXME: Allow > so long as distance is less than unroll width
-      if (auto D = DI.depends(Src, Dst, true)) {
-        assert(D->isOrdered() && "Expected an output, flow or anti dep.");
-
-        if (D->isConfused()) {
-          LLVM_DEBUG(dbgs() << "  Confused dependency between:\n"
-                            << "  " << *Src << "\n"
-                            << "  " << *Dst << "\n");
-          return false;
-        }
-        if (!InnerLoop) {
-          if (D->getDirection(LoopDepth) & Dependence::DVEntry::GT) {
-            LLVM_DEBUG(dbgs() << "  > dependency between:\n"
-                              << "  " << *Src << "\n"
-                              << "  " << *Dst << "\n");
-            return false;
-          }
-        } else {
-          assert(LoopDepth + 1 <= D->getLevels());
-          if (D->getDirection(LoopDepth) & Dependence::DVEntry::GT &&
-              D->getDirection(LoopDepth + 1) & Dependence::DVEntry::LT) {
-            LLVM_DEBUG(dbgs() << "  < > dependency between:\n"
-                              << "  " << *Src << "\n"
-                              << "  " << *Dst << "\n");
-            return false;
-          }
-        }
-      }
-    }
-  }
-  return true;
-}
-
-static bool checkDependencies(Loop *L, BasicBlockSet &ForeBlocks,
-                              BasicBlockSet &SubLoopBlocks,
-                              BasicBlockSet &AftBlocks, DependenceInfo &DI) {
-  // Get all loads/store pairs for each blocks
-  SmallVector<Value *, 4> ForeMemInstr;
-  SmallVector<Value *, 4> SubLoopMemInstr;
-  SmallVector<Value *, 4> AftMemInstr;
-  if (!getLoadsAndStores(ForeBlocks, ForeMemInstr) ||
-      !getLoadsAndStores(SubLoopBlocks, SubLoopMemInstr) ||
-      !getLoadsAndStores(AftBlocks, AftMemInstr))
-    return false;
-
-  // Check for dependencies between any blocks that may change order
-  unsigned LoopDepth = L->getLoopDepth();
-  return checkDependencies(ForeMemInstr, SubLoopMemInstr, LoopDepth, false,
-                           DI) &&
-         checkDependencies(ForeMemInstr, AftMemInstr, LoopDepth, false, DI) &&
-         checkDependencies(SubLoopMemInstr, AftMemInstr, LoopDepth, false,
-                           DI) &&
-         checkDependencies(SubLoopMemInstr, SubLoopMemInstr, LoopDepth, true,
-                           DI);
-}
-
-bool llvm::isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
-                                DependenceInfo &DI) {
-  /* We currently handle outer loops like this:
-        |
-    ForeFirst    <----\    }
-     Blocks           |    } ForeBlocks
-    ForeLast          |    }
-        |             |
-    SubLoopFirst  <\  |    }
-     Blocks        |  |    } SubLoopBlocks
-    SubLoopLast   -/  |    }
-        |             |
-    AftFirst          |    }
-     Blocks           |    } AftBlocks
-    AftLast     ------/    }
-        |
-
-    There are (theoretically) any number of blocks in ForeBlocks, SubLoopBlocks
-    and AftBlocks, providing that there is one edge from Fores to SubLoops,
-    one edge from SubLoops to Afts and a single outer loop exit (from Afts).
-    In practice we currently limit Aft blocks to a single block, and limit
-    things further in the profitablility checks of the unroll and jam pass.
-
-    Because of the way we rearrange basic blocks, we also require that
-    the Fore blocks on all unrolled iterations are safe to move before the
-    SubLoop blocks of all iterations. So we require that the phi node looping
-    operands of ForeHeader can be moved to at least the end of ForeEnd, so that
-    we can arrange cloned Fore Blocks before the subloop and match up Phi's
-    correctly.
-
-    i.e. The old order of blocks used to be F1 S1_1 S1_2 A1 F2 S2_1 S2_2 A2.
-    It needs to be safe to tranform this to F1 F2 S1_1 S2_1 S1_2 S2_2 A1 A2.
-
-    There are then a number of checks along the lines of no calls, no
-    exceptions, inner loop IV is consistent, etc. Note that for loops requiring
-    runtime unrolling, UnrollRuntimeLoopRemainder can also fail in
-    UnrollAndJamLoop if the trip count cannot be easily calculated.
-  */
-
-  if (!L->isLoopSimplifyForm() || L->getSubLoops().size() != 1)
-    return false;
-  Loop *SubLoop = L->getSubLoops()[0];
-  if (!SubLoop->isLoopSimplifyForm())
-    return false;
-
-  BasicBlock *Header = L->getHeader();
-  BasicBlock *Latch = L->getLoopLatch();
-  BasicBlock *Exit = L->getExitingBlock();
-  BasicBlock *SubLoopHeader = SubLoop->getHeader();
-  BasicBlock *SubLoopLatch = SubLoop->getLoopLatch();
-  BasicBlock *SubLoopExit = SubLoop->getExitingBlock();
-
-  if (Latch != Exit)
-    return false;
-  if (SubLoopLatch != SubLoopExit)
-    return false;
-
-  if (Header->hasAddressTaken() || SubLoopHeader->hasAddressTaken()) {
-    LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Address taken\n");
-    return false;
-  }
-
-  // Split blocks into Fore/SubLoop/Aft based on dominators
-  BasicBlockSet SubLoopBlocks;
-  BasicBlockSet ForeBlocks;
-  BasicBlockSet AftBlocks;
-  if (!partitionOuterLoopBlocks(L, SubLoop, ForeBlocks, SubLoopBlocks,
-                                AftBlocks, &DT)) {
-    LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Incompatible loop layout\n");
-    return false;
-  }
-
-  // Aft blocks may need to move instructions to fore blocks, which becomes more
-  // difficult if there are multiple (potentially conditionally executed)
-  // blocks. For now we just exclude loops with multiple aft blocks.
-  if (AftBlocks.size() != 1) {
-    LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Can't currently handle "
-                         "multiple blocks after the loop\n");
-    return false;
-  }
-
-  // Check inner loop backedge count is consistent on all iterations of the
-  // outer loop
-  if (!hasIterationCountInvariantInParent(SubLoop, SE)) {
-    LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Inner loop iteration count is "
-                         "not consistent on each iteration\n");
-    return false;
-  }
-
-  // Check the loop safety info for exceptions.
-  SimpleLoopSafetyInfo LSI;
-  LSI.computeLoopSafetyInfo(L);
-  if (LSI.anyBlockMayThrow()) {
-    LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Something may throw\n");
-    return false;
-  }
-
-  // We've ruled out the easy stuff and now need to check that there are no
-  // interdependencies which may prevent us from moving the:
-  //  ForeBlocks before Subloop and AftBlocks.
-  //  Subloop before AftBlocks.
-  //  ForeBlock phi operands before the subloop
-
-  // Make sure we can move all instructions we need to before the subloop
-  if (!processHeaderPhiOperands(
-          Header, Latch, AftBlocks, [&AftBlocks, &SubLoop](Instruction *I) {
-            if (SubLoop->contains(I->getParent()))
-              return false;
-            if (AftBlocks.count(I->getParent())) {
-              // If we hit a phi node in afts we know we are done (probably
-              // LCSSA)
-              if (isa<PHINode>(I))
-                return false;
-              // Can't move instructions with side effects or memory
-              // reads/writes
-              if (I->mayHaveSideEffects() || I->mayReadOrWriteMemory())
-                return false;
-            }
-            // Keep going
-            return true;
-          })) {
-    LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; can't move required "
-                         "instructions after subloop to before it\n");
-    return false;
-  }
-
-  // Check for memory dependencies which prohibit the unrolling we are doing.
-  // Because of the way we are unrolling Fore/Sub/Aft blocks, we need to check
-  // there are no dependencies between Fore-Sub, Fore-Aft, Sub-Aft and Sub-Sub.
-  if (!checkDependencies(L, ForeBlocks, SubLoopBlocks, AftBlocks, DI)) {
-    LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; failed dependency check\n");
-    return false;
-  }
-
-  return true;
-}