1212793Sdim//===- TypeBasedAliasAnalysis.cpp - Type-Based Alias Analysis -------------===// 2212793Sdim// 3212793Sdim// The LLVM Compiler Infrastructure 4212793Sdim// 5212793Sdim// This file is distributed under the University of Illinois Open Source 6212793Sdim// License. See LICENSE.TXT for details. 7212793Sdim// 8212793Sdim//===----------------------------------------------------------------------===// 9212793Sdim// 10212793Sdim// This file defines the TypeBasedAliasAnalysis pass, which implements 11212793Sdim// metadata-based TBAA. 12212793Sdim// 13212793Sdim// In LLVM IR, memory does not have types, so LLVM's own type system is not 14212793Sdim// suitable for doing TBAA. Instead, metadata is added to the IR to describe 15218893Sdim// a type system of a higher level language. This can be used to implement 16218893Sdim// typical C/C++ TBAA, but it can also be used to implement custom alias 17218893Sdim// analysis behavior for other languages. 18212793Sdim// 19263509Sdim// We now support two types of metadata format: scalar TBAA and struct-path 20263509Sdim// aware TBAA. After all testing cases are upgraded to use struct-path aware 21263509Sdim// TBAA and we can auto-upgrade existing bc files, the support for scalar TBAA 22263509Sdim// can be dropped. 23263509Sdim// 24263509Sdim// The scalar TBAA metadata format is very simple. TBAA MDNodes have up to 25218893Sdim// three fields, e.g.: 26218893Sdim// !0 = metadata !{ metadata !"an example type tree" } 27218893Sdim// !1 = metadata !{ metadata !"int", metadata !0 } 28218893Sdim// !2 = metadata !{ metadata !"float", metadata !0 } 29218893Sdim// !3 = metadata !{ metadata !"const float", metadata !2, i64 1 } 30212793Sdim// 31218893Sdim// The first field is an identity field. It can be any value, usually 32218893Sdim// an MDString, which uniquely identifies the type. The most important 33218893Sdim// name in the tree is the name of the root node. Two trees with 34218893Sdim// different root node names are entirely disjoint, even if they 35218893Sdim// have leaves with common names. 36212793Sdim// 37218893Sdim// The second field identifies the type's parent node in the tree, or 38218893Sdim// is null or omitted for a root node. A type is considered to alias 39221345Sdim// all of its descendants and all of its ancestors in the tree. Also, 40218893Sdim// a type is considered to alias all types in other trees, so that 41218893Sdim// bitcode produced from multiple front-ends is handled conservatively. 42212793Sdim// 43218893Sdim// If the third field is present, it's an integer which if equal to 1 44218893Sdim// indicates that the type is "constant" (meaning pointsToConstantMemory 45218893Sdim// should return true; see 46218893Sdim// http://llvm.org/docs/AliasAnalysis.html#OtherItfs). 47218893Sdim// 48263509Sdim// With struct-path aware TBAA, the MDNodes attached to an instruction using 49263509Sdim// "!tbaa" are called path tag nodes. 50263509Sdim// 51263509Sdim// The path tag node has 4 fields with the last field being optional. 52263509Sdim// 53263509Sdim// The first field is the base type node, it can be a struct type node 54263509Sdim// or a scalar type node. The second field is the access type node, it 55263509Sdim// must be a scalar type node. The third field is the offset into the base type. 56263509Sdim// The last field has the same meaning as the last field of our scalar TBAA: 57263509Sdim// it's an integer which if equal to 1 indicates that the access is "constant". 58263509Sdim// 59263509Sdim// The struct type node has a name and a list of pairs, one pair for each member 60263509Sdim// of the struct. The first element of each pair is a type node (a struct type 61263509Sdim// node or a sclar type node), specifying the type of the member, the second 62263509Sdim// element of each pair is the offset of the member. 63263509Sdim// 64263509Sdim// Given an example 65263509Sdim// typedef struct { 66263509Sdim// short s; 67263509Sdim// } A; 68263509Sdim// typedef struct { 69263509Sdim// uint16_t s; 70263509Sdim// A a; 71263509Sdim// } B; 72263509Sdim// 73263509Sdim// For an acess to B.a.s, we attach !5 (a path tag node) to the load/store 74263509Sdim// instruction. The base type is !4 (struct B), the access type is !2 (scalar 75263509Sdim// type short) and the offset is 4. 76263509Sdim// 77263509Sdim// !0 = metadata !{metadata !"Simple C/C++ TBAA"} 78263509Sdim// !1 = metadata !{metadata !"omnipotent char", metadata !0} // Scalar type node 79263509Sdim// !2 = metadata !{metadata !"short", metadata !1} // Scalar type node 80263509Sdim// !3 = metadata !{metadata !"A", metadata !2, i64 0} // Struct type node 81263509Sdim// !4 = metadata !{metadata !"B", metadata !2, i64 0, metadata !3, i64 4} 82263509Sdim// // Struct type node 83263509Sdim// !5 = metadata !{metadata !4, metadata !2, i64 4} // Path tag node 84263509Sdim// 85263509Sdim// The struct type nodes and the scalar type nodes form a type DAG. 86263509Sdim// Root (!0) 87263509Sdim// char (!1) -- edge to Root 88263509Sdim// short (!2) -- edge to char 89263509Sdim// A (!3) -- edge with offset 0 to short 90263509Sdim// B (!4) -- edge with offset 0 to short and edge with offset 4 to A 91263509Sdim// 92263509Sdim// To check if two tags (tagX and tagY) can alias, we start from the base type 93263509Sdim// of tagX, follow the edge with the correct offset in the type DAG and adjust 94263509Sdim// the offset until we reach the base type of tagY or until we reach the Root 95263509Sdim// node. 96263509Sdim// If we reach the base type of tagY, compare the adjusted offset with 97263509Sdim// offset of tagY, return Alias if the offsets are the same, return NoAlias 98263509Sdim// otherwise. 99263509Sdim// If we reach the Root node, perform the above starting from base type of tagY 100263509Sdim// to see if we reach base type of tagX. 101263509Sdim// 102263509Sdim// If they have different roots, they're part of different potentially 103263509Sdim// unrelated type systems, so we return Alias to be conservative. 104263509Sdim// If neither node is an ancestor of the other and they have the same root, 105263509Sdim// then we say NoAlias. 106263509Sdim// 107218893Sdim// TODO: The current metadata format doesn't support struct 108218893Sdim// fields. For example: 109218893Sdim// struct X { 110218893Sdim// double d; 111218893Sdim// int i; 112218893Sdim// }; 113218893Sdim// void foo(struct X *x, struct X *y, double *p) { 114218893Sdim// *x = *y; 115218893Sdim// *p = 0.0; 116218893Sdim// } 117218893Sdim// Struct X has a double member, so the store to *x can alias the store to *p. 118218893Sdim// Currently it's not possible to precisely describe all the things struct X 119218893Sdim// aliases, so struct assignments must use conservative TBAA nodes. There's 120218893Sdim// no scheme for attaching metadata to @llvm.memcpy yet either. 121218893Sdim// 122212793Sdim//===----------------------------------------------------------------------===// 123212793Sdim 124252723Sdim#include "llvm/Analysis/Passes.h" 125212793Sdim#include "llvm/Analysis/AliasAnalysis.h" 126252723Sdim#include "llvm/IR/Constants.h" 127252723Sdim#include "llvm/IR/LLVMContext.h" 128252723Sdim#include "llvm/IR/Metadata.h" 129252723Sdim#include "llvm/IR/Module.h" 130212793Sdim#include "llvm/Pass.h" 131218893Sdim#include "llvm/Support/CommandLine.h" 132212793Sdimusing namespace llvm; 133212793Sdim 134218893Sdim// A handy option for disabling TBAA functionality. The same effect can also be 135218893Sdim// achieved by stripping the !tbaa tags from IR, but this option is sometimes 136218893Sdim// more convenient. 137218893Sdimstatic cl::opt<bool> EnableTBAA("enable-tbaa", cl::init(true)); 138218893Sdim 139212793Sdimnamespace { 140212793Sdim /// TBAANode - This is a simple wrapper around an MDNode which provides a 141212793Sdim /// higher-level interface by hiding the details of how alias analysis 142212793Sdim /// information is encoded in its operands. 143212793Sdim class TBAANode { 144212793Sdim const MDNode *Node; 145212793Sdim 146212793Sdim public: 147212793Sdim TBAANode() : Node(0) {} 148218893Sdim explicit TBAANode(const MDNode *N) : Node(N) {} 149212793Sdim 150212793Sdim /// getNode - Get the MDNode for this TBAANode. 151212793Sdim const MDNode *getNode() const { return Node; } 152212793Sdim 153218893Sdim /// getParent - Get this TBAANode's Alias tree parent. 154212793Sdim TBAANode getParent() const { 155212793Sdim if (Node->getNumOperands() < 2) 156212793Sdim return TBAANode(); 157218893Sdim MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1)); 158212793Sdim if (!P) 159212793Sdim return TBAANode(); 160212793Sdim // Ok, this node has a valid parent. Return it. 161212793Sdim return TBAANode(P); 162212793Sdim } 163212793Sdim 164212793Sdim /// TypeIsImmutable - Test if this TBAANode represents a type for objects 165212793Sdim /// which are not modified (by any means) in the context where this 166212793Sdim /// AliasAnalysis is relevant. 167212793Sdim bool TypeIsImmutable() const { 168212793Sdim if (Node->getNumOperands() < 3) 169212793Sdim return false; 170212793Sdim ConstantInt *CI = dyn_cast<ConstantInt>(Node->getOperand(2)); 171212793Sdim if (!CI) 172212793Sdim return false; 173218893Sdim return CI->getValue()[0]; 174212793Sdim } 175212793Sdim }; 176252723Sdim 177252723Sdim /// This is a simple wrapper around an MDNode which provides a 178252723Sdim /// higher-level interface by hiding the details of how alias analysis 179252723Sdim /// information is encoded in its operands. 180252723Sdim class TBAAStructTagNode { 181252723Sdim /// This node should be created with createTBAAStructTagNode. 182252723Sdim const MDNode *Node; 183252723Sdim 184252723Sdim public: 185252723Sdim TBAAStructTagNode() : Node(0) {} 186252723Sdim explicit TBAAStructTagNode(const MDNode *N) : Node(N) {} 187252723Sdim 188252723Sdim /// Get the MDNode for this TBAAStructTagNode. 189252723Sdim const MDNode *getNode() const { return Node; } 190252723Sdim 191252723Sdim const MDNode *getBaseType() const { 192252723Sdim return dyn_cast_or_null<MDNode>(Node->getOperand(0)); 193252723Sdim } 194252723Sdim const MDNode *getAccessType() const { 195252723Sdim return dyn_cast_or_null<MDNode>(Node->getOperand(1)); 196252723Sdim } 197252723Sdim uint64_t getOffset() const { 198252723Sdim return cast<ConstantInt>(Node->getOperand(2))->getZExtValue(); 199252723Sdim } 200252723Sdim /// TypeIsImmutable - Test if this TBAAStructTagNode represents a type for 201252723Sdim /// objects which are not modified (by any means) in the context where this 202252723Sdim /// AliasAnalysis is relevant. 203252723Sdim bool TypeIsImmutable() const { 204252723Sdim if (Node->getNumOperands() < 4) 205252723Sdim return false; 206252723Sdim ConstantInt *CI = dyn_cast<ConstantInt>(Node->getOperand(3)); 207252723Sdim if (!CI) 208252723Sdim return false; 209252723Sdim return CI->getValue()[0]; 210252723Sdim } 211252723Sdim }; 212252723Sdim 213252723Sdim /// This is a simple wrapper around an MDNode which provides a 214252723Sdim /// higher-level interface by hiding the details of how alias analysis 215252723Sdim /// information is encoded in its operands. 216252723Sdim class TBAAStructTypeNode { 217252723Sdim /// This node should be created with createTBAAStructTypeNode. 218252723Sdim const MDNode *Node; 219252723Sdim 220252723Sdim public: 221252723Sdim TBAAStructTypeNode() : Node(0) {} 222252723Sdim explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {} 223252723Sdim 224252723Sdim /// Get the MDNode for this TBAAStructTypeNode. 225252723Sdim const MDNode *getNode() const { return Node; } 226252723Sdim 227252723Sdim /// Get this TBAAStructTypeNode's field in the type DAG with 228252723Sdim /// given offset. Update the offset to be relative to the field type. 229252723Sdim TBAAStructTypeNode getParent(uint64_t &Offset) const { 230252723Sdim // Parent can be omitted for the root node. 231252723Sdim if (Node->getNumOperands() < 2) 232252723Sdim return TBAAStructTypeNode(); 233252723Sdim 234263509Sdim // Fast path for a scalar type node and a struct type node with a single 235263509Sdim // field. 236252723Sdim if (Node->getNumOperands() <= 3) { 237263509Sdim uint64_t Cur = Node->getNumOperands() == 2 ? 0 : 238263509Sdim cast<ConstantInt>(Node->getOperand(2))->getZExtValue(); 239263509Sdim Offset -= Cur; 240252723Sdim MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1)); 241252723Sdim if (!P) 242252723Sdim return TBAAStructTypeNode(); 243252723Sdim return TBAAStructTypeNode(P); 244252723Sdim } 245252723Sdim 246252723Sdim // Assume the offsets are in order. We return the previous field if 247252723Sdim // the current offset is bigger than the given offset. 248252723Sdim unsigned TheIdx = 0; 249252723Sdim for (unsigned Idx = 1; Idx < Node->getNumOperands(); Idx += 2) { 250252723Sdim uint64_t Cur = cast<ConstantInt>(Node->getOperand(Idx + 1))-> 251252723Sdim getZExtValue(); 252252723Sdim if (Cur > Offset) { 253252723Sdim assert(Idx >= 3 && 254252723Sdim "TBAAStructTypeNode::getParent should have an offset match!"); 255252723Sdim TheIdx = Idx - 2; 256252723Sdim break; 257252723Sdim } 258252723Sdim } 259252723Sdim // Move along the last field. 260252723Sdim if (TheIdx == 0) 261252723Sdim TheIdx = Node->getNumOperands() - 2; 262252723Sdim uint64_t Cur = cast<ConstantInt>(Node->getOperand(TheIdx + 1))-> 263252723Sdim getZExtValue(); 264252723Sdim Offset -= Cur; 265252723Sdim MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(TheIdx)); 266252723Sdim if (!P) 267252723Sdim return TBAAStructTypeNode(); 268252723Sdim return TBAAStructTypeNode(P); 269252723Sdim } 270252723Sdim }; 271212793Sdim} 272212793Sdim 273212793Sdimnamespace { 274212793Sdim /// TypeBasedAliasAnalysis - This is a simple alias analysis 275212793Sdim /// implementation that uses TypeBased to answer queries. 276212793Sdim class TypeBasedAliasAnalysis : public ImmutablePass, 277212793Sdim public AliasAnalysis { 278212793Sdim public: 279212793Sdim static char ID; // Class identification, replacement for typeinfo 280218893Sdim TypeBasedAliasAnalysis() : ImmutablePass(ID) { 281218893Sdim initializeTypeBasedAliasAnalysisPass(*PassRegistry::getPassRegistry()); 282218893Sdim } 283212793Sdim 284218893Sdim virtual void initializePass() { 285218893Sdim InitializeAliasAnalysis(this); 286218893Sdim } 287218893Sdim 288212793Sdim /// getAdjustedAnalysisPointer - This method is used when a pass implements 289212793Sdim /// an analysis interface through multiple inheritance. If needed, it 290212793Sdim /// should override this to adjust the this pointer as needed for the 291212793Sdim /// specified pass info. 292212793Sdim virtual void *getAdjustedAnalysisPointer(const void *PI) { 293212793Sdim if (PI == &AliasAnalysis::ID) 294212793Sdim return (AliasAnalysis*)this; 295212793Sdim return this; 296212793Sdim } 297212793Sdim 298218893Sdim bool Aliases(const MDNode *A, const MDNode *B) const; 299252723Sdim bool PathAliases(const MDNode *A, const MDNode *B) const; 300218893Sdim 301212793Sdim private: 302212793Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const; 303218893Sdim virtual AliasResult alias(const Location &LocA, const Location &LocB); 304218893Sdim virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal); 305218893Sdim virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS); 306218893Sdim virtual ModRefBehavior getModRefBehavior(const Function *F); 307218893Sdim virtual ModRefResult getModRefInfo(ImmutableCallSite CS, 308218893Sdim const Location &Loc); 309218893Sdim virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, 310218893Sdim ImmutableCallSite CS2); 311212793Sdim }; 312212793Sdim} // End of anonymous namespace 313212793Sdim 314212793Sdim// Register this pass... 315212793Sdimchar TypeBasedAliasAnalysis::ID = 0; 316212793SdimINITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa", 317218893Sdim "Type-Based Alias Analysis", false, true, false) 318212793Sdim 319212793SdimImmutablePass *llvm::createTypeBasedAliasAnalysisPass() { 320212793Sdim return new TypeBasedAliasAnalysis(); 321212793Sdim} 322212793Sdim 323212793Sdimvoid 324212793SdimTypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 325212793Sdim AU.setPreservesAll(); 326212793Sdim AliasAnalysis::getAnalysisUsage(AU); 327212793Sdim} 328212793Sdim 329263509Sdim/// Check the first operand of the tbaa tag node, if it is a MDNode, we treat 330263509Sdim/// it as struct-path aware TBAA format, otherwise, we treat it as scalar TBAA 331263509Sdim/// format. 332263509Sdimstatic bool isStructPathTBAA(const MDNode *MD) { 333263509Sdim // Anonymous TBAA root starts with a MDNode and dragonegg uses it as 334263509Sdim // a TBAA tag. 335263509Sdim return isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3; 336263509Sdim} 337263509Sdim 338218893Sdim/// Aliases - Test whether the type represented by A may alias the 339218893Sdim/// type represented by B. 340218893Sdimbool 341218893SdimTypeBasedAliasAnalysis::Aliases(const MDNode *A, 342218893Sdim const MDNode *B) const { 343263509Sdim if (isStructPathTBAA(A)) 344252723Sdim return PathAliases(A, B); 345252723Sdim 346212793Sdim // Keep track of the root node for A and B. 347212793Sdim TBAANode RootA, RootB; 348212793Sdim 349218893Sdim // Climb the tree from A to see if we reach B. 350218893Sdim for (TBAANode T(A); ; ) { 351218893Sdim if (T.getNode() == B) 352212793Sdim // B is an ancestor of A. 353218893Sdim return true; 354212793Sdim 355212793Sdim RootA = T; 356212793Sdim T = T.getParent(); 357212793Sdim if (!T.getNode()) 358212793Sdim break; 359212793Sdim } 360212793Sdim 361218893Sdim // Climb the tree from B to see if we reach A. 362218893Sdim for (TBAANode T(B); ; ) { 363218893Sdim if (T.getNode() == A) 364212793Sdim // A is an ancestor of B. 365218893Sdim return true; 366212793Sdim 367212793Sdim RootB = T; 368212793Sdim T = T.getParent(); 369212793Sdim if (!T.getNode()) 370212793Sdim break; 371212793Sdim } 372212793Sdim 373212793Sdim // Neither node is an ancestor of the other. 374212793Sdim 375212793Sdim // If they have different roots, they're part of different potentially 376212793Sdim // unrelated type systems, so we must be conservative. 377218893Sdim if (RootA.getNode() != RootB.getNode()) 378218893Sdim return true; 379218893Sdim 380218893Sdim // If they have the same root, then we've proved there's no alias. 381218893Sdim return false; 382212793Sdim} 383212793Sdim 384252723Sdim/// Test whether the struct-path tag represented by A may alias the 385252723Sdim/// struct-path tag represented by B. 386252723Sdimbool 387252723SdimTypeBasedAliasAnalysis::PathAliases(const MDNode *A, 388252723Sdim const MDNode *B) const { 389252723Sdim // Keep track of the root node for A and B. 390252723Sdim TBAAStructTypeNode RootA, RootB; 391252723Sdim TBAAStructTagNode TagA(A), TagB(B); 392252723Sdim 393252723Sdim // TODO: We need to check if AccessType of TagA encloses AccessType of 394252723Sdim // TagB to support aggregate AccessType. If yes, return true. 395252723Sdim 396252723Sdim // Start from the base type of A, follow the edge with the correct offset in 397252723Sdim // the type DAG and adjust the offset until we reach the base type of B or 398252723Sdim // until we reach the Root node. 399252723Sdim // Compare the adjusted offset once we have the same base. 400252723Sdim 401252723Sdim // Climb the type DAG from base type of A to see if we reach base type of B. 402252723Sdim const MDNode *BaseA = TagA.getBaseType(); 403252723Sdim const MDNode *BaseB = TagB.getBaseType(); 404252723Sdim uint64_t OffsetA = TagA.getOffset(), OffsetB = TagB.getOffset(); 405252723Sdim for (TBAAStructTypeNode T(BaseA); ; ) { 406252723Sdim if (T.getNode() == BaseB) 407252723Sdim // Base type of A encloses base type of B, check if the offsets match. 408252723Sdim return OffsetA == OffsetB; 409252723Sdim 410252723Sdim RootA = T; 411252723Sdim // Follow the edge with the correct offset, OffsetA will be adjusted to 412252723Sdim // be relative to the field type. 413252723Sdim T = T.getParent(OffsetA); 414252723Sdim if (!T.getNode()) 415252723Sdim break; 416252723Sdim } 417252723Sdim 418252723Sdim // Reset OffsetA and climb the type DAG from base type of B to see if we reach 419252723Sdim // base type of A. 420252723Sdim OffsetA = TagA.getOffset(); 421252723Sdim for (TBAAStructTypeNode T(BaseB); ; ) { 422252723Sdim if (T.getNode() == BaseA) 423252723Sdim // Base type of B encloses base type of A, check if the offsets match. 424252723Sdim return OffsetA == OffsetB; 425252723Sdim 426252723Sdim RootB = T; 427252723Sdim // Follow the edge with the correct offset, OffsetB will be adjusted to 428252723Sdim // be relative to the field type. 429252723Sdim T = T.getParent(OffsetB); 430252723Sdim if (!T.getNode()) 431252723Sdim break; 432252723Sdim } 433252723Sdim 434252723Sdim // Neither node is an ancestor of the other. 435252723Sdim 436252723Sdim // If they have different roots, they're part of different potentially 437252723Sdim // unrelated type systems, so we must be conservative. 438252723Sdim if (RootA.getNode() != RootB.getNode()) 439252723Sdim return true; 440252723Sdim 441252723Sdim // If they have the same root, then we've proved there's no alias. 442252723Sdim return false; 443252723Sdim} 444252723Sdim 445218893SdimAliasAnalysis::AliasResult 446218893SdimTypeBasedAliasAnalysis::alias(const Location &LocA, 447218893Sdim const Location &LocB) { 448218893Sdim if (!EnableTBAA) 449218893Sdim return AliasAnalysis::alias(LocA, LocB); 450212793Sdim 451218893Sdim // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must 452218893Sdim // be conservative. 453218893Sdim const MDNode *AM = LocA.TBAATag; 454218893Sdim if (!AM) return AliasAnalysis::alias(LocA, LocB); 455218893Sdim const MDNode *BM = LocB.TBAATag; 456218893Sdim if (!BM) return AliasAnalysis::alias(LocA, LocB); 457212793Sdim 458218893Sdim // If they may alias, chain to the next AliasAnalysis. 459218893Sdim if (Aliases(AM, BM)) 460218893Sdim return AliasAnalysis::alias(LocA, LocB); 461218893Sdim 462218893Sdim // Otherwise return a definitive result. 463218893Sdim return NoAlias; 464218893Sdim} 465218893Sdim 466218893Sdimbool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc, 467218893Sdim bool OrLocal) { 468218893Sdim if (!EnableTBAA) 469218893Sdim return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 470218893Sdim 471218893Sdim const MDNode *M = Loc.TBAATag; 472218893Sdim if (!M) return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 473218893Sdim 474212793Sdim // If this is an "immutable" type, we can assume the pointer is pointing 475212793Sdim // to constant memory. 476263509Sdim if ((!isStructPathTBAA(M) && TBAANode(M).TypeIsImmutable()) || 477263509Sdim (isStructPathTBAA(M) && TBAAStructTagNode(M).TypeIsImmutable())) 478218893Sdim return true; 479218893Sdim 480218893Sdim return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 481212793Sdim} 482218893Sdim 483218893SdimAliasAnalysis::ModRefBehavior 484218893SdimTypeBasedAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 485218893Sdim if (!EnableTBAA) 486218893Sdim return AliasAnalysis::getModRefBehavior(CS); 487218893Sdim 488218893Sdim ModRefBehavior Min = UnknownModRefBehavior; 489218893Sdim 490218893Sdim // If this is an "immutable" type, we can assume the call doesn't write 491218893Sdim // to memory. 492218893Sdim if (const MDNode *M = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 493263509Sdim if ((!isStructPathTBAA(M) && TBAANode(M).TypeIsImmutable()) || 494263509Sdim (isStructPathTBAA(M) && TBAAStructTagNode(M).TypeIsImmutable())) 495218893Sdim Min = OnlyReadsMemory; 496218893Sdim 497218893Sdim return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); 498218893Sdim} 499218893Sdim 500218893SdimAliasAnalysis::ModRefBehavior 501218893SdimTypeBasedAliasAnalysis::getModRefBehavior(const Function *F) { 502218893Sdim // Functions don't have metadata. Just chain to the next implementation. 503218893Sdim return AliasAnalysis::getModRefBehavior(F); 504218893Sdim} 505218893Sdim 506218893SdimAliasAnalysis::ModRefResult 507218893SdimTypeBasedAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 508218893Sdim const Location &Loc) { 509218893Sdim if (!EnableTBAA) 510218893Sdim return AliasAnalysis::getModRefInfo(CS, Loc); 511218893Sdim 512218893Sdim if (const MDNode *L = Loc.TBAATag) 513218893Sdim if (const MDNode *M = 514218893Sdim CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 515218893Sdim if (!Aliases(L, M)) 516218893Sdim return NoModRef; 517218893Sdim 518218893Sdim return AliasAnalysis::getModRefInfo(CS, Loc); 519218893Sdim} 520218893Sdim 521218893SdimAliasAnalysis::ModRefResult 522218893SdimTypeBasedAliasAnalysis::getModRefInfo(ImmutableCallSite CS1, 523218893Sdim ImmutableCallSite CS2) { 524218893Sdim if (!EnableTBAA) 525218893Sdim return AliasAnalysis::getModRefInfo(CS1, CS2); 526218893Sdim 527218893Sdim if (const MDNode *M1 = 528218893Sdim CS1.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 529218893Sdim if (const MDNode *M2 = 530218893Sdim CS2.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 531218893Sdim if (!Aliases(M1, M2)) 532218893Sdim return NoModRef; 533218893Sdim 534218893Sdim return AliasAnalysis::getModRefInfo(CS1, CS2); 535218893Sdim} 536252723Sdim 537263509Sdimbool MDNode::isTBAAVtableAccess() const { 538263509Sdim if (!isStructPathTBAA(this)) { 539263509Sdim if (getNumOperands() < 1) return false; 540263509Sdim if (MDString *Tag1 = dyn_cast<MDString>(getOperand(0))) { 541263509Sdim if (Tag1->getString() == "vtable pointer") return true; 542263509Sdim } 543263509Sdim return false; 544263509Sdim } 545263509Sdim 546263509Sdim // For struct-path aware TBAA, we use the access type of the tag. 547263509Sdim if (getNumOperands() < 2) return false; 548263509Sdim MDNode *Tag = cast_or_null<MDNode>(getOperand(1)); 549263509Sdim if (!Tag) return false; 550263509Sdim if (MDString *Tag1 = dyn_cast<MDString>(Tag->getOperand(0))) { 551263509Sdim if (Tag1->getString() == "vtable pointer") return true; 552263509Sdim } 553263509Sdim return false; 554263509Sdim} 555263509Sdim 556252723SdimMDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) { 557252723Sdim if (!A || !B) 558252723Sdim return NULL; 559252723Sdim 560252723Sdim if (A == B) 561252723Sdim return A; 562252723Sdim 563252723Sdim // For struct-path aware TBAA, we use the access type of the tag. 564263509Sdim bool StructPath = isStructPathTBAA(A); 565263509Sdim if (StructPath) { 566252723Sdim A = cast_or_null<MDNode>(A->getOperand(1)); 567252723Sdim if (!A) return 0; 568252723Sdim B = cast_or_null<MDNode>(B->getOperand(1)); 569252723Sdim if (!B) return 0; 570252723Sdim } 571252723Sdim 572252723Sdim SmallVector<MDNode *, 4> PathA; 573252723Sdim MDNode *T = A; 574252723Sdim while (T) { 575252723Sdim PathA.push_back(T); 576252723Sdim T = T->getNumOperands() >= 2 ? cast_or_null<MDNode>(T->getOperand(1)) : 0; 577252723Sdim } 578252723Sdim 579252723Sdim SmallVector<MDNode *, 4> PathB; 580252723Sdim T = B; 581252723Sdim while (T) { 582252723Sdim PathB.push_back(T); 583252723Sdim T = T->getNumOperands() >= 2 ? cast_or_null<MDNode>(T->getOperand(1)) : 0; 584252723Sdim } 585252723Sdim 586252723Sdim int IA = PathA.size() - 1; 587252723Sdim int IB = PathB.size() - 1; 588252723Sdim 589252723Sdim MDNode *Ret = 0; 590252723Sdim while (IA >= 0 && IB >=0) { 591252723Sdim if (PathA[IA] == PathB[IB]) 592252723Sdim Ret = PathA[IA]; 593252723Sdim else 594252723Sdim break; 595252723Sdim --IA; 596252723Sdim --IB; 597252723Sdim } 598263509Sdim if (!StructPath) 599252723Sdim return Ret; 600252723Sdim 601252723Sdim if (!Ret) 602252723Sdim return 0; 603252723Sdim // We need to convert from a type node to a tag node. 604252723Sdim Type *Int64 = IntegerType::get(A->getContext(), 64); 605252723Sdim Value *Ops[3] = { Ret, Ret, ConstantInt::get(Int64, 0) }; 606252723Sdim return MDNode::get(A->getContext(), Ops); 607252723Sdim} 608