TypeBasedAliasAnalysis.cpp revision 42c31a70735e55bf82e66a9315c97d1821c9a798
1c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman//===- TypeBasedAliasAnalysis.cpp - Type-Based Alias Analysis -------------===// 2c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 3c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// The LLVM Compiler Infrastructure 4c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 5c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// This file is distributed under the University of Illinois Open Source 6c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// License. See LICENSE.TXT for details. 7c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 8c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman//===----------------------------------------------------------------------===// 9c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 10c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// This file defines the TypeBasedAliasAnalysis pass, which implements 11c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// metadata-based TBAA. 12c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 13c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// In LLVM IR, memory does not have types, so LLVM's own type system is not 14c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// suitable for doing TBAA. Instead, metadata is added to the IR to describe 15ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// a type system of a higher level language. This can be used to implement 16ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// typical C/C++ TBAA, but it can also be used to implement custom alias 17ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// analysis behavior for other languages. 18c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 19ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// The current metadata format is very simple. TBAA MDNodes have up to 20ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// three fields, e.g.: 21ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// !0 = metadata !{ metadata !"an example type tree" } 22ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// !1 = metadata !{ metadata !"int", metadata !0 } 23ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// !2 = metadata !{ metadata !"float", metadata !0 } 24ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// !3 = metadata !{ metadata !"const float", metadata !2, i64 1 } 25c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 26ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// The first field is an identity field. It can be any value, usually 27ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// an MDString, which uniquely identifies the type. The most important 28ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// name in the tree is the name of the root node. Two trees with 29ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// different root node names are entirely disjoint, even if they 30ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// have leaves with common names. 31ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// 32ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// The second field identifies the type's parent node in the tree, or 33ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// is null or omitted for a root node. A type is considered to alias 34269008ee8336bb6519ed714e50fe5bb428b98a51Dan Gohman// all of its decendents and all of its ancestors in the tree. Also, 35269008ee8336bb6519ed714e50fe5bb428b98a51Dan Gohman// a type is considered to alias all types in other trees, so that 36269008ee8336bb6519ed714e50fe5bb428b98a51Dan Gohman// bitcode produced from multiple front-ends is handled conservatively. 37c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 38de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// If the third field is present, it's an integer which if equal to 1 39ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// indicates that the type is "constant" (meaning pointsToConstantMemory 40ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// should return true; see 41bc078c81e66cbd0263fb75f533a63ac7dd1f137dDan Gohman// http://llvm.org/docs/AliasAnalysis.html#OtherItfs). 42de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// 43ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// TODO: The current metadata format doesn't support struct 44de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// fields. For example: 45de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// struct X { 46de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// double d; 47de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// int i; 48de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// }; 49de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// void foo(struct X *x, struct X *y, double *p) { 50de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// *x = *y; 51de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// *p = 0.0; 52de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// } 53de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// Struct X has a double member, so the store to *x can alias the store to *p. 54de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// Currently it's not possible to precisely describe all the things struct X 55de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// aliases, so struct assignments must use conservative TBAA nodes. There's 56de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// no scheme for attaching metadata to @llvm.memcpy yet either. 57c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 58c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman//===----------------------------------------------------------------------===// 59c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 60c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Analysis/AliasAnalysis.h" 61c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Analysis/Passes.h" 6287c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman#include "llvm/LLVMContext.h" 63c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Module.h" 64c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Metadata.h" 65c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Pass.h" 6601b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman#include "llvm/Support/CommandLine.h" 67c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmanusing namespace llvm; 68c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 6901b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman// For testing purposes, enable TBAA only via a special option. 7001b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohmanstatic cl::opt<bool> EnableTBAA("enable-tbaa"); 7101b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman 72c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmannamespace { 73c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// TBAANode - This is a simple wrapper around an MDNode which provides a 74c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// higher-level interface by hiding the details of how alias analysis 75c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// information is encoded in its operands. 76c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman class TBAANode { 77c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman const MDNode *Node; 78c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 79c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman public: 80c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman TBAANode() : Node(0) {} 81e6291ae96efa1e27ca6606ac59b17e35d45c057eDan Gohman explicit TBAANode(const MDNode *N) : Node(N) {} 82c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 83c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// getNode - Get the MDNode for this TBAANode. 84c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman const MDNode *getNode() const { return Node; } 85c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 860b62f95ea81d8954c21a2ae54602be10e5e1bb7eDan Gohman /// getParent - Get this TBAANode's Alias tree parent. 87c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman TBAANode getParent() const { 88c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (Node->getNumOperands() < 2) 89c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return TBAANode(); 90c05d8aa6db088b0f2e2d569d59d87de11cec9c29Dan Gohman MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1)); 91c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!P) 92c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return TBAANode(); 93c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Ok, this node has a valid parent. Return it. 94c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return TBAANode(P); 95c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 96c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 97c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// TypeIsImmutable - Test if this TBAANode represents a type for objects 98c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// which are not modified (by any means) in the context where this 99c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// AliasAnalysis is relevant. 100c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman bool TypeIsImmutable() const { 101c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (Node->getNumOperands() < 3) 102c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return false; 103c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman ConstantInt *CI = dyn_cast<ConstantInt>(Node->getOperand(2)); 104c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!CI) 105c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return false; 106ae92af6771f0a87b380706bc20e69d90bc0c1818Dan Gohman return CI->getValue()[0]; 107c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 108c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman }; 109c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 110c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 111c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmannamespace { 112c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// TypeBasedAliasAnalysis - This is a simple alias analysis 113c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// implementation that uses TypeBased to answer queries. 114c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman class TypeBasedAliasAnalysis : public ImmutablePass, 115c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman public AliasAnalysis { 116c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman public: 117c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman static char ID; // Class identification, replacement for typeinfo 118081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson TypeBasedAliasAnalysis() : ImmutablePass(ID) { 119081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeTypeBasedAliasAnalysisPass(*PassRegistry::getPassRegistry()); 120081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 121c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 122633e7023177837537adabf775395ebe7ab51b38fDan Gohman virtual void initializePass() { 123633e7023177837537adabf775395ebe7ab51b38fDan Gohman InitializeAliasAnalysis(this); 124633e7023177837537adabf775395ebe7ab51b38fDan Gohman } 125633e7023177837537adabf775395ebe7ab51b38fDan Gohman 126c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// getAdjustedAnalysisPointer - This method is used when a pass implements 127c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// an analysis interface through multiple inheritance. If needed, it 128c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// should override this to adjust the this pointer as needed for the 129c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// specified pass info. 13090c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson virtual void *getAdjustedAnalysisPointer(const void *PI) { 13190c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson if (PI == &AliasAnalysis::ID) 132c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return (AliasAnalysis*)this; 133c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return this; 134c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 135c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 136ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman bool Aliases(const MDNode *A, const MDNode *B) const; 137ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 138c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman private: 139c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman virtual void getAnalysisUsage(AnalysisUsage &AU) const; 140b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman virtual AliasResult alias(const Location &LocA, const Location &LocB); 141a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal); 142a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS); 143a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman virtual ModRefBehavior getModRefBehavior(const Function *F); 14487c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman virtual ModRefResult getModRefInfo(ImmutableCallSite CS, 14587c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman const Location &Loc); 14687c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, 14787c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman ImmutableCallSite CS2); 148c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman }; 149c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} // End of anonymous namespace 150c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 151c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// Register this pass... 152c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmanchar TypeBasedAliasAnalysis::ID = 0; 153c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan GohmanINITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa", 154ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Type-Based Alias Analysis", false, true, false) 155c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 156c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan GohmanImmutablePass *llvm::createTypeBasedAliasAnalysisPass() { 157c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return new TypeBasedAliasAnalysis(); 158c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 159c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 160c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmanvoid 161c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan GohmanTypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 162c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman AU.setPreservesAll(); 163c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman AliasAnalysis::getAnalysisUsage(AU); 164c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 165c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 166ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman/// Aliases - Test whether the type represented by A may alias the 167ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman/// type represented by B. 168ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohmanbool 169ba13864483b696e7f8e2058c3a50b5d901f2213bDan GohmanTypeBasedAliasAnalysis::Aliases(const MDNode *A, 170ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman const MDNode *B) const { 171c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Keep track of the root node for A and B. 172c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman TBAANode RootA, RootB; 173c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 1740b62f95ea81d8954c21a2ae54602be10e5e1bb7eDan Gohman // Climb the tree from A to see if we reach B. 175ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman for (TBAANode T(A); ; ) { 176ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (T.getNode() == B) 177c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // B is an ancestor of A. 178ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return true; 179c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 180c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman RootA = T; 181c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman T = T.getParent(); 182c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!T.getNode()) 183c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman break; 184c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 185c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 1860b62f95ea81d8954c21a2ae54602be10e5e1bb7eDan Gohman // Climb the tree from B to see if we reach A. 187ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman for (TBAANode T(B); ; ) { 188ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (T.getNode() == A) 189c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // A is an ancestor of B. 190ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return true; 191c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 192c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman RootB = T; 193c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman T = T.getParent(); 194c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!T.getNode()) 195c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman break; 196c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 197c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 198c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Neither node is an ancestor of the other. 199c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 200c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // If they have different roots, they're part of different potentially 201c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // unrelated type systems, so we must be conservative. 202ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (RootA.getNode() != RootB.getNode()) 203ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return true; 204ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 205ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // If they have the same root, then we've proved there's no alias. 206ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return false; 207ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman} 208ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 209ba13864483b696e7f8e2058c3a50b5d901f2213bDan GohmanAliasAnalysis::AliasResult 210ba13864483b696e7f8e2058c3a50b5d901f2213bDan GohmanTypeBasedAliasAnalysis::alias(const Location &LocA, 211ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman const Location &LocB) { 212ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (!EnableTBAA) 213ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return AliasAnalysis::alias(LocA, LocB); 214ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 215ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must 216ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // be conservative. 217ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman const MDNode *AM = LocA.TBAATag; 218ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (!AM) return AliasAnalysis::alias(LocA, LocB); 219ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman const MDNode *BM = LocB.TBAATag; 220ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (!BM) return AliasAnalysis::alias(LocA, LocB); 221ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 222ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // If they may alias, chain to the next AliasAnalysis. 223ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (Aliases(AM, BM)) 224ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return AliasAnalysis::alias(LocA, LocB); 225ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 226ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // Otherwise return a definitive result. 227ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return NoAlias; 228c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 229c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 230a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohmanbool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc, 231a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman bool OrLocal) { 23201b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman if (!EnableTBAA) 233a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 23401b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman 235e6291ae96efa1e27ca6606ac59b17e35d45c057eDan Gohman const MDNode *M = Loc.TBAATag; 236a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman if (!M) return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 237c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 238c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // If this is an "immutable" type, we can assume the pointer is pointing 239c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // to constant memory. 240acf50f5136c6f1daca2e78db756514a88470516bDan Gohman if (TBAANode(M).TypeIsImmutable()) 241acf50f5136c6f1daca2e78db756514a88470516bDan Gohman return true; 242acf50f5136c6f1daca2e78db756514a88470516bDan Gohman 243a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 244c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 24587c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 246a8598bec287108d0359880d33955759dc90cd5a1Dan GohmanAliasAnalysis::ModRefBehavior 247a8598bec287108d0359880d33955759dc90cd5a1Dan GohmanTypeBasedAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 248a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman if (!EnableTBAA) 249a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman return AliasAnalysis::getModRefBehavior(CS); 250a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman 251a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman ModRefBehavior Min = UnknownModRefBehavior; 252a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman 253a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman // If this is an "immutable" type, we can assume the call doesn't write 254a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman // to memory. 255a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman if (const MDNode *M = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 256a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman if (TBAANode(M).TypeIsImmutable()) 257a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman Min = OnlyReadsMemory; 258a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman 25942c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); 260a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman} 261a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman 262a8598bec287108d0359880d33955759dc90cd5a1Dan GohmanAliasAnalysis::ModRefBehavior 263a8598bec287108d0359880d33955759dc90cd5a1Dan GohmanTypeBasedAliasAnalysis::getModRefBehavior(const Function *F) { 26442c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman // Functions don't have metadata. Just chain to the next implementation. 265a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman return AliasAnalysis::getModRefBehavior(F); 266a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman} 267a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman 26887c5c2f069fe18df5a372e6eb7bbca3be4d09facDan GohmanAliasAnalysis::ModRefResult 26987c5c2f069fe18df5a372e6eb7bbca3be4d09facDan GohmanTypeBasedAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 27087c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman const Location &Loc) { 27187c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (!EnableTBAA) 27287c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return AliasAnalysis::getModRefInfo(CS, Loc); 27387c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 27487c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (const MDNode *L = Loc.TBAATag) 27587c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (const MDNode *M = 27687c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 27787c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (!Aliases(L, M)) 27887c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return NoModRef; 27987c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 28087c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return AliasAnalysis::getModRefInfo(CS, Loc); 28187c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman} 28287c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 28387c5c2f069fe18df5a372e6eb7bbca3be4d09facDan GohmanAliasAnalysis::ModRefResult 28487c5c2f069fe18df5a372e6eb7bbca3be4d09facDan GohmanTypeBasedAliasAnalysis::getModRefInfo(ImmutableCallSite CS1, 28587c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman ImmutableCallSite CS2) { 28687c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (!EnableTBAA) 28787c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return AliasAnalysis::getModRefInfo(CS1, CS2); 28887c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 28987c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (const MDNode *M1 = 29087c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman CS1.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 29187c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (const MDNode *M2 = 29287c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman CS2.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 29387c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (!Aliases(M1, M2)) 29487c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return NoModRef; 29587c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 29687c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return AliasAnalysis::getModRefInfo(CS1, CS2); 29787c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman} 298