FunctionAttrs.cpp | Explore in Territory

//===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
/// \file
/// This file implements interprocedural passes which walk the
/// call-graph deducing and/or propagating function attributes.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/IPO/FunctionAttrs.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/CGSCCPassManager.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/Analysis/CallGraphSCCPass.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/LazyCallGraph.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/ModuleSummaryIndex.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/IPO.h"
#include "llvm/Transforms/Utils/Local.h"
#include <cassert>
#include <iterator>
#include <map>
#include <optional>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumMemoryAttr, "Number of functions with improved memory attribute");
STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
STATISTIC(NumReturned, "Number of arguments marked returned");
STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
STATISTIC(NumWriteOnlyArg, "Number of arguments marked writeonly");
STATISTIC(NumNoAlias, "Number of function returns marked noalias");
STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
STATISTIC(NumNoUndefReturn, "Number of function returns marked noundef");
STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
STATISTIC(NumNoUnwind, "Number of functions marked as nounwind");
STATISTIC(NumNoFree, "Number of functions marked as nofree");
STATISTIC(NumWillReturn, "Number of functions marked as willreturn");
STATISTIC(NumNoSync, "Number of functions marked as nosync");
STATISTIC(NumCold, "Number of functions marked as cold");

STATISTIC(NumThinLinkNoRecurse,
          "Number of functions marked as norecurse during thinlink");
STATISTIC(NumThinLinkNoUnwind,
          "Number of functions marked as nounwind during thinlink");

static cl::opt<bool> EnableNonnullArgPropagation(
    "enable-nonnull-arg-prop", cl::init(true), cl::Hidden,
    cl::desc("Try to propagate nonnull argument attributes from callsites to "
             "caller functions."));

static cl::opt<bool> DisableNoUnwindInference(
    "disable-nounwind-inference", cl::Hidden,
    cl::desc("Stop inferring nounwind attribute during function-attrs pass"));

static cl::opt<bool> DisableNoFreeInference(
    "disable-nofree-inference", cl::Hidden,
    cl::desc("Stop inferring nofree attribute during function-attrs pass"));

static cl::opt<bool> DisableThinLTOPropagation(
    "disable-thinlto-funcattrs", cl::init(true), cl::Hidden,
    cl::desc("Don't propagate function-attrs in thinLTO"));

namespace {

SCCNodeSet;

} // end anonymous namespace

static void addLocAccess(MemoryEffects &ME, const MemoryLocation &Loc,
                         ModRefInfo MR, AAResults &AAR) { … }

static void addArgLocs(MemoryEffects &ME, const CallBase *Call,
                       ModRefInfo ArgMR, AAResults &AAR) { … }

/// Returns the memory access attribute for function F using AAR for AA results,
/// where SCCNodes is the current SCC.
///
/// If ThisBody is true, this function may examine the function body and will
/// return a result pertaining to this copy of the function. If it is false, the
/// result will be based only on AA results for the function declaration; it
/// will be assumed that some other (perhaps less optimized) version of the
/// function may be selected at link time.
///
/// The return value is split into two parts: Memory effects that always apply,
/// and additional memory effects that apply if any of the functions in the SCC
/// can access argmem.
static std::pair<MemoryEffects, MemoryEffects>
checkFunctionMemoryAccess(Function &F, bool ThisBody, AAResults &AAR,
                          const SCCNodeSet &SCCNodes) { … }

MemoryEffects llvm::computeFunctionBodyMemoryAccess(Function &F,
                                                    AAResults &AAR) { … }

/// Deduce readonly/readnone/writeonly attributes for the SCC.
template <typename AARGetterT>
static void addMemoryAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter,
                           SmallSet<Function *, 8> &Changed) { … }

// Compute definitive function attributes for a function taking into account
// prevailing definitions and linkage types
static FunctionSummary *calculatePrevailingSummary(
    ValueInfo VI,
    DenseMap<ValueInfo, FunctionSummary *> &CachedPrevailingSummary,
    function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
        IsPrevailing) { … }

bool llvm::thinLTOPropagateFunctionAttrs(
    ModuleSummaryIndex &Index,
    function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
        IsPrevailing) { … }

namespace {

/// For a given pointer Argument, this retains a list of Arguments of functions
/// in the same SCC that the pointer data flows into. We use this to build an
/// SCC of the arguments.
struct ArgumentGraphNode { … };

class ArgumentGraph { … };

/// This tracker checks whether callees are in the SCC, and if so it does not
/// consider that a capture, instead adding it to the "Uses" list and
/// continuing with the analysis.
struct ArgumentUsesTracker : public CaptureTracker { … };

} // end anonymous namespace

namespace llvm {

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

template <>
struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> { … };

} // end namespace llvm

/// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
static Attribute::AttrKind
determinePointerAccessAttrs(Argument *A,
                            const SmallPtrSet<Argument *, 8> &SCCNodes) { … }

/// Deduce returned attributes for the SCC.
static void addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes,
                                     SmallSet<Function *, 8> &Changed) { … }

/// If a callsite has arguments that are also arguments to the parent function,
/// try to propagate attributes from the callsite's arguments to the parent's
/// arguments. This may be important because inlining can cause information loss
/// when attribute knowledge disappears with the inlined call.
static bool addArgumentAttrsFromCallsites(Function &F) { … }

static bool addAccessAttr(Argument *A, Attribute::AttrKind R) { … }

/// Deduce nocapture attributes for the SCC.
static void addArgumentAttrs(const SCCNodeSet &SCCNodes,
                             SmallSet<Function *, 8> &Changed) { … }

/// Tests whether a function is "malloc-like".
///
/// A function is "malloc-like" if it returns either null or a pointer that
/// doesn't alias any other pointer visible to the caller.
static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) { … }

/// Deduce noalias attributes for the SCC.
static void addNoAliasAttrs(const SCCNodeSet &SCCNodes,
                            SmallSet<Function *, 8> &Changed) { … }

/// Tests whether this function is known to not return null.
///
/// Requires that the function returns a pointer.
///
/// Returns true if it believes the function will not return a null, and sets
/// \p Speculative based on whether the returned conclusion is a speculative
/// conclusion due to SCC calls.
static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
                            bool &Speculative) { … }

/// Deduce nonnull attributes for the SCC.
static void addNonNullAttrs(const SCCNodeSet &SCCNodes,
                            SmallSet<Function *, 8> &Changed) { … }

/// Deduce noundef attributes for the SCC.
static void addNoUndefAttrs(const SCCNodeSet &SCCNodes,
                            SmallSet<Function *, 8> &Changed) { … }

namespace {

/// Collects a set of attribute inference requests and performs them all in one
/// go on a single SCC Node. Inference involves scanning function bodies
/// looking for instructions that violate attribute assumptions.
/// As soon as all the bodies are fine we are free to set the attribute.
/// Customization of inference for individual attributes is performed by
/// providing a handful of predicates for each attribute.
class AttributeInferer { … };

/// Perform all the requested attribute inference actions according to the
/// attribute predicates stored before.
void AttributeInferer::run(const SCCNodeSet &SCCNodes,
                           SmallSet<Function *, 8> &Changed) { … }

struct SCCNodesResult { … };

} // end anonymous namespace

/// Helper for non-Convergent inference predicate InstrBreaksAttribute.
static bool InstrBreaksNonConvergent(Instruction &I,
                                     const SCCNodeSet &SCCNodes) { … }

/// Helper for NoUnwind inference predicate InstrBreaksAttribute.
static bool InstrBreaksNonThrowing(Instruction &I, const SCCNodeSet &SCCNodes) { … }

/// Helper for NoFree inference predicate InstrBreaksAttribute.
static bool InstrBreaksNoFree(Instruction &I, const SCCNodeSet &SCCNodes) { … }

// Return true if this is an atomic which has an ordering stronger than
// unordered.  Note that this is different than the predicate we use in
// Attributor.  Here we chose to be conservative and consider monotonic
// operations potentially synchronizing.  We generally don't do much with
// monotonic operations, so this is simply risk reduction.
static bool isOrderedAtomic(Instruction *I) { … }

static bool InstrBreaksNoSync(Instruction &I, const SCCNodeSet &SCCNodes) { … }

/// Attempt to remove convergent function attribute when possible.
///
/// Returns true if any changes to function attributes were made.
static void inferConvergent(const SCCNodeSet &SCCNodes,
                            SmallSet<Function *, 8> &Changed) { … }

/// Infer attributes from all functions in the SCC by scanning every
/// instruction for compliance to the attribute assumptions.
///
/// Returns true if any changes to function attributes were made.
static void inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes,
                                         SmallSet<Function *, 8> &Changed) { … }

static void addNoRecurseAttrs(const SCCNodeSet &SCCNodes,
                              SmallSet<Function *, 8> &Changed) { … }

static bool instructionDoesNotReturn(Instruction &I) { … }

// A basic block can only return if it terminates with a ReturnInst and does not
// contain calls to noreturn functions.
static bool basicBlockCanReturn(BasicBlock &BB) { … }

// FIXME: this doesn't handle recursion.
static bool canReturn(Function &F) { … }


// Set the noreturn function attribute if possible.
static void addNoReturnAttrs(const SCCNodeSet &SCCNodes,
                             SmallSet<Function *, 8> &Changed) { … }

static bool allPathsGoThroughCold(Function &F) { … }

// Set the cold function attribute if possible.
static void addColdAttrs(const SCCNodeSet &SCCNodes,
                         SmallSet<Function *, 8> &Changed) { … }

static bool functionWillReturn(const Function &F) { … }

// Set the willreturn function attribute if possible.
static void addWillReturn(const SCCNodeSet &SCCNodes,
                          SmallSet<Function *, 8> &Changed) { … }

static SCCNodesResult createSCCNodeSet(ArrayRef<Function *> Functions) { … }

template <typename AARGetterT>
static SmallSet<Function *, 8>
deriveAttrsInPostOrder(ArrayRef<Function *> Functions, AARGetterT &&AARGetter,
                       bool ArgAttrsOnly) { … }

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

void PostOrderFunctionAttrsPass::printPipeline(
    raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { … }

template <typename AARGetterT>
static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) { … }

static bool addNoRecurseAttrsTopDown(Function &F) { … }

static bool deduceFunctionAttributeInRPO(Module &M, LazyCallGraph &CG) { … }

PreservedAnalyses
ReversePostOrderFunctionAttrsPass::run(Module &M, ModuleAnalysisManager &AM) { … }
llvm/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
