GlobalsModRef.cpp | Explore in Territory

//===- GlobalsModRef.cpp - Simple Mod/Ref Analysis for Globals ------------===//
//
// 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 simple pass provides alias and mod/ref information for global values
// that do not have their address taken, and keeps track of whether functions
// read or write memory (are "pure").  For this simple (but very common) case,
// we can provide pretty accurate and useful information.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumNonAddrTakenGlobalVars,
          "Number of global vars without address taken");
STATISTIC(NumNonAddrTakenFunctions,"Number of functions without address taken");
STATISTIC(NumNoMemFunctions, "Number of functions that do not access memory");
STATISTIC(NumReadMemFunctions, "Number of functions that only read memory");
STATISTIC(NumIndirectGlobalVars, "Number of indirect global objects");

// An option to enable unsafe alias results from the GlobalsModRef analysis.
// When enabled, GlobalsModRef will provide no-alias results which in extremely
// rare cases may not be conservatively correct. In particular, in the face of
// transforms which cause asymmetry between how effective getUnderlyingObject
// is for two pointers, it may produce incorrect results.
//
// These unsafe results have been returned by GMR for many years without
// causing significant issues in the wild and so we provide a mechanism to
// re-enable them for users of LLVM that have a particular performance
// sensitivity and no known issues. The option also makes it easy to evaluate
// the performance impact of these results.
static cl::opt<bool> EnableUnsafeGlobalsModRefAliasResults(
    "enable-unsafe-globalsmodref-alias-results", cl::init(false), cl::Hidden);

/// The mod/ref information collected for a particular function.
///
/// We collect information about mod/ref behavior of a function here, both in
/// general and as pertains to specific globals. We only have this detailed
/// information when we know *something* useful about the behavior. If we
/// saturate to fully general mod/ref, we remove the info for the function.
class GlobalsAAResult::FunctionInfo { … };

void GlobalsAAResult::DeletionCallbackHandle::deleted() { … }

MemoryEffects GlobalsAAResult::getMemoryEffects(const Function *F) { … }

/// Returns the function info for the function, or null if we don't have
/// anything useful to say about it.
GlobalsAAResult::FunctionInfo *
GlobalsAAResult::getFunctionInfo(const Function *F) { … }

/// AnalyzeGlobals - Scan through the users of all of the internal
/// GlobalValue's in the program.  If none of them have their "address taken"
/// (really, their address passed to something nontrivial), record this fact,
/// and record the functions that they are used directly in.
void GlobalsAAResult::AnalyzeGlobals(Module &M) { … }

/// AnalyzeUsesOfPointer - Look at all of the users of the specified pointer.
/// If this is used by anything complex (i.e., the address escapes), return
/// true.  Also, while we are at it, keep track of those functions that read and
/// write to the value.
///
/// If OkayStoreDest is non-null, stores into this global are allowed.
bool GlobalsAAResult::AnalyzeUsesOfPointer(Value *V,
                                           SmallPtrSetImpl<Function *> *Readers,
                                           SmallPtrSetImpl<Function *> *Writers,
                                           GlobalValue *OkayStoreDest) { … }

/// AnalyzeIndirectGlobalMemory - We found an non-address-taken global variable
/// which holds a pointer type.  See if the global always points to non-aliased
/// heap memory: that is, all initializers of the globals store a value known
/// to be obtained via a noalias return function call which have no other use.
/// Further, all loads out of GV must directly use the memory, not store the
/// pointer somewhere.  If this is true, we consider the memory pointed to by
/// GV to be owned by GV and can disambiguate other pointers from it.
bool GlobalsAAResult::AnalyzeIndirectGlobalMemory(GlobalVariable *GV) { … }

void GlobalsAAResult::CollectSCCMembership(CallGraph &CG) { … }

/// AnalyzeCallGraph - At this point, we know the functions where globals are
/// immediately stored to and read from.  Propagate this information up the call
/// graph to all callers and compute the mod/ref info for all memory for each
/// function.
void GlobalsAAResult::AnalyzeCallGraph(CallGraph &CG, Module &M) { … }

// GV is a non-escaping global. V is a pointer address that has been loaded from.
// If we can prove that V must escape, we can conclude that a load from V cannot
// alias GV.
static bool isNonEscapingGlobalNoAliasWithLoad(const GlobalValue *GV,
                                               const Value *V,
                                               int &Depth,
                                               const DataLayout &DL) { … }

// There are particular cases where we can conclude no-alias between
// a non-addr-taken global and some other underlying object. Specifically,
// a non-addr-taken global is known to not be escaped from any function. It is
// also incorrect for a transformation to introduce an escape of a global in
// a way that is observable when it was not there previously. One function
// being transformed to introduce an escape which could possibly be observed
// (via loading from a global or the return value for example) within another
// function is never safe. If the observation is made through non-atomic
// operations on different threads, it is a data-race and UB. If the
// observation is well defined, by being observed the transformation would have
// changed program behavior by introducing the observed escape, making it an
// invalid transform.
//
// This property does require that transformations which *temporarily* escape
// a global that was not previously escaped, prior to restoring it, cannot rely
// on the results of GMR::alias. This seems a reasonable restriction, although
// currently there is no way to enforce it. There is also no realistic
// optimization pass that would make this mistake. The closest example is
// a transformation pass which does reg2mem of SSA values but stores them into
// global variables temporarily before restoring the global variable's value.
// This could be useful to expose "benign" races for example. However, it seems
// reasonable to require that a pass which introduces escapes of global
// variables in this way to either not trust AA results while the escape is
// active, or to be forced to operate as a module pass that cannot co-exist
// with an alias analysis such as GMR.
bool GlobalsAAResult::isNonEscapingGlobalNoAlias(const GlobalValue *GV,
                                                 const Value *V) { … }

bool GlobalsAAResult::invalidate(Module &, const PreservedAnalyses &PA,
                                 ModuleAnalysisManager::Invalidator &) { … }

/// alias - If one of the pointers is to a global that we are tracking, and the
/// other is some random pointer, we know there cannot be an alias, because the
/// address of the global isn't taken.
AliasResult GlobalsAAResult::alias(const MemoryLocation &LocA,
                                   const MemoryLocation &LocB,
                                   AAQueryInfo &AAQI, const Instruction *) { … }

ModRefInfo GlobalsAAResult::getModRefInfoForArgument(const CallBase *Call,
                                                     const GlobalValue *GV,
                                                     AAQueryInfo &AAQI) { … }

ModRefInfo GlobalsAAResult::getModRefInfo(const CallBase *Call,
                                          const MemoryLocation &Loc,
                                          AAQueryInfo &AAQI) { … }

GlobalsAAResult::GlobalsAAResult(
    const DataLayout &DL,
    std::function<const TargetLibraryInfo &(Function &F)> GetTLI)
    : … { … }

GlobalsAAResult::GlobalsAAResult(GlobalsAAResult &&Arg)
    : … { … }

GlobalsAAResult::~GlobalsAAResult() = default;

/*static*/ GlobalsAAResult GlobalsAAResult::analyzeModule(
    Module &M, std::function<const TargetLibraryInfo &(Function &F)> GetTLI,
    CallGraph &CG) { … }

AnalysisKey GlobalsAA::Key;

GlobalsAAResult GlobalsAA::run(Module &M, ModuleAnalysisManager &AM) { … }

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

char GlobalsAAWrapperPass::ID = …;
INITIALIZE_PASS_BEGIN(GlobalsAAWrapperPass, "globals-aa",
                      "Globals Alias Analysis", false, true)
INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_END(GlobalsAAWrapperPass, "globals-aa",
                    "Globals Alias Analysis", false, true)

ModulePass *llvm::createGlobalsAAWrapperPass() { … }

GlobalsAAWrapperPass::GlobalsAAWrapperPass() : … { … }

bool GlobalsAAWrapperPass::runOnModule(Module &M) { … }

bool GlobalsAAWrapperPass::doFinalization(Module &M) { … }

void GlobalsAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { … }
llvm/llvm/lib/Analysis/GlobalsModRef.cpp
