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