X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FTypeBasedAliasAnalysis.cpp;h=0faf1398ec76609775e1a05d91252f0e964d5d4b;hb=6c3541d5597033bdb2f26f5ade811b482c32a39a;hp=38f3a11372d2ed5a9b9b699523bce8edd318210c;hpb=bc078c81e66cbd0263fb75f533a63ac7dd1f137d;p=oota-llvm.git diff --git a/lib/Analysis/TypeBasedAliasAnalysis.cpp b/lib/Analysis/TypeBasedAliasAnalysis.cpp index 38f3a11372d..0faf1398ec7 100644 --- a/lib/Analysis/TypeBasedAliasAnalysis.cpp +++ b/lib/Analysis/TypeBasedAliasAnalysis.cpp @@ -12,27 +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 descendants 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" (meaning -// pointsToConstantMemory should return true; see +// 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; @@ -51,14 +59,18 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/Passes.h" +#include "llvm/Constants.h" +#include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/Metadata.h" #include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" using namespace llvm; -// For testing purposes, enable TBAA only via a special option. -static cl::opt EnableTBAA("enable-tbaa"); +// A handy option for disabling TBAA functionality. The same effect can also be +// achieved by stripping the !tbaa tags from IR, but this option is sometimes +// more convenient. +static cl::opt EnableTBAA("enable-tbaa", cl::init(true)); namespace { /// TBAANode - This is a simple wrapper around an MDNode which provides a @@ -94,8 +106,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]; } }; } @@ -130,7 +141,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 @@ -213,17 +230,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); }