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/Target/TargetData.h"
  23
  24 using namespace llvm;
  25
  26 char MemoryDependenceAnalysis::ID = 0;
  27
  28 Instruction* MemoryDependenceAnalysis::NonLocal = (Instruction*)0;
  29 Instruction* MemoryDependenceAnalysis::None = (Instruction*)~0;
  30
  31 // Register this pass...
  32 RegisterPass<MemoryDependenceAnalysis> X("memdep",
  33                                            "Memory Dependence Analysis");
  34
  35 /// getAnalysisUsage - Does not modify anything.  It uses Alias Analysis.
  36 ///
  37 void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
  38   AU.setPreservesAll();
  39   AU.addRequiredTransitive<AliasAnalysis>();
  40   AU.addRequiredTransitive<TargetData>();
  41 }
  42
  43 // Find the dependency of a CallSite
  44 Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, bool local) {
  45   assert(local && "Non-local memory dependence analysis not yet implemented");
  46
  47   AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
  48   TargetData& TD = getAnalysis<TargetData>();
  49   BasicBlock::iterator blockBegin = C.getInstruction()->getParent()->begin();
  50   BasicBlock::iterator QI = C.getInstruction();
  51
  52   while (QI != blockBegin) {
  53     --QI;
  54
  55     // If this inst is a memory op, get the pointer it accessed
  56     Value* pointer = 0;
  57     uint64_t pointerSize = 0;
  58     if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
  59       pointer = S->getPointerOperand();
  60       pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
  61     } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
  62       pointer = L->getPointerOperand();
  63       pointerSize = TD.getTypeSize(L->getType());
  64     } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
  65       pointer = AI;
  66       if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
  67         pointerSize = C->getZExtValue();
  68       else
  69         pointerSize = ~0UL;
  70     } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
  71       pointer = V->getOperand(0);
  72       pointerSize = TD.getTypeSize(V->getType());
  73     } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
  74       pointer = F->getPointerOperand();
  75
  76       // FreeInsts erase the entire structure
  77       pointerSize = ~0UL;
  78     } else if (CallSite::get(QI).getInstruction() != 0) {
  79       if (AA.getModRefInfo(C, CallSite::get(QI)) != AliasAnalysis::NoModRef) {
  80         depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(QI, true)));
  81         reverseDep.insert(std::make_pair(QI, C.getInstruction()));
  82         return QI;
  83       } else {
  84         continue;
  85       }
  86     }
  87
  88     if (AA.getModRefInfo(C, pointer, pointerSize) != AliasAnalysis::NoModRef) {
  89       depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(QI, true)));
  90       reverseDep.insert(std::make_pair(QI, C.getInstruction()));
  91       return QI;
  92     }
  93   }
  94
  95   // No dependence found
  96   depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(NonLocal, true)));
  97   reverseDep.insert(std::make_pair(NonLocal, C.getInstruction()));
  98   return NonLocal;
  99 }
 100
 101 /// getDependency - Return the instruction on which a memory operation
 102 /// depends.  The local paramter indicates if the query should only
 103 /// evaluate dependencies within the same basic block.
 104 Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
 105                                                      bool local) {
 106   if (!local)
 107     assert(0 && "Non-local memory dependence is not yet supported.");
 108
 109   // Start looking for dependencies with the queried inst
 110   BasicBlock::iterator QI = query;
 111
 112   // Check for a cached result
 113   std::pair<Instruction*, bool> cachedResult = depGraphLocal[query];
 114   // If we have a _confirmed_ cached entry, return it
 115   if (cachedResult.second)
 116     return cachedResult.first;
 117   else if (cachedResult.first != NonLocal)
 118   // If we have an unconfirmed cached entry, we can start our search from there
 119     QI = cachedResult.first;
 120
 121   AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
 122   TargetData& TD = getAnalysis<TargetData>();
 123
 124   // Get the pointer value for which dependence will be determined
 125   Value* dependee = 0;
 126   uint64_t dependeeSize = 0;
 127   bool queryIsVolatile = false;
 128   if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
 129     dependee = S->getPointerOperand();
 130     dependeeSize = TD.getTypeSize(S->getOperand(0)->getType());
 131     queryIsVolatile = S->isVolatile();
 132   } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
 133     dependee = L->getPointerOperand();
 134     dependeeSize = TD.getTypeSize(L->getType());
 135     queryIsVolatile = L->isVolatile();
 136   } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
 137     dependee = V->getOperand(0);
 138     dependeeSize = TD.getTypeSize(V->getType());
 139   } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
 140     dependee = F->getPointerOperand();
 141
 142     // FreeInsts erase the entire structure, not just a field
 143     dependeeSize = ~0UL;
 144   } else if (CallSite::get(QI).getInstruction() != 0)
 145     return getCallSiteDependency(CallSite::get(QI));
 146   else if (isa<AllocationInst>(query))
 147     return None;
 148   else
 149     return None;
 150
 151   BasicBlock::iterator blockBegin = query->getParent()->begin();
 152
 153   while (QI != blockBegin) {
 154     --QI;
 155
 156     // If this inst is a memory op, get the pointer it accessed
 157     Value* pointer = 0;
 158     uint64_t pointerSize = 0;
 159     if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
 160       // All volatile loads/stores depend on each other
 161       if (queryIsVolatile && S->isVolatile()) {
 162         depGraphLocal.insert(std::make_pair(query, std::make_pair(S, true)));
 163         reverseDep.insert(std::make_pair(S, query));
 164         return S;
 165       }
 166
 167       pointer = S->getPointerOperand();
 168       pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
 169     } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
 170       // All volatile loads/stores depend on each other
 171       if (queryIsVolatile && L->isVolatile()) {
 172         depGraphLocal.insert(std::make_pair(query, std::make_pair(L, true)));
 173         reverseDep.insert(std::make_pair(L, query));
 174         return L;
 175       }
 176
 177       pointer = L->getPointerOperand();
 178       pointerSize = TD.getTypeSize(L->getType());
 179     } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
 180       pointer = AI;
 181       if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
 182         pointerSize = C->getZExtValue();
 183       else
 184         pointerSize = ~0UL;
 185     } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
 186       pointer = V->getOperand(0);
 187       pointerSize = TD.getTypeSize(V->getType());
 188     } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
 189       pointer = F->getPointerOperand();
 190
 191       // FreeInsts erase the entire structure
 192       pointerSize = ~0UL;
 193     } else if (CallSite::get(QI).getInstruction() != 0) {
 194       // Call insts need special handling.  Check is they can modify our pointer
 195       if (AA.getModRefInfo(CallSite::get(QI), dependee, dependeeSize) !=
 196           AliasAnalysis::NoModRef) {
 197         depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
 198         reverseDep.insert(std::make_pair(QI, query));
 199         return QI;
 200       } else {
 201         continue;
 202       }
 203     }
 204
 205     // If we found a pointer, check if it could be the same as our pointer
 206     if (pointer) {
 207       AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize,
 208                                               dependee, dependeeSize);
 209
 210       if (R != AliasAnalysis::NoAlias) {
 211         depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
 212         reverseDep.insert(std::make_pair(QI, query));
 213         return QI;
 214       }
 215     }
 216   }
 217
 218   // If we found nothing, return the non-local flag
 219   depGraphLocal.insert(std::make_pair(query,
 220                                       std::make_pair(NonLocal, true)));
 221   reverseDep.insert(std::make_pair(NonLocal, query));
 222
 223   return NonLocal;
 224 }
 225
 226 /// removeInstruction - Remove an instruction from the dependence analysis,
 227 /// updating the dependence of instructions that previously depended on it.
 228 void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
 229   // Figure out the new dep for things that currently depend on rem
 230   Instruction* newDep = NonLocal;
 231   if (depGraphLocal[rem].first != NonLocal) {
 232     // If we have dep info for rem, set them to it
 233     BasicBlock::iterator RI = depGraphLocal[rem].first;
 234     RI++;
 235     newDep = RI;
 236   } else if (depGraphLocal[rem].first == NonLocal &&
 237              depGraphLocal[rem].second ) {
 238     // If we have a confirmed non-local flag, use it
 239     newDep = NonLocal;
 240   } else {
 241     // Otherwise, use the immediate successor of rem
 242     // NOTE: This is because, when getDependence is called, it will first check
 243     // the immediate predecessor of what is in the cache.
 244     BasicBlock::iterator RI = rem;
 245     RI++;
 246     newDep = RI;
 247   }
 248
 249   std::multimap<Instruction*, Instruction*>::iterator I = reverseDep.find(rem);
 250   while (I->first == rem) {
 251     // Insert the new dependencies
 252     // Mark it as unconfirmed as long as it is not the non-local flag
 253     depGraphLocal[I->second] = std::make_pair(newDep, !newDep);
 254     reverseDep.erase(I);
 255     I = reverseDep.find(rem);
 256   }
 257 }