TypeBasedAliasAnalysis.cpp revision acf50f5136c6f1daca2e78db756514a88470516b
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 15c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// a type system of a higher level language. 16c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 17c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// This pass is language-independent. The type system is encoded in 18c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// metadata. This allows this pass to support typical C and C++ TBAA, but 19c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// it can also support custom aliasing behavior for other languages. 20c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 21c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// This is a work-in-progress. It doesn't work yet, and the metadata 22c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// format isn't stable. 23c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 24c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// TODO: getModRefBehavior. The AliasAnalysis infrastructure will need to 25c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// be extended. 26c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// TODO: struct fields 27c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// 28c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman//===----------------------------------------------------------------------===// 29c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 30c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Analysis/AliasAnalysis.h" 31c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Analysis/Passes.h" 32c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Module.h" 33c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Metadata.h" 34c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman#include "llvm/Pass.h" 35c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmanusing namespace llvm; 36c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 37c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmannamespace { 38c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// TBAANode - This is a simple wrapper around an MDNode which provides a 39c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// higher-level interface by hiding the details of how alias analysis 40c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// information is encoded in its operands. 41c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman class TBAANode { 42c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman const MDNode *Node; 43c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 44c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman public: 45c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman TBAANode() : Node(0) {} 46e6291ae96efa1e27ca6606ac59b17e35d45c057eDan Gohman explicit TBAANode(const MDNode *N) : Node(N) {} 47c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 48c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// getNode - Get the MDNode for this TBAANode. 49c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman const MDNode *getNode() const { return Node; } 50c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 51c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// getParent - Get this TBAANode's Alias DAG parent. 52c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman TBAANode getParent() const { 53c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (Node->getNumOperands() < 2) 54c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return TBAANode(); 55c05d8aa6db088b0f2e2d569d59d87de11cec9c29Dan Gohman MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1)); 56c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!P) 57c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return TBAANode(); 58c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Ok, this node has a valid parent. Return it. 59c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return TBAANode(P); 60c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 61c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 62c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// TypeIsImmutable - Test if this TBAANode represents a type for objects 63c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// which are not modified (by any means) in the context where this 64c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// AliasAnalysis is relevant. 65c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman bool TypeIsImmutable() const { 66c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (Node->getNumOperands() < 3) 67c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return false; 68c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman ConstantInt *CI = dyn_cast<ConstantInt>(Node->getOperand(2)); 69c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!CI) 70c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return false; 71c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // TODO: Think about the encoding. 72c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return CI->isOne(); 73c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 74c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman }; 75c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 76c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 77c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmannamespace { 78c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// TypeBasedAliasAnalysis - This is a simple alias analysis 79c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// implementation that uses TypeBased to answer queries. 80c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman class TypeBasedAliasAnalysis : public ImmutablePass, 81c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman public AliasAnalysis { 82c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman public: 83c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman static char ID; // Class identification, replacement for typeinfo 8490c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson TypeBasedAliasAnalysis() : ImmutablePass(ID) {} 85c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 86633e7023177837537adabf775395ebe7ab51b38fDan Gohman virtual void initializePass() { 87633e7023177837537adabf775395ebe7ab51b38fDan Gohman InitializeAliasAnalysis(this); 88633e7023177837537adabf775395ebe7ab51b38fDan Gohman } 89633e7023177837537adabf775395ebe7ab51b38fDan Gohman 90c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// getAdjustedAnalysisPointer - This method is used when a pass implements 91c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// an analysis interface through multiple inheritance. If needed, it 92c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// should override this to adjust the this pointer as needed for the 93c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman /// specified pass info. 9490c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson virtual void *getAdjustedAnalysisPointer(const void *PI) { 9590c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson if (PI == &AliasAnalysis::ID) 96c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return (AliasAnalysis*)this; 97c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return this; 98c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 99c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 100c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman private: 101c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman virtual void getAnalysisUsage(AnalysisUsage &AU) const; 102b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman virtual AliasResult alias(const Location &LocA, const Location &LocB); 103b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman virtual bool pointsToConstantMemory(const Location &Loc); 104c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman }; 105c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} // End of anonymous namespace 106c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 107c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman// Register this pass... 108c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmanchar TypeBasedAliasAnalysis::ID = 0; 109c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan GohmanINITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa", 110ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Type-Based Alias Analysis", false, true, false) 111c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 112c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan GohmanImmutablePass *llvm::createTypeBasedAliasAnalysisPass() { 113c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return new TypeBasedAliasAnalysis(); 114c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 115c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 116c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohmanvoid 117c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan GohmanTypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 118c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman AU.setPreservesAll(); 119c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman AliasAnalysis::getAnalysisUsage(AU); 120c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 121c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 122c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan GohmanAliasAnalysis::AliasResult 123b2143b6247901ae4eca2192ee134564c4f5f7853Dan GohmanTypeBasedAliasAnalysis::alias(const Location &LocA, 124b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &LocB) { 125c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must 126c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // be conservative. 127e6291ae96efa1e27ca6606ac59b17e35d45c057eDan Gohman const MDNode *AM = LocA.TBAATag; 128633e7023177837537adabf775395ebe7ab51b38fDan Gohman if (!AM) return AliasAnalysis::alias(LocA, LocB); 129e6291ae96efa1e27ca6606ac59b17e35d45c057eDan Gohman const MDNode *BM = LocB.TBAATag; 130633e7023177837537adabf775395ebe7ab51b38fDan Gohman if (!BM) return AliasAnalysis::alias(LocA, LocB); 131c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 132c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Keep track of the root node for A and B. 133c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman TBAANode RootA, RootB; 134c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 135c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Climb the DAG from A to see if we reach B. 136c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman for (TBAANode T(AM); ; ) { 137c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (T.getNode() == BM) 138c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // B is an ancestor of A. 139633e7023177837537adabf775395ebe7ab51b38fDan Gohman return AliasAnalysis::alias(LocA, LocB); 140c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 141c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman RootA = T; 142c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman T = T.getParent(); 143c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!T.getNode()) 144c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman break; 145c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 146c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 147c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Climb the DAG from B to see if we reach A. 148c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman for (TBAANode T(BM); ; ) { 149c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (T.getNode() == AM) 150c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // A is an ancestor of B. 151633e7023177837537adabf775395ebe7ab51b38fDan Gohman return AliasAnalysis::alias(LocA, LocB); 152c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 153c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman RootB = T; 154c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman T = T.getParent(); 155c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!T.getNode()) 156c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman break; 157c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman } 158c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 159c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // Neither node is an ancestor of the other. 160c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 161c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // If they have the same root, then we've proved there's no alias. 162c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (RootA.getNode() == RootB.getNode()) 163c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman return NoAlias; 164c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 165c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // If they have different roots, they're part of different potentially 166c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // unrelated type systems, so we must be conservative. 167633e7023177837537adabf775395ebe7ab51b38fDan Gohman return AliasAnalysis::alias(LocA, LocB); 168c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 169c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 170b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohmanbool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc) { 171e6291ae96efa1e27ca6606ac59b17e35d45c057eDan Gohman const MDNode *M = Loc.TBAATag; 172c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman if (!M) return false; 173c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman 174c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // If this is an "immutable" type, we can assume the pointer is pointing 175c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman // to constant memory. 176acf50f5136c6f1daca2e78db756514a88470516bDan Gohman if (TBAANode(M).TypeIsImmutable()) 177acf50f5136c6f1daca2e78db756514a88470516bDan Gohman return true; 178acf50f5136c6f1daca2e78db756514a88470516bDan Gohman 179acf50f5136c6f1daca2e78db756514a88470516bDan Gohman return AliasAnalysis::pointsToConstantMemory(Loc); 180c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5Dan Gohman} 181