1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
| //===- PhiValues.h - Phi Value Analysis -------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines the PhiValues class, and associated passes, which can be
// used to find the underlying values of the phis in a function, i.e. the
// non-phi values that can be found by traversing the phi graph.
//
// This information is computed lazily and cached. If new phis are added to the
// function they are handled correctly, but if an existing phi has its operands
// modified PhiValues has to be notified by calling invalidateValue.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_PHIVALUES_H
#define LLVM_ANALYSIS_PHIVALUES_H
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
namespace llvm {
class Use;
class Value;
class PHINode;
class Function;
/// Class for calculating and caching the underlying values of phis in a
/// function.
///
/// Initially the PhiValues is empty, and gets incrementally populated whenever
/// it is queried.
class PhiValues {
public:
using ValueSet = SmallPtrSet<Value *, 4>;
/// Construct an empty PhiValues.
PhiValues(const Function &F) : F(F) {}
/// Get the underlying values of a phi.
///
/// This returns the cached value if PN has previously been processed,
/// otherwise it processes it first.
const ValueSet &getValuesForPhi(const PHINode *PN);
/// Notify PhiValues that the cached information using V is no longer valid
///
/// Whenever a phi has its operands modified the cached values for that phi
/// (and the phis that use that phi) become invalid. A user of PhiValues has
/// to notify it of this by calling invalidateValue on either the operand or
/// the phi, which will then clear the relevant cached information.
void invalidateValue(const Value *V);
/// Free the memory used by this class.
void releaseMemory();
/// Print out the values currently in the cache.
void print(raw_ostream &OS) const;
/// Handle invalidation events in the new pass manager.
bool invalidate(Function &, const PreservedAnalyses &,
FunctionAnalysisManager::Invalidator &);
private:
using PhiSet = SmallPtrSet<const PHINode *, 4>;
using ConstValueSet = SmallPtrSet<const Value *, 4>;
/// The next depth number to be used by processPhi.
unsigned int NextDepthNumber = 1;
/// Depth numbers of phis. Phis with the same depth number are part of the
/// same strongly connected component.
DenseMap<const PHINode *, unsigned int> DepthMap;
/// Non-phi values reachable from each component.
DenseMap<unsigned int, ValueSet> NonPhiReachableMap;
/// All values reachable from each component.
DenseMap<unsigned int, ConstValueSet> ReachableMap;
/// A CallbackVH to notify PhiValues when a value is deleted or replaced, so
/// that the cached information for that value can be cleared to avoid
/// dangling pointers to invalid values.
class PhiValuesCallbackVH final : public CallbackVH {
PhiValues *PV;
void deleted() override;
void allUsesReplacedWith(Value *New) override;
public:
PhiValuesCallbackVH(Value *V, PhiValues *PV = nullptr)
: CallbackVH(V), PV(PV) {}
};
/// A set of callbacks to the values that processPhi has seen.
DenseSet<PhiValuesCallbackVH, DenseMapInfo<Value *>> TrackedValues;
/// The function that the PhiValues is for.
const Function &F;
/// Process a phi so that its entries in the depth and reachable maps are
/// fully populated.
void processPhi(const PHINode *PN, SmallVector<const PHINode *, 8> &Stack);
};
/// The analysis pass which yields a PhiValues
///
/// The analysis does nothing by itself, and just returns an empty PhiValues
/// which will get filled in as it's used.
class PhiValuesAnalysis : public AnalysisInfoMixin<PhiValuesAnalysis> {
friend AnalysisInfoMixin<PhiValuesAnalysis>;
static AnalysisKey Key;
public:
using Result = PhiValues;
PhiValues run(Function &F, FunctionAnalysisManager &);
};
/// A pass for printing the PhiValues for a function.
///
/// This pass doesn't print whatever information the PhiValues happens to hold,
/// but instead first uses the PhiValues to analyze all the phis in the function
/// so the complete information is printed.
class PhiValuesPrinterPass : public PassInfoMixin<PhiValuesPrinterPass> {
raw_ostream &OS;
public:
explicit PhiValuesPrinterPass(raw_ostream &OS) : OS(OS) {}
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
};
/// Wrapper pass for the legacy pass manager
class PhiValuesWrapperPass : public FunctionPass {
std::unique_ptr<PhiValues> Result;
public:
static char ID;
PhiValuesWrapperPass();
PhiValues &getResult() { return *Result; }
const PhiValues &getResult() const { return *Result; }
bool runOnFunction(Function &F) override;
void releaseMemory() override;
void getAnalysisUsage(AnalysisUsage &AU) const override;
};
} // namespace llvm
#endif
|