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