StackSafetyAnalysis.cpp | Explore in Territory

//===- StackSafetyAnalysis.cpp - Stack memory safety analysis -------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/StackSafetyAnalysis.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/ModuleSummaryAnalysis.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/StackLifetime.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/ModuleSummaryIndex.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/FormatVariadic.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <memory>
#include <tuple>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumAllocaStackSafe, "Number of safe allocas");
STATISTIC(NumAllocaTotal, "Number of total allocas");

STATISTIC(NumCombinedCalleeLookupTotal,
          "Number of total callee lookups on combined index.");
STATISTIC(NumCombinedCalleeLookupFailed,
          "Number of failed callee lookups on combined index.");
STATISTIC(NumModuleCalleeLookupTotal,
          "Number of total callee lookups on module index.");
STATISTIC(NumModuleCalleeLookupFailed,
          "Number of failed callee lookups on module index.");
STATISTIC(NumCombinedParamAccessesBefore,
          "Number of total param accesses before generateParamAccessSummary.");
STATISTIC(NumCombinedParamAccessesAfter,
          "Number of total param accesses after generateParamAccessSummary.");
STATISTIC(NumCombinedDataFlowNodes,
          "Number of total nodes in combined index for dataflow processing.");
STATISTIC(NumIndexCalleeUnhandled, "Number of index callee which are unhandled.");
STATISTIC(NumIndexCalleeMultipleWeak, "Number of index callee non-unique weak.");
STATISTIC(NumIndexCalleeMultipleExternal, "Number of index callee non-unique external.");


static cl::opt<int> StackSafetyMaxIterations("stack-safety-max-iterations",
                                             cl::init(20), cl::Hidden);

static cl::opt<bool> StackSafetyPrint("stack-safety-print", cl::init(false),
                                      cl::Hidden);

static cl::opt<bool> StackSafetyRun("stack-safety-run", cl::init(false),
                                    cl::Hidden);

namespace {

// Check if we should bailout for such ranges.
bool isUnsafe(const ConstantRange &R) { … }

ConstantRange addOverflowNever(const ConstantRange &L, const ConstantRange &R) { … }

ConstantRange unionNoWrap(const ConstantRange &L, const ConstantRange &R) { … }

/// Describes use of address in as a function call argument.
template <typename CalleeTy> struct CallInfo { … };

/// Describe uses of address (alloca or parameter) inside of the function.
template <typename CalleeTy> struct UseInfo { … };

template <typename CalleeTy>
raw_ostream &operator<<(raw_ostream &OS, const UseInfo<CalleeTy> &U) { … }

/// Calculate the allocation size of a given alloca. Returns empty range
// in case of confution.
ConstantRange getStaticAllocaSizeRange(const AllocaInst &AI) { … }

template <typename CalleeTy> struct FunctionInfo { … };

GVToSSI;

} // namespace

struct StackSafetyInfo::InfoTy { … };

struct StackSafetyGlobalInfo::InfoTy { … };

namespace {

class StackSafetyLocalAnalysis { … };

const SCEV *StackSafetyLocalAnalysis::getSCEVAsPointer(Value *Val) { … }

ConstantRange StackSafetyLocalAnalysis::offsetFrom(Value *Addr, Value *Base) { … }

ConstantRange
StackSafetyLocalAnalysis::getAccessRange(Value *Addr, Value *Base,
                                         const ConstantRange &SizeRange) { … }

ConstantRange StackSafetyLocalAnalysis::getAccessRange(Value *Addr, Value *Base,
                                                       TypeSize Size) { … }

ConstantRange StackSafetyLocalAnalysis::getMemIntrinsicAccessRange(
    const MemIntrinsic *MI, const Use &U, Value *Base) { … }

bool StackSafetyLocalAnalysis::isSafeAccess(const Use &U, AllocaInst *AI,
                                            Value *V) { … }

bool StackSafetyLocalAnalysis::isSafeAccess(const Use &U, AllocaInst *AI,
                                            TypeSize TS) { … }

bool StackSafetyLocalAnalysis::isSafeAccess(const Use &U, AllocaInst *AI,
                                            const SCEV *AccessSize) { … }

/// The function analyzes all local uses of Ptr (alloca or argument) and
/// calculates local access range and all function calls where it was used.
void StackSafetyLocalAnalysis::analyzeAllUses(Value *Ptr,
                                              UseInfo<GlobalValue> &US,
                                              const StackLifetime &SL) { … }

FunctionInfo<GlobalValue> StackSafetyLocalAnalysis::run() { … }

template <typename CalleeTy> class StackSafetyDataFlowAnalysis { … };

template <typename CalleeTy>
ConstantRange StackSafetyDataFlowAnalysis<CalleeTy>::getArgumentAccessRange(
    const CalleeTy *Callee, unsigned ParamNo,
    const ConstantRange &Offsets) const { … }

template <typename CalleeTy>
bool StackSafetyDataFlowAnalysis<CalleeTy>::updateOneUse(UseInfo<CalleeTy> &US,
                                                         bool UpdateToFullSet) { … }

template <typename CalleeTy>
void StackSafetyDataFlowAnalysis<CalleeTy>::updateOneNode(
    const CalleeTy *Callee, FunctionInfo<CalleeTy> &FS) { … }

template <typename CalleeTy>
void StackSafetyDataFlowAnalysis<CalleeTy>::runDataFlow() { … }

#ifndef NDEBUG
template <typename CalleeTy>
void StackSafetyDataFlowAnalysis<CalleeTy>::verifyFixedPoint() {
  WorkList.clear();
  updateAllNodes();
  assert(WorkList.empty());
}
#endif

template <typename CalleeTy>
const typename StackSafetyDataFlowAnalysis<CalleeTy>::FunctionMap &
StackSafetyDataFlowAnalysis<CalleeTy>::run() { … }

FunctionSummary *findCalleeFunctionSummary(ValueInfo VI, StringRef ModuleId) { … }

const Function *findCalleeInModule(const GlobalValue *GV) { … }

const ConstantRange *findParamAccess(const FunctionSummary &FS,
                                     uint32_t ParamNo) { … }

void resolveAllCalls(UseInfo<GlobalValue> &Use,
                     const ModuleSummaryIndex *Index) { … }

GVToSSI createGlobalStackSafetyInfo(
    std::map<const GlobalValue *, FunctionInfo<GlobalValue>> Functions,
    const ModuleSummaryIndex *Index) { … }

} // end anonymous namespace

StackSafetyInfo::StackSafetyInfo() = default;

StackSafetyInfo::StackSafetyInfo(Function *F,
                                 std::function<ScalarEvolution &()> GetSE)
    : … { … }

StackSafetyInfo::StackSafetyInfo(StackSafetyInfo &&) = default;

StackSafetyInfo &StackSafetyInfo::operator=(StackSafetyInfo &&) = default;

StackSafetyInfo::~StackSafetyInfo() = default;

const StackSafetyInfo::InfoTy &StackSafetyInfo::getInfo() const { … }

void StackSafetyInfo::print(raw_ostream &O) const { … }

const StackSafetyGlobalInfo::InfoTy &StackSafetyGlobalInfo::getInfo() const { … }

std::vector<FunctionSummary::ParamAccess>
StackSafetyInfo::getParamAccesses(ModuleSummaryIndex &Index) const { … }

StackSafetyGlobalInfo::StackSafetyGlobalInfo() = default;

StackSafetyGlobalInfo::StackSafetyGlobalInfo(
    Module *M, std::function<const StackSafetyInfo &(Function &F)> GetSSI,
    const ModuleSummaryIndex *Index)
    : … { … }

StackSafetyGlobalInfo::StackSafetyGlobalInfo(StackSafetyGlobalInfo &&) =
    default;

StackSafetyGlobalInfo &
StackSafetyGlobalInfo::operator=(StackSafetyGlobalInfo &&) = default;

StackSafetyGlobalInfo::~StackSafetyGlobalInfo() = default;

bool StackSafetyGlobalInfo::isSafe(const AllocaInst &AI) const { … }

bool StackSafetyGlobalInfo::stackAccessIsSafe(const Instruction &I) const { … }

void StackSafetyGlobalInfo::print(raw_ostream &O) const { … }

LLVM_DUMP_METHOD void StackSafetyGlobalInfo::dump() const { … }

AnalysisKey StackSafetyAnalysis::Key;

StackSafetyInfo StackSafetyAnalysis::run(Function &F,
                                         FunctionAnalysisManager &AM) { … }

PreservedAnalyses StackSafetyPrinterPass::run(Function &F,
                                              FunctionAnalysisManager &AM) { … }

char StackSafetyInfoWrapperPass::ID = …;

StackSafetyInfoWrapperPass::StackSafetyInfoWrapperPass() : … { … }

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

void StackSafetyInfoWrapperPass::print(raw_ostream &O, const Module *M) const { … }

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

AnalysisKey StackSafetyGlobalAnalysis::Key;

StackSafetyGlobalInfo
StackSafetyGlobalAnalysis::run(Module &M, ModuleAnalysisManager &AM) { … }

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

char StackSafetyGlobalInfoWrapperPass::ID = …;

StackSafetyGlobalInfoWrapperPass::StackSafetyGlobalInfoWrapperPass()
    : … { … }

StackSafetyGlobalInfoWrapperPass::~StackSafetyGlobalInfoWrapperPass() = default;

void StackSafetyGlobalInfoWrapperPass::print(raw_ostream &O,
                                             const Module *M) const { … }

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

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

bool llvm::needsParamAccessSummary(const Module &M) { … }

void llvm::generateParamAccessSummary(ModuleSummaryIndex &Index) { … }

static const char LocalPassArg[] = …;
static const char LocalPassName[] = …;
INITIALIZE_PASS_BEGIN(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
                      false, true)
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
INITIALIZE_PASS_END(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
                    false, true)

static const char GlobalPassName[] = …;
INITIALIZE_PASS_BEGIN(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
                      GlobalPassName, false, true)
INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(ImmutableModuleSummaryIndexWrapperPass)
INITIALIZE_PASS_END(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
                    GlobalPassName, false, true)
llvm/llvm/lib/Analysis/StackSafetyAnalysis.cpp
