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