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"
38 /// TBAANode - This is a simple wrapper around an MDNode which provides a
39 /// higher-level interface by hiding the details of how alias analysis
40 /// information is encoded in its operands.
45 TBAANode() : Node(0) {}
46 explicit TBAANode(const MDNode *N) : Node(N) {}
48 /// getNode - Get the MDNode for this TBAANode.
49 const MDNode *getNode() const { return Node; }
51 /// getParent - Get this TBAANode's Alias DAG parent.
52 TBAANode getParent() const {
53 if (Node->getNumOperands() < 2)
55 MDNode *P = dyn_cast<MDNode>(Node->getOperand(1));
58 // Ok, this node has a valid parent. Return it.
62 /// TypeIsImmutable - Test if this TBAANode represents a type for objects
63 /// which are not modified (by any means) in the context where this
64 /// AliasAnalysis is relevant.
65 bool TypeIsImmutable() const {
66 if (Node->getNumOperands() < 3)
68 ConstantInt *CI = dyn_cast<ConstantInt>(Node->getOperand(2));
71 // TODO: Think about the encoding.
78 /// TypeBasedAliasAnalysis - This is a simple alias analysis
79 /// implementation that uses TypeBased to answer queries.
80 class TypeBasedAliasAnalysis : public ImmutablePass,
81 public AliasAnalysis {
83 static char ID; // Class identification, replacement for typeinfo
84 TypeBasedAliasAnalysis() : ImmutablePass(ID) {}
86 virtual void initializePass() {
87 InitializeAliasAnalysis(this);
90 /// getAdjustedAnalysisPointer - This method is used when a pass implements
91 /// an analysis interface through multiple inheritance. If needed, it
92 /// should override this to adjust the this pointer as needed for the
93 /// specified pass info.
94 virtual void *getAdjustedAnalysisPointer(const void *PI) {
95 if (PI == &AliasAnalysis::ID)
96 return (AliasAnalysis*)this;
101 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
102 virtual AliasResult alias(const Location &LocA, const Location &LocB);
103 virtual bool pointsToConstantMemory(const Location &Loc);
105 } // End of anonymous namespace
107 // Register this pass...
108 char TypeBasedAliasAnalysis::ID = 0;
109 INITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa",
110 "Type-Based Alias Analysis", false, true, false)
112 ImmutablePass *llvm::createTypeBasedAliasAnalysisPass() {
113 return new TypeBasedAliasAnalysis();
117 TypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
118 AU.setPreservesAll();
119 AliasAnalysis::getAnalysisUsage(AU);
122 AliasAnalysis::AliasResult
123 TypeBasedAliasAnalysis::alias(const Location &LocA,
124 const Location &LocB) {
125 // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must
127 const MDNode *AM = LocA.TBAATag;
128 if (!AM) return AliasAnalysis::alias(LocA, LocB);
129 const MDNode *BM = LocB.TBAATag;
130 if (!BM) return AliasAnalysis::alias(LocA, LocB);
132 // Keep track of the root node for A and B.
133 TBAANode RootA, RootB;
135 // Climb the DAG from A to see if we reach B.
136 for (TBAANode T(AM); ; ) {
137 if (T.getNode() == BM)
138 // B is an ancestor of A.
139 return AliasAnalysis::alias(LocA, LocB);
147 // Climb the DAG from B to see if we reach A.
148 for (TBAANode T(BM); ; ) {
149 if (T.getNode() == AM)
150 // A is an ancestor of B.
151 return AliasAnalysis::alias(LocA, LocB);
159 // Neither node is an ancestor of the other.
161 // If they have the same root, then we've proved there's no alias.
162 if (RootA.getNode() == RootB.getNode())
165 // If they have different roots, they're part of different potentially
166 // unrelated type systems, so we must be conservative.
167 return AliasAnalysis::alias(LocA, LocB);
170 bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc) {
171 const MDNode *M = Loc.TBAATag;
172 if (!M) return false;
174 // If this is an "immutable" type, we can assume the pointer is pointing
175 // to constant memory.
176 return TBAANode(M).TypeIsImmutable();