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