1 //===- Attributor.h --- Module-wide attribute deduction ---------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // Attributor: An inter procedural (abstract) "attribute" deduction framework.
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.
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.
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.
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.
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.
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.
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.
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.
95 //===----------------------------------------------------------------------===//
97 #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
98 #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
100 #include "llvm/Analysis/LazyCallGraph.h"
101 #include "llvm/IR/CallSite.h"
102 #include "llvm/IR/PassManager.h"
106 struct AbstractAttribute;
107 struct InformationCache;
111 /// Simple enum class that forces the status to be spelled out explicitly.
114 enum class ChangeStatus {
119 ChangeStatus operator|(ChangeStatus l, ChangeStatus r);
120 ChangeStatus operator&(ChangeStatus l, ChangeStatus r);
123 /// The fixpoint analysis framework that orchestrates the attribute deduction.
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.
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.
148 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
149 /// described in the file comment.
151 ~Attributor() { DeleteContainerPointers(AllAbstractAttributes); }
153 /// Run the analyses until a fixpoint is reached or enforced (timeout).
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).
158 /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED.
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.
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,
176 static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
177 "Cannot query an attribute with a type not derived from "
178 "'AbstractAttribute'!");
179 assert(AAType::ID != Attribute::None &&
180 "Cannot lookup generic abstract attributes!");
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
186 if (auto *Arg = dyn_cast<Argument>(&V))
187 ArgNo = Arg->getArgNo();
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
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);
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 *>(
201 KindToAbstractAttributeMap.lookup(AAType::ID))) {
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);
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);
216 // No matching attribute found
220 /// Introduce a new abstract attribute into the fixpoint analysis.
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.
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 ®isterAA(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'!");
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();
240 if (auto *Arg = dyn_cast<Argument>(&AnchoredVal))
241 ArgNo = Arg->getArgNo();
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);
250 /// Determine opportunities to derive 'default' attributes in \p F and create
251 /// abstract attribute objects for them.
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.
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
262 void identifyDefaultAbstractAttributes(
263 Function &F, InformationCache &InfoCache,
264 DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist = nullptr);
266 /// Check \p Pred on all function call sites.
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);
275 /// The set of all abstract attributes.
277 using AAVector = SmallVector<AbstractAttribute *, 64>;
278 AAVector AllAbstractAttributes;
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.
285 using KindToAbstractAttributeMap = DenseMap<unsigned, AbstractAttribute *>;
286 DenseMap<std::pair<const Value *, int>, KindToAbstractAttributeMap> AAMap;
289 /// A map from abstract attributes to the ones that queried them through calls
290 /// to the getAAFor<...>(...) method.
293 DenseMap<AbstractAttribute *, SetVector<AbstractAttribute *>>;
298 /// Data structure to hold cached (LLVM-IR) information.
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(..)
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.
310 struct InformationCache {
311 /// A map type from opcodes to instructions with this opcode.
312 using OpcodeInstMapTy = DenseMap<unsigned, SmallVector<Instruction *, 32>>;
314 /// Return the map that relates "interesting" opcodes with all instructions
315 /// with that opcode in \p F.
316 OpcodeInstMapTy &getOpcodeInstMapForFunction(Function &F) {
317 return FuncInstOpcodeMap[&F];
320 /// A vector type to hold instructions.
321 using InstructionVectorTy = std::vector<Instruction *>;
323 /// Return the instructions in \p F that may read or write memory.
324 InstructionVectorTy &getReadOrWriteInstsForFunction(Function &F) {
325 return FuncRWInstsMap[&F];
329 /// A map type from functions to opcode to instruction maps.
330 using FuncInstOpcodeMapTy = DenseMap<Function *, OpcodeInstMapTy>;
332 /// A map type from functions to their read or write instructions.
333 using FuncRWInstsMapTy = DenseMap<Function *, InstructionVectorTy>;
335 /// A nested map that remembers all instructions in a function with a certain
336 /// instruction opcode (Instruction::getOpcode()).
337 FuncInstOpcodeMapTy FuncInstOpcodeMap;
339 /// A map from functions to their instructions that may read or write memory.
340 FuncRWInstsMapTy FuncRWInstsMap;
342 /// Give the Attributor access to the members so
343 /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them.
344 friend struct Attributor;
347 /// An interface to query the internal state of an abstract attribute.
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.
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.
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.
363 struct AbstractState {
364 virtual ~AbstractState() {}
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;
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;
374 /// Indicate that the abstract state should converge to the optimistic state.
376 /// This will usually make the optimistically assumed state the known to be
378 virtual void indicateOptimisticFixpoint() = 0;
380 /// Indicate that the abstract state should converge to the pessimistic state.
382 /// This will usually revert the optimistically assumed state to the known to
384 virtual void indicatePessimisticFixpoint() = 0;
387 /// Simple state with integers encoding.
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;
401 /// Initialize the (best) state.
402 IntegerState(base_t BestState = ~0) : Assumed(BestState) {}
404 /// Return the worst possible representable state.
405 static constexpr base_t getWorstState() { return 0; }
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(); }
411 /// See AbstractState::isAtFixpoint()
412 bool isAtFixpoint() const override { return Assumed == Known; }
414 /// See AbstractState::indicateOptimisticFixpoint(...)
415 void indicateOptimisticFixpoint() override { Known = Assumed; }
417 /// See AbstractState::indicatePessimisticFixpoint(...)
418 void indicatePessimisticFixpoint() override { Assumed = Known; }
420 /// Return the known state encoding
421 base_t getKnown() const { return Known; }
423 /// Return the assumed state encoding.
424 base_t getAssumed() const { return Assumed; }
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;
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;
436 /// Add the bits in \p BitsEncoding to the "known bits".
437 IntegerState &addKnownBits(base_t Bits) {
438 // Make sure we never miss any "known bits".
444 /// Remove the bits in \p BitsEncoding from the "assumed bits" if not known.
445 IntegerState &removeAssumedBits(base_t BitsEncoding) {
446 // Make sure we never loose any "known bits".
447 Assumed = (Assumed & ~BitsEncoding) | Known;
451 /// Keep only "assumed bits" also set in \p BitsEncoding but all known ones.
452 IntegerState &intersectAssumedBits(base_t BitsEncoding) {
453 // Make sure we never loose any "known bits".
454 Assumed = (Assumed & BitsEncoding) | Known;
459 /// The known state encoding in an integer of type base_t.
460 base_t Known = getWorstState();
462 /// The assumed state encoding in an integer of type base_t.
466 /// Simple wrapper for a single bit (boolean) state.
467 struct BooleanState : public IntegerState {
468 BooleanState() : IntegerState(1){};
471 /// Base struct for all "concrete attribute" deductions.
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.
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.
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.
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.
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.
514 struct AbstractAttribute {
516 /// The positions attributes can be manifested in.
517 enum ManifestPosition {
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.
524 /// An abstract attribute associated with \p AssociatedVal and anchored at
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) {}
535 /// An abstract attribute associated with and anchored at \p V.
536 AbstractAttribute(Value &V, InformationCache &InfoCache)
537 : AbstractAttribute(&V, V, InfoCache) {}
539 /// Virtual destructor.
540 virtual ~AbstractAttribute() {}
542 /// Initialize the state with the information in the Attributor \p A.
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) {}
552 /// Return the internal abstract state for inspection.
553 virtual const AbstractState &getState() const = 0;
555 /// Return the value this abstract attribute is anchored with.
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.
563 Value &getAnchoredValue() { return AnchoredVal; }
564 const Value &getAnchoredValue() const { return AnchoredVal; }
567 /// Return the llvm::Function surrounding the anchored value.
570 Function &getAnchorScope();
571 const Function &getAnchorScope() const;
574 /// Return the value this abstract attribute is associated with.
576 /// The abstract state usually represents this value.
579 virtual Value *getAssociatedValue() { return AssociatedVal; }
580 virtual const Value *getAssociatedValue() const { return AssociatedVal; }
583 /// Return the position this abstract state is manifested in.
584 virtual ManifestPosition getManifestPosition() const = 0;
586 /// Return the kind that identifies the abstract attribute implementation.
587 virtual Attribute::AttrKind getAttrKind() const = 0;
589 /// Return the deduced attributes in \p Attrs.
590 virtual void getDeducedAttributes(SmallVectorImpl<Attribute> &Attrs) const {
591 LLVMContext &Ctx = AnchoredVal.getContext();
592 Attrs.emplace_back(Attribute::get(Ctx, getAttrKind()));
595 /// Helper functions, for debug purposes only.
597 virtual void print(raw_ostream &OS) const;
598 void dump() const { print(dbgs()); }
600 /// This function should return the "summarized" assumed state as string.
601 virtual const std::string getAsStr() const = 0;
604 /// Allow the Attributor access to the protected methods.
605 friend struct Attributor;
608 /// Hook for the Attributor to trigger an update of the internal state.
610 /// If this attribute is already fixed, this method will return UNCHANGED,
611 /// otherwise it delegates to `AbstractAttribute::updateImpl`.
613 /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
614 ChangeStatus update(Attributor &A);
616 /// Hook for the Attributor to trigger the manifestation of the information
617 /// represented by the abstract attribute in the LLVM-IR.
619 /// \Return CHANGED if the IR was altered, otherwise UNCHANGED.
620 virtual ChangeStatus manifest(Attributor &A);
622 /// Return the internal abstract state for careful modification.
623 virtual AbstractState &getState() = 0;
625 /// The actual update/transfer function which has to be implemented by the
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.
631 /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
632 virtual ChangeStatus updateImpl(Attributor &A) = 0;
634 /// The value this abstract attribute is associated with.
635 Value *AssociatedVal;
637 /// The value this abstract attribute is anchored at.
640 /// The information cache accessible to this abstract attribute.
641 InformationCache &InfoCache;
644 /// Forward declarations of output streams for debug purposes.
647 raw_ostream &operator<<(raw_ostream &OS, const AbstractAttribute &AA);
648 raw_ostream &operator<<(raw_ostream &OS, ChangeStatus S);
649 raw_ostream &operator<<(raw_ostream &OS, AbstractAttribute::ManifestPosition);
650 raw_ostream &operator<<(raw_ostream &OS, const AbstractState &State);
653 struct AttributorPass : public PassInfoMixin<AttributorPass> {
654 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
657 Pass *createAttributorLegacyPass();
659 /// ----------------------------------------------------------------------------
660 /// Abstract Attribute Classes
661 /// ----------------------------------------------------------------------------
663 /// An abstract attribute for the returned values of a function.
664 struct AAReturnedValues : public AbstractAttribute {
665 /// See AbstractAttribute::AbstractAttribute(...).
666 AAReturnedValues(Function &F, InformationCache &InfoCache)
667 : AbstractAttribute(F, InfoCache) {}
669 /// Check \p Pred on all returned values.
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.
675 checkForallReturnedValues(std::function<bool(Value &)> &Pred) const = 0;
677 /// See AbstractAttribute::getAttrKind()
678 Attribute::AttrKind getAttrKind() const override { return ID; }
680 /// The identifier used by the Attributor for this class of attributes.
681 static constexpr Attribute::AttrKind ID = Attribute::Returned;
684 struct AANoUnwind : public AbstractAttribute {
685 /// An abstract interface for all nosync attributes.
686 AANoUnwind(Value &V, InformationCache &InfoCache)
687 : AbstractAttribute(V, InfoCache) {}
689 /// See AbstractAttribute::getAttrKind()/
690 Attribute::AttrKind getAttrKind() const override { return ID; }
692 static constexpr Attribute::AttrKind ID = Attribute::NoUnwind;
694 /// Returns true if nounwind is assumed.
695 virtual bool isAssumedNoUnwind() const = 0;
697 /// Returns true if nounwind is known.
698 virtual bool isKnownNoUnwind() const = 0;
701 struct AANoSync : public AbstractAttribute {
702 /// An abstract interface for all nosync attributes.
703 AANoSync(Value &V, InformationCache &InfoCache)
704 : AbstractAttribute(V, InfoCache) {}
706 /// See AbstractAttribute::getAttrKind().
707 Attribute::AttrKind getAttrKind() const override { return ID; }
709 static constexpr Attribute::AttrKind ID =
710 Attribute::AttrKind(Attribute::NoSync);
712 /// Returns true if "nosync" is assumed.
713 virtual bool isAssumedNoSync() const = 0;
715 /// Returns true if "nosync" is known.
716 virtual bool isKnownNoSync() const = 0;
719 /// An abstract interface for all nonnull attributes.
720 struct AANonNull : public AbstractAttribute {
722 /// See AbstractAttribute::AbstractAttribute(...).
723 AANonNull(Value &V, InformationCache &InfoCache)
724 : AbstractAttribute(V, InfoCache) {}
726 /// See AbstractAttribute::AbstractAttribute(...).
727 AANonNull(Value *AssociatedVal, Value &AnchoredValue,
728 InformationCache &InfoCache)
729 : AbstractAttribute(AssociatedVal, AnchoredValue, InfoCache) {}
731 /// Return true if we assume that the underlying value is nonnull.
732 virtual bool isAssumedNonNull() const = 0;
734 /// Return true if we know that underlying value is nonnull.
735 virtual bool isKnownNonNull() const = 0;
737 /// See AbastractState::getAttrKind().
738 Attribute::AttrKind getAttrKind() const override { return ID; }
740 /// The identifier used by the Attributor for this class of attributes.
741 static constexpr Attribute::AttrKind ID = Attribute::NonNull;
744 /// An abstract attribute for norecurse.
745 struct AANoRecurse : public AbstractAttribute {
747 /// See AbstractAttribute::AbstractAttribute(...).
748 AANoRecurse(Value &V, InformationCache &InfoCache)
749 : AbstractAttribute(V, InfoCache) {}
751 /// See AbstractAttribute::getAttrKind()
752 virtual Attribute::AttrKind getAttrKind() const override {
753 return Attribute::NoRecurse;
756 /// Return true if "norecurse" is known.
757 virtual bool isKnownNoRecurse() const = 0;
759 /// Return true if "norecurse" is assumed.
760 virtual bool isAssumedNoRecurse() const = 0;
762 /// The identifier used by the Attributor for this class of attributes.
763 static constexpr Attribute::AttrKind ID = Attribute::NoRecurse;
766 /// An abstract attribute for willreturn.
767 struct AAWillReturn : public AbstractAttribute {
769 /// See AbstractAttribute::AbstractAttribute(...).
770 AAWillReturn(Value &V, InformationCache &InfoCache)
771 : AbstractAttribute(V, InfoCache) {}
773 /// See AbstractAttribute::getAttrKind()
774 virtual Attribute::AttrKind getAttrKind() const override {
775 return Attribute::WillReturn;
778 /// Return true if "willreturn" is known.
779 virtual bool isKnownWillReturn() const = 0;
781 /// Return true if "willreturn" is assumed.
782 virtual bool isAssumedWillReturn() const = 0;
784 /// The identifier used by the Attributor for this class of attributes.
785 static constexpr Attribute::AttrKind ID = Attribute::WillReturn;
787 } // end namespace llvm
789 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H