LLVM API Documentation
00001 //===- DataStructureAA.cpp - Data Structure Based Alias Analysis ----------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass uses the top-down data structure graphs to implement a simple 00011 // context sensitive alias analysis. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "llvm/Module.h" 00016 #include "llvm/Analysis/AliasAnalysis.h" 00017 #include "llvm/Analysis/DataStructure/DataStructure.h" 00018 #include "llvm/Analysis/DataStructure/DSGraph.h" 00019 using namespace llvm; 00020 00021 namespace { 00022 class DSAA : public ModulePass, public AliasAnalysis { 00023 TDDataStructures *TD; 00024 BUDataStructures *BU; 00025 public: 00026 DSAA() : TD(0) {} 00027 00028 //------------------------------------------------ 00029 // Implement the Pass API 00030 // 00031 00032 // run - Build up the result graph, representing the pointer graph for the 00033 // program. 00034 // 00035 bool runOnModule(Module &M) { 00036 InitializeAliasAnalysis(this); 00037 TD = &getAnalysis<TDDataStructures>(); 00038 BU = &getAnalysis<BUDataStructures>(); 00039 return false; 00040 } 00041 00042 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00043 AliasAnalysis::getAnalysisUsage(AU); 00044 AU.setPreservesAll(); // Does not transform code 00045 AU.addRequiredTransitive<TDDataStructures>(); // Uses TD Datastructures 00046 AU.addRequiredTransitive<BUDataStructures>(); // Uses BU Datastructures 00047 } 00048 00049 //------------------------------------------------ 00050 // Implement the AliasAnalysis API 00051 // 00052 00053 AliasResult alias(const Value *V1, unsigned V1Size, 00054 const Value *V2, unsigned V2Size); 00055 00056 void getMustAliases(Value *P, std::vector<Value*> &RetVals); 00057 00058 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); 00059 00060 private: 00061 DSGraph *getGraphForValue(const Value *V); 00062 }; 00063 00064 // Register the pass... 00065 RegisterOpt<DSAA> X("ds-aa", "Data Structure Graph Based Alias Analysis"); 00066 00067 // Register as an implementation of AliasAnalysis 00068 RegisterAnalysisGroup<AliasAnalysis, DSAA> Y; 00069 } 00070 00071 // getGraphForValue - Return the DSGraph to use for queries about the specified 00072 // value... 00073 // 00074 DSGraph *DSAA::getGraphForValue(const Value *V) { 00075 if (const Instruction *I = dyn_cast<Instruction>(V)) 00076 return &TD->getDSGraph(*I->getParent()->getParent()); 00077 else if (const Argument *A = dyn_cast<Argument>(V)) 00078 return &TD->getDSGraph(*A->getParent()); 00079 else if (const BasicBlock *BB = dyn_cast<BasicBlock>(V)) 00080 return &TD->getDSGraph(*BB->getParent()); 00081 return 0; 00082 } 00083 00084 // isSinglePhysicalObject - For now, the only case that we know that there is 00085 // only one memory object in the node is when there is a single global in the 00086 // node, and the only composition bit set is Global. 00087 // 00088 static bool isSinglePhysicalObject(DSNode *N) { 00089 assert(N->isComplete() && "Can only tell if this is a complete object!"); 00090 return N->isGlobalNode() && N->getGlobals().size() == 1 && 00091 !N->isHeapNode() && !N->isAllocaNode() && !N->isUnknownNode(); 00092 } 00093 00094 // alias - This is the only method here that does anything interesting... 00095 AliasAnalysis::AliasResult DSAA::alias(const Value *V1, unsigned V1Size, 00096 const Value *V2, unsigned V2Size) { 00097 if (V1 == V2) return MustAlias; 00098 00099 DSGraph *G1 = getGraphForValue(V1); 00100 DSGraph *G2 = getGraphForValue(V2); 00101 assert((!G1 || !G2 || G1 == G2) && "Alias query for 2 different functions?"); 00102 00103 // Get the graph to use... 00104 DSGraph &G = *(G1 ? G1 : (G2 ? G2 : &TD->getGlobalsGraph())); 00105 00106 const DSGraph::ScalarMapTy &GSM = G.getScalarMap(); 00107 DSGraph::ScalarMapTy::const_iterator I = GSM.find((Value*)V1); 00108 if (I == GSM.end()) return NoAlias; 00109 00110 assert(I->second.getNode() && "Scalar map points to null node?"); 00111 DSGraph::ScalarMapTy::const_iterator J = GSM.find((Value*)V2); 00112 if (J == GSM.end()) return NoAlias; 00113 00114 assert(J->second.getNode() && "Scalar map points to null node?"); 00115 00116 DSNode *N1 = I->second.getNode(), *N2 = J->second.getNode(); 00117 unsigned O1 = I->second.getOffset(), O2 = J->second.getOffset(); 00118 00119 // We can only make a judgment of one of the nodes is complete... 00120 if (N1->isComplete() || N2->isComplete()) { 00121 if (N1 != N2) 00122 return NoAlias; // Completely different nodes. 00123 00124 #if 0 // This does not correctly handle arrays! 00125 // Both point to the same node and same offset, and there is only one 00126 // physical memory object represented in the node, return must alias. 00127 // 00128 // FIXME: This isn't correct because we do not handle array indexing 00129 // correctly. 00130 00131 if (O1 == O2 && isSinglePhysicalObject(N1)) 00132 return MustAlias; // Exactly the same object & offset 00133 #endif 00134 00135 // See if they point to different offsets... if so, we may be able to 00136 // determine that they do not alias... 00137 if (O1 != O2) { 00138 if (O2 < O1) { // Ensure that O1 <= O2 00139 std::swap(V1, V2); 00140 std::swap(O1, O2); 00141 std::swap(V1Size, V2Size); 00142 } 00143 00144 // FIXME: This is not correct because we do not handle array 00145 // indexing correctly with this check! 00146 //if (O1+V1Size <= O2) return NoAlias; 00147 } 00148 } 00149 00150 // FIXME: we could improve on this by checking the globals graph for aliased 00151 // global queries... 00152 return AliasAnalysis::alias(V1, V1Size, V2, V2Size); 00153 } 00154 00155 /// getModRefInfo - does a callsite modify or reference a value? 00156 /// 00157 AliasAnalysis::ModRefResult 00158 DSAA::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 00159 Function *F = CS.getCalledFunction(); 00160 if (!F) return pointsToConstantMemory(P) ? Ref : ModRef; 00161 if (F->isExternal()) return ModRef; 00162 00163 // Clone the function TD graph, clearing off Mod/Ref flags 00164 const Function *csParent = CS.getInstruction()->getParent()->getParent(); 00165 DSGraph TDGraph(TD->getDSGraph(*csParent)); 00166 TDGraph.maskNodeTypes(0); 00167 00168 // Insert the callee's BU graph into the TD graph 00169 const DSGraph &BUGraph = BU->getDSGraph(*F); 00170 TDGraph.mergeInGraph(TDGraph.getDSCallSiteForCallSite(CS), 00171 *F, BUGraph, 0); 00172 00173 // Report the flags that have been added 00174 const DSNodeHandle &DSH = TDGraph.getNodeForValue(P); 00175 if (const DSNode *N = DSH.getNode()) 00176 if (N->isModified()) 00177 return N->isRead() ? ModRef : Mod; 00178 else 00179 return N->isRead() ? Ref : NoModRef; 00180 return NoModRef; 00181 } 00182 00183 00184 /// getMustAliases - If there are any pointers known that must alias this 00185 /// pointer, return them now. This allows alias-set based alias analyses to 00186 /// perform a form a value numbering (which is exposed by load-vn). If an alias 00187 /// analysis supports this, it should ADD any must aliased pointers to the 00188 /// specified vector. 00189 /// 00190 void DSAA::getMustAliases(Value *P, std::vector<Value*> &RetVals) { 00191 #if 0 // This does not correctly handle arrays! 00192 // Currently the only must alias information we can provide is to say that 00193 // something is equal to a global value. If we already have a global value, 00194 // don't get worked up about it. 00195 if (!isa<GlobalValue>(P)) { 00196 DSGraph *G = getGraphForValue(P); 00197 if (!G) G = &TD->getGlobalsGraph(); 00198 00199 // The only must alias information we can currently determine occurs when 00200 // the node for P is a global node with only one entry. 00201 DSGraph::ScalarMapTy::const_iterator I = G->getScalarMap().find(P); 00202 if (I != G->getScalarMap().end()) { 00203 DSNode *N = I->second.getNode(); 00204 if (N->isComplete() && isSinglePhysicalObject(N)) 00205 RetVals.push_back(N->getGlobals()[0]); 00206 } 00207 } 00208 #endif 00209 return AliasAnalysis::getMustAliases(P, RetVals); 00210 } 00211