TypeBasedAliasAnalysis.cpp revision ee135131b16390177c09c1620e322bcf38a78e0a
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 34ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// all of its decendents and all of its ancestors in the tree. 35c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 36de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// If the third field is present, it's an integer which if equal to 1 37ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// indicates that the type is "constant" (meaning pointsToConstantMemory 38ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// should return true; see 39bc078c81e66cbd0263fb75f533a63ac7dd1f137dDan Gohman// http://llvm.org/docs/AliasAnalysis.html#OtherItfs). 40de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// 41ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// TODO: The current metadata format doesn't support struct 42de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// fields. For example: 43de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// struct X { 44de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// double d; 45de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// int i; 46de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// }; 47de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// void foo(struct X *x, struct X *y, double *p) { 48de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// *x = *y; 49de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// *p = 0.0; 50de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// } 51de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// Struct X has a double member, so the store to *x can alias the store to *p. 52de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// Currently it's not possible to precisely describe all the things struct X 53de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// aliases, so struct assignments must use conservative TBAA nodes. There's 54de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// no scheme for attaching metadata to @llvm.memcpy yet either. 55c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 56c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman//===----------------------------------------------------------------------===// 57c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 58c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Analysis/AliasAnalysis.h" 59c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Analysis/Passes.h" 60c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Module.h" 61c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Metadata.h" 62c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Pass.h" 6301b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman#include "llvm/Support/CommandLine.h" 64c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmanusing namespace llvm; 65c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 6601b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman// For testing purposes, enable TBAA only via a special option. 6701b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohmanstatic cl::opt<bool> EnableTBAA("enable-tbaa"); 6801b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman 69c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmannamespace { 70c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// TBAANode - This is a simple wrapper around an MDNode which provides a 71c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// higher-level interface by hiding the details of how alias analysis 72c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// information is encoded in its operands. 73c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman class TBAANode { 74c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman const MDNode *Node; 75c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 76c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman public: 77c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman TBAANode() : Node(0) {} 78e6291ae96efa1e27ca6606ac59b17e35d45c057eDan Gohman explicit TBAANode(const MDNode *N) : Node(N) {} 79c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 80c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// getNode - Get the MDNode for this TBAANode. 81c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman const MDNode *getNode() const { return Node; } 82c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 830b62f95ea81d8954c21a2ae54602be10e5e1bb7eDan Gohman /// getParent - Get this TBAANode's Alias tree parent. 84c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman TBAANode getParent() const { 85c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (Node->getNumOperands() < 2) 86c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return TBAANode(); 87c05d8aa6db088b0f2e2d569d59d87de11cec9c29Dan Gohman MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1)); 88c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!P) 89c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return TBAANode(); 90c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Ok, this node has a valid parent. Return it. 91c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return TBAANode(P); 92c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 93c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 94c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// TypeIsImmutable - Test if this TBAANode represents a type for objects 95c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// which are not modified (by any means) in the context where this 96c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// AliasAnalysis is relevant. 97c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman bool TypeIsImmutable() const { 98c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (Node->getNumOperands() < 3) 99c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return false; 100c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman ConstantInt *CI = dyn_cast<ConstantInt>(Node->getOperand(2)); 101c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!CI) 102c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return false; 103c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // TODO: Think about the encoding. 104c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return CI->isOne(); 105c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 106c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman }; 107c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 108c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 109c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmannamespace { 110c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// TypeBasedAliasAnalysis - This is a simple alias analysis 111c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// implementation that uses TypeBased to answer queries. 112c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman class TypeBasedAliasAnalysis : public ImmutablePass, 113c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman public AliasAnalysis { 114c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman public: 115c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman static char ID; // Class identification, replacement for typeinfo 116081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson TypeBasedAliasAnalysis() : ImmutablePass(ID) { 117081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeTypeBasedAliasAnalysisPass(*PassRegistry::getPassRegistry()); 118081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 119c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 120633e7023177837537adabf775395ebe7ab51b38fDan Gohman virtual void initializePass() { 121633e7023177837537adabf775395ebe7ab51b38fDan Gohman InitializeAliasAnalysis(this); 122633e7023177837537adabf775395ebe7ab51b38fDan Gohman } 123633e7023177837537adabf775395ebe7ab51b38fDan Gohman 124c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// getAdjustedAnalysisPointer - This method is used when a pass implements 125c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// an analysis interface through multiple inheritance. If needed, it 126c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// should override this to adjust the this pointer as needed for the 127c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// specified pass info. 12890c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson virtual void *getAdjustedAnalysisPointer(const void *PI) { 12990c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson if (PI == &AliasAnalysis::ID) 130c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return (AliasAnalysis*)this; 131c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return this; 132c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 133c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 134ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman bool Aliases(const MDNode *A, const MDNode *B) const; 135ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 136c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman private: 137c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman virtual void getAnalysisUsage(AnalysisUsage &AU) const; 138b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman virtual AliasResult alias(const Location &LocA, const Location &LocB); 139b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman virtual bool pointsToConstantMemory(const Location &Loc); 140c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman }; 141c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} // End of anonymous namespace 142c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 143c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// Register this pass... 144c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmanchar TypeBasedAliasAnalysis::ID = 0; 145c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan GohmanINITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa", 146ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Type-Based Alias Analysis", false, true, false) 147c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 148c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan GohmanImmutablePass *llvm::createTypeBasedAliasAnalysisPass() { 149c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return new TypeBasedAliasAnalysis(); 150c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 151c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 152c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmanvoid 153c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan GohmanTypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 154c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman AU.setPreservesAll(); 155c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman AliasAnalysis::getAnalysisUsage(AU); 156c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 157c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 158ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman/// Aliases - Test whether the type represented by A may alias the 159ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman/// type represented by B. 160ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohmanbool 161ba13864483b696e7f8e2058c3a50b5d901f2213bDan GohmanTypeBasedAliasAnalysis::Aliases(const MDNode *A, 162ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman const MDNode *B) const { 163c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Keep track of the root node for A and B. 164c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman TBAANode RootA, RootB; 165c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 1660b62f95ea81d8954c21a2ae54602be10e5e1bb7eDan Gohman // Climb the tree from A to see if we reach B. 167ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman for (TBAANode T(A); ; ) { 168ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (T.getNode() == B) 169c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // B is an ancestor of A. 170ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return true; 171c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 172c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman RootA = T; 173c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman T = T.getParent(); 174c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!T.getNode()) 175c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman break; 176c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 177c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 1780b62f95ea81d8954c21a2ae54602be10e5e1bb7eDan Gohman // Climb the tree from B to see if we reach A. 179ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman for (TBAANode T(B); ; ) { 180ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (T.getNode() == A) 181c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // A is an ancestor of B. 182ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return true; 183c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 184c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman RootB = T; 185c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman T = T.getParent(); 186c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!T.getNode()) 187c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman break; 188c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 189c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 190c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Neither node is an ancestor of the other. 191c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 192c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // If they have different roots, they're part of different potentially 193c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // unrelated type systems, so we must be conservative. 194ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (RootA.getNode() != RootB.getNode()) 195ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return true; 196ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 197ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // If they have the same root, then we've proved there's no alias. 198ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return false; 199ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman} 200ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 201ba13864483b696e7f8e2058c3a50b5d901f2213bDan GohmanAliasAnalysis::AliasResult 202ba13864483b696e7f8e2058c3a50b5d901f2213bDan GohmanTypeBasedAliasAnalysis::alias(const Location &LocA, 203ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman const Location &LocB) { 204ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (!EnableTBAA) 205ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return AliasAnalysis::alias(LocA, LocB); 206ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 207ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must 208ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // be conservative. 209ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman const MDNode *AM = LocA.TBAATag; 210ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (!AM) return AliasAnalysis::alias(LocA, LocB); 211ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman const MDNode *BM = LocB.TBAATag; 212ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (!BM) return AliasAnalysis::alias(LocA, LocB); 213ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 214ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // If they may alias, chain to the next AliasAnalysis. 215ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (Aliases(AM, BM)) 216ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return AliasAnalysis::alias(LocA, LocB); 217ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 218ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // Otherwise return a definitive result. 219ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return NoAlias; 220c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 221c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 222b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohmanbool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc) { 22301b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman if (!EnableTBAA) 22401b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman return AliasAnalysis::pointsToConstantMemory(Loc); 22501b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman 226e6291ae96efa1e27ca6606ac59b17e35d45c057eDan Gohman const MDNode *M = Loc.TBAATag; 227c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!M) return false; 228c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 229c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // If this is an "immutable" type, we can assume the pointer is pointing 230c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // to constant memory. 231acf50f5136c6f1daca2e78db756514a88470516bDan Gohman if (TBAANode(M).TypeIsImmutable()) 232acf50f5136c6f1daca2e78db756514a88470516bDan Gohman return true; 233acf50f5136c6f1daca2e78db756514a88470516bDan Gohman 234acf50f5136c6f1daca2e78db756514a88470516bDan Gohman return AliasAnalysis::pointsToConstantMemory(Loc); 235c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 236