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