MemoryDependenceAnalysis.cpp revision 4beedbd0063a8ba6f97db02c3c94707d8ab45b50
1//===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation --*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the Owen Anderson and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements an analysis that determines, for a given memory 11// operation, what preceding memory operations it depends on. It builds on 12// alias analysis information, and tries to provide a lazy, caching interface to 13// a common kind of alias information query. 14// 15//===----------------------------------------------------------------------===// 16 17#include "llvm/Analysis/MemoryDependenceAnalysis.h" 18#include "llvm/Constants.h" 19#include "llvm/Instructions.h" 20#include "llvm/Function.h" 21#include "llvm/Analysis/AliasAnalysis.h" 22#include "llvm/Support/CFG.h" 23#include "llvm/Target/TargetData.h" 24 25using namespace llvm; 26 27char MemoryDependenceAnalysis::ID = 0; 28 29Instruction* MemoryDependenceAnalysis::NonLocal = (Instruction*)0; 30Instruction* MemoryDependenceAnalysis::None = (Instruction*)(~0 - 1); 31 32// Register this pass... 33static RegisterPass<MemoryDependenceAnalysis> X("memdep", 34 "Memory Dependence Analysis"); 35 36/// getAnalysisUsage - Does not modify anything. It uses Alias Analysis. 37/// 38void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 39 AU.setPreservesAll(); 40 AU.addRequiredTransitive<AliasAnalysis>(); 41 AU.addRequiredTransitive<TargetData>(); 42} 43 44// Find the dependency of a CallSite 45Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, Instruction* start, 46 bool local) { 47 assert(local && "Non-local memory dependence analysis not yet implemented"); 48 49 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 50 TargetData& TD = getAnalysis<TargetData>(); 51 BasicBlock::iterator blockBegin = C.getInstruction()->getParent()->begin(); 52 BasicBlock::iterator QI = C.getInstruction(); 53 54 while (QI != blockBegin) { 55 --QI; 56 57 // If this inst is a memory op, get the pointer it accessed 58 Value* pointer = 0; 59 uint64_t pointerSize = 0; 60 if (StoreInst* S = dyn_cast<StoreInst>(QI)) { 61 pointer = S->getPointerOperand(); 62 pointerSize = TD.getTypeSize(S->getOperand(0)->getType()); 63 } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) { 64 pointer = L->getPointerOperand(); 65 pointerSize = TD.getTypeSize(L->getType()); 66 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) { 67 pointer = AI; 68 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize())) 69 pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType()); 70 else 71 pointerSize = ~0UL; 72 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) { 73 pointer = V->getOperand(0); 74 pointerSize = TD.getTypeSize(V->getType()); 75 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) { 76 pointer = F->getPointerOperand(); 77 78 // FreeInsts erase the entire structure 79 pointerSize = ~0UL; 80 } else if (CallSite::get(QI).getInstruction() != 0) { 81 if (AA.getModRefInfo(C, CallSite::get(QI)) != AliasAnalysis::NoModRef) { 82 depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(QI, true))); 83 reverseDep.insert(std::make_pair(QI, C.getInstruction())); 84 return QI; 85 } else { 86 continue; 87 } 88 } else 89 continue; 90 91 if (AA.getModRefInfo(C, pointer, pointerSize) != AliasAnalysis::NoModRef) { 92 depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(QI, true))); 93 reverseDep.insert(std::make_pair(QI, C.getInstruction())); 94 return QI; 95 } 96 } 97 98 // No dependence found 99 depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(NonLocal, true))); 100 reverseDep.insert(std::make_pair(NonLocal, C.getInstruction())); 101 return NonLocal; 102} 103 104SmallPtrSet<Instruction*, 4> MemoryDependenceAnalysis::nonLocalHelper(Instruction* query, 105 BasicBlock* block) { 106 SmallPtrSet<Instruction*, 4> ret; 107 108 Instruction* localDep = getDependency(query, block->end(), block); 109 if (localDep != NonLocal) { 110 ret.insert(localDep); 111 return ret; 112 } 113 114 for (pred_iterator PI = pred_begin(block), PE = pred_end(block); 115 PI != PE; ++PI) { 116 SmallPtrSet<Instruction*, 4> pred_deps = nonLocalHelper(query, *PI); 117 for (SmallPtrSet<Instruction*, 4>::iterator I = pred_deps.begin(), 118 E = pred_deps.end(); I != E; ++I) 119 ret.insert(*I); 120 } 121 122 if (ret.empty()) 123 ret.insert(None); 124 125 return ret; 126} 127 128SmallPtrSet<Instruction*, 4> MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query) { 129 SmallPtrSet<Instruction*, 4> ret; 130 131 Instruction* localDep = getDependency(query); 132 if (localDep != NonLocal) { 133 ret.insert(localDep); 134 return ret; 135 } 136 137 BasicBlock* parent = query->getParent(); 138 for (pred_iterator PI = pred_begin(parent), PE = pred_end(parent); 139 PI != PE; ++PI) { 140 SmallPtrSet<Instruction*, 4> pred_deps = nonLocalHelper(query, *PI); 141 for (SmallPtrSet<Instruction*, 4>::iterator I = pred_deps.begin(), 142 E = pred_deps.end(); I != E; ++I) 143 ret.insert(*I); 144 } 145 146 if (ret.empty()) 147 ret.insert(None); 148 149 return ret; 150} 151 152/// getDependency - Return the instruction on which a memory operation 153/// depends. The local paramter indicates if the query should only 154/// evaluate dependencies within the same basic block. 155Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query, 156 Instruction* start, 157 BasicBlock* block) { 158 // Start looking for dependencies with the queried inst 159 BasicBlock::iterator QI = query; 160 161 // Check for a cached result 162 std::pair<Instruction*, bool> cachedResult = depGraphLocal[query]; 163 // If we have a _confirmed_ cached entry, return it 164 if (cachedResult.second) 165 return cachedResult.first; 166 else if (cachedResult.first != NonLocal) 167 // If we have an unconfirmed cached entry, we can start our search from there 168 QI = cachedResult.first; 169 170 if (start) 171 QI = start; 172 173 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 174 TargetData& TD = getAnalysis<TargetData>(); 175 176 // Get the pointer value for which dependence will be determined 177 Value* dependee = 0; 178 uint64_t dependeeSize = 0; 179 bool queryIsVolatile = false; 180 if (StoreInst* S = dyn_cast<StoreInst>(query)) { 181 dependee = S->getPointerOperand(); 182 dependeeSize = TD.getTypeSize(S->getOperand(0)->getType()); 183 queryIsVolatile = S->isVolatile(); 184 } else if (LoadInst* L = dyn_cast<LoadInst>(query)) { 185 dependee = L->getPointerOperand(); 186 dependeeSize = TD.getTypeSize(L->getType()); 187 queryIsVolatile = L->isVolatile(); 188 } else if (VAArgInst* V = dyn_cast<VAArgInst>(query)) { 189 dependee = V->getOperand(0); 190 dependeeSize = TD.getTypeSize(V->getType()); 191 } else if (FreeInst* F = dyn_cast<FreeInst>(query)) { 192 dependee = F->getPointerOperand(); 193 194 // FreeInsts erase the entire structure, not just a field 195 dependeeSize = ~0UL; 196 } else if (CallSite::get(query).getInstruction() != 0) 197 return getCallSiteDependency(CallSite::get(query), start); 198 else if (isa<AllocationInst>(query)) 199 return None; 200 else 201 return None; 202 203 BasicBlock::iterator blockBegin = block ? block->begin() 204 : query->getParent()->begin(); 205 206 while (QI != blockBegin) { 207 --QI; 208 209 // If this inst is a memory op, get the pointer it accessed 210 Value* pointer = 0; 211 uint64_t pointerSize = 0; 212 if (StoreInst* S = dyn_cast<StoreInst>(QI)) { 213 // All volatile loads/stores depend on each other 214 if (queryIsVolatile && S->isVolatile()) { 215 if (!start) { 216 depGraphLocal.insert(std::make_pair(query, std::make_pair(S, true))); 217 reverseDep.insert(std::make_pair(S, query)); 218 } 219 220 return S; 221 } 222 223 pointer = S->getPointerOperand(); 224 pointerSize = TD.getTypeSize(S->getOperand(0)->getType()); 225 } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) { 226 // All volatile loads/stores depend on each other 227 if (queryIsVolatile && L->isVolatile()) { 228 if (!start) { 229 depGraphLocal.insert(std::make_pair(query, std::make_pair(L, true))); 230 reverseDep.insert(std::make_pair(L, query)); 231 } 232 233 return L; 234 } 235 236 pointer = L->getPointerOperand(); 237 pointerSize = TD.getTypeSize(L->getType()); 238 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) { 239 pointer = AI; 240 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize())) 241 pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType()); 242 else 243 pointerSize = ~0UL; 244 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) { 245 pointer = V->getOperand(0); 246 pointerSize = TD.getTypeSize(V->getType()); 247 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) { 248 pointer = F->getPointerOperand(); 249 250 // FreeInsts erase the entire structure 251 pointerSize = ~0UL; 252 } else if (CallSite::get(QI).getInstruction() != 0) { 253 // Call insts need special handling. Check is they can modify our pointer 254 if (AA.getModRefInfo(CallSite::get(QI), dependee, dependeeSize) != 255 AliasAnalysis::NoModRef) { 256 if (!start) { 257 depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true))); 258 reverseDep.insert(std::make_pair(QI, query)); 259 } 260 261 return QI; 262 } else { 263 continue; 264 } 265 } 266 267 // If we found a pointer, check if it could be the same as our pointer 268 if (pointer) { 269 AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize, 270 dependee, dependeeSize); 271 272 if (R != AliasAnalysis::NoAlias) { 273 if (!start) { 274 depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true))); 275 reverseDep.insert(std::make_pair(QI, query)); 276 } 277 278 return QI; 279 } 280 } 281 } 282 283 // If we found nothing, return the non-local flag 284 if (!start) { 285 depGraphLocal.insert(std::make_pair(query, 286 std::make_pair(NonLocal, true))); 287 reverseDep.insert(std::make_pair(NonLocal, query)); 288 } 289 290 return NonLocal; 291} 292 293/// removeInstruction - Remove an instruction from the dependence analysis, 294/// updating the dependence of instructions that previously depended on it. 295void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) { 296 // Figure out the new dep for things that currently depend on rem 297 Instruction* newDep = NonLocal; 298 if (depGraphLocal[rem].first != NonLocal && 299 depGraphLocal[rem].second) { 300 // If we have dep info for rem, set them to it 301 BasicBlock::iterator RI = depGraphLocal[rem].first; 302 RI++; 303 newDep = RI; 304 } else if (depGraphLocal[rem].first == NonLocal && 305 depGraphLocal[rem].second ) { 306 // If we have a confirmed non-local flag, use it 307 newDep = NonLocal; 308 } else { 309 // Otherwise, use the immediate successor of rem 310 // NOTE: This is because, when getDependence is called, it will first check 311 // the immediate predecessor of what is in the cache. 312 BasicBlock::iterator RI = rem; 313 RI++; 314 newDep = RI; 315 } 316 317 std::multimap<Instruction*, Instruction*>::iterator I = reverseDep.find(rem); 318 while (I->first == rem) { 319 // Insert the new dependencies 320 // Mark it as unconfirmed as long as it is not the non-local flag 321 depGraphLocal[I->second] = std::make_pair(newDep, !newDep); 322 reverseDep.erase(I); 323 I = reverseDep.find(rem); 324 } 325 326 getAnalysis<AliasAnalysis>().deleteValue(rem); 327} 328