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