/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Analysis/CFLGraph.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- CFLGraph.h - Abstract stratified sets implementation. -----*- C++-*-===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | // |
10 | | /// \file |
11 | | /// This file defines CFLGraph, an auxiliary data structure used by CFL-based |
12 | | /// alias analysis. |
13 | | // |
14 | | //===----------------------------------------------------------------------===// |
15 | | |
16 | | #ifndef LLVM_LIB_ANALYSIS_CFLGRAPH_H |
17 | | #define LLVM_LIB_ANALYSIS_CFLGRAPH_H |
18 | | |
19 | | #include "AliasAnalysisSummary.h" |
20 | | #include "llvm/ADT/APInt.h" |
21 | | #include "llvm/ADT/DenseMap.h" |
22 | | #include "llvm/ADT/SmallVector.h" |
23 | | #include "llvm/ADT/iterator_range.h" |
24 | | #include "llvm/Analysis/MemoryBuiltins.h" |
25 | | #include "llvm/Analysis/TargetLibraryInfo.h" |
26 | | #include "llvm/IR/Argument.h" |
27 | | #include "llvm/IR/BasicBlock.h" |
28 | | #include "llvm/IR/CallSite.h" |
29 | | #include "llvm/IR/Constants.h" |
30 | | #include "llvm/IR/DataLayout.h" |
31 | | #include "llvm/IR/Function.h" |
32 | | #include "llvm/IR/GlobalValue.h" |
33 | | #include "llvm/IR/InstVisitor.h" |
34 | | #include "llvm/IR/InstrTypes.h" |
35 | | #include "llvm/IR/Instruction.h" |
36 | | #include "llvm/IR/Instructions.h" |
37 | | #include "llvm/IR/Operator.h" |
38 | | #include "llvm/IR/Type.h" |
39 | | #include "llvm/IR/Value.h" |
40 | | #include "llvm/Support/Casting.h" |
41 | | #include "llvm/Support/ErrorHandling.h" |
42 | | #include <cassert> |
43 | | #include <cstdint> |
44 | | #include <vector> |
45 | | |
46 | | namespace llvm { |
47 | | namespace cflaa { |
48 | | |
49 | | /// \brief The Program Expression Graph (PEG) of CFL analysis |
50 | | /// CFLGraph is auxiliary data structure used by CFL-based alias analysis to |
51 | | /// describe flow-insensitive pointer-related behaviors. Given an LLVM function, |
52 | | /// the main purpose of this graph is to abstract away unrelated facts and |
53 | | /// translate the rest into a form that can be easily digested by CFL analyses. |
54 | | /// Each Node in the graph is an InstantiatedValue, and each edge represent a |
55 | | /// pointer assignment between InstantiatedValue. Pointer |
56 | | /// references/dereferences are not explicitly stored in the graph: we |
57 | | /// implicitly assume that for each node (X, I) it has a dereference edge to (X, |
58 | | /// I+1) and a reference edge to (X, I-1). |
59 | | class CFLGraph { |
60 | | public: |
61 | | using Node = InstantiatedValue; |
62 | | |
63 | | struct Edge { |
64 | | Node Other; |
65 | | int64_t Offset; |
66 | | }; |
67 | | |
68 | | using EdgeList = std::vector<Edge>; |
69 | | |
70 | | struct NodeInfo { |
71 | | EdgeList Edges, ReverseEdges; |
72 | | AliasAttrs Attr; |
73 | | }; |
74 | | |
75 | | class ValueInfo { |
76 | | std::vector<NodeInfo> Levels; |
77 | | |
78 | | public: |
79 | 2.15k | bool addNodeToLevel(unsigned Level) { |
80 | 2.15k | auto NumLevels = Levels.size(); |
81 | 2.15k | if (NumLevels > Level) |
82 | 882 | return false; |
83 | 1.27k | Levels.resize(Level + 1); |
84 | 1.27k | return true; |
85 | 2.15k | } |
86 | | |
87 | 3.01k | NodeInfo &getNodeInfoAtLevel(unsigned Level) { |
88 | 3.01k | assert(Level < Levels.size()); |
89 | 3.01k | return Levels[Level]; |
90 | 3.01k | } |
91 | 3.89k | const NodeInfo &getNodeInfoAtLevel(unsigned Level) const { |
92 | 3.89k | assert(Level < Levels.size()); |
93 | 3.89k | return Levels[Level]; |
94 | 3.89k | } |
95 | | |
96 | 5.87k | unsigned getNumLevels() const { return Levels.size(); } |
97 | | }; |
98 | | |
99 | | private: |
100 | | using ValueMap = DenseMap<Value *, ValueInfo>; |
101 | | |
102 | | ValueMap ValueImpls; |
103 | | |
104 | 855 | NodeInfo *getNode(Node N) { |
105 | 855 | auto Itr = ValueImpls.find(N.Val); |
106 | 855 | if (Itr == ValueImpls.end() || 855 Itr->second.getNumLevels() <= N.DerefLevel855 ) |
107 | 0 | return nullptr; |
108 | 855 | return &Itr->second.getNodeInfoAtLevel(N.DerefLevel); |
109 | 855 | } |
110 | | |
111 | | public: |
112 | | using const_value_iterator = ValueMap::const_iterator; |
113 | | |
114 | 2.15k | bool addNode(Node N, AliasAttrs Attr = AliasAttrs()) { |
115 | 2.15k | assert(N.Val != nullptr); |
116 | 2.15k | auto &ValInfo = ValueImpls[N.Val]; |
117 | 2.15k | auto Changed = ValInfo.addNodeToLevel(N.DerefLevel); |
118 | 2.15k | ValInfo.getNodeInfoAtLevel(N.DerefLevel).Attr |= Attr; |
119 | 2.15k | return Changed; |
120 | 2.15k | } |
121 | | |
122 | 41 | void addAttr(Node N, AliasAttrs Attr) { |
123 | 41 | auto *Info = getNode(N); |
124 | 41 | assert(Info != nullptr); |
125 | 41 | Info->Attr |= Attr; |
126 | 41 | } |
127 | | |
128 | 407 | void addEdge(Node From, Node To, int64_t Offset = 0) { |
129 | 407 | auto *FromInfo = getNode(From); |
130 | 407 | assert(FromInfo != nullptr); |
131 | 407 | auto *ToInfo = getNode(To); |
132 | 407 | assert(ToInfo != nullptr); |
133 | 407 | |
134 | 407 | FromInfo->Edges.push_back(Edge{To, Offset}); |
135 | 407 | ToInfo->ReverseEdges.push_back(Edge{From, Offset}); |
136 | 407 | } |
137 | | |
138 | 3.36k | const NodeInfo *getNode(Node N) const { |
139 | 3.36k | auto Itr = ValueImpls.find(N.Val); |
140 | 3.36k | if (Itr == ValueImpls.end() || 3.36k Itr->second.getNumLevels() <= N.DerefLevel3.36k ) |
141 | 2.02k | return nullptr; |
142 | 1.33k | return &Itr->second.getNodeInfoAtLevel(N.DerefLevel); |
143 | 3.36k | } |
144 | | |
145 | 0 | AliasAttrs attrFor(Node N) const { |
146 | 0 | auto *Info = getNode(N); |
147 | 0 | assert(Info != nullptr); |
148 | 0 | return Info->Attr; |
149 | 0 | } |
150 | | |
151 | 420 | iterator_range<const_value_iterator> value_mappings() const { |
152 | 420 | return make_range<const_value_iterator>(ValueImpls.begin(), |
153 | 420 | ValueImpls.end()); |
154 | 420 | } |
155 | | }; |
156 | | |
157 | | ///\brief A builder class used to create CFLGraph instance from a given function |
158 | | /// The CFL-AA that uses this builder must provide its own type as a template |
159 | | /// argument. This is necessary for interprocedural processing: CFLGraphBuilder |
160 | | /// needs a way of obtaining the summary of other functions when callinsts are |
161 | | /// encountered. |
162 | | /// As a result, we expect the said CFL-AA to expose a getAliasSummary() public |
163 | | /// member function that takes a Function& and returns the corresponding summary |
164 | | /// as a const AliasSummary*. |
165 | | template <typename CFLAA> class CFLGraphBuilder { |
166 | | // Input of the builder |
167 | | CFLAA &Analysis; |
168 | | const TargetLibraryInfo &TLI; |
169 | | |
170 | | // Output of the builder |
171 | | CFLGraph Graph; |
172 | | SmallVector<Value *, 4> ReturnedValues; |
173 | | |
174 | | // Helper class |
175 | | /// Gets the edges our graph should have, based on an Instruction* |
176 | | class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> { |
177 | | CFLAA &AA; |
178 | | const DataLayout &DL; |
179 | | const TargetLibraryInfo &TLI; |
180 | | |
181 | | CFLGraph &Graph; |
182 | | SmallVectorImpl<Value *> &ReturnValues; |
183 | | |
184 | 10 | static bool hasUsefulEdges(ConstantExpr *CE) { |
185 | 10 | // ConstantExpr doesn't have terminators, invokes, or fences, so only |
186 | 10 | // needs |
187 | 10 | // to check for compares. |
188 | 10 | return CE->getOpcode() != Instruction::ICmp && |
189 | 10 | CE->getOpcode() != Instruction::FCmp; |
190 | 10 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::hasUsefulEdges(llvm::ConstantExpr*) Line | Count | Source | 184 | 10 | static bool hasUsefulEdges(ConstantExpr *CE) { | 185 | 10 | // ConstantExpr doesn't have terminators, invokes, or fences, so only | 186 | 10 | // needs | 187 | 10 | // to check for compares. | 188 | 10 | return CE->getOpcode() != Instruction::ICmp && | 189 | 10 | CE->getOpcode() != Instruction::FCmp; | 190 | 10 | } |
Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::hasUsefulEdges(llvm::ConstantExpr*) |
191 | | |
192 | | // Returns possible functions called by CS into the given SmallVectorImpl. |
193 | | // Returns true if targets found, false otherwise. |
194 | | static bool getPossibleTargets(CallSite CS, |
195 | 107 | SmallVectorImpl<Function *> &Output) { |
196 | 107 | if (auto *Fn107 = CS.getCalledFunction()) { |
197 | 106 | Output.push_back(Fn); |
198 | 106 | return true; |
199 | 106 | } |
200 | 107 | |
201 | 107 | // TODO: If the call is indirect, we might be able to enumerate all |
202 | 107 | // potential |
203 | 107 | // targets of the call and return them, rather than just failing. |
204 | 1 | return false; |
205 | 107 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::getPossibleTargets(llvm::CallSite, llvm::SmallVectorImpl<llvm::Function*>&) Line | Count | Source | 195 | 50 | SmallVectorImpl<Function *> &Output) { | 196 | 50 | if (auto *Fn50 = CS.getCalledFunction()) { | 197 | 50 | Output.push_back(Fn); | 198 | 50 | return true; | 199 | 50 | } | 200 | 50 | | 201 | 50 | // TODO: If the call is indirect, we might be able to enumerate all | 202 | 50 | // potential | 203 | 50 | // targets of the call and return them, rather than just failing. | 204 | 0 | return false; | 205 | 50 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::getPossibleTargets(llvm::CallSite, llvm::SmallVectorImpl<llvm::Function*>&) Line | Count | Source | 195 | 57 | SmallVectorImpl<Function *> &Output) { | 196 | 57 | if (auto *Fn57 = CS.getCalledFunction()) { | 197 | 56 | Output.push_back(Fn); | 198 | 56 | return true; | 199 | 56 | } | 200 | 57 | | 201 | 57 | // TODO: If the call is indirect, we might be able to enumerate all | 202 | 57 | // potential | 203 | 57 | // targets of the call and return them, rather than just failing. | 204 | 1 | return false; | 205 | 57 | } |
|
206 | | |
207 | 1.27k | void addNode(Value *Val, AliasAttrs Attr = AliasAttrs()) { |
208 | 1.27k | assert(Val != nullptr && Val->getType()->isPointerTy()); |
209 | 1.27k | if (auto GVal1.27k = dyn_cast<GlobalValue>(Val)) { |
210 | 28 | if (Graph.addNode(InstantiatedValue{GVal, 0}, |
211 | 28 | getGlobalOrArgAttrFromValue(*GVal))) |
212 | 26 | Graph.addNode(InstantiatedValue{GVal, 1}, getAttrUnknown()); |
213 | 1.27k | } else if (auto 1.24k CExpr1.24k = dyn_cast<ConstantExpr>(Val)) { |
214 | 10 | if (hasUsefulEdges(CExpr)10 ) { |
215 | 10 | if (Graph.addNode(InstantiatedValue{CExpr, 0})) |
216 | 5 | visitConstantExpr(CExpr); |
217 | 10 | } |
218 | 10 | } else |
219 | 1.23k | Graph.addNode(InstantiatedValue{Val, 0}, Attr); |
220 | 1.27k | } llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::addNode(llvm::Value*, std::__1::bitset<32ul>) Line | Count | Source | 207 | 605 | void addNode(Value *Val, AliasAttrs Attr = AliasAttrs()) { | 208 | 605 | assert(Val != nullptr && Val->getType()->isPointerTy()); | 209 | 605 | if (auto GVal605 = dyn_cast<GlobalValue>(Val)) { | 210 | 10 | if (Graph.addNode(InstantiatedValue{GVal, 0}, | 211 | 10 | getGlobalOrArgAttrFromValue(*GVal))) | 212 | 10 | Graph.addNode(InstantiatedValue{GVal, 1}, getAttrUnknown()); | 213 | 605 | } else if (auto 595 CExpr595 = dyn_cast<ConstantExpr>(Val)) { | 214 | 0 | if (hasUsefulEdges(CExpr)0 ) { | 215 | 0 | if (Graph.addNode(InstantiatedValue{CExpr, 0})) | 216 | 0 | visitConstantExpr(CExpr); | 217 | 0 | } | 218 | 0 | } else | 219 | 595 | Graph.addNode(InstantiatedValue{Val, 0}, Attr); | 220 | 605 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::addNode(llvm::Value*, std::__1::bitset<32ul>) Line | Count | Source | 207 | 668 | void addNode(Value *Val, AliasAttrs Attr = AliasAttrs()) { | 208 | 668 | assert(Val != nullptr && Val->getType()->isPointerTy()); | 209 | 668 | if (auto GVal668 = dyn_cast<GlobalValue>(Val)) { | 210 | 18 | if (Graph.addNode(InstantiatedValue{GVal, 0}, | 211 | 18 | getGlobalOrArgAttrFromValue(*GVal))) | 212 | 16 | Graph.addNode(InstantiatedValue{GVal, 1}, getAttrUnknown()); | 213 | 668 | } else if (auto 650 CExpr650 = dyn_cast<ConstantExpr>(Val)) { | 214 | 10 | if (hasUsefulEdges(CExpr)10 ) { | 215 | 10 | if (Graph.addNode(InstantiatedValue{CExpr, 0})) | 216 | 5 | visitConstantExpr(CExpr); | 217 | 10 | } | 218 | 10 | } else | 219 | 640 | Graph.addNode(InstantiatedValue{Val, 0}, Attr); | 220 | 668 | } |
|
221 | | |
222 | 145 | void addAssignEdge(Value *From, Value *To, int64_t Offset = 0) { |
223 | 145 | assert(From != nullptr && To != nullptr); |
224 | 145 | if (!From->getType()->isPointerTy() || 145 !To->getType()->isPointerTy()117 ) |
225 | 28 | return; |
226 | 117 | addNode(From); |
227 | 117 | if (To != From117 ) { |
228 | 117 | addNode(To); |
229 | 117 | Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 0}, |
230 | 117 | Offset); |
231 | 117 | } |
232 | 145 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::addAssignEdge(llvm::Value*, llvm::Value*, long long) Line | Count | Source | 222 | 39 | void addAssignEdge(Value *From, Value *To, int64_t Offset = 0) { | 223 | 39 | assert(From != nullptr && To != nullptr); | 224 | 39 | if (!From->getType()->isPointerTy() || 39 !To->getType()->isPointerTy()39 ) | 225 | 0 | return; | 226 | 39 | addNode(From); | 227 | 39 | if (To != From39 ) { | 228 | 39 | addNode(To); | 229 | 39 | Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 0}, | 230 | 39 | Offset); | 231 | 39 | } | 232 | 39 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::addAssignEdge(llvm::Value*, llvm::Value*, long long) Line | Count | Source | 222 | 106 | void addAssignEdge(Value *From, Value *To, int64_t Offset = 0) { | 223 | 106 | assert(From != nullptr && To != nullptr); | 224 | 106 | if (!From->getType()->isPointerTy() || 106 !To->getType()->isPointerTy()78 ) | 225 | 28 | return; | 226 | 78 | addNode(From); | 227 | 78 | if (To != From78 ) { | 228 | 78 | addNode(To); | 229 | 78 | Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 0}, | 230 | 78 | Offset); | 231 | 78 | } | 232 | 106 | } |
|
233 | | |
234 | 316 | void addDerefEdge(Value *From, Value *To, bool IsRead) { |
235 | 316 | assert(From != nullptr && To != nullptr); |
236 | 316 | // FIXME: This is subtly broken, due to how we model some instructions |
237 | 316 | // (e.g. extractvalue, extractelement) as loads. Since those take |
238 | 316 | // non-pointer operands, we'll entirely skip adding edges for those. |
239 | 316 | // |
240 | 316 | // addAssignEdge seems to have a similar issue with insertvalue, etc. |
241 | 316 | if (!From->getType()->isPointerTy() || 316 !To->getType()->isPointerTy()277 ) |
242 | 54 | return; |
243 | 262 | addNode(From); |
244 | 262 | addNode(To); |
245 | 262 | if (IsRead262 ) { |
246 | 147 | Graph.addNode(InstantiatedValue{From, 1}); |
247 | 147 | Graph.addEdge(InstantiatedValue{From, 1}, InstantiatedValue{To, 0}); |
248 | 262 | } else { |
249 | 115 | Graph.addNode(InstantiatedValue{To, 1}); |
250 | 115 | Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 1}); |
251 | 115 | } |
252 | 316 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::addDerefEdge(llvm::Value*, llvm::Value*, bool) Line | Count | Source | 234 | 147 | void addDerefEdge(Value *From, Value *To, bool IsRead) { | 235 | 147 | assert(From != nullptr && To != nullptr); | 236 | 147 | // FIXME: This is subtly broken, due to how we model some instructions | 237 | 147 | // (e.g. extractvalue, extractelement) as loads. Since those take | 238 | 147 | // non-pointer operands, we'll entirely skip adding edges for those. | 239 | 147 | // | 240 | 147 | // addAssignEdge seems to have a similar issue with insertvalue, etc. | 241 | 147 | if (!From->getType()->isPointerTy() || 147 !To->getType()->isPointerTy()140 ) | 242 | 8 | return; | 243 | 139 | addNode(From); | 244 | 139 | addNode(To); | 245 | 139 | if (IsRead139 ) { | 246 | 78 | Graph.addNode(InstantiatedValue{From, 1}); | 247 | 78 | Graph.addEdge(InstantiatedValue{From, 1}, InstantiatedValue{To, 0}); | 248 | 139 | } else { | 249 | 61 | Graph.addNode(InstantiatedValue{To, 1}); | 250 | 61 | Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 1}); | 251 | 61 | } | 252 | 147 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::addDerefEdge(llvm::Value*, llvm::Value*, bool) Line | Count | Source | 234 | 169 | void addDerefEdge(Value *From, Value *To, bool IsRead) { | 235 | 169 | assert(From != nullptr && To != nullptr); | 236 | 169 | // FIXME: This is subtly broken, due to how we model some instructions | 237 | 169 | // (e.g. extractvalue, extractelement) as loads. Since those take | 238 | 169 | // non-pointer operands, we'll entirely skip adding edges for those. | 239 | 169 | // | 240 | 169 | // addAssignEdge seems to have a similar issue with insertvalue, etc. | 241 | 169 | if (!From->getType()->isPointerTy() || 169 !To->getType()->isPointerTy()137 ) | 242 | 46 | return; | 243 | 123 | addNode(From); | 244 | 123 | addNode(To); | 245 | 123 | if (IsRead123 ) { | 246 | 69 | Graph.addNode(InstantiatedValue{From, 1}); | 247 | 69 | Graph.addEdge(InstantiatedValue{From, 1}, InstantiatedValue{To, 0}); | 248 | 123 | } else { | 249 | 54 | Graph.addNode(InstantiatedValue{To, 1}); | 250 | 54 | Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 1}); | 251 | 54 | } | 252 | 169 | } |
|
253 | | |
254 | 163 | void addLoadEdge(Value *From, Value *To) { addDerefEdge(From, To, true); } llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::addLoadEdge(llvm::Value*, llvm::Value*) Line | Count | Source | 254 | 83 | void addLoadEdge(Value *From, Value *To) { addDerefEdge(From, To, true); } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::addLoadEdge(llvm::Value*, llvm::Value*) Line | Count | Source | 254 | 80 | void addLoadEdge(Value *From, Value *To) { addDerefEdge(From, To, true); } |
|
255 | 153 | void addStoreEdge(Value *From, Value *To) { addDerefEdge(From, To, false); } llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::addStoreEdge(llvm::Value*, llvm::Value*) Line | Count | Source | 255 | 86 | void addStoreEdge(Value *From, Value *To) { addDerefEdge(From, To, false); } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::addStoreEdge(llvm::Value*, llvm::Value*) Line | Count | Source | 255 | 67 | void addStoreEdge(Value *From, Value *To) { addDerefEdge(From, To, false); } |
|
256 | | |
257 | | public: |
258 | | GetEdgesVisitor(CFLGraphBuilder &Builder, const DataLayout &DL) |
259 | | : AA(Builder.Analysis), DL(DL), TLI(Builder.TLI), Graph(Builder.Graph), |
260 | 210 | ReturnValues(Builder.ReturnedValues) {} llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::GetEdgesVisitor(llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>&, llvm::DataLayout const&) Line | Count | Source | 260 | 115 | ReturnValues(Builder.ReturnedValues) {} |
llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::GetEdgesVisitor(llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>&, llvm::DataLayout const&) Line | Count | Source | 260 | 95 | ReturnValues(Builder.ReturnedValues) {} |
|
261 | | |
262 | 0 | void visitInstruction(Instruction &) { |
263 | 0 | llvm_unreachable("Unsupported instruction encountered"); |
264 | 0 | } Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitInstruction(llvm::Instruction&) Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitInstruction(llvm::Instruction&) |
265 | | |
266 | 210 | void visitReturnInst(ReturnInst &Inst) { |
267 | 210 | if (auto RetVal210 = Inst.getReturnValue()) { |
268 | 51 | if (RetVal->getType()->isPointerTy()51 ) { |
269 | 47 | addNode(RetVal); |
270 | 47 | ReturnValues.push_back(RetVal); |
271 | 47 | } |
272 | 51 | } |
273 | 210 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitReturnInst(llvm::ReturnInst&) Line | Count | Source | 266 | 95 | void visitReturnInst(ReturnInst &Inst) { | 267 | 95 | if (auto RetVal95 = Inst.getReturnValue()) { | 268 | 23 | if (RetVal->getType()->isPointerTy()23 ) { | 269 | 23 | addNode(RetVal); | 270 | 23 | ReturnValues.push_back(RetVal); | 271 | 23 | } | 272 | 23 | } | 273 | 95 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitReturnInst(llvm::ReturnInst&) Line | Count | Source | 266 | 115 | void visitReturnInst(ReturnInst &Inst) { | 267 | 115 | if (auto RetVal115 = Inst.getReturnValue()) { | 268 | 28 | if (RetVal->getType()->isPointerTy()28 ) { | 269 | 24 | addNode(RetVal); | 270 | 24 | ReturnValues.push_back(RetVal); | 271 | 24 | } | 272 | 28 | } | 273 | 115 | } |
|
274 | | |
275 | 11 | void visitPtrToIntInst(PtrToIntInst &Inst) { |
276 | 11 | auto *Ptr = Inst.getOperand(0); |
277 | 11 | addNode(Ptr, getAttrEscaped()); |
278 | 11 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitPtrToIntInst(llvm::PtrToIntInst&) Line | Count | Source | 275 | 6 | void visitPtrToIntInst(PtrToIntInst &Inst) { | 276 | 6 | auto *Ptr = Inst.getOperand(0); | 277 | 6 | addNode(Ptr, getAttrEscaped()); | 278 | 6 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitPtrToIntInst(llvm::PtrToIntInst&) Line | Count | Source | 275 | 5 | void visitPtrToIntInst(PtrToIntInst &Inst) { | 276 | 5 | auto *Ptr = Inst.getOperand(0); | 277 | 5 | addNode(Ptr, getAttrEscaped()); | 278 | 5 | } |
|
279 | | |
280 | 7 | void visitIntToPtrInst(IntToPtrInst &Inst) { |
281 | 7 | auto *Ptr = &Inst; |
282 | 7 | addNode(Ptr, getAttrUnknown()); |
283 | 7 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitIntToPtrInst(llvm::IntToPtrInst&) Line | Count | Source | 280 | 4 | void visitIntToPtrInst(IntToPtrInst &Inst) { | 281 | 4 | auto *Ptr = &Inst; | 282 | 4 | addNode(Ptr, getAttrUnknown()); | 283 | 4 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitIntToPtrInst(llvm::IntToPtrInst&) Line | Count | Source | 280 | 3 | void visitIntToPtrInst(IntToPtrInst &Inst) { | 281 | 3 | auto *Ptr = &Inst; | 282 | 3 | addNode(Ptr, getAttrUnknown()); | 283 | 3 | } |
|
284 | | |
285 | 51 | void visitCastInst(CastInst &Inst) { |
286 | 51 | auto *Src = Inst.getOperand(0); |
287 | 51 | addAssignEdge(Src, &Inst); |
288 | 51 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitCastInst(llvm::CastInst&) Line | Count | Source | 285 | 27 | void visitCastInst(CastInst &Inst) { | 286 | 27 | auto *Src = Inst.getOperand(0); | 287 | 27 | addAssignEdge(Src, &Inst); | 288 | 27 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitCastInst(llvm::CastInst&) Line | Count | Source | 285 | 24 | void visitCastInst(CastInst &Inst) { | 286 | 24 | auto *Src = Inst.getOperand(0); | 287 | 24 | addAssignEdge(Src, &Inst); | 288 | 24 | } |
|
289 | | |
290 | 11 | void visitBinaryOperator(BinaryOperator &Inst) { |
291 | 11 | auto *Op1 = Inst.getOperand(0); |
292 | 11 | auto *Op2 = Inst.getOperand(1); |
293 | 11 | addAssignEdge(Op1, &Inst); |
294 | 11 | addAssignEdge(Op2, &Inst); |
295 | 11 | } Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitBinaryOperator(llvm::BinaryOperator&) llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitBinaryOperator(llvm::BinaryOperator&) Line | Count | Source | 290 | 11 | void visitBinaryOperator(BinaryOperator &Inst) { | 291 | 11 | auto *Op1 = Inst.getOperand(0); | 292 | 11 | auto *Op2 = Inst.getOperand(1); | 293 | 11 | addAssignEdge(Op1, &Inst); | 294 | 11 | addAssignEdge(Op2, &Inst); | 295 | 11 | } |
|
296 | | |
297 | 0 | void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) { |
298 | 0 | auto *Ptr = Inst.getPointerOperand(); |
299 | 0 | auto *Val = Inst.getNewValOperand(); |
300 | 0 | addStoreEdge(Val, Ptr); |
301 | 0 | } Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitAtomicCmpXchgInst(llvm::AtomicCmpXchgInst&) Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitAtomicCmpXchgInst(llvm::AtomicCmpXchgInst&) |
302 | | |
303 | 0 | void visitAtomicRMWInst(AtomicRMWInst &Inst) { |
304 | 0 | auto *Ptr = Inst.getPointerOperand(); |
305 | 0 | auto *Val = Inst.getValOperand(); |
306 | 0 | addStoreEdge(Val, Ptr); |
307 | 0 | } Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitAtomicRMWInst(llvm::AtomicRMWInst&) Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitAtomicRMWInst(llvm::AtomicRMWInst&) |
308 | | |
309 | 4 | void visitPHINode(PHINode &Inst) { |
310 | 4 | for (Value *Val : Inst.incoming_values()) |
311 | 8 | addAssignEdge(Val, &Inst); |
312 | 4 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitPHINode(llvm::PHINode&) Line | Count | Source | 309 | 4 | void visitPHINode(PHINode &Inst) { | 310 | 4 | for (Value *Val : Inst.incoming_values()) | 311 | 8 | addAssignEdge(Val, &Inst); | 312 | 4 | } |
Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitPHINode(llvm::PHINode&) |
313 | | |
314 | 26 | void visitGEP(GEPOperator &GEPOp) { |
315 | 26 | uint64_t Offset = UnknownOffset; |
316 | 26 | APInt APOffset(DL.getPointerSizeInBits(GEPOp.getPointerAddressSpace()), |
317 | 26 | 0); |
318 | 26 | if (GEPOp.accumulateConstantOffset(DL, APOffset)) |
319 | 19 | Offset = APOffset.getSExtValue(); |
320 | 26 | |
321 | 26 | auto *Op = GEPOp.getPointerOperand(); |
322 | 26 | addAssignEdge(Op, &GEPOp, Offset); |
323 | 26 | } Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitGEP(llvm::GEPOperator&) llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitGEP(llvm::GEPOperator&) Line | Count | Source | 314 | 26 | void visitGEP(GEPOperator &GEPOp) { | 315 | 26 | uint64_t Offset = UnknownOffset; | 316 | 26 | APInt APOffset(DL.getPointerSizeInBits(GEPOp.getPointerAddressSpace()), | 317 | 26 | 0); | 318 | 26 | if (GEPOp.accumulateConstantOffset(DL, APOffset)) | 319 | 19 | Offset = APOffset.getSExtValue(); | 320 | 26 | | 321 | 26 | auto *Op = GEPOp.getPointerOperand(); | 322 | 26 | addAssignEdge(Op, &GEPOp, Offset); | 323 | 26 | } |
|
324 | | |
325 | 21 | void visitGetElementPtrInst(GetElementPtrInst &Inst) { |
326 | 21 | auto *GEPOp = cast<GEPOperator>(&Inst); |
327 | 21 | visitGEP(*GEPOp); |
328 | 21 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitGetElementPtrInst(llvm::GetElementPtrInst&) Line | Count | Source | 325 | 21 | void visitGetElementPtrInst(GetElementPtrInst &Inst) { | 326 | 21 | auto *GEPOp = cast<GEPOperator>(&Inst); | 327 | 21 | visitGEP(*GEPOp); | 328 | 21 | } |
Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitGetElementPtrInst(llvm::GetElementPtrInst&) |
329 | | |
330 | 19 | void visitSelectInst(SelectInst &Inst) { |
331 | 19 | // Condition is not processed here (The actual statement producing |
332 | 19 | // the condition result is processed elsewhere). For select, the |
333 | 19 | // condition is evaluated, but not loaded, stored, or assigned |
334 | 19 | // simply as a result of being the condition of a select. |
335 | 19 | |
336 | 19 | auto *TrueVal = Inst.getTrueValue(); |
337 | 19 | auto *FalseVal = Inst.getFalseValue(); |
338 | 19 | addAssignEdge(TrueVal, &Inst); |
339 | 19 | addAssignEdge(FalseVal, &Inst); |
340 | 19 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitSelectInst(llvm::SelectInst&) Line | Count | Source | 330 | 6 | void visitSelectInst(SelectInst &Inst) { | 331 | 6 | // Condition is not processed here (The actual statement producing | 332 | 6 | // the condition result is processed elsewhere). For select, the | 333 | 6 | // condition is evaluated, but not loaded, stored, or assigned | 334 | 6 | // simply as a result of being the condition of a select. | 335 | 6 | | 336 | 6 | auto *TrueVal = Inst.getTrueValue(); | 337 | 6 | auto *FalseVal = Inst.getFalseValue(); | 338 | 6 | addAssignEdge(TrueVal, &Inst); | 339 | 6 | addAssignEdge(FalseVal, &Inst); | 340 | 6 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitSelectInst(llvm::SelectInst&) Line | Count | Source | 330 | 13 | void visitSelectInst(SelectInst &Inst) { | 331 | 13 | // Condition is not processed here (The actual statement producing | 332 | 13 | // the condition result is processed elsewhere). For select, the | 333 | 13 | // condition is evaluated, but not loaded, stored, or assigned | 334 | 13 | // simply as a result of being the condition of a select. | 335 | 13 | | 336 | 13 | auto *TrueVal = Inst.getTrueValue(); | 337 | 13 | auto *FalseVal = Inst.getFalseValue(); | 338 | 13 | addAssignEdge(TrueVal, &Inst); | 339 | 13 | addAssignEdge(FalseVal, &Inst); | 340 | 13 | } |
|
341 | | |
342 | 252 | void visitAllocaInst(AllocaInst &Inst) { addNode(&Inst); } llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitAllocaInst(llvm::AllocaInst&) Line | Count | Source | 342 | 127 | void visitAllocaInst(AllocaInst &Inst) { addNode(&Inst); } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitAllocaInst(llvm::AllocaInst&) Line | Count | Source | 342 | 125 | void visitAllocaInst(AllocaInst &Inst) { addNode(&Inst); } |
|
343 | | |
344 | 162 | void visitLoadInst(LoadInst &Inst) { |
345 | 162 | auto *Ptr = Inst.getPointerOperand(); |
346 | 162 | auto *Val = &Inst; |
347 | 162 | addLoadEdge(Ptr, Val); |
348 | 162 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitLoadInst(llvm::LoadInst&) Line | Count | Source | 344 | 83 | void visitLoadInst(LoadInst &Inst) { | 345 | 83 | auto *Ptr = Inst.getPointerOperand(); | 346 | 83 | auto *Val = &Inst; | 347 | 83 | addLoadEdge(Ptr, Val); | 348 | 83 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitLoadInst(llvm::LoadInst&) Line | Count | Source | 344 | 79 | void visitLoadInst(LoadInst &Inst) { | 345 | 79 | auto *Ptr = Inst.getPointerOperand(); | 346 | 79 | auto *Val = &Inst; | 347 | 79 | addLoadEdge(Ptr, Val); | 348 | 79 | } |
|
349 | | |
350 | 153 | void visitStoreInst(StoreInst &Inst) { |
351 | 153 | auto *Ptr = Inst.getPointerOperand(); |
352 | 153 | auto *Val = Inst.getValueOperand(); |
353 | 153 | addStoreEdge(Val, Ptr); |
354 | 153 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitStoreInst(llvm::StoreInst&) Line | Count | Source | 350 | 67 | void visitStoreInst(StoreInst &Inst) { | 351 | 67 | auto *Ptr = Inst.getPointerOperand(); | 352 | 67 | auto *Val = Inst.getValueOperand(); | 353 | 67 | addStoreEdge(Val, Ptr); | 354 | 67 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitStoreInst(llvm::StoreInst&) Line | Count | Source | 350 | 86 | void visitStoreInst(StoreInst &Inst) { | 351 | 86 | auto *Ptr = Inst.getPointerOperand(); | 352 | 86 | auto *Val = Inst.getValueOperand(); | 353 | 86 | addStoreEdge(Val, Ptr); | 354 | 86 | } |
|
355 | | |
356 | 1 | void visitVAArgInst(VAArgInst &Inst) { |
357 | 1 | // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it |
358 | 1 | // does |
359 | 1 | // two things: |
360 | 1 | // 1. Loads a value from *((T*)*Ptr). |
361 | 1 | // 2. Increments (stores to) *Ptr by some target-specific amount. |
362 | 1 | // For now, we'll handle this like a landingpad instruction (by placing |
363 | 1 | // the |
364 | 1 | // result in its own group, and having that group alias externals). |
365 | 1 | if (Inst.getType()->isPointerTy()) |
366 | 1 | addNode(&Inst, getAttrUnknown()); |
367 | 1 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitVAArgInst(llvm::VAArgInst&) Line | Count | Source | 356 | 1 | void visitVAArgInst(VAArgInst &Inst) { | 357 | 1 | // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it | 358 | 1 | // does | 359 | 1 | // two things: | 360 | 1 | // 1. Loads a value from *((T*)*Ptr). | 361 | 1 | // 2. Increments (stores to) *Ptr by some target-specific amount. | 362 | 1 | // For now, we'll handle this like a landingpad instruction (by placing | 363 | 1 | // the | 364 | 1 | // result in its own group, and having that group alias externals). | 365 | 1 | if (Inst.getType()->isPointerTy()) | 366 | 1 | addNode(&Inst, getAttrUnknown()); | 367 | 1 | } |
Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitVAArgInst(llvm::VAArgInst&) |
368 | | |
369 | 106 | static bool isFunctionExternal(Function *Fn) { |
370 | 106 | return !Fn->hasExactDefinition(); |
371 | 106 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::isFunctionExternal(llvm::Function*) Line | Count | Source | 369 | 56 | static bool isFunctionExternal(Function *Fn) { | 370 | 56 | return !Fn->hasExactDefinition(); | 371 | 56 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::isFunctionExternal(llvm::Function*) Line | Count | Source | 369 | 50 | static bool isFunctionExternal(Function *Fn) { | 370 | 50 | return !Fn->hasExactDefinition(); | 371 | 50 | } |
|
372 | | |
373 | | bool tryInterproceduralAnalysis(CallSite CS, |
374 | 106 | const SmallVectorImpl<Function *> &Fns) { |
375 | 106 | assert(Fns.size() > 0); |
376 | 106 | |
377 | 106 | if (CS.arg_size() > MaxSupportedArgsInSummary) |
378 | 0 | return false; |
379 | 106 | |
380 | 106 | // Exit early if we'll fail anyway |
381 | 106 | for (auto *Fn : Fns) 106 { |
382 | 106 | if (isFunctionExternal(Fn) || 106 Fn->isVarArg()64 ) |
383 | 42 | return false; |
384 | 106 | // Fail if the caller does not provide enough arguments |
385 | 64 | assert(Fn->arg_size() <= CS.arg_size()); |
386 | 64 | if (!AA.getAliasSummary(*Fn)) |
387 | 0 | return false; |
388 | 106 | } |
389 | 106 | |
390 | 64 | for (auto *Fn : Fns) 64 { |
391 | 64 | auto Summary = AA.getAliasSummary(*Fn); |
392 | 64 | assert(Summary != nullptr); |
393 | 64 | |
394 | 64 | auto &RetParamRelations = Summary->RetParamRelations; |
395 | 28 | for (auto &Relation : RetParamRelations) { |
396 | 28 | auto IRelation = instantiateExternalRelation(Relation, CS); |
397 | 28 | if (IRelation.hasValue()28 ) { |
398 | 28 | Graph.addNode(IRelation->From); |
399 | 28 | Graph.addNode(IRelation->To); |
400 | 28 | Graph.addEdge(IRelation->From, IRelation->To); |
401 | 28 | } |
402 | 28 | } |
403 | 64 | |
404 | 64 | auto &RetParamAttributes = Summary->RetParamAttributes; |
405 | 60 | for (auto &Attribute : RetParamAttributes) { |
406 | 60 | auto IAttr = instantiateExternalAttribute(Attribute, CS); |
407 | 60 | if (IAttr.hasValue()) |
408 | 60 | Graph.addNode(IAttr->IValue, IAttr->Attr); |
409 | 60 | } |
410 | 64 | } |
411 | 64 | |
412 | 64 | return true; |
413 | 106 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::tryInterproceduralAnalysis(llvm::CallSite, llvm::SmallVectorImpl<llvm::Function*> const&) Line | Count | Source | 374 | 50 | const SmallVectorImpl<Function *> &Fns) { | 375 | 50 | assert(Fns.size() > 0); | 376 | 50 | | 377 | 50 | if (CS.arg_size() > MaxSupportedArgsInSummary) | 378 | 0 | return false; | 379 | 50 | | 380 | 50 | // Exit early if we'll fail anyway | 381 | 50 | for (auto *Fn : Fns) 50 { | 382 | 50 | if (isFunctionExternal(Fn) || 50 Fn->isVarArg()32 ) | 383 | 18 | return false; | 384 | 50 | // Fail if the caller does not provide enough arguments | 385 | 32 | assert(Fn->arg_size() <= CS.arg_size()); | 386 | 32 | if (!AA.getAliasSummary(*Fn)) | 387 | 0 | return false; | 388 | 50 | } | 389 | 50 | | 390 | 32 | for (auto *Fn : Fns) 32 { | 391 | 32 | auto Summary = AA.getAliasSummary(*Fn); | 392 | 32 | assert(Summary != nullptr); | 393 | 32 | | 394 | 32 | auto &RetParamRelations = Summary->RetParamRelations; | 395 | 14 | for (auto &Relation : RetParamRelations) { | 396 | 14 | auto IRelation = instantiateExternalRelation(Relation, CS); | 397 | 14 | if (IRelation.hasValue()14 ) { | 398 | 14 | Graph.addNode(IRelation->From); | 399 | 14 | Graph.addNode(IRelation->To); | 400 | 14 | Graph.addEdge(IRelation->From, IRelation->To); | 401 | 14 | } | 402 | 14 | } | 403 | 32 | | 404 | 32 | auto &RetParamAttributes = Summary->RetParamAttributes; | 405 | 28 | for (auto &Attribute : RetParamAttributes) { | 406 | 28 | auto IAttr = instantiateExternalAttribute(Attribute, CS); | 407 | 28 | if (IAttr.hasValue()) | 408 | 28 | Graph.addNode(IAttr->IValue, IAttr->Attr); | 409 | 28 | } | 410 | 32 | } | 411 | 32 | | 412 | 32 | return true; | 413 | 50 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::tryInterproceduralAnalysis(llvm::CallSite, llvm::SmallVectorImpl<llvm::Function*> const&) Line | Count | Source | 374 | 56 | const SmallVectorImpl<Function *> &Fns) { | 375 | 56 | assert(Fns.size() > 0); | 376 | 56 | | 377 | 56 | if (CS.arg_size() > MaxSupportedArgsInSummary) | 378 | 0 | return false; | 379 | 56 | | 380 | 56 | // Exit early if we'll fail anyway | 381 | 56 | for (auto *Fn : Fns) 56 { | 382 | 56 | if (isFunctionExternal(Fn) || 56 Fn->isVarArg()32 ) | 383 | 24 | return false; | 384 | 56 | // Fail if the caller does not provide enough arguments | 385 | 32 | assert(Fn->arg_size() <= CS.arg_size()); | 386 | 32 | if (!AA.getAliasSummary(*Fn)) | 387 | 0 | return false; | 388 | 56 | } | 389 | 56 | | 390 | 32 | for (auto *Fn : Fns) 32 { | 391 | 32 | auto Summary = AA.getAliasSummary(*Fn); | 392 | 32 | assert(Summary != nullptr); | 393 | 32 | | 394 | 32 | auto &RetParamRelations = Summary->RetParamRelations; | 395 | 14 | for (auto &Relation : RetParamRelations) { | 396 | 14 | auto IRelation = instantiateExternalRelation(Relation, CS); | 397 | 14 | if (IRelation.hasValue()14 ) { | 398 | 14 | Graph.addNode(IRelation->From); | 399 | 14 | Graph.addNode(IRelation->To); | 400 | 14 | Graph.addEdge(IRelation->From, IRelation->To); | 401 | 14 | } | 402 | 14 | } | 403 | 32 | | 404 | 32 | auto &RetParamAttributes = Summary->RetParamAttributes; | 405 | 32 | for (auto &Attribute : RetParamAttributes) { | 406 | 32 | auto IAttr = instantiateExternalAttribute(Attribute, CS); | 407 | 32 | if (IAttr.hasValue()) | 408 | 32 | Graph.addNode(IAttr->IValue, IAttr->Attr); | 409 | 32 | } | 410 | 32 | } | 411 | 32 | | 412 | 32 | return true; | 413 | 56 | } |
|
414 | | |
415 | 143 | void visitCallSite(CallSite CS) { |
416 | 143 | auto Inst = CS.getInstruction(); |
417 | 143 | |
418 | 143 | // Make sure all arguments and return value are added to the graph first |
419 | 143 | for (Value *V : CS.args()) |
420 | 153 | if (153 V->getType()->isPointerTy()153 ) |
421 | 117 | addNode(V); |
422 | 143 | if (Inst->getType()->isPointerTy()) |
423 | 80 | addNode(Inst); |
424 | 143 | |
425 | 143 | // Check if Inst is a call to a library function that |
426 | 143 | // allocates/deallocates |
427 | 143 | // on the heap. Those kinds of functions do not introduce any aliases. |
428 | 143 | // TODO: address other common library functions such as realloc(), |
429 | 143 | // strdup(), |
430 | 143 | // etc. |
431 | 143 | if (isMallocOrCallocLikeFn(Inst, &TLI) || 143 isFreeCall(Inst, &TLI)109 ) |
432 | 36 | return; |
433 | 143 | |
434 | 143 | // TODO: Add support for noalias args/all the other fun function |
435 | 143 | // attributes |
436 | 143 | // that we can tack on. |
437 | 107 | SmallVector<Function *, 4> Targets; |
438 | 107 | if (getPossibleTargets(CS, Targets)) |
439 | 106 | if (106 tryInterproceduralAnalysis(CS, Targets)106 ) |
440 | 64 | return; |
441 | 107 | |
442 | 107 | // Because the function is opaque, we need to note that anything |
443 | 107 | // could have happened to the arguments (unless the function is marked |
444 | 107 | // readonly or readnone), and that the result could alias just about |
445 | 107 | // anything, too (unless the result is marked noalias). |
446 | 43 | if (43 !CS.onlyReadsMemory()43 ) |
447 | 35 | for (Value *V : CS.args()) 35 { |
448 | 35 | if (V->getType()->isPointerTy()35 ) { |
449 | 35 | // The argument itself escapes. |
450 | 35 | Graph.addAttr(InstantiatedValue{V, 0}, getAttrEscaped()); |
451 | 35 | // The fate of argument memory is unknown. Note that since |
452 | 35 | // AliasAttrs is transitive with respect to dereference, we only |
453 | 35 | // need to specify it for the first-level memory. |
454 | 35 | Graph.addNode(InstantiatedValue{V, 1}, getAttrUnknown()); |
455 | 35 | } |
456 | 35 | } |
457 | 43 | |
458 | 43 | if (Inst->getType()->isPointerTy()43 ) { |
459 | 10 | auto *Fn = CS.getCalledFunction(); |
460 | 10 | if (Fn == nullptr || 10 !Fn->returnDoesNotAlias()9 ) |
461 | 10 | // No need to call addNode() since we've added Inst at the |
462 | 10 | // beginning of this function and we know it is not a global. |
463 | 6 | Graph.addAttr(InstantiatedValue{Inst, 0}, getAttrUnknown()); |
464 | 10 | } |
465 | 143 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitCallSite(llvm::CallSite) Line | Count | Source | 415 | 78 | void visitCallSite(CallSite CS) { | 416 | 78 | auto Inst = CS.getInstruction(); | 417 | 78 | | 418 | 78 | // Make sure all arguments and return value are added to the graph first | 419 | 78 | for (Value *V : CS.args()) | 420 | 84 | if (84 V->getType()->isPointerTy()84 ) | 421 | 63 | addNode(V); | 422 | 78 | if (Inst->getType()->isPointerTy()) | 423 | 43 | addNode(Inst); | 424 | 78 | | 425 | 78 | // Check if Inst is a call to a library function that | 426 | 78 | // allocates/deallocates | 427 | 78 | // on the heap. Those kinds of functions do not introduce any aliases. | 428 | 78 | // TODO: address other common library functions such as realloc(), | 429 | 78 | // strdup(), | 430 | 78 | // etc. | 431 | 78 | if (isMallocOrCallocLikeFn(Inst, &TLI) || 78 isFreeCall(Inst, &TLI)59 ) | 432 | 21 | return; | 433 | 78 | | 434 | 78 | // TODO: Add support for noalias args/all the other fun function | 435 | 78 | // attributes | 436 | 78 | // that we can tack on. | 437 | 57 | SmallVector<Function *, 4> Targets; | 438 | 57 | if (getPossibleTargets(CS, Targets)) | 439 | 56 | if (56 tryInterproceduralAnalysis(CS, Targets)56 ) | 440 | 32 | return; | 441 | 57 | | 442 | 57 | // Because the function is opaque, we need to note that anything | 443 | 57 | // could have happened to the arguments (unless the function is marked | 444 | 57 | // readonly or readnone), and that the result could alias just about | 445 | 57 | // anything, too (unless the result is marked noalias). | 446 | 25 | if (25 !CS.onlyReadsMemory()25 ) | 447 | 21 | for (Value *V : CS.args()) 21 { | 448 | 21 | if (V->getType()->isPointerTy()21 ) { | 449 | 21 | // The argument itself escapes. | 450 | 21 | Graph.addAttr(InstantiatedValue{V, 0}, getAttrEscaped()); | 451 | 21 | // The fate of argument memory is unknown. Note that since | 452 | 21 | // AliasAttrs is transitive with respect to dereference, we only | 453 | 21 | // need to specify it for the first-level memory. | 454 | 21 | Graph.addNode(InstantiatedValue{V, 1}, getAttrUnknown()); | 455 | 21 | } | 456 | 21 | } | 457 | 25 | | 458 | 25 | if (Inst->getType()->isPointerTy()25 ) { | 459 | 6 | auto *Fn = CS.getCalledFunction(); | 460 | 6 | if (Fn == nullptr || 6 !Fn->returnDoesNotAlias()5 ) | 461 | 6 | // No need to call addNode() since we've added Inst at the | 462 | 6 | // beginning of this function and we know it is not a global. | 463 | 4 | Graph.addAttr(InstantiatedValue{Inst, 0}, getAttrUnknown()); | 464 | 6 | } | 465 | 78 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitCallSite(llvm::CallSite) Line | Count | Source | 415 | 65 | void visitCallSite(CallSite CS) { | 416 | 65 | auto Inst = CS.getInstruction(); | 417 | 65 | | 418 | 65 | // Make sure all arguments and return value are added to the graph first | 419 | 65 | for (Value *V : CS.args()) | 420 | 69 | if (69 V->getType()->isPointerTy()69 ) | 421 | 54 | addNode(V); | 422 | 65 | if (Inst->getType()->isPointerTy()) | 423 | 37 | addNode(Inst); | 424 | 65 | | 425 | 65 | // Check if Inst is a call to a library function that | 426 | 65 | // allocates/deallocates | 427 | 65 | // on the heap. Those kinds of functions do not introduce any aliases. | 428 | 65 | // TODO: address other common library functions such as realloc(), | 429 | 65 | // strdup(), | 430 | 65 | // etc. | 431 | 65 | if (isMallocOrCallocLikeFn(Inst, &TLI) || 65 isFreeCall(Inst, &TLI)50 ) | 432 | 15 | return; | 433 | 65 | | 434 | 65 | // TODO: Add support for noalias args/all the other fun function | 435 | 65 | // attributes | 436 | 65 | // that we can tack on. | 437 | 50 | SmallVector<Function *, 4> Targets; | 438 | 50 | if (getPossibleTargets(CS, Targets)) | 439 | 50 | if (50 tryInterproceduralAnalysis(CS, Targets)50 ) | 440 | 32 | return; | 441 | 50 | | 442 | 50 | // Because the function is opaque, we need to note that anything | 443 | 50 | // could have happened to the arguments (unless the function is marked | 444 | 50 | // readonly or readnone), and that the result could alias just about | 445 | 50 | // anything, too (unless the result is marked noalias). | 446 | 18 | if (18 !CS.onlyReadsMemory()18 ) | 447 | 14 | for (Value *V : CS.args()) 14 { | 448 | 14 | if (V->getType()->isPointerTy()14 ) { | 449 | 14 | // The argument itself escapes. | 450 | 14 | Graph.addAttr(InstantiatedValue{V, 0}, getAttrEscaped()); | 451 | 14 | // The fate of argument memory is unknown. Note that since | 452 | 14 | // AliasAttrs is transitive with respect to dereference, we only | 453 | 14 | // need to specify it for the first-level memory. | 454 | 14 | Graph.addNode(InstantiatedValue{V, 1}, getAttrUnknown()); | 455 | 14 | } | 456 | 14 | } | 457 | 18 | | 458 | 18 | if (Inst->getType()->isPointerTy()18 ) { | 459 | 4 | auto *Fn = CS.getCalledFunction(); | 460 | 4 | if (Fn == nullptr || 4 !Fn->returnDoesNotAlias()4 ) | 461 | 4 | // No need to call addNode() since we've added Inst at the | 462 | 4 | // beginning of this function and we know it is not a global. | 463 | 2 | Graph.addAttr(InstantiatedValue{Inst, 0}, getAttrUnknown()); | 464 | 4 | } | 465 | 65 | } |
|
466 | | |
467 | | /// Because vectors/aggregates are immutable and unaddressable, there's |
468 | | /// nothing we can do to coax a value out of them, other than calling |
469 | | /// Extract{Element,Value}. We can effectively treat them as pointers to |
470 | | /// arbitrary memory locations we can store in and load from. |
471 | 0 | void visitExtractElementInst(ExtractElementInst &Inst) { |
472 | 0 | auto *Ptr = Inst.getVectorOperand(); |
473 | 0 | auto *Val = &Inst; |
474 | 0 | addLoadEdge(Ptr, Val); |
475 | 0 | } Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitExtractElementInst(llvm::ExtractElementInst&) Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitExtractElementInst(llvm::ExtractElementInst&) |
476 | | |
477 | 0 | void visitInsertElementInst(InsertElementInst &Inst) { |
478 | 0 | auto *Vec = Inst.getOperand(0); |
479 | 0 | auto *Val = Inst.getOperand(1); |
480 | 0 | addAssignEdge(Vec, &Inst); |
481 | 0 | addStoreEdge(Val, &Inst); |
482 | 0 | } Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitInsertElementInst(llvm::InsertElementInst&) Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitInsertElementInst(llvm::InsertElementInst&) |
483 | | |
484 | 0 | void visitLandingPadInst(LandingPadInst &Inst) { |
485 | 0 | // Exceptions come from "nowhere", from our analysis' perspective. |
486 | 0 | // So we place the instruction its own group, noting that said group may |
487 | 0 | // alias externals |
488 | 0 | if (Inst.getType()->isPointerTy()) |
489 | 0 | addNode(&Inst, getAttrUnknown()); |
490 | 0 | } Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitLandingPadInst(llvm::LandingPadInst&) Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitLandingPadInst(llvm::LandingPadInst&) |
491 | | |
492 | 0 | void visitInsertValueInst(InsertValueInst &Inst) { |
493 | 0 | auto *Agg = Inst.getOperand(0); |
494 | 0 | auto *Val = Inst.getOperand(1); |
495 | 0 | addAssignEdge(Agg, &Inst); |
496 | 0 | addStoreEdge(Val, &Inst); |
497 | 0 | } Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitInsertValueInst(llvm::InsertValueInst&) Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitInsertValueInst(llvm::InsertValueInst&) |
498 | | |
499 | 1 | void visitExtractValueInst(ExtractValueInst &Inst) { |
500 | 1 | auto *Ptr = Inst.getAggregateOperand(); |
501 | 1 | addLoadEdge(Ptr, &Inst); |
502 | 1 | } Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitExtractValueInst(llvm::ExtractValueInst&) llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitExtractValueInst(llvm::ExtractValueInst&) Line | Count | Source | 499 | 1 | void visitExtractValueInst(ExtractValueInst &Inst) { | 500 | 1 | auto *Ptr = Inst.getAggregateOperand(); | 501 | 1 | addLoadEdge(Ptr, &Inst); | 502 | 1 | } |
|
503 | | |
504 | 0 | void visitShuffleVectorInst(ShuffleVectorInst &Inst) { |
505 | 0 | auto *From1 = Inst.getOperand(0); |
506 | 0 | auto *From2 = Inst.getOperand(1); |
507 | 0 | addAssignEdge(From1, &Inst); |
508 | 0 | addAssignEdge(From2, &Inst); |
509 | 0 | } Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitShuffleVectorInst(llvm::ShuffleVectorInst&) Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitShuffleVectorInst(llvm::ShuffleVectorInst&) |
510 | | |
511 | 5 | void visitConstantExpr(ConstantExpr *CE) { |
512 | 5 | switch (CE->getOpcode()) { |
513 | 5 | case Instruction::GetElementPtr: { |
514 | 5 | auto GEPOp = cast<GEPOperator>(CE); |
515 | 5 | visitGEP(*GEPOp); |
516 | 5 | break; |
517 | 5 | } |
518 | 0 | case Instruction::PtrToInt: { |
519 | 0 | auto *Ptr = CE->getOperand(0); |
520 | 0 | addNode(Ptr, getAttrEscaped()); |
521 | 0 | break; |
522 | 5 | } |
523 | 0 | case Instruction::IntToPtr: |
524 | 0 | addNode(CE, getAttrUnknown()); |
525 | 0 | break; |
526 | 5 | |
527 | 0 | case Instruction::BitCast: |
528 | 0 | case Instruction::AddrSpaceCast: |
529 | 0 | case Instruction::Trunc: |
530 | 0 | case Instruction::ZExt: |
531 | 0 | case Instruction::SExt: |
532 | 0 | case Instruction::FPExt: |
533 | 0 | case Instruction::FPTrunc: |
534 | 0 | case Instruction::UIToFP: |
535 | 0 | case Instruction::SIToFP: |
536 | 0 | case Instruction::FPToUI: |
537 | 0 | case Instruction::FPToSI: { |
538 | 0 | auto *Src = CE->getOperand(0); |
539 | 0 | addAssignEdge(Src, CE); |
540 | 0 | break; |
541 | 0 | } |
542 | 0 | case Instruction::Select: { |
543 | 0 | auto *TrueVal = CE->getOperand(0); |
544 | 0 | auto *FalseVal = CE->getOperand(1); |
545 | 0 | addAssignEdge(TrueVal, CE); |
546 | 0 | addAssignEdge(FalseVal, CE); |
547 | 0 | break; |
548 | 0 | } |
549 | 0 | case Instruction::InsertElement: { |
550 | 0 | auto *Vec = CE->getOperand(0); |
551 | 0 | auto *Val = CE->getOperand(1); |
552 | 0 | addAssignEdge(Vec, CE); |
553 | 0 | addStoreEdge(Val, CE); |
554 | 0 | break; |
555 | 0 | } |
556 | 0 | case Instruction::ExtractElement: { |
557 | 0 | auto *Ptr = CE->getOperand(0); |
558 | 0 | addLoadEdge(Ptr, CE); |
559 | 0 | break; |
560 | 0 | } |
561 | 0 | case Instruction::InsertValue: { |
562 | 0 | auto *Agg = CE->getOperand(0); |
563 | 0 | auto *Val = CE->getOperand(1); |
564 | 0 | addAssignEdge(Agg, CE); |
565 | 0 | addStoreEdge(Val, CE); |
566 | 0 | break; |
567 | 0 | } |
568 | 0 | case Instruction::ExtractValue: { |
569 | 0 | auto *Ptr = CE->getOperand(0); |
570 | 0 | addLoadEdge(Ptr, CE); |
571 | 0 | break; |
572 | 0 | } |
573 | 0 | case Instruction::ShuffleVector: { |
574 | 0 | auto *From1 = CE->getOperand(0); |
575 | 0 | auto *From2 = CE->getOperand(1); |
576 | 0 | addAssignEdge(From1, CE); |
577 | 0 | addAssignEdge(From2, CE); |
578 | 0 | break; |
579 | 0 | } |
580 | 0 | case Instruction::Add: |
581 | 0 | case Instruction::Sub: |
582 | 0 | case Instruction::FSub: |
583 | 0 | case Instruction::Mul: |
584 | 0 | case Instruction::FMul: |
585 | 0 | case Instruction::UDiv: |
586 | 0 | case Instruction::SDiv: |
587 | 0 | case Instruction::FDiv: |
588 | 0 | case Instruction::URem: |
589 | 0 | case Instruction::SRem: |
590 | 0 | case Instruction::FRem: |
591 | 0 | case Instruction::And: |
592 | 0 | case Instruction::Or: |
593 | 0 | case Instruction::Xor: |
594 | 0 | case Instruction::Shl: |
595 | 0 | case Instruction::LShr: |
596 | 0 | case Instruction::AShr: |
597 | 0 | case Instruction::ICmp: |
598 | 0 | case Instruction::FCmp: |
599 | 0 | addAssignEdge(CE->getOperand(0), CE); |
600 | 0 | addAssignEdge(CE->getOperand(1), CE); |
601 | 0 | break; |
602 | 0 |
|
603 | 0 | default: |
604 | 0 | llvm_unreachable("Unknown instruction type encountered!"); |
605 | 5 | } |
606 | 5 | } Unexecuted instantiation: llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor::visitConstantExpr(llvm::ConstantExpr*) llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor::visitConstantExpr(llvm::ConstantExpr*) Line | Count | Source | 511 | 5 | void visitConstantExpr(ConstantExpr *CE) { | 512 | 5 | switch (CE->getOpcode()) { | 513 | 5 | case Instruction::GetElementPtr: { | 514 | 5 | auto GEPOp = cast<GEPOperator>(CE); | 515 | 5 | visitGEP(*GEPOp); | 516 | 5 | break; | 517 | 5 | } | 518 | 0 | case Instruction::PtrToInt: { | 519 | 0 | auto *Ptr = CE->getOperand(0); | 520 | 0 | addNode(Ptr, getAttrEscaped()); | 521 | 0 | break; | 522 | 5 | } | 523 | 0 | case Instruction::IntToPtr: | 524 | 0 | addNode(CE, getAttrUnknown()); | 525 | 0 | break; | 526 | 5 | | 527 | 0 | case Instruction::BitCast: | 528 | 0 | case Instruction::AddrSpaceCast: | 529 | 0 | case Instruction::Trunc: | 530 | 0 | case Instruction::ZExt: | 531 | 0 | case Instruction::SExt: | 532 | 0 | case Instruction::FPExt: | 533 | 0 | case Instruction::FPTrunc: | 534 | 0 | case Instruction::UIToFP: | 535 | 0 | case Instruction::SIToFP: | 536 | 0 | case Instruction::FPToUI: | 537 | 0 | case Instruction::FPToSI: { | 538 | 0 | auto *Src = CE->getOperand(0); | 539 | 0 | addAssignEdge(Src, CE); | 540 | 0 | break; | 541 | 0 | } | 542 | 0 | case Instruction::Select: { | 543 | 0 | auto *TrueVal = CE->getOperand(0); | 544 | 0 | auto *FalseVal = CE->getOperand(1); | 545 | 0 | addAssignEdge(TrueVal, CE); | 546 | 0 | addAssignEdge(FalseVal, CE); | 547 | 0 | break; | 548 | 0 | } | 549 | 0 | case Instruction::InsertElement: { | 550 | 0 | auto *Vec = CE->getOperand(0); | 551 | 0 | auto *Val = CE->getOperand(1); | 552 | 0 | addAssignEdge(Vec, CE); | 553 | 0 | addStoreEdge(Val, CE); | 554 | 0 | break; | 555 | 0 | } | 556 | 0 | case Instruction::ExtractElement: { | 557 | 0 | auto *Ptr = CE->getOperand(0); | 558 | 0 | addLoadEdge(Ptr, CE); | 559 | 0 | break; | 560 | 0 | } | 561 | 0 | case Instruction::InsertValue: { | 562 | 0 | auto *Agg = CE->getOperand(0); | 563 | 0 | auto *Val = CE->getOperand(1); | 564 | 0 | addAssignEdge(Agg, CE); | 565 | 0 | addStoreEdge(Val, CE); | 566 | 0 | break; | 567 | 0 | } | 568 | 0 | case Instruction::ExtractValue: { | 569 | 0 | auto *Ptr = CE->getOperand(0); | 570 | 0 | addLoadEdge(Ptr, CE); | 571 | 0 | break; | 572 | 0 | } | 573 | 0 | case Instruction::ShuffleVector: { | 574 | 0 | auto *From1 = CE->getOperand(0); | 575 | 0 | auto *From2 = CE->getOperand(1); | 576 | 0 | addAssignEdge(From1, CE); | 577 | 0 | addAssignEdge(From2, CE); | 578 | 0 | break; | 579 | 0 | } | 580 | 0 | case Instruction::Add: | 581 | 0 | case Instruction::Sub: | 582 | 0 | case Instruction::FSub: | 583 | 0 | case Instruction::Mul: | 584 | 0 | case Instruction::FMul: | 585 | 0 | case Instruction::UDiv: | 586 | 0 | case Instruction::SDiv: | 587 | 0 | case Instruction::FDiv: | 588 | 0 | case Instruction::URem: | 589 | 0 | case Instruction::SRem: | 590 | 0 | case Instruction::FRem: | 591 | 0 | case Instruction::And: | 592 | 0 | case Instruction::Or: | 593 | 0 | case Instruction::Xor: | 594 | 0 | case Instruction::Shl: | 595 | 0 | case Instruction::LShr: | 596 | 0 | case Instruction::AShr: | 597 | 0 | case Instruction::ICmp: | 598 | 0 | case Instruction::FCmp: | 599 | 0 | addAssignEdge(CE->getOperand(0), CE); | 600 | 0 | addAssignEdge(CE->getOperand(1), CE); | 601 | 0 | break; | 602 | 0 |
| 603 | 0 | default: | 604 | 0 | llvm_unreachable("Unknown instruction type encountered!"); | 605 | 5 | } | 606 | 5 | } |
|
607 | | }; |
608 | | |
609 | | // Helper functions |
610 | | |
611 | | // Determines whether or not we an instruction is useless to us (e.g. |
612 | | // FenceInst) |
613 | 1.06k | static bool hasUsefulEdges(Instruction *Inst) { |
614 | 1.06k | bool IsNonInvokeRetTerminator = isa<TerminatorInst>(Inst) && |
615 | 226 | !isa<InvokeInst>(Inst) && |
616 | 226 | !isa<ReturnInst>(Inst); |
617 | 1.06k | return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) && |
618 | 1.06k | !IsNonInvokeRetTerminator; |
619 | 1.06k | } llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::hasUsefulEdges(llvm::Instruction*) Line | Count | Source | 613 | 590 | static bool hasUsefulEdges(Instruction *Inst) { | 614 | 590 | bool IsNonInvokeRetTerminator = isa<TerminatorInst>(Inst) && | 615 | 131 | !isa<InvokeInst>(Inst) && | 616 | 131 | !isa<ReturnInst>(Inst); | 617 | 587 | return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) && | 618 | 587 | !IsNonInvokeRetTerminator; | 619 | 590 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::hasUsefulEdges(llvm::Instruction*) Line | Count | Source | 613 | 475 | static bool hasUsefulEdges(Instruction *Inst) { | 614 | 475 | bool IsNonInvokeRetTerminator = isa<TerminatorInst>(Inst) && | 615 | 95 | !isa<InvokeInst>(Inst) && | 616 | 95 | !isa<ReturnInst>(Inst); | 617 | 475 | return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) && | 618 | 475 | !IsNonInvokeRetTerminator; | 619 | 475 | } |
|
620 | | |
621 | 240 | void addArgumentToGraph(Argument &Arg) { |
622 | 240 | if (Arg.getType()->isPointerTy()240 ) { |
623 | 222 | Graph.addNode(InstantiatedValue{&Arg, 0}, |
624 | 222 | getGlobalOrArgAttrFromValue(Arg)); |
625 | 222 | // Pointees of a formal parameter is known to the caller |
626 | 222 | Graph.addNode(InstantiatedValue{&Arg, 1}, getAttrCaller()); |
627 | 222 | } |
628 | 240 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::addArgumentToGraph(llvm::Argument&) Line | Count | Source | 621 | 88 | void addArgumentToGraph(Argument &Arg) { | 622 | 88 | if (Arg.getType()->isPointerTy()88 ) { | 623 | 82 | Graph.addNode(InstantiatedValue{&Arg, 0}, | 624 | 82 | getGlobalOrArgAttrFromValue(Arg)); | 625 | 82 | // Pointees of a formal parameter is known to the caller | 626 | 82 | Graph.addNode(InstantiatedValue{&Arg, 1}, getAttrCaller()); | 627 | 82 | } | 628 | 88 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::addArgumentToGraph(llvm::Argument&) Line | Count | Source | 621 | 152 | void addArgumentToGraph(Argument &Arg) { | 622 | 152 | if (Arg.getType()->isPointerTy()152 ) { | 623 | 140 | Graph.addNode(InstantiatedValue{&Arg, 0}, | 624 | 140 | getGlobalOrArgAttrFromValue(Arg)); | 625 | 140 | // Pointees of a formal parameter is known to the caller | 626 | 140 | Graph.addNode(InstantiatedValue{&Arg, 1}, getAttrCaller()); | 627 | 140 | } | 628 | 152 | } |
|
629 | | |
630 | | // Given an Instruction, this will add it to the graph, along with any |
631 | | // Instructions that are potentially only available from said Instruction |
632 | | // For example, given the following line: |
633 | | // %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2 |
634 | | // addInstructionToGraph would add both the `load` and `getelementptr` |
635 | | // instructions to the graph appropriately. |
636 | 1.06k | void addInstructionToGraph(GetEdgesVisitor &Visitor, Instruction &Inst) { |
637 | 1.06k | if (!hasUsefulEdges(&Inst)) |
638 | 19 | return; |
639 | 1.06k | |
640 | 1.04k | Visitor.visit(Inst); |
641 | 1.04k | } llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::addInstructionToGraph(llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::GetEdgesVisitor&, llvm::Instruction&) Line | Count | Source | 636 | 590 | void addInstructionToGraph(GetEdgesVisitor &Visitor, Instruction &Inst) { | 637 | 590 | if (!hasUsefulEdges(&Inst)) | 638 | 19 | return; | 639 | 590 | | 640 | 571 | Visitor.visit(Inst); | 641 | 571 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::addInstructionToGraph(llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::GetEdgesVisitor&, llvm::Instruction&) Line | Count | Source | 636 | 475 | void addInstructionToGraph(GetEdgesVisitor &Visitor, Instruction &Inst) { | 637 | 475 | if (!hasUsefulEdges(&Inst)) | 638 | 0 | return; | 639 | 475 | | 640 | 475 | Visitor.visit(Inst); | 641 | 475 | } |
|
642 | | |
643 | | // Builds the graph needed for constructing the StratifiedSets for the given |
644 | | // function |
645 | 210 | void buildGraphFrom(Function &Fn) { |
646 | 210 | GetEdgesVisitor Visitor(*this, Fn.getParent()->getDataLayout()); |
647 | 210 | |
648 | 210 | for (auto &Bb : Fn.getBasicBlockList()) |
649 | 226 | for (auto &Inst : Bb.getInstList()) |
650 | 1.06k | addInstructionToGraph(Visitor, Inst); |
651 | 210 | |
652 | 210 | for (auto &Arg : Fn.args()) |
653 | 240 | addArgumentToGraph(Arg); |
654 | 210 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::buildGraphFrom(llvm::Function&) Line | Count | Source | 645 | 115 | void buildGraphFrom(Function &Fn) { | 646 | 115 | GetEdgesVisitor Visitor(*this, Fn.getParent()->getDataLayout()); | 647 | 115 | | 648 | 115 | for (auto &Bb : Fn.getBasicBlockList()) | 649 | 131 | for (auto &Inst : Bb.getInstList()) | 650 | 590 | addInstructionToGraph(Visitor, Inst); | 651 | 115 | | 652 | 115 | for (auto &Arg : Fn.args()) | 653 | 152 | addArgumentToGraph(Arg); | 654 | 115 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::buildGraphFrom(llvm::Function&) Line | Count | Source | 645 | 95 | void buildGraphFrom(Function &Fn) { | 646 | 95 | GetEdgesVisitor Visitor(*this, Fn.getParent()->getDataLayout()); | 647 | 95 | | 648 | 95 | for (auto &Bb : Fn.getBasicBlockList()) | 649 | 95 | for (auto &Inst : Bb.getInstList()) | 650 | 475 | addInstructionToGraph(Visitor, Inst); | 651 | 95 | | 652 | 95 | for (auto &Arg : Fn.args()) | 653 | 88 | addArgumentToGraph(Arg); | 654 | 95 | } |
|
655 | | |
656 | | public: |
657 | | CFLGraphBuilder(CFLAA &Analysis, const TargetLibraryInfo &TLI, Function &Fn) |
658 | 210 | : Analysis(Analysis), TLI(TLI) { |
659 | 210 | buildGraphFrom(Fn); |
660 | 210 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::CFLGraphBuilder(llvm::CFLSteensAAResult&, llvm::TargetLibraryInfo const&, llvm::Function&) Line | Count | Source | 658 | 115 | : Analysis(Analysis), TLI(TLI) { | 659 | 115 | buildGraphFrom(Fn); | 660 | 115 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::CFLGraphBuilder(llvm::CFLAndersAAResult&, llvm::TargetLibraryInfo const&, llvm::Function&) Line | Count | Source | 658 | 95 | : Analysis(Analysis), TLI(TLI) { | 659 | 95 | buildGraphFrom(Fn); | 660 | 95 | } |
|
661 | | |
662 | 210 | const CFLGraph &getCFLGraph() const { return Graph; } llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::getCFLGraph() const Line | Count | Source | 662 | 115 | const CFLGraph &getCFLGraph() const { return Graph; } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::getCFLGraph() const Line | Count | Source | 662 | 95 | const CFLGraph &getCFLGraph() const { return Graph; } |
|
663 | 210 | const SmallVector<Value *, 4> &getReturnValues() const { |
664 | 210 | return ReturnedValues; |
665 | 210 | } llvm::cflaa::CFLGraphBuilder<llvm::CFLAndersAAResult>::getReturnValues() const Line | Count | Source | 663 | 95 | const SmallVector<Value *, 4> &getReturnValues() const { | 664 | 95 | return ReturnedValues; | 665 | 95 | } |
llvm::cflaa::CFLGraphBuilder<llvm::CFLSteensAAResult>::getReturnValues() const Line | Count | Source | 663 | 115 | const SmallVector<Value *, 4> &getReturnValues() const { | 664 | 115 | return ReturnedValues; | 665 | 115 | } |
|
666 | | }; |
667 | | |
668 | | } // end namespace cflaa |
669 | | } // end namespace llvm |
670 | | |
671 | | #endif // LLVM_LIB_ANALYSIS_CFLGRAPH_H |