LLVM 17.0.0git
FixIrreducible.cpp
Go to the documentation of this file.
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
74#include "llvm/Pass.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) {
87 }
88
89 void getAnalysisUsage(AnalysisUsage &AU) const override {
96 }
97
98 bool runOnFunction(Function &F) override;
99};
100} // namespace
101
102char FixIrreducible::ID = 0;
103
104FunctionPass *llvm::createFixIrreduciblePass() { return new FixIrreducible(); }
105
106INITIALIZE_PASS_BEGIN(FixIrreducible, "fix-irreducible",
107 "Convert irreducible control-flow into natural loops",
108 false /* Only looks at CFG */, false /* Analysis Pass */)
109INITIALIZE_PASS_DEPENDENCY(LowerSwitchLegacyPass)
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.
118static 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.
168 Loop *ParentLoop,
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
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.
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
247namespace llvm {
248// Enable the graph traits required for traversing a Loop body.
249template <> struct GraphTraits<Loop> : LoopBodyTraits {};
250} // namespace llvm
251
252// Overloaded wrappers to go with the function template below.
253static BasicBlock *unwrapBlock(BasicBlock *B) { return B; }
255
258 SetVector<BasicBlock *> &Headers) {
259 createNaturalLoopInternal(LI, DT, nullptr, Blocks, Headers);
260}
261
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&.
269template <class Graph>
270static 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;
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.
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
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
343bool FixIrreducible::runOnFunction(Function &F) {
344 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
345 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
346 return FixIrreducibleImpl(F, LI, DT);
347}
348
351 auto &LI = AM.getResult<LoopAnalysis>(F);
352 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
353 if (!FixIrreducibleImpl(F, LI, DT))
354 return PreservedAnalyses::all();
358 return PA;
359}
arm execution domain fix
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Function *F, SetVector< BasicBlock * > &Blocks, SetVector< BasicBlock * > &Headers)
static bool FixIrreducibleImpl(Function &F, LoopInfo &LI, DominatorTree &DT)
fix irreducible
fix Convert irreducible control flow into natural static false void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop, SetVector< BasicBlock * > &Blocks, SetVector< BasicBlock * > &Headers)
static BasicBlock * unwrapBlock(BasicBlock *B)
fix Convert irreducible control flow into natural loops
static bool makeReducible(LoopInfo &LI, DominatorTree &DT, Graph &&G)
static void createNaturalLoopInternal(LoopInfo &LI, DominatorTree &DT, Loop *ParentLoop, SetVector< BasicBlock * > &Blocks, SetVector< BasicBlock * > &Headers)
#define F(x, y, z)
Definition: MD5.cpp:55
#define G(x, y, z)
Definition: MD5.cpp:56
#define H(x, y, z)
Definition: MD5.cpp:57
#define P(N)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Represent the analysis usage information of a pass.
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:279
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:314
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:321
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1268
void verifyLoop() const
Verify loop structure.
Definition: LoopInfoImpl.h:302
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:412
LoopT * AllocateLoop(ArgsTy &&... Args)
Definition: LoopInfo.h:956
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:699
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
Definition: LoopInfo.h:1049
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:1005
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:1030
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1293
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
A vector that has set insertion semantics.
Definition: SetVector.h:51
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:88
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:219
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:152
const value_type & front() const
Return the first element of the SetVector.
Definition: SetVector.h:133
bool empty() const
Definition: SmallVector.h:94
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:687
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2129
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:233
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:511
char & LowerSwitchID
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
FunctionPass * createFixIrreduciblePass()
void initializeFixIrreduciblePass(PassRegistry &)
BasicBlock * CreateControlFlowHub(DomTreeUpdater *DTU, SmallVectorImpl< BasicBlock * > &GuardBlocks, const SetVector< BasicBlock * > &Predecessors, const SetVector< BasicBlock * > &Successors, const StringRef Prefix, std::optional< unsigned > MaxControlFlowBooleans=std::nullopt)
Given a set of incoming and outgoing blocks, create a "hub" such that every edge from an incoming blo...
auto predecessors(const MachineBasicBlock *BB)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
#define N
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
std::pair< const Loop *, BasicBlock * > NodeRef
Definition: LoopIterator.h:41