contrib/llvm/lib/Analysis/CFLGraph.h

   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 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   struct NodeInfo {
  71     EdgeList Edges, ReverseEdges;
  72     AliasAttrs Attr;
  73   };
  74
  75   class ValueInfo {
  76     std::vector<NodeInfo> Levels;
  77
  78   public:
  79     bool addNodeToLevel(unsigned Level) {
  80       auto NumLevels = Levels.size();
  81       if (NumLevels > Level)
  82         return false;
  83       Levels.resize(Level + 1);
  84       return true;
  85     }
  86
  87     NodeInfo &getNodeInfoAtLevel(unsigned Level) {
  88       assert(Level < Levels.size());
  89       return Levels[Level];
  90     }
  91     const NodeInfo &getNodeInfoAtLevel(unsigned Level) const {
  92       assert(Level < Levels.size());
  93       return Levels[Level];
  94     }
  95
  96     unsigned getNumLevels() const { return Levels.size(); }
  97   };
  98
  99 private:
 100   using ValueMap = DenseMap<Value *, ValueInfo>;
 101
 102   ValueMap ValueImpls;
 103
 104   NodeInfo *getNode(Node N) {
 105     auto Itr = ValueImpls.find(N.Val);
 106     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   bool addNode(Node N, AliasAttrs Attr = AliasAttrs()) {
 115     assert(N.Val != nullptr);
 116     auto &ValInfo = ValueImpls[N.Val];
 117     auto Changed = ValInfo.addNodeToLevel(N.DerefLevel);
 118     ValInfo.getNodeInfoAtLevel(N.DerefLevel).Attr |= Attr;
 119     return Changed;
 120   }
 121
 122   void addAttr(Node N, AliasAttrs Attr) {
 123     auto *Info = getNode(N);
 124     assert(Info != nullptr);
 125     Info->Attr |= Attr;
 126   }
 127
 128   void addEdge(Node From, Node To, int64_t Offset = 0) {
 129     auto *FromInfo = getNode(From);
 130     assert(FromInfo != nullptr);
 131     auto *ToInfo = getNode(To);
 132     assert(ToInfo != nullptr);
 133
 134     FromInfo->Edges.push_back(Edge{To, Offset});
 135     ToInfo->ReverseEdges.push_back(Edge{From, Offset});
 136   }
 137
 138   const NodeInfo *getNode(Node N) const {
 139     auto Itr = ValueImpls.find(N.Val);
 140     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                                             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 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       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     static bool getPossibleTargets(CallSite CS,
 195                                    SmallVectorImpl<Function *> &Output) {
 196       if (auto *Fn = CS.getCalledFunction()) {
 197         Output.push_back(Fn);
 198         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       return false;
 205     }
 206
 207     void addNode(Value *Val, AliasAttrs Attr = AliasAttrs()) {
 208       assert(Val != nullptr && Val->getType()->isPointerTy());
 209       if (auto GVal = dyn_cast<GlobalValue>(Val)) {
 210         if (Graph.addNode(InstantiatedValue{GVal, 0},
 211                           getGlobalOrArgAttrFromValue(*GVal)))
 212           Graph.addNode(InstantiatedValue{GVal, 1}, getAttrUnknown());
 213       } else if (auto CExpr = dyn_cast<ConstantExpr>(Val)) {
 214         if (hasUsefulEdges(CExpr)) {
 215           if (Graph.addNode(InstantiatedValue{CExpr, 0}))
 216             visitConstantExpr(CExpr);
 217         }
 218       } else
 219         Graph.addNode(InstantiatedValue{Val, 0}, Attr);
 220     }
 221
 222     void addAssignEdge(Value *From, Value *To, int64_t Offset = 0) {
 223       assert(From != nullptr && To != nullptr);
 224       if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
 225         return;
 226       addNode(From);
 227       if (To != From) {
 228         addNode(To);
 229         Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 0},
 230                       Offset);
 231       }
 232     }
 233
 234     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       if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
 242         return;
 243       addNode(From);
 244       addNode(To);
 245       if (IsRead) {
 246         Graph.addNode(InstantiatedValue{From, 1});
 247         Graph.addEdge(InstantiatedValue{From, 1}, InstantiatedValue{To, 0});
 248       } else {
 249         Graph.addNode(InstantiatedValue{To, 1});
 250         Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 1});
 251       }
 252     }
 253
 254     void addLoadEdge(Value *From, Value *To) { addDerefEdge(From, To, true); }
 255     void addStoreEdge(Value *From, Value *To) { addDerefEdge(From, To, false); }
 256
 257   public:
 258     GetEdgesVisitor(CFLGraphBuilder &Builder, const DataLayout &DL)
 259         : AA(Builder.Analysis), DL(DL), TLI(Builder.TLI), Graph(Builder.Graph),
 260           ReturnValues(Builder.ReturnedValues) {}
 261
 262     void visitInstruction(Instruction &) {
 263       llvm_unreachable("Unsupported instruction encountered");
 264     }
 265
 266     void visitReturnInst(ReturnInst &Inst) {
 267       if (auto RetVal = Inst.getReturnValue()) {
 268         if (RetVal->getType()->isPointerTy()) {
 269           addNode(RetVal);
 270           ReturnValues.push_back(RetVal);
 271         }
 272       }
 273     }
 274
 275     void visitPtrToIntInst(PtrToIntInst &Inst) {
 276       auto *Ptr = Inst.getOperand(0);
 277       addNode(Ptr, getAttrEscaped());
 278     }
 279
 280     void visitIntToPtrInst(IntToPtrInst &Inst) {
 281       auto *Ptr = &Inst;
 282       addNode(Ptr, getAttrUnknown());
 283     }
 284
 285     void visitCastInst(CastInst &Inst) {
 286       auto *Src = Inst.getOperand(0);
 287       addAssignEdge(Src, &Inst);
 288     }
 289
 290     void visitBinaryOperator(BinaryOperator &Inst) {
 291       auto *Op1 = Inst.getOperand(0);
 292       auto *Op2 = Inst.getOperand(1);
 293       addAssignEdge(Op1, &Inst);
 294       addAssignEdge(Op2, &Inst);
 295     }
 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     void visitPHINode(PHINode &Inst) {
 310       for (Value *Val : Inst.incoming_values())
 311         addAssignEdge(Val, &Inst);
 312     }
 313
 314     void visitGEP(GEPOperator &GEPOp) {
 315       uint64_t Offset = UnknownOffset;
 316       APInt APOffset(DL.getPointerSizeInBits(GEPOp.getPointerAddressSpace()),
 317                      0);
 318       if (GEPOp.accumulateConstantOffset(DL, APOffset))
 319         Offset = APOffset.getSExtValue();
 320
 321       auto *Op = GEPOp.getPointerOperand();
 322       addAssignEdge(Op, &GEPOp, Offset);
 323     }
 324
 325     void visitGetElementPtrInst(GetElementPtrInst &Inst) {
 326       auto *GEPOp = cast<GEPOperator>(&Inst);
 327       visitGEP(*GEPOp);
 328     }
 329
 330     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       addAssignEdge(TrueVal, &Inst);
 339       addAssignEdge(FalseVal, &Inst);
 340     }
 341
 342     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     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       if (Inst.getType()->isPointerTy())
 366         addNode(&Inst, getAttrUnknown());
 367     }
 368
 369     static bool isFunctionExternal(Function *Fn) {
 370       return !Fn->hasExactDefinition();
 371     }
 372
 373     bool tryInterproceduralAnalysis(CallSite CS,
 374                                     const SmallVectorImpl<Function *> &Fns) {
 375       assert(Fns.size() > 0);
 376
 377       if (CS.arg_size() > MaxSupportedArgsInSummary)
 378         return false;
 379
 380       // Exit early if we'll fail anyway
 381       for (auto *Fn : Fns) {
 382         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         if (!AA.getAliasSummary(*Fn))
 387           return false;
 388       }
 389
 390       for (auto *Fn : Fns) {
 391         auto Summary = AA.getAliasSummary(*Fn);
 392         assert(Summary != nullptr);
 393
 394         auto &RetParamRelations = Summary->RetParamRelations;
 395         for (auto &Relation : RetParamRelations) {
 396           auto IRelation = instantiateExternalRelation(Relation, CS);
 397           if (IRelation.hasValue()) {
 398             Graph.addNode(IRelation->From);
 399             Graph.addNode(IRelation->To);
 400             Graph.addEdge(IRelation->From, IRelation->To);
 401           }
 402         }
 403
 404         auto &RetParamAttributes = Summary->RetParamAttributes;
 405         for (auto &Attribute : RetParamAttributes) {
 406           auto IAttr = instantiateExternalAttribute(Attribute, CS);
 407           if (IAttr.hasValue())
 408             Graph.addNode(IAttr->IValue, IAttr->Attr);
 409         }
 410       }
 411
 412       return true;
 413     }
 414
 415     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       for (Value *V : CS.args())
 420         if (V->getType()->isPointerTy())
 421           addNode(V);
 422       if (Inst->getType()->isPointerTy())
 423         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       if (isMallocOrCallocLikeFn(Inst, &TLI) || isFreeCall(Inst, &TLI))
 432         return;
 433
 434       // TODO: Add support for noalias args/all the other fun function
 435       // attributes
 436       // that we can tack on.
 437       SmallVector<Function *, 4> Targets;
 438       if (getPossibleTargets(CS, Targets))
 439         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       if (!CS.onlyReadsMemory())
 447         for (Value *V : CS.args()) {
 448           if (V->getType()->isPointerTy()) {
 449             // The argument itself escapes.
 450             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             Graph.addNode(InstantiatedValue{V, 1}, getAttrUnknown());
 455           }
 456         }
 457
 458       if (Inst->getType()->isPointerTy()) {
 459         auto *Fn = CS.getCalledFunction();
 460         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           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       auto *Ptr = Inst.getVectorOperand();
 473       auto *Val = &Inst;
 474       addLoadEdge(Ptr, Val);
 475     }
 476
 477     void visitInsertElementInst(InsertElementInst &Inst) {
 478       auto *Vec = Inst.getOperand(0);
 479       auto *Val = Inst.getOperand(1);
 480       addAssignEdge(Vec, &Inst);
 481       addStoreEdge(Val, &Inst);
 482     }
 483
 484     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       if (Inst.getType()->isPointerTy())
 489         addNode(&Inst, getAttrUnknown());
 490     }
 491
 492     void visitInsertValueInst(InsertValueInst &Inst) {
 493       auto *Agg = Inst.getOperand(0);
 494       auto *Val = Inst.getOperand(1);
 495       addAssignEdge(Agg, &Inst);
 496       addStoreEdge(Val, &Inst);
 497     }
 498
 499     void visitExtractValueInst(ExtractValueInst &Inst) {
 500       auto *Ptr = Inst.getAggregateOperand();
 501       addLoadEdge(Ptr, &Inst);
 502     }
 503
 504     void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
 505       auto *From1 = Inst.getOperand(0);
 506       auto *From2 = Inst.getOperand(1);
 507       addAssignEdge(From1, &Inst);
 508       addAssignEdge(From2, &Inst);
 509     }
 510
 511     void visitConstantExpr(ConstantExpr *CE) {
 512       switch (CE->getOpcode()) {
 513       case Instruction::GetElementPtr: {
 514         auto GEPOp = cast<GEPOperator>(CE);
 515         visitGEP(*GEPOp);
 516         break;
 517       }
 518       case Instruction::PtrToInt: {
 519         auto *Ptr = CE->getOperand(0);
 520         addNode(Ptr, getAttrEscaped());
 521         break;
 522       }
 523       case Instruction::IntToPtr:
 524         addNode(CE, getAttrUnknown());
 525         break;
 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         auto *Src = CE->getOperand(0);
 539         addAssignEdge(Src, CE);
 540         break;
 541       }
 542       case Instruction::Select: {
 543         auto *TrueVal = CE->getOperand(0);
 544         auto *FalseVal = CE->getOperand(1);
 545         addAssignEdge(TrueVal, CE);
 546         addAssignEdge(FalseVal, CE);
 547         break;
 548       }
 549       case Instruction::InsertElement: {
 550         auto *Vec = CE->getOperand(0);
 551         auto *Val = CE->getOperand(1);
 552         addAssignEdge(Vec, CE);
 553         addStoreEdge(Val, CE);
 554         break;
 555       }
 556       case Instruction::ExtractElement: {
 557         auto *Ptr = CE->getOperand(0);
 558         addLoadEdge(Ptr, CE);
 559         break;
 560       }
 561       case Instruction::InsertValue: {
 562         auto *Agg = CE->getOperand(0);
 563         auto *Val = CE->getOperand(1);
 564         addAssignEdge(Agg, CE);
 565         addStoreEdge(Val, CE);
 566         break;
 567       }
 568       case Instruction::ExtractValue: {
 569         auto *Ptr = CE->getOperand(0);
 570         addLoadEdge(Ptr, CE);
 571         break;
 572       }
 573       case Instruction::ShuffleVector: {
 574         auto *From1 = CE->getOperand(0);
 575         auto *From2 = CE->getOperand(1);
 576         addAssignEdge(From1, CE);
 577         addAssignEdge(From2, CE);
 578         break;
 579       }
 580       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         addAssignEdge(CE->getOperand(0), CE);
 600         addAssignEdge(CE->getOperand(1), CE);
 601         break;
 602
 603       default:
 604         llvm_unreachable("Unknown instruction type encountered!");
 605       }
 606     }
 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     bool IsNonInvokeRetTerminator = isa<TerminatorInst>(Inst) &&
 615                                     !isa<InvokeInst>(Inst) &&
 616                                     !isa<ReturnInst>(Inst);
 617     return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) &&
 618            !IsNonInvokeRetTerminator;
 619   }
 620
 621   void addArgumentToGraph(Argument &Arg) {
 622     if (Arg.getType()->isPointerTy()) {
 623       Graph.addNode(InstantiatedValue{&Arg, 0},
 624                     getGlobalOrArgAttrFromValue(Arg));
 625       // Pointees of a formal parameter is known to the caller
 626       Graph.addNode(InstantiatedValue{&Arg, 1}, getAttrCaller());
 627     }
 628   }
 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   void addInstructionToGraph(GetEdgesVisitor &Visitor, Instruction &Inst) {
 637     if (!hasUsefulEdges(&Inst))
 638       return;
 639
 640     Visitor.visit(Inst);
 641   }
 642
 643   // Builds the graph needed for constructing the StratifiedSets for the given
 644   // function
 645   void buildGraphFrom(Function &Fn) {
 646     GetEdgesVisitor Visitor(*this, Fn.getParent()->getDataLayout());
 647
 648     for (auto &Bb : Fn.getBasicBlockList())
 649       for (auto &Inst : Bb.getInstList())
 650         addInstructionToGraph(Visitor, Inst);
 651
 652     for (auto &Arg : Fn.args())
 653       addArgumentToGraph(Arg);
 654   }
 655
 656 public:
 657   CFLGraphBuilder(CFLAA &Analysis, const TargetLibraryInfo &TLI, Function &Fn)
 658       : Analysis(Analysis), TLI(TLI) {
 659     buildGraphFrom(Fn);
 660   }
 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