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