LLVM  6.0.0svn
CFLGraph.h
Go to the documentation of this file.
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"
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"
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:
62 
63  struct Edge {
65  int64_t Offset;
66  };
67 
68  using EdgeList = std::vector<Edge>;
69 
70  struct NodeInfo {
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 
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:
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:
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 
146  auto *Info = getNode(N);
147  assert(Info != nullptr);
148  return Info->Attr;
149  }
150 
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},
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;
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 
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.
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},
625  // Pointees of a formal parameter is known to the caller
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; }
664  return ReturnedValues;
665  }
666 };
667 
668 } // end namespace cflaa
669 } // end namespace llvm
670 
671 #endif // LLVM_LIB_ANALYSIS_CFLGRAPH_H
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
Definition: Function.h:158
Return a value (possibly void), from a function.
Value * getValueOperand()
Definition: Instructions.h:395
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
unsigned getOpcode() const
Return the opcode at the root of this constant expression.
Definition: Constants.h:1171
This instruction extracts a struct member or array element value from an aggregate value...
This class represents an incoming formal argument to a Function.
Definition: Argument.h:30
Base class for instruction visitors.
Definition: InstVisitor.h:81
unsigned arg_size() const
Definition: CallSite.h:219
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
const NodeInfo * getNode(Node N) const
Definition: CFLGraph.h:138
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
an instruction that atomically checks whether a specified value is in a memory location, and, if it is, stores a new value there.
Definition: Instructions.h:514
This is the result of instantiating InterfaceValue at a particular callsite.
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
The Program Expression Graph (PEG) of CFL analysis CFLGraph is auxiliary data structure used by CFL-b...
Definition: CFLGraph.h:59
iterator_range< IterTy > args() const
Definition: CallSite.h:215
const Value * getTrueValue() const
unsigned getPointerAddressSpace() const
Method to return the address space of the pointer operand.
Definition: Operator.h:468
bool addNodeToLevel(unsigned Level)
Definition: CFLGraph.h:79
This instruction constructs a fixed permutation of two input vectors.
unsigned getPointerSizeInBits(unsigned AS=0) const
Layout pointer size, in bits FIXME: The defaults need to be removed once all of the backends/clients ...
Definition: DataLayout.h:344
An instruction for reading from memory.
Definition: Instructions.h:164
an instruction that atomically reads a memory location, combines it with another value, and then stores the result back.
Definition: Instructions.h:677
bool accumulateConstantOffset(const DataLayout &DL, APInt &Offset) const
Accumulate the constant address offset of this GEP if possible.
Definition: Operator.cpp:35
const CallInst * isFreeCall(const Value *I, const TargetLibraryInfo *TLI)
isFreeCall - Returns non-null if the value is a call to the builtin free()
bool onlyReadsMemory() const
Determine if the call does not access or only reads memory.
Definition: CallSite.h:454
This class represents the LLVM &#39;select&#39; instruction.
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:560
InstrTy * getInstruction() const
Definition: CallSite.h:92
This file implements a class to represent arbitrary precision integral constant values and operations...
This class represents a cast from a pointer to an integer.
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:862
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1554
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
void addAttr(Node N, AliasAttrs Attr)
Definition: CFLGraph.h:122
An instruction for storing to memory.
Definition: Instructions.h:306
Value * getOperand(unsigned i) const
Definition: User.h:154
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:146
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:837
CFLGraphBuilder(CFLAA &Analysis, const TargetLibraryInfo &TLI, Function &Fn)
Definition: CFLGraph.h:657
This instruction inserts a single (scalar) element into a VectorType value.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
const NodeInfo & getNodeInfoAtLevel(unsigned Level) const
Definition: CFLGraph.h:91
bool returnDoesNotAlias() const
Determine if the parameter or return value is marked with NoAlias attribute.
Definition: Function.h:518
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:221
bool addNode(Node N, AliasAttrs Attr=AliasAttrs())
Definition: CFLGraph.h:114
AliasAttrs getAttrEscaped()
AttrEscaped represent whether the said pointer comes from a known source but escapes to the unknown w...
Optional< InstantiatedAttr > instantiateExternalAttribute(ExternalAttribute EAttr, CallSite CS)
std::vector< Edge > EdgeList
Definition: CFLGraph.h:68
Value * getPointerOperand()
Definition: Operator.h:449
size_t arg_size() const
Definition: Function.h:630
Value * getPointerOperand()
Definition: Instructions.h:270
unsigned getNumLevels() const
Definition: CFLGraph.h:96
This class represents a cast from an integer to a pointer.
const SmallVector< Value *, 4 > & getReturnValues() const
Definition: CFLGraph.h:663
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
AliasAttrs getAttrUnknown()
AttrUnknown represent whether the said pointer comes from a source not known to alias analyses (such ...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Value * getValOperand()
Definition: Instructions.h:783
A builder class used to create CFLGraph instance from a given function The CFL-AA that uses this buil...
Definition: CFLGraph.h:165
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Provides information about what library functions are available for the current target.
iterator_range< const_value_iterator > value_mappings() const
Definition: CFLGraph.h:151
void addEdge(Node From, Node To, int64_t Offset=0)
Definition: CFLGraph.h:128
This file defines various utility types and functions useful to summary-based alias analysis...
A range adaptor for a pair of iterators.
Class for arbitrary precision integers.
Definition: APInt.h:69
NodeInfo & getNodeInfoAtLevel(unsigned Level)
Definition: CFLGraph.h:87
const Value * getFalseValue() const
amdgpu Simplify well known AMD library false Value Value * Arg
block Block Frequency Analysis
static const int64_t UnknownOffset
AliasAttrs getGlobalOrArgAttrFromValue(const Value &Val)
AttrGlobal represent whether the said pointer is a global value.
iterator begin()
Definition: DenseMap.h:70
bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates memory similar to malloc or...
Value * getPointerOperand()
Definition: Instructions.h:779
bool hasExactDefinition() const
Return true if this global has an exact defintion.
Definition: GlobalValue.h:398
#define N
AliasAttrs attrFor(Node N) const
Definition: CFLGraph.h:145
iterator end()
Definition: DenseMap.h:79
std::bitset< NumAliasAttrs > AliasAttrs
These are attributes that an alias analysis can use to mark certain special properties of a given poi...
This instruction extracts a single (scalar) element from a VectorType value.
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:565
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
AliasAttrs getAttrCaller()
AttrCaller represent whether the said pointer comes from a source not known to the current function b...
FunTy * getCalledFunction() const
Return the function being called if this is a direct call, otherwise return null (if it&#39;s an indirect...
Definition: CallSite.h:107
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:556
LLVM Value Representation.
Definition: Value.h:73
const CFLGraph & getCFLGraph() const
Definition: CFLGraph.h:662
Optional< InstantiatedRelation > instantiateExternalRelation(ExternalRelation ERelation, CallSite CS)
static const unsigned MaxSupportedArgsInSummary
The maximum number of arguments we can put into a summary.
op_range incoming_values()
Value * getPointerOperand()
Definition: Instructions.h:398
iterator_range< arg_iterator > args()
Definition: Function.h:621
an instruction to allocate memory on the stack
Definition: Instructions.h:60
This instruction inserts a struct field of array element value into an aggregate value.