From e02f724880ddb7ffe296cda3ffb9822761a13ce7 Mon Sep 17 00:00:00 2001 From: Duncan Sands Date: Wed, 28 Jan 2009 11:33:59 +0000 Subject: Fix PR3415 (infinite loop in EscapeAnalysis) by deleting the escape analysis pass. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@63197 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/EscapeAnalysis.h | 55 ------------ include/llvm/LinkAllPasses.h | 2 - lib/Analysis/CMakeLists.txt | 1 - lib/Analysis/EscapeAnalysis.cpp | 158 --------------------------------- win32/Analysis/Analysis.vcproj | 4 - 5 files changed, 220 deletions(-) delete mode 100644 include/llvm/Analysis/EscapeAnalysis.h delete mode 100644 lib/Analysis/EscapeAnalysis.cpp diff --git a/include/llvm/Analysis/EscapeAnalysis.h b/include/llvm/Analysis/EscapeAnalysis.h deleted file mode 100644 index 3f4da25..0000000 --- a/include/llvm/Analysis/EscapeAnalysis.h +++ /dev/null @@ -1,55 +0,0 @@ -//===------------- EscapeAnalysis.h - 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 defines the interface for the pointer escape analysis. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_ESCAPEANALYSIS_H -#define LLVM_ANALYSIS_ESCAPEANALYSIS_H - -#include "llvm/Pass.h" -#include - -namespace llvm { - -class Instruction; -class Value; - -/// EscapeAnalysis - This class determines whether an allocation (a MallocInst -/// or an AllocaInst) can escape from the current function. It performs some -/// precomputation, with the rest of the work happening on-demand. -class EscapeAnalysis : public FunctionPass { -private: - std::set EscapePoints; - -public: - static char ID; // Class identification, replacement for typeinfo - - EscapeAnalysis() : FunctionPass(intptr_t(&ID)) {} - - bool runOnFunction(Function &F); - - void releaseMemory() { - EscapePoints.clear(); - } - - void getAnalysisUsage(AnalysisUsage &AU) const; - - //===--------------------------------------------------------------------- - // Client API - - /// escapes - returns true if the value, which must have a pointer type, - /// can escape. - bool escapes(Value* A); -}; - -} // end llvm namespace - -#endif diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h index 4113b16..18f72ac 100644 --- a/include/llvm/LinkAllPasses.h +++ b/include/llvm/LinkAllPasses.h @@ -16,7 +16,6 @@ #define LLVM_LINKALLPASSES_H #include "llvm/Analysis/AliasSetTracker.h" -#include "llvm/Analysis/EscapeAnalysis.h" #include "llvm/Analysis/FindUsedTypes.h" #include "llvm/Analysis/IntervalPartition.h" #include "llvm/Analysis/LoopVR.h" @@ -132,7 +131,6 @@ namespace { (void)new llvm::FindUsedTypes(); (void)new llvm::ScalarEvolution(); (void)new llvm::LoopVR(); - (void)new llvm::EscapeAnalysis(); ((llvm::Function*)0)->viewCFGOnly(); llvm::AliasSetTracker X(*(llvm::AliasAnalysis*)0); X.add((llvm::Value*)0, 0); // for -print-alias-sets diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index c5dc2cd..f63054b 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -11,7 +11,6 @@ add_llvm_library(LLVMAnalysis ConstantFolding.cpp DbgInfoPrinter.cpp DebugInfo.cpp - EscapeAnalysis.cpp InstCount.cpp Interval.cpp IntervalPartition.cpp diff --git a/lib/Analysis/EscapeAnalysis.cpp b/lib/Analysis/EscapeAnalysis.cpp deleted file mode 100644 index c621c9f..0000000 --- a/lib/Analysis/EscapeAnalysis.cpp +++ /dev/null @@ -1,158 +0,0 @@ -//===------------- EscapeAnalysis.h - 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 implementation of the pointer escape analysis. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "escape-analysis" -#include "llvm/Analysis/EscapeAnalysis.h" -#include "llvm/Constants.h" -#include "llvm/Instructions.h" -#include "llvm/Module.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Support/InstIterator.h" -#include "llvm/Target/TargetData.h" -#include "llvm/ADT/SmallPtrSet.h" -#include -using namespace llvm; - -char EscapeAnalysis::ID = 0; -static RegisterPass X("escape-analysis", - "Pointer Escape Analysis", true, true); - - -void EscapeAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequiredTransitive(); - AU.addRequiredTransitive(); - AU.setPreservesAll(); -} - -/// runOnFunction - Precomputation for escape analysis. This collects all know -/// "escape points" in the def-use graph of the function. These are -/// instructions which allow their inputs to escape from the current function. -bool EscapeAnalysis::runOnFunction(Function& F) { - EscapePoints.clear(); - - TargetData& TD = getAnalysis(); - AliasAnalysis& AA = getAnalysis(); - Module* M = F.getParent(); - - // Walk through all instructions in the function, identifying those that - // may allow their inputs to escape. - for(inst_iterator II = inst_begin(F), IE = inst_end(F); II != IE; ++II) { - Instruction* I = &*II; - - // The most obvious case is stores. Any store that may write to global - // memory or to a function argument potentially allows its input to escape. - if (StoreInst* S = dyn_cast(I)) { - const Type* StoreType = S->getOperand(0)->getType(); - unsigned StoreSize = TD.getTypeStoreSize(StoreType); - Value* Pointer = S->getPointerOperand(); - - bool inserted = false; - for (Function::arg_iterator AI = F.arg_begin(), AE = F.arg_end(); - AI != AE; ++AI) { - if (!isa(AI->getType())) continue; - AliasAnalysis::AliasResult R = AA.alias(Pointer, StoreSize, AI, ~0U); - if (R != AliasAnalysis::NoAlias) { - EscapePoints.insert(S); - inserted = true; - break; - } - } - - if (inserted) - continue; - - for (Module::global_iterator GI = M->global_begin(), GE = M->global_end(); - GI != GE; ++GI) { - AliasAnalysis::AliasResult R = AA.alias(Pointer, StoreSize, GI, ~0U); - if (R != AliasAnalysis::NoAlias) { - EscapePoints.insert(S); - break; - } - } - - // Calls and invokes potentially allow their parameters to escape. - // FIXME: This can and should be refined. Intrinsics have known escape - // behavior, and alias analysis may be able to tell us more about callees. - } else if (isa(I) || isa(I)) { - EscapePoints.insert(I); - - // Returns allow the return value to escape. This is mostly important - // for malloc to alloca promotion. - } else if (isa(I)) { - EscapePoints.insert(I); - - // Branching on the value of a pointer may allow the value to escape through - // methods not discoverable via def-use chaining. - } else if(isa(I) || isa(I)) { - EscapePoints.insert(I); - } - - // FIXME: Are there any other possible escape points? - } - - return false; -} - -/// escapes - Determines whether the passed allocation can escape from the -/// current function. It does this by using a simple worklist algorithm to -/// search for a path in the def-use graph from the allocation to an -/// escape point. -/// FIXME: Once we've discovered a path, it would be a good idea to memoize it, -/// and all of its subpaths, to amortize the cost of future queries. -bool EscapeAnalysis::escapes(Value* A) { - assert(isa(A->getType()) && - "Can't do escape analysis on non-pointer types!"); - - std::vector worklist; - worklist.push_back(A); - - SmallPtrSet visited; - visited.insert(A); - while (!worklist.empty()) { - Value* curr = worklist.back(); - worklist.pop_back(); - - if (Instruction* I = dyn_cast(curr)) - if (EscapePoints.count(I)) { - BranchInst* B = dyn_cast(I); - if (!B) return true; - Value* condition = B->getCondition(); - ICmpInst* C = dyn_cast(condition); - if (!C) return true; - Value* O1 = C->getOperand(0); - Value* O2 = C->getOperand(1); - if (isa(O1->stripPointerCasts())) { - if (!isa(O2)) return true; - } else if(isa(O2->stripPointerCasts())) { - if (!isa(O1)) return true; - } else - return true; - } - - if (StoreInst* S = dyn_cast(curr)) { - // We know this must be an instruction, because constant gep's would - // have been found to alias a global, so stores to them would have - // been in EscapePoints. - if (visited.insert(cast(S->getPointerOperand()))) - worklist.push_back(cast(S->getPointerOperand())); - } else { - for (Instruction::use_iterator UI = curr->use_begin(), - UE = curr->use_end(); UI != UE; ++UI) - if (Instruction* U = dyn_cast(UI)) - if (visited.insert(U)) - worklist.push_back(U); - } - } - - return false; -} diff --git a/win32/Analysis/Analysis.vcproj b/win32/Analysis/Analysis.vcproj index 3f5550f..e116aa3 100644 --- a/win32/Analysis/Analysis.vcproj +++ b/win32/Analysis/Analysis.vcproj @@ -349,10 +349,6 @@ > - - -- cgit v1.1