MemoryDependenceAnalysis.cpp revision 80b1f09693dd849620330da76b445fa0b3873dd1 
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
29const Instruction* MemoryDependenceAnalysis::NonLocal = (Instruction*)-3;
30const Instruction* MemoryDependenceAnalysis::None = (Instruction*)-4;
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
45const Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C,
46                                                           Instruction* start,
47                                                            BasicBlock* block) {
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  if (start) {
55    QI = start;
56    blockBegin = start->getParent()->end();
57  } else if (!start && block) {
58    QI = block->end();
59    blockBegin = block->end();
60  }
61
62  while (QI != blockBegin) {
63    --QI;
64
65    // If this inst is a memory op, get the pointer it accessed
66    Value* pointer = 0;
67    uint64_t pointerSize = 0;
68    if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
69      pointer = S->getPointerOperand();
70      pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
71    } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
72      pointer = L->getPointerOperand();
73      pointerSize = TD.getTypeSize(L->getType());
74    } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
75      pointer = AI;
76      if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
77        pointerSize = C->getZExtValue() * \
78                      TD.getTypeSize(AI->getAllocatedType());
79      else
80        pointerSize = ~0UL;
81    } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
82      pointer = V->getOperand(0);
83      pointerSize = TD.getTypeSize(V->getType());
84    } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
85      pointer = F->getPointerOperand();
86
87      // FreeInsts erase the entire structure
88      pointerSize = ~0UL;
89    } else if (CallSite::get(QI).getInstruction() != 0) {
90      if (AA.getModRefInfo(C, CallSite::get(QI)) != AliasAnalysis::NoModRef) {
91        if (!start && !block) {
92          depGraphLocal.insert(std::make_pair(C.getInstruction(),
93                                              std::make_pair(QI, true)));
94          reverseDep[QI].insert(C.getInstruction());
95        }
96        return QI;
97      } else {
98        continue;
99      }
100    } else
101      continue;
102
103    if (AA.getModRefInfo(C, pointer, pointerSize) != AliasAnalysis::NoModRef) {
104      if (!start && !block) {
105        depGraphLocal.insert(std::make_pair(C.getInstruction(),
106                                            std::make_pair(QI, true)));
107        reverseDep[QI].insert(C.getInstruction());
108      }
109      return QI;
110    }
111  }
112
113  // No dependence found
114  depGraphLocal.insert(std::make_pair(C.getInstruction(),
115                                      std::make_pair(NonLocal, true)));
116  reverseDep[NonLocal].insert(C.getInstruction());
117  return NonLocal;
118}
119
120void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
121                                              BasicBlock* block,
122                                         DenseMap<BasicBlock*, Value*>& resp) {
123  SmallPtrSet<BasicBlock*, 4> visited;
124  SmallVector<BasicBlock*, 4> stack;
125  stack.push_back(block);
126
127  while (!stack.empty()) {
128    BasicBlock* BB = stack.back();
129
130    if (visited.count(BB)) {
131      stack.pop_back();
132      continue;
133    }
134
135    if (BB != block) {
136      visited.insert(BB);
137
138      const Instruction* localDep = getDependency(query, 0, BB);
139      if (localDep != NonLocal) {
140        resp.insert(std::make_pair(BB, const_cast<Instruction*>(localDep)));
141        stack.pop_back();
142
143        continue;
144      }
145    } else if (BB == block && stack.size() > 1) {
146      visited.insert(BB);
147
148      const Instruction* localDep = getDependency(query, 0, BB);
149      if (localDep != query)
150        resp.insert(std::make_pair(BB, const_cast<Instruction*>(localDep)));
151
152      stack.pop_back();
153
154      continue;
155    }
156
157    bool predOnStack = false;
158    bool inserted = false;
159    for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
160         PI != PE; ++PI)
161      if (!visited.count(*PI)) {
162        stack.push_back(*PI);
163        inserted = true;
164      } else
165        predOnStack = true;
166
167    if (inserted)
168      continue;
169    else if (!inserted && !predOnStack) {
170      resp.insert(std::make_pair(BB, const_cast<Instruction*>(None)));
171    } else if (!inserted && predOnStack){
172      resp.insert(std::make_pair(BB, const_cast<Instruction*>(NonLocal)));
173    }
174
175    stack.pop_back();
176  }
177}
178
179/// getNonLocalDependency - Fills the passed-in map with the non-local
180/// dependencies of the queries.  The map will contain NonLocal for
181/// blocks between the query and its dependencies.
182void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
183                                         DenseMap<BasicBlock*, Value*>& resp) {
184  const Instruction* localDep = getDependency(query);
185  if (localDep != NonLocal) {
186    resp.insert(std::make_pair(query->getParent(),
187                               const_cast<Instruction*>(localDep)));
188    return;
189  }
190
191  nonLocalHelper(query, query->getParent(), resp);
192}
193
194/// getDependency - Return the instruction on which a memory operation
195/// depends.  The local paramter indicates if the query should only
196/// evaluate dependencies within the same basic block.
197const Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
198                                                     Instruction* start,
199                                                     BasicBlock* block) {
200  // Start looking for dependencies with the queried inst
201  BasicBlock::iterator QI = query;
202
203  // Check for a cached result
204  std::pair<const Instruction*, bool> cachedResult = depGraphLocal[query];
205  // If we have a _confirmed_ cached entry, return it
206  if (cachedResult.second)
207    return cachedResult.first;
208  else if (cachedResult.first && cachedResult.first != NonLocal)
209  // If we have an unconfirmed cached entry, we can start our search from there
210    QI = const_cast<Instruction*>(cachedResult.first);
211
212  if (start)
213    QI = start;
214  else if (!start && block)
215    QI = block->end();
216
217  AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
218  TargetData& TD = getAnalysis<TargetData>();
219
220  // Get the pointer value for which dependence will be determined
221  Value* dependee = 0;
222  uint64_t dependeeSize = 0;
223  bool queryIsVolatile = false;
224  if (StoreInst* S = dyn_cast<StoreInst>(query)) {
225    dependee = S->getPointerOperand();
226    dependeeSize = TD.getTypeSize(S->getOperand(0)->getType());
227    queryIsVolatile = S->isVolatile();
228  } else if (LoadInst* L = dyn_cast<LoadInst>(query)) {
229    dependee = L->getPointerOperand();
230    dependeeSize = TD.getTypeSize(L->getType());
231    queryIsVolatile = L->isVolatile();
232  } else if (VAArgInst* V = dyn_cast<VAArgInst>(query)) {
233    dependee = V->getOperand(0);
234    dependeeSize = TD.getTypeSize(V->getType());
235  } else if (FreeInst* F = dyn_cast<FreeInst>(query)) {
236    dependee = F->getPointerOperand();
237
238    // FreeInsts erase the entire structure, not just a field
239    dependeeSize = ~0UL;
240  } else if (CallSite::get(query).getInstruction() != 0)
241    return getCallSiteDependency(CallSite::get(query), start, block);
242  else if (isa<AllocationInst>(query))
243    return None;
244  else
245    return None;
246
247  BasicBlock::iterator blockBegin = block ? block->begin()
248                                          : query->getParent()->begin();
249
250  while (QI != blockBegin) {
251    --QI;
252
253    // If this inst is a memory op, get the pointer it accessed
254    Value* pointer = 0;
255    uint64_t pointerSize = 0;
256    if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
257      // All volatile loads/stores depend on each other
258      if (queryIsVolatile && S->isVolatile()) {
259        if (!start && !block) {
260          depGraphLocal.insert(std::make_pair(query, std::make_pair(S, true)));
261          reverseDep[S].insert(query);
262        }
263
264        return S;
265      }
266
267      pointer = S->getPointerOperand();
268      pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
269    } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
270      // All volatile loads/stores depend on each other
271      if (queryIsVolatile && L->isVolatile()) {
272        if (!start && !block) {
273          depGraphLocal.insert(std::make_pair(query, std::make_pair(L, true)));
274          reverseDep[L].insert(query);
275        }
276
277        return L;
278      }
279
280      pointer = L->getPointerOperand();
281      pointerSize = TD.getTypeSize(L->getType());
282    } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
283      pointer = AI;
284      if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
285        pointerSize = C->getZExtValue() * \
286                      TD.getTypeSize(AI->getAllocatedType());
287      else
288        pointerSize = ~0UL;
289    } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
290      pointer = V->getOperand(0);
291      pointerSize = TD.getTypeSize(V->getType());
292    } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
293      pointer = F->getPointerOperand();
294
295      // FreeInsts erase the entire structure
296      pointerSize = ~0UL;
297    } else if (CallSite::get(QI).getInstruction() != 0) {
298      // Call insts need special handling. Check if they can modify our pointer
299      AliasAnalysis::ModRefResult MR = AA.getModRefInfo(CallSite::get(QI),
300                                                      dependee, dependeeSize);
301
302      if (MR != AliasAnalysis::NoModRef) {
303        // Loads don't depend on read-only calls
304        if (isa<LoadInst>(query) && MR == AliasAnalysis::Ref)
305          continue;
306
307        if (!start && !block) {
308          depGraphLocal.insert(std::make_pair(query,
309                                              std::make_pair(QI, true)));
310          reverseDep[QI].insert(query);
311        }
312
313        return QI;
314      } else {
315        continue;
316      }
317    }
318
319    // If we found a pointer, check if it could be the same as our pointer
320    if (pointer) {
321      AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize,
322                                              dependee, dependeeSize);
323
324      if (R != AliasAnalysis::NoAlias) {
325        // May-alias loads don't depend on each other
326        if (isa<LoadInst>(query) && isa<LoadInst>(QI) &&
327            R == AliasAnalysis::MayAlias)
328          continue;
329
330        if (!start && !block) {
331          depGraphLocal.insert(std::make_pair(query,
332                                              std::make_pair(QI, true)));
333          reverseDep[QI].insert(query);
334        }
335
336        return QI;
337      }
338    }
339  }
340
341  // If we found nothing, return the non-local flag
342  if (!start && !block) {
343    depGraphLocal.insert(std::make_pair(query,
344                                        std::make_pair(NonLocal, true)));
345    reverseDep[NonLocal].insert(query);
346  }
347
348  return NonLocal;
349}
350
351/// removeInstruction - Remove an instruction from the dependence analysis,
352/// updating the dependence of instructions that previously depended on it.
353void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
354  // Figure out the new dep for things that currently depend on rem
355  const Instruction* newDep = NonLocal;
356
357  depMapType::iterator depGraphEntry = depGraphLocal.find(rem);
358  // We assume here that it's not in the reverse map if it's not in
359  // the dep map.  Checking it could be expensive, so don't do it.
360
361  if (depGraphEntry != depGraphLocal.end()) {
362    if (depGraphEntry->second.first != NonLocal &&
363        depGraphEntry->second.second) {
364      // If we have dep info for rem, set them to it
365      BasicBlock::iterator RI =
366                         const_cast<Instruction*>(depGraphEntry->second.first);
367      RI++;
368      newDep = RI;
369    } else if (depGraphEntry->second.first == NonLocal &&
370               depGraphEntry->second.second ) {
371      // If we have a confirmed non-local flag, use it
372      newDep = NonLocal;
373    } else {
374      // Otherwise, use the immediate successor of rem
375      // NOTE: This is because, when getDependence is called, it will first
376      // check the immediate predecessor of what is in the cache.
377      BasicBlock::iterator RI = rem;
378      RI++;
379      newDep = RI;
380    }
381
382    SmallPtrSet<Instruction*, 4>& set = reverseDep[rem];
383    for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
384         I != E; ++I) {
385      // Insert the new dependencies
386      // Mark it as unconfirmed as long as it is not the non-local flag
387      depGraphLocal[*I] = std::make_pair(newDep, !newDep);
388    }
389    reverseDep.erase(rem);
390  }
391
392  getAnalysis<AliasAnalysis>().deleteValue(rem);
393}
394