LLVM  16.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/SetOperations.h"
105 #include "llvm/ADT/SetVector.h"
106 #include "llvm/ADT/Triple.h"
107 #include "llvm/ADT/iterator.h"
109 #include "llvm/Analysis/CFG.h"
112 #include "llvm/Analysis/LoopInfo.h"
118 #include "llvm/IR/ConstantRange.h"
119 #include "llvm/IR/Constants.h"
120 #include "llvm/IR/InstIterator.h"
121 #include "llvm/IR/Instruction.h"
122 #include "llvm/IR/PassManager.h"
123 #include "llvm/IR/Value.h"
124 #include "llvm/Support/Alignment.h"
125 #include "llvm/Support/Allocator.h"
126 #include "llvm/Support/Casting.h"
130 
131 #include <map>
132 
133 namespace llvm {
134 
135 class DataLayout;
136 class LLVMContext;
137 class Pass;
138 template <typename Fn> class function_ref;
139 struct AADepGraphNode;
140 struct AADepGraph;
141 struct Attributor;
142 struct AbstractAttribute;
143 struct InformationCache;
144 struct AAIsDead;
145 struct AttributorCallGraph;
146 struct IRPosition;
147 
148 class AAResults;
149 class Function;
150 
151 /// Abstract Attribute helper functions.
152 namespace AA {
153 
154 /// Flags to distinguish intra-procedural queries from *potentially*
155 /// inter-procedural queries. Not that information can be valid for both and
156 /// therefore both bits might be set.
157 enum ValueScope : uint8_t {
161 };
162 
163 struct ValueAndContext : public std::pair<Value *, const Instruction *> {
164  using Base = std::pair<Value *, const Instruction *>;
165  ValueAndContext(const Base &B) : Base(B) {}
166  ValueAndContext(Value &V, const Instruction *CtxI) : Base(&V, CtxI) {}
167  ValueAndContext(Value &V, const Instruction &CtxI) : Base(&V, &CtxI) {}
168 
169  Value *getValue() const { return this->first; }
170  const Instruction *getCtxI() const { return this->second; }
171 };
172 
173 /// Return true if \p I is a `nosync` instruction. Use generic reasoning and
174 /// potentially the corresponding AANoSync.
175 bool isNoSyncInst(Attributor &A, const Instruction &I,
176  const AbstractAttribute &QueryingAA);
177 
178 /// Return true if \p V is dynamically unique, that is, there are no two
179 /// "instances" of \p V at runtime with different values.
180 /// Note: If \p ForAnalysisOnly is set we only check that the Attributor will
181 /// never use \p V to represent two "instances" not that \p V could not
182 /// technically represent them.
183 bool isDynamicallyUnique(Attributor &A, const AbstractAttribute &QueryingAA,
184  const Value &V, bool ForAnalysisOnly = true);
185 
186 /// Return true if \p V is a valid value in \p Scope, that is a constant or an
187 /// instruction/argument of \p Scope.
188 bool isValidInScope(const Value &V, const Function *Scope);
189 
190 /// Return true if the value of \p VAC is a valid at the position of \p VAC,
191 /// that is a constant, an argument of the same function, or an instruction in
192 /// that function that dominates the position.
193 bool isValidAtPosition(const ValueAndContext &VAC, InformationCache &InfoCache);
194 
195 /// Try to convert \p V to type \p Ty without introducing new instructions. If
196 /// this is not possible return `nullptr`. Note: this function basically knows
197 /// how to cast various constants.
198 Value *getWithType(Value &V, Type &Ty);
199 
200 /// Return the combination of \p A and \p B such that the result is a possible
201 /// value of both. \p B is potentially casted to match the type \p Ty or the
202 /// type of \p A if \p Ty is null.
203 ///
204 /// Examples:
205 /// X + none => X
206 /// not_none + undef => not_none
207 /// V1 + V2 => nullptr
210  const Optional<Value *> &B, Type *Ty);
211 
212 /// Helper to represent an access offset and size, with logic to deal with
213 /// uncertainty and check for overlapping accesses.
215  int64_t Offset = Unassigned;
216  int64_t Size = Unassigned;
217 
218  OffsetAndSize(int64_t Offset, int64_t Size) : Offset(Offset), Size(Size) {}
219  OffsetAndSize() = default;
221 
222  /// Return true if offset or size are unknown.
223  bool offsetOrSizeAreUnknown() const {
225  }
226 
227  /// Return true if offset and size are unknown, thus this is the default
228  /// unknown object.
229  bool offsetAndSizeAreUnknown() const {
231  }
232 
233  /// Return true if the offset and size are unassigned.
234  bool isUnassigned() const {
237  "Inconsistent state!");
239  }
240 
241  /// Return true if this offset and size pair might describe an address that
242  /// overlaps with \p OAS.
243  bool mayOverlap(const OffsetAndSize &OAS) const {
244  // Any unknown value and we are giving up -> overlap.
246  return true;
247 
248  // Check if one offset point is in the other interval [offset,
249  // offset+size].
250  return OAS.Offset + OAS.Size > Offset && OAS.Offset < Offset + Size;
251  }
252 
254  if (Offset == Unassigned)
255  Offset = R.Offset;
256  else if (R.Offset != Unassigned && R.Offset != Offset)
257  Offset = Unknown;
258 
259  if (Size == Unassigned)
260  Size = R.Size;
261  else if (Size == Unknown || R.Size == Unknown)
262  Size = Unknown;
263  else if (R.Size != Unassigned)
264  Size = std::max(Size, R.Size);
265 
266  return *this;
267  }
268 
269  /// Constants used to represent special offsets or sizes.
270  /// - This assumes that Offset and Size are non-negative.
271  /// - The constants should not clash with DenseMapInfo, such as EmptyKey
272  /// (INT64_MAX) and TombstoneKey (INT64_MIN).
273  static constexpr int64_t Unassigned = -1;
274  static constexpr int64_t Unknown = -2;
275 };
276 
277 inline bool operator==(const OffsetAndSize &A, const OffsetAndSize &B) {
278  return A.Offset == B.Offset && A.Size == B.Size;
279 }
280 
281 inline bool operator!=(const OffsetAndSize &A, const OffsetAndSize &B) {
282  return !(A == B);
283 }
284 
285 /// Return the initial value of \p Obj with type \p Ty if that is a constant.
287  const TargetLibraryInfo *TLI,
288  const DataLayout &DL,
289  OffsetAndSize *OASPtr = nullptr);
290 
291 /// Collect all potential underlying objects of \p Ptr at position \p CtxI in
292 /// \p Objects. Assumed information is used and dependences onto \p QueryingAA
293 /// are added appropriately.
294 ///
295 /// \returns True if \p Objects contains all assumed underlying objects, and
296 /// false if something went wrong and the objects could not be
297 /// determined.
299  Attributor &A, const Value &Ptr, SmallSetVector<Value *, 8> &Objects,
300  const AbstractAttribute &QueryingAA, const Instruction *CtxI,
301  bool &UsedAssumedInformation, AA::ValueScope VS = AA::Interprocedural,
302  SmallPtrSetImpl<Value *> *SeenObjects = nullptr);
303 
304 /// Collect all potential values \p LI could read into \p PotentialValues. That
305 /// is, the only values read by \p LI are assumed to be known and all are in
306 /// \p PotentialValues. \p PotentialValueOrigins will contain all the
307 /// instructions that might have put a potential value into \p PotentialValues.
308 /// Dependences onto \p QueryingAA are properly tracked, \p
309 /// UsedAssumedInformation will inform the caller if assumed information was
310 /// used.
311 ///
312 /// \returns True if the assumed potential copies are all in \p PotentialValues,
313 /// false if something went wrong and the copies could not be
314 /// determined.
316  Attributor &A, LoadInst &LI, SmallSetVector<Value *, 4> &PotentialValues,
317  SmallSetVector<Instruction *, 4> &PotentialValueOrigins,
318  const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation,
319  bool OnlyExact = false);
320 
321 /// Collect all potential values of the one stored by \p SI into
322 /// \p PotentialCopies. That is, the only copies that were made via the
323 /// store are assumed to be known and all are in \p PotentialCopies. Dependences
324 /// onto \p QueryingAA are properly tracked, \p UsedAssumedInformation will
325 /// inform the caller if assumed information was used.
326 ///
327 /// \returns True if the assumed potential copies are all in \p PotentialCopies,
328 /// false if something went wrong and the copies could not be
329 /// determined.
331  Attributor &A, StoreInst &SI, SmallSetVector<Value *, 4> &PotentialCopies,
332  const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation,
333  bool OnlyExact = false);
334 
335 /// Return true if \p IRP is readonly. This will query respective AAs that
336 /// deduce the information and introduce dependences for \p QueryingAA.
337 bool isAssumedReadOnly(Attributor &A, const IRPosition &IRP,
338  const AbstractAttribute &QueryingAA, bool &IsKnown);
339 
340 /// Return true if \p IRP is readnone. This will query respective AAs that
341 /// deduce the information and introduce dependences for \p QueryingAA.
342 bool isAssumedReadNone(Attributor &A, const IRPosition &IRP,
343  const AbstractAttribute &QueryingAA, bool &IsKnown);
344 
345 /// Return true if \p ToI is potentially reachable from \p FromI. The two
346 /// instructions do not need to be in the same function. \p GoBackwardsCB
347 /// can be provided to convey domain knowledge about the "lifespan" the user is
348 /// interested in. By default, the callers of \p FromI are checked as well to
349 /// determine if \p ToI can be reached. If the query is not interested in
350 /// callers beyond a certain point, e.g., a GPU kernel entry or the function
351 /// containing an alloca, the \p GoBackwardsCB should return false.
353  Attributor &A, const Instruction &FromI, const Instruction &ToI,
354  const AbstractAttribute &QueryingAA,
355  std::function<bool(const Function &F)> GoBackwardsCB = nullptr);
356 
357 /// Same as above but it is sufficient to reach any instruction in \p ToFn.
359  Attributor &A, const Instruction &FromI, const Function &ToFn,
360  const AbstractAttribute &QueryingAA,
361  std::function<bool(const Function &F)> GoBackwardsCB);
362 
363 } // namespace AA
364 
365 template <>
366 struct DenseMapInfo<AA::ValueAndContext>
367  : public DenseMapInfo<AA::ValueAndContext::Base> {
370  return Base::getEmptyKey();
371  }
373  return Base::getTombstoneKey();
374  }
375  static unsigned getHashValue(const AA::ValueAndContext &VAC) {
376  return Base::getHashValue(VAC);
377  }
378 
379  static bool isEqual(const AA::ValueAndContext &LHS,
380  const AA::ValueAndContext &RHS) {
381  return Base::isEqual(LHS, RHS);
382  }
383 };
384 
385 template <>
386 struct DenseMapInfo<AA::ValueScope> : public DenseMapInfo<unsigned char> {
388  static inline AA::ValueScope getEmptyKey() {
389  return AA::ValueScope(Base::getEmptyKey());
390  }
391  static inline AA::ValueScope getTombstoneKey() {
392  return AA::ValueScope(Base::getTombstoneKey());
393  }
394  static unsigned getHashValue(const AA::ValueScope &S) {
395  return Base::getHashValue(S);
396  }
397 
398  static bool isEqual(const AA::ValueScope &LHS, const AA::ValueScope &RHS) {
399  return Base::isEqual(LHS, RHS);
400  }
401 };
402 
403 /// The value passed to the line option that defines the maximal initialization
404 /// chain length.
405 extern unsigned MaxInitializationChainLength;
406 
407 ///{
408 enum class ChangeStatus {
409  CHANGED,
410  UNCHANGED,
411 };
412 
417 
418 enum class DepClassTy {
419  REQUIRED, ///< The target cannot be valid if the source is not.
420  OPTIONAL, ///< The target may be valid if the source is not.
421  NONE, ///< Do not track a dependence between source and target.
422 };
423 ///}
424 
425 /// The data structure for the nodes of a dependency graph
427 public:
428  virtual ~AADepGraphNode() = default;
430 
431 protected:
432  /// Set of dependency graph nodes which should be updated if this one
433  /// is updated. The bit encodes if it is optional.
435 
436  static AADepGraphNode *DepGetVal(DepTy &DT) { return DT.getPointer(); }
438  return cast<AbstractAttribute>(DT.getPointer());
439  }
440 
441  operator AbstractAttribute *() { return cast<AbstractAttribute>(this); }
442 
443 public:
444  using iterator =
446  using aaiterator =
448 
449  aaiterator begin() { return aaiterator(Deps.begin(), &DepGetValAA); }
450  aaiterator end() { return aaiterator(Deps.end(), &DepGetValAA); }
451  iterator child_begin() { return iterator(Deps.begin(), &DepGetVal); }
452  iterator child_end() { return iterator(Deps.end(), &DepGetVal); }
453 
454  virtual void print(raw_ostream &OS) const { OS << "AADepNode Impl\n"; }
456 
457  friend struct Attributor;
458  friend struct AADepGraph;
459 };
460 
461 /// The data structure for the dependency graph
462 ///
463 /// Note that in this graph if there is an edge from A to B (A -> B),
464 /// then it means that B depends on A, and when the state of A is
465 /// updated, node B should also be updated
466 struct AADepGraph {
467  AADepGraph() = default;
468  ~AADepGraph() = default;
469 
471  static AADepGraphNode *DepGetVal(DepTy &DT) { return DT.getPointer(); }
472  using iterator =
474 
475  /// There is no root node for the dependency graph. But the SCCIterator
476  /// requires a single entry point, so we maintain a fake("synthetic") root
477  /// node that depends on every node.
480 
483 
484  void viewGraph();
485 
486  /// Dump graph to file
487  void dumpGraph();
488 
489  /// Print dependency graph
490  void print();
491 };
492 
493 /// Helper to describe and deal with positions in the LLVM-IR.
494 ///
495 /// A position in the IR is described by an anchor value and an "offset" that
496 /// could be the argument number, for call sites and arguments, or an indicator
497 /// of the "position kind". The kinds, specified in the Kind enum below, include
498 /// the locations in the attribute list, i.a., function scope and return value,
499 /// as well as a distinction between call sites and functions. Finally, there
500 /// are floating values that do not have a corresponding attribute list
501 /// position.
502 struct IRPosition {
503  // NOTE: In the future this definition can be changed to support recursive
504  // functions.
506 
507  /// The positions we distinguish in the IR.
508  enum Kind : char {
509  IRP_INVALID, ///< An invalid position.
510  IRP_FLOAT, ///< A position that is not associated with a spot suitable
511  ///< for attributes. This could be any value or instruction.
512  IRP_RETURNED, ///< An attribute for the function return value.
513  IRP_CALL_SITE_RETURNED, ///< An attribute for a call site return value.
514  IRP_FUNCTION, ///< An attribute for a function (scope).
515  IRP_CALL_SITE, ///< An attribute for a call site (function scope).
516  IRP_ARGUMENT, ///< An attribute for a function argument.
517  IRP_CALL_SITE_ARGUMENT, ///< An attribute for a call site argument.
518  };
519 
520  /// Default constructor available to create invalid positions implicitly. All
521  /// other positions need to be created explicitly through the appropriate
522  /// static member function.
523  IRPosition() : Enc(nullptr, ENC_VALUE) { verify(); }
524 
525  /// Create a position describing the value of \p V.
526  static const IRPosition value(const Value &V,
527  const CallBaseContext *CBContext = nullptr) {
528  if (auto *Arg = dyn_cast<Argument>(&V))
529  return IRPosition::argument(*Arg, CBContext);
530  if (auto *CB = dyn_cast<CallBase>(&V))
531  return IRPosition::callsite_returned(*CB);
532  return IRPosition(const_cast<Value &>(V), IRP_FLOAT, CBContext);
533  }
534 
535  /// Create a position describing the instruction \p I. This is different from
536  /// the value version because call sites are treated as intrusctions rather
537  /// than their return value in this function.
538  static const IRPosition inst(const Instruction &I,
539  const CallBaseContext *CBContext = nullptr) {
540  return IRPosition(const_cast<Instruction &>(I), IRP_FLOAT, CBContext);
541  }
542 
543  /// Create a position describing the function scope of \p F.
544  /// \p CBContext is used for call base specific analysis.
545  static const IRPosition function(const Function &F,
546  const CallBaseContext *CBContext = nullptr) {
547  return IRPosition(const_cast<Function &>(F), IRP_FUNCTION, CBContext);
548  }
549 
550  /// Create a position describing the returned value of \p F.
551  /// \p CBContext is used for call base specific analysis.
552  static const IRPosition returned(const Function &F,
553  const CallBaseContext *CBContext = nullptr) {
554  return IRPosition(const_cast<Function &>(F), IRP_RETURNED, CBContext);
555  }
556 
557  /// Create a position describing the argument \p Arg.
558  /// \p CBContext is used for call base specific analysis.
559  static const IRPosition argument(const Argument &Arg,
560  const CallBaseContext *CBContext = nullptr) {
561  return IRPosition(const_cast<Argument &>(Arg), IRP_ARGUMENT, CBContext);
562  }
563 
564  /// Create a position describing the function scope of \p CB.
565  static const IRPosition callsite_function(const CallBase &CB) {
566  return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE);
567  }
568 
569  /// Create a position describing the returned value of \p CB.
570  static const IRPosition callsite_returned(const CallBase &CB) {
571  return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE_RETURNED);
572  }
573 
574  /// Create a position describing the argument of \p CB at position \p ArgNo.
575  static const IRPosition callsite_argument(const CallBase &CB,
576  unsigned ArgNo) {
577  return IRPosition(const_cast<Use &>(CB.getArgOperandUse(ArgNo)),
579  }
580 
581  /// Create a position describing the argument of \p ACS at position \p ArgNo.
583  unsigned ArgNo) {
584  if (ACS.getNumArgOperands() <= ArgNo)
585  return IRPosition();
586  int CSArgNo = ACS.getCallArgOperandNo(ArgNo);
587  if (CSArgNo >= 0)
589  cast<CallBase>(*ACS.getInstruction()), CSArgNo);
590  return IRPosition();
591  }
592 
593  /// Create a position with function scope matching the "context" of \p IRP.
594  /// If \p IRP is a call site (see isAnyCallSitePosition()) then the result
595  /// will be a call site position, otherwise the function position of the
596  /// associated function.
597  static const IRPosition
599  const CallBaseContext *CBContext = nullptr) {
600  if (IRP.isAnyCallSitePosition()) {
602  cast<CallBase>(IRP.getAnchorValue()));
603  }
605  return IRPosition::function(*IRP.getAssociatedFunction(), CBContext);
606  }
607 
608  bool operator==(const IRPosition &RHS) const {
609  return Enc == RHS.Enc && RHS.CBContext == CBContext;
610  }
611  bool operator!=(const IRPosition &RHS) const { return !(*this == RHS); }
612 
613  /// Return the value this abstract attribute is anchored with.
614  ///
615  /// The anchor value might not be the associated value if the latter is not
616  /// sufficient to determine where arguments will be manifested. This is, so
617  /// far, only the case for call site arguments as the value is not sufficient
618  /// to pinpoint them. Instead, we can use the call site as an anchor.
620  switch (getEncodingBits()) {
621  case ENC_VALUE:
622  case ENC_RETURNED_VALUE:
623  case ENC_FLOATING_FUNCTION:
624  return *getAsValuePtr();
625  case ENC_CALL_SITE_ARGUMENT_USE:
626  return *(getAsUsePtr()->getUser());
627  default:
628  llvm_unreachable("Unkown encoding!");
629  };
630  }
631 
632  /// Return the associated function, if any.
634  if (auto *CB = dyn_cast<CallBase>(&getAnchorValue())) {
635  // We reuse the logic that associates callback calles to arguments of a
636  // call site here to identify the callback callee as the associated
637  // function.
639  return Arg->getParent();
640  return CB->getCalledFunction();
641  }
642  return getAnchorScope();
643  }
644 
645  /// Return the associated argument, if any.
647 
648  /// Return true if the position refers to a function interface, that is the
649  /// function scope, the function return, or an argument.
650  bool isFnInterfaceKind() const {
651  switch (getPositionKind()) {
655  return true;
656  default:
657  return false;
658  }
659  }
660 
661  /// Return the Function surrounding the anchor value.
663  Value &V = getAnchorValue();
664  if (isa<Function>(V))
665  return &cast<Function>(V);
666  if (isa<Argument>(V))
667  return cast<Argument>(V).getParent();
668  if (isa<Instruction>(V))
669  return cast<Instruction>(V).getFunction();
670  return nullptr;
671  }
672 
673  /// Return the context instruction, if any.
674  Instruction *getCtxI() const {
675  Value &V = getAnchorValue();
676  if (auto *I = dyn_cast<Instruction>(&V))
677  return I;
678  if (auto *Arg = dyn_cast<Argument>(&V))
679  if (!Arg->getParent()->isDeclaration())
680  return &Arg->getParent()->getEntryBlock().front();
681  if (auto *F = dyn_cast<Function>(&V))
682  if (!F->isDeclaration())
683  return &(F->getEntryBlock().front());
684  return nullptr;
685  }
686 
687  /// Return the value this abstract attribute is associated with.
689  if (getCallSiteArgNo() < 0 || isa<Argument>(&getAnchorValue()))
690  return getAnchorValue();
691  assert(isa<CallBase>(&getAnchorValue()) && "Expected a call base!");
692  return *cast<CallBase>(&getAnchorValue())
693  ->getArgOperand(getCallSiteArgNo());
694  }
695 
696  /// Return the type this abstract attribute is associated with.
700  return getAssociatedValue().getType();
701  }
702 
703  /// Return the callee argument number of the associated value if it is an
704  /// argument or call site argument, otherwise a negative value. In contrast to
705  /// `getCallSiteArgNo` this method will always return the "argument number"
706  /// from the perspective of the callee. This may not the same as the call site
707  /// if this is a callback call.
708  int getCalleeArgNo() const {
709  return getArgNo(/* CallbackCalleeArgIfApplicable */ true);
710  }
711 
712  /// Return the call site argument number of the associated value if it is an
713  /// argument or call site argument, otherwise a negative value. In contrast to
714  /// `getCalleArgNo` this method will always return the "operand number" from
715  /// the perspective of the call site. This may not the same as the callee
716  /// perspective if this is a callback call.
717  int getCallSiteArgNo() const {
718  return getArgNo(/* CallbackCalleeArgIfApplicable */ false);
719  }
720 
721  /// Return the index in the attribute list for this position.
722  unsigned getAttrIdx() const {
723  switch (getPositionKind()) {
726  break;
736  }
738  "There is no attribute index for a floating or invalid position!");
739  }
740 
741  /// Return the associated position kind.
743  char EncodingBits = getEncodingBits();
744  if (EncodingBits == ENC_CALL_SITE_ARGUMENT_USE)
745  return IRP_CALL_SITE_ARGUMENT;
746  if (EncodingBits == ENC_FLOATING_FUNCTION)
747  return IRP_FLOAT;
748 
749  Value *V = getAsValuePtr();
750  if (!V)
751  return IRP_INVALID;
752  if (isa<Argument>(V))
753  return IRP_ARGUMENT;
754  if (isa<Function>(V))
755  return isReturnPosition(EncodingBits) ? IRP_RETURNED : IRP_FUNCTION;
756  if (isa<CallBase>(V))
757  return isReturnPosition(EncodingBits) ? IRP_CALL_SITE_RETURNED
758  : IRP_CALL_SITE;
759  return IRP_FLOAT;
760  }
761 
762  /// TODO: Figure out if the attribute related helper functions should live
763  /// here or somewhere else.
764 
765  /// Return true if any kind in \p AKs existing in the IR at a position that
766  /// will affect this one. See also getAttrs(...).
767  /// \param IgnoreSubsumingPositions Flag to determine if subsuming positions,
768  /// e.g., the function position if this is an
769  /// argument position, should be ignored.
771  bool IgnoreSubsumingPositions = false,
772  Attributor *A = nullptr) const;
773 
774  /// Return the attributes of any kind in \p AKs existing in the IR at a
775  /// position that will affect this one. While each position can only have a
776  /// single attribute of any kind in \p AKs, there are "subsuming" positions
777  /// that could have an attribute as well. This method returns all attributes
778  /// found in \p Attrs.
779  /// \param IgnoreSubsumingPositions Flag to determine if subsuming positions,
780  /// e.g., the function position if this is an
781  /// argument position, should be ignored.
784  bool IgnoreSubsumingPositions = false,
785  Attributor *A = nullptr) const;
786 
787  /// Remove the attribute of kind \p AKs existing in the IR at this position.
790  return;
791 
792  AttributeList AttrList;
793  auto *CB = dyn_cast<CallBase>(&getAnchorValue());
794  if (CB)
795  AttrList = CB->getAttributes();
796  else
797  AttrList = getAssociatedFunction()->getAttributes();
798 
800  for (Attribute::AttrKind AK : AKs)
801  AttrList = AttrList.removeAttributeAtIndex(Ctx, getAttrIdx(), AK);
802 
803  if (CB)
804  CB->setAttributes(AttrList);
805  else
807  }
808 
809  bool isAnyCallSitePosition() const {
810  switch (getPositionKind()) {
814  return true;
815  default:
816  return false;
817  }
818  }
819 
820  /// Return true if the position is an argument or call site argument.
821  bool isArgumentPosition() const {
822  switch (getPositionKind()) {
825  return true;
826  default:
827  return false;
828  }
829  }
830 
831  /// Return the same position without the call base context.
833  IRPosition Result = *this;
834  Result.CBContext = nullptr;
835  return Result;
836  }
837 
838  /// Get the call base context from the position.
839  const CallBaseContext *getCallBaseContext() const { return CBContext; }
840 
841  /// Check if the position has any call base context.
842  bool hasCallBaseContext() const { return CBContext != nullptr; }
843 
844  /// Special DenseMap key values.
845  ///
846  ///{
847  static const IRPosition EmptyKey;
848  static const IRPosition TombstoneKey;
849  ///}
850 
851  /// Conversion into a void * to allow reuse of pointer hashing.
852  operator void *() const { return Enc.getOpaqueValue(); }
853 
854 private:
855  /// Private constructor for special values only!
856  explicit IRPosition(void *Ptr, const CallBaseContext *CBContext = nullptr)
857  : CBContext(CBContext) {
858  Enc.setFromOpaqueValue(Ptr);
859  }
860 
861  /// IRPosition anchored at \p AnchorVal with kind/argument numbet \p PK.
862  explicit IRPosition(Value &AnchorVal, Kind PK,
863  const CallBaseContext *CBContext = nullptr)
864  : CBContext(CBContext) {
865  switch (PK) {
867  llvm_unreachable("Cannot create invalid IRP with an anchor value!");
868  break;
870  // Special case for floating functions.
871  if (isa<Function>(AnchorVal) || isa<CallBase>(AnchorVal))
872  Enc = {&AnchorVal, ENC_FLOATING_FUNCTION};
873  else
874  Enc = {&AnchorVal, ENC_VALUE};
875  break;
878  Enc = {&AnchorVal, ENC_VALUE};
879  break;
882  Enc = {&AnchorVal, ENC_RETURNED_VALUE};
883  break;
885  Enc = {&AnchorVal, ENC_VALUE};
886  break;
889  "Cannot create call site argument IRP with an anchor value!");
890  break;
891  }
892  verify();
893  }
894 
895  /// Return the callee argument number of the associated value if it is an
896  /// argument or call site argument. See also `getCalleeArgNo` and
897  /// `getCallSiteArgNo`.
898  int getArgNo(bool CallbackCalleeArgIfApplicable) const {
899  if (CallbackCalleeArgIfApplicable)
900  if (Argument *Arg = getAssociatedArgument())
901  return Arg->getArgNo();
902  switch (getPositionKind()) {
904  return cast<Argument>(getAsValuePtr())->getArgNo();
906  Use &U = *getAsUsePtr();
907  return cast<CallBase>(U.getUser())->getArgOperandNo(&U);
908  }
909  default:
910  return -1;
911  }
912  }
913 
914  /// IRPosition for the use \p U. The position kind \p PK needs to be
915  /// IRP_CALL_SITE_ARGUMENT, the anchor value is the user, the associated value
916  /// the used value.
917  explicit IRPosition(Use &U, Kind PK) {
919  "Use constructor is for call site arguments only!");
920  Enc = {&U, ENC_CALL_SITE_ARGUMENT_USE};
921  verify();
922  }
923 
924  /// Verify internal invariants.
925  void verify();
926 
927  /// Return the attributes of kind \p AK existing in the IR as attribute.
928  bool getAttrsFromIRAttr(Attribute::AttrKind AK,
929  SmallVectorImpl<Attribute> &Attrs) const;
930 
931  /// Return the attributes of kind \p AK existing in the IR as operand bundles
932  /// of an llvm.assume.
933  bool getAttrsFromAssumes(Attribute::AttrKind AK,
934  SmallVectorImpl<Attribute> &Attrs,
935  Attributor &A) const;
936 
937  /// Return the underlying pointer as Value *, valid for all positions but
938  /// IRP_CALL_SITE_ARGUMENT.
939  Value *getAsValuePtr() const {
940  assert(getEncodingBits() != ENC_CALL_SITE_ARGUMENT_USE &&
941  "Not a value pointer!");
942  return reinterpret_cast<Value *>(Enc.getPointer());
943  }
944 
945  /// Return the underlying pointer as Use *, valid only for
946  /// IRP_CALL_SITE_ARGUMENT positions.
947  Use *getAsUsePtr() const {
948  assert(getEncodingBits() == ENC_CALL_SITE_ARGUMENT_USE &&
949  "Not a value pointer!");
950  return reinterpret_cast<Use *>(Enc.getPointer());
951  }
952 
953  /// Return true if \p EncodingBits describe a returned or call site returned
954  /// position.
955  static bool isReturnPosition(char EncodingBits) {
956  return EncodingBits == ENC_RETURNED_VALUE;
957  }
958 
959  /// Return true if the encoding bits describe a returned or call site returned
960  /// position.
961  bool isReturnPosition() const { return isReturnPosition(getEncodingBits()); }
962 
963  /// The encoding of the IRPosition is a combination of a pointer and two
964  /// encoding bits. The values of the encoding bits are defined in the enum
965  /// below. The pointer is either a Value* (for the first three encoding bit
966  /// combinations) or Use* (for ENC_CALL_SITE_ARGUMENT_USE).
967  ///
968  ///{
969  enum {
970  ENC_VALUE = 0b00,
971  ENC_RETURNED_VALUE = 0b01,
972  ENC_FLOATING_FUNCTION = 0b10,
973  ENC_CALL_SITE_ARGUMENT_USE = 0b11,
974  };
975 
976  // Reserve the maximal amount of bits so there is no need to mask out the
977  // remaining ones. We will not encode anything else in the pointer anyway.
978  static constexpr int NumEncodingBits =
980  static_assert(NumEncodingBits >= 2, "At least two bits are required!");
981 
982  /// The pointer with the encoding bits.
983  PointerIntPair<void *, NumEncodingBits, char> Enc;
984  ///}
985 
986  /// Call base context. Used for callsite specific analysis.
987  const CallBaseContext *CBContext = nullptr;
988 
989  /// Return the encoding bits.
990  char getEncodingBits() const { return Enc.getInt(); }
991 };
992 
993 /// Helper that allows IRPosition as a key in a DenseMap.
994 template <> struct DenseMapInfo<IRPosition> {
995  static inline IRPosition getEmptyKey() { return IRPosition::EmptyKey; }
996  static inline IRPosition getTombstoneKey() {
998  }
999  static unsigned getHashValue(const IRPosition &IRP) {
1000  return (DenseMapInfo<void *>::getHashValue(IRP) << 4) ^
1002  }
1003 
1004  static bool isEqual(const IRPosition &a, const IRPosition &b) {
1005  return a == b;
1006  }
1007 };
1008 
1009 /// A visitor class for IR positions.
1010 ///
1011 /// Given a position P, the SubsumingPositionIterator allows to visit "subsuming
1012 /// positions" wrt. attributes/information. Thus, if a piece of information
1013 /// holds for a subsuming position, it also holds for the position P.
1014 ///
1015 /// The subsuming positions always include the initial position and then,
1016 /// depending on the position kind, additionally the following ones:
1017 /// - for IRP_RETURNED:
1018 /// - the function (IRP_FUNCTION)
1019 /// - for IRP_ARGUMENT:
1020 /// - the function (IRP_FUNCTION)
1021 /// - for IRP_CALL_SITE:
1022 /// - the callee (IRP_FUNCTION), if known
1023 /// - for IRP_CALL_SITE_RETURNED:
1024 /// - the callee (IRP_RETURNED), if known
1025 /// - the call site (IRP_FUNCTION)
1026 /// - the callee (IRP_FUNCTION), if known
1027 /// - for IRP_CALL_SITE_ARGUMENT:
1028 /// - the argument of the callee (IRP_ARGUMENT), if known
1029 /// - the callee (IRP_FUNCTION), if known
1030 /// - the position the call site argument is associated with if it is not
1031 /// anchored to the call site, e.g., if it is an argument then the argument
1032 /// (IRP_ARGUMENT)
1034  SmallVector<IRPosition, 4> IRPositions;
1035  using iterator = decltype(IRPositions)::iterator;
1036 
1037 public:
1039  iterator begin() { return IRPositions.begin(); }
1040  iterator end() { return IRPositions.end(); }
1041 };
1042 
1043 /// Wrapper for FunctoinAnalysisManager.
1045  template <typename Analysis>
1046  typename Analysis::Result *getAnalysis(const Function &F) {
1047  if (!FAM || !F.getParent())
1048  return nullptr;
1049  return &FAM->getResult<Analysis>(const_cast<Function &>(F));
1050  }
1051 
1053  AnalysisGetter() = default;
1054 
1055 private:
1056  FunctionAnalysisManager *FAM = nullptr;
1057 };
1058 
1059 /// Data structure to hold cached (LLVM-IR) information.
1060 ///
1061 /// All attributes are given an InformationCache object at creation time to
1062 /// avoid inspection of the IR by all of them individually. This default
1063 /// InformationCache will hold information required by 'default' attributes,
1064 /// thus the ones deduced when Attributor::identifyDefaultAbstractAttributes(..)
1065 /// is called.
1066 ///
1067 /// If custom abstract attributes, registered manually through
1068 /// Attributor::registerAA(...), need more information, especially if it is not
1069 /// reusable, it is advised to inherit from the InformationCache and cast the
1070 /// instance down in the abstract attributes.
1074  : DL(M.getDataLayout()), Allocator(Allocator),
1075  Explorer(
1076  /* ExploreInterBlock */ true, /* ExploreCFGForward */ true,
1077  /* ExploreCFGBackward */ true,
1078  /* LIGetter */
1079  [&](const Function &F) { return AG.getAnalysis<LoopAnalysis>(F); },
1080  /* DTGetter */
1081  [&](const Function &F) {
1082  return AG.getAnalysis<DominatorTreeAnalysis>(F);
1083  },
1084  /* PDTGetter */
1085  [&](const Function &F) {
1086  return AG.getAnalysis<PostDominatorTreeAnalysis>(F);
1087  }),
1088  AG(AG), TargetTriple(M.getTargetTriple()) {
1089  if (CGSCC)
1091  }
1092 
1094  // The FunctionInfo objects are allocated via a BumpPtrAllocator, we call
1095  // the destructor manually.
1096  for (auto &It : FuncInfoMap)
1097  It.getSecond()->~FunctionInfo();
1098  }
1099 
1100  /// Apply \p CB to all uses of \p F. If \p LookThroughConstantExprUses is
1101  /// true, constant expression users are not given to \p CB but their uses are
1102  /// traversed transitively.
1103  template <typename CBTy>
1104  static void foreachUse(Function &F, CBTy CB,
1105  bool LookThroughConstantExprUses = true) {
1106  SmallVector<Use *, 8> Worklist(make_pointer_range(F.uses()));
1107 
1108  for (unsigned Idx = 0; Idx < Worklist.size(); ++Idx) {
1109  Use &U = *Worklist[Idx];
1110 
1111  // Allow use in constant bitcasts and simply look through them.
1112  if (LookThroughConstantExprUses && isa<ConstantExpr>(U.getUser())) {
1113  for (Use &CEU : cast<ConstantExpr>(U.getUser())->uses())
1114  Worklist.push_back(&CEU);
1115  continue;
1116  }
1117 
1118  CB(U);
1119  }
1120  }
1121 
1122  /// Initialize the ModuleSlice member based on \p SCC. ModuleSlices contains
1123  /// (a subset of) all functions that we can look at during this SCC traversal.
1124  /// This includes functions (transitively) called from the SCC and the
1125  /// (transitive) callers of SCC functions. We also can look at a function if
1126  /// there is a "reference edge", i.a., if the function somehow uses (!=calls)
1127  /// a function in the SCC or a caller of a function in the SCC.
1129  ModuleSlice.insert(SCC.begin(), SCC.end());
1130 
1132  SmallVector<Function *, 16> Worklist(SCC.begin(), SCC.end());
1133  while (!Worklist.empty()) {
1134  Function *F = Worklist.pop_back_val();
1135  ModuleSlice.insert(F);
1136 
1137  for (Instruction &I : instructions(*F))
1138  if (auto *CB = dyn_cast<CallBase>(&I))
1139  if (Function *Callee = CB->getCalledFunction())
1140  if (Seen.insert(Callee).second)
1141  Worklist.push_back(Callee);
1142  }
1143 
1144  Seen.clear();
1145  Worklist.append(SCC.begin(), SCC.end());
1146  while (!Worklist.empty()) {
1147  Function *F = Worklist.pop_back_val();
1148  ModuleSlice.insert(F);
1149 
1150  // Traverse all transitive uses.
1151  foreachUse(*F, [&](Use &U) {
1152  if (auto *UsrI = dyn_cast<Instruction>(U.getUser()))
1153  if (Seen.insert(UsrI->getFunction()).second)
1154  Worklist.push_back(UsrI->getFunction());
1155  });
1156  }
1157  }
1158 
1159  /// The slice of the module we are allowed to look at.
1161 
1162  /// A vector type to hold instructions.
1164 
1165  /// A map type from opcodes to instructions with this opcode.
1167 
1168  /// Return the map that relates "interesting" opcodes with all instructions
1169  /// with that opcode in \p F.
1171  return getFunctionInfo(F).OpcodeInstMap;
1172  }
1173 
1174  /// Return the instructions in \p F that may read or write memory.
1176  return getFunctionInfo(F).RWInsts;
1177  }
1178 
1179  /// Return MustBeExecutedContextExplorer
1181  return Explorer;
1182  }
1183 
1184  /// Return TargetLibraryInfo for function \p F.
1186  return AG.getAnalysis<TargetLibraryAnalysis>(F);
1187  }
1188 
1189  /// Return AliasAnalysis Result for function \p F.
1191 
1192  /// Return true if \p Arg is involved in a must-tail call, thus the argument
1193  /// of the caller or callee.
1195  FunctionInfo &FI = getFunctionInfo(*Arg.getParent());
1196  return FI.CalledViaMustTail || FI.ContainsMustTailCall;
1197  }
1198 
1199  bool isOnlyUsedByAssume(const Instruction &I) const {
1200  return AssumeOnlyValues.contains(&I);
1201  }
1202 
1203  /// Return the analysis result from a pass \p AP for function \p F.
1204  template <typename AP>
1205  typename AP::Result *getAnalysisResultForFunction(const Function &F) {
1206  return AG.getAnalysis<AP>(F);
1207  }
1208 
1209  /// Return datalayout used in the module.
1210  const DataLayout &getDL() { return DL; }
1211 
1212  /// Return the map conaining all the knowledge we have from `llvm.assume`s.
1213  const RetainedKnowledgeMap &getKnowledgeMap() const { return KnowledgeMap; }
1214 
1215  /// Return if \p To is potentially reachable form \p From or not
1216  /// If the same query was answered, return cached result
1218  auto KeyPair = std::make_pair(&From, &To);
1219  auto Iter = PotentiallyReachableMap.find(KeyPair);
1220  if (Iter != PotentiallyReachableMap.end())
1221  return Iter->second;
1222  const Function &F = *From.getFunction();
1223  bool Result = true;
1224  if (From.getFunction() == To.getFunction())
1225  Result = isPotentiallyReachable(&From, &To, nullptr,
1227  AG.getAnalysis<LoopAnalysis>(F));
1228  PotentiallyReachableMap.insert(std::make_pair(KeyPair, Result));
1229  return Result;
1230  }
1231 
1232  /// Check whether \p F is part of module slice.
1233  bool isInModuleSlice(const Function &F) {
1234  return ModuleSlice.empty() || ModuleSlice.count(const_cast<Function *>(&F));
1235  }
1236 
1237  /// Return true if the stack (llvm::Alloca) can be accessed by other threads.
1239 
1240  /// Return true if the target is a GPU.
1241  bool targetIsGPU() {
1242  return TargetTriple.isAMDGPU() || TargetTriple.isNVPTX();
1243  }
1244 
1245 private:
1246  struct FunctionInfo {
1247  ~FunctionInfo();
1248 
1249  /// A nested map that remembers all instructions in a function with a
1250  /// certain instruction opcode (Instruction::getOpcode()).
1251  OpcodeInstMapTy OpcodeInstMap;
1252 
1253  /// A map from functions to their instructions that may read or write
1254  /// memory.
1255  InstructionVectorTy RWInsts;
1256 
1257  /// Function is called by a `musttail` call.
1258  bool CalledViaMustTail;
1259 
1260  /// Function contains a `musttail` call.
1261  bool ContainsMustTailCall;
1262  };
1263 
1264  /// A map type from functions to informatio about it.
1265  DenseMap<const Function *, FunctionInfo *> FuncInfoMap;
1266 
1267  /// Return information about the function \p F, potentially by creating it.
1268  FunctionInfo &getFunctionInfo(const Function &F) {
1269  FunctionInfo *&FI = FuncInfoMap[&F];
1270  if (!FI) {
1271  FI = new (Allocator) FunctionInfo();
1272  initializeInformationCache(F, *FI);
1273  }
1274  return *FI;
1275  }
1276 
1277  /// Initialize the function information cache \p FI for the function \p F.
1278  ///
1279  /// This method needs to be called for all function that might be looked at
1280  /// through the information cache interface *prior* to looking at them.
1281  void initializeInformationCache(const Function &F, FunctionInfo &FI);
1282 
1283  /// The datalayout used in the module.
1284  const DataLayout &DL;
1285 
1286  /// The allocator used to allocate memory, e.g. for `FunctionInfo`s.
1287  BumpPtrAllocator &Allocator;
1288 
1289  /// MustBeExecutedContextExplorer
1290  MustBeExecutedContextExplorer Explorer;
1291 
1292  /// A map with knowledge retained in `llvm.assume` instructions.
1293  RetainedKnowledgeMap KnowledgeMap;
1294 
1295  /// A container for all instructions that are only used by `llvm.assume`.
1296  SetVector<const Instruction *> AssumeOnlyValues;
1297 
1298  /// Getters for analysis.
1299  AnalysisGetter &AG;
1300 
1301  /// Set of inlineable functions
1302  SmallPtrSet<const Function *, 8> InlineableFunctions;
1303 
1304  /// A map for caching results of queries for isPotentiallyReachable
1305  DenseMap<std::pair<const Instruction *, const Instruction *>, bool>
1306  PotentiallyReachableMap;
1307 
1308  /// The triple describing the target machine.
1309  Triple TargetTriple;
1310 
1311  /// Give the Attributor access to the members so
1312  /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them.
1313  friend struct Attributor;
1314 };
1315 
1316 /// Configuration for the Attributor.
1318 
1320 
1321  /// Is the user of the Attributor a module pass or not. This determines what
1322  /// IR we can look at and modify. If it is a module pass we might deduce facts
1323  /// outside the initial function set and modify functions outside that set,
1324  /// but only as part of the optimization of the functions in the initial
1325  /// function set. For CGSCC passes we can look at the IR of the module slice
1326  /// but never run any deduction, or perform any modification, outside the
1327  /// initial function set (which we assume is the SCC).
1328  bool IsModulePass = true;
1329 
1330  /// Flag to determine if we can delete functions or keep dead ones around.
1331  bool DeleteFns = true;
1332 
1333  /// Flag to determine if we rewrite function signatures.
1334  bool RewriteSignatures = true;
1335 
1336  /// Flag to determine if we want to initialize all default AAs for an internal
1337  /// function marked live.
1338  /// TODO: This should probably be a callback, or maybe
1339  /// identifyDefaultAbstractAttributes should be virtual, something to allow
1340  /// customizable lazy initialization for internal functions.
1342 
1343  /// Helper to update an underlying call graph and to delete functions.
1345 
1346  /// If not null, a set limiting the attribute opportunities.
1348 
1349  /// Maximum number of iterations to run until fixpoint.
1351 
1352  /// A callback function that returns an ORE object from a Function pointer.
1353  ///{
1354  using OptimizationRemarkGetter =
1357  ///}
1358 
1359  /// The name of the pass running the attributor, used to emit remarks.
1360  const char *PassName = nullptr;
1361 };
1362 
1363 /// The fixpoint analysis framework that orchestrates the attribute deduction.
1364 ///
1365 /// The Attributor provides a general abstract analysis framework (guided
1366 /// fixpoint iteration) as well as helper functions for the deduction of
1367 /// (LLVM-IR) attributes. However, also other code properties can be deduced,
1368 /// propagated, and ultimately manifested through the Attributor framework. This
1369 /// is particularly useful if these properties interact with attributes and a
1370 /// co-scheduled deduction allows to improve the solution. Even if not, thus if
1371 /// attributes/properties are completely isolated, they should use the
1372 /// Attributor framework to reduce the number of fixpoint iteration frameworks
1373 /// in the code base. Note that the Attributor design makes sure that isolated
1374 /// attributes are not impacted, in any way, by others derived at the same time
1375 /// if there is no cross-reasoning performed.
1376 ///
1377 /// The public facing interface of the Attributor is kept simple and basically
1378 /// allows abstract attributes to one thing, query abstract attributes
1379 /// in-flight. There are two reasons to do this:
1380 /// a) The optimistic state of one abstract attribute can justify an
1381 /// optimistic state of another, allowing to framework to end up with an
1382 /// optimistic (=best possible) fixpoint instead of one based solely on
1383 /// information in the IR.
1384 /// b) This avoids reimplementing various kinds of lookups, e.g., to check
1385 /// for existing IR attributes, in favor of a single lookups interface
1386 /// provided by an abstract attribute subclass.
1387 ///
1388 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
1389 /// described in the file comment.
1390 struct Attributor {
1391 
1392  /// Constructor
1393  ///
1394  /// \param Functions The set of functions we are deriving attributes for.
1395  /// \param InfoCache Cache to hold various information accessible for
1396  /// the abstract attributes.
1397  /// \param Configuration The Attributor configuration which determines what
1398  /// generic features to use.
1400  AttributorConfig Configuration)
1401  : Allocator(InfoCache.Allocator), Functions(Functions),
1402  InfoCache(InfoCache), Configuration(Configuration) {}
1403 
1404  ~Attributor();
1405 
1406  /// Run the analyses until a fixpoint is reached or enforced (timeout).
1407  ///
1408  /// The attributes registered with this Attributor can be used after as long
1409  /// as the Attributor is not destroyed (it owns the attributes now).
1410  ///
1411  /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED.
1412  ChangeStatus run();
1413 
1414  /// Lookup an abstract attribute of type \p AAType at position \p IRP. While
1415  /// no abstract attribute is found equivalent positions are checked, see
1416  /// SubsumingPositionIterator. Thus, the returned abstract attribute
1417  /// might be anchored at a different position, e.g., the callee if \p IRP is a
1418  /// call base.
1419  ///
1420  /// This method is the only (supported) way an abstract attribute can retrieve
1421  /// information from another abstract attribute. As an example, take an
1422  /// abstract attribute that determines the memory access behavior for a
1423  /// argument (readnone, readonly, ...). It should use `getAAFor` to get the
1424  /// most optimistic information for other abstract attributes in-flight, e.g.
1425  /// the one reasoning about the "captured" state for the argument or the one
1426  /// reasoning on the memory access behavior of the function as a whole.
1427  ///
1428  /// If the DepClass enum is set to `DepClassTy::None` the dependence from
1429  /// \p QueryingAA to the return abstract attribute is not automatically
1430  /// recorded. This should only be used if the caller will record the
1431  /// dependence explicitly if necessary, thus if it the returned abstract
1432  /// attribute is used for reasoning. To record the dependences explicitly use
1433  /// the `Attributor::recordDependence` method.
1434  template <typename AAType>
1435  const AAType &getAAFor(const AbstractAttribute &QueryingAA,
1436  const IRPosition &IRP, DepClassTy DepClass) {
1437  return getOrCreateAAFor<AAType>(IRP, &QueryingAA, DepClass,
1438  /* ForceUpdate */ false);
1439  }
1440 
1441  /// Similar to getAAFor but the return abstract attribute will be updated (via
1442  /// `AbstractAttribute::update`) even if it is found in the cache. This is
1443  /// especially useful for AAIsDead as changes in liveness can make updates
1444  /// possible/useful that were not happening before as the abstract attribute
1445  /// was assumed dead.
1446  template <typename AAType>
1447  const AAType &getAndUpdateAAFor(const AbstractAttribute &QueryingAA,
1448  const IRPosition &IRP, DepClassTy DepClass) {
1449  return getOrCreateAAFor<AAType>(IRP, &QueryingAA, DepClass,
1450  /* ForceUpdate */ true);
1451  }
1452 
1453  /// The version of getAAFor that allows to omit a querying abstract
1454  /// attribute. Using this after Attributor started running is restricted to
1455  /// only the Attributor itself. Initial seeding of AAs can be done via this
1456  /// function.
1457  /// NOTE: ForceUpdate is ignored in any stage other than the update stage.
1458  template <typename AAType>
1459  const AAType &getOrCreateAAFor(IRPosition IRP,
1460  const AbstractAttribute *QueryingAA,
1461  DepClassTy DepClass, bool ForceUpdate = false,
1462  bool UpdateAfterInit = true) {
1463  if (!shouldPropagateCallBaseContext(IRP))
1464  IRP = IRP.stripCallBaseContext();
1465 
1466  if (AAType *AAPtr = lookupAAFor<AAType>(IRP, QueryingAA, DepClass,
1467  /* AllowInvalidState */ true)) {
1468  if (ForceUpdate && Phase == AttributorPhase::UPDATE)
1469  updateAA(*AAPtr);
1470  return *AAPtr;
1471  }
1472 
1473  // No matching attribute found, create one.
1474  // Use the static create method.
1475  auto &AA = AAType::createForPosition(IRP, *this);
1476 
1477  // If we are currenty seeding attributes, enforce seeding rules.
1478  if (Phase == AttributorPhase::SEEDING && !shouldSeedAttribute(AA)) {
1479  AA.getState().indicatePessimisticFixpoint();
1480  return AA;
1481  }
1482 
1483  registerAA(AA);
1484 
1485  // For now we ignore naked and optnone functions.
1486  bool Invalidate =
1487  Configuration.Allowed && !Configuration.Allowed->count(&AAType::ID);
1488  const Function *AnchorFn = IRP.getAnchorScope();
1489  if (AnchorFn) {
1490  Invalidate |=
1491  AnchorFn->hasFnAttribute(Attribute::Naked) ||
1492  AnchorFn->hasFnAttribute(Attribute::OptimizeNone) ||
1493  (!isModulePass() && !getInfoCache().isInModuleSlice(*AnchorFn));
1494  }
1495 
1496  // Avoid too many nested initializations to prevent a stack overflow.
1497  Invalidate |= InitializationChainLength > MaxInitializationChainLength;
1498 
1499  // Bootstrap the new attribute with an initial update to propagate
1500  // information, e.g., function -> call site. If it is not on a given
1501  // Allowed we will not perform updates at all.
1502  if (Invalidate) {
1503  AA.getState().indicatePessimisticFixpoint();
1504  return AA;
1505  }
1506 
1507  {
1508  TimeTraceScope TimeScope(AA.getName() + "::initialize");
1509  ++InitializationChainLength;
1510  AA.initialize(*this);
1511  --InitializationChainLength;
1512  }
1513 
1514  // We update only AAs associated with functions in the Functions set or
1515  // call sites of them.
1516  if ((AnchorFn && !isRunOn(const_cast<Function *>(AnchorFn))) &&
1517  !isRunOn(IRP.getAssociatedFunction())) {
1518  AA.getState().indicatePessimisticFixpoint();
1519  return AA;
1520  }
1521 
1522  // If this is queried in the manifest stage, we force the AA to indicate
1523  // pessimistic fixpoint immediately.
1524  if (Phase == AttributorPhase::MANIFEST) {
1525  AA.getState().indicatePessimisticFixpoint();
1526  return AA;
1527  }
1528 
1529  // Allow seeded attributes to declare dependencies.
1530  // Remember the seeding state.
1531  if (UpdateAfterInit) {
1532  AttributorPhase OldPhase = Phase;
1533  Phase = AttributorPhase::UPDATE;
1534 
1535  updateAA(AA);
1536 
1537  Phase = OldPhase;
1538  }
1539 
1540  if (QueryingAA && AA.getState().isValidState())
1541  recordDependence(AA, const_cast<AbstractAttribute &>(*QueryingAA),
1542  DepClass);
1543  return AA;
1544  }
1545  template <typename AAType>
1546  const AAType &getOrCreateAAFor(const IRPosition &IRP) {
1547  return getOrCreateAAFor<AAType>(IRP, /* QueryingAA */ nullptr,
1549  }
1550 
1551  /// Return the attribute of \p AAType for \p IRP if existing and valid. This
1552  /// also allows non-AA users lookup.
1553  template <typename AAType>
1554  AAType *lookupAAFor(const IRPosition &IRP,
1555  const AbstractAttribute *QueryingAA = nullptr,
1556  DepClassTy DepClass = DepClassTy::OPTIONAL,
1557  bool AllowInvalidState = false) {
1558  static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
1559  "Cannot query an attribute with a type not derived from "
1560  "'AbstractAttribute'!");
1561  // Lookup the abstract attribute of type AAType. If found, return it after
1562  // registering a dependence of QueryingAA on the one returned attribute.
1563  AbstractAttribute *AAPtr = AAMap.lookup({&AAType::ID, IRP});
1564  if (!AAPtr)
1565  return nullptr;
1566 
1567  AAType *AA = static_cast<AAType *>(AAPtr);
1568 
1569  // Do not register a dependence on an attribute with an invalid state.
1570  if (DepClass != DepClassTy::NONE && QueryingAA &&
1571  AA->getState().isValidState())
1572  recordDependence(*AA, const_cast<AbstractAttribute &>(*QueryingAA),
1573  DepClass);
1574 
1575  // Return nullptr if this attribute has an invalid state.
1576  if (!AllowInvalidState && !AA->getState().isValidState())
1577  return nullptr;
1578  return AA;
1579  }
1580 
1581  /// Allows a query AA to request an update if a new query was received.
1583 
1584  /// Explicitly record a dependence from \p FromAA to \p ToAA, that is if
1585  /// \p FromAA changes \p ToAA should be updated as well.
1586  ///
1587  /// This method should be used in conjunction with the `getAAFor` method and
1588  /// with the DepClass enum passed to the method set to None. This can
1589  /// be beneficial to avoid false dependences but it requires the users of
1590  /// `getAAFor` to explicitly record true dependences through this method.
1591  /// The \p DepClass flag indicates if the dependence is striclty necessary.
1592  /// That means for required dependences, if \p FromAA changes to an invalid
1593  /// state, \p ToAA can be moved to a pessimistic fixpoint because it required
1594  /// information from \p FromAA but none are available anymore.
1595  void recordDependence(const AbstractAttribute &FromAA,
1596  const AbstractAttribute &ToAA, DepClassTy DepClass);
1597 
1598  /// Introduce a new abstract attribute into the fixpoint analysis.
1599  ///
1600  /// Note that ownership of the attribute is given to the Attributor. It will
1601  /// invoke delete for the Attributor on destruction of the Attributor.
1602  ///
1603  /// Attributes are identified by their IR position (AAType::getIRPosition())
1604  /// and the address of their static member (see AAType::ID).
1605  template <typename AAType> AAType &registerAA(AAType &AA) {
1606  static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
1607  "Cannot register an attribute with a type not derived from "
1608  "'AbstractAttribute'!");
1609  // Put the attribute in the lookup map structure and the container we use to
1610  // keep track of all attributes.
1611  const IRPosition &IRP = AA.getIRPosition();
1612  AbstractAttribute *&AAPtr = AAMap[{&AAType::ID, IRP}];
1613 
1614  assert(!AAPtr && "Attribute already in map!");
1615  AAPtr = &AA;
1616 
1617  // Register AA with the synthetic root only before the manifest stage.
1618  if (Phase == AttributorPhase::SEEDING || Phase == AttributorPhase::UPDATE)
1619  DG.SyntheticRoot.Deps.push_back(
1621 
1622  return AA;
1623  }
1624 
1625  /// Return the internal information cache.
1626  InformationCache &getInfoCache() { return InfoCache; }
1627 
1628  /// Return true if this is a module pass, false otherwise.
1629  bool isModulePass() const { return Configuration.IsModulePass; }
1630 
1631  /// Return true if we derive attributes for \p Fn
1632  bool isRunOn(Function &Fn) const { return isRunOn(&Fn); }
1633  bool isRunOn(Function *Fn) const {
1634  return Functions.empty() || Functions.count(Fn);
1635  }
1636 
1637  /// Determine opportunities to derive 'default' attributes in \p F and create
1638  /// abstract attribute objects for them.
1639  ///
1640  /// \param F The function that is checked for attribute opportunities.
1641  ///
1642  /// Note that abstract attribute instances are generally created even if the
1643  /// IR already contains the information they would deduce. The most important
1644  /// reason for this is the single interface, the one of the abstract attribute
1645  /// instance, which can be queried without the need to look at the IR in
1646  /// various places.
1648 
1649  /// Determine whether the function \p F is IPO amendable
1650  ///
1651  /// If a function is exactly defined or it has alwaysinline attribute
1652  /// and is viable to be inlined, we say it is IPO amendable
1654  return F.hasExactDefinition() || InfoCache.InlineableFunctions.count(&F);
1655  }
1656 
1657  /// Mark the internal function \p F as live.
1658  ///
1659  /// This will trigger the identification and initialization of attributes for
1660  /// \p F.
1662  assert(F.hasLocalLinkage() &&
1663  "Only local linkage is assumed dead initially.");
1664 
1665  if (Configuration.DefaultInitializeLiveInternals)
1667  }
1668 
1669  /// Helper function to remove callsite.
1671  if (!CI)
1672  return;
1673 
1674  Configuration.CGUpdater.removeCallSite(*CI);
1675  }
1676 
1677  /// Record that \p U is to be replaces with \p NV after information was
1678  /// manifested. This also triggers deletion of trivially dead istructions.
1680  Value *&V = ToBeChangedUses[&U];
1681  if (V && (V->stripPointerCasts() == NV.stripPointerCasts() ||
1682  isa_and_nonnull<UndefValue>(V)))
1683  return false;
1684  assert((!V || V == &NV || isa<UndefValue>(NV)) &&
1685  "Use was registered twice for replacement with different values!");
1686  V = &NV;
1687  return true;
1688  }
1689 
1690  /// Helper function to replace all uses associated with \p IRP with \p NV.
1691  /// Return true if there is any change. The flag \p ChangeDroppable indicates
1692  /// if dropppable uses should be changed too.
1694  bool ChangeDroppable = true) {
1696  auto *CB = cast<CallBase>(IRP.getCtxI());
1697  return changeUseAfterManifest(
1698  CB->getArgOperandUse(IRP.getCallSiteArgNo()), NV);
1699  }
1700  Value &V = IRP.getAssociatedValue();
1701  auto &Entry = ToBeChangedValues[&V];
1702  Value *&CurNV = Entry.first;
1703  if (CurNV && (CurNV->stripPointerCasts() == NV.stripPointerCasts() ||
1704  isa<UndefValue>(CurNV)))
1705  return false;
1706  assert((!CurNV || CurNV == &NV || isa<UndefValue>(NV)) &&
1707  "Value replacement was registered twice with different values!");
1708  CurNV = &NV;
1709  Entry.second = ChangeDroppable;
1710  return true;
1711  }
1712 
1713  /// Record that \p I is to be replaced with `unreachable` after information
1714  /// was manifested.
1716  ToBeChangedToUnreachableInsts.insert(I);
1717  }
1718 
1719  /// Record that \p II has at least one dead successor block. This information
1720  /// is used, e.g., to replace \p II with a call, after information was
1721  /// manifested.
1723  InvokeWithDeadSuccessor.insert(&II);
1724  }
1725 
1726  /// Record that \p I is deleted after information was manifested. This also
1727  /// triggers deletion of trivially dead istructions.
1728  void deleteAfterManifest(Instruction &I) { ToBeDeletedInsts.insert(&I); }
1729 
1730  /// Record that \p BB is deleted after information was manifested. This also
1731  /// triggers deletion of trivially dead istructions.
1732  void deleteAfterManifest(BasicBlock &BB) { ToBeDeletedBlocks.insert(&BB); }
1733 
1734  // Record that \p BB is added during the manifest of an AA. Added basic blocks
1735  // are preserved in the IR.
1737  ManifestAddedBlocks.insert(&BB);
1738  }
1739 
1740  /// Record that \p F is deleted after information was manifested.
1742  if (Configuration.DeleteFns)
1743  ToBeDeletedFunctions.insert(&F);
1744  }
1745 
1746  /// If \p IRP is assumed to be a constant, return it, if it is unclear yet,
1747  /// return None, otherwise return `nullptr`.
1749  const AbstractAttribute &AA,
1750  bool &UsedAssumedInformation);
1752  const AbstractAttribute &AA,
1753  bool &UsedAssumedInformation) {
1754  return getAssumedConstant(IRPosition::value(V), AA, UsedAssumedInformation);
1755  }
1756 
1757  /// If \p V is assumed simplified, return it, if it is unclear yet,
1758  /// return None, otherwise return `nullptr`.
1760  const AbstractAttribute &AA,
1761  bool &UsedAssumedInformation,
1762  AA::ValueScope S) {
1763  return getAssumedSimplified(IRP, &AA, UsedAssumedInformation, S);
1764  }
1766  const AbstractAttribute &AA,
1767  bool &UsedAssumedInformation,
1768  AA::ValueScope S) {
1770  UsedAssumedInformation, S);
1771  }
1772 
1773  /// If \p V is assumed simplified, return it, if it is unclear yet,
1774  /// return None, otherwise return `nullptr`. Same as the public version
1775  /// except that it can be used without recording dependences on any \p AA.
1777  const AbstractAttribute *AA,
1778  bool &UsedAssumedInformation,
1779  AA::ValueScope S);
1780 
1781  /// Try to simplify \p IRP and in the scope \p S. If successful, true is
1782  /// returned and all potential values \p IRP can take are put into \p Values.
1783  /// If false is returned no other information is valid.
1784  bool getAssumedSimplifiedValues(const IRPosition &IRP,
1785  const AbstractAttribute *AA,
1787  AA::ValueScope S,
1788  bool &UsedAssumedInformation);
1789 
1790  /// Register \p CB as a simplification callback.
1791  /// `Attributor::getAssumedSimplified` will use these callbacks before
1792  /// we it will ask `AAValueSimplify`. It is important to ensure this
1793  /// is called before `identifyDefaultAbstractAttributes`, assuming the
1794  /// latter is called at all.
1795  using SimplifictionCallbackTy = std::function<Optional<Value *>(
1796  const IRPosition &, const AbstractAttribute *, bool &)>;
1798  const SimplifictionCallbackTy &CB) {
1799  SimplificationCallbacks[IRP].emplace_back(CB);
1800  }
1801 
1802  /// Return true if there is a simplification callback for \p IRP.
1804  return SimplificationCallbacks.count(IRP);
1805  }
1806 
1807 private:
1808  /// The vector with all simplification callbacks registered by outside AAs.
1810  SimplificationCallbacks;
1811 
1812 public:
1813  /// Translate \p V from the callee context into the call site context.
1816  const AbstractAttribute &AA,
1817  bool &UsedAssumedInformation);
1818 
1819  /// Return true if \p AA (or its context instruction) is assumed dead.
1820  ///
1821  /// If \p LivenessAA is not provided it is queried.
1822  bool isAssumedDead(const AbstractAttribute &AA, const AAIsDead *LivenessAA,
1823  bool &UsedAssumedInformation,
1824  bool CheckBBLivenessOnly = false,
1825  DepClassTy DepClass = DepClassTy::OPTIONAL);
1826 
1827  /// Return true if \p I is assumed dead.
1828  ///
1829  /// If \p LivenessAA is not provided it is queried.
1830  bool isAssumedDead(const Instruction &I, const AbstractAttribute *QueryingAA,
1831  const AAIsDead *LivenessAA, bool &UsedAssumedInformation,
1832  bool CheckBBLivenessOnly = false,
1833  DepClassTy DepClass = DepClassTy::OPTIONAL);
1834 
1835  /// Return true if \p U is assumed dead.
1836  ///
1837  /// If \p FnLivenessAA is not provided it is queried.
1838  bool isAssumedDead(const Use &U, const AbstractAttribute *QueryingAA,
1839  const AAIsDead *FnLivenessAA, bool &UsedAssumedInformation,
1840  bool CheckBBLivenessOnly = false,
1841  DepClassTy DepClass = DepClassTy::OPTIONAL);
1842 
1843  /// Return true if \p IRP is assumed dead.
1844  ///
1845  /// If \p FnLivenessAA is not provided it is queried.
1846  bool isAssumedDead(const IRPosition &IRP, const AbstractAttribute *QueryingAA,
1847  const AAIsDead *FnLivenessAA, bool &UsedAssumedInformation,
1848  bool CheckBBLivenessOnly = false,
1849  DepClassTy DepClass = DepClassTy::OPTIONAL);
1850 
1851  /// Return true if \p BB is assumed dead.
1852  ///
1853  /// If \p LivenessAA is not provided it is queried.
1854  bool isAssumedDead(const BasicBlock &BB, const AbstractAttribute *QueryingAA,
1855  const AAIsDead *FnLivenessAA,
1856  DepClassTy DepClass = DepClassTy::OPTIONAL);
1857 
1858  /// Check \p Pred on all (transitive) uses of \p V.
1859  ///
1860  /// This method will evaluate \p Pred on all (transitive) uses of the
1861  /// associated value and return true if \p Pred holds every time.
1862  /// If uses are skipped in favor of equivalent ones, e.g., if we look through
1863  /// memory, the \p EquivalentUseCB will be used to give the caller an idea
1864  /// what original used was replaced by a new one (or new ones). The visit is
1865  /// cut short if \p EquivalentUseCB returns false and the function will return
1866  /// false as well.
1867  bool checkForAllUses(function_ref<bool(const Use &, bool &)> Pred,
1868  const AbstractAttribute &QueryingAA, const Value &V,
1869  bool CheckBBLivenessOnly = false,
1870  DepClassTy LivenessDepClass = DepClassTy::OPTIONAL,
1871  bool IgnoreDroppableUses = true,
1872  function_ref<bool(const Use &OldU, const Use &NewU)>
1873  EquivalentUseCB = nullptr);
1874 
1875  /// Emit a remark generically.
1876  ///
1877  /// This template function can be used to generically emit a remark. The
1878  /// RemarkKind should be one of the following:
1879  /// - OptimizationRemark to indicate a successful optimization attempt
1880  /// - OptimizationRemarkMissed to report a failed optimization attempt
1881  /// - OptimizationRemarkAnalysis to provide additional information about an
1882  /// optimization attempt
1883  ///
1884  /// The remark is built using a callback function \p RemarkCB that takes a
1885  /// RemarkKind as input and returns a RemarkKind.
1886  template <typename RemarkKind, typename RemarkCallBack>
1887  void emitRemark(Instruction *I, StringRef RemarkName,
1888  RemarkCallBack &&RemarkCB) const {
1889  if (!Configuration.OREGetter)
1890  return;
1891 
1892  Function *F = I->getFunction();
1893  auto &ORE = Configuration.OREGetter(F);
1894 
1895  if (RemarkName.startswith("OMP"))
1896  ORE.emit([&]() {
1897  return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, I))
1898  << " [" << RemarkName << "]";
1899  });
1900  else
1901  ORE.emit([&]() {
1902  return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, I));
1903  });
1904  }
1905 
1906  /// Emit a remark on a function.
1907  template <typename RemarkKind, typename RemarkCallBack>
1908  void emitRemark(Function *F, StringRef RemarkName,
1909  RemarkCallBack &&RemarkCB) const {
1910  if (!Configuration.OREGetter)
1911  return;
1912 
1913  auto &ORE = Configuration.OREGetter(F);
1914 
1915  if (RemarkName.startswith("OMP"))
1916  ORE.emit([&]() {
1917  return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, F))
1918  << " [" << RemarkName << "]";
1919  });
1920  else
1921  ORE.emit([&]() {
1922  return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, F));
1923  });
1924  }
1925 
1926  /// Helper struct used in the communication between an abstract attribute (AA)
1927  /// that wants to change the signature of a function and the Attributor which
1928  /// applies the changes. The struct is partially initialized with the
1929  /// information from the AA (see the constructor). All other members are
1930  /// provided by the Attributor prior to invoking any callbacks.
1932  /// Callee repair callback type
1933  ///
1934  /// The function repair callback is invoked once to rewire the replacement
1935  /// arguments in the body of the new function. The argument replacement info
1936  /// is passed, as build from the registerFunctionSignatureRewrite call, as
1937  /// well as the replacement function and an iteratore to the first
1938  /// replacement argument.
1939  using CalleeRepairCBTy = std::function<void(
1941 
1942  /// Abstract call site (ACS) repair callback type
1943  ///
1944  /// The abstract call site repair callback is invoked once on every abstract
1945  /// call site of the replaced function (\see ReplacedFn). The callback needs
1946  /// to provide the operands for the call to the new replacement function.
1947  /// The number and type of the operands appended to the provided vector
1948  /// (second argument) is defined by the number and types determined through
1949  /// the replacement type vector (\see ReplacementTypes). The first argument
1950  /// is the ArgumentReplacementInfo object registered with the Attributor
1951  /// through the registerFunctionSignatureRewrite call.
1952  using ACSRepairCBTy =
1955 
1956  /// Simple getters, see the corresponding members for details.
1957  ///{
1958 
1959  Attributor &getAttributor() const { return A; }
1960  const Function &getReplacedFn() const { return ReplacedFn; }
1961  const Argument &getReplacedArg() const { return ReplacedArg; }
1962  unsigned getNumReplacementArgs() const { return ReplacementTypes.size(); }
1964  return ReplacementTypes;
1965  }
1966 
1967  ///}
1968 
1969  private:
1970  /// Constructor that takes the argument to be replaced, the types of
1971  /// the replacement arguments, as well as callbacks to repair the call sites
1972  /// and new function after the replacement happened.
1974  ArrayRef<Type *> ReplacementTypes,
1975  CalleeRepairCBTy &&CalleeRepairCB,
1976  ACSRepairCBTy &&ACSRepairCB)
1977  : A(A), ReplacedFn(*Arg.getParent()), ReplacedArg(Arg),
1978  ReplacementTypes(ReplacementTypes.begin(), ReplacementTypes.end()),
1979  CalleeRepairCB(std::move(CalleeRepairCB)),
1980  ACSRepairCB(std::move(ACSRepairCB)) {}
1981 
1982  /// Reference to the attributor to allow access from the callbacks.
1983  Attributor &A;
1984 
1985  /// The "old" function replaced by ReplacementFn.
1986  const Function &ReplacedFn;
1987 
1988  /// The "old" argument replaced by new ones defined via ReplacementTypes.
1989  const Argument &ReplacedArg;
1990 
1991  /// The types of the arguments replacing ReplacedArg.
1992  const SmallVector<Type *, 8> ReplacementTypes;
1993 
1994  /// Callee repair callback, see CalleeRepairCBTy.
1995  const CalleeRepairCBTy CalleeRepairCB;
1996 
1997  /// Abstract call site (ACS) repair callback, see ACSRepairCBTy.
1998  const ACSRepairCBTy ACSRepairCB;
1999 
2000  /// Allow access to the private members from the Attributor.
2001  friend struct Attributor;
2002  };
2003 
2004  /// Check if we can rewrite a function signature.
2005  ///
2006  /// The argument \p Arg is replaced with new ones defined by the number,
2007  /// order, and types in \p ReplacementTypes.
2008  ///
2009  /// \returns True, if the replacement can be registered, via
2010  /// registerFunctionSignatureRewrite, false otherwise.
2012  ArrayRef<Type *> ReplacementTypes);
2013 
2014  /// Register a rewrite for a function signature.
2015  ///
2016  /// The argument \p Arg is replaced with new ones defined by the number,
2017  /// order, and types in \p ReplacementTypes. The rewiring at the call sites is
2018  /// done through \p ACSRepairCB and at the callee site through
2019  /// \p CalleeRepairCB.
2020  ///
2021  /// \returns True, if the replacement was registered, false otherwise.
2023  Argument &Arg, ArrayRef<Type *> ReplacementTypes,
2026 
2027  /// Check \p Pred on all function call sites.
2028  ///
2029  /// This method will evaluate \p Pred on call sites and return
2030  /// true if \p Pred holds in every call sites. However, this is only possible
2031  /// all call sites are known, hence the function has internal linkage.
2032  /// If true is returned, \p UsedAssumedInformation is set if assumed
2033  /// information was used to skip or simplify potential call sites.
2035  const AbstractAttribute &QueryingAA,
2036  bool RequireAllCallSites,
2037  bool &UsedAssumedInformation);
2038 
2039  /// Check \p Pred on all call sites of \p Fn.
2040  ///
2041  /// This method will evaluate \p Pred on call sites and return
2042  /// true if \p Pred holds in every call sites. However, this is only possible
2043  /// all call sites are known, hence the function has internal linkage.
2044  /// If true is returned, \p UsedAssumedInformation is set if assumed
2045  /// information was used to skip or simplify potential call sites.
2047  const Function &Fn, bool RequireAllCallSites,
2048  const AbstractAttribute *QueryingAA,
2049  bool &UsedAssumedInformation);
2050 
2051  /// Check \p Pred on all values potentially returned by \p F.
2052  ///
2053  /// This method will evaluate \p Pred on all values potentially returned by
2054  /// the function associated with \p QueryingAA. The returned values are
2055  /// matched with their respective return instructions. Returns true if \p Pred
2056  /// holds on all of them.
2058  function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> Pred,
2059  const AbstractAttribute &QueryingAA);
2060 
2061  /// Check \p Pred on all values potentially returned by the function
2062  /// associated with \p QueryingAA.
2063  ///
2064  /// This is the context insensitive version of the method above.
2065  bool checkForAllReturnedValues(function_ref<bool(Value &)> Pred,
2066  const AbstractAttribute &QueryingAA);
2067 
2068  /// Check \p Pred on all instructions in \p Fn with an opcode present in
2069  /// \p Opcodes.
2070  ///
2071  /// This method will evaluate \p Pred on all instructions with an opcode
2072  /// present in \p Opcode and return true if \p Pred holds on all of them.
2074  const Function *Fn,
2075  const AbstractAttribute &QueryingAA,
2076  const ArrayRef<unsigned> &Opcodes,
2077  bool &UsedAssumedInformation,
2078  bool CheckBBLivenessOnly = false,
2079  bool CheckPotentiallyDead = false);
2080 
2081  /// Check \p Pred on all instructions with an opcode present in \p Opcodes.
2082  ///
2083  /// This method will evaluate \p Pred on all instructions with an opcode
2084  /// present in \p Opcode and return true if \p Pred holds on all of them.
2086  const AbstractAttribute &QueryingAA,
2087  const ArrayRef<unsigned> &Opcodes,
2088  bool &UsedAssumedInformation,
2089  bool CheckBBLivenessOnly = false,
2090  bool CheckPotentiallyDead = false);
2091 
2092  /// Check \p Pred on all call-like instructions (=CallBased derived).
2093  ///
2094  /// See checkForAllCallLikeInstructions(...) for more information.
2096  const AbstractAttribute &QueryingAA,
2097  bool &UsedAssumedInformation,
2098  bool CheckBBLivenessOnly = false,
2099  bool CheckPotentiallyDead = false) {
2100  return checkForAllInstructions(
2101  Pred, QueryingAA,
2102  {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
2103  (unsigned)Instruction::Call},
2104  UsedAssumedInformation, CheckBBLivenessOnly, CheckPotentiallyDead);
2105  }
2106 
2107  /// Check \p Pred on all Read/Write instructions.
2108  ///
2109  /// This method will evaluate \p Pred on all instructions that read or write
2110  /// to memory present in the information cache and return true if \p Pred
2111  /// holds on all of them.
2113  AbstractAttribute &QueryingAA,
2114  bool &UsedAssumedInformation);
2115 
2116  /// Create a shallow wrapper for \p F such that \p F has internal linkage
2117  /// afterwards. It also sets the original \p F 's name to anonymous
2118  ///
2119  /// A wrapper is a function with the same type (and attributes) as \p F
2120  /// that will only call \p F and return the result, if any.
2121  ///
2122  /// Assuming the declaration of looks like:
2123  /// rty F(aty0 arg0, ..., atyN argN);
2124  ///
2125  /// The wrapper will then look as follows:
2126  /// rty wrapper(aty0 arg0, ..., atyN argN) {
2127  /// return F(arg0, ..., argN);
2128  /// }
2129  ///
2130  static void createShallowWrapper(Function &F);
2131 
2132  /// Returns true if the function \p F can be internalized. i.e. it has a
2133  /// compatible linkage.
2134  static bool isInternalizable(Function &F);
2135 
2136  /// Make another copy of the function \p F such that the copied version has
2137  /// internal linkage afterwards and can be analysed. Then we replace all uses
2138  /// of the original function to the copied one
2139  ///
2140  /// Only non-locally linked functions that have `linkonce_odr` or `weak_odr`
2141  /// linkage can be internalized because these linkages guarantee that other
2142  /// definitions with the same name have the same semantics as this one.
2143  ///
2144  /// This will only be run if the `attributor-allow-deep-wrappers` option is
2145  /// set, or if the function is called with \p Force set to true.
2146  ///
2147  /// If the function \p F failed to be internalized the return value will be a
2148  /// null pointer.
2149  static Function *internalizeFunction(Function &F, bool Force = false);
2150 
2151  /// Make copies of each function in the set \p FnSet such that the copied
2152  /// version has internal linkage afterwards and can be analysed. Then we
2153  /// replace all uses of the original function to the copied one. The map
2154  /// \p FnMap contains a mapping of functions to their internalized versions.
2155  ///
2156  /// Only non-locally linked functions that have `linkonce_odr` or `weak_odr`
2157  /// linkage can be internalized because these linkages guarantee that other
2158  /// definitions with the same name have the same semantics as this one.
2159  ///
2160  /// This version will internalize all the functions in the set \p FnSet at
2161  /// once and then replace the uses. This prevents internalized functions being
2162  /// called by external functions when there is an internalized version in the
2163  /// module.
2166 
2167  /// Return the data layout associated with the anchor scope.
2168  const DataLayout &getDataLayout() const { return InfoCache.DL; }
2169 
2170  /// The allocator used to allocate memory, e.g. for `AbstractAttribute`s.
2172 
2173 private:
2174  /// This method will do fixpoint iteration until fixpoint or the
2175  /// maximum iteration count is reached.
2176  ///
2177  /// If the maximum iteration count is reached, This method will
2178  /// indicate pessimistic fixpoint on attributes that transitively depend
2179  /// on attributes that were scheduled for an update.
2180  void runTillFixpoint();
2181 
2182  /// Gets called after scheduling, manifests attributes to the LLVM IR.
2183  ChangeStatus manifestAttributes();
2184 
2185  /// Gets called after attributes have been manifested, cleans up the IR.
2186  /// Deletes dead functions, blocks and instructions.
2187  /// Rewrites function signitures and updates the call graph.
2188  ChangeStatus cleanupIR();
2189 
2190  /// Identify internal functions that are effectively dead, thus not reachable
2191  /// from a live entry point. The functions are added to ToBeDeletedFunctions.
2192  void identifyDeadInternalFunctions();
2193 
2194  /// Run `::update` on \p AA and track the dependences queried while doing so.
2195  /// Also adjust the state if we know further updates are not necessary.
2196  ChangeStatus updateAA(AbstractAttribute &AA);
2197 
2198  /// Remember the dependences on the top of the dependence stack such that they
2199  /// may trigger further updates. (\see DependenceStack)
2200  void rememberDependences();
2201 
2202  /// Determine if CallBase context in \p IRP should be propagated.
2203  bool shouldPropagateCallBaseContext(const IRPosition &IRP);
2204 
2205  /// Apply all requested function signature rewrites
2206  /// (\see registerFunctionSignatureRewrite) and return Changed if the module
2207  /// was altered.
2208  ChangeStatus
2209  rewriteFunctionSignatures(SmallSetVector<Function *, 8> &ModifiedFns);
2210 
2211  /// Check if the Attribute \p AA should be seeded.
2212  /// See getOrCreateAAFor.
2213  bool shouldSeedAttribute(AbstractAttribute &AA);
2214 
2215  /// A nested map to lookup abstract attributes based on the argument position
2216  /// on the outer level, and the addresses of the static member (AAType::ID) on
2217  /// the inner level.
2218  ///{
2219  using AAMapKeyTy = std::pair<const char *, IRPosition>;
2221  ///}
2222 
2223  /// Map to remember all requested signature changes (= argument replacements).
2225  ArgumentReplacementMap;
2226 
2227  /// The set of functions we are deriving attributes for.
2228  SetVector<Function *> &Functions;
2229 
2230  /// The information cache that holds pre-processed (LLVM-IR) information.
2231  InformationCache &InfoCache;
2232 
2233  /// Abstract Attribute dependency graph
2234  AADepGraph DG;
2235 
2236  /// Set of functions for which we modified the content such that it might
2237  /// impact the call graph.
2238  SmallSetVector<Function *, 8> CGModifiedFunctions;
2239 
2240  /// Information about a dependence. If FromAA is changed ToAA needs to be
2241  /// updated as well.
2242  struct DepInfo {
2243  const AbstractAttribute *FromAA;
2244  const AbstractAttribute *ToAA;
2245  DepClassTy DepClass;
2246  };
2247 
2248  /// The dependence stack is used to track dependences during an
2249  /// `AbstractAttribute::update` call. As `AbstractAttribute::update` can be
2250  /// recursive we might have multiple vectors of dependences in here. The stack
2251  /// size, should be adjusted according to the expected recursion depth and the
2252  /// inner dependence vector size to the expected number of dependences per
2253  /// abstract attribute. Since the inner vectors are actually allocated on the
2254  /// stack we can be generous with their size.
2255  using DependenceVector = SmallVector<DepInfo, 8>;
2256  SmallVector<DependenceVector *, 16> DependenceStack;
2257 
2258  /// A set to remember the functions we already assume to be live and visited.
2259  DenseSet<const Function *> VisitedFunctions;
2260 
2261  /// Uses we replace with a new value after manifest is done. We will remove
2262  /// then trivially dead instructions as well.
2263  SmallMapVector<Use *, Value *, 32> ToBeChangedUses;
2264 
2265  /// Values we replace with a new value after manifest is done. We will remove
2266  /// then trivially dead instructions as well.
2267  SmallMapVector<Value *, std::pair<Value *, bool>, 32> ToBeChangedValues;
2268 
2269  /// Instructions we replace with `unreachable` insts after manifest is done.
2270  SmallSetVector<WeakVH, 16> ToBeChangedToUnreachableInsts;
2271 
2272  /// Invoke instructions with at least a single dead successor block.
2273  SmallSetVector<WeakVH, 16> InvokeWithDeadSuccessor;
2274 
2275  /// A flag that indicates which stage of the process we are in. Initially, the
2276  /// phase is SEEDING. Phase is changed in `Attributor::run()`
2277  enum class AttributorPhase {
2278  SEEDING,
2279  UPDATE,
2280  MANIFEST,
2281  CLEANUP,
2282  } Phase = AttributorPhase::SEEDING;
2283 
2284  /// The current initialization chain length. Tracked to avoid stack overflows.
2285  unsigned InitializationChainLength = 0;
2286 
2287  /// Functions, blocks, and instructions we delete after manifest is done.
2288  ///
2289  ///{
2290  SmallPtrSet<BasicBlock *, 8> ManifestAddedBlocks;
2291  SmallSetVector<Function *, 8> ToBeDeletedFunctions;
2292  SmallSetVector<BasicBlock *, 8> ToBeDeletedBlocks;
2293  SmallSetVector<WeakVH, 8> ToBeDeletedInsts;
2294  ///}
2295 
2296  /// Container with all the query AAs that requested an update via
2297  /// registerForUpdate.
2298  SmallSetVector<AbstractAttribute *, 16> QueryAAsAwaitingUpdate;
2299 
2300  /// User provided configuration for this Attributor instance.
2301  const AttributorConfig Configuration;
2302 
2303  friend AADepGraph;
2304  friend AttributorCallGraph;
2305 };
2306 
2307 /// An interface to query the internal state of an abstract attribute.
2308 ///
2309 /// The abstract state is a minimal interface that allows the Attributor to
2310 /// communicate with the abstract attributes about their internal state without
2311 /// enforcing or exposing implementation details, e.g., the (existence of an)
2312 /// underlying lattice.
2313 ///
2314 /// It is sufficient to be able to query if a state is (1) valid or invalid, (2)
2315 /// at a fixpoint, and to indicate to the state that (3) an optimistic fixpoint
2316 /// was reached or (4) a pessimistic fixpoint was enforced.
2317 ///
2318 /// All methods need to be implemented by the subclass. For the common use case,
2319 /// a single boolean state or a bit-encoded state, the BooleanState and
2320 /// {Inc,Dec,Bit}IntegerState classes are already provided. An abstract
2321 /// attribute can inherit from them to get the abstract state interface and
2322 /// additional methods to directly modify the state based if needed. See the
2323 /// class comments for help.
2325  virtual ~AbstractState() = default;
2326 
2327  /// Return if this abstract state is in a valid state. If false, no
2328  /// information provided should be used.
2329  virtual bool isValidState() const = 0;
2330 
2331  /// Return if this abstract state is fixed, thus does not need to be updated
2332  /// if information changes as it cannot change itself.
2333  virtual bool isAtFixpoint() const = 0;
2334 
2335  /// Indicate that the abstract state should converge to the optimistic state.
2336  ///
2337  /// This will usually make the optimistically assumed state the known to be
2338  /// true state.
2339  ///
2340  /// \returns ChangeStatus::UNCHANGED as the assumed value should not change.
2342 
2343  /// Indicate that the abstract state should converge to the pessimistic state.
2344  ///
2345  /// This will usually revert the optimistically assumed state to the known to
2346  /// be true state.
2347  ///
2348  /// \returns ChangeStatus::CHANGED as the assumed value may change.
2350 };
2351 
2352 /// Simple state with integers encoding.
2353 ///
2354 /// The interface ensures that the assumed bits are always a subset of the known
2355 /// bits. Users can only add known bits and, except through adding known bits,
2356 /// they can only remove assumed bits. This should guarantee monotoniticy and
2357 /// thereby the existence of a fixpoint (if used corretly). The fixpoint is
2358 /// reached when the assumed and known state/bits are equal. Users can
2359 /// force/inidicate a fixpoint. If an optimistic one is indicated, the known
2360 /// state will catch up with the assumed one, for a pessimistic fixpoint it is
2361 /// the other way around.
2362 template <typename base_ty, base_ty BestState, base_ty WorstState>
2364  using base_t = base_ty;
2365 
2366  IntegerStateBase() = default;
2368 
2369  /// Return the best possible representable state.
2370  static constexpr base_t getBestState() { return BestState; }
2371  static constexpr base_t getBestState(const IntegerStateBase &) {
2372  return getBestState();
2373  }
2374 
2375  /// Return the worst possible representable state.
2376  static constexpr base_t getWorstState() { return WorstState; }
2377  static constexpr base_t getWorstState(const IntegerStateBase &) {
2378  return getWorstState();
2379  }
2380 
2381  /// See AbstractState::isValidState()
2382  /// NOTE: For now we simply pretend that the worst possible state is invalid.
2383  bool isValidState() const override { return Assumed != getWorstState(); }
2384 
2385  /// See AbstractState::isAtFixpoint()
2386  bool isAtFixpoint() const override { return Assumed == Known; }
2387 
2388  /// See AbstractState::indicateOptimisticFixpoint(...)
2390  Known = Assumed;
2391  return ChangeStatus::UNCHANGED;
2392  }
2393 
2394  /// See AbstractState::indicatePessimisticFixpoint(...)
2396  Assumed = Known;
2397  return ChangeStatus::CHANGED;
2398  }
2399 
2400  /// Return the known state encoding
2401  base_t getKnown() const { return Known; }
2402 
2403  /// Return the assumed state encoding.
2404  base_t getAssumed() const { return Assumed; }
2405 
2406  /// Equality for IntegerStateBase.
2407  bool
2409  return this->getAssumed() == R.getAssumed() &&
2410  this->getKnown() == R.getKnown();
2411  }
2412 
2413  /// Inequality for IntegerStateBase.
2414  bool
2416  return !(*this == R);
2417  }
2418 
2419  /// "Clamp" this state with \p R. The result is subtype dependent but it is
2420  /// intended that only information assumed in both states will be assumed in
2421  /// this one afterwards.
2423  handleNewAssumedValue(R.getAssumed());
2424  }
2425 
2426  /// "Clamp" this state with \p R. The result is subtype dependent but it is
2427  /// intended that information known in either state will be known in
2428  /// this one afterwards.
2430  handleNewKnownValue(R.getKnown());
2431  }
2432 
2434  joinOR(R.getAssumed(), R.getKnown());
2435  }
2436 
2438  joinAND(R.getAssumed(), R.getKnown());
2439  }
2440 
2441 protected:
2442  /// Handle a new assumed value \p Value. Subtype dependent.
2443  virtual void handleNewAssumedValue(base_t Value) = 0;
2444 
2445  /// Handle a new known value \p Value. Subtype dependent.
2446  virtual void handleNewKnownValue(base_t Value) = 0;
2447 
2448  /// Handle a value \p Value. Subtype dependent.
2449  virtual void joinOR(base_t AssumedValue, base_t KnownValue) = 0;
2450 
2451  /// Handle a new assumed value \p Value. Subtype dependent.
2452  virtual void joinAND(base_t AssumedValue, base_t KnownValue) = 0;
2453 
2454  /// The known state encoding in an integer of type base_t.
2456 
2457  /// The assumed state encoding in an integer of type base_t.
2459 };
2460 
2461 /// Specialization of the integer state for a bit-wise encoding.
2462 template <typename base_ty = uint32_t, base_ty BestState = ~base_ty(0),
2463  base_ty WorstState = 0>
2465  : public IntegerStateBase<base_ty, BestState, WorstState> {
2466  using base_t = base_ty;
2467 
2468  /// Return true if the bits set in \p BitsEncoding are "known bits".
2469  bool isKnown(base_t BitsEncoding) const {
2470  return (this->Known & BitsEncoding) == BitsEncoding;
2471  }
2472 
2473  /// Return true if the bits set in \p BitsEncoding are "assumed bits".
2474  bool isAssumed(base_t BitsEncoding) const {
2475  return (this->Assumed & BitsEncoding) == BitsEncoding;
2476  }
2477 
2478  /// Add the bits in \p BitsEncoding to the "known bits".
2480  // Make sure we never miss any "known bits".
2481  this->Assumed |= Bits;
2482  this->Known |= Bits;
2483  return *this;
2484  }
2485 
2486  /// Remove the bits in \p BitsEncoding from the "assumed bits" if not known.
2488  return intersectAssumedBits(~BitsEncoding);
2489  }
2490 
2491  /// Remove the bits in \p BitsEncoding from the "known bits".
2493  this->Known = (this->Known & ~BitsEncoding);
2494  return *this;
2495  }
2496 
2497  /// Keep only "assumed bits" also set in \p BitsEncoding but all known ones.
2499  // Make sure we never loose any "known bits".
2500  this->Assumed = (this->Assumed & BitsEncoding) | this->Known;
2501  return *this;
2502  }
2503 
2504 private:
2505  void handleNewAssumedValue(base_t Value) override {
2507  }
2508  void handleNewKnownValue(base_t Value) override { addKnownBits(Value); }
2509  void joinOR(base_t AssumedValue, base_t KnownValue) override {
2510  this->Known |= KnownValue;
2511  this->Assumed |= AssumedValue;
2512  }
2513  void joinAND(base_t AssumedValue, base_t KnownValue) override {
2514  this->Known &= KnownValue;
2515  this->Assumed &= AssumedValue;
2516  }
2517 };
2518 
2519 /// Specialization of the integer state for an increasing value, hence ~0u is
2520 /// the best state and 0 the worst.
2521 template <typename base_ty = uint32_t, base_ty BestState = ~base_ty(0),
2522  base_ty WorstState = 0>
2524  : public IntegerStateBase<base_ty, BestState, WorstState> {
2526  using base_t = base_ty;
2527 
2530 
2531  /// Return the best possible representable state.
2532  static constexpr base_t getBestState() { return BestState; }
2533  static constexpr base_t
2535  return getBestState();
2536  }
2537 
2538  /// Take minimum of assumed and \p Value.
2540  // Make sure we never loose "known value".
2541  this->Assumed = std::max(std::min(this->Assumed, Value), this->Known);
2542  return *this;
2543  }
2544 
2545  /// Take maximum of known and \p Value.
2547  // Make sure we never loose "known value".
2548  this->Assumed = std::max(Value, this->Assumed);
2549  this->Known = std::max(Value, this->Known);
2550  return *this;
2551  }
2552 
2553 private:
2554  void handleNewAssumedValue(base_t Value) override {
2556  }
2557  void handleNewKnownValue(base_t Value) override { takeKnownMaximum(Value); }
2558  void joinOR(base_t AssumedValue, base_t KnownValue) override {
2559  this->Known = std::max(this->Known, KnownValue);
2560  this->Assumed = std::max(this->Assumed, AssumedValue);
2561  }
2562  void joinAND(base_t AssumedValue, base_t KnownValue) override {
2563  this->Known = std::min(this->Known, KnownValue);
2564  this->Assumed = std::min(this->Assumed, AssumedValue);
2565  }
2566 };
2567 
2568 /// Specialization of the integer state for a decreasing value, hence 0 is the
2569 /// best state and ~0u the worst.
2570 template <typename base_ty = uint32_t>
2571 struct DecIntegerState : public IntegerStateBase<base_ty, 0, ~base_ty(0)> {
2572  using base_t = base_ty;
2573 
2574  /// Take maximum of assumed and \p Value.
2576  // Make sure we never loose "known value".
2577  this->Assumed = std::min(std::max(this->Assumed, Value), this->Known);
2578  return *this;
2579  }
2580 
2581  /// Take minimum of known and \p Value.
2583  // Make sure we never loose "known value".
2584  this->Assumed = std::min(Value, this->Assumed);
2585  this->Known = std::min(Value, this->Known);
2586  return *this;
2587  }
2588 
2589 private:
2590  void handleNewAssumedValue(base_t Value) override {
2592  }
2593  void handleNewKnownValue(base_t Value) override { takeKnownMinimum(Value); }
2594  void joinOR(base_t AssumedValue, base_t KnownValue) override {
2595  this->Assumed = std::min(this->Assumed, KnownValue);
2596  this->Assumed = std::min(this->Assumed, AssumedValue);
2597  }
2598  void joinAND(base_t AssumedValue, base_t KnownValue) override {
2599  this->Assumed = std::max(this->Assumed, KnownValue);
2600  this->Assumed = std::max(this->Assumed, AssumedValue);
2601  }
2602 };
2603 
2604 /// Simple wrapper for a single bit (boolean) state.
2605 struct BooleanState : public IntegerStateBase<bool, true, false> {
2608 
2609  BooleanState() = default;
2611 
2612  /// Set the assumed value to \p Value but never below the known one.
2613  void setAssumed(bool Value) { Assumed &= (Known | Value); }
2614 
2615  /// Set the known and asssumed value to \p Value.
2616  void setKnown(bool Value) {
2617  Known |= Value;
2618  Assumed |= Value;
2619  }
2620 
2621  /// Return true if the state is assumed to hold.
2622  bool isAssumed() const { return getAssumed(); }
2623 
2624  /// Return true if the state is known to hold.
2625  bool isKnown() const { return getKnown(); }
2626 
2627 private:
2628  void handleNewAssumedValue(base_t Value) override {
2629  if (!Value)
2630  Assumed = Known;
2631  }
2632  void handleNewKnownValue(base_t Value) override {
2633  if (Value)
2634  Known = (Assumed = Value);
2635  }
2636  void joinOR(base_t AssumedValue, base_t KnownValue) override {
2637  Known |= KnownValue;
2638  Assumed |= AssumedValue;
2639  }
2640  void joinAND(base_t AssumedValue, base_t KnownValue) override {
2641  Known &= KnownValue;
2642  Assumed &= AssumedValue;
2643  }
2644 };
2645 
2646 /// State for an integer range.
2648 
2649  /// Bitwidth of the associated value.
2651 
2652  /// State representing assumed range, initially set to empty.
2654 
2655  /// State representing known range, initially set to [-inf, inf].
2657 
2660  Known(ConstantRange::getFull(BitWidth)) {}
2661 
2663  : BitWidth(CR.getBitWidth()), Assumed(CR),
2664  Known(getWorstState(CR.getBitWidth())) {}
2665 
2666  /// Return the worst possible representable state.
2668  return ConstantRange::getFull(BitWidth);
2669  }
2670 
2671  /// Return the best possible representable state.
2673  return ConstantRange::getEmpty(BitWidth);
2674  }
2676  return getBestState(IRS.getBitWidth());
2677  }
2678 
2679  /// Return associated values' bit width.
2680  uint32_t getBitWidth() const { return BitWidth; }
2681 
2682  /// See AbstractState::isValidState()
2683  bool isValidState() const override {
2684  return BitWidth > 0 && !Assumed.isFullSet();
2685  }
2686 
2687  /// See AbstractState::isAtFixpoint()
2688  bool isAtFixpoint() const override { return Assumed == Known; }
2689 
2690  /// See AbstractState::indicateOptimisticFixpoint(...)
2692  Known = Assumed;
2693  return ChangeStatus::CHANGED;
2694  }
2695 
2696  /// See AbstractState::indicatePessimisticFixpoint(...)
2698  Assumed = Known;
2699  return ChangeStatus::CHANGED;
2700  }
2701 
2702  /// Return the known state encoding
2703  ConstantRange getKnown() const { return Known; }
2704 
2705  /// Return the assumed state encoding.
2706  ConstantRange getAssumed() const { return Assumed; }
2707 
2708  /// Unite assumed range with the passed state.
2709  void unionAssumed(const ConstantRange &R) {
2710  // Don't loose a known range.
2712  }
2713 
2714  /// See IntegerRangeState::unionAssumed(..).
2716  unionAssumed(R.getAssumed());
2717  }
2718 
2719  /// Intersect known range with the passed state.
2722  Known = Known.intersectWith(R);
2723  }
2724 
2725  /// See IntegerRangeState::intersectKnown(..).
2727  intersectKnown(R.getKnown());
2728  }
2729 
2730  /// Equality for IntegerRangeState.
2731  bool operator==(const IntegerRangeState &R) const {
2732  return getAssumed() == R.getAssumed() && getKnown() == R.getKnown();
2733  }
2734 
2735  /// "Clamp" this state with \p R. The result is subtype dependent but it is
2736  /// intended that only information assumed in both states will be assumed in
2737  /// this one afterwards.
2739  // NOTE: `^=` operator seems like `intersect` but in this case, we need to
2740  // take `union`.
2741  unionAssumed(R);
2742  return *this;
2743  }
2744 
2746  // NOTE: `&=` operator seems like `intersect` but in this case, we need to
2747  // take `union`.
2748  Known = Known.unionWith(R.getKnown());
2749  Assumed = Assumed.unionWith(R.getAssumed());
2750  return *this;
2751  }
2752 };
2753 
2754 /// Simple state for a set.
2755 ///
2756 /// This represents a state containing a set of values. The interface supports
2757 /// modelling sets that contain all possible elements. The state's internal
2758 /// value is modified using union or intersection operations.
2759 template <typename BaseTy> struct SetState : public AbstractState {
2760  /// A wrapper around a set that has semantics for handling unions and
2761  /// intersections with a "universal" set that contains all elements.
2762  struct SetContents {
2763  /// Creates a universal set with no concrete elements or an empty set.
2764  SetContents(bool Universal) : Universal(Universal) {}
2765 
2766  /// Creates a non-universal set with concrete values.
2767  SetContents(const DenseSet<BaseTy> &Assumptions)
2768  : Universal(false), Set(Assumptions) {}
2769 
2770  SetContents(bool Universal, const DenseSet<BaseTy> &Assumptions)
2771  : Universal(Universal), Set(Assumptions) {}
2772 
2773  const DenseSet<BaseTy> &getSet() const { return Set; }
2774 
2775  bool isUniversal() const { return Universal; }
2776 
2777  bool empty() const { return Set.empty() && !Universal; }
2778 
2779  /// Finds A := A ^ B where A or B could be the "Universal" set which
2780  /// contains every possible attribute. Returns true if changes were made.
2782  bool IsUniversal = Universal;
2783  unsigned Size = Set.size();
2784 
2785  // A := A ^ U = A
2786  if (RHS.isUniversal())
2787  return false;
2788 
2789  // A := U ^ B = B
2790  if (Universal)
2791  Set = RHS.getSet();
2792  else
2793  set_intersect(Set, RHS.getSet());
2794 
2795  Universal &= RHS.isUniversal();
2796  return IsUniversal != Universal || Size != Set.size();
2797  }
2798 
2799  /// Finds A := A u B where A or B could be the "Universal" set which
2800  /// contains every possible attribute. returns true if changes were made.
2801  bool getUnion(const SetContents &RHS) {
2802  bool IsUniversal = Universal;
2803  unsigned Size = Set.size();
2804 
2805  // A := A u U = U = U u B
2806  if (!RHS.isUniversal() && !Universal)
2807  set_union(Set, RHS.getSet());
2808 
2809  Universal |= RHS.isUniversal();
2810  return IsUniversal != Universal || Size != Set.size();
2811  }
2812 
2813  private:
2814  /// Indicates if this set is "universal", containing every possible element.
2815  bool Universal;
2816 
2817  /// The set of currently active assumptions.
2818  DenseSet<BaseTy> Set;
2819  };
2820 
2821  SetState() : Known(false), Assumed(true), IsAtFixedpoint(false) {}
2822 
2823  /// Initializes the known state with an initial set and initializes the
2824  /// assumed state as universal.
2826  : Known(Known), Assumed(true), IsAtFixedpoint(false) {}
2827 
2828  /// See AbstractState::isValidState()
2829  bool isValidState() const override { return !Assumed.empty(); }
2830 
2831  /// See AbstractState::isAtFixpoint()
2832  bool isAtFixpoint() const override { return IsAtFixedpoint; }
2833 
2834  /// See AbstractState::indicateOptimisticFixpoint(...)
2836  IsAtFixedpoint = true;
2837  Known = Assumed;
2838  return ChangeStatus::UNCHANGED;
2839  }
2840 
2841  /// See AbstractState::indicatePessimisticFixpoint(...)
2843  IsAtFixedpoint = true;
2844  Assumed = Known;
2845  return ChangeStatus::CHANGED;
2846  }
2847 
2848  /// Return the known state encoding.
2849  const SetContents &getKnown() const { return Known; }
2850 
2851  /// Return the assumed state encoding.
2852  const SetContents &getAssumed() const { return Assumed; }
2853 
2854  /// Returns if the set state contains the element.
2855  bool setContains(const BaseTy &Elem) const {
2856  return Assumed.getSet().contains(Elem) || Known.getSet().contains(Elem);
2857  }
2858 
2859  /// Performs the set intersection between this set and \p RHS. Returns true if
2860  /// changes were made.
2861  bool getIntersection(const SetContents &RHS) {
2862  unsigned SizeBefore = Assumed.getSet().size();
2863 
2864  // Get intersection and make sure that the known set is still a proper
2865  // subset of the assumed set. A := K u (A ^ R).
2866  Assumed.getIntersection(RHS);
2867  Assumed.getUnion(Known);
2868 
2869  return SizeBefore != Assumed.getSet().size();
2870  }
2871 
2872  /// Performs the set union between this set and \p RHS. Returns true if
2873  /// changes were made.
2874  bool getUnion(const SetContents &RHS) { return Assumed.getUnion(RHS); }
2875 
2876 private:
2877  /// The set of values known for this state.
2878  SetContents Known;
2879 
2880  /// The set of assumed values for this state.
2881  SetContents Assumed;
2882 
2883  bool IsAtFixedpoint;
2884 };
2885 
2886 /// Helper struct necessary as the modular build fails if the virtual method
2887 /// IRAttribute::manifest is defined in the Attributor.cpp.
2889  static ChangeStatus manifestAttrs(Attributor &A, const IRPosition &IRP,
2890  const ArrayRef<Attribute> &DeducedAttrs,
2891  bool ForceReplace = false);
2892 };
2893 
2894 /// Helper to tie a abstract state implementation to an abstract attribute.
2895 template <typename StateTy, typename BaseType, class... Ts>
2896 struct StateWrapper : public BaseType, public StateTy {
2897  /// Provide static access to the type of the state.
2899 
2900  StateWrapper(const IRPosition &IRP, Ts... Args)
2901  : BaseType(IRP), StateTy(Args...) {}
2902 
2903  /// See AbstractAttribute::getState(...).
2904  StateType &getState() override { return *this; }
2905 
2906  /// See AbstractAttribute::getState(...).
2907  const StateType &getState() const override { return *this; }
2908 };
2909 
2910 /// Helper class that provides common functionality to manifest IR attributes.
2911 template <Attribute::AttrKind AK, typename BaseType>
2912 struct IRAttribute : public BaseType {
2913  IRAttribute(const IRPosition &IRP) : BaseType(IRP) {}
2914 
2915  /// See AbstractAttribute::initialize(...).
2916  void initialize(Attributor &A) override {
2917  const IRPosition &IRP = this->getIRPosition();
2918  if (isa<UndefValue>(IRP.getAssociatedValue()) ||
2919  this->hasAttr(getAttrKind(), /* IgnoreSubsumingPositions */ false,
2920  &A)) {
2921  this->getState().indicateOptimisticFixpoint();
2922  return;
2923  }
2924 
2925  bool IsFnInterface = IRP.isFnInterfaceKind();
2926  const Function *FnScope = IRP.getAnchorScope();
2927  // TODO: Not all attributes require an exact definition. Find a way to
2928  // enable deduction for some but not all attributes in case the
2929  // definition might be changed at runtime, see also
2930  // http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
2931  // TODO: We could always determine abstract attributes and if sufficient
2932  // information was found we could duplicate the functions that do not
2933  // have an exact definition.
2934  if (IsFnInterface && (!FnScope || !A.isFunctionIPOAmendable(*FnScope)))
2935  this->getState().indicatePessimisticFixpoint();
2936  }
2937 
2938  /// See AbstractAttribute::manifest(...).
2940  if (isa<UndefValue>(this->getIRPosition().getAssociatedValue()))
2941  return ChangeStatus::UNCHANGED;
2942  SmallVector<Attribute, 4> DeducedAttrs;
2943  getDeducedAttributes(this->getAnchorValue().getContext(), DeducedAttrs);
2944  return IRAttributeManifest::manifestAttrs(A, this->getIRPosition(),
2945  DeducedAttrs);
2946  }
2947 
2948  /// Return the kind that identifies the abstract attribute implementation.
2949  Attribute::AttrKind getAttrKind() const { return AK; }
2950 
2951  /// Return the deduced attributes in \p Attrs.
2954  Attrs.emplace_back(Attribute::get(Ctx, getAttrKind()));
2955  }
2956 };
2957 
2958 /// Base struct for all "concrete attribute" deductions.
2959 ///
2960 /// The abstract attribute is a minimal interface that allows the Attributor to
2961 /// orchestrate the abstract/fixpoint analysis. The design allows to hide away
2962 /// implementation choices made for the subclasses but also to structure their
2963 /// implementation and simplify the use of other abstract attributes in-flight.
2964 ///
2965 /// To allow easy creation of new attributes, most methods have default
2966 /// implementations. The ones that do not are generally straight forward, except
2967 /// `AbstractAttribute::updateImpl` which is the location of most reasoning
2968 /// associated with the abstract attribute. The update is invoked by the
2969 /// Attributor in case the situation used to justify the current optimistic
2970 /// state might have changed. The Attributor determines this automatically
2971 /// by monitoring the `Attributor::getAAFor` calls made by abstract attributes.
2972 ///
2973 /// The `updateImpl` method should inspect the IR and other abstract attributes
2974 /// in-flight to justify the best possible (=optimistic) state. The actual
2975 /// implementation is, similar to the underlying abstract state encoding, not
2976 /// exposed. In the most common case, the `updateImpl` will go through a list of
2977 /// reasons why its optimistic state is valid given the current information. If
2978 /// any combination of them holds and is sufficient to justify the current
2979 /// optimistic state, the method shall return UNCHAGED. If not, the optimistic
2980 /// state is adjusted to the situation and the method shall return CHANGED.
2981 ///
2982 /// If the manifestation of the "concrete attribute" deduced by the subclass
2983 /// differs from the "default" behavior, which is a (set of) LLVM-IR
2984 /// attribute(s) for an argument, call site argument, function return value, or
2985 /// function, the `AbstractAttribute::manifest` method should be overloaded.
2986 ///
2987 /// NOTE: If the state obtained via getState() is INVALID, thus if
2988 /// AbstractAttribute::getState().isValidState() returns false, no
2989 /// information provided by the methods of this class should be used.
2990 /// NOTE: The Attributor currently has certain limitations to what we can do.
2991 /// As a general rule of thumb, "concrete" abstract attributes should *for
2992 /// now* only perform "backward" information propagation. That means
2993 /// optimistic information obtained through abstract attributes should
2994 /// only be used at positions that precede the origin of the information
2995 /// with regards to the program flow. More practically, information can
2996 /// *now* be propagated from instructions to their enclosing function, but
2997 /// *not* from call sites to the called function. The mechanisms to allow
2998 /// both directions will be added in the future.
2999 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
3000 /// described in the file comment.
3003 
3005 
3006  /// Virtual destructor.
3007  virtual ~AbstractAttribute() = default;
3008 
3009  /// This function is used to identify if an \p DGN is of type
3010  /// AbstractAttribute so that the dyn_cast and cast can use such information
3011  /// to cast an AADepGraphNode to an AbstractAttribute.
3012  ///
3013  /// We eagerly return true here because all AADepGraphNodes except for the
3014  /// Synthethis Node are of type AbstractAttribute
3015  static bool classof(const AADepGraphNode *DGN) { return true; }
3016 
3017  /// Initialize the state with the information in the Attributor \p A.
3018  ///
3019  /// This function is called by the Attributor once all abstract attributes
3020  /// have been identified. It can and shall be used for task like:
3021  /// - identify existing knowledge in the IR and use it for the "known state"
3022  /// - perform any work that is not going to change over time, e.g., determine
3023  /// a subset of the IR, or attributes in-flight, that have to be looked at
3024  /// in the `updateImpl` method.
3025  virtual void initialize(Attributor &A) {}
3026 
3027  /// A query AA is always scheduled as long as we do updates because it does
3028  /// lazy computation that cannot be determined to be done from the outside.
3029  /// However, while query AAs will not be fixed if they do not have outstanding
3030  /// dependences, we will only schedule them like other AAs. If a query AA that
3031  /// received a new query it needs to request an update via
3032  /// `Attributor::requestUpdateForAA`.
3033  virtual bool isQueryAA() const { return false; }
3034 
3035  /// Return the internal abstract state for inspection.
3036  virtual StateType &getState() = 0;
3037  virtual const StateType &getState() const = 0;
3038 
3039  /// Return an IR position, see struct IRPosition.
3040  const IRPosition &getIRPosition() const { return *this; };
3041  IRPosition &getIRPosition() { return *this; };
3042 
3043  /// Helper functions, for debug purposes only.
3044  ///{
3045  void print(raw_ostream &OS) const override;
3046  virtual void printWithDeps(raw_ostream &OS) const;
3047  void dump() const { print(dbgs()); }
3048 
3049  /// This function should return the "summarized" assumed state as string.
3050  virtual const std::string getAsStr() const = 0;
3051 
3052  /// This function should return the name of the AbstractAttribute
3053  virtual const std::string getName() const = 0;
3054 
3055  /// This function should return the address of the ID of the AbstractAttribute
3056  virtual const char *getIdAddr() const = 0;
3057  ///}
3058 
3059  /// Allow the Attributor access to the protected methods.
3060  friend struct Attributor;
3061 
3062 protected:
3063  /// Hook for the Attributor to trigger an update of the internal state.
3064  ///
3065  /// If this attribute is already fixed, this method will return UNCHANGED,
3066  /// otherwise it delegates to `AbstractAttribute::updateImpl`.
3067  ///
3068  /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
3070 
3071  /// Hook for the Attributor to trigger the manifestation of the information
3072  /// represented by the abstract attribute in the LLVM-IR.
3073  ///
3074  /// \Return CHANGED if the IR was altered, otherwise UNCHANGED.
3076  return ChangeStatus::UNCHANGED;
3077  }
3078 
3079  /// Hook to enable custom statistic tracking, called after manifest that
3080  /// resulted in a change if statistics are enabled.
3081  ///
3082  /// We require subclasses to provide an implementation so we remember to
3083  /// add statistics for them.
3084  virtual void trackStatistics() const = 0;
3085 
3086  /// The actual update/transfer function which has to be implemented by the
3087  /// derived classes.
3088  ///
3089  /// If it is called, the environment has changed and we have to determine if
3090  /// the current information is still valid or adjust it otherwise.
3091  ///
3092  /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
3093  virtual ChangeStatus updateImpl(Attributor &A) = 0;
3094 };
3095 
3096 /// Forward declarations of output streams for debug purposes.
3097 ///
3098 ///{
3099 raw_ostream &operator<<(raw_ostream &OS, const AbstractAttribute &AA);
3100 raw_ostream &operator<<(raw_ostream &OS, ChangeStatus S);
3101 raw_ostream &operator<<(raw_ostream &OS, IRPosition::Kind);
3102 raw_ostream &operator<<(raw_ostream &OS, const IRPosition &);
3103 raw_ostream &operator<<(raw_ostream &OS, const AbstractState &State);
3104 template <typename base_ty, base_ty BestState, base_ty WorstState>
3105 raw_ostream &
3108  return OS << "(" << S.getKnown() << "-" << S.getAssumed() << ")"
3109  << static_cast<const AbstractState &>(S);
3110 }
3111 raw_ostream &operator<<(raw_ostream &OS, const IntegerRangeState &State);
3112 ///}
3113 
3114 struct AttributorPass : public PassInfoMixin<AttributorPass> {
3116 };
3117 struct AttributorCGSCCPass : public PassInfoMixin<AttributorCGSCCPass> {
3119  LazyCallGraph &CG, CGSCCUpdateResult &UR);
3120 };
3121 
3124 
3125 /// Helper function to clamp a state \p S of type \p StateType with the
3126 /// information in \p R and indicate/return if \p S did change (as-in update is
3127 /// required to be run again).
3128 template <typename StateType>
3129 ChangeStatus clampStateAndIndicateChange(StateType &S, const StateType &R) {
3130  auto Assumed = S.getAssumed();
3131  S ^= R;
3132  return Assumed == S.getAssumed() ? ChangeStatus::UNCHANGED
3134 }
3135 
3136 /// ----------------------------------------------------------------------------
3137 /// Abstract Attribute Classes
3138 /// ----------------------------------------------------------------------------
3139 
3140 /// An abstract attribute for the returned values of a function.
3142  : public IRAttribute<Attribute::Returned, AbstractAttribute> {
3144 
3145  /// Return an assumed unique return value if a single candidate is found. If
3146  /// there cannot be one, return a nullptr. If it is not clear yet, return the
3147  /// Optional::NoneType.
3149 
3150  /// Check \p Pred on all returned values.
3151  ///
3152  /// This method will evaluate \p Pred on returned values and return
3153  /// true if (1) all returned values are known, and (2) \p Pred returned true
3154  /// for all returned values.
3155  ///
3156  /// Note: Unlike the Attributor::checkForAllReturnedValuesAndReturnInsts
3157  /// method, this one will not filter dead return instructions.
3159  function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> Pred)
3160  const = 0;
3161 
3162  using iterator =
3164  using const_iterator =
3168 
3169  virtual size_t getNumReturnValues() const = 0;
3170 
3171  /// Create an abstract attribute view for the position \p IRP.
3172  static AAReturnedValues &createForPosition(const IRPosition &IRP,
3173  Attributor &A);
3174 
3175  /// See AbstractAttribute::getName()
3176  const std::string getName() const override { return "AAReturnedValues"; }
3177 
3178  /// See AbstractAttribute::getIdAddr()
3179  const char *getIdAddr() const override { return &ID; }
3180 
3181  /// This function should return true if the type of the \p AA is
3182  /// AAReturnedValues
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 
3192  : public IRAttribute<Attribute::NoUnwind,
3193  StateWrapper<BooleanState, AbstractAttribute>> {
3194  AANoUnwind(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3195 
3196  /// Returns true if nounwind is assumed.
3197  bool isAssumedNoUnwind() const { return getAssumed(); }
3198 
3199  /// Returns true if nounwind is known.
3200  bool isKnownNoUnwind() const { return getKnown(); }
3201 
3202  /// Create an abstract attribute view for the position \p IRP.
3203  static AANoUnwind &createForPosition(const IRPosition &IRP, Attributor &A);
3204 
3205  /// See AbstractAttribute::getName()
3206  const std::string getName() const override { return "AANoUnwind"; }
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 AANoUnwind
3212  static bool classof(const AbstractAttribute *AA) {
3213  return (AA->getIdAddr() == &ID);
3214  }
3215 
3216  /// Unique ID (due to the unique address)
3217  static const char ID;
3218 };
3219 
3220 struct AANoSync
3221  : public IRAttribute<Attribute::NoSync,
3222  StateWrapper<BooleanState, AbstractAttribute>> {
3223  AANoSync(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3224 
3225  /// Returns true if "nosync" is assumed.
3226  bool isAssumedNoSync() const { return getAssumed(); }
3227 
3228  /// Returns true if "nosync" is known.
3229  bool isKnownNoSync() const { return getKnown(); }
3230 
3231  /// Helper function used to determine whether an instruction is non-relaxed
3232  /// atomic. In other words, if an atomic instruction does not have unordered
3233  /// or monotonic ordering
3234  static bool isNonRelaxedAtomic(const Instruction *I);
3235 
3236  /// Helper function specific for intrinsics which are potentially volatile.
3237  static bool isNoSyncIntrinsic(const Instruction *I);
3238 
3239  /// Create an abstract attribute view for the position \p IRP.
3240  static AANoSync &createForPosition(const IRPosition &IRP, Attributor &A);
3241 
3242  /// See AbstractAttribute::getName()
3243  const std::string getName() const override { return "AANoSync"; }
3244 
3245  /// See AbstractAttribute::getIdAddr()
3246  const char *getIdAddr() const override { return &ID; }
3247 
3248  /// This function should return true if the type of the \p AA is AANoSync
3249  static bool classof(const AbstractAttribute *AA) {
3250  return (AA->getIdAddr() == &ID);
3251  }
3252 
3253  /// Unique ID (due to the unique address)
3254  static const char ID;
3255 };
3256 
3257 /// An abstract interface for all nonnull attributes.
3259  : public IRAttribute<Attribute::NonNull,
3260  StateWrapper<BooleanState, AbstractAttribute>> {
3261  AANonNull(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3262 
3263  /// Return true if we assume that the underlying value is nonnull.
3264  bool isAssumedNonNull() const { return getAssumed(); }
3265 
3266  /// Return true if we know that underlying value is nonnull.
3267  bool isKnownNonNull() const { return getKnown(); }
3268 
3269  /// Create an abstract attribute view for the position \p IRP.
3270  static AANonNull &createForPosition(const IRPosition &IRP, Attributor &A);
3271 
3272  /// See AbstractAttribute::getName()
3273  const std::string getName() const override { return "AANonNull"; }
3274 
3275  /// See AbstractAttribute::getIdAddr()
3276  const char *getIdAddr() const override { return &ID; }
3277 
3278  /// This function should return true if the type of the \p AA is AANonNull
3279  static bool classof(const AbstractAttribute *AA) {
3280  return (AA->getIdAddr() == &ID);
3281  }
3282 
3283  /// Unique ID (due to the unique address)
3284  static const char ID;
3285 };
3286 
3287 /// An abstract attribute for norecurse.
3289  : public IRAttribute<Attribute::NoRecurse,
3290  StateWrapper<BooleanState, AbstractAttribute>> {
3291  AANoRecurse(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3292 
3293  /// Return true if "norecurse" is assumed.
3294  bool isAssumedNoRecurse() const { return getAssumed(); }
3295 
3296  /// Return true if "norecurse" is known.
3297  bool isKnownNoRecurse() const { return getKnown(); }
3298 
3299  /// Create an abstract attribute view for the position \p IRP.
3300  static AANoRecurse &createForPosition(const IRPosition &IRP, Attributor &A);
3301 
3302  /// See AbstractAttribute::getName()
3303  const std::string getName() const override { return "AANoRecurse"; }
3304 
3305  /// See AbstractAttribute::getIdAddr()
3306  const char *getIdAddr() const override { return &ID; }
3307 
3308  /// This function should return true if the type of the \p AA is AANoRecurse
3309  static bool classof(const AbstractAttribute *AA) {
3310  return (AA->getIdAddr() == &ID);
3311  }
3312 
3313  /// Unique ID (due to the unique address)
3314  static const char ID;
3315 };
3316 
3317 /// An abstract attribute for willreturn.
3319  : public IRAttribute<Attribute::WillReturn,
3320  StateWrapper<BooleanState, AbstractAttribute>> {
3321  AAWillReturn(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3322 
3323  /// Return true if "willreturn" is assumed.
3324  bool isAssumedWillReturn() const { return getAssumed(); }
3325 
3326  /// Return true if "willreturn" is known.
3327  bool isKnownWillReturn() const { return getKnown(); }
3328 
3329  /// Create an abstract attribute view for the position \p IRP.
3330  static AAWillReturn &createForPosition(const IRPosition &IRP, Attributor &A);
3331 
3332  /// See AbstractAttribute::getName()
3333  const std::string getName() const override { return "AAWillReturn"; }
3334 
3335  /// See AbstractAttribute::getIdAddr()
3336  const char *getIdAddr() const override { return &ID; }
3337 
3338  /// This function should return true if the type of the \p AA is AAWillReturn
3339  static bool classof(const AbstractAttribute *AA) {
3340  return (AA->getIdAddr() == &ID);
3341  }
3342 
3343  /// Unique ID (due to the unique address)
3344  static const char ID;
3345 };
3346 
3347 /// An abstract attribute for undefined behavior.
3349  : public StateWrapper<BooleanState, AbstractAttribute> {
3351  AAUndefinedBehavior(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
3352 
3353  /// Return true if "undefined behavior" is assumed.
3354  bool isAssumedToCauseUB() const { return getAssumed(); }
3355 
3356  /// Return true if "undefined behavior" is assumed for a specific instruction.
3357  virtual bool isAssumedToCauseUB(Instruction *I) const = 0;
3358 
3359  /// Return true if "undefined behavior" is known.
3360  bool isKnownToCauseUB() const { return getKnown(); }
3361 
3362  /// Return true if "undefined behavior" is known for a specific instruction.
3363  virtual bool isKnownToCauseUB(Instruction *I) const = 0;
3364 
3365  /// Create an abstract attribute view for the position \p IRP.
3367  Attributor &A);
3368 
3369  /// See AbstractAttribute::getName()
3370  const std::string getName() const override { return "AAUndefinedBehavior"; }
3371 
3372  /// See AbstractAttribute::getIdAddr()
3373  const char *getIdAddr() const override { return &ID; }
3374 
3375  /// This function should return true if the type of the \p AA is
3376  /// AAUndefineBehavior
3377  static bool classof(const AbstractAttribute *AA) {
3378  return (AA->getIdAddr() == &ID);
3379  }
3380 
3381  /// Unique ID (due to the unique address)
3382  static const char ID;
3383 };
3384 
3385 /// An abstract interface to determine reachability of point A to B.
3386 struct AAReachability : public StateWrapper<BooleanState, AbstractAttribute> {
3388  AAReachability(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
3389 
3390  /// Returns true if 'From' instruction is assumed to reach, 'To' instruction.
3391  /// Users should provide two positions they are interested in, and the class
3392  /// determines (and caches) reachability.
3394  const Instruction &To) const {
3395  if (!getState().isValidState())
3396  return true;
3397  return A.getInfoCache().getPotentiallyReachable(From, To);
3398  }
3399 
3400  /// Returns true if 'From' instruction is known to reach, 'To' instruction.
3401  /// Users should provide two positions they are interested in, and the class
3402  /// determines (and caches) reachability.
3404  const Instruction &To) const {
3405  if (!getState().isValidState())
3406  return false;
3407  return A.getInfoCache().getPotentiallyReachable(From, To);
3408  }
3409 
3410  /// Create an abstract attribute view for the position \p IRP.
3411  static AAReachability &createForPosition(const IRPosition &IRP,
3412  Attributor &A);
3413 
3414  /// See AbstractAttribute::getName()
3415  const std::string getName() const override { return "AAReachability"; }
3416 
3417  /// See AbstractAttribute::getIdAddr()
3418  const char *getIdAddr() const override { return &ID; }
3419 
3420  /// This function should return true if the type of the \p AA is
3421  /// AAReachability
3422  static bool classof(const AbstractAttribute *AA) {
3423  return (AA->getIdAddr() == &ID);
3424  }
3425 
3426  /// Unique ID (due to the unique address)
3427  static const char ID;
3428 };
3429 
3430 /// An abstract interface for all noalias attributes.
3432  : public IRAttribute<Attribute::NoAlias,
3433  StateWrapper<BooleanState, AbstractAttribute>> {
3434  AANoAlias(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3435 
3436  /// Return true if we assume that the underlying value is alias.
3437  bool isAssumedNoAlias() const { return getAssumed(); }
3438 
3439  /// Return true if we know that underlying value is noalias.
3440  bool isKnownNoAlias() const { return getKnown(); }
3441 
3442  /// Create an abstract attribute view for the position \p IRP.
3443  static AANoAlias &createForPosition(const IRPosition &IRP, Attributor &A);
3444 
3445  /// See AbstractAttribute::getName()
3446  const std::string getName() const override { return "AANoAlias"; }
3447 
3448  /// See AbstractAttribute::getIdAddr()
3449  const char *getIdAddr() const override { return &ID; }
3450 
3451  /// This function should return true if the type of the \p AA is AANoAlias
3452  static bool classof(const AbstractAttribute *AA) {
3453  return (AA->getIdAddr() == &ID);
3454  }
3455 
3456  /// Unique ID (due to the unique address)
3457  static const char ID;
3458 };
3459 
3460 /// An AbstractAttribute for nofree.
3461 struct AANoFree
3462  : public IRAttribute<Attribute::NoFree,
3463  StateWrapper<BooleanState, AbstractAttribute>> {
3464  AANoFree(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3465 
3466  /// Return true if "nofree" is assumed.
3467  bool isAssumedNoFree() const { return getAssumed(); }
3468 
3469  /// Return true if "nofree" is known.
3470  bool isKnownNoFree() const { return getKnown(); }
3471 
3472  /// Create an abstract attribute view for the position \p IRP.
3473  static AANoFree &createForPosition(const IRPosition &IRP, Attributor &A);
3474 
3475  /// See AbstractAttribute::getName()
3476  const std::string getName() const override { return "AANoFree"; }
3477 
3478  /// See AbstractAttribute::getIdAddr()
3479  const char *getIdAddr() const override { return &ID; }
3480 
3481  /// This function should return true if the type of the \p AA is AANoFree
3482  static bool classof(const AbstractAttribute *AA) {
3483  return (AA->getIdAddr() == &ID);
3484  }
3485 
3486  /// Unique ID (due to the unique address)
3487  static const char ID;
3488 };
3489 
3490 /// An AbstractAttribute for noreturn.
3492  : public IRAttribute<Attribute::NoReturn,
3493  StateWrapper<BooleanState, AbstractAttribute>> {
3494  AANoReturn(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3495 
3496  /// Return true if the underlying object is assumed to never return.
3497  bool isAssumedNoReturn() const { return getAssumed(); }
3498 
3499  /// Return true if the underlying object is known to never return.
3500  bool isKnownNoReturn() const { return getKnown(); }
3501 
3502  /// Create an abstract attribute view for the position \p IRP.
3503  static AANoReturn &createForPosition(const IRPosition &IRP, Attributor &A);
3504 
3505  /// See AbstractAttribute::getName()
3506  const std::string getName() const override { return "AANoReturn"; }
3507 
3508  /// See AbstractAttribute::getIdAddr()
3509  const char *getIdAddr() const override { return &ID; }
3510 
3511  /// This function should return true if the type of the \p AA is AANoReturn
3512  static bool classof(const AbstractAttribute *AA) {
3513  return (AA->getIdAddr() == &ID);
3514  }
3515 
3516  /// Unique ID (due to the unique address)
3517  static const char ID;
3518 };
3519 
3520 /// An abstract interface for liveness abstract attribute.
3521 struct AAIsDead
3522  : public StateWrapper<BitIntegerState<uint8_t, 3, 0>, AbstractAttribute> {
3524  AAIsDead(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
3525 
3526  /// State encoding bits. A set bit in the state means the property holds.
3527  enum {
3528  HAS_NO_EFFECT = 1 << 0,
3529  IS_REMOVABLE = 1 << 1,
3530 
3532  };
3533  static_assert(IS_DEAD == getBestState(), "Unexpected BEST_STATE value");
3534 
3535 protected:
3536  /// The query functions are protected such that other attributes need to go
3537  /// through the Attributor interfaces: `Attributor::isAssumedDead(...)`
3538 
3539  /// Returns true if the underlying value is assumed dead.
3540  virtual bool isAssumedDead() const = 0;
3541 
3542  /// Returns true if the underlying value is known dead.
3543  virtual bool isKnownDead() const = 0;
3544 
3545  /// Returns true if \p BB is assumed dead.
3546  virtual bool isAssumedDead(const BasicBlock *BB) const = 0;
3547 
3548  /// Returns true if \p BB is known dead.
3549  virtual bool isKnownDead(const BasicBlock *BB) const = 0;
3550 
3551  /// Returns true if \p I is assumed dead.
3552  virtual bool isAssumedDead(const Instruction *I) const = 0;
3553 
3554  /// Returns true if \p I is known dead.
3555  virtual bool isKnownDead(const Instruction *I) const = 0;
3556 
3557  /// Return true if the underlying value is a store that is known to be
3558  /// removable. This is different from dead stores as the removable store
3559  /// can have an effect on live values, especially loads, but that effect
3560  /// is propagated which allows us to remove the store in turn.
3561  virtual bool isRemovableStore() const { return false; }
3562 
3563  /// This method is used to check if at least one instruction in a collection
3564  /// of instructions is live.
3565  template <typename T> bool isLiveInstSet(T begin, T end) const {
3566  for (const auto &I : llvm::make_range(begin, end)) {
3567  assert(I->getFunction() == getIRPosition().getAssociatedFunction() &&
3568  "Instruction must be in the same anchor scope function.");
3569 
3570  if (!isAssumedDead(I))
3571  return true;
3572  }
3573 
3574  return false;
3575  }
3576 
3577 public:
3578  /// Create an abstract attribute view for the position \p IRP.
3579  static AAIsDead &createForPosition(const IRPosition &IRP, Attributor &A);
3580 
3581  /// Determine if \p F might catch asynchronous exceptions.
3583  return F.hasPersonalityFn() && !canSimplifyInvokeNoUnwind(&F);
3584  }
3585 
3586  /// Return if the edge from \p From BB to \p To BB is assumed dead.
3587  /// This is specifically useful in AAReachability.
3588  virtual bool isEdgeDead(const BasicBlock *From, const BasicBlock *To) const {
3589  return false;
3590  }
3591 
3592  /// See AbstractAttribute::getName()
3593  const std::string getName() const override { return "AAIsDead"; }
3594 
3595  /// See AbstractAttribute::getIdAddr()
3596  const char *getIdAddr() const override { return &ID; }
3597 
3598  /// This function should return true if the type of the \p AA is AAIsDead
3599  static bool classof(const AbstractAttribute *AA) {
3600  return (AA->getIdAddr() == &ID);
3601  }
3602 
3603  /// Unique ID (due to the unique address)
3604  static const char ID;
3605 
3606  friend struct Attributor;
3607 };
3608 
3609 /// State for dereferenceable attribute
3611 
3612  static DerefState getBestState() { return DerefState(); }
3613  static DerefState getBestState(const DerefState &) { return getBestState(); }
3614 
3615  /// Return the worst possible representable state.
3617  DerefState DS;
3618  DS.indicatePessimisticFixpoint();
3619  return DS;
3620  }
3622  return getWorstState();
3623  }
3624 
3625  /// State representing for dereferenceable bytes.
3627 
3628  /// Map representing for accessed memory offsets and sizes.
3629  /// A key is Offset and a value is size.
3630  /// If there is a load/store instruction something like,
3631  /// p[offset] = v;
3632  /// (offset, sizeof(v)) will be inserted to this map.
3633  /// std::map is used because we want to iterate keys in ascending order.
3634  std::map<int64_t, uint64_t> AccessedBytesMap;
3635 
3636  /// Helper function to calculate dereferenceable bytes from current known
3637  /// bytes and accessed bytes.
3638  ///
3639  /// int f(int *A){
3640  /// *A = 0;
3641  /// *(A+2) = 2;
3642  /// *(A+1) = 1;
3643  /// *(A+10) = 10;
3644  /// }
3645  /// ```
3646  /// In that case, AccessedBytesMap is `{0:4, 4:4, 8:4, 40:4}`.
3647  /// AccessedBytesMap is std::map so it is iterated in accending order on
3648  /// key(Offset). So KnownBytes will be updated like this:
3649  ///
3650  /// |Access | KnownBytes
3651  /// |(0, 4)| 0 -> 4
3652  /// |(4, 4)| 4 -> 8
3653  /// |(8, 4)| 8 -> 12
3654  /// |(40, 4) | 12 (break)
3655  void computeKnownDerefBytesFromAccessedMap() {
3656  int64_t KnownBytes = DerefBytesState.getKnown();
3657  for (auto &Access : AccessedBytesMap) {
3658  if (KnownBytes < Access.first)
3659  break;
3660  KnownBytes = std::max(KnownBytes, Access.first + (int64_t)Access.second);
3661  }
3662 
3663  DerefBytesState.takeKnownMaximum(KnownBytes);
3664  }
3665 
3666  /// State representing that whether the value is globaly dereferenceable.
3667  BooleanState GlobalState;
3668 
3669  /// See AbstractState::isValidState()
3670  bool isValidState() const override { return DerefBytesState.isValidState(); }
3671 
3672  /// See AbstractState::isAtFixpoint()
3673  bool isAtFixpoint() const override {
3674  return !isValidState() ||
3675  (DerefBytesState.isAtFixpoint() && GlobalState.isAtFixpoint());
3676  }
3677 
3678  /// See AbstractState::indicateOptimisticFixpoint(...)
3681  GlobalState.indicateOptimisticFixpoint();
3682  return ChangeStatus::UNCHANGED;
3683  }
3684 
3685  /// See AbstractState::indicatePessimisticFixpoint(...)
3688  GlobalState.indicatePessimisticFixpoint();
3689  return ChangeStatus::CHANGED;
3690  }
3691 
3692  /// Update known dereferenceable bytes.
3693  void takeKnownDerefBytesMaximum(uint64_t Bytes) {
3695 
3696  // Known bytes might increase.
3697  computeKnownDerefBytesFromAccessedMap();
3698  }
3699 
3700  /// Update assumed dereferenceable bytes.
3701  void takeAssumedDerefBytesMinimum(uint64_t Bytes) {
3703  }
3704 
3705  /// Add accessed bytes to the map.
3706  void addAccessedBytes(int64_t Offset, uint64_t Size) {
3707  uint64_t &AccessedBytes = AccessedBytesMap[Offset];
3708  AccessedBytes = std::max(AccessedBytes, Size);
3709 
3710  // Known bytes might increase.
3711  computeKnownDerefBytesFromAccessedMap();
3712  }
3713 
3714  /// Equality for DerefState.
3715  bool operator==(const DerefState &R) const {
3716  return this->DerefBytesState == R.DerefBytesState &&
3717  this->GlobalState == R.GlobalState;
3718  }
3719 
3720  /// Inequality for DerefState.
3721  bool operator!=(const DerefState &R) const { return !(*this == R); }
3722 
3723  /// See IntegerStateBase::operator^=
3724  DerefState operator^=(const DerefState &R) {
3725  DerefBytesState ^= R.DerefBytesState;
3726  GlobalState ^= R.GlobalState;
3727  return *this;
3728  }
3729 
3730  /// See IntegerStateBase::operator+=
3731  DerefState operator+=(const DerefState &R) {
3732  DerefBytesState += R.DerefBytesState;
3733  GlobalState += R.GlobalState;
3734  return *this;
3735  }
3736 
3737  /// See IntegerStateBase::operator&=
3738  DerefState operator&=(const DerefState &R) {
3739  DerefBytesState &= R.DerefBytesState;
3740  GlobalState &= R.GlobalState;
3741  return *this;
3742  }
3743 
3744  /// See IntegerStateBase::operator|=
3745  DerefState operator|=(const DerefState &R) {
3746  DerefBytesState |= R.DerefBytesState;
3747  GlobalState |= R.GlobalState;
3748  return *this;
3749  }
3750 
3751 protected:
3752  const AANonNull *NonNullAA = nullptr;
3753 };
3754 
3755 /// An abstract interface for all dereferenceable attribute.
3757  : public IRAttribute<Attribute::Dereferenceable,
3758  StateWrapper<DerefState, AbstractAttribute>> {
3760 
3761  /// Return true if we assume that the underlying value is nonnull.
3762  bool isAssumedNonNull() const {
3763  return NonNullAA && NonNullAA->isAssumedNonNull();
3764  }
3765 
3766  /// Return true if we know that the underlying value is nonnull.
3767  bool isKnownNonNull() const {
3768  return NonNullAA && NonNullAA->isKnownNonNull();
3769  }
3770 
3771  /// Return true if we assume that underlying value is
3772  /// dereferenceable(_or_null) globally.
3773  bool isAssumedGlobal() const { return GlobalState.getAssumed(); }
3774 
3775  /// Return true if we know that underlying value is
3776  /// dereferenceable(_or_null) globally.
3777  bool isKnownGlobal() const { return GlobalState.getKnown(); }
3778 
3779  /// Return assumed dereferenceable bytes.
3781  return DerefBytesState.getAssumed();
3782  }
3783 
3784  /// Return known dereferenceable bytes.
3786  return DerefBytesState.getKnown();
3787  }
3788 
3789  /// Create an abstract attribute view for the position \p IRP.
3790  static AADereferenceable &createForPosition(const IRPosition &IRP,
3791  Attributor &A);
3792 
3793  /// See AbstractAttribute::getName()
3794  const std::string getName() const override { return "AADereferenceable"; }
3795 
3796  /// See AbstractAttribute::getIdAddr()
3797  const char *getIdAddr() const override { return &ID; }
3798 
3799  /// This function should return true if the type of the \p AA is
3800  /// AADereferenceable
3801  static bool classof(const AbstractAttribute *AA) {
3802  return (AA->getIdAddr() == &ID);
3803  }
3804 
3805  /// Unique ID (due to the unique address)
3806  static const char ID;
3807 };
3808 
3809 using AAAlignmentStateType =
3811 /// An abstract interface for all align attributes.
3812 struct AAAlign : public IRAttribute<
3813  Attribute::Alignment,
3814  StateWrapper<AAAlignmentStateType, AbstractAttribute>> {
3815  AAAlign(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3816 
3817  /// Return assumed alignment.
3818  Align getAssumedAlign() const { return Align(getAssumed()); }
3819 
3820  /// Return known alignment.
3821  Align getKnownAlign() const { return Align(getKnown()); }
3822 
3823  /// See AbstractAttribute::getName()
3824  const std::string getName() const override { return "AAAlign"; }
3825 
3826  /// See AbstractAttribute::getIdAddr()
3827  const char *getIdAddr() const override { return &ID; }
3828 
3829  /// This function should return true if the type of the \p AA is AAAlign
3830  static bool classof(const AbstractAttribute *AA) {
3831  return (AA->getIdAddr() == &ID);
3832  }
3833 
3834  /// Create an abstract attribute view for the position \p IRP.
3835  static AAAlign &createForPosition(const IRPosition &IRP, Attributor &A);
3836 
3837  /// Unique ID (due to the unique address)
3838  static const char ID;
3839 };
3840 
3841 /// An abstract interface to track if a value leaves it's defining function
3842 /// instance.
3843 /// TODO: We should make it a ternary AA tracking uniqueness, and uniqueness
3844 /// wrt. the Attributor analysis separately.
3845 struct AAInstanceInfo : public StateWrapper<BooleanState, AbstractAttribute> {
3848 
3849  /// Return true if we know that the underlying value is unique in its scope
3850  /// wrt. the Attributor analysis. That means it might not be unique but we can
3851  /// still use pointer equality without risking to represent two instances with
3852  /// one `llvm::Value`.
3853  bool isKnownUniqueForAnalysis() const { return isKnown(); }
3854 
3855  /// Return true if we assume that the underlying value is unique in its scope
3856  /// wrt. the Attributor analysis. That means it might not be unique but we can
3857  /// still use pointer equality without risking to represent two instances with
3858  /// one `llvm::Value`.
3859  bool isAssumedUniqueForAnalysis() const { return isAssumed(); }
3860 
3861  /// Create an abstract attribute view for the position \p IRP.
3862  static AAInstanceInfo &createForPosition(const IRPosition &IRP,
3863  Attributor &A);
3864 
3865  /// See AbstractAttribute::getName()
3866  const std::string getName() const override { return "AAInstanceInfo"; }
3867 
3868  /// See AbstractAttribute::getIdAddr()
3869  const char *getIdAddr() const override { return &ID; }
3870 
3871  /// This function should return true if the type of the \p AA is
3872  /// AAInstanceInfo
3873  static bool classof(const AbstractAttribute *AA) {
3874  return (AA->getIdAddr() == &ID);
3875  }
3876 
3877  /// Unique ID (due to the unique address)
3878  static const char ID;
3879 };
3880 
3881 /// An abstract interface for all nocapture attributes.
3883  : public IRAttribute<
3884  Attribute::NoCapture,
3885  StateWrapper<BitIntegerState<uint16_t, 7, 0>, AbstractAttribute>> {
3886  AANoCapture(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {}
3887 
3888  /// State encoding bits. A set bit in the state means the property holds.
3889  /// NO_CAPTURE is the best possible state, 0 the worst possible state.
3890  enum {
3894 
3895  /// If we do not capture the value in memory or through integers we can only
3896  /// communicate it back as a derived pointer.
3898 
3899  /// If we do not capture the value in memory, through integers, or as a
3900  /// derived pointer we know it is not captured.
3903  };
3904 
3905  /// Return true if we know that the underlying value is not captured in its
3906  /// respective scope.
3907  bool isKnownNoCapture() const { return isKnown(NO_CAPTURE); }
3908 
3909  /// Return true if we assume that the underlying value is not captured in its
3910  /// respective scope.
3911  bool isAssumedNoCapture() const { return isAssumed(NO_CAPTURE); }
3912 
3913  /// Return true if we know that the underlying value is not captured in its
3914  /// respective scope but we allow it to escape through a "return".
3917  }
3918 
3919  /// Return true if we assume that the underlying value is not captured in its
3920  /// respective scope but we allow it to escape through a "return".
3923  }
3924 
3925  /// Create an abstract attribute view for the position \p IRP.
3926  static AANoCapture &createForPosition(const IRPosition &IRP, Attributor &A);
3927 
3928  /// See AbstractAttribute::getName()
3929  const std::string getName() const override { return "AANoCapture"; }
3930 
3931  /// See AbstractAttribute::getIdAddr()
3932  const char *getIdAddr() const override { return &ID; }
3933 
3934  /// This function should return true if the type of the \p AA is AANoCapture
3935  static bool classof(const AbstractAttribute *AA) {
3936  return (AA->getIdAddr() == &ID);
3937  }
3938 
3939  /// Unique ID (due to the unique address)
3940  static const char ID;
3941 };
3942 
3944 
3946 
3948  return ValueSimplifyStateType(Ty);
3949  }
3951  return getBestState(VS.Ty);
3952  }
3953 
3954  /// Return the worst possible representable state.
3957  DS.indicatePessimisticFixpoint();
3958  return DS;
3959  }
3960  static ValueSimplifyStateType
3962  return getWorstState(VS.Ty);
3963  }
3964 
3965  /// See AbstractState::isValidState(...)
3966  bool isValidState() const override { return BS.isValidState(); }
3967 
3968  /// See AbstractState::isAtFixpoint(...)
3969  bool isAtFixpoint() const override { return BS.isAtFixpoint(); }
3970 
3971  /// Return the assumed state encoding.
3973  const ValueSimplifyStateType &getAssumed() const { return *this; }
3974 
3975  /// See AbstractState::indicatePessimisticFixpoint(...)
3978  }
3979 
3980  /// See AbstractState::indicateOptimisticFixpoint(...)
3982  return BS.indicateOptimisticFixpoint();
3983  }
3984 
3985  /// "Clamp" this state with \p PVS.
3987  BS ^= VS.BS;
3988  unionAssumed(VS.SimplifiedAssociatedValue);
3989  return *this;
3990  }
3991 
3993  if (isValidState() != RHS.isValidState())
3994  return false;
3995  if (!isValidState() && !RHS.isValidState())
3996  return true;
3997  return SimplifiedAssociatedValue == RHS.SimplifiedAssociatedValue;
3998  }
3999 
4000 protected:
4001  /// The type of the original value.
4003 
4004  /// Merge \p Other into the currently assumed simplified value
4005  bool unionAssumed(Optional<Value *> Other);
4006 
4007  /// Helper to track validity and fixpoint
4009 
4010  /// An assumed simplified value. Initially, it is set to Optional::None, which
4011  /// means that the value is not clear under current assumption. If in the
4012  /// pessimistic state, getAssumedSimplifiedValue doesn't return this value but
4013  /// returns orignal associated value.
4015 };
4016 
4017 /// An abstract interface for value simplify abstract attribute.
4019  : public StateWrapper<ValueSimplifyStateType, AbstractAttribute, Type *> {
4022  : Base(IRP, IRP.getAssociatedType()) {}
4023 
4024  /// Create an abstract attribute view for the position \p IRP.
4025  static AAValueSimplify &createForPosition(const IRPosition &IRP,
4026  Attributor &A);
4027 
4028  /// See AbstractAttribute::getName()
4029  const std::string getName() const override { return "AAValueSimplify"; }
4030 
4031  /// See AbstractAttribute::getIdAddr()
4032  const char *getIdAddr() const override { return &ID; }
4033 
4034  /// This function should return true if the type of the \p AA is
4035  /// AAValueSimplify
4036  static bool classof(const AbstractAttribute *AA) {
4037  return (AA->getIdAddr() == &ID);
4038  }
4039 
4040  /// Unique ID (due to the unique address)
4041  static const char ID;
4042 
4043 private:
4044  /// Return an assumed simplified value if a single candidate is found. If
4045  /// there cannot be one, return original value. If it is not clear yet, return
4046  /// the Optional::NoneType.
4047  ///
4048  /// Use `Attributor::getAssumedSimplified` for value simplification.
4049  virtual Optional<Value *> getAssumedSimplifiedValue(Attributor &A) const = 0;
4050 
4051  friend struct Attributor;
4052 };
4053 
4054 struct AAHeapToStack : public StateWrapper<BooleanState, AbstractAttribute> {
4056  AAHeapToStack(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
4057 
4058  /// Returns true if HeapToStack conversion is assumed to be possible.
4059  virtual bool isAssumedHeapToStack(const CallBase &CB) const = 0;
4060 
4061  /// Returns true if HeapToStack conversion is assumed and the CB is a
4062  /// callsite to a free operation to be removed.
4063  virtual bool isAssumedHeapToStackRemovedFree(CallBase &CB) const = 0;
4064 
4065  /// Create an abstract attribute view for the position \p IRP.
4066  static AAHeapToStack &createForPosition(const IRPosition &IRP, Attributor &A);
4067 
4068  /// See AbstractAttribute::getName()
4069  const std::string getName() const override { return "AAHeapToStack"; }
4070 
4071  /// See AbstractAttribute::getIdAddr()
4072  const char *getIdAddr() const override { return &ID; }
4073 
4074  /// This function should return true if the type of the \p AA is AAHeapToStack
4075  static bool classof(const AbstractAttribute *AA) {
4076  return (AA->getIdAddr() == &ID);
4077  }
4078 
4079  /// Unique ID (due to the unique address)
4080  static const char ID;
4081 };
4082 
4083 /// An abstract interface for privatizability.
4084 ///
4085 /// A pointer is privatizable if it can be replaced by a new, private one.
4086 /// Privatizing pointer reduces the use count, interaction between unrelated
4087 /// code parts.
4088 ///
4089 /// In order for a pointer to be privatizable its value cannot be observed
4090 /// (=nocapture), it is (for now) not written (=readonly & noalias), we know
4091 /// what values are necessary to make the private copy look like the original
4092 /// one, and the values we need can be loaded (=dereferenceable).
4094  : public StateWrapper<BooleanState, AbstractAttribute> {
4096  AAPrivatizablePtr(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
4097 
4098  /// Returns true if pointer privatization is assumed to be possible.
4099  bool isAssumedPrivatizablePtr() const { return getAssumed(); }
4100 
4101  /// Returns true if pointer privatization is known to be possible.
4102  bool isKnownPrivatizablePtr() const { return getKnown(); }
4103 
4104  /// Return the type we can choose for a private copy of the underlying
4105  /// value. None means it is not clear yet, nullptr means there is none.
4106  virtual Optional<Type *> getPrivatizableType() const = 0;
4107 
4108  /// Create an abstract attribute view for the position \p IRP.
4109  static AAPrivatizablePtr &createForPosition(const IRPosition &IRP,
4110  Attributor &A);
4111 
4112  /// See AbstractAttribute::getName()
4113  const std::string getName() const override { return "AAPrivatizablePtr"; }
4114 
4115  /// See AbstractAttribute::getIdAddr()
4116  const char *getIdAddr() const override { return &ID; }
4117 
4118  /// This function should return true if the type of the \p AA is
4119  /// AAPricatizablePtr
4120  static bool classof(const AbstractAttribute *AA) {
4121  return (AA->getIdAddr() == &ID);
4122  }
4123 
4124  /// Unique ID (due to the unique address)
4125  static const char ID;
4126 };
4127 
4128 /// An abstract interface for memory access kind related attributes
4129 /// (readnone/readonly/writeonly).
4131  : public IRAttribute<
4132  Attribute::ReadNone,
4133  StateWrapper<BitIntegerState<uint8_t, 3>, AbstractAttribute>> {
4135 
4136  /// State encoding bits. A set bit in the state means the property holds.
4137  /// BEST_STATE is the best possible state, 0 the worst possible state.
4138  enum {
4139  NO_READS = 1 << 0,
4140  NO_WRITES = 1 << 1,
4142 
4144  };
4145  static_assert(BEST_STATE == getBestState(), "Unexpected BEST_STATE value");
4146 
4147  /// Return true if we know that the underlying value is not read or accessed
4148  /// in its respective scope.
4149  bool isKnownReadNone() const { return isKnown(NO_ACCESSES); }
4150 
4151  /// Return true if we assume that the underlying value is not read or accessed
4152  /// in its respective scope.
4153  bool isAssumedReadNone() const { return isAssumed(NO_ACCESSES); }
4154 
4155  /// Return true if we know that the underlying value is not accessed
4156  /// (=written) in its respective scope.
4157  bool isKnownReadOnly() const { return isKnown(NO_WRITES); }
4158 
4159  /// Return true if we assume that the underlying value is not accessed
4160  /// (=written) in its respective scope.
4161  bool isAssumedReadOnly() const { return isAssumed(NO_WRITES); }
4162 
4163  /// Return true if we know that the underlying value is not read in its
4164  /// respective scope.
4165  bool isKnownWriteOnly() const { return isKnown(NO_READS); }
4166 
4167  /// Return true if we assume that the underlying value is not read in its
4168  /// respective scope.
4169  bool isAssumedWriteOnly() const { return isAssumed(NO_READS); }
4170 
4171  /// Create an abstract attribute view for the position \p IRP.
4172  static AAMemoryBehavior &createForPosition(const IRPosition &IRP,
4173  Attributor &A);
4174 
4175  /// See AbstractAttribute::getName()
4176  const std::string getName() const override { return "AAMemoryBehavior"; }
4177 
4178  /// See AbstractAttribute::getIdAddr()
4179  const char *getIdAddr() const override { return &ID; }
4180 
4181  /// This function should return true if the type of the \p AA is
4182  /// AAMemoryBehavior
4183  static bool classof(const AbstractAttribute *AA) {
4184  return (AA->getIdAddr() == &ID);
4185  }
4186 
4187  /// Unique ID (due to the unique address)
4188  static const char ID;
4189 };
4190 
4191 /// An abstract interface for all memory location attributes
4192 /// (readnone/argmemonly/inaccessiblememonly/inaccessibleorargmemonly).
4194  : public IRAttribute<
4195  Attribute::ReadNone,
4196  StateWrapper<BitIntegerState<uint32_t, 511>, AbstractAttribute>> {
4197  using MemoryLocationsKind = StateType::base_t;
4198 
4200 
4201  /// Encoding of different locations that could be accessed by a memory
4202  /// access.
4203  enum {
4205  NO_LOCAL_MEM = 1 << 0,
4206  NO_CONST_MEM = 1 << 1,
4213  NO_UNKOWN_MEM = 1 << 7,
4217 
4218  // Helper bit to track if we gave up or not.
4220 
4222  };
4223  static_assert(BEST_STATE == getBestState(), "Unexpected BEST_STATE value");
4224 
4225  /// Return true if we know that the associated functions has no observable
4226  /// accesses.
4227  bool isKnownReadNone() const { return isKnown(NO_LOCATIONS); }
4228 
4229  /// Return true if we assume that the associated functions has no observable
4230  /// accesses.
4231  bool isAssumedReadNone() const {
4233  }
4234 
4235  /// Return true if we know that the associated functions has at most
4236  /// local/stack accesses.
4237  bool isKnowStackOnly() const {
4238  return isKnown(inverseLocation(NO_LOCAL_MEM, true, true));
4239  }
4240 
4241  /// Return true if we assume that the associated functions has at most
4242  /// local/stack accesses.
4243  bool isAssumedStackOnly() const {
4244  return isAssumed(inverseLocation(NO_LOCAL_MEM, true, true));
4245  }
4246 
4247  /// Return true if we know that the underlying value will only access
4248  /// inaccesible memory only (see Attribute::InaccessibleMemOnly).
4250  return isKnown(inverseLocation(NO_INACCESSIBLE_MEM, true, true));
4251  }
4252 
4253  /// Return true if we assume that the underlying value will only access
4254  /// inaccesible memory only (see Attribute::InaccessibleMemOnly).
4256  return isAssumed(inverseLocation(NO_INACCESSIBLE_MEM, true, true));
4257  }
4258 
4259  /// Return true if we know that the underlying value will only access
4260  /// argument pointees (see Attribute::ArgMemOnly).
4261  bool isKnownArgMemOnly() const {
4262  return isKnown(inverseLocation(NO_ARGUMENT_MEM, true, true));
4263  }
4264 
4265  /// Return true if we assume that the underlying value will only access
4266  /// argument pointees (see Attribute::ArgMemOnly).
4267  bool isAssumedArgMemOnly() const {
4268  return isAssumed(inverseLocation(NO_ARGUMENT_MEM, true, true));
4269  }
4270 
4271  /// Return true if we know that the underlying value will only access
4272  /// inaccesible memory or argument pointees (see
4273  /// Attribute::InaccessibleOrArgMemOnly).
4275  return isKnown(
4277  }
4278 
4279  /// Return true if we assume that the underlying value will only access
4280  /// inaccesible memory or argument pointees (see
4281  /// Attribute::InaccessibleOrArgMemOnly).
4283  return isAssumed(
4285  }
4286 
4287  /// Return true if the underlying value may access memory through arguement
4288  /// pointers of the associated function, if any.
4289  bool mayAccessArgMem() const { return !isAssumed(NO_ARGUMENT_MEM); }
4290 
4291  /// Return true if only the memory locations specififed by \p MLK are assumed
4292  /// to be accessed by the associated function.
4294  return isAssumed(MLK);
4295  }
4296 
4297  /// Return the locations that are assumed to be not accessed by the associated
4298  /// function, if any.
4300  return getAssumed();
4301  }
4302 
4303  /// Return the inverse of location \p Loc, thus for NO_XXX the return
4304  /// describes ONLY_XXX. The flags \p AndLocalMem and \p AndConstMem determine
4305  /// if local (=stack) and constant memory are allowed as well. Most of the
4306  /// time we do want them to be included, e.g., argmemonly allows accesses via
4307  /// argument pointers or local or constant memory accesses.
4308  static MemoryLocationsKind
4309  inverseLocation(MemoryLocationsKind Loc, bool AndLocalMem, bool AndConstMem) {
4310  return NO_LOCATIONS & ~(Loc | (AndLocalMem ? NO_LOCAL_MEM : 0) |
4311  (AndConstMem ? NO_CONST_MEM : 0));
4312  };
4313 
4314  /// Return the locations encoded by \p MLK as a readable string.
4315  static std::string getMemoryLocationsAsStr(MemoryLocationsKind MLK);
4316 
4317  /// Simple enum to distinguish read/write/read-write accesses.
4318  enum AccessKind {
4319  NONE = 0,
4320  READ = 1 << 0,
4321  WRITE = 1 << 1,
4323  };
4324 
4325  /// Check \p Pred on all accesses to the memory kinds specified by \p MLK.
4326  ///
4327  /// This method will evaluate \p Pred on all accesses (access instruction +
4328  /// underlying accessed memory pointer) and it will return true if \p Pred
4329  /// holds every time.
4330  virtual bool checkForAllAccessesToMemoryKind(
4331  function_ref<bool(const Instruction *, const Value *, AccessKind,
4333  Pred,
4334  MemoryLocationsKind MLK) const = 0;
4335 
4336  /// Create an abstract attribute view for the position \p IRP.
4337  static AAMemoryLocation &createForPosition(const IRPosition &IRP,
4338  Attributor &A);
4339 
4340  /// See AbstractState::getAsStr().
4341  const std::string getAsStr() const override {
4343  }
4344 
4345  /// See AbstractAttribute::getName()
4346  const std::string getName() const override { return "AAMemoryLocation"; }
4347 
4348  /// See AbstractAttribute::getIdAddr()
4349  const char *getIdAddr() const override { return &ID; }
4350 
4351  /// This function should return true if the type of the \p AA is
4352  /// AAMemoryLocation
4353  static bool classof(const AbstractAttribute *AA) {
4354  return (AA->getIdAddr() == &ID);
4355  }
4356 
4357  /// Unique ID (due to the unique address)
4358  static const char ID;
4359 };
4360 
4361 /// An abstract interface for range value analysis.
4363  : public StateWrapper<IntegerRangeState, AbstractAttribute, uint32_t> {
4366  : Base(IRP, IRP.getAssociatedType()->getIntegerBitWidth()) {}
4367 
4368  /// See AbstractAttribute::getState(...).
4369  IntegerRangeState &getState() override { return *this; }
4370  const IntegerRangeState &getState() const override { return *this; }
4371 
4372  /// Create an abstract attribute view for the position \p IRP.
4374  Attributor &A);
4375 
4376  /// Return an assumed range for the associated value a program point \p CtxI.
4377  /// If \p I is nullptr, simply return an assumed range.
4378  virtual ConstantRange
4380  const Instruction *CtxI = nullptr) const = 0;
4381 
4382  /// Return a known range for the associated value at a program point \p CtxI.
4383  /// If \p I is nullptr, simply return a known range.
4384  virtual ConstantRange
4386  const Instruction *CtxI = nullptr) const = 0;
4387 
4388  /// Return an assumed constant for the associated value a program point \p
4389  /// CtxI.
4391  getAssumedConstant(Attributor &A, const Instruction *CtxI = nullptr) const {
4392  ConstantRange RangeV = getAssumedConstantRange(A, CtxI);
4393  if (auto *C = RangeV.getSingleElement()) {
4394  Type *Ty = getAssociatedValue().getType();
4395  return cast_or_null<Constant>(
4396  AA::getWithType(*ConstantInt::get(Ty->getContext(), *C), *Ty));
4397  }
4398  if (RangeV.isEmptySet())
4399  return llvm::None;
4400  return nullptr;
4401  }
4402 
4403  /// See AbstractAttribute::getName()
4404  const std::string getName() const override { return "AAValueConstantRange"; }
4405 
4406  /// See AbstractAttribute::getIdAddr()
4407  const char *getIdAddr() const override { return &ID; }
4408 
4409  /// This function should return true if the type of the \p AA is
4410  /// AAValueConstantRange
4411  static bool classof(const AbstractAttribute *AA) {
4412  return (AA->getIdAddr() == &ID);
4413  }
4414 
4415  /// Unique ID (due to the unique address)
4416  static const char ID;
4417 };
4418 
4419 /// A class for a set state.
4420 /// The assumed boolean state indicates whether the corresponding set is full
4421 /// set or not. If the assumed state is false, this is the worst state. The
4422 /// worst state (invalid state) of set of potential values is when the set
4423 /// contains every possible value (i.e. we cannot in any way limit the value
4424 /// that the target position can take). That never happens naturally, we only
4425 /// force it. As for the conditions under which we force it, see
4426 /// AAPotentialConstantValues.
4427 template <typename MemberTy> struct PotentialValuesState : AbstractState {
4429 
4430  PotentialValuesState() : IsValidState(true), UndefIsContained(false) {}
4431 
4432  PotentialValuesState(bool IsValid)
4433  : IsValidState(IsValid), UndefIsContained(false) {}
4434 
4435  /// See AbstractState::isValidState(...)
4436  bool isValidState() const override { return IsValidState.isValidState(); }
4437 
4438  /// See AbstractState::isAtFixpoint(...)
4439  bool isAtFixpoint() const override { return IsValidState.isAtFixpoint(); }
4440 
4441  /// See AbstractState::indicatePessimisticFixpoint(...)
4443  return IsValidState.indicatePessimisticFixpoint();
4444  }
4445 
4446  /// See AbstractState::indicateOptimisticFixpoint(...)
4448  return IsValidState.indicateOptimisticFixpoint();
4449  }
4450 
4451  /// Return the assumed state
4452  PotentialValuesState &getAssumed() { return *this; }
4453  const PotentialValuesState &getAssumed() const { return *this; }
4454 
4455  /// Return this set. We should check whether this set is valid or not by
4456  /// isValidState() before calling this function.
4457  const SetTy &getAssumedSet() const {
4458  assert(isValidState() && "This set shoud not be used when it is invalid!");
4459  return Set;
4460  }
4461 
4462  /// Returns whether this state contains an undef value or not.
4463  bool undefIsContained() const {
4464  assert(isValidState() && "This flag shoud not be used when it is invalid!");
4465  return UndefIsContained;
4466  }
4467 
4468  bool operator==(const PotentialValuesState &RHS) const {
4469  if (isValidState() != RHS.isValidState())
4470  return false;
4471  if (!isValidState() && !RHS.isValidState())
4472  return true;
4473  if (undefIsContained() != RHS.undefIsContained())
4474  return false;
4475  return Set == RHS.getAssumedSet();
4476  }
4477 
4478  /// Maximum number of potential values to be tracked.
4479  /// This is set by -attributor-max-potential-values command line option
4480  static unsigned MaxPotentialValues;
4481 
4482  /// Return empty set as the best state of potential values.
4484  return PotentialValuesState(true);
4485  }
4486 
4488  return getBestState();
4489  }
4490 
4491  /// Return full set as the worst state of potential values.
4493  return PotentialValuesState(false);
4494  }
4495 
4496  /// Union assumed set with the passed value.
4497  void unionAssumed(const MemberTy &C) { insert(C); }
4498 
4499  /// Union assumed set with assumed set of the passed state \p PVS.
4500  void unionAssumed(const PotentialValuesState &PVS) { unionWith(PVS); }
4501 
4502  /// Union assumed set with an undef value.
4503  void unionAssumedWithUndef() { unionWithUndef(); }
4504 
4505  /// "Clamp" this state with \p PVS.
4507  IsValidState ^= PVS.IsValidState;
4508  unionAssumed(PVS);
4509  return *this;
4510  }
4511 
4513  IsValidState &= PVS.IsValidState;
4514  unionAssumed(PVS);
4515  return *this;
4516  }
4517 
4518  bool contains(const MemberTy &V) const {
4519  return !isValidState() ? true : Set.contains(V);
4520  }
4521 
4522 protected:
4524  assert(isValidState() && "This set shoud not be used when it is invalid!");
4525  return Set;
4526  }
4527 
4528 private:
4529  /// Check the size of this set, and invalidate when the size is no
4530  /// less than \p MaxPotentialValues threshold.
4531  void checkAndInvalidate() {
4532  if (Set.size() >= MaxPotentialValues)
4534  else
4535  reduceUndefValue();
4536  }
4537 
4538  /// If this state contains both undef and not undef, we can reduce
4539  /// undef to the not undef value.
4540  void reduceUndefValue() { UndefIsContained = UndefIsContained & Set.empty(); }
4541 
4542  /// Insert an element into this set.
4543  void insert(const MemberTy &C) {
4544  if (!isValidState())
4545  return;
4546  Set.insert(C);
4547  checkAndInvalidate();
4548  }
4549 
4550  /// Take union with R.
4551  void unionWith(const PotentialValuesState &R) {
4552  /// If this is a full set, do nothing.
4553  if (!isValidState())
4554  return;
4555  /// If R is full set, change L to a full set.
4556  if (!R.isValidState()) {
4558  return;
4559  }
4560  for (const MemberTy &C : R.Set)
4561  Set.insert(C);
4562  UndefIsContained |= R.undefIsContained();
4563  checkAndInvalidate();
4564  }
4565 
4566  /// Take union with an undef value.
4567  void unionWithUndef() {
4568  UndefIsContained = true;
4569  reduceUndefValue();
4570  }
4571 
4572  /// Take intersection with R.
4573  void intersectWith(const PotentialValuesState &R) {
4574  /// If R is a full set, do nothing.
4575  if (!R.isValidState())
4576  return;
4577  /// If this is a full set, change this to R.
4578  if (!isValidState()) {
4579  *this = R;
4580  return;
4581  }
4582  SetTy IntersectSet;
4583  for (const MemberTy &C : Set) {
4584  if (R.Set.count(C))
4585  IntersectSet.insert(C);
4586  }
4587  Set = IntersectSet;
4588  UndefIsContained &= R.undefIsContained();
4589  reduceUndefValue();
4590  }
4591 
4592  /// A helper state which indicate whether this state is valid or not.
4593  BooleanState IsValidState;
4594 
4595  /// Container for potential values
4596  SetTy Set;
4597 
4598  /// Flag for undef value
4599  bool UndefIsContained;
4600 };
4601 
4605 
4609 
4610 /// An abstract interface for potential values analysis.
4611 ///
4612 /// This AA collects potential values for each IR position.
4613 /// An assumed set of potential values is initialized with the empty set (the
4614 /// best state) and it will grow monotonically as we find more potential values
4615 /// for this position.
4616 /// The set might be forced to the worst state, that is, to contain every
4617 /// possible value for this position in 2 cases.
4618 /// 1. We surpassed the \p MaxPotentialValues threshold. This includes the
4619 /// case that this position is affected (e.g. because of an operation) by a
4620 /// Value that is in the worst state.
4621 /// 2. We tried to initialize on a Value that we cannot handle (e.g. an
4622 /// operator we do not currently handle).
4623 ///
4624 /// For non constant integers see AAPotentialValues.
4626  : public StateWrapper<PotentialConstantIntValuesState, AbstractAttribute> {
4629 
4630  /// See AbstractAttribute::getState(...).
4631  PotentialConstantIntValuesState &getState() override { return *this; }
4632  const PotentialConstantIntValuesState &getState() const override {
4633  return *this;
4634  }
4635 
4636  /// Create an abstract attribute view for the position \p IRP.
4638  Attributor &A);
4639 
4640  /// Return assumed constant for the associated value
4642  getAssumedConstant(Attributor &A, const Instruction *CtxI = nullptr) const {
4643  if (!isValidState())
4644  return nullptr;