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