1 //===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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.
15 //===----------------------------------------------------------------------===//
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"
27 char MemoryDependenceAnalysis::ID = 0;
29 Instruction* MemoryDependenceAnalysis::NonLocal = (Instruction*)-3;
30 Instruction* MemoryDependenceAnalysis::None = (Instruction*)-4;
32 // Register this pass...
33 static RegisterPass<MemoryDependenceAnalysis> X("memdep",
34 "Memory Dependence Analysis");
36 /// getAnalysisUsage - Does not modify anything. It uses Alias Analysis.
38 void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
40 AU.addRequiredTransitive<AliasAnalysis>();
41 AU.addRequiredTransitive<TargetData>();
44 // Find the dependency of a CallSite
45 Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, Instruction* start,
48 AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
49 TargetData& TD = getAnalysis<TargetData>();
50 BasicBlock::iterator blockBegin = C.getInstruction()->getParent()->begin();
51 BasicBlock::iterator QI = C.getInstruction();
55 blockBegin = start->getParent()->end();
56 } else if (!start && block) {
58 blockBegin = block->end();
61 while (QI != blockBegin) {
64 // If this inst is a memory op, get the pointer it accessed
66 uint64_t pointerSize = 0;
67 if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
68 pointer = S->getPointerOperand();
69 pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
70 } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
71 pointer = L->getPointerOperand();
72 pointerSize = TD.getTypeSize(L->getType());
73 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
75 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
76 pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType());
79 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
80 pointer = V->getOperand(0);
81 pointerSize = TD.getTypeSize(V->getType());
82 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
83 pointer = F->getPointerOperand();
85 // FreeInsts erase the entire structure
87 } else if (CallSite::get(QI).getInstruction() != 0) {
88 if (AA.getModRefInfo(C, CallSite::get(QI)) != AliasAnalysis::NoModRef) {
89 if (!start && !block) {
90 depGraphLocal.insert(std::make_pair(C.getInstruction(),
91 std::make_pair(QI, true)));
92 reverseDep[QI].insert(C.getInstruction());
101 if (AA.getModRefInfo(C, pointer, pointerSize) != AliasAnalysis::NoModRef) {
102 if (!start && !block) {
103 depGraphLocal.insert(std::make_pair(C.getInstruction(),
104 std::make_pair(QI, true)));
105 reverseDep[QI].insert(C.getInstruction());
111 // No dependence found
112 depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(NonLocal, true)));
113 reverseDep[NonLocal].insert(C.getInstruction());
117 void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
119 DenseMap<BasicBlock*, Value*>& resp) {
120 SmallPtrSet<BasicBlock*, 4> visited;
121 SmallVector<BasicBlock*, 4> stack;
122 stack.push_back(block);
124 while (!stack.empty()) {
125 BasicBlock* BB = stack.back();
127 if (visited.count(BB)) {
135 Instruction* localDep = getDependency(query, 0, BB);
136 if (localDep != NonLocal) {
137 resp.insert(std::make_pair(BB, localDep));
142 } else if (BB == block && stack.size() > 1) {
145 Instruction* localDep = getDependency(query, 0, BB);
146 if (localDep != query)
147 resp.insert(std::make_pair(BB, localDep));
154 bool predOnStack = false;
155 bool inserted = false;
156 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
158 if (!visited.count(*PI)) {
159 stack.push_back(*PI);
166 else if (!inserted && !predOnStack) {
167 resp.insert(std::make_pair(BB, None));
168 } else if (!inserted && predOnStack){
169 resp.insert(std::make_pair(BB, NonLocal));
176 void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
177 DenseMap<BasicBlock*, Value*>& resp) {
178 Instruction* localDep = getDependency(query);
179 if (localDep != NonLocal) {
180 resp.insert(std::make_pair(query->getParent(), localDep));
184 nonLocalHelper(query, query->getParent(), resp);
187 /// getDependency - Return the instruction on which a memory operation
188 /// depends. The local paramter indicates if the query should only
189 /// evaluate dependencies within the same basic block.
190 Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
193 // Start looking for dependencies with the queried inst
194 BasicBlock::iterator QI = query;
196 // Check for a cached result
197 std::pair<Instruction*, bool> cachedResult = depGraphLocal[query];
198 // If we have a _confirmed_ cached entry, return it
199 if (cachedResult.second)
200 return cachedResult.first;
201 else if (cachedResult.first && cachedResult.first != NonLocal)
202 // If we have an unconfirmed cached entry, we can start our search from there
203 QI = cachedResult.first;
207 else if (!start && block)
210 AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
211 TargetData& TD = getAnalysis<TargetData>();
213 // Get the pointer value for which dependence will be determined
215 uint64_t dependeeSize = 0;
216 bool queryIsVolatile = false;
217 if (StoreInst* S = dyn_cast<StoreInst>(query)) {
218 dependee = S->getPointerOperand();
219 dependeeSize = TD.getTypeSize(S->getOperand(0)->getType());
220 queryIsVolatile = S->isVolatile();
221 } else if (LoadInst* L = dyn_cast<LoadInst>(query)) {
222 dependee = L->getPointerOperand();
223 dependeeSize = TD.getTypeSize(L->getType());
224 queryIsVolatile = L->isVolatile();
225 } else if (VAArgInst* V = dyn_cast<VAArgInst>(query)) {
226 dependee = V->getOperand(0);
227 dependeeSize = TD.getTypeSize(V->getType());
228 } else if (FreeInst* F = dyn_cast<FreeInst>(query)) {
229 dependee = F->getPointerOperand();
231 // FreeInsts erase the entire structure, not just a field
233 } else if (CallSite::get(query).getInstruction() != 0)
234 return getCallSiteDependency(CallSite::get(query), start, block);
235 else if (isa<AllocationInst>(query))
240 BasicBlock::iterator blockBegin = block ? block->begin()
241 : query->getParent()->begin();
243 while (QI != blockBegin) {
246 // If this inst is a memory op, get the pointer it accessed
248 uint64_t pointerSize = 0;
249 if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
250 // All volatile loads/stores depend on each other
251 if (queryIsVolatile && S->isVolatile()) {
252 if (!start && !block) {
253 depGraphLocal.insert(std::make_pair(query, std::make_pair(S, true)));
254 reverseDep[S].insert(query);
260 pointer = S->getPointerOperand();
261 pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
262 } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
263 // All volatile loads/stores depend on each other
264 if (queryIsVolatile && L->isVolatile()) {
265 if (!start && !block) {
266 depGraphLocal.insert(std::make_pair(query, std::make_pair(L, true)));
267 reverseDep[L].insert(query);
273 pointer = L->getPointerOperand();
274 pointerSize = TD.getTypeSize(L->getType());
275 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
277 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
278 pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType());
281 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
282 pointer = V->getOperand(0);
283 pointerSize = TD.getTypeSize(V->getType());
284 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
285 pointer = F->getPointerOperand();
287 // FreeInsts erase the entire structure
289 } else if (CallSite::get(QI).getInstruction() != 0) {
290 // Call insts need special handling. Check is they can modify our pointer
291 AliasAnalysis::ModRefResult MR = AA.getModRefInfo(CallSite::get(QI),
292 dependee, dependeeSize);
294 if (MR != AliasAnalysis::NoModRef) {
295 // Loads don't depend on read-only calls
296 if (isa<LoadInst>(query) && MR == AliasAnalysis::Ref)
299 if (!start && !block) {
300 depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
301 reverseDep[QI].insert(query);
310 // If we found a pointer, check if it could be the same as our pointer
312 AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize,
313 dependee, dependeeSize);
315 if (R != AliasAnalysis::NoAlias) {
316 // May-alias loads don't depend on each other
317 if (isa<LoadInst>(query) && isa<LoadInst>(QI) &&
318 R == AliasAnalysis::MayAlias)
321 if (!start && !block) {
322 depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
323 reverseDep[QI].insert(query);
331 // If we found nothing, return the non-local flag
332 if (!start && !block) {
333 depGraphLocal.insert(std::make_pair(query,
334 std::make_pair(NonLocal, true)));
335 reverseDep[NonLocal].insert(query);
341 /// removeInstruction - Remove an instruction from the dependence analysis,
342 /// updating the dependence of instructions that previously depended on it.
343 void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
344 // Figure out the new dep for things that currently depend on rem
345 Instruction* newDep = NonLocal;
347 depMapType::iterator depGraphEntry = depGraphLocal.find(rem);
348 // We assume here that it's not in the reverse map if it's not in
349 // the dep map. Checking it could be expensive, so don't do it.
351 if (depGraphEntry != depGraphLocal.end()) {
352 if (depGraphEntry->second.first != NonLocal &&
353 depGraphEntry->second.second) {
354 // If we have dep info for rem, set them to it
355 BasicBlock::iterator RI = depGraphEntry->second.first;
358 } else if (depGraphEntry->second.first == NonLocal &&
359 depGraphEntry->second.second ) {
360 // If we have a confirmed non-local flag, use it
363 // Otherwise, use the immediate successor of rem
364 // NOTE: This is because, when getDependence is called, it will first check
365 // the immediate predecessor of what is in the cache.
366 BasicBlock::iterator RI = rem;
371 SmallPtrSet<Instruction*, 4>& set = reverseDep[rem];
372 for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
374 // Insert the new dependencies
375 // Mark it as unconfirmed as long as it is not the non-local flag
376 depGraphLocal[*I] = std::make_pair(newDep, !newDep);
378 reverseDep.erase(rem);
381 getAnalysis<AliasAnalysis>().deleteValue(rem);