1 //===- TypeBasedAliasAnalysis.cpp - Type-Based Alias Analysis -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the TypeBasedAliasAnalysis pass, which implements
11 // metadata-based TBAA.
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.
17 // This pass is language-independent. The type system is encoded in
18 // metadata. This allows this pass to support typical C and C++ TBAA, but
19 // it can also support custom aliasing behavior for other languages.
21 // This is a work-in-progress. It doesn't work yet, and the metadata
22 // format isn't stable.
24 // TODO: getModRefBehavior. The AliasAnalysis infrastructure will need to
27 // TODO: struct fields
29 //===----------------------------------------------------------------------===//
31 #include "llvm/Analysis/AliasAnalysis.h"
32 #include "llvm/Analysis/Passes.h"
33 #include "llvm/Module.h"
34 #include "llvm/Metadata.h"
35 #include "llvm/Pass.h"
39 /// TBAANode - This is a simple wrapper around an MDNode which provides a
40 /// higher-level interface by hiding the details of how alias analysis
41 /// information is encoded in its operands.
46 TBAANode() : Node(0) {}
47 explicit TBAANode(MDNode *N) : Node(N) {}
49 /// getNode - Get the MDNode for this TBAANode.
50 const MDNode *getNode() const { return Node; }
52 /// getParent - Get this TBAANode's Alias DAG parent.
53 TBAANode getParent() const {
54 if (Node->getNumOperands() < 2)
56 MDNode *P = dyn_cast<MDNode>(Node->getOperand(1));
59 // Ok, this node has a valid parent. Return it.
63 /// TypeIsImmutable - Test if this TBAANode represents a type for objects
64 /// which are not modified (by any means) in the context where this
65 /// AliasAnalysis is relevant.
66 bool TypeIsImmutable() const {
67 if (Node->getNumOperands() < 3)
69 ConstantInt *CI = dyn_cast<ConstantInt>(Node->getOperand(2));
72 // TODO: Think about the encoding.
79 /// TypeBasedAliasAnalysis - This is a simple alias analysis
80 /// implementation that uses TypeBased to answer queries.
81 class TypeBasedAliasAnalysis : public ImmutablePass,
82 public AliasAnalysis {
84 static char ID; // Class identification, replacement for typeinfo
85 TypeBasedAliasAnalysis() : ImmutablePass(&ID) {}
87 /// getAdjustedAnalysisPointer - This method is used when a pass implements
88 /// an analysis interface through multiple inheritance. If needed, it
89 /// should override this to adjust the this pointer as needed for the
90 /// specified pass info.
91 virtual void *getAdjustedAnalysisPointer(const PassInfo *PI) {
92 if (PI->isPassID(&AliasAnalysis::ID))
93 return (AliasAnalysis*)this;
98 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
99 virtual AliasResult alias(const Value *V1, unsigned V1Size,
100 const Value *V2, unsigned V2Size);
101 virtual bool pointsToConstantMemory(const Value *P);
103 } // End of anonymous namespace
105 // Register this pass...
106 char TypeBasedAliasAnalysis::ID = 0;
107 INITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa",
108 "Type-Based Alias Analysis", false, true, false);
110 ImmutablePass *llvm::createTypeBasedAliasAnalysisPass() {
111 return new TypeBasedAliasAnalysis();
115 TypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
116 AU.setPreservesAll();
117 AliasAnalysis::getAnalysisUsage(AU);
120 AliasAnalysis::AliasResult
121 TypeBasedAliasAnalysis::alias(const Value *A, unsigned ASize,
122 const Value *B, unsigned BSize) {
123 // Currently, metadata can only be attached to Instructions.
124 const Instruction *AI = dyn_cast<Instruction>(A);
125 if (!AI) return MayAlias;
126 const Instruction *BI = dyn_cast<Instruction>(B);
127 if (!BI) return MayAlias;
129 // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must
132 AI->getMetadata(AI->getParent()->getParent()->getParent()
133 ->getMDKindID("tbaa"));
134 if (!AM) return MayAlias;
136 BI->getMetadata(BI->getParent()->getParent()->getParent()
137 ->getMDKindID("tbaa"));
138 if (!BM) return MayAlias;
140 // Keep track of the root node for A and B.
141 TBAANode RootA, RootB;
143 // Climb the DAG from A to see if we reach B.
144 for (TBAANode T(AM); ; ) {
145 if (T.getNode() == BM)
146 // B is an ancestor of A.
155 // Climb the DAG from B to see if we reach A.
156 for (TBAANode T(BM); ; ) {
157 if (T.getNode() == AM)
158 // A is an ancestor of B.
167 // Neither node is an ancestor of the other.
169 // If they have the same root, then we've proved there's no alias.
170 if (RootA.getNode() == RootB.getNode())
173 // If they have different roots, they're part of different potentially
174 // unrelated type systems, so we must be conservative.
178 bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Value *P) {
179 // Currently, metadata can only be attached to Instructions.
180 const Instruction *I = dyn_cast<Instruction>(P);
181 if (!I) return false;
184 I->getMetadata(I->getParent()->getParent()->getParent()
185 ->getMDKindID("tbaa"));
186 if (!M) return false;
188 // If this is an "immutable" type, we can assume the pointer is pointing
189 // to constant memory.
190 return TBAANode(M).TypeIsImmutable();