1 //======- CFLGraph.h - Abstract stratified sets implementation. --------======//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 /// This file defines CFLGraph, an auxiliary data structure used by CFL-based
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_ANALYSIS_CFLGRAPH_H
16 #define LLVM_ANALYSIS_CFLGRAPH_H
18 #include "AliasAnalysisSummary.h"
19 #include "llvm/Analysis/MemoryBuiltins.h"
20 #include "llvm/IR/InstVisitor.h"
21 #include "llvm/IR/Instructions.h"
26 /// \brief The Program Expression Graph (PEG) of CFL analysis
27 /// CFLGraph is auxiliary data structure used by CFL-based alias analysis to
28 /// describe flow-insensitive pointer-related behaviors. Given an LLVM function,
29 /// the main purpose of this graph is to abstract away unrelated facts and
30 /// translate the rest into a form that can be easily digested by CFL analyses.
31 /// Each Node in the graph is an InstantiatedValue, and each edge represent a
32 /// pointer assignment between InstantiatedValue. Pointer
33 /// references/dereferences are not explicitly stored in the graph: we
34 /// implicitly assume that for each node (X, I) it has a dereference edge to (X,
35 /// I+1) and a reference edge to (X, I-1).
38 typedef InstantiatedValue Node;
45 typedef std::vector<Edge> EdgeList;
48 EdgeList Edges, ReverseEdges;
53 std::vector<NodeInfo> Levels;
56 bool addNodeToLevel(unsigned Level) {
57 auto NumLevels = Levels.size();
58 if (NumLevels > Level)
60 Levels.resize(Level + 1);
64 NodeInfo &getNodeInfoAtLevel(unsigned Level) {
65 assert(Level < Levels.size());
68 const NodeInfo &getNodeInfoAtLevel(unsigned Level) const {
69 assert(Level < Levels.size());
73 unsigned getNumLevels() const { return Levels.size(); }
77 typedef DenseMap<Value *, ValueInfo> ValueMap;
80 NodeInfo *getNode(Node N) {
81 auto Itr = ValueImpls.find(N.Val);
82 if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel)
84 return &Itr->second.getNodeInfoAtLevel(N.DerefLevel);
88 typedef ValueMap::const_iterator const_value_iterator;
90 bool addNode(Node N, AliasAttrs Attr = AliasAttrs()) {
91 assert(N.Val != nullptr);
92 auto &ValInfo = ValueImpls[N.Val];
93 auto Changed = ValInfo.addNodeToLevel(N.DerefLevel);
94 ValInfo.getNodeInfoAtLevel(N.DerefLevel).Attr |= Attr;
98 void addAttr(Node N, AliasAttrs Attr) {
99 auto *Info = getNode(N);
100 assert(Info != nullptr);
104 void addEdge(Node From, Node To, int64_t Offset = 0) {
105 auto *FromInfo = getNode(From);
106 assert(FromInfo != nullptr);
107 auto *ToInfo = getNode(To);
108 assert(ToInfo != nullptr);
110 FromInfo->Edges.push_back(Edge{To, Offset});
111 ToInfo->ReverseEdges.push_back(Edge{From, Offset});
114 const NodeInfo *getNode(Node N) const {
115 auto Itr = ValueImpls.find(N.Val);
116 if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel)
118 return &Itr->second.getNodeInfoAtLevel(N.DerefLevel);
121 AliasAttrs attrFor(Node N) const {
122 auto *Info = getNode(N);
123 assert(Info != nullptr);
127 iterator_range<const_value_iterator> value_mappings() const {
128 return make_range<const_value_iterator>(ValueImpls.begin(),
133 ///\brief A builder class used to create CFLGraph instance from a given function
134 /// The CFL-AA that uses this builder must provide its own type as a template
135 /// argument. This is necessary for interprocedural processing: CFLGraphBuilder
136 /// needs a way of obtaining the summary of other functions when callinsts are
138 /// As a result, we expect the said CFL-AA to expose a getAliasSummary() public
139 /// member function that takes a Function& and returns the corresponding summary
140 /// as a const AliasSummary*.
141 template <typename CFLAA> class CFLGraphBuilder {
142 // Input of the builder
144 const TargetLibraryInfo &TLI;
146 // Output of the builder
148 SmallVector<Value *, 4> ReturnedValues;
151 /// Gets the edges our graph should have, based on an Instruction*
152 class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
154 const DataLayout &DL;
155 const TargetLibraryInfo &TLI;
158 SmallVectorImpl<Value *> &ReturnValues;
160 static bool hasUsefulEdges(ConstantExpr *CE) {
161 // ConstantExpr doesn't have terminators, invokes, or fences, so only
163 // to check for compares.
164 return CE->getOpcode() != Instruction::ICmp &&
165 CE->getOpcode() != Instruction::FCmp;
168 // Returns possible functions called by CS into the given SmallVectorImpl.
169 // Returns true if targets found, false otherwise.
170 static bool getPossibleTargets(CallSite CS,
171 SmallVectorImpl<Function *> &Output) {
172 if (auto *Fn = CS.getCalledFunction()) {
173 Output.push_back(Fn);
177 // TODO: If the call is indirect, we might be able to enumerate all
179 // targets of the call and return them, rather than just failing.
183 void addNode(Value *Val, AliasAttrs Attr = AliasAttrs()) {
184 assert(Val != nullptr && Val->getType()->isPointerTy());
185 if (auto GVal = dyn_cast<GlobalValue>(Val)) {
186 if (Graph.addNode(InstantiatedValue{GVal, 0},
187 getGlobalOrArgAttrFromValue(*GVal)))
188 Graph.addNode(InstantiatedValue{GVal, 1}, getAttrUnknown());
189 } else if (auto CExpr = dyn_cast<ConstantExpr>(Val)) {
190 if (hasUsefulEdges(CExpr)) {
191 if (Graph.addNode(InstantiatedValue{CExpr, 0}))
192 visitConstantExpr(CExpr);
195 Graph.addNode(InstantiatedValue{Val, 0}, Attr);
198 void addAssignEdge(Value *From, Value *To, int64_t Offset = 0) {
199 assert(From != nullptr && To != nullptr);
200 if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
205 Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 0},
210 void addDerefEdge(Value *From, Value *To, bool IsRead) {
211 assert(From != nullptr && To != nullptr);
212 // FIXME: This is subtly broken, due to how we model some instructions
213 // (e.g. extractvalue, extractelement) as loads. Since those take
214 // non-pointer operands, we'll entirely skip adding edges for those.
216 // addAssignEdge seems to have a similar issue with insertvalue, etc.
217 if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
222 Graph.addNode(InstantiatedValue{From, 1});
223 Graph.addEdge(InstantiatedValue{From, 1}, InstantiatedValue{To, 0});
225 Graph.addNode(InstantiatedValue{To, 1});
226 Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 1});
230 void addLoadEdge(Value *From, Value *To) { addDerefEdge(From, To, true); }
231 void addStoreEdge(Value *From, Value *To) { addDerefEdge(From, To, false); }
234 GetEdgesVisitor(CFLGraphBuilder &Builder, const DataLayout &DL)
235 : AA(Builder.Analysis), DL(DL), TLI(Builder.TLI), Graph(Builder.Graph),
236 ReturnValues(Builder.ReturnedValues) {}
238 void visitInstruction(Instruction &) {
239 llvm_unreachable("Unsupported instruction encountered");
242 void visitReturnInst(ReturnInst &Inst) {
243 if (auto RetVal = Inst.getReturnValue()) {
244 if (RetVal->getType()->isPointerTy()) {
246 ReturnValues.push_back(RetVal);
251 void visitPtrToIntInst(PtrToIntInst &Inst) {
252 auto *Ptr = Inst.getOperand(0);
253 addNode(Ptr, getAttrEscaped());
256 void visitIntToPtrInst(IntToPtrInst &Inst) {
258 addNode(Ptr, getAttrUnknown());
261 void visitCastInst(CastInst &Inst) {
262 auto *Src = Inst.getOperand(0);
263 addAssignEdge(Src, &Inst);
266 void visitBinaryOperator(BinaryOperator &Inst) {
267 auto *Op1 = Inst.getOperand(0);
268 auto *Op2 = Inst.getOperand(1);
269 addAssignEdge(Op1, &Inst);
270 addAssignEdge(Op2, &Inst);
273 void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
274 auto *Ptr = Inst.getPointerOperand();
275 auto *Val = Inst.getNewValOperand();
276 addStoreEdge(Val, Ptr);
279 void visitAtomicRMWInst(AtomicRMWInst &Inst) {
280 auto *Ptr = Inst.getPointerOperand();
281 auto *Val = Inst.getValOperand();
282 addStoreEdge(Val, Ptr);
285 void visitPHINode(PHINode &Inst) {
286 for (Value *Val : Inst.incoming_values())
287 addAssignEdge(Val, &Inst);
290 void visitGEP(GEPOperator &GEPOp) {
291 uint64_t Offset = UnknownOffset;
292 APInt APOffset(DL.getPointerSizeInBits(GEPOp.getPointerAddressSpace()),
294 if (GEPOp.accumulateConstantOffset(DL, APOffset))
295 Offset = APOffset.getSExtValue();
297 auto *Op = GEPOp.getPointerOperand();
298 addAssignEdge(Op, &GEPOp, Offset);
301 void visitGetElementPtrInst(GetElementPtrInst &Inst) {
302 auto *GEPOp = cast<GEPOperator>(&Inst);
306 void visitSelectInst(SelectInst &Inst) {
307 // Condition is not processed here (The actual statement producing
308 // the condition result is processed elsewhere). For select, the
309 // condition is evaluated, but not loaded, stored, or assigned
310 // simply as a result of being the condition of a select.
312 auto *TrueVal = Inst.getTrueValue();
313 auto *FalseVal = Inst.getFalseValue();
314 addAssignEdge(TrueVal, &Inst);
315 addAssignEdge(FalseVal, &Inst);
318 void visitAllocaInst(AllocaInst &Inst) { addNode(&Inst); }
320 void visitLoadInst(LoadInst &Inst) {
321 auto *Ptr = Inst.getPointerOperand();
323 addLoadEdge(Ptr, Val);
326 void visitStoreInst(StoreInst &Inst) {
327 auto *Ptr = Inst.getPointerOperand();
328 auto *Val = Inst.getValueOperand();
329 addStoreEdge(Val, Ptr);
332 void visitVAArgInst(VAArgInst &Inst) {
333 // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it
336 // 1. Loads a value from *((T*)*Ptr).
337 // 2. Increments (stores to) *Ptr by some target-specific amount.
338 // For now, we'll handle this like a landingpad instruction (by placing
340 // result in its own group, and having that group alias externals).
341 if (Inst.getType()->isPointerTy())
342 addNode(&Inst, getAttrUnknown());
345 static bool isFunctionExternal(Function *Fn) {
346 return !Fn->hasExactDefinition();
349 bool tryInterproceduralAnalysis(CallSite CS,
350 const SmallVectorImpl<Function *> &Fns) {
351 assert(Fns.size() > 0);
353 if (CS.arg_size() > MaxSupportedArgsInSummary)
356 // Exit early if we'll fail anyway
357 for (auto *Fn : Fns) {
358 if (isFunctionExternal(Fn) || Fn->isVarArg())
360 // Fail if the caller does not provide enough arguments
361 assert(Fn->arg_size() <= CS.arg_size());
362 if (!AA.getAliasSummary(*Fn))
366 for (auto *Fn : Fns) {
367 auto Summary = AA.getAliasSummary(*Fn);
368 assert(Summary != nullptr);
370 auto &RetParamRelations = Summary->RetParamRelations;
371 for (auto &Relation : RetParamRelations) {
372 auto IRelation = instantiateExternalRelation(Relation, CS);
373 if (IRelation.hasValue()) {
374 Graph.addNode(IRelation->From);
375 Graph.addNode(IRelation->To);
376 Graph.addEdge(IRelation->From, IRelation->To);
380 auto &RetParamAttributes = Summary->RetParamAttributes;
381 for (auto &Attribute : RetParamAttributes) {
382 auto IAttr = instantiateExternalAttribute(Attribute, CS);
383 if (IAttr.hasValue())
384 Graph.addNode(IAttr->IValue, IAttr->Attr);
391 void visitCallSite(CallSite CS) {
392 auto Inst = CS.getInstruction();
394 // Make sure all arguments and return value are added to the graph first
395 for (Value *V : CS.args())
396 if (V->getType()->isPointerTy())
398 if (Inst->getType()->isPointerTy())
401 // Check if Inst is a call to a library function that
402 // allocates/deallocates
403 // on the heap. Those kinds of functions do not introduce any aliases.
404 // TODO: address other common library functions such as realloc(),
407 if (isMallocOrCallocLikeFn(Inst, &TLI) || isFreeCall(Inst, &TLI))
410 // TODO: Add support for noalias args/all the other fun function
412 // that we can tack on.
413 SmallVector<Function *, 4> Targets;
414 if (getPossibleTargets(CS, Targets))
415 if (tryInterproceduralAnalysis(CS, Targets))
418 // Because the function is opaque, we need to note that anything
419 // could have happened to the arguments (unless the function is marked
420 // readonly or readnone), and that the result could alias just about
421 // anything, too (unless the result is marked noalias).
422 if (!CS.onlyReadsMemory())
423 for (Value *V : CS.args()) {
424 if (V->getType()->isPointerTy()) {
425 // The argument itself escapes.
426 Graph.addAttr(InstantiatedValue{V, 0}, getAttrEscaped());
427 // The fate of argument memory is unknown. Note that since
428 // AliasAttrs is transitive with respect to dereference, we only
429 // need to specify it for the first-level memory.
430 Graph.addNode(InstantiatedValue{V, 1}, getAttrUnknown());
434 if (Inst->getType()->isPointerTy()) {
435 auto *Fn = CS.getCalledFunction();
436 if (Fn == nullptr || !Fn->returnDoesNotAlias())
437 // No need to call addNode() since we've added Inst at the
438 // beginning of this function and we know it is not a global.
439 Graph.addAttr(InstantiatedValue{Inst, 0}, getAttrUnknown());
443 /// Because vectors/aggregates are immutable and unaddressable, there's
444 /// nothing we can do to coax a value out of them, other than calling
445 /// Extract{Element,Value}. We can effectively treat them as pointers to
446 /// arbitrary memory locations we can store in and load from.
447 void visitExtractElementInst(ExtractElementInst &Inst) {
448 auto *Ptr = Inst.getVectorOperand();
450 addLoadEdge(Ptr, Val);
453 void visitInsertElementInst(InsertElementInst &Inst) {
454 auto *Vec = Inst.getOperand(0);
455 auto *Val = Inst.getOperand(1);
456 addAssignEdge(Vec, &Inst);
457 addStoreEdge(Val, &Inst);
460 void visitLandingPadInst(LandingPadInst &Inst) {
461 // Exceptions come from "nowhere", from our analysis' perspective.
462 // So we place the instruction its own group, noting that said group may
464 if (Inst.getType()->isPointerTy())
465 addNode(&Inst, getAttrUnknown());
468 void visitInsertValueInst(InsertValueInst &Inst) {
469 auto *Agg = Inst.getOperand(0);
470 auto *Val = Inst.getOperand(1);
471 addAssignEdge(Agg, &Inst);
472 addStoreEdge(Val, &Inst);
475 void visitExtractValueInst(ExtractValueInst &Inst) {
476 auto *Ptr = Inst.getAggregateOperand();
477 addLoadEdge(Ptr, &Inst);
480 void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
481 auto *From1 = Inst.getOperand(0);
482 auto *From2 = Inst.getOperand(1);
483 addAssignEdge(From1, &Inst);
484 addAssignEdge(From2, &Inst);
487 void visitConstantExpr(ConstantExpr *CE) {
488 switch (CE->getOpcode()) {
489 case Instruction::GetElementPtr: {
490 auto GEPOp = cast<GEPOperator>(CE);
494 case Instruction::PtrToInt: {
495 auto *Ptr = CE->getOperand(0);
496 addNode(Ptr, getAttrEscaped());
499 case Instruction::IntToPtr: {
500 addNode(CE, getAttrUnknown());
503 case Instruction::BitCast:
504 case Instruction::AddrSpaceCast:
505 case Instruction::Trunc:
506 case Instruction::ZExt:
507 case Instruction::SExt:
508 case Instruction::FPExt:
509 case Instruction::FPTrunc:
510 case Instruction::UIToFP:
511 case Instruction::SIToFP:
512 case Instruction::FPToUI:
513 case Instruction::FPToSI: {
514 auto *Src = CE->getOperand(0);
515 addAssignEdge(Src, CE);
518 case Instruction::Select: {
519 auto *TrueVal = CE->getOperand(0);
520 auto *FalseVal = CE->getOperand(1);
521 addAssignEdge(TrueVal, CE);
522 addAssignEdge(FalseVal, CE);
525 case Instruction::InsertElement: {
526 auto *Vec = CE->getOperand(0);
527 auto *Val = CE->getOperand(1);
528 addAssignEdge(Vec, CE);
529 addStoreEdge(Val, CE);
532 case Instruction::ExtractElement: {
533 auto *Ptr = CE->getOperand(0);
534 addLoadEdge(Ptr, CE);
537 case Instruction::InsertValue: {
538 auto *Agg = CE->getOperand(0);
539 auto *Val = CE->getOperand(1);
540 addAssignEdge(Agg, CE);
541 addStoreEdge(Val, CE);
544 case Instruction::ExtractValue: {
545 auto *Ptr = CE->getOperand(0);
546 addLoadEdge(Ptr, CE);
549 case Instruction::ShuffleVector: {
550 auto *From1 = CE->getOperand(0);
551 auto *From2 = CE->getOperand(1);
552 addAssignEdge(From1, CE);
553 addAssignEdge(From2, CE);
556 case Instruction::Add:
557 case Instruction::Sub:
558 case Instruction::FSub:
559 case Instruction::Mul:
560 case Instruction::FMul:
561 case Instruction::UDiv:
562 case Instruction::SDiv:
563 case Instruction::FDiv:
564 case Instruction::URem:
565 case Instruction::SRem:
566 case Instruction::FRem:
567 case Instruction::And:
568 case Instruction::Or:
569 case Instruction::Xor:
570 case Instruction::Shl:
571 case Instruction::LShr:
572 case Instruction::AShr:
573 case Instruction::ICmp:
574 case Instruction::FCmp: {
575 addAssignEdge(CE->getOperand(0), CE);
576 addAssignEdge(CE->getOperand(1), CE);
580 llvm_unreachable("Unknown instruction type encountered!");
587 // Determines whether or not we an instruction is useless to us (e.g.
589 static bool hasUsefulEdges(Instruction *Inst) {
590 bool IsNonInvokeRetTerminator = isa<TerminatorInst>(Inst) &&
591 !isa<InvokeInst>(Inst) &&
592 !isa<ReturnInst>(Inst);
593 return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) &&
594 !IsNonInvokeRetTerminator;
597 void addArgumentToGraph(Argument &Arg) {
598 if (Arg.getType()->isPointerTy()) {
599 Graph.addNode(InstantiatedValue{&Arg, 0},
600 getGlobalOrArgAttrFromValue(Arg));
601 // Pointees of a formal parameter is known to the caller
602 Graph.addNode(InstantiatedValue{&Arg, 1}, getAttrCaller());
606 // Given an Instruction, this will add it to the graph, along with any
607 // Instructions that are potentially only available from said Instruction
608 // For example, given the following line:
609 // %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2
610 // addInstructionToGraph would add both the `load` and `getelementptr`
611 // instructions to the graph appropriately.
612 void addInstructionToGraph(GetEdgesVisitor &Visitor, Instruction &Inst) {
613 if (!hasUsefulEdges(&Inst))
619 // Builds the graph needed for constructing the StratifiedSets for the given
621 void buildGraphFrom(Function &Fn) {
622 GetEdgesVisitor Visitor(*this, Fn.getParent()->getDataLayout());
624 for (auto &Bb : Fn.getBasicBlockList())
625 for (auto &Inst : Bb.getInstList())
626 addInstructionToGraph(Visitor, Inst);
628 for (auto &Arg : Fn.args())
629 addArgumentToGraph(Arg);
633 CFLGraphBuilder(CFLAA &Analysis, const TargetLibraryInfo &TLI, Function &Fn)
634 : Analysis(Analysis), TLI(TLI) {
638 const CFLGraph &getCFLGraph() const { return Graph; }
639 const SmallVector<Value *, 4> &getReturnValues() const {
640 return ReturnedValues;