blob: 498e54c7272031e77ee3f2a9475715ee981718fb [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"
22#include "llvm/Target/TargetData.h"
23
24using namespace llvm;
25
26char MemoryDependenceAnalysis::ID = 0;
27
28Instruction* MemoryDependenceAnalysis::NonLocal = (Instruction*)0;
29Instruction* MemoryDependenceAnalysis::None = (Instruction*)~0;
30
31// Register this pass...
Owen Anderson776ee1f2007-07-10 20:21:08 +000032static RegisterPass<MemoryDependenceAnalysis> X("memdep",
33 "Memory Dependence Analysis");
Owen Anderson78e02f72007-07-06 23:14:35 +000034
35/// getAnalysisUsage - Does not modify anything. It uses Alias Analysis.
36///
37void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
38 AU.setPreservesAll();
39 AU.addRequiredTransitive<AliasAnalysis>();
40 AU.addRequiredTransitive<TargetData>();
41}
42
Owen Anderson5f323202007-07-10 17:59:22 +000043// Find the dependency of a CallSite
Owen Andersonfaac5182007-07-16 21:52:50 +000044Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, Instruction* start,
45 bool local) {
Owen Anderson5f323202007-07-10 17:59:22 +000046 assert(local && "Non-local memory dependence analysis not yet implemented");
47
48 AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
49 TargetData& TD = getAnalysis<TargetData>();
50 BasicBlock::iterator blockBegin = C.getInstruction()->getParent()->begin();
51 BasicBlock::iterator QI = C.getInstruction();
52
53 while (QI != blockBegin) {
54 --QI;
55
56 // If this inst is a memory op, get the pointer it accessed
57 Value* pointer = 0;
58 uint64_t pointerSize = 0;
59 if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
60 pointer = S->getPointerOperand();
61 pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
62 } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
63 pointer = L->getPointerOperand();
64 pointerSize = TD.getTypeSize(L->getType());
65 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
66 pointer = AI;
67 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
Owen Anderson8e850482007-07-10 20:48:38 +000068 pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType());
Owen Anderson5f323202007-07-10 17:59:22 +000069 else
70 pointerSize = ~0UL;
Owen Anderson06b6e822007-07-10 18:43:15 +000071 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
72 pointer = V->getOperand(0);
73 pointerSize = TD.getTypeSize(V->getType());
Owen Anderson5f323202007-07-10 17:59:22 +000074 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
75 pointer = F->getPointerOperand();
76
77 // FreeInsts erase the entire structure
78 pointerSize = ~0UL;
79 } else if (CallSite::get(QI).getInstruction() != 0) {
80 if (AA.getModRefInfo(C, CallSite::get(QI)) != AliasAnalysis::NoModRef) {
81 depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(QI, true)));
82 reverseDep.insert(std::make_pair(QI, C.getInstruction()));
83 return QI;
84 } else {
85 continue;
86 }
Owen Anderson202da142007-07-10 20:39:07 +000087 } else
88 continue;
Owen Anderson5f323202007-07-10 17:59:22 +000089
90 if (AA.getModRefInfo(C, pointer, pointerSize) != AliasAnalysis::NoModRef) {
91 depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(QI, true)));
92 reverseDep.insert(std::make_pair(QI, C.getInstruction()));
93 return QI;
94 }
95 }
96
97 // No dependence found
98 depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(NonLocal, true)));
99 reverseDep.insert(std::make_pair(NonLocal, C.getInstruction()));
100 return NonLocal;
101}
102
Owen Anderson78e02f72007-07-06 23:14:35 +0000103/// getDependency - Return the instruction on which a memory operation
Owen Anderson6b278fc2007-07-10 17:08:11 +0000104/// depends. The local paramter indicates if the query should only
105/// evaluate dependencies within the same basic block.
Owen Anderson78e02f72007-07-06 23:14:35 +0000106Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
Owen Andersonfaac5182007-07-16 21:52:50 +0000107 Instruction* start,
Owen Anderson78e02f72007-07-06 23:14:35 +0000108 bool local) {
109 if (!local)
110 assert(0 && "Non-local memory dependence is not yet supported.");
111
112 // Start looking for dependencies with the queried inst
113 BasicBlock::iterator QI = query;
114
115 // Check for a cached result
116 std::pair<Instruction*, bool> cachedResult = depGraphLocal[query];
117 // If we have a _confirmed_ cached entry, return it
118 if (cachedResult.second)
119 return cachedResult.first;
120 else if (cachedResult.first != NonLocal)
121 // If we have an unconfirmed cached entry, we can start our search from there
122 QI = cachedResult.first;
123
Owen Andersonfaac5182007-07-16 21:52:50 +0000124 if (start)
125 QI = start;
126
Owen Anderson78e02f72007-07-06 23:14:35 +0000127 AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
Owen Anderson6b278fc2007-07-10 17:08:11 +0000128 TargetData& TD = getAnalysis<TargetData>();
Owen Anderson78e02f72007-07-06 23:14:35 +0000129
130 // Get the pointer value for which dependence will be determined
131 Value* dependee = 0;
Owen Anderson6b278fc2007-07-10 17:08:11 +0000132 uint64_t dependeeSize = 0;
Owen Andersone314eb32007-07-10 18:11:42 +0000133 bool queryIsVolatile = false;
Owen Andersonfaac5182007-07-16 21:52:50 +0000134 if (StoreInst* S = dyn_cast<StoreInst>(query)) {
Owen Anderson78e02f72007-07-06 23:14:35 +0000135 dependee = S->getPointerOperand();
Owen Anderson7a616a12007-07-10 17:25:03 +0000136 dependeeSize = TD.getTypeSize(S->getOperand(0)->getType());
Owen Andersone314eb32007-07-10 18:11:42 +0000137 queryIsVolatile = S->isVolatile();
Owen Andersonfaac5182007-07-16 21:52:50 +0000138 } else if (LoadInst* L = dyn_cast<LoadInst>(query)) {
Owen Anderson78e02f72007-07-06 23:14:35 +0000139 dependee = L->getPointerOperand();
Owen Anderson7a616a12007-07-10 17:25:03 +0000140 dependeeSize = TD.getTypeSize(L->getType());
Owen Andersone314eb32007-07-10 18:11:42 +0000141 queryIsVolatile = L->isVolatile();
Owen Andersonfaac5182007-07-16 21:52:50 +0000142 } else if (VAArgInst* V = dyn_cast<VAArgInst>(query)) {
Owen Anderson06b6e822007-07-10 18:43:15 +0000143 dependee = V->getOperand(0);
144 dependeeSize = TD.getTypeSize(V->getType());
Owen Andersonfaac5182007-07-16 21:52:50 +0000145 } else if (FreeInst* F = dyn_cast<FreeInst>(query)) {
Owen Anderson78e02f72007-07-06 23:14:35 +0000146 dependee = F->getPointerOperand();
Owen Anderson6b278fc2007-07-10 17:08:11 +0000147
148 // FreeInsts erase the entire structure, not just a field
149 dependeeSize = ~0UL;
Owen Andersonfaac5182007-07-16 21:52:50 +0000150 } else if (CallSite::get(query).getInstruction() != 0)
151 return getCallSiteDependency(CallSite::get(query), start);
Owen Anderson5f323202007-07-10 17:59:22 +0000152 else if (isa<AllocationInst>(query))
Owen Anderson78e02f72007-07-06 23:14:35 +0000153 return None;
Owen Anderson7a616a12007-07-10 17:25:03 +0000154 else
Owen Anderson6b278fc2007-07-10 17:08:11 +0000155 return None;
Owen Anderson78e02f72007-07-06 23:14:35 +0000156
Owen Anderson6b278fc2007-07-10 17:08:11 +0000157 BasicBlock::iterator blockBegin = query->getParent()->begin();
Owen Anderson78e02f72007-07-06 23:14:35 +0000158
159 while (QI != blockBegin) {
Owen Anderson6b278fc2007-07-10 17:08:11 +0000160 --QI;
161
Owen Anderson78e02f72007-07-06 23:14:35 +0000162 // If this inst is a memory op, get the pointer it accessed
163 Value* pointer = 0;
Owen Anderson6b278fc2007-07-10 17:08:11 +0000164 uint64_t pointerSize = 0;
165 if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
Owen Andersone314eb32007-07-10 18:11:42 +0000166 // All volatile loads/stores depend on each other
167 if (queryIsVolatile && S->isVolatile()) {
Owen Andersonfaac5182007-07-16 21:52:50 +0000168 if (!start) {
169 depGraphLocal.insert(std::make_pair(query, std::make_pair(S, true)));
170 reverseDep.insert(std::make_pair(S, query));
171 }
172
Owen Andersone314eb32007-07-10 18:11:42 +0000173 return S;
174 }
175
Owen Anderson78e02f72007-07-06 23:14:35 +0000176 pointer = S->getPointerOperand();
Owen Anderson7a616a12007-07-10 17:25:03 +0000177 pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
Owen Anderson6b278fc2007-07-10 17:08:11 +0000178 } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
Owen Andersone314eb32007-07-10 18:11:42 +0000179 // All volatile loads/stores depend on each other
180 if (queryIsVolatile && L->isVolatile()) {
Owen Andersonfaac5182007-07-16 21:52:50 +0000181 if (!start) {
182 depGraphLocal.insert(std::make_pair(query, std::make_pair(L, true)));
183 reverseDep.insert(std::make_pair(L, query));
184 }
185
Owen Andersone314eb32007-07-10 18:11:42 +0000186 return L;
187 }
188
Owen Anderson78e02f72007-07-06 23:14:35 +0000189 pointer = L->getPointerOperand();
Owen Anderson7a616a12007-07-10 17:25:03 +0000190 pointerSize = TD.getTypeSize(L->getType());
Owen Anderson6b278fc2007-07-10 17:08:11 +0000191 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
192 pointer = AI;
Owen Anderson7a616a12007-07-10 17:25:03 +0000193 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
Owen Anderson8e850482007-07-10 20:48:38 +0000194 pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType());
Owen Anderson6b278fc2007-07-10 17:08:11 +0000195 else
196 pointerSize = ~0UL;
Owen Anderson06b6e822007-07-10 18:43:15 +0000197 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
198 pointer = V->getOperand(0);
199 pointerSize = TD.getTypeSize(V->getType());
Owen Anderson6b278fc2007-07-10 17:08:11 +0000200 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
Owen Anderson78e02f72007-07-06 23:14:35 +0000201 pointer = F->getPointerOperand();
Owen Anderson6b278fc2007-07-10 17:08:11 +0000202
203 // FreeInsts erase the entire structure
204 pointerSize = ~0UL;
Owen Anderson5f323202007-07-10 17:59:22 +0000205 } else if (CallSite::get(QI).getInstruction() != 0) {
Owen Anderson78e02f72007-07-06 23:14:35 +0000206 // Call insts need special handling. Check is they can modify our pointer
Owen Anderson5f323202007-07-10 17:59:22 +0000207 if (AA.getModRefInfo(CallSite::get(QI), dependee, dependeeSize) !=
208 AliasAnalysis::NoModRef) {
Owen Andersonfaac5182007-07-16 21:52:50 +0000209 if (!start) {
210 depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
211 reverseDep.insert(std::make_pair(QI, query));
212 }
213
Owen Anderson5f323202007-07-10 17:59:22 +0000214 return QI;
Owen Anderson7a616a12007-07-10 17:25:03 +0000215 } else {
216 continue;
217 }
Owen Anderson78e02f72007-07-06 23:14:35 +0000218 }
219
220 // If we found a pointer, check if it could be the same as our pointer
221 if (pointer) {
Owen Anderson6b278fc2007-07-10 17:08:11 +0000222 AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize,
223 dependee, dependeeSize);
Owen Anderson78e02f72007-07-06 23:14:35 +0000224
225 if (R != AliasAnalysis::NoAlias) {
Owen Andersonfaac5182007-07-16 21:52:50 +0000226 if (!start) {
227 depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
228 reverseDep.insert(std::make_pair(QI, query));
229 }
230
Owen Anderson78e02f72007-07-06 23:14:35 +0000231 return QI;
232 }
233 }
Owen Anderson78e02f72007-07-06 23:14:35 +0000234 }
235
236 // If we found nothing, return the non-local flag
Owen Andersonfaac5182007-07-16 21:52:50 +0000237 if (!start) {
238 depGraphLocal.insert(std::make_pair(query,
239 std::make_pair(NonLocal, true)));
240 reverseDep.insert(std::make_pair(NonLocal, query));
241 }
Owen Anderson78e02f72007-07-06 23:14:35 +0000242
243 return NonLocal;
244}
245
246/// removeInstruction - Remove an instruction from the dependence analysis,
247/// updating the dependence of instructions that previously depended on it.
248void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
249 // Figure out the new dep for things that currently depend on rem
250 Instruction* newDep = NonLocal;
251 if (depGraphLocal[rem].first != NonLocal) {
252 // If we have dep info for rem, set them to it
253 BasicBlock::iterator RI = depGraphLocal[rem].first;
254 RI++;
255 newDep = RI;
256 } else if (depGraphLocal[rem].first == NonLocal &&
257 depGraphLocal[rem].second ) {
258 // If we have a confirmed non-local flag, use it
259 newDep = NonLocal;
260 } else {
261 // Otherwise, use the immediate successor of rem
262 // NOTE: This is because, when getDependence is called, it will first check
263 // the immediate predecessor of what is in the cache.
264 BasicBlock::iterator RI = rem;
265 RI++;
266 newDep = RI;
267 }
268
269 std::multimap<Instruction*, Instruction*>::iterator I = reverseDep.find(rem);
270 while (I->first == rem) {
271 // Insert the new dependencies
272 // Mark it as unconfirmed as long as it is not the non-local flag
273 depGraphLocal[I->second] = std::make_pair(newDep, !newDep);
274 reverseDep.erase(I);
275 I = reverseDep.find(rem);
276 }
Owen Anderson1cb960a2007-07-12 00:06:21 +0000277
278 getAnalysis<AliasAnalysis>().deleteValue(rem);
Owen Anderson78e02f72007-07-06 23:14:35 +0000279}