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