Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/OrderedBasicBlock.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- OrderedBasicBlock.cpp --------------------------------- -*- C++ -*-===//
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 the OrderedBasicBlock class. OrderedBasicBlock
10
// maintains an interface where clients can query if one instruction comes
11
// before another in a BasicBlock. Since BasicBlock currently lacks a reliable
12
// way to query relative position between instructions one can use
13
// OrderedBasicBlock to do such queries. OrderedBasicBlock is lazily built on a
14
// source BasicBlock and maintains an internal Instruction -> Position map. A
15
// OrderedBasicBlock instance should be discarded whenever the source
16
// BasicBlock changes.
17
//
18
// It's currently used by the CaptureTracker in order to find relative
19
// positions of a pair of instructions inside a BasicBlock.
20
//
21
//===----------------------------------------------------------------------===//
22
23
#include "llvm/Analysis/OrderedBasicBlock.h"
24
#include "llvm/IR/Instruction.h"
25
using namespace llvm;
26
27
OrderedBasicBlock::OrderedBasicBlock(const BasicBlock *BasicB)
28
12.6M
    : NextInstPos(0), BB(BasicB) {
29
12.6M
  LastInstFound = BB->end();
30
12.6M
}
31
32
/// Given no cached results, find if \p A comes before \p B in \p BB.
33
/// Cache and number out instruction while walking \p BB.
34
bool OrderedBasicBlock::comesBefore(const Instruction *A,
35
844k
                                    const Instruction *B) {
36
844k
  const Instruction *Inst = nullptr;
37
844k
  assert(!(LastInstFound == BB->end() && NextInstPos != 0) &&
38
844k
         "Instruction supposed to be in NumberedInsts");
39
844k
  assert(A->getParent() == BB && "Instruction supposed to be in the block!");
40
844k
  assert(B->getParent() == BB && "Instruction supposed to be in the block!");
41
844k
42
844k
  // Start the search with the instruction found in the last lookup round.
43
844k
  auto II = BB->begin();
44
844k
  auto IE = BB->end();
45
844k
  if (LastInstFound != IE)
46
204k
    II = std::next(LastInstFound);
47
844k
48
844k
  // Number all instructions up to the point where we find 'A' or 'B'.
49
4.79M
  for (; II != IE; 
++II3.95M
) {
50
4.79M
    Inst = cast<Instruction>(II);
51
4.79M
    NumberedInsts[Inst] = NextInstPos++;
52
4.79M
    if (Inst == A || 
Inst == B4.26M
)
53
844k
      break;
54
4.79M
  }
55
844k
56
844k
  assert(II != IE && "Instruction not found?");
57
844k
  assert((Inst == A || Inst == B) && "Should find A or B");
58
844k
  LastInstFound = II;
59
844k
  return Inst != B;
60
844k
}
61
62
/// Find out whether \p A dominates \p B, meaning whether \p A
63
/// comes before \p B in \p BB. This is a simplification that considers
64
/// cached instruction positions and ignores other basic blocks, being
65
/// only relevant to compare relative instructions positions inside \p BB.
66
10.2M
bool OrderedBasicBlock::dominates(const Instruction *A, const Instruction *B) {
67
10.2M
  assert(A->getParent() == B->getParent() &&
68
10.2M
         "Instructions must be in the same basic block!");
69
10.2M
  assert(A->getParent() == BB && "Instructions must be in the tracked block!");
70
10.2M
71
10.2M
  // First we lookup the instructions. If they don't exist, lookup will give us
72
10.2M
  // back ::end(). If they both exist, we compare the numbers. Otherwise, if NA
73
10.2M
  // exists and NB doesn't, it means NA must come before NB because we would
74
10.2M
  // have numbered NB as well if it didn't. The same is true for NB. If it
75
10.2M
  // exists, but NA does not, NA must come after it. If neither exist, we need
76
10.2M
  // to number the block and cache the results (by calling comesBefore).
77
10.2M
  auto NAI = NumberedInsts.find(A);
78
10.2M
  auto NBI = NumberedInsts.find(B);
79
10.2M
  if (NAI != NumberedInsts.end() && 
NBI != NumberedInsts.end()9.27M
)
80
8.04M
    return NAI->second < NBI->second;
81
2.24M
  if (NAI != NumberedInsts.end())
82
1.23M
    return true;
83
1.01M
  if (NBI != NumberedInsts.end())
84
171k
    return false;
85
844k
86
844k
  return comesBefore(A, B);
87
844k
}
88
89
10.5k
void OrderedBasicBlock::eraseInstruction(const Instruction *I) {
90
10.5k
  if (LastInstFound != BB->end() && 
I == &*LastInstFound941
) {
91
57
    if (LastInstFound == BB->begin()) {
92
0
      LastInstFound = BB->end();
93
0
      NextInstPos = 0;
94
0
    } else
95
57
      LastInstFound--;
96
57
  }
97
10.5k
98
10.5k
  NumberedInsts.erase(I);
99
10.5k
}
100
101
void OrderedBasicBlock::replaceInstruction(const Instruction *Old,
102
187
                                           const Instruction *New) {
103
187
  auto OI = NumberedInsts.find(Old);
104
187
  if (OI == NumberedInsts.end())
105
186
    return;
106
1
107
1
  NumberedInsts.insert({New, OI->second});
108
1
  if (LastInstFound != BB->end() && Old == &*LastInstFound)
109
1
    LastInstFound = New->getIterator();
110
1
  NumberedInsts.erase(Old);
111
1
}