X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FTypeBasedAliasAnalysis.cpp;h=20b797ebeb1808b3ca9d861f9b7e87faf1a7527f;hb=48f17ba2a611d197082d4de730b646a4ecf68df4;hp=1cc743a3824e8d72de7007aef3d64dd96d5edf4d;hpb=de38897cfc49f09ffc84fb023a76c076f4b2d402;p=oota-llvm.git diff --git a/lib/Analysis/TypeBasedAliasAnalysis.cpp b/lib/Analysis/TypeBasedAliasAnalysis.cpp index 1cc743a3824..20b797ebeb1 100644 --- a/lib/Analysis/TypeBasedAliasAnalysis.cpp +++ b/lib/Analysis/TypeBasedAliasAnalysis.cpp @@ -12,25 +12,35 @@ // // In LLVM IR, memory does not have types, so LLVM's own type system is not // suitable for doing TBAA. Instead, metadata is added to the IR to describe -// a type system of a higher level language. +// a type system of a higher level language. This can be used to implement +// typical C/C++ TBAA, but it can also be used to implement custom alias +// analysis behavior for other languages. // -// This pass is language-independent. The type system is encoded in -// metadata. This allows this pass to support typical C and C++ TBAA, but -// it can also support custom aliasing behavior for other languages. +// The current metadata format is very simple. TBAA MDNodes have up to +// three fields, e.g.: +// !0 = metadata !{ metadata !"an example type tree" } +// !1 = metadata !{ metadata !"int", metadata !0 } +// !2 = metadata !{ metadata !"float", metadata !0 } +// !3 = metadata !{ metadata !"const float", metadata !2, i64 1 } // -// This is a work-in-progress. It doesn't work yet, and the metadata -// format isn't stable. +// The first field is an identity field. It can be any value, usually +// an MDString, which uniquely identifies the type. The most important +// name in the tree is the name of the root node. Two trees with +// different root node names are entirely disjoint, even if they +// have leaves with common names. +// +// The second field identifies the type's parent node in the tree, or +// is null or omitted for a root node. A type is considered to alias +// all of its decendents and all of its ancestors in the tree. Also, +// a type is considered to alias all types in other trees, so that +// bitcode produced from multiple front-ends is handled conservatively. // -// The current metadata format is very simple. MDNodes have up to three -// fields, e.g.: -// !0 = metadata !{ !"name", !1, 0 } -// The first field is an identity field. It can be any MDString which -// uniquely identifies the type. The second field identifies the type's -// parent node in the tree, or is null or omitted for a root node. // If the third field is present, it's an integer which if equal to 1 -// indicates that the type is "constant". +// indicates that the type is "constant" (meaning pointsToConstantMemory +// should return true; see +// http://llvm.org/docs/AliasAnalysis.html#OtherItfs). // -// TODO: The current metadata encoding scheme doesn't support struct +// TODO: The current metadata format doesn't support struct // fields. For example: // struct X { // double d; @@ -49,6 +59,7 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/Passes.h" +#include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/Metadata.h" #include "llvm/Pass.h" @@ -56,7 +67,7 @@ using namespace llvm; // For testing purposes, enable TBAA only via a special option. -static cl::opt EnableTBAA("enable-tbaa"); +static cl::opt EnableTBAA("enable-tbaa", cl::init(false)); namespace { /// TBAANode - This is a simple wrapper around an MDNode which provides a @@ -92,8 +103,7 @@ namespace { ConstantInt *CI = dyn_cast(Node->getOperand(2)); if (!CI) return false; - // TODO: Think about the encoding. - return CI->isOne(); + return CI->getValue()[0]; } }; } @@ -128,7 +138,13 @@ namespace { private: virtual void getAnalysisUsage(AnalysisUsage &AU) const; virtual AliasResult alias(const Location &LocA, const Location &LocB); - virtual bool pointsToConstantMemory(const Location &Loc); + virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal); + virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS); + virtual ModRefBehavior getModRefBehavior(const Function *F); + virtual ModRefResult getModRefInfo(ImmutableCallSite CS, + const Location &Loc); + virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, + ImmutableCallSite CS2); }; } // End of anonymous namespace @@ -211,17 +227,71 @@ TypeBasedAliasAnalysis::alias(const Location &LocA, return NoAlias; } -bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc) { +bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc, + bool OrLocal) { if (!EnableTBAA) - return AliasAnalysis::pointsToConstantMemory(Loc); + return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); const MDNode *M = Loc.TBAATag; - if (!M) return false; + if (!M) return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); // If this is an "immutable" type, we can assume the pointer is pointing // to constant memory. if (TBAANode(M).TypeIsImmutable()) return true; - return AliasAnalysis::pointsToConstantMemory(Loc); + return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); +} + +AliasAnalysis::ModRefBehavior +TypeBasedAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { + if (!EnableTBAA) + return AliasAnalysis::getModRefBehavior(CS); + + ModRefBehavior Min = UnknownModRefBehavior; + + // If this is an "immutable" type, we can assume the call doesn't write + // to memory. + if (const MDNode *M = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) + if (TBAANode(M).TypeIsImmutable()) + Min = OnlyReadsMemory; + + return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); +} + +AliasAnalysis::ModRefBehavior +TypeBasedAliasAnalysis::getModRefBehavior(const Function *F) { + // Functions don't have metadata. Just chain to the next implementation. + return AliasAnalysis::getModRefBehavior(F); +} + +AliasAnalysis::ModRefResult +TypeBasedAliasAnalysis::getModRefInfo(ImmutableCallSite CS, + const Location &Loc) { + if (!EnableTBAA) + return AliasAnalysis::getModRefInfo(CS, Loc); + + if (const MDNode *L = Loc.TBAATag) + if (const MDNode *M = + CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) + if (!Aliases(L, M)) + return NoModRef; + + return AliasAnalysis::getModRefInfo(CS, Loc); +} + +AliasAnalysis::ModRefResult +TypeBasedAliasAnalysis::getModRefInfo(ImmutableCallSite CS1, + ImmutableCallSite CS2) { + if (!EnableTBAA) + return AliasAnalysis::getModRefInfo(CS1, CS2); + + if (const MDNode *M1 = + CS1.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) + if (const MDNode *M2 = + CS2.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) + if (!Aliases(M1, M2)) + return NoModRef; + + return AliasAnalysis::getModRefInfo(CS1, CS2); }