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