LLVM  13.0.0git
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 visitFreezeInst(FreezeInst &Inst) {
288  // Accessing freeze(ptr) is equivalent to accessing ptr.
289  // The former raises UB iff latter raises UB.
290  auto *Src = Inst.getOperand(0);
291  addAssignEdge(Src, &Inst);
292  }
293 
294  void visitBinaryOperator(BinaryOperator &Inst) {
295  auto *Op1 = Inst.getOperand(0);
296  auto *Op2 = Inst.getOperand(1);
297  addAssignEdge(Op1, &Inst);
298  addAssignEdge(Op2, &Inst);
299  }
300 
301  void visitUnaryOperator(UnaryOperator &Inst) {
302  auto *Src = Inst.getOperand(0);
303  addAssignEdge(Src, &Inst);
304  }
305 
306  void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
307  auto *Ptr = Inst.getPointerOperand();
308  auto *Val = Inst.getNewValOperand();
309  addStoreEdge(Val, Ptr);
310  }
311 
312  void visitAtomicRMWInst(AtomicRMWInst &Inst) {
313  auto *Ptr = Inst.getPointerOperand();
314  auto *Val = Inst.getValOperand();
315  addStoreEdge(Val, Ptr);
316  }
317 
318  void visitPHINode(PHINode &Inst) {
319  for (Value *Val : Inst.incoming_values())
320  addAssignEdge(Val, &Inst);
321  }
322 
323  void visitGEP(GEPOperator &GEPOp) {
324  uint64_t Offset = UnknownOffset;
325  APInt APOffset(DL.getPointerSizeInBits(GEPOp.getPointerAddressSpace()),
326  0);
327  if (GEPOp.accumulateConstantOffset(DL, APOffset))
328  Offset = APOffset.getSExtValue();
329 
330  auto *Op = GEPOp.getPointerOperand();
331  addAssignEdge(Op, &GEPOp, Offset);
332  }
333 
334  void visitGetElementPtrInst(GetElementPtrInst &Inst) {
335  auto *GEPOp = cast<GEPOperator>(&Inst);
336  visitGEP(*GEPOp);
337  }
338 
339  void visitSelectInst(SelectInst &Inst) {
340  // Condition is not processed here (The actual statement producing
341  // the condition result is processed elsewhere). For select, the
342  // condition is evaluated, but not loaded, stored, or assigned
343  // simply as a result of being the condition of a select.
344 
345  auto *TrueVal = Inst.getTrueValue();
346  auto *FalseVal = Inst.getFalseValue();
347  addAssignEdge(TrueVal, &Inst);
348  addAssignEdge(FalseVal, &Inst);
349  }
350 
351  void visitAllocaInst(AllocaInst &Inst) { addNode(&Inst); }
352 
353  void visitLoadInst(LoadInst &Inst) {
354  auto *Ptr = Inst.getPointerOperand();
355  auto *Val = &Inst;
356  addLoadEdge(Ptr, Val);
357  }
358 
359  void visitStoreInst(StoreInst &Inst) {
360  auto *Ptr = Inst.getPointerOperand();
361  auto *Val = Inst.getValueOperand();
362  addStoreEdge(Val, Ptr);
363  }
364 
365  void visitVAArgInst(VAArgInst &Inst) {
366  // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it
367  // does
368  // two things:
369  // 1. Loads a value from *((T*)*Ptr).
370  // 2. Increments (stores to) *Ptr by some target-specific amount.
371  // For now, we'll handle this like a landingpad instruction (by placing
372  // the
373  // result in its own group, and having that group alias externals).
374  if (Inst.getType()->isPointerTy())
375  addNode(&Inst, getAttrUnknown());
376  }
377 
378  static bool isFunctionExternal(Function *Fn) {
379  return !Fn->hasExactDefinition();
380  }
381 
382  bool tryInterproceduralAnalysis(CallBase &Call,
383  const SmallVectorImpl<Function *> &Fns) {
384  assert(Fns.size() > 0);
385 
386  if (Call.arg_size() > MaxSupportedArgsInSummary)
387  return false;
388 
389  // Exit early if we'll fail anyway
390  for (auto *Fn : Fns) {
391  if (isFunctionExternal(Fn) || Fn->isVarArg())
392  return false;
393  // Fail if the caller does not provide enough arguments
394  assert(Fn->arg_size() <= Call.arg_size());
395  if (!AA.getAliasSummary(*Fn))
396  return false;
397  }
398 
399  for (auto *Fn : Fns) {
400  auto Summary = AA.getAliasSummary(*Fn);
401  assert(Summary != nullptr);
402 
403  auto &RetParamRelations = Summary->RetParamRelations;
404  for (auto &Relation : RetParamRelations) {
405  auto IRelation = instantiateExternalRelation(Relation, Call);
406  if (IRelation.hasValue()) {
407  Graph.addNode(IRelation->From);
408  Graph.addNode(IRelation->To);
409  Graph.addEdge(IRelation->From, IRelation->To);
410  }
411  }
412 
413  auto &RetParamAttributes = Summary->RetParamAttributes;
414  for (auto &Attribute : RetParamAttributes) {
415  auto IAttr = instantiateExternalAttribute(Attribute, Call);
416  if (IAttr.hasValue())
417  Graph.addNode(IAttr->IValue, IAttr->Attr);
418  }
419  }
420 
421  return true;
422  }
423 
424  void visitCallBase(CallBase &Call) {
425  // Make sure all arguments and return value are added to the graph first
426  for (Value *V : Call.args())
427  if (V->getType()->isPointerTy())
428  addNode(V);
429  if (Call.getType()->isPointerTy())
430  addNode(&Call);
431 
432  // Check if Inst is a call to a library function that
433  // allocates/deallocates on the heap. Those kinds of functions do not
434  // introduce any aliases.
435  // TODO: address other common library functions such as realloc(),
436  // strdup(), etc.
437  if (isMallocOrCallocLikeFn(&Call, &TLI) || isFreeCall(&Call, &TLI))
438  return;
439 
440  // TODO: Add support for noalias args/all the other fun function
441  // attributes that we can tack on.
443  if (getPossibleTargets(Call, Targets))
444  if (tryInterproceduralAnalysis(Call, Targets))
445  return;
446 
447  // Because the function is opaque, we need to note that anything
448  // could have happened to the arguments (unless the function is marked
449  // readonly or readnone), and that the result could alias just about
450  // anything, too (unless the result is marked noalias).
451  if (!Call.onlyReadsMemory())
452  for (Value *V : Call.args()) {
453  if (V->getType()->isPointerTy()) {
454  // The argument itself escapes.
455  Graph.addAttr(InstantiatedValue{V, 0}, getAttrEscaped());
456  // The fate of argument memory is unknown. Note that since
457  // AliasAttrs is transitive with respect to dereference, we only
458  // need to specify it for the first-level memory.
459  Graph.addNode(InstantiatedValue{V, 1}, getAttrUnknown());
460  }
461  }
462 
463  if (Call.getType()->isPointerTy()) {
464  auto *Fn = Call.getCalledFunction();
465  if (Fn == nullptr || !Fn->returnDoesNotAlias())
466  // No need to call addNode() since we've added Inst at the
467  // beginning of this function and we know it is not a global.
468  Graph.addAttr(InstantiatedValue{&Call, 0}, getAttrUnknown());
469  }
470  }
471 
472  /// Because vectors/aggregates are immutable and unaddressable, there's
473  /// nothing we can do to coax a value out of them, other than calling
474  /// Extract{Element,Value}. We can effectively treat them as pointers to
475  /// arbitrary memory locations we can store in and load from.
476  void visitExtractElementInst(ExtractElementInst &Inst) {
477  auto *Ptr = Inst.getVectorOperand();
478  auto *Val = &Inst;
479  addLoadEdge(Ptr, Val);
480  }
481 
482  void visitInsertElementInst(InsertElementInst &Inst) {
483  auto *Vec = Inst.getOperand(0);
484  auto *Val = Inst.getOperand(1);
485  addAssignEdge(Vec, &Inst);
486  addStoreEdge(Val, &Inst);
487  }
488 
489  void visitLandingPadInst(LandingPadInst &Inst) {
490  // Exceptions come from "nowhere", from our analysis' perspective.
491  // So we place the instruction its own group, noting that said group may
492  // alias externals
493  if (Inst.getType()->isPointerTy())
494  addNode(&Inst, getAttrUnknown());
495  }
496 
497  void visitInsertValueInst(InsertValueInst &Inst) {
498  auto *Agg = Inst.getOperand(0);
499  auto *Val = Inst.getOperand(1);
500  addAssignEdge(Agg, &Inst);
501  addStoreEdge(Val, &Inst);
502  }
503 
504  void visitExtractValueInst(ExtractValueInst &Inst) {
505  auto *Ptr = Inst.getAggregateOperand();
506  addLoadEdge(Ptr, &Inst);
507  }
508 
509  void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
510  auto *From1 = Inst.getOperand(0);
511  auto *From2 = Inst.getOperand(1);
512  addAssignEdge(From1, &Inst);
513  addAssignEdge(From2, &Inst);
514  }
515 
516  void visitConstantExpr(ConstantExpr *CE) {
517  switch (CE->getOpcode()) {
518  case Instruction::GetElementPtr: {
519  auto GEPOp = cast<GEPOperator>(CE);
520  visitGEP(*GEPOp);
521  break;
522  }
523 
524  case Instruction::PtrToInt: {
525  addNode(CE->getOperand(0), getAttrEscaped());
526  break;
527  }
528 
529  case Instruction::IntToPtr: {
530  addNode(CE, getAttrUnknown());
531  break;
532  }
533 
534  case Instruction::BitCast:
535  case Instruction::AddrSpaceCast:
536  case Instruction::Trunc:
537  case Instruction::ZExt:
538  case Instruction::SExt:
539  case Instruction::FPExt:
540  case Instruction::FPTrunc:
541  case Instruction::UIToFP:
542  case Instruction::SIToFP:
543  case Instruction::FPToUI:
544  case Instruction::FPToSI: {
545  addAssignEdge(CE->getOperand(0), CE);
546  break;
547  }
548 
549  case Instruction::Select: {
550  addAssignEdge(CE->getOperand(1), CE);
551  addAssignEdge(CE->getOperand(2), CE);
552  break;
553  }
554 
555  case Instruction::InsertElement:
556  case Instruction::InsertValue: {
557  addAssignEdge(CE->getOperand(0), CE);
558  addStoreEdge(CE->getOperand(1), CE);
559  break;
560  }
561 
562  case Instruction::ExtractElement:
563  case Instruction::ExtractValue: {
564  addLoadEdge(CE->getOperand(0), CE);
565  break;
566  }
567 
568  case Instruction::Add:
569  case Instruction::FAdd:
570  case Instruction::Sub:
571  case Instruction::FSub:
572  case Instruction::Mul:
573  case Instruction::FMul:
574  case Instruction::UDiv:
575  case Instruction::SDiv:
576  case Instruction::FDiv:
577  case Instruction::URem:
578  case Instruction::SRem:
579  case Instruction::FRem:
580  case Instruction::And:
581  case Instruction::Or:
582  case Instruction::Xor:
583  case Instruction::Shl:
584  case Instruction::LShr:
585  case Instruction::AShr:
586  case Instruction::ICmp:
587  case Instruction::FCmp:
588  case Instruction::ShuffleVector: {
589  addAssignEdge(CE->getOperand(0), CE);
590  addAssignEdge(CE->getOperand(1), CE);
591  break;
592  }
593 
594  case Instruction::FNeg: {
595  addAssignEdge(CE->getOperand(0), CE);
596  break;
597  }
598 
599  default:
600  llvm_unreachable("Unknown instruction type encountered!");
601  }
602  }
603  };
604 
605  // Helper functions
606 
607  // Determines whether or not we an instruction is useless to us (e.g.
608  // FenceInst)
609  static bool hasUsefulEdges(Instruction *Inst) {
610  bool IsNonInvokeRetTerminator = Inst->isTerminator() &&
611  !isa<InvokeInst>(Inst) &&
612  !isa<ReturnInst>(Inst);
613  return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) &&
614  !IsNonInvokeRetTerminator;
615  }
616 
617  void addArgumentToGraph(Argument &Arg) {
618  if (Arg.getType()->isPointerTy()) {
619  Graph.addNode(InstantiatedValue{&Arg, 0},
621  // Pointees of a formal parameter is known to the caller
622  Graph.addNode(InstantiatedValue{&Arg, 1}, getAttrCaller());
623  }
624  }
625 
626  // Given an Instruction, this will add it to the graph, along with any
627  // Instructions that are potentially only available from said Instruction
628  // For example, given the following line:
629  // %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2
630  // addInstructionToGraph would add both the `load` and `getelementptr`
631  // instructions to the graph appropriately.
632  void addInstructionToGraph(GetEdgesVisitor &Visitor, Instruction &Inst) {
633  if (!hasUsefulEdges(&Inst))
634  return;
635 
636  Visitor.visit(Inst);
637  }
638 
639  // Builds the graph needed for constructing the StratifiedSets for the given
640  // function
641  void buildGraphFrom(Function &Fn) {
642  GetEdgesVisitor Visitor(*this, Fn.getParent()->getDataLayout());
643 
644  for (auto &Bb : Fn.getBasicBlockList())
645  for (auto &Inst : Bb.getInstList())
646  addInstructionToGraph(Visitor, Inst);
647 
648  for (auto &Arg : Fn.args())
649  addArgumentToGraph(Arg);
650  }
651 
652 public:
653  CFLGraphBuilder(CFLAA &Analysis, const TargetLibraryInfo &TLI, Function &Fn)
654  : Analysis(Analysis), TLI(TLI) {
655  buildGraphFrom(Fn);
656  }
657 
658  const CFLGraph &getCFLGraph() const { return Graph; }
660  return ReturnedValues;
661  }
662 };
663 
664 } // end namespace cflaa
665 } // end namespace llvm
666 
667 #endif // LLVM_LIB_ANALYSIS_CFLGRAPH_H
llvm::cflaa::CFLGraph
The Program Expression Graph (PEG) of CFL analysis CFLGraph is auxiliary data structure used by CFL-b...
Definition: CFLGraph.h:57
llvm::Instruction::isTerminator
bool isTerminator() const
Definition: Instruction.h:163
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
llvm::isMallocOrCallocLikeFn
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...
Definition: MemoryBuiltins.cpp:298
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::cflaa::CFLGraph::getNode
const NodeInfo * getNode(Node N) const
Definition: CFLGraph.h:136
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:2950
llvm::VAArgInst
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
Definition: Instructions.h:1835
llvm::PHINode::incoming_values
op_range incoming_values()
Definition: Instructions.h:2683
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:228
llvm::ValueMap::end
iterator end()
Definition: ValueMap.h:136
llvm::ExtractElementInst
This instruction extracts a single (scalar) element from a VectorType value.
Definition: Instructions.h:1875
llvm::Function
Definition: Function.h:61
llvm::Attribute
Definition: Attributes.h:52
llvm::cflaa::instantiateExternalAttribute
Optional< InstantiatedAttr > instantiateExternalAttribute(ExternalAttribute EAttr, CallBase &Call)
Definition: AliasAnalysisSummary.cpp:96
llvm::ReturnInst::getReturnValue
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
Definition: Instructions.h:2995
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::LandingPadInst
The landingpad instruction holds all of the information necessary to generate correct exception handl...
Definition: Instructions.h:2849
llvm::APInt::getSExtValue
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1643
ErrorHandling.h
llvm::cflaa::CFLGraph::NodeInfo::Attr
AliasAttrs Attr
Definition: CFLGraph.h:70
llvm::cflaa::CFLGraph::addAttr
void addAttr(Node N, AliasAttrs Attr)
Definition: CFLGraph.h:120
AliasAnalysisSummary.h
APInt.h
llvm::Function::arg_size
size_t arg_size() const
Definition: Function.h:826
llvm::DenseMapIterator
Definition: DenseMap.h:56
DenseMap.h
MemoryBuiltins.h
Analysis
block Block Frequency Analysis
Definition: BlockFrequencyInfo.cpp:302
llvm::cflaa::CFLGraph::attrFor
AliasAttrs attrFor(Node N) const
Definition: CFLGraph.h:143
llvm::cflaa::CFLGraph::Edge::Other
Node Other
Definition: CFLGraph.h:62
llvm::cflaa::CFLGraphBuilder
A builder class used to create CFLGraph instance from a given function The CFL-AA that uses this buil...
Definition: CFLGraph.h:163
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::tgtok::FalseVal
@ FalseVal
Definition: TGLexer.h:61
llvm::SelectInst::getFalseValue
const Value * getFalseValue() const
Definition: Instructions.h:1789
llvm::cflaa::CFLGraph::NodeInfo::ReverseEdges
EdgeList ReverseEdges
Definition: CFLGraph.h:69
Operator.h
llvm::cflaa::CFLGraph::addNode
bool addNode(Node N, AliasAttrs Attr=AliasAttrs())
Definition: CFLGraph.h:112
llvm::LoadInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:267
llvm::UnaryOperator
Definition: InstrTypes.h:102
llvm::AtomicRMWInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:865
llvm::DenseMapBase< DenseMap< Value *, ValueInfo, DenseMapInfo< Value * >, llvm::detail::DenseMapPair< Value *, ValueInfo > >, Value *, ValueInfo, DenseMapInfo< Value * >, llvm::detail::DenseMapPair< Value *, ValueInfo > >::const_iterator
DenseMapIterator< Value *, ValueInfo, DenseMapInfo< Value * >, llvm::detail::DenseMapPair< Value *, ValueInfo >, true > const_iterator
Definition: DenseMap.h:72
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
Instruction.h
llvm::StoreInst::getValueOperand
Value * getValueOperand()
Definition: Instructions.h:398
GlobalValue.h
llvm::GlobalValue::hasExactDefinition
bool hasExactDefinition() const
Return true if this global has an exact defintion.
Definition: GlobalValue.h:415
llvm::AtomicCmpXchgInst::getNewValOperand
Value * getNewValOperand()
Definition: Instructions.h:658
Constants.h
llvm::GEPOperator::getPointerOperand
Value * getPointerOperand()
Definition: Operator.h:499
InstrTypes.h
llvm::cflaa::CFLGraph::EdgeList
std::vector< Edge > EdgeList
Definition: CFLGraph.h:66
TargetLibraryInfo.h
llvm::InsertElementInst
This instruction inserts a single (scalar) element into a VectorType value.
Definition: Instructions.h:1939
llvm::Instruction
Definition: Instruction.h:45
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
llvm::ValueMap::begin
iterator begin()
Definition: ValueMap.h:135
llvm::cflaa::getAttrEscaped
AliasAttrs getAttrEscaped()
AttrEscaped represent whether the said pointer comes from a known source but escapes to the unknown w...
Definition: AliasAnalysisSummary.cpp:41
Type.h
llvm::cflaa::instantiateExternalRelation
Optional< InstantiatedRelation > instantiateExternalRelation(ExternalRelation ERelation, CallBase &Call)
Definition: AliasAnalysisSummary.cpp:86
BasicBlock.h
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:304
llvm::cflaa::CFLGraph::ValueInfo
Definition: CFLGraph.h:73
llvm::cflaa::CFLGraph::ValueInfo::getNodeInfoAtLevel
NodeInfo & getNodeInfoAtLevel(unsigned Level)
Definition: CFLGraph.h:85
llvm::DenseMap< Value *, ValueInfo >
llvm::cflaa::CFLGraphBuilder::getCFLGraph
const CFLGraph & getCFLGraph() const
Definition: CFLGraph.h:658
llvm::cflaa::getAttrUnknown
AliasAttrs getAttrUnknown()
AttrUnknown represent whether the said pointer comes from a source not known to alias analyses (such ...
Definition: AliasAnalysisSummary.cpp:32
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:928
llvm::SelectInst::getTrueValue
const Value * getTrueValue() const
Definition: Instructions.h:1788
llvm::cflaa::CFLGraph::addEdge
void addEdge(Node From, Node To, int64_t Offset=0)
Definition: CFLGraph.h:126
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ValueMapIterator::ValueTypeProxy::second
ValueT & second
Definition: ValueMap.h:346
llvm::cflaa::CFLGraphBuilder::getReturnValues
const SmallVector< Value *, 4 > & getReturnValues() const
Definition: CFLGraph.h:659
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1740
iterator_range.h
llvm::GEPOperator
Definition: Operator.h:458
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:70
llvm::cflaa::UnknownOffset
static const int64_t UnknownOffset
Definition: AliasAnalysisSummary.h:142
llvm::BinaryOperator
Definition: InstrTypes.h:189
DataLayout.h
InstVisitor.h
llvm::ExtractElementInst::getVectorOperand
Value * getVectorOperand()
Definition: Instructions.h:1904
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::PtrToIntInst
This class represents a cast from a pointer to an integer.
Definition: Instructions.h:5113
llvm::InstVisitor
Base class for instruction visitors.
Definition: InstVisitor.h:79
llvm::PICLevel::Level
Level
Definition: CodeGen.h:33
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:430
llvm::cflaa::getAttrCaller
AliasAttrs getAttrCaller()
AttrCaller represent whether the said pointer comes from a source not known to the current function b...
Definition: AliasAnalysisSummary.cpp:35
llvm::cflaa::CFLGraph::ValueInfo::getNodeInfoAtLevel
const NodeInfo & getNodeInfoAtLevel(unsigned Level) const
Definition: CFLGraph.h:89
Node
Definition: ItaniumDemangle.h:114
llvm::ValueMap
See the file comment.
Definition: ValueMap.h:85
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
llvm::AtomicRMWInst
an instruction that atomically reads a memory location, combines it with another value,...
Definition: Instructions.h:726
llvm::cflaa::CFLGraph::value_mappings
iterator_range< const_value_iterator > value_mappings() const
Definition: CFLGraph.h:149
Argument.h
llvm::cflaa::getGlobalOrArgAttrFromValue
AliasAttrs getGlobalOrArgAttrFromValue(const Value &Val)
AttrGlobal represent whether the said pointer is a global value.
Definition: AliasAnalysisSummary.cpp:52
llvm::cflaa::CFLGraph::Edge::Offset
int64_t Offset
Definition: CFLGraph.h:63
llvm::GEPOperator::getPointerAddressSpace
unsigned getPointerAddressSpace() const
Method to return the address space of the pointer operand.
Definition: Operator.h:518
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:162
llvm::Function::returnDoesNotAlias
bool returnDoesNotAlias() const
Determine if the parameter or return value is marked with NoAlias attribute.
Definition: Function.h:701
llvm::ConstantExpr
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:936
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::cflaa::InstantiatedValue
This is the result of instantiating InterfaceValue at a particular call.
Definition: AliasAnalysisSummary.h:202
llvm::ExtractValueInst
This instruction extracts a struct member or array element value from an aggregate value.
Definition: Instructions.h:2344
llvm::GEPOperator::accumulateConstantOffset
bool accumulateConstantOffset(const DataLayout &DL, APInt &Offset, function_ref< bool(Value &, APInt &)> ExternalAnalysis=nullptr) const
Accumulate the constant address offset of this GEP if possible.
Definition: Operator.cpp:61
Casting.h
Function.h
llvm::AtomicCmpXchgInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:651
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:219
llvm::ExtractValueInst::getAggregateOperand
Value * getAggregateOperand()
Definition: Instructions.h:2399
llvm::ValueMap::find
iterator find(const KeyT &Val)
Definition: ValueMap.h:156
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::IntToPtrInst
This class represents a cast from an integer to a pointer.
Definition: Instructions.h:5070
llvm::AtomicRMWInst::getValOperand
Value * getValOperand()
Definition: Instructions.h:869
llvm::Function::isVarArg
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
Definition: Function.h:188
llvm::ShuffleVectorInst
This instruction constructs a fixed permutation of two input vectors.
Definition: Instructions.h:2011
Instructions.h
SmallVector.h
llvm::StoreInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:401
llvm::FreezeInst
This class represents a freeze function that returns random concrete value if an operand is either a ...
Definition: Instructions.h:5324
N
#define N
llvm::cflaa::AliasAttrs
std::bitset< NumAliasAttrs > AliasAttrs
These are attributes that an alias analysis can use to mark certain special properties of a given poi...
Definition: AliasAnalysisSummary.h:61
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::PHINode
Definition: Instructions.h:2597
llvm::SmallVectorImpl< Value * >
llvm::cflaa::CFLGraph::NodeInfo
Definition: CFLGraph.h:68
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:62
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cflaa::CFLGraph::NodeInfo::Edges
EdgeList Edges
Definition: CFLGraph.h:69
llvm::InsertValueInst
This instruction inserts a struct field of array element value into an aggregate value.
Definition: Instructions.h:2455
llvm::tgtok::TrueVal
@ TrueVal
Definition: TGLexer.h:61
Value.h
llvm::cflaa::MaxSupportedArgsInSummary
static const unsigned MaxSupportedArgsInSummary
The maximum number of arguments we can put into a summary.
Definition: AliasAnalysisSummary.h:104
llvm::cflaa::CFLGraph::ValueInfo::getNumLevels
unsigned getNumLevels() const
Definition: CFLGraph.h:94
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::AtomicCmpXchgInst
An instruction that atomically checks whether a specified value is in a memory location,...
Definition: Instructions.h:521
llvm::isFreeCall
const CallInst * isFreeCall(const Value *I, const TargetLibraryInfo *TLI)
isFreeCall - Returns non-null if the value is a call to the builtin free()
Definition: MemoryBuiltins.cpp:487
llvm::cflaa::CFLGraph::Edge
Definition: CFLGraph.h:61
llvm::cflaa::CFLGraphBuilder::CFLGraphBuilder
CFLGraphBuilder(CFLAA &Analysis, const TargetLibraryInfo &TLI, Function &Fn)
Definition: CFLGraph.h:653
llvm::cflaa::CFLGraph::ValueInfo::addNodeToLevel
bool addNodeToLevel(unsigned Level)
Definition: CFLGraph.h:77