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