LLVM  9.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
185  // to check for compares.
186  return CE->getOpcode() != Instruction::ICmp &&
187  CE->getOpcode() != Instruction::FCmp;
188  }
189 
190  // Returns possible functions called by CS into the given SmallVectorImpl.
191  // Returns true if targets found, false otherwise.
192  static bool getPossibleTargets(CallBase &Call,
193  SmallVectorImpl<Function *> &Output) {
194  if (auto *Fn = Call.getCalledFunction()) {
195  Output.push_back(Fn);
196  return true;
197  }
198 
199  // TODO: If the call is indirect, we might be able to enumerate all
200  // potential
201  // targets of the call and return them, rather than just failing.
202  return false;
203  }
204 
205  void addNode(Value *Val, AliasAttrs Attr = AliasAttrs()) {
206  assert(Val != nullptr && Val->getType()->isPointerTy());
207  if (auto GVal = dyn_cast<GlobalValue>(Val)) {
208  if (Graph.addNode(InstantiatedValue{GVal, 0},
210  Graph.addNode(InstantiatedValue{GVal, 1}, getAttrUnknown());
211  } else if (auto CExpr = dyn_cast<ConstantExpr>(Val)) {
212  if (hasUsefulEdges(CExpr)) {
213  if (Graph.addNode(InstantiatedValue{CExpr, 0}))
214  visitConstantExpr(CExpr);
215  }
216  } else
217  Graph.addNode(InstantiatedValue{Val, 0}, Attr);
218  }
219 
220  void addAssignEdge(Value *From, Value *To, int64_t Offset = 0) {
221  assert(From != nullptr && To != nullptr);
222  if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
223  return;
224  addNode(From);
225  if (To != From) {
226  addNode(To);
228  Offset);
229  }
230  }
231 
232  void addDerefEdge(Value *From, Value *To, bool IsRead) {
233  assert(From != nullptr && To != nullptr);
234  // FIXME: This is subtly broken, due to how we model some instructions
235  // (e.g. extractvalue, extractelement) as loads. Since those take
236  // non-pointer operands, we'll entirely skip adding edges for those.
237  //
238  // addAssignEdge seems to have a similar issue with insertvalue, etc.
239  if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
240  return;
241  addNode(From);
242  addNode(To);
243  if (IsRead) {
244  Graph.addNode(InstantiatedValue{From, 1});
245  Graph.addEdge(InstantiatedValue{From, 1}, InstantiatedValue{To, 0});
246  } else {
247  Graph.addNode(InstantiatedValue{To, 1});
248  Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 1});
249  }
250  }
251 
252  void addLoadEdge(Value *From, Value *To) { addDerefEdge(From, To, true); }
253  void addStoreEdge(Value *From, Value *To) { addDerefEdge(From, To, false); }
254 
255  public:
256  GetEdgesVisitor(CFLGraphBuilder &Builder, const DataLayout &DL)
257  : AA(Builder.Analysis), DL(DL), TLI(Builder.TLI), Graph(Builder.Graph),
258  ReturnValues(Builder.ReturnedValues) {}
259 
260  void visitInstruction(Instruction &) {
261  llvm_unreachable("Unsupported instruction encountered");
262  }
263 
264  void visitReturnInst(ReturnInst &Inst) {
265  if (auto RetVal = Inst.getReturnValue()) {
266  if (RetVal->getType()->isPointerTy()) {
267  addNode(RetVal);
268  ReturnValues.push_back(RetVal);
269  }
270  }
271  }
272 
273  void visitPtrToIntInst(PtrToIntInst &Inst) {
274  auto *Ptr = Inst.getOperand(0);
275  addNode(Ptr, getAttrEscaped());
276  }
277 
278  void visitIntToPtrInst(IntToPtrInst &Inst) {
279  auto *Ptr = &Inst;
280  addNode(Ptr, getAttrUnknown());
281  }
282 
283  void visitCastInst(CastInst &Inst) {
284  auto *Src = Inst.getOperand(0);
285  addAssignEdge(Src, &Inst);
286  }
287 
288  void visitBinaryOperator(BinaryOperator &Inst) {
289  auto *Op1 = Inst.getOperand(0);
290  auto *Op2 = Inst.getOperand(1);
291  addAssignEdge(Op1, &Inst);
292  addAssignEdge(Op2, &Inst);
293  }
294 
295  void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
296  auto *Ptr = Inst.getPointerOperand();
297  auto *Val = Inst.getNewValOperand();
298  addStoreEdge(Val, Ptr);
299  }
300 
301  void visitAtomicRMWInst(AtomicRMWInst &Inst) {
302  auto *Ptr = Inst.getPointerOperand();
303  auto *Val = Inst.getValOperand();
304  addStoreEdge(Val, Ptr);
305  }
306 
307  void visitPHINode(PHINode &Inst) {
308  for (Value *Val : Inst.incoming_values())
309  addAssignEdge(Val, &Inst);
310  }
311 
312  void visitGEP(GEPOperator &GEPOp) {
313  uint64_t Offset = UnknownOffset;
315  0);
316  if (GEPOp.accumulateConstantOffset(DL, APOffset))
317  Offset = APOffset.getSExtValue();
318 
319  auto *Op = GEPOp.getPointerOperand();
320  addAssignEdge(Op, &GEPOp, Offset);
321  }
322 
323  void visitGetElementPtrInst(GetElementPtrInst &Inst) {
324  auto *GEPOp = cast<GEPOperator>(&Inst);
325  visitGEP(*GEPOp);
326  }
327 
328  void visitSelectInst(SelectInst &Inst) {
329  // Condition is not processed here (The actual statement producing
330  // the condition result is processed elsewhere). For select, the
331  // condition is evaluated, but not loaded, stored, or assigned
332  // simply as a result of being the condition of a select.
333 
334  auto *TrueVal = Inst.getTrueValue();
335  auto *FalseVal = Inst.getFalseValue();
336  addAssignEdge(TrueVal, &Inst);
337  addAssignEdge(FalseVal, &Inst);
338  }
339 
340  void visitAllocaInst(AllocaInst &Inst) { addNode(&Inst); }
341 
342  void visitLoadInst(LoadInst &Inst) {
343  auto *Ptr = Inst.getPointerOperand();
344  auto *Val = &Inst;
345  addLoadEdge(Ptr, Val);
346  }
347 
348  void visitStoreInst(StoreInst &Inst) {
349  auto *Ptr = Inst.getPointerOperand();
350  auto *Val = Inst.getValueOperand();
351  addStoreEdge(Val, Ptr);
352  }
353 
354  void visitVAArgInst(VAArgInst &Inst) {
355  // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it
356  // does
357  // two things:
358  // 1. Loads a value from *((T*)*Ptr).
359  // 2. Increments (stores to) *Ptr by some target-specific amount.
360  // For now, we'll handle this like a landingpad instruction (by placing
361  // the
362  // result in its own group, and having that group alias externals).
363  if (Inst.getType()->isPointerTy())
364  addNode(&Inst, getAttrUnknown());
365  }
366 
367  static bool isFunctionExternal(Function *Fn) {
368  return !Fn->hasExactDefinition();
369  }
370 
371  bool tryInterproceduralAnalysis(CallBase &Call,
372  const SmallVectorImpl<Function *> &Fns) {
373  assert(Fns.size() > 0);
374 
375  if (Call.arg_size() > MaxSupportedArgsInSummary)
376  return false;
377 
378  // Exit early if we'll fail anyway
379  for (auto *Fn : Fns) {
380  if (isFunctionExternal(Fn) || Fn->isVarArg())
381  return false;
382  // Fail if the caller does not provide enough arguments
383  assert(Fn->arg_size() <= Call.arg_size());
384  if (!AA.getAliasSummary(*Fn))
385  return false;
386  }
387 
388  for (auto *Fn : Fns) {
389  auto Summary = AA.getAliasSummary(*Fn);
390  assert(Summary != nullptr);
391 
392  auto &RetParamRelations = Summary->RetParamRelations;
393  for (auto &Relation : RetParamRelations) {
394  auto IRelation = instantiateExternalRelation(Relation, Call);
395  if (IRelation.hasValue()) {
396  Graph.addNode(IRelation->From);
397  Graph.addNode(IRelation->To);
398  Graph.addEdge(IRelation->From, IRelation->To);
399  }
400  }
401 
402  auto &RetParamAttributes = Summary->RetParamAttributes;
403  for (auto &Attribute : RetParamAttributes) {
404  auto IAttr = instantiateExternalAttribute(Attribute, Call);
405  if (IAttr.hasValue())
406  Graph.addNode(IAttr->IValue, IAttr->Attr);
407  }
408  }
409 
410  return true;
411  }
412 
413  void visitCallBase(CallBase &Call) {
414  // Make sure all arguments and return value are added to the graph first
415  for (Value *V : Call.args())
416  if (V->getType()->isPointerTy())
417  addNode(V);
418  if (Call.getType()->isPointerTy())
419  addNode(&Call);
420 
421  // Check if Inst is a call to a library function that
422  // allocates/deallocates on the heap. Those kinds of functions do not
423  // introduce any aliases.
424  // TODO: address other common library functions such as realloc(),
425  // strdup(), etc.
426  if (isMallocOrCallocLikeFn(&Call, &TLI) || isFreeCall(&Call, &TLI))
427  return;
428 
429  // TODO: Add support for noalias args/all the other fun function
430  // attributes that we can tack on.
432  if (getPossibleTargets(Call, Targets))
433  if (tryInterproceduralAnalysis(Call, Targets))
434  return;
435 
436  // Because the function is opaque, we need to note that anything
437  // could have happened to the arguments (unless the function is marked
438  // readonly or readnone), and that the result could alias just about
439  // anything, too (unless the result is marked noalias).
440  if (!Call.onlyReadsMemory())
441  for (Value *V : Call.args()) {
442  if (V->getType()->isPointerTy()) {
443  // The argument itself escapes.
444  Graph.addAttr(InstantiatedValue{V, 0}, getAttrEscaped());
445  // The fate of argument memory is unknown. Note that since
446  // AliasAttrs is transitive with respect to dereference, we only
447  // need to specify it for the first-level memory.
448  Graph.addNode(InstantiatedValue{V, 1}, getAttrUnknown());
449  }
450  }
451 
452  if (Call.getType()->isPointerTy()) {
453  auto *Fn = Call.getCalledFunction();
454  if (Fn == nullptr || !Fn->returnDoesNotAlias())
455  // No need to call addNode() since we've added Inst at the
456  // beginning of this function and we know it is not a global.
457  Graph.addAttr(InstantiatedValue{&Call, 0}, getAttrUnknown());
458  }
459  }
460 
461  /// Because vectors/aggregates are immutable and unaddressable, there's
462  /// nothing we can do to coax a value out of them, other than calling
463  /// Extract{Element,Value}. We can effectively treat them as pointers to
464  /// arbitrary memory locations we can store in and load from.
465  void visitExtractElementInst(ExtractElementInst &Inst) {
466  auto *Ptr = Inst.getVectorOperand();
467  auto *Val = &Inst;
468  addLoadEdge(Ptr, Val);
469  }
470 
471  void visitInsertElementInst(InsertElementInst &Inst) {
472  auto *Vec = Inst.getOperand(0);
473  auto *Val = Inst.getOperand(1);
474  addAssignEdge(Vec, &Inst);
475  addStoreEdge(Val, &Inst);
476  }
477 
478  void visitLandingPadInst(LandingPadInst &Inst) {
479  // Exceptions come from "nowhere", from our analysis' perspective.
480  // So we place the instruction its own group, noting that said group may
481  // alias externals
482  if (Inst.getType()->isPointerTy())
483  addNode(&Inst, getAttrUnknown());
484  }
485 
486  void visitInsertValueInst(InsertValueInst &Inst) {
487  auto *Agg = Inst.getOperand(0);
488  auto *Val = Inst.getOperand(1);
489  addAssignEdge(Agg, &Inst);
490  addStoreEdge(Val, &Inst);
491  }
492 
493  void visitExtractValueInst(ExtractValueInst &Inst) {
494  auto *Ptr = Inst.getAggregateOperand();
495  addLoadEdge(Ptr, &Inst);
496  }
497 
498  void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
499  auto *From1 = Inst.getOperand(0);
500  auto *From2 = Inst.getOperand(1);
501  addAssignEdge(From1, &Inst);
502  addAssignEdge(From2, &Inst);
503  }
504 
505  void visitConstantExpr(ConstantExpr *CE) {
506  switch (CE->getOpcode()) {
507  case Instruction::GetElementPtr: {
508  auto GEPOp = cast<GEPOperator>(CE);
509  visitGEP(*GEPOp);
510  break;
511  }
512 
513  case Instruction::PtrToInt: {
514  addNode(CE->getOperand(0), getAttrEscaped());
515  break;
516  }
517 
518  case Instruction::IntToPtr: {
519  addNode(CE, getAttrUnknown());
520  break;
521  }
522 
523  case Instruction::BitCast:
524  case Instruction::AddrSpaceCast:
525  case Instruction::Trunc:
526  case Instruction::ZExt:
527  case Instruction::SExt:
528  case Instruction::FPExt:
529  case Instruction::FPTrunc:
530  case Instruction::UIToFP:
531  case Instruction::SIToFP:
532  case Instruction::FPToUI:
533  case Instruction::FPToSI: {
534  addAssignEdge(CE->getOperand(0), CE);
535  break;
536  }
537 
538  case Instruction::Select: {
539  addAssignEdge(CE->getOperand(1), CE);
540  addAssignEdge(CE->getOperand(2), CE);
541  break;
542  }
543 
544  case Instruction::InsertElement:
545  case Instruction::InsertValue: {
546  addAssignEdge(CE->getOperand(0), CE);
547  addStoreEdge(CE->getOperand(1), CE);
548  break;
549  }
550 
551  case Instruction::ExtractElement:
552  case Instruction::ExtractValue: {
553  addLoadEdge(CE->getOperand(0), CE);
554  break;
555  }
556 
557  case Instruction::Add:
558  case Instruction::Sub:
559  case Instruction::FSub:
560  case Instruction::Mul:
561  case Instruction::FMul:
562  case Instruction::UDiv:
563  case Instruction::SDiv:
564  case Instruction::FDiv:
565  case Instruction::URem:
566  case Instruction::SRem:
567  case Instruction::FRem:
568  case Instruction::And:
569  case Instruction::Or:
570  case Instruction::Xor:
571  case Instruction::Shl:
572  case Instruction::LShr:
573  case Instruction::AShr:
574  case Instruction::ICmp:
575  case Instruction::FCmp:
576  case Instruction::ShuffleVector: {
577  addAssignEdge(CE->getOperand(0), CE);
578  addAssignEdge(CE->getOperand(1), CE);
579  break;
580  }
581 
582  default:
583  llvm_unreachable("Unknown instruction type encountered!");
584  }
585  }
586  };
587 
588  // Helper functions
589 
590  // Determines whether or not we an instruction is useless to us (e.g.
591  // FenceInst)
592  static bool hasUsefulEdges(Instruction *Inst) {
593  bool IsNonInvokeRetTerminator = Inst->isTerminator() &&
594  !isa<InvokeInst>(Inst) &&
595  !isa<ReturnInst>(Inst);
596  return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) &&
597  !IsNonInvokeRetTerminator;
598  }
599 
600  void addArgumentToGraph(Argument &Arg) {
601  if (Arg.getType()->isPointerTy()) {
602  Graph.addNode(InstantiatedValue{&Arg, 0},
604  // Pointees of a formal parameter is known to the caller
606  }
607  }
608 
609  // Given an Instruction, this will add it to the graph, along with any
610  // Instructions that are potentially only available from said Instruction
611  // For example, given the following line:
612  // %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2
613  // addInstructionToGraph would add both the `load` and `getelementptr`
614  // instructions to the graph appropriately.
615  void addInstructionToGraph(GetEdgesVisitor &Visitor, Instruction &Inst) {
616  if (!hasUsefulEdges(&Inst))
617  return;
618 
619  Visitor.visit(Inst);
620  }
621 
622  // Builds the graph needed for constructing the StratifiedSets for the given
623  // function
624  void buildGraphFrom(Function &Fn) {
625  GetEdgesVisitor Visitor(*this, Fn.getParent()->getDataLayout());
626 
627  for (auto &Bb : Fn.getBasicBlockList())
628  for (auto &Inst : Bb.getInstList())
629  addInstructionToGraph(Visitor, Inst);
630 
631  for (auto &Arg : Fn.args())
632  addArgumentToGraph(Arg);
633  }
634 
635 public:
636  CFLGraphBuilder(CFLAA &Analysis, const TargetLibraryInfo &TLI, Function &Fn)
637  : Analysis(Analysis), TLI(TLI) {
638  buildGraphFrom(Fn);
639  }
640 
641  const CFLGraph &getCFLGraph() const { return Graph; }
643  return ReturnedValues;
644  }
645 };
646 
647 } // end namespace cflaa
648 } // end namespace llvm
649 
650 #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:409
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
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:528
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:492
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:388
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1014
An instruction for reading from memory.
Definition: Instructions.h:167
an instruction that atomically reads a memory location, combines it with another value, and then stores the result back.
Definition: Instructions.h:691
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:353
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:1574
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
void addAttr(Node N, AliasAttrs Attr)
Definition: CFLGraph.h:120
An instruction for storing to memory.
Definition: Instructions.h:320
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:176
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:873
CFLGraphBuilder(CFLAA &Analysis, const TargetLibraryInfo &TLI, Function &Fn)
Definition: CFLGraph.h:636
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:1143
bool returnDoesNotAlias() const
Determine if the parameter or return value is marked with NoAlias attribute.
Definition: Function.h:585
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:223
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:473
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
size_t arg_size() const
Definition: Function.h:700
Value * getPointerOperand()
Definition: Instructions.h:284
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:642
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:1136
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Value * getValOperand()
Definition: Instructions.h:815
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:841
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:99
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:811
bool hasExactDefinition() const
Return true if this global has an exact defintion.
Definition: GlobalValue.h:406
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1201
bool onlyReadsMemory(unsigned OpNo) const
Definition: InstrTypes.h:1471
#define N
AliasAttrs attrFor(Node N) const
Definition: CFLGraph.h:143
iterator end()
Definition: DenseMap.h:108
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:635
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:565
LLVM Value Representation.
Definition: Value.h:72
const CFLGraph & getCFLGraph() const
Definition: CFLGraph.h:641
static const unsigned MaxSupportedArgsInSummary
The maximum number of arguments we can put into a summary.
op_range incoming_values()
Value * getPointerOperand()
Definition: Instructions.h:412
iterator_range< arg_iterator > args()
Definition: Function.h:691
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.