blob: 5a8cb7bfaa7eeb1748783c566ee274d0ae0c495f [file] [log] [blame]
Owen Anderson78e02f72007-07-06 23:14:35 +00001//===- 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"
Owen Anderson7a616a12007-07-10 17:25:03 +000018#include "llvm/Constants.h"
Owen Anderson78e02f72007-07-06 23:14:35 +000019#include "llvm/Instructions.h"
20#include "llvm/Function.h"
21#include "llvm/Analysis/AliasAnalysis.h"
Owen Anderson4beedbd2007-07-24 21:52:37 +000022#include "llvm/Support/CFG.h"
Owen Anderson78e02f72007-07-06 23:14:35 +000023#include "llvm/Target/TargetData.h"
24
25using namespace llvm;
26
27char MemoryDependenceAnalysis::ID = 0;
28
Owen Anderson0cd32032007-07-25 19:57:03 +000029Instruction* MemoryDependenceAnalysis::NonLocal = (Instruction*)-2;
30Instruction* MemoryDependenceAnalysis::None = (Instruction*)-3;
Owen Anderson78e02f72007-07-06 23:14:35 +000031
32// Register this pass...
Owen Anderson776ee1f2007-07-10 20:21:08 +000033static RegisterPass<MemoryDependenceAnalysis> X("memdep",
34 "Memory Dependence Analysis");
Owen Anderson78e02f72007-07-06 23:14:35 +000035
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
Owen Anderson5f323202007-07-10 17:59:22 +000044// Find the dependency of a CallSite
Owen Andersonfaac5182007-07-16 21:52:50 +000045Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, Instruction* start,
46 bool local) {
Owen Anderson5f323202007-07-10 17:59:22 +000047 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()))
Owen Anderson8e850482007-07-10 20:48:38 +000069 pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType());
Owen Anderson5f323202007-07-10 17:59:22 +000070 else
71 pointerSize = ~0UL;
Owen Anderson06b6e822007-07-10 18:43:15 +000072 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
73 pointer = V->getOperand(0);
74 pointerSize = TD.getTypeSize(V->getType());
Owen Anderson5f323202007-07-10 17:59:22 +000075 } 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 }
Owen Anderson202da142007-07-10 20:39:07 +000088 } else
89 continue;
Owen Anderson5f323202007-07-10 17:59:22 +000090
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
Owen Anderson0cd32032007-07-25 19:57:03 +0000104bool MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
105 BasicBlock* block,
Owen Anderson3dfcf332007-07-25 21:26:36 +0000106 DenseMap<BasicBlock*, Value*>& resp,
107 SmallPtrSet<BasicBlock*, 4>& visited) {
Owen Anderson0cd32032007-07-25 19:57:03 +0000108 if (resp.count(block))
109 return resp[block] != None;
Owen Anderson4beedbd2007-07-24 21:52:37 +0000110
Owen Anderson0cd32032007-07-25 19:57:03 +0000111 Instruction* localDep = getDependency(query, 0, block);
Owen Anderson4beedbd2007-07-24 21:52:37 +0000112 if (localDep != NonLocal) {
Owen Anderson0cd32032007-07-25 19:57:03 +0000113 resp.insert(std::make_pair(block, localDep));
114 return true;
Owen Anderson4beedbd2007-07-24 21:52:37 +0000115 }
116
Owen Anderson3dfcf332007-07-25 21:26:36 +0000117 visited.insert(block);
118
Owen Anderson0cd32032007-07-25 19:57:03 +0000119 bool inserted = false;
Owen Andersona377a242007-07-26 18:57:04 +0000120 bool predOnStack = false;
Owen Anderson4beedbd2007-07-24 21:52:37 +0000121 for (pred_iterator PI = pred_begin(block), PE = pred_end(block);
Owen Anderson0cd32032007-07-25 19:57:03 +0000122 PI != PE; ++PI)
Owen Anderson3dfcf332007-07-25 21:26:36 +0000123 if (!visited.count(*PI))
124 inserted |= nonLocalHelper(query, *PI, resp, visited);
Owen Andersona377a242007-07-26 18:57:04 +0000125 else
126 predOnStack = true;
127
Owen Anderson3dfcf332007-07-25 21:26:36 +0000128 visited.erase(block);
Owen Andersona377a242007-07-26 18:57:04 +0000129
130 if (!inserted && !predOnStack)
131 resp.insert(std::make_pair(block, None));
Owen Anderson45c83882007-07-30 17:29:24 +0000132 else if (inserted && predOnStack)
133 resp.insert(std::make_pair(block, NonLocal));
Owen Anderson4beedbd2007-07-24 21:52:37 +0000134
Owen Anderson0cd32032007-07-25 19:57:03 +0000135 return inserted;
Owen Anderson4beedbd2007-07-24 21:52:37 +0000136}
137
Owen Anderson0cd32032007-07-25 19:57:03 +0000138bool MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
139 DenseMap<BasicBlock*, Value*>& resp) {
Owen Anderson4beedbd2007-07-24 21:52:37 +0000140 Instruction* localDep = getDependency(query);
141 if (localDep != NonLocal) {
Owen Anderson0cd32032007-07-25 19:57:03 +0000142 resp.insert(std::make_pair(query->getParent(), localDep));
143 return true;
Owen Anderson4beedbd2007-07-24 21:52:37 +0000144 }
145
Owen Anderson0cd32032007-07-25 19:57:03 +0000146 bool inserted = false;
Owen Anderson3dfcf332007-07-25 21:26:36 +0000147 SmallPtrSet<BasicBlock*, 4> visited;
148 visited.insert(query->getParent());
Owen Anderson0cd32032007-07-25 19:57:03 +0000149
Owen Anderson4beedbd2007-07-24 21:52:37 +0000150 BasicBlock* parent = query->getParent();
151 for (pred_iterator PI = pred_begin(parent), PE = pred_end(parent);
152 PI != PE; ++PI) {
Owen Anderson3dfcf332007-07-25 21:26:36 +0000153 if (!visited.count(*PI))
154 inserted |= nonLocalHelper(query, *PI, resp, visited);
Owen Anderson4beedbd2007-07-24 21:52:37 +0000155 }
156
Owen Anderson0cd32032007-07-25 19:57:03 +0000157 if (!inserted)
158 resp.insert(std::make_pair(query->getParent(), None));
Owen Anderson4beedbd2007-07-24 21:52:37 +0000159
Owen Anderson0cd32032007-07-25 19:57:03 +0000160 return inserted;
Owen Anderson4beedbd2007-07-24 21:52:37 +0000161}
162
Owen Anderson78e02f72007-07-06 23:14:35 +0000163/// getDependency - Return the instruction on which a memory operation
Owen Anderson6b278fc2007-07-10 17:08:11 +0000164/// depends. The local paramter indicates if the query should only
165/// evaluate dependencies within the same basic block.
Owen Anderson78e02f72007-07-06 23:14:35 +0000166Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
Owen Andersonfaac5182007-07-16 21:52:50 +0000167 Instruction* start,
Owen Anderson4beedbd2007-07-24 21:52:37 +0000168 BasicBlock* block) {
Owen Anderson78e02f72007-07-06 23:14:35 +0000169 // Start looking for dependencies with the queried inst
170 BasicBlock::iterator QI = query;
171
172 // Check for a cached result
173 std::pair<Instruction*, bool> cachedResult = depGraphLocal[query];
174 // If we have a _confirmed_ cached entry, return it
175 if (cachedResult.second)
176 return cachedResult.first;
Owen Anderson0cd32032007-07-25 19:57:03 +0000177 else if (cachedResult.first && cachedResult.first != NonLocal)
Owen Anderson78e02f72007-07-06 23:14:35 +0000178 // If we have an unconfirmed cached entry, we can start our search from there
179 QI = cachedResult.first;
180
Owen Andersonfaac5182007-07-16 21:52:50 +0000181 if (start)
182 QI = start;
Owen Anderson0cd32032007-07-25 19:57:03 +0000183 else if (!start && block)
184 QI = block->end();
Owen Andersonfaac5182007-07-16 21:52:50 +0000185
Owen Anderson78e02f72007-07-06 23:14:35 +0000186 AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
Owen Anderson6b278fc2007-07-10 17:08:11 +0000187 TargetData& TD = getAnalysis<TargetData>();
Owen Anderson78e02f72007-07-06 23:14:35 +0000188
189 // Get the pointer value for which dependence will be determined
190 Value* dependee = 0;
Owen Anderson6b278fc2007-07-10 17:08:11 +0000191 uint64_t dependeeSize = 0;
Owen Andersone314eb32007-07-10 18:11:42 +0000192 bool queryIsVolatile = false;
Owen Andersonfaac5182007-07-16 21:52:50 +0000193 if (StoreInst* S = dyn_cast<StoreInst>(query)) {
Owen Anderson78e02f72007-07-06 23:14:35 +0000194 dependee = S->getPointerOperand();
Owen Anderson7a616a12007-07-10 17:25:03 +0000195 dependeeSize = TD.getTypeSize(S->getOperand(0)->getType());
Owen Andersone314eb32007-07-10 18:11:42 +0000196 queryIsVolatile = S->isVolatile();
Owen Andersonfaac5182007-07-16 21:52:50 +0000197 } else if (LoadInst* L = dyn_cast<LoadInst>(query)) {
Owen Anderson78e02f72007-07-06 23:14:35 +0000198 dependee = L->getPointerOperand();
Owen Anderson7a616a12007-07-10 17:25:03 +0000199 dependeeSize = TD.getTypeSize(L->getType());
Owen Andersone314eb32007-07-10 18:11:42 +0000200 queryIsVolatile = L->isVolatile();
Owen Andersonfaac5182007-07-16 21:52:50 +0000201 } else if (VAArgInst* V = dyn_cast<VAArgInst>(query)) {
Owen Anderson06b6e822007-07-10 18:43:15 +0000202 dependee = V->getOperand(0);
203 dependeeSize = TD.getTypeSize(V->getType());
Owen Andersonfaac5182007-07-16 21:52:50 +0000204 } else if (FreeInst* F = dyn_cast<FreeInst>(query)) {
Owen Anderson78e02f72007-07-06 23:14:35 +0000205 dependee = F->getPointerOperand();
Owen Anderson6b278fc2007-07-10 17:08:11 +0000206
207 // FreeInsts erase the entire structure, not just a field
208 dependeeSize = ~0UL;
Owen Andersonfaac5182007-07-16 21:52:50 +0000209 } else if (CallSite::get(query).getInstruction() != 0)
210 return getCallSiteDependency(CallSite::get(query), start);
Owen Anderson5f323202007-07-10 17:59:22 +0000211 else if (isa<AllocationInst>(query))
Owen Anderson78e02f72007-07-06 23:14:35 +0000212 return None;
Owen Anderson7a616a12007-07-10 17:25:03 +0000213 else
Owen Anderson6b278fc2007-07-10 17:08:11 +0000214 return None;
Owen Anderson78e02f72007-07-06 23:14:35 +0000215
Owen Anderson4beedbd2007-07-24 21:52:37 +0000216 BasicBlock::iterator blockBegin = block ? block->begin()
217 : query->getParent()->begin();
Owen Anderson78e02f72007-07-06 23:14:35 +0000218
219 while (QI != blockBegin) {
Owen Anderson6b278fc2007-07-10 17:08:11 +0000220 --QI;
221
Owen Anderson78e02f72007-07-06 23:14:35 +0000222 // If this inst is a memory op, get the pointer it accessed
223 Value* pointer = 0;
Owen Anderson6b278fc2007-07-10 17:08:11 +0000224 uint64_t pointerSize = 0;
225 if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
Owen Andersone314eb32007-07-10 18:11:42 +0000226 // All volatile loads/stores depend on each other
227 if (queryIsVolatile && S->isVolatile()) {
Owen Anderson0cd32032007-07-25 19:57:03 +0000228 if (!start || block) {
Owen Andersonfaac5182007-07-16 21:52:50 +0000229 depGraphLocal.insert(std::make_pair(query, std::make_pair(S, true)));
230 reverseDep.insert(std::make_pair(S, query));
231 }
232
Owen Andersone314eb32007-07-10 18:11:42 +0000233 return S;
234 }
235
Owen Anderson78e02f72007-07-06 23:14:35 +0000236 pointer = S->getPointerOperand();
Owen Anderson7a616a12007-07-10 17:25:03 +0000237 pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
Owen Anderson6b278fc2007-07-10 17:08:11 +0000238 } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
Owen Andersone314eb32007-07-10 18:11:42 +0000239 // All volatile loads/stores depend on each other
240 if (queryIsVolatile && L->isVolatile()) {
Owen Anderson0cd32032007-07-25 19:57:03 +0000241 if (!start || block) {
Owen Andersonfaac5182007-07-16 21:52:50 +0000242 depGraphLocal.insert(std::make_pair(query, std::make_pair(L, true)));
243 reverseDep.insert(std::make_pair(L, query));
244 }
245
Owen Andersone314eb32007-07-10 18:11:42 +0000246 return L;
247 }
248
Owen Anderson78e02f72007-07-06 23:14:35 +0000249 pointer = L->getPointerOperand();
Owen Anderson7a616a12007-07-10 17:25:03 +0000250 pointerSize = TD.getTypeSize(L->getType());
Owen Anderson6b278fc2007-07-10 17:08:11 +0000251 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
252 pointer = AI;
Owen Anderson7a616a12007-07-10 17:25:03 +0000253 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
Owen Anderson8e850482007-07-10 20:48:38 +0000254 pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType());
Owen Anderson6b278fc2007-07-10 17:08:11 +0000255 else
256 pointerSize = ~0UL;
Owen Anderson06b6e822007-07-10 18:43:15 +0000257 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
258 pointer = V->getOperand(0);
259 pointerSize = TD.getTypeSize(V->getType());
Owen Anderson6b278fc2007-07-10 17:08:11 +0000260 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
Owen Anderson78e02f72007-07-06 23:14:35 +0000261 pointer = F->getPointerOperand();
Owen Anderson6b278fc2007-07-10 17:08:11 +0000262
263 // FreeInsts erase the entire structure
264 pointerSize = ~0UL;
Owen Anderson5f323202007-07-10 17:59:22 +0000265 } else if (CallSite::get(QI).getInstruction() != 0) {
Owen Anderson78e02f72007-07-06 23:14:35 +0000266 // Call insts need special handling. Check is they can modify our pointer
Owen Anderson5f323202007-07-10 17:59:22 +0000267 if (AA.getModRefInfo(CallSite::get(QI), dependee, dependeeSize) !=
268 AliasAnalysis::NoModRef) {
Owen Anderson0cd32032007-07-25 19:57:03 +0000269 if (!start || block) {
Owen Andersonfaac5182007-07-16 21:52:50 +0000270 depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
271 reverseDep.insert(std::make_pair(QI, query));
272 }
273
Owen Anderson5f323202007-07-10 17:59:22 +0000274 return QI;
Owen Anderson7a616a12007-07-10 17:25:03 +0000275 } else {
276 continue;
277 }
Owen Anderson78e02f72007-07-06 23:14:35 +0000278 }
279
280 // If we found a pointer, check if it could be the same as our pointer
281 if (pointer) {
Owen Anderson6b278fc2007-07-10 17:08:11 +0000282 AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize,
283 dependee, dependeeSize);
Owen Anderson78e02f72007-07-06 23:14:35 +0000284
285 if (R != AliasAnalysis::NoAlias) {
Owen Anderson0cd32032007-07-25 19:57:03 +0000286 if (!start || block) {
Owen Andersonfaac5182007-07-16 21:52:50 +0000287 depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
288 reverseDep.insert(std::make_pair(QI, query));
289 }
290
Owen Anderson78e02f72007-07-06 23:14:35 +0000291 return QI;
292 }
293 }
Owen Anderson78e02f72007-07-06 23:14:35 +0000294 }
295
296 // If we found nothing, return the non-local flag
Owen Anderson0cd32032007-07-25 19:57:03 +0000297 if (!start || block) {
Owen Andersonfaac5182007-07-16 21:52:50 +0000298 depGraphLocal.insert(std::make_pair(query,
299 std::make_pair(NonLocal, true)));
300 reverseDep.insert(std::make_pair(NonLocal, query));
301 }
Owen Anderson78e02f72007-07-06 23:14:35 +0000302
303 return NonLocal;
304}
305
306/// removeInstruction - Remove an instruction from the dependence analysis,
307/// updating the dependence of instructions that previously depended on it.
308void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
309 // Figure out the new dep for things that currently depend on rem
310 Instruction* newDep = NonLocal;
David Greenedf464192007-07-31 20:01:27 +0000311
312 depMapType::iterator depGraphEntry = depGraphLocal.find(rem);
313 // We assume here that it's not in the reverse map if it's not in
314 // the dep map. Checking it could be expensive, so don't do it.
315
316 if (depGraphEntry != depGraphLocal.end()) {
317 if (depGraphEntry->second.first != NonLocal &&
318 depGraphEntry->second.second) {
319 // If we have dep info for rem, set them to it
320 BasicBlock::iterator RI = depGraphEntry->second.first;
321 RI++;
322 newDep = RI;
323 } else if (depGraphEntry->second.first == NonLocal &&
324 depGraphEntry->second.second ) {
325 // If we have a confirmed non-local flag, use it
326 newDep = NonLocal;
327 } else {
328 // Otherwise, use the immediate successor of rem
329 // NOTE: This is because, when getDependence is called, it will first check
330 // the immediate predecessor of what is in the cache.
331 BasicBlock::iterator RI = rem;
332 RI++;
333 newDep = RI;
334 }
335
336 std::multimap<Instruction*, Instruction*>::iterator I = reverseDep.find(rem);
337 while (I != reverseDep.end() && I->first == rem) {
338 // Insert the new dependencies
339 // Mark it as unconfirmed as long as it is not the non-local flag
340 depGraphLocal[I->second] = std::make_pair(newDep, !newDep);
341 reverseDep.erase(I);
342 I = reverseDep.find(rem);
343 }
Owen Anderson78e02f72007-07-06 23:14:35 +0000344 }
345
Owen Anderson1cb960a2007-07-12 00:06:21 +0000346 getAnalysis<AliasAnalysis>().deleteValue(rem);
Owen Anderson78e02f72007-07-06 23:14:35 +0000347}