AliasAnalysis.cpp | Explore in Territory

//==- AliasAnalysis.cpp - Generic Alias Analysis Interface 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 the generic AliasAnalysis interface which is used as the
// common interface used by all clients and implementations of alias analysis.
//
// This file also implements the default version of the AliasAnalysis interface
// that is to be used when no other implementation is specified.  This does some
// simple tests that detect obvious cases: two different global pointers cannot
// alias, a global cannot alias a malloc, two different mallocs cannot alias,
// etc.
//
// This alias analysis implementation really isn't very good for anything, but
// it is very fast, and makes a nice clean default implementation.  Because it
// handles lots of little corner cases, other, more complex, alias analysis
// implementations may choose to rely on this pass to resolve these simple and
// easy cases.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/ObjCARCAliasAnalysis.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/Analysis/ScopedNoAliasAA.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TypeBasedAliasAnalysis.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Type.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 <algorithm>
#include <cassert>
#include <functional>
#include <iterator>

#define DEBUG_TYPE …

usingnamespacellvm;

STATISTIC(NumNoAlias,   "Number of NoAlias results");
STATISTIC(NumMayAlias,  "Number of MayAlias results");
STATISTIC(NumMustAlias, "Number of MustAlias results");

namespace llvm {
/// Allow disabling BasicAA from the AA results. This is particularly useful
/// when testing to isolate a single AA implementation.
cl::opt<bool> DisableBasicAA("disable-basic-aa", cl::Hidden, cl::init(false));
} // namespace llvm

#ifndef NDEBUG
/// Print a trace of alias analysis queries and their results.
static cl::opt<bool> EnableAATrace("aa-trace", cl::Hidden, cl::init(false));
#else
static const bool EnableAATrace = …;
#endif

AAResults::AAResults(const TargetLibraryInfo &TLI) : … { … }

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

AAResults::~AAResults() { … }

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

//===----------------------------------------------------------------------===//
// Default chaining methods
//===----------------------------------------------------------------------===//

AliasResult AAResults::alias(const MemoryLocation &LocA,
                             const MemoryLocation &LocB) { … }

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

ModRefInfo AAResults::getModRefInfoMask(const MemoryLocation &Loc,
                                        bool IgnoreLocals) { … }

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

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

ModRefInfo AAResults::getModRefInfo(const Instruction *I,
                                    const CallBase *Call2) { … }

ModRefInfo AAResults::getModRefInfo(const Instruction *I, const CallBase *Call2,
                                    AAQueryInfo &AAQI) { … }

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

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

MemoryEffects AAResults::getMemoryEffects(const CallBase *Call,
                                          AAQueryInfo &AAQI) { … }

MemoryEffects AAResults::getMemoryEffects(const CallBase *Call) { … }

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

raw_ostream &llvm::operator<<(raw_ostream &OS, AliasResult AR) { … }

//===----------------------------------------------------------------------===//
// Helper method implementation
//===----------------------------------------------------------------------===//

ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
                                    const MemoryLocation &Loc,
                                    AAQueryInfo &AAQI) { … }

ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
                                    const MemoryLocation &Loc,
                                    AAQueryInfo &AAQI) { … }

ModRefInfo AAResults::getModRefInfo(const FenceInst *S,
                                    const MemoryLocation &Loc,
                                    AAQueryInfo &AAQI) { … }

ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
                                    const MemoryLocation &Loc,
                                    AAQueryInfo &AAQI) { … }

ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad,
                                    const MemoryLocation &Loc,
                                    AAQueryInfo &AAQI) { … }

ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet,
                                    const MemoryLocation &Loc,
                                    AAQueryInfo &AAQI) { … }

ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,
                                    const MemoryLocation &Loc,
                                    AAQueryInfo &AAQI) { … }

ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,
                                    const MemoryLocation &Loc,
                                    AAQueryInfo &AAQI) { … }

ModRefInfo AAResults::getModRefInfo(const Instruction *I,
                                    const std::optional<MemoryLocation> &OptLoc,
                                    AAQueryInfo &AAQIP) { … }

/// Return information about whether a particular call site modifies
/// or reads the specified memory location \p MemLoc before instruction \p I
/// in a BasicBlock.
/// FIXME: this is really just shoring-up a deficiency in alias analysis.
/// BasicAA isn't willing to spend linear time determining whether an alloca
/// was captured before or after this particular call, while we are. However,
/// with a smarter AA in place, this test is just wasting compile time.
ModRefInfo AAResults::callCapturesBefore(const Instruction *I,
                                         const MemoryLocation &MemLoc,
                                         DominatorTree *DT,
                                         AAQueryInfo &AAQI) { … }

/// canBasicBlockModify - Return true if it is possible for execution of the
/// specified basic block to modify the location Loc.
///
bool AAResults::canBasicBlockModify(const BasicBlock &BB,
                                    const MemoryLocation &Loc) { … }

/// canInstructionRangeModRef - Return true if it is possible for the
/// execution of the specified instructions to mod\ref (according to the
/// mode) the location Loc. The instructions to consider are all
/// of the instructions in the range of [I1,I2] INCLUSIVE.
/// I1 and I2 must be in the same basic block.
bool AAResults::canInstructionRangeModRef(const Instruction &I1,
                                          const Instruction &I2,
                                          const MemoryLocation &Loc,
                                          const ModRefInfo Mode) { … }

// Provide a definition for the root virtual destructor.
AAResults::Concept::~Concept() = default;

// Provide a definition for the static object used to identify passes.
AnalysisKey AAManager::Key;

ExternalAAWrapperPass::ExternalAAWrapperPass() : … { … }

ExternalAAWrapperPass::ExternalAAWrapperPass(CallbackT CB)
    : … { … }

char ExternalAAWrapperPass::ID = …;

INITIALIZE_PASS(…)

ImmutablePass *
llvm::createExternalAAWrapperPass(ExternalAAWrapperPass::CallbackT Callback) { … }

AAResultsWrapperPass::AAResultsWrapperPass() : … { … }

char AAResultsWrapperPass::ID = …;

INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa",
                      "Function Alias Analysis Results", false, true)
INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
INITIALIZE_PASS_DEPENDENCY(ScopedNoAliasAAWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TypeBasedAAWrapperPass)
INITIALIZE_PASS_END(AAResultsWrapperPass, "aa",
                    "Function Alias Analysis Results", false, true)

/// Run the wrapper pass to rebuild an aggregation over known AA passes.
///
/// This is the legacy pass manager's interface to the new-style AA results
/// aggregation object. Because this is somewhat shoe-horned into the legacy
/// pass manager, we hard code all the specific alias analyses available into
/// it. While the particular set enabled is configured via commandline flags,
/// adding a new alias analysis to LLVM will require adding support for it to
/// this list.
bool AAResultsWrapperPass::runOnFunction(Function &F) { … }

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

AAManager::Result AAManager::run(Function &F, FunctionAnalysisManager &AM) { … }

bool llvm::isNoAliasCall(const Value *V) { … }

static bool isNoAliasOrByValArgument(const Value *V) { … }

bool llvm::isIdentifiedObject(const Value *V) { … }

bool llvm::isIdentifiedFunctionLocal(const Value *V) { … }

bool llvm::isEscapeSource(const Value *V) { … }

bool llvm::isNotVisibleOnUnwind(const Value *Object,
                                bool &RequiresNoCaptureBeforeUnwind) { … }

// We don't consider globals as writable: While the physical memory is writable,
// we may not have provenance to perform the write.
bool llvm::isWritableObject(const Value *Object,
                            bool &ExplicitlyDereferenceableOnly) { … }
llvm/llvm/lib/Analysis/AliasAnalysis.cpp
