[Analysis] Add Basic Escape Analysis

[JDevlieghere]

Summary

At GuardSquare we make extensive use of LLVM. Recently we were in need for Escape Analysis and to our surprise it was not part of LLVM. A quick search revealed that it was removed due to a bug (infinite loop) back in 2008. We came up with our own implementation which we would gladly make available to the community and upstream. The implementation has worked well so far for our need, but it is by no means complete, as it does not currently account for thread-related escapes to name an example. However, our hope is that, if there's interest from the community, it can serve as a starting point for further development as part of LLVM.

[zaks.anna]

This is LLVM patch, while the clang static analyzer works on clang AST level.

[zaks.anna]

Added llvm-commits list as per http://llvm.org/docs/Phabricator.html.

Chandler, do you know who could review this patch?

[JDevlieghere]

Ping. If anyone knows the right people to review this patch, please let me know!

[hfinkel]

How does this differ from our capture tracking (include/llvm/Analysis/CaptureTracking.h and lib/Analysis/CaptureTracking.cpp)?

[reames]

Can you give a bit of context on the expected use of this code? In particular, how it differs from the existing capture tracking analysis which is used by various parts of the optimizer? I'm generally in support of improving LLVM's escape analysis capabilities, I'm just looking for a bit more information.

p.s. There are a bunch of stylistic issues with the code which will need corrected. I am not going to review carefully until the meta issue is settled.

[JDevlieghere]

Hal, Philip, thanks for having a look. Because you both mentioned CaptureTracking.cpp, I took another look at the source code and I'm starting to doubt my original premise that there are cases where we have something that escapes but isn't captured. I'll do some testing over the weekend to make sure.

[hfinkel]

In D26685#611617, @JDevlieghere wrote:

Hal, Philip, thanks for having a look. Because you both mentioned CaptureTracking.cpp, I took another look at the source code and I'm starting to doubt my original premise that there are cases where we have something that escapes but isn't captured. I'll do some testing over the weekend to make sure.

I'd also be interested in the opposite situations: Are there cases where things are captured but don't escape and that's uncovered by your analysis. I'm under the impressions that some of our capturing checks are really escape checks and more precision could be useful.

[JDevlieghere]

I ran our local tests against the CaptureTracker and everything is properly detected. Most of our cases involve stores and the current implementation is very conservative in that it always assumes a store captures.

The code also contains the following TODO, which I think I might be able to address with my implementation.

// TODO: If StoreCaptures is not true, we could do Fancy analysis
// to determine whether this store is not actually an escape point.
// In that case, BasicAliasAnalysis should be updated as well to
// take advantage of this.

I only considers a values to be escaped if the it is stored to the enclosing function's arguments or to a global. I rely on AliasAnalysis to check that the pointer might be an alias to these values. Because AliasAnalysis depends on CaptureTracking, I see two possibilities:

1. Keeping the current interface and not using AliasAnalysis, but comparing for equality rather than checking for "might alias". This is not really conservative, though arguably what you might expect from setting StoreCapture to false?
2. Adding a new interface where the caller provides alias analysis info, like what's currently done for the dominator tree. The AliasAnalysis implementation could continue using the current implementation where a store is assumed to capture.

What do you guys think?

PS: I'm not entirely sure what is meant by the last sentence in the TODO though, so I might be missing something. I'm doing my best to get a better understanding of how all of this works in LLVM, so please don't hesitate to point out if anything I mentioned doesn't make sense.

[hfinkel]

In D26685#614942, @JDevlieghere wrote:

I ran our local tests against the CaptureTracker and everything is properly detected. Most of our cases involve stores and the current implementation is very conservative in that it always assumes a store captures.

The code also contains the following TODO, which I think I might be able to address with my implementation.

// TODO: If StoreCaptures is not true, we could do Fancy analysis
// to determine whether this store is not actually an escape point.
// In that case, BasicAliasAnalysis should be updated as well to
// take advantage of this.

I only considers a values to be escaped if the it is stored to the enclosing function's arguments or to a global. I rely on AliasAnalysis to check that the pointer might be an alias to these values. Because AliasAnalysis depends on CaptureTracking, I see two possibilities:

1. Keeping the current interface and not using AliasAnalysis, but comparing for equality rather than checking for "might alias". This is not really conservative, though arguably what you might expect from setting StoreCapture to false?
2. Adding a new interface where the caller provides alias analysis info, like what's currently done for the dominator tree. The AliasAnalysis implementation could continue using the current implementation where a store is assumed to capture.

What do you guys think?

Our current use of capture tracking in AA is not very efficient (especially on large basic blocks, although the OrderedBasicBlock cache has made this a bit better). Using a pre-computed analysis could be significantly better.

However, I'm not sure that I understand how this would work. Generally, the uses in AA care about whether or not a pointer has been captured before some point:

ptr2 = ...;
...
ptr1 = foo();
x = *ptr1;
y = *ptr2; // might *ptr1 and *ptr2 alias here? It might depend on whether ptr2 is captured before the call to foo(). If it was, then foo() might return the pointer somehow. If not, then we know that ptr2 does not alias with ptr1.

Would your escape analysis tell us this?

PS: I'm not entirely sure what is meant by the last sentence in the TODO though, so I might be missing something. I'm doing my best to get a better understanding of how all of this works in LLVM, so please don't hesitate to point out if anything I mentioned doesn't make sense.

[JDevlieghere]

In reply to @reames e-mail: I don't know what particular transformation would benefit from this change, but I can hardly imagine that making it more accurate is a bad thing. Consider the following example:

define void @sample() {
entry:
  %ptr = alloca i32
  store i32 1, i32* %ptr
  %ptrtoptr = alloca i32*
  store i32* %ptr, i32** %ptrtoptr
  ret void
}

The current implementation of CaptureTracking says that %ptr escapes because it's the operand of the second store. What I propose is to only consider %ptr to escape if it's stored to either a global or to one of the arguments of the function. Neither is the case in the example, so it would not be considered escaped. So why do we need AliasAnalysis? Because %ptr might be stored to another pointer that's aliasing a function argument or global. With option (2), AA would continue working as it does today (considering any store to capture), but other passes that rely on AA anyway, could choose to use the more optimistic implementation.

Since I don't think that option (2) adds much code, I'll create a new differential to show what I mean exactly. Once we agree on whether this is a good idea or not we can look into the other improvements you guys mentioned such as the lazy caching and making the optimistic algorithm context-sensitive. I think it would be good to split those in separate changes anyway.

[JDevlieghere]

I'm abandoning this differential in favor of https://reviews.llvm.org/D27585.

include/llvm/Analysis/EscapeAnalysis.h

+//===- 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 <unordered_map>
+#include <vector>
+
+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<const llvm::Value *,
+                     std::vector<const llvm::Instruction *>>
+      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<EscapeAnalysis>, which returns an
+/// EscapeInfo object.
+class EscapeAnalysis : public AnalysisInfoMixin<EscapeAnalysis> {
+  friend AnalysisInfoMixin<EscapeAnalysis>;
+  static char PassID;
+
+public:
+  typedef EscapeInfo Result;
+
+  EscapeInfo run(Function &F, FunctionAnalysisManager &AM);
+};
+
+/// Printer pass for the EscapeInfo results.
+class EscapeAnalysisPrinterPass
+    : public PassInfoMixin<EscapeAnalysisPrinterPass> {
+
+public:
+  explicit EscapeAnalysisPrinterPass(raw_ostream &OS);
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+
+private:
+  raw_ostream &OS;
+};
+} // End llvm namespace
+
+#endif

include/llvm/InitializePasses.h

 void initializeDominatorTreeWrapperPassPass(PassRegistry&);
 void initializeDwarfEHPreparePass(PassRegistry&);
 void initializeEarlyCSELegacyPassPass(PassRegistry &);
 void initializeEarlyCSEMemSSALegacyPassPass(PassRegistry &);
 void initializeEarlyIfConverterPass(PassRegistry&);
 void initializeEdgeBundlesPass(PassRegistry&);
 void initializeEfficiencySanitizerPass(PassRegistry&);
 void initializeEliminateAvailableExternallyLegacyPassPass(PassRegistry &);
+void initializeEscapeAnalysisPassPass(PassRegistry&);
 void initializeGVNHoistLegacyPassPass(PassRegistry &);
 void initializeExpandISelPseudosPass(PassRegistry&);
 void initializeExpandPostRAPass(PassRegistry&);
 void initializeExternalAAWrapperPassPass(PassRegistry&);
 void initializeFinalizeMachineBundlesPass(PassRegistry&);
 void initializeFlattenCFGPassPass(PassRegistry&);
 void initializeFloat2IntLegacyPassPass(PassRegistry&);
 void initializeForceFunctionAttrsLegacyPassPass(PassRegistry&);

lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeDependenceAnalysisWrapperPassPass(Registry);
   initializeDelinearizationPass(Registry);
   initializeDemandedBitsWrapperPassPass(Registry);
   initializeDivergenceAnalysisPass(Registry);
   initializeDominanceFrontierWrapperPassPass(Registry);
   initializeDomViewerPass(Registry);
   initializeDomPrinterPass(Registry);
   initializeDomOnlyViewerPass(Registry);
+  initializeEscapeAnalysisPassPass(Registry);
   initializePostDomViewerPass(Registry);
   initializeDomOnlyPrinterPass(Registry);
   initializePostDomPrinterPass(Registry);
   initializePostDomOnlyViewerPass(Registry);
   initializePostDomOnlyPrinterPass(Registry);
   initializeAAResultsWrapperPassPass(Registry);
   initializeGlobalsAAWrapperPassPass(Registry);
   initializeIVUsersWrapperPassPass(Registry);

lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   ConstantFolding.cpp
   Delinearization.cpp
   DemandedBits.cpp
   DependenceAnalysis.cpp
   DivergenceAnalysis.cpp
   DomPrinter.cpp
   DominanceFrontier.cpp
   EHPersonalities.cpp
+  EscapeAnalysis.cpp
   GlobalsModRef.cpp
   IVUsers.cpp
   IndirectCallPromotionAnalysis.cpp
   InlineCost.cpp
   InstCount.cpp
   InstructionSimplify.cpp
   Interval.cpp
   IntervalPartition.cpp

lib/Analysis/EscapeAnalysis.cpp

+//===- 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 <unordered_set>
+
+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<CallInst>(I)) {
+    llvm::Function *Callee = CI->getCalledFunction();
+    if (Callee == nullptr || !Callee->isDeclaration())
+      return false;
+    return Callee->getName() == "malloc";
+  }
+
+  return isa<AllocaInst>(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<Instruction *> Worklist = {I};
+      std::unordered_set<const Instruction *> 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<Instruction>(U))
+            Worklist.push_back(Inst);
+
+          // No escape through load instructions, no need to look further.
+          if (isa<LoadInst>(U))
+            continue;
+
+          // Returns allow the return value to escape. This is mostly important
+          // for malloc to alloca promotion.
+          if (auto Inst = dyn_cast<ReturnInst>(U)) {
+            EscapePoints[I].push_back(Inst);
+            continue;
+          }
+
+          // Calls potentially allow their parameters to escape.
+          if (auto Inst = dyn_cast<CallInst>(U)) {
+            EscapePoints[I].push_back(Inst);
+            continue;
+          }
+
+          // Like calls, invokes potentially allow their parameters to escape.
+          if (auto Inst = dyn_cast<InvokeInst>(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<StoreInst>(U)) {
+            Value *Ptr = Inst->getPointerOperand();
+
+            bool Escapes;
+
+            // Check function arguments
+            for (auto &Arg : F.getArgumentList()) {
+              if (!isa<PointerType>(Arg.getType()))
+                continue;
+
+              if (auto *V = dyn_cast<Value>(&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<Value>(&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<AAResultsWrapperPass>();
+}
+
+bool EscapeAnalysisPass::runOnFunction(llvm::Function &F) {
+  EI.recalculate(F, getAnalysis<AAResultsWrapperPass>().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<AAManager>(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<EscapeAnalysis>(F).print(OS);
+
+  return PreservedAnalyses::all();
+}
+}

lib/Passes/PassBuilder.cpp

 #include "llvm/Analysis/CFGPrinter.h"
 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #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"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
bool PassBuilder::parseModulePass(ModulePassManager &MPM,
   // Manually handle aliases for pre-configured pipeline fragments.
   if (Name.startswith("default") || Name.startswith("lto")) {
     SmallVector<StringRef, 3> Matches;
     if (!DefaultAliasRegex.match(Name, &Matches))
       return false;
     assert(Matches.size() == 3 && "Must capture two matched strings!");
 
     OptimizationLevel L = StringSwitch<OptimizationLevel>(Matches[2])
                               .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);
     } else if (Matches[1] == "lto-pre-link") {
       addLTOPreLinkDefaultPipeline(MPM, L, DebugLogging);
     } else {
       assert(Matches[1] == "lto" && "Not one of the matched options!");
       addLTODefaultPipeline(MPM, L, DebugLogging);
     }
     return true;
   }
 
-  // Finally expand the basic registered passes from the .inc file.
 #define MODULE_PASS(NAME, CREATE_PASS)                                         \
   if (Name == NAME) {                                                          \
     MPM.addPass(CREATE_PASS);                                                  \
     return true;                                                               \
   }
 #define MODULE_ANALYSIS(NAME, CREATE_PASS)                                     \
   if (Name == "require<" NAME ">") {                                           \
     MPM.addPass(                                                               \
if (auto Count = parseRepeatPassName(Name)) {
         return false;
       CGPM.addPass(createRepeatedPass(*Count, std::move(NestedCGPM)));
       return true;
     }
     // Normal passes can't have pipelines.
     return false;
   }
 
-  // Now expand the basic registered passes from the .inc file.
 #define CGSCC_PASS(NAME, CREATE_PASS)                                          \
   if (Name == NAME) {                                                          \
     CGPM.addPass(CREATE_PASS);                                                 \
     return true;                                                               \
   }
 #define CGSCC_ANALYSIS(NAME, CREATE_PASS)                                      \
   if (Name == "require<" NAME ">") {                                           \
     CGPM.addPass(RequireAnalysisPass<                                          \
if (auto Count = parseRepeatPassName(Name)) {
         return false;
       FPM.addPass(createRepeatedPass(*Count, std::move(NestedFPM)));
       return true;
     }
     // Normal passes can't have pipelines.
     return false;
   }
 
-  // Now expand the basic registered passes from the .inc file.
 #define FUNCTION_PASS(NAME, CREATE_PASS)                                       \
   if (Name == NAME) {                                                          \
     FPM.addPass(CREATE_PASS);                                                  \
     return true;                                                               \
   }
 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)                                   \
   if (Name == "require<" NAME ">") {                                           \
     FPM.addPass(                                                               \
if (auto Count = parseRepeatPassName(Name)) {
         return false;
       LPM.addPass(createRepeatedPass(*Count, std::move(NestedLPM)));
       return true;
     }
     // Normal passes can't have pipelines.
     return false;
   }
 
-  // Now expand the basic registered passes from the .inc file.
 #define LOOP_PASS(NAME, CREATE_PASS)                                           \
   if (Name == NAME) {                                                          \
     LPM.addPass(CREATE_PASS);                                                  \
     return true;                                                               \
   }
 #define LOOP_ANALYSIS(NAME, CREATE_PASS)                                       \
   if (Name == "require<" NAME ">") {                                           \
     LPM.addPass(RequireAnalysisPass<                                           \

lib/Passes/PassRegistry.def

 #ifndef FUNCTION_ANALYSIS
 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)
 #endif
 FUNCTION_ANALYSIS("aa", AAManager())
 FUNCTION_ANALYSIS("assumptions", AssumptionAnalysis())
 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())
 FUNCTION_ANALYSIS("loops", LoopAnalysis())
 FUNCTION_ANALYSIS("lazy-value-info", LazyValueAnalysis())
 FUNCTION_ANALYSIS("da", DependenceAnalysis())
 FUNCTION_ANALYSIS("memdep", MemoryDependenceAnalysis())
 FUNCTION_ANALYSIS("memoryssa", MemorySSAAnalysis())

 FUNCTION_PASS("loop-data-prefetch", LoopDataPrefetchPass())
 FUNCTION_PASS("loop-distribute", LoopDistributePass())
 FUNCTION_PASS("loop-vectorize", LoopVectorizePass())
 FUNCTION_PASS("print", PrintFunctionPass(dbgs()))
 FUNCTION_PASS("print<assumptions>", AssumptionPrinterPass(dbgs()))
 FUNCTION_PASS("print<block-freq>", BlockFrequencyPrinterPass(dbgs()))
 FUNCTION_PASS("print<branch-prob>", BranchProbabilityPrinterPass(dbgs()))
 FUNCTION_PASS("print<domtree>", DominatorTreePrinterPass(dbgs()))
+FUNCTION_PASS("print<escape-analysis>", EscapeAnalysisPrinterPass(dbgs()))
 FUNCTION_PASS("print<postdomtree>", PostDominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<demanded-bits>", DemandedBitsPrinterPass(dbgs()))
 FUNCTION_PASS("print<domfrontier>", DominanceFrontierPrinterPass(dbgs()))
 FUNCTION_PASS("print<loops>", LoopPrinterPass(dbgs()))
 FUNCTION_PASS("print<memoryssa>", MemorySSAPrinterPass(dbgs()))
 FUNCTION_PASS("print<regions>", RegionInfoPrinterPass(dbgs()))
 FUNCTION_PASS("print<scalar-evolution>", ScalarEvolutionPrinterPass(dbgs()))
 FUNCTION_PASS("reassociate", ReassociatePass())

test/Analysis/EscapeAnalysis/call.ll

+; RUN: opt < %s -analyze -escape-analysis | FileCheck %s
+; RUN: opt < %s -passes='print<escape-analysis>' -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

test/Analysis/EscapeAnalysis/return.ll

+; RUN: opt < %s -analyze -escape-analysis | FileCheck %s
+; RUN: opt < %s -passes='print<escape-analysis>' -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
+

test/Analysis/EscapeAnalysis/store.ll

+; RUN: opt < %s -analyze -escape-analysis | FileCheck %s
+; RUN: opt < %s -passes='print<escape-analysis>' -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
+}