diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -74,6 +74,7 @@ void initializeArgPromotionPass(PassRegistry&); void initializeAssumptionCacheTrackerPass(PassRegistry&); void initializeAtomicExpandPass(PassRegistry&); +void initializeAttributorLegacyPassPass(PassRegistry&); void initializeBDCELegacyPassPass(PassRegistry&); void initializeBarrierNoopPass(PassRegistry&); void initializeBasicAAWrapperPassPass(PassRegistry&); diff --git a/llvm/include/llvm/LinkAllPasses.h b/llvm/include/llvm/LinkAllPasses.h --- a/llvm/include/llvm/LinkAllPasses.h +++ b/llvm/include/llvm/LinkAllPasses.h @@ -41,6 +41,7 @@ #include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h" #include "llvm/Transforms/IPO.h" #include "llvm/Transforms/IPO/AlwaysInliner.h" +#include "llvm/Transforms/IPO/Attributor.h" #include "llvm/Transforms/IPO/FunctionAttrs.h" #include "llvm/Transforms/InstCombine/InstCombine.h" #include "llvm/Transforms/Instrumentation.h" @@ -188,6 +189,7 @@ (void) llvm::createPostDomTree(); (void) llvm::createInstructionNamerPass(); (void) llvm::createMetaRenamerPass(); + (void) llvm::createAttributorLegacyPass(); (void) llvm::createPostOrderFunctionAttrsLegacyPass(); (void) llvm::createReversePostOrderFunctionAttrsPass(); (void) llvm::createMergeFunctionsPass(); diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Transforms/IPO/Attributor.h @@ -0,0 +1,325 @@ +//===- Attributor.h --- Module-wide attribute deduction ---------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Attributor: An inter procedural (abstract) attribute propagation framework. +// +// The Attributor framework is an inter procedural abstract analysis (fix point +// iteration analysis). The goal is to allow easy deduction of new attributes as +// well as information exchange between abstract attributes in-flight. +// +// The Attributor class is the driver and the link between the various abstract +// attributes. The Attributor will iterate until a fix point state is reached by +// all abstract attributes in-flight, or until it will enforce a pessimistic fix +// point because an iteration limit is reached. +// +// Abstract attributes, derived from the AbstractAttribute class, describe +// properties of the code. They can correspond to actual LLVM-IR attributes or +// they can be more general, ultimately unrelated to LLVM-IR attributes. The +// latter is useful when an abstract attributes provides information to other +// abstract attributes in-flight. The Attributor allows to query in-flight +// abstract attributes through the `getAAFor` function. If used by an abstract +// attribute P, and resulting in an abstract attribute Q, the Attributor will +// automatically capture a potential dependence from Q to P. This dependence +// will cause P to be reevaluated whenever Q changes. +// +// The Attributor will only reevaluated abstract attributes that might have +// changed since the last iteration. That means that the Attribute will not +// revisit all instructions/blocks/functions in the module but only query +// an update from a subset of the abstract attributes. +// +// The update methode `AbstractAttribute::updateImpl` is implemented by the +// specific "abstract attribute" subclasses. The method is invoked whenever the +// currently assumed state (see AbstractAttribute::getState) might not be valid +// anymore. This can, for example, happen if the state was dependent on another +// abstract attribute that changed. The update method has to adjust the internal +// state to a point that is justifiable by the IR and abstract attributes +// in-flight. Since the IR is given and assumed to be valid, the information +// derived from it can be assumed to hold. However, information derived from +// other abstract attributes is conditional on various things. If the justifying +// state changed, the `updateImpl` has to revisit the situation and potentially +// find another justification or limit the optimistic assumes made. +// +// Change is the key in this framework. Until a state of no-change, thus a +// fix point, is reached, the Attributor will query the abstract attributes +// in-flight to re-evaluate their state. If the (current) state is to +// optimistic, hence it cannot be justified anymore through other abstract +// attributes or the state of the IR, the state of the abstract attribute will +// have to change. Generally, we assume abstract attribute state to be a finite +// height lattice and the update function to be monotone. However, these +// conditions are not enforced as the iteration limit will guarantee +// termination. If an optimistic fix point is reached or a pessimistic fix point +// is enforced after a timeout, the abstract attributes are tasked to manifest +// their result in the IR for passes to come. +// +// Attribute manifestation is not mandatory. If desired, there is support to +// generate a single LLVM-IR attribute already in the AbstractAttribute base +// class. Other use cases can be easily achieved by overloading a subset of the +// AbstractAttribute member functions. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H +#define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H + +#include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/Analysis/LazyCallGraph.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +struct AbstractAttribute; +struct Attributor; + +class Function; +class Module; + +/// Simple enum class that forces the status to be spelled out explicitly. +/// +///{ +enum class ChangeStatus { + CHANGED, + UNCHANGED, +}; + +ChangeStatus operator|(ChangeStatus l, ChangeStatus r); +ChangeStatus operator&(ChangeStatus l, ChangeStatus r); +///} + +/// The fixpoint analysis framework that drives the attribute deduction. +struct Attributor { + ~Attributor() { DeleteContainerPointers(AllAbstractAttributes); } + + /// Run the fixpoint analyses on the call graph SCC \p SCC. + /// + /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED. + ChangeStatus run(SmallVectorImpl &SCC); + + /// Lookup an abstract attribute of type \p AAType anchored at value \p V and + /// argument number \p ArgNo. If no attribute is found and \p V is a call base + /// instruction, the calleed function is tried as a value next. Thus, the + /// returned abstract attribute might be anchored at the callee of \p V. + template + const AAType *getAAFor(AbstractAttribute &QueryingAA, const Value &V, + int ArgNo = -1); + + /// A map from opcodes to instructions with this opcode. + using OpcodeInstMapTy = DenseMap>; + + /// Return the map that relates "interesting" opcodes with all instructions + /// with that opcode in \p F. + OpcodeInstMapTy &getOpcodeInstMapForFunction(Function &F) { + return FuncInstOpcodeMap[&F]; + } + + /// A vector type to hold instructions. + using InstructionVectorTy = std::vector; + + /// Return the instructions in \p F that may read or write memory. + InstructionVectorTy &getReadOrWriteInstsForFunction(Function &F) { + return FunctionReadOrWriteInstsMap[&F]; + } + +private: + /// Introduce a new abstract attribute into the fixpoint analysis. + template AAType ®isterAA(AAType &AA, int ArgNo = -1); + + /// Determine opportunities to derive attributes in \p F and create abstract + /// attribute objects for them. + void identifyAbstractAttributes(Function &F); + + /// The set of all abstract attributes. + ///{ + using AAVector = SmallVector; + AAVector AllAbstractAttributes; + ///} + + /// A nested map that remembers all instructions in a function with a certain + /// instruction opcode (Instruction::getOpcode()). + DenseMap FuncInstOpcodeMap; + + /// A map from functions to their instructions that may read or write memory. + DenseMap FunctionReadOrWriteInstsMap; + + /// A map from abstract attributes to the ones that queried them through calls + /// to the getAAFor<...>(...) method. + DenseMap> QueryMap; + + /// A nested map to lookup abstract attributes based on the anchored value and + /// an argument positions (or -1) on the outer level, and attribute kinds + /// (Attribute::AttrKind) on the inner level. + ///{ + using KindToAbstractAttributeMap = DenseMap; + DenseMap, KindToAbstractAttributeMap> AAMap; + ///} +}; + +/// ---------------------------------------------------------------------------- +/// Abstract State & Abstract Attribute Interface +/// ---------------------------------------------------------------------------- + +/// An interface for the internal state of an abstract attribute. +struct AbstractState { + virtual ~AbstractState() {} + + /// Return if this abstract state is in a valid state. If false, no + /// information provided should be used. + virtual bool isValidState() const = 0; + + /// Return if this abstract state is fixed, thus does not need to be updated + /// if information changes as it cannot change itself. + virtual bool isAtFixpoint() const = 0; + + /// Indicate that the abstract state should converge to a fixed state. + /// + /// If \p Optimistic is true, this will usually make the optimistically + /// assumed state the known to be true state. + /// + /// If \p Optimistic is false, this will usually revert the optimistically + /// assumed state to the known to be true state + virtual void indicateFixpoint(bool Optimistic) = 0; +}; + +/// Base class for all abstract states maintained for potential attributes. +/// +/// NOTE: If the state obtained via getState() is the "worst possible", thus if +/// getState(),isValidState() returns false, no information provided +/// by this class should be used for reasoning. +struct AbstractAttribute { + + /// The positions attributes can be manifested in. + enum ManifestPosition { + MP_ARGUMENT, ///< An attribute for a function argument. + MP_CALL_SITE_ARGUMENT, ///< An attribute for a call site argument. + MP_FUNCTION, ///< An attribute for a function as a whole. + MP_RETURNED, ///< An attribute for the function return value. + }; + + /// An abstract attribute associated with \p AssociatedVal and anchored at + /// \p AnchoredVal. + AbstractAttribute(Value *AssociatedVal, Value &AnchoredVal) + : AssociatedVal(AssociatedVal), AnchoredVal(AnchoredVal) {} + + /// An abstract attribute associated with and anchored at \p V. + AbstractAttribute(Value &V) : AbstractAttribute(&V, V) {} + + /// Virtual destructor. + virtual ~AbstractAttribute() {} + + /// Initialize the state with the information in the attributor \p A. + virtual void initialize(Attributor &A) {} + + /// Return the internal abstract state for inspection. + virtual const AbstractState &getState() const = 0; + + /// Return the llvm::Value this abstract attribute is anchored with. + /// + /// The anchored value might not be the associated value if the latter is not + /// sufficient to determine where arguments will be manifested. + /// + ///{ + Value &getAnchoredValue() { return AnchoredVal; } + const Value &getAnchoredValue() const { return AnchoredVal; } + ///} + + /// Return the llvm::Function surrounding the anchored value. + /// + ///{ + Function &getAnchorScope(); + const Function &getAnchorScope() const; + ///} + + /// Return the value this abstract attribute is associated with. + /// + /// The abstract state usally represents this value. + /// + ///{ + virtual Value *getAssociatedValue() { return AssociatedVal; } + virtual const Value *getAssociatedValue() const { return AssociatedVal; } + ///} + + /// Return the position this abstract state is manifested in. + virtual ManifestPosition getManifestPosition() const = 0; + + /// Return the kind that identifies the abstract attribute implementation. + virtual Attribute::AttrKind getAttrKind() const = 0; + + /// Return the deduced attributes in \p Attrs. + virtual void getDeducedAttributes(SmallVectorImpl &Attrs) const { + LLVMContext &Ctx = AnchoredVal.getContext(); + Attrs.emplace_back(Attribute::get(Ctx, getAttrKind())); + } + + /// Helper functions, for debug purposes only. + ///{ + virtual void print(raw_ostream &OS) const; + void dump() const { print(dbgs()); } + + /// This function should return the "summarized" assumed state as string. + virtual const std::string getAsStr() const = 0; + ///} + + /// Allow the attributor access to the protected methods. + friend struct Attributor; + +protected: + /// Hook for the Attributor to trigger an update of the internal state. + /// If this attribute is already fixed, nothing happens, if it is not, the + /// environment was changed and we have to determine if the current + /// information is still valid or adjust it otherwise. + /// + /// \Return CHANGED if the internal state changed, otherwise UNCHANGED. + ChangeStatus update(Attributor &A); + + /// Hook for the Attributor to trigger the manifestation of the information + /// represented by the abstract attribute in the LLVM-IR. + /// + /// \Return CHANGED if the IR was altered, otherwise UNCHANGED. + virtual ChangeStatus manifest(Attributor &A); + + /// Return the internal abstract state for careful modification. + virtual AbstractState &getState() = 0; + + /// The actual update/transfer function which has to be implemented by the + /// derived classes. + virtual ChangeStatus updateImpl(Attributor &A) = 0; + + /// The value this abstract attribute is associated with. + Value *AssociatedVal; + + /// The value this abstract attribute is anchored at. + Value &AnchoredVal; +}; + +/// Forward declarations of output streams for debug purposes. +/// +///{ +raw_ostream &operator<<(raw_ostream &OS, const AbstractAttribute &AA); +raw_ostream &operator<<(raw_ostream &OS, ChangeStatus S); +raw_ostream &operator<<(raw_ostream &OS, AbstractAttribute::ManifestPosition); +raw_ostream &operator<<(raw_ostream &OS, const AbstractState &State); +///} + +/// ---------------------------------------------------------------------------- +/// Abstract Attribute Classes +/// ---------------------------------------------------------------------------- + +/// ---------------------------------------------------------------------------- +/// Pass (Manager) Boilerplate +/// ---------------------------------------------------------------------------- + +struct AttributorPass : public PassInfoMixin { + PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, + LazyCallGraph &CG, CGSCCUpdateResult &); +}; + +Pass *createAttributorLegacyPass(); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H diff --git a/llvm/lib/LTO/LTOCodeGenerator.cpp b/llvm/lib/LTO/LTOCodeGenerator.cpp --- a/llvm/lib/LTO/LTOCodeGenerator.cpp +++ b/llvm/lib/LTO/LTOCodeGenerator.cpp @@ -125,6 +125,7 @@ initializeArgPromotionPass(R); initializeJumpThreadingPass(R); initializeSROALegacyPassPass(R); + initializeAttributorLegacyPassPass(R); initializePostOrderFunctionAttrsLegacyPassPass(R); initializeReversePostOrderFunctionAttrsLegacyPassPass(R); initializeGlobalsAAWrapperPassPass(R); diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -64,6 +64,7 @@ #include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h" #include "llvm/Transforms/IPO/AlwaysInliner.h" #include "llvm/Transforms/IPO/ArgumentPromotion.h" +#include "llvm/Transforms/IPO/Attributor.h" #include "llvm/Transforms/IPO/CalledValuePropagation.h" #include "llvm/Transforms/IPO/ConstantMerge.h" #include "llvm/Transforms/IPO/CrossDSOCFI.h" diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -98,6 +98,7 @@ #define CGSCC_PASS(NAME, CREATE_PASS) #endif CGSCC_PASS("argpromotion", ArgumentPromotionPass()) +CGSCC_PASS("attributor", AttributorPass()) CGSCC_PASS("invalidate", InvalidateAllAnalysesPass()) CGSCC_PASS("function-attrs", PostOrderFunctionAttrsPass()) CGSCC_PASS("inline", InlinerPass()) diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -0,0 +1,543 @@ +//===- Attributor.cpp - Module-wide attribute deduction -------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file implements an interprocedural pass which walk the call-graph +// deducing and/or propagating attributes along the way. This is done in an +// abstract interpretation style fixpoint iteration. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/IPO/Attributor.h" + +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/CallGraph.h" +#include "llvm/Analysis/CallGraphSCCPass.h" +#include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/IR/Argument.h" +#include "llvm/IR/Attributes.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include + +using namespace llvm; + +#define DEBUG_TYPE "attributor" + +STATISTIC(NumFnWithExactDefinition, + "Number of function with exact definitions"); +STATISTIC(NumFnWithoutExactDefinition, + "Number of function without exact definitions"); +STATISTIC(NumAttributesTimedOut, + "Number of abstract attributes timed out before fixpoint"); +STATISTIC(NumAttributesValidFixpoint, + "Number of abstract attributes in a valid fixpoint state"); +STATISTIC(NumAttributesManifested, + "Number of abstract attributes manifested in IR"); + +// TODO: Determine a good default value. +// +// In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads +// (when run with the first 5 abstract attributes). The results also indicate +// that we never reach 32 iterations but always find a fixpoint sooner. +// +// This will become more evolved once we perform two interleaved fixpoint +// iterations: bottom-up and top-down. +static cl::opt + MaxFixpointIterations("attributor-max-iterations", cl::Hidden, + cl::desc("Maximal number of fixpoint iterations."), + cl::init(32)); + +static cl::opt DisableAttributor( + "attributor-disable", cl::Hidden, + cl::desc("Disable the attributor inter-procedural deduction pass."), + cl::init(false)); + +/// Logic operators for the change status enum class. +/// +///{ +ChangeStatus llvm::operator|(ChangeStatus l, ChangeStatus r) { + return l == ChangeStatus::CHANGED ? l : r; +} +ChangeStatus llvm::operator&(ChangeStatus l, ChangeStatus r) { + return l == ChangeStatus::UNCHANGED ? l : r; +} +///} + +/// Helper to adjust the statistics. +static void bookkeeping(AbstractAttribute::ManifestPosition MP, + const Attribute &Attr) { + if (!AreStatisticsEnabled()) + return; + + if (!Attr.isEnumAttribute()) + return; + switch (Attr.getKindAsEnum()) { + default: + return; + } +} + +/// Helper to identify the correct offset into an attribute list. +static unsigned getAttrIndex(AbstractAttribute::ManifestPosition MP, + unsigned ArgNo = 0) { + switch (MP) { + case AbstractAttribute::MP_ARGUMENT: + case AbstractAttribute::MP_CALL_SITE_ARGUMENT: + return ArgNo + AttributeList::FirstArgIndex; + case AbstractAttribute::MP_FUNCTION: + return AttributeList::FunctionIndex; + case AbstractAttribute::MP_RETURNED: + return AttributeList::ReturnIndex; + } +} + +/// Return true if \p New is equal or worse than \p Old. +static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) { + if (!Old.isIntAttribute()) + return true; + + if (Old.getValueAsInt() >= New.getValueAsInt()) + return true; + + return false; +} + +/// Return true if the information provided by \p Attr was added to the +/// attribute list \p Attrs. This is only the case if it was not already present +/// in \p Attrs at the position describe by \p MP and \p ArgNo. +static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr, + AttributeList &Attrs, + AbstractAttribute::ManifestPosition MP, + unsigned ArgNo = 0) { + unsigned AttrIdx = getAttrIndex(MP, ArgNo); + + if (Attr.isEnumAttribute()) { + Attribute::AttrKind Kind = Attr.getKindAsEnum(); + if (Attrs.hasAttribute(AttrIdx, Kind)) + if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind))) + return false; + Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr); + return true; + } + if (Attr.isStringAttribute()) { + StringRef Kind = Attr.getKindAsString(); + if (Attrs.hasAttribute(AttrIdx, Kind)) + if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind))) + return false; + Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr); + return true; + } + + llvm_unreachable("Expected enum or string attribute!"); +} + +ChangeStatus AbstractAttribute::update(Attributor &A) { + ChangeStatus Changed = ChangeStatus::UNCHANGED; + if (getState().isAtFixpoint()) + return Changed; + + LLVM_DEBUG(dbgs() << "[Attributor] Update: " << *this << "\n"); + + Changed = updateImpl(A); + + LLVM_DEBUG(dbgs() << "[Attributor] Update " << Changed << " " << *this + << "\n"); + + return Changed; +} + +ChangeStatus AbstractAttribute::manifest(Attributor &A) { + assert(getState().isValidState() && + "Attempted to manifest an invalid state!"); + assert(getAssociatedValue() && + "Attempted to manifest an attribute without associated value!"); + + ChangeStatus Changed = ChangeStatus::UNCHANGED; + SmallVector DeducedAttrs; + getDeducedAttributes(DeducedAttrs); + + Function &ScopeFn = getAnchorScope(); + LLVMContext &Ctx = ScopeFn.getContext(); + ManifestPosition MP = getManifestPosition(); + + AttributeList Attrs; + SmallVector ArgNos; + + // In the following some generic code that will manifest attributes in + // DeducedAttrs if they improve the current IR. Due to the different + // annotation positions we use the underlying AttributeList interface. + // Note that MP_CALL_SITE_ARGUMENT can annotate multiple locations. + + switch (MP) { + case MP_ARGUMENT: + ArgNos.push_back(cast(getAssociatedValue())->getArgNo()); + Attrs = ScopeFn.getAttributes(); + break; + case MP_FUNCTION: + case MP_RETURNED: + ArgNos.push_back(0); + Attrs = ScopeFn.getAttributes(); + break; + case MP_CALL_SITE_ARGUMENT: { + CallSite CS(&getAnchoredValue()); + for (unsigned u = 0, e = CS.getNumArgOperands(); u != e; u++) + if (CS.getArgOperand(u) == getAssociatedValue()) + ArgNos.push_back(u); + Attrs = CS.getAttributes(); + } + } + + for (const Attribute &Attr : DeducedAttrs) { + for (unsigned ArgNo : ArgNos) { + if (!addIfNotExistent(Ctx, Attr, Attrs, MP, ArgNo)) + continue; + + // Bookkeeping. + Changed = ChangeStatus::CHANGED; + bookkeeping(MP, Attr); + } + } + + if (Changed == ChangeStatus::UNCHANGED) + return Changed; + + switch (MP) { + case MP_ARGUMENT: + case MP_FUNCTION: + case MP_RETURNED: + ScopeFn.setAttributes(Attrs); + break; + case MP_CALL_SITE_ARGUMENT: + CallSite(&getAnchoredValue()).setAttributes(Attrs); + } + + return Changed; +} + +Function &AbstractAttribute::getAnchorScope() { + Value &V = getAnchoredValue(); + if (isa(V)) + return cast(V); + if (isa(V)) + return *cast(V).getParent(); + if (isa(V)) + return *cast(V).getFunction(); + llvm_unreachable("No scope for anchored value found!"); +} + +const Function &AbstractAttribute::getAnchorScope() const { + return const_cast(this)->getAnchorScope(); +} + +/// ---------------------------------------------------------------------------- +/// Attributor +/// ---------------------------------------------------------------------------- + +ChangeStatus Attributor::run(SmallVectorImpl &SCC) { + if (DisableAttributor) + return ChangeStatus::UNCHANGED; + + LLVM_DEBUG(dbgs() << "[Attributor] Run on SCC with " << SCC.size() + << " functions.\n"); + + for (Function *F : SCC) { + + // TODO: Not all attributes require an exact definition. Find a way to + // enable deduction for some but not all attributes in case the + // definition might be changed at runtime, see also + // http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html. + // TODO: We could always determine abstract attributes and if sufficient + // information was found we could duplicate the functions that do not + // have an exact definition. + if (!F->hasExactDefinition()) { + + // Bookkeeping. + NumFnWithoutExactDefinition++; + continue; + } + + // For now we ignore naked and optnone functions. + if (F->hasFnAttribute(Attribute::Naked) || + F->hasFnAttribute(Attribute::OptimizeNone)) + continue; + + // Bookkeeping. + NumFnWithExactDefinition++; + + // Sanity check. + assert(!F->isDeclaration() && "Expected a definition not a declaration!"); + + // Populate abstract attributes for the function. + identifyAbstractAttributes(*F); + } + + // Initialize all abstract attributes. + for (AbstractAttribute *AA : AllAbstractAttributes) + AA->initialize(*this); + + LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized " + << AllAbstractAttributes.size() + << " abstract attributes.\n"); + + // Now that all abstract attributes for the model are collected and + // initialized we start the abstract analysis. + + unsigned IterationCounter = 1; + + SmallVector ChangedAAs; + SetVector Worklist; + Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end()); + + do { + LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter + << ", Worklist size: " << Worklist.size() << "\n"); + + for (AbstractAttribute *ChangedAA : ChangedAAs) { + auto &QuerriedAAs = QueryMap[ChangedAA]; + Worklist.insert(QuerriedAAs.begin(), QuerriedAAs.end()); + } + + ChangedAAs.clear(); + + // Update all abstract attribute in the worklist. + for (AbstractAttribute *AA : Worklist) + if (AA->update(*this) == ChangeStatus::CHANGED) + ChangedAAs.push_back(AA); + + Worklist.clear(); + Worklist.insert(ChangedAAs.begin(), ChangedAAs.end()); + + } while (!Worklist.empty() && ++IterationCounter < MaxFixpointIterations); + + LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: " + << IterationCounter << "/" << MaxFixpointIterations + << " iterations\n"); + + // Reset abstract arguments not settled in a sound fixpoint by now. + SmallPtrSet Visited; + for (unsigned u = 0; u < ChangedAAs.size(); u++) { + AbstractAttribute *ChangedAA = ChangedAAs[u]; + if (!Visited.insert(ChangedAA).second) + continue; + + AbstractState &State = ChangedAA->getState(); + if (!State.isAtFixpoint()) { + State.indicateFixpoint(/* Optimistic */ false); + + // Bookkeeping. + NumAttributesTimedOut++; + } + + auto &QuerriedAAs = QueryMap[ChangedAA]; + ChangedAAs.append(QuerriedAAs.begin(), QuerriedAAs.end()); + } + + LLVM_DEBUG({ + if (!Visited.empty()) + dbgs() << "\n[Attributor] Finalized " << Visited.size() + << " abstract attributes.\n"; + }); + + unsigned NumManifested = 0; + unsigned NumAtFixpoint = 0; + ChangeStatus ManifestChange = ChangeStatus::UNCHANGED; + for (AbstractAttribute *AA : AllAbstractAttributes) { + AbstractState &State = AA->getState(); + + if (!State.isAtFixpoint()) + State.indicateFixpoint(/* Optimistic */ true); + + // If the state is invalid, we do not try to manifest it. + if (!State.isValidState()) + continue; + + // Manifest the state and record if we changed the IR. + ChangeStatus LocalChange = AA->manifest(*this); + ManifestChange = ManifestChange | LocalChange; + + NumAtFixpoint++; + NumManifested += (LocalChange == ChangeStatus::CHANGED); + } + + (void)NumManifested; + (void)NumAtFixpoint; + LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested + << " arguments while " << NumAtFixpoint + << " were in a valid fixpoint state\n"); + + // Bookkeeping. + NumAttributesManifested += NumManifested; + NumAttributesValidFixpoint += NumAtFixpoint; + + return ManifestChange; +} + +template +const AAType *Attributor::getAAFor(AbstractAttribute &QueryingAA, + const Value &V, int ArgNo) { + assert(AAType::ID != Attribute::None && + "Cannot lookup generic abstract attributes!"); + + if (auto *Arg = dyn_cast(&V)) + ArgNo = Arg->getArgNo(); + else if (ArgNo >= 0 && isa(&V) && + cast(&V)->arg_size() > (size_t)ArgNo) + return getAAFor(QueryingAA, + *(cast(&V)->arg_begin() + ArgNo), ArgNo); + + const auto &KindToAbstractAttributeMap = AAMap.lookup({&V, ArgNo}); + if (AAType *AA = static_cast( + KindToAbstractAttributeMap.lookup(AAType::ID))) { + QueryMap[AA].insert(&QueryingAA); + return AA; + } + + ImmutableCallSite ICS(&V); + if (ICS && ICS.getCalledValue()) + return getAAFor(QueryingAA, *ICS.getCalledValue(), ArgNo); + + return nullptr; +} + +template +AAType &Attributor::registerAA(AAType &AA, int ArgNo) { + Value &AnchoredVal = AA.getAnchoredValue(); + if (auto *Arg = dyn_cast(&AnchoredVal)) + ArgNo = Arg->getArgNo(); + AAMap[{&AnchoredVal, ArgNo}][AAType::ID] = &AA; + AllAbstractAttributes.push_back(&AA); + return AA; +} + +void Attributor::identifyAbstractAttributes(Function &F) { + // Walk all instructions to find more attribute opportunities and also + // interesting instructions that might be querried by abstract attributes + // during their initialziation or update. + auto &ReadOrWriteInsts = FunctionReadOrWriteInstsMap[&F]; + auto &InstOpcodeMap = FuncInstOpcodeMap[&F]; + + for (Instruction &I : instructions(&F)) { + bool IsInterestingOpcode = false; + + switch (I.getOpcode()) { + default: + break; + } + if (IsInterestingOpcode) + InstOpcodeMap[I.getOpcode()].push_back(&I); + if (I.mayReadOrWriteMemory()) + ReadOrWriteInsts.push_back(&I); + } +} + +/// Helpers to ease debugging through output streams and print calls. +/// +///{ +raw_ostream &llvm::operator<<(raw_ostream &OS, ChangeStatus S) { + return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged"); +} + +raw_ostream &llvm::operator<<(raw_ostream &OS, + AbstractAttribute::ManifestPosition AP) { + switch (AP) { + case AbstractAttribute::MP_ARGUMENT: + return OS << "arg"; + case AbstractAttribute::MP_CALL_SITE_ARGUMENT: + return OS << "cs_arg"; + case AbstractAttribute::MP_FUNCTION: + return OS << "fn"; + case AbstractAttribute::MP_RETURNED: + return OS << "fn_ret"; + } + llvm_unreachable("Unknown attribute position!"); +} + +raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &S) { + return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : "")); +} + +/// Helper to dump abstract attributes into a stream. +raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) { + AA.print(OS); + return OS; +} + +void AbstractAttribute::print(raw_ostream &OS) const { + OS << "[" << getManifestPosition() << "][" << getAsStr() << "][" + << AnchoredVal.getName() << "]"; +} +///} + +/// ---------------------------------------------------------------------------- +/// Pass (Manager) Boilerplate +/// ---------------------------------------------------------------------------- + +PreservedAnalyses AttributorPass::run(LazyCallGraph::SCC &C, + CGSCCAnalysisManager &, LazyCallGraph &, + CGSCCUpdateResult &) { + + SmallVector SCCFunctions; + for (LazyCallGraph::Node &N : C) { + Function &Fn = N.getFunction(); + if (!Fn.isDeclaration()) + SCCFunctions.push_back(&Fn); + } + + Attributor A; + if (A.run(SCCFunctions) == ChangeStatus::CHANGED) + return PreservedAnalyses::none(); + + return PreservedAnalyses::all(); +} + +namespace { + +struct AttributorLegacyPass : public CallGraphSCCPass { + // Pass identification, replacement for typeid + static char ID; + + AttributorLegacyPass() : CallGraphSCCPass(ID) { + initializeAttributorLegacyPassPass(*PassRegistry::getPassRegistry()); + } + + bool runOnSCC(CallGraphSCC &SCC) override { + if (skipSCC(SCC)) + return false; + + SmallVector SCCFunctions; + for (CallGraphNode *I : SCC) + if (Function *Fn = I->getFunction()) + if (!Fn->isDeclaration()) + SCCFunctions.push_back(Fn); + + Attributor A; + return A.run(SCCFunctions) == ChangeStatus::CHANGED; + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesCFG(); + AU.addPreserved(); + CallGraphSCCPass::getAnalysisUsage(AU); + } +}; + +} // end anonymous namespace + +Pass *llvm::createAttributorLegacyPass() { return new AttributorLegacyPass(); } + +char AttributorLegacyPass::ID = 0; +INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor", + "Deduce and propagate attributes", false, false) +INITIALIZE_PASS_END(AttributorLegacyPass, "attributor", + "Deduce and propagate attributes", false, false) + diff --git a/llvm/lib/Transforms/IPO/CMakeLists.txt b/llvm/lib/Transforms/IPO/CMakeLists.txt --- a/llvm/lib/Transforms/IPO/CMakeLists.txt +++ b/llvm/lib/Transforms/IPO/CMakeLists.txt @@ -1,6 +1,7 @@ add_llvm_library(LLVMipo AlwaysInliner.cpp ArgumentPromotion.cpp + Attributor.cpp BarrierNoopPass.cpp BlockExtractor.cpp CalledValuePropagation.cpp diff --git a/llvm/lib/Transforms/IPO/IPO.cpp b/llvm/lib/Transforms/IPO/IPO.cpp --- a/llvm/lib/Transforms/IPO/IPO.cpp +++ b/llvm/lib/Transforms/IPO/IPO.cpp @@ -45,6 +45,7 @@ initializeLowerTypeTestsPass(Registry); initializeMergeFunctionsPass(Registry); initializePartialInlinerLegacyPassPass(Registry); + initializeAttributorLegacyPassPass(Registry); initializePostOrderFunctionAttrsLegacyPassPass(Registry); initializeReversePostOrderFunctionAttrsLegacyPassPass(Registry); initializePruneEHPass(Registry); diff --git a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp --- a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp +++ b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp @@ -30,6 +30,7 @@ #include "llvm/Support/ManagedStatic.h" #include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h" #include "llvm/Transforms/IPO.h" +#include "llvm/Transforms/IPO/Attributor.h" #include "llvm/Transforms/IPO/ForceFunctionAttrs.h" #include "llvm/Transforms/IPO/FunctionAttrs.h" #include "llvm/Transforms/IPO/InferFunctionAttrs.h" @@ -561,6 +562,8 @@ RunInliner = true; } + // Infer attributes on declarations, call sites, arguments, etc. + MPM.add(createAttributorLegacyPass()); MPM.add(createPostOrderFunctionAttrsLegacyPass()); if (OptLevel > 2) MPM.add(createArgumentPromotionPass()); // Scalarize uninlined fn args @@ -831,6 +834,8 @@ // Infer attributes about definitions. The readnone attribute in particular is // required for virtual constant propagation. + // Infer attributes on declarations, call sites, arguments, etc. + PM.add(createAttributorLegacyPass()); PM.add(createPostOrderFunctionAttrsLegacyPass()); PM.add(createReversePostOrderFunctionAttrsPass()); @@ -900,8 +905,10 @@ // link-time inlining, and visibility of nocapture attribute. PM.add(createTailCallEliminationPass()); - // Run a few AA driven optimizations here and now, to cleanup the code. + // Infer attributes on declarations, call sites, arguments, etc. + PM.add(createAttributorLegacyPass()); PM.add(createPostOrderFunctionAttrsLegacyPass()); // Add nocapture. + // Run a few AA driven optimizations here and now, to cleanup the code. PM.add(createGlobalsAAWrapperPass()); // IP alias analysis. PM.add(createLICMPass()); // Hoist loop invariants. diff --git a/llvm/test/Other/opt-O2-pipeline.ll b/llvm/test/Other/opt-O2-pipeline.ll --- a/llvm/test/Other/opt-O2-pipeline.ll +++ b/llvm/test/Other/opt-O2-pipeline.ll @@ -51,6 +51,7 @@ ; CHECK-NEXT: Call Graph SCC Pass Manager ; CHECK-NEXT: Remove unused exception handling info ; CHECK-NEXT: Function Integration/Inlining +; CHECK-NEXT: Deduce and propagate attributes ; CHECK-NEXT: Deduce function attributes ; CHECK-NEXT: FunctionPass Manager ; CHECK-NEXT: Dominator Tree Construction diff --git a/llvm/test/Other/opt-O3-pipeline.ll b/llvm/test/Other/opt-O3-pipeline.ll --- a/llvm/test/Other/opt-O3-pipeline.ll +++ b/llvm/test/Other/opt-O3-pipeline.ll @@ -54,6 +54,7 @@ ; CHECK-NEXT: Call Graph SCC Pass Manager ; CHECK-NEXT: Remove unused exception handling info ; CHECK-NEXT: Function Integration/Inlining +; CHECK-NEXT: Deduce and propagate attributes ; CHECK-NEXT: Deduce function attributes ; CHECK-NEXT: Promote 'by reference' arguments to scalars ; CHECK-NEXT: FunctionPass Manager diff --git a/llvm/test/Other/opt-Os-pipeline.ll b/llvm/test/Other/opt-Os-pipeline.ll --- a/llvm/test/Other/opt-Os-pipeline.ll +++ b/llvm/test/Other/opt-Os-pipeline.ll @@ -51,6 +51,7 @@ ; CHECK-NEXT: Call Graph SCC Pass Manager ; CHECK-NEXT: Remove unused exception handling info ; CHECK-NEXT: Function Integration/Inlining +; CHECK-NEXT: Deduce and propagate attributes ; CHECK-NEXT: Deduce function attributes ; CHECK-NEXT: FunctionPass Manager ; CHECK-NEXT: Dominator Tree Construction diff --git a/llvm/test/Other/pass-pipelines.ll b/llvm/test/Other/pass-pipelines.ll --- a/llvm/test/Other/pass-pipelines.ll +++ b/llvm/test/Other/pass-pipelines.ll @@ -46,6 +46,7 @@ ; CHECK-O2-NEXT: Call Graph SCC Pass Manager ; CHECK-O2-NEXT: Remove unused exception handling info ; CHECK-O2-NEXT: Function Integration/Inlining +; CHECK-O2-NEXT: Deduce and propagate attributes ; CHECK-O2-NEXT: Deduce function attributes ; Next up is the main function pass pipeline. It shouldn't be split up and ; should contain the main loop pass pipeline as well. diff --git a/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll b/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll --- a/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll +++ b/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll @@ -1,4 +1,4 @@ -; RUN: opt -functionattrs -S < %s | FileCheck %s +; RUN: opt -functionattrs -attributor -S < %s | FileCheck %s ; ; Test cases specifically designed for the "no-capture" argument attribute. ; We use FIXME's to indicate problems and missing attributes. diff --git a/llvm/test/Transforms/FunctionAttrs/arg_returned.ll b/llvm/test/Transforms/FunctionAttrs/arg_returned.ll --- a/llvm/test/Transforms/FunctionAttrs/arg_returned.ll +++ b/llvm/test/Transforms/FunctionAttrs/arg_returned.ll @@ -1,4 +1,4 @@ -; RUN: opt -functionattrs -S < %s | FileCheck %s +; RUN: opt -functionattrs -attributor -S < %s | FileCheck %s ; ; Test cases specifically designed for the "returned" argument attribute. ; We use FIXME's to indicate problems and missing attributes. diff --git a/llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll b/llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll --- a/llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll +++ b/llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll @@ -1,4 +1,4 @@ -; RUN: opt -functionattrs -S < %s | FileCheck %s +; RUN: opt -functionattrs -attributor -S < %s | FileCheck %s ; ; Test cases specifically designed for the "no-return" function attribute. ; We use FIXME's to indicate problems and missing attributes. diff --git a/llvm/test/Transforms/FunctionAttrs/read_write_returned_arguments_scc.ll b/llvm/test/Transforms/FunctionAttrs/read_write_returned_arguments_scc.ll --- a/llvm/test/Transforms/FunctionAttrs/read_write_returned_arguments_scc.ll +++ b/llvm/test/Transforms/FunctionAttrs/read_write_returned_arguments_scc.ll @@ -1,4 +1,4 @@ -; RUN: opt -S -functionattrs -enable-nonnull-arg-prop %s | FileCheck %s +; RUN: opt -S -functionattrs -enable-nonnull-arg-prop -attributor %s | FileCheck %s ; ; This is an evolved example to stress test SCC parameter attribute propagation. ; The SCC in this test is made up of the following six function, three of which