lib/Analysis/MemoryDependenceAnalysis.cpp

   1 //===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation  --*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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/Support/CommandLine.h"
  24 #include "llvm/Target/TargetData.h"
  25 #include "llvm/ADT/Statistic.h"
  26
  27 #define DEBUG_TYPE "memdep"
  28
  29 using namespace llvm;
  30
  31 // Control the calculation of non-local dependencies by only examining the
  32 // predecessors if the basic block has less than X amount (50 by default).
  33 static cl::opt<int>
  34 PredLimit("nonlocaldep-threshold", cl::Hidden, cl::init(50),
  35           cl::desc("Control the calculation of non-local"
  36                    "dependencies (default = 50)"));
  37
  38 STATISTIC(NumCacheNonlocal, "Number of cached non-local responses");
  39 STATISTIC(NumUncacheNonlocal, "Number of uncached non-local responses");
  40
  41 char MemoryDependenceAnalysis::ID = 0;
  42
  43 Instruction* const MemoryDependenceAnalysis::NonLocal = (Instruction*)-3;
  44 Instruction* const MemoryDependenceAnalysis::None = (Instruction*)-4;
  45 Instruction* const MemoryDependenceAnalysis::Dirty = (Instruction*)-5;
  46
  47 // Register this pass...
  48 static RegisterPass<MemoryDependenceAnalysis> X("memdep",
  49                                                 "Memory Dependence Analysis", false, true);
  50
  51 void MemoryDependenceAnalysis::ping(Instruction *D) {
  52   for (depMapType::iterator I = depGraphLocal.begin(), E = depGraphLocal.end();
  53        I != E; ++I) {
  54     assert(I->first != D);
  55     assert(I->second.first != D);
  56   }
  57
  58   for (nonLocalDepMapType::iterator I = depGraphNonLocal.begin(), E = depGraphNonLocal.end();
  59        I != E; ++I) {
  60     assert(I->first != D);
  61   }
  62
  63   for (reverseDepMapType::iterator I = reverseDep.begin(), E = reverseDep.end();
  64        I != E; ++I)
  65     for (SmallPtrSet<Instruction*, 4>::iterator II = I->second.begin(), EE = I->second.end();
  66          II != EE; ++II)
  67       assert(*II != D);
  68
  69   for (reverseDepMapType::iterator I = reverseDepNonLocal.begin(), E = reverseDepNonLocal.end();
  70        I != E; ++I)
  71     for (SmallPtrSet<Instruction*, 4>::iterator II = I->second.begin(), EE = I->second.end();
  72          II != EE; ++II)
  73       assert(*II != D);
  74 }
  75
  76 /// getAnalysisUsage - Does not modify anything.  It uses Alias Analysis.
  77 ///
  78 void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
  79   AU.setPreservesAll();
  80   AU.addRequiredTransitive<AliasAnalysis>();
  81   AU.addRequiredTransitive<TargetData>();
  82 }
  83
  84 /// getCallSiteDependency - Private helper for finding the local dependencies
  85 /// of a call site.
  86 Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C,
  87                                                            Instruction* start,
  88                                                             BasicBlock* block) {
  89
  90   std::pair<Instruction*, bool>& cachedResult =
  91                                               depGraphLocal[C.getInstruction()];
  92   AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
  93   TargetData& TD = getAnalysis<TargetData>();
  94   BasicBlock::iterator blockBegin = C.getInstruction()->getParent()->begin();
  95   BasicBlock::iterator QI = C.getInstruction();
  96
  97   // If the starting point was specifiy, use it
  98   if (start) {
  99     QI = start;
 100     blockBegin = start->getParent()->begin();
 101   // If the starting point wasn't specified, but the block was, use it
 102   } else if (!start && block) {
 103     QI = block->end();
 104     blockBegin = block->begin();
 105   }
 106
 107   // Walk backwards through the block, looking for dependencies
 108   while (QI != blockBegin) {
 109     --QI;
 110
 111     // If this inst is a memory op, get the pointer it accessed
 112     Value* pointer = 0;
 113     uint64_t pointerSize = 0;
 114     if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
 115       pointer = S->getPointerOperand();
 116       pointerSize = TD.getTypeStoreSize(S->getOperand(0)->getType());
 117     } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
 118       pointer = AI;
 119       if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
 120         pointerSize = C->getZExtValue() * \
 121                       TD.getABITypeSize(AI->getAllocatedType());
 122       else
 123         pointerSize = ~0UL;
 124     } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
 125       pointer = V->getOperand(0);
 126       pointerSize = TD.getTypeStoreSize(V->getType());
 127     } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
 128       pointer = F->getPointerOperand();
 129
 130       // FreeInsts erase the entire structure
 131       pointerSize = ~0UL;
 132     } else if (isa<CallInst>(QI)) {
 133       AliasAnalysis::ModRefBehavior result =
 134                    AA.getModRefBehavior(CallSite::get(QI));
 135       if (result != AliasAnalysis::DoesNotAccessMemory) {
 136         if (!start && !block) {
 137           cachedResult.first = QI;
 138           cachedResult.second = true;
 139           reverseDep[QI].insert(C.getInstruction());
 140         }
 141         return QI;
 142       } else {
 143         continue;
 144       }
 145     } else
 146       continue;
 147
 148     if (AA.getModRefInfo(C, pointer, pointerSize) != AliasAnalysis::NoModRef) {
 149       if (!start && !block) {
 150         cachedResult.first = QI;
 151         cachedResult.second = true;
 152         reverseDep[QI].insert(C.getInstruction());
 153       }
 154       return QI;
 155     }
 156   }
 157
 158   // No dependence found
 159   cachedResult.first = NonLocal;
 160   cachedResult.second = true;
 161   reverseDep[NonLocal].insert(C.getInstruction());
 162   return NonLocal;
 163 }
 164
 165 /// nonLocalHelper - Private helper used to calculate non-local dependencies
 166 /// by doing DFS on the predecessors of a block to find its dependencies
 167 void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
 168                                               BasicBlock* block,
 169                                          DenseMap<BasicBlock*, Value*>& resp) {
 170   // Set of blocks that we've already visited in our DFS
 171   SmallPtrSet<BasicBlock*, 4> visited;
 172   // If we're updating a dirtied cache entry, we don't need to reprocess
 173   // already computed entries.
 174   for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(),
 175        E = resp.end(); I != E; ++I)
 176     if (I->second != Dirty)
 177       visited.insert(I->first);
 178
 179   // Current stack of the DFS
 180   SmallVector<BasicBlock*, 4> stack;
 181   for (pred_iterator PI = pred_begin(block), PE = pred_end(block);
 182        PI != PE; ++PI)
 183     stack.push_back(*PI);
 184
 185   // Do a basic DFS
 186   while (!stack.empty()) {
 187     BasicBlock* BB = stack.back();
 188
 189     // If we've already visited this block, no need to revist
 190     if (visited.count(BB)) {
 191       stack.pop_back();
 192       continue;
 193     }
 194
 195     // If we find a new block with a local dependency for query,
 196     // then we insert the new dependency and backtrack.
 197     if (BB != block) {
 198       visited.insert(BB);
 199
 200       Instruction* localDep = getDependency(query, 0, BB);
 201       if (localDep != NonLocal) {
 202         resp.insert(std::make_pair(BB, localDep));
 203         stack.pop_back();
 204
 205         continue;
 206       }
 207     // If we re-encounter the starting block, we still need to search it
 208     // because there might be a dependency in the starting block AFTER
 209     // the position of the query.  This is necessary to get loops right.
 210     } else if (BB == block) {
 211       visited.insert(BB);
 212
 213       Instruction* localDep = getDependency(query, 0, BB);
 214       if (localDep != query)
 215         resp.insert(std::make_pair(BB, localDep));
 216
 217       stack.pop_back();
 218
 219       continue;
 220     }
 221
 222     // If we didn't find anything, recurse on the precessors of this block
 223     // Only do this for blocks with a small number of predecessors.
 224     bool predOnStack = false;
 225     bool inserted = false;
 226     if (std::distance(pred_begin(BB), pred_end(BB)) <= PredLimit) {
 227       for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 228            PI != PE; ++PI)
 229         if (!visited.count(*PI)) {
 230           stack.push_back(*PI);
 231           inserted = true;
 232         } else
 233           predOnStack = true;
 234     }
 235
 236     // If we inserted a new predecessor, then we'll come back to this block
 237     if (inserted)
 238       continue;
 239     // If we didn't insert because we have no predecessors, then this
 240     // query has no dependency at all.
 241     else if (!inserted && !predOnStack) {
 242       resp.insert(std::make_pair(BB, None));
 243     // If we didn't insert because our predecessors are already on the stack,
 244     // then we might still have a dependency, but it will be discovered during
 245     // backtracking.
 246     } else if (!inserted && predOnStack){
 247       resp.insert(std::make_pair(BB, NonLocal));
 248     }
 249
 250     stack.pop_back();
 251   }
 252 }
 253
 254 /// getNonLocalDependency - Fills the passed-in map with the non-local
 255 /// dependencies of the queries.  The map will contain NonLocal for
 256 /// blocks between the query and its dependencies.
 257 void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
 258                                          DenseMap<BasicBlock*, Value*>& resp) {
 259   if (depGraphNonLocal.count(query)) {
 260     DenseMap<BasicBlock*, Value*>& cached = depGraphNonLocal[query];
 261     NumCacheNonlocal++;
 262
 263     SmallVector<BasicBlock*, 4> dirtied;
 264     for (DenseMap<BasicBlock*, Value*>::iterator I = cached.begin(),
 265          E = cached.end(); I != E; ++I)
 266       if (I->second == Dirty)
 267         dirtied.push_back(I->first);
 268
 269     for (SmallVector<BasicBlock*, 4>::iterator I = dirtied.begin(),
 270          E = dirtied.end(); I != E; ++I) {
 271       Instruction* localDep = getDependency(query, 0, *I);
 272       if (localDep != NonLocal)
 273         cached[*I] = localDep;
 274       else {
 275         cached.erase(*I);
 276         nonLocalHelper(query, *I, cached);
 277       }
 278     }
 279
 280     resp = cached;
 281
 282     return;
 283   } else
 284     NumUncacheNonlocal++;
 285
 286   // If not, go ahead and search for non-local deps.
 287   nonLocalHelper(query, query->getParent(), resp);
 288
 289   // Update the non-local dependency cache
 290   for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(), E = resp.end();
 291        I != E; ++I) {
 292     depGraphNonLocal[query].insert(*I);
 293     reverseDepNonLocal[I->second].insert(query);
 294   }
 295 }
 296
 297 /// getDependency - Return the instruction on which a memory operation
 298 /// depends.  The local parameter indicates if the query should only
 299 /// evaluate dependencies within the same basic block.
 300 Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
 301                                                      Instruction* start,
 302                                                      BasicBlock* block) {
 303   // Start looking for dependencies with the queried inst
 304   BasicBlock::iterator QI = query;
 305
 306   // Check for a cached result
 307   std::pair<Instruction*, bool>& cachedResult = depGraphLocal[query];
 308   // If we have a _confirmed_ cached entry, return it
 309   if (!block && !start) {
 310     if (cachedResult.second)
 311       return cachedResult.first;
 312     else if (cachedResult.first && cachedResult.first != NonLocal)
 313       // If we have an unconfirmed cached entry, we can start our search from there
 314       QI = cachedResult.first;
 315   }
 316
 317   if (start)
 318     QI = start;
 319   else if (!start && block)
 320     QI = block->end();
 321
 322   AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
 323   TargetData& TD = getAnalysis<TargetData>();
 324
 325   // Get the pointer value for which dependence will be determined
 326   Value* dependee = 0;
 327   uint64_t dependeeSize = 0;
 328   bool queryIsVolatile = false;
 329   if (StoreInst* S = dyn_cast<StoreInst>(query)) {
 330     dependee = S->getPointerOperand();
 331     dependeeSize = TD.getTypeStoreSize(S->getOperand(0)->getType());
 332     queryIsVolatile = S->isVolatile();
 333   } else if (LoadInst* L = dyn_cast<LoadInst>(query)) {
 334     dependee = L->getPointerOperand();
 335     dependeeSize = TD.getTypeStoreSize(L->getType());
 336     queryIsVolatile = L->isVolatile();
 337   } else if (VAArgInst* V = dyn_cast<VAArgInst>(query)) {
 338     dependee = V->getOperand(0);
 339     dependeeSize = TD.getTypeStoreSize(V->getType());
 340   } else if (FreeInst* F = dyn_cast<FreeInst>(query)) {
 341     dependee = F->getPointerOperand();
 342
 343     // FreeInsts erase the entire structure, not just a field
 344     dependeeSize = ~0UL;
 345   } else if (CallSite::get(query).getInstruction() != 0)
 346     return getCallSiteDependency(CallSite::get(query), start, block);
 347   else if (isa<AllocationInst>(query))
 348     return None;
 349   else
 350     return None;
 351
 352   BasicBlock::iterator blockBegin = block ? block->begin()
 353                                           : query->getParent()->begin();
 354
 355   // Walk backwards through the basic block, looking for dependencies
 356   while (QI != blockBegin) {
 357     --QI;
 358
 359     // If this inst is a memory op, get the pointer it accessed
 360     Value* pointer = 0;
 361     uint64_t pointerSize = 0;
 362     if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
 363       // All volatile loads/stores depend on each other
 364       if (queryIsVolatile && S->isVolatile()) {
 365         if (!start && !block) {
 366           cachedResult.first = S;
 367           cachedResult.second = true;
 368           reverseDep[S].insert(query);
 369         }
 370
 371         return S;
 372       }
 373
 374       pointer = S->getPointerOperand();
 375       pointerSize = TD.getTypeStoreSize(S->getOperand(0)->getType());
 376     } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
 377       // All volatile loads/stores depend on each other
 378       if (queryIsVolatile && L->isVolatile()) {
 379         if (!start && !block) {
 380           cachedResult.first = L;
 381           cachedResult.second = true;
 382           reverseDep[L].insert(query);
 383         }
 384
 385         return L;
 386       }
 387
 388       pointer = L->getPointerOperand();
 389       pointerSize = TD.getTypeStoreSize(L->getType());
 390     } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
 391       pointer = AI;
 392       if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
 393         pointerSize = C->getZExtValue() * \
 394                       TD.getABITypeSize(AI->getAllocatedType());
 395       else
 396         pointerSize = ~0UL;
 397     } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
 398       pointer = V->getOperand(0);
 399       pointerSize = TD.getTypeStoreSize(V->getType());
 400     } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
 401       pointer = F->getPointerOperand();
 402
 403       // FreeInsts erase the entire structure
 404       pointerSize = ~0UL;
 405     } else if (CallSite::get(QI).getInstruction() != 0) {
 406       // Call insts need special handling. Check if they can modify our pointer
 407       AliasAnalysis::ModRefResult MR = AA.getModRefInfo(CallSite::get(QI),
 408                                                       dependee, dependeeSize);
 409
 410       if (MR != AliasAnalysis::NoModRef) {
 411         // Loads don't depend on read-only calls
 412         if (isa<LoadInst>(query) && MR == AliasAnalysis::Ref)
 413           continue;
 414
 415         if (!start && !block) {
 416           cachedResult.first = QI;
 417           cachedResult.second = true;
 418           reverseDep[QI].insert(query);
 419         }
 420
 421         return QI;
 422       } else {
 423         continue;
 424       }
 425     }
 426
 427     // If we found a pointer, check if it could be the same as our pointer
 428     if (pointer) {
 429       AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize,
 430                                               dependee, dependeeSize);
 431
 432       if (R != AliasAnalysis::NoAlias) {
 433         // May-alias loads don't depend on each other
 434         if (isa<LoadInst>(query) && isa<LoadInst>(QI) &&
 435             R == AliasAnalysis::MayAlias)
 436           continue;
 437
 438         if (!start && !block) {
 439           cachedResult.first = QI;
 440           cachedResult.second = true;
 441           reverseDep[QI].insert(query);
 442         }
 443
 444         return QI;
 445       }
 446     }
 447   }
 448
 449   // If we found nothing, return the non-local flag
 450   if (!start && !block) {
 451     cachedResult.first = NonLocal;
 452     cachedResult.second = true;
 453     reverseDep[NonLocal].insert(query);
 454   }
 455
 456   return NonLocal;
 457 }
 458
 459 /// dropInstruction - Remove an instruction from the analysis, making
 460 /// absolutely conservative assumptions when updating the cache.  This is
 461 /// useful, for example when an instruction is changed rather than removed.
 462 void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) {
 463   depMapType::iterator depGraphEntry = depGraphLocal.find(drop);
 464   if (depGraphEntry != depGraphLocal.end())
 465     reverseDep[depGraphEntry->second.first].erase(drop);
 466
 467   // Drop dependency information for things that depended on this instr
 468   SmallPtrSet<Instruction*, 4>& set = reverseDep[drop];
 469   for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 470        I != E; ++I)
 471     depGraphLocal.erase(*I);
 472
 473   depGraphLocal.erase(drop);
 474   reverseDep.erase(drop);
 475
 476   for (DenseMap<BasicBlock*, Value*>::iterator DI =
 477        depGraphNonLocal[drop].begin(), DE = depGraphNonLocal[drop].end();
 478        DI != DE; ++DI)
 479     if (DI->second != None)
 480       reverseDepNonLocal[DI->second].erase(drop);
 481
 482   if (reverseDepNonLocal.count(drop)) {
 483     SmallPtrSet<Instruction*, 4>& set = reverseDepNonLocal[drop];
 484     for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 485          I != E; ++I)
 486       for (DenseMap<BasicBlock*, Value*>::iterator DI =
 487            depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end();
 488            DI != DE; ++DI)
 489         if (DI->second == drop)
 490           DI->second = Dirty;
 491   }
 492
 493   reverseDepNonLocal.erase(drop);
 494   nonLocalDepMapType::iterator I = depGraphNonLocal.find(drop);
 495   if (I != depGraphNonLocal.end())
 496     depGraphNonLocal.erase(I);
 497 }
 498
 499 /// removeInstruction - Remove an instruction from the dependence analysis,
 500 /// updating the dependence of instructions that previously depended on it.
 501 /// This method attempts to keep the cache coherent using the reverse map.
 502 void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
 503   // Figure out the new dep for things that currently depend on rem
 504   Instruction* newDep = NonLocal;
 505
 506   for (DenseMap<BasicBlock*, Value*>::iterator DI =
 507        depGraphNonLocal[rem].begin(), DE = depGraphNonLocal[rem].end();
 508        DI != DE; ++DI)
 509     if (DI->second != None)
 510       reverseDepNonLocal[DI->second].erase(rem);
 511
 512   depMapType::iterator depGraphEntry = depGraphLocal.find(rem);
 513
 514   if (depGraphEntry != depGraphLocal.end()) {
 515     reverseDep[depGraphEntry->second.first].erase(rem);
 516
 517     if (depGraphEntry->second.first != NonLocal &&
 518         depGraphEntry->second.first != None &&
 519         depGraphEntry->second.second) {
 520       // If we have dep info for rem, set them to it
 521       BasicBlock::iterator RI = depGraphEntry->second.first;
 522       RI++;
 523       newDep = RI;
 524     } else if ( (depGraphEntry->second.first == NonLocal ||
 525                  depGraphEntry->second.first == None ) &&
 526                depGraphEntry->second.second ) {
 527       // If we have a confirmed non-local flag, use it
 528       newDep = depGraphEntry->second.first;
 529     } else {
 530       // Otherwise, use the immediate successor of rem
 531       // NOTE: This is because, when getDependence is called, it will first
 532       // check the immediate predecessor of what is in the cache.
 533       BasicBlock::iterator RI = rem;
 534       RI++;
 535       newDep = RI;
 536     }
 537   } else {
 538     // Otherwise, use the immediate successor of rem
 539     // NOTE: This is because, when getDependence is called, it will first
 540     // check the immediate predecessor of what is in the cache.
 541     BasicBlock::iterator RI = rem;
 542     RI++;
 543     newDep = RI;
 544   }
 545
 546   SmallPtrSet<Instruction*, 4>& set = reverseDep[rem];
 547   for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 548        I != E; ++I) {
 549     // Insert the new dependencies
 550     // Mark it as unconfirmed as long as it is not the non-local flag
 551     depGraphLocal[*I] = std::make_pair(newDep, (newDep == NonLocal ||
 552                                                 newDep == None));
 553   }
 554
 555   depGraphLocal.erase(rem);
 556   reverseDep.erase(rem);
 557
 558   if (reverseDepNonLocal.count(rem)) {
 559     SmallPtrSet<Instruction*, 4>& set = reverseDepNonLocal[rem];
 560     for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 561          I != E; ++I)
 562       for (DenseMap<BasicBlock*, Value*>::iterator DI =
 563            depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end();
 564            DI != DE; ++DI)
 565         if (DI->second == rem)
 566           DI->second = Dirty;
 567
 568   }
 569
 570   reverseDepNonLocal.erase(rem);
 571   nonLocalDepMapType::iterator I = depGraphNonLocal.find(rem);
 572   if (I != depGraphNonLocal.end())
 573     depGraphNonLocal.erase(I);
 574
 575   getAnalysis<AliasAnalysis>().deleteValue(rem);
 576 }