Index: include/llvm/Analysis/EscapeAnalysis.h =================================================================== --- /dev/null +++ include/llvm/Analysis/EscapeAnalysis.h @@ -0,0 +1,99 @@ +//===- EscapeAnalysis.h - Pointer Escape Analysis ---------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the Escape Analysis pass. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_ESCAPEANALYSIS_H +#define LLVM_ANALYSIS_ESCAPEANALYSIS_H + +#include "llvm/IR/PassManager.h" +#include "llvm/Pass.h" + +#include +#include + +namespace llvm { + +class AliasUsage; +class Function; +class Instruction; +class Value; + +/// Calculates escape points for the given function. +/// +/// This class is responsible for identifying allocations that escape their +/// enclosing function. For each allocation a list is kept containing the +/// instructions that form possible points of escape. +class EscapeInfo { +public: + EscapeInfo() = default; + + void recalculate(llvm::Function &F, AliasAnalysis &AA); + bool escapes(const llvm::Value *V) const; + void print(llvm::raw_ostream &O) const; + +private: + std::unordered_map> + EscapePoints; +}; + +/// Legacy analysis pass that exposes the EscapeInfo for a function. +/// +/// It runs the analysis for a function on demand. This can be initiated by +/// querying the escape info via EscapeAnalsis::getInfo, which returns a +/// EscapeInfo object. +class EscapeAnalysisPass : public llvm::FunctionPass { +public: + EscapeAnalysisPass(); + + bool runOnFunction(llvm::Function &F) override; + void getAnalysisUsage(llvm::AnalysisUsage &AU) const override; + void print(llvm::raw_ostream &O, const Module *M) const override; + + EscapeInfo &getEscapeInfo() { return EI; } + const EscapeInfo &getEscapeInfo() const { return EI; } + + static char ID; + +private: + EscapeInfo EI; +}; + +/// Analysis pass that exposes the EscapeInfo for a function. +/// +/// It runs the analysis for a function on demand. This can be inintiated by +/// querying the escape info via AM.getResult, which returns an +/// EscapeInfo object. +class EscapeAnalysis : public AnalysisInfoMixin { + friend AnalysisInfoMixin; + static char PassID; + +public: + typedef EscapeInfo Result; + + EscapeInfo run(Function &F, FunctionAnalysisManager &AM); +}; + +/// Printer pass for the EscapeInfo results. +class EscapeAnalysisPrinterPass + : public PassInfoMixin { + +public: + explicit EscapeAnalysisPrinterPass(raw_ostream &OS); + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + +private: + raw_ostream &OS; +}; +} // End llvm namespace + +#endif Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -126,6 +126,7 @@ void initializeEdgeBundlesPass(PassRegistry&); void initializeEfficiencySanitizerPass(PassRegistry&); void initializeEliminateAvailableExternallyLegacyPassPass(PassRegistry &); +void initializeEscapeAnalysisPassPass(PassRegistry&); void initializeGVNHoistLegacyPassPass(PassRegistry &); void initializeExpandISelPseudosPass(PassRegistry&); void initializeExpandPostRAPass(PassRegistry&); Index: lib/Analysis/Analysis.cpp =================================================================== --- lib/Analysis/Analysis.cpp +++ lib/Analysis/Analysis.cpp @@ -44,6 +44,7 @@ initializeDomViewerPass(Registry); initializeDomPrinterPass(Registry); initializeDomOnlyViewerPass(Registry); + initializeEscapeAnalysisPassPass(Registry); initializePostDomViewerPass(Registry); initializeDomOnlyPrinterPass(Registry); initializePostDomPrinterPass(Registry); Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -28,6 +28,7 @@ DomPrinter.cpp DominanceFrontier.cpp EHPersonalities.cpp + EscapeAnalysis.cpp GlobalsModRef.cpp IVUsers.cpp IndirectCallPromotionAnalysis.cpp Index: lib/Analysis/EscapeAnalysis.cpp =================================================================== --- /dev/null +++ lib/Analysis/EscapeAnalysis.cpp @@ -0,0 +1,191 @@ +//===- EscapeAnalysis.cpp - Pointer Escape Analysis ------------------------==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides the EscapeAnalysis analysis pass. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/EscapeAnalysis.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instruction.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Value.h" + +#include + +using namespace llvm; + +#define DEBUG_TYPE "escape-analysis" + +INITIALIZE_PASS_BEGIN(EscapeAnalysisPass, "escape-analysis", "Escape Analysis", + false, false) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) +INITIALIZE_PASS_END(EscapeAnalysisPass, "escape-analysis", "Escape Analysis", + false, false) + +namespace llvm { + +static bool IsAlloc(llvm::Instruction *I) { + if (CallInst *CI = dyn_cast(I)) { + llvm::Function *Callee = CI->getCalledFunction(); + if (Callee == nullptr || !Callee->isDeclaration()) + return false; + return Callee->getName() == "malloc"; + } + + return isa(I); +} + +void EscapeInfo::recalculate(llvm::Function &F, AliasAnalysis &AA) { + for (auto &BB : F) { + for (auto &BBI : BB) { + + Instruction *I = &BBI; + if (!IsAlloc(I)) + continue; + + std::vector Worklist = {I}; + std::unordered_set Visited; + + while (!Worklist.empty()) { + Instruction *CurrentInst = Worklist.back(); + Worklist.pop_back(); + + if (Visited.count(CurrentInst)) + continue; + Visited.insert(CurrentInst); + + for (User *U : CurrentInst->users()) { + // Add this user to the worklist. + if (auto Inst = dyn_cast(U)) + Worklist.push_back(Inst); + + // No escape through load instructions, no need to look further. + if (isa(U)) + continue; + + // Returns allow the return value to escape. This is mostly important + // for malloc to alloca promotion. + if (auto Inst = dyn_cast(U)) { + EscapePoints[I].push_back(Inst); + continue; + } + + // Calls potentially allow their parameters to escape. + if (auto Inst = dyn_cast(U)) { + EscapePoints[I].push_back(Inst); + continue; + } + + // Like calls, invokes potentially allow their parameters to escape. + if (auto Inst = dyn_cast(U)) { + EscapePoints[I].push_back(Inst); + continue; + } + + // The most obvious case: stores. Any store that writes to global + // memory or to a function argument potentially allows its input to + // escape. + if (auto *Inst = dyn_cast(U)) { + Value *Ptr = Inst->getPointerOperand(); + + bool Escapes; + + // Check function arguments + for (auto &Arg : F.getArgumentList()) { + if (!isa(Arg.getType())) + continue; + + if (auto *V = dyn_cast(&Arg)) { + if (!AA.isNoAlias(Ptr, V)) { + EscapePoints[I].push_back(Inst); + Escapes = true; + break; + } + } + } + + // No need to check globals if we already found an escape point. + if (Escapes) + continue; + + // Check globals for escape. + for (auto &Global : F.getParent()->globals()) { + if (auto *V = dyn_cast(&Global)) { + if (!AA.isNoAlias(Ptr, V)) { + EscapePoints[I].push_back(Inst); + break; + } + } + } + + // No escape through store. + continue; + } + } + } + } + } +} + +bool EscapeInfo::escapes(const Value *V) const { + auto it = EscapePoints.find(V); + if (it == EscapePoints.cend()) + return false; + + return !it->second.empty(); +} + +void EscapeInfo::print(llvm::raw_ostream &O) const { + for (auto P : EscapePoints) { + O << "Value '" << P.first->getName() << "' has " << P.second.size() + << " possible escape point(s).\n"; + } +} + +char EscapeAnalysisPass::ID = 0; + +EscapeAnalysisPass::EscapeAnalysisPass() : llvm::FunctionPass(ID) { + initializeEscapeAnalysisPassPass(*PassRegistry::getPassRegistry()); +} + +void EscapeAnalysisPass::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequiredTransitive(); +} + +bool EscapeAnalysisPass::runOnFunction(llvm::Function &F) { + EI.recalculate(F, getAnalysis().getAAResults()); + return false; +} + +void EscapeAnalysisPass::print(llvm::raw_ostream &O, const Module *M) const { + EI.print(O); +} + +char EscapeAnalysis::PassID; + +EscapeInfo EscapeAnalysis::run(Function &F, FunctionAnalysisManager &AM) { + EscapeInfo EI; + EI.recalculate(F, AM.getResult(F)); + return EI; +} + +EscapeAnalysisPrinterPass::EscapeAnalysisPrinterPass(raw_ostream &OS) + : OS(OS) {} + +PreservedAnalyses EscapeAnalysisPrinterPass::run(Function &F, + FunctionAnalysisManager &AM) { + OS << "Escape Analysis for function: " << F.getName() << "\n"; + AM.getResult(F).print(OS); + + return PreservedAnalyses::all(); +} +} Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -32,6 +32,7 @@ #include "llvm/Analysis/DemandedBits.h" #include "llvm/Analysis/DependenceAnalysis.h" #include "llvm/Analysis/DominanceFrontier.h" +#include "llvm/Analysis/EscapeAnalysis.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/IVUsers.h" #include "llvm/Analysis/LazyCallGraph.h" @@ -492,12 +493,12 @@ assert(Matches.size() == 3 && "Must capture two matched strings!"); OptimizationLevel L = StringSwitch(Matches[2]) - .Case("O0", O0) - .Case("O1", O1) - .Case("O2", O2) - .Case("O3", O3) - .Case("Os", Os) - .Case("Oz", Oz); + .Case("O0", O0) + .Case("O1", O1) + .Case("O2", O2) + .Case("O3", O3) + .Case("Os", Os) + .Case("Oz", Oz); if (Matches[1] == "default") { addPerModuleDefaultPipeline(MPM, L, DebugLogging); @@ -510,7 +511,7 @@ return true; } - // Finally expand the basic registered passes from the .inc file. +// Finally expand the basic registered passes from the .inc file. #define MODULE_PASS(NAME, CREATE_PASS) \ if (Name == NAME) { \ MPM.addPass(CREATE_PASS); \ @@ -572,7 +573,7 @@ return false; } - // Now expand the basic registered passes from the .inc file. +// Now expand the basic registered passes from the .inc file. #define CGSCC_PASS(NAME, CREATE_PASS) \ if (Name == NAME) { \ CGPM.addPass(CREATE_PASS); \ @@ -634,7 +635,7 @@ return false; } - // Now expand the basic registered passes from the .inc file. +// Now expand the basic registered passes from the .inc file. #define FUNCTION_PASS(NAME, CREATE_PASS) \ if (Name == NAME) { \ FPM.addPass(CREATE_PASS); \ @@ -685,7 +686,7 @@ return false; } - // Now expand the basic registered passes from the .inc file. +// Now expand the basic registered passes from the .inc file. #define LOOP_PASS(NAME, CREATE_PASS) \ if (Name == NAME) { \ LPM.addPass(CREATE_PASS); \ Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -96,6 +96,7 @@ FUNCTION_ANALYSIS("block-freq", BlockFrequencyAnalysis()) FUNCTION_ANALYSIS("branch-prob", BranchProbabilityAnalysis()) FUNCTION_ANALYSIS("domtree", DominatorTreeAnalysis()) +FUNCTION_ANALYSIS("escape-analysis", EscapeAnalysis()) FUNCTION_ANALYSIS("postdomtree", PostDominatorTreeAnalysis()) FUNCTION_ANALYSIS("demanded-bits", DemandedBitsAnalysis()) FUNCTION_ANALYSIS("domfrontier", DominanceFrontierAnalysis()) @@ -172,6 +173,7 @@ FUNCTION_PASS("print", BlockFrequencyPrinterPass(dbgs())) FUNCTION_PASS("print", BranchProbabilityPrinterPass(dbgs())) FUNCTION_PASS("print", DominatorTreePrinterPass(dbgs())) +FUNCTION_PASS("print", EscapeAnalysisPrinterPass(dbgs())) FUNCTION_PASS("print", PostDominatorTreePrinterPass(dbgs())) FUNCTION_PASS("print", DemandedBitsPrinterPass(dbgs())) FUNCTION_PASS("print", DominanceFrontierPrinterPass(dbgs())) Index: test/Analysis/EscapeAnalysis/call.ll =================================================================== --- /dev/null +++ test/Analysis/EscapeAnalysis/call.ll @@ -0,0 +1,21 @@ +; RUN: opt < %s -analyze -escape-analysis | FileCheck %s +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s + +; CHECK: Value 'test' has 2 possible escape point(s). + +@.str = private unnamed_addr constant [12 x i8] c"testingonly\00", align 1 + +define i8* @create_str() #0 { +entry: + %test = alloca i8*, align 8 + %call = call i8* @malloc(i64 12) + store i8* %call, i8** %test, align 8 + %0 = load i8*, i8** %test, align 8 + %call1 = call i8* @strcpy(i8* %0, i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i32 0, i32 0)) + %1 = load i8*, i8** %test, align 8 + ret i8* %1 +} + +declare i8* @malloc(i64) #1 + +declare i8* @strcpy(i8*, i8*) #1 Index: test/Analysis/EscapeAnalysis/return.ll =================================================================== --- /dev/null +++ test/Analysis/EscapeAnalysis/return.ll @@ -0,0 +1,18 @@ +; RUN: opt < %s -analyze -escape-analysis | FileCheck %s +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s + +; CHECK: Value 'alloc' has 1 possible escape point(s). + +define i32* @func() { + %alloc = alloca i32*, align 8 + %call = call i8* @malloc(i64 4) + %bc = bitcast i8* %call to i32* + store i32* %bc, i32** %alloc, align 8 + %load = load i32*, i32** %alloc, align 8 + store i32 10, i32* %load, align 4 + %load2 = load i32*, i32** %alloc, align 8 + ret i32* %load2 +} + +declare i8* @malloc(i64) #2 + Index: test/Analysis/EscapeAnalysis/store.ll =================================================================== --- /dev/null +++ test/Analysis/EscapeAnalysis/store.ll @@ -0,0 +1,16 @@ +; RUN: opt < %s -analyze -escape-analysis | FileCheck %s +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s + +; CHECK: Value 'ptr' has 1 possible escape point(s). + +@.str = private unnamed_addr constant [12 x i8] c"Hello World\00", align 1 +@test_string = global i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i32 0, i32 0), align 8 + +; Function Attrs: nounwind ssp uwtable +define i8** @create_ptr() { +entry: + %ptr = alloca i8**, align 8 + store i8** @test_string, i8*** %ptr, align 8 + %0 = load i8**, i8*** %ptr, align 8 + ret i8** %0 +}