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/SetVector.h"
100 #include "llvm/ADT/MapVector.h"
101 #include "llvm/IR/CallSite.h"
102 #include "llvm/IR/PassManager.h"
103 
104 namespace llvm {
105 
106 struct AbstractAttribute;
107 struct InformationCache;
108 struct AAIsDead;
109 
110 class Function;
111 
112 /// Simple enum class that forces the status to be spelled out explicitly.
113 ///
114 ///{
115 enum class ChangeStatus {
116  CHANGED,
117  UNCHANGED,
118 };
119 
122 ///}
123 
124 /// Helper to describe and deal with positions in the LLVM-IR.
125 ///
126 /// A position in the IR is described by an anchor value and an "offset" that
127 /// could be the argument number, for call sites and arguments, or an indicator
128 /// of the "position kind". The kinds, specified in the Kind enum below, include
129 /// the locations in the attribute list, i.a., function scope and return value,
130 /// as well as a distinction between call sites and functions. Finally, there
131 /// are floating values that do not have a corresponding attribute list
132 /// position.
133 struct IRPosition {
134  virtual ~IRPosition() {}
135 
136  /// The positions we distinguish in the IR.
137  ///
138  /// The values are chosen such that the KindOrArgNo member has a value >= 1
139  /// if it is an argument or call site argument while a value < 1 indicates the
140  /// respective kind of that value.
141  enum Kind : int {
142  IRP_INVALID = -6, ///< An invalid position.
143  IRP_FLOAT = -5, ///< A position that is not associated with a spot suitable
144  ///< for attributes. This could be any value or instruction.
145  IRP_RETURNED = -4, ///< An attribute for the function return value.
146  IRP_CALL_SITE_RETURNED = -3, ///< An attribute for a call site return value.
147  IRP_FUNCTION = -2, ///< An attribute for a function (scope).
148  IRP_CALL_SITE = -1, ///< An attribute for a call site (function scope).
149  IRP_ARGUMENT = 0, ///< An attribute for a function argument.
150  IRP_CALL_SITE_ARGUMENT = 1, ///< An attribute for a call site argument.
151  };
152 
153  /// Default constructor available to create invalid positions implicitly. All
154  /// other positions need to be created explicitly through the appropriate
155  /// static member function.
156  IRPosition() : AnchorVal(nullptr), KindOrArgNo(IRP_INVALID) { verify(); }
157 
158  /// Create a position describing the value of \p V.
159  static const IRPosition value(const Value &V) {
160  if (auto *Arg = dyn_cast<Argument>(&V))
161  return IRPosition::argument(*Arg);
162  if (auto *CB = dyn_cast<CallBase>(&V))
163  return IRPosition::callsite_returned(*CB);
164  return IRPosition(const_cast<Value &>(V), IRP_FLOAT);
165  }
166 
167  /// Create a position describing the function scope of \p F.
168  static const IRPosition function(const Function &F) {
169  return IRPosition(const_cast<Function &>(F), IRP_FUNCTION);
170  }
171 
172  /// Create a position describing the returned value of \p F.
173  static const IRPosition returned(const Function &F) {
174  return IRPosition(const_cast<Function &>(F), IRP_RETURNED);
175  }
176 
177  /// Create a position describing the argument \p Arg.
178  static const IRPosition argument(const Argument &Arg) {
179  return IRPosition(const_cast<Argument &>(Arg), Kind(Arg.getArgNo()));
180  }
181 
182  /// Create a position describing the function scope of \p CB.
183  static const IRPosition callsite_function(const CallBase &CB) {
184  return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE);
185  }
186 
187  /// Create a position describing the returned value of \p CB.
188  static const IRPosition callsite_returned(const CallBase &CB) {
189  return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE_RETURNED);
190  }
191 
192  /// Create a position describing the argument of \p CB at position \p ArgNo.
193  static const IRPosition callsite_argument(const CallBase &CB,
194  unsigned ArgNo) {
195  return IRPosition(const_cast<CallBase &>(CB), Kind(ArgNo));
196  }
197 
198  /// Create a position describing the function scope of \p ICS.
200  return IRPosition::callsite_function(cast<CallBase>(*ICS.getInstruction()));
201  }
202 
203  /// Create a position describing the returned value of \p ICS.
205  return IRPosition::callsite_returned(cast<CallBase>(*ICS.getInstruction()));
206  }
207 
208  /// Create a position describing the argument of \p ICS at position \p ArgNo.
210  unsigned ArgNo) {
211  return IRPosition::callsite_argument(cast<CallBase>(*ICS.getInstruction()),
212  ArgNo);
213  }
214 
215  /// Create a position with function scope matching the "context" of \p IRP.
216  /// If \p IRP is a call site (see isAnyCallSitePosition()) then the result
217  /// will be a call site position, otherwise the function position of the
218  /// associated function.
219  static const IRPosition function_scope(const IRPosition &IRP) {
220  if (IRP.isAnyCallSitePosition()) {
222  cast<CallBase>(IRP.getAnchorValue()));
223  }
226  }
227 
228  bool operator==(const IRPosition &RHS) const {
229  return (AnchorVal == RHS.AnchorVal) && (KindOrArgNo == RHS.KindOrArgNo);
230  }
231  bool operator!=(const IRPosition &RHS) const { return !(*this == RHS); }
232 
233  /// Return the value this abstract attribute is anchored with.
234  ///
235  /// The anchor value might not be the associated value if the latter is not
236  /// sufficient to determine where arguments will be manifested. This is, so
237  /// far, only the case for call site arguments as the value is not sufficient
238  /// to pinpoint them. Instead, we can use the call site as an anchor.
239  ///
240  ///{
242  assert(KindOrArgNo != IRP_INVALID &&
243  "Invalid position does not have an anchor value!");
244  return *AnchorVal;
245  }
246  const Value &getAnchorValue() const {
247  return const_cast<IRPosition *>(this)->getAnchorValue();
248  }
249  ///}
250 
251  /// Return the associated function, if any.
252  ///
253  ///{
255  if (auto *CB = dyn_cast<CallBase>(AnchorVal))
256  return CB->getCalledFunction();
257  assert(KindOrArgNo != IRP_INVALID &&
258  "Invalid position does not have an anchor scope!");
259  Value &V = getAnchorValue();
260  if (isa<Function>(V))
261  return &cast<Function>(V);
262  if (isa<Argument>(V))
263  return cast<Argument>(V).getParent();
264  if (isa<Instruction>(V))
265  return cast<Instruction>(V).getFunction();
266  return nullptr;
267  }
269  return const_cast<IRPosition *>(this)->getAssociatedFunction();
270  }
271  ///}
272 
273  /// Return the associated argument, if any.
274  ///
275  ///{
277  if (auto *Arg = dyn_cast<Argument>(&getAnchorValue()))
278  return Arg;
279  int ArgNo = getArgNo();
280  if (ArgNo < 0)
281  return nullptr;
282  Function *AssociatedFn = getAssociatedFunction();
283  if (!AssociatedFn || AssociatedFn->arg_size() <= unsigned(ArgNo))
284  return nullptr;
285  return AssociatedFn->arg_begin() + ArgNo;
286  }
288  return const_cast<IRPosition *>(this)->getAssociatedArgument();
289  }
290  ///}
291 
292  /// Return true if the position refers to a function interface, that is the
293  /// function scope, the function return, or an argumnt.
294  bool isFnInterfaceKind() const {
295  switch (getPositionKind()) {
299  return true;
300  default:
301  return false;
302  }
303  }
304 
305  /// Return the Function surrounding the anchor value.
306  ///
307  ///{
309  Value &V = getAnchorValue();
310  if (isa<Function>(V))
311  return &cast<Function>(V);
312  if (isa<Argument>(V))
313  return cast<Argument>(V).getParent();
314  if (isa<Instruction>(V))
315  return cast<Instruction>(V).getFunction();
316  return nullptr;
317  }
318  const Function *getAnchorScope() const {
319  return const_cast<IRPosition *>(this)->getAnchorScope();
320  }
321  ///}
322 
323  /// Return the context instruction, if any.
324  ///
325  ///{
327  Value &V = getAnchorValue();
328  if (auto *I = dyn_cast<Instruction>(&V))
329  return I;
330  if (auto *Arg = dyn_cast<Argument>(&V))
331  if (!Arg->getParent()->isDeclaration())
332  return &Arg->getParent()->getEntryBlock().front();
333  if (auto *F = dyn_cast<Function>(&V))
334  if (!F->isDeclaration())
335  return &(F->getEntryBlock().front());
336  return nullptr;
337  }
338  const Instruction *getCtxI() const {
339  return const_cast<IRPosition *>(this)->getCtxI();
340  }
341  ///}
342 
343  /// Return the value this abstract attribute is associated with.
344  ///
345  ///{
347  assert(KindOrArgNo != IRP_INVALID &&
348  "Invalid position does not have an associated value!");
349  if (getArgNo() < 0 || isa<Argument>(AnchorVal))
350  return *AnchorVal;
351  assert(isa<CallBase>(AnchorVal) && "Expected a call base!");
352  return *cast<CallBase>(AnchorVal)->getArgOperand(getArgNo());
353  }
354  const Value &getAssociatedValue() const {
355  return const_cast<IRPosition *>(this)->getAssociatedValue();
356  }
357  ///}
358 
359  /// Return the argument number of the associated value if it is an argument or
360  /// call site argument, otherwise a negative value.
361  int getArgNo() const { return KindOrArgNo; }
362 
363  /// Return the index in the attribute list for this position.
364  unsigned getAttrIdx() const {
365  switch (getPositionKind()) {
368  break;
377  return KindOrArgNo + AttributeList::FirstArgIndex;
378  }
380  "There is no attribute index for a floating or invalid position!");
381  }
382 
383  /// Return the associated position kind.
385  if (getArgNo() >= 0) {
386  assert(((isa<Argument>(getAnchorValue()) &&
387  isa<Argument>(getAssociatedValue())) ||
388  isa<CallBase>(getAnchorValue())) &&
389  "Expected argument or call base due to argument number!");
390  if (isa<CallBase>(getAnchorValue()))
391  return IRP_CALL_SITE_ARGUMENT;
392  return IRP_ARGUMENT;
393  }
394 
395  assert(KindOrArgNo < 0 &&
396  "Expected (call site) arguments to never reach this point!");
397  assert(!isa<Argument>(getAnchorValue()) &&
398  "Expected arguments to have an associated argument position!");
399  return Kind(KindOrArgNo);
400  }
401 
402  /// TODO: Figure out if the attribute related helper functions should live
403  /// here or somewhere else.
404 
405  /// Return true if any kind in \p AKs existing in the IR at a position that
406  /// will affect this one. See also getAttrs(...).
407  bool hasAttr(ArrayRef<Attribute::AttrKind> AKs) const;
408 
409  /// Return the attributes of any kind in \p AKs existing in the IR at a
410  /// position that will affect this one. While each position can only have a
411  /// single attribute of any kind in \p AKs, there are "subsuming" positions
412  /// that could have an attribute as well. This method returns all attributes
413  /// found in \p Attrs.
414  void getAttrs(ArrayRef<Attribute::AttrKind> AKs,
416 
417  /// Return the attribute of kind \p AK existing in the IR at this position.
419  if (getPositionKind() == IRP_INVALID || getPositionKind() == IRP_FLOAT)
420  return Attribute();
421 
422  AttributeList AttrList;
423  if (ImmutableCallSite ICS = ImmutableCallSite(&getAnchorValue()))
424  AttrList = ICS.getAttributes();
425  else
426  AttrList = getAssociatedFunction()->getAttributes();
427 
428  if (AttrList.hasAttribute(getAttrIdx(), AK))
429  return AttrList.getAttribute(getAttrIdx(), AK);
430  return Attribute();
431  }
432 
433  bool isAnyCallSitePosition() const {
434  switch (getPositionKind()) {
438  return true;
439  default:
440  return false;
441  }
442  }
443 
444  /// Special DenseMap key values.
445  ///
446  ///{
447  static const IRPosition EmptyKey;
448  static const IRPosition TombstoneKey;
449  ///}
450 
451 private:
452  /// Private constructor for special values only!
453  explicit IRPosition(int KindOrArgNo)
454  : AnchorVal(0), KindOrArgNo(KindOrArgNo) {}
455 
456  /// IRPosition anchored at \p AnchorVal with kind/argument numbet \p PK.
457  explicit IRPosition(Value &AnchorVal, Kind PK)
458  : AnchorVal(&AnchorVal), KindOrArgNo(PK) {
459  verify();
460  }
461 
462  /// Verify internal invariants.
463  void verify();
464 
465  /// The value this position is anchored at.
466  Value *AnchorVal;
467 
468  /// The argument number, if non-negative, or the position "kind".
469  int KindOrArgNo;
470 };
471 
472 /// Helper that allows IRPosition as a key in a DenseMap.
473 template <> struct DenseMapInfo<IRPosition> {
474  static inline IRPosition getEmptyKey() { return IRPosition::EmptyKey; }
475  static inline IRPosition getTombstoneKey() {
477  }
478  static unsigned getHashValue(const IRPosition &IRP) {
480  (unsigned(IRP.getArgNo()));
481  }
482  static bool isEqual(const IRPosition &LHS, const IRPosition &RHS) {
483  return LHS == RHS;
484  }
485 };
486 
487 /// A visitor class for IR positions.
488 ///
489 /// Given a position P, the SubsumingPositionIterator allows to visit "subsuming
490 /// positions" wrt. attributes/information. Thus, if a piece of information
491 /// holds for a subsuming position, it also holds for the position P.
492 ///
493 /// The subsuming positions always include the initial position and then,
494 /// depending on the position kind, additionally the following ones:
495 /// - for IRP_RETURNED:
496 /// - the function (IRP_FUNCTION)
497 /// - for IRP_ARGUMENT:
498 /// - the function (IRP_FUNCTION)
499 /// - for IRP_CALL_SITE:
500 /// - the callee (IRP_FUNCTION), if known
501 /// - for IRP_CALL_SITE_RETURNED:
502 /// - the callee (IRP_RETURNED), if known
503 /// - the call site (IRP_FUNCTION)
504 /// - the callee (IRP_FUNCTION), if known
505 /// - for IRP_CALL_SITE_ARGUMENT:
506 /// - the argument of the callee (IRP_ARGUMENT), if known
507 /// - the callee (IRP_FUNCTION), if known
508 /// - the position the call site argument is associated with if it is not
509 /// anchored to the call site, e.g., if it is an arugment then the argument
510 /// (IRP_ARGUMENT)
512  SmallVector<IRPosition, 4> IRPositions;
513  using iterator = decltype(IRPositions)::iterator;
514 
515 public:
517  iterator begin() { return IRPositions.begin(); }
518  iterator end() { return IRPositions.end(); }
519 };
520 
521 /// Data structure to hold cached (LLVM-IR) information.
522 ///
523 /// All attributes are given an InformationCache object at creation time to
524 /// avoid inspection of the IR by all of them individually. This default
525 /// InformationCache will hold information required by 'default' attributes,
526 /// thus the ones deduced when Attributor::identifyDefaultAbstractAttributes(..)
527 /// is called.
528 ///
529 /// If custom abstract attributes, registered manually through
530 /// Attributor::registerAA(...), need more information, especially if it is not
531 /// reusable, it is advised to inherit from the InformationCache and cast the
532 /// instance down in the abstract attributes.
534  InformationCache(const DataLayout &DL) : DL(DL) {}
535 
536  /// A map type from opcodes to instructions with this opcode.
538 
539  /// Return the map that relates "interesting" opcodes with all instructions
540  /// with that opcode in \p F.
542  return FuncInstOpcodeMap[&F];
543  }
544 
545  /// A vector type to hold instructions.
546  using InstructionVectorTy = std::vector<Instruction *>;
547 
548  /// Return the instructions in \p F that may read or write memory.
550  return FuncRWInstsMap[&F];
551  }
552 
553 private:
554  /// A map type from functions to opcode to instruction maps.
556 
557  /// A map type from functions to their read or write instructions.
559 
560  /// A nested map that remembers all instructions in a function with a certain
561  /// instruction opcode (Instruction::getOpcode()).
562  FuncInstOpcodeMapTy FuncInstOpcodeMap;
563 
564  /// A map from functions to their instructions that may read or write memory.
565  FuncRWInstsMapTy FuncRWInstsMap;
566 
567  /// The datalayout used in the module.
568  const DataLayout &DL;
569 
570  /// Give the Attributor access to the members so
571  /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them.
572  friend struct Attributor;
573 };
574 
575 /// The fixpoint analysis framework that orchestrates the attribute deduction.
576 ///
577 /// The Attributor provides a general abstract analysis framework (guided
578 /// fixpoint iteration) as well as helper functions for the deduction of
579 /// (LLVM-IR) attributes. However, also other code properties can be deduced,
580 /// propagated, and ultimately manifested through the Attributor framework. This
581 /// is particularly useful if these properties interact with attributes and a
582 /// co-scheduled deduction allows to improve the solution. Even if not, thus if
583 /// attributes/properties are completely isolated, they should use the
584 /// Attributor framework to reduce the number of fixpoint iteration frameworks
585 /// in the code base. Note that the Attributor design makes sure that isolated
586 /// attributes are not impacted, in any way, by others derived at the same time
587 /// if there is no cross-reasoning performed.
588 ///
589 /// The public facing interface of the Attributor is kept simple and basically
590 /// allows abstract attributes to one thing, query abstract attributes
591 /// in-flight. There are two reasons to do this:
592 /// a) The optimistic state of one abstract attribute can justify an
593 /// optimistic state of another, allowing to framework to end up with an
594 /// optimistic (=best possible) fixpoint instead of one based solely on
595 /// information in the IR.
596 /// b) This avoids reimplementing various kinds of lookups, e.g., to check
597 /// for existing IR attributes, in favor of a single lookups interface
598 /// provided by an abstract attribute subclass.
599 ///
600 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
601 /// described in the file comment.
602 struct Attributor {
603  /// Constructor
604  ///
605  /// \param InfoCache Cache to hold various information accessible for
606  /// the abstract attributes.
607  /// \param DepRecomputeInterval Number of iterations until the dependences
608  /// between abstract attributes are recomputed.
609  /// \param Whitelist If not null, a set limiting the attribute opportunities.
610  Attributor(InformationCache &InfoCache, unsigned DepRecomputeInterval,
611  DenseSet<const char *> *Whitelist = nullptr)
612  : InfoCache(InfoCache), DepRecomputeInterval(DepRecomputeInterval),
613  Whitelist(Whitelist) {}
614 
615  ~Attributor() { DeleteContainerPointers(AllAbstractAttributes); }
616 
617  /// Run the analyses until a fixpoint is reached or enforced (timeout).
618  ///
619  /// The attributes registered with this Attributor can be used after as long
620  /// as the Attributor is not destroyed (it owns the attributes now).
621  ///
622  /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED.
623  ChangeStatus run(Module &M);
624 
625  /// Lookup an abstract attribute of type \p AAType at position \p IRP. While
626  /// no abstract attribute is found equivalent positions are checked, see
627  /// SubsumingPositionIterator. Thus, the returned abstract attribute
628  /// might be anchored at a different position, e.g., the callee if \p IRP is a
629  /// call base.
630  ///
631  /// This method is the only (supported) way an abstract attribute can retrieve
632  /// information from another abstract attribute. As an example, take an
633  /// abstract attribute that determines the memory access behavior for a
634  /// argument (readnone, readonly, ...). It should use `getAAFor` to get the
635  /// most optimistic information for other abstract attributes in-flight, e.g.
636  /// the one reasoning about the "captured" state for the argument or the one
637  /// reasoning on the memory access behavior of the function as a whole.
638  ///
639  /// If the flag \p TrackDependence is set to false the dependence from
640  /// \p QueryingAA to the return abstract attribute is not automatically
641  /// recorded. This should only be used if the caller will record the
642  /// dependence explicitly if necessary, thus if it the returned abstract
643  /// attribute is used for reasoning. To record the dependences explicitly use
644  /// the `Attributor::recordDependence` method.
645  template <typename AAType>
646  const AAType &getAAFor(const AbstractAttribute &QueryingAA,
647  const IRPosition &IRP, bool TrackDependence = true) {
648  return getOrCreateAAFor<AAType>(IRP, &QueryingAA, TrackDependence);
649  }
650 
651  /// Explicitly record a dependence from \p FromAA to \p ToAA, that is if
652  /// \p FromAA changes \p ToAA should be updated as well.
653  ///
654  /// This method should be used in conjunction with the `getAAFor` method and
655  /// with the TrackDependence flag passed to the method set to false. This can
656  /// be beneficial to avoid false dependences but it requires the users of
657  /// `getAAFor` to explicitly record true dependences through this method.
659  const AbstractAttribute &ToAA) {
660  QueryMap[&FromAA].insert(const_cast<AbstractAttribute *>(&ToAA));
661  }
662 
663  /// Introduce a new abstract attribute into the fixpoint analysis.
664  ///
665  /// Note that ownership of the attribute is given to the Attributor. It will
666  /// invoke delete for the Attributor on destruction of the Attributor.
667  ///
668  /// Attributes are identified by their IR position (AAType::getIRPosition())
669  /// and the address of their static member (see AAType::ID).
670  template <typename AAType> AAType &registerAA(AAType &AA) {
671  static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
672  "Cannot register an attribute with a type not derived from "
673  "'AbstractAttribute'!");
674  // Put the attribute in the lookup map structure and the container we use to
675  // keep track of all attributes.
676  IRPosition &IRP = AA.getIRPosition();
677  auto &KindToAbstractAttributeMap = AAMap[IRP];
679  "Attribute already in map!");
681  AllAbstractAttributes.push_back(&AA);
682  return AA;
683  }
684 
685  /// Return the internal information cache.
686  InformationCache &getInfoCache() { return InfoCache; }
687 
688  /// Determine opportunities to derive 'default' attributes in \p F and create
689  /// abstract attribute objects for them.
690  ///
691  /// \param F The function that is checked for attribute opportunities.
692  ///
693  /// Note that abstract attribute instances are generally created even if the
694  /// IR already contains the information they would deduce. The most important
695  /// reason for this is the single interface, the one of the abstract attribute
696  /// instance, which can be queried without the need to look at the IR in
697  /// various places.
698  void identifyDefaultAbstractAttributes(Function &F);
699 
700  /// Mark the internal function \p F as live.
701  ///
702  /// This will trigger the identification and initialization of attributes for
703  /// \p F.
706  "Only internal linkage is assumed dead initially.");
707  identifyDefaultAbstractAttributes(const_cast<Function &>(F));
708  }
709 
710  /// Record that \p I is deleted after information was manifested.
711  void deleteAfterManifest(Instruction &I) { ToBeDeletedInsts.insert(&I); }
712 
713  /// Record that \p BB is deleted after information was manifested.
714  void deleteAfterManifest(BasicBlock &BB) { ToBeDeletedBlocks.insert(&BB); }
715 
716  /// Record that \p F is deleted after information was manifested.
717  void deleteAfterManifest(Function &F) { ToBeDeletedFunctions.insert(&F); }
718 
719  /// Return true if \p AA (or its context instruction) is assumed dead.
720  ///
721  /// If \p LivenessAA is not provided it is queried.
722  bool isAssumedDead(const AbstractAttribute &AA, const AAIsDead *LivenessAA);
723 
724  /// Check \p Pred on all function call sites.
725  ///
726  /// This method will evaluate \p Pred on call sites and return
727  /// true if \p Pred holds in every call sites. However, this is only possible
728  /// all call sites are known, hence the function has internal linkage.
729  bool checkForAllCallSites(const function_ref<bool(CallSite)> &Pred,
730  const AbstractAttribute &QueryingAA,
731  bool RequireAllCallSites);
732 
733  /// Check \p Pred on all values potentially returned by \p F.
734  ///
735  /// This method will evaluate \p Pred on all values potentially returned by
736  /// the function associated with \p QueryingAA. The returned values are
737  /// matched with their respective return instructions. Returns true if \p Pred
738  /// holds on all of them.
739  bool checkForAllReturnedValuesAndReturnInsts(
740  const function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)>
741  &Pred,
742  const AbstractAttribute &QueryingAA);
743 
744  /// Check \p Pred on all values potentially returned by the function
745  /// associated with \p QueryingAA.
746  ///
747  /// This is the context insensitive version of the method above.
748  bool checkForAllReturnedValues(const function_ref<bool(Value &)> &Pred,
749  const AbstractAttribute &QueryingAA);
750 
751  /// Check \p Pred on all instructions with an opcode present in \p Opcodes.
752  ///
753  /// This method will evaluate \p Pred on all instructions with an opcode
754  /// present in \p Opcode and return true if \p Pred holds on all of them.
755  bool checkForAllInstructions(const function_ref<bool(Instruction &)> &Pred,
756  const AbstractAttribute &QueryingAA,
757  const ArrayRef<unsigned> &Opcodes);
758 
759  /// Check \p Pred on all call-like instructions (=CallBased derived).
760  ///
761  /// See checkForAllCallLikeInstructions(...) for more information.
762  bool
764  const AbstractAttribute &QueryingAA) {
765  return checkForAllInstructions(Pred, QueryingAA,
766  {(unsigned)Instruction::Invoke,
767  (unsigned)Instruction::CallBr,
769  }
770 
771  /// Check \p Pred on all Read/Write instructions.
772  ///
773  /// This method will evaluate \p Pred on all instructions that read or write
774  /// to memory present in the information cache and return true if \p Pred
775  /// holds on all of them.
776  bool checkForAllReadWriteInstructions(
777  const llvm::function_ref<bool(Instruction &)> &Pred,
778  AbstractAttribute &QueryingAA);
779 
780  /// Return the data layout associated with the anchor scope.
781  const DataLayout &getDataLayout() const { return InfoCache.DL; }
782 
783 private:
784 
785  /// The private version of getAAFor that allows to omit a querying abstract
786  /// attribute. See also the public getAAFor method.
787  template <typename AAType>
788  const AAType &getOrCreateAAFor(const IRPosition &IRP,
789  const AbstractAttribute *QueryingAA = nullptr,
790  bool TrackDependence = false) {
791  if (const AAType *AAPtr =
792  lookupAAFor<AAType>(IRP, QueryingAA, TrackDependence))
793  return *AAPtr;
794 
795  // No matching attribute found, create one.
796  // Use the static create method.
797  auto &AA = AAType::createForPosition(IRP, *this);
798  registerAA(AA);
799  AA.initialize(*this);
800 
801  // Bootstrap the new attribute with an initial update to propagate
802  // information, e.g., function -> call site. If it is not on a given
803  // whitelist we will not perform updates at all.
804  if (Whitelist && !Whitelist->count(&AAType::ID))
806  else
807  AA.update(*this);
808 
809  if (TrackDependence && AA.getState().isValidState())
810  QueryMap[&AA].insert(const_cast<AbstractAttribute *>(QueryingAA));
811  return AA;
812  }
813 
814  /// Return the attribute of \p AAType for \p IRP if existing.
815  template <typename AAType>
816  const AAType *lookupAAFor(const IRPosition &IRP,
817  const AbstractAttribute *QueryingAA = nullptr,
818  bool TrackDependence = false) {
819  static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
820  "Cannot query an attribute with a type not derived from "
821  "'AbstractAttribute'!");
822  assert((QueryingAA || !TrackDependence) &&
823  "Cannot track dependences without a QueryingAA!");
824 
825  // Lookup the abstract attribute of type AAType. If found, return it after
826  // registering a dependence of QueryingAA on the one returned attribute.
827  const auto &KindToAbstractAttributeMap = AAMap.lookup(IRP);
828  if (AAType *AA = static_cast<AAType *>(
830  // Do not register a dependence on an attribute with an invalid state.
831  if (TrackDependence && AA->getState().isValidState())
832  QueryMap[AA].insert(const_cast<AbstractAttribute *>(QueryingAA));
833  return AA;
834  }
835  return nullptr;
836  }
837 
838  /// The set of all abstract attributes.
839  ///{
841  AAVector AllAbstractAttributes;
842  ///}
843 
844  /// A nested map to lookup abstract attributes based on the argument position
845  /// on the outer level, and the addresses of the static member (AAType::ID) on
846  /// the inner level.
847  ///{
851  ///}
852 
853  /// A map from abstract attributes to the ones that queried them through calls
854  /// to the getAAFor<...>(...) method.
855  ///{
856  using QueryMapTy =
858  QueryMapTy QueryMap;
859  ///}
860 
861  /// The information cache that holds pre-processed (LLVM-IR) information.
862  InformationCache &InfoCache;
863 
864  /// Number of iterations until the dependences between abstract attributes are
865  /// recomputed.
866  const unsigned DepRecomputeInterval;
867 
868  /// If not null, a set limiting the attribute opportunities.
869  const DenseSet<const char *> *Whitelist;
870 
871  /// A set to remember the functions we already assume to be live and visited.
872  DenseSet<const Function *> VisitedFunctions;
873 
874  /// Functions, blocks, and instructions we delete after manifest is done.
875  ///
876  ///{
877  SmallPtrSet<Function *, 8> ToBeDeletedFunctions;
878  SmallPtrSet<BasicBlock *, 8> ToBeDeletedBlocks;
879  SmallPtrSet<Instruction *, 8> ToBeDeletedInsts;
880  ///}
881 };
882 
883 /// An interface to query the internal state of an abstract attribute.
884 ///
885 /// The abstract state is a minimal interface that allows the Attributor to
886 /// communicate with the abstract attributes about their internal state without
887 /// enforcing or exposing implementation details, e.g., the (existence of an)
888 /// underlying lattice.
889 ///
890 /// It is sufficient to be able to query if a state is (1) valid or invalid, (2)
891 /// at a fixpoint, and to indicate to the state that (3) an optimistic fixpoint
892 /// was reached or (4) a pessimistic fixpoint was enforced.
893 ///
894 /// All methods need to be implemented by the subclass. For the common use case,
895 /// a single boolean state or a bit-encoded state, the BooleanState and
896 /// IntegerState classes are already provided. An abstract attribute can inherit
897 /// from them to get the abstract state interface and additional methods to
898 /// directly modify the state based if needed. See the class comments for help.
900  virtual ~AbstractState() {}
901 
902  /// Return if this abstract state is in a valid state. If false, no
903  /// information provided should be used.
904  virtual bool isValidState() const = 0;
905 
906  /// Return if this abstract state is fixed, thus does not need to be updated
907  /// if information changes as it cannot change itself.
908  virtual bool isAtFixpoint() const = 0;
909 
910  /// Indicate that the abstract state should converge to the optimistic state.
911  ///
912  /// This will usually make the optimistically assumed state the known to be
913  /// true state.
914  ///
915  /// \returns ChangeStatus::UNCHANGED as the assumed value should not change.
916  virtual ChangeStatus indicateOptimisticFixpoint() = 0;
917 
918  /// Indicate that the abstract state should converge to the pessimistic state.
919  ///
920  /// This will usually revert the optimistically assumed state to the known to
921  /// be true state.
922  ///
923  /// \returns ChangeStatus::CHANGED as the assumed value may change.
924  virtual ChangeStatus indicatePessimisticFixpoint() = 0;
925 };
926 
927 /// Simple state with integers encoding.
928 ///
929 /// The interface ensures that the assumed bits are always a subset of the known
930 /// bits. Users can only add known bits and, except through adding known bits,
931 /// they can only remove assumed bits. This should guarantee monotoniticy and
932 /// thereby the existence of a fixpoint (if used corretly). The fixpoint is
933 /// reached when the assumed and known state/bits are equal. Users can
934 /// force/inidicate a fixpoint. If an optimistic one is indicated, the known
935 /// state will catch up with the assumed one, for a pessimistic fixpoint it is
936 /// the other way around.
937 struct IntegerState : public AbstractState {
938  /// Underlying integer type, we assume 32 bits to be enough.
939  using base_t = uint32_t;
940 
941  /// Initialize the (best) state.
942  IntegerState(base_t BestState = ~0) : Assumed(BestState) {}
943 
944  /// Return the worst possible representable state.
945  static constexpr base_t getWorstState() { return 0; }
946 
947  /// See AbstractState::isValidState()
948  /// NOTE: For now we simply pretend that the worst possible state is invalid.
949  bool isValidState() const override { return Assumed != getWorstState(); }
950 
951  /// See AbstractState::isAtFixpoint()
952  bool isAtFixpoint() const override { return Assumed == Known; }
953 
954  /// See AbstractState::indicateOptimisticFixpoint(...)
956  Known = Assumed;
958  }
959 
960  /// See AbstractState::indicatePessimisticFixpoint(...)
962  Assumed = Known;
963  return ChangeStatus::CHANGED;
964  }
965 
966  /// Return the known state encoding
967  base_t getKnown() const { return Known; }
968 
969  /// Return the assumed state encoding.
970  base_t getAssumed() const { return Assumed; }
971 
972  /// Return true if the bits set in \p BitsEncoding are "known bits".
973  bool isKnown(base_t BitsEncoding) const {
974  return (Known & BitsEncoding) == BitsEncoding;
975  }
976 
977  /// Return true if the bits set in \p BitsEncoding are "assumed bits".
978  bool isAssumed(base_t BitsEncoding) const {
979  return (Assumed & BitsEncoding) == BitsEncoding;
980  }
981 
982  /// Add the bits in \p BitsEncoding to the "known bits".
984  // Make sure we never miss any "known bits".
985  Assumed |= Bits;
986  Known |= Bits;
987  return *this;
988  }
989 
990  /// Remove the bits in \p BitsEncoding from the "assumed bits" if not known.
992  // Make sure we never loose any "known bits".
993  Assumed = (Assumed & ~BitsEncoding) | Known;
994  return *this;
995  }
996 
997  /// Keep only "assumed bits" also set in \p BitsEncoding but all known ones.
999  // Make sure we never loose any "known bits".
1000  Assumed = (Assumed & BitsEncoding) | Known;
1001  return *this;
1002  }
1003 
1004  /// Take minimum of assumed and \p Value.
1006  // Make sure we never loose "known value".
1007  Assumed = std::max(std::min(Assumed, Value), Known);
1008  return *this;
1009  }
1010 
1011  /// Take maximum of known and \p Value.
1013  // Make sure we never loose "known value".
1014  Assumed = std::max(Value, Assumed);
1015  Known = std::max(Value, Known);
1016  return *this;
1017  }
1018 
1019  /// Equality for IntegerState.
1020  bool operator==(const IntegerState &R) const {
1021  return this->getAssumed() == R.getAssumed() &&
1022  this->getKnown() == R.getKnown();
1023  }
1024 
1025  /// Inequality for IntegerState.
1026  bool operator!=(const IntegerState &R) const { return !(*this == R); }
1027 
1028  /// "Clamp" this state with \p R. The result is the minimum of the assumed
1029  /// information but not less than what was known before.
1030  ///
1031  /// TODO: Consider replacing the operator with a call or using it only when
1032  /// we can also take the maximum of the known information, thus when
1033  /// \p R is not dependent on additional assumed state.
1035  takeAssumedMinimum(R.Assumed);
1036  return *this;
1037  }
1038 
1039  /// "Clamp" this state with \p R. The result is the maximum of the known
1040  /// information but not more than what was assumed before.
1042  takeKnownMaximum(R.Known);
1043  return *this;
1044  }
1045 
1046  /// Make this the minimum, known and assumed, of this state and \p R.
1048  Known = std::min(Known, R.Known);
1049  Assumed = std::min(Assumed, R.Assumed);
1050  return *this;
1051  }
1052 
1053  /// Make this the maximum, known and assumed, of this state and \p R.
1055  Known = std::max(Known, R.Known);
1056  Assumed = std::max(Assumed, R.Assumed);
1057  return *this;
1058  }
1059 
1060 private:
1061  /// The known state encoding in an integer of type base_t.
1062  base_t Known = getWorstState();
1063 
1064  /// The assumed state encoding in an integer of type base_t.
1065  base_t Assumed;
1066 };
1067 
1068 /// Simple wrapper for a single bit (boolean) state.
1069 struct BooleanState : public IntegerState {
1071 };
1072 
1073 /// Helper struct necessary as the modular build fails if the virtual method
1074 /// IRAttribute::manifest is defined in the Attributor.cpp.
1076  static ChangeStatus manifestAttrs(Attributor &A, IRPosition &IRP,
1077  const ArrayRef<Attribute> &DeducedAttrs);
1078 };
1079 
1080 /// Helper to tie a abstract state implementation to an abstract attribute.
1081 template <typename StateTy, typename Base>
1082 struct StateWrapper : public StateTy, public Base {
1083  /// Provide static access to the type of the state.
1085 
1086  /// See AbstractAttribute::getState(...).
1087  StateType &getState() override { return *this; }
1088 
1089  /// See AbstractAttribute::getState(...).
1090  const AbstractState &getState() const override { return *this; }
1091 };
1092 
1093 /// Helper class that provides common functionality to manifest IR attributes.
1094 template <Attribute::AttrKind AK, typename Base>
1095 struct IRAttribute : public IRPosition, public Base {
1096  IRAttribute(const IRPosition &IRP) : IRPosition(IRP) {}
1098 
1099  /// See AbstractAttribute::initialize(...).
1100  virtual void initialize(Attributor &A) override {
1101  if (hasAttr(getAttrKind())) {
1102  this->getState().indicateOptimisticFixpoint();
1103  return;
1104  }
1105 
1106  const IRPosition &IRP = this->getIRPosition();
1107  bool IsFnInterface = IRP.isFnInterfaceKind();
1108  const Function *FnScope = IRP.getAnchorScope();
1109  // TODO: Not all attributes require an exact definition. Find a way to
1110  // enable deduction for some but not all attributes in case the
1111  // definition might be changed at runtime, see also
1112  // http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
1113  // TODO: We could always determine abstract attributes and if sufficient
1114  // information was found we could duplicate the functions that do not
1115  // have an exact definition.
1116  if (IsFnInterface && (!FnScope || !FnScope->hasExactDefinition()))
1117  this->getState().indicatePessimisticFixpoint();
1118  }
1119 
1120  /// See AbstractAttribute::manifest(...).
1122  SmallVector<Attribute, 4> DeducedAttrs;
1123  getDeducedAttributes(getAnchorValue().getContext(), DeducedAttrs);
1124  return IRAttributeManifest::manifestAttrs(A, getIRPosition(), DeducedAttrs);
1125  }
1126 
1127  /// Return the kind that identifies the abstract attribute implementation.
1128  Attribute::AttrKind getAttrKind() const { return AK; }
1129 
1130  /// Return the deduced attributes in \p Attrs.
1133  Attrs.emplace_back(Attribute::get(Ctx, getAttrKind()));
1134  }
1135 
1136  /// Return an IR position, see struct IRPosition.
1137  ///
1138  ///{
1139  IRPosition &getIRPosition() override { return *this; }
1140  const IRPosition &getIRPosition() const override { return *this; }
1141  ///}
1142 };
1143 
1144 /// Base struct for all "concrete attribute" deductions.
1145 ///
1146 /// The abstract attribute is a minimal interface that allows the Attributor to
1147 /// orchestrate the abstract/fixpoint analysis. The design allows to hide away
1148 /// implementation choices made for the subclasses but also to structure their
1149 /// implementation and simplify the use of other abstract attributes in-flight.
1150 ///
1151 /// To allow easy creation of new attributes, most methods have default
1152 /// implementations. The ones that do not are generally straight forward, except
1153 /// `AbstractAttribute::updateImpl` which is the location of most reasoning
1154 /// associated with the abstract attribute. The update is invoked by the
1155 /// Attributor in case the situation used to justify the current optimistic
1156 /// state might have changed. The Attributor determines this automatically
1157 /// by monitoring the `Attributor::getAAFor` calls made by abstract attributes.
1158 ///
1159 /// The `updateImpl` method should inspect the IR and other abstract attributes
1160 /// in-flight to justify the best possible (=optimistic) state. The actual
1161 /// implementation is, similar to the underlying abstract state encoding, not
1162 /// exposed. In the most common case, the `updateImpl` will go through a list of
1163 /// reasons why its optimistic state is valid given the current information. If
1164 /// any combination of them holds and is sufficient to justify the current
1165 /// optimistic state, the method shall return UNCHAGED. If not, the optimistic
1166 /// state is adjusted to the situation and the method shall return CHANGED.
1167 ///
1168 /// If the manifestation of the "concrete attribute" deduced by the subclass
1169 /// differs from the "default" behavior, which is a (set of) LLVM-IR
1170 /// attribute(s) for an argument, call site argument, function return value, or
1171 /// function, the `AbstractAttribute::manifest` method should be overloaded.
1172 ///
1173 /// NOTE: If the state obtained via getState() is INVALID, thus if
1174 /// AbstractAttribute::getState().isValidState() returns false, no
1175 /// information provided by the methods of this class should be used.
1176 /// NOTE: The Attributor currently has certain limitations to what we can do.
1177 /// As a general rule of thumb, "concrete" abstract attributes should *for
1178 /// now* only perform "backward" information propagation. That means
1179 /// optimistic information obtained through abstract attributes should
1180 /// only be used at positions that precede the origin of the information
1181 /// with regards to the program flow. More practically, information can
1182 /// *now* be propagated from instructions to their enclosing function, but
1183 /// *not* from call sites to the called function. The mechanisms to allow
1184 /// both directions will be added in the future.
1185 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
1186 /// described in the file comment.
1189 
1190  /// Virtual destructor.
1191  virtual ~AbstractAttribute() {}
1192 
1193  /// Initialize the state with the information in the Attributor \p A.
1194  ///
1195  /// This function is called by the Attributor once all abstract attributes
1196  /// have been identified. It can and shall be used for task like:
1197  /// - identify existing knowledge in the IR and use it for the "known state"
1198  /// - perform any work that is not going to change over time, e.g., determine
1199  /// a subset of the IR, or attributes in-flight, that have to be looked at
1200  /// in the `updateImpl` method.
1201  virtual void initialize(Attributor &A) {}
1202 
1203  /// Return the internal abstract state for inspection.
1204  virtual StateType &getState() = 0;
1205  virtual const StateType &getState() const = 0;
1206 
1207  /// Return an IR position, see struct IRPosition.
1208  virtual const IRPosition &getIRPosition() const = 0;
1209 
1210  /// Helper functions, for debug purposes only.
1211  ///{
1212  virtual void print(raw_ostream &OS) const;
1213  void dump() const { print(dbgs()); }
1214 
1215  /// This function should return the "summarized" assumed state as string.
1216  virtual const std::string getAsStr() const = 0;
1217  ///}
1218 
1219  /// Allow the Attributor access to the protected methods.
1220  friend struct Attributor;
1221 
1222 protected:
1223  /// Hook for the Attributor to trigger an update of the internal state.
1224  ///
1225  /// If this attribute is already fixed, this method will return UNCHANGED,
1226  /// otherwise it delegates to `AbstractAttribute::updateImpl`.
1227  ///
1228  /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
1229  ChangeStatus update(Attributor &A);
1230 
1231  /// Hook for the Attributor to trigger the manifestation of the information
1232  /// represented by the abstract attribute in the LLVM-IR.
1233  ///
1234  /// \Return CHANGED if the IR was altered, otherwise UNCHANGED.
1236  return ChangeStatus::UNCHANGED;
1237  }
1238 
1239  /// Hook to enable custom statistic tracking, called after manifest that
1240  /// resulted in a change if statistics are enabled.
1241  ///
1242  /// We require subclasses to provide an implementation so we remember to
1243  /// add statistics for them.
1244  virtual void trackStatistics() const = 0;
1245 
1246  /// Return an IR position, see struct IRPosition.
1247  virtual IRPosition &getIRPosition() = 0;
1248 
1249  /// The actual update/transfer function which has to be implemented by the
1250  /// derived classes.
1251  ///
1252  /// If it is called, the environment has changed and we have to determine if
1253  /// the current information is still valid or adjust it otherwise.
1254  ///
1255  /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
1256  virtual ChangeStatus updateImpl(Attributor &A) = 0;
1257 };
1258 
1259 /// Forward declarations of output streams for debug purposes.
1260 ///
1261 ///{
1266 raw_ostream &operator<<(raw_ostream &OS, const AbstractState &State);
1268 ///}
1269 
1270 struct AttributorPass : public PassInfoMixin<AttributorPass> {
1272 };
1273 
1275 
1276 /// ----------------------------------------------------------------------------
1277 /// Abstract Attribute Classes
1278 /// ----------------------------------------------------------------------------
1279 
1280 /// An abstract attribute for the returned values of a function.
1282  : public IRAttribute<Attribute::Returned, AbstractAttribute> {
1284 
1285  /// Return an assumed unique return value if a single candidate is found. If
1286  /// there cannot be one, return a nullptr. If it is not clear yet, return the
1287  /// Optional::NoneType.
1288  Optional<Value *> getAssumedUniqueReturnValue(Attributor &A) const;
1289 
1290  /// Check \p Pred on all returned values.
1291  ///
1292  /// This method will evaluate \p Pred on returned values and return
1293  /// true if (1) all returned values are known, and (2) \p Pred returned true
1294  /// for all returned values.
1295  ///
1296  /// Note: Unlike the Attributor::checkForAllReturnedValuesAndReturnInsts
1297  /// method, this one will not filter dead return instructions.
1298  virtual bool checkForAllReturnedValuesAndReturnInsts(
1299  const function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)>
1300  &Pred) const = 0;
1301 
1303  using const_iterator =
1305  virtual llvm::iterator_range<iterator> returned_values() = 0;
1306  virtual llvm::iterator_range<const_iterator> returned_values() const = 0;
1307 
1308  virtual size_t getNumReturnValues() const = 0;
1309  virtual const SmallSetVector<CallBase *, 4> &getUnresolvedCalls() const = 0;
1310 
1311  /// Create an abstract attribute view for the position \p IRP.
1312  static AAReturnedValues &createForPosition(const IRPosition &IRP,
1313  Attributor &A);
1314 
1315  /// Unique ID (due to the unique address)
1316  static const char ID;
1317 };
1318 
1320  : public IRAttribute<Attribute::NoUnwind,
1321  StateWrapper<BooleanState, AbstractAttribute>> {
1322  AANoUnwind(const IRPosition &IRP) : IRAttribute(IRP) {}
1323 
1324  /// Returns true if nounwind is assumed.
1325  bool isAssumedNoUnwind() const { return getAssumed(); }
1326 
1327  /// Returns true if nounwind is known.
1328  bool isKnownNoUnwind() const { return getKnown(); }
1329 
1330  /// Create an abstract attribute view for the position \p IRP.
1331  static AANoUnwind &createForPosition(const IRPosition &IRP, Attributor &A);
1332 
1333  /// Unique ID (due to the unique address)
1334  static const char ID;
1335 };
1336 
1337 struct AANoSync
1338  : public IRAttribute<Attribute::NoSync,
1339  StateWrapper<BooleanState, AbstractAttribute>> {
1340  AANoSync(const IRPosition &IRP) : IRAttribute(IRP) {}
1341 
1342  /// Returns true if "nosync" is assumed.
1343  bool isAssumedNoSync() const { return getAssumed(); }
1344 
1345  /// Returns true if "nosync" is known.
1346  bool isKnownNoSync() const { return getKnown(); }
1347 
1348  /// Create an abstract attribute view for the position \p IRP.
1349  static AANoSync &createForPosition(const IRPosition &IRP, Attributor &A);
1350 
1351  /// Unique ID (due to the unique address)
1352  static const char ID;
1353 };
1354 
1355 /// An abstract interface for all nonnull attributes.
1357  : public IRAttribute<Attribute::NonNull,
1358  StateWrapper<BooleanState, AbstractAttribute>> {
1359  AANonNull(const IRPosition &IRP) : IRAttribute(IRP) {}
1360 
1361  /// Return true if we assume that the underlying value is nonnull.
1362  bool isAssumedNonNull() const { return getAssumed(); }
1363 
1364  /// Return true if we know that underlying value is nonnull.
1365  bool isKnownNonNull() const { return getKnown(); }
1366 
1367  /// Create an abstract attribute view for the position \p IRP.
1368  static AANonNull &createForPosition(const IRPosition &IRP, Attributor &A);
1369 
1370  /// Unique ID (due to the unique address)
1371  static const char ID;
1372 };
1373 
1374 /// An abstract attribute for norecurse.
1376  : public IRAttribute<Attribute::NoRecurse,
1377  StateWrapper<BooleanState, AbstractAttribute>> {
1378  AANoRecurse(const IRPosition &IRP) : IRAttribute(IRP) {}
1379 
1380  /// Return true if "norecurse" is assumed.
1381  bool isAssumedNoRecurse() const { return getAssumed(); }
1382 
1383  /// Return true if "norecurse" is known.
1384  bool isKnownNoRecurse() const { return getKnown(); }
1385 
1386  /// Create an abstract attribute view for the position \p IRP.
1387  static AANoRecurse &createForPosition(const IRPosition &IRP, Attributor &A);
1388 
1389  /// Unique ID (due to the unique address)
1390  static const char ID;
1391 };
1392 
1393 /// An abstract attribute for willreturn.
1395  : public IRAttribute<Attribute::WillReturn,
1396  StateWrapper<BooleanState, AbstractAttribute>> {
1397  AAWillReturn(const IRPosition &IRP) : IRAttribute(IRP) {}
1398 
1399  /// Return true if "willreturn" is assumed.
1400  bool isAssumedWillReturn() const { return getAssumed(); }
1401 
1402  /// Return true if "willreturn" is known.
1403  bool isKnownWillReturn() const { return getKnown(); }
1404 
1405  /// Create an abstract attribute view for the position \p IRP.
1406  static AAWillReturn &createForPosition(const IRPosition &IRP, Attributor &A);
1407 
1408  /// Unique ID (due to the unique address)
1409  static const char ID;
1410 };
1411 
1412 /// An abstract interface for all noalias attributes.
1414  : public IRAttribute<Attribute::NoAlias,
1415  StateWrapper<BooleanState, AbstractAttribute>> {
1416  AANoAlias(const IRPosition &IRP) : IRAttribute(IRP) {}
1417 
1418  /// Return true if we assume that the underlying value is alias.
1419  bool isAssumedNoAlias() const { return getAssumed(); }
1420 
1421  /// Return true if we know that underlying value is noalias.
1422  bool isKnownNoAlias() const { return getKnown(); }
1423 
1424  /// Create an abstract attribute view for the position \p IRP.
1425  static AANoAlias &createForPosition(const IRPosition &IRP, Attributor &A);
1426 
1427  /// Unique ID (due to the unique address)
1428  static const char ID;
1429 };
1430 
1431 /// An AbstractAttribute for nofree.
1432 struct AANoFree
1433  : public IRAttribute<Attribute::NoFree,
1434  StateWrapper<BooleanState, AbstractAttribute>> {
1435  AANoFree(const IRPosition &IRP) : IRAttribute(IRP) {}
1436 
1437  /// Return true if "nofree" is assumed.
1438  bool isAssumedNoFree() const { return getAssumed(); }
1439 
1440  /// Return true if "nofree" is known.
1441  bool isKnownNoFree() const { return getKnown(); }
1442 
1443  /// Create an abstract attribute view for the position \p IRP.
1444  static AANoFree &createForPosition(const IRPosition &IRP, Attributor &A);
1445 
1446  /// Unique ID (due to the unique address)
1447  static const char ID;
1448 };
1449 
1450 /// An AbstractAttribute for noreturn.
1452  : public IRAttribute<Attribute::NoReturn,
1453  StateWrapper<BooleanState, AbstractAttribute>> {
1454  AANoReturn(const IRPosition &IRP) : IRAttribute(IRP) {}
1455 
1456  /// Return true if the underlying object is assumed to never return.
1457  bool isAssumedNoReturn() const { return getAssumed(); }
1458 
1459  /// Return true if the underlying object is known to never return.
1460  bool isKnownNoReturn() const { return getKnown(); }
1461 
1462  /// Create an abstract attribute view for the position \p IRP.
1463  static AANoReturn &createForPosition(const IRPosition &IRP, Attributor &A);
1464 
1465  /// Unique ID (due to the unique address)
1466  static const char ID;
1467 };
1468 
1469 /// An abstract interface for liveness abstract attribute.
1470 struct AAIsDead : public StateWrapper<BooleanState, AbstractAttribute>,
1471  public IRPosition {
1472  AAIsDead(const IRPosition &IRP) : IRPosition(IRP) {}
1473 
1474  /// Returns true if \p BB is assumed dead.
1475  virtual bool isAssumedDead(const BasicBlock *BB) const = 0;
1476 
1477  /// Returns true if \p BB is known dead.
1478  virtual bool isKnownDead(const BasicBlock *BB) const = 0;
1479 
1480  /// Returns true if \p I is assumed dead.
1481  virtual bool isAssumedDead(const Instruction *I) const = 0;
1482 
1483  /// Returns true if \p I is known dead.
1484  virtual bool isKnownDead(const Instruction *I) const = 0;
1485 
1486  /// This method is used to check if at least one instruction in a collection
1487  /// of instructions is live.
1488  template <typename T> bool isLiveInstSet(T begin, T end) const {
1489  for (const auto &I : llvm::make_range(begin, end)) {
1490  assert(I->getFunction() == getIRPosition().getAssociatedFunction() &&
1491  "Instruction must be in the same anchor scope function.");
1492 
1493  if (!isAssumedDead(I))
1494  return true;
1495  }
1496 
1497  return false;
1498  }
1499 
1500  /// Return an IR position, see struct IRPosition.
1501  ///
1502  ///{
1503  IRPosition &getIRPosition() override { return *this; }
1504  const IRPosition &getIRPosition() const override { return *this; }
1505  ///}
1506 
1507  /// Create an abstract attribute view for the position \p IRP.
1508  static AAIsDead &createForPosition(const IRPosition &IRP, Attributor &A);
1509 
1510  /// Unique ID (due to the unique address)
1511  static const char ID;
1512 };
1513 
1514 /// State for dereferenceable attribute
1516 
1517  /// State representing for dereferenceable bytes.
1519 
1520  /// State representing that whether the value is globaly dereferenceable.
1522 
1523  /// See AbstractState::isValidState()
1524  bool isValidState() const override { return DerefBytesState.isValidState(); }
1525 
1526  /// See AbstractState::isAtFixpoint()
1527  bool isAtFixpoint() const override {
1528  return !isValidState() ||
1529  (DerefBytesState.isAtFixpoint() && GlobalState.isAtFixpoint());
1530  }
1531 
1532  /// See AbstractState::indicateOptimisticFixpoint(...)
1534  DerefBytesState.indicateOptimisticFixpoint();
1535  GlobalState.indicateOptimisticFixpoint();
1536  return ChangeStatus::UNCHANGED;
1537  }
1538 
1539  /// See AbstractState::indicatePessimisticFixpoint(...)
1541  DerefBytesState.indicatePessimisticFixpoint();
1542  GlobalState.indicatePessimisticFixpoint();
1543  return ChangeStatus::CHANGED;
1544  }
1545 
1546  /// Update known dereferenceable bytes.
1547  void takeKnownDerefBytesMaximum(uint64_t Bytes) {
1548  DerefBytesState.takeKnownMaximum(Bytes);
1549  }
1550 
1551  /// Update assumed dereferenceable bytes.
1552  void takeAssumedDerefBytesMinimum(uint64_t Bytes) {
1553  DerefBytesState.takeAssumedMinimum(Bytes);
1554  }
1555 
1556  /// Equality for DerefState.
1557  bool operator==(const DerefState &R) {
1558  return this->DerefBytesState == R.DerefBytesState &&
1559  this->GlobalState == R.GlobalState;
1560  }
1561 
1562  /// Inequality for IntegerState.
1563  bool operator!=(const DerefState &R) { return !(*this == R); }
1564 
1565  /// See IntegerState::operator^=
1567  DerefBytesState ^= R.DerefBytesState;
1568  GlobalState ^= R.GlobalState;
1569  return *this;
1570  }
1571 
1572  /// See IntegerState::operator+=
1574  DerefBytesState += R.DerefBytesState;
1575  GlobalState += R.GlobalState;
1576  return *this;
1577  }
1578 
1579  /// See IntegerState::operator&=
1581  DerefBytesState &= R.DerefBytesState;
1582  GlobalState &= R.GlobalState;
1583  return *this;
1584  }
1585 
1586  /// See IntegerState::operator|=
1588  DerefBytesState |= R.DerefBytesState;
1589  GlobalState |= R.GlobalState;
1590  return *this;
1591  }
1592 
1593 protected:
1594  const AANonNull *NonNullAA = nullptr;
1595 };
1596 
1597 /// An abstract interface for all dereferenceable attribute.
1599  : public IRAttribute<Attribute::Dereferenceable,
1600  StateWrapper<DerefState, AbstractAttribute>> {
1602 
1603  /// Return true if we assume that the underlying value is nonnull.
1604  bool isAssumedNonNull() const {
1605  return NonNullAA && NonNullAA->isAssumedNonNull();
1606  }
1607 
1608  /// Return true if we assume that underlying value is
1609  /// dereferenceable(_or_null) globally.
1610  bool isAssumedGlobal() const { return GlobalState.getAssumed(); }
1611 
1612  /// Return true if we know that underlying value is
1613  /// dereferenceable(_or_null) globally.
1614  bool isKnownGlobal() const { return GlobalState.getKnown(); }
1615 
1616  /// Return assumed dereferenceable bytes.
1618  return DerefBytesState.getAssumed();
1619  }
1620 
1621  /// Return known dereferenceable bytes.
1623  return DerefBytesState.getKnown();
1624  }
1625 
1626  /// Create an abstract attribute view for the position \p IRP.
1627  static AADereferenceable &createForPosition(const IRPosition &IRP,
1628  Attributor &A);
1629 
1630  /// Unique ID (due to the unique address)
1631  static const char ID;
1632 };
1633 
1634 /// An abstract interface for all align attributes.
1635 struct AAAlign
1636  : public IRAttribute<Attribute::Alignment,
1637  StateWrapper<IntegerState, AbstractAttribute>> {
1638  AAAlign(const IRPosition &IRP) : IRAttribute(IRP) {}
1639 
1640  /// Return assumed alignment.
1641  unsigned getAssumedAlign() const { return getAssumed(); }
1642 
1643  /// Return known alignemnt.
1644  unsigned getKnownAlign() const { return getKnown(); }
1645 
1646  /// Create an abstract attribute view for the position \p IRP.
1647  static AAAlign &createForPosition(const IRPosition &IRP, Attributor &A);
1648 
1649  /// Unique ID (due to the unique address)
1650  static const char ID;
1651 };
1652 
1653 /// An abstract interface for all nocapture attributes.
1655  : public IRAttribute<Attribute::NoCapture,
1656  StateWrapper<IntegerState, AbstractAttribute>> {
1657  AANoCapture(const IRPosition &IRP) : IRAttribute(IRP) {}
1658 
1659  /// State encoding bits. A set bit in the state means the property holds.
1660  /// NO_CAPTURE is the best possible state, 0 the worst possible state.
1661  enum {
1662  NOT_CAPTURED_IN_MEM = 1 << 0,
1663  NOT_CAPTURED_IN_INT = 1 << 1,
1664  NOT_CAPTURED_IN_RET = 1 << 2,
1665 
1666  /// If we do not capture the value in memory or through integers we can only
1667  /// communicate it back as a derived pointer.
1668  NO_CAPTURE_MAYBE_RETURNED = NOT_CAPTURED_IN_MEM | NOT_CAPTURED_IN_INT,
1669 
1670  /// If we do not capture the value in memory, through integers, or as a
1671  /// derived pointer we know it is not captured.
1672  NO_CAPTURE =
1673  NOT_CAPTURED_IN_MEM | NOT_CAPTURED_IN_INT | NOT_CAPTURED_IN_RET,
1674  };
1675 
1676  /// Return true if we know that the underlying value is not captured in its
1677  /// respective scope.
1678  bool isKnownNoCapture() const { return isKnown(NO_CAPTURE); }
1679 
1680  /// Return true if we assume that the underlying value is not captured in its
1681  /// respective scope.
1682  bool isAssumedNoCapture() const { return isAssumed(NO_CAPTURE); }
1683 
1684  /// Return true if we know that the underlying value is not captured in its
1685  /// respective scope but we allow it to escape through a "return".
1687  return isKnown(NO_CAPTURE_MAYBE_RETURNED);
1688  }
1689 
1690  /// Return true if we assume that the underlying value is not captured in its
1691  /// respective scope but we allow it to escape through a "return".
1693  return isAssumed(NO_CAPTURE_MAYBE_RETURNED);
1694  }
1695 
1696  /// Create an abstract attribute view for the position \p IRP.
1697  static AANoCapture &createForPosition(const IRPosition &IRP, Attributor &A);
1698 
1699  /// Unique ID (due to the unique address)
1700  static const char ID;
1701 };
1702 
1703 /// An abstract interface for value simplify abstract attribute.
1704 struct AAValueSimplify : public StateWrapper<BooleanState, AbstractAttribute>,
1705  public IRPosition {
1706  AAValueSimplify(const IRPosition &IRP) : IRPosition(IRP) {}
1707 
1708  /// Return an IR position, see struct IRPosition.
1709  ///
1710  ///{
1711  IRPosition &getIRPosition() { return *this; }
1712  const IRPosition &getIRPosition() const { return *this; }
1713  ///}
1714 
1715  /// Return an assumed simplified value if a single candidate is found. If
1716  /// there cannot be one, return original value. If it is not clear yet, return
1717  /// the Optional::NoneType.
1718  virtual Optional<Value *> getAssumedSimplifiedValue(Attributor &A) const = 0;
1719 
1720  /// Create an abstract attribute view for the position \p IRP.
1721  static AAValueSimplify &createForPosition(const IRPosition &IRP,
1722  Attributor &A);
1723 
1724  /// Unique ID (due to the unique address)
1725  static const char ID;
1726 };
1727 
1728 } // end namespace llvm
1729 
1730 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H
An attribute for a call site return value.
Definition: Attributor.h:146
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
ChangeStatus indicateOptimisticFixpoint() override
See AbstractState::indicateOptimisticFixpoint(...)
Definition: Attributor.h:955
OpcodeInstMapTy & getOpcodeInstMapForFunction(const Function &F)
Return the map that relates "interesting" opcodes with all instructions with that opcode in F...
Definition: Attributor.h:541
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1725
void DeleteContainerPointers(Container &C)
For a container of pointers, deletes the pointers and then clears the container.
Definition: STLExtras.h:1128
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
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:1552
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:1686
static IRPosition getEmptyKey()
Definition: Attributor.h:474
uint32_t getKnownDereferenceableBytes() const
Return known dereferenceable bytes.
Definition: Attributor.h:1622
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
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:301
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool isAssumedNoSync() const
Returns true if "nosync" is assumed.
Definition: Attributor.h:1343
const Function * getAnchorScope() const
Definition: Attributor.h:318
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
ChangeStatus
Simple enum class that forces the status to be spelled out explicitly.
Definition: Attributor.h:115
static IRPosition getTombstoneKey()
Definition: Attributor.h:475
IRPosition & getIRPosition() override
Return an IR position, see struct IRPosition.
Definition: Attributor.h:1139
InformationCache(const DataLayout &DL)
Definition: Attributor.h:534
A position that is not associated with a spot suitable for attributes.
Definition: Attributor.h:143
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
IntegerState DerefBytesState
State representing for dereferenceable bytes.
Definition: Attributor.h:1518
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1447
bool isAnyCallSitePosition() const
Definition: Attributor.h:433
AANoAlias(const IRPosition &IRP)
Definition: Attributor.h:1416
An abstract interface for all nocapture attributes.
Definition: Attributor.h:1654
Abstract Attribute Classes
Definition: Attributor.h:1281
virtual ~AbstractState()
Definition: Attributor.h:900
Helper struct necessary as the modular build fails if the virtual method IRAttribute::manifest is def...
Definition: Attributor.h:1075
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:970
An attribute for a call site argument.
Definition: Attributor.h:150
bool isAssumedNoReturn() const
Return true if the underlying object is assumed to never return.
Definition: Attributor.h:1457
IntegerState & takeAssumedMinimum(base_t Value)
Take minimum of assumed and Value.
Definition: Attributor.h:1005
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:1381
An abstract attribute for willreturn.
Definition: Attributor.h:1394
APInt operator &(APInt a, const APInt &b)
Definition: APInt.h:1985
Value & getAssociatedValue()
}
Definition: Attributor.h:346
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
F(f)
bool isValidState() const override
See AbstractState::isValidState() NOTE: For now we simply pretend that the worst possible state is in...
Definition: Attributor.h:949
MapVector< Value *, SmallSetVector< ReturnInst *, 4 > >::const_iterator const_iterator
Definition: Attributor.h:1304
const Argument * getAssociatedArgument() const
Definition: Attributor.h:287
unsigned getKnownAlign() const
Return known alignemnt.
Definition: Attributor.h:1644
Helper to tie a abstract state implementation to an abstract attribute.
Definition: Attributor.h:1082
Kind
The positions we distinguish in the IR.
Definition: Attributor.h:141
bool operator==(const IntegerState &R) const
Equality for IntegerState.
Definition: Attributor.h:1020
AANoReturn(const IRPosition &IRP)
Definition: Attributor.h:1454
IntegerState operator|=(const IntegerState &R)
Make this the maximum, known and assumed, of this state and R.
Definition: Attributor.h:1054
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:1034
bool hasAttribute(unsigned Index, Attribute::AttrKind Kind) const
Return true if the attribute exists at the given index.
Instruction * getCtxI()
}
Definition: Attributor.h:326
const Value & getAnchorValue() const
Definition: Attributor.h:246
AAAlign(const IRPosition &IRP)
Definition: Attributor.h:1638
static const IRPosition function_scope(const IRPosition &IRP)
Create a position with function scope matching the "context" of IRP.
Definition: Attributor.h:219
An AbstractAttribute for noreturn.
Definition: Attributor.h:1451
A visitor class for IR positions.
Definition: Attributor.h:511
bool isKnownNoReturn() const
Return true if the underlying object is known to never return.
Definition: Attributor.h:1460
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1650
const IRPosition & getIRPosition() const
Return an IR position, see struct IRPosition.
Definition: Attributor.h:1712
std::vector< Instruction * > InstructionVectorTy
A vector type to hold instructions.
Definition: Attributor.h:546
bool isAssumedNoAlias() const
Return true if we assume that the underlying value is alias.
Definition: Attributor.h:1419
bool isKnown(base_t BitsEncoding) const
Return true if the bits set in BitsEncoding are "known bits".
Definition: Attributor.h:973
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:1375
bool isAssumedNoUnwind() const
Returns true if nounwind is assumed.
Definition: Attributor.h:1325
virtual ~IRPosition()
Definition: Attributor.h:134
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1390
An abstract interface for all noalias attributes.
Definition: Attributor.h:1413
An attribute for the function return value.
Definition: Attributor.h:145
void takeKnownDerefBytesMaximum(uint64_t Bytes)
Update known dereferenceable bytes.
Definition: Attributor.h:1547
InstrTy * getInstruction() const
Definition: CallSite.h:96
uint32_t getAssumedDereferenceableBytes() const
Return assumed dereferenceable bytes.
Definition: Attributor.h:1617
ChangeStatus indicatePessimisticFixpoint() override
See AbstractState::indicatePessimisticFixpoint(...)
Definition: Attributor.h:961
InstructionVectorTy & getReadOrWriteInstsForFunction(const Function &F)
Return the instructions in F that may read or write memory.
Definition: Attributor.h:549
int getArgNo() const
}
Definition: Attributor.h:361
Attribute getAttr(Attribute::AttrKind AK) const
Return the attribute of kind AK existing in the IR at this position.
Definition: Attributor.h:418
bool operator==(const IRPosition &RHS) const
Definition: Attributor.h:228
AANoCapture(const IRPosition &IRP)
Definition: Attributor.h:1657
An abstract interface for liveness abstract attribute.
Definition: Attributor.h:1470
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:1438
AAWillReturn(const IRPosition &IRP)
Definition: Attributor.h:1397
static const IRPosition callsite_returned(ImmutableCallSite ICS)
Create a position describing the returned value of ICS.
Definition: Attributor.h:204
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
bool operator!=(const IRPosition &RHS) const
Definition: Attributor.h:231
bool isKnownNoUnwind() const
Returns true if nounwind is known.
Definition: Attributor.h:1328
An abstract interface for all nonnull attributes.
Definition: Attributor.h:1356
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:942
ChangeStatus manifest(Attributor &A) override
See AbstractAttribute::manifest(...).
Definition: Attributor.h:1121
ChangeStatus update(Attributor &A)
Hook for the Attributor to trigger an update of the internal state.
Definition: Attributor.cpp:285
IntegerState & takeKnownMaximum(base_t Value)
Take maximum of known and Value.
Definition: Attributor.h:1012
bool isAssumedGlobal() const
Return true if we assume that underlying value is dereferenceable(_or_null) globally.
Definition: Attributor.h:1610
unsigned getAttrIdx() const
Return the index in the attribute list for this position.
Definition: Attributor.h:364
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:646
bool isKnownNoFree() const
Return true if "nofree" is known.
Definition: Attributor.h:1441
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:1428
IRPosition & getIRPosition() override
Return an IR position, see struct IRPosition.
Definition: Attributor.h:1503
AttributeSet getAttributes(unsigned Index) const
The attributes for the specified index are returned.
AAReturnedValues(const IRPosition &IRP)
Definition: Attributor.h:1283
static const IRPosition callsite_function(ImmutableCallSite ICS)
Create a position describing the function scope of ICS.
Definition: Attributor.h:199
MapVector< Value *, SmallSetVector< ReturnInst *, 4 > >::iterator iterator
Definition: Attributor.h:1302
base_t getKnown() const
Return the known state encoding.
Definition: Attributor.h:967
bool isAtFixpoint() const override
See AbstractState::isAtFixpoint()
Definition: Attributor.h:1527
DerefState operator+=(const DerefState &R)
See IntegerState::operator+=.
Definition: Attributor.h:1573
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:763
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1700
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
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:1409
An abstract interface for all dereferenceable attribute.
Definition: Attributor.h:1598
AAType & registerAA(AAType &AA)
Introduce a new abstract attribute into the fixpoint analysis.
Definition: Attributor.h:670
bool isKnownNoSync() const
Returns true if "nosync" is known.
Definition: Attributor.h:1346
AANoUnwind(const IRPosition &IRP)
Definition: Attributor.h:1322
bool isKnownNoCapture() const
Return true if we know that the underlying value is not captured in its respective scope...
Definition: Attributor.h:1678
AADereferenceable(const IRPosition &IRP)
Definition: Attributor.h:1601
Value & getAnchorValue()
Return the value this abstract attribute is anchored with.
Definition: Attributor.h:241
static const IRPosition returned(const Function &F)
Create a position describing the returned value of F.
Definition: Attributor.h:173
An attribute for a function (scope).
Definition: Attributor.h:147
virtual void initialize(Attributor &A)
Initialize the state with the information in the Attributor A.
Definition: Attributor.h:1201
bool hasInternalLinkage() const
Definition: GlobalValue.h:443
AANoFree(const IRPosition &IRP)
Definition: Attributor.h:1435
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:1692
An attribute for a function argument.
Definition: Attributor.h:149
bool isFnInterfaceKind() const
}
Definition: Attributor.h:294
bool isAssumedNonNull() const
Return true if we assume that the underlying value is nonnull.
Definition: Attributor.h:1362
The fixpoint analysis framework that orchestrates the attribute deduction.
Definition: Attributor.h:602
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:781
static unsigned getHashValue(const IRPosition &IRP)
Definition: Attributor.h:478
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:59
Simple state with integers encoding.
Definition: Attributor.h:937
Attribute::AttrKind getAttrKind() const
Return the kind that identifies the abstract attribute implementation.
Definition: Attributor.h:1128
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:1187
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1511
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:658
#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:1334
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:1087
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:610
virtual StateType & getState()=0
Return the internal abstract state for inspection.
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1316
An AbstractAttribute for nofree.
Definition: Attributor.h:1432
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:991
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:1378
const IRPosition & getIRPosition() const override
Definition: Attributor.h:1140
BooleanState GlobalState
State representing that whether the value is globaly dereferenceable.
Definition: Attributor.h:1521
bool isAssumedNoCapture() const
Return true if we assume that the underlying value is not captured in its respective scope...
Definition: Attributor.h:1682
void deleteAfterManifest(Instruction &I)
Record that I is deleted after information was manifested.
Definition: Attributor.h:711
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Data structure to hold cached (LLVM-IR) information.
Definition: Attributor.h:533
void markLiveInternalFunction(const Function &F)
Mark the internal function F as live.
Definition: Attributor.h:704
const Instruction * getCtxI() const
Definition: Attributor.h:338
static const IRPosition callsite_argument(ImmutableCallSite ICS, unsigned ArgNo)
Create a position describing the argument of ICS at position ArgNo.
Definition: Attributor.h:209
IRAttribute(const IRPosition &IRP)
Definition: Attributor.h:1096
virtual void initialize(Attributor &A) override
See AbstractAttribute::initialize(...).
Definition: Attributor.h:1100
bool operator==(const DerefState &R)
Equality for DerefState.
Definition: Attributor.h:1557
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:188
A range adaptor for a pair of iterators.
bool operator!=(const IntegerState &R) const
Inequality for IntegerState.
Definition: Attributor.h:1026
Helper class that provides common functionality to manifest IR attributes.
Definition: Attributor.h:1095
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1352
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:1504
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1466
static const IRPosition value(const Value &V)
Create a position describing the value of V.
Definition: Attributor.h:159
An interface to query the internal state of an abstract attribute.
Definition: Attributor.h:899
void deleteAfterManifest(Function &F)
Record that F is deleted after information was manifested.
Definition: Attributor.h:717
Function * getAssociatedFunction()
}
Definition: Attributor.h:254
An abstract interface for all align attributes.
Definition: Attributor.h:1635
static const IRPosition argument(const Argument &Arg)
Create a position describing the argument Arg.
Definition: Attributor.h:178
IRPosition & getIRPosition()
Return an IR position, see struct IRPosition.
Definition: Attributor.h:1711
IntegerState & addKnownBits(base_t Bits)
Add the bits in BitsEncoding to the "known bits".
Definition: Attributor.h:983
static bool isEqual(const IRPosition &LHS, const IRPosition &RHS)
Definition: Attributor.h:482
Pass * createAttributorLegacyPass()
Argument * getAssociatedArgument()
}
Definition: Attributor.h:276
const Value & getAssociatedValue() const
Definition: Attributor.h:354
InformationCache & getInfoCache()
Return the internal information cache.
Definition: Attributor.h:686
const Function * getAssociatedFunction() const
Definition: Attributor.h:268
bool operator!=(const DerefState &R)
Inequality for IntegerState.
Definition: Attributor.h:1563
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:897
#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:1371
An abstract interface for value simplify abstract attribute.
Definition: Attributor.h:1704
virtual void getDeducedAttributes(LLVMContext &Ctx, SmallVectorImpl< Attribute > &Attrs) const
Return the deduced attributes in Attrs.
Definition: Attributor.h:1131
static const IRPosition callsite_function(const CallBase &CB)
Create a position describing the function scope of CB.
Definition: Attributor.h:183
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:1488
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:148
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1631
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2045
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
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:1641
bool isKnownGlobal() const
Return true if we know that underlying value is dereferenceable(_or_null) globally.
Definition: Attributor.h:1614
bool isKnownNoRecurse() const
Return true if "norecurse" is known.
Definition: Attributor.h:1384
AAValueSimplify(const IRPosition &IRP)
Definition: Attributor.h:1706
bool isValidState() const override
See AbstractState::isValidState()
Definition: Attributor.h:1524
AANonNull(const IRPosition &IRP)
Definition: Attributor.h:1359
static const IRPosition EmptyKey
Special DenseMap key values.
Definition: Attributor.h:447
bool isKnownWillReturn() const
Return true if "willreturn" is known.
Definition: Attributor.h:1403
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static const IRPosition TombstoneKey
Definition: Attributor.h:448
LLVM Value Representation.
Definition: Value.h:73
bool isKnownNonNull() const
Return true if we know that underlying value is nonnull.
Definition: Attributor.h:1365
E & operator &=(E &LHS, E RHS)
Definition: BitmaskEnum.h:133
Function * getAnchorScope()
Return the Function surrounding the anchor value.
Definition: Attributor.h:308
const AbstractState & getState() const override
See AbstractAttribute::getState(...).
Definition: Attributor.h:1090
virtual ChangeStatus manifest(Attributor &A)
Hook for the Attributor to trigger the manifestation of the information represented by the abstract a...
Definition: Attributor.h:1235
bool isAssumedWillReturn() const
Return true if "willreturn" is assumed.
Definition: Attributor.h:1400
An invalid position.
Definition: Attributor.h:142
virtual ~AbstractAttribute()
Virtual destructor.
Definition: Attributor.h:1191
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:1515
bool isAtFixpoint() const override
See AbstractState::isAtFixpoint()
Definition: Attributor.h:952
static const IRPosition callsite_argument(const CallBase &CB, unsigned ArgNo)
Create a position describing the argument of CB at position ArgNo.
Definition: Attributor.h:193
bool isKnownNoAlias() const
Return true if we know that underlying value is noalias.
Definition: Attributor.h:1422
ChangeStatus indicatePessimisticFixpoint() override
See AbstractState::indicatePessimisticFixpoint(...)
Definition: Attributor.h:1540
A container for analyses that lazily runs them and caches their results.
DerefState operator|=(const DerefState &R)
See IntegerState::operator|=.
Definition: Attributor.h:1587
APInt operator|(APInt a, const APInt &b)
Definition: APInt.h:2005
static constexpr base_t getWorstState()
Return the worst possible representable state.
Definition: Attributor.h:945
AAIsDead(const IRPosition &IRP)
Definition: Attributor.h:1472
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:1604
bool isAssumed(base_t BitsEncoding) const
Return true if the bits set in BitsEncoding are "assumed bits".
Definition: Attributor.h:978
IntegerState operator+=(const IntegerState &R)
"Clamp" this state with R.
Definition: Attributor.h:1041
AANoSync(const IRPosition &IRP)
Definition: Attributor.h:1340
DerefState operator^=(const DerefState &R)
See IntegerState::operator^=.
Definition: Attributor.h:1566
static const IRPosition function(const Function &F)
Create a position describing the function scope of F.
Definition: Attributor.h:168
IRPosition()
Default constructor available to create invalid positions implicitly.
Definition: Attributor.h:156
Kind getPositionKind() const
Return the associated position kind.
Definition: Attributor.h:384
void deleteAfterManifest(BasicBlock &BB)
Record that BB is deleted after information was manifested.
Definition: Attributor.h:714
Simple wrapper for a single bit (boolean) state.
Definition: Attributor.h:1069
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:998
ChangeStatus indicateOptimisticFixpoint() override
See AbstractState::indicateOptimisticFixpoint(...)
Definition: Attributor.h:1533