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