Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/PhiValues.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- PhiValues.cpp - Phi Value 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
#include "llvm/Analysis/PhiValues.h"
10
#include "llvm/ADT/SmallPtrSet.h"
11
#include "llvm/ADT/SmallVector.h"
12
#include "llvm/IR/Instructions.h"
13
14
using namespace llvm;
15
16
9.73k
void PhiValues::PhiValuesCallbackVH::deleted() {
17
9.73k
  PV->invalidateValue(getValPtr());
18
9.73k
}
19
20
25.1k
void PhiValues::PhiValuesCallbackVH::allUsesReplacedWith(Value *) {
21
25.1k
  // We could potentially update the cached values we have with the new value,
22
25.1k
  // but it's simpler to just treat the old value as invalidated.
23
25.1k
  PV->invalidateValue(getValPtr());
24
25.1k
}
25
26
bool PhiValues::invalidate(Function &, const PreservedAnalyses &PA,
27
1.07k
                           FunctionAnalysisManager::Invalidator &) {
28
1.07k
  // PhiValues is invalidated if it isn't preserved.
29
1.07k
  auto PAC = PA.getChecker<PhiValuesAnalysis>();
30
1.07k
  return !(PAC.preserved() || 
PAC.preservedSet<AllAnalysesOn<Function>>()1.06k
);
31
1.07k
}
32
33
// The goal here is to find all of the non-phi values reachable from this phi,
34
// and to do the same for all of the phis reachable from this phi, as doing so
35
// is necessary anyway in order to get the values for this phi. We do this using
36
// Tarjan's algorithm with Nuutila's improvements to find the strongly connected
37
// components of the phi graph rooted in this phi:
38
//  * All phis in a strongly connected component will have the same reachable
39
//    non-phi values. The SCC may not be the maximal subgraph for that set of
40
//    reachable values, but finding out that isn't really necessary (it would
41
//    only reduce the amount of memory needed to store the values).
42
//  * Tarjan's algorithm completes components in a bottom-up manner, i.e. it
43
//    never completes a component before the components reachable from it have
44
//    been completed. This means that when we complete a component we have
45
//    everything we need to collect the values reachable from that component.
46
//  * We collect both the non-phi values reachable from each SCC, as that's what
47
//    we're ultimately interested in, and all of the reachable values, i.e.
48
//    including phis, as that makes invalidateValue easier.
49
void PhiValues::processPhi(const PHINode *Phi,
50
128k
                           SmallVector<const PHINode *, 8> &Stack) {
51
128k
  // Initialize the phi with the next depth number.
52
128k
  assert(DepthMap.lookup(Phi) == 0);
53
128k
  assert(NextDepthNumber != UINT_MAX);
54
128k
  unsigned int DepthNumber = ++NextDepthNumber;
55
128k
  DepthMap[Phi] = DepthNumber;
56
128k
57
128k
  // Recursively process the incoming phis of this phi.
58
128k
  TrackedValues.insert(PhiValuesCallbackVH(const_cast<PHINode *>(Phi), this));
59
287k
  for (Value *PhiOp : Phi->incoming_values()) {
60
287k
    if (PHINode *PhiPhiOp = dyn_cast<PHINode>(PhiOp)) {
61
78.8k
      // Recurse if the phi has not yet been visited.
62
78.8k
      if (DepthMap.lookup(PhiPhiOp) == 0)
63
42.3k
        processPhi(PhiPhiOp, Stack);
64
78.8k
      assert(DepthMap.lookup(PhiPhiOp) != 0);
65
78.8k
      // If the phi did not become part of a component then this phi and that
66
78.8k
      // phi are part of the same component, so adjust the depth number.
67
78.8k
      if (!ReachableMap.count(DepthMap[PhiPhiOp]))
68
40.8k
        DepthMap[Phi] = std::min(DepthMap[Phi], DepthMap[PhiPhiOp]);
69
208k
    } else {
70
208k
      TrackedValues.insert(PhiValuesCallbackVH(PhiOp, this));
71
208k
    }
72
287k
  }
73
128k
74
128k
  // Now that incoming phis have been handled, push this phi to the stack.
75
128k
  Stack.push_back(Phi);
76
128k
77
128k
  // If the depth number has not changed then we've finished collecting the phis
78
128k
  // of a strongly connected component.
79
128k
  if (DepthMap[Phi] == DepthNumber) {
80
111k
    // Collect the reachable values for this component. The phis of this
81
111k
    // component will be those on top of the depth stach with the same or
82
111k
    // greater depth number.
83
111k
    ConstValueSet Reachable;
84
240k
    while (!Stack.empty() && 
DepthMap[Stack.back()] >= DepthNumber130k
) {
85
128k
      const PHINode *ComponentPhi = Stack.pop_back_val();
86
128k
      Reachable.insert(ComponentPhi);
87
128k
      DepthMap[ComponentPhi] = DepthNumber;
88
287k
      for (Value *Op : ComponentPhi->incoming_values()) {
89
287k
        if (PHINode *PhiOp = dyn_cast<PHINode>(Op)) {
90
78.8k
          // If this phi is not part of the same component then that component
91
78.8k
          // is guaranteed to have been completed before this one. Therefore we
92
78.8k
          // can just add its reachable values to the reachable values of this
93
78.8k
          // component.
94
78.8k
          auto It = ReachableMap.find(DepthMap[PhiOp]);
95
78.8k
          if (It != ReachableMap.end())
96
38.0k
            Reachable.insert(It->second.begin(), It->second.end());
97
208k
        } else {
98
208k
          Reachable.insert(Op);
99
208k
        }
100
287k
      }
101
128k
    }
102
111k
    ReachableMap.insert({DepthNumber,Reachable});
103
111k
104
111k
    // Filter out phis to get the non-phi reachable values.
105
111k
    ValueSet NonPhi;
106
111k
    for (const Value *V : Reachable)
107
533k
      if (!isa<PHINode>(V))
108
294k
        NonPhi.insert(const_cast<Value*>(V));
109
111k
    NonPhiReachableMap.insert({DepthNumber,NonPhi});
110
111k
  }
111
128k
}
112
113
1.41M
const PhiValues::ValueSet &PhiValues::getValuesForPhi(const PHINode *PN) {
114
1.41M
  if (DepthMap.count(PN) == 0) {
115
86.5k
    SmallVector<const PHINode *, 8> Stack;
116
86.5k
    processPhi(PN, Stack);
117
86.5k
    assert(Stack.empty());
118
86.5k
  }
119
1.41M
  assert(DepthMap.lookup(PN) != 0);
120
1.41M
  return NonPhiReachableMap[DepthMap[PN]];
121
1.41M
}
122
123
962k
void PhiValues::invalidateValue(const Value *V) {
124
962k
  // Components that can reach V are invalid.
125
962k
  SmallVector<unsigned int, 8> InvalidComponents;
126
962k
  for (auto &Pair : ReachableMap)
127
4.19M
    if (Pair.second.count(V))
128
70.2k
      InvalidComponents.push_back(Pair.first);
129
962k
130
962k
  for (unsigned int N : InvalidComponents) {
131
70.2k
    for (const Value *V : ReachableMap[N])
132
368k
      if (const PHINode *PN = dyn_cast<PHINode>(V))
133
175k
        DepthMap.erase(PN);
134
70.2k
    NonPhiReachableMap.erase(N);
135
70.2k
    ReachableMap.erase(N);
136
70.2k
  }
137
962k
  // This value is no longer tracked
138
962k
  auto It = TrackedValues.find_as(V);
139
962k
  if (It != TrackedValues.end())
140
106k
    TrackedValues.erase(It);
141
962k
}
142
143
1.42M
void PhiValues::releaseMemory() {
144
1.42M
  DepthMap.clear();
145
1.42M
  NonPhiReachableMap.clear();
146
1.42M
  ReachableMap.clear();
147
1.42M
}
148
149
11
void PhiValues::print(raw_ostream &OS) const {
150
11
  // Iterate through the phi nodes of the function rather than iterating through
151
11
  // DepthMap in order to get predictable ordering.
152
95
  for (const BasicBlock &BB : F) {
153
95
    for (const PHINode &PN : BB.phis()) {
154
40
      OS << "PHI ";
155
40
      PN.printAsOperand(OS, false);
156
40
      OS << " has values:\n";
157
40
      unsigned int N = DepthMap.lookup(&PN);
158
40
      auto It = NonPhiReachableMap.find(N);
159
40
      if (It == NonPhiReachableMap.end())
160
0
        OS << "  UNKNOWN\n";
161
40
      else if (It->second.empty())
162
1
        OS << "  NONE\n";
163
39
      else
164
39
        for (Value *V : It->second)
165
76
          // Printing of an instruction prints two spaces at the start, so
166
76
          // handle instructions and everything else slightly differently in
167
76
          // order to get consistent indenting.
168
76
          if (Instruction *I = dyn_cast<Instruction>(V))
169
3
            OS << *I << "\n";
170
73
          else
171
73
            OS << "  " << *V << "\n";
172
40
    }
173
95
  }
174
11
}
175
176
AnalysisKey PhiValuesAnalysis::Key;
177
1.41k
PhiValues PhiValuesAnalysis::run(Function &F, FunctionAnalysisManager &) {
178
1.41k
  return PhiValues(F);
179
1.41k
}
180
181
PreservedAnalyses PhiValuesPrinterPass::run(Function &F,
182
11
                                            FunctionAnalysisManager &AM) {
183
11
  OS << "PHI Values for function: " << F.getName() << "\n";
184
11
  PhiValues &PI = AM.getResult<PhiValuesAnalysis>(F);
185
11
  for (const BasicBlock &BB : F)
186
95
    for (const PHINode &PN : BB.phis())
187
40
      PI.getValuesForPhi(&PN);
188
11
  PI.print(OS);
189
11
  return PreservedAnalyses::all();
190
11
}
191
192
42.4k
PhiValuesWrapperPass::PhiValuesWrapperPass() : FunctionPass(ID) {
193
42.4k
  initializePhiValuesWrapperPassPass(*PassRegistry::getPassRegistry());
194
42.4k
}
195
196
1.42M
bool PhiValuesWrapperPass::runOnFunction(Function &F) {
197
1.42M
  Result.reset(new PhiValues(F));
198
1.42M
  return false;
199
1.42M
}
200
201
1.42M
void PhiValuesWrapperPass::releaseMemory() {
202
1.42M
  Result->releaseMemory();
203
1.42M
}
204
205
42.4k
void PhiValuesWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
206
42.4k
  AU.setPreservesAll();
207
42.4k
}
208
209
char PhiValuesWrapperPass::ID = 0;
210
211
INITIALIZE_PASS(PhiValuesWrapperPass, "phi-values", "Phi Values Analysis", false,
212
                true)