lib/Analysis/MemoryDependenceAnalysis.cpp

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