GlobalOpt.cpp | Explore in Territory

//===- GlobalOpt.cpp - Optimize Global Variables --------------------------===//
//
// 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 pass transforms simple global variables that never have their address
// taken.  If obviously true, it marks read/write globals as constant, deletes
// variables only stored to, etc.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/IPO/GlobalOpt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/Twine.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/BinaryFormat/Dwarf.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CallingConv.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/AtomicOrdering.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.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/CtorUtils.h"
#include "llvm/Transforms/Utils/Evaluator.h"
#include "llvm/Transforms/Utils/GlobalStatus.h"
#include "llvm/Transforms/Utils/Local.h"
#include <cassert>
#include <cstdint>
#include <optional>
#include <utility>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumMarked    , "Number of globals marked constant");
STATISTIC(NumUnnamed   , "Number of globals marked unnamed_addr");
STATISTIC(NumSRA       , "Number of aggregate globals broken into scalars");
STATISTIC(NumSubstitute,"Number of globals with initializers stored into them");
STATISTIC(NumDeleted   , "Number of globals deleted");
STATISTIC(NumGlobUses  , "Number of global uses devirtualized");
STATISTIC(NumLocalized , "Number of globals localized");
STATISTIC(NumShrunkToBool  , "Number of global vars shrunk to booleans");
STATISTIC(NumFastCallFns   , "Number of functions converted to fastcc");
STATISTIC(NumCtorsEvaluated, "Number of static ctors evaluated");
STATISTIC(NumNestRemoved   , "Number of nest attributes removed");
STATISTIC(NumAliasesResolved, "Number of global aliases resolved");
STATISTIC(NumAliasesRemoved, "Number of global aliases eliminated");
STATISTIC(NumCXXDtorsRemoved, "Number of global C++ destructors removed");
STATISTIC(NumAtExitRemoved, "Number of atexit handlers removed");
STATISTIC(NumInternalFunc, "Number of internal functions");
STATISTIC(NumColdCC, "Number of functions marked coldcc");
STATISTIC(NumIFuncsResolved, "Number of statically resolved IFuncs");
STATISTIC(NumIFuncsDeleted, "Number of IFuncs removed");

static cl::opt<bool>
    EnableColdCCStressTest("enable-coldcc-stress-test",
                           cl::desc("Enable stress test of coldcc by adding "
                                    "calling conv to all internal functions."),
                           cl::init(false), cl::Hidden);

static cl::opt<int> ColdCCRelFreq(
    "coldcc-rel-freq", cl::Hidden, cl::init(2),
    cl::desc(
        "Maximum block frequency, expressed as a percentage of caller's "
        "entry frequency, for a call site to be considered cold for enabling"
        "coldcc"));

/// Is this global variable possibly used by a leak checker as a root?  If so,
/// we might not really want to eliminate the stores to it.
static bool isLeakCheckerRoot(GlobalVariable *GV) { … }

/// Given a value that is stored to a global but never read, determine whether
/// it's safe to remove the store and the chain of computation that feeds the
/// store.
static bool IsSafeComputationToRemove(
    Value *V, function_ref<TargetLibraryInfo &(Function &)> GetTLI) { … }

/// This GV is a pointer root.  Loop over all users of the global and clean up
/// any that obviously don't assign the global a value that isn't dynamically
/// allocated.
static bool
CleanupPointerRootUsers(GlobalVariable *GV,
                        function_ref<TargetLibraryInfo &(Function &)> GetTLI) { … }

/// We just marked GV constant.  Loop over all users of the global, cleaning up
/// the obvious ones.  This is largely just a quick scan over the use list to
/// clean up the easy and obvious cruft.  This returns true if it made a change.
static bool CleanupConstantGlobalUsers(GlobalVariable *GV,
                                       const DataLayout &DL) { … }

/// Part of the global at a specific offset, which is only accessed through
/// loads and stores with the given type.
struct GlobalPart { … };

/// Look at all uses of the global and determine which (offset, type) pairs it
/// can be split into.
static bool collectSRATypes(DenseMap<uint64_t, GlobalPart> &Parts,
                            GlobalVariable *GV, const DataLayout &DL) { … }

/// Copy over the debug info for a variable to its SRA replacements.
static void transferSRADebugInfo(GlobalVariable *GV, GlobalVariable *NGV,
                                 uint64_t FragmentOffsetInBits,
                                 uint64_t FragmentSizeInBits,
                                 uint64_t VarSize) { … }

/// Perform scalar replacement of aggregates on the specified global variable.
/// This opens the door for other optimizations by exposing the behavior of the
/// program in a more fine-grained way.  We have determined that this
/// transformation is safe already.  We return the first global variable we
/// insert so that the caller can reprocess it.
static GlobalVariable *SRAGlobal(GlobalVariable *GV, const DataLayout &DL) { … }

/// Return true if all users of the specified value will trap if the value is
/// dynamically null.  PHIs keeps track of any phi nodes we've seen to avoid
/// reprocessing them.
static bool AllUsesOfValueWillTrapIfNull(const Value *V,
                                        SmallPtrSetImpl<const PHINode*> &PHIs) { … }

/// Return true if all uses of any loads from GV will trap if the loaded value
/// is null.  Note that this also permits comparisons of the loaded value
/// against null, as a special case.
static bool allUsesOfLoadedValueWillTrapIfNull(const GlobalVariable *GV) { … }

/// Get all the loads/store uses for global variable \p GV.
static void allUsesOfLoadAndStores(GlobalVariable *GV,
                                   SmallVector<Value *, 4> &Uses) { … }

static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) { … }

/// The specified global has only one non-null value stored into it.  If there
/// are uses of the loaded value that would trap if the loaded value is
/// dynamically null, then we know that they cannot be reachable with a null
/// optimize away the load.
static bool OptimizeAwayTrappingUsesOfLoads(
    GlobalVariable *GV, Constant *LV, const DataLayout &DL,
    function_ref<TargetLibraryInfo &(Function &)> GetTLI) { … }

/// Walk the use list of V, constant folding all of the instructions that are
/// foldable.
static void ConstantPropUsersOf(Value *V, const DataLayout &DL,
                                TargetLibraryInfo *TLI) { … }

/// This function takes the specified global variable, and transforms the
/// program as if it always contained the result of the specified malloc.
/// Because it is always the result of the specified malloc, there is no reason
/// to actually DO the malloc.  Instead, turn the malloc into a global, and any
/// loads of GV as uses of the new global.
static GlobalVariable *
OptimizeGlobalAddressOfAllocation(GlobalVariable *GV, CallInst *CI,
                                  uint64_t AllocSize, Constant *InitVal,
                                  const DataLayout &DL,
                                  TargetLibraryInfo *TLI) { … }

/// Scan the use-list of GV checking to make sure that there are no complex uses
/// of GV.  We permit simple things like dereferencing the pointer, but not
/// storing through the address, unless it is to the specified global.
static bool
valueIsOnlyUsedLocallyOrStoredToOneGlobal(const CallInst *CI,
                                          const GlobalVariable *GV) { … }

/// If we have a global that is only initialized with a fixed size allocation
/// try to transform the program to use global memory instead of heap
/// allocated memory. This eliminates dynamic allocation, avoids an indirection
/// accessing the data, and exposes the resultant global to further GlobalOpt.
static bool tryToOptimizeStoreOfAllocationToGlobal(GlobalVariable *GV,
                                                   CallInst *CI,
                                                   const DataLayout &DL,
                                                   TargetLibraryInfo *TLI) { … }

// Try to optimize globals based on the knowledge that only one value (besides
// its initializer) is ever stored to the global.
static bool
optimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal,
                         const DataLayout &DL,
                         function_ref<TargetLibraryInfo &(Function &)> GetTLI) { … }

/// At this point, we have learned that the only two values ever stored into GV
/// are its initializer and OtherVal.  See if we can shrink the global into a
/// boolean and select between the two values whenever it is used.  This exposes
/// the values to other scalar optimizations.
static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) { … }

static bool
deleteIfDead(GlobalValue &GV,
             SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats,
             function_ref<void(Function &)> DeleteFnCallback = nullptr) { … }

static bool isPointerValueDeadOnEntryToFunction(
    const Function *F, GlobalValue *GV,
    function_ref<DominatorTree &(Function &)> LookupDomTree) { … }

// For a global variable with one store, if the store dominates any loads,
// those loads will always load the stored value (as opposed to the
// initializer), even in the presence of recursion.
static bool forwardStoredOnceStore(
    GlobalVariable *GV, const StoreInst *StoredOnceStore,
    function_ref<DominatorTree &(Function &)> LookupDomTree) { … }

/// Analyze the specified global variable and optimize
/// it if possible.  If we make a change, return true.
static bool
processInternalGlobal(GlobalVariable *GV, const GlobalStatus &GS,
                      function_ref<TargetTransformInfo &(Function &)> GetTTI,
                      function_ref<TargetLibraryInfo &(Function &)> GetTLI,
                      function_ref<DominatorTree &(Function &)> LookupDomTree) { … }

/// Analyze the specified global variable and optimize it if possible.  If we
/// make a change, return true.
static bool
processGlobal(GlobalValue &GV,
              function_ref<TargetTransformInfo &(Function &)> GetTTI,
              function_ref<TargetLibraryInfo &(Function &)> GetTLI,
              function_ref<DominatorTree &(Function &)> LookupDomTree) { … }

/// Walk all of the direct calls of the specified function, changing them to
/// FastCC.
static void ChangeCalleesToFastCall(Function *F) { … }

static AttributeList StripAttr(LLVMContext &C, AttributeList Attrs,
                               Attribute::AttrKind A) { … }

static void RemoveAttribute(Function *F, Attribute::AttrKind A) { … }

/// Return true if this is a calling convention that we'd like to change.  The
/// idea here is that we don't want to mess with the convention if the user
/// explicitly requested something with performance implications like coldcc,
/// GHC, or anyregcc.
static bool hasChangeableCCImpl(Function *F) { … }

ChangeableCCCacheTy;
static bool hasChangeableCC(Function *F,
                            ChangeableCCCacheTy &ChangeableCCCache) { … }

/// Return true if the block containing the call site has a BlockFrequency of
/// less than ColdCCRelFreq% of the entry block.
static bool isColdCallSite(CallBase &CB, BlockFrequencyInfo &CallerBFI) { … }

// This function checks if the input function F is cold at all call sites. It
// also looks each call site's containing function, returning false if the
// caller function contains other non cold calls. The input vector AllCallsCold
// contains a list of functions that only have call sites in cold blocks.
static bool
isValidCandidateForColdCC(Function &F,
                          function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
                          const std::vector<Function *> &AllCallsCold) { … }

static void changeCallSitesToColdCC(Function *F) { … }

// This function iterates over all the call instructions in the input Function
// and checks that all call sites are in cold blocks and are allowed to use the
// coldcc calling convention.
static bool
hasOnlyColdCalls(Function &F,
                 function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
                 ChangeableCCCacheTy &ChangeableCCCache) { … }

static bool hasMustTailCallers(Function *F) { … }

static bool hasInvokeCallers(Function *F) { … }

static void RemovePreallocated(Function *F) { … }

static bool
OptimizeFunctions(Module &M,
                  function_ref<TargetLibraryInfo &(Function &)> GetTLI,
                  function_ref<TargetTransformInfo &(Function &)> GetTTI,
                  function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
                  function_ref<DominatorTree &(Function &)> LookupDomTree,
                  SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats,
                  function_ref<void(Function &F)> ChangedCFGCallback,
                  function_ref<void(Function &F)> DeleteFnCallback) { … }

static bool
OptimizeGlobalVars(Module &M,
                   function_ref<TargetTransformInfo &(Function &)> GetTTI,
                   function_ref<TargetLibraryInfo &(Function &)> GetTLI,
                   function_ref<DominatorTree &(Function &)> LookupDomTree,
                   SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) { … }

/// Evaluate static constructors in the function, if we can.  Return true if we
/// can, false otherwise.
static bool EvaluateStaticConstructor(Function *F, const DataLayout &DL,
                                      TargetLibraryInfo *TLI) { … }

static int compareNames(Constant *const *A, Constant *const *B) { … }

static void setUsedInitializer(GlobalVariable &V,
                               const SmallPtrSetImpl<GlobalValue *> &Init) { … }

namespace {

/// An easy to access representation of llvm.used and llvm.compiler.used.
class LLVMUsed { … };

} // end anonymous namespace

static bool hasUseOtherThanLLVMUsed(GlobalAlias &GA, const LLVMUsed &U) { … }

static bool mayHaveOtherReferences(GlobalValue &GV, const LLVMUsed &U) { … }

static bool hasUsesToReplace(GlobalAlias &GA, const LLVMUsed &U,
                             bool &RenameTarget) { … }

static bool
OptimizeGlobalAliases(Module &M,
                      SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) { … }

static Function *
FindAtExitLibFunc(Module &M,
                  function_ref<TargetLibraryInfo &(Function &)> GetTLI,
                  LibFunc Func) { … }

/// Returns whether the given function is an empty C++ destructor or atexit
/// handler and can therefore be eliminated. Note that we assume that other
/// optimization passes have already simplified the code so we simply check for
/// 'ret'.
static bool IsEmptyAtExitFunction(const Function &Fn) { … }

static bool OptimizeEmptyGlobalAtExitDtors(Function *CXAAtExitFn, bool isCXX) { … }

static Function *hasSideeffectFreeStaticResolution(GlobalIFunc &IF) { … }

/// Find IFuncs that have resolvers that always point at the same statically
/// known callee, and replace their callers with a direct call.
static bool OptimizeStaticIFuncs(Module &M) { … }

static bool
DeleteDeadIFuncs(Module &M,
                 SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) { … }

static bool
optimizeGlobalsInModule(Module &M, const DataLayout &DL,
                        function_ref<TargetLibraryInfo &(Function &)> GetTLI,
                        function_ref<TargetTransformInfo &(Function &)> GetTTI,
                        function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
                        function_ref<DominatorTree &(Function &)> LookupDomTree,
                        function_ref<void(Function &F)> ChangedCFGCallback,
                        function_ref<void(Function &F)> DeleteFnCallback) { … }

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