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