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