MemoryDependenceAnalysis.cpp | Explore in Territory

//===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation -------------===//
//
// 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 analysis that determines, for a given memory
// operation, what preceding memory operations it depends on.  It builds on
// alias analysis information, and tries to provide a lazy, caching interface to
// a common kind of alias information query.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/MemoryDependenceAnalysis.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/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/PHITransAddr.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PredIteratorCache.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/AtomicOrdering.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <utility>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses");
STATISTIC(NumCacheDirtyNonLocal, "Number of dirty cached non-local responses");
STATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses");

STATISTIC(NumCacheNonLocalPtr,
          "Number of fully cached non-local ptr responses");
STATISTIC(NumCacheDirtyNonLocalPtr,
          "Number of cached, but dirty, non-local ptr responses");
STATISTIC(NumUncacheNonLocalPtr, "Number of uncached non-local ptr responses");
STATISTIC(NumCacheCompleteNonLocalPtr,
          "Number of block queries that were completely cached");

// Limit for the number of instructions to scan in a block.

static cl::opt<unsigned> BlockScanLimit(
    "memdep-block-scan-limit", cl::Hidden, cl::init(100),
    cl::desc("The number of instructions to scan in a block in memory "
             "dependency analysis (default = 100)"));

static cl::opt<unsigned>
    BlockNumberLimit("memdep-block-number-limit", cl::Hidden, cl::init(200),
                     cl::desc("The number of blocks to scan during memory "
                              "dependency analysis (default = 200)"));

// Limit on the number of memdep results to process.
static const unsigned int NumResultsLimit = …;

/// This is a helper function that removes Val from 'Inst's set in ReverseMap.
///
/// If the set becomes empty, remove Inst's entry.
template <typename KeyTy>
static void
RemoveFromReverseMap(DenseMap<Instruction *, SmallPtrSet<KeyTy, 4>> &ReverseMap,
                     Instruction *Inst, KeyTy Val) { … }

/// If the given instruction references a specific memory location, fill in Loc
/// with the details, otherwise set Loc.Ptr to null.
///
/// Returns a ModRefInfo value describing the general behavior of the
/// instruction.
static ModRefInfo GetLocation(const Instruction *Inst, MemoryLocation &Loc,
                              const TargetLibraryInfo &TLI) { … }

/// Private helper for finding the local dependencies of a call site.
MemDepResult MemoryDependenceResults::getCallDependencyFrom(
    CallBase *Call, bool isReadOnlyCall, BasicBlock::iterator ScanIt,
    BasicBlock *BB) { … }

MemDepResult MemoryDependenceResults::getPointerDependencyFrom(
    const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
    BasicBlock *BB, Instruction *QueryInst, unsigned *Limit,
    BatchAAResults &BatchAA) { … }

MemDepResult MemoryDependenceResults::getPointerDependencyFrom(
    const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
    BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) { … }

MemDepResult
MemoryDependenceResults::getInvariantGroupPointerDependency(LoadInst *LI,
                                                            BasicBlock *BB) { … }

// Check if SI that may alias with MemLoc can be safely skipped. This is
// possible in case if SI can only must alias or no alias with MemLoc (no
// partial overlapping possible) and it writes the same value that MemLoc
// contains now (it was loaded before this store and was not modified in
// between).
static bool canSkipClobberingStore(const StoreInst *SI,
                                   const MemoryLocation &MemLoc,
                                   Align MemLocAlign, BatchAAResults &BatchAA,
                                   unsigned ScanLimit) { … }

MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
    const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
    BasicBlock *BB, Instruction *QueryInst, unsigned *Limit,
    BatchAAResults &BatchAA) { … }

MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst) { … }

#ifndef NDEBUG
/// This method is used when -debug is specified to verify that cache arrays
/// are properly kept sorted.
static void AssertSorted(MemoryDependenceResults::NonLocalDepInfo &Cache,
                         int Count = -1) {
  if (Count == -1)
    Count = Cache.size();
  assert(std::is_sorted(Cache.begin(), Cache.begin() + Count) &&
         "Cache isn't sorted!");
}
#endif

const MemoryDependenceResults::NonLocalDepInfo &
MemoryDependenceResults::getNonLocalCallDependency(CallBase *QueryCall) { … }

void MemoryDependenceResults::getNonLocalPointerDependency(
    Instruction *QueryInst, SmallVectorImpl<NonLocalDepResult> &Result) { … }

/// Compute the memdep value for BB with Pointer/PointeeSize using either
/// cached information in Cache or by doing a lookup (which may use dirty cache
/// info if available).
///
/// If we do a lookup, add the result to the cache.
MemDepResult MemoryDependenceResults::getNonLocalInfoForBlock(
    Instruction *QueryInst, const MemoryLocation &Loc, bool isLoad,
    BasicBlock *BB, NonLocalDepInfo *Cache, unsigned NumSortedEntries,
    BatchAAResults &BatchAA) { … }

/// Sort the NonLocalDepInfo cache, given a certain number of elements in the
/// array that are already properly ordered.
///
/// This is optimized for the case when only a few entries are added.
static void
SortNonLocalDepInfoCache(MemoryDependenceResults::NonLocalDepInfo &Cache,
                         unsigned NumSortedEntries) { … }

/// Perform a dependency query based on pointer/pointeesize starting at the end
/// of StartBB.
///
/// Add any clobber/def results to the results vector and keep track of which
/// blocks are visited in 'Visited'.
///
/// This has special behavior for the first block queries (when SkipFirstBlock
/// is true).  In this special case, it ignores the contents of the specified
/// block and starts returning dependence info for its predecessors.
///
/// This function returns true on success, or false to indicate that it could
/// not compute dependence information for some reason.  This should be treated
/// as a clobber dependence on the first instruction in the predecessor block.
bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
    Instruction *QueryInst, const PHITransAddr &Pointer,
    const MemoryLocation &Loc, bool isLoad, BasicBlock *StartBB,
    SmallVectorImpl<NonLocalDepResult> &Result,
    DenseMap<BasicBlock *, Value *> &Visited, bool SkipFirstBlock,
    bool IsIncomplete) { … }

/// If P exists in CachedNonLocalPointerInfo or NonLocalDefsCache, remove it.
void MemoryDependenceResults::removeCachedNonLocalPointerDependencies(
    ValueIsLoadPair P) { … }

void MemoryDependenceResults::invalidateCachedPointerInfo(Value *Ptr) { … }

void MemoryDependenceResults::invalidateCachedPredecessors() { … }

void MemoryDependenceResults::removeInstruction(Instruction *RemInst) { … }

/// Verify that the specified instruction does not occur in our internal data
/// structures.
///
/// This function verifies by asserting in debug builds.
void MemoryDependenceResults::verifyRemoved(Instruction *D) const { … }

AnalysisKey MemoryDependenceAnalysis::Key;

MemoryDependenceAnalysis::MemoryDependenceAnalysis()
    : … { … }

MemoryDependenceResults
MemoryDependenceAnalysis::run(Function &F, FunctionAnalysisManager &AM) { … }

char MemoryDependenceWrapperPass::ID = …;

INITIALIZE_PASS_BEGIN(MemoryDependenceWrapperPass, "memdep",
                      "Memory Dependence Analysis", false, true)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_END(MemoryDependenceWrapperPass, "memdep",
                    "Memory Dependence Analysis", false, true)

MemoryDependenceWrapperPass::MemoryDependenceWrapperPass() : … { … }

MemoryDependenceWrapperPass::~MemoryDependenceWrapperPass() = default;

void MemoryDependenceWrapperPass::releaseMemory() { … }

void MemoryDependenceWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { … }

bool MemoryDependenceResults::invalidate(Function &F, const PreservedAnalyses &PA,
                               FunctionAnalysisManager::Invalidator &Inv) { … }

unsigned MemoryDependenceResults::getDefaultBlockScanLimit() const { … }

bool MemoryDependenceWrapperPass::runOnFunction(Function &F) { … }
llvm/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
