LLVM  10.0.0svn
Attributor.h
Go to the documentation of this file.
1 //===- Attributor.h --- Module-wide attribute deduction ---------*- 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 // Attributor: An inter procedural (abstract) "attribute" deduction framework.
10 //
11 // The Attributor framework is an inter procedural abstract analysis (fixpoint
12 // iteration analysis). The goal is to allow easy deduction of new attributes as
13 // well as information exchange between abstract attributes in-flight.
14 //
15 // The Attributor class is the driver and the link between the various abstract
16 // attributes. The Attributor will iterate until a fixpoint state is reached by
17 // all abstract attributes in-flight, or until it will enforce a pessimistic fix
18 // point because an iteration limit is reached.
19 //
20 // Abstract attributes, derived from the AbstractAttribute class, actually
21 // describe properties of the code. They can correspond to actual LLVM-IR
22 // attributes, or they can be more general, ultimately unrelated to LLVM-IR
23 // attributes. The latter is useful when an abstract attributes provides
24 // information to other abstract attributes in-flight but we might not want to
25 // manifest the information. The Attributor allows to query in-flight abstract
26 // attributes through the `Attributor::getAAFor` method (see the method
27 // description for an example). If the method is used by an abstract attribute
28 // P, and it results in an abstract attribute Q, the Attributor will
29 // automatically capture a potential dependence from Q to P. This dependence
30 // will cause P to be reevaluated whenever Q changes in the future.
31 //
32 // The Attributor will only reevaluated abstract attributes that might have
33 // changed since the last iteration. That means that the Attribute will not
34 // revisit all instructions/blocks/functions in the module but only query
35 // an update from a subset of the abstract attributes.
36 //
37 // The update method `AbstractAttribute::updateImpl` is implemented by the
38 // specific "abstract attribute" subclasses. The method is invoked whenever the
39 // currently assumed state (see the AbstractState class) might not be valid
40 // anymore. This can, for example, happen if the state was dependent on another
41 // abstract attribute that changed. In every invocation, the update method has
42 // to adjust the internal state of an abstract attribute to a point that is
43 // justifiable by the underlying IR and the current state of abstract attributes
44 // in-flight. Since the IR is given and assumed to be valid, the information
45 // derived from it can be assumed to hold. However, information derived from
46 // other abstract attributes is conditional on various things. If the justifying
47 // state changed, the `updateImpl` has to revisit the situation and potentially
48 // find another justification or limit the optimistic assumes made.
49 //
50 // Change is the key in this framework. Until a state of no-change, thus a
51 // fixpoint, is reached, the Attributor will query the abstract attributes
52 // in-flight to re-evaluate their state. If the (current) state is too
53 // optimistic, hence it cannot be justified anymore through other abstract
54 // attributes or the state of the IR, the state of the abstract attribute will
55 // have to change. Generally, we assume abstract attribute state to be a finite
56 // height lattice and the update function to be monotone. However, these
57 // conditions are not enforced because the iteration limit will guarantee
58 // termination. If an optimistic fixpoint is reached, or a pessimistic fix
59 // point is enforced after a timeout, the abstract attributes are tasked to
60 // manifest their result in the IR for passes to come.
61 //
62 // Attribute manifestation is not mandatory. If desired, there is support to
63 // generate a single or multiple LLVM-IR attributes already in the helper struct
64 // IRAttribute. In the simplest case, a subclass inherits from IRAttribute with
65 // a proper Attribute::AttrKind as template parameter. The Attributor
66 // manifestation framework will then create and place a new attribute if it is
67 // allowed to do so (based on the abstract state). Other use cases can be
68 // achieved by overloading AbstractAttribute or IRAttribute methods.
69 //
70 //
71 // The "mechanics" of adding a new "abstract attribute":
72 // - Define a class (transitively) inheriting from AbstractAttribute and one
73 // (which could be the same) that (transitively) inherits from AbstractState.
74 // For the latter, consider the already available BooleanState and
75 // IntegerState if they fit your needs, e.g., you require only a bit-encoding.
76 // - Implement all pure methods. Also use overloading if the attribute is not
77 // conforming with the "default" behavior: A (set of) LLVM-IR attribute(s) for
78 // an argument, call site argument, function return value, or function. See
79 // the class and method descriptions for more information on the two
80 // "Abstract" classes and their respective methods.
81 // - Register opportunities for the new abstract attribute in the
82 // `Attributor::identifyDefaultAbstractAttributes` method if it should be
83 // counted as a 'default' attribute.
84 // - Add sufficient tests.
85 // - Add a Statistics object for bookkeeping. If it is a simple (set of)
86 // attribute(s) manifested through the Attributor manifestation framework, see
87 // the bookkeeping function in Attributor.cpp.
88 // - If instructions with a certain opcode are interesting to the attribute, add
89 // that opcode to the switch in `Attributor::identifyAbstractAttributes`. This
90 // will make it possible to query all those instructions through the
91 // `InformationCache::getOpcodeInstMapForFunction` interface and eliminate the
92 // need to traverse the IR repeatedly.
93 //
94 //===----------------------------------------------------------------------===//
95 
96 #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
97 #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
98 
99 #include "llvm/ADT/MapVector.h"
100 #include "llvm/ADT/SCCIterator.h"
101 #include "llvm/ADT/SetVector.h"
103 #include "llvm/Analysis/CallGraph.h"
106 #include "llvm/IR/CallSite.h"
107 #include "llvm/IR/PassManager.h"
108 
109 namespace llvm {
110 
111 struct AbstractAttribute;
112 struct InformationCache;
113 struct AAIsDead;
114 
115 class Function;
116 
117 /// Simple enum class that forces the status to be spelled out explicitly.
118 ///
119 ///{
120 enum class ChangeStatus {
121  CHANGED,
122  UNCHANGED,
123 };
124 
127 ///}
128 
129 /// Helper to describe and deal with positions in the LLVM-IR.
130 ///
131 /// A position in the IR is described by an anchor value and an "offset" that
132 /// could be the argument number, for call sites and arguments, or an indicator
133 /// of the "position kind". The kinds, specified in the Kind enum below, include
134 /// the locations in the attribute list, i.a., function scope and return value,
135 /// as well as a distinction between call sites and functions. Finally, there
136 /// are floating values that do not have a corresponding attribute list
137 /// position.
138 struct IRPosition {
139  virtual ~IRPosition() {}
140 
141  /// The positions we distinguish in the IR.
142  ///
143  /// The values are chosen such that the KindOrArgNo member has a value >= 1
144  /// if it is an argument or call site argument while a value < 1 indicates the
145  /// respective kind of that value.
146  enum Kind : int {
147  IRP_INVALID = -6, ///< An invalid position.
148  IRP_FLOAT = -5, ///< A position that is not associated with a spot suitable
149  ///< for attributes. This could be any value or instruction.
150  IRP_RETURNED = -4, ///< An attribute for the function return value.
151  IRP_CALL_SITE_RETURNED = -3, ///< An attribute for a call site return value.
152  IRP_FUNCTION = -2, ///< An attribute for a function (scope).
153  IRP_CALL_SITE = -1, ///< An attribute for a call site (function scope).
154  IRP_ARGUMENT = 0, ///< An attribute for a function argument.
155  IRP_CALL_SITE_ARGUMENT = 1, ///< An attribute for a call site argument.
156  };
157 
158  /// Default constructor available to create invalid positions implicitly. All
159  /// other positions need to be created explicitly through the appropriate
160  /// static member function.
161  IRPosition() : AnchorVal(nullptr), KindOrArgNo(IRP_INVALID) { verify(); }
162 
163  /// Create a position describing the value of \p V.
164  static const IRPosition value(const Value &V) {
165  if (auto *Arg = dyn_cast<Argument>(&V))
166  return IRPosition::argument(*Arg);
167  if (auto *CB = dyn_cast<CallBase>(&V))
168  return IRPosition::callsite_returned(*CB);
169  return IRPosition(const_cast<Value &>(V), IRP_FLOAT);
170  }
171 
172  /// Create a position describing the function scope of \p F.
173  static const IRPosition function(const Function &F) {
174  return IRPosition(const_cast<Function &>(F), IRP_FUNCTION);
175  }
176 
177  /// Create a position describing the returned value of \p F.
178  static const IRPosition returned(const Function &F) {
179  return IRPosition(const_cast<Function &>(F), IRP_RETURNED);
180  }
181 
182  /// Create a position describing the argument \p Arg.
183  static const IRPosition argument(const Argument &Arg) {
184  return IRPosition(const_cast<Argument &>(Arg), Kind(Arg.getArgNo()));
185  }
186 
187  /// Create a position describing the function scope of \p CB.
188  static const IRPosition callsite_function(const CallBase &CB) {
189  return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE);
190  }
191 
192  /// Create a position describing the returned value of \p CB.
193  static const IRPosition callsite_returned(const CallBase &CB) {
194  return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE_RETURNED);
195  }
196 
197  /// Create a position describing the argument of \p CB at position \p ArgNo.
198  static const IRPosition callsite_argument(const CallBase &CB,
199  unsigned ArgNo) {
200  return IRPosition(const_cast<CallBase &>(CB), Kind(ArgNo));
201  }
202 
203  /// Create a position describing the function scope of \p ICS.
205  return IRPosition::callsite_function(cast<CallBase>(*ICS.getInstruction()));
206  }
207 
208  /// Create a position describing the returned value of \p ICS.
210  return IRPosition::callsite_returned(cast<CallBase>(*ICS.getInstruction()));
211  }
212 
213  /// Create a position describing the argument of \p ICS at position \p ArgNo.
215  unsigned ArgNo) {
216  return IRPosition::callsite_argument(cast<CallBase>(*ICS.getInstruction()),
217  ArgNo);
218  }
219 
220  /// Create a position describing the argument of \p ACS at position \p ArgNo.
222  unsigned ArgNo) {
223  int CSArgNo = ACS.getCallArgOperandNo(ArgNo);
224  if (CSArgNo >= 0)
226  cast<CallBase>(*ACS.getInstruction()), CSArgNo);
227  return IRPosition();
228  }
229 
230  /// Create a position with function scope matching the "context" of \p IRP.
231  /// If \p IRP is a call site (see isAnyCallSitePosition()) then the result
232  /// will be a call site position, otherwise the function position of the
233  /// associated function.
234  static const IRPosition function_scope(const IRPosition &IRP) {
235  if (IRP.isAnyCallSitePosition()) {
237  cast<CallBase>(IRP.getAnchorValue()));
238  }
241  }
242 
243  bool operator==(const IRPosition &RHS) const {
244  return (AnchorVal == RHS.AnchorVal) && (KindOrArgNo == RHS.KindOrArgNo);
245  }
246  bool operator!=(const IRPosition &RHS) const { return !(*this == RHS); }
247 
248  /// Return the value this abstract attribute is anchored with.
249  ///
250  /// The anchor value might not be the associated value if the latter is not
251  /// sufficient to determine where arguments will be manifested. This is, so
252  /// far, only the case for call site arguments as the value is not sufficient
253  /// to pinpoint them. Instead, we can use the call site as an anchor.
254  ///
255  ///{
257  assert(KindOrArgNo != IRP_INVALID &&
258  "Invalid position does not have an anchor value!");
259  return *AnchorVal;
260  }
261  const Value &getAnchorValue() const {
262  return const_cast<IRPosition *>(this)->getAnchorValue();
263  }
264  ///}
265 
266  /// Return the associated function, if any.
267  ///
268  ///{
270  if (auto *CB = dyn_cast<CallBase>(AnchorVal))
271  return CB->getCalledFunction();
272  assert(KindOrArgNo != IRP_INVALID &&
273  "Invalid position does not have an anchor scope!");
274  Value &V = getAnchorValue();
275  if (isa<Function>(V))
276  return &cast<Function>(V);
277  if (isa<Argument>(V))
278  return cast<Argument>(V).getParent();
279  if (isa<Instruction>(V))
280  return cast<Instruction>(V).getFunction();
281  return nullptr;
282  }
284  return const_cast<IRPosition *>(this)->getAssociatedFunction();
285  }
286  ///}
287 
288  /// Return the associated argument, if any.
289  ///
290  ///{
292  if (auto *Arg = dyn_cast<Argument>(&getAnchorValue()))
293  return Arg;
294  int ArgNo = getArgNo();
295  if (ArgNo < 0)
296  return nullptr;
297  Function *AssociatedFn = getAssociatedFunction();
298  if (!AssociatedFn || AssociatedFn->arg_size() <= unsigned(ArgNo))
299  return nullptr;
300  return AssociatedFn->arg_begin() + ArgNo;
301  }
303  return const_cast<IRPosition *>(this)->getAssociatedArgument();
304  }
305  ///}
306 
307  /// Return true if the position refers to a function interface, that is the
308  /// function scope, the function return, or an argumnt.
309  bool isFnInterfaceKind() const {
310  switch (getPositionKind()) {
314  return true;
315  default:
316  return false;
317  }
318  }
319 
320  /// Return the Function surrounding the anchor value.
321  ///
322  ///{
324  Value &V = getAnchorValue();
325  if (isa<Function>(V))
326  return &cast<Function>(V);
327  if (isa<Argument>(V))
328  return cast<Argument>(V).getParent();
329  if (isa<Instruction>(V))
330  return cast<Instruction>(V).getFunction();
331  return nullptr;
332  }
333  const Function *getAnchorScope() const {
334  return const_cast<IRPosition *>(this)->getAnchorScope();
335  }
336  ///}
337 
338  /// Return the context instruction, if any.
339  ///
340  ///{
342  Value &V = getAnchorValue();
343  if (auto *I = dyn_cast<Instruction>(&V))
344  return I;
345  if (auto *Arg = dyn_cast<Argument>(&V))
346  if (!Arg->getParent()->isDeclaration())
347  return &Arg->getParent()->getEntryBlock().front();
348  if (auto *F = dyn_cast<Function>(&V))
349  if (!F->isDeclaration())
350  return &(F->getEntryBlock().front());
351  return nullptr;
352  }
353  const Instruction *getCtxI() const {
354  return const_cast<IRPosition *>(this)->getCtxI();
355  }
356  ///}
357 
358  /// Return the value this abstract attribute is associated with.
359  ///
360  ///{
362  assert(KindOrArgNo != IRP_INVALID &&
363  "Invalid position does not have an associated value!");
364  if (getArgNo() < 0 || isa<Argument>(AnchorVal))
365  return *AnchorVal;
366  assert(isa<CallBase>(AnchorVal) && "Expected a call base!");
367  return *cast<CallBase>(AnchorVal)->getArgOperand(getArgNo());
368  }
369  const Value &getAssociatedValue() const {
370  return const_cast<IRPosition *>(this)->getAssociatedValue();
371  }
372  ///}
373 
374  /// Return the argument number of the associated value if it is an argument or
375  /// call site argument, otherwise a negative value.
376  int getArgNo() const { return KindOrArgNo; }
377 
378  /// Return the index in the attribute list for this position.
379  unsigned getAttrIdx() const {
380  switch (getPositionKind()) {
383  break;
392  return KindOrArgNo + AttributeList::FirstArgIndex;
393  }
395  "There is no attribute index for a floating or invalid position!");
396  }
397 
398  /// Return the associated position kind.
400  if (getArgNo() >= 0) {
401  assert(((isa<Argument>(getAnchorValue()) &&
402  isa<Argument>(getAssociatedValue())) ||
403  isa<CallBase>(getAnchorValue())) &&
404  "Expected argument or call base due to argument number!");
405  if (isa<CallBase>(getAnchorValue()))
406  return IRP_CALL_SITE_ARGUMENT;
407  return IRP_ARGUMENT;
408  }
409 
410  assert(KindOrArgNo < 0 &&
411  "Expected (call site) arguments to never reach this point!");
412  return Kind(KindOrArgNo);
413  }
414 
415  /// TODO: Figure out if the attribute related helper functions should live
416  /// here or somewhere else.
417 
418  /// Return true if any kind in \p AKs existing in the IR at a position that
419  /// will affect this one. See also getAttrs(...).
420  /// \param IgnoreSubsumingPositions Flag to determine if subsuming positions,
421  /// e.g., the function position if this is an
422  /// argument position, should be ignored.
423  bool hasAttr(ArrayRef<Attribute::AttrKind> AKs,
424  bool IgnoreSubsumingPositions = false) const;
425 
426  /// Return the attributes of any kind in \p AKs existing in the IR at a
427  /// position that will affect this one. While each position can only have a
428  /// single attribute of any kind in \p AKs, there are "subsuming" positions
429  /// that could have an attribute as well. This method returns all attributes
430  /// found in \p Attrs.
431  void getAttrs(ArrayRef<Attribute::AttrKind> AKs,
433 
434  /// Return the attribute of kind \p AK existing in the IR at this position.
436  if (getPositionKind() == IRP_INVALID || getPositionKind() == IRP_FLOAT)
437  return Attribute();
438 
439  AttributeList AttrList;
440  if (ImmutableCallSite ICS = ImmutableCallSite(&getAnchorValue()))
441  AttrList = ICS.getAttributes();
442  else
443  AttrList = getAssociatedFunction()->getAttributes();
444 
445  if (AttrList.hasAttribute(getAttrIdx(), AK))
446  return AttrList.getAttribute(getAttrIdx(), AK);
447  return Attribute();
448  }
449 
450  /// Remove the attribute of kind \p AKs existing in the IR at this position.
452  if (getPositionKind() == IRP_INVALID || getPositionKind() == IRP_FLOAT)
453  return;
454 
455  AttributeList AttrList;
456  CallSite CS = CallSite(&getAnchorValue());
457  if (CS)
458  AttrList = CS.getAttributes();
459  else
460  AttrList = getAssociatedFunction()->getAttributes();
461 
462  LLVMContext &Ctx = getAnchorValue().getContext();
463  for (Attribute::AttrKind AK : AKs)
464  AttrList = AttrList.removeAttribute(Ctx, getAttrIdx(), AK);
465 
466  if (CS)
467  CS.setAttributes(AttrList);
468  else
469  getAssociatedFunction()->setAttributes(AttrList);
470  }
471 
472  bool isAnyCallSitePosition() const {
473  switch (getPositionKind()) {
477  return true;
478  default:
479  return false;
480  }
481  }
482 
483  /// Special DenseMap key values.
484  ///
485  ///{
486  static const IRPosition EmptyKey;
487  static const IRPosition TombstoneKey;
488  ///}
489 
490 private:
491  /// Private constructor for special values only!
492  explicit IRPosition(int KindOrArgNo)
493  : AnchorVal(0), KindOrArgNo(KindOrArgNo) {}
494 
495  /// IRPosition anchored at \p AnchorVal with kind/argument numbet \p PK.
496  explicit IRPosition(Value &AnchorVal, Kind PK)
497  : AnchorVal(&AnchorVal), KindOrArgNo(PK) {
498  verify();
499  }
500 
501  /// Verify internal invariants.
502  void verify();
503 
504  /// The value this position is anchored at.
505  Value *AnchorVal;
506 
507  /// The argument number, if non-negative, or the position "kind".
508  int KindOrArgNo;
509 };
510 
511 /// Helper that allows IRPosition as a key in a DenseMap.
512 template <> struct DenseMapInfo<IRPosition> {
513  static inline IRPosition getEmptyKey() { return IRPosition::EmptyKey; }
514  static inline IRPosition getTombstoneKey() {
516  }
517  static unsigned getHashValue(const IRPosition &IRP) {
519  (unsigned(IRP.getArgNo()));
520  }
521  static bool isEqual(const IRPosition &LHS, const IRPosition &RHS) {
522  return LHS == RHS;
523  }
524 };
525 
526 /// A visitor class for IR positions.
527 ///
528 /// Given a position P, the SubsumingPositionIterator allows to visit "subsuming
529 /// positions" wrt. attributes/information. Thus, if a piece of information
530 /// holds for a subsuming position, it also holds for the position P.
531 ///
532 /// The subsuming positions always include the initial position and then,
533 /// depending on the position kind, additionally the following ones:
534 /// - for IRP_RETURNED:
535 /// - the function (IRP_FUNCTION)
536 /// - for IRP_ARGUMENT:
537 /// - the function (IRP_FUNCTION)
538 /// - for IRP_CALL_SITE:
539 /// - the callee (IRP_FUNCTION), if known
540 /// - for IRP_CALL_SITE_RETURNED:
541 /// - the callee (IRP_RETURNED), if known
542 /// - the call site (IRP_FUNCTION)
543 /// - the callee (IRP_FUNCTION), if known
544 /// - for IRP_CALL_SITE_ARGUMENT:
545 /// - the argument of the callee (IRP_ARGUMENT), if known
546 /// - the callee (IRP_FUNCTION), if known
547 /// - the position the call site argument is associated with if it is not
548 /// anchored to the call site, e.g., if it is an arugment then the argument
549 /// (IRP_ARGUMENT)
551  SmallVector<IRPosition, 4> IRPositions;
552  using iterator = decltype(IRPositions)::iterator;
553 
554 public:
556  iterator begin() { return IRPositions.begin(); }
557  iterator end() { return IRPositions.end(); }
558 };
559 
560 /// Wrapper for FunctoinAnalysisManager.
562  template <typename Analysis>
563  typename Analysis::Result *getAnalysis(const Function &F) {
564  if (!MAM || !F.getParent())
565  return nullptr;
566  auto &FAM = MAM->getResult<FunctionAnalysisManagerModuleProxy>(
567  const_cast<Module &>(*F.getParent()))
568  .getManager();
569  return &FAM.getResult<Analysis>(const_cast<Function &>(F));
570  }
571 
572  template <typename Analysis>
573  typename Analysis::Result *getAnalysis(const Module &M) {
574  if (!MAM)
575  return nullptr;
576  return &MAM->getResult<Analysis>(const_cast<Module &>(M));
577  }
580 
581 private:
582  ModuleAnalysisManager *MAM = nullptr;
583 };
584 
585 /// Data structure to hold cached (LLVM-IR) information.
586 ///
587 /// All attributes are given an InformationCache object at creation time to
588 /// avoid inspection of the IR by all of them individually. This default
589 /// InformationCache will hold information required by 'default' attributes,
590 /// thus the ones deduced when Attributor::identifyDefaultAbstractAttributes(..)
591 /// is called.
592 ///
593 /// If custom abstract attributes, registered manually through
594 /// Attributor::registerAA(...), need more information, especially if it is not
595 /// reusable, it is advised to inherit from the InformationCache and cast the
596 /// instance down in the abstract attributes.
599  : DL(M.getDataLayout()), Explorer(/* ExploreInterBlock */ true), AG(AG) {
600 
602  if (!CG)
603  return;
604 
606  for (scc_iterator<CallGraph *> I = scc_begin(CG); !I.isAtEnd(); ++I) {
607  for (CallGraphNode *Node : *I)
608  SccSize[Node->getFunction()] = I->size();
609  }
610  SccSizeOpt = std::move(SccSize);
611  }
612 
613  /// A map type from opcodes to instructions with this opcode.
615 
616  /// Return the map that relates "interesting" opcodes with all instructions
617  /// with that opcode in \p F.
619  return FuncInstOpcodeMap[&F];
620  }
621 
622  /// A vector type to hold instructions.
623  using InstructionVectorTy = std::vector<Instruction *>;
624 
625  /// Return the instructions in \p F that may read or write memory.
627  return FuncRWInstsMap[&F];
628  }
629 
630  /// Return MustBeExecutedContextExplorer
632  return Explorer;
633  }
634 
635  /// Return TargetLibraryInfo for function \p F.
637  return AG.getAnalysis<TargetLibraryAnalysis>(F);
638  }
639 
640  /// Return AliasAnalysis Result for function \p F.
642  return AG.getAnalysis<AAManager>(F);
643  }
644 
645  /// Return SCC size on call graph for function \p F.
646  unsigned getSccSize(const Function &F) {
647  if (!SccSizeOpt.hasValue())
648  return 0;
649  return (SccSizeOpt.getValue())[&F];
650  }
651 
652  /// Return datalayout used in the module.
653  const DataLayout &getDL() { return DL; }
654 
655 private:
656  /// A map type from functions to opcode to instruction maps.
658 
659  /// A map type from functions to their read or write instructions.
661 
662  /// A nested map that remembers all instructions in a function with a certain
663  /// instruction opcode (Instruction::getOpcode()).
664  FuncInstOpcodeMapTy FuncInstOpcodeMap;
665 
666  /// A map from functions to their instructions that may read or write memory.
667  FuncRWInstsMapTy FuncRWInstsMap;
668 
669  /// The datalayout used in the module.
670  const DataLayout &DL;
671 
672  /// MustBeExecutedContextExplorer
674 
675  /// Getters for analysis.
676  AnalysisGetter &AG;
677 
678  /// Cache result for scc size in the call graph
680 
681  /// Give the Attributor access to the members so
682  /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them.
683  friend struct Attributor;
684 };
685 
686 /// The fixpoint analysis framework that orchestrates the attribute deduction.
687 ///
688 /// The Attributor provides a general abstract analysis framework (guided
689 /// fixpoint iteration) as well as helper functions for the deduction of
690 /// (LLVM-IR) attributes. However, also other code properties can be deduced,
691 /// propagated, and ultimately manifested through the Attributor framework. This
692 /// is particularly useful if these properties interact with attributes and a
693 /// co-scheduled deduction allows to improve the solution. Even if not, thus if
694 /// attributes/properties are completely isolated, they should use the
695 /// Attributor framework to reduce the number of fixpoint iteration frameworks
696 /// in the code base. Note that the Attributor design makes sure that isolated
697 /// attributes are not impacted, in any way, by others derived at the same time
698 /// if there is no cross-reasoning performed.
699 ///
700 /// The public facing interface of the Attributor is kept simple and basically
701 /// allows abstract attributes to one thing, query abstract attributes
702 /// in-flight. There are two reasons to do this:
703 /// a) The optimistic state of one abstract attribute can justify an
704 /// optimistic state of another, allowing to framework to end up with an
705 /// optimistic (=best possible) fixpoint instead of one based solely on
706 /// information in the IR.
707 /// b) This avoids reimplementing various kinds of lookups, e.g., to check
708 /// for existing IR attributes, in favor of a single lookups interface
709 /// provided by an abstract attribute subclass.
710 ///
711 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
712 /// described in the file comment.
713 struct Attributor {
714  /// Constructor
715  ///
716  /// \param InfoCache Cache to hold various information accessible for
717  /// the abstract attributes.
718  /// \param DepRecomputeInterval Number of iterations until the dependences
719  /// between abstract attributes are recomputed.
720  /// \param Whitelist If not null, a set limiting the attribute opportunities.
721  Attributor(InformationCache &InfoCache, unsigned DepRecomputeInterval,
722  DenseSet<const char *> *Whitelist = nullptr)
723  : InfoCache(InfoCache), DepRecomputeInterval(DepRecomputeInterval),
724  Whitelist(Whitelist) {}
725 
726  ~Attributor() { DeleteContainerPointers(AllAbstractAttributes); }
727 
728  /// Run the analyses until a fixpoint is reached or enforced (timeout).
729  ///
730  /// The attributes registered with this Attributor can be used after as long
731  /// as the Attributor is not destroyed (it owns the attributes now).
732  ///
733  /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED.
734  ChangeStatus run(Module &M);
735 
736  /// Lookup an abstract attribute of type \p AAType at position \p IRP. While
737  /// no abstract attribute is found equivalent positions are checked, see
738  /// SubsumingPositionIterator. Thus, the returned abstract attribute
739  /// might be anchored at a different position, e.g., the callee if \p IRP is a
740  /// call base.
741  ///
742  /// This method is the only (supported) way an abstract attribute can retrieve
743  /// information from another abstract attribute. As an example, take an
744  /// abstract attribute that determines the memory access behavior for a
745  /// argument (readnone, readonly, ...). It should use `getAAFor` to get the
746  /// most optimistic information for other abstract attributes in-flight, e.g.
747  /// the one reasoning about the "captured" state for the argument or the one
748  /// reasoning on the memory access behavior of the function as a whole.
749  ///
750  /// If the flag \p TrackDependence is set to false the dependence from
751  /// \p QueryingAA to the return abstract attribute is not automatically
752  /// recorded. This should only be used if the caller will record the
753  /// dependence explicitly if necessary, thus if it the returned abstract
754  /// attribute is used for reasoning. To record the dependences explicitly use
755  /// the `Attributor::recordDependence` method.
756  template <typename AAType>
757  const AAType &getAAFor(const AbstractAttribute &QueryingAA,
758  const IRPosition &IRP, bool TrackDependence = true) {
759  return getOrCreateAAFor<AAType>(IRP, &QueryingAA, TrackDependence);
760  }
761 
762  /// Explicitly record a dependence from \p FromAA to \p ToAA, that is if
763  /// \p FromAA changes \p ToAA should be updated as well.
764  ///
765  /// This method should be used in conjunction with the `getAAFor` method and
766  /// with the TrackDependence flag passed to the method set to false. This can
767  /// be beneficial to avoid false dependences but it requires the users of
768  /// `getAAFor` to explicitly record true dependences through this method.
770  const AbstractAttribute &ToAA) {
771  QueryMap[&FromAA].insert(const_cast<AbstractAttribute *>(&ToAA));
772  }
773 
774  /// Introduce a new abstract attribute into the fixpoint analysis.
775  ///
776  /// Note that ownership of the attribute is given to the Attributor. It will
777  /// invoke delete for the Attributor on destruction of the Attributor.
778  ///
779  /// Attributes are identified by their IR position (AAType::getIRPosition())
780  /// and the address of their static member (see AAType::ID).
781  template <typename AAType> AAType &registerAA(AAType &AA) {
782  static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
783  "Cannot register an attribute with a type not derived from "
784  "'AbstractAttribute'!");
785  // Put the attribute in the lookup map structure and the container we use to
786  // keep track of all attributes.
787  IRPosition &IRP = AA.getIRPosition();
788  auto &KindToAbstractAttributeMap = AAMap[IRP];
790  "Attribute already in map!");
792  AllAbstractAttributes.push_back(&AA);
793  return AA;
794  }
795 
796  /// Return the internal information cache.
797  InformationCache &getInfoCache() { return InfoCache; }
798 
799  /// Determine opportunities to derive 'default' attributes in \p F and create
800  /// abstract attribute objects for them.
801  ///
802  /// \param F The function that is checked for attribute opportunities.
803  ///
804  /// Note that abstract attribute instances are generally created even if the
805  /// IR already contains the information they would deduce. The most important
806  /// reason for this is the single interface, the one of the abstract attribute
807  /// instance, which can be queried without the need to look at the IR in
808  /// various places.
809  void identifyDefaultAbstractAttributes(Function &F);
810 
811  /// Initialize the information cache for queries regarding function \p F.
812  ///
813  /// This method needs to be called for all function that might be looked at
814  /// through the information cache interface *prior* to looking at them.
815  void initializeInformationCache(Function &F);
816 
817  /// Mark the internal function \p F as live.
818  ///
819  /// This will trigger the identification and initialization of attributes for
820  /// \p F.
822  assert(F.hasLocalLinkage() &&
823  "Only local linkage is assumed dead initially.");
824 
825  identifyDefaultAbstractAttributes(const_cast<Function &>(F));
826  }
827 
828  /// Record that \p I is deleted after information was manifested.
829  void deleteAfterManifest(Instruction &I) { ToBeDeletedInsts.insert(&I); }
830 
831  /// Record that \p BB is deleted after information was manifested.
832  void deleteAfterManifest(BasicBlock &BB) { ToBeDeletedBlocks.insert(&BB); }
833 
834  /// Record that \p F is deleted after information was manifested.
835  void deleteAfterManifest(Function &F) { ToBeDeletedFunctions.insert(&F); }
836 
837  /// Return true if \p AA (or its context instruction) is assumed dead.
838  ///
839  /// If \p LivenessAA is not provided it is queried.
840  bool isAssumedDead(const AbstractAttribute &AA, const AAIsDead *LivenessAA);
841 
842  /// Check \p Pred on all function call sites.
843  ///
844  /// This method will evaluate \p Pred on call sites and return
845  /// true if \p Pred holds in every call sites. However, this is only possible
846  /// all call sites are known, hence the function has internal linkage.
847  bool checkForAllCallSites(const function_ref<bool(AbstractCallSite)> &Pred,
848  const AbstractAttribute &QueryingAA,
849  bool RequireAllCallSites);
850 
851  /// Check \p Pred on all values potentially returned by \p F.
852  ///
853  /// This method will evaluate \p Pred on all values potentially returned by
854  /// the function associated with \p QueryingAA. The returned values are
855  /// matched with their respective return instructions. Returns true if \p Pred
856  /// holds on all of them.
857  bool checkForAllReturnedValuesAndReturnInsts(
858  const function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)>
859  &Pred,
860  const AbstractAttribute &QueryingAA);
861 
862  /// Check \p Pred on all values potentially returned by the function
863  /// associated with \p QueryingAA.
864  ///
865  /// This is the context insensitive version of the method above.
866  bool checkForAllReturnedValues(const function_ref<bool(Value &)> &Pred,
867  const AbstractAttribute &QueryingAA);
868 
869  /// Check \p Pred on all instructions with an opcode present in \p Opcodes.
870  ///
871  /// This method will evaluate \p Pred on all instructions with an opcode
872  /// present in \p Opcode and return true if \p Pred holds on all of them.
873  bool checkForAllInstructions(const function_ref<bool(Instruction &)> &Pred,
874  const AbstractAttribute &QueryingAA,
875  const ArrayRef<unsigned> &Opcodes);
876 
877  /// Check \p Pred on all call-like instructions (=CallBased derived).
878  ///
879  /// See checkForAllCallLikeInstructions(...) for more information.
880  bool
882  const AbstractAttribute &QueryingAA) {
883  return checkForAllInstructions(Pred, QueryingAA,
884  {(unsigned)Instruction::Invoke,
885  (unsigned)Instruction::CallBr,
887  }
888 
889  /// Check \p Pred on all Read/Write instructions.
890  ///
891  /// This method will evaluate \p Pred on all instructions that read or write
892  /// to memory present in the information cache and return true if \p Pred
893  /// holds on all of them.
894  bool checkForAllReadWriteInstructions(
895  const llvm::function_ref<bool(Instruction &)> &Pred,
896  AbstractAttribute &QueryingAA);
897 
898  /// Return the data layout associated with the anchor scope.
899  const DataLayout &getDataLayout() const { return InfoCache.DL; }
900 
901 private:
902  /// Check \p Pred on all call sites of \p Fn.
903  ///
904  /// This method will evaluate \p Pred on call sites and return
905  /// true if \p Pred holds in every call sites. However, this is only possible
906  /// all call sites are known, hence the function has internal linkage.
907  bool checkForAllCallSites(const function_ref<bool(AbstractCallSite)> &Pred,
908  const Function &Fn, bool RequireAllCallSites,
909  const AbstractAttribute *QueryingAA);
910 
911  /// The private version of getAAFor that allows to omit a querying abstract
912  /// attribute. See also the public getAAFor method.
913  template <typename AAType>
914  const AAType &getOrCreateAAFor(const IRPosition &IRP,
915  const AbstractAttribute *QueryingAA = nullptr,
916  bool TrackDependence = false) {
917  if (const AAType *AAPtr =
918  lookupAAFor<AAType>(IRP, QueryingAA, TrackDependence))
919  return *AAPtr;
920 
921  // No matching attribute found, create one.
922  // Use the static create method.
923  auto &AA = AAType::createForPosition(IRP, *this);
924  registerAA(AA);
925 
926  // For now we ignore naked and optnone functions.
927  bool Invalidate = Whitelist && !Whitelist->count(&AAType::ID);
928  if (const Function *Fn = IRP.getAnchorScope())
929  Invalidate |= Fn->hasFnAttribute(Attribute::Naked) ||
930  Fn->hasFnAttribute(Attribute::OptimizeNone);
931 
932  // Bootstrap the new attribute with an initial update to propagate
933  // information, e.g., function -> call site. If it is not on a given
934  // whitelist we will not perform updates at all.
935  if (Invalidate) {
937  return AA;
938  }
939 
940  AA.initialize(*this);
941  AA.update(*this);
942 
943  if (TrackDependence && AA.getState().isValidState())
944  QueryMap[&AA].insert(const_cast<AbstractAttribute *>(QueryingAA));
945  return AA;
946  }
947 
948  /// Return the attribute of \p AAType for \p IRP if existing.
949  template <typename AAType>
950  const AAType *lookupAAFor(const IRPosition &IRP,
951  const AbstractAttribute *QueryingAA = nullptr,
952  bool TrackDependence = false) {
953  static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
954  "Cannot query an attribute with a type not derived from "
955  "'AbstractAttribute'!");
956  assert((QueryingAA || !TrackDependence) &&
957  "Cannot track dependences without a QueryingAA!");
958 
959  // Lookup the abstract attribute of type AAType. If found, return it after
960  // registering a dependence of QueryingAA on the one returned attribute.
961  const auto &KindToAbstractAttributeMap = AAMap.lookup(IRP);
962  if (AAType *AA = static_cast<AAType *>(
964  // Do not register a dependence on an attribute with an invalid state.
965  if (TrackDependence && AA->getState().isValidState())
966  QueryMap[AA].insert(const_cast<AbstractAttribute *>(QueryingAA));
967  return AA;
968  }
969  return nullptr;
970  }
971 
972  /// The set of all abstract attributes.
973  ///{
975  AAVector AllAbstractAttributes;
976  ///}
977 
978  /// A nested map to lookup abstract attributes based on the argument position
979  /// on the outer level, and the addresses of the static member (AAType::ID) on
980  /// the inner level.
981  ///{
985  ///}
986 
987  /// A map from abstract attributes to the ones that queried them through calls
988  /// to the getAAFor<...>(...) method.
989  ///{
990  using QueryMapTy =
992  QueryMapTy QueryMap;
993  ///}
994 
995  /// The information cache that holds pre-processed (LLVM-IR) information.
996  InformationCache &InfoCache;
997 
998  /// Number of iterations until the dependences between abstract attributes are
999  /// recomputed.
1000  const unsigned DepRecomputeInterval;
1001 
1002  /// If not null, a set limiting the attribute opportunities.
1003  const DenseSet<const char *> *Whitelist;
1004 
1005  /// A set to remember the functions we already assume to be live and visited.
1006  DenseSet<const Function *> VisitedFunctions;
1007 
1008  /// Functions, blocks, and instructions we delete after manifest is done.
1009  ///
1010  ///{
1011  SmallPtrSet<Function *, 8> ToBeDeletedFunctions;
1012  SmallPtrSet<BasicBlock *, 8> ToBeDeletedBlocks;
1013  SmallPtrSet<Instruction *, 8> ToBeDeletedInsts;
1014  ///}
1015 };
1016 
1017 /// An interface to query the internal state of an abstract attribute.
1018 ///
1019 /// The abstract state is a minimal interface that allows the Attributor to
1020 /// communicate with the abstract attributes about their internal state without
1021 /// enforcing or exposing implementation details, e.g., the (existence of an)
1022 /// underlying lattice.
1023 ///
1024 /// It is sufficient to be able to query if a state is (1) valid or invalid, (2)
1025 /// at a fixpoint, and to indicate to the state that (3) an optimistic fixpoint
1026 /// was reached or (4) a pessimistic fixpoint was enforced.
1027 ///
1028 /// All methods need to be implemented by the subclass. For the common use case,
1029 /// a single boolean state or a bit-encoded state, the BooleanState and
1030 /// IntegerState classes are already provided. An abstract attribute can inherit
1031 /// from them to get the abstract state interface and additional methods to
1032 /// directly modify the state based if needed. See the class comments for help.
1034  virtual ~AbstractState() {}
1035 
1036  /// Return if this abstract state is in a valid state. If false, no
1037  /// information provided should be used.
1038  virtual bool isValidState() const = 0;
1039 
1040  /// Return if this abstract state is fixed, thus does not need to be updated
1041  /// if information changes as it cannot change itself.
1042  virtual bool isAtFixpoint() const = 0;
1043 
1044  /// Indicate that the abstract state should converge to the optimistic state.
1045  ///
1046  /// This will usually make the optimistically assumed state the known to be
1047  /// true state.
1048  ///
1049  /// \returns ChangeStatus::UNCHANGED as the assumed value should not change.
1050  virtual ChangeStatus indicateOptimisticFixpoint() = 0;
1051 
1052  /// Indicate that the abstract state should converge to the pessimistic state.
1053  ///
1054  /// This will usually revert the optimistically assumed state to the known to
1055  /// be true state.
1056  ///
1057  /// \returns ChangeStatus::CHANGED as the assumed value may change.
1058  virtual ChangeStatus indicatePessimisticFixpoint() = 0;
1059 };
1060 
1061 /// Simple state with integers encoding.
1062 ///
1063 /// The interface ensures that the assumed bits are always a subset of the known
1064 /// bits. Users can only add known bits and, except through adding known bits,
1065 /// they can only remove assumed bits. This should guarantee monotoniticy and
1066 /// thereby the existence of a fixpoint (if used corretly). The fixpoint is
1067 /// reached when the assumed and known state/bits are equal. Users can
1068 /// force/inidicate a fixpoint. If an optimistic one is indicated, the known
1069 /// state will catch up with the assumed one, for a pessimistic fixpoint it is
1070 /// the other way around.
1071 struct IntegerState : public AbstractState {
1072  /// Underlying integer type, we assume 32 bits to be enough.
1073  using base_t = uint32_t;
1074 
1075  /// Initialize the (best) state.
1076  IntegerState(base_t BestState = ~0) : Assumed(BestState) {}
1077 
1078  /// Return the worst possible representable state.
1079  static constexpr base_t getWorstState() { return 0; }
1080 
1081  /// See AbstractState::isValidState()
1082  /// NOTE: For now we simply pretend that the worst possible state is invalid.
1083  bool isValidState() const override { return Assumed != getWorstState(); }
1084 
1085  /// See AbstractState::isAtFixpoint()
1086  bool isAtFixpoint() const override { return Assumed == Known; }
1087 
1088  /// See AbstractState::indicateOptimisticFixpoint(...)
1090  Known = Assumed;
1091  return ChangeStatus::UNCHANGED;
1092  }
1093 
1094  /// See AbstractState::indicatePessimisticFixpoint(...)
1096  Assumed = Known;
1097  return ChangeStatus::CHANGED;
1098  }
1099 
1100  /// Return the known state encoding
1101  base_t getKnown() const { return Known; }
1102 
1103  /// Return the assumed state encoding.
1104  base_t getAssumed() const { return Assumed; }
1105 
1106  /// Return true if the bits set in \p BitsEncoding are "known bits".
1107  bool isKnown(base_t BitsEncoding) const {
1108  return (Known & BitsEncoding) == BitsEncoding;
1109  }
1110 
1111  /// Return true if the bits set in \p BitsEncoding are "assumed bits".
1112  bool isAssumed(base_t BitsEncoding) const {
1113  return (Assumed & BitsEncoding) == BitsEncoding;
1114  }
1115 
1116  /// Add the bits in \p BitsEncoding to the "known bits".
1118  // Make sure we never miss any "known bits".
1119  Assumed |= Bits;
1120  Known |= Bits;
1121  return *this;
1122  }
1123 
1124  /// Remove the bits in \p BitsEncoding from the "assumed bits" if not known.
1126  // Make sure we never loose any "known bits".
1127  Assumed = (Assumed & ~BitsEncoding) | Known;
1128  return *this;
1129  }
1130 
1131  /// Remove the bits in \p BitsEncoding from the "known bits".
1133  Known = (Known & ~BitsEncoding);
1134  return *this;
1135  }
1136 
1137  /// Keep only "assumed bits" also set in \p BitsEncoding but all known ones.
1139  // Make sure we never loose any "known bits".
1140  Assumed = (Assumed & BitsEncoding) | Known;
1141  return *this;
1142  }
1143 
1144  /// Take minimum of assumed and \p Value.
1146  // Make sure we never loose "known value".
1147  Assumed = std::max(std::min(Assumed, Value), Known);
1148  return *this;
1149  }
1150 
1151  /// Take maximum of known and \p Value.
1153  // Make sure we never loose "known value".
1154  Assumed = std::max(Value, Assumed);
1155  Known = std::max(Value, Known);
1156  return *this;
1157  }
1158 
1159  /// Equality for IntegerState.
1160  bool operator==(const IntegerState &R) const {
1161  return this->getAssumed() == R.getAssumed() &&
1162  this->getKnown() == R.getKnown();
1163  }
1164 
1165  /// Inequality for IntegerState.
1166  bool operator!=(const IntegerState &R) const { return !(*this == R); }
1167 
1168  /// "Clamp" this state with \p R. The result is the minimum of the assumed
1169  /// information but not less than what was known before.
1170  ///
1171  /// TODO: Consider replacing the operator with a call or using it only when
1172  /// we can also take the maximum of the known information, thus when
1173  /// \p R is not dependent on additional assumed state.
1175  takeAssumedMinimum(R.Assumed);
1176  return *this;
1177  }
1178 
1179  /// "Clamp" this state with \p R. The result is the maximum of the known
1180  /// information but not more than what was assumed before.
1182  takeKnownMaximum(R.Known);
1183  return *this;
1184  }
1185 
1186  /// Make this the minimum, known and assumed, of this state and \p R.
1188  Known = std::min(Known, R.Known);
1189  Assumed = std::min(Assumed, R.Assumed);
1190  return *this;
1191  }
1192 
1193  /// Make this the maximum, known and assumed, of this state and \p R.
1195  Known = std::max(Known, R.Known);
1196  Assumed = std::max(Assumed, R.Assumed);
1197  return *this;
1198  }
1199 
1200 private:
1201  /// The known state encoding in an integer of type base_t.
1202  base_t Known = getWorstState();
1203 
1204  /// The assumed state encoding in an integer of type base_t.
1205  base_t Assumed;
1206 };
1207 
1208 /// Simple wrapper for a single bit (boolean) state.
1209 struct BooleanState : public IntegerState {
1211 };
1212 
1213 /// Helper struct necessary as the modular build fails if the virtual method
1214 /// IRAttribute::manifest is defined in the Attributor.cpp.
1216  static ChangeStatus manifestAttrs(Attributor &A, IRPosition &IRP,
1217  const ArrayRef<Attribute> &DeducedAttrs);
1218 };
1219 
1220 /// Helper to tie a abstract state implementation to an abstract attribute.
1221 template <typename StateTy, typename Base>
1222 struct StateWrapper : public StateTy, public Base {
1223  /// Provide static access to the type of the state.
1225 
1226  /// See AbstractAttribute::getState(...).
1227  StateType &getState() override { return *this; }
1228 
1229  /// See AbstractAttribute::getState(...).
1230  const AbstractState &getState() const override { return *this; }
1231 };
1232 
1233 /// Helper class that provides common functionality to manifest IR attributes.
1234 template <Attribute::AttrKind AK, typename Base>
1235 struct IRAttribute : public IRPosition, public Base {
1236  IRAttribute(const IRPosition &IRP) : IRPosition(IRP) {}
1238 
1239  /// See AbstractAttribute::initialize(...).
1240  virtual void initialize(Attributor &A) override {
1241  if (hasAttr(getAttrKind())) {
1242  this->getState().indicateOptimisticFixpoint();
1243  return;
1244  }
1245 
1246  const IRPosition &IRP = this->getIRPosition();
1247  bool IsFnInterface = IRP.isFnInterfaceKind();
1248  const Function *FnScope = IRP.getAnchorScope();
1249  // TODO: Not all attributes require an exact definition. Find a way to
1250  // enable deduction for some but not all attributes in case the
1251  // definition might be changed at runtime, see also
1252  // http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
1253  // TODO: We could always determine abstract attributes and if sufficient
1254  // information was found we could duplicate the functions that do not
1255  // have an exact definition.
1256  if (IsFnInterface && (!FnScope || !FnScope->hasExactDefinition()))
1257  this->getState().indicatePessimisticFixpoint();
1258  }
1259 
1260  /// See AbstractAttribute::manifest(...).
1262  SmallVector<Attribute, 4> DeducedAttrs;
1263  getDeducedAttributes(getAnchorValue().getContext(), DeducedAttrs);
1264  return IRAttributeManifest::manifestAttrs(A, getIRPosition(), DeducedAttrs);
1265  }
1266 
1267  /// Return the kind that identifies the abstract attribute implementation.
1268  Attribute::AttrKind getAttrKind() const { return AK; }
1269 
1270  /// Return the deduced attributes in \p Attrs.
1273  Attrs.emplace_back(Attribute::get(Ctx, getAttrKind()));
1274  }
1275 
1276  /// Return an IR position, see struct IRPosition.
1277  ///
1278  ///{
1279  IRPosition &getIRPosition() override { return *this; }
1280  const IRPosition &getIRPosition() const override { return *this; }
1281  ///}
1282 };
1283 
1284 /// Base struct for all "concrete attribute" deductions.
1285 ///
1286 /// The abstract attribute is a minimal interface that allows the Attributor to
1287 /// orchestrate the abstract/fixpoint analysis. The design allows to hide away
1288 /// implementation choices made for the subclasses but also to structure their
1289 /// implementation and simplify the use of other abstract attributes in-flight.
1290 ///
1291 /// To allow easy creation of new attributes, most methods have default
1292 /// implementations. The ones that do not are generally straight forward, except
1293 /// `AbstractAttribute::updateImpl` which is the location of most reasoning
1294 /// associated with the abstract attribute. The update is invoked by the
1295 /// Attributor in case the situation used to justify the current optimistic
1296 /// state might have changed. The Attributor determines this automatically
1297 /// by monitoring the `Attributor::getAAFor` calls made by abstract attributes.
1298 ///
1299 /// The `updateImpl` method should inspect the IR and other abstract attributes
1300 /// in-flight to justify the best possible (=optimistic) state. The actual
1301 /// implementation is, similar to the underlying abstract state encoding, not
1302 /// exposed. In the most common case, the `updateImpl` will go through a list of
1303 /// reasons why its optimistic state is valid given the current information. If
1304 /// any combination of them holds and is sufficient to justify the current
1305 /// optimistic state, the method shall return UNCHAGED. If not, the optimistic
1306 /// state is adjusted to the situation and the method shall return CHANGED.
1307 ///
1308 /// If the manifestation of the "concrete attribute" deduced by the subclass
1309 /// differs from the "default" behavior, which is a (set of) LLVM-IR
1310 /// attribute(s) for an argument, call site argument, function return value, or
1311 /// function, the `AbstractAttribute::manifest` method should be overloaded.
1312 ///
1313 /// NOTE: If the state obtained via getState() is INVALID, thus if
1314 /// AbstractAttribute::getState().isValidState() returns false, no
1315 /// information provided by the methods of this class should be used.
1316 /// NOTE: The Attributor currently has certain limitations to what we can do.
1317 /// As a general rule of thumb, "concrete" abstract attributes should *for
1318 /// now* only perform "backward" information propagation. That means
1319 /// optimistic information obtained through abstract attributes should
1320 /// only be used at positions that precede the origin of the information
1321 /// with regards to the program flow. More practically, information can
1322 /// *now* be propagated from instructions to their enclosing function, but
1323 /// *not* from call sites to the called function. The mechanisms to allow
1324 /// both directions will be added in the future.
1325 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
1326 /// described in the file comment.
1329 
1330  /// Virtual destructor.
1331  virtual ~AbstractAttribute() {}
1332 
1333  /// Initialize the state with the information in the Attributor \p A.
1334  ///
1335  /// This function is called by the Attributor once all abstract attributes
1336  /// have been identified. It can and shall be used for task like:
1337  /// - identify existing knowledge in the IR and use it for the "known state"
1338  /// - perform any work that is not going to change over time, e.g., determine
1339  /// a subset of the IR, or attributes in-flight, that have to be looked at
1340  /// in the `updateImpl` method.
1341  virtual void initialize(Attributor &A) {}
1342 
1343  /// Return the internal abstract state for inspection.
1344  virtual StateType &getState() = 0;
1345  virtual const StateType &getState() const = 0;
1346 
1347  /// Return an IR position, see struct IRPosition.
1348  virtual const IRPosition &getIRPosition() const = 0;
1349 
1350  /// Helper functions, for debug purposes only.
1351  ///{
1352  virtual void print(raw_ostream &OS) const;
1353  void dump() const { print(dbgs()); }
1354 
1355  /// This function should return the "summarized" assumed state as string.
1356  virtual const std::string getAsStr() const = 0;
1357  ///}
1358 
1359  /// Allow the Attributor access to the protected methods.
1360  friend struct Attributor;
1361 
1362 protected:
1363  /// Hook for the Attributor to trigger an update of the internal state.
1364  ///
1365  /// If this attribute is already fixed, this method will return UNCHANGED,
1366  /// otherwise it delegates to `AbstractAttribute::updateImpl`.
1367  ///
1368  /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
1369  ChangeStatus update(Attributor &A);
1370 
1371  /// Hook for the Attributor to trigger the manifestation of the information
1372  /// represented by the abstract attribute in the LLVM-IR.
1373  ///
1374  /// \Return CHANGED if the IR was altered, otherwise UNCHANGED.
1376  return ChangeStatus::UNCHANGED;
1377  }
1378 
1379  /// Hook to enable custom statistic tracking, called after manifest that
1380  /// resulted in a change if statistics are enabled.
1381  ///
1382  /// We require subclasses to provide an implementation so we remember to
1383  /// add statistics for them.
1384  virtual void trackStatistics() const = 0;
1385 
1386  /// Return an IR position, see struct IRPosition.
1387  virtual IRPosition &getIRPosition() = 0;
1388 
1389  /// The actual update/transfer function which has to be implemented by the
1390  /// derived classes.
1391  ///
1392  /// If it is called, the environment has changed and we have to determine if
1393  /// the current information is still valid or adjust it otherwise.
1394  ///
1395  /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
1396  virtual ChangeStatus updateImpl(Attributor &A) = 0;
1397 };
1398 
1399 /// Forward declarations of output streams for debug purposes.
1400 ///
1401 ///{
1406 raw_ostream &operator<<(raw_ostream &OS, const AbstractState &State);
1408 ///}
1409 
1410 struct AttributorPass : public PassInfoMixin<AttributorPass> {
1412 };
1413 
1415 
1416 /// ----------------------------------------------------------------------------
1417 /// Abstract Attribute Classes
1418 /// ----------------------------------------------------------------------------
1419 
1420 /// An abstract attribute for the returned values of a function.
1422  : public IRAttribute<Attribute::Returned, AbstractAttribute> {
1424 
1425  /// Return an assumed unique return value if a single candidate is found. If
1426  /// there cannot be one, return a nullptr. If it is not clear yet, return the
1427  /// Optional::NoneType.
1428  Optional<Value *> getAssumedUniqueReturnValue(Attributor &A) const;
1429 
1430  /// Check \p Pred on all returned values.
1431  ///
1432  /// This method will evaluate \p Pred on returned values and return
1433  /// true if (1) all returned values are known, and (2) \p Pred returned true
1434  /// for all returned values.
1435  ///
1436  /// Note: Unlike the Attributor::checkForAllReturnedValuesAndReturnInsts
1437  /// method, this one will not filter dead return instructions.
1438  virtual bool checkForAllReturnedValuesAndReturnInsts(
1439  const function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)>
1440  &Pred) const = 0;
1441 
1442  using iterator =
1444  using const_iterator =
1446  virtual llvm::iterator_range<iterator> returned_values() = 0;
1447  virtual llvm::iterator_range<const_iterator> returned_values() const = 0;
1448 
1449  virtual size_t getNumReturnValues() const = 0;
1450  virtual const SmallSetVector<CallBase *, 4> &getUnresolvedCalls() const = 0;
1451 
1452  /// Create an abstract attribute view for the position \p IRP.
1453  static AAReturnedValues &createForPosition(const IRPosition &IRP,
1454  Attributor &A);
1455 
1456  /// Unique ID (due to the unique address)
1457  static const char ID;
1458 };
1459 
1461  : public IRAttribute<Attribute::NoUnwind,
1462  StateWrapper<BooleanState, AbstractAttribute>> {
1463  AANoUnwind(const IRPosition &IRP) : IRAttribute(IRP) {}
1464 
1465  /// Returns true if nounwind is assumed.
1466  bool isAssumedNoUnwind() const { return getAssumed(); }
1467 
1468  /// Returns true if nounwind is known.
1469  bool isKnownNoUnwind() const { return getKnown(); }
1470 
1471  /// Create an abstract attribute view for the position \p IRP.
1472  static AANoUnwind &createForPosition(const IRPosition &IRP, Attributor &A);
1473 
1474  /// Unique ID (due to the unique address)
1475  static const char ID;
1476 };
1477 
1478 struct AANoSync
1479  : public IRAttribute<Attribute::NoSync,
1480  StateWrapper<BooleanState, AbstractAttribute>> {
1481  AANoSync(const IRPosition &IRP) : IRAttribute(IRP) {}
1482 
1483  /// Returns true if "nosync" is assumed.
1484  bool isAssumedNoSync() const { return getAssumed(); }
1485 
1486  /// Returns true if "nosync" is known.
1487  bool isKnownNoSync() const { return getKnown(); }
1488 
1489  /// Create an abstract attribute view for the position \p IRP.
1490  static AANoSync &createForPosition(const IRPosition &IRP, Attributor &A);
1491 
1492  /// Unique ID (due to the unique address)
1493  static const char ID;
1494 };
1495 
1496 /// An abstract interface for all nonnull attributes.
1498  : public IRAttribute<Attribute::NonNull,
1499  StateWrapper<BooleanState, AbstractAttribute>> {
1500  AANonNull(const IRPosition &IRP) : IRAttribute(IRP) {}
1501 
1502  /// Return true if we assume that the underlying value is nonnull.
1503  bool isAssumedNonNull() const { return getAssumed(); }
1504 
1505  /// Return true if we know that underlying value is nonnull.
1506  bool isKnownNonNull() const { return getKnown(); }
1507 
1508  /// Create an abstract attribute view for the position \p IRP.
1509  static AANonNull &createForPosition(const IRPosition &IRP, Attributor &A);
1510 
1511  /// Unique ID (due to the unique address)
1512  static const char ID;
1513 };
1514 
1515 /// An abstract attribute for norecurse.
1517  : public IRAttribute<Attribute::NoRecurse,
1518  StateWrapper<BooleanState, AbstractAttribute>> {
1519  AANoRecurse(const IRPosition &IRP) : IRAttribute(IRP) {}
1520 
1521  /// Return true if "norecurse" is assumed.
1522  bool isAssumedNoRecurse() const { return getAssumed(); }
1523 
1524  /// Return true if "norecurse" is known.
1525  bool isKnownNoRecurse() const { return getKnown(); }
1526 
1527  /// Create an abstract attribute view for the position \p IRP.
1528  static AANoRecurse &createForPosition(const IRPosition &IRP, Attributor &A);
1529 
1530  /// Unique ID (due to the unique address)
1531  static const char ID;
1532 };
1533 
1534 /// An abstract attribute for willreturn.
1536  : public IRAttribute<Attribute::WillReturn,
1537  StateWrapper<BooleanState, AbstractAttribute>> {
1538  AAWillReturn(const IRPosition &IRP) : IRAttribute(IRP) {}
1539 
1540  /// Return true if "willreturn" is assumed.
1541  bool isAssumedWillReturn() const { return getAssumed(); }
1542 
1543  /// Return true if "willreturn" is known.
1544  bool isKnownWillReturn() const { return getKnown(); }
1545 
1546  /// Create an abstract attribute view for the position \p IRP.
1547  static AAWillReturn &createForPosition(const IRPosition &IRP, Attributor &A);
1548 
1549  /// Unique ID (due to the unique address)
1550  static const char ID;
1551 };
1552 
1553 /// An abstract interface for all noalias attributes.
1555  : public IRAttribute<Attribute::NoAlias,
1556  StateWrapper<BooleanState, AbstractAttribute>> {
1557  AANoAlias(const IRPosition &IRP) : IRAttribute(IRP) {}
1558 
1559  /// Return true if we assume that the underlying value is alias.
1560  bool isAssumedNoAlias() const { return getAssumed(); }
1561 
1562  /// Return true if we know that underlying value is noalias.
1563  bool isKnownNoAlias() const { return getKnown(); }
1564 
1565  /// Create an abstract attribute view for the position \p IRP.
1566  static AANoAlias &createForPosition(const IRPosition &IRP, Attributor &A);
1567 
1568  /// Unique ID (due to the unique address)
1569  static const char ID;
1570 };
1571 
1572 /// An AbstractAttribute for nofree.
1573 struct AANoFree
1574  : public IRAttribute<Attribute::NoFree,
1575  StateWrapper<BooleanState, AbstractAttribute>> {
1576  AANoFree(const IRPosition &IRP) : IRAttribute(IRP) {}
1577 
1578  /// Return true if "nofree" is assumed.
1579  bool isAssumedNoFree() const { return getAssumed(); }
1580 
1581  /// Return true if "nofree" is known.
1582  bool isKnownNoFree() const { return getKnown(); }
1583 
1584  /// Create an abstract attribute view for the position \p IRP.
1585  static AANoFree &createForPosition(const IRPosition &IRP, Attributor &A);
1586 
1587  /// Unique ID (due to the unique address)
1588  static const char ID;
1589 };
1590 
1591 /// An AbstractAttribute for noreturn.
1593  : public IRAttribute<Attribute::NoReturn,
1594  StateWrapper<BooleanState, AbstractAttribute>> {
1595  AANoReturn(const IRPosition &IRP) : IRAttribute(IRP) {}
1596 
1597  /// Return true if the underlying object is assumed to never return.
1598  bool isAssumedNoReturn() const { return getAssumed(); }
1599 
1600  /// Return true if the underlying object is known to never return.
1601  bool isKnownNoReturn() const { return getKnown(); }
1602 
1603  /// Create an abstract attribute view for the position \p IRP.
1604  static AANoReturn &createForPosition(const IRPosition &IRP, Attributor &A);
1605 
1606  /// Unique ID (due to the unique address)
1607  static const char ID;
1608 };
1609 
1610 /// An abstract interface for liveness abstract attribute.
1611 struct AAIsDead : public StateWrapper<BooleanState, AbstractAttribute>,
1612  public IRPosition {
1613  AAIsDead(const IRPosition &IRP) : IRPosition(IRP) {}
1614 
1615  /// Returns true if \p BB is assumed dead.
1616  virtual bool isAssumedDead(const BasicBlock *BB) const = 0;
1617 
1618  /// Returns true if \p BB is known dead.
1619  virtual bool isKnownDead(const BasicBlock *BB) const = 0;
1620 
1621  /// Returns true if \p I is assumed dead.
1622  virtual bool isAssumedDead(const Instruction *I) const = 0;
1623 
1624  /// Returns true if \p I is known dead.
1625  virtual bool isKnownDead(const Instruction *I) const = 0;
1626 
1627  /// This method is used to check if at least one instruction in a collection
1628  /// of instructions is live.
1629  template <typename T> bool isLiveInstSet(T begin, T end) const {
1630  for (const auto &I : llvm::make_range(begin, end)) {
1631  assert(I->getFunction() == getIRPosition().getAssociatedFunction() &&
1632  "Instruction must be in the same anchor scope function.");
1633 
1634  if (!isAssumedDead(I))
1635  return true;
1636  }
1637 
1638  return false;
1639  }
1640 
1641  /// Return an IR position, see struct IRPosition.
1642  ///
1643  ///{
1644  IRPosition &getIRPosition() override { return *this; }
1645  const IRPosition &getIRPosition() const override { return *this; }
1646  ///}
1647 
1648  /// Create an abstract attribute view for the position \p IRP.
1649  static AAIsDead &createForPosition(const IRPosition &IRP, Attributor &A);
1650 
1651  /// Unique ID (due to the unique address)
1652  static const char ID;
1653 };
1654 
1655 /// State for dereferenceable attribute
1657 
1658  /// State representing for dereferenceable bytes.
1660 
1661  /// State representing that whether the value is globaly dereferenceable.
1663 
1664  /// See AbstractState::isValidState()
1665  bool isValidState() const override { return DerefBytesState.isValidState(); }
1666 
1667  /// See AbstractState::isAtFixpoint()
1668  bool isAtFixpoint() const override {
1669  return !isValidState() ||
1670  (DerefBytesState.isAtFixpoint() && GlobalState.isAtFixpoint());
1671  }
1672 
1673  /// See AbstractState::indicateOptimisticFixpoint(...)
1675  DerefBytesState.indicateOptimisticFixpoint();
1676  GlobalState.indicateOptimisticFixpoint();
1677  return ChangeStatus::UNCHANGED;
1678  }
1679 
1680  /// See AbstractState::indicatePessimisticFixpoint(...)
1682  DerefBytesState.indicatePessimisticFixpoint();
1683  GlobalState.indicatePessimisticFixpoint();
1684  return ChangeStatus::CHANGED;
1685  }
1686 
1687  /// Update known dereferenceable bytes.
1688  void takeKnownDerefBytesMaximum(uint64_t Bytes) {
1689  DerefBytesState.takeKnownMaximum(Bytes);
1690  }
1691 
1692  /// Update assumed dereferenceable bytes.
1693  void takeAssumedDerefBytesMinimum(uint64_t Bytes) {
1694  DerefBytesState.takeAssumedMinimum(Bytes);
1695  }
1696 
1697  /// Equality for DerefState.
1698  bool operator==(const DerefState &R) {
1699  return this->DerefBytesState == R.DerefBytesState &&
1700  this->GlobalState == R.GlobalState;
1701  }
1702 
1703  /// Inequality for IntegerState.
1704  bool operator!=(const DerefState &R) { return !(*this == R); }
1705 
1706  /// See IntegerState::operator^=
1708  DerefBytesState ^= R.DerefBytesState;
1709  GlobalState ^= R.GlobalState;
1710  return *this;
1711  }
1712 
1713  /// See IntegerState::operator+=
1715  DerefBytesState += R.DerefBytesState;
1716  GlobalState += R.GlobalState;
1717  return *this;
1718  }
1719 
1720  /// See IntegerState::operator&=
1722  DerefBytesState &= R.DerefBytesState;
1723  GlobalState &= R.GlobalState;
1724  return *this;
1725  }
1726 
1727  /// See IntegerState::operator|=
1729  DerefBytesState |= R.DerefBytesState;
1730  GlobalState |= R.GlobalState;
1731  return *this;
1732  }
1733 
1734 protected:
1735  const AANonNull *NonNullAA = nullptr;
1736 };
1737 
1738 /// An abstract interface for all dereferenceable attribute.
1740  : public IRAttribute<Attribute::Dereferenceable,
1741  StateWrapper<DerefState, AbstractAttribute>> {
1743 
1744  /// Return true if we assume that the underlying value is nonnull.
1745  bool isAssumedNonNull() const {
1746  return NonNullAA && NonNullAA->isAssumedNonNull();
1747  }
1748 
1749  /// Return true if we know that the underlying value is nonnull.
1750  bool isKnownNonNull() const {
1751  return NonNullAA && NonNullAA->isKnownNonNull();
1752  }
1753 
1754  /// Return true if we assume that underlying value is
1755  /// dereferenceable(_or_null) globally.
1756  bool isAssumedGlobal() const { return GlobalState.getAssumed(); }
1757 
1758  /// Return true if we know that underlying value is
1759  /// dereferenceable(_or_null) globally.
1760  bool isKnownGlobal() const { return GlobalState.getKnown(); }
1761 
1762  /// Return assumed dereferenceable bytes.
1764  return DerefBytesState.getAssumed();
1765  }
1766 
1767  /// Return known dereferenceable bytes.
1769  return DerefBytesState.getKnown();
1770  }
1771 
1772  /// Create an abstract attribute view for the position \p IRP.
1773  static AADereferenceable &createForPosition(const IRPosition &IRP,
1774  Attributor &A);
1775 
1776  /// Unique ID (due to the unique address)
1777  static const char ID;
1778 };
1779 
1780 /// An abstract interface for all align attributes.
1781 struct AAAlign
1782  : public IRAttribute<Attribute::Alignment,
1783  StateWrapper<IntegerState, AbstractAttribute>> {
1784  AAAlign(const IRPosition &IRP) : IRAttribute(IRP) {}
1785 
1786  /// Return assumed alignment.
1787  unsigned getAssumedAlign() const { return getAssumed(); }
1788 
1789  /// Return known alignemnt.
1790  unsigned getKnownAlign() const { return getKnown(); }
1791 
1792  /// Create an abstract attribute view for the position \p IRP.
1793  static AAAlign &createForPosition(const IRPosition &IRP, Attributor &A);
1794 
1795  /// Unique ID (due to the unique address)
1796  static const char ID;
1797 };
1798 
1799 /// An abstract interface for all nocapture attributes.
1801  : public IRAttribute<Attribute::NoCapture,
1802  StateWrapper<IntegerState, AbstractAttribute>> {
1803  AANoCapture(const IRPosition &IRP) : IRAttribute(IRP) {}
1804 
1805  /// State encoding bits. A set bit in the state means the property holds.
1806  /// NO_CAPTURE is the best possible state, 0 the worst possible state.
1807  enum {
1808  NOT_CAPTURED_IN_MEM = 1 << 0,
1809  NOT_CAPTURED_IN_INT = 1 << 1,
1810  NOT_CAPTURED_IN_RET = 1 << 2,
1811 
1812  /// If we do not capture the value in memory or through integers we can only
1813  /// communicate it back as a derived pointer.
1814  NO_CAPTURE_MAYBE_RETURNED = NOT_CAPTURED_IN_MEM | NOT_CAPTURED_IN_INT,
1815 
1816  /// If we do not capture the value in memory, through integers, or as a
1817  /// derived pointer we know it is not captured.
1818  NO_CAPTURE =
1819  NOT_CAPTURED_IN_MEM | NOT_CAPTURED_IN_INT | NOT_CAPTURED_IN_RET,
1820  };
1821 
1822  /// Return true if we know that the underlying value is not captured in its
1823  /// respective scope.
1824  bool isKnownNoCapture() const { return isKnown(NO_CAPTURE); }
1825 
1826  /// Return true if we assume that the underlying value is not captured in its
1827  /// respective scope.
1828  bool isAssumedNoCapture() const { return isAssumed(NO_CAPTURE); }
1829 
1830  /// Return true if we know that the underlying value is not captured in its
1831  /// respective scope but we allow it to escape through a "return".
1833  return isKnown(NO_CAPTURE_MAYBE_RETURNED);
1834  }
1835 
1836  /// Return true if we assume that the underlying value is not captured in its
1837  /// respective scope but we allow it to escape through a "return".
1839  return isAssumed(NO_CAPTURE_MAYBE_RETURNED);
1840  }
1841 
1842  /// Create an abstract attribute view for the position \p IRP.
1843  static AANoCapture &createForPosition(const IRPosition &IRP, Attributor &A);
1844 
1845  /// Unique ID (due to the unique address)
1846  static const char ID;
1847 };
1848 
1849 /// An abstract interface for value simplify abstract attribute.
1850 struct AAValueSimplify : public StateWrapper<BooleanState, AbstractAttribute>,
1851  public IRPosition {
1852  AAValueSimplify(const IRPosition &IRP) : IRPosition(IRP) {}
1853 
1854  /// Return an IR position, see struct IRPosition.
1855  ///
1856  ///{
1857  IRPosition &getIRPosition() { return *this; }
1858  const IRPosition &getIRPosition() const { return *this; }
1859  ///}
1860 
1861  /// Return an assumed simplified value if a single candidate is found. If
1862  /// there cannot be one, return original value. If it is not clear yet, return
1863  /// the Optional::NoneType.
1864  virtual Optional<Value *> getAssumedSimplifiedValue(Attributor &A) const = 0;
1865 
1866  /// Create an abstract attribute view for the position \p IRP.
1867  static AAValueSimplify &createForPosition(const IRPosition &IRP,
1868  Attributor &A);
1869 
1870  /// Unique ID (due to the unique address)
1871  static const char ID;
1872 };
1873 
1874 struct AAHeapToStack : public StateWrapper<BooleanState, AbstractAttribute>,
1875  public IRPosition {
1876  AAHeapToStack(const IRPosition &IRP) : IRPosition(IRP) {}
1877 
1878  /// Returns true if HeapToStack conversion is assumed to be possible.
1879  bool isAssumedHeapToStack() const { return getAssumed(); }
1880 
1881  /// Returns true if HeapToStack conversion is known to be possible.
1882  bool isKnownHeapToStack() const { return getKnown(); }
1883 
1884  /// Return an IR position, see struct IRPosition.
1885  ///
1886  ///{
1887  IRPosition &getIRPosition() { return *this; }
1888  const IRPosition &getIRPosition() const { return *this; }
1889  ///}
1890 
1891  /// Create an abstract attribute view for the position \p IRP.
1892  static AAHeapToStack &createForPosition(const IRPosition &IRP, Attributor &A);
1893 
1894  /// Unique ID (due to the unique address)
1895  static const char ID;
1896 };
1897 
1898 /// An abstract interface for all memory related attributes.
1900  : public IRAttribute<Attribute::ReadNone,
1901  StateWrapper<IntegerState, AbstractAttribute>> {
1903 
1904  /// State encoding bits. A set bit in the state means the property holds.
1905  /// BEST_STATE is the best possible state, 0 the worst possible state.
1906  enum {
1907  NO_READS = 1 << 0,
1908  NO_WRITES = 1 << 1,
1909  NO_ACCESSES = NO_READS | NO_WRITES,
1910 
1911  BEST_STATE = NO_ACCESSES,
1912  };
1913 
1914  /// Return true if we know that the underlying value is not read or accessed
1915  /// in its respective scope.
1916  bool isKnownReadNone() const { return isKnown(NO_ACCESSES); }
1917 
1918  /// Return true if we assume that the underlying value is not read or accessed
1919  /// in its respective scope.
1920  bool isAssumedReadNone() const { return isAssumed(NO_ACCESSES); }
1921 
1922  /// Return true if we know that the underlying value is not accessed
1923  /// (=written) in its respective scope.
1924  bool isKnownReadOnly() const { return isKnown(NO_WRITES); }
1925 
1926  /// Return true if we assume that the underlying value is not accessed
1927  /// (=written) in its respective scope.
1928  bool isAssumedReadOnly() const { return isAssumed(NO_WRITES); }
1929 
1930  /// Return true if we know that the underlying value is not read in its
1931  /// respective scope.
1932  bool isKnownWriteOnly() const { return isKnown(NO_READS); }
1933 
1934  /// Return true if we assume that the underlying value is not read in its
1935  /// respective scope.
1936  bool isAssumedWriteOnly() const { return isAssumed(NO_READS); }
1937 
1938  /// Create an abstract attribute view for the position \p IRP.
1939  static AAMemoryBehavior &createForPosition(const IRPosition &IRP,
1940  Attributor &A);
1941 
1942  /// Unique ID (due to the unique address)
1943  static const char ID;
1944 };
1945 
1946 } // end namespace llvm
1947 
1948 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H
An attribute for a call site return value.
Definition: Attributor.h:151
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
ChangeStatus indicateOptimisticFixpoint() override
See AbstractState::indicateOptimisticFixpoint(...)
Definition: Attributor.h:1089
OpcodeInstMapTy & getOpcodeInstMapForFunction(const Function &F)
Return the map that relates "interesting" opcodes with all instructions with that opcode in F...
Definition: Attributor.h:618
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1871
void DeleteContainerPointers(Container &C)
For a container of pointers, deletes the pointers and then clears the container.
Definition: STLExtras.h:1128
Analysis::Result * getAnalysis(const Module &M)
Definition: Attributor.h:573
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:112
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:641
void takeAssumedDerefBytesMinimum(uint64_t Bytes)
Update assumed dereferenceable bytes.
Definition: Attributor.h:1693
bool isKnownNoCaptureMaybeReturned() const
Return true if we know that the underlying value is not captured in its respective scope but we allow...
Definition: Attributor.h:1832
static IRPosition getEmptyKey()
Definition: Attributor.h:513
uint32_t getKnownDereferenceableBytes() const
Return known dereferenceable bytes.
Definition: Attributor.h:1768
bool hasLocalLinkage() const
Definition: GlobalValue.h:445
int getCallArgOperandNo(Argument &Arg) const
Return the operand index of the underlying instruction associated with Arg.
Definition: CallSite.h:820
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
static ChangeStatus manifestAttrs(Attributor &A, IRPosition &IRP, const ArrayRef< Attribute > &DeducedAttrs)
Definition: Attributor.cpp:331
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool isAssumedNoSync() const
Returns true if "nosync" is assumed.
Definition: Attributor.h:1484
const Function * getAnchorScope() const
Definition: Attributor.h:333
void setAttributes(AttributeList PAL)
Set the parameter attributes of the call.
Definition: CallSite.h:341
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
bool isAssumedReadOnly() const
Return true if we assume that the underlying value is not accessed (=written) in its respective scope...
Definition: Attributor.h:1928
ChangeStatus
Simple enum class that forces the status to be spelled out explicitly.
Definition: Attributor.h:120
static IRPosition getTombstoneKey()
Definition: Attributor.h:514
IRPosition & getIRPosition() override
Return an IR position, see struct IRPosition.
Definition: Attributor.h:1279
A position that is not associated with a spot suitable for attributes.
Definition: Attributor.h:148
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1943
IntegerState DerefBytesState
State representing for dereferenceable bytes.
Definition: Attributor.h:1659
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1588
bool isAnyCallSitePosition() const
Definition: Attributor.h:472
AANoAlias(const IRPosition &IRP)
Definition: Attributor.h:1557
An abstract interface for all nocapture attributes.
Definition: Attributor.h:1800
Abstract Attribute Classes
Definition: Attributor.h:1421
virtual ~AbstractState()
Definition: Attributor.h:1034
Helper struct necessary as the modular build fails if the virtual method IRAttribute::manifest is def...
Definition: Attributor.h:1215
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:104
base_t getAssumed() const
Return the assumed state encoding.
Definition: Attributor.h:1104
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1895
An attribute for a call site argument.
Definition: Attributor.h:155
bool isAssumedNoReturn() const
Return true if the underlying object is assumed to never return.
Definition: Attributor.h:1598
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:323
IntegerState & takeAssumedMinimum(base_t Value)
Take minimum of assumed and Value.
Definition: Attributor.h:1145
This class implements a map that also provides access to all stored values in a deterministic order...
Definition: MapVector.h:37
bool isAssumedNoRecurse() const
Return true if "norecurse" is assumed.
Definition: Attributor.h:1522
An abstract attribute for willreturn.
Definition: Attributor.h:1535
APInt operator &(APInt a, const APInt &b)
Definition: APInt.h:1987
Value & getAssociatedValue()
}
Definition: Attributor.h:361
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
F(f)
MustBeExecutedContextExplorer & getMustBeExecutedContextExplorer()
Return MustBeExecutedContextExplorer.
Definition: Attributor.h:631
bool isValidState() const override
See AbstractState::isValidState() NOTE: For now we simply pretend that the worst possible state is in...
Definition: Attributor.h:1083
MapVector< Value *, SmallSetVector< ReturnInst *, 4 > >::const_iterator const_iterator
Definition: Attributor.h:1445
block Block Frequency true
const Argument * getAssociatedArgument() const
Definition: Attributor.h:302
unsigned getKnownAlign() const
Return known alignemnt.
Definition: Attributor.h:1790
Helper to tie a abstract state implementation to an abstract attribute.
Definition: Attributor.h:1222
Kind
The positions we distinguish in the IR.
Definition: Attributor.h:146
bool operator==(const IntegerState &R) const
Equality for IntegerState.
Definition: Attributor.h:1160
Wrapper for FunctoinAnalysisManager.
Definition: Attributor.h:561
A node in the call graph for a module.
Definition: CallGraph.h:164
AANoReturn(const IRPosition &IRP)
Definition: Attributor.h:1595
IntegerState operator|=(const IntegerState &R)
Make this the maximum, known and assumed, of this state and R.
Definition: Attributor.h:1194
virtual ChangeStatus indicatePessimisticFixpoint()=0
Indicate that the abstract state should converge to the pessimistic state.
IntegerState operator^=(const IntegerState &R)
"Clamp" this state with R.
Definition: Attributor.h:1174
bool isAssumedHeapToStack() const
Returns true if HeapToStack conversion is assumed to be possible.
Definition: Attributor.h:1879
bool hasAttribute(unsigned Index, Attribute::AttrKind Kind) const
Return true if the attribute exists at the given index.
Instruction * getCtxI()
}
Definition: Attributor.h:341
const Value & getAnchorValue() const
Definition: Attributor.h:261
AAAlign(const IRPosition &IRP)
Definition: Attributor.h:1784
IRPosition & getIRPosition()
Return an IR position, see struct IRPosition.
Definition: Attributor.h:1887
static const IRPosition function_scope(const IRPosition &IRP)
Create a position with function scope matching the "context" of IRP.
Definition: Attributor.h:234
An AbstractAttribute for noreturn.
Definition: Attributor.h:1592
A visitor class for IR positions.
Definition: Attributor.h:550
bool isKnownNoReturn() const
Return true if the underlying object is known to never return.
Definition: Attributor.h:1601
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1796
static const IRPosition callsite_argument(AbstractCallSite ACS, unsigned ArgNo)
Create a position describing the argument of ACS at position ArgNo.
Definition: Attributor.h:221
const IRPosition & getIRPosition() const
Return an IR position, see struct IRPosition.
Definition: Attributor.h:1858
std::vector< Instruction * > InstructionVectorTy
A vector type to hold instructions.
Definition: Attributor.h:623
bool isAssumedNoAlias() const
Return true if we assume that the underlying value is alias.
Definition: Attributor.h:1560
bool isKnown(base_t BitsEncoding) const
Return true if the bits set in BitsEncoding are "known bits".
Definition: Attributor.h:1107
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
An abstract attribute for norecurse.
Definition: Attributor.h:1516
bool isAssumedNoUnwind() const
Returns true if nounwind is assumed.
Definition: Attributor.h:1466
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
virtual ~IRPosition()
Definition: Attributor.h:139
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1531
An abstract interface for all noalias attributes.
Definition: Attributor.h:1554
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:225
An attribute for the function return value.
Definition: Attributor.h:150
void takeKnownDerefBytesMaximum(uint64_t Bytes)
Update known dereferenceable bytes.
Definition: Attributor.h:1688
InstrTy * getInstruction() const
Definition: CallSite.h:96
uint32_t getAssumedDereferenceableBytes() const
Return assumed dereferenceable bytes.
Definition: Attributor.h:1763
ChangeStatus indicatePessimisticFixpoint() override
See AbstractState::indicatePessimisticFixpoint(...)
Definition: Attributor.h:1095
InstructionVectorTy & getReadOrWriteInstsForFunction(const Function &F)
Return the instructions in F that may read or write memory.
Definition: Attributor.h:626
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
int getArgNo() const
}
Definition: Attributor.h:376
Attribute getAttr(Attribute::AttrKind AK) const
Return the attribute of kind AK existing in the IR at this position.
Definition: Attributor.h:435
bool operator==(const IRPosition &RHS) const
Definition: Attributor.h:243
AANoCapture(const IRPosition &IRP)
Definition: Attributor.h:1803
An abstract interface for liveness abstract attribute.
Definition: Attributor.h:1611
IntegerState & removeKnownBits(base_t BitsEncoding)
Remove the bits in BitsEncoding from the "known bits".
Definition: Attributor.h:1132
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:372
bool isAssumedNoFree() const
Return true if "nofree" is assumed.
Definition: Attributor.h:1579
AAWillReturn(const IRPosition &IRP)
Definition: Attributor.h:1538
static const IRPosition callsite_returned(ImmutableCallSite ICS)
Create a position describing the returned value of ICS.
Definition: Attributor.h:209
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
bool isKnownWriteOnly() const
Return true if we know that the underlying value is not read in its respective scope.
Definition: Attributor.h:1932
bool operator!=(const IRPosition &RHS) const
Definition: Attributor.h:246
bool isKnownNoUnwind() const
Returns true if nounwind is known.
Definition: Attributor.h:1469
An abstract interface for all nonnull attributes.
Definition: Attributor.h:1497
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:258
constexpr char Attrs[]
Key for Kernel::Metadata::mAttrs.
IntegerState(base_t BestState=~0)
Initialize the (best) state.
Definition: Attributor.h:1076
ChangeStatus manifest(Attributor &A) override
See AbstractAttribute::manifest(...).
Definition: Attributor.h:1261
ChangeStatus update(Attributor &A)
Hook for the Attributor to trigger an update of the internal state.
Definition: Attributor.cpp:315
IntegerState & takeKnownMaximum(base_t Value)
Take maximum of known and Value.
Definition: Attributor.h:1152
bool isAssumedGlobal() const
Return true if we assume that underlying value is dereferenceable(_or_null) globally.
Definition: Attributor.h:1756
unsigned getAttrIdx() const
Return the index in the attribute list for this position.
Definition: Attributor.h:379
AAHeapToStack(const IRPosition &IRP)
Definition: Attributor.h:1876
const AAType & getAAFor(const AbstractAttribute &QueryingAA, const IRPosition &IRP, bool TrackDependence=true)
Lookup an abstract attribute of type AAType at position IRP.
Definition: Attributor.h:757
bool isKnownNoFree() const
Return true if "nofree" is known.
Definition: Attributor.h:1582
virtual bool isValidState() const =0
Return if this abstract state is in a valid state.
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1569
IRPosition & getIRPosition() override
Return an IR position, see struct IRPosition.
Definition: Attributor.h:1644
bool isKnownReadOnly() const
Return true if we know that the underlying value is not accessed (=written) in its respective scope...
Definition: Attributor.h:1924
AttributeSet getAttributes(unsigned Index) const
The attributes for the specified index are returned.
AAReturnedValues(const IRPosition &IRP)
Definition: Attributor.h:1423
static const IRPosition callsite_function(ImmutableCallSite ICS)
Create a position describing the function scope of ICS.
Definition: Attributor.h:204
MapVector< Value *, SmallSetVector< ReturnInst *, 4 > >::iterator iterator
Definition: Attributor.h:1443
base_t getKnown() const
Return the known state encoding.
Definition: Attributor.h:1101
bool isAtFixpoint() const override
See AbstractState::isAtFixpoint()
Definition: Attributor.h:1668
DerefState operator+=(const DerefState &R)
See IntegerState::operator+=.
Definition: Attributor.h:1714
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
bool checkForAllCallLikeInstructions(const function_ref< bool(Instruction &)> &Pred, const AbstractAttribute &QueryingAA)
Check Pred on all call-like instructions (=CallBased derived).
Definition: Attributor.h:881
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1846
void removeAttrs(ArrayRef< Attribute::AttrKind > AKs)
Remove the attribute of kind AKs existing in the IR at this position.
Definition: Attributor.h:451
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
Instruction * getInstruction() const
Return the underlying instruction.
Definition: CallSite.h:772
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1550
An abstract interface for all dereferenceable attribute.
Definition: Attributor.h:1739
AAType & registerAA(AAType &AA)
Introduce a new abstract attribute into the fixpoint analysis.
Definition: Attributor.h:781
bool isKnownNoSync() const
Returns true if "nosync" is known.
Definition: Attributor.h:1487
AANoUnwind(const IRPosition &IRP)
Definition: Attributor.h:1463
AttributeList getAttributes() const
Get the parameter attributes of the call.
Definition: CallSite.h:337
A manager for alias analyses.
bool isKnownNoCapture() const
Return true if we know that the underlying value is not captured in its respective scope...
Definition: Attributor.h:1824
AADereferenceable(const IRPosition &IRP)
Definition: Attributor.h:1742
Value & getAnchorValue()
Return the value this abstract attribute is anchored with.
Definition: Attributor.h:256
static const IRPosition returned(const Function &F)
Create a position describing the returned value of F.
Definition: Attributor.h:178
An attribute for a function (scope).
Definition: Attributor.h:152
virtual void initialize(Attributor &A)
Initialize the state with the information in the Attributor A.
Definition: Attributor.h:1341
AANoFree(const IRPosition &IRP)
Definition: Attributor.h:1576
bool isAssumedNoCaptureMaybeReturned() const
Return true if we assume that the underlying value is not captured in its respective scope but we all...
Definition: Attributor.h:1838
An attribute for a function argument.
Definition: Attributor.h:154
bool isFnInterfaceKind() const
}
Definition: Attributor.h:309
bool isAssumedNonNull() const
Return true if we assume that the underlying value is nonnull.
Definition: Attributor.h:1503
The fixpoint analysis framework that orchestrates the attribute deduction.
Definition: Attributor.h:713
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
size_t arg_size() const
Definition: Function.h:728
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
arg_iterator arg_begin()
Definition: Function.h:695
const DataLayout & getDataLayout() const
Return the data layout associated with the anchor scope.
Definition: Attributor.h:899
static unsigned getHashValue(const IRPosition &IRP)
Definition: Attributor.h:517
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:59
Simple state with integers encoding.
Definition: Attributor.h:1071
unsigned getSccSize(const Function &F)
Return SCC size on call graph for function F.
Definition: Attributor.h:646
Attribute::AttrKind getAttrKind() const
Return the kind that identifies the abstract attribute implementation.
Definition: Attributor.h:1268
Attribute getAttribute(unsigned Index, Attribute::AttrKind Kind) const
Return the attribute object that exists at the given index.
Base struct for all "concrete attribute" deductions.
Definition: Attributor.h:1327
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1652
AAMemoryBehavior(const IRPosition &IRP)
Definition: Attributor.h:1902
void recordDependence(const AbstractAttribute &FromAA, const AbstractAttribute &ToAA)
Explicitly record a dependence from FromAA to ToAA, that is if FromAA changes ToAA should be updated ...
Definition: Attributor.h:769
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1475
bool verify(const TargetRegisterInfo &TRI) const
Check that information hold by this instance make sense for the given TRI.
StateType & getState() override
See AbstractAttribute::getState(...).
Definition: Attributor.h:1227
bool isKnownHeapToStack() const
Returns true if HeapToStack conversion is known to be possible.
Definition: Attributor.h:1882
An abstract interface for all memory related attributes.
Definition: Attributor.h:1899
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Attributor(InformationCache &InfoCache, unsigned DepRecomputeInterval, DenseSet< const char *> *Whitelist=nullptr)
Constructor.
Definition: Attributor.h:721
virtual StateType & getState()=0
Return the internal abstract state for inspection.
bool isKnownNonNull() const
Return true if we know that the underlying value is nonnull.
Definition: Attributor.h:1750
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1457
An AbstractAttribute for nofree.
Definition: Attributor.h:1573
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:297
IntegerState & removeAssumedBits(base_t BitsEncoding)
Remove the bits in BitsEncoding from the "assumed bits" if not known.
Definition: Attributor.h:1125
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
AANoRecurse(const IRPosition &IRP)
Definition: Attributor.h:1519
const IRPosition & getIRPosition() const override
Definition: Attributor.h:1280
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:390
BooleanState GlobalState
State representing that whether the value is globaly dereferenceable.
Definition: Attributor.h:1662
bool isAssumedNoCapture() const
Return true if we assume that the underlying value is not captured in its respective scope...
Definition: Attributor.h:1828
void deleteAfterManifest(Instruction &I)
Record that I is deleted after information was manifested.
Definition: Attributor.h:829
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
bool isKnownReadNone() const
Return true if we know that the underlying value is not read or accessed in its respective scope...
Definition: Attributor.h:1916
Data structure to hold cached (LLVM-IR) information.
Definition: Attributor.h:597
Provides information about what library functions are available for the current target.
void markLiveInternalFunction(const Function &F)
Mark the internal function F as live.
Definition: Attributor.h:821
const Instruction * getCtxI() const
Definition: Attributor.h:353
static const IRPosition callsite_argument(ImmutableCallSite ICS, unsigned ArgNo)
Create a position describing the argument of ICS at position ArgNo.
Definition: Attributor.h:214
IRAttribute(const IRPosition &IRP)
Definition: Attributor.h:1236
const DataLayout & getDL()
Return datalayout used in the module.
Definition: Attributor.h:653
virtual void initialize(Attributor &A) override
See AbstractAttribute::initialize(...).
Definition: Attributor.h:1240
bool operator==(const DerefState &R)
Equality for DerefState.
Definition: Attributor.h:1698
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static const IRPosition callsite_returned(const CallBase &CB)
Create a position describing the returned value of CB.
Definition: Attributor.h:193
A range adaptor for a pair of iterators.
bool operator!=(const IntegerState &R) const
Inequality for IntegerState.
Definition: Attributor.h:1166
InformationCache(const Module &M, AnalysisGetter &AG)
Definition: Attributor.h:598
Helper class that provides common functionality to manifest IR attributes.
Definition: Attributor.h:1235
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1493
unsigned getArgNo() const
Return the index of this formal argument in its containing function.
Definition: Argument.h:47
const IRPosition & getIRPosition() const override
Return an IR position, see struct IRPosition.
Definition: Attributor.h:1645
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1607
static const IRPosition value(const Value &V)
Create a position describing the value of V.
Definition: Attributor.h:164
A "must be executed context" for a given program point PP is the set of instructions, potentially before and after PP, that are executed always when PP is reached.
Definition: MustExecute.h:368
An interface to query the internal state of an abstract attribute.
Definition: Attributor.h:1033
void deleteAfterManifest(Function &F)
Record that F is deleted after information was manifested.
Definition: Attributor.h:835
An analysis pass to compute the CallGraph for a Module.
Definition: CallGraph.h:292
Function * getAssociatedFunction()
}
Definition: Attributor.h:269
An abstract interface for all align attributes.
Definition: Attributor.h:1781
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:73
bool isAssumedWriteOnly() const
Return true if we assume that the underlying value is not read in its respective scope.
Definition: Attributor.h:1936
static const IRPosition argument(const Argument &Arg)
Create a position describing the argument Arg.
Definition: Attributor.h:183
TargetLibraryInfo * getTargetLibraryInfoForFunction(const Function &F)
Return TargetLibraryInfo for function F.
Definition: Attributor.h:636
IRPosition & getIRPosition()
Return an IR position, see struct IRPosition.
Definition: Attributor.h:1857
IntegerState & addKnownBits(base_t Bits)
Add the bits in BitsEncoding to the "known bits".
Definition: Attributor.h:1117
block Block Frequency Analysis
static bool isEqual(const IRPosition &LHS, const IRPosition &RHS)
Definition: Attributor.h:521
Analysis::Result * getAnalysis(const Function &F)
Definition: Attributor.h:563
Pass * createAttributorLegacyPass()
Argument * getAssociatedArgument()
}
Definition: Attributor.h:291
const Value & getAssociatedValue() const
Definition: Attributor.h:369
InformationCache & getInfoCache()
Return the internal information cache.
Definition: Attributor.h:797
const Function * getAssociatedFunction() const
Definition: Attributor.h:283
bool operator!=(const DerefState &R)
Inequality for IntegerState.
Definition: Attributor.h:1704
bool hasExactDefinition() const
Return true if this global has an exact defintion.
Definition: GlobalValue.h:416
Establish a view to a call site for examination.
Definition: CallSite.h:906
LLVM_NODISCARD AttributeList removeAttribute(LLVMContext &C, unsigned Index, Attribute::AttrKind Kind) const
Remove the specified attribute at the specified index from this attribute list.
#define I(x, y, z)
Definition: MD5.cpp:58
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1512
An abstract interface for value simplify abstract attribute.
Definition: Attributor.h:1850
virtual void getDeducedAttributes(LLVMContext &Ctx, SmallVectorImpl< Attribute > &Attrs) const
Return the deduced attributes in Attrs.
Definition: Attributor.h:1271
static const IRPosition callsite_function(const CallBase &CB)
Create a position describing the function scope of CB.
Definition: Attributor.h:188
bool isLiveInstSet(T begin, T end) const
This method is used to check if at least one instruction in a collection of instructions is live...
Definition: Attributor.h:1629
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:80
An attribute for a call site (function scope).
Definition: Attributor.h:153
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1777
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2047
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
AAResults * getAAResultsForFunction(const Function &F)
Return AliasAnalysis Result for function F.
Definition: Attributor.h:641
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:185
unsigned getAssumedAlign() const
Return assumed alignment.
Definition: Attributor.h:1787
bool isKnownGlobal() const
Return true if we know that underlying value is dereferenceable(_or_null) globally.
Definition: Attributor.h:1760
bool isKnownNoRecurse() const
Return true if "norecurse" is known.
Definition: Attributor.h:1525
AAValueSimplify(const IRPosition &IRP)
Definition: Attributor.h:1852
Analysis pass providing the TargetLibraryInfo.
bool isValidState() const override
See AbstractState::isValidState()
Definition: Attributor.h:1665
AANonNull(const IRPosition &IRP)
Definition: Attributor.h:1500
static const IRPosition EmptyKey
Special DenseMap key values.
Definition: Attributor.h:486
bool isKnownWillReturn() const
Return true if "willreturn" is known.
Definition: Attributor.h:1544
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static const IRPosition TombstoneKey
Definition: Attributor.h:487
const IRPosition & getIRPosition() const
Return an IR position, see struct IRPosition.
Definition: Attributor.h:1888
AbstractCallSite.
Definition: CallSite.h:718
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:575
LLVM Value Representation.
Definition: Value.h:74
bool isKnownNonNull() const
Return true if we know that underlying value is nonnull.
Definition: Attributor.h:1506
E & operator &=(E &LHS, E RHS)
Definition: BitmaskEnum.h:133
Function * getAnchorScope()
Return the Function surrounding the anchor value.
Definition: Attributor.h:323
const AbstractState & getState() const override
See AbstractAttribute::getState(...).
Definition: Attributor.h:1230
virtual ChangeStatus manifest(Attributor &A)
Hook for the Attributor to trigger the manifestation of the information represented by the abstract a...
Definition: Attributor.h:1375
bool isAssumedWillReturn() const
Return true if "willreturn" is assumed.
Definition: Attributor.h:1541
An invalid position.
Definition: Attributor.h:147
virtual ~AbstractAttribute()
Virtual destructor.
Definition: Attributor.h:1331
bool isAssumedReadNone() const
Return true if we assume that the underlying value is not read or accessed in its respective scope...
Definition: Attributor.h:1920
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
State for dereferenceable attribute.
Definition: Attributor.h:1656
bool isAtFixpoint() const override
See AbstractState::isAtFixpoint()
Definition: Attributor.h:1086
static const IRPosition callsite_argument(const CallBase &CB, unsigned ArgNo)
Create a position describing the argument of CB at position ArgNo.
Definition: Attributor.h:198
bool isKnownNoAlias() const
Return true if we know that underlying value is noalias.
Definition: Attributor.h:1563
ChangeStatus indicatePessimisticFixpoint() override
See AbstractState::indicatePessimisticFixpoint(...)
Definition: Attributor.h:1681
A container for analyses that lazily runs them and caches their results.
DerefState operator|=(const DerefState &R)
See IntegerState::operator|=.
Definition: Attributor.h:1728
APInt operator|(APInt a, const APInt &b)
Definition: APInt.h:2007
static constexpr base_t getWorstState()
Return the worst possible representable state.
Definition: Attributor.h:1079
AAIsDead(const IRPosition &IRP)
Definition: Attributor.h:1613
This header defines various interfaces for pass management in LLVM.
bool isAssumedNonNull() const
Return true if we assume that the underlying value is nonnull.
Definition: Attributor.h:1745
bool isAssumed(base_t BitsEncoding) const
Return true if the bits set in BitsEncoding are "assumed bits".
Definition: Attributor.h:1112
IntegerState operator+=(const IntegerState &R)
"Clamp" this state with R.
Definition: Attributor.h:1181
AANoSync(const IRPosition &IRP)
Definition: Attributor.h:1481
DerefState operator^=(const DerefState &R)
See IntegerState::operator^=.
Definition: Attributor.h:1707
static const IRPosition function(const Function &F)
Create a position describing the function scope of F.
Definition: Attributor.h:173
IRPosition()
Default constructor available to create invalid positions implicitly.
Definition: Attributor.h:161
Kind getPositionKind() const
Return the associated position kind.
Definition: Attributor.h:399
void deleteAfterManifest(BasicBlock &BB)
Record that BB is deleted after information was manifested.
Definition: Attributor.h:832
AnalysisGetter(ModuleAnalysisManager &MAM)
Definition: Attributor.h:578
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
Definition: SCCIterator.h:42
Simple wrapper for a single bit (boolean) state.
Definition: Attributor.h:1209
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results...
Definition: Attributes.h:70
IntegerState & intersectAssumedBits(base_t BitsEncoding)
Keep only "assumed bits" also set in BitsEncoding but all known ones.
Definition: Attributor.h:1138
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:1044
ChangeStatus indicateOptimisticFixpoint() override
See AbstractState::indicateOptimisticFixpoint(...)
Definition: Attributor.h:1674