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