TypeBasedAliasAnalysis.cpp revision d04a8d4b33ff316ca4cf961e06c9e312eff8e64f
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 347a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner// all of its descendants 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/Passes.h" 61d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/AliasAnalysis.h" 62562b84b3aea359d1f918184e355da82bf05eb290Jay Foad#include "llvm/Constants.h" 6387c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman#include "llvm/LLVMContext.h" 64c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Metadata.h" 65d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Module.h" 66c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Pass.h" 6701b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman#include "llvm/Support/CommandLine.h" 68c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmanusing namespace llvm; 69c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 70326faecc3506fae441795b1f0c75e8b96bf11ce1Dan Gohman// A handy option for disabling TBAA functionality. The same effect can also be 71326faecc3506fae441795b1f0c75e8b96bf11ce1Dan Gohman// achieved by stripping the !tbaa tags from IR, but this option is sometimes 72326faecc3506fae441795b1f0c75e8b96bf11ce1Dan Gohman// more convenient. 73d67ca9de89ea4e13c3e9832ecf587d09d16d65c8Dan Gohmanstatic cl::opt<bool> EnableTBAA("enable-tbaa", cl::init(true)); 7401b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman 75c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmannamespace { 76c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// TBAANode - This is a simple wrapper around an MDNode which provides a 77c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// higher-level interface by hiding the details of how alias analysis 78c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// information is encoded in its operands. 79c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman class TBAANode { 80c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman const MDNode *Node; 81c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 82c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman public: 83c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman TBAANode() : Node(0) {} 84e6291ae96efa1e27ca6606ac59b17e35d45c057eDan Gohman explicit TBAANode(const MDNode *N) : Node(N) {} 85c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 86c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// getNode - Get the MDNode for this TBAANode. 87c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman const MDNode *getNode() const { return Node; } 88c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 890b62f95ea81d8954c21a2ae54602be10e5e1bb7eDan Gohman /// getParent - Get this TBAANode's Alias tree parent. 90c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman TBAANode getParent() const { 91c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (Node->getNumOperands() < 2) 92c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return TBAANode(); 93c05d8aa6db088b0f2e2d569d59d87de11cec9c29Dan Gohman MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1)); 94c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!P) 95c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return TBAANode(); 96c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Ok, this node has a valid parent. Return it. 97c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return TBAANode(P); 98c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 99c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 100c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// TypeIsImmutable - Test if this TBAANode represents a type for objects 101c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// which are not modified (by any means) in the context where this 102c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// AliasAnalysis is relevant. 103c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman bool TypeIsImmutable() const { 104c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (Node->getNumOperands() < 3) 105c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return false; 106c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman ConstantInt *CI = dyn_cast<ConstantInt>(Node->getOperand(2)); 107c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!CI) 108c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return false; 109ae92af6771f0a87b380706bc20e69d90bc0c1818Dan Gohman return CI->getValue()[0]; 110c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 111c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman }; 112c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 113c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 114c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmannamespace { 115c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// TypeBasedAliasAnalysis - This is a simple alias analysis 116c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// implementation that uses TypeBased to answer queries. 117c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman class TypeBasedAliasAnalysis : public ImmutablePass, 118c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman public AliasAnalysis { 119c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman public: 120c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman static char ID; // Class identification, replacement for typeinfo 121081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson TypeBasedAliasAnalysis() : ImmutablePass(ID) { 122081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeTypeBasedAliasAnalysisPass(*PassRegistry::getPassRegistry()); 123081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 124c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 125633e7023177837537adabf775395ebe7ab51b38fDan Gohman virtual void initializePass() { 126633e7023177837537adabf775395ebe7ab51b38fDan Gohman InitializeAliasAnalysis(this); 127633e7023177837537adabf775395ebe7ab51b38fDan Gohman } 128633e7023177837537adabf775395ebe7ab51b38fDan Gohman 129c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// getAdjustedAnalysisPointer - This method is used when a pass implements 130c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// an analysis interface through multiple inheritance. If needed, it 131c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// should override this to adjust the this pointer as needed for the 132c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// specified pass info. 13390c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson virtual void *getAdjustedAnalysisPointer(const void *PI) { 13490c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson if (PI == &AliasAnalysis::ID) 135c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return (AliasAnalysis*)this; 136c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return this; 137c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 138c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 139ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman bool Aliases(const MDNode *A, const MDNode *B) const; 140ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 141c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman private: 142c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman virtual void getAnalysisUsage(AnalysisUsage &AU) const; 143b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman virtual AliasResult alias(const Location &LocA, const Location &LocB); 144a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal); 145a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS); 146a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman virtual ModRefBehavior getModRefBehavior(const Function *F); 14787c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman virtual ModRefResult getModRefInfo(ImmutableCallSite CS, 14887c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman const Location &Loc); 14987c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, 15087c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman ImmutableCallSite CS2); 151c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman }; 152c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} // End of anonymous namespace 153c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 154c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// Register this pass... 155c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmanchar TypeBasedAliasAnalysis::ID = 0; 156c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan GohmanINITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa", 157ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Type-Based Alias Analysis", false, true, false) 158c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 159c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan GohmanImmutablePass *llvm::createTypeBasedAliasAnalysisPass() { 160c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return new TypeBasedAliasAnalysis(); 161c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 162c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 163c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmanvoid 164c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan GohmanTypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 165c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman AU.setPreservesAll(); 166c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman AliasAnalysis::getAnalysisUsage(AU); 167c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 168c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 169ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman/// Aliases - Test whether the type represented by A may alias the 170ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman/// type represented by B. 171ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohmanbool 172ba13864483b696e7f8e2058c3a50b5d901f2213bDan GohmanTypeBasedAliasAnalysis::Aliases(const MDNode *A, 173ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman const MDNode *B) const { 174c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Keep track of the root node for A and B. 175c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman TBAANode RootA, RootB; 176c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 1770b62f95ea81d8954c21a2ae54602be10e5e1bb7eDan Gohman // Climb the tree from A to see if we reach B. 178ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman for (TBAANode T(A); ; ) { 179ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (T.getNode() == B) 180c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // B is an ancestor of A. 181ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return true; 182c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 183c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman RootA = T; 184c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman T = T.getParent(); 185c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!T.getNode()) 186c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman break; 187c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 188c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 1890b62f95ea81d8954c21a2ae54602be10e5e1bb7eDan Gohman // Climb the tree from B to see if we reach A. 190ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman for (TBAANode T(B); ; ) { 191ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (T.getNode() == A) 192c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // A is an ancestor of B. 193ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return true; 194c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 195c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman RootB = T; 196c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman T = T.getParent(); 197c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!T.getNode()) 198c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman break; 199c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 200c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 201c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Neither node is an ancestor of the other. 202c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 203c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // If they have different roots, they're part of different potentially 204c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // unrelated type systems, so we must be conservative. 205ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (RootA.getNode() != RootB.getNode()) 206ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return true; 207ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 208ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // If they have the same root, then we've proved there's no alias. 209ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return false; 210ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman} 211ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 212ba13864483b696e7f8e2058c3a50b5d901f2213bDan GohmanAliasAnalysis::AliasResult 213ba13864483b696e7f8e2058c3a50b5d901f2213bDan GohmanTypeBasedAliasAnalysis::alias(const Location &LocA, 214ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman const Location &LocB) { 215ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (!EnableTBAA) 216ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return AliasAnalysis::alias(LocA, LocB); 217ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 218ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must 219ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // be conservative. 220ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman const MDNode *AM = LocA.TBAATag; 221ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (!AM) return AliasAnalysis::alias(LocA, LocB); 222ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman const MDNode *BM = LocB.TBAATag; 223ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (!BM) return AliasAnalysis::alias(LocA, LocB); 224ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 225ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // If they may alias, chain to the next AliasAnalysis. 226ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (Aliases(AM, BM)) 227ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return AliasAnalysis::alias(LocA, LocB); 228ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 229ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // Otherwise return a definitive result. 230ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return NoAlias; 231c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 232c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 233a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohmanbool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc, 234a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman bool OrLocal) { 23501b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman if (!EnableTBAA) 236a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 23701b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman 238e6291ae96efa1e27ca6606ac59b17e35d45c057eDan Gohman const MDNode *M = Loc.TBAATag; 239a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman if (!M) return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 240c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 241c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // If this is an "immutable" type, we can assume the pointer is pointing 242c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // to constant memory. 243acf50f5136c6f1daca2e78db756514a88470516bDan Gohman if (TBAANode(M).TypeIsImmutable()) 244acf50f5136c6f1daca2e78db756514a88470516bDan Gohman return true; 245acf50f5136c6f1daca2e78db756514a88470516bDan Gohman 246a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 247c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 24887c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 249a8598bec287108d0359880d33955759dc90cd5a1Dan GohmanAliasAnalysis::ModRefBehavior 250a8598bec287108d0359880d33955759dc90cd5a1Dan GohmanTypeBasedAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 251a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman if (!EnableTBAA) 252a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman return AliasAnalysis::getModRefBehavior(CS); 253a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman 254a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman ModRefBehavior Min = UnknownModRefBehavior; 255a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman 256a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman // If this is an "immutable" type, we can assume the call doesn't write 257a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman // to memory. 258a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman if (const MDNode *M = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 259a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman if (TBAANode(M).TypeIsImmutable()) 260a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman Min = OnlyReadsMemory; 261a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman 26242c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); 263a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman} 264a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman 265a8598bec287108d0359880d33955759dc90cd5a1Dan GohmanAliasAnalysis::ModRefBehavior 266a8598bec287108d0359880d33955759dc90cd5a1Dan GohmanTypeBasedAliasAnalysis::getModRefBehavior(const Function *F) { 26742c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman // Functions don't have metadata. Just chain to the next implementation. 268a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman return AliasAnalysis::getModRefBehavior(F); 269a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman} 270a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman 27187c5c2f069fe18df5a372e6eb7bbca3be4d09facDan GohmanAliasAnalysis::ModRefResult 27287c5c2f069fe18df5a372e6eb7bbca3be4d09facDan GohmanTypeBasedAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 27387c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman const Location &Loc) { 27487c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (!EnableTBAA) 27587c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return AliasAnalysis::getModRefInfo(CS, Loc); 27687c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 27787c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (const MDNode *L = Loc.TBAATag) 27887c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (const MDNode *M = 27987c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 28087c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (!Aliases(L, M)) 28187c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return NoModRef; 28287c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 28387c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return AliasAnalysis::getModRefInfo(CS, Loc); 28487c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman} 28587c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 28687c5c2f069fe18df5a372e6eb7bbca3be4d09facDan GohmanAliasAnalysis::ModRefResult 28787c5c2f069fe18df5a372e6eb7bbca3be4d09facDan GohmanTypeBasedAliasAnalysis::getModRefInfo(ImmutableCallSite CS1, 28887c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman ImmutableCallSite CS2) { 28987c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (!EnableTBAA) 29087c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return AliasAnalysis::getModRefInfo(CS1, CS2); 29187c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 29287c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (const MDNode *M1 = 29387c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman CS1.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 29487c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (const MDNode *M2 = 29587c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman CS2.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 29687c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (!Aliases(M1, M2)) 29787c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return NoModRef; 29887c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 29987c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return AliasAnalysis::getModRefInfo(CS1, CS2); 30087c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman} 301