LLVM  9.0.0svn
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 reevaluated 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 LLVM-IR attribute already in the AbstractAttribute base
64 // class. In the simplest case, a subclass overloads
65 // `AbstractAttribute::getManifestPosition()` and
66 // `AbstractAttribute::getAttrKind()` to return the appropriate values. The
67 // Attributor manifestation framework will then create and place a new attribute
68 // if it is allowed to do so (based on the abstract state). Other use cases can
69 // be achieved by overloading other abstract attribute methods.
70 //
71 //
72 // The "mechanics" of adding a new "abstract attribute":
73 // - Define a class (transitively) inheriting from AbstractAttribute and one
74 // (which could be the same) that (transitively) inherits from AbstractState.
75 // For the latter, consider the already available BooleanState and
76 // IntegerState if they fit your needs, e.g., you require only a 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 
101 #include "llvm/IR/CallSite.h"
102 #include "llvm/IR/PassManager.h"
103 
104 namespace llvm {
105 
106 struct AbstractAttribute;
107 struct InformationCache;
108 
109 class Function;
110 
111 /// Simple enum class that forces the status to be spelled out explicitly.
112 ///
113 ///{
114 enum class ChangeStatus {
115  CHANGED,
116  UNCHANGED,
117 };
118 
121 ///}
122 
123 /// The fixpoint analysis framework that orchestrates the attribute deduction.
124 ///
125 /// The Attributor provides a general abstract analysis framework (guided
126 /// fixpoint iteration) as well as helper functions for the deduction of
127 /// (LLVM-IR) attributes. However, also other code properties can be deduced,
128 /// propagated, and ultimately manifested through the Attributor framework. This
129 /// is particularly useful if these properties interact with attributes and a
130 /// co-scheduled deduction allows to improve the solution. Even if not, thus if
131 /// attributes/properties are completely isolated, they should use the
132 /// Attributor framework to reduce the number of fixpoint iteration frameworks
133 /// in the code base. Note that the Attributor design makes sure that isolated
134 /// attributes are not impacted, in any way, by others derived at the same time
135 /// if there is no cross-reasoning performed.
136 ///
137 /// The public facing interface of the Attributor is kept simple and basically
138 /// allows abstract attributes to one thing, query abstract attributes
139 /// in-flight. There are two reasons to do this:
140 /// a) The optimistic state of one abstract attribute can justify an
141 /// optimistic state of another, allowing to framework to end up with an
142 /// optimistic (=best possible) fixpoint instead of one based solely on
143 /// information in the IR.
144 /// b) This avoids reimplementing various kinds of lookups, e.g., to check
145 /// for existing IR attributes, in favor of a single lookups interface
146 /// provided by an abstract attribute subclass.
147 ///
148 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
149 /// described in the file comment.
150 struct Attributor {
151  ~Attributor() { DeleteContainerPointers(AllAbstractAttributes); }
152 
153  /// Run the analyses until a fixpoint is reached or enforced (timeout).
154  ///
155  /// The attributes registered with this Attributor can be used after as long
156  /// as the Attributor is not destroyed (it owns the attributes now).
157  ///
158  /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED.
159  ChangeStatus run();
160 
161  /// Lookup an abstract attribute of type \p AAType anchored at value \p V and
162  /// argument number \p ArgNo. If no attribute is found and \p V is a call base
163  /// instruction, the called function is tried as a value next. Thus, the
164  /// returned abstract attribute might be anchored at the callee of \p V.
165  ///
166  /// This method is the only (supported) way an abstract attribute can retrieve
167  /// information from another abstract attribute. As an example, take an
168  /// abstract attribute that determines the memory access behavior for a
169  /// argument (readnone, readonly, ...). It should use `getAAFor` to get the
170  /// most optimistic information for other abstract attributes in-flight, e.g.
171  /// the one reasoning about the "captured" state for the argument or the one
172  /// reasoning on the memory access behavior of the function as a whole.
173  template <typename AAType>
174  const AAType *getAAFor(AbstractAttribute &QueryingAA, const Value &V,
175  int ArgNo = -1) {
176  static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
177  "Cannot query an attribute with a type not derived from "
178  "'AbstractAttribute'!");
180  "Cannot lookup generic abstract attributes!");
181 
182  // Determine the argument number automatically for llvm::Arguments if none
183  // is set. Do not override a given one as it could be a use of the argument
184  // in a call site.
185  if (ArgNo == -1)
186  if (auto *Arg = dyn_cast<Argument>(&V))
187  ArgNo = Arg->getArgNo();
188 
189  // If a function was given together with an argument number, perform the
190  // lookup for the actual argument instead. Don't do it for variadic
191  // arguments.
192  if (ArgNo >= 0 && isa<Function>(&V) &&
193  cast<Function>(&V)->arg_size() > (size_t)ArgNo)
194  return getAAFor<AAType>(
195  QueryingAA, *(cast<Function>(&V)->arg_begin() + ArgNo), ArgNo);
196 
197  // Lookup the abstract attribute of type AAType. If found, return it after
198  // registering a dependence of QueryingAA on the one returned attribute.
199  const auto &KindToAbstractAttributeMap = AAMap.lookup({&V, ArgNo});
200  if (AAType *AA = static_cast<AAType *>(
202  // Do not return an attribute with an invalid state. This minimizes checks
203  // at the calls sites and allows the fallback below to kick in.
204  if (AA->getState().isValidState()) {
205  QueryMap[AA].insert(&QueryingAA);
206  return AA;
207  }
208  }
209 
210  // If no abstract attribute was found and we look for a call site argument,
211  // defer to the actual argument instead.
212  ImmutableCallSite ICS(&V);
213  if (ICS && ICS.getCalledValue())
214  return getAAFor<AAType>(QueryingAA, *ICS.getCalledValue(), ArgNo);
215 
216  // No matching attribute found
217  return nullptr;
218  }
219 
220  /// Introduce a new abstract attribute into the fixpoint analysis.
221  ///
222  /// Note that ownership of the attribute is given to the Attributor. It will
223  /// invoke delete for the Attributor on destruction of the Attributor.
224  ///
225  /// Attributes are identified by
226  /// (1) their anchored value (see AA.getAnchoredValue()),
227  /// (2) their argument number (\p ArgNo, or Argument::getArgNo()), and
228  /// (3) their default attribute kind (see AAType::ID).
229  template <typename AAType> AAType &registerAA(AAType &AA, int ArgNo = -1) {
230  static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
231  "Cannot register an attribute with a type not derived from "
232  "'AbstractAttribute'!");
233 
234  // Determine the anchor value and the argument number which are used to
235  // lookup the attribute together with AAType::ID. If passed an argument,
236  // use its argument number but do not override a given one as it could be a
237  // use of the argument at a call site.
238  Value &AnchoredVal = AA.getAnchoredValue();
239  if (ArgNo == -1)
240  if (auto *Arg = dyn_cast<Argument>(&AnchoredVal))
241  ArgNo = Arg->getArgNo();
242 
243  // Put the attribute in the lookup map structure and the container we use to
244  // keep track of all attributes.
245  AAMap[{&AnchoredVal, ArgNo}][AAType::ID] = &AA;
246  AllAbstractAttributes.push_back(&AA);
247  return AA;
248  }
249 
250  /// Determine opportunities to derive 'default' attributes in \p F and create
251  /// abstract attribute objects for them.
252  ///
253  /// \param F The function that is checked for attribute opportunities.
254  /// \param InfoCache A cache for information queryable by the new attributes.
255  /// \param Whitelist If not null, a set limiting the attribute opportunities.
256  ///
257  /// Note that abstract attribute instances are generally created even if the
258  /// IR already contains the information they would deduce. The most important
259  /// reason for this is the single interface, the one of the abstract attribute
260  /// instance, which can be queried without the need to look at the IR in
261  /// various places.
262  void identifyDefaultAbstractAttributes(
263  Function &F, InformationCache &InfoCache,
264  DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist = nullptr);
265 
266  /// Check \p Pred on all function call sites.
267  ///
268  /// This method will evaluate \p Pred on call sites and return
269  /// true if \p Pred holds in every call sites. However, this is only possible
270  /// all call sites are known, hence the function has internal linkage.
271  bool checkForAllCallSites(Function &F, std::function<bool(CallSite)> &Pred,
272  bool RequireAllCallSites);
273 
274 private:
275  /// The set of all abstract attributes.
276  ///{
278  AAVector AllAbstractAttributes;
279  ///}
280 
281  /// A nested map to lookup abstract attributes based on the anchored value and
282  /// an argument positions (or -1) on the outer level, and attribute kinds
283  /// (Attribute::AttrKind) on the inner level.
284  ///{
287  ///}
288 
289  /// A map from abstract attributes to the ones that queried them through calls
290  /// to the getAAFor<...>(...) method.
291  ///{
292  using QueryMapTy =
294  QueryMapTy QueryMap;
295  ///}
296 };
297 
298 /// Data structure to hold cached (LLVM-IR) information.
299 ///
300 /// All attributes are given an InformationCache object at creation time to
301 /// avoid inspection of the IR by all of them individually. This default
302 /// InformationCache will hold information required by 'default' attributes,
303 /// thus the ones deduced when Attributor::identifyDefaultAbstractAttributes(..)
304 /// is called.
305 ///
306 /// If custom abstract attributes, registered manually through
307 /// Attributor::registerAA(...), need more information, especially if it is not
308 /// reusable, it is advised to inherit from the InformationCache and cast the
309 /// instance down in the abstract attributes.
311  /// A map type from opcodes to instructions with this opcode.
313 
314  /// Return the map that relates "interesting" opcodes with all instructions
315  /// with that opcode in \p F.
317  return FuncInstOpcodeMap[&F];
318  }
319 
320  /// A vector type to hold instructions.
321  using InstructionVectorTy = std::vector<Instruction *>;
322 
323  /// Return the instructions in \p F that may read or write memory.
325  return FuncRWInstsMap[&F];
326  }
327 
328 private:
329  /// A map type from functions to opcode to instruction maps.
331 
332  /// A map type from functions to their read or write instructions.
334 
335  /// A nested map that remembers all instructions in a function with a certain
336  /// instruction opcode (Instruction::getOpcode()).
337  FuncInstOpcodeMapTy FuncInstOpcodeMap;
338 
339  /// A map from functions to their instructions that may read or write memory.
340  FuncRWInstsMapTy FuncRWInstsMap;
341 
342  /// Give the Attributor access to the members so
343  /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them.
344  friend struct Attributor;
345 };
346 
347 /// An interface to query the internal state of an abstract attribute.
348 ///
349 /// The abstract state is a minimal interface that allows the Attributor to
350 /// communicate with the abstract attributes about their internal state without
351 /// enforcing or exposing implementation details, e.g., the (existence of an)
352 /// underlying lattice.
353 ///
354 /// It is sufficient to be able to query if a state is (1) valid or invalid, (2)
355 /// at a fixpoint, and to indicate to the state that (3) an optimistic fixpoint
356 /// was reached or (4) a pessimistic fixpoint was enforced.
357 ///
358 /// All methods need to be implemented by the subclass. For the common use case,
359 /// a single boolean state or a bit-encoded state, the BooleanState and
360 /// IntegerState classes are already provided. An abstract attribute can inherit
361 /// from them to get the abstract state interface and additional methods to
362 /// directly modify the state based if needed. See the class comments for help.
364  virtual ~AbstractState() {}
365 
366  /// Return if this abstract state is in a valid state. If false, no
367  /// information provided should be used.
368  virtual bool isValidState() const = 0;
369 
370  /// Return if this abstract state is fixed, thus does not need to be updated
371  /// if information changes as it cannot change itself.
372  virtual bool isAtFixpoint() const = 0;
373 
374  /// Indicate that the abstract state should converge to the optimistic state.
375  ///
376  /// This will usually make the optimistically assumed state the known to be
377  /// true state.
378  virtual void indicateOptimisticFixpoint() = 0;
379 
380  /// Indicate that the abstract state should converge to the pessimistic state.
381  ///
382  /// This will usually revert the optimistically assumed state to the known to
383  /// be true state.
384  virtual void indicatePessimisticFixpoint() = 0;
385 };
386 
387 /// Simple state with integers encoding.
388 ///
389 /// The interface ensures that the assumed bits are always a subset of the known
390 /// bits. Users can only add known bits and, except through adding known bits,
391 /// they can only remove assumed bits. This should guarantee monotoniticy and
392 /// thereby the existence of a fixpoint (if used corretly). The fixpoint is
393 /// reached when the assumed and known state/bits are equal. Users can
394 /// force/inidicate a fixpoint. If an optimistic one is indicated, the known
395 /// state will catch up with the assumed one, for a pessimistic fixpoint it is
396 /// the other way around.
397 struct IntegerState : public AbstractState {
398  /// Underlying integer type, we assume 32 bits to be enough.
399  using base_t = uint32_t;
400 
401  /// Initialize the (best) state.
402  IntegerState(base_t BestState = ~0) : Assumed(BestState) {}
403 
404  /// Return the worst possible representable state.
405  static constexpr base_t getWorstState() { return 0; }
406 
407  /// See AbstractState::isValidState()
408  /// NOTE: For now we simply pretend that the worst possible state is invalid.
409  bool isValidState() const override { return Assumed != getWorstState(); }
410 
411  /// See AbstractState::isAtFixpoint()
412  bool isAtFixpoint() const override { return Assumed == Known; }
413 
414  /// See AbstractState::indicateOptimisticFixpoint(...)
415  void indicateOptimisticFixpoint() override { Known = Assumed; }
416 
417  /// See AbstractState::indicatePessimisticFixpoint(...)
418  void indicatePessimisticFixpoint() override { Assumed = Known; }
419 
420  /// Return the known state encoding
421  base_t getKnown() const { return Known; }
422 
423  /// Return the assumed state encoding.
424  base_t getAssumed() const { return Assumed; }
425 
426  /// Return true if the bits set in \p BitsEncoding are "known bits".
427  bool isKnown(base_t BitsEncoding) const {
428  return (Known & BitsEncoding) == BitsEncoding;
429  }
430 
431  /// Return true if the bits set in \p BitsEncoding are "assumed bits".
432  bool isAssumed(base_t BitsEncoding) const {
433  return (Assumed & BitsEncoding) == BitsEncoding;
434  }
435 
436  /// Add the bits in \p BitsEncoding to the "known bits".
438  // Make sure we never miss any "known bits".
439  Assumed |= Bits;
440  Known |= Bits;
441  return *this;
442  }
443 
444  /// Remove the bits in \p BitsEncoding from the "assumed bits" if not known.
446  // Make sure we never loose any "known bits".
447  Assumed = (Assumed & ~BitsEncoding) | Known;
448  return *this;
449  }
450 
451  /// Keep only "assumed bits" also set in \p BitsEncoding but all known ones.
453  // Make sure we never loose any "known bits".
454  Assumed = (Assumed & BitsEncoding) | Known;
455  return *this;
456  }
457 
458 private:
459  /// The known state encoding in an integer of type base_t.
460  base_t Known = getWorstState();
461 
462  /// The assumed state encoding in an integer of type base_t.
463  base_t Assumed;
464 };
465 
466 /// Simple wrapper for a single bit (boolean) state.
467 struct BooleanState : public IntegerState {
469 };
470 
471 /// Base struct for all "concrete attribute" deductions.
472 ///
473 /// The abstract attribute is a minimal interface that allows the Attributor to
474 /// orchestrate the abstract/fixpoint analysis. The design allows to hide away
475 /// implementation choices made for the subclasses but also to structure their
476 /// implementation and simplify the use of other abstract attributes in-flight.
477 ///
478 /// To allow easy creation of new attributes, most methods have default
479 /// implementations. The ones that do not are generally straight forward, except
480 /// `AbstractAttribute::updateImpl` which is the location of most reasoning
481 /// associated with the abstract attribute. The update is invoked by the
482 /// Attributor in case the situation used to justify the current optimistic
483 /// state might have changed. The Attributor determines this automatically
484 /// by monitoring the `Attributor::getAAFor` calls made by abstract attributes.
485 ///
486 /// The `updateImpl` method should inspect the IR and other abstract attributes
487 /// in-flight to justify the best possible (=optimistic) state. The actual
488 /// implementation is, similar to the underlying abstract state encoding, not
489 /// exposed. In the most common case, the `updateImpl` will go through a list of
490 /// reasons why its optimistic state is valid given the current information. If
491 /// any combination of them holds and is sufficient to justify the current
492 /// optimistic state, the method shall return UNCHAGED. If not, the optimistic
493 /// state is adjusted to the situation and the method shall return CHANGED.
494 ///
495 /// If the manifestation of the "concrete attribute" deduced by the subclass
496 /// differs from the "default" behavior, which is a (set of) LLVM-IR
497 /// attribute(s) for an argument, call site argument, function return value, or
498 /// function, the `AbstractAttribute::manifest` method should be overloaded.
499 ///
500 /// NOTE: If the state obtained via getState() is INVALID, thus if
501 /// AbstractAttribute::getState().isValidState() returns false, no
502 /// information provided by the methods of this class should be used.
503 /// NOTE: The Attributor currently has certain limitations to what we can do.
504 /// As a general rule of thumb, "concrete" abstract attributes should *for
505 /// now* only perform "backward" information propagation. That means
506 /// optimistic information obtained through abstract attributes should
507 /// only be used at positions that precede the origin of the information
508 /// with regards to the program flow. More practically, information can
509 /// *now* be propagated from instructions to their enclosing function, but
510 /// *not* from call sites to the called function. The mechanisms to allow
511 /// both directions will be added in the future.
512 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
513 /// described in the file comment.
515 
516  /// The positions attributes can be manifested in.
518  MP_ARGUMENT, ///< An attribute for a function argument.
519  MP_CALL_SITE_ARGUMENT, ///< An attribute for a call site argument.
520  MP_FUNCTION, ///< An attribute for a function as a whole.
521  MP_RETURNED, ///< An attribute for the function return value.
522  };
523 
524  /// An abstract attribute associated with \p AssociatedVal and anchored at
525  /// \p AnchoredVal.
526  ///
527  /// \param AssociatedVal The value this abstract attribute is associated with.
528  /// \param AnchoredVal The value this abstract attributes is anchored at.
529  /// \param InfoCache Cached information accessible to the abstract attribute.
530  AbstractAttribute(Value *AssociatedVal, Value &AnchoredVal,
531  InformationCache &InfoCache)
532  : AssociatedVal(AssociatedVal), AnchoredVal(AnchoredVal),
533  InfoCache(InfoCache) {}
534 
535  /// An abstract attribute associated with and anchored at \p V.
537  : AbstractAttribute(&V, V, InfoCache) {}
538 
539  /// Virtual destructor.
540  virtual ~AbstractAttribute() {}
541 
542  /// Initialize the state with the information in the Attributor \p A.
543  ///
544  /// This function is called by the Attributor once all abstract attributes
545  /// have been identified. It can and shall be used for task like:
546  /// - identify existing knowledge in the IR and use it for the "known state"
547  /// - perform any work that is not going to change over time, e.g., determine
548  /// a subset of the IR, or attributes in-flight, that have to be looked at
549  /// in the `updateImpl` method.
550  virtual void initialize(Attributor &A) {}
551 
552  /// Return the internal abstract state for inspection.
553  virtual const AbstractState &getState() const = 0;
554 
555  /// Return the value this abstract attribute is anchored with.
556  ///
557  /// The anchored value might not be the associated value if the latter is not
558  /// sufficient to determine where arguments will be manifested. This is mostly
559  /// the case for call site arguments as the value is not sufficient to
560  /// pinpoint them. Instead, we can use the call site as an anchor.
561  ///
562  ///{
563  Value &getAnchoredValue() { return AnchoredVal; }
564  const Value &getAnchoredValue() const { return AnchoredVal; }
565  ///}
566 
567  /// Return the llvm::Function surrounding the anchored value.
568  ///
569  ///{
570  Function &getAnchorScope();
571  const Function &getAnchorScope() const;
572  ///}
573 
574  /// Return the value this abstract attribute is associated with.
575  ///
576  /// The abstract state usually represents this value.
577  ///
578  ///{
579  virtual Value *getAssociatedValue() { return AssociatedVal; }
580  virtual const Value *getAssociatedValue() const { return AssociatedVal; }
581  ///}
582 
583  /// Return the position this abstract state is manifested in.
584  virtual ManifestPosition getManifestPosition() const = 0;
585 
586  /// Return the kind that identifies the abstract attribute implementation.
587  virtual Attribute::AttrKind getAttrKind() const = 0;
588 
589  /// Return the deduced attributes in \p Attrs.
591  LLVMContext &Ctx = AnchoredVal.getContext();
592  Attrs.emplace_back(Attribute::get(Ctx, getAttrKind()));
593  }
594 
595  /// Helper functions, for debug purposes only.
596  ///{
597  virtual void print(raw_ostream &OS) const;
598  void dump() const { print(dbgs()); }
599 
600  /// This function should return the "summarized" assumed state as string.
601  virtual const std::string getAsStr() const = 0;
602  ///}
603 
604  /// Allow the Attributor access to the protected methods.
605  friend struct Attributor;
606 
607 protected:
608  /// Hook for the Attributor to trigger an update of the internal state.
609  ///
610  /// If this attribute is already fixed, this method will return UNCHANGED,
611  /// otherwise it delegates to `AbstractAttribute::updateImpl`.
612  ///
613  /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
614  ChangeStatus update(Attributor &A);
615 
616  /// Hook for the Attributor to trigger the manifestation of the information
617  /// represented by the abstract attribute in the LLVM-IR.
618  ///
619  /// \Return CHANGED if the IR was altered, otherwise UNCHANGED.
620  virtual ChangeStatus manifest(Attributor &A);
621 
622  /// Return the internal abstract state for careful modification.
623  virtual AbstractState &getState() = 0;
624 
625  /// The actual update/transfer function which has to be implemented by the
626  /// derived classes.
627  ///
628  /// If it is called, the environment has changed and we have to determine if
629  /// the current information is still valid or adjust it otherwise.
630  ///
631  /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
632  virtual ChangeStatus updateImpl(Attributor &A) = 0;
633 
634  /// The value this abstract attribute is associated with.
636 
637  /// The value this abstract attribute is anchored at.
639 
640  /// The information cache accessible to this abstract attribute.
642 };
643 
644 /// Forward declarations of output streams for debug purposes.
645 ///
646 ///{
650 raw_ostream &operator<<(raw_ostream &OS, const AbstractState &State);
651 ///}
652 
653 struct AttributorPass : public PassInfoMixin<AttributorPass> {
655 };
656 
658 
659 /// ----------------------------------------------------------------------------
660 /// Abstract Attribute Classes
661 /// ----------------------------------------------------------------------------
662 
663 /// An abstract attribute for the returned values of a function.
665  /// See AbstractAttribute::AbstractAttribute(...).
667  : AbstractAttribute(F, InfoCache) {}
668 
669  /// Check \p Pred on all returned values.
670  ///
671  /// This method will evaluate \p Pred on returned values and return
672  /// true if (1) all returned values are known, and (2) \p Pred returned true
673  /// for all returned values.
674  virtual bool
675  checkForallReturnedValues(std::function<bool(Value &)> &Pred) const = 0;
676 
677  /// See AbstractAttribute::getAttrKind()
678  Attribute::AttrKind getAttrKind() const override { return ID; }
679 
680  /// The identifier used by the Attributor for this class of attributes.
681  static constexpr Attribute::AttrKind ID = Attribute::Returned;
682 };
683 
684 struct AANoUnwind : public AbstractAttribute {
685  /// An abstract interface for all nosync attributes.
687  : AbstractAttribute(V, InfoCache) {}
688 
689  /// See AbstractAttribute::getAttrKind()/
690  Attribute::AttrKind getAttrKind() const override { return ID; }
691 
692  static constexpr Attribute::AttrKind ID = Attribute::NoUnwind;
693 
694  /// Returns true if nounwind is assumed.
695  virtual bool isAssumedNoUnwind() const = 0;
696 
697  /// Returns true if nounwind is known.
698  virtual bool isKnownNoUnwind() const = 0;
699 };
700 
701 struct AANoSync : public AbstractAttribute {
702  /// An abstract interface for all nosync attributes.
704  : AbstractAttribute(V, InfoCache) {}
705 
706  /// See AbstractAttribute::getAttrKind().
707  Attribute::AttrKind getAttrKind() const override { return ID; }
708 
709  static constexpr Attribute::AttrKind ID =
710  Attribute::AttrKind(Attribute::NoSync);
711 
712  /// Returns true if "nosync" is assumed.
713  virtual bool isAssumedNoSync() const = 0;
714 
715  /// Returns true if "nosync" is known.
716  virtual bool isKnownNoSync() const = 0;
717 };
718 
719 /// An abstract interface for all nonnull attributes.
720 struct AANonNull : public AbstractAttribute {
721 
722  /// See AbstractAttribute::AbstractAttribute(...).
724  : AbstractAttribute(V, InfoCache) {}
725 
726  /// See AbstractAttribute::AbstractAttribute(...).
727  AANonNull(Value *AssociatedVal, Value &AnchoredValue,
728  InformationCache &InfoCache)
729  : AbstractAttribute(AssociatedVal, AnchoredValue, InfoCache) {}
730 
731  /// Return true if we assume that the underlying value is nonnull.
732  virtual bool isAssumedNonNull() const = 0;
733 
734  /// Return true if we know that underlying value is nonnull.
735  virtual bool isKnownNonNull() const = 0;
736 
737  /// See AbastractState::getAttrKind().
738  Attribute::AttrKind getAttrKind() const override { return ID; }
739 
740  /// The identifier used by the Attributor for this class of attributes.
741  static constexpr Attribute::AttrKind ID = Attribute::NonNull;
742 };
743 } // end namespace llvm
744 
745 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
void DeleteContainerPointers(Container &C)
For a container of pointers, deletes the pointers and then clears the container.
Definition: STLExtras.h:1155
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:641
An attribute for a function as a whole.
Definition: Attributor.h:520
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
ChangeStatus
Simple enum class that forces the status to be spelled out explicitly.
Definition: Attributor.h:114
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
Implements a lazy call graph analysis and related passes for the new pass manager.
Attribute::AttrKind getAttrKind() const override
See AbstractAttribute::getAttrKind().
Definition: Attributor.h:707
Abstract Attribute Classes
Definition: Attributor.h:664
virtual ~AbstractState()
Definition: Attributor.h:364
base_t getAssumed() const
Return the assumed state encoding.
Definition: Attributor.h:424
APInt operator &(APInt a, const APInt &b)
Definition: APInt.h:1978
F(f)
bool isValidState() const override
See AbstractState::isValidState() NOTE: For now we simply pretend that the worst possible state is in...
Definition: Attributor.h:409
An attribute for a function argument.
Definition: Attributor.h:518
AbstractAttribute(Value *AssociatedVal, Value &AnchoredVal, InformationCache &InfoCache)
An abstract attribute associated with AssociatedVal and anchored at AnchoredVal.
Definition: Attributor.h:530
ValTy * getCalledValue() const
Return the pointer to function that is being called.
Definition: CallSite.h:104
std::vector< Instruction * > InstructionVectorTy
A vector type to hold instructions.
Definition: Attributor.h:321
bool isKnown(base_t BitsEncoding) const
Return true if the bits set in BitsEncoding are "known bits".
Definition: Attributor.h:427
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
const AAType * getAAFor(AbstractAttribute &QueryingAA, const Value &V, int ArgNo=-1)
Lookup an abstract attribute of type AAType anchored at value V and argument number ArgNo...
Definition: Attributor.h:174
No attributes have been set.
Definition: Attributes.h:71
Attribute::AttrKind getAttrKind() const override
See AbastractState::getAttrKind().
Definition: Attributor.h:738
void indicatePessimisticFixpoint() override
See AbstractState::indicatePessimisticFixpoint(...)
Definition: Attributor.h:418
InformationCache & InfoCache
The information cache accessible to this abstract attribute.
Definition: Attributor.h:641
An attribute for a call site argument.
Definition: Attributor.h:519
AANoUnwind(Value &V, InformationCache &InfoCache)
An abstract interface for all nosync attributes.
Definition: Attributor.h:686
Attribute::AttrKind getAttrKind() const override
See AbstractAttribute::getAttrKind()/.
Definition: Attributor.h:690
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:372
virtual const Value * getAssociatedValue() const
Definition: Attributor.h:580
An abstract interface for all nonnull attributes.
Definition: Attributor.h:720
constexpr char Attrs[]
Key for Kernel::Metadata::mAttrs.
IntegerState(base_t BestState=~0)
Initialize the (best) state.
Definition: Attributor.h:402
InstructionVectorTy & getReadOrWriteInstsForFunction(Function &F)
Return the instructions in F that may read or write memory.
Definition: Attributor.h:324
AAType & registerAA(AAType &AA, int ArgNo=-1)
Introduce a new abstract attribute into the fixpoint analysis.
Definition: Attributor.h:229
Value * AssociatedVal
The value this abstract attribute is associated with.
Definition: Attributor.h:635
base_t getKnown() const
Return the known state encoding.
Definition: Attributor.h:421
ManifestPosition
The positions attributes can be manifested in.
Definition: Attributor.h:517
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
void indicateOptimisticFixpoint() override
See AbstractState::indicateOptimisticFixpoint(...)
Definition: Attributor.h:415
AANoSync(Value &V, InformationCache &InfoCache)
An abstract interface for all nosync attributes.
Definition: Attributor.h:703
AANonNull(Value *AssociatedVal, Value &AnchoredValue, InformationCache &InfoCache)
See AbstractAttribute::AbstractAttribute(...).
Definition: Attributor.h:727
virtual void initialize(Attributor &A)
Initialize the state with the information in the Attributor A.
Definition: Attributor.h:550
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Simple state with integers encoding.
Definition: Attributor.h:397
An attribute for the function return value.
Definition: Attributor.h:521
Value & getAnchoredValue()
Return the value this abstract attribute is anchored with.
Definition: Attributor.h:563
Base struct for all "concrete attribute" deductions.
Definition: Attributor.h:514
virtual void getDeducedAttributes(SmallVectorImpl< Attribute > &Attrs) const
Return the deduced attributes in Attrs.
Definition: Attributor.h:590
IntegerState & removeAssumedBits(base_t BitsEncoding)
Remove the bits in BitsEncoding from the "assumed bits" if not known.
Definition: Attributor.h:445
Value & AnchoredVal
The value this abstract attribute is anchored at.
Definition: Attributor.h:638
const Value & getAnchoredValue() const
Definition: Attributor.h:564
Data structure to hold cached (LLVM-IR) information.
Definition: Attributor.h:310
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
OpcodeInstMapTy & getOpcodeInstMapForFunction(Function &F)
Return the map that relates "interesting" opcodes with all instructions with that opcode in F...
Definition: Attributor.h:316
An interface to query the internal state of an abstract attribute.
Definition: Attributor.h:363
IntegerState & addKnownBits(base_t Bits)
Add the bits in BitsEncoding to the "known bits".
Definition: Attributor.h:437
Pass * createAttributorLegacyPass()
Establish a view to a call site for examination.
Definition: CallSite.h:897
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Attribute::AttrKind getAttrKind() const override
See AbstractAttribute::getAttrKind()
Definition: Attributor.h:678
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:80
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2038
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:211
virtual Value * getAssociatedValue()
}
Definition: Attributor.h:579
AAReturnedValues(Function &F, InformationCache &InfoCache)
See AbstractAttribute::AbstractAttribute(...).
Definition: Attributor.h:666
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
AbstractAttribute(Value &V, InformationCache &InfoCache)
An abstract attribute associated with and anchored at V.
Definition: Attributor.h:536
LLVM Value Representation.
Definition: Value.h:72
virtual ~AbstractAttribute()
Virtual destructor.
Definition: Attributor.h:540
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
bool isAtFixpoint() const override
See AbstractState::isAtFixpoint()
Definition: Attributor.h:412
print Print MemDeps of function
A container for analyses that lazily runs them and caches their results.
APInt operator|(APInt a, const APInt &b)
Definition: APInt.h:1998
static constexpr base_t getWorstState()
Return the worst possible representable state.
Definition: Attributor.h:405
This header defines various interfaces for pass management in LLVM.
bool isAssumed(base_t BitsEncoding) const
Return true if the bits set in BitsEncoding are "assumed bits".
Definition: Attributor.h:432
AANonNull(Value &V, InformationCache &InfoCache)
See AbstractAttribute::AbstractAttribute(...).
Definition: Attributor.h:723
Simple wrapper for a single bit (boolean) state.
Definition: Attributor.h:467
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results...
Definition: Attributes.h:69
IntegerState & intersectAssumedBits(base_t BitsEncoding)
Keep only "assumed bits" also set in BitsEncoding but all known ones.
Definition: Attributor.h:452