LLVM  13.0.0git
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 reevaluate 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 // {Inc,Dec,Bit}IntegerState if they fit your needs, e.g., you require only a
76 // number tracking or bit-encoding.
77 // - Implement all pure methods. Also use overloading if the attribute is not
78 // conforming with the "default" behavior: A (set of) LLVM-IR attribute(s) for
79 // an argument, call site argument, function return value, or function. See
80 // the class and method descriptions for more information on the two
81 // "Abstract" classes and their respective methods.
82 // - Register opportunities for the new abstract attribute in the
83 // `Attributor::identifyDefaultAbstractAttributes` method if it should be
84 // counted as a 'default' attribute.
85 // - Add sufficient tests.
86 // - Add a Statistics object for bookkeeping. If it is a simple (set of)
87 // attribute(s) manifested through the Attributor manifestation framework, see
88 // the bookkeeping function in Attributor.cpp.
89 // - If instructions with a certain opcode are interesting to the attribute, add
90 // that opcode to the switch in `Attributor::identifyAbstractAttributes`. This
91 // will make it possible to query all those instructions through the
92 // `InformationCache::getOpcodeInstMapForFunction` interface and eliminate the
93 // need to traverse the IR repeatedly.
94 //
95 //===----------------------------------------------------------------------===//
96 
97 #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
98 #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
99 
100 #include "llvm/ADT/DenseSet.h"
101 #include "llvm/ADT/GraphTraits.h"
102 #include "llvm/ADT/MapVector.h"
103 #include "llvm/ADT/STLExtras.h"
104 #include "llvm/ADT/SetVector.h"
106 #include "llvm/Analysis/CFG.h"
109 #include "llvm/Analysis/LoopInfo.h"
114 #include "llvm/IR/ConstantRange.h"
115 #include "llvm/IR/PassManager.h"
116 #include "llvm/Support/Allocator.h"
117 #include "llvm/Support/Casting.h"
120 
121 namespace llvm {
122 
123 struct AADepGraphNode;
124 struct AADepGraph;
125 struct Attributor;
126 struct AbstractAttribute;
127 struct InformationCache;
128 struct AAIsDead;
129 
130 class AAManager;
131 class AAResults;
132 class Function;
133 
134 /// Abstract Attribute helper functions.
135 namespace AA {
136 /// Try to convert \p V to type \p Ty without introducing new instructions. If
137 /// this is not possible return `nullptr`. Note: this function basically knows
138 /// how to cast various constants.
139 Value *getWithType(Value &V, Type &Ty);
140 
141 } // namespace AA
142 
143 /// The value passed to the line option that defines the maximal initialization
144 /// chain length.
145 extern unsigned MaxInitializationChainLength;
146 
147 ///{
148 enum class ChangeStatus {
149  CHANGED,
150  UNCHANGED,
151 };
152 
155 
156 enum class DepClassTy {
157  REQUIRED, ///< The target cannot be valid if the source is not.
158  OPTIONAL, ///< The target may be valid if the source is not.
159  NONE, ///< Do not track a dependence between source and target.
160 };
161 ///}
162 
163 /// The data structure for the nodes of a dependency graph
165 public:
166  virtual ~AADepGraphNode(){};
168 
169 protected:
170  /// Set of dependency graph nodes which should be updated if this one
171  /// is updated. The bit encodes if it is optional.
173 
174  static AADepGraphNode *DepGetVal(DepTy &DT) { return DT.getPointer(); }
176  return cast<AbstractAttribute>(DT.getPointer());
177  }
178 
179  operator AbstractAttribute *() { return cast<AbstractAttribute>(this); }
180 
181 public:
182  using iterator =
184  using aaiterator =
186 
187  aaiterator begin() { return aaiterator(Deps.begin(), &DepGetValAA); }
188  aaiterator end() { return aaiterator(Deps.end(), &DepGetValAA); }
189  iterator child_begin() { return iterator(Deps.begin(), &DepGetVal); }
190  iterator child_end() { return iterator(Deps.end(), &DepGetVal); }
191 
192  virtual void print(raw_ostream &OS) const { OS << "AADepNode Impl\n"; }
194 
195  friend struct Attributor;
196  friend struct AADepGraph;
197 };
198 
199 /// The data structure for the dependency graph
200 ///
201 /// Note that in this graph if there is an edge from A to B (A -> B),
202 /// then it means that B depends on A, and when the state of A is
203 /// updated, node B should also be updated
204 struct AADepGraph {
207 
209  static AADepGraphNode *DepGetVal(DepTy &DT) { return DT.getPointer(); }
210  using iterator =
212 
213  /// There is no root node for the dependency graph. But the SCCIterator
214  /// requires a single entry point, so we maintain a fake("synthetic") root
215  /// node that depends on every node.
218 
221 
222  void viewGraph();
223 
224  /// Dump graph to file
225  void dumpGraph();
226 
227  /// Print dependency graph
228  void print();
229 };
230 
231 /// Helper to describe and deal with positions in the LLVM-IR.
232 ///
233 /// A position in the IR is described by an anchor value and an "offset" that
234 /// could be the argument number, for call sites and arguments, or an indicator
235 /// of the "position kind". The kinds, specified in the Kind enum below, include
236 /// the locations in the attribute list, i.a., function scope and return value,
237 /// as well as a distinction between call sites and functions. Finally, there
238 /// are floating values that do not have a corresponding attribute list
239 /// position.
240 struct IRPosition {
241  // NOTE: In the future this definition can be changed to support recursive
242  // functions.
244 
245  /// The positions we distinguish in the IR.
246  enum Kind : char {
247  IRP_INVALID, ///< An invalid position.
248  IRP_FLOAT, ///< A position that is not associated with a spot suitable
249  ///< for attributes. This could be any value or instruction.
250  IRP_RETURNED, ///< An attribute for the function return value.
251  IRP_CALL_SITE_RETURNED, ///< An attribute for a call site return value.
252  IRP_FUNCTION, ///< An attribute for a function (scope).
253  IRP_CALL_SITE, ///< An attribute for a call site (function scope).
254  IRP_ARGUMENT, ///< An attribute for a function argument.
255  IRP_CALL_SITE_ARGUMENT, ///< An attribute for a call site argument.
256  };
257 
258  /// Default constructor available to create invalid positions implicitly. All
259  /// other positions need to be created explicitly through the appropriate
260  /// static member function.
261  IRPosition() : Enc(nullptr, ENC_VALUE) { verify(); }
262 
263  /// Create a position describing the value of \p V.
264  static const IRPosition value(const Value &V,
265  const CallBaseContext *CBContext = nullptr) {
266  if (auto *Arg = dyn_cast<Argument>(&V))
267  return IRPosition::argument(*Arg, CBContext);
268  if (auto *CB = dyn_cast<CallBase>(&V))
269  return IRPosition::callsite_returned(*CB);
270  return IRPosition(const_cast<Value &>(V), IRP_FLOAT, CBContext);
271  }
272 
273  /// Create a position describing the function scope of \p F.
274  /// \p CBContext is used for call base specific analysis.
275  static const IRPosition function(const Function &F,
276  const CallBaseContext *CBContext = nullptr) {
277  return IRPosition(const_cast<Function &>(F), IRP_FUNCTION, CBContext);
278  }
279 
280  /// Create a position describing the returned value of \p F.
281  /// \p CBContext is used for call base specific analysis.
282  static const IRPosition returned(const Function &F,
283  const CallBaseContext *CBContext = nullptr) {
284  return IRPosition(const_cast<Function &>(F), IRP_RETURNED, CBContext);
285  }
286 
287  /// Create a position describing the argument \p Arg.
288  /// \p CBContext is used for call base specific analysis.
289  static const IRPosition argument(const Argument &Arg,
290  const CallBaseContext *CBContext = nullptr) {
291  return IRPosition(const_cast<Argument &>(Arg), IRP_ARGUMENT, CBContext);
292  }
293 
294  /// Create a position describing the function scope of \p CB.
295  static const IRPosition callsite_function(const CallBase &CB) {
296  return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE);
297  }
298 
299  /// Create a position describing the returned value of \p CB.
300  static const IRPosition callsite_returned(const CallBase &CB) {
301  return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE_RETURNED);
302  }
303 
304  /// Create a position describing the argument of \p CB at position \p ArgNo.
305  static const IRPosition callsite_argument(const CallBase &CB,
306  unsigned ArgNo) {
307  return IRPosition(const_cast<Use &>(CB.getArgOperandUse(ArgNo)),
309  }
310 
311  /// Create a position describing the argument of \p ACS at position \p ArgNo.
313  unsigned ArgNo) {
314  if (ACS.getNumArgOperands() <= ArgNo)
315  return IRPosition();
316  int CSArgNo = ACS.getCallArgOperandNo(ArgNo);
317  if (CSArgNo >= 0)
319  cast<CallBase>(*ACS.getInstruction()), CSArgNo);
320  return IRPosition();
321  }
322 
323  /// Create a position with function scope matching the "context" of \p IRP.
324  /// If \p IRP is a call site (see isAnyCallSitePosition()) then the result
325  /// will be a call site position, otherwise the function position of the
326  /// associated function.
327  static const IRPosition
329  const CallBaseContext *CBContext = nullptr) {
330  if (IRP.isAnyCallSitePosition()) {
332  cast<CallBase>(IRP.getAnchorValue()));
333  }
335  return IRPosition::function(*IRP.getAssociatedFunction(), CBContext);
336  }
337 
338  bool operator==(const IRPosition &RHS) const {
339  return Enc == RHS.Enc && RHS.CBContext == CBContext;
340  }
341  bool operator!=(const IRPosition &RHS) const { return !(*this == RHS); }
342 
343  /// Return the value this abstract attribute is anchored with.
344  ///
345  /// The anchor value might not be the associated value if the latter is not
346  /// sufficient to determine where arguments will be manifested. This is, so
347  /// far, only the case for call site arguments as the value is not sufficient
348  /// to pinpoint them. Instead, we can use the call site as an anchor.
350  switch (getEncodingBits()) {
351  case ENC_VALUE:
352  case ENC_RETURNED_VALUE:
353  case ENC_FLOATING_FUNCTION:
354  return *getAsValuePtr();
355  case ENC_CALL_SITE_ARGUMENT_USE:
356  return *(getAsUsePtr()->getUser());
357  default:
358  llvm_unreachable("Unkown encoding!");
359  };
360  }
361 
362  /// Return the associated function, if any.
364  if (auto *CB = dyn_cast<CallBase>(&getAnchorValue())) {
365  // We reuse the logic that associates callback calles to arguments of a
366  // call site here to identify the callback callee as the associated
367  // function.
369  return Arg->getParent();
370  return CB->getCalledFunction();
371  }
372  return getAnchorScope();
373  }
374 
375  /// Return the associated argument, if any.
377 
378  /// Return true if the position refers to a function interface, that is the
379  /// function scope, the function return, or an argument.
380  bool isFnInterfaceKind() const {
381  switch (getPositionKind()) {
385  return true;
386  default:
387  return false;
388  }
389  }
390 
391  /// Return the Function surrounding the anchor value.
393  Value &V = getAnchorValue();
394  if (isa<Function>(V))
395  return &cast<Function>(V);
396  if (isa<Argument>(V))
397  return cast<Argument>(V).getParent();
398  if (isa<Instruction>(V))
399  return cast<Instruction>(V).getFunction();
400  return nullptr;
401  }
402 
403  /// Return the context instruction, if any.
404  Instruction *getCtxI() const {
405  Value &V = getAnchorValue();
406  if (auto *I = dyn_cast<Instruction>(&V))
407  return I;
408  if (auto *Arg = dyn_cast<Argument>(&V))
409  if (!Arg->getParent()->isDeclaration())
410  return &Arg->getParent()->getEntryBlock().front();
411  if (auto *F = dyn_cast<Function>(&V))
412  if (!F->isDeclaration())
413  return &(F->getEntryBlock().front());
414  return nullptr;
415  }
416 
417  /// Return the value this abstract attribute is associated with.
419  if (getCallSiteArgNo() < 0 || isa<Argument>(&getAnchorValue()))
420  return getAnchorValue();
421  assert(isa<CallBase>(&getAnchorValue()) && "Expected a call base!");
422  return *cast<CallBase>(&getAnchorValue())
423  ->getArgOperand(getCallSiteArgNo());
424  }
425 
426  /// Return the type this abstract attribute is associated with.
430  return getAssociatedValue().getType();
431  }
432 
433  /// Return the callee argument number of the associated value if it is an
434  /// argument or call site argument, otherwise a negative value. In contrast to
435  /// `getCallSiteArgNo` this method will always return the "argument number"
436  /// from the perspective of the callee. This may not the same as the call site
437  /// if this is a callback call.
438  int getCalleeArgNo() const {
439  return getArgNo(/* CallbackCalleeArgIfApplicable */ true);
440  }
441 
442  /// Return the call site argument number of the associated value if it is an
443  /// argument or call site argument, otherwise a negative value. In contrast to
444  /// `getCalleArgNo` this method will always return the "operand number" from
445  /// the perspective of the call site. This may not the same as the callee
446  /// perspective if this is a callback call.
447  int getCallSiteArgNo() const {
448  return getArgNo(/* CallbackCalleeArgIfApplicable */ false);
449  }
450 
451  /// Return the index in the attribute list for this position.
452  unsigned getAttrIdx() const {
453  switch (getPositionKind()) {
456  break;
466  }
468  "There is no attribute index for a floating or invalid position!");
469  }
470 
471  /// Return the associated position kind.
473  char EncodingBits = getEncodingBits();
474  if (EncodingBits == ENC_CALL_SITE_ARGUMENT_USE)
475  return IRP_CALL_SITE_ARGUMENT;
476  if (EncodingBits == ENC_FLOATING_FUNCTION)
477  return IRP_FLOAT;
478 
479  Value *V = getAsValuePtr();
480  if (!V)
481  return IRP_INVALID;
482  if (isa<Argument>(V))
483  return IRP_ARGUMENT;
484  if (isa<Function>(V))
485  return isReturnPosition(EncodingBits) ? IRP_RETURNED : IRP_FUNCTION;
486  if (isa<CallBase>(V))
487  return isReturnPosition(EncodingBits) ? IRP_CALL_SITE_RETURNED
488  : IRP_CALL_SITE;
489  return IRP_FLOAT;
490  }
491 
492  /// TODO: Figure out if the attribute related helper functions should live
493  /// here or somewhere else.
494 
495  /// Return true if any kind in \p AKs existing in the IR at a position that
496  /// will affect this one. See also getAttrs(...).
497  /// \param IgnoreSubsumingPositions Flag to determine if subsuming positions,
498  /// e.g., the function position if this is an
499  /// argument position, should be ignored.
501  bool IgnoreSubsumingPositions = false,
502  Attributor *A = nullptr) const;
503 
504  /// Return the attributes of any kind in \p AKs existing in the IR at a
505  /// position that will affect this one. While each position can only have a
506  /// single attribute of any kind in \p AKs, there are "subsuming" positions
507  /// that could have an attribute as well. This method returns all attributes
508  /// found in \p Attrs.
509  /// \param IgnoreSubsumingPositions Flag to determine if subsuming positions,
510  /// e.g., the function position if this is an
511  /// argument position, should be ignored.
514  bool IgnoreSubsumingPositions = false,
515  Attributor *A = nullptr) const;
516 
517  /// Remove the attribute of kind \p AKs existing in the IR at this position.
520  return;
521 
522  AttributeList AttrList;
523  auto *CB = dyn_cast<CallBase>(&getAnchorValue());
524  if (CB)
525  AttrList = CB->getAttributes();
526  else
527  AttrList = getAssociatedFunction()->getAttributes();
528 
530  for (Attribute::AttrKind AK : AKs)
531  AttrList = AttrList.removeAttribute(Ctx, getAttrIdx(), AK);
532 
533  if (CB)
534  CB->setAttributes(AttrList);
535  else
537  }
538 
539  bool isAnyCallSitePosition() const {
540  switch (getPositionKind()) {
544  return true;
545  default:
546  return false;
547  }
548  }
549 
550  /// Return true if the position is an argument or call site argument.
551  bool isArgumentPosition() const {
552  switch (getPositionKind()) {
555  return true;
556  default:
557  return false;
558  }
559  }
560 
561  /// Return the same position without the call base context.
563  IRPosition Result = *this;
564  Result.CBContext = nullptr;
565  return Result;
566  }
567 
568  /// Get the call base context from the position.
569  const CallBaseContext *getCallBaseContext() const { return CBContext; }
570 
571  /// Check if the position has any call base context.
572  bool hasCallBaseContext() const { return CBContext != nullptr; }
573 
574  /// Special DenseMap key values.
575  ///
576  ///{
577  static const IRPosition EmptyKey;
578  static const IRPosition TombstoneKey;
579  ///}
580 
581  /// Conversion into a void * to allow reuse of pointer hashing.
582  operator void *() const { return Enc.getOpaqueValue(); }
583 
584 private:
585  /// Private constructor for special values only!
586  explicit IRPosition(void *Ptr, const CallBaseContext *CBContext = nullptr)
587  : CBContext(CBContext) {
588  Enc.setFromOpaqueValue(Ptr);
589  }
590 
591  /// IRPosition anchored at \p AnchorVal with kind/argument numbet \p PK.
592  explicit IRPosition(Value &AnchorVal, Kind PK,
593  const CallBaseContext *CBContext = nullptr)
594  : CBContext(CBContext) {
595  switch (PK) {
597  llvm_unreachable("Cannot create invalid IRP with an anchor value!");
598  break;
600  // Special case for floating functions.
601  if (isa<Function>(AnchorVal))
602  Enc = {&AnchorVal, ENC_FLOATING_FUNCTION};
603  else
604  Enc = {&AnchorVal, ENC_VALUE};
605  break;
608  Enc = {&AnchorVal, ENC_VALUE};
609  break;
612  Enc = {&AnchorVal, ENC_RETURNED_VALUE};
613  break;
615  Enc = {&AnchorVal, ENC_VALUE};
616  break;
619  "Cannot create call site argument IRP with an anchor value!");
620  break;
621  }
622  verify();
623  }
624 
625  /// Return the callee argument number of the associated value if it is an
626  /// argument or call site argument. See also `getCalleeArgNo` and
627  /// `getCallSiteArgNo`.
628  int getArgNo(bool CallbackCalleeArgIfApplicable) const {
629  if (CallbackCalleeArgIfApplicable)
630  if (Argument *Arg = getAssociatedArgument())
631  return Arg->getArgNo();
632  switch (getPositionKind()) {
634  return cast<Argument>(getAsValuePtr())->getArgNo();
636  Use &U = *getAsUsePtr();
637  return cast<CallBase>(U.getUser())->getArgOperandNo(&U);
638  }
639  default:
640  return -1;
641  }
642  }
643 
644  /// IRPosition for the use \p U. The position kind \p PK needs to be
645  /// IRP_CALL_SITE_ARGUMENT, the anchor value is the user, the associated value
646  /// the used value.
647  explicit IRPosition(Use &U, Kind PK) {
649  "Use constructor is for call site arguments only!");
650  Enc = {&U, ENC_CALL_SITE_ARGUMENT_USE};
651  verify();
652  }
653 
654  /// Verify internal invariants.
655  void verify();
656 
657  /// Return the attributes of kind \p AK existing in the IR as attribute.
658  bool getAttrsFromIRAttr(Attribute::AttrKind AK,
659  SmallVectorImpl<Attribute> &Attrs) const;
660 
661  /// Return the attributes of kind \p AK existing in the IR as operand bundles
662  /// of an llvm.assume.
663  bool getAttrsFromAssumes(Attribute::AttrKind AK,
664  SmallVectorImpl<Attribute> &Attrs,
665  Attributor &A) const;
666 
667  /// Return the underlying pointer as Value *, valid for all positions but
668  /// IRP_CALL_SITE_ARGUMENT.
669  Value *getAsValuePtr() const {
670  assert(getEncodingBits() != ENC_CALL_SITE_ARGUMENT_USE &&
671  "Not a value pointer!");
672  return reinterpret_cast<Value *>(Enc.getPointer());
673  }
674 
675  /// Return the underlying pointer as Use *, valid only for
676  /// IRP_CALL_SITE_ARGUMENT positions.
677  Use *getAsUsePtr() const {
678  assert(getEncodingBits() == ENC_CALL_SITE_ARGUMENT_USE &&
679  "Not a value pointer!");
680  return reinterpret_cast<Use *>(Enc.getPointer());
681  }
682 
683  /// Return true if \p EncodingBits describe a returned or call site returned
684  /// position.
685  static bool isReturnPosition(char EncodingBits) {
686  return EncodingBits == ENC_RETURNED_VALUE;
687  }
688 
689  /// Return true if the encoding bits describe a returned or call site returned
690  /// position.
691  bool isReturnPosition() const { return isReturnPosition(getEncodingBits()); }
692 
693  /// The encoding of the IRPosition is a combination of a pointer and two
694  /// encoding bits. The values of the encoding bits are defined in the enum
695  /// below. The pointer is either a Value* (for the first three encoding bit
696  /// combinations) or Use* (for ENC_CALL_SITE_ARGUMENT_USE).
697  ///
698  ///{
699  enum {
700  ENC_VALUE = 0b00,
701  ENC_RETURNED_VALUE = 0b01,
702  ENC_FLOATING_FUNCTION = 0b10,
703  ENC_CALL_SITE_ARGUMENT_USE = 0b11,
704  };
705 
706  // Reserve the maximal amount of bits so there is no need to mask out the
707  // remaining ones. We will not encode anything else in the pointer anyway.
708  static constexpr int NumEncodingBits =
710  static_assert(NumEncodingBits >= 2, "At least two bits are required!");
711 
712  /// The pointer with the encoding bits.
713  PointerIntPair<void *, NumEncodingBits, char> Enc;
714  ///}
715 
716  /// Call base context. Used for callsite specific analysis.
717  const CallBaseContext *CBContext = nullptr;
718 
719  /// Return the encoding bits.
720  char getEncodingBits() const { return Enc.getInt(); }
721 };
722 
723 /// Helper that allows IRPosition as a key in a DenseMap.
724 template <> struct DenseMapInfo<IRPosition> {
725  static inline IRPosition getEmptyKey() { return IRPosition::EmptyKey; }
726  static inline IRPosition getTombstoneKey() {
728  }
729  static unsigned getHashValue(const IRPosition &IRP) {
730  return (DenseMapInfo<void *>::getHashValue(IRP) << 4) ^
732  }
733 
734  static bool isEqual(const IRPosition &a, const IRPosition &b) {
735  return a == b;
736  }
737 };
738 
739 /// A visitor class for IR positions.
740 ///
741 /// Given a position P, the SubsumingPositionIterator allows to visit "subsuming
742 /// positions" wrt. attributes/information. Thus, if a piece of information
743 /// holds for a subsuming position, it also holds for the position P.
744 ///
745 /// The subsuming positions always include the initial position and then,
746 /// depending on the position kind, additionally the following ones:
747 /// - for IRP_RETURNED:
748 /// - the function (IRP_FUNCTION)
749 /// - for IRP_ARGUMENT:
750 /// - the function (IRP_FUNCTION)
751 /// - for IRP_CALL_SITE:
752 /// - the callee (IRP_FUNCTION), if known
753 /// - for IRP_CALL_SITE_RETURNED:
754 /// - the callee (IRP_RETURNED), if known
755 /// - the call site (IRP_FUNCTION)
756 /// - the callee (IRP_FUNCTION), if known
757 /// - for IRP_CALL_SITE_ARGUMENT:
758 /// - the argument of the callee (IRP_ARGUMENT), if known
759 /// - the callee (IRP_FUNCTION), if known
760 /// - the position the call site argument is associated with if it is not
761 /// anchored to the call site, e.g., if it is an argument then the argument
762 /// (IRP_ARGUMENT)
764  SmallVector<IRPosition, 4> IRPositions;
765  using iterator = decltype(IRPositions)::iterator;
766 
767 public:
769  iterator begin() { return IRPositions.begin(); }
770  iterator end() { return IRPositions.end(); }
771 };
772 
773 /// Wrapper for FunctoinAnalysisManager.
775  template <typename Analysis>
776  typename Analysis::Result *getAnalysis(const Function &F) {
777  if (!FAM || !F.getParent())
778  return nullptr;
779  return &FAM->getResult<Analysis>(const_cast<Function &>(F));
780  }
781 
784 
785 private:
786  FunctionAnalysisManager *FAM = nullptr;
787 };
788 
789 /// Data structure to hold cached (LLVM-IR) information.
790 ///
791 /// All attributes are given an InformationCache object at creation time to
792 /// avoid inspection of the IR by all of them individually. This default
793 /// InformationCache will hold information required by 'default' attributes,
794 /// thus the ones deduced when Attributor::identifyDefaultAbstractAttributes(..)
795 /// is called.
796 ///
797 /// If custom abstract attributes, registered manually through
798 /// Attributor::registerAA(...), need more information, especially if it is not
799 /// reusable, it is advised to inherit from the InformationCache and cast the
800 /// instance down in the abstract attributes.
803  BumpPtrAllocator &Allocator, SetVector<Function *> *CGSCC)
804  : DL(M.getDataLayout()), Allocator(Allocator),
805  Explorer(
806  /* ExploreInterBlock */ true, /* ExploreCFGForward */ true,
807  /* ExploreCFGBackward */ true,
808  /* LIGetter */
809  [&](const Function &F) { return AG.getAnalysis<LoopAnalysis>(F); },
810  /* DTGetter */
811  [&](const Function &F) {
812  return AG.getAnalysis<DominatorTreeAnalysis>(F);
813  },
814  /* PDTGetter */
815  [&](const Function &F) {
816  return AG.getAnalysis<PostDominatorTreeAnalysis>(F);
817  }),
818  AG(AG), CGSCC(CGSCC) {
819  if (CGSCC)
820  initializeModuleSlice(*CGSCC);
821  }
822 
824  // The FunctionInfo objects are allocated via a BumpPtrAllocator, we call
825  // the destructor manually.
826  for (auto &It : FuncInfoMap)
827  It.getSecond()->~FunctionInfo();
828  }
829 
830  /// Apply \p CB to all uses of \p F. If \p LookThroughConstantExprUses is
831  /// true, constant expression users are not given to \p CB but their uses are
832  /// traversed transitively.
833  template <typename CBTy>
834  static void foreachUse(Function &F, CBTy CB,
835  bool LookThroughConstantExprUses = true) {
836  SmallVector<Use *, 8> Worklist(make_pointer_range(F.uses()));
837 
838  for (unsigned Idx = 0; Idx < Worklist.size(); ++Idx) {
839  Use &U = *Worklist[Idx];
840 
841  // Allow use in constant bitcasts and simply look through them.
842  if (LookThroughConstantExprUses && isa<ConstantExpr>(U.getUser())) {
843  for (Use &CEU : cast<ConstantExpr>(U.getUser())->uses())
844  Worklist.push_back(&CEU);
845  continue;
846  }
847 
848  CB(U);
849  }
850  }
851 
852  /// Initialize the ModuleSlice member based on \p SCC. ModuleSlices contains
853  /// (a subset of) all functions that we can look at during this SCC traversal.
854  /// This includes functions (transitively) called from the SCC and the
855  /// (transitive) callers of SCC functions. We also can look at a function if
856  /// there is a "reference edge", i.a., if the function somehow uses (!=calls)
857  /// a function in the SCC or a caller of a function in the SCC.
859  ModuleSlice.insert(SCC.begin(), SCC.end());
860 
862  SmallVector<Function *, 16> Worklist(SCC.begin(), SCC.end());
863  while (!Worklist.empty()) {
864  Function *F = Worklist.pop_back_val();
865  ModuleSlice.insert(F);
866 
867  for (Instruction &I : instructions(*F))
868  if (auto *CB = dyn_cast<CallBase>(&I))
869  if (Function *Callee = CB->getCalledFunction())
870  if (Seen.insert(Callee).second)
871  Worklist.push_back(Callee);
872  }
873 
874  Seen.clear();
875  Worklist.append(SCC.begin(), SCC.end());
876  while (!Worklist.empty()) {
877  Function *F = Worklist.pop_back_val();
878  ModuleSlice.insert(F);
879 
880  // Traverse all transitive uses.
881  foreachUse(*F, [&](Use &U) {
882  if (auto *UsrI = dyn_cast<Instruction>(U.getUser()))
883  if (Seen.insert(UsrI->getFunction()).second)
884  Worklist.push_back(UsrI->getFunction());
885  });
886  }
887  }
888 
889  /// The slice of the module we are allowed to look at.
891 
892  /// A vector type to hold instructions.
894 
895  /// A map type from opcodes to instructions with this opcode.
897 
898  /// Return the map that relates "interesting" opcodes with all instructions
899  /// with that opcode in \p F.
901  return getFunctionInfo(F).OpcodeInstMap;
902  }
903 
904  /// Return the instructions in \p F that may read or write memory.
906  return getFunctionInfo(F).RWInsts;
907  }
908 
909  /// Return MustBeExecutedContextExplorer
911  return Explorer;
912  }
913 
914  /// Return TargetLibraryInfo for function \p F.
916  return AG.getAnalysis<TargetLibraryAnalysis>(F);
917  }
918 
919  /// Return AliasAnalysis Result for function \p F.
921 
922  /// Return true if \p Arg is involved in a must-tail call, thus the argument
923  /// of the caller or callee.
925  FunctionInfo &FI = getFunctionInfo(*Arg.getParent());
926  return FI.CalledViaMustTail || FI.ContainsMustTailCall;
927  }
928 
929  /// Return the analysis result from a pass \p AP for function \p F.
930  template <typename AP>
931  typename AP::Result *getAnalysisResultForFunction(const Function &F) {
932  return AG.getAnalysis<AP>(F);
933  }
934 
935  /// Return SCC size on call graph for function \p F or 0 if unknown.
936  unsigned getSccSize(const Function &F) {
937  if (CGSCC && CGSCC->count(const_cast<Function *>(&F)))
938  return CGSCC->size();
939  return 0;
940  }
941 
942  /// Return datalayout used in the module.
943  const DataLayout &getDL() { return DL; }
944 
945  /// Return the map conaining all the knowledge we have from `llvm.assume`s.
946  const RetainedKnowledgeMap &getKnowledgeMap() const { return KnowledgeMap; }
947 
948  /// Return if \p To is potentially reachable form \p From or not
949  /// If the same query was answered, return cached result
951  auto KeyPair = std::make_pair(&From, &To);
952  auto Iter = PotentiallyReachableMap.find(KeyPair);
953  if (Iter != PotentiallyReachableMap.end())
954  return Iter->second;
955  const Function &F = *From.getFunction();
956  bool Result = isPotentiallyReachable(
957  &From, &To, nullptr, AG.getAnalysis<DominatorTreeAnalysis>(F),
958  AG.getAnalysis<LoopAnalysis>(F));
959  PotentiallyReachableMap.insert(std::make_pair(KeyPair, Result));
960  return Result;
961  }
962 
963  /// Check whether \p F is part of module slice.
964  bool isInModuleSlice(const Function &F) {
965  return ModuleSlice.count(const_cast<Function *>(&F));
966  }
967 
968 private:
969  struct FunctionInfo {
970  ~FunctionInfo();
971 
972  /// A nested map that remembers all instructions in a function with a
973  /// certain instruction opcode (Instruction::getOpcode()).
974  OpcodeInstMapTy OpcodeInstMap;
975 
976  /// A map from functions to their instructions that may read or write
977  /// memory.
978  InstructionVectorTy RWInsts;
979 
980  /// Function is called by a `musttail` call.
981  bool CalledViaMustTail;
982 
983  /// Function contains a `musttail` call.
984  bool ContainsMustTailCall;
985  };
986 
987  /// A map type from functions to informatio about it.
988  DenseMap<const Function *, FunctionInfo *> FuncInfoMap;
989 
990  /// Return information about the function \p F, potentially by creating it.
991  FunctionInfo &getFunctionInfo(const Function &F) {
992  FunctionInfo *&FI = FuncInfoMap[&F];
993  if (!FI) {
994  FI = new (Allocator) FunctionInfo();
995  initializeInformationCache(F, *FI);
996  }
997  return *FI;
998  }
999 
1000  /// Initialize the function information cache \p FI for the function \p F.
1001  ///
1002  /// This method needs to be called for all function that might be looked at
1003  /// through the information cache interface *prior* to looking at them.
1004  void initializeInformationCache(const Function &F, FunctionInfo &FI);
1005 
1006  /// The datalayout used in the module.
1007  const DataLayout &DL;
1008 
1009  /// The allocator used to allocate memory, e.g. for `FunctionInfo`s.
1010  BumpPtrAllocator &Allocator;
1011 
1012  /// MustBeExecutedContextExplorer
1013  MustBeExecutedContextExplorer Explorer;
1014 
1015  /// A map with knowledge retained in `llvm.assume` instructions.
1016  RetainedKnowledgeMap KnowledgeMap;
1017 
1018  /// Getters for analysis.
1019  AnalysisGetter &AG;
1020 
1021  /// The underlying CGSCC, or null if not available.
1022  SetVector<Function *> *CGSCC;
1023 
1024  /// Set of inlineable functions
1025  SmallPtrSet<const Function *, 8> InlineableFunctions;
1026 
1027  /// A map for caching results of queries for isPotentiallyReachable
1028  DenseMap<std::pair<const Instruction *, const Instruction *>, bool>
1029  PotentiallyReachableMap;
1030 
1031  /// Give the Attributor access to the members so
1032  /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them.
1033  friend struct Attributor;
1034 };
1035 
1036 /// The fixpoint analysis framework that orchestrates the attribute deduction.
1037 ///
1038 /// The Attributor provides a general abstract analysis framework (guided
1039 /// fixpoint iteration) as well as helper functions for the deduction of
1040 /// (LLVM-IR) attributes. However, also other code properties can be deduced,
1041 /// propagated, and ultimately manifested through the Attributor framework. This
1042 /// is particularly useful if these properties interact with attributes and a
1043 /// co-scheduled deduction allows to improve the solution. Even if not, thus if
1044 /// attributes/properties are completely isolated, they should use the
1045 /// Attributor framework to reduce the number of fixpoint iteration frameworks
1046 /// in the code base. Note that the Attributor design makes sure that isolated
1047 /// attributes are not impacted, in any way, by others derived at the same time
1048 /// if there is no cross-reasoning performed.
1049 ///
1050 /// The public facing interface of the Attributor is kept simple and basically
1051 /// allows abstract attributes to one thing, query abstract attributes
1052 /// in-flight. There are two reasons to do this:
1053 /// a) The optimistic state of one abstract attribute can justify an
1054 /// optimistic state of another, allowing to framework to end up with an
1055 /// optimistic (=best possible) fixpoint instead of one based solely on
1056 /// information in the IR.
1057 /// b) This avoids reimplementing various kinds of lookups, e.g., to check
1058 /// for existing IR attributes, in favor of a single lookups interface
1059 /// provided by an abstract attribute subclass.
1060 ///
1061 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
1062 /// described in the file comment.
1063 struct Attributor {
1064  /// Constructor
1065  ///
1066  /// \param Functions The set of functions we are deriving attributes for.
1067  /// \param InfoCache Cache to hold various information accessible for
1068  /// the abstract attributes.
1069  /// \param CGUpdater Helper to update an underlying call graph.
1070  /// \param Allowed If not null, a set limiting the attribute opportunities.
1071  /// \param DeleteFns Whether to delete functions
1073  CallGraphUpdater &CGUpdater,
1074  DenseSet<const char *> *Allowed = nullptr, bool DeleteFns = true)
1075  : Allocator(InfoCache.Allocator), Functions(Functions),
1076  InfoCache(InfoCache), CGUpdater(CGUpdater), Allowed(Allowed),
1077  DeleteFns(DeleteFns) {}
1078 
1079  ~Attributor();
1080 
1081  /// Run the analyses until a fixpoint is reached or enforced (timeout).
1082  ///
1083  /// The attributes registered with this Attributor can be used after as long
1084  /// as the Attributor is not destroyed (it owns the attributes now).
1085  ///
1086  /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED.
1087  ChangeStatus run();
1088 
1089  /// Lookup an abstract attribute of type \p AAType at position \p IRP. While
1090  /// no abstract attribute is found equivalent positions are checked, see
1091  /// SubsumingPositionIterator. Thus, the returned abstract attribute
1092  /// might be anchored at a different position, e.g., the callee if \p IRP is a
1093  /// call base.
1094  ///
1095  /// This method is the only (supported) way an abstract attribute can retrieve
1096  /// information from another abstract attribute. As an example, take an
1097  /// abstract attribute that determines the memory access behavior for a
1098  /// argument (readnone, readonly, ...). It should use `getAAFor` to get the
1099  /// most optimistic information for other abstract attributes in-flight, e.g.
1100  /// the one reasoning about the "captured" state for the argument or the one
1101  /// reasoning on the memory access behavior of the function as a whole.
1102  ///
1103  /// If the DepClass enum is set to `DepClassTy::None` the dependence from
1104  /// \p QueryingAA to the return abstract attribute is not automatically
1105  /// recorded. This should only be used if the caller will record the
1106  /// dependence explicitly if necessary, thus if it the returned abstract
1107  /// attribute is used for reasoning. To record the dependences explicitly use
1108  /// the `Attributor::recordDependence` method.
1109  template <typename AAType>
1110  const AAType &getAAFor(const AbstractAttribute &QueryingAA,
1111  const IRPosition &IRP, DepClassTy DepClass) {
1112  return getOrCreateAAFor<AAType>(IRP, &QueryingAA, DepClass,
1113  /* ForceUpdate */ false);
1114  }
1115 
1116  /// Similar to getAAFor but the return abstract attribute will be updated (via
1117  /// `AbstractAttribute::update`) even if it is found in the cache. This is
1118  /// especially useful for AAIsDead as changes in liveness can make updates
1119  /// possible/useful that were not happening before as the abstract attribute
1120  /// was assumed dead.
1121  template <typename AAType>
1122  const AAType &getAndUpdateAAFor(const AbstractAttribute &QueryingAA,
1123  const IRPosition &IRP, DepClassTy DepClass) {
1124  return getOrCreateAAFor<AAType>(IRP, &QueryingAA, DepClass,
1125  /* ForceUpdate */ true);
1126  }
1127 
1128  /// The version of getAAFor that allows to omit a querying abstract
1129  /// attribute. Using this after Attributor started running is restricted to
1130  /// only the Attributor itself. Initial seeding of AAs can be done via this
1131  /// function.
1132  /// NOTE: ForceUpdate is ignored in any stage other than the update stage.
1133  template <typename AAType>
1134  const AAType &
1136  DepClassTy DepClass, bool ForceUpdate = false) {
1137  if (!shouldPropagateCallBaseContext(IRP))
1138  IRP = IRP.stripCallBaseContext();
1139 
1140  if (AAType *AAPtr = lookupAAFor<AAType>(IRP, QueryingAA, DepClass,
1141  /* AllowInvalidState */ true)) {
1142  if (ForceUpdate && Phase == AttributorPhase::UPDATE)
1143  updateAA(*AAPtr);
1144  return *AAPtr;
1145  }
1146 
1147  // No matching attribute found, create one.
1148  // Use the static create method.
1149  auto &AA = AAType::createForPosition(IRP, *this);
1150 
1151  // If we are currenty seeding attributes, enforce seeding rules.
1152  if (Phase == AttributorPhase::SEEDING && !shouldSeedAttribute(AA)) {
1153  AA.getState().indicatePessimisticFixpoint();
1154  return AA;
1155  }
1156 
1157  registerAA(AA);
1158 
1159  // For now we ignore naked and optnone functions.
1160  bool Invalidate = Allowed && !Allowed->count(&AAType::ID);
1161  const Function *FnScope = IRP.getAnchorScope();
1162  if (FnScope)
1163  Invalidate |= FnScope->hasFnAttribute(Attribute::Naked) ||
1164  FnScope->hasFnAttribute(Attribute::OptimizeNone);
1165 
1166  // Avoid too many nested initializations to prevent a stack overflow.
1167  Invalidate |= InitializationChainLength > MaxInitializationChainLength;
1168 
1169  // Bootstrap the new attribute with an initial update to propagate
1170  // information, e.g., function -> call site. If it is not on a given
1171  // Allowed we will not perform updates at all.
1172  if (Invalidate) {
1173  AA.getState().indicatePessimisticFixpoint();
1174  return AA;
1175  }
1176 
1177  {
1178  TimeTraceScope TimeScope(AA.getName() + "::initialize");
1179  ++InitializationChainLength;
1180  AA.initialize(*this);
1181  --InitializationChainLength;
1182  }
1183 
1184  // Initialize and update is allowed for code outside of the current function
1185  // set, but only if it is part of module slice we are allowed to look at.
1186  // Only exception is AAIsDeadFunction whose initialization is prevented
1187  // directly, since we don't to compute it twice.
1188  if (FnScope && !Functions.count(const_cast<Function *>(FnScope))) {
1189  if (!getInfoCache().isInModuleSlice(*FnScope)) {
1190  AA.getState().indicatePessimisticFixpoint();
1191  return AA;
1192  }
1193  }
1194 
1195  // If this is queried in the manifest stage, we force the AA to indicate
1196  // pessimistic fixpoint immediately.
1197  if (Phase == AttributorPhase::MANIFEST) {
1198  AA.getState().indicatePessimisticFixpoint();
1199  return AA;
1200  }
1201 
1202  // Allow seeded attributes to declare dependencies.
1203  // Remember the seeding state.
1204  AttributorPhase OldPhase = Phase;
1205  Phase = AttributorPhase::UPDATE;
1206 
1207  updateAA(AA);
1208 
1209  Phase = OldPhase;
1210 
1211  if (QueryingAA && AA.getState().isValidState())
1212  recordDependence(AA, const_cast<AbstractAttribute &>(*QueryingAA),
1213  DepClass);
1214  return AA;
1215  }
1216  template <typename AAType>
1217  const AAType &getOrCreateAAFor(const IRPosition &IRP) {
1218  return getOrCreateAAFor<AAType>(IRP, /* QueryingAA */ nullptr,
1220  }
1221 
1222  /// Return the attribute of \p AAType for \p IRP if existing and valid. This
1223  /// also allows non-AA users lookup.
1224  template <typename AAType>
1225  AAType *lookupAAFor(const IRPosition &IRP,
1226  const AbstractAttribute *QueryingAA = nullptr,
1227  DepClassTy DepClass = DepClassTy::OPTIONAL,
1228  bool AllowInvalidState = false) {
1229  static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
1230  "Cannot query an attribute with a type not derived from "
1231  "'AbstractAttribute'!");
1232  // Lookup the abstract attribute of type AAType. If found, return it after
1233  // registering a dependence of QueryingAA on the one returned attribute.
1234  AbstractAttribute *AAPtr = AAMap.lookup({&AAType::ID, IRP});
1235  if (!AAPtr)
1236  return nullptr;
1237 
1238  AAType *AA = static_cast<AAType *>(AAPtr);
1239 
1240  // Do not register a dependence on an attribute with an invalid state.
1241  if (DepClass != DepClassTy::NONE && QueryingAA &&
1242  AA->getState().isValidState())
1243  recordDependence(*AA, const_cast<AbstractAttribute &>(*QueryingAA),
1244  DepClass);
1245 
1246  // Return nullptr if this attribute has an invalid state.
1247  if (!AllowInvalidState && !AA->getState().isValidState())
1248  return nullptr;
1249  return AA;
1250  }
1251 
1252  /// Explicitly record a dependence from \p FromAA to \p ToAA, that is if
1253  /// \p FromAA changes \p ToAA should be updated as well.
1254  ///
1255  /// This method should be used in conjunction with the `getAAFor` method and
1256  /// with the DepClass enum passed to the method set to None. This can
1257  /// be beneficial to avoid false dependences but it requires the users of
1258  /// `getAAFor` to explicitly record true dependences through this method.
1259  /// The \p DepClass flag indicates if the dependence is striclty necessary.
1260  /// That means for required dependences, if \p FromAA changes to an invalid
1261  /// state, \p ToAA can be moved to a pessimistic fixpoint because it required
1262  /// information from \p FromAA but none are available anymore.
1263  void recordDependence(const AbstractAttribute &FromAA,
1264  const AbstractAttribute &ToAA, DepClassTy DepClass);
1265 
1266  /// Introduce a new abstract attribute into the fixpoint analysis.
1267  ///
1268  /// Note that ownership of the attribute is given to the Attributor. It will
1269  /// invoke delete for the Attributor on destruction of the Attributor.
1270  ///
1271  /// Attributes are identified by their IR position (AAType::getIRPosition())
1272  /// and the address of their static member (see AAType::ID).
1273  template <typename AAType> AAType &registerAA(AAType &AA) {
1274  static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
1275  "Cannot register an attribute with a type not derived from "
1276  "'AbstractAttribute'!");
1277  // Put the attribute in the lookup map structure and the container we use to
1278  // keep track of all attributes.
1279  const IRPosition &IRP = AA.getIRPosition();
1280  AbstractAttribute *&AAPtr = AAMap[{&AAType::ID, IRP}];
1281 
1282  assert(!AAPtr && "Attribute already in map!");
1283  AAPtr = &AA;
1284 
1285  // Register AA with the synthetic root only before the manifest stage.
1286  if (Phase == AttributorPhase::SEEDING || Phase == AttributorPhase::UPDATE)
1287  DG.SyntheticRoot.Deps.push_back(
1289 
1290  return AA;
1291  }
1292 
1293  /// Return the internal information cache.
1294  InformationCache &getInfoCache() { return InfoCache; }
1295 
1296  /// Return true if this is a module pass, false otherwise.
1297  bool isModulePass() const {
1298  return !Functions.empty() &&
1299  Functions.size() == Functions.front()->getParent()->size();
1300  }
1301 
1302  /// Return true if we derive attributes for \p Fn
1303  bool isRunOn(Function &Fn) const {
1304  return Functions.empty() || Functions.count(&Fn);
1305  }
1306 
1307  /// Determine opportunities to derive 'default' attributes in \p F and create
1308  /// abstract attribute objects for them.
1309  ///
1310  /// \param F The function that is checked for attribute opportunities.
1311  ///
1312  /// Note that abstract attribute instances are generally created even if the
1313  /// IR already contains the information they would deduce. The most important
1314  /// reason for this is the single interface, the one of the abstract attribute
1315  /// instance, which can be queried without the need to look at the IR in
1316  /// various places.
1318 
1319  /// Determine whether the function \p F is IPO amendable
1320  ///
1321  /// If a function is exactly defined or it has alwaysinline attribute
1322  /// and is viable to be inlined, we say it is IPO amendable
1324  return F.hasExactDefinition() || InfoCache.InlineableFunctions.count(&F);
1325  }
1326 
1327  /// Mark the internal function \p F as live.
1328  ///
1329  /// This will trigger the identification and initialization of attributes for
1330  /// \p F.
1332  assert(F.hasLocalLinkage() &&
1333  "Only local linkage is assumed dead initially.");
1334 
1336  }
1337 
1338  /// Helper function to remove callsite.
1340  if (!CI)
1341  return;
1342 
1343  CGUpdater.removeCallSite(*CI);
1344  }
1345 
1346  /// Record that \p U is to be replaces with \p NV after information was
1347  /// manifested. This also triggers deletion of trivially dead istructions.
1349  Value *&V = ToBeChangedUses[&U];
1350  if (V && (V->stripPointerCasts() == NV.stripPointerCasts() ||
1351  isa_and_nonnull<UndefValue>(V)))
1352  return false;
1353  assert((!V || V == &NV || isa<UndefValue>(NV)) &&
1354  "Use was registered twice for replacement with different values!");
1355  V = &NV;
1356  return true;
1357  }
1358 
1359  /// Helper function to replace all uses of \p V with \p NV. Return true if
1360  /// there is any change. The flag \p ChangeDroppable indicates if dropppable
1361  /// uses should be changed too.
1363  bool ChangeDroppable = true) {
1364  bool Changed = false;
1365  for (auto &U : V.uses())
1366  if (ChangeDroppable || !U.getUser()->isDroppable())
1367  Changed |= changeUseAfterManifest(U, NV);
1368 
1369  return Changed;
1370  }
1371 
1372  /// Record that \p I is to be replaced with `unreachable` after information
1373  /// was manifested.
1375  ToBeChangedToUnreachableInsts.insert(I);
1376  }
1377 
1378  /// Record that \p II has at least one dead successor block. This information
1379  /// is used, e.g., to replace \p II with a call, after information was
1380  /// manifested.
1382  InvokeWithDeadSuccessor.push_back(&II);
1383  }
1384 
1385  /// Record that \p I is deleted after information was manifested. This also
1386  /// triggers deletion of trivially dead istructions.
1387  void deleteAfterManifest(Instruction &I) { ToBeDeletedInsts.insert(&I); }
1388 
1389  /// Record that \p BB is deleted after information was manifested. This also
1390  /// triggers deletion of trivially dead istructions.
1391  void deleteAfterManifest(BasicBlock &BB) { ToBeDeletedBlocks.insert(&BB); }
1392 
1393  /// Record that \p F is deleted after information was manifested.
1395  if (DeleteFns)
1396  ToBeDeletedFunctions.insert(&F);
1397  }
1398 
1399  /// If \p V is assumed to be a constant, return it, if it is unclear yet,
1400  /// return None, otherwise return `nullptr`.
1402  const AbstractAttribute &AA,
1403  bool &UsedAssumedInformation);
1404 
1405  /// Return true if \p AA (or its context instruction) is assumed dead.
1406  ///
1407  /// If \p LivenessAA is not provided it is queried.
1408  bool isAssumedDead(const AbstractAttribute &AA, const AAIsDead *LivenessAA,
1409  bool CheckBBLivenessOnly = false,
1410  DepClassTy DepClass = DepClassTy::OPTIONAL);
1411 
1412  /// Return true if \p I is assumed dead.
1413  ///
1414  /// If \p LivenessAA is not provided it is queried.
1415  bool isAssumedDead(const Instruction &I, const AbstractAttribute *QueryingAA,
1416  const AAIsDead *LivenessAA,
1417  bool CheckBBLivenessOnly = false,
1418  DepClassTy DepClass = DepClassTy::OPTIONAL);
1419 
1420  /// Return true if \p U is assumed dead.
1421  ///
1422  /// If \p FnLivenessAA is not provided it is queried.
1423  bool isAssumedDead(const Use &U, const AbstractAttribute *QueryingAA,
1424  const AAIsDead *FnLivenessAA,
1425  bool CheckBBLivenessOnly = false,
1426  DepClassTy DepClass = DepClassTy::OPTIONAL);
1427 
1428  /// Return true if \p IRP is assumed dead.
1429  ///
1430  /// If \p FnLivenessAA is not provided it is queried.
1431  bool isAssumedDead(const IRPosition &IRP, const AbstractAttribute *QueryingAA,
1432  const AAIsDead *FnLivenessAA,
1433  bool CheckBBLivenessOnly = false,
1434  DepClassTy DepClass = DepClassTy::OPTIONAL);
1435 
1436  /// Check \p Pred on all (transitive) uses of \p V.
1437  ///
1438  /// This method will evaluate \p Pred on all (transitive) uses of the
1439  /// associated value and return true if \p Pred holds every time.
1440  bool checkForAllUses(function_ref<bool(const Use &, bool &)> Pred,
1441  const AbstractAttribute &QueryingAA, const Value &V,
1442  DepClassTy LivenessDepClass = DepClassTy::OPTIONAL);
1443 
1444  /// Helper struct used in the communication between an abstract attribute (AA)
1445  /// that wants to change the signature of a function and the Attributor which
1446  /// applies the changes. The struct is partially initialized with the
1447  /// information from the AA (see the constructor). All other members are
1448  /// provided by the Attributor prior to invoking any callbacks.
1450  /// Callee repair callback type
1451  ///
1452  /// The function repair callback is invoked once to rewire the replacement
1453  /// arguments in the body of the new function. The argument replacement info
1454  /// is passed, as build from the registerFunctionSignatureRewrite call, as
1455  /// well as the replacement function and an iteratore to the first
1456  /// replacement argument.
1457  using CalleeRepairCBTy = std::function<void(
1459 
1460  /// Abstract call site (ACS) repair callback type
1461  ///
1462  /// The abstract call site repair callback is invoked once on every abstract
1463  /// call site of the replaced function (\see ReplacedFn). The callback needs
1464  /// to provide the operands for the call to the new replacement function.
1465  /// The number and type of the operands appended to the provided vector
1466  /// (second argument) is defined by the number and types determined through
1467  /// the replacement type vector (\see ReplacementTypes). The first argument
1468  /// is the ArgumentReplacementInfo object registered with the Attributor
1469  /// through the registerFunctionSignatureRewrite call.
1470  using ACSRepairCBTy =
1473 
1474  /// Simple getters, see the corresponding members for details.
1475  ///{
1476 
1477  Attributor &getAttributor() const { return A; }
1478  const Function &getReplacedFn() const { return ReplacedFn; }
1479  const Argument &getReplacedArg() const { return ReplacedArg; }
1480  unsigned getNumReplacementArgs() const { return ReplacementTypes.size(); }
1482  return ReplacementTypes;
1483  }
1484 
1485  ///}
1486 
1487  private:
1488  /// Constructor that takes the argument to be replaced, the types of
1489  /// the replacement arguments, as well as callbacks to repair the call sites
1490  /// and new function after the replacement happened.
1492  ArrayRef<Type *> ReplacementTypes,
1493  CalleeRepairCBTy &&CalleeRepairCB,
1494  ACSRepairCBTy &&ACSRepairCB)
1495  : A(A), ReplacedFn(*Arg.getParent()), ReplacedArg(Arg),
1496  ReplacementTypes(ReplacementTypes.begin(), ReplacementTypes.end()),
1497  CalleeRepairCB(std::move(CalleeRepairCB)),
1498  ACSRepairCB(std::move(ACSRepairCB)) {}
1499 
1500  /// Reference to the attributor to allow access from the callbacks.
1501  Attributor &A;
1502 
1503  /// The "old" function replaced by ReplacementFn.
1504  const Function &ReplacedFn;
1505 
1506  /// The "old" argument replaced by new ones defined via ReplacementTypes.
1507  const Argument &ReplacedArg;
1508 
1509  /// The types of the arguments replacing ReplacedArg.
1510  const SmallVector<Type *, 8> ReplacementTypes;
1511 
1512  /// Callee repair callback, see CalleeRepairCBTy.
1513  const CalleeRepairCBTy CalleeRepairCB;
1514 
1515  /// Abstract call site (ACS) repair callback, see ACSRepairCBTy.
1516  const ACSRepairCBTy ACSRepairCB;
1517 
1518  /// Allow access to the private members from the Attributor.
1519  friend struct Attributor;
1520  };
1521 
1522  /// Check if we can rewrite a function signature.
1523  ///
1524  /// The argument \p Arg is replaced with new ones defined by the number,
1525  /// order, and types in \p ReplacementTypes.
1526  ///
1527  /// \returns True, if the replacement can be registered, via
1528  /// registerFunctionSignatureRewrite, false otherwise.
1530  ArrayRef<Type *> ReplacementTypes);
1531 
1532  /// Register a rewrite for a function signature.
1533  ///
1534  /// The argument \p Arg is replaced with new ones defined by the number,
1535  /// order, and types in \p ReplacementTypes. The rewiring at the call sites is
1536  /// done through \p ACSRepairCB and at the callee site through
1537  /// \p CalleeRepairCB.
1538  ///
1539  /// \returns True, if the replacement was registered, false otherwise.
1541  Argument &Arg, ArrayRef<Type *> ReplacementTypes,
1544 
1545  /// Check \p Pred on all function call sites.
1546  ///
1547  /// This method will evaluate \p Pred on call sites and return
1548  /// true if \p Pred holds in every call sites. However, this is only possible
1549  /// all call sites are known, hence the function has internal linkage.
1550  /// If true is returned, \p AllCallSitesKnown is set if all possible call
1551  /// sites of the function have been visited.
1553  const AbstractAttribute &QueryingAA,
1554  bool RequireAllCallSites, bool &AllCallSitesKnown);
1555 
1556  /// Check \p Pred on all values potentially returned by \p F.
1557  ///
1558  /// This method will evaluate \p Pred on all values potentially returned by
1559  /// the function associated with \p QueryingAA. The returned values are
1560  /// matched with their respective return instructions. Returns true if \p Pred
1561  /// holds on all of them.
1563  function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> Pred,
1564  const AbstractAttribute &QueryingAA);
1565 
1566  /// Check \p Pred on all values potentially returned by the function
1567  /// associated with \p QueryingAA.
1568  ///
1569  /// This is the context insensitive version of the method above.
1570  bool checkForAllReturnedValues(function_ref<bool(Value &)> Pred,
1571  const AbstractAttribute &QueryingAA);
1572 
1573  /// Check \p Pred on all instructions with an opcode present in \p Opcodes.
1574  ///
1575  /// This method will evaluate \p Pred on all instructions with an opcode
1576  /// present in \p Opcode and return true if \p Pred holds on all of them.
1578  const AbstractAttribute &QueryingAA,
1579  const ArrayRef<unsigned> &Opcodes,
1580  bool CheckBBLivenessOnly = false);
1581 
1582  /// Check \p Pred on all call-like instructions (=CallBased derived).
1583  ///
1584  /// See checkForAllCallLikeInstructions(...) for more information.
1586  const AbstractAttribute &QueryingAA) {
1587  return checkForAllInstructions(Pred, QueryingAA,
1588  {(unsigned)Instruction::Invoke,
1589  (unsigned)Instruction::CallBr,
1590  (unsigned)Instruction::Call});
1591  }
1592 
1593  /// Check \p Pred on all Read/Write instructions.
1594  ///
1595  /// This method will evaluate \p Pred on all instructions that read or write
1596  /// to memory present in the information cache and return true if \p Pred
1597  /// holds on all of them.
1599  AbstractAttribute &QueryingAA);
1600 
1601  /// Create a shallow wrapper for \p F such that \p F has internal linkage
1602  /// afterwards. It also sets the original \p F 's name to anonymous
1603  ///
1604  /// A wrapper is a function with the same type (and attributes) as \p F
1605  /// that will only call \p F and return the result, if any.
1606  ///
1607  /// Assuming the declaration of looks like:
1608  /// rty F(aty0 arg0, ..., atyN argN);
1609  ///
1610  /// The wrapper will then look as follows:
1611  /// rty wrapper(aty0 arg0, ..., atyN argN) {
1612  /// return F(arg0, ..., argN);
1613  /// }
1614  ///
1615  static void createShallowWrapper(Function &F);
1616 
1617  /// Return the data layout associated with the anchor scope.
1618  const DataLayout &getDataLayout() const { return InfoCache.DL; }
1619 
1620  /// The allocator used to allocate memory, e.g. for `AbstractAttribute`s.
1622 
1623 private:
1624  /// This method will do fixpoint iteration until fixpoint or the
1625  /// maximum iteration count is reached.
1626  ///
1627  /// If the maximum iteration count is reached, This method will
1628  /// indicate pessimistic fixpoint on attributes that transitively depend
1629  /// on attributes that were scheduled for an update.
1630  void runTillFixpoint();
1631 
1632  /// Gets called after scheduling, manifests attributes to the LLVM IR.
1633  ChangeStatus manifestAttributes();
1634 
1635  /// Gets called after attributes have been manifested, cleans up the IR.
1636  /// Deletes dead functions, blocks and instructions.
1637  /// Rewrites function signitures and updates the call graph.
1638  ChangeStatus cleanupIR();
1639 
1640  /// Identify internal functions that are effectively dead, thus not reachable
1641  /// from a live entry point. The functions are added to ToBeDeletedFunctions.
1642  void identifyDeadInternalFunctions();
1643 
1644  /// Run `::update` on \p AA and track the dependences queried while doing so.
1645  /// Also adjust the state if we know further updates are not necessary.
1646  ChangeStatus updateAA(AbstractAttribute &AA);
1647 
1648  /// Remember the dependences on the top of the dependence stack such that they
1649  /// may trigger further updates. (\see DependenceStack)
1650  void rememberDependences();
1651 
1652  /// Check \p Pred on all call sites of \p Fn.
1653  ///
1654  /// This method will evaluate \p Pred on call sites and return
1655  /// true if \p Pred holds in every call sites. However, this is only possible
1656  /// all call sites are known, hence the function has internal linkage.
1657  /// If true is returned, \p AllCallSitesKnown is set if all possible call
1658  /// sites of the function have been visited.
1660  const Function &Fn, bool RequireAllCallSites,
1661  const AbstractAttribute *QueryingAA,
1662  bool &AllCallSitesKnown);
1663 
1664  /// Determine if CallBase context in \p IRP should be propagated.
1665  bool shouldPropagateCallBaseContext(const IRPosition &IRP);
1666 
1667  /// Apply all requested function signature rewrites
1668  /// (\see registerFunctionSignatureRewrite) and return Changed if the module
1669  /// was altered.
1670  ChangeStatus
1671  rewriteFunctionSignatures(SmallPtrSetImpl<Function *> &ModifiedFns);
1672 
1673  /// Check if the Attribute \p AA should be seeded.
1674  /// See getOrCreateAAFor.
1675  bool shouldSeedAttribute(AbstractAttribute &AA);
1676 
1677  /// A nested map to lookup abstract attributes based on the argument position
1678  /// on the outer level, and the addresses of the static member (AAType::ID) on
1679  /// the inner level.
1680  ///{
1681  using AAMapKeyTy = std::pair<const char *, IRPosition>;
1683  ///}
1684 
1685  /// Map to remember all requested signature changes (= argument replacements).
1687  ArgumentReplacementMap;
1688 
1689  /// The set of functions we are deriving attributes for.
1690  SetVector<Function *> &Functions;
1691 
1692  /// The information cache that holds pre-processed (LLVM-IR) information.
1693  InformationCache &InfoCache;
1694 
1695  /// Helper to update an underlying call graph.
1696  CallGraphUpdater &CGUpdater;
1697 
1698  /// Abstract Attribute dependency graph
1699  AADepGraph DG;
1700 
1701  /// Set of functions for which we modified the content such that it might
1702  /// impact the call graph.
1703  SmallPtrSet<Function *, 8> CGModifiedFunctions;
1704 
1705  /// Information about a dependence. If FromAA is changed ToAA needs to be
1706  /// updated as well.
1707  struct DepInfo {
1708  const AbstractAttribute *FromAA;
1709  const AbstractAttribute *ToAA;
1710  DepClassTy DepClass;
1711  };
1712 
1713  /// The dependence stack is used to track dependences during an
1714  /// `AbstractAttribute::update` call. As `AbstractAttribute::update` can be
1715  /// recursive we might have multiple vectors of dependences in here. The stack
1716  /// size, should be adjusted according to the expected recursion depth and the
1717  /// inner dependence vector size to the expected number of dependences per
1718  /// abstract attribute. Since the inner vectors are actually allocated on the
1719  /// stack we can be generous with their size.
1720  using DependenceVector = SmallVector<DepInfo, 8>;
1721  SmallVector<DependenceVector *, 16> DependenceStack;
1722 
1723  /// If not null, a set limiting the attribute opportunities.
1724  const DenseSet<const char *> *Allowed;
1725 
1726  /// Whether to delete functions.
1727  const bool DeleteFns;
1728 
1729  /// A set to remember the functions we already assume to be live and visited.
1730  DenseSet<const Function *> VisitedFunctions;
1731 
1732  /// Uses we replace with a new value after manifest is done. We will remove
1733  /// then trivially dead instructions as well.
1734  DenseMap<Use *, Value *> ToBeChangedUses;
1735 
1736  /// Instructions we replace with `unreachable` insts after manifest is done.
1737  SmallDenseSet<WeakVH, 16> ToBeChangedToUnreachableInsts;
1738 
1739  /// Invoke instructions with at least a single dead successor block.
1740  SmallVector<WeakVH, 16> InvokeWithDeadSuccessor;
1741 
1742  /// A flag that indicates which stage of the process we are in. Initially, the
1743  /// phase is SEEDING. Phase is changed in `Attributor::run()`
1744  enum class AttributorPhase {
1745  SEEDING,
1746  UPDATE,
1747  MANIFEST,
1748  CLEANUP,
1749  } Phase = AttributorPhase::SEEDING;
1750 
1751  /// The current initialization chain length. Tracked to avoid stack overflows.
1752  unsigned InitializationChainLength = 0;
1753 
1754  /// Functions, blocks, and instructions we delete after manifest is done.
1755  ///
1756  ///{
1757  SmallPtrSet<Function *, 8> ToBeDeletedFunctions;
1758  SmallPtrSet<BasicBlock *, 8> ToBeDeletedBlocks;
1759  SmallDenseSet<WeakVH, 8> ToBeDeletedInsts;
1760  ///}
1761 
1762  friend AADepGraph;
1763 };
1764 
1765 /// An interface to query the internal state of an abstract attribute.
1766 ///
1767 /// The abstract state is a minimal interface that allows the Attributor to
1768 /// communicate with the abstract attributes about their internal state without
1769 /// enforcing or exposing implementation details, e.g., the (existence of an)
1770 /// underlying lattice.
1771 ///
1772 /// It is sufficient to be able to query if a state is (1) valid or invalid, (2)
1773 /// at a fixpoint, and to indicate to the state that (3) an optimistic fixpoint
1774 /// was reached or (4) a pessimistic fixpoint was enforced.
1775 ///
1776 /// All methods need to be implemented by the subclass. For the common use case,
1777 /// a single boolean state or a bit-encoded state, the BooleanState and
1778 /// {Inc,Dec,Bit}IntegerState classes are already provided. An abstract
1779 /// attribute can inherit from them to get the abstract state interface and
1780 /// additional methods to directly modify the state based if needed. See the
1781 /// class comments for help.
1783  virtual ~AbstractState() {}
1784 
1785  /// Return if this abstract state is in a valid state. If false, no
1786  /// information provided should be used.
1787  virtual bool isValidState() const = 0;
1788 
1789  /// Return if this abstract state is fixed, thus does not need to be updated
1790  /// if information changes as it cannot change itself.
1791  virtual bool isAtFixpoint() const = 0;
1792 
1793  /// Indicate that the abstract state should converge to the optimistic state.
1794  ///
1795  /// This will usually make the optimistically assumed state the known to be
1796  /// true state.
1797  ///
1798  /// \returns ChangeStatus::UNCHANGED as the assumed value should not change.
1800 
1801  /// Indicate that the abstract state should converge to the pessimistic state.
1802  ///
1803  /// This will usually revert the optimistically assumed state to the known to
1804  /// be true state.
1805  ///
1806  /// \returns ChangeStatus::CHANGED as the assumed value may change.
1808 };
1809 
1810 /// Simple state with integers encoding.
1811 ///
1812 /// The interface ensures that the assumed bits are always a subset of the known
1813 /// bits. Users can only add known bits and, except through adding known bits,
1814 /// they can only remove assumed bits. This should guarantee monotoniticy and
1815 /// thereby the existence of a fixpoint (if used corretly). The fixpoint is
1816 /// reached when the assumed and known state/bits are equal. Users can
1817 /// force/inidicate a fixpoint. If an optimistic one is indicated, the known
1818 /// state will catch up with the assumed one, for a pessimistic fixpoint it is
1819 /// the other way around.
1820 template <typename base_ty, base_ty BestState, base_ty WorstState>
1822  using base_t = base_ty;
1823 
1826 
1827  /// Return the best possible representable state.
1828  static constexpr base_t getBestState() { return BestState; }
1829  static constexpr base_t getBestState(const IntegerStateBase &) {
1830  return getBestState();
1831  }
1832 
1833  /// Return the worst possible representable state.
1834  static constexpr base_t getWorstState() { return WorstState; }
1835  static constexpr base_t getWorstState(const IntegerStateBase &) {
1836  return getWorstState();
1837  }
1838 
1839  /// See AbstractState::isValidState()
1840  /// NOTE: For now we simply pretend that the worst possible state is invalid.
1841  bool isValidState() const override { return Assumed != getWorstState(); }
1842 
1843  /// See AbstractState::isAtFixpoint()
1844  bool isAtFixpoint() const override { return Assumed == Known; }
1845 
1846  /// See AbstractState::indicateOptimisticFixpoint(...)
1848  Known = Assumed;
1849  return ChangeStatus::UNCHANGED;
1850  }
1851 
1852  /// See AbstractState::indicatePessimisticFixpoint(...)
1854  Assumed = Known;
1855  return ChangeStatus::CHANGED;
1856  }
1857 
1858  /// Return the known state encoding
1859  base_t getKnown() const { return Known; }
1860 
1861  /// Return the assumed state encoding.
1862  base_t getAssumed() const { return Assumed; }
1863 
1864  /// Equality for IntegerStateBase.
1865  bool
1867  return this->getAssumed() == R.getAssumed() &&
1868  this->getKnown() == R.getKnown();
1869  }
1870 
1871  /// Inequality for IntegerStateBase.
1872  bool
1874  return !(*this == R);
1875  }
1876 
1877  /// "Clamp" this state with \p R. The result is subtype dependent but it is
1878  /// intended that only information assumed in both states will be assumed in
1879  /// this one afterwards.
1881  handleNewAssumedValue(R.getAssumed());
1882  }
1883 
1884  /// "Clamp" this state with \p R. The result is subtype dependent but it is
1885  /// intended that information known in either state will be known in
1886  /// this one afterwards.
1888  handleNewKnownValue(R.getKnown());
1889  }
1890 
1892  joinOR(R.getAssumed(), R.getKnown());
1893  }
1894 
1896  joinAND(R.getAssumed(), R.getKnown());
1897  }
1898 
1899 protected:
1900  /// Handle a new assumed value \p Value. Subtype dependent.
1901  virtual void handleNewAssumedValue(base_t Value) = 0;
1902 
1903  /// Handle a new known value \p Value. Subtype dependent.
1904  virtual void handleNewKnownValue(base_t Value) = 0;
1905 
1906  /// Handle a value \p Value. Subtype dependent.
1907  virtual void joinOR(base_t AssumedValue, base_t KnownValue) = 0;
1908 
1909  /// Handle a new assumed value \p Value. Subtype dependent.
1910  virtual void joinAND(base_t AssumedValue, base_t KnownValue) = 0;
1911 
1912  /// The known state encoding in an integer of type base_t.
1914 
1915  /// The assumed state encoding in an integer of type base_t.
1917 };
1918 
1919 /// Specialization of the integer state for a bit-wise encoding.
1920 template <typename base_ty = uint32_t, base_ty BestState = ~base_ty(0),
1921  base_ty WorstState = 0>
1923  : public IntegerStateBase<base_ty, BestState, WorstState> {
1924  using base_t = base_ty;
1925 
1926  /// Return true if the bits set in \p BitsEncoding are "known bits".
1927  bool isKnown(base_t BitsEncoding) const {
1928  return (this->Known & BitsEncoding) == BitsEncoding;
1929  }
1930 
1931  /// Return true if the bits set in \p BitsEncoding are "assumed bits".
1932  bool isAssumed(base_t BitsEncoding) const {
1933  return (this->Assumed & BitsEncoding) == BitsEncoding;
1934  }
1935 
1936  /// Add the bits in \p BitsEncoding to the "known bits".
1938  // Make sure we never miss any "known bits".
1939  this->Assumed |= Bits;
1940  this->Known |= Bits;
1941  return *this;
1942  }
1943 
1944  /// Remove the bits in \p BitsEncoding from the "assumed bits" if not known.
1946  return intersectAssumedBits(~BitsEncoding);
1947  }
1948 
1949  /// Remove the bits in \p BitsEncoding from the "known bits".
1951  this->Known = (this->Known & ~BitsEncoding);
1952  return *this;
1953  }
1954 
1955  /// Keep only "assumed bits" also set in \p BitsEncoding but all known ones.
1957  // Make sure we never loose any "known bits".
1958  this->Assumed = (this->Assumed & BitsEncoding) | this->Known;
1959  return *this;
1960  }
1961 
1962 private:
1963  void handleNewAssumedValue(base_t Value) override {
1965  }
1966  void handleNewKnownValue(base_t Value) override { addKnownBits(Value); }
1967  void joinOR(base_t AssumedValue, base_t KnownValue) override {
1968  this->Known |= KnownValue;
1969  this->Assumed |= AssumedValue;
1970  }
1971  void joinAND(base_t AssumedValue, base_t KnownValue) override {
1972  this->Known &= KnownValue;
1973  this->Assumed &= AssumedValue;
1974  }
1975 };
1976 
1977 /// Specialization of the integer state for an increasing value, hence ~0u is
1978 /// the best state and 0 the worst.
1979 template <typename base_ty = uint32_t, base_ty BestState = ~base_ty(0),
1980  base_ty WorstState = 0>
1982  : public IntegerStateBase<base_ty, BestState, WorstState> {
1984  using base_t = base_ty;
1985 
1988 
1989  /// Return the best possible representable state.
1990  static constexpr base_t getBestState() { return BestState; }
1991  static constexpr base_t
1993  return getBestState();
1994  }
1995 
1996  /// Take minimum of assumed and \p Value.
1998  // Make sure we never loose "known value".
1999  this->Assumed = std::max(std::min(this->Assumed, Value), this->Known);
2000  return *this;
2001  }
2002 
2003  /// Take maximum of known and \p Value.
2005  // Make sure we never loose "known value".
2006  this->Assumed = std::max(Value, this->Assumed);
2007  this->Known = std::max(Value, this->Known);
2008  return *this;
2009  }
2010 
2011 private:
2012  void handleNewAssumedValue(base_t Value) override {
2014  }
2015  void handleNewKnownValue(base_t Value) override { takeKnownMaximum(Value); }
2016  void joinOR(base_t AssumedValue, base_t KnownValue) override {
2017  this->Known = std::max(this->Known, KnownValue);
2018  this->Assumed = std::max(this->Assumed, AssumedValue);
2019  }
2020  void joinAND(base_t AssumedValue, base_t KnownValue) override {
2021  this->Known = std::min(this->Known, KnownValue);
2022  this->Assumed = std::min(this->Assumed, AssumedValue);
2023  }
2024 };
2025 
2026 /// Specialization of the integer state for a decreasing value, hence 0 is the
2027 /// best state and ~0u the worst.
2028 template <typename base_ty = uint32_t>
2029 struct DecIntegerState : public IntegerStateBase<base_ty, 0, ~base_ty(0)> {
2030  using base_t = base_ty;
2031 
2032  /// Take maximum of assumed and \p Value.
2034  // Make sure we never loose "known value".
2035  this->Assumed = std::min(std::max(this->Assumed, Value), this->Known);
2036  return *this;
2037  }
2038 
2039  /// Take minimum of known and \p Value.
2041  // Make sure we never loose "known value".
2042  this->Assumed = std::min(Value, this->Assumed);
2043  this->Known = std::min(Value, this->Known);
2044  return *this;
2045  }
2046 
2047 private:
2048  void handleNewAssumedValue(base_t Value) override {
2050  }
2051  void handleNewKnownValue(base_t Value) override { takeKnownMinimum(Value); }
2052  void joinOR(base_t AssumedValue, base_t KnownValue) override {
2053  this->Assumed = std::min(this->Assumed, KnownValue);
2054  this->Assumed = std::min(this->Assumed, AssumedValue);
2055  }
2056  void joinAND(base_t AssumedValue, base_t KnownValue) override {
2057  this->Assumed = std::max(this->Assumed, KnownValue);
2058  this->Assumed = std::max(this->Assumed, AssumedValue);
2059  }
2060 };
2061 
2062 /// Simple wrapper for a single bit (boolean) state.
2063 struct BooleanState : public IntegerStateBase<bool, 1, 0> {
2066 
2069 
2070  /// Set the assumed value to \p Value but never below the known one.
2071  void setAssumed(bool Value) { Assumed &= (Known | Value); }
2072 
2073  /// Set the known and asssumed value to \p Value.
2074  void setKnown(bool Value) {
2075  Known |= Value;
2076  Assumed |= Value;
2077  }
2078 
2079  /// Return true if the state is assumed to hold.
2080  bool isAssumed() const { return getAssumed(); }
2081 
2082  /// Return true if the state is known to hold.
2083  bool isKnown() const { return getKnown(); }
2084 
2085 private:
2086  void handleNewAssumedValue(base_t Value) override {
2087  if (!Value)
2088  Assumed = Known;
2089  }
2090  void handleNewKnownValue(base_t Value) override {
2091  if (Value)
2092  Known = (Assumed = Value);
2093  }
2094  void joinOR(base_t AssumedValue, base_t KnownValue) override {
2095  Known |= KnownValue;
2096  Assumed |= AssumedValue;
2097  }
2098  void joinAND(base_t AssumedValue, base_t KnownValue) override {
2099  Known &= KnownValue;
2100  Assumed &= AssumedValue;
2101  }
2102 };
2103 
2104 /// State for an integer range.
2106 
2107  /// Bitwidth of the associated value.
2109 
2110  /// State representing assumed range, initially set to empty.
2112 
2113  /// State representing known range, initially set to [-inf, inf].
2115 
2118  Known(ConstantRange::getFull(BitWidth)) {}
2119 
2121  : BitWidth(CR.getBitWidth()), Assumed(CR),
2122  Known(getWorstState(CR.getBitWidth())) {}
2123 
2124  /// Return the worst possible representable state.
2126  return ConstantRange::getFull(BitWidth);
2127  }
2128 
2129  /// Return the best possible representable state.
2131  return ConstantRange::getEmpty(BitWidth);
2132  }
2134  return getBestState(IRS.getBitWidth());
2135  }
2136 
2137  /// Return associated values' bit width.
2138  uint32_t getBitWidth() const { return BitWidth; }
2139 
2140  /// See AbstractState::isValidState()
2141  bool isValidState() const override {
2142  return BitWidth > 0 && !Assumed.isFullSet();
2143  }
2144 
2145  /// See AbstractState::isAtFixpoint()
2146  bool isAtFixpoint() const override { return Assumed == Known; }
2147 
2148  /// See AbstractState::indicateOptimisticFixpoint(...)
2150  Known = Assumed;
2151  return ChangeStatus::CHANGED;
2152  }
2153 
2154  /// See AbstractState::indicatePessimisticFixpoint(...)
2156  Assumed = Known;
2157  return ChangeStatus::CHANGED;
2158  }
2159 
2160  /// Return the known state encoding
2161  ConstantRange getKnown() const { return Known; }
2162 
2163  /// Return the assumed state encoding.
2164  ConstantRange getAssumed() const { return Assumed; }
2165 
2166  /// Unite assumed range with the passed state.
2167  void unionAssumed(const ConstantRange &R) {
2168  // Don't loose a known range.
2170  }
2171 
2172  /// See IntegerRangeState::unionAssumed(..).
2174  unionAssumed(R.getAssumed());
2175  }
2176 
2177  /// Unite known range with the passed state.
2178  void unionKnown(const ConstantRange &R) {
2179  // Don't loose a known range.
2180  Known = Known.unionWith(R);
2182  }
2183 
2184  /// See IntegerRangeState::unionKnown(..).
2185  void unionKnown(const IntegerRangeState &R) { unionKnown(R.getKnown()); }
2186 
2187  /// Intersect known range with the passed state.
2190  Known = Known.intersectWith(R);
2191  }
2192 
2193  /// See IntegerRangeState::intersectKnown(..).
2195  intersectKnown(R.getKnown());
2196  }
2197 
2198  /// Equality for IntegerRangeState.
2199  bool operator==(const IntegerRangeState &R) const {
2200  return getAssumed() == R.getAssumed() && getKnown() == R.getKnown();
2201  }
2202 
2203  /// "Clamp" this state with \p R. The result is subtype dependent but it is
2204  /// intended that only information assumed in both states will be assumed in
2205  /// this one afterwards.
2207  // NOTE: `^=` operator seems like `intersect` but in this case, we need to
2208  // take `union`.
2209  unionAssumed(R);
2210  return *this;
2211  }
2212 
2214  // NOTE: `&=` operator seems like `intersect` but in this case, we need to
2215  // take `union`.
2216  unionKnown(R);
2217  unionAssumed(R);
2218  return *this;
2219  }
2220 };
2221 /// Helper struct necessary as the modular build fails if the virtual method
2222 /// IRAttribute::manifest is defined in the Attributor.cpp.
2224  static ChangeStatus manifestAttrs(Attributor &A, const IRPosition &IRP,
2225  const ArrayRef<Attribute> &DeducedAttrs);
2226 };
2227 
2228 /// Helper to tie a abstract state implementation to an abstract attribute.
2229 template <typename StateTy, typename BaseType, class... Ts>
2230 struct StateWrapper : public BaseType, public StateTy {
2231  /// Provide static access to the type of the state.
2233 
2234  StateWrapper(const IRPosition &IRP, Ts... Args)
2235  : BaseType(IRP), StateTy(Args...) {}
2236 
2237  /// See AbstractAttribute::getState(...).
2238  StateType &getState() override { return *this; }
2239 
2240  /// See AbstractAttribute::getState(...).
2241  const StateType &getState() const override { return *this; }
2242 };
2243 
2244 /// Helper class that provides common functionality to manifest IR attributes.
2245 template <Attribute::AttrKind AK, typename BaseType>
2246 struct IRAttribute : public BaseType {
2247  IRAttribute(const IRPosition &IRP) : BaseType(IRP) {}
2248 
2249  /// See AbstractAttribute::initialize(...).
2250  virtual void initialize(Attributor &A) override {
2251  const IRPosition &IRP = this->getIRPosition();
2252  if (isa<UndefValue>(IRP.getAssociatedValue()) ||
2253  this->hasAttr(getAttrKind(), /* IgnoreSubsumingPositions */ false,
2254  &A)) {
2255  this->getState().indicateOptimisticFixpoint();
2256  return;
2257  }
2258 
2259  bool IsFnInterface = IRP.isFnInterfaceKind();
2260  const Function *FnScope = IRP.getAnchorScope();
2261  // TODO: Not all attributes require an exact definition. Find a way to
2262  // enable deduction for some but not all attributes in case the
2263  // definition might be changed at runtime, see also
2264  // http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
2265  // TODO: We could always determine abstract attributes and if sufficient
2266  // information was found we could duplicate the functions that do not
2267  // have an exact definition.
2268  if (IsFnInterface && (!FnScope || !A.isFunctionIPOAmendable(*FnScope)))
2269  this->getState().indicatePessimisticFixpoint();
2270  }
2271 
2272  /// See AbstractAttribute::manifest(...).
2274  if (isa<UndefValue>(this->getIRPosition().getAssociatedValue()))
2275  return ChangeStatus::UNCHANGED;
2276  SmallVector<Attribute, 4> DeducedAttrs;
2277  getDeducedAttributes(this->getAnchorValue().getContext(), DeducedAttrs);
2278  return IRAttributeManifest::manifestAttrs(A, this->getIRPosition(),
2279  DeducedAttrs);
2280  }
2281 
2282  /// Return the kind that identifies the abstract attribute implementation.
2283  Attribute::AttrKind getAttrKind() const { return AK; }
2284 
2285  /// Return the deduced attributes in \p Attrs.
2288  Attrs.emplace_back(Attribute::get(Ctx, getAttrKind()));
2289  }
2290 };
2291 
2292 /// Base struct for all "concrete attribute" deductions.
2293 ///
2294 /// The abstract attribute is a minimal interface that allows the Attributor to
2295 /// orchestrate the abstract/fixpoint analysis. The design allows to hide away
2296 /// implementation choices made for the subclasses but also to structure their
2297 /// implementation and simplify the use of other abstract attributes in-flight.
2298 ///
2299 /// To allow easy creation of new attributes, most methods have default
2300 /// implementations. The ones that do not are generally straight forward, except
2301 /// `AbstractAttribute::updateImpl` which is the location of most reasoning
2302 /// associated with the abstract attribute. The update is invoked by the
2303 /// Attributor in case the situation used to justify the current optimistic
2304 /// state might have changed. The Attributor determines this automatically
2305 /// by monitoring the `Attributor::getAAFor` calls made by abstract attributes.
2306 ///
2307 /// The `updateImpl` method should inspect the IR and other abstract attributes
2308 /// in-flight to justify the best possible (=optimistic) state. The actual
2309 /// implementation is, similar to the underlying abstract state encoding, not
2310 /// exposed. In the most common case, the `updateImpl` will go through a list of
2311 /// reasons why its optimistic state is valid given the current information. If
2312 /// any combination of them holds and is sufficient to justify the current
2313 /// optimistic state, the method shall return UNCHAGED. If not, the optimistic
2314 /// state is adjusted to the situation and the method shall return CHANGED.
2315 ///
2316 /// If the manifestation of the "concrete attribute" deduced by the subclass
2317 /// differs from the "default" behavior, which is a (set of) LLVM-IR
2318 /// attribute(s) for an argument, call site argument, function return value, or
2319 /// function, the `AbstractAttribute::manifest` method should be overloaded.
2320 ///
2321 /// NOTE: If the state obtained via getState() is INVALID, thus if
2322 /// AbstractAttribute::getState().isValidState() returns false, no
2323 /// information provided by the methods of this class should be used.
2324 /// NOTE: The Attributor currently has certain limitations to what we can do.
2325 /// As a general rule of thumb, "concrete" abstract attributes should *for
2326 /// now* only perform "backward" information propagation. That means
2327 /// optimistic information obtained through abstract attributes should
2328 /// only be used at positions that precede the origin of the information
2329 /// with regards to the program flow. More practically, information can
2330 /// *now* be propagated from instructions to their enclosing function, but
2331 /// *not* from call sites to the called function. The mechanisms to allow
2332 /// both directions will be added in the future.
2333 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
2334 /// described in the file comment.
2337 
2339 
2340  /// Virtual destructor.
2341  virtual ~AbstractAttribute() {}
2342 
2343  /// This function is used to identify if an \p DGN is of type
2344  /// AbstractAttribute so that the dyn_cast and cast can use such information
2345  /// to cast an AADepGraphNode to an AbstractAttribute.
2346  ///
2347  /// We eagerly return true here because all AADepGraphNodes except for the
2348  /// Synthethis Node are of type AbstractAttribute
2349  static bool classof(const AADepGraphNode *DGN) { return true; }
2350 
2351  /// Initialize the state with the information in the Attributor \p A.
2352  ///
2353  /// This function is called by the Attributor once all abstract attributes
2354  /// have been identified. It can and shall be used for task like:
2355  /// - identify existing knowledge in the IR and use it for the "known state"
2356  /// - perform any work that is not going to change over time, e.g., determine
2357  /// a subset of the IR, or attributes in-flight, that have to be looked at
2358  /// in the `updateImpl` method.
2359  virtual void initialize(Attributor &A) {}
2360 
2361  /// Return the internal abstract state for inspection.
2362  virtual StateType &getState() = 0;
2363  virtual const StateType &getState() const = 0;
2364 
2365  /// Return an IR position, see struct IRPosition.
2366  const IRPosition &getIRPosition() const { return *this; };
2367  IRPosition &getIRPosition() { return *this; };
2368 
2369  /// Helper functions, for debug purposes only.
2370  ///{
2371  void print(raw_ostream &OS) const override;
2372  virtual void printWithDeps(raw_ostream &OS) const;
2373  void dump() const { print(dbgs()); }
2374 
2375  /// This function should return the "summarized" assumed state as string.
2376  virtual const std::string getAsStr() const = 0;
2377 
2378  /// This function should return the name of the AbstractAttribute
2379  virtual const std::string getName() const = 0;
2380 
2381  /// This function should return the address of the ID of the AbstractAttribute
2382  virtual const char *getIdAddr() const = 0;
2383  ///}
2384 
2385  /// Allow the Attributor access to the protected methods.
2386  friend struct Attributor;
2387 
2388 protected:
2389  /// Hook for the Attributor to trigger an update of the internal state.
2390  ///
2391  /// If this attribute is already fixed, this method will return UNCHANGED,
2392  /// otherwise it delegates to `AbstractAttribute::updateImpl`.
2393  ///
2394  /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
2396 
2397  /// Hook for the Attributor to trigger the manifestation of the information
2398  /// represented by the abstract attribute in the LLVM-IR.
2399  ///
2400  /// \Return CHANGED if the IR was altered, otherwise UNCHANGED.
2402  return ChangeStatus::UNCHANGED;
2403  }
2404 
2405  /// Hook to enable custom statistic tracking, called after manifest that
2406  /// resulted in a change if statistics are enabled.
2407  ///
2408  /// We require subclasses to provide an implementation so we remember to
2409  /// add statistics for them.
2410  virtual void trackStatistics() const = 0;
2411 
2412  /// The actual update/transfer function which has to be implemented by the
2413  /// derived classes.
2414  ///
2415  /// If it is called, the environment has changed and we have to determine if
2416  /// the current information is still valid or adjust it otherwise.
2417  ///
2418  /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
2419  virtual ChangeStatus updateImpl(Attributor &A) = 0;
2420 };
2421 
2422 /// Forward declarations of output streams for debug purposes.
2423 ///
2424 ///{
2425 raw_ostream &operator<<(raw_ostream &OS, const AbstractAttribute &AA);
2426 raw_ostream &operator<<(raw_ostream &OS, ChangeStatus S);
2427 raw_ostream &operator<<(raw_ostream &OS, IRPosition::Kind);
2428 raw_ostream &operator<<(raw_ostream &OS, const IRPosition &);
2429 raw_ostream &operator<<(raw_ostream &OS, const AbstractState &State);
2430 template <typename base_ty, base_ty BestState, base_ty WorstState>
2431 raw_ostream &
2434  return OS << "(" << S.getKnown() << "-" << S.getAssumed() << ")"
2435  << static_cast<const AbstractState &>(S);
2436 }
2437 raw_ostream &operator<<(raw_ostream &OS, const IntegerRangeState &State);
2438 ///}
2439 
2440 struct AttributorPass : public PassInfoMixin<AttributorPass> {
2442 };
2443 struct AttributorCGSCCPass : public PassInfoMixin<AttributorCGSCCPass> {
2445  LazyCallGraph &CG, CGSCCUpdateResult &UR);
2446 };
2447 
2450 
2451 /// ----------------------------------------------------------------------------
2452 /// Abstract Attribute Classes
2453 /// ----------------------------------------------------------------------------
2454 
2455 /// An abstract attribute for the returned values of a function.
2457  : public IRAttribute<Attribute::Returned, AbstractAttribute> {
2459 
2460  /// Return an assumed unique return value if a single candidate is found. If
2461  /// there cannot be one, return a nullptr. If it is not clear yet, return the
2462  /// Optional::NoneType.
2464 
2465  /// Check \p Pred on all returned values.
2466  ///
2467  /// This method will evaluate \p Pred on returned values and return
2468  /// true if (1) all returned values are known, and (2) \p Pred returned true
2469  /// for all returned values.
2470  ///
2471  /// Note: Unlike the Attributor::checkForAllReturnedValuesAndReturnInsts
2472  /// method, this one will not filter dead return instructions.
2474  function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> Pred)
2475  const = 0;
2476 
2477  using iterator =
2479  using const_iterator =
2483 
2484  virtual size_t getNumReturnValues() const = 0;
2485  virtual const SmallSetVector<CallBase *, 4> &getUnresolvedCalls() const = 0;
2486 
2487  /// Create an abstract attribute view for the position \p IRP.
2488  static AAReturnedValues &createForPosition(const IRPosition &IRP,
2489  Attributor &A);
2490 
2491  /// See AbstractAttribute::getName()
2492  const std::string getName() const override { return "AAReturnedValues"; }
2493 
2494  /// See AbstractAttribute::getIdAddr()
2495  const char *getIdAddr() const override { return &ID; }
2496 
2497  /// This function should return true if the type of the \p AA is
2498  /// AAReturnedValues
2499  static bool classof(const AbstractAttribute *AA) {
2500  return (AA->getIdAddr() == &ID);
2501  }
2502 
2503  /// Unique ID (due to the unique address)
2504  static const char ID;
2505 };
2506 
2508  : public IRAttribute<Attribute::NoUnwind,
2509  StateWrapper<BooleanState, AbstractAttribute>> {
2510  AANoUnwind(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
2511 
2512  /// Returns true if nounwind is assumed.
2513  bool isAssumedNoUnwind() const { return getAssumed(); }
2514 
2515  /// Returns true if nounwind is known.
2516  bool isKnownNoUnwind() const { return getKnown(); }
2517 
2518  /// Create an abstract attribute view for the position \p IRP.
2519  static AANoUnwind &createForPosition(const IRPosition &IRP, Attributor &A);
2520 
2521  /// See AbstractAttribute::getName()
2522  const std::string getName() const override { return "AANoUnwind"; }
2523 
2524  /// See AbstractAttribute::getIdAddr()
2525  const char *getIdAddr() const override { return &ID; }
2526 
2527  /// This function should return true if the type of the \p AA is AANoUnwind
2528  static bool classof(const AbstractAttribute *AA) {
2529  return (AA->getIdAddr() == &ID);
2530  }
2531 
2532  /// Unique ID (due to the unique address)
2533  static const char ID;
2534 };
2535 
2536 struct AANoSync
2537  : public IRAttribute<Attribute::NoSync,
2538  StateWrapper<BooleanState, AbstractAttribute>> {
2539  AANoSync(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
2540 
2541  /// Returns true if "nosync" is assumed.
2542  bool isAssumedNoSync() const { return getAssumed(); }
2543 
2544  /// Returns true if "nosync" is known.
2545  bool isKnownNoSync() const { return getKnown(); }
2546 
2547  /// Create an abstract attribute view for the position \p IRP.
2548  static AANoSync &createForPosition(const IRPosition &IRP, Attributor &A);
2549 
2550  /// See AbstractAttribute::getName()
2551  const std::string getName() const override { return "AANoSync"; }
2552 
2553  /// See AbstractAttribute::getIdAddr()
2554  const char *getIdAddr() const override { return &ID; }
2555 
2556  /// This function should return true if the type of the \p AA is AANoSync
2557  static bool classof(const AbstractAttribute *AA) {
2558  return (AA->getIdAddr() == &ID);
2559  }
2560 
2561  /// Unique ID (due to the unique address)
2562  static const char ID;
2563 };
2564 
2565 /// An abstract interface for all nonnull attributes.
2567  : public IRAttribute<Attribute::NonNull,
2568  StateWrapper<BooleanState, AbstractAttribute>> {
2569  AANonNull(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
2570 
2571  /// Return true if we assume that the underlying value is nonnull.
2572  bool isAssumedNonNull() const { return getAssumed(); }
2573 
2574  /// Return true if we know that underlying value is nonnull.
2575  bool isKnownNonNull() const { return getKnown(); }
2576 
2577  /// Create an abstract attribute view for the position \p IRP.
2578  static AANonNull &createForPosition(const IRPosition &IRP, Attributor &A);
2579 
2580  /// See AbstractAttribute::getName()
2581  const std::string getName() const override { return "AANonNull"; }
2582 
2583  /// See AbstractAttribute::getIdAddr()
2584  const char *getIdAddr() const override { return &ID; }
2585 
2586  /// This function should return true if the type of the \p AA is AANonNull
2587  static bool classof(const AbstractAttribute *AA) {
2588  return (AA->getIdAddr() == &ID);
2589  }
2590 
2591  /// Unique ID (due to the unique address)
2592  static const char ID;
2593 };
2594 
2595 /// An abstract attribute for norecurse.
2597  : public IRAttribute<Attribute::NoRecurse,
2598  StateWrapper<BooleanState, AbstractAttribute>> {
2599  AANoRecurse(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
2600 
2601  /// Return true if "norecurse" is assumed.
2602  bool isAssumedNoRecurse() const { return getAssumed(); }
2603 
2604  /// Return true if "norecurse" is known.
2605  bool isKnownNoRecurse() const { return getKnown(); }
2606 
2607  /// Create an abstract attribute view for the position \p IRP.
2608  static AANoRecurse &createForPosition(const IRPosition &IRP, Attributor &A);
2609 
2610  /// See AbstractAttribute::getName()
2611  const std::string getName() const override { return "AANoRecurse"; }
2612 
2613  /// See AbstractAttribute::getIdAddr()
2614  const char *getIdAddr() const override { return &ID; }
2615 
2616  /// This function should return true if the type of the \p AA is AANoRecurse
2617  static bool classof(const AbstractAttribute *AA) {
2618  return (AA->getIdAddr() == &ID);
2619  }
2620 
2621  /// Unique ID (due to the unique address)
2622  static const char ID;
2623 };
2624 
2625 /// An abstract attribute for willreturn.
2627  : public IRAttribute<Attribute::WillReturn,
2628  StateWrapper<BooleanState, AbstractAttribute>> {
2629  AAWillReturn(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
2630 
2631  /// Return true if "willreturn" is assumed.
2632  bool isAssumedWillReturn() const { return getAssumed(); }
2633 
2634  /// Return true if "willreturn" is known.
2635  bool isKnownWillReturn() const { return getKnown(); }
2636 
2637  /// Create an abstract attribute view for the position \p IRP.
2638  static AAWillReturn &createForPosition(const IRPosition &IRP, Attributor &A);
2639 
2640  /// See AbstractAttribute::getName()
2641  const std::string getName() const override { return "AAWillReturn"; }
2642 
2643  /// See AbstractAttribute::getIdAddr()
2644  const char *getIdAddr() const override { return &ID; }
2645 
2646  /// This function should return true if the type of the \p AA is AAWillReturn
2647  static bool classof(const AbstractAttribute *AA) {
2648  return (AA->getIdAddr() == &ID);
2649  }
2650 
2651  /// Unique ID (due to the unique address)
2652  static const char ID;
2653 };
2654 
2655 /// An abstract attribute for undefined behavior.
2657  : public StateWrapper<BooleanState, AbstractAttribute> {
2659  AAUndefinedBehavior(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
2660 
2661  /// Return true if "undefined behavior" is assumed.
2662  bool isAssumedToCauseUB() const { return getAssumed(); }
2663 
2664  /// Return true if "undefined behavior" is assumed for a specific instruction.
2665  virtual bool isAssumedToCauseUB(Instruction *I) const = 0;
2666 
2667  /// Return true if "undefined behavior" is known.
2668  bool isKnownToCauseUB() const { return getKnown(); }
2669 
2670  /// Return true if "undefined behavior" is known for a specific instruction.
2671  virtual bool isKnownToCauseUB(Instruction *I) const = 0;
2672 
2673  /// Create an abstract attribute view for the position \p IRP.
2675  Attributor &A);
2676 
2677  /// See AbstractAttribute::getName()
2678  const std::string getName() const override { return "AAUndefinedBehavior"; }
2679 
2680  /// See AbstractAttribute::getIdAddr()
2681  const char *getIdAddr() const override { return &ID; }
2682 
2683  /// This function should return true if the type of the \p AA is
2684  /// AAUndefineBehavior
2685  static bool classof(const AbstractAttribute *AA) {
2686  return (AA->getIdAddr() == &ID);
2687  }
2688 
2689  /// Unique ID (due to the unique address)
2690  static const char ID;
2691 };
2692 
2693 /// An abstract interface to determine reachability of point A to B.
2694 struct AAReachability : public StateWrapper<BooleanState, AbstractAttribute> {
2696  AAReachability(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
2697 
2698  /// Returns true if 'From' instruction is assumed to reach, 'To' instruction.
2699  /// Users should provide two positions they are interested in, and the class
2700  /// determines (and caches) reachability.
2702  const Instruction &To) const {
2703  return A.getInfoCache().getPotentiallyReachable(From, To);
2704  }
2705 
2706  /// Returns true if 'From' instruction is known to reach, 'To' instruction.
2707  /// Users should provide two positions they are interested in, and the class
2708  /// determines (and caches) reachability.
2710  const Instruction &To) const {
2711  return A.getInfoCache().getPotentiallyReachable(From, To);
2712  }
2713 
2714  /// Create an abstract attribute view for the position \p IRP.
2715  static AAReachability &createForPosition(const IRPosition &IRP,
2716  Attributor &A);
2717 
2718  /// See AbstractAttribute::getName()
2719  const std::string getName() const override { return "AAReachability"; }
2720 
2721  /// See AbstractAttribute::getIdAddr()
2722  const char *getIdAddr() const override { return &ID; }
2723 
2724  /// This function should return true if the type of the \p AA is
2725  /// AAReachability
2726  static bool classof(const AbstractAttribute *AA) {
2727  return (AA->getIdAddr() == &ID);
2728  }
2729 
2730  /// Unique ID (due to the unique address)
2731  static const char ID;
2732 };
2733 
2734 /// An abstract interface for all noalias attributes.
2736  : public IRAttribute<Attribute::NoAlias,
2737  StateWrapper<BooleanState, AbstractAttribute>> {
2738  AANoAlias(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
2739 
2740  /// Return true if we assume that the underlying value is alias.
2741  bool isAssumedNoAlias() const { return getAssumed(); }
2742 
2743  /// Return true if we know that underlying value is noalias.
2744  bool isKnownNoAlias() const { return getKnown(); }
2745 
2746  /// Create an abstract attribute view for the position \p IRP.
2747  static AANoAlias &createForPosition(const IRPosition &IRP, Attributor &A);
2748 
2749  /// See AbstractAttribute::getName()
2750  const std::string getName() const override { return "AANoAlias"; }
2751 
2752  /// See AbstractAttribute::getIdAddr()
2753  const char *getIdAddr() const override { return &ID; }
2754 
2755  /// This function should return true if the type of the \p AA is AANoAlias
2756  static bool classof(const AbstractAttribute *AA) {
2757  return (AA->getIdAddr() == &ID);
2758  }
2759 
2760  /// Unique ID (due to the unique address)
2761  static const char ID;
2762 };
2763 
2764 /// An AbstractAttribute for nofree.
2765 struct AANoFree
2766  : public IRAttribute<Attribute::NoFree,
2767  StateWrapper<BooleanState, AbstractAttribute>> {
2768  AANoFree(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
2769 
2770  /// Return true if "nofree" is assumed.
2771  bool isAssumedNoFree() const { return getAssumed(); }
2772 
2773  /// Return true if "nofree" is known.
2774  bool isKnownNoFree() const { return getKnown(); }
2775 
2776  /// Create an abstract attribute view for the position \p IRP.
2777  static AANoFree &createForPosition(const IRPosition &IRP, Attributor &A);
2778 
2779  /// See AbstractAttribute::getName()
2780  const std::string getName() const override { return "AANoFree"; }
2781 
2782  /// See AbstractAttribute::getIdAddr()
2783  const char *getIdAddr() const override { return &ID; }
2784 
2785  /// This function should return true if the type of the \p AA is AANoFree
2786  static bool classof(const AbstractAttribute *AA) {
2787  return (AA->getIdAddr() == &ID);
2788  }
2789 
2790  /// Unique ID (due to the unique address)
2791  static const char ID;
2792 };
2793 
2794 /// An AbstractAttribute for noreturn.
2796  : public IRAttribute<Attribute::NoReturn,
2797  StateWrapper<BooleanState, AbstractAttribute>> {
2798  AANoReturn(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
2799 
2800  /// Return true if the underlying object is assumed to never return.
2801  bool isAssumedNoReturn() const { return getAssumed(); }
2802 
2803  /// Return true if the underlying object is known to never return.
2804  bool isKnownNoReturn() const { return getKnown(); }
2805 
2806  /// Create an abstract attribute view for the position \p IRP.
2807  static AANoReturn &createForPosition(const IRPosition &IRP, Attributor &A);
2808 
2809  /// See AbstractAttribute::getName()
2810  const std::string getName() const override { return "AANoReturn"; }
2811 
2812  /// See AbstractAttribute::getIdAddr()
2813  const char *getIdAddr() const override { return &ID; }
2814 
2815  /// This function should return true if the type of the \p AA is AANoReturn
2816  static bool classof(const AbstractAttribute *AA) {
2817  return (AA->getIdAddr() == &ID);
2818  }
2819 
2820  /// Unique ID (due to the unique address)
2821  static const char ID;
2822 };
2823 
2824 /// An abstract interface for liveness abstract attribute.
2825 struct AAIsDead : public StateWrapper<BooleanState, AbstractAttribute> {
2827  AAIsDead(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
2828 
2829 protected:
2830  /// The query functions are protected such that other attributes need to go
2831  /// through the Attributor interfaces: `Attributor::isAssumedDead(...)`
2832 
2833  /// Returns true if the underlying value is assumed dead.
2834  virtual bool isAssumedDead() const = 0;
2835 
2836  /// Returns true if the underlying value is known dead.
2837  virtual bool isKnownDead() const = 0;
2838 
2839  /// Returns true if \p BB is assumed dead.
2840  virtual bool isAssumedDead(const BasicBlock *BB) const = 0;
2841 
2842  /// Returns true if \p BB is known dead.
2843  virtual bool isKnownDead(const BasicBlock *BB) const = 0;
2844 
2845  /// Returns true if \p I is assumed dead.
2846  virtual bool isAssumedDead(const Instruction *I) const = 0;
2847 
2848  /// Returns true if \p I is known dead.
2849  virtual bool isKnownDead(const Instruction *I) const = 0;
2850 
2851  /// This method is used to check if at least one instruction in a collection
2852  /// of instructions is live.
2853  template <typename T> bool isLiveInstSet(T begin, T end) const {
2854  for (const auto &I : llvm::make_range(begin, end)) {
2855  assert(I->getFunction() == getIRPosition().getAssociatedFunction() &&
2856  "Instruction must be in the same anchor scope function.");
2857 
2858  if (!isAssumedDead(I))
2859  return true;
2860  }
2861 
2862  return false;
2863  }
2864 
2865 public:
2866  /// Create an abstract attribute view for the position \p IRP.
2867  static AAIsDead &createForPosition(const IRPosition &IRP, Attributor &A);
2868 
2869  /// Determine if \p F might catch asynchronous exceptions.
2871  return F.hasPersonalityFn() && !canSimplifyInvokeNoUnwind(&F);
2872  }
2873 
2874  /// Return if the edge from \p From BB to \p To BB is assumed dead.
2875  /// This is specifically useful in AAReachability.
2876  virtual bool isEdgeDead(const BasicBlock *From, const BasicBlock *To) const {
2877  return false;
2878  }
2879 
2880  /// See AbstractAttribute::getName()
2881  const std::string getName() const override { return "AAIsDead"; }
2882 
2883  /// See AbstractAttribute::getIdAddr()
2884  const char *getIdAddr() const override { return &ID; }
2885 
2886  /// This function should return true if the type of the \p AA is AAIsDead
2887  static bool classof(const AbstractAttribute *AA) {
2888  return (AA->getIdAddr() == &ID);
2889  }
2890 
2891  /// Unique ID (due to the unique address)
2892  static const char ID;
2893 
2894  friend struct Attributor;
2895 };
2896 
2897 /// State for dereferenceable attribute
2899 
2900  static DerefState getBestState() { return DerefState(); }
2901  static DerefState getBestState(const DerefState &) { return getBestState(); }
2902 
2903  /// Return the worst possible representable state.
2905  DerefState DS;
2906  DS.indicatePessimisticFixpoint();
2907  return DS;
2908  }
2910  return getWorstState();
2911  }
2912 
2913  /// State representing for dereferenceable bytes.
2915 
2916  /// Map representing for accessed memory offsets and sizes.
2917  /// A key is Offset and a value is size.
2918  /// If there is a load/store instruction something like,
2919  /// p[offset] = v;
2920  /// (offset, sizeof(v)) will be inserted to this map.
2921  /// std::map is used because we want to iterate keys in ascending order.
2922  std::map<int64_t, uint64_t> AccessedBytesMap;
2923 
2924  /// Helper function to calculate dereferenceable bytes from current known
2925  /// bytes and accessed bytes.
2926  ///
2927  /// int f(int *A){
2928  /// *A = 0;
2929  /// *(A+2) = 2;
2930  /// *(A+1) = 1;
2931  /// *(A+10) = 10;
2932  /// }
2933  /// ```
2934  /// In that case, AccessedBytesMap is `{0:4, 4:4, 8:4, 40:4}`.
2935  /// AccessedBytesMap is std::map so it is iterated in accending order on
2936  /// key(Offset). So KnownBytes will be updated like this:
2937  ///
2938  /// |Access | KnownBytes
2939  /// |(0, 4)| 0 -> 4
2940  /// |(4, 4)| 4 -> 8
2941  /// |(8, 4)| 8 -> 12
2942  /// |(40, 4) | 12 (break)
2943  void computeKnownDerefBytesFromAccessedMap() {
2944  int64_t KnownBytes = DerefBytesState.getKnown();
2945  for (auto &Access : AccessedBytesMap) {
2946  if (KnownBytes < Access.first)
2947  break;
2948  KnownBytes = std::max(KnownBytes, Access.first + (int64_t)Access.second);
2949  }
2950 
2951  DerefBytesState.takeKnownMaximum(KnownBytes);
2952  }
2953 
2954  /// State representing that whether the value is globaly dereferenceable.
2955  BooleanState GlobalState;
2956 
2957  /// See AbstractState::isValidState()
2958  bool isValidState() const override { return DerefBytesState.isValidState(); }
2959 
2960  /// See AbstractState::isAtFixpoint()
2961  bool isAtFixpoint() const override {
2962  return !isValidState() ||
2963  (DerefBytesState.isAtFixpoint() && GlobalState.isAtFixpoint());
2964  }
2965 
2966  /// See AbstractState::indicateOptimisticFixpoint(...)
2969  GlobalState.indicateOptimisticFixpoint();
2970  return ChangeStatus::UNCHANGED;
2971  }
2972 
2973  /// See AbstractState::indicatePessimisticFixpoint(...)
2976  GlobalState.indicatePessimisticFixpoint();
2977  return ChangeStatus::CHANGED;
2978  }
2979 
2980  /// Update known dereferenceable bytes.
2981  void takeKnownDerefBytesMaximum(uint64_t Bytes) {
2983 
2984  // Known bytes might increase.
2985  computeKnownDerefBytesFromAccessedMap();
2986  }
2987 
2988  /// Update assumed dereferenceable bytes.
2989  void takeAssumedDerefBytesMinimum(uint64_t Bytes) {
2991  }
2992 
2993  /// Add accessed bytes to the map.
2994  void addAccessedBytes(int64_t Offset, uint64_t Size) {
2995  uint64_t &AccessedBytes = AccessedBytesMap[Offset];
2996  AccessedBytes = std::max(AccessedBytes, Size);
2997 
2998  // Known bytes might increase.
2999  computeKnownDerefBytesFromAccessedMap();
3000  }
3001 
3002  /// Equality for DerefState.
3003  bool operator==(const DerefState &R) const {
3004  return this->DerefBytesState == R.DerefBytesState &&
3005  this->GlobalState == R.GlobalState;
3006  }
3007 
3008  /// Inequality for DerefState.
3009  bool operator!=(const DerefState &R) const { return !(*this == R); }
3010 
3011  /// See IntegerStateBase::operator^=
3012  DerefState operator^=(const DerefState &R) {
3013  DerefBytesState ^= R.DerefBytesState;
3014  GlobalState ^= R.GlobalState;
3015  return *this;
3016  }
3017 
3018  /// See IntegerStateBase::operator+=
3019  DerefState operator+=(const DerefState &R) {
3020  DerefBytesState += R.DerefBytesState;
3021  GlobalState += R.GlobalState;
3022  return *this;
3023  }
3024 
3025  /// See IntegerStateBase::operator&=
3026  DerefState operator&=(const DerefState &R) {
3027  DerefBytesState &= R.DerefBytesState;
3028  GlobalState &= R.GlobalState;
3029  return *this;
3030  }
3031 
3032  /// See IntegerStateBase::operator|=
3033  DerefState operator|=(const DerefState &R) {
3034  DerefBytesState |= R.DerefBytesState;
3035  GlobalState |= R.GlobalState;
3036  return *this;
3037  }
3038 
3039 protected:
3040  const AANonNull *NonNullAA = nullptr;
3041 };
3042 
3043 /// An abstract interface for all dereferenceable attribute.
3045  : public IRAttribute<Attribute::Dereferenceable,
3046  StateWrapper<DerefState, AbstractAttribute>> {
3048 
3049  /// Return true if we assume that the underlying value is nonnull.
3050  bool isAssumedNonNull() const {
3051  return NonNullAA && NonNullAA->isAssumedNonNull();
3052  }
3053 
3054  /// Return true if we know that the underlying value is nonnull.
3055  bool isKnownNonNull() const {
3056  return NonNullAA && NonNullAA->isKnownNonNull();
3057  }
3058 
3059  /// Return true if we assume that underlying value is
3060  /// dereferenceable(_or_null) globally.
3061  bool isAssumedGlobal() const { return GlobalState.getAssumed(); }
3062 
3063  /// Return true if we know that underlying value is
3064  /// dereferenceable(_or_null) globally.
3065  bool isKnownGlobal() const { return GlobalState.getKnown(); }
3066 
3067  /// Return assumed dereferenceable bytes.
3069  return DerefBytesState.getAssumed();
3070  }
3071 
3072  /// Return known dereferenceable bytes.
3074  return DerefBytesState.getKnown();
3075  }
3076 
3077  /// Create an abstract attribute view for the position \p IRP.
3078  static AADereferenceable &createForPosition(const IRPosition &IRP,
3079  Attributor &A);
3080 
3081  /// See AbstractAttribute::getName()
3082  const std::string getName() const override { return "AADereferenceable"; }
3083 
3084  /// See AbstractAttribute::getIdAddr()
3085  const char *getIdAddr() const override { return &ID; }
3086 
3087  /// This function should return true if the type of the \p AA is
3088  /// AADereferenceable
3089  static bool classof(const AbstractAttribute *AA) {
3090  return (AA->getIdAddr() == &ID);
3091  }
3092 
3093  /// Unique ID (due to the unique address)
3094  static const char ID;
3095 };
3096 
3097 using AAAlignmentStateType =
3099 /// An abstract interface for all align attributes.
3100 struct AAAlign : public IRAttribute<
3101  Attribute::Alignment,
3102  StateWrapper<AAAlignmentStateType, AbstractAttribute>> {
3103  AAAlign(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3104 
3105  /// Return assumed alignment.
3106  unsigned getAssumedAlign() const { return getAssumed(); }
3107 
3108  /// Return known alignment.
3109  unsigned getKnownAlign() const { return getKnown(); }
3110 
3111  /// See AbstractAttribute::getName()
3112  const std::string getName() const override { return "AAAlign"; }
3113 
3114  /// See AbstractAttribute::getIdAddr()
3115  const char *getIdAddr() const override { return &ID; }
3116 
3117  /// This function should return true if the type of the \p AA is AAAlign
3118  static bool classof(const AbstractAttribute *AA) {
3119  return (AA->getIdAddr() == &ID);
3120  }
3121 
3122  /// Create an abstract attribute view for the position \p IRP.
3123  static AAAlign &createForPosition(const IRPosition &IRP, Attributor &A);
3124 
3125  /// Unique ID (due to the unique address)
3126  static const char ID;
3127 };
3128 
3129 /// An abstract interface for all nocapture attributes.
3131  : public IRAttribute<
3132  Attribute::NoCapture,
3133  StateWrapper<BitIntegerState<uint16_t, 7, 0>, AbstractAttribute>> {
3134  AANoCapture(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3135 
3136  /// State encoding bits. A set bit in the state means the property holds.
3137  /// NO_CAPTURE is the best possible state, 0 the worst possible state.
3138  enum {
3142 
3143  /// If we do not capture the value in memory or through integers we can only
3144  /// communicate it back as a derived pointer.
3146 
3147  /// If we do not capture the value in memory, through integers, or as a
3148  /// derived pointer we know it is not captured.
3151  };
3152 
3153  /// Return true if we know that the underlying value is not captured in its
3154  /// respective scope.
3155  bool isKnownNoCapture() const { return isKnown(NO_CAPTURE); }
3156 
3157  /// Return true if we assume that the underlying value is not captured in its
3158  /// respective scope.
3159  bool isAssumedNoCapture() const { return isAssumed(NO_CAPTURE); }
3160 
3161  /// Return true if we know that the underlying value is not captured in its
3162  /// respective scope but we allow it to escape through a "return".
3165  }
3166 
3167  /// Return true if we assume that the underlying value is not captured in its
3168  /// respective scope but we allow it to escape through a "return".
3171  }
3172 
3173  /// Create an abstract attribute view for the position \p IRP.
3174  static AANoCapture &createForPosition(const IRPosition &IRP, Attributor &A);
3175 
3176  /// See AbstractAttribute::getName()
3177  const std::string getName() const override { return "AANoCapture"; }
3178 
3179  /// See AbstractAttribute::getIdAddr()
3180  const char *getIdAddr() const override { return &ID; }
3181 
3182  /// This function should return true if the type of the \p AA is AANoCapture
3183  static bool classof(const AbstractAttribute *AA) {
3184  return (AA->getIdAddr() == &ID);
3185  }
3186 
3187  /// Unique ID (due to the unique address)
3188  static const char ID;
3189 };
3190 
3191 /// An abstract interface for value simplify abstract attribute.
3192 struct AAValueSimplify : public StateWrapper<BooleanState, AbstractAttribute> {
3194  AAValueSimplify(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
3195 
3196  /// Return an assumed simplified value if a single candidate is found. If
3197  /// there cannot be one, return original value. If it is not clear yet, return
3198  /// the Optional::NoneType.
3200 
3201  /// Create an abstract attribute view for the position \p IRP.
3202  static AAValueSimplify &createForPosition(const IRPosition &IRP,
3203  Attributor &A);
3204 
3205  /// See AbstractAttribute::getName()
3206  const std::string getName() const override { return "AAValueSimplify"; }
3207 
3208  /// See AbstractAttribute::getIdAddr()
3209  const char *getIdAddr() const override { return &ID; }
3210 
3211  /// This function should return true if the type of the \p AA is
3212  /// AAValueSimplify
3213  static bool classof(const AbstractAttribute *AA) {
3214  return (AA->getIdAddr() == &ID);
3215  }
3216 
3217  /// Unique ID (due to the unique address)
3218  static const char ID;
3219 };
3220 
3221 struct AAHeapToStack : public StateWrapper<BooleanState, AbstractAttribute> {
3223  AAHeapToStack(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
3224 
3225  /// Returns true if HeapToStack conversion is assumed to be possible.
3226  virtual bool isAssumedHeapToStack(CallBase &CB) const = 0;
3227 
3228  /// Returns true if HeapToStack conversion is known to be possible.
3229  virtual bool isKnownHeapToStack(CallBase &CB) const = 0;
3230 
3231  /// Create an abstract attribute view for the position \p IRP.
3232  static AAHeapToStack &createForPosition(const IRPosition &IRP, Attributor &A);
3233 
3234  /// See AbstractAttribute::getName()
3235  const std::string getName() const override { return "AAHeapToStack"; }
3236 
3237  /// See AbstractAttribute::getIdAddr()
3238  const char *getIdAddr() const override { return &ID; }
3239 
3240  /// This function should return true if the type of the \p AA is AAHeapToStack
3241  static bool classof(const AbstractAttribute *AA) {
3242  return (AA->getIdAddr() == &ID);
3243  }
3244 
3245  /// Unique ID (due to the unique address)
3246  static const char ID;
3247 };
3248 
3249 /// An abstract interface for privatizability.
3250 ///
3251 /// A pointer is privatizable if it can be replaced by a new, private one.
3252 /// Privatizing pointer reduces the use count, interaction between unrelated
3253 /// code parts.
3254 ///
3255 /// In order for a pointer to be privatizable its value cannot be observed
3256 /// (=nocapture), it is (for now) not written (=readonly & noalias), we know
3257 /// what values are necessary to make the private copy look like the original
3258 /// one, and the values we need can be loaded (=dereferenceable).
3260  : public StateWrapper<BooleanState, AbstractAttribute> {
3262  AAPrivatizablePtr(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
3263 
3264  /// Returns true if pointer privatization is assumed to be possible.
3265  bool isAssumedPrivatizablePtr() const { return getAssumed(); }
3266 
3267  /// Returns true if pointer privatization is known to be possible.
3268  bool isKnownPrivatizablePtr() const { return getKnown(); }
3269 
3270  /// Return the type we can choose for a private copy of the underlying
3271  /// value. None means it is not clear yet, nullptr means there is none.
3272  virtual Optional<Type *> getPrivatizableType() const = 0;
3273 
3274  /// Create an abstract attribute view for the position \p IRP.
3275  static AAPrivatizablePtr &createForPosition(const IRPosition &IRP,
3276  Attributor &A);
3277 
3278  /// See AbstractAttribute::getName()
3279  const std::string getName() const override { return "AAPrivatizablePtr"; }
3280 
3281  /// See AbstractAttribute::getIdAddr()
3282  const char *getIdAddr() const override { return &ID; }
3283 
3284  /// This function should return true if the type of the \p AA is
3285  /// AAPricatizablePtr
3286  static bool classof(const AbstractAttribute *AA) {
3287  return (AA->getIdAddr() == &ID);
3288  }
3289 
3290  /// Unique ID (due to the unique address)
3291  static const char ID;
3292 };
3293 
3294 /// An abstract interface for memory access kind related attributes
3295 /// (readnone/readonly/writeonly).
3297  : public IRAttribute<
3298  Attribute::ReadNone,
3299  StateWrapper<BitIntegerState<uint8_t, 3>, AbstractAttribute>> {
3301 
3302  /// State encoding bits. A set bit in the state means the property holds.
3303  /// BEST_STATE is the best possible state, 0 the worst possible state.
3304  enum {
3305  NO_READS = 1 << 0,
3306  NO_WRITES = 1 << 1,
3308 
3310  };
3311  static_assert(BEST_STATE == getBestState(), "Unexpected BEST_STATE value");
3312 
3313  /// Return true if we know that the underlying value is not read or accessed
3314  /// in its respective scope.
3315  bool isKnownReadNone() const { return isKnown(NO_ACCESSES); }
3316 
3317  /// Return true if we assume that the underlying value is not read or accessed
3318  /// in its respective scope.
3319  bool isAssumedReadNone() const { return isAssumed(NO_ACCESSES); }
3320 
3321  /// Return true if we know that the underlying value is not accessed
3322  /// (=written) in its respective scope.
3323  bool isKnownReadOnly() const { return isKnown(NO_WRITES); }
3324 
3325  /// Return true if we assume that the underlying value is not accessed
3326  /// (=written) in its respective scope.
3327  bool isAssumedReadOnly() const { return isAssumed(NO_WRITES); }
3328 
3329  /// Return true if we know that the underlying value is not read in its
3330  /// respective scope.
3331  bool isKnownWriteOnly() const { return isKnown(NO_READS); }
3332 
3333  /// Return true if we assume that the underlying value is not read in its
3334  /// respective scope.
3335  bool isAssumedWriteOnly() const { return isAssumed(NO_READS); }
3336 
3337  /// Create an abstract attribute view for the position \p IRP.
3338  static AAMemoryBehavior &createForPosition(const IRPosition &IRP,
3339  Attributor &A);
3340 
3341  /// See AbstractAttribute::getName()
3342  const std::string getName() const override { return "AAMemoryBehavior"; }
3343 
3344  /// See AbstractAttribute::getIdAddr()
3345  const char *getIdAddr() const override { return &ID; }
3346 
3347  /// This function should return true if the type of the \p AA is
3348  /// AAMemoryBehavior
3349  static bool classof(const AbstractAttribute *AA) {
3350  return (AA->getIdAddr() == &ID);
3351  }
3352 
3353  /// Unique ID (due to the unique address)
3354  static const char ID;
3355 };
3356 
3357 /// An abstract interface for all memory location attributes
3358 /// (readnone/argmemonly/inaccessiblememonly/inaccessibleorargmemonly).
3360  : public IRAttribute<
3361  Attribute::ReadNone,
3362  StateWrapper<BitIntegerState<uint32_t, 511>, AbstractAttribute>> {
3363  using MemoryLocationsKind = StateType::base_t;
3364 
3366 
3367  /// Encoding of different locations that could be accessed by a memory
3368  /// access.
3369  enum {
3371  NO_LOCAL_MEM = 1 << 0,
3372  NO_CONST_MEM = 1 << 1,
3379  NO_UNKOWN_MEM = 1 << 7,
3383 
3384  // Helper bit to track if we gave up or not.
3386 
3388  };
3389  static_assert(BEST_STATE == getBestState(), "Unexpected BEST_STATE value");
3390 
3391  /// Return true if we know that the associated functions has no observable
3392  /// accesses.
3393  bool isKnownReadNone() const { return isKnown(NO_LOCATIONS); }
3394 
3395  /// Return true if we assume that the associated functions has no observable
3396  /// accesses.
3397  bool isAssumedReadNone() const {
3399  }
3400 
3401  /// Return true if we know that the associated functions has at most
3402  /// local/stack accesses.
3403  bool isKnowStackOnly() const {
3404  return isKnown(inverseLocation(NO_LOCAL_MEM, true, true));
3405  }
3406 
3407  /// Return true if we assume that the associated functions has at most
3408  /// local/stack accesses.
3409  bool isAssumedStackOnly() const {
3410  return isAssumed(inverseLocation(NO_LOCAL_MEM, true, true));
3411  }
3412 
3413  /// Return true if we know that the underlying value will only access
3414  /// inaccesible memory only (see Attribute::InaccessibleMemOnly).
3416  return isKnown(inverseLocation(NO_INACCESSIBLE_MEM, true, true));
3417  }
3418 
3419  /// Return true if we assume that the underlying value will only access
3420  /// inaccesible memory only (see Attribute::InaccessibleMemOnly).
3422  return isAssumed(inverseLocation(NO_INACCESSIBLE_MEM, true, true));
3423  }
3424 
3425  /// Return true if we know that the underlying value will only access
3426  /// argument pointees (see Attribute::ArgMemOnly).
3427  bool isKnownArgMemOnly() const {
3428  return isKnown(inverseLocation(NO_ARGUMENT_MEM, true, true));
3429  }
3430 
3431  /// Return true if we assume that the underlying value will only access
3432  /// argument pointees (see Attribute::ArgMemOnly).
3433  bool isAssumedArgMemOnly() const {
3434  return isAssumed(inverseLocation(NO_ARGUMENT_MEM, true, true));
3435  }
3436 
3437  /// Return true if we know that the underlying value will only access
3438  /// inaccesible memory or argument pointees (see
3439  /// Attribute::InaccessibleOrArgMemOnly).
3441  return isKnown(
3443  }
3444 
3445  /// Return true if we assume that the underlying value will only access
3446  /// inaccesible memory or argument pointees (see
3447  /// Attribute::InaccessibleOrArgMemOnly).
3449  return isAssumed(
3451  }
3452 
3453  /// Return true if the underlying value may access memory through arguement
3454  /// pointers of the associated function, if any.
3455  bool mayAccessArgMem() const { return !isAssumed(NO_ARGUMENT_MEM); }
3456 
3457  /// Return true if only the memory locations specififed by \p MLK are assumed
3458  /// to be accessed by the associated function.
3460  return isAssumed(MLK);
3461  }
3462 
3463  /// Return the locations that are assumed to be not accessed by the associated
3464  /// function, if any.
3466  return getAssumed();
3467  }
3468 
3469  /// Return the inverse of location \p Loc, thus for NO_XXX the return
3470  /// describes ONLY_XXX. The flags \p AndLocalMem and \p AndConstMem determine
3471  /// if local (=stack) and constant memory are allowed as well. Most of the
3472  /// time we do want them to be included, e.g., argmemonly allows accesses via
3473  /// argument pointers or local or constant memory accesses.
3474  static MemoryLocationsKind
3475  inverseLocation(MemoryLocationsKind Loc, bool AndLocalMem, bool AndConstMem) {
3476  return NO_LOCATIONS & ~(Loc | (AndLocalMem ? NO_LOCAL_MEM : 0) |
3477  (AndConstMem ? NO_CONST_MEM : 0));
3478  };
3479 
3480  /// Return the locations encoded by \p MLK as a readable string.
3481  static std::string getMemoryLocationsAsStr(MemoryLocationsKind MLK);
3482 
3483  /// Simple enum to distinguish read/write/read-write accesses.
3484  enum AccessKind {
3485  NONE = 0,
3486  READ = 1 << 0,
3487  WRITE = 1 << 1,
3489  };
3490 
3491  /// Check \p Pred on all accesses to the memory kinds specified by \p MLK.
3492  ///
3493  /// This method will evaluate \p Pred on all accesses (access instruction +
3494  /// underlying accessed memory pointer) and it will return true if \p Pred
3495  /// holds every time.
3496  virtual bool checkForAllAccessesToMemoryKind(
3497  function_ref<bool(const Instruction *, const Value *, AccessKind,
3499  Pred,
3500  MemoryLocationsKind MLK) const = 0;
3501 
3502  /// Create an abstract attribute view for the position \p IRP.
3503  static AAMemoryLocation &createForPosition(const IRPosition &IRP,
3504  Attributor &A);
3505 
3506  /// See AbstractState::getAsStr().
3507  const std::string getAsStr() const override {
3509  }
3510 
3511  /// See AbstractAttribute::getName()
3512  const std::string getName() const override { return "AAMemoryLocation"; }
3513 
3514  /// See AbstractAttribute::getIdAddr()
3515  const char *getIdAddr() const override { return &ID; }
3516 
3517  /// This function should return true if the type of the \p AA is
3518  /// AAMemoryLocation
3519  static bool classof(const AbstractAttribute *AA) {
3520  return (AA->getIdAddr() == &ID);
3521  }
3522 
3523  /// Unique ID (due to the unique address)
3524  static const char ID;
3525 };
3526 
3527 /// An abstract interface for range value analysis.
3529  : public StateWrapper<IntegerRangeState, AbstractAttribute, uint32_t> {
3532  : Base(IRP, IRP.getAssociatedType()->getIntegerBitWidth()) {}
3533 
3534  /// See AbstractAttribute::getState(...).
3535  IntegerRangeState &getState() override { return *this; }
3536  const IntegerRangeState &getState() const override { return *this; }
3537 
3538  /// Create an abstract attribute view for the position \p IRP.
3540  Attributor &A);
3541 
3542  /// Return an assumed range for the assocaited value a program point \p CtxI.
3543  /// If \p I is nullptr, simply return an assumed range.
3544  virtual ConstantRange
3546  const Instruction *CtxI = nullptr) const = 0;
3547 
3548  /// Return a known range for the assocaited value at a program point \p CtxI.
3549  /// If \p I is nullptr, simply return a known range.
3550  virtual ConstantRange
3552  const Instruction *CtxI = nullptr) const = 0;
3553 
3554  /// Return an assumed constant for the assocaited value a program point \p
3555  /// CtxI.
3558  const Instruction *CtxI = nullptr) const {
3559  ConstantRange RangeV = getAssumedConstantRange(A, CtxI);
3560  if (auto *C = RangeV.getSingleElement())
3561  return cast<ConstantInt>(
3563  if (RangeV.isEmptySet())
3564  return llvm::None;
3565  return nullptr;
3566  }
3567 
3568  /// See AbstractAttribute::getName()
3569  const std::string getName() const override { return "AAValueConstantRange"; }
3570 
3571  /// See AbstractAttribute::getIdAddr()
3572  const char *getIdAddr() const override { return &ID; }
3573 
3574  /// This function should return true if the type of the \p AA is
3575  /// AAValueConstantRange
3576  static bool classof(const AbstractAttribute *AA) {
3577  return (AA->getIdAddr() == &ID);
3578  }
3579 
3580  /// Unique ID (due to the unique address)
3581  static const char ID;
3582 };
3583 
3584 /// A class for a set state.
3585 /// The assumed boolean state indicates whether the corresponding set is full
3586 /// set or not. If the assumed state is false, this is the worst state. The
3587 /// worst state (invalid state) of set of potential values is when the set
3588 /// contains every possible value (i.e. we cannot in any way limit the value
3589 /// that the target position can take). That never happens naturally, we only
3590 /// force it. As for the conditions under which we force it, see
3591 /// AAPotentialValues.
3592 template <typename MemberTy, typename KeyInfo = DenseMapInfo<MemberTy>>
3595 
3596  PotentialValuesState() : IsValidState(true), UndefIsContained(false) {}
3597 
3598  PotentialValuesState(bool IsValid)
3599  : IsValidState(IsValid), UndefIsContained(false) {}
3600 
3601  /// See AbstractState::isValidState(...)
3602  bool isValidState() const override { return IsValidState.isValidState(); }
3603 
3604  /// See AbstractState::isAtFixpoint(...)
3605  bool isAtFixpoint() const override { return IsValidState.isAtFixpoint(); }
3606 
3607  /// See AbstractState::indicatePessimisticFixpoint(...)
3609  return IsValidState.indicatePessimisticFixpoint();
3610  }
3611 
3612  /// See AbstractState::indicateOptimisticFixpoint(...)
3614  return IsValidState.indicateOptimisticFixpoint();
3615  }
3616 
3617  /// Return the assumed state
3618  PotentialValuesState &getAssumed() { return *this; }
3619  const PotentialValuesState &getAssumed() const { return *this; }
3620 
3621  /// Return this set. We should check whether this set is valid or not by
3622  /// isValidState() before calling this function.
3623  const SetTy &getAssumedSet() const {
3624  assert(isValidState() && "This set shoud not be used when it is invalid!");
3625  return Set;
3626  }
3627 
3628  /// Returns whether this state contains an undef value or not.
3629  bool undefIsContained() const {
3630  assert(isValidState() && "This flag shoud not be used when it is invalid!");
3631  return UndefIsContained;
3632  }
3633 
3634  bool operator==(const PotentialValuesState &RHS) const {
3635  if (isValidState() != RHS.isValidState())
3636  return false;
3637  if (!isValidState() && !RHS.isValidState())
3638  return true;
3639  if (undefIsContained() != RHS.undefIsContained())
3640  return false;
3641  return Set == RHS.getAssumedSet();
3642  }
3643 
3644  /// Maximum number of potential values to be tracked.
3645  /// This is set by -attributor-max-potential-values command line option
3646  static unsigned MaxPotentialValues;
3647 
3648  /// Return empty set as the best state of potential values.
3650  return PotentialValuesState(true);
3651  }
3652 
3654  return getBestState();
3655  }
3656 
3657  /// Return full set as the worst state of potential values.
3659  return PotentialValuesState(false);
3660  }
3661 
3662  /// Union assumed set with the passed value.
3663  void unionAssumed(const MemberTy &C) { insert(C); }
3664 
3665  /// Union assumed set with assumed set of the passed state \p PVS.
3666  void unionAssumed(const PotentialValuesState &PVS) { unionWith(PVS); }
3667 
3668  /// Union assumed set with an undef value.
3669  void unionAssumedWithUndef() { unionWithUndef(); }
3670 
3671  /// "Clamp" this state with \p PVS.
3673  IsValidState ^= PVS.IsValidState;
3674  unionAssumed(PVS);
3675  return *this;
3676  }
3677 
3679  IsValidState &= PVS.IsValidState;
3680  unionAssumed(PVS);
3681  return *this;
3682  }
3683 
3684 private:
3685  /// Check the size of this set, and invalidate when the size is no
3686  /// less than \p MaxPotentialValues threshold.
3687  void checkAndInvalidate() {
3688  if (Set.size() >= MaxPotentialValues)
3690  else
3691  reduceUndefValue();
3692  }
3693 
3694  /// If this state contains both undef and not undef, we can reduce
3695  /// undef to the not undef value.
3696  void reduceUndefValue() { UndefIsContained = UndefIsContained & Set.empty(); }
3697 
3698  /// Insert an element into this set.
3699  void insert(const MemberTy &C) {
3700  if (!isValidState())
3701  return;
3702  Set.insert(C);
3703  checkAndInvalidate();
3704  }
3705 
3706  /// Take union with R.
3707  void unionWith(const PotentialValuesState &R) {
3708  /// If this is a full set, do nothing.
3709  if (!isValidState())
3710  return;
3711  /// If R is full set, change L to a full set.
3712  if (!R.isValidState()) {
3714  return;
3715  }
3716  for (const MemberTy &C : R.Set)
3717  Set.insert(C);
3718  UndefIsContained |= R.undefIsContained();
3719  checkAndInvalidate();
3720  }
3721 
3722  /// Take union with an undef value.
3723  void unionWithUndef() {
3724  UndefIsContained = true;
3725  reduceUndefValue();
3726  }
3727 
3728  /// Take intersection with R.
3729  void intersectWith(const PotentialValuesState &R) {
3730  /// If R is a full set, do nothing.
3731  if (!R.isValidState())
3732  return;
3733  /// If this is a full set, change this to R.
3734  if (!isValidState()) {
3735  *this = R;
3736  return;
3737  }
3738  SetTy IntersectSet;
3739  for (const MemberTy &C : Set) {
3740  if (R.Set.count(C))
3741  IntersectSet.insert(C);
3742  }
3743  Set = IntersectSet;
3744  UndefIsContained &= R.undefIsContained();
3745  reduceUndefValue();
3746  }
3747 
3748  /// A helper state which indicate whether this state is valid or not.
3749  BooleanState IsValidState;
3750 
3751  /// Container for potential values
3752  SetTy Set;
3753 
3754  /// Flag for undef value
3755  bool UndefIsContained;
3756 };
3757 
3759 
3762 
3763 /// An abstract interface for potential values analysis.
3764 ///
3765 /// This AA collects potential values for each IR position.
3766 /// An assumed set of potential values is initialized with the empty set (the
3767 /// best state) and it will grow monotonically as we find more potential values
3768 /// for this position.
3769 /// The set might be forced to the worst state, that is, to contain every
3770 /// possible value for this position in 2 cases.
3771 /// 1. We surpassed the \p MaxPotentialValues threshold. This includes the
3772 /// case that this position is affected (e.g. because of an operation) by a
3773 /// Value that is in the worst state.
3774 /// 2. We tried to initialize on a Value that we cannot handle (e.g. an
3775 /// operator we do not currently handle).
3776 ///
3777 /// TODO: Support values other than constant integers.
3779  : public StateWrapper<PotentialConstantIntValuesState, AbstractAttribute> {
3781  AAPotentialValues(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
3782 
3783  /// See AbstractAttribute::getState(...).
3784  PotentialConstantIntValuesState &getState() override { return *this; }
3785  const PotentialConstantIntValuesState &getState() const override {
3786  return *this;
3787  }
3788 
3789  /// Create an abstract attribute view for the position \p IRP.
3790  static AAPotentialValues &createForPosition(const IRPosition &IRP,
3791  Attributor &A);
3792 
3793  /// Return assumed constant for the associated value
3796  const Instruction *CtxI = nullptr) const {
3797  if (!isValidState())
3798  return nullptr;
3799  if (getAssumedSet().size() == 1)
3800  return cast<ConstantInt>(ConstantInt::get(getAssociatedValue().getType(),
3801  *(getAssumedSet().begin())));
3802  if (getAssumedSet().size() == 0) {
3803  if (undefIsContained())
3804  return cast<ConstantInt>(
3806  return llvm::None;
3807  }
3808 
3809  return nullptr;
3810  }
3811 
3812  /// See AbstractAttribute::getName()
3813  const std::string getName() const override { return "AAPotentialValues"; }
3814 
3815  /// See AbstractAttribute::getIdAddr()
3816  const char *getIdAddr() const override { return &ID; }
3817 
3818  /// This function should return true if the type of the \p AA is
3819  /// AAPotentialValues
3820  static bool classof(const AbstractAttribute *AA) {
3821  return (AA->getIdAddr() == &ID);
3822  }
3823 
3824  /// Unique ID (due to the unique address)
3825  static const char ID;
3826 };
3827 
3828 /// An abstract interface for all noundef attributes.
3830  : public IRAttribute<Attribute::NoUndef,
3831  StateWrapper<BooleanState, AbstractAttribute>> {
3832  AANoUndef(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3833 
3834  /// Return true if we assume that the underlying value is noundef.
3835  bool isAssumedNoUndef() const { return getAssumed(); }
3836 
3837  /// Return true if we know that underlying value is noundef.
3838  bool isKnownNoUndef() const { return getKnown(); }
3839 
3840  /// Create an abstract attribute view for the position \p IRP.
3841  static AANoUndef &createForPosition(const IRPosition &IRP, Attributor &A);
3842 
3843  /// See AbstractAttribute::getName()
3844  const std::string getName() const override { return "AANoUndef"; }
3845 
3846  /// See AbstractAttribute::getIdAddr()
3847  const char *getIdAddr() const override { return &ID; }
3848 
3849  /// This function should return true if the type of the \p AA is AANoUndef
3850  static bool classof(const AbstractAttribute *AA) {
3851  return (AA->getIdAddr() == &ID);
3852  }
3853 
3854  /// Unique ID (due to the unique address)
3855  static const char ID;
3856 };
3857 
3858 /// Run options, used by the pass manager.
3860  NONE = 0,
3861  MODULE = 1 << 0,
3862  CGSCC = 1 << 1,
3864 };
3865 
3866 } // end namespace llvm
3867 
3868 #endif // LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm::AANoUnwind::AANoUnwind
AANoUnwind(const IRPosition &IRP, Attributor &A)
Definition: Attributor.h:2510
llvm::AAIsDead::isKnownDead
virtual bool isKnownDead() const =0
Returns true if the underlying value is known dead.
llvm::AAMemoryBehavior::NO_ACCESSES
@ NO_ACCESSES
Definition: Attributor.h:3307
llvm::AAValueConstantRange::AAValueConstantRange
AAValueConstantRange(const IRPosition &IRP, Attributor &A)
Definition: Attributor.h:3531
llvm::ConstantRange::isFullSet
bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
Definition: ConstantRange.cpp:310
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::CallGraphUpdater
Wrapper to unify "old style" CallGraph and "new style" LazyCallGraph.
Definition: CallGraphUpdater.h:28
llvm::IntegerStateBase::indicateOptimisticFixpoint
ChangeStatus indicateOptimisticFixpoint() override
See AbstractState::indicateOptimisticFixpoint(...)
Definition: Attributor.h:1847
llvm::IntegerStateBase::base_t
base_ty base_t
Definition: Attributor.h:1822
llvm::PotentialValuesState::indicatePessimisticFixpoint
ChangeStatus indicatePessimisticFixpoint() override
See AbstractState::indicatePessimisticFixpoint(...)
Definition: Attributor.h:3608
llvm::PotentialValuesState::MaxPotentialValues
static unsigned MaxPotentialValues
Maximum number of potential values to be tracked.
Definition: Attributor.h:3646
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
llvm::AANoSync::isAssumedNoSync
bool isAssumedNoSync() const
Returns true if "nosync" is assumed.
Definition: Attributor.h:2542
llvm::IRPosition::function
static const IRPosition function(const Function &F, const CallBaseContext *CBContext=nullptr)
Create a position describing the function scope of F.
Definition: Attributor.h:275
Attrs
Function Attrs
Definition: README_ALTIVEC.txt:215
llvm::AAMemoryBehavior::classof
static bool classof(const AbstractAttribute *AA)
This function should return true if the type of the AA is AAMemoryBehavior.
Definition: Attributor.h:3349
llvm::AADepGraphNode::DepGetValAA
static AbstractAttribute * DepGetValAA(DepTy &DT)
Definition: Attributor.h:175
llvm::AAMemoryLocation::getName
const std::string getName() const override
See AbstractAttribute::getName()
Definition: Attributor.h:3512
llvm::IntegerStateBase::IntegerStateBase
IntegerStateBase(base_t Assumed)
Definition: Attributor.h:1825
llvm::AAMemoryBehavior::NO_WRITES
@ NO_WRITES
Definition: Attributor.h:3306
llvm::Attributor::changeToUnreachableAfterManifest
void changeToUnreachableAfterManifest(Instruction *I)
Record that I is to be replaced with unreachable after information was manifested.
Definition: Attributor.h:1374
llvm::BitIntegerState
Specialization of the integer state for a bit-wise encoding.
Definition: Attributor.h:1922
llvm::AAValueConstantRange
An abstract interface for range value analysis.
Definition: Attributor.h:3528
llvm::PotentialValuesState::getBestState
static PotentialValuesState getBestState(PotentialValuesState &PVS)
Definition: Attributor.h:3653
AccessKind
AccessKind
Definition: AArch64InstrInfo.cpp:1268
llvm::AAMemoryLocation::isKnownInaccessibleMemOnly
bool isKnownInaccessibleMemOnly() const
Return true if we know that the underlying value will only access inaccesible memory only (see Attrib...
Definition: Attributor.h:3415
llvm
Definition: AllocatorList.h:23
llvm::AANoUndef::ID
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:3855
llvm::AANoSync::AANoSync
AANoSync(const IRPosition &IRP, Attributor &A)
Definition: Attributor.h:2539
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::AAPrivatizablePtr::classof
static bool classof(const AbstractAttribute *AA)
This function should return true if the type of the AA is AAPricatizablePtr.
Definition: Attributor.h:3286
llvm::AbstractAttribute::dump
void dump() const
Definition: Attributor.h:2373
llvm::AANoUndef::classof
static bool classof(const AbstractAttribute *AA)
This function should return true if the type of the AA is AANoUndef.
Definition: Attributor.h:3850
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::TimeTraceScope
The TimeTraceScope is a helper class to call the begin and end functions of the time trace profiler.
Definition: TimeProfiler.h:65
llvm::AAMemoryLocation::isKnowStackOnly
bool isKnowStackOnly() const
Return true if we know that the associated functions has at most local/stack accesses.
Definition: Attributor.h:3403
llvm::IRPosition::getCallBaseContext
const CallBaseContext * getCallBaseContext() const
Get the call base context from the position.
Definition: Attributor.h:569
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::AAReturnedValues::returned_values
virtual llvm::iterator_range< iterator > returned_values()=0
llvm::IRPosition::getAssociatedFunction
Function * getAssociatedFunction() const
Return the associated function, if any.
Definition: Attributor.h:363
llvm::AAAlign::AAAlign
AAAlign(const IRPosition &IRP, Attributor &A)
Definition: Attributor.h:3103
llvm::Attributor::ArgumentReplacementInfo::getAttributor
Attributor & getAttributor() const
Simple getters, see the corresponding members for details.
Definition: Attributor.h:1477
llvm::AAReachability::getName
const std::string getName() const override
See AbstractAttribute::getName()
Definition: Attributor.h:2719
llvm::IntegerStateBase::operator|=
void operator|=(const IntegerStateBase< base_t, BestState, WorstState > &R)
Definition: Attributor.h:1891
llvm::IncIntegerState::IncIntegerState
IncIntegerState()
Definition: Attributor.h:1986
llvm::IntegerStateBase::joinOR
virtual void joinOR(base_t AssumedValue, base_t KnownValue)=0
Handle a value Value. Subtype dependent.
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
llvm::IRPosition::isArgumentPosition
bool isArgumentPosition() const
Return true if the position is an argument or call site argument.
Definition: Attributor.h:551
llvm::AANoUndef::createForPosition
static AANoUndef & createForPosition(const IRPosition &IRP, Attributor &A)
Create an abstract attribute view for the position IRP.
llvm::BitIntegerState::removeAssumedBits
BitIntegerState & removeAssumedBits(base_t BitsEncoding)
Remove the bits in BitsEncoding from the "assumed bits" if not known.
Definition: Attributor.h:1945
llvm::Attributor::ArgumentReplacementInfo
Helper struct used in the communication between an abstract attribute (AA) that wants to change the s...
Definition: Attributor.h:1449
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::IntegerRangeState::intersectKnown
void intersectKnown(const ConstantRange &R)
Intersect known range with the passed state.
Definition: Attributor.h:2188
llvm::PotentialValuesState::SetTy
DenseSet< MemberTy, KeyInfo > SetTy
Definition: Attributor.h:3594
llvm::AAMemoryLocation::getIdAddr
const char * getIdAddr() const override
See AbstractAttribute::getIdAddr()
Definition: Attributor.h:3515
llvm::AAMemoryBehavior::isKnownWriteOnly
bool isKnownWriteOnly() const
Return true if we know that the underlying value is not read in its respective scope.
Definition: Attributor.h:3331
llvm::Function
Definition: Function.h:61
llvm::IntegerRangeState::operator^=
IntegerRangeState operator^=(const IntegerRangeState &R)
"Clamp" this state with R.
Definition: Attributor.h:2206
llvm::AADereferenceable::isKnownGlobal
bool isKnownGlobal() const
Return true if we know that underlying value is dereferenceable(_or_null) globally.
Definition: Attributor.h:3065
llvm::AbstractAttribute::update
ChangeStatus update(Attributor &A)
Hook for the Attributor to trigger an update of the internal state.
Definition: Attributor.cpp:277
llvm::ALL
@ ALL
Definition: Attributor.h:3863
llvm::AANonNull::createForPosition
static AANonNull & createForPosition(const IRPosition &IRP, Attributor &A)
Create an abstract attribute view for the position IRP.
llvm::AAMemoryLocation::isKnownReadNone
bool isKnownReadNone() const
Return true if we know that the associated functions has no observable accesses.
Definition: Attributor.h:3393
llvm::AAUndefinedBehavior::classof
static bool classof(const AbstractAttribute *AA)
This function should return true if the type of the AA is AAUndefineBehavior.
Definition: Attributor.h:2685
llvm::AAWillReturn
An abstract attribute for willreturn.
Definition: Attributor.h:2626
llvm::IntegerRangeState::operator==
bool operator==(const IntegerRangeState &R) const
Equality for IntegerRangeState.
Definition: Attributor.h:2199
llvm::StateWrapper::getState
StateType & getState() override
See AbstractAttribute::getState(...).
Definition: Attributor.h:2238
llvm::Attribute::get
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:92
llvm::AANoRecurse
An abstract attribute for norecurse.
Definition: Attributor.h:2596
llvm::AAReachability
An abstract interface to determine reachability of point A to B.
Definition: Attributor.h:2694
llvm::AAMemoryLocation::createForPosition
static AAMemoryLocation & createForPosition(const IRPosition &IRP, Attributor &A)
Create an abstract attribute view for the position IRP.
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
llvm::IntegerRangeState::unionAssumed
void unionAssumed(const ConstantRange &R)
Unite assumed range with the passed state.
Definition: Attributor.h:2167
llvm::AANoCapture::classof
static bool classof(const AbstractAttribute *AA)
This function should return true if the type of the AA is AANoCapture.
Definition: Attributor.h:3183
llvm::IRPosition::value
static const IRPosition value(const Value &V, const CallBaseContext *CBContext=nullptr)
Create a position describing the value of V.
Definition: Attributor.h:264
llvm::AAHeapToStack::ID
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:3246
llvm::IntegerStateBase::getBestState
static constexpr base_t getBestState(const IntegerStateBase &)
Definition: Attributor.h:1829
llvm::AANoRecurse::getIdAddr
const char * getIdAddr() const override
See AbstractAttribute::getIdAddr()
Definition: Attributor.h:2614
llvm::AnalysisGetter::AnalysisGetter
AnalysisGetter()
Definition: Attributor.h:783
llvm::AbstractAttribute::initialize
virtual void initialize(Attributor &A)
Initialize the state with the information in the Attributor A.
Definition: Attributor.h:2359
llvm::AANoUnwind::isAssumedNoUnwind
bool isAssumedNoUnwind() const
Returns true if nounwind is assumed.
Definition: Attributor.h:2513
llvm::AANoUnwind::getName
const std::string getName() const override
See AbstractAttribute::getName()
Definition: Attributor.h:2522
llvm::AANoReturn::getName
const std::string getName() const override
See AbstractAttribute::getName()
Definition: Attributor.h:2810
llvm::AADereferenceable::AADereferenceable
AADereferenceable(const IRPosition &IRP, Attributor &A)
Definition: Attributor.h:3047
llvm::SmallDenseSet
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:286
llvm::AbstractAttribute::getName
virtual const std::string getName() const =0
This function should return the name of the AbstractAttribute.
llvm::IntegerRangeState::Assumed
ConstantRange Assumed
State representing assumed range, initially set to empty.
Definition: Attributor.h:2111
MapVector.h
llvm::StateWrapper
Helper to tie a abstract state implementation to an abstract attribute.
Definition: Attributor.h:2230
Allocator.h
llvm::AAMemoryLocation::getMemoryLocationsAsStr
static std::string getMemoryLocationsAsStr(MemoryLocationsKind MLK)
Return the locations encoded by MLK as a readable string.
Definition: AttributorAttributes.cpp:6433
llvm::AANoUndef::getName
const std::string getName() const override
See AbstractAttribute::getName()
Definition: Attributor.h:3844
llvm::AAMemoryLocation::isAssumedStackOnly
bool isAssumedStackOnly() const
Return true if we assume that the associated functions has at most local/stack accesses.
Definition: Attributor.h:3409
llvm::IRPosition::isAnyCallSitePosition
bool isAnyCallSitePosition() const
Definition: Attributor.h:539
llvm::AADepGraph::~AADepGraph
~AADepGraph()
Definition: Attributor.h:206
llvm::SubsumingPositionIterator::SubsumingPositionIterator
SubsumingPositionIterator(const IRPosition &IRP)
Definition: Attributor.cpp:354
llvm::Attributor::deleteAfterManifest
void deleteAfterManifest(Function &F)
Record that F is deleted after information was manifested.
Definition: Attributor.h:1394
llvm::AAMemoryLocation::isAssumedSpecifiedMemOnly
bool isAssumedSpecifiedMemOnly(MemoryLocationsKind MLK) const
Return true if only the memory locations specififed by MLK are assumed to be accessed by the associat...
Definition: Attributor.h:3459
llvm::AANoCapture::AANoCapture
AANoCapture(const IRPosition &IRP, Attributor &A)
Definition: Attributor.h:3134
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
llvm::IRPosition::getAttrs
void getAttrs(ArrayRef< Attribute::AttrKind > AKs, SmallVectorImpl< Attribute > &Attrs, bool IgnoreSubsumingPositions=false, Attributor *A=nullptr) const
Return the attributes of any kind in AKs existing in the IR at a position that will affect this one.
Definition: Attributor.cpp:440
llvm::AbstractAttribute::classof
static bool classof(const AADepGraphNode *DGN)
This function is used to identify if an DGN is of type AbstractAttribute so that the dyn_cast and cas...
Definition: Attributor.h:2349
llvm::AANoCapture
An abstract interface for all nocapture attributes.
Definition: Attributor.h:3130
llvm::AADepGraph::dumpGraph
void dumpGraph()
Dump graph to file.
Definition: Attributor.cpp:2451
llvm::CallBase::getArgOperandUse
const Use & getArgOperandUse(unsigned i) const
Wrappers for getting the Use of a call argument.
Definition: InstrTypes.h:1352
llvm::AAPotentialValues::getState
const PotentialConstantIntValuesState & getState() const override
Definition: Attributor.h:3785
llvm::Attributor::getDataLayout
const DataLayout & getDataLayout() const
Return the data layout associated with the anchor scope.
Definition: Attributor.h:1618
llvm::Attributor::checkForAllUses
bool checkForAllUses(function_ref< bool(const Use &, bool &)> Pred, const AbstractAttribute &QueryingAA, const Value &V, DepClassTy LivenessDepClass=DepClassTy::OPTIONAL)
Check Pred on all (transitive) uses of V.
Definition: Attributor.cpp:718
llvm::IRAttribute
Helper class that provides common functionality to manifest IR attributes.
Definition: Attributor.h:2246
llvm::Attributor::isRunOn
bool isRunOn(Function &Fn) const
Return true if we derive attributes for Fn.
Definition: Attributor.h:1303
llvm::AAPotentialValues::getState
PotentialConstantIntValuesState & getState() override
See AbstractAttribute::getState(...).
Definition: Attributor.h:3784
llvm::AbstractState::indicatePessimisticFixpoint
virtual ChangeStatus indicatePessimisticFixpoint()=0
Indicate that the abstract state should converge to the pessimistic state.
llvm::IntegerStateBase::getWorstState
static constexpr base_t getWorstState()
Return the worst possible representable state.
Definition: Attributor.h:1834
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
llvm::AADereferenceable::isKnownNonNull
bool isKnownNonNull() const
Return true if we know that the underlying value is nonnull.
Definition: Attributor.h:3055
llvm::AttributeList
Definition: Attributes.h:385
llvm::tgtok::Bits
@ Bits
Definition: TGLexer.h:50
Analysis
block Block Frequency Analysis
Definition: BlockFrequencyInfo.cpp:302
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
llvm::IRPosition::getAssociatedType
Type * getAssociatedType() const
Return the type this abstract attribute is associated with.
Definition: Attributor.h:427
llvm::AANoSync::getIdAddr
const char * getIdAddr() const override
See AbstractAttribute::getIdAddr()
Definition: Attributor.h:2554
llvm::InformationCache::ModuleSlice
SmallPtrSet< Function *, 8 > ModuleSlice
The slice of the module we are allowed to look at.
Definition: Attributor.h:890
llvm::IntegerRangeState::getBestState
static ConstantRange getBestState(uint32_t BitWidth)
Return the best possible representable state.
Definition: Attributor.h:2130
llvm::PotentialValuesState::unionAssumed
void unionAssumed(const PotentialValuesState &PVS)
Union assumed set with assumed set of the passed state PVS.
Definition: Attributor.h:3666
llvm::IntegerRangeState::IntegerRangeState
IntegerRangeState(const ConstantRange &CR)
Definition: Attributor.h:2120
llvm::operator!=
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:2039
llvm::InformationCache
Data structure to hold cached (LLVM-IR) information.
Definition: Attributor.h:801
llvm::BitIntegerState::intersectAssumedBits
BitIntegerState & intersectAssumedBits(base_t BitsEncoding)
Keep only "assumed bits" also set in BitsEncoding but all known ones.
Definition: Attributor.h:1956
llvm::AAIsDead::createForPosition
static AAIsDead & createForPosition(const IRPosition &IRP, Attributor &A)
Create an abstract attribute view for the position IRP.
llvm::Function::hasFnAttribute
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:355
llvm::Optional
Definition: APInt.h:33
llvm::BumpPtrAllocator
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition: Allocator.h:369
llvm::InformationCache::getAAResultsForFunction
AAResults * getAAResultsForFunction(const Function &F)
Return AliasAnalysis Result for function F.
Definition: Attributor.cpp:1998
llvm::mapped_iterator
Definition: STLExtras.h:277
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::AADepGraph::SyntheticRoot
AADepGraphNode SyntheticRoot
There is no root node for the dependency graph.
Definition: Attributor.h:216
llvm::AAReturnedValues::iterator
MapVector< Value *, SmallSetVector< ReturnInst *, 4 > >::iterator iterator
Definition: Attributor.h:2478
llvm::AbstractAttribute::manifest
virtual ChangeStatus manifest(Attributor &A)
Hook for the Attributor to trigger the manifestation of the information represented by the abstract a...
Definition: Attributor.h:2401
llvm::Attributor::recordDependence
void recordDependence(const AbstractAttribute &FromAA, const AbstractAttribute &ToAA, DepClassTy DepClass)
Explicitly record a dependence from FromAA to ToAA, that is if FromAA changes ToAA should be updated ...
Definition: Attributor.cpp:2009
llvm::AADereferenceable::isAssumedNonNull
bool isAssumedNonNull() const
Return true if we assume that the underlying value is nonnull.
Definition: Attributor.h:3050
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::AADereferenceable::classof
static bool classof(const AbstractAttribute *AA)
This function should return true if the type of the AA is AADereferenceable.
Definition: Attributor.h:3089
llvm::Attributor::run
ChangeStatus run()
Run the analyses until a fixpoint is reached or enforced (timeout).
Definition: Attributor.cpp:1467
llvm::AAValueSimplify
An abstract interface for value simplify abstract attribute.
Definition: Attributor.h:3192
llvm::AAMemoryLocation::isAssumedInaccessibleMemOnly
bool isAssumedInaccessibleMemOnly() const
Return true if we assume that the underlying value will only access inaccesible memory only (see Attr...
Definition: Attributor.h:3421
llvm::AAWillReturn::isKnownWillReturn
bool isKnownWillReturn() const
Return true if "willreturn" is known.
Definition: Attributor.h:2635
llvm::AAPrivatizablePtr::getPrivatizableType
virtual Optional< Type * > getPrivatizableType() const =0
Return the type we can choose for a private copy of the underlying value.
llvm::IRPosition::IRP_ARGUMENT
@ IRP_ARGUMENT
An attribute for a function argument.
Definition: Attributor.h:254
llvm::Attributor::~Attributor
~Attributor()
Definition: Attributor.cpp:594
llvm::AADepGraphNode::end
aaiterator end()
Definition: Attributor.h:188
llvm::IRPosition::IRP_RETURNED
@ IRP_RETURNED
An attribute for the function return value.
Definition: Attributor.h:250
llvm::AAMemoryLocation::isAssumedArgMemOnly
bool isAssumedArgMemOnly() const
Return true if we assume that the underlying value will only access argument pointees (see Attribute:...
Definition: Attributor.h:3433
llvm::createAttributorLegacyPass
Pass * createAttributorLegacyPass()
Definition: Attributor.cpp:2644
llvm::AAPotentialValues::ID
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:3825
llvm::Attributor::checkForAllReturnedValues
bool checkForAllReturnedValues(function_ref< bool(Value &)> Pred, const AbstractAttribute &QueryingAA)
Check Pred on all values potentially returned by the function associated with QueryingAA.
Definition: Attributor.cpp:918
llvm::BooleanState::BooleanState
BooleanState()
Definition: Attributor.h:2067
llvm::AANoReturn::createForPosition
static AANoReturn & createForPosition(const IRPosition &IRP, Attributor &A)
Create an abstract attribute view for the position IRP.
llvm::AAUndefinedBehavior
An abstract attribute for undefined behavior.
Definition: Attributor.h:2656
STLExtras.h
llvm::AbstractCallSite
AbstractCallSite.
Definition: AbstractCallSite.h:50
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:634
llvm::DenseMapInfo< IRPosition >::getTombstoneKey
static IRPosition getTombstoneKey()
Definition: Attributor.h:726
llvm::DerefState
State for dereferenceable attribute.
Definition: Attributor.h:2898
llvm::SubsumingPositionIterator::begin
iterator begin()
Definition: Attributor.h:769
llvm::AANoUndef::getIdAddr
const char * getIdAddr() const override
See AbstractAttribute::getIdAddr()
Definition: Attributor.h:3847
llvm::AAValueConstantRange::createForPosition
static AAValueConstantRange & createForPosition(const IRPosition &IRP, Attributor &A)
Create an abstract attribute view for the position IRP.
llvm::Attributor::Allocator
BumpPtrAllocator & Allocator
The allocator used to allocate memory, e.g. for AbstractAttributes.
Definition: Attributor.h:1621
llvm::AAUndefinedBehavior::isAssumedToCauseUB
bool isAssumedToCauseUB() const
Return true if "undefined behavior" is assumed.
Definition: Attributor.h:2662
llvm::SIInstrFlags::DS
@ DS
Definition: SIDefines.h:52
BaseType
llvm::AAAlign::ID
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:3126
llvm::AAMemoryBehavior::isKnownReadOnly
bool isKnownReadOnly() const
Return true if we know that the underlying value is not accessed (=written) in its respective scope.
Definition: Attributor.h:3323
llvm::AAMemoryLocation::isAssumedReadNone
bool isAssumedReadNone() const
Return true if we assume that the associated functions has no observable accesses.
Definition: Attributor.h:3397
llvm::IntegerRangeState::unionAssumed
void unionAssumed(const IntegerRangeState &R)
See IntegerRangeState::unionAssumed(..).
Definition: Attributor.h:2173
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::Attributor::deleteAfterManifest
void deleteAfterManifest(Instruction &I)
Record that I is deleted after information was manifested.
Definition: Attributor.h:1387
llvm::IRPosition::hasCallBaseContext
bool hasCallBaseContext() const
Check if the position has any call base context.
Definition: Attributor.h:572
llvm::AAAlign::classof
static bool classof(const AbstractAttribute *AA)
This function should return true if the type of the AA is AAAlign.
Definition: Attributor.h:3118
llvm::AbstractCallSite::getNumArgOperands
unsigned getNumArgOperands() const
Return the number of parameters of the callee.
Definition: AbstractCallSite.h:154
llvm::AAIsDead::mayCatchAsynchronousExceptions
static bool mayCatchAsynchronousExceptions(const Function &F)
Determine if F might catch asynchronous exceptions.
Definition: Attributor.h:2870
llvm::InformationCache::InstructionVectorTy
SmallVector< Instruction *, 8 > InstructionVectorTy
A vector type to hold instructions.
Definition: Attributor.h:893
llvm::IRPosition::IRP_FLOAT
@ IRP_FLOAT
A position that is not associated with a spot suitable for attributes.
Definition: Attributor.h:248
llvm::IntegerRangeState::getWorstState
static ConstantRange getWorstState(uint32_t BitWidth)
Return the worst possible representable state.
Definition: Attributor.h:2125
MustExecute.h
llvm::IncIntegerState::IncIntegerState
IncIntegerState(base_t Assumed)
Definition: Attributor.h:1987
llvm::MaxInitializationChainLength
unsigned MaxInitializationChainLength
The value passed to the line option that defines the maximal initialization chain length.
Definition: Attributor.cpp:88
llvm::DenseMapInfo< IRPosition >::getEmptyKey
static IRPosition getEmptyKey()
Definition: Attributor.h:725
llvm::IRAttributeManifest::manifestAttrs
static ChangeStatus manifestAttrs(Attributor &A, const IRPosition &IRP, const ArrayRef< Attribute > &DeducedAttrs)
Definition: Attributor.cpp:293
llvm::AANoReturn::isKnownNoReturn
bool isKnownNoReturn() const
Return true if the underlying object is known to never return.
Definition: Attributor.h:2804
llvm::AAReachability::getIdAddr
const char * getIdAddr() const override
See AbstractAttribute::getIdAddr()
Definition: Attributor.h:2722
llvm::AANonNull::isAssumedNonNull
bool isAssumedNonNull() const
Return true if we assume that the underlying value is nonnull.
Definition: Attributor.h:2572
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:180
llvm::IntegerStateBase::operator^=
void operator^=(const IntegerStateBase< base_t, BestState, WorstState > &R)
"Clamp" this state with R.
Definition: Attributor.h:1880
llvm::AANoFree::isKnownNoFree
bool isKnownNoFree() const
Return true if "nofree" is known.
Definition: Attributor.h:2774
llvm::AAAlign
An abstract interface for all align attributes.
Definition: Attributor.h:3100
llvm::AANoAlias::ID
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:2761
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::AAMemoryLocation::NO_LOCAL_MEM
@ NO_LOCAL_MEM
Definition: Attributor.h:3371
a
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
Definition: README.txt:489
llvm::IntegerRangeState::operator&=
IntegerRangeState operator&=(const IntegerRangeState &R)
Definition: Attributor.h:2213
llvm::createAttributorCGSCCLegacyPass
Pass * createAttributorCGSCCLegacyPass()
Definition: Attributor.cpp:2645
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
GraphTraits.h
llvm::AAMemoryBehavior::isKnownReadNone
bool isKnownReadNone() const
Return true if we know that the underlying value is not read or accessed in its respective scope.
Definition: Attributor.h:3315
llvm::AbstractAttribute::trackStatistics
virtual void trackStatistics() const =0
Hook to enable custom statistic tracking, called after manifest that resulted in a change if statisti...
llvm::IntegerStateBase::getBestState
static constexpr base_t getBestState()
Return the best possible representable state.
Definition: Attributor.h:1828
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
llvm::AANoCapture::isAssumedNoCapture
bool isAssumedNoCapture() const
Return true if we assume that the underlying value is not captured in its respective scope.
Definition: Attributor.h:3159
llvm::AANoFree::getIdAddr
const char * getIdAddr() const override
See AbstractAttribute::getIdAddr()
Definition: Attributor.h:2783
llvm::MODULE
@ MODULE
Definition: Attributor.h:3861
llvm::Intrinsic::getType
FunctionType * getType(LLVMContext &Context, ID id, ArrayRef< Type * > Tys=None)
Return the function type for an intrinsic.
Definition: Function.cpp:1285
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::operator&=
bool operator&=(SparseBitVector< ElementSize > *LHS, const SparseBitVector< ElementSize > &RHS)
Definition: SparseBitVector.h:834
llvm::PotentialValuesState::operator==
bool operator==(const PotentialValuesState &RHS) const
Definition: Attributor.h:3634
llvm::AANoSync::classof
static bool classof(const AbstractAttribute *AA)
This function should return true if the type of the AA is AANoSync.
Definition: Attributor.h:2557
llvm::AADereferenceable::createForPosition
static AADereferenceable & createForPosition(const IRPosition &IRP, Attributor &A)
Create an abstract attribute view for the position IRP.
llvm::IRPosition::callsite_argument
static const IRPosition callsite_argument(AbstractCallSite ACS, unsigned ArgNo)
Create a position describing the argument of ACS at position ArgNo.
Definition: Attributor.h:312
llvm::AANoCapture::NOT_CAPTURED_IN_INT
@ NOT_CAPTURED_IN_INT
Definition: Attributor.h:3140
llvm::IRAttribute::IRAttribute
IRAttribute(const IRPosition &IRP)
Definition: Attributor.h:2247
llvm::AttributorPass
}
Definition: Attributor.h:2440
llvm::LazyCallGraph::SCC
An SCC of the call graph.
Definition: LazyCallGraph.h:421
llvm::Attributor::checkForAllCallSites
bool checkForAllCallSites(function_ref< bool(AbstractCallSite)> Pred, const AbstractAttribute &QueryingAA, bool RequireAllCallSites, bool &AllCallSitesKnown)
Check Pred on all function call sites.
Definition: Attributor.cpp:783
llvm::InformationCache::getKnowledgeMap
const RetainedKnowledgeMap & getKnowledgeMap() const
Return the map conaining all the knowledge we have from llvm.assumes.
Definition: Attributor.h:946
llvm::AANoCapture::createForPosition
static AANoCapture & createForPosition(const IRPosition &IRP, Attributor &A)
Create an abstract attribute view for the position IRP.
llvm::AAMemoryBehavior
An abstract interface for memory access kind related attributes (readnone/readonly/writeonly).
Definition: Attributor.h:3296
llvm::AANonNull::getName
const std::string getName() const override
See AbstractAttribute::getName()
Definition: Attributor.h:2581
llvm::PotentialValuesState::getWorstState
static PotentialValuesState getWorstState()
Return full set as the worst state of potential values.
Definition: Attributor.h:3658
llvm::IRPosition::stripCallBaseContext
IRPosition stripCallBaseContext() const
Return the same position without the call base context.
Definition: Attributor.h:562
llvm::DerefState::AccessedBytesMap
std::map< int64_t, uint64_t > AccessedBytesMap
Map representing for accessed memory offsets and sizes.
Definition: Attributor.h:2922
llvm::AADereferenceable::getName
const std::string getName() const override
See AbstractAttribute::getName()
Definition: Attributor.h:3082
llvm::AAResults
Definition: AliasAnalysis.h:456
llvm::AAMemoryLocation::checkForAllAccessesToMemoryKind
virtual bool checkForAllAccessesToMemoryKind(function_ref< bool(const Instruction *, const Value *, AccessKind, MemoryLocationsKind)> Pred, MemoryLocationsKind MLK) const =0
Check Pred on all accesses to the memory kinds specified by MLK.
PostDominators.h
llvm::IntegerRangeState::unionKnown
void unionKnown(const ConstantRange &R)
Unite known range with the passed state.
Definition: Attributor.h:2178
llvm::Attributor::getAAFor
const AAType & getAAFor(const AbstractAttribute &QueryingAA, const IRPosition &IRP, DepClassTy DepClass)
Lookup an abstract attribute of type AAType at position IRP.
Definition: Attributor.h:1110
llvm::AAMemoryBehavior::isAssumedWriteOnly
bool isAssumedWriteOnly() const
Return true if we assume that the underlying value is not read in its respective scope.
Definition: Attributor.h:3335
llvm::IRAttribute::initialize
virtual void initialize(Attributor &A) override
See AbstractAttribute::initialize(...).
Definition: Attributor.h:2250
llvm::PotentialValuesState::getAssumed
const PotentialValuesState & getAssumed() const
Definition: Attributor.h:3619
llvm::AANoRecurse::AANoRecurse
AANoRecurse(const IRPosition &IRP, Attributor &A)
Definition: Attributor.h:2599
llvm::ChangeStatus
ChangeStatus
{
Definition: Attributor.h:148
llvm::Attributor::getOrCreateAAFor
const AAType & getOrCreateAAFor(IRPosition IRP, const AbstractAttribute *QueryingAA, DepClassTy DepClass, bool ForceUpdate=false)
The version of getAAFor that allows to omit a querying abstract attribute.
Definition: Attributor.h:1135
llvm::AAValueConstantRange::getIdAddr
const char * getIdAddr() const override
See AbstractAttribute::getIdAddr()
Definition: Attributor.h:3572
llvm::BooleanState::isKnown
bool isKnown() const
Return true if the state is known to hold.
Definition: Attributor.h:2083
llvm::AAReturnedValues::const_iterator
MapVector< Value *, SmallSetVector< ReturnInst *, 4 > >::const_iterator const_iterator
Definition: Attributor.h:2480
llvm::CallGraphUpdater::removeCallSite
void removeCallSite(CallBase &CS)
Remove the call site CS from the call graph.
Definition: CallGraphUpdater.cpp:160
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:647
llvm::AAReturnedValues
An abstract attribute for the returned values of a function.
Definition: Attributor.h:2456
llvm::AbstractAttribute::getState
virtual StateType & getState()=0
Return the internal abstract state for inspection.
llvm::IntegerRangeState::getBitWidth
uint32_t getBitWidth() const
Return associated values' bit width.
Definition: Attributor.h:2138
llvm::AAAlign::getAssumedAlign
unsigned getAssumedAlign() const
Return assumed alignment.
Definition: Attributor.h:3106
llvm::IntegerStateBase::operator!=
bool operator!=(const IntegerStateBase< base_t, BestState, WorstState > &R) const
Inequality for IntegerStateBase.
Definition: Attributor.h:1873
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::AbstractAttribute::printWithDeps
virtual void printWithDeps(raw_ostream &OS) const
Definition: Attributor.cpp:2352
llvm::AANoUndef::isAssumedNoUndef
bool isAssumedNoUndef() const
Return true if we assume that the underlying value is noundef.
Definition: Attributor.h:3835
llvm::AAUndefinedBehavior::isKnownToCauseUB
bool isKnownToCauseUB() const
Return true if "undefined behavior" is known.
Definition: Attributor.h:2668
llvm::IntegerStateBase::operator==
bool operator==(const IntegerStateBase< base_t, BestState, WorstState > &R) const
Equality for IntegerStateBase.
Definition: Attributor.h:1866
llvm::PotentialValuesState::isAtFixpoint
bool isAtFixpoint() const override
See AbstractState::isAtFixpoint(...)
Definition: Attributor.h:3605
llvm::AADepGraphNode::iterator
mapped_iterator< TinyPtrVector< DepTy >::iterator, decltype(&DepGetVal)> iterator
Definition: Attributor.h:183
llvm::AAPrivatizablePtr::AAPrivatizablePtr
AAPrivatizablePtr(const IRPosition &IRP, Attributor &A)
Definition: Attributor.h:3262
llvm::AANoAlias::getName
const std::string getName() const override
See AbstractAttribute::getName()
Definition: Attributor.h:2750
llvm::Attributor::registerInvokeWithDeadSuccessor
void registerInvokeWithDeadSuccessor(InvokeInst &II)
Record that II has at least one dead successor block.
Definition: Attributor.h:1381
llvm::operator+=
std::string & operator+=(std::string &buffer, StringRef string)
Definition: StringRef.h:919
llvm::AANonNull::classof
static bool classof(const AbstractAttribute *AA)
This function should return true if the type of the AA is AANonNull.
Definition: Attributor.h:2587
llvm::InformationCache::foreachUse
static void foreachUse(Function &F, CBTy CB, bool LookThroughConstantExprUses=true)
Apply CB to all uses of F.
Definition: Attributor.h:834
llvm::PotentialValuesState::isValidState
bool isValidState() const override
See AbstractState::isValidState(...)
Definition: Attributor.h:3602
AssumeBundleQueries.h
b
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int b
Definition: README.txt:418
llvm::AADepGraph::GetEntryNode
AADepGraphNode * GetEntryNode()
Definition: Attributor.h:217
llvm::AAMemoryLocation::NO_GLOBAL_EXTERNAL_MEM
@ NO_GLOBAL_EXTERNAL_MEM
Definition: Attributor.h:3374
llvm::AADepGraph::print
void print()
Print dependency graph.
Definition: Attributor.cpp:2473
llvm::DerefState::getBestState
static DerefState getBestState()
Definition: Attributor.h:2900
llvm::AAMemoryLocation
An abstract interface for all memory location attributes (readnone/argmemonly/inaccessiblememonly/ina...
Definition: Attributor.h:3359
llvm::BitIntegerState::base_t
base_ty base_t
Definition: Attributor.h:1924
TargetLibraryInfo.h
llvm::AADereferenceable
An abstract interface for all dereferenceable attribute.
Definition: Attributor.h:3044
llvm::AAPrivatizablePtr::createForPosition
static AAPrivatizablePtr & createForPosition(const IRPosition &IRP, Attributor &A)
Create an abstract attribute view for the position IRP.
l
This requires reassociating to forms of expressions that are already something that reassoc doesn t think about yet These two functions should generate the same code on big endian int * l
Definition: README.txt:100
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:377
DenseSet.h
false
Definition: StackSlotColoring.cpp:142
llvm::AANoSync
Definition: Attributor.h:2536
llvm::AAReturnedValues::AAReturnedValues
AAReturnedValues(const IRPosition &IRP, Attributor &A)
Definition: Attributor.h:2458
llvm::isPotentiallyReachable
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
Definition: CFG.cpp:236
llvm::AbstractAttribute::~AbstractAttribute
virtual ~AbstractAttribute()
Virtual destructor.
Definition: Attributor.h:2341
llvm::AAPotentialValues::getName
const std::string getName() const override
See AbstractAttribute::getName()
Definition: Attributor.h:3813
llvm::RetainedKnowledgeMap
DenseMap< RetainedKnowledgeKey, Assume2KnowledgeMap > RetainedKnowledgeMap
Definition: AssumeBundleQueries.h:84
llvm::Attributor::getOrCreateAAFor
const AAType & getOrCreateAAFor(const IRPosition &IRP)
Definition: Attributor.h:1217
llvm::IRPosition::hasAttr
bool hasAttr(ArrayRef< Attribute::AttrKind > AKs, bool IgnoreSubsumingPositions=false, Attributor *A=nullptr) const
TODO: Figure out if the attribute related helper functions should live here or somewhere else.
Definition: Attributor.cpp:420
llvm::detail::DenseSetImpl::size
size_type size() const
Definition: DenseSet.h:81
llvm::IncIntegerState::getBestState
static constexpr base_t getBestState(const IncIntegerState< base_ty, BestState, WorstState > &)
Definition: Attributor.h:1992
llvm::BooleanState::setKnown
void setKnown(bool Value)
Set the known and asssumed value to Value.
Definition: Attributor.h:2074
llvm::AbstractState::isValidState
virtual bool isValidState() const =0
Return if this abstract state is in a valid state.
llvm::Instruction
Definition: Instruction.h:45
llvm::BooleanState::isAssumed
bool isAssumed() const
Return true if the state is assumed to hold.
Definition: Attributor.h:2080
llvm::AAMemoryLocation::NO_INACCESSIBLE_MEM
@ NO_INACCESSIBLE_MEM
Definition: Attributor.h:3377
llvm::AAMemoryBehavior::isAssumedReadNone
bool isAssumedReadNone() const
Return true if we assume that the underlying value is not read or accessed in its respective scope.
Definition: Attributor.h:3319
llvm::IRPosition::getPositionKind
Kind getPositionKind() const
Return the associated position kind.
Definition: Attributor.h:472
llvm::IRPosition::getCtxI
Instruction * getCtxI() const
Return the context instruction, if any.
Definition: Attributor.h:404
llvm::DepClassTy::OPTIONAL
@ OPTIONAL
The target may be valid if the source is not.
llvm::AttributeList::getAttributes
AttributeSet getAttributes(unsigned Index) const
The attributes for the specified index are returned.
Definition: Attributes.cpp:1667
llvm::ConstantRange::unionWith
ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
Definition: ConstantRange.cpp:574
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::AAValueSimplify::classof
static bool classof(const AbstractAttribute *AA)
This function should return true if the type of the AA is AAValueSimplify.
Definition: Attributor.h:3213
llvm::Attributor::ArgumentReplacementInfo::getReplacedFn
const Function & getReplacedFn() const
Definition: Attributor.h:1478
llvm::AAMemoryLocation::READ_WRITE
@ READ_WRITE
Definition: Attributor.h:3488
llvm::IntegerRangeState
State for an integer range.
Definition: Attributor.h:2105
llvm::AAWillReturn::getIdAddr
const char * getIdAddr() const override
See AbstractAttribute::getIdAddr()
Definition: Attributor.h:2644
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::AAHeapToStack::createForPosition
static AAHeapToStack & createForPosition(const IRPosition &IRP, Attributor &A)
Create an abstract attribute view for the position IRP.
llvm::PotentialValuesState
A class for a set state.
Definition: Attributor.h:3593
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:898
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:73
llvm::AANoUnwind::classof
static bool classof(const AbstractAttribute *AA)
This function should return true if the type of the AA is AANoUnwind.
Definition: Attributor.h:2528
llvm::IRPosition::operator!=
bool operator!=(const IRPosition &RHS) const
Definition: Attributor.h:341
llvm::AbstractCallSite::getInstruction
CallBase * getInstruction() const
Return the underlying instruction.
Definition: AbstractCallSite.h:112
llvm::AAMemoryLocation::NO_ARGUMENT_MEM
@ NO_ARGUMENT_MEM
Definition: Attributor.h:3376
llvm::AAHeapToStack::isAssumedHeapToStack
virtual bool isAssumedHeapToStack(CallBase &CB) const =0
Returns true if HeapToStack conversion is assumed to be possible.
llvm::AAPotentialValues::getIdAddr
const char * getIdAddr() const override
See AbstractAttribute::getIdAddr()
Definition: Attributor.h:3816
llvm::AANoCapture::NOT_CAPTURED_IN_RET
@ NOT_CAPTURED_IN_RET
Definition: Attributor.h:3141
llvm::AADepGraphNode::getDeps
TinyPtrVector< DepTy > & getDeps()
Definition: Attributor.h:193
LazyCallGraph.h
llvm::AANoFree::isAssumedNoFree
bool isAssumedNoFree() const
Return true if "nofree" is assumed.
Definition: Attributor.h:2771
llvm::AANoRecurse::classof
static bool classof(const AbstractAttribute *AA)
This function should return true if the type of the AA is AANoRecurse.
Definition: Attributor.h:2617
llvm::Attributor::removeCallSite
void removeCallSite(CallInst *CI)
Helper function to remove callsite.
Definition: Attributor.h:1339
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:153
llvm::Attributor::ArgumentReplacementInfo::getNumReplacementArgs
unsigned getNumReplacementArgs() const
Definition: Attributor.h:1480
llvm::AANoUnwind::ID
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:2533
llvm::None
const NoneType None
Definition: None.h:23
llvm::IRPosition::EmptyKey
static const IRPosition EmptyKey
Special DenseMap key values.
Definition: Attributor.h:577
llvm::AAMemoryLocation::isAssumedInaccessibleOrArgMemOnly
bool isAssumedInaccessibleOrArgMemOnly() const
Return true if we assume that the underlying value will only access inaccesible memory or argument po...
Definition: Attributor.h:3448
llvm::InformationCache::OpcodeInstMapTy
DenseMap< unsigned, InstructionVectorTy * > OpcodeInstMapTy
A map type from opcodes to instructions with this opcode.
Definition: Attributor.h:896
llvm::AADepGraph::iterator
mapped_iterator< TinyPtrVector< DepTy >::iterator, decltype(&DepGetVal)> iterator
Definition: Attributor.h:211
llvm::DenseMapInfo< IRPosition >::isEqual
static bool isEqual(const IRPosition &a, const IRPosition &b)
Definition: Attributor.h:734
llvm::AbstractState::isAtFixpoint
virtual bool isAtFixpoint() const =0
Return if this abstract state is fixed, thus does not need to be updated if information changes as it...
llvm::AAHeapToStack::classof
static bool classof(const AbstractAttribute *AA)
This function should return true if the type of the AA is AAHeapToStack.
Definition: Attributor.h:3241
llvm::AnalysisGetter::getAnalysis
Analysis::Result * getAnalysis(const Function &F)
Definition: Attributor.h:776
llvm::AADepGraphNode::Deps
TinyPtrVector< DepTy > Deps
Set of dependency graph nodes which should be updated if this one is updated.
Definition: Attributor.h:172
llvm::AANoCapture::getIdAddr
const char * getIdAddr() const override
See AbstractAttribute::getIdAddr()
Definition: Attributor.h:3180
llvm::AbstractAttribute::getAsStr
virtual const std::string getAsStr() const =0
This function should return the "summarized" assumed state as string.
llvm::AADepGraphNode::DepTy
PointerIntPair< AADepGraphNode *, 1 > DepTy
Definition: Attributor.h:167
llvm::IntegerRangeState::indicatePessimisticFixpoint
ChangeStatus indicatePessimisticFixpoint() override
See AbstractState::indicatePessimisticFixpoint(...)
Definition: Attributor.h:2155
llvm::DerefState::DerefBytesState
IncIntegerState DerefBytesState
State representing for dereferenceable bytes.
Definition: Attributor.h:2914
llvm::AANoRecurse::createForPosition
static AANoRecurse & createForPosition(const IRPosition &IRP, Attributor &A)
Create an abstract attribute view for the position IRP.
llvm::AAPrivatizablePtr::isAssumedPrivatizablePtr
bool isAssumedPrivatizablePtr() const
Returns true if pointer privatization is assumed to be possible.
Definition: Attributor.h:3265
LoopInfo.h
llvm::AttributorCGSCCPass::run
PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR)
Definition: Attributor.cpp:2498
llvm::Function::getAttributes
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:249
llvm::ChangeStatus::UNCHANGED
@ UNCHANGED
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3716
llvm::IRPosition::getCalleeArgNo
int getCalleeArgNo() const
Return the callee argument number of the associated value if it is an argument or call site argument,...
Definition: Attributor.h:438
llvm::IntegerRangeState::indicateOptimisticFixpoint
ChangeStatus indicateOptimisticFixpoint() override
See AbstractState::indicateOptimisticFixpoint(...)
Definition: Attributor.h:2149
llvm::IntegerRangeState::Known
ConstantRange Known
State representing known range, initially set to [-inf, inf].
Definition: Attributor.h:2114
llvm::AANoCapture::NO_CAPTURE
@ NO_CAPTURE
If we do not capture the value in memory, through integers, or as a derived pointer we know it is not...
Definition: Attributor.h:3149
llvm::BitmaskEnumDetail::operator^=
E & operator^=(E &LHS, E RHS)
Definition: BitmaskEnum.h:137
llvm::AAAlign::getName
const std::string getName() const override
See AbstractAttribute::getName()
Definition: Attributor.h:3112
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:168
llvm::BooleanState::setAssumed
void setAssumed(bool Value)
Set the assumed value to Value but never below the known one.
Definition: Attributor.h:2071
llvm::AAMemoryLocation::getAssumedNotAccessedLocation
MemoryLocationsKind getAssumedNotAccessedLocation() const
Return the locations that are assumed to be not accessed by the associated function,...
Definition: Attributor.h:3465
llvm::PointerIntPair::getPointer
PointerTy getPointer() const
Definition: PointerIntPair.h:59
llvm::AANoCapture::isKnownNoCaptureMaybeReturned
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:3163
llvm::AAPrivatizablePtr::isKnownPrivatizablePtr
bool isKnownPrivatizablePtr() const
Returns true if pointer privatization is known to be possible.
Definition: Attributor.h:3268
llvm::AAPotentialValues::createForPosition
static AAPotentialValues & createForPosition(const IRPosition &IRP, Attributor &A)
Create an abstract attribute view for the position IRP.
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::Attributor::createShallowWrapper
static void createShallowWrapper(Function &F)
Create a shallow wrapper for F such that F has internal linkage afterwards.
Definition: Attributor.cpp:1526
llvm::AttributorPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: Attributor.cpp:2478
llvm::AbstractState::~AbstractState
virtual ~AbstractState()
Definition: Attributor.h:1783
llvm::AAAlign::getIdAddr
const char * getIdAddr() const override
See AbstractAttribute::getIdAddr()
Definition: Attributor.h:3115
llvm::AAMemoryLocation::READ
@ READ
Definition: Attributor.h:3486
llvm::AANoFree::createForPosition
static AANoFree & createForPosition(const IRPosition &IRP, Attributor &A)
Create an abstract attribute view for the position IRP.
llvm::AANoSync::getName
const std::string getName() const override
See AbstractAttribute::getName()
Definition: Attributor.h:2551
llvm::AttributeList::ReturnIndex
@ ReturnIndex
Definition: Attributes.h:388
llvm::IRAttribute::manifest
ChangeStatus manifest(Attributor &A) override
See AbstractAttribute::manifest(...).
Definition: Attributor.h:2273
llvm::IRPosition::callsite_argument
static const IRPosition callsite_argument(const CallBase &CB, unsigned ArgNo)
Create a position describing the argument of CB at position ArgNo.
Definition: Attributor.h:305
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::Attributor::ArgumentReplacementInfo::ACSRepairCBTy
std::function< void(const ArgumentReplacementInfo &, AbstractCallSite, SmallVectorImpl< Value * > &)> ACSRepairCBTy
Abstract call site (ACS) repair callback type.
Definition: Attributor.h:1472
BaseType
BaseType
A given derived pointer can have multiple base pointers through phi/selects.
Definition: SafepointIRVerifier.cpp:316
llvm::AAReturnedValues::classof
static bool classof(const AbstractAttribute *AA)
This function should return true if the type of the AA is AAReturnedValues.
Definition: Attributor.h:2499
llvm::AAMemoryLocation::AAMemoryLocation
AAMemoryLocation(const IRPosition &IRP, Attributor &A)
Definition: Attributor.h:3365
llvm::AANoUndef::isKnownNoUndef
bool isKnownNoUndef() const
Return true if we know that underlying value is noundef.
Definition: Attributor.h:3838
llvm::InformationCache::isInModuleSlice
bool isInModuleSlice(const Function &F)
Check whether F is part of module slice.
Definition: Attributor.h:964
llvm::NONE
@ NONE
Do not track a dependence between source and target.
llvm::InformationCache::~InformationCache
~InformationCache()
Definition: Attributor.h:823
llvm::AANoAlias
An abstract interface for all noalias attributes.
Definition: Attributor.h:2735
llvm::operator|
APInt operator|(APInt a, const APInt &b)
Definition: APInt.h:2069
llvm::Function::getReturnType
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:180
llvm::IntegerStateBase::getKnown
base_t getKnown() const
Return the known state encoding.
Definition: Attributor.h:1859
llvm::AANoUndef
An abstract interface for all noundef attributes.
Definition: Attributor.h:3829
llvm::AbstractAttribute
Base struct for all "concrete attribute" deductions.
Definition: Attributor.h:2335
llvm::PotentialValuesState::PotentialValuesState
PotentialValuesState()
Definition: Attributor.h:3596
llvm::InformationCache::getOpcodeInstMapForFunction
OpcodeInstMapTy & getOpcodeInstMapForFunction(const Function &F)
Return the map that relates "interesting" opcodes with all instructions with that opcode in F.
Definition: Attributor.h:900
llvm::DepClassTy::REQUIRED
@ REQUIRED
The target cannot be valid if the source is not.
llvm::AAPrivatizablePtr
An abstract interface for privatizability.
Definition: Attributor.h:3259
llvm::AANoRecurse::isKnownNoRecurse
bool isKnownNoRecurse() const
Return true if "norecurse" is known.
Definition: Attributor.h:2605
llvm::AAIsDead::ID
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:2892
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::AAMemoryBehavior::getName
const std::string getName() const override
See AbstractAttribute::getName()
Definition: Attributor.h:3342
llvm::AADereferenceable::getIdAddr
const char * getIdAddr() const override
See AbstractAttribute::getIdAddr()
Definition: Attributor.h:3085
llvm::AAMemoryLocation::BEST_STATE
@ BEST_STATE
Definition: Attributor.h:3387
llvm::PointerIntPair::setFromOpaqueValue
void setFromOpaqueValue(void *Val) LLVM_LVALUE_FUNCTION
Definition: PointerIntPair.h:93
llvm::PotentialValuesState::indicateOptimisticFixpoint
ChangeStatus indicateOptimisticFixpoint() override
See AbstractState::indicateOptimisticFixpoint(...)
Definition: Attributor.h:3613
llvm::canSimplifyInvokeNoUnwind
bool canSimplifyInvokeNoUnwind(const Function *F)
Definition: EHPersonalities.cpp:73
llvm::AANoSync::isKnownNoSync
bool isKnownNoSync() const
Returns true if "nosync" is known.
Definition: Attributor.h:2545
llvm::IntegerRangeState::isValidState
bool isValidState() const override
See AbstractState::isValidState()
Definition: Attributor.h:2141
llvm::InformationCache::InformationCache
InformationCache(const Module &M, AnalysisGetter &AG, BumpPtrAllocator &Allocator, SetVector< Function * > *CGSCC)
Definition: Attributor.h:802
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
llvm::InformationCache::initializeModuleSlice
void initializeModuleSlice(SetVector< Function * > &SCC)
Initialize the ModuleSlice member based on SCC.
Definition: Attributor.h:858
llvm::DecIntegerState::takeKnownMinimum
DecIntegerState & takeKnownMinimum(base_t Value)
Take minimum of known and Value.
Definition: Attributor.h:2040
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::AttributorCGSCCPass
Definition: Attributor.h:2443
llvm::IRPosition::IRP_FUNCTION
@ IRP_FUNCTION
An attribute for a function (scope).
Definition: