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 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 /// getDependency - Return the instruction on which a memory operation
  44 /// depends.  The local paramter indicates if the query should only
  45 /// evaluate dependencies within the same basic block.
  46 Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
  47                                                      bool local) {
  48   if (!local)
  49     assert(0 && "Non-local memory dependence is not yet supported.");
  50
  51   // Start looking for dependencies with the queried inst
  52   BasicBlock::iterator QI = query;
  53
  54   // Check for a cached result
  55   std::pair<Instruction*, bool> cachedResult = depGraphLocal[query];
  56   // If we have a _confirmed_ cached entry, return it
  57   if (cachedResult.second)
  58     return cachedResult.first;
  59   else if (cachedResult.first != NonLocal)
  60   // If we have an unconfirmed cached entry, we can start our search from there
  61     QI = cachedResult.first;
  62
  63   AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
  64   TargetData& TD = getAnalysis<TargetData>();
  65
  66   // Get the pointer value for which dependence will be determined
  67   Value* dependee = 0;
  68   uint64_t dependeeSize = 0;
  69   if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
  70     dependee = S->getPointerOperand();
  71     dependeeSize = TD.getTypeSize(S->getOperand(0)->getType());
  72   } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
  73     dependee = L->getPointerOperand();
  74     dependeeSize = TD.getTypeSize(L->getType());
  75   } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
  76     dependee = F->getPointerOperand();
  77
  78     // FreeInsts erase the entire structure, not just a field
  79     dependeeSize = ~0UL;
  80   } else if (isa<AllocationInst>(query))
  81     return None;
  82   else
  83     // FIXME: Call/InvokeInsts need proper handling
  84     return None;
  85
  86
  87   BasicBlock::iterator blockBegin = query->getParent()->begin();
  88
  89   while (QI != blockBegin) {
  90     --QI;
  91
  92     // If this inst is a memory op, get the pointer it accessed
  93     Value* pointer = 0;
  94     uint64_t pointerSize = 0;
  95     if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
  96       pointer = S->getPointerOperand();
  97       pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
  98     } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
  99       pointer = L->getPointerOperand();
 100       pointerSize = TD.getTypeSize(L->getType());
 101     } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
 102       pointer = AI;
 103       if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
 104         pointerSize = C->getZExtValue();
 105       else
 106         pointerSize = ~0UL;
 107     } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
 108       pointer = F->getPointerOperand();
 109
 110       // FreeInsts erase the entire structure
 111       pointerSize = ~0UL;
 112     } else if (CallInst* C = dyn_cast<CallInst>(QI)) {
 113       // Call insts need special handling.  Check is they can modify our pointer
 114       if (AA.getModRefInfo(C, dependee, dependeeSize) != AliasAnalysis::NoModRef) {
 115         depGraphLocal.insert(std::make_pair(query, std::make_pair(C, true)));
 116         reverseDep.insert(std::make_pair(C, query));
 117         return C;
 118       } else {
 119         continue;
 120       }
 121     } else if (InvokeInst* I = dyn_cast<InvokeInst>(QI)) {
 122       // Invoke insts need special handling.  Check is they can modify our pointer
 123       if (AA.getModRefInfo(I, dependee, dependeeSize) != AliasAnalysis::NoModRef) {
 124         depGraphLocal.insert(std::make_pair(query, std::make_pair(I, true)));
 125         reverseDep.insert(std::make_pair(I, query));
 126         return I;
 127       } else {
 128         continue;
 129       }
 130     }
 131
 132     // If we found a pointer, check if it could be the same as our pointer
 133     if (pointer) {
 134       AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize,
 135                                               dependee, dependeeSize);
 136
 137       if (R != AliasAnalysis::NoAlias) {
 138         depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
 139         reverseDep.insert(std::make_pair(QI, query));
 140         return QI;
 141       }
 142     }
 143   }
 144
 145   // If we found nothing, return the non-local flag
 146   depGraphLocal.insert(std::make_pair(query,
 147                                       std::make_pair(NonLocal, true)));
 148   reverseDep.insert(std::make_pair(NonLocal, query));
 149
 150   return NonLocal;
 151 }
 152
 153 /// removeInstruction - Remove an instruction from the dependence analysis,
 154 /// updating the dependence of instructions that previously depended on it.
 155 void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
 156   // Figure out the new dep for things that currently depend on rem
 157   Instruction* newDep = NonLocal;
 158   if (depGraphLocal[rem].first != NonLocal) {
 159     // If we have dep info for rem, set them to it
 160     BasicBlock::iterator RI = depGraphLocal[rem].first;
 161     RI++;
 162     newDep = RI;
 163   } else if (depGraphLocal[rem].first == NonLocal &&
 164              depGraphLocal[rem].second ) {
 165     // If we have a confirmed non-local flag, use it
 166     newDep = NonLocal;
 167   } else {
 168     // Otherwise, use the immediate successor of rem
 169     // NOTE: This is because, when getDependence is called, it will first check
 170     // the immediate predecessor of what is in the cache.
 171     BasicBlock::iterator RI = rem;
 172     RI++;
 173     newDep = RI;
 174   }
 175
 176   std::multimap<Instruction*, Instruction*>::iterator I = reverseDep.find(rem);
 177   while (I->first == rem) {
 178     // Insert the new dependencies
 179     // Mark it as unconfirmed as long as it is not the non-local flag
 180     depGraphLocal[I->second] = std::make_pair(newDep, !newDep);
 181     reverseDep.erase(I);
 182     I = reverseDep.find(rem);
 183   }
 184 }