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