CFG.cpp revision 263508 
1//===-- CFG.cpp - BasicBlock analysis --------------------------------------==//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This family of functions performs analyses on basic blocks, and instructions
11// contained within basic blocks.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Analysis/CFG.h"
16
17#include "llvm/ADT/SmallSet.h"
18#include "llvm/Analysis/Dominators.h"
19#include "llvm/Analysis/LoopInfo.h"
20
21using namespace llvm;
22
23/// FindFunctionBackedges - Analyze the specified function to find all of the
24/// loop backedges in the function and return them.  This is a relatively cheap
25/// (compared to computing dominators and loop info) analysis.
26///
27/// The output is added to Result, as pairs of <from,to> edge info.
28void llvm::FindFunctionBackedges(const Function &F,
29     SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) {
30  const BasicBlock *BB = &F.getEntryBlock();
31  if (succ_begin(BB) == succ_end(BB))
32    return;
33
34  SmallPtrSet<const BasicBlock*, 8> Visited;
35  SmallVector<std::pair<const BasicBlock*, succ_const_iterator>, 8> VisitStack;
36  SmallPtrSet<const BasicBlock*, 8> InStack;
37
38  Visited.insert(BB);
39  VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
40  InStack.insert(BB);
41  do {
42    std::pair<const BasicBlock*, succ_const_iterator> &Top = VisitStack.back();
43    const BasicBlock *ParentBB = Top.first;
44    succ_const_iterator &I = Top.second;
45
46    bool FoundNew = false;
47    while (I != succ_end(ParentBB)) {
48      BB = *I++;
49      if (Visited.insert(BB)) {
50        FoundNew = true;
51        break;
52      }
53      // Successor is in VisitStack, it's a back edge.
54      if (InStack.count(BB))
55        Result.push_back(std::make_pair(ParentBB, BB));
56    }
57
58    if (FoundNew) {
59      // Go down one level if there is a unvisited successor.
60      InStack.insert(BB);
61      VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
62    } else {
63      // Go up one level.
64      InStack.erase(VisitStack.pop_back_val().first);
65    }
66  } while (!VisitStack.empty());
67}
68
69/// GetSuccessorNumber - Search for the specified successor of basic block BB
70/// and return its position in the terminator instruction's list of
71/// successors.  It is an error to call this with a block that is not a
72/// successor.
73unsigned llvm::GetSuccessorNumber(BasicBlock *BB, BasicBlock *Succ) {
74  TerminatorInst *Term = BB->getTerminator();
75#ifndef NDEBUG
76  unsigned e = Term->getNumSuccessors();
77#endif
78  for (unsigned i = 0; ; ++i) {
79    assert(i != e && "Didn't find edge?");
80    if (Term->getSuccessor(i) == Succ)
81      return i;
82  }
83}
84
85/// isCriticalEdge - Return true if the specified edge is a critical edge.
86/// Critical edges are edges from a block with multiple successors to a block
87/// with multiple predecessors.
88bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
89                          bool AllowIdenticalEdges) {
90  assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!");
91  if (TI->getNumSuccessors() == 1) return false;
92
93  const BasicBlock *Dest = TI->getSuccessor(SuccNum);
94  const_pred_iterator I = pred_begin(Dest), E = pred_end(Dest);
95
96  // If there is more than one predecessor, this is a critical edge...
97  assert(I != E && "No preds, but we have an edge to the block?");
98  const BasicBlock *FirstPred = *I;
99  ++I;        // Skip one edge due to the incoming arc from TI.
100  if (!AllowIdenticalEdges)
101    return I != E;
102
103  // If AllowIdenticalEdges is true, then we allow this edge to be considered
104  // non-critical iff all preds come from TI's block.
105  while (I != E) {
106    const BasicBlock *P = *I;
107    if (P != FirstPred)
108      return true;
109    // Note: leave this as is until no one ever compiles with either gcc 4.0.1
110    // or Xcode 2. This seems to work around the pred_iterator assert in PR 2207
111    E = pred_end(P);
112    ++I;
113  }
114  return false;
115}
116
117// LoopInfo contains a mapping from basic block to the innermost loop. Find
118// the outermost loop in the loop nest that contains BB.
119static const Loop *getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB) {
120  const Loop *L = LI->getLoopFor(BB);
121  if (L) {
122    while (const Loop *Parent = L->getParentLoop())
123      L = Parent;
124  }
125  return L;
126}
127
128// True if there is a loop which contains both BB1 and BB2.
129static bool loopContainsBoth(const LoopInfo *LI,
130                             const BasicBlock *BB1, const BasicBlock *BB2) {
131  const Loop *L1 = getOutermostLoop(LI, BB1);
132  const Loop *L2 = getOutermostLoop(LI, BB2);
133  return L1 != NULL && L1 == L2;
134}
135
136static bool isPotentiallyReachableInner(SmallVectorImpl<BasicBlock *> &Worklist,
137                                        BasicBlock *StopBB,
138                                        const DominatorTree *DT,
139                                        const LoopInfo *LI) {
140  // When the stop block is unreachable, it's dominated from everywhere,
141  // regardless of whether there's a path between the two blocks.
142  if (DT && !DT->isReachableFromEntry(StopBB))
143    DT = 0;
144
145  // Limit the number of blocks we visit. The goal is to avoid run-away compile
146  // times on large CFGs without hampering sensible code. Arbitrarily chosen.
147  unsigned Limit = 32;
148  SmallSet<const BasicBlock*, 64> Visited;
149  do {
150    BasicBlock *BB = Worklist.pop_back_val();
151    if (!Visited.insert(BB))
152      continue;
153    if (BB == StopBB)
154      return true;
155    if (DT && DT->dominates(BB, StopBB))
156      return true;
157    if (LI && loopContainsBoth(LI, BB, StopBB))
158      return true;
159
160    if (!--Limit) {
161      // We haven't been able to prove it one way or the other. Conservatively
162      // answer true -- that there is potentially a path.
163      return true;
164    }
165
166    if (const Loop *Outer = LI ? getOutermostLoop(LI, BB) : 0) {
167      // All blocks in a single loop are reachable from all other blocks. From
168      // any of these blocks, we can skip directly to the exits of the loop,
169      // ignoring any other blocks inside the loop body.
170      Outer->getExitBlocks(Worklist);
171    } else {
172      for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
173        Worklist.push_back(*I);
174    }
175  } while (!Worklist.empty());
176
177  // We have exhausted all possible paths and are certain that 'To' can not be
178  // reached from 'From'.
179  return false;
180}
181
182bool llvm::isPotentiallyReachable(const BasicBlock *A, const BasicBlock *B,
183                                  const DominatorTree *DT, const LoopInfo *LI) {
184  assert(A->getParent() == B->getParent() &&
185         "This analysis is function-local!");
186
187  SmallVector<BasicBlock*, 32> Worklist;
188  Worklist.push_back(const_cast<BasicBlock*>(A));
189
190  return isPotentiallyReachableInner(Worklist, const_cast<BasicBlock*>(B),
191                                     DT, LI);
192}
193
194bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B,
195                                  const DominatorTree *DT, const LoopInfo *LI) {
196  assert(A->getParent()->getParent() == B->getParent()->getParent() &&
197         "This analysis is function-local!");
198
199  SmallVector<BasicBlock*, 32> Worklist;
200
201  if (A->getParent() == B->getParent()) {
202    // The same block case is special because it's the only time we're looking
203    // within a single block to see which instruction comes first. Once we
204    // start looking at multiple blocks, the first instruction of the block is
205    // reachable, so we only need to determine reachability between whole
206    // blocks.
207    BasicBlock *BB = const_cast<BasicBlock *>(A->getParent());
208
209    // If the block is in a loop then we can reach any instruction in the block
210    // from any other instruction in the block by going around a backedge.
211    if (LI && LI->getLoopFor(BB) != 0)
212      return true;
213
214    // Linear scan, start at 'A', see whether we hit 'B' or the end first.
215    for (BasicBlock::const_iterator I = A, E = BB->end(); I != E; ++I) {
216      if (&*I == B)
217        return true;
218    }
219
220    // Can't be in a loop if it's the entry block -- the entry block may not
221    // have predecessors.
222    if (BB == &BB->getParent()->getEntryBlock())
223      return false;
224
225    // Otherwise, continue doing the normal per-BB CFG walk.
226    for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
227      Worklist.push_back(*I);
228
229    if (Worklist.empty()) {
230      // We've proven that there's no path!
231      return false;
232    }
233  } else {
234    Worklist.push_back(const_cast<BasicBlock*>(A->getParent()));
235  }
236
237  if (A->getParent() == &A->getParent()->getParent()->getEntryBlock())
238    return true;
239  if (B->getParent() == &A->getParent()->getParent()->getEntryBlock())
240    return false;
241
242  return isPotentiallyReachableInner(Worklist,
243                                     const_cast<BasicBlock*>(B->getParent()),
244                                     DT, LI);
245}
246