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
26 // TODO: struct fields
28 //===----------------------------------------------------------------------===//
30 #include "llvm/Analysis/AliasAnalysis.h"
31 #include "llvm/Analysis/Passes.h"
32 #include "llvm/Module.h"
33 #include "llvm/Metadata.h"
34 #include "llvm/Pass.h"
35 #include "llvm/Support/CommandLine.h"
38 // For testing purposes, enable TBAA only via a special option.
39 static cl::opt<bool> EnableTBAA("enable-tbaa");
42 /// TBAANode - This is a simple wrapper around an MDNode which provides a
43 /// higher-level interface by hiding the details of how alias analysis
44 /// information is encoded in its operands.
49 TBAANode() : Node(0) {}
50 explicit TBAANode(const MDNode *N) : Node(N) {}
52 /// getNode - Get the MDNode for this TBAANode.
53 const MDNode *getNode() const { return Node; }
55 /// getParent - Get this TBAANode's Alias DAG parent.
56 TBAANode getParent() const {
57 if (Node->getNumOperands() < 2)
59 MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1));
62 // Ok, this node has a valid parent. Return it.
66 /// TypeIsImmutable - Test if this TBAANode represents a type for objects
67 /// which are not modified (by any means) in the context where this
68 /// AliasAnalysis is relevant.
69 bool TypeIsImmutable() const {
70 if (Node->getNumOperands() < 3)
72 ConstantInt *CI = dyn_cast<ConstantInt>(Node->getOperand(2));
75 // TODO: Think about the encoding.
82 /// TypeBasedAliasAnalysis - This is a simple alias analysis
83 /// implementation that uses TypeBased to answer queries.
84 class TypeBasedAliasAnalysis : public ImmutablePass,
85 public AliasAnalysis {
87 static char ID; // Class identification, replacement for typeinfo
88 TypeBasedAliasAnalysis() : ImmutablePass(ID) {
89 initializeTypeBasedAliasAnalysisPass(*PassRegistry::getPassRegistry());
92 virtual void initializePass() {
93 InitializeAliasAnalysis(this);
96 /// getAdjustedAnalysisPointer - This method is used when a pass implements
97 /// an analysis interface through multiple inheritance. If needed, it
98 /// should override this to adjust the this pointer as needed for the
99 /// specified pass info.
100 virtual void *getAdjustedAnalysisPointer(const void *PI) {
101 if (PI == &AliasAnalysis::ID)
102 return (AliasAnalysis*)this;
107 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
108 virtual AliasResult alias(const Location &LocA, const Location &LocB);
109 virtual bool pointsToConstantMemory(const Location &Loc);
111 } // End of anonymous namespace
113 // Register this pass...
114 char TypeBasedAliasAnalysis::ID = 0;
115 INITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa",
116 "Type-Based Alias Analysis", false, true, false)
118 ImmutablePass *llvm::createTypeBasedAliasAnalysisPass() {
119 return new TypeBasedAliasAnalysis();
123 TypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
124 AU.setPreservesAll();
125 AliasAnalysis::getAnalysisUsage(AU);
128 AliasAnalysis::AliasResult
129 TypeBasedAliasAnalysis::alias(const Location &LocA,
130 const Location &LocB) {
132 return AliasAnalysis::alias(LocA, LocB);
134 // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must
136 const MDNode *AM = LocA.TBAATag;
137 if (!AM) return AliasAnalysis::alias(LocA, LocB);
138 const MDNode *BM = LocB.TBAATag;
139 if (!BM) return AliasAnalysis::alias(LocA, LocB);
141 // Keep track of the root node for A and B.
142 TBAANode RootA, RootB;
144 // Climb the DAG from A to see if we reach B.
145 for (TBAANode T(AM); ; ) {
146 if (T.getNode() == BM)
147 // B is an ancestor of A.
148 return AliasAnalysis::alias(LocA, LocB);
156 // Climb the DAG from B to see if we reach A.
157 for (TBAANode T(BM); ; ) {
158 if (T.getNode() == AM)
159 // A is an ancestor of B.
160 return AliasAnalysis::alias(LocA, LocB);
168 // Neither node is an ancestor of the other.
170 // If they have the same root, then we've proved there's no alias.
171 if (RootA.getNode() == RootB.getNode())
174 // If they have different roots, they're part of different potentially
175 // unrelated type systems, so we must be conservative.
176 return AliasAnalysis::alias(LocA, LocB);
179 bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc) {
181 return AliasAnalysis::pointsToConstantMemory(Loc);
183 const MDNode *M = Loc.TBAATag;
184 if (!M) return false;
186 // If this is an "immutable" type, we can assume the pointer is pointing
187 // to constant memory.
188 if (TBAANode(M).TypeIsImmutable())
191 return AliasAnalysis::pointsToConstantMemory(Loc);