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*)-3;
  30 Instruction* MemoryDependenceAnalysis::None = (Instruction*)-4;
  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                                                              BasicBlock* block) {
  47
  48   AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
  49   TargetData& TD = getAnalysis<TargetData>();
  50   BasicBlock::iterator blockBegin = C.getInstruction()->getParent()->begin();
  51   BasicBlock::iterator QI = C.getInstruction();
  52
  53   if (start) {
  54     QI = start;
  55     blockBegin = start->getParent()->end();
  56   } else if (!start && block) {
  57     QI = block->end();
  58     blockBegin = block->end();
  59   }
  60
  61   while (QI != blockBegin) {
  62     --QI;
  63
  64     // If this inst is a memory op, get the pointer it accessed
  65     Value* pointer = 0;
  66     uint64_t pointerSize = 0;
  67     if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
  68       pointer = S->getPointerOperand();
  69       pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
  70     } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
  71       pointer = L->getPointerOperand();
  72       pointerSize = TD.getTypeSize(L->getType());
  73     } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
  74       pointer = AI;
  75       if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
  76         pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType());
  77       else
  78         pointerSize = ~0UL;
  79     } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
  80       pointer = V->getOperand(0);
  81       pointerSize = TD.getTypeSize(V->getType());
  82     } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
  83       pointer = F->getPointerOperand();
  84
  85       // FreeInsts erase the entire structure
  86       pointerSize = ~0UL;
  87     } else if (CallSite::get(QI).getInstruction() != 0) {
  88       if (AA.getModRefInfo(C, CallSite::get(QI)) != AliasAnalysis::NoModRef) {
  89         if (!start && !block) {
  90           depGraphLocal.insert(std::make_pair(C.getInstruction(),
  91                                               std::make_pair(QI, true)));
  92           reverseDep[QI].insert(C.getInstruction());
  93         }
  94         return QI;
  95       } else {
  96         continue;
  97       }
  98     } else
  99       continue;
 100
 101     if (AA.getModRefInfo(C, pointer, pointerSize) != AliasAnalysis::NoModRef) {
 102       if (!start && !block) {
 103         depGraphLocal.insert(std::make_pair(C.getInstruction(),
 104                                             std::make_pair(QI, true)));
 105         reverseDep[QI].insert(C.getInstruction());
 106       }
 107       return QI;
 108     }
 109   }
 110
 111   // No dependence found
 112   depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(NonLocal, true)));
 113   reverseDep[NonLocal].insert(C.getInstruction());
 114   return NonLocal;
 115 }
 116
 117 void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
 118                                               BasicBlock* block,
 119                                               DenseMap<BasicBlock*, Value*>& resp) {
 120   SmallPtrSet<BasicBlock*, 4> visited;
 121   SmallVector<BasicBlock*, 4> stack;
 122   stack.push_back(block);
 123
 124   while (!stack.empty()) {
 125     BasicBlock* BB = stack.back();
 126
 127     if (visited.count(BB)) {
 128       stack.pop_back();
 129       continue;
 130     }
 131
 132     if (BB != block) {
 133       visited.insert(BB);
 134
 135       Instruction* localDep = getDependency(query, 0, BB);
 136       if (localDep != NonLocal) {
 137         resp.insert(std::make_pair(BB, localDep));
 138         stack.pop_back();
 139
 140         continue;
 141       }
 142     } else if (BB == block && stack.size() > 1) {
 143       visited.insert(BB);
 144
 145       Instruction* localDep = getDependency(query, 0, BB);
 146       if (localDep != query)
 147         resp.insert(std::make_pair(BB, localDep));
 148
 149       stack.pop_back();
 150
 151       continue;
 152     }
 153
 154     bool predOnStack = false;
 155     bool inserted = false;
 156     for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 157          PI != PE; ++PI)
 158       if (!visited.count(*PI)) {
 159         stack.push_back(*PI);
 160         inserted = true;
 161       } else
 162         predOnStack = true;
 163
 164     if (inserted)
 165       continue;
 166     else if (!inserted && !predOnStack) {
 167       resp.insert(std::make_pair(BB, None));
 168     } else if (!inserted && predOnStack){
 169       resp.insert(std::make_pair(BB, NonLocal));
 170     }
 171
 172     stack.pop_back();
 173   }
 174 }
 175
 176 void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
 177                                                      DenseMap<BasicBlock*, Value*>& resp) {
 178   Instruction* localDep = getDependency(query);
 179   if (localDep != NonLocal) {
 180     resp.insert(std::make_pair(query->getParent(), localDep));
 181     return;
 182   }
 183
 184   nonLocalHelper(query, query->getParent(), resp);
 185 }
 186
 187 /// getDependency - Return the instruction on which a memory operation
 188 /// depends.  The local paramter indicates if the query should only
 189 /// evaluate dependencies within the same basic block.
 190 Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
 191                                                      Instruction* start,
 192                                                      BasicBlock* block) {
 193   // Start looking for dependencies with the queried inst
 194   BasicBlock::iterator QI = query;
 195
 196   // Check for a cached result
 197   std::pair<Instruction*, bool> cachedResult = depGraphLocal[query];
 198   // If we have a _confirmed_ cached entry, return it
 199   if (cachedResult.second)
 200     return cachedResult.first;
 201   else if (cachedResult.first && cachedResult.first != NonLocal)
 202   // If we have an unconfirmed cached entry, we can start our search from there
 203     QI = cachedResult.first;
 204
 205   if (start)
 206     QI = start;
 207   else if (!start && block)
 208     QI = block->end();
 209
 210   AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
 211   TargetData& TD = getAnalysis<TargetData>();
 212
 213   // Get the pointer value for which dependence will be determined
 214   Value* dependee = 0;
 215   uint64_t dependeeSize = 0;
 216   bool queryIsVolatile = false;
 217   if (StoreInst* S = dyn_cast<StoreInst>(query)) {
 218     dependee = S->getPointerOperand();
 219     dependeeSize = TD.getTypeSize(S->getOperand(0)->getType());
 220     queryIsVolatile = S->isVolatile();
 221   } else if (LoadInst* L = dyn_cast<LoadInst>(query)) {
 222     dependee = L->getPointerOperand();
 223     dependeeSize = TD.getTypeSize(L->getType());
 224     queryIsVolatile = L->isVolatile();
 225   } else if (VAArgInst* V = dyn_cast<VAArgInst>(query)) {
 226     dependee = V->getOperand(0);
 227     dependeeSize = TD.getTypeSize(V->getType());
 228   } else if (FreeInst* F = dyn_cast<FreeInst>(query)) {
 229     dependee = F->getPointerOperand();
 230
 231     // FreeInsts erase the entire structure, not just a field
 232     dependeeSize = ~0UL;
 233   } else if (CallSite::get(query).getInstruction() != 0)
 234     return getCallSiteDependency(CallSite::get(query), start, block);
 235   else if (isa<AllocationInst>(query))
 236     return None;
 237   else
 238     return None;
 239
 240   BasicBlock::iterator blockBegin = block ? block->begin()
 241                                           : query->getParent()->begin();
 242
 243   while (QI != blockBegin) {
 244     --QI;
 245
 246     // If this inst is a memory op, get the pointer it accessed
 247     Value* pointer = 0;
 248     uint64_t pointerSize = 0;
 249     if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
 250       // All volatile loads/stores depend on each other
 251       if (queryIsVolatile && S->isVolatile()) {
 252         if (!start && !block) {
 253           depGraphLocal.insert(std::make_pair(query, std::make_pair(S, true)));
 254           reverseDep[S].insert(query);
 255         }
 256
 257         return S;
 258       }
 259
 260       pointer = S->getPointerOperand();
 261       pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
 262     } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
 263       // All volatile loads/stores depend on each other
 264       if (queryIsVolatile && L->isVolatile()) {
 265         if (!start && !block) {
 266           depGraphLocal.insert(std::make_pair(query, std::make_pair(L, true)));
 267           reverseDep[L].insert(query);
 268         }
 269
 270         return L;
 271       }
 272
 273       pointer = L->getPointerOperand();
 274       pointerSize = TD.getTypeSize(L->getType());
 275     } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
 276       pointer = AI;
 277       if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
 278         pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType());
 279       else
 280         pointerSize = ~0UL;
 281     } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
 282       pointer = V->getOperand(0);
 283       pointerSize = TD.getTypeSize(V->getType());
 284     } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
 285       pointer = F->getPointerOperand();
 286
 287       // FreeInsts erase the entire structure
 288       pointerSize = ~0UL;
 289     } else if (CallSite::get(QI).getInstruction() != 0) {
 290       // Call insts need special handling.  Check is they can modify our pointer
 291       AliasAnalysis::ModRefResult MR = AA.getModRefInfo(CallSite::get(QI),
 292                                                       dependee, dependeeSize);
 293
 294       if (MR != AliasAnalysis::NoModRef) {
 295         // Loads don't depend on read-only calls
 296         if (isa<LoadInst>(query) && MR == AliasAnalysis::Ref)
 297           continue;
 298
 299         if (!start && !block) {
 300           depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
 301           reverseDep[QI].insert(query);
 302         }
 303
 304         return QI;
 305       } else {
 306         continue;
 307       }
 308     }
 309
 310     // If we found a pointer, check if it could be the same as our pointer
 311     if (pointer) {
 312       AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize,
 313                                               dependee, dependeeSize);
 314
 315       if (R != AliasAnalysis::NoAlias) {
 316         // May-alias loads don't depend on each other
 317         if (isa<LoadInst>(query) && isa<LoadInst>(QI) &&
 318             R == AliasAnalysis::MayAlias)
 319           continue;
 320
 321         if (!start && !block) {
 322           depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
 323           reverseDep[QI].insert(query);
 324         }
 325
 326         return QI;
 327       }
 328     }
 329   }
 330
 331   // If we found nothing, return the non-local flag
 332   if (!start && !block) {
 333     depGraphLocal.insert(std::make_pair(query,
 334                                         std::make_pair(NonLocal, true)));
 335     reverseDep[NonLocal].insert(query);
 336   }
 337
 338   return NonLocal;
 339 }
 340
 341 /// removeInstruction - Remove an instruction from the dependence analysis,
 342 /// updating the dependence of instructions that previously depended on it.
 343 void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
 344   // Figure out the new dep for things that currently depend on rem
 345   Instruction* newDep = NonLocal;
 346
 347   depMapType::iterator depGraphEntry = depGraphLocal.find(rem);
 348   // We assume here that it's not in the reverse map if it's not in
 349   // the dep map.  Checking it could be expensive, so don't do it.
 350
 351   if (depGraphEntry != depGraphLocal.end()) {
 352     if (depGraphEntry->second.first != NonLocal &&
 353         depGraphEntry->second.second) {
 354       // If we have dep info for rem, set them to it
 355       BasicBlock::iterator RI = depGraphEntry->second.first;
 356       RI++;
 357       newDep = RI;
 358     } else if (depGraphEntry->second.first == NonLocal &&
 359                depGraphEntry->second.second ) {
 360       // If we have a confirmed non-local flag, use it
 361       newDep = NonLocal;
 362     } else {
 363       // Otherwise, use the immediate successor of rem
 364       // NOTE: This is because, when getDependence is called, it will first check
 365       // the immediate predecessor of what is in the cache.
 366       BasicBlock::iterator RI = rem;
 367       RI++;
 368       newDep = RI;
 369     }
 370
 371     SmallPtrSet<Instruction*, 4>& set = reverseDep[rem];
 372     for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 373          I != E; ++I) {
 374       // Insert the new dependencies
 375       // Mark it as unconfirmed as long as it is not the non-local flag
 376       depGraphLocal[*I] = std::make_pair(newDep, !newDep);
 377     }
 378     reverseDep.erase(rem);
 379   }
 380
 381   getAnalysis<AliasAnalysis>().deleteValue(rem);
 382 }