llvm/llvm/lib/Transforms/IPO/Attributor.cpp

//===- 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 that deduces and/or propagates
// attributes. This is done in an abstract interpretation style fixpoint
// iteration. See the Attributor.h file comment and the class descriptions in
// that file for more information.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/IPO/Attributor.h"

#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/Analysis/CallGraphSCCPass.h"
#include "llvm/Analysis/InlineCost.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MustExecute.h"
#include "llvm/IR/AttributeMask.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantFold.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/DebugCounter.h"
#include "llvm/Support/FileSystem.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/ModRef.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#include <cstdint>
#include <memory>

#ifdef EXPENSIVE_CHECKS
#include "llvm/IR/Verifier.h"
#endif

#include <cassert>
#include <optional>
#include <string>

usingnamespacellvm;

#define DEBUG_TYPE …
#define VERBOSE_DEBUG_TYPE …

DEBUG_COUNTER(ManifestDBGCounter, "attributor-manifest",
              "Determine what attributes are manifested in the IR");

STATISTIC(NumFnDeleted, "Number of function deleted");
STATISTIC(NumFnWithExactDefinition,
          "Number of functions with exact definitions");
STATISTIC(NumFnWithoutExactDefinition,
          "Number of functions without exact definitions");
STATISTIC(NumFnShallowWrappersCreated, "Number of shallow wrappers created");
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<unsigned>
    SetFixpointIterations("attributor-max-iterations", cl::Hidden,
                          cl::desc("Maximal number of fixpoint iterations."),
                          cl::init(32));

static cl::opt<unsigned>
    MaxSpecializationPerCB("attributor-max-specializations-per-call-base",
                           cl::Hidden,
                           cl::desc("Maximal number of callees specialized for "
                                    "a call base"),
                           cl::init(UINT32_MAX));

static cl::opt<unsigned, true> MaxInitializationChainLengthX(
    "attributor-max-initialization-chain-length", cl::Hidden,
    cl::desc(
        "Maximal number of chained initializations (to avoid stack overflows)"),
    cl::location(MaxInitializationChainLength), cl::init(1024));
unsigned llvm::MaxInitializationChainLength;

static cl::opt<bool> AnnotateDeclarationCallSites(
    "attributor-annotate-decl-cs", cl::Hidden,
    cl::desc("Annotate call sites of function declarations."), cl::init(false));

static cl::opt<bool> EnableHeapToStack("enable-heap-to-stack-conversion",
                                       cl::init(true), cl::Hidden);

static cl::opt<bool>
    AllowShallowWrappers("attributor-allow-shallow-wrappers", cl::Hidden,
                         cl::desc("Allow the Attributor to create shallow "
                                  "wrappers for non-exact definitions."),
                         cl::init(false));

static cl::opt<bool>
    AllowDeepWrapper("attributor-allow-deep-wrappers", cl::Hidden,
                     cl::desc("Allow the Attributor to use IP information "
                              "derived from non-exact functions via cloning"),
                     cl::init(false));

// These options can only used for debug builds.
#ifndef NDEBUG
static cl::list<std::string>
    SeedAllowList("attributor-seed-allow-list", cl::Hidden,
                  cl::desc("Comma separated list of attribute names that are "
                           "allowed to be seeded."),
                  cl::CommaSeparated);

static cl::list<std::string> FunctionSeedAllowList(
    "attributor-function-seed-allow-list", cl::Hidden,
    cl::desc("Comma separated list of function names that are "
             "allowed to be seeded."),
    cl::CommaSeparated);
#endif

static cl::opt<bool>
    DumpDepGraph("attributor-dump-dep-graph", cl::Hidden,
                 cl::desc("Dump the dependency graph to dot files."),
                 cl::init(false));

static cl::opt<std::string> DepGraphDotFileNamePrefix(
    "attributor-depgraph-dot-filename-prefix", cl::Hidden,
    cl::desc("The prefix used for the CallGraph dot file names."));

static cl::opt<bool> ViewDepGraph("attributor-view-dep-graph", cl::Hidden,
                                  cl::desc("View the dependency graph."),
                                  cl::init(false));

static cl::opt<bool> PrintDependencies("attributor-print-dep", cl::Hidden,
                                       cl::desc("Print attribute dependencies"),
                                       cl::init(false));

static cl::opt<bool> EnableCallSiteSpecific(
    "attributor-enable-call-site-specific-deduction", cl::Hidden,
    cl::desc("Allow the Attributor to do call site specific analysis"),
    cl::init(false));

static cl::opt<bool>
    PrintCallGraph("attributor-print-call-graph", cl::Hidden,
                   cl::desc("Print Attributor's internal call graph"),
                   cl::init(false));

static cl::opt<bool> SimplifyAllLoads("attributor-simplify-all-loads",
                                      cl::Hidden,
                                      cl::desc("Try to simplify all loads."),
                                      cl::init(true));

static cl::opt<bool> CloseWorldAssumption(
    "attributor-assume-closed-world", cl::Hidden,
    cl::desc("Should a closed world be assumed, or not. Default if not set."));

/// Logic operators for the change status enum class.
///
///{
ChangeStatus llvm::operator|(ChangeStatus L, ChangeStatus R) { … }
ChangeStatus &llvm::operator|=(ChangeStatus &L, ChangeStatus R) { … }
ChangeStatus llvm::operator&(ChangeStatus L, ChangeStatus R) { … }
ChangeStatus &llvm::operator&=(ChangeStatus &L, ChangeStatus R) { … }
///}

bool AA::isGPU(const Module &M) { … }

bool AA::isNoSyncInst(Attributor &A, const Instruction &I,
                      const AbstractAttribute &QueryingAA) { … }

bool AA::isDynamicallyUnique(Attributor &A, const AbstractAttribute &QueryingAA,
                             const Value &V, bool ForAnalysisOnly) { … }

Constant *
AA::getInitialValueForObj(Attributor &A, const AbstractAttribute &QueryingAA,
                          Value &Obj, Type &Ty, const TargetLibraryInfo *TLI,
                          const DataLayout &DL, AA::RangeTy *RangePtr) { … }

bool AA::isValidInScope(const Value &V, const Function *Scope) { … }

bool AA::isValidAtPosition(const AA::ValueAndContext &VAC,
                           InformationCache &InfoCache) { … }

Value *AA::getWithType(Value &V, Type &Ty) { … }

std::optional<Value *>
AA::combineOptionalValuesInAAValueLatice(const std::optional<Value *> &A,
                                         const std::optional<Value *> &B,
                                         Type *Ty) { … }

template <bool IsLoad, typename Ty>
static bool getPotentialCopiesOfMemoryValue(
    Attributor &A, Ty &I, SmallSetVector<Value *, 4> &PotentialCopies,
    SmallSetVector<Instruction *, 4> *PotentialValueOrigins,
    const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation,
    bool OnlyExact) { … }

bool AA::getPotentiallyLoadedValues(
    Attributor &A, LoadInst &LI, SmallSetVector<Value *, 4> &PotentialValues,
    SmallSetVector<Instruction *, 4> &PotentialValueOrigins,
    const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation,
    bool OnlyExact) { … }

bool AA::getPotentialCopiesOfStoredValue(
    Attributor &A, StoreInst &SI, SmallSetVector<Value *, 4> &PotentialCopies,
    const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation,
    bool OnlyExact) { … }

static bool isAssumedReadOnlyOrReadNone(Attributor &A, const IRPosition &IRP,
                                        const AbstractAttribute &QueryingAA,
                                        bool RequireReadNone, bool &IsKnown) { … }

bool AA::isAssumedReadOnly(Attributor &A, const IRPosition &IRP,
                           const AbstractAttribute &QueryingAA, bool &IsKnown) { … }
bool AA::isAssumedReadNone(Attributor &A, const IRPosition &IRP,
                           const AbstractAttribute &QueryingAA, bool &IsKnown) { … }

static bool
isPotentiallyReachable(Attributor &A, const Instruction &FromI,
                       const Instruction *ToI, const Function &ToFn,
                       const AbstractAttribute &QueryingAA,
                       const AA::InstExclusionSetTy *ExclusionSet,
                       std::function<bool(const Function &F)> GoBackwardsCB) { … }

bool AA::isPotentiallyReachable(
    Attributor &A, const Instruction &FromI, const Instruction &ToI,
    const AbstractAttribute &QueryingAA,
    const AA::InstExclusionSetTy *ExclusionSet,
    std::function<bool(const Function &F)> GoBackwardsCB) { … }

bool AA::isPotentiallyReachable(
    Attributor &A, const Instruction &FromI, const Function &ToFn,
    const AbstractAttribute &QueryingAA,
    const AA::InstExclusionSetTy *ExclusionSet,
    std::function<bool(const Function &F)> GoBackwardsCB) { … }

bool AA::isAssumedThreadLocalObject(Attributor &A, Value &Obj,
                                    const AbstractAttribute &QueryingAA) { … }

bool AA::isPotentiallyAffectedByBarrier(Attributor &A, const Instruction &I,
                                        const AbstractAttribute &QueryingAA) { … }

bool AA::isPotentiallyAffectedByBarrier(Attributor &A,
                                        ArrayRef<const Value *> Ptrs,
                                        const AbstractAttribute &QueryingAA,
                                        const Instruction *CtxI) { … }

/// Return true if \p New is equal or worse than \p Old.
static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) { … }

/// Return true if the information provided by \p Attr was added to the
/// attribute set \p AttrSet. This is only the case if it was not already
/// present in \p AttrSet.
static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr,
                             AttributeSet AttrSet, bool ForceReplace,
                             AttrBuilder &AB) { … }

Argument *IRPosition::getAssociatedArgument() const { … }

ChangeStatus AbstractAttribute::update(Attributor &A) { … }

Attributor::Attributor(SetVector<Function *> &Functions,
                       InformationCache &InfoCache,
                       AttributorConfig Configuration)
    : … { … }

bool Attributor::getAttrsFromAssumes(const IRPosition &IRP,
                                     Attribute::AttrKind AK,
                                     SmallVectorImpl<Attribute> &Attrs) { … }

template <typename DescTy>
ChangeStatus
Attributor::updateAttrMap(const IRPosition &IRP, ArrayRef<DescTy> AttrDescs,
                          function_ref<bool(const DescTy &, AttributeSet,
                                            AttributeMask &, AttrBuilder &)>
                              CB) { … }

bool Attributor::hasAttr(const IRPosition &IRP,
                         ArrayRef<Attribute::AttrKind> AttrKinds,
                         bool IgnoreSubsumingPositions,
                         Attribute::AttrKind ImpliedAttributeKind) { … }

void Attributor::getAttrs(const IRPosition &IRP,
                          ArrayRef<Attribute::AttrKind> AttrKinds,
                          SmallVectorImpl<Attribute> &Attrs,
                          bool IgnoreSubsumingPositions) { … }

ChangeStatus Attributor::removeAttrs(const IRPosition &IRP,
                                     ArrayRef<Attribute::AttrKind> AttrKinds) { … }

ChangeStatus Attributor::removeAttrs(const IRPosition &IRP,
                                     ArrayRef<StringRef> Attrs) { … }

ChangeStatus Attributor::manifestAttrs(const IRPosition &IRP,
                                       ArrayRef<Attribute> Attrs,
                                       bool ForceReplace) { … }

const IRPosition IRPosition::EmptyKey(DenseMapInfo<void *>::getEmptyKey());
const IRPosition
    IRPosition::TombstoneKey(DenseMapInfo<void *>::getTombstoneKey());

SubsumingPositionIterator::SubsumingPositionIterator(const IRPosition &IRP) { … }

void IRPosition::verify() { … }

std::optional<Constant *>
Attributor::getAssumedConstant(const IRPosition &IRP,
                               const AbstractAttribute &AA,
                               bool &UsedAssumedInformation) { … }

std::optional<Value *> Attributor::getAssumedSimplified(
    const IRPosition &IRP, const AbstractAttribute *AA,
    bool &UsedAssumedInformation, AA::ValueScope S) { … }

bool Attributor::getAssumedSimplifiedValues(
    const IRPosition &InitialIRP, const AbstractAttribute *AA,
    SmallVectorImpl<AA::ValueAndContext> &Values, AA::ValueScope S,
    bool &UsedAssumedInformation, bool RecurseForSelectAndPHI) { … }

std::optional<Value *> Attributor::translateArgumentToCallSiteContent(
    std::optional<Value *> V, CallBase &CB, const AbstractAttribute &AA,
    bool &UsedAssumedInformation) { … }

Attributor::~Attributor() { … }

bool Attributor::isAssumedDead(const AbstractAttribute &AA,
                               const AAIsDead *FnLivenessAA,
                               bool &UsedAssumedInformation,
                               bool CheckBBLivenessOnly, DepClassTy DepClass) { … }

bool Attributor::isAssumedDead(const Use &U,
                               const AbstractAttribute *QueryingAA,
                               const AAIsDead *FnLivenessAA,
                               bool &UsedAssumedInformation,
                               bool CheckBBLivenessOnly, DepClassTy DepClass) { … }

bool Attributor::isAssumedDead(const Instruction &I,
                               const AbstractAttribute *QueryingAA,
                               const AAIsDead *FnLivenessAA,
                               bool &UsedAssumedInformation,
                               bool CheckBBLivenessOnly, DepClassTy DepClass,
                               bool CheckForDeadStore) { … }

bool Attributor::isAssumedDead(const IRPosition &IRP,
                               const AbstractAttribute *QueryingAA,
                               const AAIsDead *FnLivenessAA,
                               bool &UsedAssumedInformation,
                               bool CheckBBLivenessOnly, DepClassTy DepClass) { … }

bool Attributor::isAssumedDead(const BasicBlock &BB,
                               const AbstractAttribute *QueryingAA,
                               const AAIsDead *FnLivenessAA,
                               DepClassTy DepClass) { … }

bool Attributor::checkForAllCallees(
    function_ref<bool(ArrayRef<const Function *>)> Pred,
    const AbstractAttribute &QueryingAA, const CallBase &CB) { … }

bool canMarkAsVisited(const User *Usr) { … }

bool Attributor::checkForAllUses(
    function_ref<bool(const Use &, bool &)> Pred,
    const AbstractAttribute &QueryingAA, const Value &V,
    bool CheckBBLivenessOnly, DepClassTy LivenessDepClass,
    bool IgnoreDroppableUses,
    function_ref<bool(const Use &OldU, const Use &NewU)> EquivalentUseCB) { … }

bool Attributor::checkForAllCallSites(function_ref<bool(AbstractCallSite)> Pred,
                                      const AbstractAttribute &QueryingAA,
                                      bool RequireAllCallSites,
                                      bool &UsedAssumedInformation) { … }

bool Attributor::checkForAllCallSites(function_ref<bool(AbstractCallSite)> Pred,
                                      const Function &Fn,
                                      bool RequireAllCallSites,
                                      const AbstractAttribute *QueryingAA,
                                      bool &UsedAssumedInformation,
                                      bool CheckPotentiallyDead) { … }

bool Attributor::shouldPropagateCallBaseContext(const IRPosition &IRP) { … }

bool Attributor::checkForAllReturnedValues(function_ref<bool(Value &)> Pred,
                                           const AbstractAttribute &QueryingAA,
                                           AA::ValueScope S,
                                           bool RecurseForSelectAndPHI) { … }

static bool checkForAllInstructionsImpl(
    Attributor *A, InformationCache::OpcodeInstMapTy &OpcodeInstMap,
    function_ref<bool(Instruction &)> Pred, const AbstractAttribute *QueryingAA,
    const AAIsDead *LivenessAA, ArrayRef<unsigned> Opcodes,
    bool &UsedAssumedInformation, bool CheckBBLivenessOnly = false,
    bool CheckPotentiallyDead = false) { … }

bool Attributor::checkForAllInstructions(function_ref<bool(Instruction &)> Pred,
                                         const Function *Fn,
                                         const AbstractAttribute *QueryingAA,
                                         ArrayRef<unsigned> Opcodes,
                                         bool &UsedAssumedInformation,
                                         bool CheckBBLivenessOnly,
                                         bool CheckPotentiallyDead) { … }

bool Attributor::checkForAllInstructions(function_ref<bool(Instruction &)> Pred,
                                         const AbstractAttribute &QueryingAA,
                                         ArrayRef<unsigned> Opcodes,
                                         bool &UsedAssumedInformation,
                                         bool CheckBBLivenessOnly,
                                         bool CheckPotentiallyDead) { … }

bool Attributor::checkForAllReadWriteInstructions(
    function_ref<bool(Instruction &)> Pred, AbstractAttribute &QueryingAA,
    bool &UsedAssumedInformation) { … }

void Attributor::runTillFixpoint() { … }

void Attributor::registerForUpdate(AbstractAttribute &AA) { … }

ChangeStatus Attributor::manifestAttributes() { … }

void Attributor::identifyDeadInternalFunctions() { … }

ChangeStatus Attributor::cleanupIR() { … }

ChangeStatus Attributor::run() { … }

ChangeStatus Attributor::updateAA(AbstractAttribute &AA) { … }

void Attributor::createShallowWrapper(Function &F) { … }

bool Attributor::isInternalizable(Function &F) { … }

Function *Attributor::internalizeFunction(Function &F, bool Force) { … }

bool Attributor::internalizeFunctions(SmallPtrSetImpl<Function *> &FnSet,
                                      DenseMap<Function *, Function *> &FnMap) { … }

bool Attributor::isValidFunctionSignatureRewrite(
    Argument &Arg, ArrayRef<Type *> ReplacementTypes) { … }

bool Attributor::registerFunctionSignatureRewrite(
    Argument &Arg, ArrayRef<Type *> ReplacementTypes,
    ArgumentReplacementInfo::CalleeRepairCBTy &&CalleeRepairCB,
    ArgumentReplacementInfo::ACSRepairCBTy &&ACSRepairCB) { … }

bool Attributor::shouldSeedAttribute(AbstractAttribute &AA) { … }

ChangeStatus Attributor::rewriteFunctionSignatures(
    SmallSetVector<Function *, 8> &ModifiedFns) { … }

void InformationCache::initializeInformationCache(const Function &CF,
                                                  FunctionInfo &FI) { … }

InformationCache::FunctionInfo::~FunctionInfo() { … }

const ArrayRef<Function *>
InformationCache::getIndirectlyCallableFunctions(Attributor &A) const { … }

std::optional<unsigned> InformationCache::getFlatAddressSpace() const { … }

void Attributor::recordDependence(const AbstractAttribute &FromAA,
                                  const AbstractAttribute &ToAA,
                                  DepClassTy DepClass) { … }

void Attributor::rememberDependences() { … }

template <Attribute::AttrKind AK, typename AAType>
void Attributor::checkAndQueryIRAttr(const IRPosition &IRP,
                                     AttributeSet Attrs) { … }

void Attributor::identifyDefaultAbstractAttributes(Function &F) { … }

bool Attributor::isClosedWorldModule() const { … }

/// Helpers to ease debugging through output streams and print calls.
///
///{
raw_ostream &llvm::operator<<(raw_ostream &OS, ChangeStatus S) { … }

raw_ostream &llvm::operator<<(raw_ostream &OS, IRPosition::Kind AP) { … }

raw_ostream &llvm::operator<<(raw_ostream &OS, const IRPosition &Pos) { … }

raw_ostream &llvm::operator<<(raw_ostream &OS, const IntegerRangeState &S) { … }

raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &S) { … }

raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) { … }

raw_ostream &llvm::operator<<(raw_ostream &OS,
                              const PotentialConstantIntValuesState &S) { … }

raw_ostream &llvm::operator<<(raw_ostream &OS,
                              const PotentialLLVMValuesState &S) { … }

void AbstractAttribute::print(Attributor *A, raw_ostream &OS) const { … }

void AbstractAttribute::printWithDeps(raw_ostream &OS) const { … }

raw_ostream &llvm::operator<<(raw_ostream &OS,
                              const AAPointerInfo::Access &Acc) { … }
///}

/// ----------------------------------------------------------------------------
///                       Pass (Manager) Boilerplate
/// ----------------------------------------------------------------------------

static bool runAttributorOnFunctions(InformationCache &InfoCache,
                                     SetVector<Function *> &Functions,
                                     AnalysisGetter &AG,
                                     CallGraphUpdater &CGUpdater,
                                     bool DeleteFns, bool IsModulePass) { … }

static bool runAttributorLightOnFunctions(InformationCache &InfoCache,
                                          SetVector<Function *> &Functions,
                                          AnalysisGetter &AG,
                                          CallGraphUpdater &CGUpdater,
                                          FunctionAnalysisManager &FAM,
                                          bool IsModulePass) { … }

void AADepGraph::viewGraph() { … }

void AADepGraph::dumpGraph() { … }

void AADepGraph::print() { … }

PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) { … }

PreservedAnalyses AttributorCGSCCPass::run(LazyCallGraph::SCC &C,
                                           CGSCCAnalysisManager &AM,
                                           LazyCallGraph &CG,
                                           CGSCCUpdateResult &UR) { … }

PreservedAnalyses AttributorLightPass::run(Module &M,
                                           ModuleAnalysisManager &AM) { … }

PreservedAnalyses AttributorLightCGSCCPass::run(LazyCallGraph::SCC &C,
                                                CGSCCAnalysisManager &AM,
                                                LazyCallGraph &CG,
                                                CGSCCUpdateResult &UR) { … }
namespace llvm {

template <> struct GraphTraits<AADepGraphNode *> { … };

template <>
struct GraphTraits<AADepGraph *> : public GraphTraits<AADepGraphNode *> { … };

template <> struct DOTGraphTraits<AADepGraph *> : public DefaultDOTGraphTraits { … };

} // end namespace llvm