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