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