TypeBasedAliasAnalysis.cpp revision ee135131b16390177c09c1620e322bcf38a78e0a
1//===- TypeBasedAliasAnalysis.cpp - Type-Based Alias Analysis -------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the TypeBasedAliasAnalysis pass, which implements 11// metadata-based TBAA. 12// 13// In LLVM IR, memory does not have types, so LLVM's own type system is not 14// suitable for doing TBAA. Instead, metadata is added to the IR to describe 15// a type system of a higher level language. This can be used to implement 16// typical C/C++ TBAA, but it can also be used to implement custom alias 17// analysis behavior for other languages. 18// 19// The current metadata format is very simple. TBAA MDNodes have up to 20// three fields, e.g.: 21// !0 = metadata !{ metadata !"an example type tree" } 22// !1 = metadata !{ metadata !"int", metadata !0 } 23// !2 = metadata !{ metadata !"float", metadata !0 } 24// !3 = metadata !{ metadata !"const float", metadata !2, i64 1 } 25// 26// The first field is an identity field. It can be any value, usually 27// an MDString, which uniquely identifies the type. The most important 28// name in the tree is the name of the root node. Two trees with 29// different root node names are entirely disjoint, even if they 30// have leaves with common names. 31// 32// The second field identifies the type's parent node in the tree, or 33// is null or omitted for a root node. A type is considered to alias 34// all of its decendents and all of its ancestors in the tree. 35// 36// If the third field is present, it's an integer which if equal to 1 37// indicates that the type is "constant" (meaning pointsToConstantMemory 38// should return true; see 39// http://llvm.org/docs/AliasAnalysis.html#OtherItfs). 40// 41// TODO: The current metadata format doesn't support struct 42// fields. For example: 43// struct X { 44// double d; 45// int i; 46// }; 47// void foo(struct X *x, struct X *y, double *p) { 48// *x = *y; 49// *p = 0.0; 50// } 51// Struct X has a double member, so the store to *x can alias the store to *p. 52// Currently it's not possible to precisely describe all the things struct X 53// aliases, so struct assignments must use conservative TBAA nodes. There's 54// no scheme for attaching metadata to @llvm.memcpy yet either. 55// 56//===----------------------------------------------------------------------===// 57 58#include "llvm/Analysis/AliasAnalysis.h" 59#include "llvm/Analysis/Passes.h" 60#include "llvm/Module.h" 61#include "llvm/Metadata.h" 62#include "llvm/Pass.h" 63#include "llvm/Support/CommandLine.h" 64using namespace llvm; 65 66// For testing purposes, enable TBAA only via a special option. 67static cl::opt<bool> EnableTBAA("enable-tbaa"); 68 69namespace { 70 /// TBAANode - This is a simple wrapper around an MDNode which provides a 71 /// higher-level interface by hiding the details of how alias analysis 72 /// information is encoded in its operands. 73 class TBAANode { 74 const MDNode *Node; 75 76 public: 77 TBAANode() : Node(0) {} 78 explicit TBAANode(const MDNode *N) : Node(N) {} 79 80 /// getNode - Get the MDNode for this TBAANode. 81 const MDNode *getNode() const { return Node; } 82 83 /// getParent - Get this TBAANode's Alias tree parent. 84 TBAANode getParent() const { 85 if (Node->getNumOperands() < 2) 86 return TBAANode(); 87 MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1)); 88 if (!P) 89 return TBAANode(); 90 // Ok, this node has a valid parent. Return it. 91 return TBAANode(P); 92 } 93 94 /// TypeIsImmutable - Test if this TBAANode represents a type for objects 95 /// which are not modified (by any means) in the context where this 96 /// AliasAnalysis is relevant. 97 bool TypeIsImmutable() const { 98 if (Node->getNumOperands() < 3) 99 return false; 100 ConstantInt *CI = dyn_cast<ConstantInt>(Node->getOperand(2)); 101 if (!CI) 102 return false; 103 // TODO: Think about the encoding. 104 return CI->isOne(); 105 } 106 }; 107} 108 109namespace { 110 /// TypeBasedAliasAnalysis - This is a simple alias analysis 111 /// implementation that uses TypeBased to answer queries. 112 class TypeBasedAliasAnalysis : public ImmutablePass, 113 public AliasAnalysis { 114 public: 115 static char ID; // Class identification, replacement for typeinfo 116 TypeBasedAliasAnalysis() : ImmutablePass(ID) { 117 initializeTypeBasedAliasAnalysisPass(*PassRegistry::getPassRegistry()); 118 } 119 120 virtual void initializePass() { 121 InitializeAliasAnalysis(this); 122 } 123 124 /// getAdjustedAnalysisPointer - This method is used when a pass implements 125 /// an analysis interface through multiple inheritance. If needed, it 126 /// should override this to adjust the this pointer as needed for the 127 /// specified pass info. 128 virtual void *getAdjustedAnalysisPointer(const void *PI) { 129 if (PI == &AliasAnalysis::ID) 130 return (AliasAnalysis*)this; 131 return this; 132 } 133 134 bool Aliases(const MDNode *A, const MDNode *B) const; 135 136 private: 137 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 138 virtual AliasResult alias(const Location &LocA, const Location &LocB); 139 virtual bool pointsToConstantMemory(const Location &Loc); 140 }; 141} // End of anonymous namespace 142 143// Register this pass... 144char TypeBasedAliasAnalysis::ID = 0; 145INITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa", 146 "Type-Based Alias Analysis", false, true, false) 147 148ImmutablePass *llvm::createTypeBasedAliasAnalysisPass() { 149 return new TypeBasedAliasAnalysis(); 150} 151 152void 153TypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 154 AU.setPreservesAll(); 155 AliasAnalysis::getAnalysisUsage(AU); 156} 157 158/// Aliases - Test whether the type represented by A may alias the 159/// type represented by B. 160bool 161TypeBasedAliasAnalysis::Aliases(const MDNode *A, 162 const MDNode *B) const { 163 // Keep track of the root node for A and B. 164 TBAANode RootA, RootB; 165 166 // Climb the tree from A to see if we reach B. 167 for (TBAANode T(A); ; ) { 168 if (T.getNode() == B) 169 // B is an ancestor of A. 170 return true; 171 172 RootA = T; 173 T = T.getParent(); 174 if (!T.getNode()) 175 break; 176 } 177 178 // Climb the tree from B to see if we reach A. 179 for (TBAANode T(B); ; ) { 180 if (T.getNode() == A) 181 // A is an ancestor of B. 182 return true; 183 184 RootB = T; 185 T = T.getParent(); 186 if (!T.getNode()) 187 break; 188 } 189 190 // Neither node is an ancestor of the other. 191 192 // If they have different roots, they're part of different potentially 193 // unrelated type systems, so we must be conservative. 194 if (RootA.getNode() != RootB.getNode()) 195 return true; 196 197 // If they have the same root, then we've proved there's no alias. 198 return false; 199} 200 201AliasAnalysis::AliasResult 202TypeBasedAliasAnalysis::alias(const Location &LocA, 203 const Location &LocB) { 204 if (!EnableTBAA) 205 return AliasAnalysis::alias(LocA, LocB); 206 207 // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must 208 // be conservative. 209 const MDNode *AM = LocA.TBAATag; 210 if (!AM) return AliasAnalysis::alias(LocA, LocB); 211 const MDNode *BM = LocB.TBAATag; 212 if (!BM) return AliasAnalysis::alias(LocA, LocB); 213 214 // If they may alias, chain to the next AliasAnalysis. 215 if (Aliases(AM, BM)) 216 return AliasAnalysis::alias(LocA, LocB); 217 218 // Otherwise return a definitive result. 219 return NoAlias; 220} 221 222bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc) { 223 if (!EnableTBAA) 224 return AliasAnalysis::pointsToConstantMemory(Loc); 225 226 const MDNode *M = Loc.TBAATag; 227 if (!M) return false; 228 229 // If this is an "immutable" type, we can assume the pointer is pointing 230 // to constant memory. 231 if (TBAANode(M).TypeIsImmutable()) 232 return true; 233 234 return AliasAnalysis::pointsToConstantMemory(Loc); 235} 236