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", false, true);
  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()->begin();
 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->begin();
 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         if (!start && !block) {
 139           cachedResult.first = QI;
 140           cachedResult.second = true;
 141           reverseDep[QI].insert(C.getInstruction());
 142         }
 143         return QI;
 144       } else {
 145         continue;
 146       }
 147     } else
 148       continue;
 149
 150     if (AA.getModRefInfo(C, pointer, pointerSize) != AliasAnalysis::NoModRef) {
 151       if (!start && !block) {
 152         cachedResult.first = QI;
 153         cachedResult.second = true;
 154         reverseDep[QI].insert(C.getInstruction());
 155       }
 156       return QI;
 157     }
 158   }
 159
 160   // No dependence found
 161   cachedResult.first = NonLocal;
 162   cachedResult.second = true;
 163   reverseDep[NonLocal].insert(C.getInstruction());
 164   return NonLocal;
 165 }
 166
 167 /// nonLocalHelper - Private helper used to calculate non-local dependencies
 168 /// by doing DFS on the predecessors of a block to find its dependencies
 169 void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
 170                                               BasicBlock* block,
 171                                          DenseMap<BasicBlock*, Value*>& resp) {
 172   // Set of blocks that we've already visited in our DFS
 173   SmallPtrSet<BasicBlock*, 4> visited;
 174   // If we're updating a dirtied cache entry, we don't need to reprocess
 175   // already computed entries.
 176   for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(),
 177        E = resp.end(); I != E; ++I)
 178     if (I->second != Dirty)
 179       visited.insert(I->first);
 180
 181   // Current stack of the DFS
 182   SmallVector<BasicBlock*, 4> stack;
 183   for (pred_iterator PI = pred_begin(block), PE = pred_end(block);
 184        PI != PE; ++PI)
 185     stack.push_back(*PI);
 186
 187   // Do a basic DFS
 188   while (!stack.empty()) {
 189     BasicBlock* BB = stack.back();
 190
 191     // If we've already visited this block, no need to revist
 192     if (visited.count(BB)) {
 193       stack.pop_back();
 194       continue;
 195     }
 196
 197     // If we find a new block with a local dependency for query,
 198     // then we insert the new dependency and backtrack.
 199     if (BB != block) {
 200       visited.insert(BB);
 201
 202       Instruction* localDep = getDependency(query, 0, BB);
 203       if (localDep != NonLocal) {
 204         resp.insert(std::make_pair(BB, localDep));
 205         stack.pop_back();
 206
 207         continue;
 208       }
 209     // If we re-encounter the starting block, we still need to search it
 210     // because there might be a dependency in the starting block AFTER
 211     // the position of the query.  This is necessary to get loops right.
 212     } else if (BB == block) {
 213       visited.insert(BB);
 214
 215       Instruction* localDep = getDependency(query, 0, BB);
 216       if (localDep != query)
 217         resp.insert(std::make_pair(BB, localDep));
 218
 219       stack.pop_back();
 220
 221       continue;
 222     }
 223
 224     // If we didn't find anything, recurse on the precessors of this block
 225     // Only do this for blocks with a small number of predecessors.
 226     bool predOnStack = false;
 227     bool inserted = false;
 228     if (std::distance(pred_begin(BB), pred_end(BB)) <= PredLimit) {
 229       for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 230            PI != PE; ++PI)
 231         if (!visited.count(*PI)) {
 232           stack.push_back(*PI);
 233           inserted = true;
 234         } else
 235           predOnStack = true;
 236     }
 237
 238     // If we inserted a new predecessor, then we'll come back to this block
 239     if (inserted)
 240       continue;
 241     // If we didn't insert because we have no predecessors, then this
 242     // query has no dependency at all.
 243     else if (!inserted && !predOnStack) {
 244       resp.insert(std::make_pair(BB, None));
 245     // If we didn't insert because our predecessors are already on the stack,
 246     // then we might still have a dependency, but it will be discovered during
 247     // backtracking.
 248     } else if (!inserted && predOnStack){
 249       resp.insert(std::make_pair(BB, NonLocal));
 250     }
 251
 252     stack.pop_back();
 253   }
 254 }
 255
 256 /// getNonLocalDependency - Fills the passed-in map with the non-local
 257 /// dependencies of the queries.  The map will contain NonLocal for
 258 /// blocks between the query and its dependencies.
 259 void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
 260                                          DenseMap<BasicBlock*, Value*>& resp) {
 261   if (depGraphNonLocal.count(query)) {
 262     DenseMap<BasicBlock*, Value*>& cached = depGraphNonLocal[query];
 263     NumCacheNonlocal++;
 264
 265     SmallVector<BasicBlock*, 4> dirtied;
 266     for (DenseMap<BasicBlock*, Value*>::iterator I = cached.begin(),
 267          E = cached.end(); I != E; ++I)
 268       if (I->second == Dirty)
 269         dirtied.push_back(I->first);
 270
 271     for (SmallVector<BasicBlock*, 4>::iterator I = dirtied.begin(),
 272          E = dirtied.end(); I != E; ++I) {
 273       Instruction* localDep = getDependency(query, 0, *I);
 274       if (localDep != NonLocal)
 275         cached[*I] = localDep;
 276       else {
 277         cached.erase(*I);
 278         nonLocalHelper(query, *I, cached);
 279       }
 280     }
 281
 282     resp = cached;
 283
 284     return;
 285   } else
 286     NumUncacheNonlocal++;
 287
 288   // If not, go ahead and search for non-local deps.
 289   nonLocalHelper(query, query->getParent(), resp);
 290
 291   // Update the non-local dependency cache
 292   for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(), E = resp.end();
 293        I != E; ++I) {
 294     depGraphNonLocal[query].insert(*I);
 295     reverseDepNonLocal[I->second].insert(query);
 296   }
 297 }
 298
 299 /// getDependency - Return the instruction on which a memory operation
 300 /// depends.  The local parameter indicates if the query should only
 301 /// evaluate dependencies within the same basic block.
 302 Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
 303                                                      Instruction* start,
 304                                                      BasicBlock* block) {
 305   // Start looking for dependencies with the queried inst
 306   BasicBlock::iterator QI = query;
 307
 308   // Check for a cached result
 309   std::pair<Instruction*, bool>& cachedResult = depGraphLocal[query];
 310   // If we have a _confirmed_ cached entry, return it
 311   if (!block && !start) {
 312     if (cachedResult.second)
 313       return cachedResult.first;
 314     else if (cachedResult.first && cachedResult.first != NonLocal)
 315       // If we have an unconfirmed cached entry, we can start our search from there
 316       QI = cachedResult.first;
 317   }
 318
 319   if (start)
 320     QI = start;
 321   else if (!start && block)
 322     QI = block->end();
 323
 324   AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
 325   TargetData& TD = getAnalysis<TargetData>();
 326
 327   // Get the pointer value for which dependence will be determined
 328   Value* dependee = 0;
 329   uint64_t dependeeSize = 0;
 330   bool queryIsVolatile = false;
 331   if (StoreInst* S = dyn_cast<StoreInst>(query)) {
 332     dependee = S->getPointerOperand();
 333     dependeeSize = TD.getTypeStoreSize(S->getOperand(0)->getType());
 334     queryIsVolatile = S->isVolatile();
 335   } else if (LoadInst* L = dyn_cast<LoadInst>(query)) {
 336     dependee = L->getPointerOperand();
 337     dependeeSize = TD.getTypeStoreSize(L->getType());
 338     queryIsVolatile = L->isVolatile();
 339   } else if (VAArgInst* V = dyn_cast<VAArgInst>(query)) {
 340     dependee = V->getOperand(0);
 341     dependeeSize = TD.getTypeStoreSize(V->getType());
 342   } else if (FreeInst* F = dyn_cast<FreeInst>(query)) {
 343     dependee = F->getPointerOperand();
 344
 345     // FreeInsts erase the entire structure, not just a field
 346     dependeeSize = ~0UL;
 347   } else if (CallSite::get(query).getInstruction() != 0)
 348     return getCallSiteDependency(CallSite::get(query), start, block);
 349   else if (isa<AllocationInst>(query))
 350     return None;
 351   else
 352     return None;
 353
 354   BasicBlock::iterator blockBegin = block ? block->begin()
 355                                           : query->getParent()->begin();
 356
 357   // Walk backwards through the basic block, looking for dependencies
 358   while (QI != blockBegin) {
 359     --QI;
 360
 361     // If this inst is a memory op, get the pointer it accessed
 362     Value* pointer = 0;
 363     uint64_t pointerSize = 0;
 364     if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
 365       // All volatile loads/stores depend on each other
 366       if (queryIsVolatile && S->isVolatile()) {
 367         if (!start && !block) {
 368           cachedResult.first = S;
 369           cachedResult.second = true;
 370           reverseDep[S].insert(query);
 371         }
 372
 373         return S;
 374       }
 375
 376       pointer = S->getPointerOperand();
 377       pointerSize = TD.getTypeStoreSize(S->getOperand(0)->getType());
 378     } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
 379       // All volatile loads/stores depend on each other
 380       if (queryIsVolatile && L->isVolatile()) {
 381         if (!start && !block) {
 382           cachedResult.first = L;
 383           cachedResult.second = true;
 384           reverseDep[L].insert(query);
 385         }
 386
 387         return L;
 388       }
 389
 390       pointer = L->getPointerOperand();
 391       pointerSize = TD.getTypeStoreSize(L->getType());
 392     } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
 393       pointer = AI;
 394       if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
 395         pointerSize = C->getZExtValue() * \
 396                       TD.getABITypeSize(AI->getAllocatedType());
 397       else
 398         pointerSize = ~0UL;
 399     } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
 400       pointer = V->getOperand(0);
 401       pointerSize = TD.getTypeStoreSize(V->getType());
 402     } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
 403       pointer = F->getPointerOperand();
 404
 405       // FreeInsts erase the entire structure
 406       pointerSize = ~0UL;
 407     } else if (CallSite::get(QI).getInstruction() != 0) {
 408       // Call insts need special handling. Check if they can modify our pointer
 409       AliasAnalysis::ModRefResult MR = AA.getModRefInfo(CallSite::get(QI),
 410                                                       dependee, dependeeSize);
 411
 412       if (MR != AliasAnalysis::NoModRef) {
 413         // Loads don't depend on read-only calls
 414         if (isa<LoadInst>(query) && MR == AliasAnalysis::Ref)
 415           continue;
 416
 417         if (!start && !block) {
 418           cachedResult.first = QI;
 419           cachedResult.second = true;
 420           reverseDep[QI].insert(query);
 421         }
 422
 423         return QI;
 424       } else {
 425         continue;
 426       }
 427     }
 428
 429     // If we found a pointer, check if it could be the same as our pointer
 430     if (pointer) {
 431       AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize,
 432                                               dependee, dependeeSize);
 433
 434       if (R != AliasAnalysis::NoAlias) {
 435         // May-alias loads don't depend on each other
 436         if (isa<LoadInst>(query) && isa<LoadInst>(QI) &&
 437             R == AliasAnalysis::MayAlias)
 438           continue;
 439
 440         if (!start && !block) {
 441           cachedResult.first = QI;
 442           cachedResult.second = true;
 443           reverseDep[QI].insert(query);
 444         }
 445
 446         return QI;
 447       }
 448     }
 449   }
 450
 451   // If we found nothing, return the non-local flag
 452   if (!start && !block) {
 453     cachedResult.first = NonLocal;
 454     cachedResult.second = true;
 455     reverseDep[NonLocal].insert(query);
 456   }
 457
 458   return NonLocal;
 459 }
 460
 461 /// dropInstruction - Remove an instruction from the analysis, making
 462 /// absolutely conservative assumptions when updating the cache.  This is
 463 /// useful, for example when an instruction is changed rather than removed.
 464 void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) {
 465   depMapType::iterator depGraphEntry = depGraphLocal.find(drop);
 466   if (depGraphEntry != depGraphLocal.end())
 467     reverseDep[depGraphEntry->second.first].erase(drop);
 468
 469   // Drop dependency information for things that depended on this instr
 470   SmallPtrSet<Instruction*, 4>& set = reverseDep[drop];
 471   for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 472        I != E; ++I)
 473     depGraphLocal.erase(*I);
 474
 475   depGraphLocal.erase(drop);
 476   reverseDep.erase(drop);
 477
 478   for (DenseMap<BasicBlock*, Value*>::iterator DI =
 479        depGraphNonLocal[drop].begin(), DE = depGraphNonLocal[drop].end();
 480        DI != DE; ++DI)
 481     if (DI->second != None)
 482       reverseDepNonLocal[DI->second].erase(drop);
 483
 484   if (reverseDepNonLocal.count(drop)) {
 485     SmallPtrSet<Instruction*, 4>& set = reverseDepNonLocal[drop];
 486     for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 487          I != E; ++I)
 488       for (DenseMap<BasicBlock*, Value*>::iterator DI =
 489            depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end();
 490            DI != DE; ++DI)
 491         if (DI->second == drop)
 492           DI->second = Dirty;
 493   }
 494
 495   reverseDepNonLocal.erase(drop);
 496   nonLocalDepMapType::iterator I = depGraphNonLocal.find(drop);
 497   if (I != depGraphNonLocal.end())
 498     depGraphNonLocal.erase(I);
 499 }
 500
 501 /// removeInstruction - Remove an instruction from the dependence analysis,
 502 /// updating the dependence of instructions that previously depended on it.
 503 /// This method attempts to keep the cache coherent using the reverse map.
 504 void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
 505   // Figure out the new dep for things that currently depend on rem
 506   Instruction* newDep = NonLocal;
 507
 508   for (DenseMap<BasicBlock*, Value*>::iterator DI =
 509        depGraphNonLocal[rem].begin(), DE = depGraphNonLocal[rem].end();
 510        DI != DE; ++DI)
 511     if (DI->second != None)
 512       reverseDepNonLocal[DI->second].erase(rem);
 513
 514   depMapType::iterator depGraphEntry = depGraphLocal.find(rem);
 515
 516   if (depGraphEntry != depGraphLocal.end()) {
 517     reverseDep[depGraphEntry->second.first].erase(rem);
 518
 519     if (depGraphEntry->second.first != NonLocal &&
 520         depGraphEntry->second.first != None &&
 521         depGraphEntry->second.second) {
 522       // If we have dep info for rem, set them to it
 523       BasicBlock::iterator RI = depGraphEntry->second.first;
 524       RI++;
 525       newDep = RI;
 526     } else if ( (depGraphEntry->second.first == NonLocal ||
 527                  depGraphEntry->second.first == None ) &&
 528                depGraphEntry->second.second ) {
 529       // If we have a confirmed non-local flag, use it
 530       newDep = depGraphEntry->second.first;
 531     } else {
 532       // Otherwise, use the immediate successor of rem
 533       // NOTE: This is because, when getDependence is called, it will first
 534       // check the immediate predecessor of what is in the cache.
 535       BasicBlock::iterator RI = rem;
 536       RI++;
 537       newDep = RI;
 538     }
 539   } else {
 540     // Otherwise, use the immediate successor of rem
 541     // NOTE: This is because, when getDependence is called, it will first
 542     // check the immediate predecessor of what is in the cache.
 543     BasicBlock::iterator RI = rem;
 544     RI++;
 545     newDep = RI;
 546   }
 547
 548   SmallPtrSet<Instruction*, 4>& set = reverseDep[rem];
 549   for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 550        I != E; ++I) {
 551     // Insert the new dependencies
 552     // Mark it as unconfirmed as long as it is not the non-local flag
 553     depGraphLocal[*I] = std::make_pair(newDep, (newDep == NonLocal ||
 554                                                 newDep == None));
 555   }
 556
 557   depGraphLocal.erase(rem);
 558   reverseDep.erase(rem);
 559
 560   if (reverseDepNonLocal.count(rem)) {
 561     SmallPtrSet<Instruction*, 4>& set = reverseDepNonLocal[rem];
 562     for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 563          I != E; ++I)
 564       for (DenseMap<BasicBlock*, Value*>::iterator DI =
 565            depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end();
 566            DI != DE; ++DI)
 567         if (DI->second == rem)
 568           DI->second = Dirty;
 569
 570   }
 571
 572   reverseDepNonLocal.erase(rem);
 573   nonLocalDepMapType::iterator I = depGraphNonLocal.find(rem);
 574   if (I != depGraphNonLocal.end())
 575     depGraphNonLocal.erase(I);
 576
 577   getAnalysis<AliasAnalysis>().deleteValue(rem);
 578 }