MemoryDependenceAnalysis.cpp revision 4d13de4e3bfc5121207efd01e1b31caa6bb4e40b
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* const MemoryDependenceAnalysis::NonLocal = (Instruction*)-3; 30Instruction* const MemoryDependenceAnalysis::None = (Instruction*)-4; 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/// getCallSiteDependency - Private helper for finding the local dependencies 45/// of a call site. 46Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, 47 Instruction* start, 48 BasicBlock* block) { 49 50 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 51 TargetData& TD = getAnalysis<TargetData>(); 52 BasicBlock::iterator blockBegin = C.getInstruction()->getParent()->begin(); 53 BasicBlock::iterator QI = C.getInstruction(); 54 55 // If the starting point was specifiy, use it 56 if (start) { 57 QI = start; 58 blockBegin = start->getParent()->end(); 59 // If the starting point wasn't specified, but the block was, use it 60 } else if (!start && block) { 61 QI = block->end(); 62 blockBegin = block->end(); 63 } 64 65 // Walk backwards through the block, looking for dependencies 66 while (QI != blockBegin) { 67 --QI; 68 69 // If this inst is a memory op, get the pointer it accessed 70 Value* pointer = 0; 71 uint64_t pointerSize = 0; 72 if (StoreInst* S = dyn_cast<StoreInst>(QI)) { 73 pointer = S->getPointerOperand(); 74 pointerSize = TD.getTypeSize(S->getOperand(0)->getType()); 75 } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) { 76 pointer = L->getPointerOperand(); 77 pointerSize = TD.getTypeSize(L->getType()); 78 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) { 79 pointer = AI; 80 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize())) 81 pointerSize = C->getZExtValue() * \ 82 TD.getTypeSize(AI->getAllocatedType()); 83 else 84 pointerSize = ~0UL; 85 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) { 86 pointer = V->getOperand(0); 87 pointerSize = TD.getTypeSize(V->getType()); 88 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) { 89 pointer = F->getPointerOperand(); 90 91 // FreeInsts erase the entire structure 92 pointerSize = ~0UL; 93 } else if (CallSite::get(QI).getInstruction() != 0) { 94 if (AA.getModRefInfo(C, CallSite::get(QI)) != AliasAnalysis::NoModRef) { 95 if (!start && !block) { 96 depGraphLocal.insert(std::make_pair(C.getInstruction(), 97 std::make_pair(QI, true))); 98 reverseDep[QI].insert(C.getInstruction()); 99 } 100 return QI; 101 } else { 102 continue; 103 } 104 } else 105 continue; 106 107 if (AA.getModRefInfo(C, pointer, pointerSize) != AliasAnalysis::NoModRef) { 108 if (!start && !block) { 109 depGraphLocal.insert(std::make_pair(C.getInstruction(), 110 std::make_pair(QI, true))); 111 reverseDep[QI].insert(C.getInstruction()); 112 } 113 return QI; 114 } 115 } 116 117 // No dependence found 118 depGraphLocal.insert(std::make_pair(C.getInstruction(), 119 std::make_pair(NonLocal, true))); 120 reverseDep[NonLocal].insert(C.getInstruction()); 121 return NonLocal; 122} 123 124/// nonLocalHelper - Private helper used to calculate non-local dependencies 125/// by doing DFS on the predecessors of a block to find its dependencies 126void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query, 127 BasicBlock* block, 128 DenseMap<BasicBlock*, Value*>& resp) { 129 // Set of blocks that we've already visited in our DFS 130 SmallPtrSet<BasicBlock*, 4> visited; 131 // Current stack of the DFS 132 SmallVector<BasicBlock*, 4> stack; 133 stack.push_back(block); 134 135 // Do a basic DFS 136 while (!stack.empty()) { 137 BasicBlock* BB = stack.back(); 138 139 // If we've already visited this block, no need to revist 140 if (visited.count(BB)) { 141 stack.pop_back(); 142 continue; 143 } 144 145 // If we find a new block with a local dependency for query, 146 // then we insert the new dependency and backtrack. 147 if (BB != block) { 148 visited.insert(BB); 149 150 Instruction* localDep = getDependency(query, 0, BB); 151 if (localDep != NonLocal) { 152 resp.insert(std::make_pair(BB, localDep)); 153 stack.pop_back(); 154 155 continue; 156 } 157 // If we re-encounter the starting block, we still need to search it 158 // because there might be a dependency in the starting block AFTER 159 // the position of the query. This is necessary to get loops right. 160 } else if (BB == block && stack.size() > 1) { 161 visited.insert(BB); 162 163 Instruction* localDep = getDependency(query, 0, BB); 164 if (localDep != query) 165 resp.insert(std::make_pair(BB, localDep)); 166 167 stack.pop_back(); 168 169 continue; 170 } 171 172 // If we didn't find anything, recurse on the precessors of this block 173 bool predOnStack = false; 174 bool inserted = false; 175 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); 176 PI != PE; ++PI) 177 if (!visited.count(*PI)) { 178 stack.push_back(*PI); 179 inserted = true; 180 } else 181 predOnStack = true; 182 183 // If we inserted a new predecessor, then we'll come back to this block 184 if (inserted) 185 continue; 186 // If we didn't insert because we have no predecessors, then this 187 // query has no dependency at all. 188 else if (!inserted && !predOnStack) { 189 resp.insert(std::make_pair(BB, None)); 190 // If we didn't insert because our predecessors are already on the stack, 191 // then we might still have a dependency, but it will be discovered during 192 // backtracking. 193 } else if (!inserted && predOnStack){ 194 resp.insert(std::make_pair(BB, NonLocal)); 195 } 196 197 stack.pop_back(); 198 } 199} 200 201/// getNonLocalDependency - Fills the passed-in map with the non-local 202/// dependencies of the queries. The map will contain NonLocal for 203/// blocks between the query and its dependencies. 204void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query, 205 DenseMap<BasicBlock*, Value*>& resp) { 206 if (depGraphNonLocal.count(query)) { 207 resp = depGraphNonLocal[query]; 208 return; 209 } 210 211 // First check that we don't actually have a local dependency. 212 Instruction* localDep = getDependency(query); 213 if (localDep != NonLocal) { 214 resp.insert(std::make_pair(query->getParent(),localDep)); 215 return; 216 } 217 218 // If not, go ahead and search for non-local ones. 219 nonLocalHelper(query, query->getParent(), resp); 220 221 // Update the non-local dependency cache 222 for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(), E = resp.end(); 223 I != E; ++I) { 224 depGraphNonLocal[query].insert(*I); 225 reverseDepNonLocal[I->second].insert(query); 226 } 227} 228 229/// getDependency - Return the instruction on which a memory operation 230/// depends. The local paramter indicates if the query should only 231/// evaluate dependencies within the same basic block. 232Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query, 233 Instruction* start, 234 BasicBlock* block) { 235 // Start looking for dependencies with the queried inst 236 BasicBlock::iterator QI = query; 237 238 // Check for a cached result 239 std::pair<Instruction*, bool> cachedResult = depGraphLocal[query]; 240 // If we have a _confirmed_ cached entry, return it 241 if (cachedResult.second) 242 return cachedResult.first; 243 else if (cachedResult.first && cachedResult.first != NonLocal) 244 // If we have an unconfirmed cached entry, we can start our search from there 245 QI = cachedResult.first; 246 247 if (start) 248 QI = start; 249 else if (!start && block) 250 QI = block->end(); 251 252 AliasAnalysis& AA = getAnalysis<AliasAnalysis>(); 253 TargetData& TD = getAnalysis<TargetData>(); 254 255 // Get the pointer value for which dependence will be determined 256 Value* dependee = 0; 257 uint64_t dependeeSize = 0; 258 bool queryIsVolatile = false; 259 if (StoreInst* S = dyn_cast<StoreInst>(query)) { 260 dependee = S->getPointerOperand(); 261 dependeeSize = TD.getTypeSize(S->getOperand(0)->getType()); 262 queryIsVolatile = S->isVolatile(); 263 } else if (LoadInst* L = dyn_cast<LoadInst>(query)) { 264 dependee = L->getPointerOperand(); 265 dependeeSize = TD.getTypeSize(L->getType()); 266 queryIsVolatile = L->isVolatile(); 267 } else if (VAArgInst* V = dyn_cast<VAArgInst>(query)) { 268 dependee = V->getOperand(0); 269 dependeeSize = TD.getTypeSize(V->getType()); 270 } else if (FreeInst* F = dyn_cast<FreeInst>(query)) { 271 dependee = F->getPointerOperand(); 272 273 // FreeInsts erase the entire structure, not just a field 274 dependeeSize = ~0UL; 275 } else if (CallSite::get(query).getInstruction() != 0) 276 return getCallSiteDependency(CallSite::get(query), start, block); 277 else if (isa<AllocationInst>(query)) 278 return None; 279 else 280 return None; 281 282 BasicBlock::iterator blockBegin = block ? block->begin() 283 : query->getParent()->begin(); 284 285 // Walk backwards through the basic block, looking for dependencies 286 while (QI != blockBegin) { 287 --QI; 288 289 // If this inst is a memory op, get the pointer it accessed 290 Value* pointer = 0; 291 uint64_t pointerSize = 0; 292 if (StoreInst* S = dyn_cast<StoreInst>(QI)) { 293 // All volatile loads/stores depend on each other 294 if (queryIsVolatile && S->isVolatile()) { 295 if (!start && !block) { 296 depGraphLocal.insert(std::make_pair(query, std::make_pair(S, true))); 297 reverseDep[S].insert(query); 298 } 299 300 return S; 301 } 302 303 pointer = S->getPointerOperand(); 304 pointerSize = TD.getTypeSize(S->getOperand(0)->getType()); 305 } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) { 306 // All volatile loads/stores depend on each other 307 if (queryIsVolatile && L->isVolatile()) { 308 if (!start && !block) { 309 depGraphLocal.insert(std::make_pair(query, std::make_pair(L, true))); 310 reverseDep[L].insert(query); 311 } 312 313 return L; 314 } 315 316 pointer = L->getPointerOperand(); 317 pointerSize = TD.getTypeSize(L->getType()); 318 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) { 319 pointer = AI; 320 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize())) 321 pointerSize = C->getZExtValue() * \ 322 TD.getTypeSize(AI->getAllocatedType()); 323 else 324 pointerSize = ~0UL; 325 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) { 326 pointer = V->getOperand(0); 327 pointerSize = TD.getTypeSize(V->getType()); 328 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) { 329 pointer = F->getPointerOperand(); 330 331 // FreeInsts erase the entire structure 332 pointerSize = ~0UL; 333 } else if (CallSite::get(QI).getInstruction() != 0) { 334 // Call insts need special handling. Check if they can modify our pointer 335 AliasAnalysis::ModRefResult MR = AA.getModRefInfo(CallSite::get(QI), 336 dependee, dependeeSize); 337 338 if (MR != AliasAnalysis::NoModRef) { 339 // Loads don't depend on read-only calls 340 if (isa<LoadInst>(query) && MR == AliasAnalysis::Ref) 341 continue; 342 343 if (!start && !block) { 344 depGraphLocal.insert(std::make_pair(query, 345 std::make_pair(QI, true))); 346 reverseDep[QI].insert(query); 347 } 348 349 return QI; 350 } else { 351 continue; 352 } 353 } 354 355 // If we found a pointer, check if it could be the same as our pointer 356 if (pointer) { 357 AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize, 358 dependee, dependeeSize); 359 360 if (R != AliasAnalysis::NoAlias) { 361 // May-alias loads don't depend on each other 362 if (isa<LoadInst>(query) && isa<LoadInst>(QI) && 363 R == AliasAnalysis::MayAlias) 364 continue; 365 366 if (!start && !block) { 367 depGraphLocal.insert(std::make_pair(query, 368 std::make_pair(QI, true))); 369 reverseDep[QI].insert(query); 370 } 371 372 return QI; 373 } 374 } 375 } 376 377 // If we found nothing, return the non-local flag 378 if (!start && !block) { 379 depGraphLocal.insert(std::make_pair(query, 380 std::make_pair(NonLocal, true))); 381 reverseDep[NonLocal].insert(query); 382 } 383 384 return NonLocal; 385} 386 387/// removeInstruction - Remove an instruction from the dependence analysis, 388/// updating the dependence of instructions that previously depended on it. 389/// This method attempts to keep the cache coherent using the reverse map. 390void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) { 391 // Figure out the new dep for things that currently depend on rem 392 Instruction* newDep = NonLocal; 393 394 depMapType::iterator depGraphEntry = depGraphLocal.find(rem); 395 396 if (depGraphEntry != depGraphLocal.end()) { 397 if (depGraphEntry->second.first != NonLocal && 398 depGraphEntry->second.second) { 399 // If we have dep info for rem, set them to it 400 BasicBlock::iterator RI = depGraphEntry->second.first; 401 RI++; 402 newDep = RI; 403 } else if (depGraphEntry->second.first == NonLocal && 404 depGraphEntry->second.second ) { 405 // If we have a confirmed non-local flag, use it 406 newDep = NonLocal; 407 } else { 408 // Otherwise, use the immediate successor of rem 409 // NOTE: This is because, when getDependence is called, it will first 410 // check the immediate predecessor of what is in the cache. 411 BasicBlock::iterator RI = rem; 412 RI++; 413 newDep = RI; 414 } 415 416 SmallPtrSet<Instruction*, 4>& set = reverseDep[rem]; 417 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 418 I != E; ++I) { 419 // Insert the new dependencies 420 // Mark it as unconfirmed as long as it is not the non-local flag 421 depGraphLocal[*I] = std::make_pair(newDep, !newDep); 422 } 423 424 reverseDep.erase(rem); 425 } 426 427 if (depGraphNonLocal.count(rem)) { 428 SmallPtrSet<Instruction*, 4>& set = reverseDepNonLocal[rem]; 429 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); 430 I != E; ++I) 431 depGraphNonLocal.erase(*I); 432 433 reverseDepNonLocal.erase(rem); 434 } 435 436 getAnalysis<AliasAnalysis>().deleteValue(rem); 437} 438