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) {}
90 virtual void initializePass() {
91 InitializeAliasAnalysis(this);
94 /// getAdjustedAnalysisPointer - This method is used when a pass implements
95 /// an analysis interface through multiple inheritance. If needed, it
96 /// should override this to adjust the this pointer as needed for the
97 /// specified pass info.
98 virtual void *getAdjustedAnalysisPointer(const void *PI) {
99 if (PI == &AliasAnalysis::ID)
100 return (AliasAnalysis*)this;
105 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
106 virtual AliasResult alias(const Location &LocA, const Location &LocB);
107 virtual bool pointsToConstantMemory(const Location &Loc);
109 } // End of anonymous namespace
111 // Register this pass...
112 char TypeBasedAliasAnalysis::ID = 0;
113 INITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa",
114 "Type-Based Alias Analysis", false, true, false)
116 ImmutablePass *llvm::createTypeBasedAliasAnalysisPass() {
117 return new TypeBasedAliasAnalysis();
121 TypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
122 AU.setPreservesAll();
123 AliasAnalysis::getAnalysisUsage(AU);
126 AliasAnalysis::AliasResult
127 TypeBasedAliasAnalysis::alias(const Location &LocA,
128 const Location &LocB) {
130 return AliasAnalysis::alias(LocA, LocB);
132 // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must
134 const MDNode *AM = LocA.TBAATag;
135 if (!AM) return AliasAnalysis::alias(LocA, LocB);
136 const MDNode *BM = LocB.TBAATag;
137 if (!BM) return AliasAnalysis::alias(LocA, LocB);
139 // Keep track of the root node for A and B.
140 TBAANode RootA, RootB;
142 // Climb the DAG from A to see if we reach B.
143 for (TBAANode T(AM); ; ) {
144 if (T.getNode() == BM)
145 // B is an ancestor of A.
146 return AliasAnalysis::alias(LocA, LocB);
154 // Climb the DAG from B to see if we reach A.
155 for (TBAANode T(BM); ; ) {
156 if (T.getNode() == AM)
157 // A is an ancestor of B.
158 return AliasAnalysis::alias(LocA, LocB);
166 // Neither node is an ancestor of the other.
168 // If they have the same root, then we've proved there's no alias.
169 if (RootA.getNode() == RootB.getNode())
172 // If they have different roots, they're part of different potentially
173 // unrelated type systems, so we must be conservative.
174 return AliasAnalysis::alias(LocA, LocB);
177 bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc) {
179 return AliasAnalysis::pointsToConstantMemory(Loc);
181 const MDNode *M = Loc.TBAATag;
182 if (!M) return false;
184 // If this is an "immutable" type, we can assume the pointer is pointing
185 // to constant memory.
186 if (TBAANode(M).TypeIsImmutable())
189 return AliasAnalysis::pointsToConstantMemory(Loc);