contrib/llvm/lib/Analysis/CFLGraph.h

   1 //======- CFLGraph.h - Abstract stratified sets implementation. --------======//
   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 /// \file
  10 /// This file defines CFLGraph, an auxiliary data structure used by CFL-based
  11 /// alias analysis.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_ANALYSIS_CFLGRAPH_H
  16 #define LLVM_ANALYSIS_CFLGRAPH_H
  17
  18 #include "AliasAnalysisSummary.h"
  19 #include "llvm/Analysis/MemoryBuiltins.h"
  20 #include "llvm/IR/InstVisitor.h"
  21 #include "llvm/IR/Instructions.h"
  22
  23 namespace llvm {
  24 namespace cflaa {
  25
  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).
  36 class CFLGraph {
  37 public:
  38   typedef InstantiatedValue Node;
  39
  40   struct Edge {
  41     Node Other;
  42     int64_t Offset;
  43   };
  44
  45   typedef std::vector<Edge> EdgeList;
  46
  47   struct NodeInfo {
  48     EdgeList Edges, ReverseEdges;
  49     AliasAttrs Attr;
  50   };
  51
  52   class ValueInfo {
  53     std::vector<NodeInfo> Levels;
  54
  55   public:
  56     bool addNodeToLevel(unsigned Level) {
  57       auto NumLevels = Levels.size();
  58       if (NumLevels > Level)
  59         return false;
  60       Levels.resize(Level + 1);
  61       return true;
  62     }
  63
  64     NodeInfo &getNodeInfoAtLevel(unsigned Level) {
  65       assert(Level < Levels.size());
  66       return Levels[Level];
  67     }
  68     const NodeInfo &getNodeInfoAtLevel(unsigned Level) const {
  69       assert(Level < Levels.size());
  70       return Levels[Level];
  71     }
  72
  73     unsigned getNumLevels() const { return Levels.size(); }
  74   };
  75
  76 private:
  77   typedef DenseMap<Value *, ValueInfo> ValueMap;
  78   ValueMap ValueImpls;
  79
  80   NodeInfo *getNode(Node N) {
  81     auto Itr = ValueImpls.find(N.Val);
  82     if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel)
  83       return nullptr;
  84     return &Itr->second.getNodeInfoAtLevel(N.DerefLevel);
  85   }
  86
  87 public:
  88   typedef ValueMap::const_iterator const_value_iterator;
  89
  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;
  95     return Changed;
  96   }
  97
  98   void addAttr(Node N, AliasAttrs Attr) {
  99     auto *Info = getNode(N);
 100     assert(Info != nullptr);
 101     Info->Attr |= Attr;
 102   }
 103
 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);
 109
 110     FromInfo->Edges.push_back(Edge{To, Offset});
 111     ToInfo->ReverseEdges.push_back(Edge{From, Offset});
 112   }
 113
 114   const NodeInfo *getNode(Node N) const {
 115     auto Itr = ValueImpls.find(N.Val);
 116     if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel)
 117       return nullptr;
 118     return &Itr->second.getNodeInfoAtLevel(N.DerefLevel);
 119   }
 120
 121   AliasAttrs attrFor(Node N) const {
 122     auto *Info = getNode(N);
 123     assert(Info != nullptr);
 124     return Info->Attr;
 125   }
 126
 127   iterator_range<const_value_iterator> value_mappings() const {
 128     return make_range<const_value_iterator>(ValueImpls.begin(),
 129                                             ValueImpls.end());
 130   }
 131 };
 132
 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
 137 /// encountered.
 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
 143   CFLAA &Analysis;
 144   const TargetLibraryInfo &TLI;
 145
 146   // Output of the builder
 147   CFLGraph Graph;
 148   SmallVector<Value *, 4> ReturnedValues;
 149
 150   // Helper class
 151   /// Gets the edges our graph should have, based on an Instruction*
 152   class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
 153     CFLAA &AA;
 154     const DataLayout &DL;
 155     const TargetLibraryInfo &TLI;
 156
 157     CFLGraph &Graph;
 158     SmallVectorImpl<Value *> &ReturnValues;
 159
 160     static bool hasUsefulEdges(ConstantExpr *CE) {
 161       // ConstantExpr doesn't have terminators, invokes, or fences, so only
 162       // needs
 163       // to check for compares.
 164       return CE->getOpcode() != Instruction::ICmp &&
 165              CE->getOpcode() != Instruction::FCmp;
 166     }
 167
 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);
 174         return true;
 175       }
 176
 177       // TODO: If the call is indirect, we might be able to enumerate all
 178       // potential
 179       // targets of the call and return them, rather than just failing.
 180       return false;
 181     }
 182
 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);
 193         }
 194       } else
 195         Graph.addNode(InstantiatedValue{Val, 0}, Attr);
 196     }
 197
 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())
 201         return;
 202       addNode(From);
 203       if (To != From) {
 204         addNode(To);
 205         Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 0},
 206                       Offset);
 207       }
 208     }
 209
 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.
 215       //
 216       // addAssignEdge seems to have a similar issue with insertvalue, etc.
 217       if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
 218         return;
 219       addNode(From);
 220       addNode(To);
 221       if (IsRead) {
 222         Graph.addNode(InstantiatedValue{From, 1});
 223         Graph.addEdge(InstantiatedValue{From, 1}, InstantiatedValue{To, 0});
 224       } else {
 225         Graph.addNode(InstantiatedValue{To, 1});
 226         Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 1});
 227       }
 228     }
 229
 230     void addLoadEdge(Value *From, Value *To) { addDerefEdge(From, To, true); }
 231     void addStoreEdge(Value *From, Value *To) { addDerefEdge(From, To, false); }
 232
 233   public:
 234     GetEdgesVisitor(CFLGraphBuilder &Builder, const DataLayout &DL)
 235         : AA(Builder.Analysis), DL(DL), TLI(Builder.TLI), Graph(Builder.Graph),
 236           ReturnValues(Builder.ReturnedValues) {}
 237
 238     void visitInstruction(Instruction &) {
 239       llvm_unreachable("Unsupported instruction encountered");
 240     }
 241
 242     void visitReturnInst(ReturnInst &Inst) {
 243       if (auto RetVal = Inst.getReturnValue()) {
 244         if (RetVal->getType()->isPointerTy()) {
 245           addNode(RetVal);
 246           ReturnValues.push_back(RetVal);
 247         }
 248       }
 249     }
 250
 251     void visitPtrToIntInst(PtrToIntInst &Inst) {
 252       auto *Ptr = Inst.getOperand(0);
 253       addNode(Ptr, getAttrEscaped());
 254     }
 255
 256     void visitIntToPtrInst(IntToPtrInst &Inst) {
 257       auto *Ptr = &Inst;
 258       addNode(Ptr, getAttrUnknown());
 259     }
 260
 261     void visitCastInst(CastInst &Inst) {
 262       auto *Src = Inst.getOperand(0);
 263       addAssignEdge(Src, &Inst);
 264     }
 265
 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);
 271     }
 272
 273     void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
 274       auto *Ptr = Inst.getPointerOperand();
 275       auto *Val = Inst.getNewValOperand();
 276       addStoreEdge(Val, Ptr);
 277     }
 278
 279     void visitAtomicRMWInst(AtomicRMWInst &Inst) {
 280       auto *Ptr = Inst.getPointerOperand();
 281       auto *Val = Inst.getValOperand();
 282       addStoreEdge(Val, Ptr);
 283     }
 284
 285     void visitPHINode(PHINode &Inst) {
 286       for (Value *Val : Inst.incoming_values())
 287         addAssignEdge(Val, &Inst);
 288     }
 289
 290     void visitGEP(GEPOperator &GEPOp) {
 291       uint64_t Offset = UnknownOffset;
 292       APInt APOffset(DL.getPointerSizeInBits(GEPOp.getPointerAddressSpace()),
 293                      0);
 294       if (GEPOp.accumulateConstantOffset(DL, APOffset))
 295         Offset = APOffset.getSExtValue();
 296
 297       auto *Op = GEPOp.getPointerOperand();
 298       addAssignEdge(Op, &GEPOp, Offset);
 299     }
 300
 301     void visitGetElementPtrInst(GetElementPtrInst &Inst) {
 302       auto *GEPOp = cast<GEPOperator>(&Inst);
 303       visitGEP(*GEPOp);
 304     }
 305
 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.
 311
 312       auto *TrueVal = Inst.getTrueValue();
 313       auto *FalseVal = Inst.getFalseValue();
 314       addAssignEdge(TrueVal, &Inst);
 315       addAssignEdge(FalseVal, &Inst);
 316     }
 317
 318     void visitAllocaInst(AllocaInst &Inst) { addNode(&Inst); }
 319
 320     void visitLoadInst(LoadInst &Inst) {
 321       auto *Ptr = Inst.getPointerOperand();
 322       auto *Val = &Inst;
 323       addLoadEdge(Ptr, Val);
 324     }
 325
 326     void visitStoreInst(StoreInst &Inst) {
 327       auto *Ptr = Inst.getPointerOperand();
 328       auto *Val = Inst.getValueOperand();
 329       addStoreEdge(Val, Ptr);
 330     }
 331
 332     void visitVAArgInst(VAArgInst &Inst) {
 333       // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it
 334       // does
 335       // two things:
 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
 339       // the
 340       // result in its own group, and having that group alias externals).
 341       if (Inst.getType()->isPointerTy())
 342         addNode(&Inst, getAttrUnknown());
 343     }
 344
 345     static bool isFunctionExternal(Function *Fn) {
 346       return !Fn->hasExactDefinition();
 347     }
 348
 349     bool tryInterproceduralAnalysis(CallSite CS,
 350                                     const SmallVectorImpl<Function *> &Fns) {
 351       assert(Fns.size() > 0);
 352
 353       if (CS.arg_size() > MaxSupportedArgsInSummary)
 354         return false;
 355
 356       // Exit early if we'll fail anyway
 357       for (auto *Fn : Fns) {
 358         if (isFunctionExternal(Fn) || Fn->isVarArg())
 359           return false;
 360         // Fail if the caller does not provide enough arguments
 361         assert(Fn->arg_size() <= CS.arg_size());
 362         if (!AA.getAliasSummary(*Fn))
 363           return false;
 364       }
 365
 366       for (auto *Fn : Fns) {
 367         auto Summary = AA.getAliasSummary(*Fn);
 368         assert(Summary != nullptr);
 369
 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);
 377           }
 378         }
 379
 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);
 385         }
 386       }
 387
 388       return true;
 389     }
 390
 391     void visitCallSite(CallSite CS) {
 392       auto Inst = CS.getInstruction();
 393
 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())
 397           addNode(V);
 398       if (Inst->getType()->isPointerTy())
 399         addNode(Inst);
 400
 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(),
 405       // strdup(),
 406       // etc.
 407       if (isMallocOrCallocLikeFn(Inst, &TLI) || isFreeCall(Inst, &TLI))
 408         return;
 409
 410       // TODO: Add support for noalias args/all the other fun function
 411       // attributes
 412       // that we can tack on.
 413       SmallVector<Function *, 4> Targets;
 414       if (getPossibleTargets(CS, Targets))
 415         if (tryInterproceduralAnalysis(CS, Targets))
 416           return;
 417
 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());
 431           }
 432         }
 433
 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());
 440       }
 441     }
 442
 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();
 449       auto *Val = &Inst;
 450       addLoadEdge(Ptr, Val);
 451     }
 452
 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);
 458     }
 459
 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
 463       // alias externals
 464       if (Inst.getType()->isPointerTy())
 465         addNode(&Inst, getAttrUnknown());
 466     }
 467
 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);
 473     }
 474
 475     void visitExtractValueInst(ExtractValueInst &Inst) {
 476       auto *Ptr = Inst.getAggregateOperand();
 477       addLoadEdge(Ptr, &Inst);
 478     }
 479
 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);
 485     }
 486
 487     void visitConstantExpr(ConstantExpr *CE) {
 488       switch (CE->getOpcode()) {
 489       case Instruction::GetElementPtr: {
 490         auto GEPOp = cast<GEPOperator>(CE);
 491         visitGEP(*GEPOp);
 492         break;
 493       }
 494       case Instruction::PtrToInt: {
 495         auto *Ptr = CE->getOperand(0);
 496         addNode(Ptr, getAttrEscaped());
 497         break;
 498       }
 499       case Instruction::IntToPtr: {
 500         addNode(CE, getAttrUnknown());
 501         break;
 502       }
 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);
 516         break;
 517       }
 518       case Instruction::Select: {
 519         auto *TrueVal = CE->getOperand(0);
 520         auto *FalseVal = CE->getOperand(1);
 521         addAssignEdge(TrueVal, CE);
 522         addAssignEdge(FalseVal, CE);
 523         break;
 524       }
 525       case Instruction::InsertElement: {
 526         auto *Vec = CE->getOperand(0);
 527         auto *Val = CE->getOperand(1);
 528         addAssignEdge(Vec, CE);
 529         addStoreEdge(Val, CE);
 530         break;
 531       }
 532       case Instruction::ExtractElement: {
 533         auto *Ptr = CE->getOperand(0);
 534         addLoadEdge(Ptr, CE);
 535         break;
 536       }
 537       case Instruction::InsertValue: {
 538         auto *Agg = CE->getOperand(0);
 539         auto *Val = CE->getOperand(1);
 540         addAssignEdge(Agg, CE);
 541         addStoreEdge(Val, CE);
 542         break;
 543       }
 544       case Instruction::ExtractValue: {
 545         auto *Ptr = CE->getOperand(0);
 546         addLoadEdge(Ptr, CE);
 547         break;
 548       }
 549       case Instruction::ShuffleVector: {
 550         auto *From1 = CE->getOperand(0);
 551         auto *From2 = CE->getOperand(1);
 552         addAssignEdge(From1, CE);
 553         addAssignEdge(From2, CE);
 554         break;
 555       }
 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);
 577         break;
 578       }
 579       default:
 580         llvm_unreachable("Unknown instruction type encountered!");
 581       }
 582     }
 583   };
 584
 585   // Helper functions
 586
 587   // Determines whether or not we an instruction is useless to us (e.g.
 588   // FenceInst)
 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;
 595   }
 596
 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());
 603     }
 604   }
 605
 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))
 614       return;
 615
 616     Visitor.visit(Inst);
 617   }
 618
 619   // Builds the graph needed for constructing the StratifiedSets for the given
 620   // function
 621   void buildGraphFrom(Function &Fn) {
 622     GetEdgesVisitor Visitor(*this, Fn.getParent()->getDataLayout());
 623
 624     for (auto &Bb : Fn.getBasicBlockList())
 625       for (auto &Inst : Bb.getInstList())
 626         addInstructionToGraph(Visitor, Inst);
 627
 628     for (auto &Arg : Fn.args())
 629       addArgumentToGraph(Arg);
 630   }
 631
 632 public:
 633   CFLGraphBuilder(CFLAA &Analysis, const TargetLibraryInfo &TLI, Function &Fn)
 634       : Analysis(Analysis), TLI(TLI) {
 635     buildGraphFrom(Fn);
 636   }
 637
 638   const CFLGraph &getCFLGraph() const { return Graph; }
 639   const SmallVector<Value *, 4> &getReturnValues() const {
 640     return ReturnedValues;
 641   }
 642 };
 643 }
 644 }
 645
 646 #endif