Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Analysis/CFG.cpp
Line
Count
Source (jump to first uncovered line)
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
20
using 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.
27
void llvm::FindFunctionBackedges(const Function &F,
28
5.76M
     SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) {
29
5.76M
  const BasicBlock *BB = &F.getEntryBlock();
30
5.76M
  if (succ_empty(BB))
31
3.29M
    return;
32
2.47M
33
2.47M
  SmallPtrSet<const BasicBlock*, 8> Visited;
34
2.47M
  SmallVector<std::pair<const BasicBlock*, succ_const_iterator>, 8> VisitStack;
35
2.47M
  SmallPtrSet<const BasicBlock*, 8> InStack;
36
2.47M
37
2.47M
  Visited.insert(BB);
38
2.47M
  VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
39
2.47M
  InStack.insert(BB);
40
73.5M
  do {
41
73.5M
    std::pair<const BasicBlock*, succ_const_iterator> &Top = VisitStack.back();
42
73.5M
    const BasicBlock *ParentBB = Top.first;
43
73.5M
    succ_const_iterator &I = Top.second;
44
73.5M
45
73.5M
    bool FoundNew = false;
46
93.2M
    while (
I != succ_end(ParentBB)93.2M
) {
47
55.2M
      BB = *I++;
48
55.2M
      if (
Visited.insert(BB).second55.2M
) {
49
35.5M
        FoundNew = true;
50
35.5M
        break;
51
35.5M
      }
52
19.6M
      // Successor is in VisitStack, it's a back edge.
53
19.6M
      
if (19.6M
InStack.count(BB)19.6M
)
54
3.64M
        Result.push_back(std::make_pair(ParentBB, BB));
55
55.2M
    }
56
73.5M
57
73.5M
    if (
FoundNew73.5M
) {
58
35.5M
      // Go down one level if there is a unvisited successor.
59
35.5M
      InStack.insert(BB);
60
35.5M
      VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
61
73.5M
    } else {
62
37.9M
      // Go up one level.
63
37.9M
      InStack.erase(VisitStack.pop_back_val().first);
64
37.9M
    }
65
73.5M
  } while (!VisitStack.empty());
66
5.76M
}
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.
72
unsigned llvm::GetSuccessorNumber(const BasicBlock *BB,
73
46.5k
    const BasicBlock *Succ) {
74
46.5k
  const TerminatorInst *Term = BB->getTerminator();
75
#ifndef NDEBUG
76
  unsigned e = Term->getNumSuccessors();
77
#endif
78
46.5k
  for (unsigned i = 0; ; 
++i6.33k
) {
79
52.9k
    assert(i != e && "Didn't find edge?");
80
52.9k
    if (Term->getSuccessor(i) == Succ)
81
46.5k
      return i;
82
52.9k
  }
83
46.5k
}
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.
88
bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
89
182k
                          bool AllowIdenticalEdges) {
90
182k
  assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!");
91
182k
  if (
TI->getNumSuccessors() == 1182k
)
return false34.7k
;
92
147k
93
147k
  const BasicBlock *Dest = TI->getSuccessor(SuccNum);
94
147k
  const_pred_iterator I = pred_begin(Dest), E = pred_end(Dest);
95
147k
96
147k
  // If there is more than one predecessor, this is a critical edge...
97
147k
  assert(I != E && "No preds, but we have an edge to the block?");
98
147k
  const BasicBlock *FirstPred = *I;
99
147k
  ++I;        // Skip one edge due to the incoming arc from TI.
100
147k
  if (!AllowIdenticalEdges)
101
139k
    return I != E;
102
8.82k
103
8.82k
  // If AllowIdenticalEdges is true, then we allow this edge to be considered
104
8.82k
  // non-critical iff all preds come from TI's block.
105
8.84k
  
for (; 8.82k
I != E8.84k
;
++I24
)
106
8.84k
    
if (8.84k
*I != FirstPred8.84k
)
107
8.82k
      return true;
108
3
  return false;
109
182k
}
110
111
// LoopInfo contains a mapping from basic block to the innermost loop. Find
112
// the outermost loop in the loop nest that contains BB.
113
7.72M
static const Loop *getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB) {
114
7.72M
  const Loop *L = LI->getLoopFor(BB);
115
7.72M
  if (
L7.72M
) {
116
1.41M
    while (const Loop *Parent = L->getParentLoop())
117
359k
      L = Parent;
118
1.05M
  }
119
7.72M
  return L;
120
7.72M
}
121
122
// True if there is a loop which contains both BB1 and BB2.
123
static bool loopContainsBoth(const LoopInfo *LI,
124
2.67M
                             const BasicBlock *BB1, const BasicBlock *BB2) {
125
2.67M
  const Loop *L1 = getOutermostLoop(LI, BB1);
126
2.67M
  const Loop *L2 = getOutermostLoop(LI, BB2);
127
519k
  return L1 != nullptr && L1 == L2;
128
2.67M
}
129
130
bool llvm::isPotentiallyReachableFromMany(
131
    SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
132
1.48M
    const DominatorTree *DT, const LoopInfo *LI) {
133
1.48M
  // When the stop block is unreachable, it's dominated from everywhere,
134
1.48M
  // regardless of whether there's a path between the two blocks.
135
1.48M
  if (
DT && 1.48M
!DT->isReachableFromEntry(StopBB)1.48M
)
136
664
    DT = nullptr;
137
1.48M
138
1.48M
  // Limit the number of blocks we visit. The goal is to avoid run-away compile
139
1.48M
  // times on large CFGs without hampering sensible code. Arbitrarily chosen.
140
1.48M
  unsigned Limit = 32;
141
1.48M
  SmallPtrSet<const BasicBlock*, 32> Visited;
142
10.9M
  do {
143
10.9M
    BasicBlock *BB = Worklist.pop_back_val();
144
10.9M
    if (!Visited.insert(BB).second)
145
1.89M
      continue;
146
9.10M
    
if (9.10M
BB == StopBB9.10M
)
147
460k
      return true;
148
8.64M
    
if (8.64M
DT && 8.64M
DT->dominates(BB, StopBB)8.63M
)
149
216k
      return true;
150
8.42M
    
if (8.42M
LI && 8.42M
loopContainsBoth(LI, BB, StopBB)2.67M
)
151
281k
      return true;
152
8.14M
153
8.14M
    
if (8.14M
!--Limit8.14M
) {
154
141k
      // We haven't been able to prove it one way or the other. Conservatively
155
141k
      // answer true -- that there is potentially a path.
156
141k
      return true;
157
141k
    }
158
8.00M
159
8.00M
    
if (const Loop *8.00M
Outer8.00M
= LI ? getOutermostLoop(LI, BB) : nullptr) {
160
235k
      // All blocks in a single loop are reachable from all other blocks. From
161
235k
      // any of these blocks, we can skip directly to the exits of the loop,
162
235k
      // ignoring any other blocks inside the loop body.
163
235k
      Outer->getExitBlocks(Worklist);
164
8.00M
    } else {
165
7.76M
      Worklist.append(succ_begin(BB), succ_end(BB));
166
7.76M
    }
167
9.89M
  } while (!Worklist.empty());
168
1.48M
169
1.48M
  // We have exhausted all possible paths and are certain that 'To' can not be
170
1.48M
  // reached from 'From'.
171
385k
  return false;
172
1.48M
}
173
174
bool llvm::isPotentiallyReachable(const BasicBlock *A, const BasicBlock *B,
175
1.02M
                                  const DominatorTree *DT, const LoopInfo *LI) {
176
1.02M
  assert(A->getParent() == B->getParent() &&
177
1.02M
         "This analysis is function-local!");
178
1.02M
179
1.02M
  SmallVector<BasicBlock*, 32> Worklist;
180
1.02M
  Worklist.push_back(const_cast<BasicBlock*>(A));
181
1.02M
182
1.02M
  return isPotentiallyReachableFromMany(Worklist, const_cast<BasicBlock *>(B),
183
1.02M
                                        DT, LI);
184
1.02M
}
185
186
bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B,
187
740k
                                  const DominatorTree *DT, const LoopInfo *LI) {
188
740k
  assert(A->getParent()->getParent() == B->getParent()->getParent() &&
189
740k
         "This analysis is function-local!");
190
740k
191
740k
  SmallVector<BasicBlock*, 32> Worklist;
192
740k
193
740k
  if (
A->getParent() == B->getParent()740k
) {
194
203k
    // The same block case is special because it's the only time we're looking
195
203k
    // within a single block to see which instruction comes first. Once we
196
203k
    // start looking at multiple blocks, the first instruction of the block is
197
203k
    // reachable, so we only need to determine reachability between whole
198
203k
    // blocks.
199
203k
    BasicBlock *BB = const_cast<BasicBlock *>(A->getParent());
200
203k
201
203k
    // If the block is in a loop then we can reach any instruction in the block
202
203k
    // from any other instruction in the block by going around a backedge.
203
203k
    if (
LI && 203k
LI->getLoopFor(BB) != nullptr19.8k
)
204
19.0k
      return true;
205
184k
206
184k
    // Linear scan, start at 'A', see whether we hit 'B' or the end first.
207
777k
    
for (BasicBlock::const_iterator I = A->getIterator(), E = BB->end(); 184k
I != E777k
;
208
593k
         
++I593k
) {
209
777k
      if (&*I == B)
210
184k
        return true;
211
777k
    }
212
184k
213
184k
    // Can't be in a loop if it's the entry block -- the entry block may not
214
184k
    // have predecessors.
215
10
    
if (10
BB == &BB->getParent()->getEntryBlock()10
)
216
4
      return false;
217
6
218
6
    // Otherwise, continue doing the normal per-BB CFG walk.
219
6
    Worklist.append(succ_begin(BB), succ_end(BB));
220
6
221
6
    if (
Worklist.empty()6
) {
222
0
      // We've proven that there's no path!
223
0
      return false;
224
0
    }
225
536k
  } else {
226
536k
    Worklist.push_back(const_cast<BasicBlock*>(A->getParent()));
227
536k
  }
228
740k
229
536k
  
if (536k
A->getParent() == &A->getParent()->getParent()->getEntryBlock()536k
)
230
8
    return true;
231
536k
  
if (536k
B->getParent() == &A->getParent()->getParent()->getEntryBlock()536k
)
232
141k
    return false;
233
395k
234
395k
  return isPotentiallyReachableFromMany(
235
395k
      Worklist, const_cast<BasicBlock *>(B->getParent()), DT, LI);
236
395k
}