BasicAliasAnalysis.cpp | Explore in Territory

//===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===//
//
// 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 defines the primary stateless implementation of the
// Alias Analysis interface that implements identities (two different
// globals cannot alias, etc), but does no stateful analysis.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ScopeExit.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/CFG.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/SaveAndRestore.h"
#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <optional>
#include <utility>

#define DEBUG_TYPE …

usingnamespacellvm;

/// Enable analysis of recursive PHI nodes.
static cl::opt<bool> EnableRecPhiAnalysis("basic-aa-recphi", cl::Hidden,
                                          cl::init(true));

static cl::opt<bool> EnableSeparateStorageAnalysis("basic-aa-separate-storage",
                                                   cl::Hidden, cl::init(true));

/// SearchLimitReached / SearchTimes shows how often the limit of
/// to decompose GEPs is reached. It will affect the precision
/// of basic alias analysis.
STATISTIC(SearchLimitReached, "Number of times the limit to "
                              "decompose GEPs is reached");
STATISTIC(SearchTimes, "Number of times a GEP is decomposed");

// The max limit of the search depth in DecomposeGEPExpression() and
// getUnderlyingObject().
static const unsigned MaxLookupSearchDepth = …;

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

//===----------------------------------------------------------------------===//
// Useful predicates
//===----------------------------------------------------------------------===//

/// Returns the size of the object specified by V or UnknownSize if unknown.
static std::optional<TypeSize> getObjectSize(const Value *V,
                                             const DataLayout &DL,
                                             const TargetLibraryInfo &TLI,
                                             bool NullIsValidLoc,
                                             bool RoundToAlign = false) { … }

/// Returns true if we can prove that the object specified by V is smaller than
/// Size. Bails out early unless the root object is passed as the first
/// parameter.
static bool isObjectSmallerThan(const Value *V, TypeSize Size,
                                const DataLayout &DL,
                                const TargetLibraryInfo &TLI,
                                bool NullIsValidLoc) { … }

/// Return the minimal extent from \p V to the end of the underlying object,
/// assuming the result is used in an aliasing query. E.g., we do use the query
/// location size and the fact that null pointers cannot alias here.
static TypeSize getMinimalExtentFrom(const Value &V,
                                     const LocationSize &LocSize,
                                     const DataLayout &DL,
                                     bool NullIsValidLoc) { … }

/// Returns true if we can prove that the object specified by V has size Size.
static bool isObjectSize(const Value *V, TypeSize Size, const DataLayout &DL,
                         const TargetLibraryInfo &TLI, bool NullIsValidLoc) { … }

/// Return true if both V1 and V2 are VScale
static bool areBothVScale(const Value *V1, const Value *V2) { … }

//===----------------------------------------------------------------------===//
// CaptureInfo implementations
//===----------------------------------------------------------------------===//

CaptureInfo::~CaptureInfo() = default;

bool SimpleCaptureInfo::isNotCapturedBefore(const Value *Object,
                                            const Instruction *I, bool OrAt) { … }

static bool isNotInCycle(const Instruction *I, const DominatorTree *DT,
                         const LoopInfo *LI) { … }

bool EarliestEscapeInfo::isNotCapturedBefore(const Value *Object,
                                             const Instruction *I, bool OrAt) { … }

void EarliestEscapeInfo::removeInstruction(Instruction *I) { … }

//===----------------------------------------------------------------------===//
// GetElementPtr Instruction Decomposition and Analysis
//===----------------------------------------------------------------------===//

namespace {
/// Represents zext(sext(trunc(V))).
struct CastedValue { … };

/// Represents zext(sext(trunc(V))) * Scale + Offset.
struct LinearExpression { … };
}

/// Analyzes the specified value as a linear expression: "A*V + B", where A and
/// B are constant integers.
static LinearExpression GetLinearExpression(
    const CastedValue &Val,  const DataLayout &DL, unsigned Depth,
    AssumptionCache *AC, DominatorTree *DT) { … }

/// To ensure a pointer offset fits in an integer of size IndexSize
/// (in bits) when that size is smaller than the maximum index size. This is
/// an issue, for example, in particular for 32b pointers with negative indices
/// that rely on two's complement wrap-arounds for precise alias information
/// where the maximum index size is 64b.
static void adjustToIndexSize(APInt &Offset, unsigned IndexSize) { … }

namespace {
// A linear transformation of a Value; this class represents
// ZExt(SExt(Trunc(V, TruncBits), SExtBits), ZExtBits) * Scale.
struct VariableGEPIndex { … };
}

// Represents the internal structure of a GEP, decomposed into a base pointer,
// constant offsets, and variable scaled indices.
struct BasicAAResult::DecomposedGEP { … };


/// If V is a symbolic pointer expression, decompose it into a base pointer
/// with a constant offset and a number of scaled symbolic offsets.
///
/// The scaled symbolic offsets (represented by pairs of a Value* and a scale
/// in the VarIndices vector) are Value*'s that are known to be scaled by the
/// specified amount, but which may have other unrepresented high bits. As
/// such, the gep cannot necessarily be reconstructed from its decomposed form.
BasicAAResult::DecomposedGEP
BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL,
                                      AssumptionCache *AC, DominatorTree *DT) { … }

ModRefInfo BasicAAResult::getModRefInfoMask(const MemoryLocation &Loc,
                                            AAQueryInfo &AAQI,
                                            bool IgnoreLocals) { … }

static bool isIntrinsicCall(const CallBase *Call, Intrinsic::ID IID) { … }

/// Returns the behavior when calling the given call site.
MemoryEffects BasicAAResult::getMemoryEffects(const CallBase *Call,
                                              AAQueryInfo &AAQI) { … }

/// Returns the behavior when calling the given function. For use when the call
/// site is not known.
MemoryEffects BasicAAResult::getMemoryEffects(const Function *F) { … }

ModRefInfo BasicAAResult::getArgModRefInfo(const CallBase *Call,
                                           unsigned ArgIdx) { … }

#ifndef NDEBUG
static const Function *getParent(const Value *V) {
  if (const Instruction *inst = dyn_cast<Instruction>(V)) {
    if (!inst->getParent())
      return nullptr;
    return inst->getParent()->getParent();
  }

  if (const Argument *arg = dyn_cast<Argument>(V))
    return arg->getParent();

  return nullptr;
}

static bool notDifferentParent(const Value *O1, const Value *O2) {

  const Function *F1 = getParent(O1);
  const Function *F2 = getParent(O2);

  return !F1 || !F2 || F1 == F2;
}
#endif

AliasResult BasicAAResult::alias(const MemoryLocation &LocA,
                                 const MemoryLocation &LocB, AAQueryInfo &AAQI,
                                 const Instruction *CtxI) { … }

/// Checks to see if the specified callsite can clobber the specified memory
/// object.
///
/// Since we only look at local properties of this function, we really can't
/// say much about this query.  We do, however, use simple "address taken"
/// analysis on local objects.
ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call,
                                        const MemoryLocation &Loc,
                                        AAQueryInfo &AAQI) { … }

ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call1,
                                        const CallBase *Call2,
                                        AAQueryInfo &AAQI) { … }

/// Return true if we know V to the base address of the corresponding memory
/// object.  This implies that any address less than V must be out of bounds
/// for the underlying object.  Note that just being isIdentifiedObject() is
/// not enough - For example, a negative offset from a noalias argument or call
/// can be inbounds w.r.t the actual underlying object.
static bool isBaseOfObject(const Value *V) { … }

/// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against
/// another pointer.
///
/// We know that V1 is a GEP, but we don't know anything about V2.
/// UnderlyingV1 is getUnderlyingObject(GEP1), UnderlyingV2 is the same for
/// V2.
AliasResult BasicAAResult::aliasGEP(
    const GEPOperator *GEP1, LocationSize V1Size,
    const Value *V2, LocationSize V2Size,
    const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) { … }

static AliasResult MergeAliasResults(AliasResult A, AliasResult B) { … }

/// Provides a bunch of ad-hoc rules to disambiguate a Select instruction
/// against another.
AliasResult
BasicAAResult::aliasSelect(const SelectInst *SI, LocationSize SISize,
                           const Value *V2, LocationSize V2Size,
                           AAQueryInfo &AAQI) { … }

/// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against
/// another.
AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
                                    const Value *V2, LocationSize V2Size,
                                    AAQueryInfo &AAQI) { … }

/// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as
/// array references.
AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
                                      const Value *V2, LocationSize V2Size,
                                      AAQueryInfo &AAQI,
                                      const Instruction *CtxI) { … }

AliasResult BasicAAResult::aliasCheckRecursive(
    const Value *V1, LocationSize V1Size,
    const Value *V2, LocationSize V2Size,
    AAQueryInfo &AAQI, const Value *O1, const Value *O2) { … }

/// Check whether two Values can be considered equivalent.
///
/// If the values may come from different cycle iterations, this will also
/// check that the values are not part of cycle. We have to do this because we
/// are looking through phi nodes, that is we say
/// noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB).
bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
                                                  const Value *V2,
                                                  const AAQueryInfo &AAQI) { … }

/// Computes the symbolic difference between two de-composed GEPs.
void BasicAAResult::subtractDecomposedGEPs(DecomposedGEP &DestGEP,
                                           const DecomposedGEP &SrcGEP,
                                           const AAQueryInfo &AAQI) { … }

bool BasicAAResult::constantOffsetHeuristic(const DecomposedGEP &GEP,
                                            LocationSize MaybeV1Size,
                                            LocationSize MaybeV2Size,
                                            AssumptionCache *AC,
                                            DominatorTree *DT,
                                            const AAQueryInfo &AAQI) { … }

//===----------------------------------------------------------------------===//
// BasicAliasAnalysis Pass
//===----------------------------------------------------------------------===//

AnalysisKey BasicAA::Key;

BasicAAResult BasicAA::run(Function &F, FunctionAnalysisManager &AM) { … }

BasicAAWrapperPass::BasicAAWrapperPass() : … { … }

char BasicAAWrapperPass::ID = …;

void BasicAAWrapperPass::anchor() { … }

INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basic-aa",
                      "Basic Alias Analysis (stateless AA impl)", true, true)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_END(BasicAAWrapperPass, "basic-aa",
                    "Basic Alias Analysis (stateless AA impl)", true, true)

FunctionPass *llvm::createBasicAAWrapperPass() { … }

bool BasicAAWrapperPass::runOnFunction(Function &F) { … }

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