From 0cf84bc9111a2515f1f6517417744340fb24c533 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Sat, 15 Aug 2015 09:22:21 +0000 Subject: [PATCH] [PM/AA] Delete the LibCallAliasAnalysis and all the associated infrastructure. This AA was never used in tree. It's infrastructure also completely overlaps that of TargetLibraryInfo which is used heavily by BasicAA to achieve similar goals to those stated for this analysis. As has come up in several discussions, the use case here is still really important, but this code isn't helping move toward that use case. Any progress on better supporting rich AA information for runtime library environments would likely be better off starting from scratch or starting from TargetLibraryInfo than from this base. Differential Revision: http://reviews.llvm.org/D12028 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@245155 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/LibCallAliasAnalysis.h | 74 ---------- include/llvm/Analysis/LibCallSemantics.h | 142 ------------------- include/llvm/Analysis/Passes.h | 1 - include/llvm/InitializePasses.h | 1 - include/llvm/LinkAllPasses.h | 2 - lib/Analysis/Analysis.cpp | 1 - lib/Analysis/CMakeLists.txt | 1 - lib/Analysis/LibCallAliasAnalysis.cpp | 139 ------------------ lib/Analysis/LibCallSemantics.cpp | 44 ------ 9 files changed, 405 deletions(-) delete mode 100644 include/llvm/Analysis/LibCallAliasAnalysis.h delete mode 100644 lib/Analysis/LibCallAliasAnalysis.cpp diff --git a/include/llvm/Analysis/LibCallAliasAnalysis.h b/include/llvm/Analysis/LibCallAliasAnalysis.h deleted file mode 100644 index ebdee73e162..00000000000 --- a/include/llvm/Analysis/LibCallAliasAnalysis.h +++ /dev/null @@ -1,74 +0,0 @@ -//===- LibCallAliasAnalysis.h - Implement AliasAnalysis for libcalls ------===// -// -// 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 LibCallAliasAnalysis class. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_LIBCALLALIASANALYSIS_H -#define LLVM_ANALYSIS_LIBCALLALIASANALYSIS_H - -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/IR/Module.h" -#include "llvm/Pass.h" - -namespace llvm { - -class LibCallInfo; -struct LibCallFunctionInfo; - -/// Alias analysis driven from LibCallInfo. -struct LibCallAliasAnalysis : public FunctionPass, public AliasAnalysis { - static char ID; // Class identification - - LibCallInfo *LCI; - - explicit LibCallAliasAnalysis(LibCallInfo *LC = nullptr) - : FunctionPass(ID), LCI(LC) { - initializeLibCallAliasAnalysisPass(*PassRegistry::getPassRegistry()); - } - explicit LibCallAliasAnalysis(char &ID, LibCallInfo *LC) - : FunctionPass(ID), LCI(LC) { - initializeLibCallAliasAnalysisPass(*PassRegistry::getPassRegistry()); - } - ~LibCallAliasAnalysis() override; - - ModRefInfo getModRefInfo(ImmutableCallSite CS, - const MemoryLocation &Loc) override; - - void getAnalysisUsage(AnalysisUsage &AU) const override; - - bool runOnFunction(Function &F) override; - - /// This method is used when a pass implements an analysis interface through - /// multiple inheritance. - /// - /// If needed, it should override this to adjust the this pointer as needed - /// for the specified pass info. - void *getAdjustedAnalysisPointer(const void *PI) override { - if (PI == &AliasAnalysis::ID) - return (AliasAnalysis *)this; - return this; - } - -private: - ModRefInfo AnalyzeLibCallDetails(const LibCallFunctionInfo *FI, - ImmutableCallSite CS, - const MemoryLocation &Loc); -}; - -/// Create an alias analysis pass that knows about the semantics of a set of -/// libcalls specified by LCI. -/// -/// The newly constructed pass takes ownership of the pointer that is provided. -FunctionPass *createLibCallAliasAnalysisPass(LibCallInfo *LCI); - -} // End of llvm namespace - -#endif diff --git a/include/llvm/Analysis/LibCallSemantics.h b/include/llvm/Analysis/LibCallSemantics.h index 09411b9b860..a23dc08feb7 100644 --- a/include/llvm/Analysis/LibCallSemantics.h +++ b/include/llvm/Analysis/LibCallSemantics.h @@ -20,148 +20,6 @@ namespace llvm { class InvokeInst; - /// LibCallLocationInfo - This struct describes a set of memory locations that - /// are accessed by libcalls. Identification of a location is doing with a - /// simple callback function. - /// - /// For example, the LibCallInfo may be set up to model the behavior of - /// standard libm functions. The location that they may be interested in is - /// an abstract location that represents errno for the current target. In - /// this case, a location for errno is anything such that the predicate - /// returns true. On Mac OS X, this predicate would return true if the - /// pointer is the result of a call to "__error()". - /// - /// Locations can also be defined in a constant-sensitive way. For example, - /// it is possible to define a location that returns true iff it is passed - /// into the call as a specific argument. This is useful for modeling things - /// like "printf", which can store to memory, but only through pointers passed - /// with a '%n' constraint. - /// - struct LibCallLocationInfo { - // TODO: Flags: isContextSensitive etc. - - /// isLocation - Return a LocResult if the specified pointer refers to this - /// location for the specified call site. This returns "Yes" if we can tell - /// that the pointer *does definitely* refer to the location, "No" if we can - /// tell that the location *definitely does not* refer to the location, and - /// returns "Unknown" if we cannot tell for certain. - enum LocResult { - Yes, No, Unknown - }; - LocResult (*isLocation)(ImmutableCallSite CS, const MemoryLocation &Loc); - }; - - /// LibCallFunctionInfo - Each record in the array of FunctionInfo structs - /// records the behavior of one libcall that is known by the optimizer. This - /// captures things like the side effects of the call. Side effects are - /// modeled both universally (in the readnone/readonly) sense, but also - /// potentially against a set of abstract locations defined by the optimizer. - /// This allows an optimizer to define that some libcall (e.g. sqrt) is - /// side-effect free except that it might modify errno (thus, the call is - /// *not* universally readonly). Or it might say that the side effects - /// are unknown other than to say that errno is not modified. - /// - struct LibCallFunctionInfo { - /// Name - This is the name of the libcall this describes. - const char *Name; - - /// TODO: Constant folding function: Constant* vector -> Constant*. - - /// UniversalBehavior - This captures the absolute mod/ref behavior without - /// any specific context knowledge. For example, if the function is known - /// to be readonly, this would be set to 'ref'. If known to be readnone, - /// this is set to NoModRef. - ModRefInfo UniversalBehavior; - - /// LocationMRInfo - This pair captures info about whether a specific - /// location is modified or referenced by a libcall. - struct LocationMRInfo { - /// LocationID - ID # of the accessed location or ~0U for array end. - unsigned LocationID; - /// MRInfo - Mod/Ref info for this location. - ModRefInfo MRInfo; - }; - - /// DetailsType - Indicate the sense of the LocationDetails array. This - /// controls how the LocationDetails array is interpreted. - enum { - /// DoesOnly - If DetailsType is set to DoesOnly, then we know that the - /// *only* mod/ref behavior of this function is captured by the - /// LocationDetails array. If we are trying to say that 'sqrt' can only - /// modify errno, we'd have the {errnoloc,mod} in the LocationDetails - /// array and have DetailsType set to DoesOnly. - DoesOnly, - - /// DoesNot - If DetailsType is set to DoesNot, then the sense of the - /// LocationDetails array is completely inverted. This means that we *do - /// not* know everything about the side effects of this libcall, but we do - /// know things that the libcall cannot do. This is useful for complex - /// functions like 'ctime' which have crazy mod/ref behavior, but are - /// known to never read or write errno. In this case, we'd have - /// {errnoloc,modref} in the LocationDetails array and DetailsType would - /// be set to DoesNot, indicating that ctime does not read or write the - /// errno location. - DoesNot - } DetailsType; - - /// LocationDetails - This is a pointer to an array of LocationMRInfo - /// structs which indicates the behavior of the libcall w.r.t. specific - /// locations. For example, if this libcall is known to only modify - /// 'errno', it would have a LocationDetails array with the errno ID and - /// 'mod' in it. See the DetailsType field for how this is interpreted. - /// - /// In the "DoesOnly" case, this information is 'may' information for: there - /// is no guarantee that the specified side effect actually does happen, - /// just that it could. In the "DoesNot" case, this is 'must not' info. - /// - /// If this pointer is null, no details are known. - /// - const LocationMRInfo *LocationDetails; - }; - - - /// LibCallInfo - Abstract interface to query about library call information. - /// Instances of this class return known information about some set of - /// libcalls. - /// - class LibCallInfo { - // Implementation details of this object, private. - mutable void *Impl; - mutable const LibCallLocationInfo *Locations; - mutable unsigned NumLocations; - public: - LibCallInfo() : Impl(nullptr), Locations(nullptr), NumLocations(0) {} - virtual ~LibCallInfo(); - - //===------------------------------------------------------------------===// - // Accessor Methods: Efficient access to contained data. - //===------------------------------------------------------------------===// - - /// getLocationInfo - Return information about the specified LocationID. - const LibCallLocationInfo &getLocationInfo(unsigned LocID) const; - - - /// getFunctionInfo - Return the LibCallFunctionInfo object corresponding to - /// the specified function if we have it. If not, return null. - const LibCallFunctionInfo *getFunctionInfo(const Function *F) const; - - - //===------------------------------------------------------------------===// - // Implementation Methods: Subclasses should implement these. - //===------------------------------------------------------------------===// - - /// getLocationInfo - Return descriptors for the locations referenced by - /// this set of libcalls. - virtual unsigned getLocationInfo(const LibCallLocationInfo *&Array) const { - return 0; - } - - /// getFunctionInfoArray - Return an array of descriptors that describe the - /// set of libcalls represented by this LibCallInfo object. This array is - /// terminated by an entry with a NULL name. - virtual const LibCallFunctionInfo *getFunctionInfoArray() const = 0; - }; - enum class EHPersonality { Unknown, GNU_Ada, diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index ef757238b40..bb0e569067e 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -22,7 +22,6 @@ namespace llvm { class ModulePass; class Pass; class PassInfo; - class LibCallInfo; //===--------------------------------------------------------------------===// // diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h index 02ea255c115..d3aeb0b326a 100644 --- a/include/llvm/InitializePasses.h +++ b/include/llvm/InitializePasses.h @@ -154,7 +154,6 @@ void initializeJumpThreadingPass(PassRegistry&); void initializeLCSSAPass(PassRegistry&); void initializeLICMPass(PassRegistry&); void initializeLazyValueInfoPass(PassRegistry&); -void initializeLibCallAliasAnalysisPass(PassRegistry&); void initializeLintPass(PassRegistry&); void initializeLiveDebugVariablesPass(PassRegistry&); void initializeLiveIntervalsPass(PassRegistry&); diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h index fc9b63dd872..251df727fe1 100644 --- a/include/llvm/LinkAllPasses.h +++ b/include/llvm/LinkAllPasses.h @@ -24,7 +24,6 @@ #include "llvm/Analysis/DomPrinter.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/IntervalPartition.h" -#include "llvm/Analysis/LibCallAliasAnalysis.h" #include "llvm/Analysis/Lint.h" #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/PostDominators.h" @@ -64,7 +63,6 @@ namespace { (void) llvm::createArgumentPromotionPass(); (void) llvm::createAlignmentFromAssumptionsPass(); (void) llvm::createBasicAliasAnalysisPass(); - (void) llvm::createLibCallAliasAnalysisPass(nullptr); (void) llvm::createScalarEvolutionAliasAnalysisPass(); (void) llvm::createTypeBasedAliasAnalysisPass(); (void) llvm::createScopedNoAliasAAPass(); diff --git a/lib/Analysis/Analysis.cpp b/lib/Analysis/Analysis.cpp index 472956ca4a7..1ca151da94f 100644 --- a/lib/Analysis/Analysis.cpp +++ b/lib/Analysis/Analysis.cpp @@ -51,7 +51,6 @@ void llvm::initializeAnalysis(PassRegistry &Registry) { initializeInstCountPass(Registry); initializeIntervalPartitionPass(Registry); initializeLazyValueInfoPass(Registry); - initializeLibCallAliasAnalysisPass(Registry); initializeLintPass(Registry); initializeLoopInfoWrapperPassPass(Registry); initializeMemDepPrinterPass(Registry); diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index 431bd34371f..16417b610cb 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -31,7 +31,6 @@ add_llvm_library(LLVMAnalysis IteratedDominanceFrontier.cpp LazyCallGraph.cpp LazyValueInfo.cpp - LibCallAliasAnalysis.cpp LibCallSemantics.cpp Lint.cpp Loads.cpp diff --git a/lib/Analysis/LibCallAliasAnalysis.cpp b/lib/Analysis/LibCallAliasAnalysis.cpp deleted file mode 100644 index 0c58e7ca4dc..00000000000 --- a/lib/Analysis/LibCallAliasAnalysis.cpp +++ /dev/null @@ -1,139 +0,0 @@ -//===- LibCallAliasAnalysis.cpp - Implement AliasAnalysis for libcalls ----===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements the LibCallAliasAnalysis class. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/LibCallAliasAnalysis.h" -#include "llvm/Analysis/LibCallSemantics.h" -#include "llvm/IR/Function.h" -#include "llvm/Pass.h" -using namespace llvm; - -char LibCallAliasAnalysis::ID = 0; -INITIALIZE_AG_PASS(LibCallAliasAnalysis, AliasAnalysis, "libcall-aa", - "LibCall Alias Analysis", false, true, false) - -FunctionPass *llvm::createLibCallAliasAnalysisPass(LibCallInfo *LCI) { - return new LibCallAliasAnalysis(LCI); -} - -LibCallAliasAnalysis::~LibCallAliasAnalysis() { delete LCI; } - -void LibCallAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { - AliasAnalysis::getAnalysisUsage(AU); - AU.setPreservesAll(); // Does not transform code -} - -bool LibCallAliasAnalysis::runOnFunction(Function &F) { - // set up super class - InitializeAliasAnalysis(this, &F.getParent()->getDataLayout()); - return false; -} - -/// Given a call to a function with the specified LibCallFunctionInfo, see if -/// we can improve the mod/ref footprint of the call vs the specified -/// pointer/size. -ModRefInfo -LibCallAliasAnalysis::AnalyzeLibCallDetails(const LibCallFunctionInfo *FI, - ImmutableCallSite CS, - const MemoryLocation &Loc) { - // If we have a function, check to see what kind of mod/ref effects it - // has. Start by including any info globally known about the function. - ModRefInfo MRInfo = FI->UniversalBehavior; - if (MRInfo == MRI_NoModRef) - return MRInfo; - - // If that didn't tell us that the function is 'readnone', check to see - // if we have detailed info and if 'P' is any of the locations we know - // about. - const LibCallFunctionInfo::LocationMRInfo *Details = FI->LocationDetails; - if (Details == nullptr) - return MRInfo; - - // If the details array is of the 'DoesNot' kind, we only know something if - // the pointer is a match for one of the locations in 'Details'. If we find a - // match, we can prove some interactions cannot happen. - // - if (FI->DetailsType == LibCallFunctionInfo::DoesNot) { - // Find out if the pointer refers to a known location. - for (unsigned i = 0; Details[i].LocationID != ~0U; ++i) { - const LibCallLocationInfo &LocInfo = - LCI->getLocationInfo(Details[i].LocationID); - LibCallLocationInfo::LocResult Res = LocInfo.isLocation(CS, Loc); - if (Res != LibCallLocationInfo::Yes) - continue; - - // If we find a match against a location that we 'do not' interact with, - // learn this info into MRInfo. - return ModRefInfo(MRInfo & ~Details[i].MRInfo); - } - return MRInfo; - } - - // If the details are of the 'DoesOnly' sort, we know something if the pointer - // is a match for one of the locations in 'Details'. Also, if we can prove - // that the pointers is *not* one of the locations in 'Details', we know that - // the call is MRI_NoModRef. - assert(FI->DetailsType == LibCallFunctionInfo::DoesOnly); - - // Find out if the pointer refers to a known location. - bool NoneMatch = true; - for (unsigned i = 0; Details[i].LocationID != ~0U; ++i) { - const LibCallLocationInfo &LocInfo = - LCI->getLocationInfo(Details[i].LocationID); - LibCallLocationInfo::LocResult Res = LocInfo.isLocation(CS, Loc); - if (Res == LibCallLocationInfo::No) - continue; - - // If we don't know if this pointer points to the location, then we have to - // assume it might alias in some case. - if (Res == LibCallLocationInfo::Unknown) { - NoneMatch = false; - continue; - } - - // If we know that this pointer definitely is pointing into the location, - // merge in this information. - return ModRefInfo(MRInfo & Details[i].MRInfo); - } - - // If we found that the pointer is guaranteed to not match any of the - // locations in our 'DoesOnly' rule, then we know that the pointer must point - // to some other location. Since the libcall doesn't mod/ref any other - // locations, return MRI_NoModRef. - if (NoneMatch) - return MRI_NoModRef; - - // Otherwise, return any other info gained so far. - return MRInfo; -} - -/// Check to see if the specified callsite can clobber the specified memory -/// object. -ModRefInfo LibCallAliasAnalysis::getModRefInfo(ImmutableCallSite CS, - const MemoryLocation &Loc) { - ModRefInfo MRInfo = MRI_ModRef; - - // If this is a direct call to a function that LCI knows about, get the - // information about the runtime function. - if (LCI) { - if (const Function *F = CS.getCalledFunction()) { - if (const LibCallFunctionInfo *FI = LCI->getFunctionInfo(F)) { - MRInfo = ModRefInfo(MRInfo & AnalyzeLibCallDetails(FI, CS, Loc)); - if (MRInfo == MRI_NoModRef) - return MRI_NoModRef; - } - } - } - - // The AliasAnalysis base class has some smarts, lets use them. - return (ModRefInfo)(MRInfo | AliasAnalysis::getModRefInfo(CS, Loc)); -} diff --git a/lib/Analysis/LibCallSemantics.cpp b/lib/Analysis/LibCallSemantics.cpp index 003c81e87b6..36b92c38e89 100644 --- a/lib/Analysis/LibCallSemantics.cpp +++ b/lib/Analysis/LibCallSemantics.cpp @@ -14,54 +14,10 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/LibCallSemantics.h" -#include "llvm/ADT/StringMap.h" #include "llvm/ADT/StringSwitch.h" #include "llvm/IR/Function.h" using namespace llvm; -/// This impl pointer in ~LibCallInfo is actually a StringMap. This -/// helper does the cast. -static StringMap *getMap(void *Ptr) { - return static_cast *>(Ptr); -} - -LibCallInfo::~LibCallInfo() { - delete getMap(Impl); -} - -const LibCallLocationInfo &LibCallInfo::getLocationInfo(unsigned LocID) const { - // Get location info on the first call. - if (NumLocations == 0) - NumLocations = getLocationInfo(Locations); - - assert(LocID < NumLocations && "Invalid location ID!"); - return Locations[LocID]; -} - - -/// Return the LibCallFunctionInfo object corresponding to -/// the specified function if we have it. If not, return null. -const LibCallFunctionInfo * -LibCallInfo::getFunctionInfo(const Function *F) const { - StringMap *Map = getMap(Impl); - - /// If this is the first time we are querying for this info, lazily construct - /// the StringMap to index it. - if (!Map) { - Impl = Map = new StringMap(); - - const LibCallFunctionInfo *Array = getFunctionInfoArray(); - if (!Array) return nullptr; - - // We now have the array of entries. Populate the StringMap. - for (unsigned i = 0; Array[i].Name; ++i) - (*Map)[Array[i].Name] = Array+i; - } - - // Look up this function in the string map. - return Map->lookup(F->getName()); -} - /// See if the given exception handling personality function is one that we /// understand. If so, return a description of it; otherwise return Unknown. EHPersonality llvm::classifyEHPersonality(const Value *Pers) { -- 2.34.1