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/DomTreeUpdater.h"
72#include "llvm/Analysis/LoopIterator.h"
73#include "llvm/InitializePasses.h"
74#include "llvm/Pass.h"
75#include "llvm/Transforms/Utils.h"
76#include "llvm/Transforms/Utils/BasicBlockUtils.h"
77
78#define DEBUG_TYPE "fix-irreducible"
79
80using namespace llvm;
81
82namespace {
83struct FixIrreducible : public FunctionPass {
84 static char ID;
85 FixIrreducible() : FunctionPass(ID) {
86 initializeFixIrreduciblePass(*PassRegistry::getPassRegistry());
87 }
88
89 void getAnalysisUsage(AnalysisUsage &AU) const override {
90 AU.addRequired<DominatorTreeWrapperPass>();
91 AU.addRequired<LoopInfoWrapperPass>();
92 AU.addPreserved<DominatorTreeWrapperPass>();
93 AU.addPreserved<LoopInfoWrapperPass>();
94 }
95
96 bool runOnFunction(Function &F) override;
97};
98} // namespace
99
100char FixIrreducible::ID = 0;
101
102FunctionPass *llvm::createFixIrreduciblePass() { return new FixIrreducible(); }
103
104INITIALIZE_PASS_BEGIN(FixIrreducible, "fix-irreducible",
105 "Convert irreducible control-flow into natural loops",
106 false /* Only looks at CFG */, false /* Analysis Pass */)
107INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
108INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
109INITIALIZE_PASS_END(FixIrreducible, "fix-irreducible",
110 "Convert irreducible control-flow into natural loops",
111 false /* Only looks at CFG */, false /* Analysis Pass */)
112
113// When a new loop is created, existing children of the parent loop may now be
114// fully inside the new loop. Reconnect these as children of the new loop.
115static void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop,
116 SetVector<BasicBlock *> &Blocks,
117 SetVector<BasicBlock *> &Headers) {
118 auto &CandidateLoops = ParentLoop ? ParentLoop->getSubLoopsVector()
119 : LI.getTopLevelLoopsVector();
120 // The new loop cannot be its own child, and any candidate is a
121 // child iff its header is owned by the new loop. Move all the
122 // children to a new vector.
123 auto FirstChild = std::partition(
124 first: CandidateLoops.begin(), last: CandidateLoops.end(), pred: [&](Loop *L) {
125 return L == NewLoop || !Blocks.contains(key: L->getHeader());
126 });
127 SmallVector<Loop *, 8> ChildLoops(FirstChild, CandidateLoops.end());
128 CandidateLoops.erase(first: FirstChild, last: CandidateLoops.end());
129
130 for (Loop *Child : ChildLoops) {
131 LLVM_DEBUG(dbgs() << "child loop: " << Child->getHeader()->getName()
132 << "\n");
133 // TODO: A child loop whose header is also a header in the current
134 // SCC gets destroyed since its backedges are removed. That may
135 // not be necessary if we can retain such backedges.
136 if (Headers.count(key: Child->getHeader())) {
137 for (auto *BB : Child->blocks()) {
138 if (LI.getLoopFor(BB) != Child)
139 continue;
140 LI.changeLoopFor(BB, L: NewLoop);
141 LLVM_DEBUG(dbgs() << "moved block from child: " << BB->getName()
142 << "\n");
143 }
144 std::vector<Loop *> GrandChildLoops;
145 std::swap(x&: GrandChildLoops, y&: Child->getSubLoopsVector());
146 for (auto *GrandChildLoop : GrandChildLoops) {
147 GrandChildLoop->setParentLoop(nullptr);
148 NewLoop->addChildLoop(NewChild: GrandChildLoop);
149 }
150 LI.destroy(L: Child);
151 LLVM_DEBUG(dbgs() << "subsumed child loop (common header)\n");
152 continue;
153 }
154
155 Child->setParentLoop(nullptr);
156 NewLoop->addChildLoop(NewChild: Child);
157 LLVM_DEBUG(dbgs() << "added child loop to new loop\n");
158 }
159}
160
161// Given a set of blocks and headers in an irreducible SCC, convert it into a
162// natural loop. Also insert this new loop at its appropriate place in the
163// hierarchy of loops.
164static void createNaturalLoopInternal(LoopInfo &LI, DominatorTree &DT,
165 Loop *ParentLoop,
166 SetVector<BasicBlock *> &Blocks,
167 SetVector<BasicBlock *> &Headers) {
168#ifndef NDEBUG
169 // All headers are part of the SCC
170 for (auto *H : Headers) {
171 assert(Blocks.count(H));
172 }
173#endif
174
175 SetVector<BasicBlock *> Predecessors;
176 for (auto *H : Headers) {
177 for (auto *P : predecessors(BB: H)) {
178 Predecessors.insert(X: P);
179 }
180 }
181
182 LLVM_DEBUG(
183 dbgs() << "Found predecessors:";
184 for (auto P : Predecessors) {
185 dbgs() << " " << P->getName();
186 }
187 dbgs() << "\n");
188
189 // Redirect all the backedges through a "hub" consisting of a series
190 // of guard blocks that manage the flow of control from the
191 // predecessors to the headers.
192 SmallVector<BasicBlock *, 8> GuardBlocks;
193 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
194 CreateControlFlowHub(DTU: &DTU, GuardBlocks, Predecessors, Successors: Headers, Prefix: "irr");
195#if defined(EXPENSIVE_CHECKS)
196 assert(DT.verify(DominatorTree::VerificationLevel::Full));
197#else
198 assert(DT.verify(DominatorTree::VerificationLevel::Fast));
199#endif
200
201 // Create a new loop from the now-transformed cycle
202 auto NewLoop = LI.AllocateLoop();
203 if (ParentLoop) {
204 ParentLoop->addChildLoop(NewChild: NewLoop);
205 } else {
206 LI.addTopLevelLoop(New: NewLoop);
207 }
208
209 // Add the guard blocks to the new loop. The first guard block is
210 // the head of all the backedges, and it is the first to be inserted
211 // in the loop. This ensures that it is recognized as the
212 // header. Since the new loop is already in LoopInfo, the new blocks
213 // are also propagated up the chain of parent loops.
214 for (auto *G : GuardBlocks) {
215 LLVM_DEBUG(dbgs() << "added guard block: " << G->getName() << "\n");
216 NewLoop->addBasicBlockToLoop(NewBB: G, LI);
217 }
218
219 // Add the SCC blocks to the new loop.
220 for (auto *BB : Blocks) {
221 NewLoop->addBlockEntry(BB);
222 if (LI.getLoopFor(BB) == ParentLoop) {
223 LLVM_DEBUG(dbgs() << "moved block from parent: " << BB->getName()
224 << "\n");
225 LI.changeLoopFor(BB, L: NewLoop);
226 } else {
227 LLVM_DEBUG(dbgs() << "added block from child: " << BB->getName() << "\n");
228 }
229 }
230 LLVM_DEBUG(dbgs() << "header for new loop: "
231 << NewLoop->getHeader()->getName() << "\n");
232
233 reconnectChildLoops(LI, ParentLoop, NewLoop, Blocks, Headers);
234
235 NewLoop->verifyLoop();
236 if (ParentLoop) {
237 ParentLoop->verifyLoop();
238 }
239#if defined(EXPENSIVE_CHECKS)
240 LI.verify(DT);
241#endif // EXPENSIVE_CHECKS
242}
243
244namespace llvm {
245// Enable the graph traits required for traversing a Loop body.
246template <> struct GraphTraits<Loop> : LoopBodyTraits {};
247} // namespace llvm
248
249// Overloaded wrappers to go with the function template below.
250static BasicBlock *unwrapBlock(BasicBlock *B) { return B; }
251static BasicBlock *unwrapBlock(LoopBodyTraits::NodeRef &N) { return N.second; }
252
253static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Function *F,
254 SetVector<BasicBlock *> &Blocks,
255 SetVector<BasicBlock *> &Headers) {
256 createNaturalLoopInternal(LI, DT, ParentLoop: nullptr, Blocks, Headers);
257}
258
259static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Loop &L,
260 SetVector<BasicBlock *> &Blocks,
261 SetVector<BasicBlock *> &Headers) {
262 createNaturalLoopInternal(LI, DT, ParentLoop: &L, Blocks, Headers);
263}
264
265// Convert irreducible SCCs; Graph G may be a Function* or a Loop&.
266template <class Graph>
267static bool makeReducible(LoopInfo &LI, DominatorTree &DT, Graph &&G) {
268 bool Changed = false;
269 for (auto Scc = scc_begin(G); !Scc.isAtEnd(); ++Scc) {
270 if (Scc->size() < 2)
271 continue;
272 SetVector<BasicBlock *> Blocks;
273 LLVM_DEBUG(dbgs() << "Found SCC:");
274 for (auto N : *Scc) {
275 auto BB = unwrapBlock(N);
276 LLVM_DEBUG(dbgs() << " " << BB->getName());
277 Blocks.insert(BB);
278 }
279 LLVM_DEBUG(dbgs() << "\n");
280
281 // Minor optimization: The SCC blocks are usually discovered in an order
282 // that is the opposite of the order in which these blocks appear as branch
283 // targets. This results in a lot of condition inversions in the control
284 // flow out of the new ControlFlowHub, which can be mitigated if the orders
285 // match. So we discover the headers using the reverse of the block order.
286 SetVector<BasicBlock *> Headers;
287 LLVM_DEBUG(dbgs() << "Found headers:");
288 for (auto *BB : reverse(C&: Blocks)) {
289 for (const auto P : predecessors(BB)) {
290 // Skip unreachable predecessors.
291 if (!DT.isReachableFromEntry(A: P))
292 continue;
293 if (!Blocks.count(key: P)) {
294 LLVM_DEBUG(dbgs() << " " << BB->getName());
295 Headers.insert(X: BB);
296 break;
297 }
298 }
299 }
300 LLVM_DEBUG(dbgs() << "\n");
301
302 if (Headers.size() == 1) {
303 assert(LI.isLoopHeader(Headers.front()));
304 LLVM_DEBUG(dbgs() << "Natural loop with a single header: skipped\n");
305 continue;
306 }
307 createNaturalLoop(LI, DT, G, Blocks, Headers);
308 Changed = true;
309 }
310 return Changed;
311}
312
313static bool FixIrreducibleImpl(Function &F, LoopInfo &LI, DominatorTree &DT) {
314 LLVM_DEBUG(dbgs() << "===== Fix irreducible control-flow in function: "
315 << F.getName() << "\n");
316
317 assert(hasOnlySimpleTerminator(F) && "Unsupported block terminator.");
318
319 bool Changed = false;
320 SmallVector<Loop *, 8> WorkList;
321
322 LLVM_DEBUG(dbgs() << "visiting top-level\n");
323 Changed |= makeReducible(LI, DT, G: &F);
324
325 // Any SCCs reduced are now already in the list of top-level loops, so simply
326 // add them all to the worklist.
327 append_range(C&: WorkList, R&: LI);
328
329 while (!WorkList.empty()) {
330 auto L = WorkList.pop_back_val();
331 LLVM_DEBUG(dbgs() << "visiting loop with header "
332 << L->getHeader()->getName() << "\n");
333 Changed |= makeReducible(LI, DT, G&: *L);
334 // Any SCCs reduced are now already in the list of child loops, so simply
335 // add them all to the worklist.
336 WorkList.append(in_start: L->begin(), in_end: L->end());
337 }
338
339 return Changed;
340}
341
342bool FixIrreducible::runOnFunction(Function &F) {
343 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
344 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
345 return FixIrreducibleImpl(F, LI, DT);
346}
347
348PreservedAnalyses FixIrreduciblePass::run(Function &F,
349 FunctionAnalysisManager &AM) {
350 auto &LI = AM.getResult<LoopAnalysis>(IR&: F);
351 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
352 if (!FixIrreducibleImpl(F, LI, DT))
353 return PreservedAnalyses::all();
354 PreservedAnalyses PA;
355 PA.preserve<LoopAnalysis>();
356 PA.preserve<DominatorTreeAnalysis>();
357 return PA;
358}
359