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