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