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 #define DEBUG_TYPE "memdep"
  18 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
  19 #include "llvm/Constants.h"
  20 #include "llvm/Instructions.h"
  21 #include "llvm/Function.h"
  22 #include "llvm/Analysis/AliasAnalysis.h"
  23 #include "llvm/ADT/Statistic.h"
  24 #include "llvm/ADT/STLExtras.h"
  25 #include "llvm/Support/CFG.h"
  26 #include "llvm/Support/CommandLine.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Target/TargetData.h"
  29 using namespace llvm;
  30
  31 STATISTIC(NumCacheNonlocal, "Number of cached non-local responses");
  32 STATISTIC(NumUncacheNonlocal, "Number of uncached non-local responses");
  33
  34 char MemoryDependenceAnalysis::ID = 0;
  35
  36 // Register this pass...
  37 static RegisterPass<MemoryDependenceAnalysis> X("memdep",
  38                                      "Memory Dependence Analysis", false, true);
  39
  40 /// getAnalysisUsage - Does not modify anything.  It uses Alias Analysis.
  41 ///
  42 void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
  43   AU.setPreservesAll();
  44   AU.addRequiredTransitive<AliasAnalysis>();
  45   AU.addRequiredTransitive<TargetData>();
  46 }
  47
  48 /// getCallSiteDependency - Private helper for finding the local dependencies
  49 /// of a call site.
  50 MemDepResult MemoryDependenceAnalysis::
  51 getCallSiteDependency(CallSite C, BasicBlock::iterator ScanIt,
  52                       BasicBlock *BB) {
  53   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
  54   TargetData &TD = getAnalysis<TargetData>();
  55
  56   // Walk backwards through the block, looking for dependencies
  57   while (ScanIt != BB->begin()) {
  58     Instruction *Inst = --ScanIt;
  59
  60     // If this inst is a memory op, get the pointer it accessed
  61     Value *Pointer = 0;
  62     uint64_t PointerSize = 0;
  63     if (StoreInst *S = dyn_cast<StoreInst>(Inst)) {
  64       Pointer = S->getPointerOperand();
  65       PointerSize = TD.getTypeStoreSize(S->getOperand(0)->getType());
  66     } else if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) {
  67       Pointer = AI;
  68       if (ConstantInt *C = dyn_cast<ConstantInt>(AI->getArraySize()))
  69         // Use ABI size (size between elements), not store size (size of one
  70         // element without padding).
  71         PointerSize = C->getZExtValue() *
  72                       TD.getABITypeSize(AI->getAllocatedType());
  73       else
  74         PointerSize = ~0UL;
  75     } else if (VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
  76       Pointer = V->getOperand(0);
  77       PointerSize = TD.getTypeStoreSize(V->getType());
  78     } else if (FreeInst *F = dyn_cast<FreeInst>(Inst)) {
  79       Pointer = F->getPointerOperand();
  80
  81       // FreeInsts erase the entire structure
  82       PointerSize = ~0UL;
  83     } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) {
  84       if (AA.getModRefBehavior(CallSite::get(Inst)) ==
  85             AliasAnalysis::DoesNotAccessMemory)
  86         continue;
  87       return MemDepResult::get(Inst);
  88     } else
  89       continue;
  90
  91     if (AA.getModRefInfo(C, Pointer, PointerSize) != AliasAnalysis::NoModRef)
  92       return MemDepResult::get(Inst);
  93   }
  94
  95   // No dependence found.
  96   return MemDepResult::getNonLocal();
  97 }
  98
  99 /// getNonLocalDependency - Perform a full dependency query for the
 100 /// specified instruction, returning the set of blocks that the value is
 101 /// potentially live across.  The returned set of results will include a
 102 /// "NonLocal" result for all blocks where the value is live across.
 103 ///
 104 /// This method assumes the instruction returns a "nonlocal" dependency
 105 /// within its own block.
 106 ///
 107 void MemoryDependenceAnalysis::
 108 getNonLocalDependency(Instruction *QueryInst,
 109                       SmallVectorImpl<std::pair<BasicBlock*,
 110                                                       MemDepResult> > &Result) {
 111   assert(getDependency(QueryInst).isNonLocal() &&
 112      "getNonLocalDependency should only be used on insts with non-local deps!");
 113   DenseMap<BasicBlock*, DepResultTy> &Cache = NonLocalDeps[QueryInst];
 114
 115   /// DirtyBlocks - This is the set of blocks that need to be recomputed.  This
 116   /// can happen due to instructions being deleted etc.
 117   SmallVector<BasicBlock*, 32> DirtyBlocks;
 118
 119   if (!Cache.empty()) {
 120     // If we already have a partially computed set of results, scan them to
 121     // determine what is dirty, seeding our initial DirtyBlocks worklist.
 122     // FIXME: In the "don't need to be updated" case, this is expensive, why not
 123     // have a per-"cache" flag saying it is undirty?
 124     for (DenseMap<BasicBlock*, DepResultTy>::iterator I = Cache.begin(),
 125          E = Cache.end(); I != E; ++I)
 126       if (I->second.getInt() == Dirty)
 127         DirtyBlocks.push_back(I->first);
 128
 129     NumCacheNonlocal++;
 130   } else {
 131     // Seed DirtyBlocks with each of the preds of QueryInst's block.
 132     BasicBlock *QueryBB = QueryInst->getParent();
 133     DirtyBlocks.append(pred_begin(QueryBB), pred_end(QueryBB));
 134     NumUncacheNonlocal++;
 135   }
 136
 137   // Iterate while we still have blocks to update.
 138   while (!DirtyBlocks.empty()) {
 139     BasicBlock *DirtyBB = DirtyBlocks.back();
 140     DirtyBlocks.pop_back();
 141
 142     // Get the entry for this block.  Note that this relies on DepResultTy
 143     // default initializing to Dirty.
 144     DepResultTy &DirtyBBEntry = Cache[DirtyBB];
 145
 146     // If DirtyBBEntry isn't dirty, it ended up on the worklist multiple times.
 147     if (DirtyBBEntry.getInt() != Dirty) continue;
 148
 149     // Find out if this block has a local dependency for QueryInst.
 150     // FIXME: If the dirty entry has an instruction pointer, scan from it!
 151     // FIXME: Don't convert back and forth for MemDepResult <-> DepResultTy.
 152     DirtyBBEntry = ConvFromResult(getDependencyFrom(QueryInst, DirtyBB->end(),
 153                                                     DirtyBB));
 154
 155     // If the block has a dependency (i.e. it isn't completely transparent to
 156     // the value), remember it!
 157     if (DirtyBBEntry.getInt() != NonLocal) {
 158       // Keep the ReverseNonLocalDeps map up to date so we can efficiently
 159       // update this when we remove  instructions.
 160       if (Instruction *Inst = DirtyBBEntry.getPointer())
 161         ReverseNonLocalDeps[Inst].insert(QueryInst);
 162       continue;
 163     }
 164
 165     // If the block *is* completely transparent to the load, we need to check
 166     // the predecessors of this block.  Add them to our worklist.
 167     for (pred_iterator I = pred_begin(DirtyBB), E = pred_end(DirtyBB);
 168          I != E; ++I)
 169       DirtyBlocks.push_back(*I);
 170   }
 171
 172   // Copy the result into the output set.
 173   for (DenseMap<BasicBlock*, DepResultTy>::iterator I = Cache.begin(),
 174        E = Cache.end(); I != E; ++I)
 175     Result.push_back(std::make_pair(I->first, ConvToResult(I->second)));
 176 }
 177
 178 /// getDependency - Return the instruction on which a memory operation
 179 /// depends.  The local parameter indicates if the query should only
 180 /// evaluate dependencies within the same basic block.
 181 MemDepResult MemoryDependenceAnalysis::
 182 getDependencyFrom(Instruction *QueryInst, BasicBlock::iterator ScanIt,
 183                   BasicBlock *BB) {
 184   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
 185   TargetData &TD = getAnalysis<TargetData>();
 186
 187   // Get the pointer value for which dependence will be determined
 188   Value *MemPtr = 0;
 189   uint64_t MemSize = 0;
 190   bool MemVolatile = false;
 191
 192   if (StoreInst* S = dyn_cast<StoreInst>(QueryInst)) {
 193     MemPtr = S->getPointerOperand();
 194     MemSize = TD.getTypeStoreSize(S->getOperand(0)->getType());
 195     MemVolatile = S->isVolatile();
 196   } else if (LoadInst* L = dyn_cast<LoadInst>(QueryInst)) {
 197     MemPtr = L->getPointerOperand();
 198     MemSize = TD.getTypeStoreSize(L->getType());
 199     MemVolatile = L->isVolatile();
 200   } else if (VAArgInst* V = dyn_cast<VAArgInst>(QueryInst)) {
 201     MemPtr = V->getOperand(0);
 202     MemSize = TD.getTypeStoreSize(V->getType());
 203   } else if (FreeInst* F = dyn_cast<FreeInst>(QueryInst)) {
 204     MemPtr = F->getPointerOperand();
 205     // FreeInsts erase the entire structure, not just a field.
 206     MemSize = ~0UL;
 207   } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst))
 208     return getCallSiteDependency(CallSite::get(QueryInst), ScanIt, BB);
 209   else  // Non-memory instructions depend on nothing.
 210     return MemDepResult::getNone();
 211
 212   // Walk backwards through the basic block, looking for dependencies
 213   while (ScanIt != BB->begin()) {
 214     Instruction *Inst = --ScanIt;
 215
 216     // If the access is volatile and this is a volatile load/store, return a
 217     // dependence.
 218     if (MemVolatile &&
 219         ((isa<LoadInst>(Inst) && cast<LoadInst>(Inst)->isVolatile()) ||
 220          (isa<StoreInst>(Inst) && cast<StoreInst>(Inst)->isVolatile())))
 221       return MemDepResult::get(Inst);
 222
 223     // MemDep is broken w.r.t. loads: it says that two loads of the same pointer
 224     // depend on each other.  :(
 225     // FIXME: ELIMINATE THIS!
 226     if (LoadInst *L = dyn_cast<LoadInst>(Inst)) {
 227       Value *Pointer = L->getPointerOperand();
 228       uint64_t PointerSize = TD.getTypeStoreSize(L->getType());
 229
 230       // If we found a pointer, check if it could be the same as our pointer
 231       AliasAnalysis::AliasResult R =
 232         AA.alias(Pointer, PointerSize, MemPtr, MemSize);
 233
 234       if (R == AliasAnalysis::NoAlias)
 235         continue;
 236
 237       // May-alias loads don't depend on each other without a dependence.
 238       if (isa<LoadInst>(QueryInst) && R == AliasAnalysis::MayAlias)
 239         continue;
 240       return MemDepResult::get(Inst);
 241     }
 242
 243     // FIXME: This claims that an access depends on the allocation.  This may
 244     // make sense, but is dubious at best.  It would be better to fix GVN to
 245     // handle a 'None' Query.
 246     if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) {
 247       Value *Pointer = AI;
 248       uint64_t PointerSize;
 249       if (ConstantInt *C = dyn_cast<ConstantInt>(AI->getArraySize()))
 250         // Use ABI size (size between elements), not store size (size of one
 251         // element without padding).
 252         PointerSize = C->getZExtValue() *
 253           TD.getABITypeSize(AI->getAllocatedType());
 254       else
 255         PointerSize = ~0UL;
 256
 257       AliasAnalysis::AliasResult R =
 258         AA.alias(Pointer, PointerSize, MemPtr, MemSize);
 259
 260       if (R == AliasAnalysis::NoAlias)
 261         continue;
 262       return MemDepResult::get(Inst);
 263     }
 264
 265
 266     // See if this instruction mod/ref's the pointer.
 267     AliasAnalysis::ModRefResult MRR = AA.getModRefInfo(Inst, MemPtr, MemSize);
 268
 269     if (MRR == AliasAnalysis::NoModRef)
 270       continue;
 271
 272     // Loads don't depend on read-only instructions.
 273     if (isa<LoadInst>(QueryInst) && MRR == AliasAnalysis::Ref)
 274       continue;
 275
 276     // Otherwise, there is a dependence.
 277     return MemDepResult::get(Inst);
 278   }
 279
 280   // If we found nothing, return the non-local flag.
 281   return MemDepResult::getNonLocal();
 282 }
 283
 284 /// getDependency - Return the instruction on which a memory operation
 285 /// depends.
 286 MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
 287   Instruction *ScanPos = QueryInst;
 288
 289   // Check for a cached result
 290   DepResultTy &LocalCache = LocalDeps[QueryInst];
 291
 292   // If the cached entry is non-dirty, just return it.
 293   if (LocalCache.getInt() != Dirty)
 294     return ConvToResult(LocalCache);
 295
 296   // Otherwise, if we have a dirty entry, we know we can start the scan at that
 297   // instruction, which may save us some work.
 298   if (Instruction *Inst = LocalCache.getPointer())
 299     ScanPos = Inst;
 300
 301   // Do the scan.
 302   MemDepResult Res =
 303     getDependencyFrom(QueryInst, ScanPos, QueryInst->getParent());
 304
 305   // Remember the result!
 306   // FIXME: Don't convert back and forth!  Make a shared helper function.
 307   LocalCache = ConvFromResult(Res);
 308   if (Instruction *I = Res.getInst())
 309     ReverseLocalDeps[I].insert(QueryInst);
 310
 311   return Res;
 312 }
 313
 314
 315 /// dropInstruction - Remove an instruction from the analysis, making
 316 /// absolutely conservative assumptions when updating the cache.  This is
 317 /// useful, for example when an instruction is changed rather than removed.
 318 void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) {
 319   LocalDepMapType::iterator depGraphEntry = LocalDeps.find(drop);
 320   if (depGraphEntry != LocalDeps.end())
 321     if (Instruction *Inst = depGraphEntry->second.getPointer())
 322       ReverseLocalDeps[Inst].erase(drop);
 323
 324   // Drop dependency information for things that depended on this instr
 325   SmallPtrSet<Instruction*, 4>& set = ReverseLocalDeps[drop];
 326   for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 327        I != E; ++I)
 328     LocalDeps.erase(*I);
 329
 330   LocalDeps.erase(drop);
 331   ReverseLocalDeps.erase(drop);
 332
 333   for (DenseMap<BasicBlock*, DepResultTy>::iterator DI =
 334          NonLocalDeps[drop].begin(), DE = NonLocalDeps[drop].end();
 335        DI != DE; ++DI)
 336     if (Instruction *Inst = DI->second.getPointer())
 337       ReverseNonLocalDeps[Inst].erase(drop);
 338
 339   if (ReverseNonLocalDeps.count(drop)) {
 340     SmallPtrSet<Instruction*, 4>& set =
 341       ReverseNonLocalDeps[drop];
 342     for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 343          I != E; ++I)
 344       for (DenseMap<BasicBlock*, DepResultTy>::iterator DI =
 345            NonLocalDeps[*I].begin(), DE = NonLocalDeps[*I].end();
 346            DI != DE; ++DI)
 347         if (DI->second == DepResultTy(drop, Normal))
 348           // FIXME: Why not remember the old insertion point??
 349           DI->second = DepResultTy(0, Dirty);
 350   }
 351
 352   ReverseNonLocalDeps.erase(drop);
 353   NonLocalDeps.erase(drop);
 354 }
 355
 356 /// removeInstruction - Remove an instruction from the dependence analysis,
 357 /// updating the dependence of instructions that previously depended on it.
 358 /// This method attempts to keep the cache coherent using the reverse map.
 359 void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
 360   // Walk through the Non-local dependencies, removing this one as the value
 361   // for any cached queries.
 362   for (DenseMap<BasicBlock*, DepResultTy>::iterator DI =
 363        NonLocalDeps[RemInst].begin(), DE = NonLocalDeps[RemInst].end();
 364        DI != DE; ++DI)
 365     if (Instruction *Inst = DI->second.getPointer())
 366       ReverseNonLocalDeps[Inst].erase(RemInst);
 367
 368   // Shortly after this, we will look for things that depend on RemInst.  In
 369   // order to update these, we'll need a new dependency to base them on.  We
 370   // could completely delete any entries that depend on this, but it is better
 371   // to make a more accurate approximation where possible.  Compute that better
 372   // approximation if we can.
 373   DepResultTy NewDependency;
 374
 375   // If we have a cached local dependence query for this instruction, remove it.
 376   //
 377   LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
 378   if (LocalDepEntry != LocalDeps.end()) {
 379     DepResultTy LocalDep = LocalDepEntry->second;
 380
 381     // Remove this local dependency info.
 382     LocalDeps.erase(LocalDepEntry);
 383
 384     // Remove us from DepInst's reverse set now that the local dep info is gone.
 385     if (Instruction *Inst = LocalDep.getPointer())
 386       ReverseLocalDeps[Inst].erase(RemInst);
 387
 388     // If we have unconfirmed info, don't trust it.
 389     if (LocalDep.getInt() != Dirty) {
 390       // If we have a confirmed non-local flag, use it.
 391       if (LocalDep.getInt() == NonLocal || LocalDep.getInt() == None) {
 392         // The only time this dependency is confirmed is if it is non-local.
 393         NewDependency = LocalDep;
 394       } else {
 395         // If we have dep info for RemInst, set them to it.
 396         Instruction *NDI = next(BasicBlock::iterator(LocalDep.getPointer()));
 397         if (NDI != RemInst) // Don't use RemInst for the new dependency!
 398           NewDependency = DepResultTy(NDI, Dirty);
 399       }
 400     }
 401   }
 402
 403   // If we don't already have a local dependency answer for this instruction,
 404   // use the immediate successor of RemInst.  We use the successor because
 405   // getDependence starts by checking the immediate predecessor of what is in
 406   // the cache.
 407   if (NewDependency == DepResultTy(0, Dirty))
 408     NewDependency = DepResultTy(next(BasicBlock::iterator(RemInst)), Dirty);
 409
 410   // Loop over all of the things that depend on the instruction we're removing.
 411   //
 412   ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
 413   if (ReverseDepIt != ReverseLocalDeps.end()) {
 414     SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second;
 415     for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(),
 416          E = ReverseDeps.end(); I != E; ++I) {
 417       Instruction *InstDependingOnRemInst = *I;
 418
 419       // If we thought the instruction depended on itself (possible for
 420       // unconfirmed dependencies) ignore the update.
 421       if (InstDependingOnRemInst == RemInst) continue;
 422
 423       // Insert the new dependencies.
 424       LocalDeps[InstDependingOnRemInst] = NewDependency;
 425
 426       // If our NewDependency is an instruction, make sure to remember that new
 427       // things depend on it.
 428       if (Instruction *Inst = NewDependency.getPointer())
 429         ReverseLocalDeps[Inst].insert(InstDependingOnRemInst);
 430     }
 431     ReverseLocalDeps.erase(RemInst);
 432   }
 433
 434   ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
 435   if (ReverseDepIt != ReverseNonLocalDeps.end()) {
 436     SmallPtrSet<Instruction*, 4>& set = ReverseDepIt->second;
 437     for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 438          I != E; ++I)
 439       for (DenseMap<BasicBlock*, DepResultTy>::iterator
 440            DI = NonLocalDeps[*I].begin(), DE = NonLocalDeps[*I].end();
 441            DI != DE; ++DI)
 442         if (DI->second == DepResultTy(RemInst, Normal))
 443           // FIXME: Why not remember the old insertion point??
 444           DI->second = DepResultTy(0, Dirty);
 445     ReverseNonLocalDeps.erase(ReverseDepIt);
 446   }
 447
 448   NonLocalDeps.erase(RemInst);
 449
 450   getAnalysis<AliasAnalysis>().deleteValue(RemInst);
 451
 452   DEBUG(verifyRemoved(RemInst));
 453 }
 454
 455 /// verifyRemoved - Verify that the specified instruction does not occur
 456 /// in our internal data structures.
 457 void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const {
 458   for (LocalDepMapType::const_iterator I = LocalDeps.begin(),
 459        E = LocalDeps.end(); I != E; ++I) {
 460     assert(I->first != D && "Inst occurs in data structures");
 461     assert(I->second.getPointer() != D &&
 462            "Inst occurs in data structures");
 463   }
 464
 465   for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(),
 466        E = NonLocalDeps.end(); I != E; ++I) {
 467     assert(I->first != D && "Inst occurs in data structures");
 468     for (DenseMap<BasicBlock*, DepResultTy>::iterator II = I->second.begin(),
 469          EE = I->second.end(); II  != EE; ++II)
 470       assert(II->second.getPointer() != D && "Inst occurs in data structures");
 471   }
 472
 473   for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(),
 474        E = ReverseLocalDeps.end(); I != E; ++I)
 475     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
 476          EE = I->second.end(); II != EE; ++II)
 477       assert(*II != D && "Inst occurs in data structures");
 478
 479   for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(),
 480        E = ReverseNonLocalDeps.end();
 481        I != E; ++I)
 482     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
 483          EE = I->second.end(); II != EE; ++II)
 484       assert(*II != D && "Inst occurs in data structures");
 485 }