LCOV - code coverage report
Current view: top level - lib/Analysis - CFLGraph.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 164 193 85.0 %
Date: 2018-06-17 00:07:59 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             : /// 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         327 : 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        4408 :   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        3032 :       return Levels[Level];
      90             :     }
      91             :     const NodeInfo &getNodeInfoAtLevel(unsigned Level) const {
      92             :       assert(Level < Levels.size());
      93        3912 :       return Levels[Level];
      94             :     }
      95             : 
      96       11806 :     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        1726 :     if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel)
     107             :       return nullptr;
     108             :     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         822 :     FromInfo->Edges.push_back(Edge{To, Offset});
     135         822 :     ToInfo->ReverseEdges.push_back(Edge{From, Offset});
     136         411 :   }
     137             : 
     138        3370 :   const NodeInfo *getNode(Node N) const {
     139        3370 :     auto Itr = ValueImpls.find(N.Val);
     140        6740 :     if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel)
     141             :       return nullptr;
     142             :     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         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         422 : 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         413 :       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         924 :       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         167 :     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         422 :         : AA(Builder.Analysis), DL(DL), TLI(Builder.TLI), Graph(Builder.Graph),
     260         422 :           ReturnValues(Builder.ReturnedValues) {}
     261             : 
     262             :     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          20 :       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         234 :       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         192 :       for (auto *Fn : Fns) {
     391          64 :         auto Summary = AA.getAliasSummary(*Fn);
     392             :         assert(Summary != nullptr);
     393             : 
     394             :         auto &RetParamRelations = Summary->RetParamRelations;
     395         120 :         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         184 :         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         252 :       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           6 :           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         227 :     bool IsNonInvokeRetTerminator = isa<TerminatorInst>(Inst) &&
     598        1299 :                                     !isa<InvokeInst>(Inst) &&
     599             :                                     !isa<ReturnInst>(Inst);
     600        1069 :     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        1072 :   void addInstructionToGraph(GetEdgesVisitor &Visitor, Instruction &Inst) {
     620             :     if (!hasUsefulEdges(&Inst))
     621             :       return;
     622             : 
     623        1053 :     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

Generated by: LCOV version 1.13