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