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