Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/IR/Dominators.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- Dominators.cpp - Dominator Calculation -----------------------------===//
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 file implements simple dominator construction algorithms for finding
10
// forward dominators.  Postdominators are available in libanalysis, but are not
11
// included in libvmcore, because it's not needed.  Forward dominators are
12
// needed to support the Verifier pass.
13
//
14
//===----------------------------------------------------------------------===//
15
16
#include "llvm/IR/Dominators.h"
17
#include "llvm/ADT/DepthFirstIterator.h"
18
#include "llvm/ADT/SmallPtrSet.h"
19
#include "llvm/Config/llvm-config.h"
20
#include "llvm/IR/CFG.h"
21
#include "llvm/IR/Constants.h"
22
#include "llvm/IR/Instructions.h"
23
#include "llvm/IR/PassManager.h"
24
#include "llvm/Support/CommandLine.h"
25
#include "llvm/Support/Debug.h"
26
#include "llvm/Support/GenericDomTreeConstruction.h"
27
#include "llvm/Support/raw_ostream.h"
28
#include <algorithm>
29
using namespace llvm;
30
31
bool llvm::VerifyDomInfo = false;
32
static cl::opt<bool, true>
33
    VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), cl::Hidden,
34
                   cl::desc("Verify dominator info (time consuming)"));
35
36
#ifdef EXPENSIVE_CHECKS
37
static constexpr bool ExpensiveChecksEnabled = true;
38
#else
39
static constexpr bool ExpensiveChecksEnabled = false;
40
#endif
41
42
4.39M
bool BasicBlockEdge::isSingleEdge() const {
43
4.39M
  const Instruction *TI = Start->getTerminator();
44
4.39M
  unsigned NumEdgesToEnd = 0;
45
13.1M
  for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; 
++i8.79M
) {
46
8.79M
    if (TI->getSuccessor(i) == End)
47
4.39M
      ++NumEdgesToEnd;
48
8.79M
    if (NumEdgesToEnd >= 2)
49
6
      return false;
50
8.79M
  }
51
4.39M
  assert(NumEdgesToEnd == 1);
52
4.39M
  return true;
53
4.39M
}
54
55
//===----------------------------------------------------------------------===//
56
//  DominatorTree Implementation
57
//===----------------------------------------------------------------------===//
58
//
59
// Provide public access to DominatorTree information.  Implementation details
60
// can be found in Dominators.h, GenericDomTree.h, and
61
// GenericDomTreeConstruction.h.
62
//
63
//===----------------------------------------------------------------------===//
64
65
template class llvm::DomTreeNodeBase<BasicBlock>;
66
template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
67
template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
68
69
template class llvm::cfg::Update<BasicBlock *>;
70
71
template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
72
    DomTreeBuilder::BBDomTree &DT);
73
template void
74
llvm::DomTreeBuilder::CalculateWithUpdates<DomTreeBuilder::BBDomTree>(
75
    DomTreeBuilder::BBDomTree &DT, BBUpdates U);
76
77
template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
78
    DomTreeBuilder::BBPostDomTree &DT);
79
// No CalculateWithUpdates<PostDomTree> instantiation, unless a usecase arises.
80
81
template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
82
    DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
83
template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
84
    DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
85
86
template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
87
    DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
88
template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
89
    DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
90
91
template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
92
    DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBUpdates);
93
template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
94
    DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBUpdates);
95
96
template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
97
    const DomTreeBuilder::BBDomTree &DT,
98
    DomTreeBuilder::BBDomTree::VerificationLevel VL);
99
template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
100
    const DomTreeBuilder::BBPostDomTree &DT,
101
    DomTreeBuilder::BBPostDomTree::VerificationLevel VL);
102
103
bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
104
6.93k
                               FunctionAnalysisManager::Invalidator &) {
105
6.93k
  // Check whether the analysis, all analyses on functions, or the function's
106
6.93k
  // CFG have been preserved.
107
6.93k
  auto PAC = PA.getChecker<DominatorTreeAnalysis>();
108
6.93k
  return !(PAC.preserved() || 
PAC.preservedSet<AllAnalysesOn<Function>>()5.02k
||
109
6.93k
           
PAC.preservedSet<CFGAnalyses>()5.00k
);
110
6.93k
}
111
112
// dominates - Return true if Def dominates a use in User. This performs
113
// the special checks necessary if Def and User are in the same basic block.
114
// Note that Def doesn't dominate a use in Def itself!
115
bool DominatorTree::dominates(const Instruction *Def,
116
13.1M
                              const Instruction *User) const {
117
13.1M
  const BasicBlock *UseBB = User->getParent();
118
13.1M
  const BasicBlock *DefBB = Def->getParent();
119
13.1M
120
13.1M
  // Any unreachable use is dominated, even if Def == User.
121
13.1M
  if (!isReachableFromEntry(UseBB))
122
6
    return true;
123
13.1M
124
13.1M
  // Unreachable definitions don't dominate anything.
125
13.1M
  if (!isReachableFromEntry(DefBB))
126
6
    return false;
127
13.1M
128
13.1M
  // An instruction doesn't dominate a use in itself.
129
13.1M
  if (Def == User)
130
220k
    return false;
131
12.9M
132
12.9M
  // The value defined by an invoke dominates an instruction only if it
133
12.9M
  // dominates every instruction in UseBB.
134
12.9M
  // A PHI is dominated only if the instruction dominates every possible use in
135
12.9M
  // the UseBB.
136
12.9M
  if (isa<InvokeInst>(Def) || 
isa<PHINode>(User)11.2M
)
137
3.56M
    return dominates(Def, UseBB);
138
9.35M
139
9.35M
  if (DefBB != UseBB)
140
8.38M
    return dominates(DefBB, UseBB);
141
968k
142
968k
  // Loop through the basic block until we find Def or User.
143
968k
  BasicBlock::const_iterator I = DefBB->begin();
144
47.8M
  for (; &*I != Def && 
&*I != User46.9M
;
++I46.8M
)
145
46.8M
    /*empty*/;
146
968k
147
968k
  return &*I == Def;
148
968k
}
149
150
// true if Def would dominate a use in any instruction in UseBB.
151
// note that dominates(Def, Def->getParent()) is false.
152
bool DominatorTree::dominates(const Instruction *Def,
153
4.20M
                              const BasicBlock *UseBB) const {
154
4.20M
  const BasicBlock *DefBB = Def->getParent();
155
4.20M
156
4.20M
  // Any unreachable use is dominated, even if DefBB == UseBB.
157
4.20M
  if (!isReachableFromEntry(UseBB))
158
3
    return true;
159
4.20M
160
4.20M
  // Unreachable definitions don't dominate anything.
161
4.20M
  if (!isReachableFromEntry(DefBB))
162
9
    return false;
163
4.20M
164
4.20M
  if (DefBB == UseBB)
165
608k
    return false;
166
3.59M
167
3.59M
  // Invoke results are only usable in the normal destination, not in the
168
3.59M
  // exceptional destination.
169
3.59M
  if (const auto *II = dyn_cast<InvokeInst>(Def)) {
170
1.68M
    BasicBlock *NormalDest = II->getNormalDest();
171
1.68M
    BasicBlockEdge E(DefBB, NormalDest);
172
1.68M
    return dominates(E, UseBB);
173
1.68M
  }
174
1.90M
175
1.90M
  return dominates(DefBB, UseBB);
176
1.90M
}
177
178
bool DominatorTree::dominates(const BasicBlockEdge &BBE,
179
12.6M
                              const BasicBlock *UseBB) const {
180
12.6M
  // If the BB the edge ends in doesn't dominate the use BB, then the
181
12.6M
  // edge also doesn't.
182
12.6M
  const BasicBlock *Start = BBE.getStart();
183
12.6M
  const BasicBlock *End = BBE.getEnd();
184
12.6M
  if (!dominates(End, UseBB))
185
11.3M
    return false;
186
1.26M
187
1.26M
  // Simple case: if the end BB has a single predecessor, the fact that it
188
1.26M
  // dominates the use block implies that the edge also does.
189
1.26M
  if (End->getSinglePredecessor())
190
643k
    return true;
191
617k
192
617k
  // The normal edge from the invoke is critical. Conceptually, what we would
193
617k
  // like to do is split it and check if the new block dominates the use.
194
617k
  // With X being the new block, the graph would look like:
195
617k
  //
196
617k
  //        DefBB
197
617k
  //          /\      .  .
198
617k
  //         /  \     .  .
199
617k
  //        /    \    .  .
200
617k
  //       /      \   |  |
201
617k
  //      A        X  B  C
202
617k
  //      |         \ | /
203
617k
  //      .          \|/
204
617k
  //      .      NormalDest
205
617k
  //      .
206
617k
  //
207
617k
  // Given the definition of dominance, NormalDest is dominated by X iff X
208
617k
  // dominates all of NormalDest's predecessors (X, B, C in the example). X
209
617k
  // trivially dominates itself, so we only have to find if it dominates the
210
617k
  // other predecessors. Since the only way out of X is via NormalDest, X can
211
617k
  // only properly dominate a node if NormalDest dominates that node too.
212
617k
  int IsDuplicateEdge = 0;
213
617k
  for (const_pred_iterator PI = pred_begin(End), E = pred_end(End);
214
789k
       PI != E; 
++PI172k
) {
215
789k
    const BasicBlock *BB = *PI;
216
789k
    if (BB == Start) {
217
171k
      // If there are multiple edges between Start and End, by definition they
218
171k
      // can't dominate anything.
219
171k
      if (IsDuplicateEdge++)
220
2
        return false;
221
171k
      continue;
222
171k
    }
223
617k
224
617k
    if (!dominates(End, BB))
225
616k
      return false;
226
617k
  }
227
617k
  
return true627
;
228
617k
}
229
230
7.11M
bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
231
7.11M
  Instruction *UserInst = cast<Instruction>(U.getUser());
232
7.11M
  // A PHI in the end of the edge is dominated by it.
233
7.11M
  PHINode *PN = dyn_cast<PHINode>(UserInst);
234
7.11M
  if (PN && 
PN->getParent() == BBE.getEnd()1.00M
&&
235
7.11M
      
PN->getIncomingBlock(U) == BBE.getStart()311k
)
236
249k
    return true;
237
6.86M
238
6.86M
  // Otherwise use the edge-dominates-block query, which
239
6.86M
  // handles the crazy critical edge cases properly.
240
6.86M
  const BasicBlock *UseBB;
241
6.86M
  if (PN)
242
760k
    UseBB = PN->getIncomingBlock(U);
243
6.10M
  else
244
6.10M
    UseBB = UserInst->getParent();
245
6.86M
  return dominates(BBE, UseBB);
246
6.86M
}
247
248
564k
bool DominatorTree::dominates(const Instruction *Def, const Use &U) const {
249
564k
  Instruction *UserInst = cast<Instruction>(U.getUser());
250
564k
  const BasicBlock *DefBB = Def->getParent();
251
564k
252
564k
  // Determine the block in which the use happens. PHI nodes use
253
564k
  // their operands on edges; simulate this by thinking of the use
254
564k
  // happening at the end of the predecessor block.
255
564k
  const BasicBlock *UseBB;
256
564k
  if (PHINode *PN = dyn_cast<PHINode>(UserInst))
257
125k
    UseBB = PN->getIncomingBlock(U);
258
439k
  else
259
439k
    UseBB = UserInst->getParent();
260
564k
261
564k
  // Any unreachable use is dominated, even if Def == User.
262
564k
  if (!isReachableFromEntry(UseBB))
263
956
    return true;
264
563k
265
563k
  // Unreachable definitions don't dominate anything.
266
563k
  if (!isReachableFromEntry(DefBB))
267
0
    return false;
268
563k
269
563k
  // Invoke instructions define their return values on the edges to their normal
270
563k
  // successors, so we have to handle them specially.
271
563k
  // Among other things, this means they don't dominate anything in
272
563k
  // their own block, except possibly a phi, so we don't need to
273
563k
  // walk the block in any case.
274
563k
  if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) {
275
1.28k
    BasicBlock *NormalDest = II->getNormalDest();
276
1.28k
    BasicBlockEdge E(DefBB, NormalDest);
277
1.28k
    return dominates(E, U);
278
1.28k
  }
279
562k
280
562k
  // If the def and use are in different blocks, do a simple CFG dominator
281
562k
  // tree query.
282
562k
  if (DefBB != UseBB)
283
453k
    return dominates(DefBB, UseBB);
284
108k
285
108k
  // Ok, def and use are in the same block. If the def is an invoke, it
286
108k
  // doesn't dominate anything in the block. If it's a PHI, it dominates
287
108k
  // everything in the block.
288
108k
  if (isa<PHINode>(UserInst))
289
108k
    return true;
290
281
291
281
  // Otherwise, just loop through the basic block until we find Def or User.
292
281
  BasicBlock::const_iterator I = DefBB->begin();
293
580
  for (; &*I != Def && 
&*I != UserInst319
;
++I299
)
294
299
    /*empty*/;
295
281
296
281
  return &*I != UserInst;
297
281
}
298
299
126
bool DominatorTree::isReachableFromEntry(const Use &U) const {
300
126
  Instruction *I = dyn_cast<Instruction>(U.getUser());
301
126
302
126
  // ConstantExprs aren't really reachable from the entry block, but they
303
126
  // don't need to be treated like unreachable code either.
304
126
  if (!I) 
return true0
;
305
126
306
126
  // PHI nodes use their operands on their incoming edges.
307
126
  if (PHINode *PN = dyn_cast<PHINode>(I))
308
8
    return isReachableFromEntry(PN->getIncomingBlock(U));
309
118
310
118
  // Everything else uses their operands in their own block.
311
118
  return isReachableFromEntry(I->getParent());
312
118
}
313
314
//===----------------------------------------------------------------------===//
315
//  DominatorTreeAnalysis and related pass implementations
316
//===----------------------------------------------------------------------===//
317
//
318
// This implements the DominatorTreeAnalysis which is used with the new pass
319
// manager. It also implements some methods from utility passes.
320
//
321
//===----------------------------------------------------------------------===//
322
323
DominatorTree DominatorTreeAnalysis::run(Function &F,
324
9.02k
                                         FunctionAnalysisManager &) {
325
9.02k
  DominatorTree DT;
326
9.02k
  DT.recalculate(F);
327
9.02k
  return DT;
328
9.02k
}
329
330
AnalysisKey DominatorTreeAnalysis::Key;
331
332
2
DominatorTreePrinterPass::DominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {}
333
334
PreservedAnalyses DominatorTreePrinterPass::run(Function &F,
335
3
                                                FunctionAnalysisManager &AM) {
336
3
  OS << "DominatorTree for function: " << F.getName() << "\n";
337
3
  AM.getResult<DominatorTreeAnalysis>(F).print(OS);
338
3
339
3
  return PreservedAnalyses::all();
340
3
}
341
342
PreservedAnalyses DominatorTreeVerifierPass::run(Function &F,
343
32
                                                 FunctionAnalysisManager &AM) {
344
32
  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
345
32
  assert(DT.verify());
346
32
  (void)DT;
347
32
  return PreservedAnalyses::all();
348
32
}
349
350
//===----------------------------------------------------------------------===//
351
//  DominatorTreeWrapperPass Implementation
352
//===----------------------------------------------------------------------===//
353
//
354
// The implementation details of the wrapper pass that holds a DominatorTree
355
// suitable for use with the legacy pass manager.
356
//
357
//===----------------------------------------------------------------------===//
358
359
char DominatorTreeWrapperPass::ID = 0;
360
INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree",
361
                "Dominator Tree Construction", true, true)
362
363
9.23M
bool DominatorTreeWrapperPass::runOnFunction(Function &F) {
364
9.23M
  DT.recalculate(F);
365
9.23M
  return false;
366
9.23M
}
367
368
0
void DominatorTreeWrapperPass::verifyAnalysis() const {
369
0
  if (VerifyDomInfo)
370
0
    assert(DT.verify(DominatorTree::VerificationLevel::Full));
371
0
  else if (ExpensiveChecksEnabled)
372
0
    assert(DT.verify(DominatorTree::VerificationLevel::Basic));
373
0
}
374
375
6
void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
376
6
  DT.print(OS);
377
6
}
378