LLVM  15.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  return L ? L->getOutermostLoop() : nullptr;
131 }
132 
134  SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
135  const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
136  const LoopInfo *LI) {
137  // When the stop block is unreachable, it's dominated from everywhere,
138  // regardless of whether there's a path between the two blocks.
139  if (DT && !DT->isReachableFromEntry(StopBB))
140  DT = nullptr;
141 
142  // We can't skip directly from a block that dominates the stop block if the
143  // exclusion block is potentially in between.
144  if (ExclusionSet && !ExclusionSet->empty())
145  DT = nullptr;
146 
147  // Normally any block in a loop is reachable from any other block in a loop,
148  // however excluded blocks might partition the body of a loop to make that
149  // untrue.
150  SmallPtrSet<const Loop *, 8> LoopsWithHoles;
151  if (LI && ExclusionSet) {
152  for (auto BB : *ExclusionSet) {
153  if (const Loop *L = getOutermostLoop(LI, BB))
154  LoopsWithHoles.insert(L);
155  }
156  }
157 
158  const Loop *StopLoop = LI ? getOutermostLoop(LI, StopBB) : nullptr;
159 
160  unsigned Limit = DefaultMaxBBsToExplore;
162  do {
163  BasicBlock *BB = Worklist.pop_back_val();
164  if (!Visited.insert(BB).second)
165  continue;
166  if (BB == StopBB)
167  return true;
168  if (ExclusionSet && ExclusionSet->count(BB))
169  continue;
170  if (DT && DT->dominates(BB, StopBB))
171  return true;
172 
173  const Loop *Outer = nullptr;
174  if (LI) {
175  Outer = getOutermostLoop(LI, BB);
176  // If we're in a loop with a hole, not all blocks in the loop are
177  // reachable from all other blocks. That implies we can't simply jump to
178  // the loop's exit blocks, as that exit might need to pass through an
179  // excluded block. Clear Outer so we process BB's successors.
180  if (LoopsWithHoles.count(Outer))
181  Outer = nullptr;
182  if (StopLoop && Outer == StopLoop)
183  return true;
184  }
185 
186  if (!--Limit) {
187  // We haven't been able to prove it one way or the other. Conservatively
188  // answer true -- that there is potentially a path.
189  return true;
190  }
191 
192  if (Outer) {
193  // All blocks in a single loop are reachable from all other blocks. From
194  // any of these blocks, we can skip directly to the exits of the loop,
195  // ignoring any other blocks inside the loop body.
196  Outer->getExitBlocks(Worklist);
197  } else {
198  Worklist.append(succ_begin(BB), succ_end(BB));
199  }
200  } while (!Worklist.empty());
201 
202  // We have exhausted all possible paths and are certain that 'To' can not be
203  // reached from 'From'.
204  return false;
205 }
206 
208  const BasicBlock *A, const BasicBlock *B,
209  const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
210  const LoopInfo *LI) {
211  assert(A->getParent() == B->getParent() &&
212  "This analysis is function-local!");
213 
214  if (DT) {
215  if (DT->isReachableFromEntry(A) && !DT->isReachableFromEntry(B))
216  return false;
217  if (!ExclusionSet || ExclusionSet->empty()) {
218  if (A->isEntryBlock() && DT->isReachableFromEntry(B))
219  return true;
220  if (B->isEntryBlock() && DT->isReachableFromEntry(A))
221  return false;
222  }
223  }
224 
226  Worklist.push_back(const_cast<BasicBlock*>(A));
227 
228  return isPotentiallyReachableFromMany(Worklist, const_cast<BasicBlock *>(B),
229  ExclusionSet, DT, LI);
230 }
231 
233  const Instruction *A, const Instruction *B,
234  const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
235  const LoopInfo *LI) {
236  assert(A->getParent()->getParent() == B->getParent()->getParent() &&
237  "This analysis is function-local!");
238 
239  if (A->getParent() == B->getParent()) {
240  // The same block case is special because it's the only time we're looking
241  // within a single block to see which instruction comes first. Once we
242  // start looking at multiple blocks, the first instruction of the block is
243  // reachable, so we only need to determine reachability between whole
244  // blocks.
245  BasicBlock *BB = const_cast<BasicBlock *>(A->getParent());
246 
247  // If the block is in a loop then we can reach any instruction in the block
248  // from any other instruction in the block by going around a backedge.
249  if (LI && LI->getLoopFor(BB) != nullptr)
250  return true;
251 
252  // If A comes before B, then B is definitively reachable from A.
253  if (A == B || A->comesBefore(B))
254  return true;
255 
256  // Can't be in a loop if it's the entry block -- the entry block may not
257  // have predecessors.
258  if (BB->isEntryBlock())
259  return false;
260 
261  // Otherwise, continue doing the normal per-BB CFG walk.
263  Worklist.append(succ_begin(BB), succ_end(BB));
264  if (Worklist.empty()) {
265  // We've proven that there's no path!
266  return false;
267  }
268 
270  Worklist, const_cast<BasicBlock *>(B->getParent()), ExclusionSet,
271  DT, LI);
272  }
273 
274  return isPotentiallyReachable(
275  A->getParent(), B->getParent(), ExclusionSet, DT, LI);
276 }
llvm::SuccIterator
Definition: CFG.h:138
i
i
Definition: README.txt:29
llvm::Instruction::isTerminator
bool isTerminator() const
Definition: Instruction.h:160
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:379
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:133
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::LoopBase::getOutermostLoop
const LoopT * getOutermostLoop() const
Get the outermost loop in which this loop is contained.
Definition: LoopInfo.h:117
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
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:1185
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:166
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
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:654
llvm::succ_empty
bool succ_empty(const Instruction *I)
Definition: CFG.h:255
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
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:122
CommandLine.h
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:777
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:667
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:232
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction
Definition: Instruction.h:42
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:789
LoopInfo.h
llvm::cl::opt
Definition: CommandLine.h:1392
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:986
I
#define I(x, y, z)
Definition: MD5.cpp:58
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::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
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:1682
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:335
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:383
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:1102
llvm::PredIterator
Definition: CFG.h:42
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:92
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
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:405
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:365