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