LCOV - code coverage report
Current view: top level - lib/Analysis - CFLGraph.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 194 267 72.7 %
Date: 2017-09-14 15:23:50 Functions: 38 51 74.5 %
Legend: Lines: hit not hit

          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             : /// \brief The Program Expression Graph (PEG) of CFL analysis
      50             : /// CFLGraph is auxiliary data structure used by CFL-based alias analysis to
      51             : /// describe flow-insensitive pointer-related behaviors. Given an LLVM function,
      52             : /// the main purpose of this graph is to abstract away unrelated facts and
      53             : /// translate the rest into a form that can be easily digested by CFL analyses.
      54             : /// Each Node in the graph is an InstantiatedValue, and each edge represent a
      55             : /// pointer assignment between InstantiatedValue. Pointer
      56             : /// references/dereferences are not explicitly stored in the graph: we
      57             : /// implicitly assume that for each node (X, I) it has a dereference edge to (X,
      58             : /// I+1) and a reference edge to (X, I-1).
      59         840 : 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       11682 :   struct NodeInfo {
      71             :     EdgeList Edges, ReverseEdges;
      72             :     AliasAttrs Attr;
      73             :   };
      74             : 
      75        2490 :   class ValueInfo {
      76             :     std::vector<NodeInfo> Levels;
      77             : 
      78             :   public:
      79             :     bool addNodeToLevel(unsigned Level) {
      80        4312 :       auto NumLevels = Levels.size();
      81        2156 :       if (NumLevels > Level)
      82             :         return false;
      83        1274 :       Levels.resize(Level + 1);
      84             :       return true;
      85             :     }
      86             : 
      87             :     NodeInfo &getNodeInfoAtLevel(unsigned Level) {
      88             :       assert(Level < Levels.size());
      89        6022 :       return Levels[Level];
      90             :     }
      91             :     const NodeInfo &getNodeInfoAtLevel(unsigned Level) const {
      92             :       assert(Level < Levels.size());
      93        7319 :       return Levels[Level];
      94             :     }
      95             : 
      96       11742 :     unsigned getNumLevels() const { return Levels.size(); }
      97             :   };
      98             : 
      99             : private:
     100             :   using ValueMap = DenseMap<Value *, ValueInfo>;
     101             : 
     102             :   ValueMap ValueImpls;
     103             : 
     104         855 :   NodeInfo *getNode(Node N) {
     105         855 :     auto Itr = ValueImpls.find(N.Val);
     106        3420 :     if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel)
     107             :       return nullptr;
     108        1710 :     return &Itr->second.getNodeInfoAtLevel(N.DerefLevel);
     109             :   }
     110             : 
     111             : public:
     112             :   using const_value_iterator = ValueMap::const_iterator;
     113             : 
     114        2156 :   bool addNode(Node N, AliasAttrs Attr = AliasAttrs()) {
     115             :     assert(N.Val != nullptr);
     116        4312 :     auto &ValInfo = ValueImpls[N.Val];
     117        4312 :     auto Changed = ValInfo.addNodeToLevel(N.DerefLevel);
     118        6468 :     ValInfo.getNodeInfoAtLevel(N.DerefLevel).Attr |= Attr;
     119        2156 :     return Changed;
     120             :   }
     121             : 
     122             :   void addAttr(Node N, AliasAttrs Attr) {
     123          41 :     auto *Info = getNode(N);
     124             :     assert(Info != nullptr);
     125          82 :     Info->Attr |= Attr;
     126             :   }
     127             : 
     128         407 :   void addEdge(Node From, Node To, int64_t Offset = 0) {
     129         407 :     auto *FromInfo = getNode(From);
     130             :     assert(FromInfo != nullptr);
     131         407 :     auto *ToInfo = getNode(To);
     132             :     assert(ToInfo != nullptr);
     133             : 
     134         814 :     FromInfo->Edges.push_back(Edge{To, Offset});
     135         814 :     ToInfo->ReverseEdges.push_back(Edge{From, Offset});
     136         407 :   }
     137             : 
     138        3356 :   const NodeInfo *getNode(Node N) const {
     139        3356 :     auto Itr = ValueImpls.find(N.Val);
     140       10068 :     if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel)
     141             :       return nullptr;
     142        2668 :     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             :     return make_range<const_value_iterator>(ValueImpls.begin(),
     153        1260 :                                             ValueImpls.end());
     154             :   }
     155             : };
     156             : 
     157             : ///\brief A builder class used to create CFLGraph instance from a given function
     158             : /// The CFL-AA that uses this builder must provide its own type as a template
     159             : /// argument. This is necessary for interprocedural processing: CFLGraphBuilder
     160             : /// needs a way of obtaining the summary of other functions when callinsts are
     161             : /// encountered.
     162             : /// As a result, we expect the said CFL-AA to expose a getAliasSummary() public
     163             : /// member function that takes a Function& and returns the corresponding summary
     164             : /// as a const AliasSummary*.
     165         630 : 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          20 :       return CE->getOpcode() != Instruction::ICmp &&
     189          10 :              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        1273 :     void addNode(Value *Val, AliasAttrs Attr = AliasAttrs()) {
     208             :       assert(Val != nullptr && Val->getType()->isPointerTy());
     209          28 :       if (auto GVal = dyn_cast<GlobalValue>(Val)) {
     210          28 :         if (Graph.addNode(InstantiatedValue{GVal, 0},
     211             :                           getGlobalOrArgAttrFromValue(*GVal)))
     212          26 :           Graph.addNode(InstantiatedValue{GVal, 1}, getAttrUnknown());
     213          10 :       } else if (auto CExpr = dyn_cast<ConstantExpr>(Val)) {
     214          10 :         if (hasUsefulEdges(CExpr)) {
     215          20 :           if (Graph.addNode(InstantiatedValue{CExpr, 0}))
     216           5 :             visitConstantExpr(CExpr);
     217             :         }
     218             :       } else
     219        1235 :         Graph.addNode(InstantiatedValue{Val, 0}, Attr);
     220        1273 :     }
     221             : 
     222         145 :     void addAssignEdge(Value *From, Value *To, int64_t Offset = 0) {
     223             :       assert(From != nullptr && To != nullptr);
     224         407 :       if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
     225             :         return;
     226         117 :       addNode(From);
     227         117 :       if (To != From) {
     228         117 :         addNode(To);
     229         117 :         Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 0},
     230             :                       Offset);
     231             :       }
     232             :     }
     233             : 
     234         316 :     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         909 :       if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
     242             :         return;
     243         262 :       addNode(From);
     244         262 :       addNode(To);
     245         262 :       if (IsRead) {
     246         294 :         Graph.addNode(InstantiatedValue{From, 1});
     247         147 :         Graph.addEdge(InstantiatedValue{From, 1}, InstantiatedValue{To, 0});
     248             :       } else {
     249         230 :         Graph.addNode(InstantiatedValue{To, 1});
     250         115 :         Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 1});
     251             :       }
     252             :     }
     253             : 
     254         163 :     void addLoadEdge(Value *From, Value *To) { addDerefEdge(From, To, true); }
     255         153 :     void addStoreEdge(Value *From, Value *To) { addDerefEdge(From, To, false); }
     256             : 
     257             :   public:
     258         210 :     GetEdgesVisitor(CFLGraphBuilder &Builder, const DataLayout &DL)
     259         420 :         : AA(Builder.Analysis), DL(DL), TLI(Builder.TLI), Graph(Builder.Graph),
     260         420 :           ReturnValues(Builder.ReturnedValues) {}
     261             : 
     262             :     void visitInstruction(Instruction &) {
     263           0 :       llvm_unreachable("Unsupported instruction encountered");
     264             :     }
     265             : 
     266         210 :     void visitReturnInst(ReturnInst &Inst) {
     267         210 :       if (auto RetVal = Inst.getReturnValue()) {
     268         102 :         if (RetVal->getType()->isPointerTy()) {
     269          47 :           addNode(RetVal);
     270          47 :           ReturnValues.push_back(RetVal);
     271             :         }
     272             :       }
     273         210 :     }
     274             : 
     275          11 :     void visitPtrToIntInst(PtrToIntInst &Inst) {
     276          22 :       auto *Ptr = Inst.getOperand(0);
     277          11 :       addNode(Ptr, getAttrEscaped());
     278          11 :     }
     279             : 
     280             :     void visitIntToPtrInst(IntToPtrInst &Inst) {
     281           7 :       auto *Ptr = &Inst;
     282           7 :       addNode(Ptr, getAttrUnknown());
     283             :     }
     284             : 
     285             :     void visitCastInst(CastInst &Inst) {
     286         102 :       auto *Src = Inst.getOperand(0);
     287          51 :       addAssignEdge(Src, &Inst);
     288             :     }
     289             : 
     290          11 :     void visitBinaryOperator(BinaryOperator &Inst) {
     291          11 :       auto *Op1 = Inst.getOperand(0);
     292          11 :       auto *Op2 = Inst.getOperand(1);
     293          11 :       addAssignEdge(Op1, &Inst);
     294          11 :       addAssignEdge(Op2, &Inst);
     295          11 :     }
     296             : 
     297             :     void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
     298           0 :       auto *Ptr = Inst.getPointerOperand();
     299           0 :       auto *Val = Inst.getNewValOperand();
     300           0 :       addStoreEdge(Val, Ptr);
     301             :     }
     302             : 
     303             :     void visitAtomicRMWInst(AtomicRMWInst &Inst) {
     304           0 :       auto *Ptr = Inst.getPointerOperand();
     305           0 :       auto *Val = Inst.getValOperand();
     306           0 :       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          26 :       uint64_t Offset = UnknownOffset;
     316         130 :       APInt APOffset(DL.getPointerSizeInBits(GEPOp.getPointerAddressSpace()),
     317             :                      0);
     318          26 :       if (GEPOp.accumulateConstantOffset(DL, APOffset))
     319          19 :         Offset = APOffset.getSExtValue();
     320             : 
     321          26 :       auto *Op = GEPOp.getPointerOperand();
     322          26 :       addAssignEdge(Op, &GEPOp, Offset);
     323          26 :     }
     324             : 
     325             :     void visitGetElementPtrInst(GetElementPtrInst &Inst) {
     326          21 :       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          19 :       auto *TrueVal = Inst.getTrueValue();
     337          19 :       auto *FalseVal = Inst.getFalseValue();
     338          19 :       addAssignEdge(TrueVal, &Inst);
     339          19 :       addAssignEdge(FalseVal, &Inst);
     340          19 :     }
     341             : 
     342         252 :     void visitAllocaInst(AllocaInst &Inst) { addNode(&Inst); }
     343             : 
     344             :     void visitLoadInst(LoadInst &Inst) {
     345         162 :       auto *Ptr = Inst.getPointerOperand();
     346         162 :       auto *Val = &Inst;
     347         162 :       addLoadEdge(Ptr, Val);
     348             :     }
     349             : 
     350             :     void visitStoreInst(StoreInst &Inst) {
     351         153 :       auto *Ptr = Inst.getPointerOperand();
     352         153 :       auto *Val = Inst.getValueOperand();
     353         153 :       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         382 :       for (auto *Fn : Fns) {
     382         170 :         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         256 :       for (auto *Fn : Fns) {
     391          64 :         auto Summary = AA.getAliasSummary(*Fn);
     392             :         assert(Summary != nullptr);
     393             : 
     394          64 :         auto &RetParamRelations = Summary->RetParamRelations;
     395         220 :         for (auto &Relation : RetParamRelations) {
     396          56 :           auto IRelation = instantiateExternalRelation(Relation, CS);
     397          28 :           if (IRelation.hasValue()) {
     398          84 :             Graph.addNode(IRelation->From);
     399          84 :             Graph.addNode(IRelation->To);
     400          84 :             Graph.addEdge(IRelation->From, IRelation->To);
     401             :           }
     402             :         }
     403             : 
     404          64 :         auto &RetParamAttributes = Summary->RetParamAttributes;
     405         252 :         for (auto &Attribute : RetParamAttributes) {
     406         120 :           auto IAttr = instantiateExternalAttribute(Attribute, CS);
     407          60 :           if (IAttr.hasValue())
     408         180 :             Graph.addNode(IAttr->IValue, IAttr->Attr);
     409             :         }
     410             :       }
     411             : 
     412             :       return true;
     413             :     }
     414             : 
     415         143 :     void visitCallSite(CallSite CS) {
     416         143 :       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
     427             :       // on the heap. Those kinds of functions do not introduce any aliases.
     428             :       // TODO: address other common library functions such as realloc(),
     429             :       // strdup(),
     430             :       // etc.
     431         252 :       if (isMallocOrCallocLikeFn(Inst, &TLI) || isFreeCall(Inst, &TLI))
     432         100 :         return;
     433             : 
     434             :       // TODO: Add support for noalias args/all the other fun function
     435             :       // attributes
     436             :       // that we can tack on.
     437         150 :       SmallVector<Function *, 4> Targets;
     438         107 :       if (getPossibleTargets(CS, Targets))
     439         106 :         if (tryInterproceduralAnalysis(CS, Targets))
     440             :           return;
     441             : 
     442             :       // Because the function is opaque, we need to note that anything
     443             :       // could have happened to the arguments (unless the function is marked
     444             :       // readonly or readnone), and that the result could alias just about
     445             :       // anything, too (unless the result is marked noalias).
     446          43 :       if (!CS.onlyReadsMemory())
     447          70 :         for (Value *V : CS.args()) {
     448          70 :           if (V->getType()->isPointerTy()) {
     449             :             // The argument itself escapes.
     450          70 :             Graph.addAttr(InstantiatedValue{V, 0}, getAttrEscaped());
     451             :             // The fate of argument memory is unknown. Note that since
     452             :             // AliasAttrs is transitive with respect to dereference, we only
     453             :             // need to specify it for the first-level memory.
     454          35 :             Graph.addNode(InstantiatedValue{V, 1}, getAttrUnknown());
     455             :           }
     456             :         }
     457             : 
     458          86 :       if (Inst->getType()->isPointerTy()) {
     459           9 :         auto *Fn = CS.getCalledFunction();
     460           9 :         if (Fn == nullptr || !Fn->returnDoesNotAlias())
     461             :           // No need to call addNode() since we've added Inst at the
     462             :           // beginning of this function and we know it is not a global.
     463           6 :           Graph.addAttr(InstantiatedValue{Inst, 0}, getAttrUnknown());
     464             :       }
     465             :     }
     466             : 
     467             :     /// Because vectors/aggregates are immutable and unaddressable, there's
     468             :     /// nothing we can do to coax a value out of them, other than calling
     469             :     /// Extract{Element,Value}. We can effectively treat them as pointers to
     470             :     /// arbitrary memory locations we can store in and load from.
     471             :     void visitExtractElementInst(ExtractElementInst &Inst) {
     472           0 :       auto *Ptr = Inst.getVectorOperand();
     473           0 :       auto *Val = &Inst;
     474           0 :       addLoadEdge(Ptr, Val);
     475             :     }
     476             : 
     477           0 :     void visitInsertElementInst(InsertElementInst &Inst) {
     478           0 :       auto *Vec = Inst.getOperand(0);
     479           0 :       auto *Val = Inst.getOperand(1);
     480           0 :       addAssignEdge(Vec, &Inst);
     481           0 :       addStoreEdge(Val, &Inst);
     482           0 :     }
     483             : 
     484           0 :     void visitLandingPadInst(LandingPadInst &Inst) {
     485             :       // Exceptions come from "nowhere", from our analysis' perspective.
     486             :       // So we place the instruction its own group, noting that said group may
     487             :       // alias externals
     488           0 :       if (Inst.getType()->isPointerTy())
     489           0 :         addNode(&Inst, getAttrUnknown());
     490           0 :     }
     491             : 
     492           0 :     void visitInsertValueInst(InsertValueInst &Inst) {
     493           0 :       auto *Agg = Inst.getOperand(0);
     494           0 :       auto *Val = Inst.getOperand(1);
     495           0 :       addAssignEdge(Agg, &Inst);
     496           0 :       addStoreEdge(Val, &Inst);
     497           0 :     }
     498             : 
     499             :     void visitExtractValueInst(ExtractValueInst &Inst) {
     500           1 :       auto *Ptr = Inst.getAggregateOperand();
     501           2 :       addLoadEdge(Ptr, &Inst);
     502             :     }
     503             : 
     504           0 :     void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
     505           0 :       auto *From1 = Inst.getOperand(0);
     506           0 :       auto *From2 = Inst.getOperand(1);
     507           0 :       addAssignEdge(From1, &Inst);
     508           0 :       addAssignEdge(From2, &Inst);
     509           0 :     }
     510             : 
     511           5 :     void visitConstantExpr(ConstantExpr *CE) {
     512           5 :       switch (CE->getOpcode()) {
     513           5 :       case Instruction::GetElementPtr: {
     514           5 :         auto GEPOp = cast<GEPOperator>(CE);
     515           5 :         visitGEP(*GEPOp);
     516           5 :         break;
     517             :       }
     518           0 :       case Instruction::PtrToInt: {
     519           0 :         auto *Ptr = CE->getOperand(0);
     520           0 :         addNode(Ptr, getAttrEscaped());
     521           0 :         break;
     522             :       }
     523           0 :       case Instruction::IntToPtr:
     524           0 :         addNode(CE, getAttrUnknown());
     525           0 :         break;
     526             : 
     527           0 :       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 :         auto *Src = CE->getOperand(0);
     539           0 :         addAssignEdge(Src, CE);
     540           0 :         break;
     541             :       }
     542           0 :       case Instruction::Select: {
     543           0 :         auto *TrueVal = CE->getOperand(0);
     544           0 :         auto *FalseVal = CE->getOperand(1);
     545           0 :         addAssignEdge(TrueVal, CE);
     546           0 :         addAssignEdge(FalseVal, CE);
     547           0 :         break;
     548             :       }
     549           0 :       case Instruction::InsertElement: {
     550           0 :         auto *Vec = CE->getOperand(0);
     551           0 :         auto *Val = CE->getOperand(1);
     552           0 :         addAssignEdge(Vec, CE);
     553             :         addStoreEdge(Val, CE);
     554             :         break;
     555             :       }
     556           0 :       case Instruction::ExtractElement: {
     557           0 :         auto *Ptr = CE->getOperand(0);
     558             :         addLoadEdge(Ptr, CE);
     559             :         break;
     560             :       }
     561           0 :       case Instruction::InsertValue: {
     562           0 :         auto *Agg = CE->getOperand(0);
     563           0 :         auto *Val = CE->getOperand(1);
     564           0 :         addAssignEdge(Agg, CE);
     565             :         addStoreEdge(Val, CE);
     566             :         break;
     567             :       }
     568           0 :       case Instruction::ExtractValue: {
     569           0 :         auto *Ptr = CE->getOperand(0);
     570             :         addLoadEdge(Ptr, CE);
     571             :         break;
     572             :       }
     573           0 :       case Instruction::ShuffleVector: {
     574           0 :         auto *From1 = CE->getOperand(0);
     575           0 :         auto *From2 = CE->getOperand(1);
     576           0 :         addAssignEdge(From1, CE);
     577           0 :         addAssignEdge(From2, CE);
     578           0 :         break;
     579             :       }
     580           0 :       case Instruction::Add:
     581             :       case Instruction::Sub:
     582             :       case Instruction::FSub:
     583             :       case Instruction::Mul:
     584             :       case Instruction::FMul:
     585             :       case Instruction::UDiv:
     586             :       case Instruction::SDiv:
     587             :       case Instruction::FDiv:
     588             :       case Instruction::URem:
     589             :       case Instruction::SRem:
     590             :       case Instruction::FRem:
     591             :       case Instruction::And:
     592             :       case Instruction::Or:
     593             :       case Instruction::Xor:
     594             :       case Instruction::Shl:
     595             :       case Instruction::LShr:
     596             :       case Instruction::AShr:
     597             :       case Instruction::ICmp:
     598             :       case Instruction::FCmp:
     599           0 :         addAssignEdge(CE->getOperand(0), CE);
     600           0 :         addAssignEdge(CE->getOperand(1), CE);
     601           0 :         break;
     602             : 
     603           0 :       default:
     604           0 :         llvm_unreachable("Unknown instruction type encountered!");
     605             :       }
     606           5 :     }
     607             :   };
     608             : 
     609             :   // Helper functions
     610             : 
     611             :   // Determines whether or not we an instruction is useless to us (e.g.
     612             :   // FenceInst)
     613             :   static bool hasUsefulEdges(Instruction *Inst) {
     614        2356 :     bool IsNonInvokeRetTerminator = isa<TerminatorInst>(Inst) &&
     615        1291 :                                     !isa<InvokeInst>(Inst) &&
     616         226 :                                     !isa<ReturnInst>(Inst);
     617        3189 :     return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) &&
     618             :            !IsNonInvokeRetTerminator;
     619             :   }
     620             : 
     621         240 :   void addArgumentToGraph(Argument &Arg) {
     622         480 :     if (Arg.getType()->isPointerTy()) {
     623         222 :       Graph.addNode(InstantiatedValue{&Arg, 0},
     624             :                     getGlobalOrArgAttrFromValue(Arg));
     625             :       // Pointees of a formal parameter is known to the caller
     626         222 :       Graph.addNode(InstantiatedValue{&Arg, 1}, getAttrCaller());
     627             :     }
     628         240 :   }
     629             : 
     630             :   // Given an Instruction, this will add it to the graph, along with any
     631             :   // Instructions that are potentially only available from said Instruction
     632             :   // For example, given the following line:
     633             :   //   %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2
     634             :   // addInstructionToGraph would add both the `load` and `getelementptr`
     635             :   // instructions to the graph appropriately.
     636        1065 :   void addInstructionToGraph(GetEdgesVisitor &Visitor, Instruction &Inst) {
     637        1046 :     if (!hasUsefulEdges(&Inst))
     638             :       return;
     639             : 
     640        1046 :     Visitor.visit(Inst);
     641             :   }
     642             : 
     643             :   // Builds the graph needed for constructing the StratifiedSets for the given
     644             :   // function
     645         210 :   void buildGraphFrom(Function &Fn) {
     646         420 :     GetEdgesVisitor Visitor(*this, Fn.getParent()->getDataLayout());
     647             : 
     648         856 :     for (auto &Bb : Fn.getBasicBlockList())
     649        1743 :       for (auto &Inst : Bb.getInstList())
     650        1065 :         addInstructionToGraph(Visitor, Inst);
     651             : 
     652         450 :     for (auto &Arg : Fn.args())
     653         240 :       addArgumentToGraph(Arg);
     654         210 :   }
     655             : 
     656             : public:
     657         210 :   CFLGraphBuilder(CFLAA &Analysis, const TargetLibraryInfo &TLI, Function &Fn)
     658         630 :       : Analysis(Analysis), TLI(TLI) {
     659         210 :     buildGraphFrom(Fn);
     660         115 :   }
     661             : 
     662             :   const CFLGraph &getCFLGraph() const { return Graph; }
     663             :   const SmallVector<Value *, 4> &getReturnValues() const {
     664             :     return ReturnedValues;
     665             :   }
     666             : };
     667             : 
     668             : } // end namespace cflaa
     669             : } // end namespace llvm
     670             : 
     671             : #endif // LLVM_LIB_ANALYSIS_CFLGRAPH_H

Generated by: LCOV version 1.13