LLVM  16.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, const 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, B, ExclusionSet, DT, LI);
229 }
230 
232  const Instruction *A, const Instruction *B,
233  const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
234  const LoopInfo *LI) {
235  assert(A->getParent()->getParent() == B->getParent()->getParent() &&
236  "This analysis is function-local!");
237 
238  if (A->getParent() == B->getParent()) {
239  // The same block case is special because it's the only time we're looking
240  // within a single block to see which instruction comes first. Once we
241  // start looking at multiple blocks, the first instruction of the block is
242  // reachable, so we only need to determine reachability between whole
243  // blocks.
244  BasicBlock *BB = const_cast<BasicBlock *>(A->getParent());
245 
246  // If the block is in a loop then we can reach any instruction in the block
247  // from any other instruction in the block by going around a backedge.
248  if (LI && LI->getLoopFor(BB) != nullptr)
249  return true;
250 
251  // If A comes before B, then B is definitively reachable from A.
252  if (A == B || A->comesBefore(B))
253  return true;
254 
255  // Can't be in a loop if it's the entry block -- the entry block may not
256  // have predecessors.
257  if (BB->isEntryBlock())
258  return false;
259 
260  // Otherwise, continue doing the normal per-BB CFG walk.
262  Worklist.append(succ_begin(BB), succ_end(BB));
263  if (Worklist.empty()) {
264  // We've proven that there's no path!
265  return false;
266  }
267 
268  return isPotentiallyReachableFromMany(Worklist, B->getParent(),
269  ExclusionSet, DT, LI);
270  }
271 
272  return isPotentiallyReachable(
273  A->getParent(), B->getParent(), ExclusionSet, DT, LI);
274 }
llvm::SuccIterator
Definition: CFG.h:138
i
i
Definition: README.txt:29
llvm::Instruction::isTerminator
bool isTerminator() const
Definition: Instruction.h:172
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
Definition: Instruction.cpp:810
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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::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:118
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:547
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:1199
llvm::isPotentiallyReachableFromMany
bool isPotentiallyReachableFromMany(SmallVectorImpl< BasicBlock * > &Worklist, const 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
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::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
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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:231
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::SmallVectorImpl::append
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:687
LoopInfo.h
llvm::SmallPtrSetImplBase::empty
bool empty() const
Definition: SmallPtrSet.h:92
llvm::cl::opt
Definition: CommandLine.h:1411
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:822
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
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::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:446
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:1868
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:1108
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::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
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:412
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
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