LLVM 19.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 {
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 */)
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,
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 CandidateLoops.begin(), CandidateLoops.end(), [&](Loop *L) {
125 return L == NewLoop || !Blocks.contains(L->getHeader());
126 });
127 SmallVector<Loop *, 8> ChildLoops(FirstChild, CandidateLoops.end());
128 CandidateLoops.erase(FirstChild, 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(Child->getHeader())) {
137 for (auto *BB : Child->blocks()) {
138 if (LI.getLoopFor(BB) != Child)
139 continue;
140 LI.changeLoopFor(BB, NewLoop);
141 LLVM_DEBUG(dbgs() << "moved block from child: " << BB->getName()
142 << "\n");
143 }
144 std::vector<Loop *> GrandChildLoops;
145 std::swap(GrandChildLoops, Child->getSubLoopsVector());
146 for (auto *GrandChildLoop : GrandChildLoops) {
147 GrandChildLoop->setParentLoop(nullptr);
148 NewLoop->addChildLoop(GrandChildLoop);
149 }
150 LI.destroy(Child);
151 LLVM_DEBUG(dbgs() << "subsumed child loop (common header)\n");
152 continue;
153 }
154
155 Child->setParentLoop(nullptr);
156 NewLoop->addChildLoop(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.
165 Loop *ParentLoop,
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(H)) {
178 Predecessors.insert(P);
179 }
180 }
181
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.
193 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
194 CreateControlFlowHub(&DTU, GuardBlocks, Predecessors, Headers, "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(NewLoop);
205 } else {
206 LI.addTopLevelLoop(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(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, 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; }
252
255 SetVector<BasicBlock *> &Headers) {
256 createNaturalLoopInternal(LI, DT, nullptr, Blocks, Headers);
257}
258
261 SetVector<BasicBlock *> &Headers) {
262 createNaturalLoopInternal(LI, DT, &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;
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.
287 LLVM_DEBUG(dbgs() << "Found headers:");
288 for (auto *BB : reverse(Blocks)) {
289 for (const auto P : predecessors(BB)) {
290 // Skip unreachable predecessors.
291 if (!DT.isReachableFromEntry(P))
292 continue;
293 if (!Blocks.count(P)) {
294 LLVM_DEBUG(dbgs() << " " << BB->getName());
295 Headers.insert(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
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, &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(WorkList, 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, *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(L->begin(), 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
350 auto &LI = AM.getResult<LoopAnalysis>(F);
351 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
352 if (!FixIrreducibleImpl(F, LI, DT))
353 return PreservedAnalyses::all();
357 return PA;
358}
arm execution domain fix
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
DenseMap< Block *, BlockRelaxAux > Blocks
Definition: ELF_riscv.cpp:507
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:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
Represent the analysis usage information of a pass.
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:60
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:317
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
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:311
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:566
void verifyLoop() const
Verify loop structure.
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
LoopT * AllocateLoop(ArgsTy &&...Args)
bool isLoopHeader(const BlockT *BB) const
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:593
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
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: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:129
A vector that has set insertion semantics.
Definition: SetVector.h:57
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:98
const value_type & front() const
Return the first element of the SetVector.
Definition: SetVector.h:143
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
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:696
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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
bool hasOnlySimpleTerminator(const Function &F)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2082
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:428
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