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