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