Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/CFG.cpp
Line
Count
Source (jump to first uncovered line)
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/ADT/SmallPtrSet.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
4.69M
     SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) {
29
4.69M
  const BasicBlock *BB = &F.getEntryBlock();
30
4.69M
  if (succ_empty(BB))
31
2.84M
    return;
32
1.85M
33
1.85M
  SmallPtrSet<const BasicBlock*, 8> Visited;
34
1.85M
  SmallVector<std::pair<const BasicBlock*, succ_const_iterator>, 8> VisitStack;
35
1.85M
  SmallPtrSet<const BasicBlock*, 8> InStack;
36
1.85M
37
1.85M
  Visited.insert(BB);
38
1.85M
  VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
39
1.85M
  InStack.insert(BB);
40
49.8M
  do {
41
49.8M
    std::pair<const BasicBlock*, succ_const_iterator> &Top = VisitStack.back();
42
49.8M
    const BasicBlock *ParentBB = Top.first;
43
49.8M
    succ_const_iterator &I = Top.second;
44
49.8M
45
49.8M
    bool FoundNew = false;
46
62.9M
    while (I != succ_end(ParentBB)) {
47
37.0M
      BB = *I++;
48
37.0M
      if (Visited.insert(BB).second) {
49
23.9M
        FoundNew = true;
50
23.9M
        break;
51
23.9M
      }
52
13.1M
      // Successor is in VisitStack, it's a back edge.
53
13.1M
      if (InStack.count(BB))
54
2.16M
        Result.push_back(std::make_pair(ParentBB, BB));
55
13.1M
    }
56
49.8M
57
49.8M
    if (FoundNew) {
58
23.9M
      // Go down one level if there is a unvisited successor.
59
23.9M
      InStack.insert(BB);
60
23.9M
      VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
61
25.8M
    } else {
62
25.8M
      // Go up one level.
63
25.8M
      InStack.erase(VisitStack.pop_back_val().first);
64
25.8M
    }
65
49.8M
  } while (!VisitStack.empty());
66
1.85M
}
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
36.5k
    const BasicBlock *Succ) {
74
36.5k
  const Instruction *Term = BB->getTerminator();
75
#ifndef NDEBUG
76
  unsigned e = Term->getNumSuccessors();
77
#endif
78
45.3k
  for (unsigned i = 0; ; 
++i8.77k
) {
79
45.3k
    assert(i != e && "Didn't find edge?");
80
45.3k
    if (Term->getSuccessor(i) == Succ)
81
36.5k
      return i;
82
45.3k
  }
83
36.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 Instruction *TI, unsigned SuccNum,
89
137k
                          bool AllowIdenticalEdges) {
90
137k
  assert(TI->isTerminator() && "Must be a terminator to have successors!");
91
137k
  assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!");
92
137k
  if (TI->getNumSuccessors() == 1) 
return false26.2k
;
93
111k
94
111k
  const BasicBlock *Dest = TI->getSuccessor(SuccNum);
95
111k
  const_pred_iterator I = pred_begin(Dest), E = pred_end(Dest);
96
111k
97
111k
  // If there is more than one predecessor, this is a critical edge...
98
111k
  assert(I != E && "No preds, but we have an edge to the block?");
99
111k
  const BasicBlock *FirstPred = *I;
100
111k
  ++I;        // Skip one edge due to the incoming arc from TI.
101
111k
  if (!AllowIdenticalEdges)
102
106k
    return I != E;
103
5.46k
104
5.46k
  // If AllowIdenticalEdges is true, then we allow this edge to be considered
105
5.46k
  // non-critical iff all preds come from TI's block.
106
5.47k
  
for (; 5.46k
I != E;
++I10
)
107
5.47k
    if (*I != FirstPred)
108
5.46k
      return true;
109
5.46k
  
return false3
;
110
5.46k
}
111
112
// LoopInfo contains a mapping from basic block to the innermost loop. Find
113
// the outermost loop in the loop nest that contains BB.
114
3.07M
static const Loop *getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB) {
115
3.07M
  const Loop *L = LI->getLoopFor(BB);
116
3.07M
  if (L) {
117
1.59M
    while (const Loop *Parent = L->getParentLoop())
118
512k
      L = Parent;
119
1.08M
  }
120
3.07M
  return L;
121
3.07M
}
122
123
bool llvm::isPotentiallyReachableFromMany(
124
    SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
125
    const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
126
1.82M
    const LoopInfo *LI) {
127
1.82M
  // When the stop block is unreachable, it's dominated from everywhere,
128
1.82M
  // regardless of whether there's a path between the two blocks.
129
1.82M
  if (DT && 
!DT->isReachableFromEntry(StopBB)1.77M
)
130
1.29k
    DT = nullptr;
131
1.82M
132
1.82M
  // We can't skip directly from a block that dominates the stop block if the
133
1.82M
  // exclusion block is potentially in between.
134
1.82M
  if (ExclusionSet && 
!ExclusionSet->empty()70
)
135
12
    DT = nullptr;
136
1.82M
137
1.82M
  // Normally any block in a loop is reachable from any other block in a loop,
138
1.82M
  // however excluded blocks might partition the body of a loop to make that
139
1.82M
  // untrue.
140
1.82M
  SmallPtrSet<const Loop *, 8> LoopsWithHoles;
141
1.82M
  if (LI && 
ExclusionSet883k
) {
142
34
    for (auto BB : *ExclusionSet) {
143
8
      if (const Loop *L = getOutermostLoop(LI, BB))
144
0
        LoopsWithHoles.insert(L);
145
8
    }
146
34
  }
147
1.82M
148
1.82M
  const Loop *StopLoop = LI ? 
getOutermostLoop(LI, StopBB)883k
:
nullptr937k
;
149
1.82M
150
1.82M
  // Limit the number of blocks we visit. The goal is to avoid run-away compile
151
1.82M
  // times on large CFGs without hampering sensible code. Arbitrarily chosen.
152
1.82M
  unsigned Limit = 32;
153
1.82M
  SmallPtrSet<const BasicBlock*, 32> Visited;
154
24.3M
  do {
155
24.3M
    BasicBlock *BB = Worklist.pop_back_val();
156
24.3M
    if (!Visited.insert(BB).second)
157
4.42M
      continue;
158
19.9M
    if (BB == StopBB)
159
332k
      return true;
160
19.6M
    if (ExclusionSet && 
ExclusionSet->count(BB)116
)
161
12
      continue;
162
19.6M
    if (DT && 
DT->dominates(BB, StopBB)19.1M
)
163
207k
      return true;
164
19.4M
165
19.4M
    const Loop *Outer = nullptr;
166
19.4M
    if (LI) {
167
2.18M
      Outer = getOutermostLoop(LI, BB);
168
2.18M
      // If we're in a loop with a hole, not all blocks in the loop are
169
2.18M
      // reachable from all other blocks. That implies we can't simply jump to
170
2.18M
      // the loop's exit blocks, as that exit might need to pass through an
171
2.18M
      // excluded block. Clear Outer so we process BB's successors.
172
2.18M
      if (LoopsWithHoles.count(Outer))
173
0
        Outer = nullptr;
174
2.18M
      if (StopLoop && 
Outer == StopLoop279k
)
175
239k
        return true;
176
19.1M
    }
177
19.1M
178
19.1M
    if (!--Limit) {
179
409k
      // We haven't been able to prove it one way or the other. Conservatively
180
409k
      // answer true -- that there is potentially a path.
181
409k
      return true;
182
409k
    }
183
18.7M
184
18.7M
    if (Outer) {
185
204k
      // All blocks in a single loop are reachable from all other blocks. From
186
204k
      // any of these blocks, we can skip directly to the exits of the loop,
187
204k
      // ignoring any other blocks inside the loop body.
188
204k
      Outer->getExitBlocks(Worklist);
189
18.5M
    } else {
190
18.5M
      Worklist.append(succ_begin(BB), succ_end(BB));
191
18.5M
    }
192
23.1M
  } while (!Worklist.empty());
193
1.82M
194
1.82M
  // We have exhausted all possible paths and are certain that 'To' can not be
195
1.82M
  // reached from 'From'.
196
1.82M
  
return false632k
;
197
1.82M
}
198
199
bool llvm::isPotentiallyReachable(const BasicBlock *A, const BasicBlock *B,
200
756k
                                  const DominatorTree *DT, const LoopInfo *LI) {
201
756k
  assert(A->getParent() == B->getParent() &&
202
756k
         "This analysis is function-local!");
203
756k
204
756k
  SmallVector<BasicBlock*, 32> Worklist;
205
756k
  Worklist.push_back(const_cast<BasicBlock*>(A));
206
756k
207
756k
  return isPotentiallyReachableFromMany(Worklist, const_cast<BasicBlock *>(B),
208
756k
                                        nullptr, DT, LI);
209
756k
}
210
211
bool llvm::isPotentiallyReachable(
212
    const Instruction *A, const Instruction *B,
213
    const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
214
1.13M
    const LoopInfo *LI) {
215
1.13M
  assert(A->getParent()->getParent() == B->getParent()->getParent() &&
216
1.13M
         "This analysis is function-local!");
217
1.13M
218
1.13M
  SmallVector<BasicBlock*, 32> Worklist;
219
1.13M
220
1.13M
  if (A->getParent() == B->getParent()) {
221
109k
    // The same block case is special because it's the only time we're looking
222
109k
    // within a single block to see which instruction comes first. Once we
223
109k
    // start looking at multiple blocks, the first instruction of the block is
224
109k
    // reachable, so we only need to determine reachability between whole
225
109k
    // blocks.
226
109k
    BasicBlock *BB = const_cast<BasicBlock *>(A->getParent());
227
109k
228
109k
    // If the block is in a loop then we can reach any instruction in the block
229
109k
    // from any other instruction in the block by going around a backedge.
230
109k
    if (LI && 
LI->getLoopFor(BB) != nullptr94.8k
)
231
93.5k
      return true;
232
15.8k
233
15.8k
    // Linear scan, start at 'A', see whether we hit 'B' or the end first.
234
69.8k
    
for (BasicBlock::const_iterator I = A->getIterator(), E = BB->end(); 15.8k
I != E;
235
69.8k
         
++I54.0k
) {
236
69.8k
      if (&*I == B)
237
15.8k
        return true;
238
69.8k
    }
239
15.8k
240
15.8k
    // Can't be in a loop if it's the entry block -- the entry block may not
241
15.8k
    // have predecessors.
242
15.8k
    
if (10
BB == &BB->getParent()->getEntryBlock()10
)
243
4
      return false;
244
6
245
6
    // Otherwise, continue doing the normal per-BB CFG walk.
246
6
    Worklist.append(succ_begin(BB), succ_end(BB));
247
6
248
6
    if (Worklist.empty()) {
249
0
      // We've proven that there's no path!
250
0
      return false;
251
0
    }
252
1.02M
  } else {
253
1.02M
    Worklist.push_back(const_cast<BasicBlock*>(A->getParent()));
254
1.02M
  }
255
1.13M
256
1.13M
  
if (1.02M
DT1.02M
) {
257
1.02M
    if (DT->isReachableFromEntry(A->getParent()) &&
258
1.02M
        
!DT->isReachableFromEntry(B->getParent())1.02M
)
259
4
      return false;
260
1.02M
    if (!ExclusionSet || 
ExclusionSet->empty()37
) {
261
1.02M
      if (A->getParent() == &A->getParent()->getParent()->getEntryBlock() &&
262
1.02M
          
DT->isReachableFromEntry(B->getParent())4
)
263
4
        return true;
264
1.02M
      if (B->getParent() == &A->getParent()->getParent()->getEntryBlock() &&
265
1.02M
          
DT->isReachableFromEntry(A->getParent())168k
)
266
167k
        return false;
267
861k
    }
268
1.02M
  }
269
861k
270
861k
  return isPotentiallyReachableFromMany(
271
861k
      Worklist, const_cast<BasicBlock *>(B->getParent()), ExclusionSet, DT, LI);
272
861k
}