llvm/lib/Transforms/Utils/UnifyLoopExits.cpp

   1 //===- UnifyLoopExits.cpp - Redirect exiting edges to one block -*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // For each natural loop with multiple exit blocks, this pass creates a new
  10 // block N such that all exiting blocks now branch to N, and then control flow
  11 // is redistributed to all the original exit blocks.
  12 //
  13 // Limitation: This assumes that all terminators in the CFG are direct branches
  14 //             (the "br" instruction). The presence of any other control flow
  15 //             such as indirectbr, switch or callbr will cause an assert.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "llvm/Transforms/Utils/UnifyLoopExits.h"
  20 #include "llvm/ADT/MapVector.h"
  21 #include "llvm/Analysis/DomTreeUpdater.h"
  22 #include "llvm/Analysis/LoopInfo.h"
  23 #include "llvm/IR/Constants.h"
  24 #include "llvm/IR/Dominators.h"
  25 #include "llvm/InitializePasses.h"
  26 #include "llvm/Support/CommandLine.h"
  27 #include "llvm/Transforms/Utils.h"
  28 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  29
  30 #define DEBUG_TYPE "unify-loop-exits"
  31
  32 using namespace llvm;
  33
  34 static cl::opt<unsigned> MaxBooleansInControlFlowHub(
  35     "max-booleans-in-control-flow-hub", cl::init(32), cl::Hidden,
  36     cl::desc("Set the maximum number of outgoing blocks for using a boolean "
  37              "value to record the exiting block in CreateControlFlowHub."));
  38
  39 namespace {
  40 struct UnifyLoopExitsLegacyPass : public FunctionPass {
  41   static char ID;
  42   UnifyLoopExitsLegacyPass() : FunctionPass(ID) {
  43     initializeUnifyLoopExitsLegacyPassPass(*PassRegistry::getPassRegistry());
  44   }
  45
  46   void getAnalysisUsage(AnalysisUsage &AU) const override {
  47     AU.addRequired<LoopInfoWrapperPass>();
  48     AU.addRequired<DominatorTreeWrapperPass>();
  49     AU.addPreserved<LoopInfoWrapperPass>();
  50     AU.addPreserved<DominatorTreeWrapperPass>();
  51   }
  52
  53   bool runOnFunction(Function &F) override;
  54 };
  55 } // namespace
  56
  57 char UnifyLoopExitsLegacyPass::ID = 0;
  58
  59 FunctionPass *llvm::createUnifyLoopExitsPass() {
  60   return new UnifyLoopExitsLegacyPass();
  61 }
  62
  63 INITIALIZE_PASS_BEGIN(UnifyLoopExitsLegacyPass, "unify-loop-exits",
  64                       "Fixup each natural loop to have a single exit block",
  65                       false /* Only looks at CFG */, false /* Analysis Pass */)
  66 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
  67 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
  68 INITIALIZE_PASS_END(UnifyLoopExitsLegacyPass, "unify-loop-exits",
  69                     "Fixup each natural loop to have a single exit block",
  70                     false /* Only looks at CFG */, false /* Analysis Pass */)
  71
  72 // The current transform introduces new control flow paths which may break the
  73 // SSA requirement that every def must dominate all its uses. For example,
  74 // consider a value D defined inside the loop that is used by some instruction
  75 // U outside the loop. It follows that D dominates U, since the original
  76 // program has valid SSA form. After merging the exits, all paths from D to U
  77 // now flow through the unified exit block. In addition, there may be other
  78 // paths that do not pass through D, but now reach the unified exit
  79 // block. Thus, D no longer dominates U.
  80 //
  81 // Restore the dominance by creating a phi for each such D at the new unified
  82 // loop exit. But when doing this, ignore any uses U that are in the new unified
  83 // loop exit, since those were introduced specially when the block was created.
  84 //
  85 // The use of SSAUpdater seems like overkill for this operation. The location
  86 // for creating the new PHI is well-known, and also the set of incoming blocks
  87 // to the new PHI.
  88 static void restoreSSA(const DominatorTree &DT, const Loop *L,
  89                        const SetVector<BasicBlock *> &Incoming,
  90                        BasicBlock *LoopExitBlock) {
  91   using InstVector = SmallVector<Instruction *, 8>;
  92   using IIMap = MapVector<Instruction *, InstVector>;
  93   IIMap ExternalUsers;
  94   for (auto *BB : L->blocks()) {
  95     for (auto &I : *BB) {
  96       for (auto &U : I.uses()) {
  97         auto UserInst = cast<Instruction>(U.getUser());
  98         auto UserBlock = UserInst->getParent();
  99         if (UserBlock == LoopExitBlock)
 100           continue;
 101         if (L->contains(UserBlock))
 102           continue;
 103         LLVM_DEBUG(dbgs() << "added ext use for " << I.getName() << "("
 104                           << BB->getName() << ")"
 105                           << ": " << UserInst->getName() << "("
 106                           << UserBlock->getName() << ")"
 107                           << "\n");
 108         ExternalUsers[&I].push_back(UserInst);
 109       }
 110     }
 111   }
 112
 113   for (const auto &II : ExternalUsers) {
 114     // For each Def used outside the loop, create NewPhi in
 115     // LoopExitBlock. NewPhi receives Def only along exiting blocks that
 116     // dominate it, while the remaining values are undefined since those paths
 117     // didn't exist in the original CFG.
 118     auto Def = II.first;
 119     LLVM_DEBUG(dbgs() << "externally used: " << Def->getName() << "\n");
 120     auto NewPhi =
 121         PHINode::Create(Def->getType(), Incoming.size(),
 122                         Def->getName() + ".moved", &LoopExitBlock->front());
 123     for (auto *In : Incoming) {
 124       LLVM_DEBUG(dbgs() << "predecessor " << In->getName() << ": ");
 125       if (Def->getParent() == In || DT.dominates(Def, In)) {
 126         LLVM_DEBUG(dbgs() << "dominated\n");
 127         NewPhi->addIncoming(Def, In);
 128       } else {
 129         LLVM_DEBUG(dbgs() << "not dominated\n");
 130         NewPhi->addIncoming(PoisonValue::get(Def->getType()), In);
 131       }
 132     }
 133
 134     LLVM_DEBUG(dbgs() << "external users:");
 135     for (auto *U : II.second) {
 136       LLVM_DEBUG(dbgs() << " " << U->getName());
 137       U->replaceUsesOfWith(Def, NewPhi);
 138     }
 139     LLVM_DEBUG(dbgs() << "\n");
 140   }
 141 }
 142
 143 static bool unifyLoopExits(DominatorTree &DT, LoopInfo &LI, Loop *L) {
 144   // To unify the loop exits, we need a list of the exiting blocks as
 145   // well as exit blocks. The functions for locating these lists both
 146   // traverse the entire loop body. It is more efficient to first
 147   // locate the exiting blocks and then examine their successors to
 148   // locate the exit blocks.
 149   SetVector<BasicBlock *> ExitingBlocks;
 150   SetVector<BasicBlock *> Exits;
 151
 152   // We need SetVectors, but the Loop API takes a vector, so we use a temporary.
 153   SmallVector<BasicBlock *, 8> Temp;
 154   L->getExitingBlocks(Temp);
 155   for (auto *BB : Temp) {
 156     ExitingBlocks.insert(BB);
 157     for (auto *S : successors(BB)) {
 158       auto SL = LI.getLoopFor(S);
 159       // A successor is not an exit if it is directly or indirectly in the
 160       // current loop.
 161       if (SL == L || L->contains(SL))
 162         continue;
 163       Exits.insert(S);
 164     }
 165   }
 166
 167   LLVM_DEBUG(
 168       dbgs() << "Found exit blocks:";
 169       for (auto Exit : Exits) {
 170         dbgs() << " " << Exit->getName();
 171       }
 172       dbgs() << "\n";
 173
 174       dbgs() << "Found exiting blocks:";
 175       for (auto EB : ExitingBlocks) {
 176         dbgs() << " " << EB->getName();
 177       }
 178       dbgs() << "\n";);
 179
 180   if (Exits.size() <= 1) {
 181     LLVM_DEBUG(dbgs() << "loop does not have multiple exits; nothing to do\n");
 182     return false;
 183   }
 184
 185   SmallVector<BasicBlock *, 8> GuardBlocks;
 186   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
 187   auto LoopExitBlock =
 188       CreateControlFlowHub(&DTU, GuardBlocks, ExitingBlocks, Exits, "loop.exit",
 189                            MaxBooleansInControlFlowHub.getValue());
 190
 191   restoreSSA(DT, L, ExitingBlocks, LoopExitBlock);
 192
 193 #if defined(EXPENSIVE_CHECKS)
 194   assert(DT.verify(DominatorTree::VerificationLevel::Full));
 195 #else
 196   assert(DT.verify(DominatorTree::VerificationLevel::Fast));
 197 #endif // EXPENSIVE_CHECKS
 198   L->verifyLoop();
 199
 200   // The guard blocks were created outside the loop, so they need to become
 201   // members of the parent loop.
 202   if (auto ParentLoop = L->getParentLoop()) {
 203     for (auto *G : GuardBlocks) {
 204       ParentLoop->addBasicBlockToLoop(G, LI);
 205     }
 206     ParentLoop->verifyLoop();
 207   }
 208
 209 #if defined(EXPENSIVE_CHECKS)
 210   LI.verify(DT);
 211 #endif // EXPENSIVE_CHECKS
 212
 213   return true;
 214 }
 215
 216 static bool runImpl(LoopInfo &LI, DominatorTree &DT) {
 217
 218   bool Changed = false;
 219   auto Loops = LI.getLoopsInPreorder();
 220   for (auto *L : Loops) {
 221     LLVM_DEBUG(dbgs() << "Loop: " << L->getHeader()->getName() << " (depth: "
 222                       << LI.getLoopDepth(L->getHeader()) << ")\n");
 223     Changed |= unifyLoopExits(DT, LI, L);
 224   }
 225   return Changed;
 226 }
 227
 228 bool UnifyLoopExitsLegacyPass::runOnFunction(Function &F) {
 229   LLVM_DEBUG(dbgs() << "===== Unifying loop exits in function " << F.getName()
 230                     << "\n");
 231   auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 232   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 233
 234   assert(hasOnlySimpleTerminator(F) && "Unsupported block terminator.");
 235
 236   return runImpl(LI, DT);
 237 }
 238
 239 namespace llvm {
 240
 241 PreservedAnalyses UnifyLoopExitsPass::run(Function &F,
 242                                           FunctionAnalysisManager &AM) {
 243   auto &LI = AM.getResult<LoopAnalysis>(F);
 244   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 245
 246   if (!runImpl(LI, DT))
 247     return PreservedAnalyses::all();
 248   PreservedAnalyses PA;
 249   PA.preserve<LoopAnalysis>();
 250   PA.preserve<DominatorTreeAnalysis>();
 251   return PA;
 252 }
 253 } // namespace llvm