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