LLVM  12.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 
69 #include "llvm/ADT/SCCIterator.h"
71 #include "llvm/InitializePasses.h"
72 #include "llvm/Pass.h"
73 #include "llvm/Transforms/Utils.h"
75 
76 #define DEBUG_TYPE "fix-irreducible"
77 
78 using namespace llvm;
79 
80 namespace {
81 struct FixIrreducible : public FunctionPass {
82  static char ID;
83  FixIrreducible() : FunctionPass(ID) {
85  }
86 
87  void getAnalysisUsage(AnalysisUsage &AU) const override {
94  }
95 
96  bool runOnFunction(Function &F) override;
97 };
98 } // namespace
99 
100 char FixIrreducible::ID = 0;
101 
102 FunctionPass *llvm::createFixIrreduciblePass() { return new FixIrreducible(); }
103 
104 INITIALIZE_PASS_BEGIN(FixIrreducible, "fix-irreducible",
105  "Convert irreducible control-flow into natural loops",
106  false /* Only looks at CFG */, false /* Analysis Pass */)
107 INITIALIZE_PASS_DEPENDENCY(LowerSwitch)
111  "Convert irreducible control-flow into natural loops",
112  false /* Only looks at CFG */, false /* Analysis Pass */)
113 
114 // When a new loop is created, existing children of the parent loop may now be
115 // fully inside the new loop. Reconnect these as children of the new loop.
116 static void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop,
117  SetVector<BasicBlock *> &Blocks,
118  SetVector<BasicBlock *> &Headers) {
119  auto &CandidateLoops = ParentLoop ? ParentLoop->getSubLoopsVector()
120  : LI.getTopLevelLoopsVector();
121  // The new loop cannot be its own child, and any candidate is a
122  // child iff its header is owned by the new loop. Move all the
123  // children to a new vector.
124  auto FirstChild = std::partition(
125  CandidateLoops.begin(), CandidateLoops.end(), [&](Loop *L) {
126  return L == NewLoop || Blocks.count(L->getHeader()) == 0;
127  });
128  SmallVector<Loop *, 8> ChildLoops(FirstChild, CandidateLoops.end());
129  CandidateLoops.erase(FirstChild, CandidateLoops.end());
130 
131  for (auto II = ChildLoops.begin(), IE = ChildLoops.end(); II != IE; ++II) {
132  auto Child = *II;
133  LLVM_DEBUG(dbgs() << "child loop: " << Child->getHeader()->getName()
134  << "\n");
135  // TODO: A child loop whose header is also a header in the current
136  // SCC gets destroyed since its backedges are removed. That may
137  // not be necessary if we can retain such backedges.
138  if (Headers.count(Child->getHeader())) {
139  for (auto BB : Child->blocks()) {
140  LI.changeLoopFor(BB, NewLoop);
141  LLVM_DEBUG(dbgs() << "moved block from child: " << BB->getName()
142  << "\n");
143  }
144  LI.destroy(Child);
145  LLVM_DEBUG(dbgs() << "subsumed child loop (common header)\n");
146  continue;
147  }
148 
149  Child->setParentLoop(nullptr);
150  NewLoop->addChildLoop(Child);
151  LLVM_DEBUG(dbgs() << "added child loop to new loop\n");
152  }
153 }
154 
155 // Given a set of blocks and headers in an irreducible SCC, convert it into a
156 // natural loop. Also insert this new loop at its appropriate place in the
157 // hierarchy of loops.
159  Loop *ParentLoop,
160  SetVector<BasicBlock *> &Blocks,
161  SetVector<BasicBlock *> &Headers) {
162 #ifndef NDEBUG
163  // All headers are part of the SCC
164  for (auto H : Headers) {
165  assert(Blocks.count(H));
166  }
167 #endif
168 
169  SetVector<BasicBlock *> Predecessors;
170  for (auto H : Headers) {
171  for (auto P : predecessors(H)) {
172  Predecessors.insert(P);
173  }
174  }
175 
176  LLVM_DEBUG(
177  dbgs() << "Found predecessors:";
178  for (auto P : Predecessors) {
179  dbgs() << " " << P->getName();
180  }
181  dbgs() << "\n");
182 
183  // Redirect all the backedges through a "hub" consisting of a series
184  // of guard blocks that manage the flow of control from the
185  // predecessors to the headers.
186  SmallVector<BasicBlock *, 8> GuardBlocks;
188  CreateControlFlowHub(&DTU, GuardBlocks, Predecessors, Headers, "irr");
189 #if defined(EXPENSIVE_CHECKS)
191 #else
193 #endif
194 
195  // Create a new loop from the now-transformed cycle
196  auto NewLoop = LI.AllocateLoop();
197  if (ParentLoop) {
198  ParentLoop->addChildLoop(NewLoop);
199  } else {
200  LI.addTopLevelLoop(NewLoop);
201  }
202 
203  // Add the guard blocks to the new loop. The first guard block is
204  // the head of all the backedges, and it is the first to be inserted
205  // in the loop. This ensures that it is recognized as the
206  // header. Since the new loop is already in LoopInfo, the new blocks
207  // are also propagated up the chain of parent loops.
208  for (auto G : GuardBlocks) {
209  LLVM_DEBUG(dbgs() << "added guard block: " << G->getName() << "\n");
210  NewLoop->addBasicBlockToLoop(G, LI);
211  }
212 
213  // Add the SCC blocks to the new loop.
214  for (auto BB : Blocks) {
215  NewLoop->addBlockEntry(BB);
216  if (LI.getLoopFor(BB) == ParentLoop) {
217  LLVM_DEBUG(dbgs() << "moved block from parent: " << BB->getName()
218  << "\n");
219  LI.changeLoopFor(BB, NewLoop);
220  } else {
221  LLVM_DEBUG(dbgs() << "added block from child: " << BB->getName() << "\n");
222  }
223  }
224  LLVM_DEBUG(dbgs() << "header for new loop: "
225  << NewLoop->getHeader()->getName() << "\n");
226 
227  reconnectChildLoops(LI, ParentLoop, NewLoop, Blocks, Headers);
228 
229  NewLoop->verifyLoop();
230  if (ParentLoop) {
231  ParentLoop->verifyLoop();
232  }
233 #if defined(EXPENSIVE_CHECKS)
234  LI.verify(DT);
235 #endif // EXPENSIVE_CHECKS
236 }
237 
238 namespace llvm {
239 // Enable the graph traits required for traversing a Loop body.
240 template <> struct GraphTraits<Loop> : LoopBodyTraits {};
241 } // namespace llvm
242 
243 // Overloaded wrappers to go with the function template below.
244 static BasicBlock *unwrapBlock(BasicBlock *B) { return B; }
245 static BasicBlock *unwrapBlock(LoopBodyTraits::NodeRef &N) { return N.second; }
246 
248  SetVector<BasicBlock *> &Blocks,
249  SetVector<BasicBlock *> &Headers) {
250  createNaturalLoopInternal(LI, DT, nullptr, Blocks, Headers);
251 }
252 
253 static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Loop &L,
254  SetVector<BasicBlock *> &Blocks,
255  SetVector<BasicBlock *> &Headers) {
256  createNaturalLoopInternal(LI, DT, &L, Blocks, Headers);
257 }
258 
259 // Convert irreducible SCCs; Graph G may be a Function* or a Loop&.
260 template <class Graph>
261 static bool makeReducible(LoopInfo &LI, DominatorTree &DT, Graph &&G) {
262  bool Changed = false;
263  for (auto Scc = scc_begin(G); !Scc.isAtEnd(); ++Scc) {
264  if (Scc->size() < 2)
265  continue;
267  LLVM_DEBUG(dbgs() << "Found SCC:");
268  for (auto N : *Scc) {
269  auto BB = unwrapBlock(N);
270  LLVM_DEBUG(dbgs() << " " << BB->getName());
271  Blocks.insert(BB);
272  }
273  LLVM_DEBUG(dbgs() << "\n");
274 
275  // Minor optimization: The SCC blocks are usually discovered in an order
276  // that is the opposite of the order in which these blocks appear as branch
277  // targets. This results in a lot of condition inversions in the control
278  // flow out of the new ControlFlowHub, which can be mitigated if the orders
279  // match. So we discover the headers using the reverse of the block order.
280  SetVector<BasicBlock *> Headers;
281  LLVM_DEBUG(dbgs() << "Found headers:");
282  for (auto BB : reverse(Blocks)) {
283  for (const auto P : predecessors(BB)) {
284  // Skip unreachable predecessors.
285  if (!DT.isReachableFromEntry(P))
286  continue;
287  if (!Blocks.count(P)) {
288  LLVM_DEBUG(dbgs() << " " << BB->getName());
289  Headers.insert(BB);
290  break;
291  }
292  }
293  }
294  LLVM_DEBUG(dbgs() << "\n");
295 
296  if (Headers.size() == 1) {
297  assert(LI.isLoopHeader(Headers.front()));
298  LLVM_DEBUG(dbgs() << "Natural loop with a single header: skipped\n");
299  continue;
300  }
301  createNaturalLoop(LI, DT, G, Blocks, Headers);
302  Changed = true;
303  }
304  return Changed;
305 }
306 
308  LLVM_DEBUG(dbgs() << "===== Fix irreducible control-flow in function: "
309  << F.getName() << "\n");
310  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
311  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
312 
313  bool Changed = false;
314  SmallVector<Loop *, 8> WorkList;
315 
316  LLVM_DEBUG(dbgs() << "visiting top-level\n");
317  Changed |= makeReducible(LI, DT, &F);
318 
319  // Any SCCs reduced are now already in the list of top-level loops, so simply
320  // add them all to the worklist.
321  for (auto L : LI) {
322  WorkList.push_back(L);
323  }
324 
325  while (!WorkList.empty()) {
326  auto L = WorkList.back();
327  WorkList.pop_back();
328  LLVM_DEBUG(dbgs() << "visiting loop with header "
329  << L->getHeader()->getName() << "\n");
330  Changed |= makeReducible(LI, DT, *L);
331  // Any SCCs reduced are now already in the list of child loops, so simply
332  // add them all to the worklist.
333  WorkList.append(L->begin(), L->end());
334  }
335 
336  return Changed;
337 }
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
const T & front() const
Return the first element of the SetVector.
Definition: SetVector.h:122
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void initializeFixIrreduciblePass(PassRegistry &)
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:69
void push_back(const T &Elt)
Definition: SmallVector.h:246
F(f)
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:304
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:680
AnalysisUsage & addRequired()
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:947
static BasicBlock * unwrapBlock(BasicBlock *B)
fix Convert irreducible control flow into natural loops
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:228
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
Definition: LoopInfo.h:1004
AnalysisUsage & addPreservedID(const void *ID)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:210
static void createNaturalLoopInternal(LoopInfo &LI, DominatorTree &DT, Loop *ParentLoop, SetVector< BasicBlock *> &Blocks, SetVector< BasicBlock *> &Headers)
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
std::pair< const Loop *, BasicBlock * > NodeRef
Definition: LoopIterator.h:41
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
#define H(x, y, z)
Definition: MD5.cpp:58
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
char & LowerSwitchID
iterator erase(const_iterator CI)
Definition: SmallVector.h:480
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
arm execution domain fix
BasicBlock * CreateControlFlowHub(DomTreeUpdater *DTU, SmallVectorImpl< BasicBlock *> &GuardBlocks, const SetVector< BasicBlock *> &Predecessors, const SetVector< BasicBlock *> &Successors, const StringRef Prefix)
Given a set of incoming and outgoing blocks, create a "hub" such that every edge from an incoming blo...
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:266
fix Convert irreducible control flow into natural static false void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop, SetVector< BasicBlock *> &Blocks, SetVector< BasicBlock *> &Headers)
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
LoopT * AllocateLoop(ArgsTy &&... Args)
Definition: LoopInfo.h:911
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:125
fix irreducible
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:960
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:433
FunctionPass * createFixIrreduciblePass()
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:382
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:516
static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Function *F, SetVector< BasicBlock *> &Blocks, SetVector< BasicBlock *> &Headers)
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:270
#define N
INITIALIZE_PASS_BEGIN(FixIrreducible, "fix-irreducible", "Convert irreducible control-flow into natural loops", false, false) INITIALIZE_PASS_END(FixIrreducible
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:985
auto partition(R &&Range, UnaryPredicate P)
Provide wrappers to std::partition which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1588
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A vector that has set insertion semantics.
Definition: SetVector.h:40
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:1233
void verifyLoop() const
Verify loop structure.
Definition: LoopInfoImpl.h:278
static bool makeReducible(LoopInfo &LI, DominatorTree &DT, Graph &&G)
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:262
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:341
#define LLVM_DEBUG(X)
Definition: Debug.h:122
Fast - This calling convention attempts to make calls as fast as possible (e.g.
Definition: CallingConv.h:42
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)