1 //===- FixIrreducible.cpp - Convert irreducible control-flow into loops ---===//
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 // An irreducible SCC is one which has multiple "header" blocks, i.e., blocks
10 // with control-flow edges incident from outside the SCC. This pass converts a
11 // irreducible SCC into a natural loop by applying the following transformation:
12 //
13 // 1. Collect the set of headers H of the SCC.
14 // 2. Collect the set of predecessors P of these headers. These may be inside as
15 // well as outside the SCC.
16 // 3. Create block N and redirect every edge from set P to set H through N.
17 //
18 // This converts the SCC into a natural loop with N as the header: N is the only
19 // block with edges incident from outside the SCC, and all backedges in the SCC
20 // are incident on N, i.e., for every backedge, the head now dominates the tail.
21 //
22 // INPUT CFG: The blocks A and B form an irreducible loop with two headers.
23 //
24 // Entry
25 // / \
26 // v v
27 // A ----> B
28 // ^ /|
29 // `----' |
30 // v
31 // Exit
32 //
33 // OUTPUT CFG: Edges incident on A and B are now redirected through a
34 // new block N, forming a natural loop consisting of N, A and B.
35 //
36 // Entry
37 // |
38 // v
39 // .---> N <---.
40 // / / \ \
41 // | / \ |
42 // \ v v /
43 // `-- A B --'
44 // |
45 // v
46 // Exit
47 //
48 // The transformation is applied to every maximal SCC that is not already
49 // recognized as a loop. The pass operates on all maximal SCCs found in the
50 // function body outside of any loop, as well as those found inside each loop,
51 // including inside any newly created loops. This ensures that any SCC hidden
52 // inside a maximal SCC is also transformed.
53 //
54 // The actual transformation is handled by function CreateControlFlowHub, which
55 // takes a set of incoming blocks (the predecessors) and outgoing blocks (the
56 // headers). The function also moves every PHINode in an outgoing block to the
57 // hub. Since the hub dominates all the outgoing blocks, each such PHINode
58 // continues to dominate its uses. Since every header in an SCC has at least two
59 // predecessors, every value used in the header (or later) but defined in a
60 // predecessor (or earlier) is represented by a PHINode in a header. Hence the
61 // above handling of PHINodes is sufficient and no further processing is
62 // required to restore SSA.
63 //
64 // Limitation: The pass cannot handle switch statements and indirect
65 // branches. Both must be lowered to plain branches first.
66 //
67 //===----------------------------------------------------------------------===//
68
69 #include "llvm/Transforms/Utils/FixIrreducible.h"
70 #include "llvm/ADT/SCCIterator.h"
71 #include "llvm/Analysis/LoopIterator.h"
72 #include "llvm/InitializePasses.h"
73 #include "llvm/Pass.h"
74 #include "llvm/Transforms/Utils.h"
75 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
76
77 #define DEBUG_TYPE "fix-irreducible"
78
79 using namespace llvm;
80
81 namespace {
82 struct FixIrreducible : public FunctionPass {
83 static char ID;
FixIrreducible__anon1ecf022b0111::FixIrreducible84 FixIrreducible() : FunctionPass(ID) {
85 initializeFixIrreduciblePass(*PassRegistry::getPassRegistry());
86 }
87
getAnalysisUsage__anon1ecf022b0111::FixIrreducible88 void getAnalysisUsage(AnalysisUsage &AU) const override {
89 AU.addRequiredID(LowerSwitchID);
90 AU.addRequired<DominatorTreeWrapperPass>();
91 AU.addRequired<LoopInfoWrapperPass>();
92 AU.addPreservedID(LowerSwitchID);
93 AU.addPreserved<DominatorTreeWrapperPass>();
94 AU.addPreserved<LoopInfoWrapperPass>();
95 }
96
97 bool runOnFunction(Function &F) override;
98 };
99 } // namespace
100
101 char FixIrreducible::ID = 0;
102
createFixIrreduciblePass()103 FunctionPass *llvm::createFixIrreduciblePass() { return new FixIrreducible(); }
104
105 INITIALIZE_PASS_BEGIN(FixIrreducible, "fix-irreducible",
106 "Convert irreducible control-flow into natural loops",
107 false /* Only looks at CFG */, false /* Analysis Pass */)
INITIALIZE_PASS_DEPENDENCY(LowerSwitchLegacyPass)108 INITIALIZE_PASS_DEPENDENCY(LowerSwitchLegacyPass)
109 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
110 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
111 INITIALIZE_PASS_END(FixIrreducible, "fix-irreducible",
112 "Convert irreducible control-flow into natural loops",
113 false /* Only looks at CFG */, false /* Analysis Pass */)
114
115 // When a new loop is created, existing children of the parent loop may now be
116 // fully inside the new loop. Reconnect these as children of the new loop.
117 static void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop,
118 SetVector<BasicBlock *> &Blocks,
119 SetVector<BasicBlock *> &Headers) {
120 auto &CandidateLoops = ParentLoop ? ParentLoop->getSubLoopsVector()
121 : LI.getTopLevelLoopsVector();
122 // The new loop cannot be its own child, and any candidate is a
123 // child iff its header is owned by the new loop. Move all the
124 // children to a new vector.
125 auto FirstChild = std::partition(
126 CandidateLoops.begin(), CandidateLoops.end(), [&](Loop *L) {
127 return L == NewLoop || Blocks.count(L->getHeader()) == 0;
128 });
129 SmallVector<Loop *, 8> ChildLoops(FirstChild, CandidateLoops.end());
130 CandidateLoops.erase(FirstChild, CandidateLoops.end());
131
132 for (auto II = ChildLoops.begin(), IE = ChildLoops.end(); II != IE; ++II) {
133 auto Child = *II;
134 LLVM_DEBUG(dbgs() << "child loop: " << Child->getHeader()->getName()
135 << "\n");
136 // TODO: A child loop whose header is also a header in the current
137 // SCC gets destroyed since its backedges are removed. That may
138 // not be necessary if we can retain such backedges.
139 if (Headers.count(Child->getHeader())) {
140 for (auto BB : Child->blocks()) {
141 LI.changeLoopFor(BB, NewLoop);
142 LLVM_DEBUG(dbgs() << "moved block from child: " << BB->getName()
143 << "\n");
144 }
145 LI.destroy(Child);
146 LLVM_DEBUG(dbgs() << "subsumed child loop (common header)\n");
147 continue;
148 }
149
150 Child->setParentLoop(nullptr);
151 NewLoop->addChildLoop(Child);
152 LLVM_DEBUG(dbgs() << "added child loop to new loop\n");
153 }
154 }
155
156 // Given a set of blocks and headers in an irreducible SCC, convert it into a
157 // natural loop. Also insert this new loop at its appropriate place in the
158 // hierarchy of loops.
createNaturalLoopInternal(LoopInfo & LI,DominatorTree & DT,Loop * ParentLoop,SetVector<BasicBlock * > & Blocks,SetVector<BasicBlock * > & Headers)159 static void createNaturalLoopInternal(LoopInfo &LI, DominatorTree &DT,
160 Loop *ParentLoop,
161 SetVector<BasicBlock *> &Blocks,
162 SetVector<BasicBlock *> &Headers) {
163 #ifndef NDEBUG
164 // All headers are part of the SCC
165 for (auto H : Headers) {
166 assert(Blocks.count(H));
167 }
168 #endif
169
170 SetVector<BasicBlock *> Predecessors;
171 for (auto H : Headers) {
172 for (auto P : predecessors(H)) {
173 Predecessors.insert(P);
174 }
175 }
176
177 LLVM_DEBUG(
178 dbgs() << "Found predecessors:";
179 for (auto P : Predecessors) {
180 dbgs() << " " << P->getName();
181 }
182 dbgs() << "\n");
183
184 // Redirect all the backedges through a "hub" consisting of a series
185 // of guard blocks that manage the flow of control from the
186 // predecessors to the headers.
187 SmallVector<BasicBlock *, 8> GuardBlocks;
188 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
189 CreateControlFlowHub(&DTU, GuardBlocks, Predecessors, Headers, "irr");
190 #if defined(EXPENSIVE_CHECKS)
191 assert(DT.verify(DominatorTree::VerificationLevel::Full));
192 #else
193 assert(DT.verify(DominatorTree::VerificationLevel::Fast));
194 #endif
195
196 // Create a new loop from the now-transformed cycle
197 auto NewLoop = LI.AllocateLoop();
198 if (ParentLoop) {
199 ParentLoop->addChildLoop(NewLoop);
200 } else {
201 LI.addTopLevelLoop(NewLoop);
202 }
203
204 // Add the guard blocks to the new loop. The first guard block is
205 // the head of all the backedges, and it is the first to be inserted
206 // in the loop. This ensures that it is recognized as the
207 // header. Since the new loop is already in LoopInfo, the new blocks
208 // are also propagated up the chain of parent loops.
209 for (auto G : GuardBlocks) {
210 LLVM_DEBUG(dbgs() << "added guard block: " << G->getName() << "\n");
211 NewLoop->addBasicBlockToLoop(G, LI);
212 }
213
214 // Add the SCC blocks to the new loop.
215 for (auto BB : Blocks) {
216 NewLoop->addBlockEntry(BB);
217 if (LI.getLoopFor(BB) == ParentLoop) {
218 LLVM_DEBUG(dbgs() << "moved block from parent: " << BB->getName()
219 << "\n");
220 LI.changeLoopFor(BB, NewLoop);
221 } else {
222 LLVM_DEBUG(dbgs() << "added block from child: " << BB->getName() << "\n");
223 }
224 }
225 LLVM_DEBUG(dbgs() << "header for new loop: "
226 << NewLoop->getHeader()->getName() << "\n");
227
228 reconnectChildLoops(LI, ParentLoop, NewLoop, Blocks, Headers);
229
230 NewLoop->verifyLoop();
231 if (ParentLoop) {
232 ParentLoop->verifyLoop();
233 }
234 #if defined(EXPENSIVE_CHECKS)
235 LI.verify(DT);
236 #endif // EXPENSIVE_CHECKS
237 }
238
239 namespace llvm {
240 // Enable the graph traits required for traversing a Loop body.
241 template <> struct GraphTraits<Loop> : LoopBodyTraits {};
242 } // namespace llvm
243
244 // Overloaded wrappers to go with the function template below.
unwrapBlock(BasicBlock * B)245 static BasicBlock *unwrapBlock(BasicBlock *B) { return B; }
unwrapBlock(LoopBodyTraits::NodeRef & N)246 static BasicBlock *unwrapBlock(LoopBodyTraits::NodeRef &N) { return N.second; }
247
createNaturalLoop(LoopInfo & LI,DominatorTree & DT,Function * F,SetVector<BasicBlock * > & Blocks,SetVector<BasicBlock * > & Headers)248 static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Function *F,
249 SetVector<BasicBlock *> &Blocks,
250 SetVector<BasicBlock *> &Headers) {
251 createNaturalLoopInternal(LI, DT, nullptr, Blocks, Headers);
252 }
253
createNaturalLoop(LoopInfo & LI,DominatorTree & DT,Loop & L,SetVector<BasicBlock * > & Blocks,SetVector<BasicBlock * > & Headers)254 static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Loop &L,
255 SetVector<BasicBlock *> &Blocks,
256 SetVector<BasicBlock *> &Headers) {
257 createNaturalLoopInternal(LI, DT, &L, Blocks, Headers);
258 }
259
260 // Convert irreducible SCCs; Graph G may be a Function* or a Loop&.
261 template <class Graph>
makeReducible(LoopInfo & LI,DominatorTree & DT,Graph && G)262 static bool makeReducible(LoopInfo &LI, DominatorTree &DT, Graph &&G) {
263 bool Changed = false;
264 for (auto Scc = scc_begin(G); !Scc.isAtEnd(); ++Scc) {
265 if (Scc->size() < 2)
266 continue;
267 SetVector<BasicBlock *> Blocks;
268 LLVM_DEBUG(dbgs() << "Found SCC:");
269 for (auto N : *Scc) {
270 auto BB = unwrapBlock(N);
271 LLVM_DEBUG(dbgs() << " " << BB->getName());
272 Blocks.insert(BB);
273 }
274 LLVM_DEBUG(dbgs() << "\n");
275
276 // Minor optimization: The SCC blocks are usually discovered in an order
277 // that is the opposite of the order in which these blocks appear as branch
278 // targets. This results in a lot of condition inversions in the control
279 // flow out of the new ControlFlowHub, which can be mitigated if the orders
280 // match. So we discover the headers using the reverse of the block order.
281 SetVector<BasicBlock *> Headers;
282 LLVM_DEBUG(dbgs() << "Found headers:");
283 for (auto BB : reverse(Blocks)) {
284 for (const auto P : predecessors(BB)) {
285 // Skip unreachable predecessors.
286 if (!DT.isReachableFromEntry(P))
287 continue;
288 if (!Blocks.count(P)) {
289 LLVM_DEBUG(dbgs() << " " << BB->getName());
290 Headers.insert(BB);
291 break;
292 }
293 }
294 }
295 LLVM_DEBUG(dbgs() << "\n");
296
297 if (Headers.size() == 1) {
298 assert(LI.isLoopHeader(Headers.front()));
299 LLVM_DEBUG(dbgs() << "Natural loop with a single header: skipped\n");
300 continue;
301 }
302 createNaturalLoop(LI, DT, G, Blocks, Headers);
303 Changed = true;
304 }
305 return Changed;
306 }
307
FixIrreducibleImpl(Function & F,LoopInfo & LI,DominatorTree & DT)308 static bool FixIrreducibleImpl(Function &F, LoopInfo &LI, DominatorTree &DT) {
309 LLVM_DEBUG(dbgs() << "===== Fix irreducible control-flow in function: "
310 << F.getName() << "\n");
311
312 bool Changed = false;
313 SmallVector<Loop *, 8> WorkList;
314
315 LLVM_DEBUG(dbgs() << "visiting top-level\n");
316 Changed |= makeReducible(LI, DT, &F);
317
318 // Any SCCs reduced are now already in the list of top-level loops, so simply
319 // add them all to the worklist.
320 append_range(WorkList, LI);
321
322 while (!WorkList.empty()) {
323 auto L = WorkList.pop_back_val();
324 LLVM_DEBUG(dbgs() << "visiting loop with header "
325 << L->getHeader()->getName() << "\n");
326 Changed |= makeReducible(LI, DT, *L);
327 // Any SCCs reduced are now already in the list of child loops, so simply
328 // add them all to the worklist.
329 WorkList.append(L->begin(), L->end());
330 }
331
332 return Changed;
333 }
334
runOnFunction(Function & F)335 bool FixIrreducible::runOnFunction(Function &F) {
336 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
337 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
338 return FixIrreducibleImpl(F, LI, DT);
339 }
340
run(Function & F,FunctionAnalysisManager & AM)341 PreservedAnalyses FixIrreduciblePass::run(Function &F,
342 FunctionAnalysisManager &AM) {
343 auto &LI = AM.getResult<LoopAnalysis>(F);
344 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
345 if (!FixIrreducibleImpl(F, LI, DT))
346 return PreservedAnalyses::all();
347 PreservedAnalyses PA;
348 PA.preserve<LoopAnalysis>();
349 PA.preserve<DominatorTreeAnalysis>();
350 return PA;
351 }
352