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// INPUT CFG: The blocks H and B form an irreducible cycle with two headers.
10//
11// Entry
12// / \
13// v v
14// H ----> B
15// ^ /|
16// `----' |
17// v
18// Exit
19//
20// OUTPUT CFG: Converted to a natural loop with a new header N.
21//
22// Entry
23// |
24// v
25// N <---.
26// / \ \
27// / \ |
28// v v /
29// H --> B --'
30// |
31// v
32// Exit
33//
34// To convert an irreducible cycle C to a natural loop L:
35//
36// 1. Add a new node N to C.
37// 2. Redirect all external incoming edges through N.
38// 3. Redirect all edges incident on header H through N.
39//
40// This is sufficient to ensure that:
41//
42// a. Every closed path in C also exists in L, with the modification that any
43// path passing through H now passes through N before reaching H.
44// b. Every external path incident on any entry of C is now incident on N and
45// then redirected to the entry.
46//
47// Thus, L is a strongly connected component dominated by N, and hence L is a
48// natural loop with header N.
49//
50// When an irreducible cycle C with header H is transformed into a loop, the
51// following invariants hold:
52//
53// 1. No new subcycles are "discovered" in the set (C-H). The only internal
54// edges that are redirected by the transform are incident on H. Any subcycle
55// S in (C-H), already existed prior to this transform, and is already in the
56// list of children for this cycle C.
57//
58// 2. Subcycles of C are not modified by the transform. For some subcycle S of
59// C, edges incident on the entries of S are either internal to C, or they
60// are now redirected through N, which is outside of S. So the list of
61// entries to S does not change. Since the transform only adds a block
62// outside S, and redirects edges that are not internal to S, the list of
63// blocks in S does not change.
64//
65// 3. Similarly, any natural loop L included in C is not affected, with one
66// exception: L is "destroyed" by the transform iff its header is H. The
67// backedges of such a loop are now redirected to N instead, and hence the
68// body of this loop gets merged into the new loop with header N.
69//
70// The actual transformation is handled by the ControlFlowHub, which redirects
71// specified control flow edges through a set of guard blocks. This also moves
72// every PHINode in an outgoing block to the hub. Since the hub dominates all
73// the outgoing blocks, each such PHINode continues to dominate its uses. Since
74// every header in an SCC has at least two predecessors, every value used in the
75// header (or later) but defined in a predecessor (or earlier) is represented by
76// a PHINode in a header. Hence the above handling of PHINodes is sufficient and
77// no further processing is required to restore SSA.
78//
79// Limitation: The pass cannot handle indirect branches. They must be lowered to
80// plain branches first.
81//
82// CallBr and Switch support: CallBr and Switch terminators are handled as a
83// more general branch instruction which can have multiple successors. The pass
84// redirects the edges to intermediate target blocks that unconditionally branch
85// to the original target blocks. This allows the control flow hub to know to
86// which of the original target blocks to jump to. Example input CFG:
87// Entry (callbr/switch)
88// / \
89// v v
90// H ----> B
91// ^ /|
92// `----' |
93// v
94// Exit
95//
96// becomes:
97// Entry (callbr/switch)
98// / \
99// v v
100// target.H target.B
101// | |
102// v v
103// H ----> B
104// ^ /|
105// `----' |
106// v
107// Exit
108//
109// Note
110// OUTPUT CFG: Converted to a natural loop with a new header N.
111//
112// Entry (callbr/switch)
113// / \
114// v v
115// target.H target.B
116// \ /
117// \ /
118// v v
119// N <---.
120// / \ \
121// / \ |
122// v v /
123// H --> B --'
124// |
125// v
126// Exit
127//
128//===----------------------------------------------------------------------===//
129
130#include "llvm/Transforms/Utils/FixIrreducible.h"
131#include "llvm/ADT/DenseMap.h"
132#include "llvm/Analysis/CycleAnalysis.h"
133#include "llvm/Analysis/DomTreeUpdater.h"
134#include "llvm/Analysis/LoopInfo.h"
135#include "llvm/IR/Instructions.h"
136#include "llvm/InitializePasses.h"
137#include "llvm/Pass.h"
138#include "llvm/Support/ErrorHandling.h"
139#include "llvm/Transforms/Utils.h"
140#include "llvm/Transforms/Utils/BasicBlockUtils.h"
141#include "llvm/Transforms/Utils/ControlFlowUtils.h"
142
143#define DEBUG_TYPE "fix-irreducible"
144
145using namespace llvm;
146
147namespace {
148struct FixIrreducible : public FunctionPass {
149 static char ID;
150 FixIrreducible() : FunctionPass(ID) {
151 initializeFixIrreduciblePass(*PassRegistry::getPassRegistry());
152 }
153
154 void getAnalysisUsage(AnalysisUsage &AU) const override {
155 AU.addRequired<DominatorTreeWrapperPass>();
156 AU.addRequired<CycleInfoWrapperPass>();
157 AU.addPreserved<DominatorTreeWrapperPass>();
158 AU.addPreserved<CycleInfoWrapperPass>();
159 AU.addPreserved<LoopInfoWrapperPass>();
160 }
161
162 bool runOnFunction(Function &F) override;
163};
164} // namespace
165
166char FixIrreducible::ID = 0;
167
168FunctionPass *llvm::createFixIrreduciblePass() { return new FixIrreducible(); }
169
170INITIALIZE_PASS_BEGIN(FixIrreducible, "fix-irreducible",
171 "Convert irreducible control-flow into natural loops",
172 false /* Only looks at CFG */, false /* Analysis Pass */)
173INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
174INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
175INITIALIZE_PASS_END(FixIrreducible, "fix-irreducible",
176 "Convert irreducible control-flow into natural loops",
177 false /* Only looks at CFG */, false /* Analysis Pass */)
178
179// When a new loop is created, existing children of the parent loop may now be
180// fully inside the new loop. Reconnect these as children of the new loop.
181static void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop,
182 BasicBlock *OldHeader) {
183 auto &CandidateLoops = ParentLoop ? ParentLoop->getSubLoopsVector()
184 : LI.getTopLevelLoopsVector();
185 // Any candidate is a child iff its header is owned by the new loop. Move all
186 // the children to a new vector.
187 auto FirstChild = llvm::partition(Range&: CandidateLoops, P: [&](Loop *L) {
188 return NewLoop == L || !NewLoop->contains(BB: L->getHeader());
189 });
190 SmallVector<Loop *, 8> ChildLoops(FirstChild, CandidateLoops.end());
191 CandidateLoops.erase(first: FirstChild, last: CandidateLoops.end());
192
193 for (Loop *Child : ChildLoops) {
194 LLVM_DEBUG(dbgs() << "child loop: " << Child->getHeader()->getName()
195 << "\n");
196 // A child loop whose header was the old cycle header gets destroyed since
197 // its backedges are removed.
198 if (Child->getHeader() == OldHeader) {
199 for (auto *BB : Child->blocks()) {
200 if (LI.getLoopFor(BB) != Child)
201 continue;
202 LI.changeLoopFor(BB, L: NewLoop);
203 LLVM_DEBUG(dbgs() << "moved block from child: " << BB->getName()
204 << "\n");
205 }
206 std::vector<Loop *> GrandChildLoops;
207 std::swap(x&: GrandChildLoops, y&: Child->getSubLoopsVector());
208 for (auto *GrandChildLoop : GrandChildLoops) {
209 GrandChildLoop->setParentLoop(nullptr);
210 NewLoop->addChildLoop(NewChild: GrandChildLoop);
211 }
212 LI.destroy(L: Child);
213 LLVM_DEBUG(dbgs() << "subsumed child loop (common header)\n");
214 continue;
215 }
216
217 Child->setParentLoop(nullptr);
218 NewLoop->addChildLoop(NewChild: Child);
219 LLVM_DEBUG(dbgs() << "added child loop to new loop\n");
220 }
221}
222
223static void updateLoopInfo(CycleInfo &CI, LoopInfo &LI, CycleRef C,
224 ArrayRef<BasicBlock *> GuardBlocks) {
225 // The parent loop is a natural loop L mapped to the cycle header H as long as
226 // H is not also the header of L. In the latter case, L is destroyed and we
227 // seek its parent instead.
228 BasicBlock *CycleHeader = CI.getHeader(C);
229 Loop *ParentLoop = LI.getLoopFor(BB: CycleHeader);
230 if (ParentLoop && ParentLoop->getHeader() == CycleHeader)
231 ParentLoop = ParentLoop->getParentLoop();
232
233 // Create a new loop from the now-transformed cycle
234 auto *NewLoop = LI.AllocateLoop();
235 if (ParentLoop) {
236 ParentLoop->addChildLoop(NewChild: NewLoop);
237 } else {
238 LI.addTopLevelLoop(New: NewLoop);
239 }
240
241 // Add the guard blocks to the new loop. The first guard block is
242 // the head of all the backedges, and it is the first to be inserted
243 // in the loop. This ensures that it is recognized as the
244 // header. Since the new loop is already in LoopInfo, the new blocks
245 // are also propagated up the chain of parent loops.
246 for (auto *G : GuardBlocks) {
247 LLVM_DEBUG(dbgs() << "added guard block to loop: " << G->getName() << "\n");
248 NewLoop->addBasicBlockToLoop(NewBB: G, LI);
249 }
250
251 for (auto *BB : CI.getBlocks(C)) {
252 NewLoop->addBlockEntry(BB);
253 if (LI.getLoopFor(BB) == ParentLoop) {
254 LLVM_DEBUG(dbgs() << "moved block from parent: " << BB->getName()
255 << "\n");
256 LI.changeLoopFor(BB, L: NewLoop);
257 } else {
258 LLVM_DEBUG(dbgs() << "added block from child: " << BB->getName() << "\n");
259 }
260 }
261 LLVM_DEBUG(dbgs() << "header for new loop: "
262 << NewLoop->getHeader()->getName() << "\n");
263
264 reconnectChildLoops(LI, ParentLoop, NewLoop, OldHeader: CI.getHeader(C));
265
266 LLVM_DEBUG(dbgs() << "Verify new loop.\n"; NewLoop->print(dbgs()));
267 NewLoop->verifyLoop();
268 if (ParentLoop) {
269 LLVM_DEBUG(dbgs() << "Verify parent loop.\n"; ParentLoop->print(dbgs()));
270 ParentLoop->verifyLoop();
271 }
272}
273
274// Given a set of blocks and headers in an irreducible SCC, convert it into a
275// natural loop. Also insert this new loop at its appropriate place in the
276// hierarchy of loops.
277static bool fixIrreducible(CycleRef C, CycleInfo &CI, DominatorTree &DT,
278 LoopInfo *LI) {
279 if (CI.isReducible(C))
280 return false;
281 LLVM_DEBUG(dbgs() << "Processing cycle:\n" << CI.print(C) << "\n";);
282
283 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
284 ControlFlowHub CHub;
285 SetVector<BasicBlock *> Predecessors;
286
287 // Redirect internal edges incident on the header.
288 BasicBlock *Header = CI.getHeader(C);
289 for (BasicBlock *P : predecessors(BB: Header)) {
290 if (CI.contains(C, Block: P))
291 Predecessors.insert(X: P);
292 }
293
294 for (BasicBlock *P : Predecessors) {
295 Instruction *Term = P->getTerminator();
296 if (isa<UncondBrInst>(Val: Term)) {
297 assert(Term->getSuccessor(0) == Header);
298 CHub.addBranch(BB: P, Succ0: Header);
299
300 LLVM_DEBUG(dbgs() << "Added internal branch: " << printBasicBlock(P)
301 << " -> " << printBasicBlock(Header) << '\n');
302 } else if (CondBrInst *Branch = dyn_cast<CondBrInst>(Val: Term)) {
303 BasicBlock *Succ0 = Branch->getSuccessor(i: 0) == Header ? Header : nullptr;
304 BasicBlock *Succ1 = Branch->getSuccessor(i: 1) == Header ? Header : nullptr;
305 assert(Succ0 || Succ1);
306 CHub.addBranch(BB: P, Succ0, Succ1);
307
308 LLVM_DEBUG(dbgs() << "Added internal branch: " << printBasicBlock(P)
309 << " -> " << printBasicBlock(Succ0)
310 << (Succ0 && Succ1 ? " " : "") << printBasicBlock(Succ1)
311 << '\n');
312 } else if (isa<CallBrInst>(Val: Term) || isa<SwitchInst>(Val: Term)) {
313 BasicBlock *NewSucc = nullptr;
314 for (unsigned I = 0; I < Term->getNumSuccessors(); ++I) {
315 BasicBlock *Succ = Term->getSuccessor(Idx: I);
316 if (Succ != Header)
317 continue;
318 NewSucc = SplitMultiBrEdge(MultiBrBlock: P, Succ, SuccIdx: I, BrTarget: NewSucc, DTU: &DTU, CI: &CI, LI);
319 LLVM_DEBUG(dbgs() << "Added internal branch: "
320 << printBasicBlock(NewSucc) << " -> "
321 << printBasicBlock(Succ) << '\n');
322 }
323 if (NewSucc)
324 CHub.addBranch(BB: NewSucc, Succ0: Header);
325 } else {
326 reportFatalUsageError(
327 reason: "unsupported block terminator: fix-irreducible "
328 "only supports br, callbr, and switch instructions");
329 }
330 }
331
332 // Redirect external incoming edges. This includes the edges on the header.
333 Predecessors.clear();
334 for (BasicBlock *E : CI.getEntries(C)) {
335 for (BasicBlock *P : predecessors(BB: E)) {
336 if (!CI.contains(C, Block: P))
337 Predecessors.insert(X: P);
338 }
339 }
340
341 for (BasicBlock *P : Predecessors) {
342 Instruction *Term = P->getTerminator();
343 if (UncondBrInst *Branch = dyn_cast<UncondBrInst>(Val: Term)) {
344 BasicBlock *Succ0 = Branch->getSuccessor();
345 Succ0 = CI.contains(C, Block: Succ0) ? Succ0 : nullptr;
346 CHub.addBranch(BB: P, Succ0);
347
348 LLVM_DEBUG(dbgs() << "Added external branch: " << printBasicBlock(P)
349 << " -> " << printBasicBlock(Succ0) << '\n');
350 } else if (CondBrInst *Branch = dyn_cast<CondBrInst>(Val: Term)) {
351 BasicBlock *Succ0 = Branch->getSuccessor(i: 0);
352 Succ0 = CI.contains(C, Block: Succ0) ? Succ0 : nullptr;
353 BasicBlock *Succ1 = Branch->getSuccessor(i: 1);
354 Succ1 = CI.contains(C, Block: Succ1) ? Succ1 : nullptr;
355 CHub.addBranch(BB: P, Succ0, Succ1);
356
357 LLVM_DEBUG(dbgs() << "Added external branch: " << printBasicBlock(P)
358 << " -> " << printBasicBlock(Succ0)
359 << (Succ0 && Succ1 ? " " : "") << printBasicBlock(Succ1)
360 << '\n');
361 } else if (isa<CallBrInst>(Val: Term) || isa<SwitchInst>(Val: Term)) {
362 SmallDenseMap<BasicBlock *, BasicBlock *> MultiBrTargets;
363 for (unsigned I = 0; I < Term->getNumSuccessors(); ++I) {
364 BasicBlock *Succ = Term->getSuccessor(Idx: I);
365 if (!CI.contains(C, Block: Succ))
366 continue;
367 auto It = MultiBrTargets.find(Val: Succ);
368 BasicBlock *ExistingTarget =
369 (It != MultiBrTargets.end()) ? It->second : nullptr;
370
371 BasicBlock *NewSucc =
372 SplitMultiBrEdge(MultiBrBlock: P, Succ, SuccIdx: I, BrTarget: ExistingTarget, DTU: &DTU, CI: &CI, LI);
373 if (!ExistingTarget) {
374 CHub.addBranch(BB: NewSucc, Succ0: Succ);
375 MultiBrTargets[Succ] = NewSucc;
376 }
377 LLVM_DEBUG(dbgs() << "Added external branch: "
378 << printBasicBlock(NewSucc) << " -> "
379 << printBasicBlock(Succ) << '\n');
380 }
381 } else {
382 reportFatalUsageError(
383 reason: "unsupported block terminator: fix-irreducible "
384 "only supports br, callbr, and switch instructions");
385 }
386 }
387
388 // Redirect all the backedges through a "hub" consisting of a series
389 // of guard blocks that manage the flow of control from the
390 // predecessors to the headers.
391 SmallVector<BasicBlock *> GuardBlocks;
392
393 // Minor optimization: The cycle entries are discovered in an order that is
394 // the opposite of the order in which these blocks appear as branch targets.
395 // This results in a lot of condition inversions in the control flow out of
396 // the new ControlFlowHub, which can be mitigated if the orders match. So we
397 // reverse the entries when adding them to the hub.
398 SetVector<BasicBlock *> Entries;
399 Entries.insert(Start: CI.getEntries(C).rbegin(), End: CI.getEntries(C).rend());
400
401 CHub.finalize(DTU: &DTU, GuardBlocks, Prefix: "irr");
402#if defined(EXPENSIVE_CHECKS)
403 assert(DT.verify(DominatorTree::VerificationLevel::Full));
404#else
405 assert(DT.verify(DominatorTree::VerificationLevel::Fast));
406#endif
407
408 // If we are updating LoopInfo, do that now before modifying the cycle. This
409 // ensures that the first guard block is the header of a new natural loop.
410 if (LI)
411 updateLoopInfo(CI, LI&: *LI, C, GuardBlocks);
412
413 for (auto *G : GuardBlocks) {
414 LLVM_DEBUG(dbgs() << "added guard block to cycle: " << G->getName()
415 << "\n");
416 CI.addBlockToCycle(Block: G, C);
417 }
418 CI.setSingleEntry(C, Block: GuardBlocks[0]);
419
420 CI.verifyCycle(C);
421 if (CycleRef Parent = CI.getParentCycle(C))
422 CI.verifyCycle(C: Parent);
423
424 LLVM_DEBUG(dbgs() << "Finished one cycle:\n"; CI.print(dbgs()););
425 return true;
426}
427
428static bool FixIrreducibleImpl(Function &F, CycleInfo &CI, DominatorTree &DT,
429 LoopInfo *LI) {
430 LLVM_DEBUG(dbgs() << "===== Fix irreducible control-flow in function: "
431 << F.getName() << "\n");
432
433 bool Changed = false;
434 for (auto C : CI.cycles())
435 Changed |= fixIrreducible(C, CI, DT, LI);
436
437 if (!Changed)
438 return false;
439
440#if defined(EXPENSIVE_CHECKS)
441 CI.verify();
442 if (LI) {
443 LI->verify(DT);
444 }
445#endif // EXPENSIVE_CHECKS
446
447 return true;
448}
449
450bool FixIrreducible::runOnFunction(Function &F) {
451 auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
452 LoopInfo *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
453 auto &CI = getAnalysis<CycleInfoWrapperPass>().getResult();
454 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
455 return FixIrreducibleImpl(F, CI, DT, LI);
456}
457
458PreservedAnalyses FixIrreduciblePass::run(Function &F,
459 FunctionAnalysisManager &AM) {
460 auto *LI = AM.getCachedResult<LoopAnalysis>(IR&: F);
461 auto &CI = AM.getResult<CycleAnalysis>(IR&: F);
462 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
463
464 if (!FixIrreducibleImpl(F, CI, DT, LI))
465 return PreservedAnalyses::all();
466
467 PreservedAnalyses PA;
468 PA.preserve<LoopAnalysis>();
469 PA.preserve<CycleAnalysis>();
470 PA.preserve<DominatorTreeAnalysis>();
471 return PA;
472}
473