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(const 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 void *PI) {
92 if (PI == &AliasAnalysis::ID)
93 return (AliasAnalysis*)this;
98 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
99 virtual AliasResult alias(const Location &LocA, const Location &LocB);
100 virtual bool pointsToConstantMemory(const Location &Loc);
102 } // End of anonymous namespace
104 // Register this pass...
105 char TypeBasedAliasAnalysis::ID = 0;
106 INITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa",
107 "Type-Based Alias Analysis", false, true, false);
109 ImmutablePass *llvm::createTypeBasedAliasAnalysisPass() {
110 return new TypeBasedAliasAnalysis();
114 TypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
115 AU.setPreservesAll();
116 AliasAnalysis::getAnalysisUsage(AU);
119 AliasAnalysis::AliasResult
120 TypeBasedAliasAnalysis::alias(const Location &LocA,
121 const Location &LocB) {
122 // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must
124 const MDNode *AM = LocA.TBAATag;
125 if (!AM) return MayAlias;
126 const MDNode *BM = LocB.TBAATag;
127 if (!BM) return MayAlias;
129 // Keep track of the root node for A and B.
130 TBAANode RootA, RootB;
132 // Climb the DAG from A to see if we reach B.
133 for (TBAANode T(AM); ; ) {
134 if (T.getNode() == BM)
135 // B is an ancestor of A.
144 // Climb the DAG from B to see if we reach A.
145 for (TBAANode T(BM); ; ) {
146 if (T.getNode() == AM)
147 // A is an ancestor of B.
156 // Neither node is an ancestor of the other.
158 // If they have the same root, then we've proved there's no alias.
159 if (RootA.getNode() == RootB.getNode())
162 // If they have different roots, they're part of different potentially
163 // unrelated type systems, so we must be conservative.
167 bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc) {
168 const MDNode *M = Loc.TBAATag;
169 if (!M) return false;
171 // If this is an "immutable" type, we can assume the pointer is pointing
172 // to constant memory.
173 return TBAANode(M).TypeIsImmutable();