MemoryDependenceAnalysis.cpp revision 0cd320362e91852c8f7f2c8c4841498aab7f92fa 
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  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
127bool 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.
152Instruction* 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.
294void 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}
327