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* MemoryDependenceAnalysis::NonLocal = (Instruction*)-2;
  30 Instruction* MemoryDependenceAnalysis::None = (Instruction*)-3;
  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 // Find the dependency of a CallSite
  45 Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, Instruction* start,
  46                                                              bool local) {
  47   assert(local && "Non-local memory dependence analysis not yet implemented");
  48
  49   AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
  50   TargetData& TD = getAnalysis<TargetData>();
  51   BasicBlock::iterator blockBegin = C.getInstruction()->getParent()->begin();
  52   BasicBlock::iterator QI = C.getInstruction();
  53
  54   while (QI != blockBegin) {
  55     --QI;
  56
  57     // If this inst is a memory op, get the pointer it accessed
  58     Value* pointer = 0;
  59     uint64_t pointerSize = 0;
  60     if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
  61       pointer = S->getPointerOperand();
  62       pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
  63     } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
  64       pointer = L->getPointerOperand();
  65       pointerSize = TD.getTypeSize(L->getType());
  66     } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
  67       pointer = AI;
  68       if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
  69         pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType());
  70       else
  71         pointerSize = ~0UL;
  72     } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
  73       pointer = V->getOperand(0);
  74       pointerSize = TD.getTypeSize(V->getType());
  75     } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
  76       pointer = F->getPointerOperand();
  77
  78       // FreeInsts erase the entire structure
  79       pointerSize = ~0UL;
  80     } else if (CallSite::get(QI).getInstruction() != 0) {
  81       if (AA.getModRefInfo(C, CallSite::get(QI)) != AliasAnalysis::NoModRef) {
  82         depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(QI, true)));
  83         reverseDep.insert(std::make_pair(QI, C.getInstruction()));
  84         return QI;
  85       } else {
  86         continue;
  87       }
  88     } else
  89       continue;
  90
  91     if (AA.getModRefInfo(C, pointer, pointerSize) != AliasAnalysis::NoModRef) {
  92       depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(QI, true)));
  93       reverseDep.insert(std::make_pair(QI, C.getInstruction()));
  94       return QI;
  95     }
  96   }
  97
  98   // No dependence found
  99   depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(NonLocal, true)));
 100   reverseDep.insert(std::make_pair(NonLocal, C.getInstruction()));
 101   return NonLocal;
 102 }
 103
 104 void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
 105                                               BasicBlock* block,
 106                                               DenseMap<BasicBlock*, Value*>& resp) {
 107   SmallPtrSet<BasicBlock*, 4> visited;
 108   SmallVector<BasicBlock*, 4> stack;
 109   stack.push_back(block);
 110
 111   while (!stack.empty()) {
 112     BasicBlock* BB = stack.back();
 113
 114     if (visited.count(BB)) {
 115       stack.pop_back();
 116       continue;
 117     }
 118
 119     if (BB != block) {
 120       visited.insert(BB);
 121
 122       Instruction* localDep = getDependency(query, 0, BB);
 123       if (localDep != NonLocal) {
 124         resp.insert(std::make_pair(BB, localDep));
 125         stack.pop_back();
 126
 127         continue;
 128       }
 129     } else if (BB == block && stack.size() > 1) {
 130       visited.insert(BB);
 131
 132       Instruction* localDep = getDependency(query, 0, BB);
 133       if (localDep != query)
 134         resp.insert(std::make_pair(BB, localDep));
 135
 136       stack.pop_back();
 137
 138       continue;
 139     }
 140
 141     bool predOnStack = false;
 142     bool inserted = false;
 143     for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 144          PI != PE; ++PI)
 145       if (!visited.count(*PI)) {
 146         stack.push_back(*PI);
 147         inserted = true;
 148       } else
 149         predOnStack = true;
 150
 151     if (inserted)
 152       continue;
 153     else if (!inserted && !predOnStack) {
 154       resp.insert(std::make_pair(BB, None));
 155     } else if (!inserted && predOnStack){
 156       resp.insert(std::make_pair(BB, NonLocal));
 157     }
 158
 159     stack.pop_back();
 160   }
 161 }
 162
 163 void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
 164                                                      DenseMap<BasicBlock*, Value*>& resp) {
 165   Instruction* localDep = getDependency(query);
 166   if (localDep != NonLocal) {
 167     resp.insert(std::make_pair(query->getParent(), localDep));
 168     return;
 169   }
 170
 171   nonLocalHelper(query, query->getParent(), resp);
 172 }
 173
 174 /// getDependency - Return the instruction on which a memory operation
 175 /// depends.  The local paramter indicates if the query should only
 176 /// evaluate dependencies within the same basic block.
 177 Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
 178                                                      Instruction* start,
 179                                                      BasicBlock* block) {
 180   // Start looking for dependencies with the queried inst
 181   BasicBlock::iterator QI = query;
 182
 183   // Check for a cached result
 184   std::pair<Instruction*, bool> cachedResult = depGraphLocal[query];
 185   // If we have a _confirmed_ cached entry, return it
 186   if (cachedResult.second)
 187     return cachedResult.first;
 188   else if (cachedResult.first && cachedResult.first != NonLocal)
 189   // If we have an unconfirmed cached entry, we can start our search from there
 190     QI = cachedResult.first;
 191
 192   if (start)
 193     QI = start;
 194   else if (!start && block)
 195     QI = block->end();
 196
 197   AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
 198   TargetData& TD = getAnalysis<TargetData>();
 199
 200   // Get the pointer value for which dependence will be determined
 201   Value* dependee = 0;
 202   uint64_t dependeeSize = 0;
 203   bool queryIsVolatile = false;
 204   if (StoreInst* S = dyn_cast<StoreInst>(query)) {
 205     dependee = S->getPointerOperand();
 206     dependeeSize = TD.getTypeSize(S->getOperand(0)->getType());
 207     queryIsVolatile = S->isVolatile();
 208   } else if (LoadInst* L = dyn_cast<LoadInst>(query)) {
 209     dependee = L->getPointerOperand();
 210     dependeeSize = TD.getTypeSize(L->getType());
 211     queryIsVolatile = L->isVolatile();
 212   } else if (VAArgInst* V = dyn_cast<VAArgInst>(query)) {
 213     dependee = V->getOperand(0);
 214     dependeeSize = TD.getTypeSize(V->getType());
 215   } else if (FreeInst* F = dyn_cast<FreeInst>(query)) {
 216     dependee = F->getPointerOperand();
 217
 218     // FreeInsts erase the entire structure, not just a field
 219     dependeeSize = ~0UL;
 220   } else if (CallSite::get(query).getInstruction() != 0)
 221     return getCallSiteDependency(CallSite::get(query), start);
 222   else if (isa<AllocationInst>(query))
 223     return None;
 224   else
 225     return None;
 226
 227   BasicBlock::iterator blockBegin = block ? block->begin()
 228                                           : query->getParent()->begin();
 229
 230   while (QI != blockBegin) {
 231     --QI;
 232
 233     // If this inst is a memory op, get the pointer it accessed
 234     Value* pointer = 0;
 235     uint64_t pointerSize = 0;
 236     if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
 237       // All volatile loads/stores depend on each other
 238       if (queryIsVolatile && S->isVolatile()) {
 239         if (!start || block) {
 240           depGraphLocal.insert(std::make_pair(query, std::make_pair(S, true)));
 241           reverseDep.insert(std::make_pair(S, query));
 242         }
 243
 244         return S;
 245       }
 246
 247       pointer = S->getPointerOperand();
 248       pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
 249     } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
 250       // All volatile loads/stores depend on each other
 251       if (queryIsVolatile && L->isVolatile()) {
 252         if (!start || block) {
 253           depGraphLocal.insert(std::make_pair(query, std::make_pair(L, true)));
 254           reverseDep.insert(std::make_pair(L, query));
 255         }
 256
 257         return L;
 258       }
 259
 260       pointer = L->getPointerOperand();
 261       pointerSize = TD.getTypeSize(L->getType());
 262     } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
 263       pointer = AI;
 264       if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
 265         pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType());
 266       else
 267         pointerSize = ~0UL;
 268     } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
 269       pointer = V->getOperand(0);
 270       pointerSize = TD.getTypeSize(V->getType());
 271     } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
 272       pointer = F->getPointerOperand();
 273
 274       // FreeInsts erase the entire structure
 275       pointerSize = ~0UL;
 276     } else if (CallSite::get(QI).getInstruction() != 0) {
 277       // Call insts need special handling.  Check is they can modify our pointer
 278       if (AA.getModRefInfo(CallSite::get(QI), dependee, dependeeSize) !=
 279           AliasAnalysis::NoModRef) {
 280         if (!start || block) {
 281           depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
 282           reverseDep.insert(std::make_pair(QI, query));
 283         }
 284
 285         return QI;
 286       } else {
 287         continue;
 288       }
 289     }
 290
 291     // If we found a pointer, check if it could be the same as our pointer
 292     if (pointer) {
 293       AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize,
 294                                               dependee, dependeeSize);
 295
 296       if (R != AliasAnalysis::NoAlias) {
 297         if (!start || block) {
 298           depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
 299           reverseDep.insert(std::make_pair(QI, query));
 300         }
 301
 302         return QI;
 303       }
 304     }
 305   }
 306
 307   // If we found nothing, return the non-local flag
 308   if (!start || block) {
 309     depGraphLocal.insert(std::make_pair(query,
 310                                         std::make_pair(NonLocal, true)));
 311     reverseDep.insert(std::make_pair(NonLocal, query));
 312   }
 313
 314   return NonLocal;
 315 }
 316
 317 /// removeInstruction - Remove an instruction from the dependence analysis,
 318 /// updating the dependence of instructions that previously depended on it.
 319 void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
 320   // Figure out the new dep for things that currently depend on rem
 321   Instruction* newDep = NonLocal;
 322
 323   depMapType::iterator depGraphEntry = depGraphLocal.find(rem);
 324   // We assume here that it's not in the reverse map if it's not in
 325   // the dep map.  Checking it could be expensive, so don't do it.
 326
 327   if (depGraphEntry != depGraphLocal.end()) {
 328     if (depGraphEntry->second.first != NonLocal &&
 329         depGraphEntry->second.second) {
 330       // If we have dep info for rem, set them to it
 331       BasicBlock::iterator RI = depGraphEntry->second.first;
 332       RI++;
 333       newDep = RI;
 334     } else if (depGraphEntry->second.first == NonLocal &&
 335                depGraphEntry->second.second ) {
 336       // If we have a confirmed non-local flag, use it
 337       newDep = NonLocal;
 338     } else {
 339       // Otherwise, use the immediate successor of rem
 340       // NOTE: This is because, when getDependence is called, it will first check
 341       // the immediate predecessor of what is in the cache.
 342       BasicBlock::iterator RI = rem;
 343       RI++;
 344       newDep = RI;
 345     }
 346
 347     std::multimap<Instruction*, Instruction*>::iterator I = reverseDep.find(rem);
 348     while (I != reverseDep.end() && I->first == rem) {
 349       // Insert the new dependencies
 350       // Mark it as unconfirmed as long as it is not the non-local flag
 351       depGraphLocal[I->second] = std::make_pair(newDep, !newDep);
 352       reverseDep.erase(I);
 353       I = reverseDep.find(rem);
 354     }
 355   }
 356
 357   getAnalysis<AliasAnalysis>().deleteValue(rem);
 358 }