MemoryDependenceAnalysis.cpp revision 1cb960a4bb97336be1339fd5bc2eb28f125f099a 
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
24using namespace llvm;
25
26char MemoryDependenceAnalysis::ID = 0;
27
28Instruction* MemoryDependenceAnalysis::NonLocal = (Instruction*)0;
29Instruction* MemoryDependenceAnalysis::None = (Instruction*)~0;
30
31// Register this pass...
32static RegisterPass<MemoryDependenceAnalysis> X("memdep",
33                                                "Memory Dependence Analysis");
34
35/// getAnalysisUsage - Does not modify anything.  It uses Alias Analysis.
36///
37void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
38  AU.setPreservesAll();
39  AU.addRequiredTransitive<AliasAnalysis>();
40  AU.addRequiredTransitive<TargetData>();
41}
42
43// Find the dependency of a CallSite
44Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, bool local) {
45  assert(local && "Non-local memory dependence analysis not yet implemented");
46
47  AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
48  TargetData& TD = getAnalysis<TargetData>();
49  BasicBlock::iterator blockBegin = C.getInstruction()->getParent()->begin();
50  BasicBlock::iterator QI = C.getInstruction();
51
52  while (QI != blockBegin) {
53    --QI;
54
55    // If this inst is a memory op, get the pointer it accessed
56    Value* pointer = 0;
57    uint64_t pointerSize = 0;
58    if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
59      pointer = S->getPointerOperand();
60      pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
61    } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
62      pointer = L->getPointerOperand();
63      pointerSize = TD.getTypeSize(L->getType());
64    } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
65      pointer = AI;
66      if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
67        pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType());
68      else
69        pointerSize = ~0UL;
70    } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
71      pointer = V->getOperand(0);
72      pointerSize = TD.getTypeSize(V->getType());
73    } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
74      pointer = F->getPointerOperand();
75
76      // FreeInsts erase the entire structure
77      pointerSize = ~0UL;
78    } else if (CallSite::get(QI).getInstruction() != 0) {
79      if (AA.getModRefInfo(C, CallSite::get(QI)) != AliasAnalysis::NoModRef) {
80        depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(QI, true)));
81        reverseDep.insert(std::make_pair(QI, C.getInstruction()));
82        return QI;
83      } else {
84        continue;
85      }
86    } else
87      continue;
88
89    if (AA.getModRefInfo(C, pointer, pointerSize) != AliasAnalysis::NoModRef) {
90      depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(QI, true)));
91      reverseDep.insert(std::make_pair(QI, C.getInstruction()));
92      return QI;
93    }
94  }
95
96  // No dependence found
97  depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(NonLocal, true)));
98  reverseDep.insert(std::make_pair(NonLocal, C.getInstruction()));
99  return NonLocal;
100}
101
102/// getDependency - Return the instruction on which a memory operation
103/// depends.  The local paramter indicates if the query should only
104/// evaluate dependencies within the same basic block.
105Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
106                                                     bool local) {
107  if (!local)
108    assert(0 && "Non-local memory dependence is not yet supported.");
109
110  // Start looking for dependencies with the queried inst
111  BasicBlock::iterator QI = query;
112
113  // Check for a cached result
114  std::pair<Instruction*, bool> cachedResult = depGraphLocal[query];
115  // If we have a _confirmed_ cached entry, return it
116  if (cachedResult.second)
117    return cachedResult.first;
118  else if (cachedResult.first != NonLocal)
119  // If we have an unconfirmed cached entry, we can start our search from there
120    QI = cachedResult.first;
121
122  AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
123  TargetData& TD = getAnalysis<TargetData>();
124
125  // Get the pointer value for which dependence will be determined
126  Value* dependee = 0;
127  uint64_t dependeeSize = 0;
128  bool queryIsVolatile = false;
129  if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
130    dependee = S->getPointerOperand();
131    dependeeSize = TD.getTypeSize(S->getOperand(0)->getType());
132    queryIsVolatile = S->isVolatile();
133  } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
134    dependee = L->getPointerOperand();
135    dependeeSize = TD.getTypeSize(L->getType());
136    queryIsVolatile = L->isVolatile();
137  } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
138    dependee = V->getOperand(0);
139    dependeeSize = TD.getTypeSize(V->getType());
140  } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
141    dependee = F->getPointerOperand();
142
143    // FreeInsts erase the entire structure, not just a field
144    dependeeSize = ~0UL;
145  } else if (CallSite::get(QI).getInstruction() != 0)
146    return getCallSiteDependency(CallSite::get(QI));
147  else if (isa<AllocationInst>(query))
148    return None;
149  else
150    return None;
151
152  BasicBlock::iterator blockBegin = query->getParent()->begin();
153
154  while (QI != blockBegin) {
155    --QI;
156
157    // If this inst is a memory op, get the pointer it accessed
158    Value* pointer = 0;
159    uint64_t pointerSize = 0;
160    if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
161      // All volatile loads/stores depend on each other
162      if (queryIsVolatile && S->isVolatile()) {
163        depGraphLocal.insert(std::make_pair(query, std::make_pair(S, true)));
164        reverseDep.insert(std::make_pair(S, query));
165        return S;
166      }
167
168      pointer = S->getPointerOperand();
169      pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
170    } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
171      // All volatile loads/stores depend on each other
172      if (queryIsVolatile && L->isVolatile()) {
173        depGraphLocal.insert(std::make_pair(query, std::make_pair(L, true)));
174        reverseDep.insert(std::make_pair(L, query));
175        return L;
176      }
177
178      pointer = L->getPointerOperand();
179      pointerSize = TD.getTypeSize(L->getType());
180    } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
181      pointer = AI;
182      if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
183        pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType());
184      else
185        pointerSize = ~0UL;
186    } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
187      pointer = V->getOperand(0);
188      pointerSize = TD.getTypeSize(V->getType());
189    } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
190      pointer = F->getPointerOperand();
191
192      // FreeInsts erase the entire structure
193      pointerSize = ~0UL;
194    } else if (CallSite::get(QI).getInstruction() != 0) {
195      // Call insts need special handling.  Check is they can modify our pointer
196      if (AA.getModRefInfo(CallSite::get(QI), dependee, dependeeSize) !=
197          AliasAnalysis::NoModRef) {
198        depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
199        reverseDep.insert(std::make_pair(QI, query));
200        return QI;
201      } else {
202        continue;
203      }
204    }
205
206    // If we found a pointer, check if it could be the same as our pointer
207    if (pointer) {
208      AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize,
209                                              dependee, dependeeSize);
210
211      if (R != AliasAnalysis::NoAlias) {
212        depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
213        reverseDep.insert(std::make_pair(QI, query));
214        return QI;
215      }
216    }
217  }
218
219  // If we found nothing, return the non-local flag
220  depGraphLocal.insert(std::make_pair(query,
221                                      std::make_pair(NonLocal, true)));
222  reverseDep.insert(std::make_pair(NonLocal, query));
223
224  return NonLocal;
225}
226
227/// removeInstruction - Remove an instruction from the dependence analysis,
228/// updating the dependence of instructions that previously depended on it.
229void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
230  // Figure out the new dep for things that currently depend on rem
231  Instruction* newDep = NonLocal;
232  if (depGraphLocal[rem].first != NonLocal) {
233    // If we have dep info for rem, set them to it
234    BasicBlock::iterator RI = depGraphLocal[rem].first;
235    RI++;
236    newDep = RI;
237  } else if (depGraphLocal[rem].first == NonLocal &&
238             depGraphLocal[rem].second ) {
239    // If we have a confirmed non-local flag, use it
240    newDep = NonLocal;
241  } else {
242    // Otherwise, use the immediate successor of rem
243    // NOTE: This is because, when getDependence is called, it will first check
244    // the immediate predecessor of what is in the cache.
245    BasicBlock::iterator RI = rem;
246    RI++;
247    newDep = RI;
248  }
249
250  std::multimap<Instruction*, Instruction*>::iterator I = reverseDep.find(rem);
251  while (I->first == rem) {
252    // Insert the new dependencies
253    // Mark it as unconfirmed as long as it is not the non-local flag
254    depGraphLocal[I->second] = std::make_pair(newDep, !newDep);
255    reverseDep.erase(I);
256    I = reverseDep.find(rem);
257  }
258
259  getAnalysis<AliasAnalysis>().deleteValue(rem);
260}
261