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// 199e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// We now support two types of metadata format: scalar TBAA and struct-path 209e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// aware TBAA. After all testing cases are upgraded to use struct-path aware 219e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// TBAA and we can auto-upgrade existing bc files, the support for scalar TBAA 229e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// can be dropped. 239e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// 249e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// The scalar TBAA metadata format is very simple. TBAA MDNodes have up to 25ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// three fields, e.g.: 26ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// !0 = metadata !{ metadata !"an example type tree" } 27ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// !1 = metadata !{ metadata !"int", metadata !0 } 28ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// !2 = metadata !{ metadata !"float", metadata !0 } 29ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// !3 = metadata !{ metadata !"const float", metadata !2, i64 1 } 30c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 31ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// The first field is an identity field. It can be any value, usually 32ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// an MDString, which uniquely identifies the type. The most important 33ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// name in the tree is the name of the root node. Two trees with 34ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// different root node names are entirely disjoint, even if they 35ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// have leaves with common names. 36ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// 37ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// The second field identifies the type's parent node in the tree, or 38ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// is null or omitted for a root node. A type is considered to alias 397a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner// all of its descendants and all of its ancestors in the tree. Also, 40269008ee8336bb6519ed714e50fe5bb428b98a51Dan Gohman// a type is considered to alias all types in other trees, so that 41269008ee8336bb6519ed714e50fe5bb428b98a51Dan Gohman// bitcode produced from multiple front-ends is handled conservatively. 42c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 43de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// If the third field is present, it's an integer which if equal to 1 44ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// indicates that the type is "constant" (meaning pointsToConstantMemory 45ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// should return true; see 46bc078c81e66cbd0263fb75f533a63ac7dd1f137dDan Gohman// http://llvm.org/docs/AliasAnalysis.html#OtherItfs). 47de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// 489e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// With struct-path aware TBAA, the MDNodes attached to an instruction using 499e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// "!tbaa" are called path tag nodes. 509e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// 519e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// The path tag node has 4 fields with the last field being optional. 529e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// 539e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// The first field is the base type node, it can be a struct type node 549e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// or a scalar type node. The second field is the access type node, it 559e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// must be a scalar type node. The third field is the offset into the base type. 569e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// The last field has the same meaning as the last field of our scalar TBAA: 579e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// it's an integer which if equal to 1 indicates that the access is "constant". 589e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// 599e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// The struct type node has a name and a list of pairs, one pair for each member 609e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// of the struct. The first element of each pair is a type node (a struct type 619e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// node or a sclar type node), specifying the type of the member, the second 629e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// element of each pair is the offset of the member. 639e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// 649e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// Given an example 659e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// typedef struct { 669e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// short s; 679e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// } A; 689e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// typedef struct { 699e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// uint16_t s; 709e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// A a; 719e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// } B; 729e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// 739e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// For an acess to B.a.s, we attach !5 (a path tag node) to the load/store 749e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// instruction. The base type is !4 (struct B), the access type is !2 (scalar 759e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// type short) and the offset is 4. 769e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// 779e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// !0 = metadata !{metadata !"Simple C/C++ TBAA"} 789e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// !1 = metadata !{metadata !"omnipotent char", metadata !0} // Scalar type node 799e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// !2 = metadata !{metadata !"short", metadata !1} // Scalar type node 809e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// !3 = metadata !{metadata !"A", metadata !2, i64 0} // Struct type node 819e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// !4 = metadata !{metadata !"B", metadata !2, i64 0, metadata !3, i64 4} 829e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// // Struct type node 839e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// !5 = metadata !{metadata !4, metadata !2, i64 4} // Path tag node 849e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// 859e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// The struct type nodes and the scalar type nodes form a type DAG. 869e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// Root (!0) 879e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// char (!1) -- edge to Root 889e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// short (!2) -- edge to char 899e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// A (!3) -- edge with offset 0 to short 909e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// B (!4) -- edge with offset 0 to short and edge with offset 4 to A 919e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// 929e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// To check if two tags (tagX and tagY) can alias, we start from the base type 939e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// of tagX, follow the edge with the correct offset in the type DAG and adjust 949e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// the offset until we reach the base type of tagY or until we reach the Root 959e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// node. 969e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// If we reach the base type of tagY, compare the adjusted offset with 979e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// offset of tagY, return Alias if the offsets are the same, return NoAlias 989e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// otherwise. 999e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// If we reach the Root node, perform the above starting from base type of tagY 1009e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// to see if we reach base type of tagX. 1019e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// 1029e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// If they have different roots, they're part of different potentially 1039e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// unrelated type systems, so we return Alias to be conservative. 1049e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// If neither node is an ancestor of the other and they have the same root, 1059e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// then we say NoAlias. 1069e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren// 107ee135131b16390177c09c1620e322bcf38a78e0aDan Gohman// TODO: The current metadata format doesn't support struct 108de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// fields. For example: 109de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// struct X { 110de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// double d; 111de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// int i; 112de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// }; 113de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// void foo(struct X *x, struct X *y, double *p) { 114de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// *x = *y; 115de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// *p = 0.0; 116de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// } 117de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// Struct X has a double member, so the store to *x can alias the store to *p. 118de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// Currently it's not possible to precisely describe all the things struct X 119de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// aliases, so struct assignments must use conservative TBAA nodes. There's 120de38897cfc49f09ffc84fb023a76c076f4b2d402Dan Gohman// no scheme for attaching metadata to @llvm.memcpy yet either. 121c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 122c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman//===----------------------------------------------------------------------===// 123c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 124c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Analysis/Passes.h" 125d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/AliasAnalysis.h" 1260b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 1270b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 1280b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Metadata.h" 1290b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 130c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Pass.h" 13101b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman#include "llvm/Support/CommandLine.h" 132c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmanusing namespace llvm; 133c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 134326faecc3506fae441795b1f0c75e8b96bf11ce1Dan Gohman// A handy option for disabling TBAA functionality. The same effect can also be 135326faecc3506fae441795b1f0c75e8b96bf11ce1Dan Gohman// achieved by stripping the !tbaa tags from IR, but this option is sometimes 136326faecc3506fae441795b1f0c75e8b96bf11ce1Dan Gohman// more convenient. 137d67ca9de89ea4e13c3e9832ecf587d09d16d65c8Dan Gohmanstatic cl::opt<bool> EnableTBAA("enable-tbaa", cl::init(true)); 13801b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman 139c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmannamespace { 140c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// TBAANode - This is a simple wrapper around an MDNode which provides a 141c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// higher-level interface by hiding the details of how alias analysis 142c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// information is encoded in its operands. 143c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman class TBAANode { 144c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman const MDNode *Node; 145c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 146c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman public: 147dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TBAANode() : Node(nullptr) {} 148e6291ae96efa1e27ca6606ac59b17e35d45c057eDan Gohman explicit TBAANode(const MDNode *N) : Node(N) {} 149c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 150c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// getNode - Get the MDNode for this TBAANode. 151c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman const MDNode *getNode() const { return Node; } 152c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 1530b62f95ea81d8954c21a2ae54602be10e5e1bb7eDan Gohman /// getParent - Get this TBAANode's Alias tree parent. 154c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman TBAANode getParent() const { 155c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (Node->getNumOperands() < 2) 156c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return TBAANode(); 157c05d8aa6db088b0f2e2d569d59d87de11cec9c29Dan Gohman MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1)); 158c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!P) 159c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return TBAANode(); 160c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Ok, this node has a valid parent. Return it. 161c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return TBAANode(P); 162c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 163c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 164c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// TypeIsImmutable - Test if this TBAANode represents a type for objects 165c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// which are not modified (by any means) in the context where this 166c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// AliasAnalysis is relevant. 167c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman bool TypeIsImmutable() const { 168c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (Node->getNumOperands() < 3) 169c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return false; 170c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman ConstantInt *CI = dyn_cast<ConstantInt>(Node->getOperand(2)); 171c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!CI) 172c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return false; 173ae92af6771f0a87b380706bc20e69d90bc0c1818Dan Gohman return CI->getValue()[0]; 174c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 175c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman }; 1764df1854f263180fcd04cee3347990afe34749a89Manman Ren 1774df1854f263180fcd04cee3347990afe34749a89Manman Ren /// This is a simple wrapper around an MDNode which provides a 1784df1854f263180fcd04cee3347990afe34749a89Manman Ren /// higher-level interface by hiding the details of how alias analysis 1794df1854f263180fcd04cee3347990afe34749a89Manman Ren /// information is encoded in its operands. 1804df1854f263180fcd04cee3347990afe34749a89Manman Ren class TBAAStructTagNode { 1814df1854f263180fcd04cee3347990afe34749a89Manman Ren /// This node should be created with createTBAAStructTagNode. 1824df1854f263180fcd04cee3347990afe34749a89Manman Ren const MDNode *Node; 1834df1854f263180fcd04cee3347990afe34749a89Manman Ren 1844df1854f263180fcd04cee3347990afe34749a89Manman Ren public: 1854df1854f263180fcd04cee3347990afe34749a89Manman Ren explicit TBAAStructTagNode(const MDNode *N) : Node(N) {} 1864df1854f263180fcd04cee3347990afe34749a89Manman Ren 1874df1854f263180fcd04cee3347990afe34749a89Manman Ren /// Get the MDNode for this TBAAStructTagNode. 1884df1854f263180fcd04cee3347990afe34749a89Manman Ren const MDNode *getNode() const { return Node; } 1894df1854f263180fcd04cee3347990afe34749a89Manman Ren 1904df1854f263180fcd04cee3347990afe34749a89Manman Ren const MDNode *getBaseType() const { 1914df1854f263180fcd04cee3347990afe34749a89Manman Ren return dyn_cast_or_null<MDNode>(Node->getOperand(0)); 1924df1854f263180fcd04cee3347990afe34749a89Manman Ren } 1934df1854f263180fcd04cee3347990afe34749a89Manman Ren const MDNode *getAccessType() const { 1944df1854f263180fcd04cee3347990afe34749a89Manman Ren return dyn_cast_or_null<MDNode>(Node->getOperand(1)); 1954df1854f263180fcd04cee3347990afe34749a89Manman Ren } 1964df1854f263180fcd04cee3347990afe34749a89Manman Ren uint64_t getOffset() const { 1974df1854f263180fcd04cee3347990afe34749a89Manman Ren return cast<ConstantInt>(Node->getOperand(2))->getZExtValue(); 1984df1854f263180fcd04cee3347990afe34749a89Manman Ren } 199a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren /// TypeIsImmutable - Test if this TBAAStructTagNode represents a type for 200a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren /// objects which are not modified (by any means) in the context where this 201a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren /// AliasAnalysis is relevant. 202a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren bool TypeIsImmutable() const { 203a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren if (Node->getNumOperands() < 4) 204a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren return false; 205a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren ConstantInt *CI = dyn_cast<ConstantInt>(Node->getOperand(3)); 206a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren if (!CI) 207a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren return false; 208a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren return CI->getValue()[0]; 209a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren } 2104df1854f263180fcd04cee3347990afe34749a89Manman Ren }; 2114df1854f263180fcd04cee3347990afe34749a89Manman Ren 2124df1854f263180fcd04cee3347990afe34749a89Manman Ren /// This is a simple wrapper around an MDNode which provides a 2134df1854f263180fcd04cee3347990afe34749a89Manman Ren /// higher-level interface by hiding the details of how alias analysis 2144df1854f263180fcd04cee3347990afe34749a89Manman Ren /// information is encoded in its operands. 2154df1854f263180fcd04cee3347990afe34749a89Manman Ren class TBAAStructTypeNode { 2164df1854f263180fcd04cee3347990afe34749a89Manman Ren /// This node should be created with createTBAAStructTypeNode. 2174df1854f263180fcd04cee3347990afe34749a89Manman Ren const MDNode *Node; 2184df1854f263180fcd04cee3347990afe34749a89Manman Ren 2194df1854f263180fcd04cee3347990afe34749a89Manman Ren public: 220dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TBAAStructTypeNode() : Node(nullptr) {} 2214df1854f263180fcd04cee3347990afe34749a89Manman Ren explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {} 2224df1854f263180fcd04cee3347990afe34749a89Manman Ren 2234df1854f263180fcd04cee3347990afe34749a89Manman Ren /// Get the MDNode for this TBAAStructTypeNode. 2244df1854f263180fcd04cee3347990afe34749a89Manman Ren const MDNode *getNode() const { return Node; } 2254df1854f263180fcd04cee3347990afe34749a89Manman Ren 2264df1854f263180fcd04cee3347990afe34749a89Manman Ren /// Get this TBAAStructTypeNode's field in the type DAG with 2274df1854f263180fcd04cee3347990afe34749a89Manman Ren /// given offset. Update the offset to be relative to the field type. 2284df1854f263180fcd04cee3347990afe34749a89Manman Ren TBAAStructTypeNode getParent(uint64_t &Offset) const { 229a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren // Parent can be omitted for the root node. 2304df1854f263180fcd04cee3347990afe34749a89Manman Ren if (Node->getNumOperands() < 2) 2314df1854f263180fcd04cee3347990afe34749a89Manman Ren return TBAAStructTypeNode(); 2324df1854f263180fcd04cee3347990afe34749a89Manman Ren 23311d78777d5ced531823abc0fd111e1c4594dc53eManman Ren // Fast path for a scalar type node and a struct type node with a single 23411d78777d5ced531823abc0fd111e1c4594dc53eManman Ren // field. 235a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren if (Node->getNumOperands() <= 3) { 23611d78777d5ced531823abc0fd111e1c4594dc53eManman Ren uint64_t Cur = Node->getNumOperands() == 2 ? 0 : 23711d78777d5ced531823abc0fd111e1c4594dc53eManman Ren cast<ConstantInt>(Node->getOperand(2))->getZExtValue(); 23811d78777d5ced531823abc0fd111e1c4594dc53eManman Ren Offset -= Cur; 239a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1)); 240a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren if (!P) 241a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren return TBAAStructTypeNode(); 242a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren return TBAAStructTypeNode(P); 243a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren } 244a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren 2454df1854f263180fcd04cee3347990afe34749a89Manman Ren // Assume the offsets are in order. We return the previous field if 2464df1854f263180fcd04cee3347990afe34749a89Manman Ren // the current offset is bigger than the given offset. 2474df1854f263180fcd04cee3347990afe34749a89Manman Ren unsigned TheIdx = 0; 2484df1854f263180fcd04cee3347990afe34749a89Manman Ren for (unsigned Idx = 1; Idx < Node->getNumOperands(); Idx += 2) { 249a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren uint64_t Cur = cast<ConstantInt>(Node->getOperand(Idx + 1))-> 250a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren getZExtValue(); 2514df1854f263180fcd04cee3347990afe34749a89Manman Ren if (Cur > Offset) { 2524df1854f263180fcd04cee3347990afe34749a89Manman Ren assert(Idx >= 3 && 2534df1854f263180fcd04cee3347990afe34749a89Manman Ren "TBAAStructTypeNode::getParent should have an offset match!"); 2544df1854f263180fcd04cee3347990afe34749a89Manman Ren TheIdx = Idx - 2; 2554df1854f263180fcd04cee3347990afe34749a89Manman Ren break; 2564df1854f263180fcd04cee3347990afe34749a89Manman Ren } 2574df1854f263180fcd04cee3347990afe34749a89Manman Ren } 2584df1854f263180fcd04cee3347990afe34749a89Manman Ren // Move along the last field. 2594df1854f263180fcd04cee3347990afe34749a89Manman Ren if (TheIdx == 0) 2604df1854f263180fcd04cee3347990afe34749a89Manman Ren TheIdx = Node->getNumOperands() - 2; 261a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren uint64_t Cur = cast<ConstantInt>(Node->getOperand(TheIdx + 1))-> 2624df1854f263180fcd04cee3347990afe34749a89Manman Ren getZExtValue(); 2634df1854f263180fcd04cee3347990afe34749a89Manman Ren Offset -= Cur; 264a5b314c27a585b979ac9c9da944aa3cec27d22a6Manman Ren MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(TheIdx)); 2654df1854f263180fcd04cee3347990afe34749a89Manman Ren if (!P) 2664df1854f263180fcd04cee3347990afe34749a89Manman Ren return TBAAStructTypeNode(); 2674df1854f263180fcd04cee3347990afe34749a89Manman Ren return TBAAStructTypeNode(P); 2684df1854f263180fcd04cee3347990afe34749a89Manman Ren } 2694df1854f263180fcd04cee3347990afe34749a89Manman Ren }; 270c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 271c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 272c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmannamespace { 273c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// TypeBasedAliasAnalysis - This is a simple alias analysis 274c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// implementation that uses TypeBased to answer queries. 275c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman class TypeBasedAliasAnalysis : public ImmutablePass, 276c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman public AliasAnalysis { 277c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman public: 278c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman static char ID; // Class identification, replacement for typeinfo 279081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson TypeBasedAliasAnalysis() : ImmutablePass(ID) { 280081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeTypeBasedAliasAnalysisPass(*PassRegistry::getPassRegistry()); 281081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 282c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 28336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void initializePass() override { 284633e7023177837537adabf775395ebe7ab51b38fDan Gohman InitializeAliasAnalysis(this); 285633e7023177837537adabf775395ebe7ab51b38fDan Gohman } 286633e7023177837537adabf775395ebe7ab51b38fDan Gohman 287c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// getAdjustedAnalysisPointer - This method is used when a pass implements 288c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// an analysis interface through multiple inheritance. If needed, it 289c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// should override this to adjust the this pointer as needed for the 290c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// specified pass info. 29136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void *getAdjustedAnalysisPointer(const void *PI) override { 29290c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson if (PI == &AliasAnalysis::ID) 293c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return (AliasAnalysis*)this; 294c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return this; 295c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 296c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 297ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman bool Aliases(const MDNode *A, const MDNode *B) const; 2984df1854f263180fcd04cee3347990afe34749a89Manman Ren bool PathAliases(const MDNode *A, const MDNode *B) const; 299ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 300c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman private: 30136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override; 30236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AliasResult alias(const Location &LocA, const Location &LocB) override; 30336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool pointsToConstantMemory(const Location &Loc, bool OrLocal) override; 30436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ModRefBehavior getModRefBehavior(ImmutableCallSite CS) override; 30536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ModRefBehavior getModRefBehavior(const Function *F) override; 30636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ModRefResult getModRefInfo(ImmutableCallSite CS, 30736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const Location &Loc) override; 30836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ModRefResult getModRefInfo(ImmutableCallSite CS1, 30936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ImmutableCallSite CS2) override; 310c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman }; 311c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} // End of anonymous namespace 312c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 313c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// Register this pass... 314c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmanchar TypeBasedAliasAnalysis::ID = 0; 315c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan GohmanINITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa", 316ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Type-Based Alias Analysis", false, true, false) 317c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 318c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan GohmanImmutablePass *llvm::createTypeBasedAliasAnalysisPass() { 319c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return new TypeBasedAliasAnalysis(); 320c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 321c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 322c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmanvoid 323c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan GohmanTypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 324c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman AU.setPreservesAll(); 325c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman AliasAnalysis::getAnalysisUsage(AU); 326c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 327c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 3289e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren/// Check the first operand of the tbaa tag node, if it is a MDNode, we treat 3299e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren/// it as struct-path aware TBAA format, otherwise, we treat it as scalar TBAA 3309e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren/// format. 3319e81c3bdb216e7ca457acf6614591e5b807cf70cManman Renstatic bool isStructPathTBAA(const MDNode *MD) { 332e5f32cf3207da58359a6e3aeeb5b01205645f710Manman Ren // Anonymous TBAA root starts with a MDNode and dragonegg uses it as 333e5f32cf3207da58359a6e3aeeb5b01205645f710Manman Ren // a TBAA tag. 334e5f32cf3207da58359a6e3aeeb5b01205645f710Manman Ren return isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3; 3359e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren} 3369e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren 337ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman/// Aliases - Test whether the type represented by A may alias the 338ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman/// type represented by B. 339ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohmanbool 340ba13864483b696e7f8e2058c3a50b5d901f2213bDan GohmanTypeBasedAliasAnalysis::Aliases(const MDNode *A, 341ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman const MDNode *B) const { 342dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Make sure that both MDNodes are struct-path aware. 343dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (isStructPathTBAA(A) && isStructPathTBAA(B)) 3444df1854f263180fcd04cee3347990afe34749a89Manman Ren return PathAliases(A, B); 3454df1854f263180fcd04cee3347990afe34749a89Manman Ren 346c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Keep track of the root node for A and B. 347c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman TBAANode RootA, RootB; 348c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 3490b62f95ea81d8954c21a2ae54602be10e5e1bb7eDan Gohman // Climb the tree from A to see if we reach B. 350ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman for (TBAANode T(A); ; ) { 351ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (T.getNode() == B) 352c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // B is an ancestor of A. 353ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return true; 354c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 355c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman RootA = T; 356c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman T = T.getParent(); 357c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!T.getNode()) 358c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman break; 359c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 360c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 3610b62f95ea81d8954c21a2ae54602be10e5e1bb7eDan Gohman // Climb the tree from B to see if we reach A. 362ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman for (TBAANode T(B); ; ) { 363ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (T.getNode() == A) 364c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // A is an ancestor of B. 365ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return true; 366c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 367c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman RootB = T; 368c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman T = T.getParent(); 369c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!T.getNode()) 370c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman break; 371c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 372c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 373c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Neither node is an ancestor of the other. 374c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 375c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // If they have different roots, they're part of different potentially 376c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // unrelated type systems, so we must be conservative. 3774df1854f263180fcd04cee3347990afe34749a89Manman Ren if (RootA.getNode() != RootB.getNode()) 3784df1854f263180fcd04cee3347990afe34749a89Manman Ren return true; 3794df1854f263180fcd04cee3347990afe34749a89Manman Ren 3804df1854f263180fcd04cee3347990afe34749a89Manman Ren // If they have the same root, then we've proved there's no alias. 3814df1854f263180fcd04cee3347990afe34749a89Manman Ren return false; 3824df1854f263180fcd04cee3347990afe34749a89Manman Ren} 3834df1854f263180fcd04cee3347990afe34749a89Manman Ren 3844df1854f263180fcd04cee3347990afe34749a89Manman Ren/// Test whether the struct-path tag represented by A may alias the 3854df1854f263180fcd04cee3347990afe34749a89Manman Ren/// struct-path tag represented by B. 3864df1854f263180fcd04cee3347990afe34749a89Manman Renbool 3874df1854f263180fcd04cee3347990afe34749a89Manman RenTypeBasedAliasAnalysis::PathAliases(const MDNode *A, 3884df1854f263180fcd04cee3347990afe34749a89Manman Ren const MDNode *B) const { 389dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Verify that both input nodes are struct-path aware. 390dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(isStructPathTBAA(A) && "MDNode A is not struct-path aware."); 391dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(isStructPathTBAA(B) && "MDNode B is not struct-path aware."); 392dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 3934df1854f263180fcd04cee3347990afe34749a89Manman Ren // Keep track of the root node for A and B. 3944df1854f263180fcd04cee3347990afe34749a89Manman Ren TBAAStructTypeNode RootA, RootB; 3954df1854f263180fcd04cee3347990afe34749a89Manman Ren TBAAStructTagNode TagA(A), TagB(B); 3964df1854f263180fcd04cee3347990afe34749a89Manman Ren 3974df1854f263180fcd04cee3347990afe34749a89Manman Ren // TODO: We need to check if AccessType of TagA encloses AccessType of 3984df1854f263180fcd04cee3347990afe34749a89Manman Ren // TagB to support aggregate AccessType. If yes, return true. 3994df1854f263180fcd04cee3347990afe34749a89Manman Ren 4004df1854f263180fcd04cee3347990afe34749a89Manman Ren // Start from the base type of A, follow the edge with the correct offset in 4014df1854f263180fcd04cee3347990afe34749a89Manman Ren // the type DAG and adjust the offset until we reach the base type of B or 4024df1854f263180fcd04cee3347990afe34749a89Manman Ren // until we reach the Root node. 4034df1854f263180fcd04cee3347990afe34749a89Manman Ren // Compare the adjusted offset once we have the same base. 4044df1854f263180fcd04cee3347990afe34749a89Manman Ren 4054df1854f263180fcd04cee3347990afe34749a89Manman Ren // Climb the type DAG from base type of A to see if we reach base type of B. 4064df1854f263180fcd04cee3347990afe34749a89Manman Ren const MDNode *BaseA = TagA.getBaseType(); 4074df1854f263180fcd04cee3347990afe34749a89Manman Ren const MDNode *BaseB = TagB.getBaseType(); 4084df1854f263180fcd04cee3347990afe34749a89Manman Ren uint64_t OffsetA = TagA.getOffset(), OffsetB = TagB.getOffset(); 4094df1854f263180fcd04cee3347990afe34749a89Manman Ren for (TBAAStructTypeNode T(BaseA); ; ) { 4104df1854f263180fcd04cee3347990afe34749a89Manman Ren if (T.getNode() == BaseB) 4114df1854f263180fcd04cee3347990afe34749a89Manman Ren // Base type of A encloses base type of B, check if the offsets match. 4124df1854f263180fcd04cee3347990afe34749a89Manman Ren return OffsetA == OffsetB; 4134df1854f263180fcd04cee3347990afe34749a89Manman Ren 4144df1854f263180fcd04cee3347990afe34749a89Manman Ren RootA = T; 4154df1854f263180fcd04cee3347990afe34749a89Manman Ren // Follow the edge with the correct offset, OffsetA will be adjusted to 4164df1854f263180fcd04cee3347990afe34749a89Manman Ren // be relative to the field type. 4174df1854f263180fcd04cee3347990afe34749a89Manman Ren T = T.getParent(OffsetA); 4184df1854f263180fcd04cee3347990afe34749a89Manman Ren if (!T.getNode()) 4194df1854f263180fcd04cee3347990afe34749a89Manman Ren break; 4204df1854f263180fcd04cee3347990afe34749a89Manman Ren } 4214df1854f263180fcd04cee3347990afe34749a89Manman Ren 4224df1854f263180fcd04cee3347990afe34749a89Manman Ren // Reset OffsetA and climb the type DAG from base type of B to see if we reach 4234df1854f263180fcd04cee3347990afe34749a89Manman Ren // base type of A. 4244df1854f263180fcd04cee3347990afe34749a89Manman Ren OffsetA = TagA.getOffset(); 4254df1854f263180fcd04cee3347990afe34749a89Manman Ren for (TBAAStructTypeNode T(BaseB); ; ) { 4264df1854f263180fcd04cee3347990afe34749a89Manman Ren if (T.getNode() == BaseA) 4274df1854f263180fcd04cee3347990afe34749a89Manman Ren // Base type of B encloses base type of A, check if the offsets match. 4284df1854f263180fcd04cee3347990afe34749a89Manman Ren return OffsetA == OffsetB; 4294df1854f263180fcd04cee3347990afe34749a89Manman Ren 4304df1854f263180fcd04cee3347990afe34749a89Manman Ren RootB = T; 4314df1854f263180fcd04cee3347990afe34749a89Manman Ren // Follow the edge with the correct offset, OffsetB will be adjusted to 4324df1854f263180fcd04cee3347990afe34749a89Manman Ren // be relative to the field type. 4334df1854f263180fcd04cee3347990afe34749a89Manman Ren T = T.getParent(OffsetB); 4344df1854f263180fcd04cee3347990afe34749a89Manman Ren if (!T.getNode()) 4354df1854f263180fcd04cee3347990afe34749a89Manman Ren break; 4364df1854f263180fcd04cee3347990afe34749a89Manman Ren } 4374df1854f263180fcd04cee3347990afe34749a89Manman Ren 4384df1854f263180fcd04cee3347990afe34749a89Manman Ren // Neither node is an ancestor of the other. 4394df1854f263180fcd04cee3347990afe34749a89Manman Ren 4404df1854f263180fcd04cee3347990afe34749a89Manman Ren // If they have different roots, they're part of different potentially 4414df1854f263180fcd04cee3347990afe34749a89Manman Ren // unrelated type systems, so we must be conservative. 442ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (RootA.getNode() != RootB.getNode()) 443ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return true; 444ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 445ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // If they have the same root, then we've proved there's no alias. 446ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return false; 447ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman} 448ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 449ba13864483b696e7f8e2058c3a50b5d901f2213bDan GohmanAliasAnalysis::AliasResult 450ba13864483b696e7f8e2058c3a50b5d901f2213bDan GohmanTypeBasedAliasAnalysis::alias(const Location &LocA, 451ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman const Location &LocB) { 452ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (!EnableTBAA) 453ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return AliasAnalysis::alias(LocA, LocB); 454ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 455ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must 456ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // be conservative. 457ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman const MDNode *AM = LocA.TBAATag; 458ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (!AM) return AliasAnalysis::alias(LocA, LocB); 459ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman const MDNode *BM = LocB.TBAATag; 460ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (!BM) return AliasAnalysis::alias(LocA, LocB); 461ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 462ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // If they may alias, chain to the next AliasAnalysis. 463ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman if (Aliases(AM, BM)) 464ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return AliasAnalysis::alias(LocA, LocB); 465ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman 466ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman // Otherwise return a definitive result. 467ba13864483b696e7f8e2058c3a50b5d901f2213bDan Gohman return NoAlias; 468c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 469c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 470a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohmanbool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc, 471a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman bool OrLocal) { 47201b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman if (!EnableTBAA) 473a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 47401b58f637c23e203dd95a4709bdd40cdfc31ffa9Dan Gohman 475e6291ae96efa1e27ca6606ac59b17e35d45c057eDan Gohman const MDNode *M = Loc.TBAATag; 476a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman if (!M) return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 477c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 478c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // If this is an "immutable" type, we can assume the pointer is pointing 479c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // to constant memory. 4809e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren if ((!isStructPathTBAA(M) && TBAANode(M).TypeIsImmutable()) || 4819e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren (isStructPathTBAA(M) && TBAAStructTagNode(M).TypeIsImmutable())) 482acf50f5136c6f1daca2e78db756514a88470516bDan Gohman return true; 483acf50f5136c6f1daca2e78db756514a88470516bDan Gohman 484a25e5dbcc2371352386a01e3c1b8e76dd890272bDan Gohman return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 485c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 48687c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 487a8598bec287108d0359880d33955759dc90cd5a1Dan GohmanAliasAnalysis::ModRefBehavior 488a8598bec287108d0359880d33955759dc90cd5a1Dan GohmanTypeBasedAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 489a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman if (!EnableTBAA) 490a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman return AliasAnalysis::getModRefBehavior(CS); 491a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman 492a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman ModRefBehavior Min = UnknownModRefBehavior; 493a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman 494a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman // If this is an "immutable" type, we can assume the call doesn't write 495a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman // to memory. 496a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman if (const MDNode *M = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 4979e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren if ((!isStructPathTBAA(M) && TBAANode(M).TypeIsImmutable()) || 4989e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren (isStructPathTBAA(M) && TBAAStructTagNode(M).TypeIsImmutable())) 499a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman Min = OnlyReadsMemory; 500a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman 50142c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); 502a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman} 503a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman 504a8598bec287108d0359880d33955759dc90cd5a1Dan GohmanAliasAnalysis::ModRefBehavior 505a8598bec287108d0359880d33955759dc90cd5a1Dan GohmanTypeBasedAliasAnalysis::getModRefBehavior(const Function *F) { 50642c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman // Functions don't have metadata. Just chain to the next implementation. 507a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman return AliasAnalysis::getModRefBehavior(F); 508a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman} 509a8598bec287108d0359880d33955759dc90cd5a1Dan Gohman 51087c5c2f069fe18df5a372e6eb7bbca3be4d09facDan GohmanAliasAnalysis::ModRefResult 51187c5c2f069fe18df5a372e6eb7bbca3be4d09facDan GohmanTypeBasedAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 51287c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman const Location &Loc) { 51387c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (!EnableTBAA) 51487c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return AliasAnalysis::getModRefInfo(CS, Loc); 51587c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 51687c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (const MDNode *L = Loc.TBAATag) 51787c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (const MDNode *M = 51887c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 51987c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (!Aliases(L, M)) 52087c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return NoModRef; 52187c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 52287c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return AliasAnalysis::getModRefInfo(CS, Loc); 52387c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman} 52487c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 52587c5c2f069fe18df5a372e6eb7bbca3be4d09facDan GohmanAliasAnalysis::ModRefResult 52687c5c2f069fe18df5a372e6eb7bbca3be4d09facDan GohmanTypeBasedAliasAnalysis::getModRefInfo(ImmutableCallSite CS1, 52787c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman ImmutableCallSite CS2) { 52887c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (!EnableTBAA) 52987c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return AliasAnalysis::getModRefInfo(CS1, CS2); 53087c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 53187c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (const MDNode *M1 = 53287c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman CS1.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 53387c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (const MDNode *M2 = 53487c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman CS2.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) 53587c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman if (!Aliases(M1, M2)) 53687c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return NoModRef; 53787c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman 53887c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman return AliasAnalysis::getModRefInfo(CS1, CS2); 53987c5c2f069fe18df5a372e6eb7bbca3be4d09facDan Gohman} 5402ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren 5410b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Renbool MDNode::isTBAAVtableAccess() const { 5429e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren if (!isStructPathTBAA(this)) { 5430b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Ren if (getNumOperands() < 1) return false; 5440b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Ren if (MDString *Tag1 = dyn_cast<MDString>(getOperand(0))) { 5450b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Ren if (Tag1->getString() == "vtable pointer") return true; 5460b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Ren } 5470b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Ren return false; 5480b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Ren } 5490b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Ren 5500b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Ren // For struct-path aware TBAA, we use the access type of the tag. 5510b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Ren if (getNumOperands() < 2) return false; 5520b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Ren MDNode *Tag = cast_or_null<MDNode>(getOperand(1)); 5530b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Ren if (!Tag) return false; 5540b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Ren if (MDString *Tag1 = dyn_cast<MDString>(Tag->getOperand(0))) { 5550b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Ren if (Tag1->getString() == "vtable pointer") return true; 5560b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Ren } 5570b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Ren return false; 5580b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Ren} 5590b3d39235aaed8bc66ccffb3942bf7b5f185329cManman Ren 5602ff97832e593926ea8dbdd5fc5bcf367475638a9Manman RenMDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) { 5612ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren if (!A || !B) 562dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 5632ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren 5642ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren if (A == B) 5652ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren return A; 5662ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren 5672ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren // For struct-path aware TBAA, we use the access type of the tag. 568dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool StructPath = isStructPathTBAA(A) && isStructPathTBAA(B); 5699e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren if (StructPath) { 5702ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren A = cast_or_null<MDNode>(A->getOperand(1)); 571dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!A) return nullptr; 5722ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren B = cast_or_null<MDNode>(B->getOperand(1)); 573dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!B) return nullptr; 5742ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren } 5752ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren 5762ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren SmallVector<MDNode *, 4> PathA; 5772ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren MDNode *T = A; 5782ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren while (T) { 5792ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren PathA.push_back(T); 580dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines T = T->getNumOperands() >= 2 ? cast_or_null<MDNode>(T->getOperand(1)) 581dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : nullptr; 5822ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren } 5832ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren 5842ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren SmallVector<MDNode *, 4> PathB; 5852ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren T = B; 5862ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren while (T) { 5872ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren PathB.push_back(T); 588dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines T = T->getNumOperands() >= 2 ? cast_or_null<MDNode>(T->getOperand(1)) 589dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : nullptr; 5902ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren } 5912ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren 5922ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren int IA = PathA.size() - 1; 5932ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren int IB = PathB.size() - 1; 5942ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren 595dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MDNode *Ret = nullptr; 5962ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren while (IA >= 0 && IB >=0) { 5972ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren if (PathA[IA] == PathB[IB]) 5982ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren Ret = PathA[IA]; 5992ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren else 6002ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren break; 6012ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren --IA; 6022ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren --IB; 6032ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren } 6049e81c3bdb216e7ca457acf6614591e5b807cf70cManman Ren if (!StructPath) 6052ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren return Ret; 6062ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren 6072ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren if (!Ret) 608dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 6092ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren // We need to convert from a type node to a tag node. 6102ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren Type *Int64 = IntegerType::get(A->getContext(), 64); 6112ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren Value *Ops[3] = { Ret, Ret, ConstantInt::get(Int64, 0) }; 6122ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren return MDNode::get(A->getContext(), Ops); 6132ff97832e593926ea8dbdd5fc5bcf367475638a9Manman Ren} 614