LLVM  14.0.0git
CFG.cpp
Go to the documentation of this file.
1 //===-- CFG.cpp - BasicBlock analysis --------------------------------------==//
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 // This family of functions performs analyses on basic blocks, and instructions
10 // contained within basic blocks.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/Analysis/CFG.h"
15 #include "llvm/Analysis/LoopInfo.h"
16 #include "llvm/IR/Dominators.h"
18 
19 using namespace llvm;
20 
21 // The max number of basic blocks explored during reachability analysis between
22 // two basic blocks. This is kept reasonably small to limit compile time when
23 // repeatedly used by clients of this analysis (such as captureTracking).
25  "dom-tree-reachability-max-bbs-to-explore", cl::Hidden,
26  cl::desc("Max number of BBs to explore for reachability analysis"),
27  cl::init(32));
28 
29 /// FindFunctionBackedges - Analyze the specified function to find all of the
30 /// loop backedges in the function and return them. This is a relatively cheap
31 /// (compared to computing dominators and loop info) analysis.
32 ///
33 /// The output is added to Result, as pairs of <from,to> edge info.
35  SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) {
36  const BasicBlock *BB = &F.getEntryBlock();
37  if (succ_empty(BB))
38  return;
39 
43 
44  Visited.insert(BB);
45  VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
46  InStack.insert(BB);
47  do {
48  std::pair<const BasicBlock *, const_succ_iterator> &Top = VisitStack.back();
49  const BasicBlock *ParentBB = Top.first;
50  const_succ_iterator &I = Top.second;
51 
52  bool FoundNew = false;
53  while (I != succ_end(ParentBB)) {
54  BB = *I++;
55  if (Visited.insert(BB).second) {
56  FoundNew = true;
57  break;
58  }
59  // Successor is in VisitStack, it's a back edge.
60  if (InStack.count(BB))
61  Result.push_back(std::make_pair(ParentBB, BB));
62  }
63 
64  if (FoundNew) {
65  // Go down one level if there is a unvisited successor.
66  InStack.insert(BB);
67  VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
68  } else {
69  // Go up one level.
70  InStack.erase(VisitStack.pop_back_val().first);
71  }
72  } while (!VisitStack.empty());
73 }
74 
75 /// GetSuccessorNumber - Search for the specified successor of basic block BB
76 /// and return its position in the terminator instruction's list of
77 /// successors. It is an error to call this with a block that is not a
78 /// successor.
80  const BasicBlock *Succ) {
81  const Instruction *Term = BB->getTerminator();
82 #ifndef NDEBUG
83  unsigned e = Term->getNumSuccessors();
84 #endif
85  for (unsigned i = 0; ; ++i) {
86  assert(i != e && "Didn't find edge?");
87  if (Term->getSuccessor(i) == Succ)
88  return i;
89  }
90 }
91 
92 /// isCriticalEdge - Return true if the specified edge is a critical edge.
93 /// Critical edges are edges from a block with multiple successors to a block
94 /// with multiple predecessors.
95 bool llvm::isCriticalEdge(const Instruction *TI, unsigned SuccNum,
96  bool AllowIdenticalEdges) {
97  assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!");
98  return isCriticalEdge(TI, TI->getSuccessor(SuccNum), AllowIdenticalEdges);
99 }
100 
101 bool llvm::isCriticalEdge(const Instruction *TI, const BasicBlock *Dest,
102  bool AllowIdenticalEdges) {
103  assert(TI->isTerminator() && "Must be a terminator to have successors!");
104  if (TI->getNumSuccessors() == 1) return false;
105 
106  assert(is_contained(predecessors(Dest), TI->getParent()) &&
107  "No edge between TI's block and Dest.");
108 
109  const_pred_iterator I = pred_begin(Dest), E = pred_end(Dest);
110 
111  // If there is more than one predecessor, this is a critical edge...
112  assert(I != E && "No preds, but we have an edge to the block?");
113  const BasicBlock *FirstPred = *I;
114  ++I; // Skip one edge due to the incoming arc from TI.
115  if (!AllowIdenticalEdges)
116  return I != E;
117 
118  // If AllowIdenticalEdges is true, then we allow this edge to be considered
119  // non-critical iff all preds come from TI's block.
120  for (; I != E; ++I)
121  if (*I != FirstPred)
122  return true;
123  return false;
124 }
125 
126 // LoopInfo contains a mapping from basic block to the innermost loop. Find
127 // the outermost loop in the loop nest that contains BB.
128 static const Loop *getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB) {
129  const Loop *L = LI->getLoopFor(BB);
130  if (L) {
131  while (const Loop *Parent = L->getParentLoop())
132  L = Parent;
133  }
134  return L;
135 }
136 
138  SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
139  const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
140  const LoopInfo *LI) {
141  // When the stop block is unreachable, it's dominated from everywhere,
142  // regardless of whether there's a path between the two blocks.
143  if (DT && !DT->isReachableFromEntry(StopBB))
144  DT = nullptr;
145 
146  // We can't skip directly from a block that dominates the stop block if the
147  // exclusion block is potentially in between.
148  if (ExclusionSet && !ExclusionSet->empty())
149  DT = nullptr;
150 
151  // Normally any block in a loop is reachable from any other block in a loop,
152  // however excluded blocks might partition the body of a loop to make that
153  // untrue.
154  SmallPtrSet<const Loop *, 8> LoopsWithHoles;
155  if (LI && ExclusionSet) {
156  for (auto BB : *ExclusionSet) {
157  if (const Loop *L = getOutermostLoop(LI, BB))
158  LoopsWithHoles.insert(L);
159  }
160  }
161 
162  const Loop *StopLoop = LI ? getOutermostLoop(LI, StopBB) : nullptr;
163 
164  unsigned Limit = DefaultMaxBBsToExplore;
166  do {
167  BasicBlock *BB = Worklist.pop_back_val();
168  if (!Visited.insert(BB).second)
169  continue;
170  if (BB == StopBB)
171  return true;
172  if (ExclusionSet && ExclusionSet->count(BB))
173  continue;
174  if (DT && DT->dominates(BB, StopBB))
175  return true;
176 
177  const Loop *Outer = nullptr;
178  if (LI) {
179  Outer = getOutermostLoop(LI, BB);
180  // If we're in a loop with a hole, not all blocks in the loop are
181  // reachable from all other blocks. That implies we can't simply jump to
182  // the loop's exit blocks, as that exit might need to pass through an
183  // excluded block. Clear Outer so we process BB's successors.
184  if (LoopsWithHoles.count(Outer))
185  Outer = nullptr;
186  if (StopLoop && Outer == StopLoop)
187  return true;
188  }
189 
190  if (!--Limit) {
191  // We haven't been able to prove it one way or the other. Conservatively
192  // answer true -- that there is potentially a path.
193  return true;
194  }
195 
196  if (Outer) {
197  // All blocks in a single loop are reachable from all other blocks. From
198  // any of these blocks, we can skip directly to the exits of the loop,
199  // ignoring any other blocks inside the loop body.
200  Outer->getExitBlocks(Worklist);
201  } else {
202  Worklist.append(succ_begin(BB), succ_end(BB));
203  }
204  } while (!Worklist.empty());
205 
206  // We have exhausted all possible paths and are certain that 'To' can not be
207  // reached from 'From'.
208  return false;
209 }
210 
212  const BasicBlock *A, const BasicBlock *B,
213  const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
214  const LoopInfo *LI) {
215  assert(A->getParent() == B->getParent() &&
216  "This analysis is function-local!");
217 
218  if (DT) {
219  if (DT->isReachableFromEntry(A) && !DT->isReachableFromEntry(B))
220  return false;
221  if (!ExclusionSet || ExclusionSet->empty()) {
222  if (A->isEntryBlock() && DT->isReachableFromEntry(B))
223  return true;
224  if (B->isEntryBlock() && DT->isReachableFromEntry(A))
225  return false;
226  }
227  }
228 
230  Worklist.push_back(const_cast<BasicBlock*>(A));
231 
232  return isPotentiallyReachableFromMany(Worklist, const_cast<BasicBlock *>(B),
233  ExclusionSet, DT, LI);
234 }
235 
237  const Instruction *A, const Instruction *B,
238  const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
239  const LoopInfo *LI) {
240  assert(A->getParent()->getParent() == B->getParent()->getParent() &&
241  "This analysis is function-local!");
242 
243  if (A->getParent() == B->getParent()) {
244  // The same block case is special because it's the only time we're looking
245  // within a single block to see which instruction comes first. Once we
246  // start looking at multiple blocks, the first instruction of the block is
247  // reachable, so we only need to determine reachability between whole
248  // blocks.
249  BasicBlock *BB = const_cast<BasicBlock *>(A->getParent());
250 
251  // If the block is in a loop then we can reach any instruction in the block
252  // from any other instruction in the block by going around a backedge.
253  if (LI && LI->getLoopFor(BB) != nullptr)
254  return true;
255 
256  // If A comes before B, then B is definitively reachable from A.
257  if (A == B || A->comesBefore(B))
258  return true;
259 
260  // Can't be in a loop if it's the entry block -- the entry block may not
261  // have predecessors.
262  if (BB->isEntryBlock())
263  return false;
264 
265  // Otherwise, continue doing the normal per-BB CFG walk.
267  Worklist.append(succ_begin(BB), succ_end(BB));
268  if (Worklist.empty()) {
269  // We've proven that there's no path!
270  return false;
271  }
272 
274  Worklist, const_cast<BasicBlock *>(B->getParent()), ExclusionSet,
275  DT, LI);
276  }
277 
278  return isPotentiallyReachable(
279  A->getParent(), B->getParent(), ExclusionSet, DT, LI);
280 }
llvm::SuccIterator
Definition: CFG.h:139
i
i
Definition: README.txt:29
llvm::Instruction::isTerminator
bool isTerminator() const
Definition: Instruction.h:163
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::SmallPtrSetImpl::erase
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:378
llvm::isPotentiallyReachableFromMany
bool isPotentiallyReachableFromMany(SmallVectorImpl< BasicBlock * > &Worklist, BasicBlock *StopBB, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether there is at least one path from a block in 'Worklist' to 'StopBB' without passing t...
Definition: CFG.cpp:137
llvm::FindFunctionBackedges
void FindFunctionBackedges(const Function &F, SmallVectorImpl< std::pair< const BasicBlock *, const BasicBlock * > > &Result)
Analyze the specified function to find all of the loop backedges in the function and return them.
Definition: CFG.cpp:34
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::Function
Definition: Function.h:61
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
DefaultMaxBBsToExplore
static cl::opt< unsigned > DefaultMaxBBsToExplore("dom-tree-reachability-max-bbs-to-explore", cl::Hidden, cl::desc("Max number of BBs to explore for reachability analysis"), cl::init(32))
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
getOutermostLoop
static const Loop * getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB)
Definition: CFG.cpp:128
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::SmallPtrSet< const BasicBlock *, 8 >
llvm::isCriticalEdge
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:95
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::succ_empty
bool succ_empty(const Instruction *I)
Definition: CFG.h:256
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:115
CommandLine.h
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:765
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:648
llvm::isPotentiallyReachable
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
Definition: CFG.cpp:236
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction
Definition: Instruction.h:45
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:777
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
LoopInfo.h
llvm::cl::opt
Definition: CommandLine.h:1434
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:967
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::succ_begin
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1616
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:328
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::GetSuccessorNumber
unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ)
Search for the specified successor of basic block BB and return its position in the terminator instru...
Definition: CFG.cpp:79
CFG.h
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::PredIterator
Definition: CFG.h:43
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::pred_begin
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
Dominators.h
llvm::SmallPtrSetImplBase::empty
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::cl::desc
Definition: CommandLine.h:414
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364