Line data Source code
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 : /// 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 116 : 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 918 : struct NodeInfo {
71 : EdgeList Edges, ReverseEdges;
72 : AliasAttrs Attr;
73 : };
74 :
75 835 : class ValueInfo {
76 : std::vector<NodeInfo> Levels;
77 :
78 : public:
79 : bool addNodeToLevel(unsigned Level) {
80 2169 : auto NumLevels = Levels.size();
81 2169 : if (NumLevels > Level)
82 : return false;
83 1282 : Levels.resize(Level + 1);
84 : return true;
85 : }
86 :
87 : NodeInfo &getNodeInfoAtLevel(unsigned Level) {
88 : assert(Level < Levels.size());
89 863 : return Levels[Level];
90 : }
91 : const NodeInfo &getNodeInfoAtLevel(unsigned Level) const {
92 : assert(Level < Levels.size());
93 3907 : return Levels[Level];
94 : }
95 :
96 7554 : unsigned getNumLevels() const { return Levels.size(); }
97 : };
98 :
99 : private:
100 : using ValueMap = DenseMap<Value *, ValueInfo>;
101 :
102 : ValueMap ValueImpls;
103 :
104 863 : NodeInfo *getNode(Node N) {
105 863 : auto Itr = ValueImpls.find(N.Val);
106 863 : if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel)
107 0 : return nullptr;
108 863 : return &Itr->second.getNodeInfoAtLevel(N.DerefLevel);
109 : }
110 :
111 : public:
112 : using const_value_iterator = ValueMap::const_iterator;
113 :
114 2169 : bool addNode(Node N, AliasAttrs Attr = AliasAttrs()) {
115 : assert(N.Val != nullptr);
116 2169 : auto &ValInfo = ValueImpls[N.Val];
117 2169 : auto Changed = ValInfo.addNodeToLevel(N.DerefLevel);
118 2169 : ValInfo.getNodeInfoAtLevel(N.DerefLevel).Attr |= Attr;
119 2169 : return Changed;
120 : }
121 :
122 : void addAttr(Node N, AliasAttrs Attr) {
123 41 : auto *Info = getNode(N);
124 : assert(Info != nullptr);
125 : Info->Attr |= Attr;
126 : }
127 :
128 411 : void addEdge(Node From, Node To, int64_t Offset = 0) {
129 411 : auto *FromInfo = getNode(From);
130 : assert(FromInfo != nullptr);
131 411 : auto *ToInfo = getNode(To);
132 : assert(ToInfo != nullptr);
133 :
134 411 : FromInfo->Edges.push_back(Edge{To, Offset});
135 411 : ToInfo->ReverseEdges.push_back(Edge{From, Offset});
136 411 : }
137 :
138 3351 : const NodeInfo *getNode(Node N) const {
139 3351 : auto Itr = ValueImpls.find(N.Val);
140 3351 : if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel)
141 2016 : return nullptr;
142 1335 : return &Itr->second.getNodeInfoAtLevel(N.DerefLevel);
143 : }
144 :
145 : AliasAttrs attrFor(Node N) const {
146 : auto *Info = getNode(N);
147 : assert(Info != nullptr);
148 : return Info->Attr;
149 : }
150 :
151 : iterator_range<const_value_iterator> value_mappings() const {
152 190 : return make_range<const_value_iterator>(ValueImpls.begin(),
153 422 : ValueImpls.end());
154 : }
155 : };
156 :
157 : ///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 : static bool hasUsefulEdges(ConstantExpr *CE) {
185 : // ConstantExpr doesn't have terminators, invokes, or fences, so only
186 : // needs
187 : // to check for compares.
188 13 : return CE->getOpcode() != Instruction::ICmp &&
189 : CE->getOpcode() != Instruction::FCmp;
190 : }
191 :
192 : // Returns possible functions called by CS into the given SmallVectorImpl.
193 : // Returns true if targets found, false otherwise.
194 107 : static bool getPossibleTargets(CallSite CS,
195 : SmallVectorImpl<Function *> &Output) {
196 107 : if (auto *Fn = CS.getCalledFunction()) {
197 106 : Output.push_back(Fn);
198 106 : return true;
199 : }
200 :
201 : // TODO: If the call is indirect, we might be able to enumerate all
202 : // potential
203 : // targets of the call and return them, rather than just failing.
204 1 : return false;
205 : }
206 :
207 1282 : void addNode(Value *Val, AliasAttrs Attr = AliasAttrs()) {
208 : assert(Val != nullptr && Val->getType()->isPointerTy());
209 : if (auto GVal = dyn_cast<GlobalValue>(Val)) {
210 30 : if (Graph.addNode(InstantiatedValue{GVal, 0},
211 : getGlobalOrArgAttrFromValue(*GVal)))
212 28 : Graph.addNode(InstantiatedValue{GVal, 1}, getAttrUnknown());
213 : } else if (auto CExpr = dyn_cast<ConstantExpr>(Val)) {
214 : if (hasUsefulEdges(CExpr)) {
215 26 : if (Graph.addNode(InstantiatedValue{CExpr, 0}))
216 6 : visitConstantExpr(CExpr);
217 : }
218 : } else
219 1239 : Graph.addNode(InstantiatedValue{Val, 0}, Attr);
220 1282 : }
221 :
222 147 : void addAssignEdge(Value *From, Value *To, int64_t Offset = 0) {
223 : assert(From != nullptr && To != nullptr);
224 294 : if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
225 : return;
226 119 : addNode(From);
227 119 : if (To != From) {
228 119 : addNode(To);
229 119 : Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 0},
230 : Offset);
231 : }
232 : }
233 :
234 321 : void addDerefEdge(Value *From, Value *To, bool IsRead) {
235 : assert(From != nullptr && To != nullptr);
236 : // FIXME: This is subtly broken, due to how we model some instructions
237 : // (e.g. extractvalue, extractelement) as loads. Since those take
238 : // non-pointer operands, we'll entirely skip adding edges for those.
239 : //
240 : // addAssignEdge seems to have a similar issue with insertvalue, etc.
241 642 : if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
242 : return;
243 264 : addNode(From);
244 264 : addNode(To);
245 264 : if (IsRead) {
246 296 : Graph.addNode(InstantiatedValue{From, 1});
247 148 : Graph.addEdge(InstantiatedValue{From, 1}, InstantiatedValue{To, 0});
248 : } else {
249 232 : Graph.addNode(InstantiatedValue{To, 1});
250 116 : Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 1});
251 : }
252 : }
253 :
254 166 : void addLoadEdge(Value *From, Value *To) { addDerefEdge(From, To, true); }
255 154 : void addStoreEdge(Value *From, Value *To) { addDerefEdge(From, To, false); }
256 :
257 : public:
258 211 : GetEdgesVisitor(CFLGraphBuilder &Builder, const DataLayout &DL)
259 633 : : AA(Builder.Analysis), DL(DL), TLI(Builder.TLI), Graph(Builder.Graph),
260 211 : ReturnValues(Builder.ReturnedValues) {}
261 :
262 0 : void visitInstruction(Instruction &) {
263 0 : llvm_unreachable("Unsupported instruction encountered");
264 : }
265 :
266 211 : void visitReturnInst(ReturnInst &Inst) {
267 211 : if (auto RetVal = Inst.getReturnValue()) {
268 102 : if (RetVal->getType()->isPointerTy()) {
269 47 : addNode(RetVal);
270 47 : ReturnValues.push_back(RetVal);
271 : }
272 : }
273 211 : }
274 :
275 11 : void visitPtrToIntInst(PtrToIntInst &Inst) {
276 : auto *Ptr = Inst.getOperand(0);
277 11 : addNode(Ptr, getAttrEscaped());
278 11 : }
279 :
280 : void visitIntToPtrInst(IntToPtrInst &Inst) {
281 : auto *Ptr = &Inst;
282 7 : addNode(Ptr, getAttrUnknown());
283 : }
284 :
285 : void visitCastInst(CastInst &Inst) {
286 : auto *Src = Inst.getOperand(0);
287 51 : addAssignEdge(Src, &Inst);
288 : }
289 :
290 11 : void visitBinaryOperator(BinaryOperator &Inst) {
291 : auto *Op1 = Inst.getOperand(0);
292 : auto *Op2 = Inst.getOperand(1);
293 11 : addAssignEdge(Op1, &Inst);
294 11 : addAssignEdge(Op2, &Inst);
295 11 : }
296 :
297 : void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
298 : auto *Ptr = Inst.getPointerOperand();
299 : auto *Val = Inst.getNewValOperand();
300 : addStoreEdge(Val, Ptr);
301 : }
302 :
303 : void visitAtomicRMWInst(AtomicRMWInst &Inst) {
304 : auto *Ptr = Inst.getPointerOperand();
305 : auto *Val = Inst.getValOperand();
306 : addStoreEdge(Val, Ptr);
307 : }
308 :
309 4 : void visitPHINode(PHINode &Inst) {
310 12 : for (Value *Val : Inst.incoming_values())
311 8 : addAssignEdge(Val, &Inst);
312 4 : }
313 :
314 26 : void visitGEP(GEPOperator &GEPOp) {
315 : uint64_t Offset = UnknownOffset;
316 26 : APInt APOffset(DL.getPointerSizeInBits(GEPOp.getPointerAddressSpace()),
317 : 0);
318 26 : if (GEPOp.accumulateConstantOffset(DL, APOffset))
319 19 : Offset = APOffset.getSExtValue();
320 :
321 : auto *Op = GEPOp.getPointerOperand();
322 26 : addAssignEdge(Op, &GEPOp, Offset);
323 26 : }
324 :
325 : void visitGetElementPtrInst(GetElementPtrInst &Inst) {
326 : auto *GEPOp = cast<GEPOperator>(&Inst);
327 21 : visitGEP(*GEPOp);
328 : }
329 :
330 19 : void visitSelectInst(SelectInst &Inst) {
331 : // Condition is not processed here (The actual statement producing
332 : // the condition result is processed elsewhere). For select, the
333 : // condition is evaluated, but not loaded, stored, or assigned
334 : // simply as a result of being the condition of a select.
335 :
336 : auto *TrueVal = Inst.getTrueValue();
337 : auto *FalseVal = Inst.getFalseValue();
338 19 : addAssignEdge(TrueVal, &Inst);
339 19 : addAssignEdge(FalseVal, &Inst);
340 19 : }
341 :
342 253 : void visitAllocaInst(AllocaInst &Inst) { addNode(&Inst); }
343 :
344 : void visitLoadInst(LoadInst &Inst) {
345 : auto *Ptr = Inst.getPointerOperand();
346 : auto *Val = &Inst;
347 : addLoadEdge(Ptr, Val);
348 : }
349 :
350 : void visitStoreInst(StoreInst &Inst) {
351 : auto *Ptr = Inst.getPointerOperand();
352 : auto *Val = Inst.getValueOperand();
353 : addStoreEdge(Val, Ptr);
354 : }
355 :
356 1 : void visitVAArgInst(VAArgInst &Inst) {
357 : // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it
358 : // does
359 : // two things:
360 : // 1. Loads a value from *((T*)*Ptr).
361 : // 2. Increments (stores to) *Ptr by some target-specific amount.
362 : // For now, we'll handle this like a landingpad instruction (by placing
363 : // the
364 : // result in its own group, and having that group alias externals).
365 2 : if (Inst.getType()->isPointerTy())
366 1 : addNode(&Inst, getAttrUnknown());
367 1 : }
368 :
369 : static bool isFunctionExternal(Function *Fn) {
370 106 : return !Fn->hasExactDefinition();
371 : }
372 :
373 106 : bool tryInterproceduralAnalysis(CallSite CS,
374 : const SmallVectorImpl<Function *> &Fns) {
375 : assert(Fns.size() > 0);
376 :
377 106 : if (CS.arg_size() > MaxSupportedArgsInSummary)
378 : return false;
379 :
380 : // Exit early if we'll fail anyway
381 170 : for (auto *Fn : Fns) {
382 106 : if (isFunctionExternal(Fn) || Fn->isVarArg())
383 : return false;
384 : // Fail if the caller does not provide enough arguments
385 : assert(Fn->arg_size() <= CS.arg_size());
386 64 : if (!AA.getAliasSummary(*Fn))
387 : return false;
388 : }
389 :
390 128 : for (auto *Fn : Fns) {
391 64 : auto Summary = AA.getAliasSummary(*Fn);
392 : assert(Summary != nullptr);
393 :
394 : auto &RetParamRelations = Summary->RetParamRelations;
395 92 : for (auto &Relation : RetParamRelations) {
396 28 : auto IRelation = instantiateExternalRelation(Relation, CS);
397 28 : if (IRelation.hasValue()) {
398 56 : Graph.addNode(IRelation->From);
399 56 : Graph.addNode(IRelation->To);
400 28 : Graph.addEdge(IRelation->From, IRelation->To);
401 : }
402 : }
403 :
404 : auto &RetParamAttributes = Summary->RetParamAttributes;
405 124 : 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 : }
410 : }
411 :
412 : return true;
413 : }
414 :
415 143 : void visitCallSite(CallSite CS) {
416 : auto Inst = CS.getInstruction();
417 :
418 : // Make sure all arguments and return value are added to the graph first
419 296 : for (Value *V : CS.args())
420 306 : if (V->getType()->isPointerTy())
421 117 : addNode(V);
422 286 : if (Inst->getType()->isPointerTy())
423 80 : addNode(Inst);
424 :
425 : // Check if Inst is a call to a library function that
426 : // allocates/deallocates on the heap. Those kinds of functions do not
427 : // introduce any aliases.
428 : // TODO: address other common library functions such as realloc(),
429 : // strdup(), etc.
430 143 : if (isMallocOrCallocLikeFn(Inst, &TLI) || isFreeCall(Inst, &TLI))
431 100 : return;
432 :
433 : // TODO: Add support for noalias args/all the other fun function
434 : // attributes that we can tack on.
435 : SmallVector<Function *, 4> Targets;
436 107 : if (getPossibleTargets(CS, Targets))
437 106 : if (tryInterproceduralAnalysis(CS, Targets))
438 : return;
439 :
440 : // Because the function is opaque, we need to note that anything
441 : // could have happened to the arguments (unless the function is marked
442 : // readonly or readnone), and that the result could alias just about
443 : // anything, too (unless the result is marked noalias).
444 43 : if (!CS.onlyReadsMemory())
445 70 : for (Value *V : CS.args()) {
446 70 : if (V->getType()->isPointerTy()) {
447 : // The argument itself escapes.
448 35 : Graph.addAttr(InstantiatedValue{V, 0}, getAttrEscaped());
449 : // The fate of argument memory is unknown. Note that since
450 : // AliasAttrs is transitive with respect to dereference, we only
451 : // need to specify it for the first-level memory.
452 35 : Graph.addNode(InstantiatedValue{V, 1}, getAttrUnknown());
453 : }
454 : }
455 :
456 86 : if (Inst->getType()->isPointerTy()) {
457 : auto *Fn = CS.getCalledFunction();
458 9 : if (Fn == nullptr || !Fn->returnDoesNotAlias())
459 : // No need to call addNode() since we've added Inst at the
460 : // beginning of this function and we know it is not a global.
461 12 : Graph.addAttr(InstantiatedValue{Inst, 0}, getAttrUnknown());
462 : }
463 : }
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 : void visitExtractElementInst(ExtractElementInst &Inst) {
470 : auto *Ptr = Inst.getVectorOperand();
471 : auto *Val = &Inst;
472 : addLoadEdge(Ptr, Val);
473 : }
474 :
475 0 : void visitInsertElementInst(InsertElementInst &Inst) {
476 : auto *Vec = Inst.getOperand(0);
477 : auto *Val = Inst.getOperand(1);
478 0 : addAssignEdge(Vec, &Inst);
479 : addStoreEdge(Val, &Inst);
480 0 : }
481 :
482 0 : void visitLandingPadInst(LandingPadInst &Inst) {
483 : // Exceptions come from "nowhere", from our analysis' perspective.
484 : // So we place the instruction its own group, noting that said group may
485 : // alias externals
486 0 : if (Inst.getType()->isPointerTy())
487 0 : addNode(&Inst, getAttrUnknown());
488 0 : }
489 :
490 0 : void visitInsertValueInst(InsertValueInst &Inst) {
491 : auto *Agg = Inst.getOperand(0);
492 : auto *Val = Inst.getOperand(1);
493 0 : addAssignEdge(Agg, &Inst);
494 : addStoreEdge(Val, &Inst);
495 0 : }
496 :
497 : void visitExtractValueInst(ExtractValueInst &Inst) {
498 : auto *Ptr = Inst.getAggregateOperand();
499 1 : addLoadEdge(Ptr, &Inst);
500 : }
501 :
502 0 : void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
503 : auto *From1 = Inst.getOperand(0);
504 : auto *From2 = Inst.getOperand(1);
505 0 : addAssignEdge(From1, &Inst);
506 0 : addAssignEdge(From2, &Inst);
507 0 : }
508 :
509 6 : void visitConstantExpr(ConstantExpr *CE) {
510 6 : switch (CE->getOpcode()) {
511 : case Instruction::GetElementPtr: {
512 : auto GEPOp = cast<GEPOperator>(CE);
513 5 : visitGEP(*GEPOp);
514 5 : break;
515 : }
516 :
517 0 : case Instruction::PtrToInt: {
518 0 : addNode(CE->getOperand(0), getAttrEscaped());
519 0 : break;
520 : }
521 :
522 0 : case Instruction::IntToPtr: {
523 0 : addNode(CE, getAttrUnknown());
524 0 : break;
525 : }
526 :
527 : case Instruction::BitCast:
528 : case Instruction::AddrSpaceCast:
529 : case Instruction::Trunc:
530 : case Instruction::ZExt:
531 : case Instruction::SExt:
532 : case Instruction::FPExt:
533 : case Instruction::FPTrunc:
534 : case Instruction::UIToFP:
535 : case Instruction::SIToFP:
536 : case Instruction::FPToUI:
537 : case Instruction::FPToSI: {
538 0 : addAssignEdge(CE->getOperand(0), CE);
539 0 : break;
540 : }
541 :
542 : case Instruction::Select: {
543 1 : addAssignEdge(CE->getOperand(1), CE);
544 1 : addAssignEdge(CE->getOperand(2), CE);
545 1 : break;
546 : }
547 :
548 : case Instruction::InsertElement:
549 : case Instruction::InsertValue: {
550 0 : addAssignEdge(CE->getOperand(0), CE);
551 : addStoreEdge(CE->getOperand(1), CE);
552 : break;
553 : }
554 :
555 : case Instruction::ExtractElement:
556 : case Instruction::ExtractValue: {
557 : addLoadEdge(CE->getOperand(0), CE);
558 : break;
559 : }
560 :
561 : case Instruction::Add:
562 : case Instruction::Sub:
563 : case Instruction::FSub:
564 : case Instruction::Mul:
565 : case Instruction::FMul:
566 : case Instruction::UDiv:
567 : case Instruction::SDiv:
568 : case Instruction::FDiv:
569 : case Instruction::URem:
570 : case Instruction::SRem:
571 : case Instruction::FRem:
572 : case Instruction::And:
573 : case Instruction::Or:
574 : case Instruction::Xor:
575 : case Instruction::Shl:
576 : case Instruction::LShr:
577 : case Instruction::AShr:
578 : case Instruction::ICmp:
579 : case Instruction::FCmp:
580 : case Instruction::ShuffleVector: {
581 0 : addAssignEdge(CE->getOperand(0), CE);
582 0 : addAssignEdge(CE->getOperand(1), CE);
583 0 : break;
584 : }
585 :
586 0 : default:
587 0 : llvm_unreachable("Unknown instruction type encountered!");
588 : }
589 6 : }
590 : };
591 :
592 : // Helper functions
593 :
594 : // Determines whether or not we an instruction is useless to us (e.g.
595 : // FenceInst)
596 : static bool hasUsefulEdges(Instruction *Inst) {
597 0 : bool IsNonInvokeRetTerminator = Inst->isTerminator() &&
598 0 : !isa<InvokeInst>(Inst) &&
599 : !isa<ReturnInst>(Inst);
600 0 : return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) &&
601 : !IsNonInvokeRetTerminator;
602 : }
603 :
604 240 : void addArgumentToGraph(Argument &Arg) {
605 480 : if (Arg.getType()->isPointerTy()) {
606 222 : Graph.addNode(InstantiatedValue{&Arg, 0},
607 : getGlobalOrArgAttrFromValue(Arg));
608 : // Pointees of a formal parameter is known to the caller
609 222 : Graph.addNode(InstantiatedValue{&Arg, 1}, getAttrCaller());
610 : }
611 240 : }
612 :
613 : // Given an Instruction, this will add it to the graph, along with any
614 : // Instructions that are potentially only available from said Instruction
615 : // For example, given the following line:
616 : // %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2
617 : // addInstructionToGraph would add both the `load` and `getelementptr`
618 : // instructions to the graph appropriately.
619 0 : void addInstructionToGraph(GetEdgesVisitor &Visitor, Instruction &Inst) {
620 : if (!hasUsefulEdges(&Inst))
621 0 : return;
622 :
623 0 : Visitor.visit(Inst);
624 : }
625 :
626 : // Builds the graph needed for constructing the StratifiedSets for the given
627 : // function
628 211 : void buildGraphFrom(Function &Fn) {
629 211 : GetEdgesVisitor Visitor(*this, Fn.getParent()->getDataLayout());
630 :
631 438 : for (auto &Bb : Fn.getBasicBlockList())
632 1299 : for (auto &Inst : Bb.getInstList())
633 1072 : addInstructionToGraph(Visitor, Inst);
634 :
635 451 : for (auto &Arg : Fn.args())
636 240 : addArgumentToGraph(Arg);
637 211 : }
638 :
639 : public:
640 211 : CFLGraphBuilder(CFLAA &Analysis, const TargetLibraryInfo &TLI, Function &Fn)
641 211 : : Analysis(Analysis), TLI(TLI) {
642 211 : buildGraphFrom(Fn);
643 116 : }
644 :
645 : const CFLGraph &getCFLGraph() const { return Graph; }
646 : const SmallVector<Value *, 4> &getReturnValues() const {
647 : return ReturnedValues;
648 : }
649 : };
650 :
651 : } // end namespace cflaa
652 : } // end namespace llvm
653 :
654 : #endif // LLVM_LIB_ANALYSIS_CFLGRAPH_H
|
