LLVM  16.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 
85  NodeInfo &getNodeInfoAtLevel(unsigned Level) {
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) {
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)
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) ||
438  getFreedOperand(&Call, &TLI) != nullptr)
439  return;
440 
441  // TODO: Add support for noalias args/all the other fun function
442  // attributes that we can tack on.
444  if (getPossibleTargets(Call, Targets))
445  if (tryInterproceduralAnalysis(Call, Targets))
446  return;
447 
448  // Because the function is opaque, we need to note that anything
449  // could have happened to the arguments (unless the function is marked
450  // readonly or readnone), and that the result could alias just about
451  // anything, too (unless the result is marked noalias).
452  if (!Call.onlyReadsMemory())
453  for (Value *V : Call.args()) {
454  if (V->getType()->isPointerTy()) {
455  // The argument itself escapes.
456  Graph.addAttr(InstantiatedValue{V, 0}, getAttrEscaped());
457  // The fate of argument memory is unknown. Note that since
458  // AliasAttrs is transitive with respect to dereference, we only
459  // need to specify it for the first-level memory.
460  Graph.addNode(InstantiatedValue{V, 1}, getAttrUnknown());
461  }
462  }
463 
464  if (Call.getType()->isPointerTy()) {
465  auto *Fn = Call.getCalledFunction();
466  if (Fn == nullptr || !Fn->returnDoesNotAlias())
467  // No need to call addNode() since we've added Inst at the
468  // beginning of this function and we know it is not a global.
469  Graph.addAttr(InstantiatedValue{&Call, 0}, getAttrUnknown());
470  }
471  }
472 
473  /// Because vectors/aggregates are immutable and unaddressable, there's
474  /// nothing we can do to coax a value out of them, other than calling
475  /// Extract{Element,Value}. We can effectively treat them as pointers to
476  /// arbitrary memory locations we can store in and load from.
477  void visitExtractElementInst(ExtractElementInst &Inst) {
478  auto *Ptr = Inst.getVectorOperand();
479  auto *Val = &Inst;
480  addLoadEdge(Ptr, Val);
481  }
482 
483  void visitInsertElementInst(InsertElementInst &Inst) {
484  auto *Vec = Inst.getOperand(0);
485  auto *Val = Inst.getOperand(1);
486  addAssignEdge(Vec, &Inst);
487  addStoreEdge(Val, &Inst);
488  }
489 
490  void visitLandingPadInst(LandingPadInst &Inst) {
491  // Exceptions come from "nowhere", from our analysis' perspective.
492  // So we place the instruction its own group, noting that said group may
493  // alias externals
494  if (Inst.getType()->isPointerTy())
495  addNode(&Inst, getAttrUnknown());
496  }
497 
498  void visitInsertValueInst(InsertValueInst &Inst) {
499  auto *Agg = Inst.getOperand(0);
500  auto *Val = Inst.getOperand(1);
501  addAssignEdge(Agg, &Inst);
502  addStoreEdge(Val, &Inst);
503  }
504 
505  void visitExtractValueInst(ExtractValueInst &Inst) {
506  auto *Ptr = Inst.getAggregateOperand();
507  addLoadEdge(Ptr, &Inst);
508  }
509 
510  void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
511  auto *From1 = Inst.getOperand(0);
512  auto *From2 = Inst.getOperand(1);
513  addAssignEdge(From1, &Inst);
514  addAssignEdge(From2, &Inst);
515  }
516 
517  void visitConstantExpr(ConstantExpr *CE) {
518  switch (CE->getOpcode()) {
519  case Instruction::GetElementPtr: {
520  auto GEPOp = cast<GEPOperator>(CE);
521  visitGEP(*GEPOp);
522  break;
523  }
524 
525  case Instruction::PtrToInt: {
526  addNode(CE->getOperand(0), getAttrEscaped());
527  break;
528  }
529 
530  case Instruction::IntToPtr: {
531  addNode(CE, getAttrUnknown());
532  break;
533  }
534 
535  case Instruction::BitCast:
536  case Instruction::AddrSpaceCast:
537  case Instruction::Trunc:
538  case Instruction::ZExt:
539  case Instruction::SExt:
540  case Instruction::FPExt:
541  case Instruction::FPTrunc:
542  case Instruction::UIToFP:
543  case Instruction::SIToFP:
544  case Instruction::FPToUI:
545  case Instruction::FPToSI: {
546  addAssignEdge(CE->getOperand(0), CE);
547  break;
548  }
549 
550  case Instruction::Select: {
551  addAssignEdge(CE->getOperand(1), CE);
552  addAssignEdge(CE->getOperand(2), CE);
553  break;
554  }
555 
556  case Instruction::InsertElement:
557  case Instruction::InsertValue: {
558  addAssignEdge(CE->getOperand(0), CE);
559  addStoreEdge(CE->getOperand(1), CE);
560  break;
561  }
562 
563  case Instruction::ExtractElement:
564  case Instruction::ExtractValue: {
565  addLoadEdge(CE->getOperand(0), CE);
566  break;
567  }
568 
569  case Instruction::Add:
570  case Instruction::FAdd:
571  case Instruction::Sub:
572  case Instruction::FSub:
573  case Instruction::Mul:
574  case Instruction::FMul:
575  case Instruction::UDiv:
576  case Instruction::SDiv:
577  case Instruction::FDiv:
578  case Instruction::URem:
579  case Instruction::SRem:
580  case Instruction::FRem:
581  case Instruction::And:
582  case Instruction::Or:
583  case Instruction::Xor:
584  case Instruction::Shl:
585  case Instruction::LShr:
586  case Instruction::AShr:
587  case Instruction::ICmp:
588  case Instruction::FCmp:
589  case Instruction::ShuffleVector: {
590  addAssignEdge(CE->getOperand(0), CE);
591  addAssignEdge(CE->getOperand(1), CE);
592  break;
593  }
594 
595  case Instruction::FNeg: {
596  addAssignEdge(CE->getOperand(0), CE);
597  break;
598  }
599 
600  default:
601  llvm_unreachable("Unknown instruction type encountered!");
602  }
603  }
604  };
605 
606  // Helper functions
607 
608  // Determines whether or not we an instruction is useless to us (e.g.
609  // FenceInst)
610  static bool hasUsefulEdges(Instruction *Inst) {
611  bool IsNonInvokeRetTerminator = Inst->isTerminator() &&
612  !isa<InvokeInst>(Inst) &&
613  !isa<ReturnInst>(Inst);
614  return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) &&
615  !IsNonInvokeRetTerminator;
616  }
617 
618  void addArgumentToGraph(Argument &Arg) {
619  if (Arg.getType()->isPointerTy()) {
620  Graph.addNode(InstantiatedValue{&Arg, 0},
622  // Pointees of a formal parameter is known to the caller
623  Graph.addNode(InstantiatedValue{&Arg, 1}, getAttrCaller());
624  }
625  }
626 
627  // Given an Instruction, this will add it to the graph, along with any
628  // Instructions that are potentially only available from said Instruction
629  // For example, given the following line:
630  // %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2
631  // addInstructionToGraph would add both the `load` and `getelementptr`
632  // instructions to the graph appropriately.
633  void addInstructionToGraph(GetEdgesVisitor &Visitor, Instruction &Inst) {
634  if (!hasUsefulEdges(&Inst))
635  return;
636 
637  Visitor.visit(Inst);
638  }
639 
640  // Builds the graph needed for constructing the StratifiedSets for the given
641  // function
642  void buildGraphFrom(Function &Fn) {
643  GetEdgesVisitor Visitor(*this, Fn.getParent()->getDataLayout());
644 
645  for (auto &Bb : Fn.getBasicBlockList())
646  for (auto &Inst : Bb)
647  addInstructionToGraph(Visitor, Inst);
648 
649  for (auto &Arg : Fn.args())
650  addArgumentToGraph(Arg);
651  }
652 
653 public:
654  CFLGraphBuilder(CFLAA &Analysis, const TargetLibraryInfo &TLI, Function &Fn)
655  : Analysis(Analysis), TLI(TLI) {
656  buildGraphFrom(Fn);
657  }
658 
659  const CFLGraph &getCFLGraph() const { return Graph; }
661  return ReturnedValues;
662  }
663 };
664 
665 } // end namespace cflaa
666 } // end namespace llvm
667 
668 #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:172
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:3050
llvm::VAArgInst
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
Definition: Instructions.h:1830
llvm::PHINode::incoming_values
op_range incoming_values()
Definition: Instructions.h:2783
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:237
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:1870
llvm::Function
Definition: Function.h:60
llvm::Attribute
Definition: Attributes.h:66
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:3095
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::LandingPadInst
The landingpad instruction holds all of the information necessary to generate correct exception handl...
Definition: Instructions.h:2949
llvm::APInt::getSExtValue
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1498
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:755
llvm::DenseMapIterator
Definition: DenseMap.h:57
DenseMap.h
MemoryBuiltins.h
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
llvm::tgtok::FalseVal
@ FalseVal
Definition: TGLexer.h:62
llvm::SelectInst::getFalseValue
const Value * getFalseValue() const
Definition: Instructions.h:1784
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:261
llvm::UnaryOperator
Definition: InstrTypes.h:102
llvm::AtomicRMWInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:866
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:73
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:187
Instruction.h
llvm::StoreInst::getValueOperand
Value * getValueOperand()
Definition: Instructions.h:387
GlobalValue.h
llvm::GlobalValue::hasExactDefinition
bool hasExactDefinition() const
Return true if this global has an exact defintion.
Definition: GlobalValue.h:490
llvm::AtomicCmpXchgInst::getNewValOperand
Value * getNewValOperand()
Definition: Instructions.h:647
Constants.h
llvm::GEPOperator::getPointerOperand
Value * getPointerOperand()
Definition: Operator.h:417
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:1934
llvm::Instruction
Definition: Instruction.h:42
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::getFreedOperand
Value * getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI)
If this if a call to a free function, return the freed operand.
Definition: MemoryBuiltins.cpp:583
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:298
llvm::cflaa::CFLGraph::ValueInfo
Definition: CFLGraph.h:73
uint64_t
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:659
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:929
llvm::SelectInst::getTrueValue
const Value * getTrueValue() const
Definition: Instructions.h:1783
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:660
Ptr
@ Ptr
Definition: TargetLibraryInfo.cpp:60
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1735
iterator_range.h
llvm::GEPOperator
Definition: Operator.h:375
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::cflaa::UnknownOffset
static const int64_t UnknownOffset
Definition: AliasAnalysisSummary.h:142
llvm::BinaryOperator
Definition: InstrTypes.h:189
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
DataLayout.h
InstVisitor.h
llvm::ExtractElementInst::getVectorOperand
Value * getVectorOperand()
Definition: Instructions.h:1899
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
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:5202
llvm::InstVisitor
Base class for instruction visitors.
Definition: InstVisitor.h:78
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:156
llvm::ValueMap
See the file comment.
Definition: ValueMap.h:85
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
llvm::AtomicRMWInst
an instruction that atomically reads a memory location, combines it with another value,...
Definition: Instructions.h:715
Analysis
block Block Frequency Analysis
Definition: BlockFrequencyInfo.cpp:301
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:436
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:164
llvm::Function::returnDoesNotAlias
bool returnDoesNotAlias() const
Determine if the parameter or return value is marked with NoAlias attribute.
Definition: Function.h:633
llvm::ConstantExpr
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:972
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
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:2444
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:86
Casting.h
Function.h
llvm::AtomicCmpXchgInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:640
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:226
llvm::ExtractValueInst::getAggregateOperand
Value * getAggregateOperand()
Definition: Instructions.h:2499
llvm::ValueMap::find
iterator find(const KeyT &Val)
Definition: ValueMap.h:156
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
llvm::IntToPtrInst
This class represents a cast from an integer to a pointer.
Definition: Instructions.h:5159
llvm::AtomicRMWInst::getValOperand
Value * getValOperand()
Definition: Instructions.h:870
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:2006
Instructions.h
SmallVector.h
llvm::StoreInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:390
llvm::FreezeInst
This class represents a freeze function that returns random concrete value if an operand is either a ...
Definition: Instructions.h:5435
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:2697
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:1175
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:59
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:2555
llvm::tgtok::TrueVal
@ TrueVal
Definition: TGLexer.h:62
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:74
llvm::AtomicCmpXchgInst
An instruction that atomically checks whether a specified value is in a memory location,...
Definition: Instructions.h:510
llvm::isMallocOrCallocLikeFn
bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates memory similar to malloc or...
Definition: MemoryBuiltins.cpp:333
llvm::cflaa::CFLGraph::Edge
Definition: CFLGraph.h:61
llvm::cflaa::CFLGraphBuilder::CFLGraphBuilder
CFLGraphBuilder(CFLAA &Analysis, const TargetLibraryInfo &TLI, Function &Fn)
Definition: CFLGraph.h:654
llvm::cflaa::CFLGraph::ValueInfo::addNodeToLevel
bool addNodeToLevel(unsigned Level)
Definition: CFLGraph.h:77