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 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.
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.
95 //===----------------------------------------------------------------------===//
97 #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
98 #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
100 #include "llvm/ADT/MapVector.h"
101 #include "llvm/ADT/SCCIterator.h"
102 #include "llvm/ADT/SetVector.h"
103 #include "llvm/Analysis/AliasAnalysis.h"
104 #include "llvm/Analysis/CallGraph.h"
105 #include "llvm/Analysis/MustExecute.h"
106 #include "llvm/Analysis/TargetLibraryInfo.h"
107 #include "llvm/IR/CallSite.h"
108 #include "llvm/IR/ConstantRange.h"
109 #include "llvm/IR/PassManager.h"
113 struct AbstractAttribute;
114 struct InformationCache;
119 /// Simple enum classes that forces properties to be spelled out explicitly.
122 enum class ChangeStatus {
127 ChangeStatus operator|(ChangeStatus l, ChangeStatus r);
128 ChangeStatus operator&(ChangeStatus l, ChangeStatus r);
130 enum class DepClassTy {
136 /// Helper to describe and deal with positions in the LLVM-IR.
138 /// A position in the IR is described by an anchor value and an "offset" that
139 /// could be the argument number, for call sites and arguments, or an indicator
140 /// of the "position kind". The kinds, specified in the Kind enum below, include
141 /// the locations in the attribute list, i.a., function scope and return value,
142 /// as well as a distinction between call sites and functions. Finally, there
143 /// are floating values that do not have a corresponding attribute list
146 virtual ~IRPosition() {}
148 /// The positions we distinguish in the IR.
150 /// The values are chosen such that the KindOrArgNo member has a value >= 1
151 /// if it is an argument or call site argument while a value < 1 indicates the
152 /// respective kind of that value.
154 IRP_INVALID = -6, ///< An invalid position.
155 IRP_FLOAT = -5, ///< A position that is not associated with a spot suitable
156 ///< for attributes. This could be any value or instruction.
157 IRP_RETURNED = -4, ///< An attribute for the function return value.
158 IRP_CALL_SITE_RETURNED = -3, ///< An attribute for a call site return value.
159 IRP_FUNCTION = -2, ///< An attribute for a function (scope).
160 IRP_CALL_SITE = -1, ///< An attribute for a call site (function scope).
161 IRP_ARGUMENT = 0, ///< An attribute for a function argument.
162 IRP_CALL_SITE_ARGUMENT = 1, ///< An attribute for a call site argument.
165 /// Default constructor available to create invalid positions implicitly. All
166 /// other positions need to be created explicitly through the appropriate
167 /// static member function.
168 IRPosition() : AnchorVal(nullptr), KindOrArgNo(IRP_INVALID) { verify(); }
170 /// Create a position describing the value of \p V.
171 static const IRPosition value(const Value &V) {
172 if (auto *Arg = dyn_cast<Argument>(&V))
173 return IRPosition::argument(*Arg);
174 if (auto *CB = dyn_cast<CallBase>(&V))
175 return IRPosition::callsite_returned(*CB);
176 return IRPosition(const_cast<Value &>(V), IRP_FLOAT);
179 /// Create a position describing the function scope of \p F.
180 static const IRPosition function(const Function &F) {
181 return IRPosition(const_cast<Function &>(F), IRP_FUNCTION);
184 /// Create a position describing the returned value of \p F.
185 static const IRPosition returned(const Function &F) {
186 return IRPosition(const_cast<Function &>(F), IRP_RETURNED);
189 /// Create a position describing the argument \p Arg.
190 static const IRPosition argument(const Argument &Arg) {
191 return IRPosition(const_cast<Argument &>(Arg), Kind(Arg.getArgNo()));
194 /// Create a position describing the function scope of \p CB.
195 static const IRPosition callsite_function(const CallBase &CB) {
196 return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE);
199 /// Create a position describing the returned value of \p CB.
200 static const IRPosition callsite_returned(const CallBase &CB) {
201 return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE_RETURNED);
204 /// Create a position describing the argument of \p CB at position \p ArgNo.
205 static const IRPosition callsite_argument(const CallBase &CB,
207 return IRPosition(const_cast<CallBase &>(CB), Kind(ArgNo));
210 /// Create a position describing the function scope of \p ICS.
211 static const IRPosition callsite_function(ImmutableCallSite ICS) {
212 return IRPosition::callsite_function(cast<CallBase>(*ICS.getInstruction()));
215 /// Create a position describing the returned value of \p ICS.
216 static const IRPosition callsite_returned(ImmutableCallSite ICS) {
217 return IRPosition::callsite_returned(cast<CallBase>(*ICS.getInstruction()));
220 /// Create a position describing the argument of \p ICS at position \p ArgNo.
221 static const IRPosition callsite_argument(ImmutableCallSite ICS,
223 return IRPosition::callsite_argument(cast<CallBase>(*ICS.getInstruction()),
227 /// Create a position describing the argument of \p ACS at position \p ArgNo.
228 static const IRPosition callsite_argument(AbstractCallSite ACS,
230 int CSArgNo = ACS.getCallArgOperandNo(ArgNo);
232 return IRPosition::callsite_argument(
233 cast<CallBase>(*ACS.getInstruction()), CSArgNo);
237 /// Create a position with function scope matching the "context" of \p IRP.
238 /// If \p IRP is a call site (see isAnyCallSitePosition()) then the result
239 /// will be a call site position, otherwise the function position of the
240 /// associated function.
241 static const IRPosition function_scope(const IRPosition &IRP) {
242 if (IRP.isAnyCallSitePosition()) {
243 return IRPosition::callsite_function(
244 cast<CallBase>(IRP.getAnchorValue()));
246 assert(IRP.getAssociatedFunction());
247 return IRPosition::function(*IRP.getAssociatedFunction());
250 bool operator==(const IRPosition &RHS) const {
251 return (AnchorVal == RHS.AnchorVal) && (KindOrArgNo == RHS.KindOrArgNo);
253 bool operator!=(const IRPosition &RHS) const { return !(*this == RHS); }
255 /// Return the value this abstract attribute is anchored with.
257 /// The anchor value might not be the associated value if the latter is not
258 /// sufficient to determine where arguments will be manifested. This is, so
259 /// far, only the case for call site arguments as the value is not sufficient
260 /// to pinpoint them. Instead, we can use the call site as an anchor.
261 Value &getAnchorValue() const {
262 assert(KindOrArgNo != IRP_INVALID &&
263 "Invalid position does not have an anchor value!");
267 /// Return the associated function, if any.
268 Function *getAssociatedFunction() const {
269 if (auto *CB = dyn_cast<CallBase>(AnchorVal))
270 return CB->getCalledFunction();
271 assert(KindOrArgNo != IRP_INVALID &&
272 "Invalid position does not have an anchor scope!");
273 Value &V = getAnchorValue();
274 if (isa<Function>(V))
275 return &cast<Function>(V);
276 if (isa<Argument>(V))
277 return cast<Argument>(V).getParent();
278 if (isa<Instruction>(V))
279 return cast<Instruction>(V).getFunction();
283 /// Return the associated argument, if any.
284 Argument *getAssociatedArgument() const;
286 /// Return true if the position refers to a function interface, that is the
287 /// function scope, the function return, or an argument.
288 bool isFnInterfaceKind() const {
289 switch (getPositionKind()) {
290 case IRPosition::IRP_FUNCTION:
291 case IRPosition::IRP_RETURNED:
292 case IRPosition::IRP_ARGUMENT:
299 /// Return the Function surrounding the anchor value.
300 Function *getAnchorScope() const {
301 Value &V = getAnchorValue();
302 if (isa<Function>(V))
303 return &cast<Function>(V);
304 if (isa<Argument>(V))
305 return cast<Argument>(V).getParent();
306 if (isa<Instruction>(V))
307 return cast<Instruction>(V).getFunction();
311 /// Return the context instruction, if any.
312 Instruction *getCtxI() const {
313 Value &V = getAnchorValue();
314 if (auto *I = dyn_cast<Instruction>(&V))
316 if (auto *Arg = dyn_cast<Argument>(&V))
317 if (!Arg->getParent()->isDeclaration())
318 return &Arg->getParent()->getEntryBlock().front();
319 if (auto *F = dyn_cast<Function>(&V))
320 if (!F->isDeclaration())
321 return &(F->getEntryBlock().front());
325 /// Return the value this abstract attribute is associated with.
326 Value &getAssociatedValue() const {
327 assert(KindOrArgNo != IRP_INVALID &&
328 "Invalid position does not have an associated value!");
329 if (getArgNo() < 0 || isa<Argument>(AnchorVal))
331 assert(isa<CallBase>(AnchorVal) && "Expected a call base!");
332 return *cast<CallBase>(AnchorVal)->getArgOperand(getArgNo());
335 /// Return the argument number of the associated value if it is an argument or
336 /// call site argument, otherwise a negative value.
337 int getArgNo() const { return KindOrArgNo; }
339 /// Return the index in the attribute list for this position.
340 unsigned getAttrIdx() const {
341 switch (getPositionKind()) {
342 case IRPosition::IRP_INVALID:
343 case IRPosition::IRP_FLOAT:
345 case IRPosition::IRP_FUNCTION:
346 case IRPosition::IRP_CALL_SITE:
347 return AttributeList::FunctionIndex;
348 case IRPosition::IRP_RETURNED:
349 case IRPosition::IRP_CALL_SITE_RETURNED:
350 return AttributeList::ReturnIndex;
351 case IRPosition::IRP_ARGUMENT:
352 case IRPosition::IRP_CALL_SITE_ARGUMENT:
353 return KindOrArgNo + AttributeList::FirstArgIndex;
356 "There is no attribute index for a floating or invalid position!");
359 /// Return the associated position kind.
360 Kind getPositionKind() const {
361 if (getArgNo() >= 0) {
362 assert(((isa<Argument>(getAnchorValue()) &&
363 isa<Argument>(getAssociatedValue())) ||
364 isa<CallBase>(getAnchorValue())) &&
365 "Expected argument or call base due to argument number!");
366 if (isa<CallBase>(getAnchorValue()))
367 return IRP_CALL_SITE_ARGUMENT;
371 assert(KindOrArgNo < 0 &&
372 "Expected (call site) arguments to never reach this point!");
373 return Kind(KindOrArgNo);
376 /// TODO: Figure out if the attribute related helper functions should live
377 /// here or somewhere else.
379 /// Return true if any kind in \p AKs existing in the IR at a position that
380 /// will affect this one. See also getAttrs(...).
381 /// \param IgnoreSubsumingPositions Flag to determine if subsuming positions,
382 /// e.g., the function position if this is an
383 /// argument position, should be ignored.
384 bool hasAttr(ArrayRef<Attribute::AttrKind> AKs,
385 bool IgnoreSubsumingPositions = false) const;
387 /// Return the attributes of any kind in \p AKs existing in the IR at a
388 /// position that will affect this one. While each position can only have a
389 /// single attribute of any kind in \p AKs, there are "subsuming" positions
390 /// that could have an attribute as well. This method returns all attributes
391 /// found in \p Attrs.
392 /// \param IgnoreSubsumingPositions Flag to determine if subsuming positions,
393 /// e.g., the function position if this is an
394 /// argument position, should be ignored.
395 void getAttrs(ArrayRef<Attribute::AttrKind> AKs,
396 SmallVectorImpl<Attribute> &Attrs,
397 bool IgnoreSubsumingPositions = false) const;
399 /// Return the attribute of kind \p AK existing in the IR at this position.
400 Attribute getAttr(Attribute::AttrKind AK) const {
401 if (getPositionKind() == IRP_INVALID || getPositionKind() == IRP_FLOAT)
404 AttributeList AttrList;
405 if (ImmutableCallSite ICS = ImmutableCallSite(&getAnchorValue()))
406 AttrList = ICS.getAttributes();
408 AttrList = getAssociatedFunction()->getAttributes();
410 if (AttrList.hasAttribute(getAttrIdx(), AK))
411 return AttrList.getAttribute(getAttrIdx(), AK);
415 /// Remove the attribute of kind \p AKs existing in the IR at this position.
416 void removeAttrs(ArrayRef<Attribute::AttrKind> AKs) const {
417 if (getPositionKind() == IRP_INVALID || getPositionKind() == IRP_FLOAT)
420 AttributeList AttrList;
421 CallSite CS = CallSite(&getAnchorValue());
423 AttrList = CS.getAttributes();
425 AttrList = getAssociatedFunction()->getAttributes();
427 LLVMContext &Ctx = getAnchorValue().getContext();
428 for (Attribute::AttrKind AK : AKs)
429 AttrList = AttrList.removeAttribute(Ctx, getAttrIdx(), AK);
432 CS.setAttributes(AttrList);
434 getAssociatedFunction()->setAttributes(AttrList);
437 bool isAnyCallSitePosition() const {
438 switch (getPositionKind()) {
439 case IRPosition::IRP_CALL_SITE:
440 case IRPosition::IRP_CALL_SITE_RETURNED:
441 case IRPosition::IRP_CALL_SITE_ARGUMENT:
448 /// Special DenseMap key values.
451 static const IRPosition EmptyKey;
452 static const IRPosition TombstoneKey;
456 /// Private constructor for special values only!
457 explicit IRPosition(int KindOrArgNo)
458 : AnchorVal(0), KindOrArgNo(KindOrArgNo) {}
460 /// IRPosition anchored at \p AnchorVal with kind/argument numbet \p PK.
461 explicit IRPosition(Value &AnchorVal, Kind PK)
462 : AnchorVal(&AnchorVal), KindOrArgNo(PK) {
466 /// Verify internal invariants.
470 /// The value this position is anchored at.
473 /// The argument number, if non-negative, or the position "kind".
477 /// Helper that allows IRPosition as a key in a DenseMap.
478 template <> struct DenseMapInfo<IRPosition> {
479 static inline IRPosition getEmptyKey() { return IRPosition::EmptyKey; }
480 static inline IRPosition getTombstoneKey() {
481 return IRPosition::TombstoneKey;
483 static unsigned getHashValue(const IRPosition &IRP) {
484 return (DenseMapInfo<Value *>::getHashValue(&IRP.getAnchorValue()) << 4) ^
485 (unsigned(IRP.getArgNo()));
487 static bool isEqual(const IRPosition &LHS, const IRPosition &RHS) {
492 /// A visitor class for IR positions.
494 /// Given a position P, the SubsumingPositionIterator allows to visit "subsuming
495 /// positions" wrt. attributes/information. Thus, if a piece of information
496 /// holds for a subsuming position, it also holds for the position P.
498 /// The subsuming positions always include the initial position and then,
499 /// depending on the position kind, additionally the following ones:
500 /// - for IRP_RETURNED:
501 /// - the function (IRP_FUNCTION)
502 /// - for IRP_ARGUMENT:
503 /// - the function (IRP_FUNCTION)
504 /// - for IRP_CALL_SITE:
505 /// - the callee (IRP_FUNCTION), if known
506 /// - for IRP_CALL_SITE_RETURNED:
507 /// - the callee (IRP_RETURNED), if known
508 /// - the call site (IRP_FUNCTION)
509 /// - the callee (IRP_FUNCTION), if known
510 /// - for IRP_CALL_SITE_ARGUMENT:
511 /// - the argument of the callee (IRP_ARGUMENT), if known
512 /// - the callee (IRP_FUNCTION), if known
513 /// - the position the call site argument is associated with if it is not
514 /// anchored to the call site, e.g., if it is an argument then the argument
516 class SubsumingPositionIterator {
517 SmallVector<IRPosition, 4> IRPositions;
518 using iterator = decltype(IRPositions)::iterator;
521 SubsumingPositionIterator(const IRPosition &IRP);
522 iterator begin() { return IRPositions.begin(); }
523 iterator end() { return IRPositions.end(); }
526 /// Wrapper for FunctoinAnalysisManager.
527 struct AnalysisGetter {
528 template <typename Analysis>
529 typename Analysis::Result *getAnalysis(const Function &F) {
530 if (!MAM || !F.getParent())
532 auto &FAM = MAM->getResult<FunctionAnalysisManagerModuleProxy>(
533 const_cast<Module &>(*F.getParent()))
535 return &FAM.getResult<Analysis>(const_cast<Function &>(F));
538 template <typename Analysis>
539 typename Analysis::Result *getAnalysis(const Module &M) {
542 return &MAM->getResult<Analysis>(const_cast<Module &>(M));
544 AnalysisGetter(ModuleAnalysisManager &MAM) : MAM(&MAM) {}
548 ModuleAnalysisManager *MAM = nullptr;
551 /// Data structure to hold cached (LLVM-IR) information.
553 /// All attributes are given an InformationCache object at creation time to
554 /// avoid inspection of the IR by all of them individually. This default
555 /// InformationCache will hold information required by 'default' attributes,
556 /// thus the ones deduced when Attributor::identifyDefaultAbstractAttributes(..)
559 /// If custom abstract attributes, registered manually through
560 /// Attributor::registerAA(...), need more information, especially if it is not
561 /// reusable, it is advised to inherit from the InformationCache and cast the
562 /// instance down in the abstract attributes.
563 struct InformationCache {
564 InformationCache(const Module &M, AnalysisGetter &AG)
565 : DL(M.getDataLayout()), Explorer(/* ExploreInterBlock */ true), AG(AG) {
567 CallGraph *CG = AG.getAnalysis<CallGraphAnalysis>(M);
571 DenseMap<const Function *, unsigned> SccSize;
572 for (scc_iterator<CallGraph *> I = scc_begin(CG); !I.isAtEnd(); ++I) {
573 for (CallGraphNode *Node : *I)
574 SccSize[Node->getFunction()] = I->size();
576 SccSizeOpt = std::move(SccSize);
579 /// A map type from opcodes to instructions with this opcode.
580 using OpcodeInstMapTy = DenseMap<unsigned, SmallVector<Instruction *, 32>>;
582 /// Return the map that relates "interesting" opcodes with all instructions
583 /// with that opcode in \p F.
584 OpcodeInstMapTy &getOpcodeInstMapForFunction(const Function &F) {
585 return FuncInstOpcodeMap[&F];
588 /// A vector type to hold instructions.
589 using InstructionVectorTy = std::vector<Instruction *>;
591 /// Return the instructions in \p F that may read or write memory.
592 InstructionVectorTy &getReadOrWriteInstsForFunction(const Function &F) {
593 return FuncRWInstsMap[&F];
596 /// Return MustBeExecutedContextExplorer
597 MustBeExecutedContextExplorer &getMustBeExecutedContextExplorer() {
601 /// Return TargetLibraryInfo for function \p F.
602 TargetLibraryInfo *getTargetLibraryInfoForFunction(const Function &F) {
603 return AG.getAnalysis<TargetLibraryAnalysis>(F);
606 /// Return AliasAnalysis Result for function \p F.
607 AAResults *getAAResultsForFunction(const Function &F) {
608 return AG.getAnalysis<AAManager>(F);
611 /// Return the analysis result from a pass \p AP for function \p F.
612 template <typename AP>
613 typename AP::Result *getAnalysisResultForFunction(const Function &F) {
614 return AG.getAnalysis<AP>(F);
617 /// Return SCC size on call graph for function \p F.
618 unsigned getSccSize(const Function &F) {
619 if (!SccSizeOpt.hasValue())
621 return (SccSizeOpt.getValue())[&F];
624 /// Return datalayout used in the module.
625 const DataLayout &getDL() { return DL; }
628 /// A map type from functions to opcode to instruction maps.
629 using FuncInstOpcodeMapTy = DenseMap<const Function *, OpcodeInstMapTy>;
631 /// A map type from functions to their read or write instructions.
632 using FuncRWInstsMapTy = DenseMap<const Function *, InstructionVectorTy>;
634 /// A nested map that remembers all instructions in a function with a certain
635 /// instruction opcode (Instruction::getOpcode()).
636 FuncInstOpcodeMapTy FuncInstOpcodeMap;
638 /// A map from functions to their instructions that may read or write memory.
639 FuncRWInstsMapTy FuncRWInstsMap;
641 /// The datalayout used in the module.
642 const DataLayout &DL;
644 /// MustBeExecutedContextExplorer
645 MustBeExecutedContextExplorer Explorer;
647 /// Getters for analysis.
650 /// Cache result for scc size in the call graph
651 Optional<DenseMap<const Function *, unsigned>> SccSizeOpt;
653 /// Give the Attributor access to the members so
654 /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them.
655 friend struct Attributor;
658 /// The fixpoint analysis framework that orchestrates the attribute deduction.
660 /// The Attributor provides a general abstract analysis framework (guided
661 /// fixpoint iteration) as well as helper functions for the deduction of
662 /// (LLVM-IR) attributes. However, also other code properties can be deduced,
663 /// propagated, and ultimately manifested through the Attributor framework. This
664 /// is particularly useful if these properties interact with attributes and a
665 /// co-scheduled deduction allows to improve the solution. Even if not, thus if
666 /// attributes/properties are completely isolated, they should use the
667 /// Attributor framework to reduce the number of fixpoint iteration frameworks
668 /// in the code base. Note that the Attributor design makes sure that isolated
669 /// attributes are not impacted, in any way, by others derived at the same time
670 /// if there is no cross-reasoning performed.
672 /// The public facing interface of the Attributor is kept simple and basically
673 /// allows abstract attributes to one thing, query abstract attributes
674 /// in-flight. There are two reasons to do this:
675 /// a) The optimistic state of one abstract attribute can justify an
676 /// optimistic state of another, allowing to framework to end up with an
677 /// optimistic (=best possible) fixpoint instead of one based solely on
678 /// information in the IR.
679 /// b) This avoids reimplementing various kinds of lookups, e.g., to check
680 /// for existing IR attributes, in favor of a single lookups interface
681 /// provided by an abstract attribute subclass.
683 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
684 /// described in the file comment.
688 /// \param InfoCache Cache to hold various information accessible for
689 /// the abstract attributes.
690 /// \param DepRecomputeInterval Number of iterations until the dependences
691 /// between abstract attributes are recomputed.
692 /// \param Whitelist If not null, a set limiting the attribute opportunities.
693 Attributor(InformationCache &InfoCache, unsigned DepRecomputeInterval,
694 DenseSet<const char *> *Whitelist = nullptr)
695 : InfoCache(InfoCache), DepRecomputeInterval(DepRecomputeInterval),
696 Whitelist(Whitelist) {}
699 DeleteContainerPointers(AllAbstractAttributes);
700 for (auto &It : ArgumentReplacementMap)
701 DeleteContainerPointers(It.second);
704 /// Run the analyses until a fixpoint is reached or enforced (timeout).
706 /// The attributes registered with this Attributor can be used after as long
707 /// as the Attributor is not destroyed (it owns the attributes now).
709 /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED.
710 ChangeStatus run(Module &M);
712 /// Lookup an abstract attribute of type \p AAType at position \p IRP. While
713 /// no abstract attribute is found equivalent positions are checked, see
714 /// SubsumingPositionIterator. Thus, the returned abstract attribute
715 /// might be anchored at a different position, e.g., the callee if \p IRP is a
718 /// This method is the only (supported) way an abstract attribute can retrieve
719 /// information from another abstract attribute. As an example, take an
720 /// abstract attribute that determines the memory access behavior for a
721 /// argument (readnone, readonly, ...). It should use `getAAFor` to get the
722 /// most optimistic information for other abstract attributes in-flight, e.g.
723 /// the one reasoning about the "captured" state for the argument or the one
724 /// reasoning on the memory access behavior of the function as a whole.
726 /// If the flag \p TrackDependence is set to false the dependence from
727 /// \p QueryingAA to the return abstract attribute is not automatically
728 /// recorded. This should only be used if the caller will record the
729 /// dependence explicitly if necessary, thus if it the returned abstract
730 /// attribute is used for reasoning. To record the dependences explicitly use
731 /// the `Attributor::recordDependence` method.
732 template <typename AAType>
733 const AAType &getAAFor(const AbstractAttribute &QueryingAA,
734 const IRPosition &IRP, bool TrackDependence = true,
735 DepClassTy DepClass = DepClassTy::REQUIRED) {
736 return getOrCreateAAFor<AAType>(IRP, &QueryingAA, TrackDependence,
740 /// Explicitly record a dependence from \p FromAA to \p ToAA, that is if
741 /// \p FromAA changes \p ToAA should be updated as well.
743 /// This method should be used in conjunction with the `getAAFor` method and
744 /// with the TrackDependence flag passed to the method set to false. This can
745 /// be beneficial to avoid false dependences but it requires the users of
746 /// `getAAFor` to explicitly record true dependences through this method.
747 /// The \p DepClass flag indicates if the dependence is striclty necessary.
748 /// That means for required dependences, if \p FromAA changes to an invalid
749 /// state, \p ToAA can be moved to a pessimistic fixpoint because it required
750 /// information from \p FromAA but none are available anymore.
751 void recordDependence(const AbstractAttribute &FromAA,
752 const AbstractAttribute &ToAA, DepClassTy DepClass);
754 /// Introduce a new abstract attribute into the fixpoint analysis.
756 /// Note that ownership of the attribute is given to the Attributor. It will
757 /// invoke delete for the Attributor on destruction of the Attributor.
759 /// Attributes are identified by their IR position (AAType::getIRPosition())
760 /// and the address of their static member (see AAType::ID).
761 template <typename AAType> AAType ®isterAA(AAType &AA) {
762 static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
763 "Cannot register an attribute with a type not derived from "
764 "'AbstractAttribute'!");
765 // Put the attribute in the lookup map structure and the container we use to
766 // keep track of all attributes.
767 const IRPosition &IRP = AA.getIRPosition();
768 auto &KindToAbstractAttributeMap = AAMap[IRP];
769 assert(!KindToAbstractAttributeMap.count(&AAType::ID) &&
770 "Attribute already in map!");
771 KindToAbstractAttributeMap[&AAType::ID] = &AA;
772 AllAbstractAttributes.push_back(&AA);
776 /// Return the internal information cache.
777 InformationCache &getInfoCache() { return InfoCache; }
779 /// Determine opportunities to derive 'default' attributes in \p F and create
780 /// abstract attribute objects for them.
782 /// \param F The function that is checked for attribute opportunities.
784 /// Note that abstract attribute instances are generally created even if the
785 /// IR already contains the information they would deduce. The most important
786 /// reason for this is the single interface, the one of the abstract attribute
787 /// instance, which can be queried without the need to look at the IR in
789 void identifyDefaultAbstractAttributes(Function &F);
791 /// Initialize the information cache for queries regarding function \p F.
793 /// This method needs to be called for all function that might be looked at
794 /// through the information cache interface *prior* to looking at them.
795 void initializeInformationCache(Function &F);
797 /// Mark the internal function \p F as live.
799 /// This will trigger the identification and initialization of attributes for
801 void markLiveInternalFunction(const Function &F) {
802 assert(F.hasLocalLinkage() &&
803 "Only local linkage is assumed dead initially.");
805 identifyDefaultAbstractAttributes(const_cast<Function &>(F));
808 /// Record that \p U is to be replaces with \p NV after information was
809 /// manifested. This also triggers deletion of trivially dead istructions.
810 bool changeUseAfterManifest(Use &U, Value &NV) {
811 Value *&V = ToBeChangedUses[&U];
812 if (V && (V->stripPointerCasts() == NV.stripPointerCasts() ||
813 isa_and_nonnull<UndefValue>(V)))
815 assert((!V || V == &NV || isa<UndefValue>(NV)) &&
816 "Use was registered twice for replacement with different values!");
821 /// Helper function to replace all uses of \p V with \p NV. Return true if
822 /// there is any change.
823 bool changeValueAfterManifest(Value &V, Value &NV) {
824 bool Changed = false;
825 for (auto &U : V.uses())
826 Changed |= changeUseAfterManifest(U, NV);
831 /// Get pointer operand of memory accessing instruction. If \p I is
832 /// not a memory accessing instruction, return nullptr. If \p AllowVolatile,
833 /// is set to false and the instruction is volatile, return nullptr.
834 static const Value *getPointerOperand(const Instruction *I,
835 bool AllowVolatile) {
836 if (auto *LI = dyn_cast<LoadInst>(I)) {
837 if (!AllowVolatile && LI->isVolatile())
839 return LI->getPointerOperand();
842 if (auto *SI = dyn_cast<StoreInst>(I)) {
843 if (!AllowVolatile && SI->isVolatile())
845 return SI->getPointerOperand();
848 if (auto *CXI = dyn_cast<AtomicCmpXchgInst>(I)) {
849 if (!AllowVolatile && CXI->isVolatile())
851 return CXI->getPointerOperand();
854 if (auto *RMWI = dyn_cast<AtomicRMWInst>(I)) {
855 if (!AllowVolatile && RMWI->isVolatile())
857 return RMWI->getPointerOperand();
863 /// Record that \p I is to be replaced with `unreachable` after information
865 void changeToUnreachableAfterManifest(Instruction *I) {
866 ToBeChangedToUnreachableInsts.insert(I);
869 /// Record that \p II has at least one dead successor block. This information
870 /// is used, e.g., to replace \p II with a call, after information was
872 void registerInvokeWithDeadSuccessor(InvokeInst &II) {
873 InvokeWithDeadSuccessor.push_back(&II);
876 /// Record that \p I is deleted after information was manifested. This also
877 /// triggers deletion of trivially dead istructions.
878 void deleteAfterManifest(Instruction &I) { ToBeDeletedInsts.insert(&I); }
880 /// Record that \p BB is deleted after information was manifested. This also
881 /// triggers deletion of trivially dead istructions.
882 void deleteAfterManifest(BasicBlock &BB) { ToBeDeletedBlocks.insert(&BB); }
884 /// Record that \p F is deleted after information was manifested.
885 void deleteAfterManifest(Function &F) { ToBeDeletedFunctions.insert(&F); }
887 /// Return true if \p AA (or its context instruction) is assumed dead.
889 /// If \p LivenessAA is not provided it is queried.
890 bool isAssumedDead(const AbstractAttribute &AA, const AAIsDead *LivenessAA);
892 /// Check \p Pred on all (transitive) uses of \p V.
894 /// This method will evaluate \p Pred on all (transitive) uses of the
895 /// associated value and return true if \p Pred holds every time.
896 bool checkForAllUses(const function_ref<bool(const Use &, bool &)> &Pred,
897 const AbstractAttribute &QueryingAA, const Value &V);
899 /// Helper struct used in the communication between an abstract attribute (AA)
900 /// that wants to change the signature of a function and the Attributor which
901 /// applies the changes. The struct is partially initialized with the
902 /// information from the AA (see the constructor). All other members are
903 /// provided by the Attributor prior to invoking any callbacks.
904 struct ArgumentReplacementInfo {
905 /// Callee repair callback type
907 /// The function repair callback is invoked once to rewire the replacement
908 /// arguments in the body of the new function. The argument replacement info
909 /// is passed, as build from the registerFunctionSignatureRewrite call, as
910 /// well as the replacement function and an iteratore to the first
911 /// replacement argument.
912 using CalleeRepairCBTy = std::function<void(
913 const ArgumentReplacementInfo &, Function &, Function::arg_iterator)>;
915 /// Abstract call site (ACS) repair callback type
917 /// The abstract call site repair callback is invoked once on every abstract
918 /// call site of the replaced function (\see ReplacedFn). The callback needs
919 /// to provide the operands for the call to the new replacement function.
920 /// The number and type of the operands appended to the provided vector
921 /// (second argument) is defined by the number and types determined through
922 /// the replacement type vector (\see ReplacementTypes). The first argument
923 /// is the ArgumentReplacementInfo object registered with the Attributor
924 /// through the registerFunctionSignatureRewrite call.
925 using ACSRepairCBTy =
926 std::function<void(const ArgumentReplacementInfo &, AbstractCallSite,
927 SmallVectorImpl<Value *> &)>;
929 /// Simple getters, see the corresponding members for details.
932 Attributor &getAttributor() const { return A; }
933 const Function &getReplacedFn() const { return ReplacedFn; }
934 const Argument &getReplacedArg() const { return ReplacedArg; }
935 unsigned getNumReplacementArgs() const { return ReplacementTypes.size(); }
936 const SmallVectorImpl<Type *> &getReplacementTypes() const {
937 return ReplacementTypes;
943 /// Constructor that takes the argument to be replaced, the types of
944 /// the replacement arguments, as well as callbacks to repair the call sites
945 /// and new function after the replacement happened.
946 ArgumentReplacementInfo(Attributor &A, Argument &Arg,
947 ArrayRef<Type *> ReplacementTypes,
948 CalleeRepairCBTy &&CalleeRepairCB,
949 ACSRepairCBTy &&ACSRepairCB)
950 : A(A), ReplacedFn(*Arg.getParent()), ReplacedArg(Arg),
951 ReplacementTypes(ReplacementTypes.begin(), ReplacementTypes.end()),
952 CalleeRepairCB(std::move(CalleeRepairCB)),
953 ACSRepairCB(std::move(ACSRepairCB)) {}
955 /// Reference to the attributor to allow access from the callbacks.
958 /// The "old" function replaced by ReplacementFn.
959 const Function &ReplacedFn;
961 /// The "old" argument replaced by new ones defined via ReplacementTypes.
962 const Argument &ReplacedArg;
964 /// The types of the arguments replacing ReplacedArg.
965 const SmallVector<Type *, 8> ReplacementTypes;
967 /// Callee repair callback, see CalleeRepairCBTy.
968 const CalleeRepairCBTy CalleeRepairCB;
970 /// Abstract call site (ACS) repair callback, see ACSRepairCBTy.
971 const ACSRepairCBTy ACSRepairCB;
973 /// Allow access to the private members from the Attributor.
974 friend struct Attributor;
977 /// Register a rewrite for a function signature.
979 /// The argument \p Arg is replaced with new ones defined by the number,
980 /// order, and types in \p ReplacementTypes. The rewiring at the call sites is
981 /// done through \p ACSRepairCB and at the callee site through
982 /// \p CalleeRepairCB.
984 /// \returns True, if the replacement was registered, false otherwise.
985 bool registerFunctionSignatureRewrite(
986 Argument &Arg, ArrayRef<Type *> ReplacementTypes,
987 ArgumentReplacementInfo::CalleeRepairCBTy &&CalleeRepairCB,
988 ArgumentReplacementInfo::ACSRepairCBTy &&ACSRepairCB);
990 /// Check \p Pred on all function call sites.
992 /// This method will evaluate \p Pred on call sites and return
993 /// true if \p Pred holds in every call sites. However, this is only possible
994 /// all call sites are known, hence the function has internal linkage.
995 bool checkForAllCallSites(const function_ref<bool(AbstractCallSite)> &Pred,
996 const AbstractAttribute &QueryingAA,
997 bool RequireAllCallSites);
999 /// Check \p Pred on all values potentially returned by \p F.
1001 /// This method will evaluate \p Pred on all values potentially returned by
1002 /// the function associated with \p QueryingAA. The returned values are
1003 /// matched with their respective return instructions. Returns true if \p Pred
1004 /// holds on all of them.
1005 bool checkForAllReturnedValuesAndReturnInsts(
1006 const function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)>
1008 const AbstractAttribute &QueryingAA);
1010 /// Check \p Pred on all values potentially returned by the function
1011 /// associated with \p QueryingAA.
1013 /// This is the context insensitive version of the method above.
1014 bool checkForAllReturnedValues(const function_ref<bool(Value &)> &Pred,
1015 const AbstractAttribute &QueryingAA);
1017 /// Check \p Pred on all instructions with an opcode present in \p Opcodes.
1019 /// This method will evaluate \p Pred on all instructions with an opcode
1020 /// present in \p Opcode and return true if \p Pred holds on all of them.
1021 bool checkForAllInstructions(const function_ref<bool(Instruction &)> &Pred,
1022 const AbstractAttribute &QueryingAA,
1023 const ArrayRef<unsigned> &Opcodes);
1025 /// Check \p Pred on all call-like instructions (=CallBased derived).
1027 /// See checkForAllCallLikeInstructions(...) for more information.
1029 checkForAllCallLikeInstructions(const function_ref<bool(Instruction &)> &Pred,
1030 const AbstractAttribute &QueryingAA) {
1031 return checkForAllInstructions(Pred, QueryingAA,
1032 {(unsigned)Instruction::Invoke,
1033 (unsigned)Instruction::CallBr,
1034 (unsigned)Instruction::Call});
1037 /// Check \p Pred on all Read/Write instructions.
1039 /// This method will evaluate \p Pred on all instructions that read or write
1040 /// to memory present in the information cache and return true if \p Pred
1041 /// holds on all of them.
1042 bool checkForAllReadWriteInstructions(
1043 const llvm::function_ref<bool(Instruction &)> &Pred,
1044 AbstractAttribute &QueryingAA);
1046 /// Return the data layout associated with the anchor scope.
1047 const DataLayout &getDataLayout() const { return InfoCache.DL; }
1050 /// Check \p Pred on all call sites of \p Fn.
1052 /// This method will evaluate \p Pred on call sites and return
1053 /// true if \p Pred holds in every call sites. However, this is only possible
1054 /// all call sites are known, hence the function has internal linkage.
1055 bool checkForAllCallSites(const function_ref<bool(AbstractCallSite)> &Pred,
1056 const Function &Fn, bool RequireAllCallSites,
1057 const AbstractAttribute *QueryingAA);
1059 /// The private version of getAAFor that allows to omit a querying abstract
1060 /// attribute. See also the public getAAFor method.
1061 template <typename AAType>
1062 const AAType &getOrCreateAAFor(const IRPosition &IRP,
1063 const AbstractAttribute *QueryingAA = nullptr,
1064 bool TrackDependence = false,
1065 DepClassTy DepClass = DepClassTy::OPTIONAL) {
1066 if (const AAType *AAPtr =
1067 lookupAAFor<AAType>(IRP, QueryingAA, TrackDependence))
1070 // No matching attribute found, create one.
1071 // Use the static create method.
1072 auto &AA = AAType::createForPosition(IRP, *this);
1075 // For now we ignore naked and optnone functions.
1076 bool Invalidate = Whitelist && !Whitelist->count(&AAType::ID);
1077 if (const Function *Fn = IRP.getAnchorScope())
1078 Invalidate |= Fn->hasFnAttribute(Attribute::Naked) ||
1079 Fn->hasFnAttribute(Attribute::OptimizeNone);
1081 // Bootstrap the new attribute with an initial update to propagate
1082 // information, e.g., function -> call site. If it is not on a given
1083 // whitelist we will not perform updates at all.
1085 AA.getState().indicatePessimisticFixpoint();
1089 AA.initialize(*this);
1092 if (TrackDependence && AA.getState().isValidState())
1093 recordDependence(AA, const_cast<AbstractAttribute &>(*QueryingAA),
1098 /// Return the attribute of \p AAType for \p IRP if existing.
1099 template <typename AAType>
1100 const AAType *lookupAAFor(const IRPosition &IRP,
1101 const AbstractAttribute *QueryingAA = nullptr,
1102 bool TrackDependence = false,
1103 DepClassTy DepClass = DepClassTy::OPTIONAL) {
1104 static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
1105 "Cannot query an attribute with a type not derived from "
1106 "'AbstractAttribute'!");
1107 assert((QueryingAA || !TrackDependence) &&
1108 "Cannot track dependences without a QueryingAA!");
1110 // Lookup the abstract attribute of type AAType. If found, return it after
1111 // registering a dependence of QueryingAA on the one returned attribute.
1112 const auto &KindToAbstractAttributeMap = AAMap.lookup(IRP);
1113 if (AAType *AA = static_cast<AAType *>(
1114 KindToAbstractAttributeMap.lookup(&AAType::ID))) {
1115 // Do not register a dependence on an attribute with an invalid state.
1116 if (TrackDependence && AA->getState().isValidState())
1117 recordDependence(*AA, const_cast<AbstractAttribute &>(*QueryingAA),
1124 /// Apply all requested function signature rewrites
1125 /// (\see registerFunctionSignatureRewrite) and return Changed if the module
1127 ChangeStatus rewriteFunctionSignatures();
1129 /// The set of all abstract attributes.
1131 using AAVector = SmallVector<AbstractAttribute *, 64>;
1132 AAVector AllAbstractAttributes;
1135 /// A nested map to lookup abstract attributes based on the argument position
1136 /// on the outer level, and the addresses of the static member (AAType::ID) on
1137 /// the inner level.
1139 using KindToAbstractAttributeMap =
1140 DenseMap<const char *, AbstractAttribute *>;
1141 DenseMap<IRPosition, KindToAbstractAttributeMap> AAMap;
1144 /// A map from abstract attributes to the ones that queried them through calls
1145 /// to the getAAFor<...>(...) method.
1147 struct QueryMapValueTy {
1148 /// Set of abstract attributes which were used but not necessarily required
1149 /// for a potential optimistic state.
1150 SetVector<AbstractAttribute *> OptionalAAs;
1152 /// Set of abstract attributes which were used and which were necessarily
1153 /// required for any potential optimistic state.
1154 SetVector<AbstractAttribute *> RequiredAAs;
1156 using QueryMapTy = MapVector<const AbstractAttribute *, QueryMapValueTy>;
1157 QueryMapTy QueryMap;
1160 /// Map to remember all requested signature changes (= argument replacements).
1161 DenseMap<Function *, SmallVector<ArgumentReplacementInfo *, 8>>
1162 ArgumentReplacementMap;
1164 /// The information cache that holds pre-processed (LLVM-IR) information.
1165 InformationCache &InfoCache;
1167 /// Set if the attribute currently updated did query a non-fix attribute.
1168 bool QueriedNonFixAA;
1170 /// Number of iterations until the dependences between abstract attributes are
1172 const unsigned DepRecomputeInterval;
1174 /// If not null, a set limiting the attribute opportunities.
1175 const DenseSet<const char *> *Whitelist;
1177 /// A set to remember the functions we already assume to be live and visited.
1178 DenseSet<const Function *> VisitedFunctions;
1180 /// Uses we replace with a new value after manifest is done. We will remove
1181 /// then trivially dead instructions as well.
1182 DenseMap<Use *, Value *> ToBeChangedUses;
1184 /// Instructions we replace with `unreachable` insts after manifest is done.
1185 SmallDenseSet<WeakVH, 16> ToBeChangedToUnreachableInsts;
1187 /// Invoke instructions with at least a single dead successor block.
1188 SmallVector<WeakVH, 16> InvokeWithDeadSuccessor;
1190 /// Functions, blocks, and instructions we delete after manifest is done.
1193 SmallPtrSet<Function *, 8> ToBeDeletedFunctions;
1194 SmallPtrSet<BasicBlock *, 8> ToBeDeletedBlocks;
1195 SmallPtrSet<Instruction *, 8> ToBeDeletedInsts;
1199 /// An interface to query the internal state of an abstract attribute.
1201 /// The abstract state is a minimal interface that allows the Attributor to
1202 /// communicate with the abstract attributes about their internal state without
1203 /// enforcing or exposing implementation details, e.g., the (existence of an)
1204 /// underlying lattice.
1206 /// It is sufficient to be able to query if a state is (1) valid or invalid, (2)
1207 /// at a fixpoint, and to indicate to the state that (3) an optimistic fixpoint
1208 /// was reached or (4) a pessimistic fixpoint was enforced.
1210 /// All methods need to be implemented by the subclass. For the common use case,
1211 /// a single boolean state or a bit-encoded state, the BooleanState and
1212 /// {Inc,Dec,Bit}IntegerState classes are already provided. An abstract
1213 /// attribute can inherit from them to get the abstract state interface and
1214 /// additional methods to directly modify the state based if needed. See the
1215 /// class comments for help.
1216 struct AbstractState {
1217 virtual ~AbstractState() {}
1219 /// Return if this abstract state is in a valid state. If false, no
1220 /// information provided should be used.
1221 virtual bool isValidState() const = 0;
1223 /// Return if this abstract state is fixed, thus does not need to be updated
1224 /// if information changes as it cannot change itself.
1225 virtual bool isAtFixpoint() const = 0;
1227 /// Indicate that the abstract state should converge to the optimistic state.
1229 /// This will usually make the optimistically assumed state the known to be
1232 /// \returns ChangeStatus::UNCHANGED as the assumed value should not change.
1233 virtual ChangeStatus indicateOptimisticFixpoint() = 0;
1235 /// Indicate that the abstract state should converge to the pessimistic state.
1237 /// This will usually revert the optimistically assumed state to the known to
1240 /// \returns ChangeStatus::CHANGED as the assumed value may change.
1241 virtual ChangeStatus indicatePessimisticFixpoint() = 0;
1244 /// Simple state with integers encoding.
1246 /// The interface ensures that the assumed bits are always a subset of the known
1247 /// bits. Users can only add known bits and, except through adding known bits,
1248 /// they can only remove assumed bits. This should guarantee monotoniticy and
1249 /// thereby the existence of a fixpoint (if used corretly). The fixpoint is
1250 /// reached when the assumed and known state/bits are equal. Users can
1251 /// force/inidicate a fixpoint. If an optimistic one is indicated, the known
1252 /// state will catch up with the assumed one, for a pessimistic fixpoint it is
1253 /// the other way around.
1254 template <typename base_ty, base_ty BestState, base_ty WorstState>
1255 struct IntegerStateBase : public AbstractState {
1256 using base_t = base_ty;
1258 /// Return the best possible representable state.
1259 static constexpr base_t getBestState() { return BestState; }
1261 /// Return the worst possible representable state.
1262 static constexpr base_t getWorstState() { return WorstState; }
1264 /// See AbstractState::isValidState()
1265 /// NOTE: For now we simply pretend that the worst possible state is invalid.
1266 bool isValidState() const override { return Assumed != getWorstState(); }
1268 /// See AbstractState::isAtFixpoint()
1269 bool isAtFixpoint() const override { return Assumed == Known; }
1271 /// See AbstractState::indicateOptimisticFixpoint(...)
1272 ChangeStatus indicateOptimisticFixpoint() override {
1274 return ChangeStatus::UNCHANGED;
1277 /// See AbstractState::indicatePessimisticFixpoint(...)
1278 ChangeStatus indicatePessimisticFixpoint() override {
1280 return ChangeStatus::CHANGED;
1283 /// Return the known state encoding
1284 base_t getKnown() const { return Known; }
1286 /// Return the assumed state encoding.
1287 base_t getAssumed() const { return Assumed; }
1289 /// Equality for IntegerStateBase.
1291 operator==(const IntegerStateBase<base_t, BestState, WorstState> &R) const {
1292 return this->getAssumed() == R.getAssumed() &&
1293 this->getKnown() == R.getKnown();
1296 /// Inequality for IntegerStateBase.
1298 operator!=(const IntegerStateBase<base_t, BestState, WorstState> &R) const {
1299 return !(*this == R);
1302 /// "Clamp" this state with \p R. The result is subtype dependent but it is
1303 /// intended that only information assumed in both states will be assumed in
1304 /// this one afterwards.
1305 void operator^=(const IntegerStateBase<base_t, BestState, WorstState> &R) {
1306 handleNewAssumedValue(R.getAssumed());
1309 void operator|=(const IntegerStateBase<base_t, BestState, WorstState> &R) {
1310 joinOR(R.getAssumed(), R.getKnown());
1313 void operator&=(const IntegerStateBase<base_t, BestState, WorstState> &R) {
1314 joinAND(R.getAssumed(), R.getKnown());
1318 /// Handle a new assumed value \p Value. Subtype dependent.
1319 virtual void handleNewAssumedValue(base_t Value) = 0;
1321 /// Handle a new known value \p Value. Subtype dependent.
1322 virtual void handleNewKnownValue(base_t Value) = 0;
1324 /// Handle a value \p Value. Subtype dependent.
1325 virtual void joinOR(base_t AssumedValue, base_t KnownValue) = 0;
1327 /// Handle a new assumed value \p Value. Subtype dependent.
1328 virtual void joinAND(base_t AssumedValue, base_t KnownValue) = 0;
1330 /// The known state encoding in an integer of type base_t.
1331 base_t Known = getWorstState();
1333 /// The assumed state encoding in an integer of type base_t.
1334 base_t Assumed = getBestState();
1337 /// Specialization of the integer state for a bit-wise encoding.
1338 template <typename base_ty = uint32_t, base_ty BestState = ~base_ty(0),
1339 base_ty WorstState = 0>
1340 struct BitIntegerState
1341 : public IntegerStateBase<base_ty, BestState, WorstState> {
1342 using base_t = base_ty;
1344 /// Return true if the bits set in \p BitsEncoding are "known bits".
1345 bool isKnown(base_t BitsEncoding) const {
1346 return (this->Known & BitsEncoding) == BitsEncoding;
1349 /// Return true if the bits set in \p BitsEncoding are "assumed bits".
1350 bool isAssumed(base_t BitsEncoding) const {
1351 return (this->Assumed & BitsEncoding) == BitsEncoding;
1354 /// Add the bits in \p BitsEncoding to the "known bits".
1355 BitIntegerState &addKnownBits(base_t Bits) {
1356 // Make sure we never miss any "known bits".
1357 this->Assumed |= Bits;
1358 this->Known |= Bits;
1362 /// Remove the bits in \p BitsEncoding from the "assumed bits" if not known.
1363 BitIntegerState &removeAssumedBits(base_t BitsEncoding) {
1364 return intersectAssumedBits(~BitsEncoding);
1367 /// Remove the bits in \p BitsEncoding from the "known bits".
1368 BitIntegerState &removeKnownBits(base_t BitsEncoding) {
1369 this->Known = (this->Known & ~BitsEncoding);
1373 /// Keep only "assumed bits" also set in \p BitsEncoding but all known ones.
1374 BitIntegerState &intersectAssumedBits(base_t BitsEncoding) {
1375 // Make sure we never loose any "known bits".
1376 this->Assumed = (this->Assumed & BitsEncoding) | this->Known;
1381 void handleNewAssumedValue(base_t Value) override {
1382 intersectAssumedBits(Value);
1384 void handleNewKnownValue(base_t Value) override { addKnownBits(Value); }
1385 void joinOR(base_t AssumedValue, base_t KnownValue) override {
1386 this->Known |= KnownValue;
1387 this->Assumed |= AssumedValue;
1389 void joinAND(base_t AssumedValue, base_t KnownValue) override {
1390 this->Known &= KnownValue;
1391 this->Assumed &= AssumedValue;
1395 /// Specialization of the integer state for an increasing value, hence ~0u is
1396 /// the best state and 0 the worst.
1397 template <typename base_ty = uint32_t, base_ty BestState = ~base_ty(0),
1398 base_ty WorstState = 0>
1399 struct IncIntegerState
1400 : public IntegerStateBase<base_ty, BestState, WorstState> {
1401 using base_t = base_ty;
1403 /// Take minimum of assumed and \p Value.
1404 IncIntegerState &takeAssumedMinimum(base_t Value) {
1405 // Make sure we never loose "known value".
1406 this->Assumed = std::max(std::min(this->Assumed, Value), this->Known);
1410 /// Take maximum of known and \p Value.
1411 IncIntegerState &takeKnownMaximum(base_t Value) {
1412 // Make sure we never loose "known value".
1413 this->Assumed = std::max(Value, this->Assumed);
1414 this->Known = std::max(Value, this->Known);
1419 void handleNewAssumedValue(base_t Value) override {
1420 takeAssumedMinimum(Value);
1422 void handleNewKnownValue(base_t Value) override { takeKnownMaximum(Value); }
1423 void joinOR(base_t AssumedValue, base_t KnownValue) override {
1424 this->Known = std::max(this->Known, KnownValue);
1425 this->Assumed = std::max(this->Assumed, AssumedValue);
1427 void joinAND(base_t AssumedValue, base_t KnownValue) override {
1428 this->Known = std::min(this->Known, KnownValue);
1429 this->Assumed = std::min(this->Assumed, AssumedValue);
1433 /// Specialization of the integer state for a decreasing value, hence 0 is the
1434 /// best state and ~0u the worst.
1435 template <typename base_ty = uint32_t>
1436 struct DecIntegerState : public IntegerStateBase<base_ty, 0, ~base_ty(0)> {
1437 using base_t = base_ty;
1439 /// Take maximum of assumed and \p Value.
1440 DecIntegerState &takeAssumedMaximum(base_t Value) {
1441 // Make sure we never loose "known value".
1442 this->Assumed = std::min(std::max(this->Assumed, Value), this->Known);
1446 /// Take minimum of known and \p Value.
1447 DecIntegerState &takeKnownMinimum(base_t Value) {
1448 // Make sure we never loose "known value".
1449 this->Assumed = std::min(Value, this->Assumed);
1450 this->Known = std::min(Value, this->Known);
1455 void handleNewAssumedValue(base_t Value) override {
1456 takeAssumedMaximum(Value);
1458 void handleNewKnownValue(base_t Value) override { takeKnownMinimum(Value); }
1459 void joinOR(base_t AssumedValue, base_t KnownValue) override {
1460 this->Assumed = std::min(this->Assumed, KnownValue);
1461 this->Assumed = std::min(this->Assumed, AssumedValue);
1463 void joinAND(base_t AssumedValue, base_t KnownValue) override {
1464 this->Assumed = std::max(this->Assumed, KnownValue);
1465 this->Assumed = std::max(this->Assumed, AssumedValue);
1469 /// Simple wrapper for a single bit (boolean) state.
1470 struct BooleanState : public IntegerStateBase<bool, 1, 0> {
1471 using base_t = IntegerStateBase::base_t;
1473 /// Set the assumed value to \p Value but never below the known one.
1474 void setAssumed(bool Value) { Assumed &= (Known | Value); }
1476 /// Set the known and asssumed value to \p Value.
1477 void setKnown(bool Value) {
1482 /// Return true if the state is assumed to hold.
1483 bool isAssumed() const { return getAssumed(); }
1485 /// Return true if the state is known to hold.
1486 bool isKnown() const { return getKnown(); }
1489 void handleNewAssumedValue(base_t Value) override {
1493 void handleNewKnownValue(base_t Value) override {
1495 Known = (Assumed = Value);
1497 void joinOR(base_t AssumedValue, base_t KnownValue) override {
1498 Known |= KnownValue;
1499 Assumed |= AssumedValue;
1501 void joinAND(base_t AssumedValue, base_t KnownValue) override {
1502 Known &= KnownValue;
1503 Assumed &= AssumedValue;
1507 /// State for an integer range.
1508 struct IntegerRangeState : public AbstractState {
1510 /// Bitwidth of the associated value.
1513 /// State representing assumed range, initially set to empty.
1514 ConstantRange Assumed;
1516 /// State representing known range, initially set to [-inf, inf].
1517 ConstantRange Known;
1519 IntegerRangeState(uint32_t BitWidth)
1520 : BitWidth(BitWidth), Assumed(ConstantRange::getEmpty(BitWidth)),
1521 Known(ConstantRange::getFull(BitWidth)) {}
1523 /// Return the worst possible representable state.
1524 static ConstantRange getWorstState(uint32_t BitWidth) {
1525 return ConstantRange::getFull(BitWidth);
1528 /// Return the best possible representable state.
1529 static ConstantRange getBestState(uint32_t BitWidth) {
1530 return ConstantRange::getEmpty(BitWidth);
1533 /// Return associated values' bit width.
1534 uint32_t getBitWidth() const { return BitWidth; }
1536 /// See AbstractState::isValidState()
1537 bool isValidState() const override {
1538 return BitWidth > 0 && !Assumed.isFullSet();
1541 /// See AbstractState::isAtFixpoint()
1542 bool isAtFixpoint() const override { return Assumed == Known; }
1544 /// See AbstractState::indicateOptimisticFixpoint(...)
1545 ChangeStatus indicateOptimisticFixpoint() override {
1547 return ChangeStatus::CHANGED;
1550 /// See AbstractState::indicatePessimisticFixpoint(...)
1551 ChangeStatus indicatePessimisticFixpoint() override {
1553 return ChangeStatus::CHANGED;
1556 /// Return the known state encoding
1557 ConstantRange getKnown() const { return Known; }
1559 /// Return the assumed state encoding.
1560 ConstantRange getAssumed() const { return Assumed; }
1562 /// Unite assumed range with the passed state.
1563 void unionAssumed(const ConstantRange &R) {
1564 // Don't loose a known range.
1565 Assumed = Assumed.unionWith(R).intersectWith(Known);
1568 /// See IntegerRangeState::unionAssumed(..).
1569 void unionAssumed(const IntegerRangeState &R) {
1570 unionAssumed(R.getAssumed());
1573 /// Unite known range with the passed state.
1574 void unionKnown(const ConstantRange &R) {
1575 // Don't loose a known range.
1576 Known = Known.unionWith(R);
1577 Assumed = Assumed.unionWith(Known);
1580 /// See IntegerRangeState::unionKnown(..).
1581 void unionKnown(const IntegerRangeState &R) { unionKnown(R.getKnown()); }
1583 /// Intersect known range with the passed state.
1584 void intersectKnown(const ConstantRange &R) {
1585 Assumed = Assumed.intersectWith(R);
1586 Known = Known.intersectWith(R);
1589 /// See IntegerRangeState::intersectKnown(..).
1590 void intersectKnown(const IntegerRangeState &R) {
1591 intersectKnown(R.getKnown());
1594 /// Equality for IntegerRangeState.
1595 bool operator==(const IntegerRangeState &R) const {
1596 return getAssumed() == R.getAssumed() && getKnown() == R.getKnown();
1599 /// "Clamp" this state with \p R. The result is subtype dependent but it is
1600 /// intended that only information assumed in both states will be assumed in
1601 /// this one afterwards.
1602 IntegerRangeState operator^=(const IntegerRangeState &R) {
1603 // NOTE: `^=` operator seems like `intersect` but in this case, we need to
1609 IntegerRangeState operator&=(const IntegerRangeState &R) {
1610 // NOTE: `&=` operator seems like `intersect` but in this case, we need to
1617 /// Helper struct necessary as the modular build fails if the virtual method
1618 /// IRAttribute::manifest is defined in the Attributor.cpp.
1619 struct IRAttributeManifest {
1620 static ChangeStatus manifestAttrs(Attributor &A, const IRPosition &IRP,
1621 const ArrayRef<Attribute> &DeducedAttrs);
1624 /// Helper to tie a abstract state implementation to an abstract attribute.
1625 template <typename StateTy, typename Base>
1626 struct StateWrapper : public StateTy, public Base {
1627 /// Provide static access to the type of the state.
1628 using StateType = StateTy;
1630 /// See AbstractAttribute::getState(...).
1631 StateType &getState() override { return *this; }
1633 /// See AbstractAttribute::getState(...).
1634 const AbstractState &getState() const override { return *this; }
1637 /// Helper class that provides common functionality to manifest IR attributes.
1638 template <Attribute::AttrKind AK, typename Base>
1639 struct IRAttribute : public IRPosition, public Base {
1640 IRAttribute(const IRPosition &IRP) : IRPosition(IRP) {}
1643 /// See AbstractAttribute::initialize(...).
1644 virtual void initialize(Attributor &A) override {
1645 const IRPosition &IRP = this->getIRPosition();
1646 if (isa<UndefValue>(IRP.getAssociatedValue()) || hasAttr(getAttrKind())) {
1647 this->getState().indicateOptimisticFixpoint();
1651 bool IsFnInterface = IRP.isFnInterfaceKind();
1652 const Function *FnScope = IRP.getAnchorScope();
1653 // TODO: Not all attributes require an exact definition. Find a way to
1654 // enable deduction for some but not all attributes in case the
1655 // definition might be changed at runtime, see also
1656 // http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
1657 // TODO: We could always determine abstract attributes and if sufficient
1658 // information was found we could duplicate the functions that do not
1659 // have an exact definition.
1660 if (IsFnInterface && (!FnScope || !FnScope->hasExactDefinition()))
1661 this->getState().indicatePessimisticFixpoint();
1664 /// See AbstractAttribute::manifest(...).
1665 ChangeStatus manifest(Attributor &A) override {
1666 if (isa<UndefValue>(getIRPosition().getAssociatedValue()))
1667 return ChangeStatus::UNCHANGED;
1668 SmallVector<Attribute, 4> DeducedAttrs;
1669 getDeducedAttributes(getAnchorValue().getContext(), DeducedAttrs);
1670 return IRAttributeManifest::manifestAttrs(A, getIRPosition(), DeducedAttrs);
1673 /// Return the kind that identifies the abstract attribute implementation.
1674 Attribute::AttrKind getAttrKind() const { return AK; }
1676 /// Return the deduced attributes in \p Attrs.
1677 virtual void getDeducedAttributes(LLVMContext &Ctx,
1678 SmallVectorImpl<Attribute> &Attrs) const {
1679 Attrs.emplace_back(Attribute::get(Ctx, getAttrKind()));
1682 /// Return an IR position, see struct IRPosition.
1683 const IRPosition &getIRPosition() const override { return *this; }
1686 /// Base struct for all "concrete attribute" deductions.
1688 /// The abstract attribute is a minimal interface that allows the Attributor to
1689 /// orchestrate the abstract/fixpoint analysis. The design allows to hide away
1690 /// implementation choices made for the subclasses but also to structure their
1691 /// implementation and simplify the use of other abstract attributes in-flight.
1693 /// To allow easy creation of new attributes, most methods have default
1694 /// implementations. The ones that do not are generally straight forward, except
1695 /// `AbstractAttribute::updateImpl` which is the location of most reasoning
1696 /// associated with the abstract attribute. The update is invoked by the
1697 /// Attributor in case the situation used to justify the current optimistic
1698 /// state might have changed. The Attributor determines this automatically
1699 /// by monitoring the `Attributor::getAAFor` calls made by abstract attributes.
1701 /// The `updateImpl` method should inspect the IR and other abstract attributes
1702 /// in-flight to justify the best possible (=optimistic) state. The actual
1703 /// implementation is, similar to the underlying abstract state encoding, not
1704 /// exposed. In the most common case, the `updateImpl` will go through a list of
1705 /// reasons why its optimistic state is valid given the current information. If
1706 /// any combination of them holds and is sufficient to justify the current
1707 /// optimistic state, the method shall return UNCHAGED. If not, the optimistic
1708 /// state is adjusted to the situation and the method shall return CHANGED.
1710 /// If the manifestation of the "concrete attribute" deduced by the subclass
1711 /// differs from the "default" behavior, which is a (set of) LLVM-IR
1712 /// attribute(s) for an argument, call site argument, function return value, or
1713 /// function, the `AbstractAttribute::manifest` method should be overloaded.
1715 /// NOTE: If the state obtained via getState() is INVALID, thus if
1716 /// AbstractAttribute::getState().isValidState() returns false, no
1717 /// information provided by the methods of this class should be used.
1718 /// NOTE: The Attributor currently has certain limitations to what we can do.
1719 /// As a general rule of thumb, "concrete" abstract attributes should *for
1720 /// now* only perform "backward" information propagation. That means
1721 /// optimistic information obtained through abstract attributes should
1722 /// only be used at positions that precede the origin of the information
1723 /// with regards to the program flow. More practically, information can
1724 /// *now* be propagated from instructions to their enclosing function, but
1725 /// *not* from call sites to the called function. The mechanisms to allow
1726 /// both directions will be added in the future.
1727 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
1728 /// described in the file comment.
1729 struct AbstractAttribute {
1730 using StateType = AbstractState;
1732 /// Virtual destructor.
1733 virtual ~AbstractAttribute() {}
1735 /// Initialize the state with the information in the Attributor \p A.
1737 /// This function is called by the Attributor once all abstract attributes
1738 /// have been identified. It can and shall be used for task like:
1739 /// - identify existing knowledge in the IR and use it for the "known state"
1740 /// - perform any work that is not going to change over time, e.g., determine
1741 /// a subset of the IR, or attributes in-flight, that have to be looked at
1742 /// in the `updateImpl` method.
1743 virtual void initialize(Attributor &A) {}
1745 /// Return the internal abstract state for inspection.
1746 virtual StateType &getState() = 0;
1747 virtual const StateType &getState() const = 0;
1749 /// Return an IR position, see struct IRPosition.
1750 virtual const IRPosition &getIRPosition() const = 0;
1752 /// Helper functions, for debug purposes only.
1754 virtual void print(raw_ostream &OS) const;
1755 void dump() const { print(dbgs()); }
1757 /// This function should return the "summarized" assumed state as string.
1758 virtual const std::string getAsStr() const = 0;
1761 /// Allow the Attributor access to the protected methods.
1762 friend struct Attributor;
1765 /// Hook for the Attributor to trigger an update of the internal state.
1767 /// If this attribute is already fixed, this method will return UNCHANGED,
1768 /// otherwise it delegates to `AbstractAttribute::updateImpl`.
1770 /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
1771 ChangeStatus update(Attributor &A);
1773 /// Hook for the Attributor to trigger the manifestation of the information
1774 /// represented by the abstract attribute in the LLVM-IR.
1776 /// \Return CHANGED if the IR was altered, otherwise UNCHANGED.
1777 virtual ChangeStatus manifest(Attributor &A) {
1778 return ChangeStatus::UNCHANGED;
1781 /// Hook to enable custom statistic tracking, called after manifest that
1782 /// resulted in a change if statistics are enabled.
1784 /// We require subclasses to provide an implementation so we remember to
1785 /// add statistics for them.
1786 virtual void trackStatistics() const = 0;
1788 /// The actual update/transfer function which has to be implemented by the
1789 /// derived classes.
1791 /// If it is called, the environment has changed and we have to determine if
1792 /// the current information is still valid or adjust it otherwise.
1794 /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
1795 virtual ChangeStatus updateImpl(Attributor &A) = 0;
1798 /// Forward declarations of output streams for debug purposes.
1801 raw_ostream &operator<<(raw_ostream &OS, const AbstractAttribute &AA);
1802 raw_ostream &operator<<(raw_ostream &OS, ChangeStatus S);
1803 raw_ostream &operator<<(raw_ostream &OS, IRPosition::Kind);
1804 raw_ostream &operator<<(raw_ostream &OS, const IRPosition &);
1805 raw_ostream &operator<<(raw_ostream &OS, const AbstractState &State);
1806 template <typename base_ty, base_ty BestState, base_ty WorstState>
1808 operator<<(raw_ostream &OS,
1809 const IntegerStateBase<base_ty, BestState, WorstState> &State);
1810 raw_ostream &operator<<(raw_ostream &OS, const IntegerRangeState &State);
1813 struct AttributorPass : public PassInfoMixin<AttributorPass> {
1814 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
1817 Pass *createAttributorLegacyPass();
1819 /// ----------------------------------------------------------------------------
1820 /// Abstract Attribute Classes
1821 /// ----------------------------------------------------------------------------
1823 /// An abstract attribute for the returned values of a function.
1824 struct AAReturnedValues
1825 : public IRAttribute<Attribute::Returned, AbstractAttribute> {
1826 AAReturnedValues(const IRPosition &IRP) : IRAttribute(IRP) {}
1828 /// Return an assumed unique return value if a single candidate is found. If
1829 /// there cannot be one, return a nullptr. If it is not clear yet, return the
1830 /// Optional::NoneType.
1831 Optional<Value *> getAssumedUniqueReturnValue(Attributor &A) const;
1833 /// Check \p Pred on all returned values.
1835 /// This method will evaluate \p Pred on returned values and return
1836 /// true if (1) all returned values are known, and (2) \p Pred returned true
1837 /// for all returned values.
1839 /// Note: Unlike the Attributor::checkForAllReturnedValuesAndReturnInsts
1840 /// method, this one will not filter dead return instructions.
1841 virtual bool checkForAllReturnedValuesAndReturnInsts(
1842 const function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)>
1846 MapVector<Value *, SmallSetVector<ReturnInst *, 4>>::iterator;
1847 using const_iterator =
1848 MapVector<Value *, SmallSetVector<ReturnInst *, 4>>::const_iterator;
1849 virtual llvm::iterator_range<iterator> returned_values() = 0;
1850 virtual llvm::iterator_range<const_iterator> returned_values() const = 0;
1852 virtual size_t getNumReturnValues() const = 0;
1853 virtual const SmallSetVector<CallBase *, 4> &getUnresolvedCalls() const = 0;
1855 /// Create an abstract attribute view for the position \p IRP.
1856 static AAReturnedValues &createForPosition(const IRPosition &IRP,
1859 /// Unique ID (due to the unique address)
1860 static const char ID;
1864 : public IRAttribute<Attribute::NoUnwind,
1865 StateWrapper<BooleanState, AbstractAttribute>> {
1866 AANoUnwind(const IRPosition &IRP) : IRAttribute(IRP) {}
1868 /// Returns true if nounwind is assumed.
1869 bool isAssumedNoUnwind() const { return getAssumed(); }
1871 /// Returns true if nounwind is known.
1872 bool isKnownNoUnwind() const { return getKnown(); }
1874 /// Create an abstract attribute view for the position \p IRP.
1875 static AANoUnwind &createForPosition(const IRPosition &IRP, Attributor &A);
1877 /// Unique ID (due to the unique address)
1878 static const char ID;
1882 : public IRAttribute<Attribute::NoSync,
1883 StateWrapper<BooleanState, AbstractAttribute>> {
1884 AANoSync(const IRPosition &IRP) : IRAttribute(IRP) {}
1886 /// Returns true if "nosync" is assumed.
1887 bool isAssumedNoSync() const { return getAssumed(); }
1889 /// Returns true if "nosync" is known.
1890 bool isKnownNoSync() const { return getKnown(); }
1892 /// Create an abstract attribute view for the position \p IRP.
1893 static AANoSync &createForPosition(const IRPosition &IRP, Attributor &A);
1895 /// Unique ID (due to the unique address)
1896 static const char ID;
1899 /// An abstract interface for all nonnull attributes.
1901 : public IRAttribute<Attribute::NonNull,
1902 StateWrapper<BooleanState, AbstractAttribute>> {
1903 AANonNull(const IRPosition &IRP) : IRAttribute(IRP) {}
1905 /// Return true if we assume that the underlying value is nonnull.
1906 bool isAssumedNonNull() const { return getAssumed(); }
1908 /// Return true if we know that underlying value is nonnull.
1909 bool isKnownNonNull() const { return getKnown(); }
1911 /// Create an abstract attribute view for the position \p IRP.
1912 static AANonNull &createForPosition(const IRPosition &IRP, Attributor &A);
1914 /// Unique ID (due to the unique address)
1915 static const char ID;
1918 /// An abstract attribute for norecurse.
1920 : public IRAttribute<Attribute::NoRecurse,
1921 StateWrapper<BooleanState, AbstractAttribute>> {
1922 AANoRecurse(const IRPosition &IRP) : IRAttribute(IRP) {}
1924 /// Return true if "norecurse" is assumed.
1925 bool isAssumedNoRecurse() const { return getAssumed(); }
1927 /// Return true if "norecurse" is known.
1928 bool isKnownNoRecurse() const { return getKnown(); }
1930 /// Create an abstract attribute view for the position \p IRP.
1931 static AANoRecurse &createForPosition(const IRPosition &IRP, Attributor &A);
1933 /// Unique ID (due to the unique address)
1934 static const char ID;
1937 /// An abstract attribute for willreturn.
1939 : public IRAttribute<Attribute::WillReturn,
1940 StateWrapper<BooleanState, AbstractAttribute>> {
1941 AAWillReturn(const IRPosition &IRP) : IRAttribute(IRP) {}
1943 /// Return true if "willreturn" is assumed.
1944 bool isAssumedWillReturn() const { return getAssumed(); }
1946 /// Return true if "willreturn" is known.
1947 bool isKnownWillReturn() const { return getKnown(); }
1949 /// Create an abstract attribute view for the position \p IRP.
1950 static AAWillReturn &createForPosition(const IRPosition &IRP, Attributor &A);
1952 /// Unique ID (due to the unique address)
1953 static const char ID;
1956 /// An abstract attribute for undefined behavior.
1957 struct AAUndefinedBehavior
1958 : public StateWrapper<BooleanState, AbstractAttribute>,
1960 AAUndefinedBehavior(const IRPosition &IRP) : IRPosition(IRP) {}
1962 /// Return true if "undefined behavior" is assumed.
1963 bool isAssumedToCauseUB() const { return getAssumed(); }
1965 /// Return true if "undefined behavior" is assumed for a specific instruction.
1966 virtual bool isAssumedToCauseUB(Instruction *I) const = 0;
1968 /// Return true if "undefined behavior" is known.
1969 bool isKnownToCauseUB() const { return getKnown(); }
1971 /// Return true if "undefined behavior" is known for a specific instruction.
1972 virtual bool isKnownToCauseUB(Instruction *I) const = 0;
1974 /// Return an IR position, see struct IRPosition.
1975 const IRPosition &getIRPosition() const override { return *this; }
1977 /// Create an abstract attribute view for the position \p IRP.
1978 static AAUndefinedBehavior &createForPosition(const IRPosition &IRP,
1981 /// Unique ID (due to the unique address)
1982 static const char ID;
1985 /// An abstract interface to determine reachability of point A to B.
1986 struct AAReachability : public StateWrapper<BooleanState, AbstractAttribute>,
1988 AAReachability(const IRPosition &IRP) : IRPosition(IRP) {}
1990 /// Returns true if 'From' instruction is assumed to reach, 'To' instruction.
1991 /// Users should provide two positions they are interested in, and the class
1992 /// determines (and caches) reachability.
1993 bool isAssumedReachable(const Instruction *From,
1994 const Instruction *To) const {
1998 /// Returns true if 'From' instruction is known to reach, 'To' instruction.
1999 /// Users should provide two positions they are interested in, and the class
2000 /// determines (and caches) reachability.
2001 bool isKnownReachable(const Instruction *From, const Instruction *To) const {
2005 /// Return an IR position, see struct IRPosition.
2006 const IRPosition &getIRPosition() const override { return *this; }
2008 /// Create an abstract attribute view for the position \p IRP.
2009 static AAReachability &createForPosition(const IRPosition &IRP,
2012 /// Unique ID (due to the unique address)
2013 static const char ID;
2016 /// An abstract interface for all noalias attributes.
2018 : public IRAttribute<Attribute::NoAlias,
2019 StateWrapper<BooleanState, AbstractAttribute>> {
2020 AANoAlias(const IRPosition &IRP) : IRAttribute(IRP) {}
2022 /// Return true if we assume that the underlying value is alias.
2023 bool isAssumedNoAlias() const { return getAssumed(); }
2025 /// Return true if we know that underlying value is noalias.
2026 bool isKnownNoAlias() const { return getKnown(); }
2028 /// Create an abstract attribute view for the position \p IRP.
2029 static AANoAlias &createForPosition(const IRPosition &IRP, Attributor &A);
2031 /// Unique ID (due to the unique address)
2032 static const char ID;
2035 /// An AbstractAttribute for nofree.
2037 : public IRAttribute<Attribute::NoFree,
2038 StateWrapper<BooleanState, AbstractAttribute>> {
2039 AANoFree(const IRPosition &IRP) : IRAttribute(IRP) {}
2041 /// Return true if "nofree" is assumed.
2042 bool isAssumedNoFree() const { return getAssumed(); }
2044 /// Return true if "nofree" is known.
2045 bool isKnownNoFree() const { return getKnown(); }
2047 /// Create an abstract attribute view for the position \p IRP.
2048 static AANoFree &createForPosition(const IRPosition &IRP, Attributor &A);
2050 /// Unique ID (due to the unique address)
2051 static const char ID;
2054 /// An AbstractAttribute for noreturn.
2056 : public IRAttribute<Attribute::NoReturn,
2057 StateWrapper<BooleanState, AbstractAttribute>> {
2058 AANoReturn(const IRPosition &IRP) : IRAttribute(IRP) {}
2060 /// Return true if the underlying object is assumed to never return.
2061 bool isAssumedNoReturn() const { return getAssumed(); }
2063 /// Return true if the underlying object is known to never return.
2064 bool isKnownNoReturn() const { return getKnown(); }
2066 /// Create an abstract attribute view for the position \p IRP.
2067 static AANoReturn &createForPosition(const IRPosition &IRP, Attributor &A);
2069 /// Unique ID (due to the unique address)
2070 static const char ID;
2073 /// An abstract interface for liveness abstract attribute.
2074 struct AAIsDead : public StateWrapper<BooleanState, AbstractAttribute>,
2076 AAIsDead(const IRPosition &IRP) : IRPosition(IRP) {}
2078 /// Returns true if the underlying value is assumed dead.
2079 virtual bool isAssumedDead() const = 0;
2081 /// Returns true if \p BB is assumed dead.
2082 virtual bool isAssumedDead(const BasicBlock *BB) const = 0;
2084 /// Returns true if \p BB is known dead.
2085 virtual bool isKnownDead(const BasicBlock *BB) const = 0;
2087 /// Returns true if \p I is assumed dead.
2088 virtual bool isAssumedDead(const Instruction *I) const = 0;
2090 /// Returns true if \p I is known dead.
2091 virtual bool isKnownDead(const Instruction *I) const = 0;
2093 /// This method is used to check if at least one instruction in a collection
2094 /// of instructions is live.
2095 template <typename T> bool isLiveInstSet(T begin, T end) const {
2096 for (const auto &I : llvm::make_range(begin, end)) {
2097 assert(I->getFunction() == getIRPosition().getAssociatedFunction() &&
2098 "Instruction must be in the same anchor scope function.");
2100 if (!isAssumedDead(I))
2107 /// Return an IR position, see struct IRPosition.
2108 const IRPosition &getIRPosition() const override { return *this; }
2110 /// Create an abstract attribute view for the position \p IRP.
2111 static AAIsDead &createForPosition(const IRPosition &IRP, Attributor &A);
2113 /// Unique ID (due to the unique address)
2114 static const char ID;
2117 /// State for dereferenceable attribute
2118 struct DerefState : AbstractState {
2120 /// State representing for dereferenceable bytes.
2121 IncIntegerState<> DerefBytesState;
2123 /// Map representing for accessed memory offsets and sizes.
2124 /// A key is Offset and a value is size.
2125 /// If there is a load/store instruction something like,
2127 /// (offset, sizeof(v)) will be inserted to this map.
2128 /// std::map is used because we want to iterate keys in ascending order.
2129 std::map<int64_t, uint64_t> AccessedBytesMap;
2131 /// Helper function to calculate dereferenceable bytes from current known
2132 /// bytes and accessed bytes.
2141 /// In that case, AccessedBytesMap is `{0:4, 4:4, 8:4, 40:4}`.
2142 /// AccessedBytesMap is std::map so it is iterated in accending order on
2143 /// key(Offset). So KnownBytes will be updated like this:
2145 /// |Access | KnownBytes
2148 /// |(8, 4)| 8 -> 12
2149 /// |(40, 4) | 12 (break)
2150 void computeKnownDerefBytesFromAccessedMap() {
2151 int64_t KnownBytes = DerefBytesState.getKnown();
2152 for (auto &Access : AccessedBytesMap) {
2153 if (KnownBytes < Access.first)
2155 KnownBytes = std::max(KnownBytes, Access.first + (int64_t)Access.second);
2158 DerefBytesState.takeKnownMaximum(KnownBytes);
2161 /// State representing that whether the value is globaly dereferenceable.
2162 BooleanState GlobalState;
2164 /// See AbstractState::isValidState()
2165 bool isValidState() const override { return DerefBytesState.isValidState(); }
2167 /// See AbstractState::isAtFixpoint()
2168 bool isAtFixpoint() const override {
2169 return !isValidState() ||
2170 (DerefBytesState.isAtFixpoint() && GlobalState.isAtFixpoint());
2173 /// See AbstractState::indicateOptimisticFixpoint(...)
2174 ChangeStatus indicateOptimisticFixpoint() override {
2175 DerefBytesState.indicateOptimisticFixpoint();
2176 GlobalState.indicateOptimisticFixpoint();
2177 return ChangeStatus::UNCHANGED;
2180 /// See AbstractState::indicatePessimisticFixpoint(...)
2181 ChangeStatus indicatePessimisticFixpoint() override {
2182 DerefBytesState.indicatePessimisticFixpoint();
2183 GlobalState.indicatePessimisticFixpoint();
2184 return ChangeStatus::CHANGED;
2187 /// Update known dereferenceable bytes.
2188 void takeKnownDerefBytesMaximum(uint64_t Bytes) {
2189 DerefBytesState.takeKnownMaximum(Bytes);
2191 // Known bytes might increase.
2192 computeKnownDerefBytesFromAccessedMap();
2195 /// Update assumed dereferenceable bytes.
2196 void takeAssumedDerefBytesMinimum(uint64_t Bytes) {
2197 DerefBytesState.takeAssumedMinimum(Bytes);
2200 /// Add accessed bytes to the map.
2201 void addAccessedBytes(int64_t Offset, uint64_t Size) {
2202 AccessedBytesMap[Offset] = std::max(AccessedBytesMap[Offset], Size);
2204 // Known bytes might increase.
2205 computeKnownDerefBytesFromAccessedMap();
2208 /// Equality for DerefState.
2209 bool operator==(const DerefState &R) {
2210 return this->DerefBytesState == R.DerefBytesState &&
2211 this->GlobalState == R.GlobalState;
2214 /// Inequality for DerefState.
2215 bool operator!=(const DerefState &R) { return !(*this == R); }
2217 /// See IntegerStateBase::operator^=
2218 DerefState operator^=(const DerefState &R) {
2219 DerefBytesState ^= R.DerefBytesState;
2220 GlobalState ^= R.GlobalState;
2224 /// See IntegerStateBase::operator&=
2225 DerefState operator&=(const DerefState &R) {
2226 DerefBytesState &= R.DerefBytesState;
2227 GlobalState &= R.GlobalState;
2231 /// See IntegerStateBase::operator|=
2232 DerefState operator|=(const DerefState &R) {
2233 DerefBytesState |= R.DerefBytesState;
2234 GlobalState |= R.GlobalState;
2239 const AANonNull *NonNullAA = nullptr;
2242 /// An abstract interface for all dereferenceable attribute.
2243 struct AADereferenceable
2244 : public IRAttribute<Attribute::Dereferenceable,
2245 StateWrapper<DerefState, AbstractAttribute>> {
2246 AADereferenceable(const IRPosition &IRP) : IRAttribute(IRP) {}
2248 /// Return true if we assume that the underlying value is nonnull.
2249 bool isAssumedNonNull() const {
2250 return NonNullAA && NonNullAA->isAssumedNonNull();
2253 /// Return true if we know that the underlying value is nonnull.
2254 bool isKnownNonNull() const {
2255 return NonNullAA && NonNullAA->isKnownNonNull();
2258 /// Return true if we assume that underlying value is
2259 /// dereferenceable(_or_null) globally.
2260 bool isAssumedGlobal() const { return GlobalState.getAssumed(); }
2262 /// Return true if we know that underlying value is
2263 /// dereferenceable(_or_null) globally.
2264 bool isKnownGlobal() const { return GlobalState.getKnown(); }
2266 /// Return assumed dereferenceable bytes.
2267 uint32_t getAssumedDereferenceableBytes() const {
2268 return DerefBytesState.getAssumed();
2271 /// Return known dereferenceable bytes.
2272 uint32_t getKnownDereferenceableBytes() const {
2273 return DerefBytesState.getKnown();
2276 /// Create an abstract attribute view for the position \p IRP.
2277 static AADereferenceable &createForPosition(const IRPosition &IRP,
2280 /// Unique ID (due to the unique address)
2281 static const char ID;
2284 using AAAlignmentStateType =
2285 IncIntegerState<uint32_t, /* maximal alignment */ 1U << 29, 0>;
2286 /// An abstract interface for all align attributes.
2287 struct AAAlign : public IRAttribute<
2288 Attribute::Alignment,
2289 StateWrapper<AAAlignmentStateType, AbstractAttribute>> {
2290 AAAlign(const IRPosition &IRP) : IRAttribute(IRP) {}
2292 /// Return assumed alignment.
2293 unsigned getAssumedAlign() const { return getAssumed(); }
2295 /// Return known alignment.
2296 unsigned getKnownAlign() const { return getKnown(); }
2298 /// Create an abstract attribute view for the position \p IRP.
2299 static AAAlign &createForPosition(const IRPosition &IRP, Attributor &A);
2301 /// Unique ID (due to the unique address)
2302 static const char ID;
2305 /// An abstract interface for all nocapture attributes.
2307 : public IRAttribute<
2308 Attribute::NoCapture,
2309 StateWrapper<BitIntegerState<uint16_t, 7, 0>, AbstractAttribute>> {
2310 AANoCapture(const IRPosition &IRP) : IRAttribute(IRP) {}
2312 /// State encoding bits. A set bit in the state means the property holds.
2313 /// NO_CAPTURE is the best possible state, 0 the worst possible state.
2315 NOT_CAPTURED_IN_MEM = 1 << 0,
2316 NOT_CAPTURED_IN_INT = 1 << 1,
2317 NOT_CAPTURED_IN_RET = 1 << 2,
2319 /// If we do not capture the value in memory or through integers we can only
2320 /// communicate it back as a derived pointer.
2321 NO_CAPTURE_MAYBE_RETURNED = NOT_CAPTURED_IN_MEM | NOT_CAPTURED_IN_INT,
2323 /// If we do not capture the value in memory, through integers, or as a
2324 /// derived pointer we know it is not captured.
2326 NOT_CAPTURED_IN_MEM | NOT_CAPTURED_IN_INT | NOT_CAPTURED_IN_RET,
2329 /// Return true if we know that the underlying value is not captured in its
2330 /// respective scope.
2331 bool isKnownNoCapture() const { return isKnown(NO_CAPTURE); }
2333 /// Return true if we assume that the underlying value is not captured in its
2334 /// respective scope.
2335 bool isAssumedNoCapture() const { return isAssumed(NO_CAPTURE); }
2337 /// Return true if we know that the underlying value is not captured in its
2338 /// respective scope but we allow it to escape through a "return".
2339 bool isKnownNoCaptureMaybeReturned() const {
2340 return isKnown(NO_CAPTURE_MAYBE_RETURNED);
2343 /// Return true if we assume that the underlying value is not captured in its
2344 /// respective scope but we allow it to escape through a "return".
2345 bool isAssumedNoCaptureMaybeReturned() const {
2346 return isAssumed(NO_CAPTURE_MAYBE_RETURNED);
2349 /// Create an abstract attribute view for the position \p IRP.
2350 static AANoCapture &createForPosition(const IRPosition &IRP, Attributor &A);
2352 /// Unique ID (due to the unique address)
2353 static const char ID;
2356 /// An abstract interface for value simplify abstract attribute.
2357 struct AAValueSimplify : public StateWrapper<BooleanState, AbstractAttribute>,
2359 AAValueSimplify(const IRPosition &IRP) : IRPosition(IRP) {}
2361 /// Return an IR position, see struct IRPosition.
2362 const IRPosition &getIRPosition() const { return *this; }
2364 /// Return an assumed simplified value if a single candidate is found. If
2365 /// there cannot be one, return original value. If it is not clear yet, return
2366 /// the Optional::NoneType.
2367 virtual Optional<Value *> getAssumedSimplifiedValue(Attributor &A) const = 0;
2369 /// Create an abstract attribute view for the position \p IRP.
2370 static AAValueSimplify &createForPosition(const IRPosition &IRP,
2373 /// Unique ID (due to the unique address)
2374 static const char ID;
2377 struct AAHeapToStack : public StateWrapper<BooleanState, AbstractAttribute>,
2379 AAHeapToStack(const IRPosition &IRP) : IRPosition(IRP) {}
2381 /// Returns true if HeapToStack conversion is assumed to be possible.
2382 bool isAssumedHeapToStack() const { return getAssumed(); }
2384 /// Returns true if HeapToStack conversion is known to be possible.
2385 bool isKnownHeapToStack() const { return getKnown(); }
2387 /// Return an IR position, see struct IRPosition.
2388 const IRPosition &getIRPosition() const { return *this; }
2390 /// Create an abstract attribute view for the position \p IRP.
2391 static AAHeapToStack &createForPosition(const IRPosition &IRP, Attributor &A);
2393 /// Unique ID (due to the unique address)
2394 static const char ID;
2397 /// An abstract interface for all memory related attributes.
2398 struct AAMemoryBehavior
2399 : public IRAttribute<
2400 Attribute::ReadNone,
2401 StateWrapper<BitIntegerState<uint8_t, 3>, AbstractAttribute>> {
2402 AAMemoryBehavior(const IRPosition &IRP) : IRAttribute(IRP) {}
2404 /// State encoding bits. A set bit in the state means the property holds.
2405 /// BEST_STATE is the best possible state, 0 the worst possible state.
2409 NO_ACCESSES = NO_READS | NO_WRITES,
2411 BEST_STATE = NO_ACCESSES,
2414 /// Return true if we know that the underlying value is not read or accessed
2415 /// in its respective scope.
2416 bool isKnownReadNone() const { return isKnown(NO_ACCESSES); }
2418 /// Return true if we assume that the underlying value is not read or accessed
2419 /// in its respective scope.
2420 bool isAssumedReadNone() const { return isAssumed(NO_ACCESSES); }
2422 /// Return true if we know that the underlying value is not accessed
2423 /// (=written) in its respective scope.
2424 bool isKnownReadOnly() const { return isKnown(NO_WRITES); }
2426 /// Return true if we assume that the underlying value is not accessed
2427 /// (=written) in its respective scope.
2428 bool isAssumedReadOnly() const { return isAssumed(NO_WRITES); }
2430 /// Return true if we know that the underlying value is not read in its
2431 /// respective scope.
2432 bool isKnownWriteOnly() const { return isKnown(NO_READS); }
2434 /// Return true if we assume that the underlying value is not read in its
2435 /// respective scope.
2436 bool isAssumedWriteOnly() const { return isAssumed(NO_READS); }
2438 /// Create an abstract attribute view for the position \p IRP.
2439 static AAMemoryBehavior &createForPosition(const IRPosition &IRP,
2442 /// Unique ID (due to the unique address)
2443 static const char ID;
2446 /// An abstract interface for range value analysis.
2447 struct AAValueConstantRange : public IntegerRangeState,
2448 public AbstractAttribute,
2450 AAValueConstantRange(const IRPosition &IRP)
2451 : IntegerRangeState(
2452 IRP.getAssociatedValue().getType()->getIntegerBitWidth()),
2455 /// Return an IR position, see struct IRPosition.
2456 const IRPosition &getIRPosition() const override { return *this; }
2458 /// See AbstractAttribute::getState(...).
2459 IntegerRangeState &getState() override { return *this; }
2460 const AbstractState &getState() const override { return *this; }
2462 /// Create an abstract attribute view for the position \p IRP.
2463 static AAValueConstantRange &createForPosition(const IRPosition &IRP,
2466 /// Return an assumed range for the assocaited value a program point \p CtxI.
2467 /// If \p I is nullptr, simply return an assumed range.
2468 virtual ConstantRange
2469 getAssumedConstantRange(Attributor &A,
2470 const Instruction *CtxI = nullptr) const = 0;
2472 /// Return a known range for the assocaited value at a program point \p CtxI.
2473 /// If \p I is nullptr, simply return a known range.
2474 virtual ConstantRange
2475 getKnownConstantRange(Attributor &A,
2476 const Instruction *CtxI = nullptr) const = 0;
2478 /// Return an assumed constant for the assocaited value a program point \p
2480 Optional<ConstantInt *>
2481 getAssumedConstantInt(Attributor &A, const Instruction *CtxI = nullptr) const {
2482 ConstantRange RangeV = getAssumedConstantRange(A, CtxI);
2483 if (auto *C = RangeV.getSingleElement())
2484 return cast<ConstantInt>(
2485 ConstantInt::get(getAssociatedValue().getType(), *C));
2486 if (RangeV.isEmptySet())
2491 /// Unique ID (due to the unique address)
2492 static const char ID;
2495 } // end namespace llvm
2497 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H