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*)-2;
30 Instruction* MemoryDependenceAnalysis::None = (Instruction*)-3;
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,
47 assert(local && "Non-local memory dependence analysis not yet implemented");
49 AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
50 TargetData& TD = getAnalysis<TargetData>();
51 BasicBlock::iterator blockBegin = C.getInstruction()->getParent()->begin();
52 BasicBlock::iterator QI = C.getInstruction();
54 while (QI != blockBegin) {
57 // If this inst is a memory op, get the pointer it accessed
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)) {
68 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
69 pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType());
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();
78 // FreeInsts erase the entire structure
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()));
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()));
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()));
104 void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
106 DenseMap<BasicBlock*, Value*>& resp) {
107 SmallPtrSet<BasicBlock*, 4> visited;
108 SmallVector<BasicBlock*, 4> stack;
109 stack.push_back(block);
111 while (!stack.empty()) {
112 BasicBlock* BB = stack.back();
114 if (visited.count(BB)) {
122 Instruction* localDep = getDependency(query, 0, BB);
123 if (localDep != NonLocal) {
124 resp.insert(std::make_pair(BB, localDep));
129 } else if (BB == block && stack.size() > 1) {
132 Instruction* localDep = getDependency(query, 0, BB);
133 if (localDep != query)
134 resp.insert(std::make_pair(BB, localDep));
141 bool predOnStack = false;
142 bool inserted = false;
143 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
145 if (!visited.count(*PI)) {
146 stack.push_back(*PI);
153 else if (!inserted && !predOnStack) {
154 resp.insert(std::make_pair(BB, None));
155 } else if (!inserted && predOnStack){
156 resp.insert(std::make_pair(BB, NonLocal));
163 void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
164 DenseMap<BasicBlock*, Value*>& resp) {
165 Instruction* localDep = getDependency(query);
166 if (localDep != NonLocal) {
167 resp.insert(std::make_pair(query->getParent(), localDep));
171 nonLocalHelper(query, query->getParent(), resp);
174 /// getDependency - Return the instruction on which a memory operation
175 /// depends. The local paramter indicates if the query should only
176 /// evaluate dependencies within the same basic block.
177 Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
180 // Start looking for dependencies with the queried inst
181 BasicBlock::iterator QI = query;
183 // Check for a cached result
184 std::pair<Instruction*, bool> cachedResult = depGraphLocal[query];
185 // If we have a _confirmed_ cached entry, return it
186 if (cachedResult.second)
187 return cachedResult.first;
188 else if (cachedResult.first && cachedResult.first != NonLocal)
189 // If we have an unconfirmed cached entry, we can start our search from there
190 QI = cachedResult.first;
194 else if (!start && block)
197 AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
198 TargetData& TD = getAnalysis<TargetData>();
200 // Get the pointer value for which dependence will be determined
202 uint64_t dependeeSize = 0;
203 bool queryIsVolatile = false;
204 if (StoreInst* S = dyn_cast<StoreInst>(query)) {
205 dependee = S->getPointerOperand();
206 dependeeSize = TD.getTypeSize(S->getOperand(0)->getType());
207 queryIsVolatile = S->isVolatile();
208 } else if (LoadInst* L = dyn_cast<LoadInst>(query)) {
209 dependee = L->getPointerOperand();
210 dependeeSize = TD.getTypeSize(L->getType());
211 queryIsVolatile = L->isVolatile();
212 } else if (VAArgInst* V = dyn_cast<VAArgInst>(query)) {
213 dependee = V->getOperand(0);
214 dependeeSize = TD.getTypeSize(V->getType());
215 } else if (FreeInst* F = dyn_cast<FreeInst>(query)) {
216 dependee = F->getPointerOperand();
218 // FreeInsts erase the entire structure, not just a field
220 } else if (CallSite::get(query).getInstruction() != 0)
221 return getCallSiteDependency(CallSite::get(query), start);
222 else if (isa<AllocationInst>(query))
227 BasicBlock::iterator blockBegin = block ? block->begin()
228 : query->getParent()->begin();
230 while (QI != blockBegin) {
233 // If this inst is a memory op, get the pointer it accessed
235 uint64_t pointerSize = 0;
236 if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
237 // All volatile loads/stores depend on each other
238 if (queryIsVolatile && S->isVolatile()) {
239 if (!start || block) {
240 depGraphLocal.insert(std::make_pair(query, std::make_pair(S, true)));
241 reverseDep.insert(std::make_pair(S, query));
247 pointer = S->getPointerOperand();
248 pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
249 } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
250 // All volatile loads/stores depend on each other
251 if (queryIsVolatile && L->isVolatile()) {
252 if (!start || block) {
253 depGraphLocal.insert(std::make_pair(query, std::make_pair(L, true)));
254 reverseDep.insert(std::make_pair(L, query));
260 pointer = L->getPointerOperand();
261 pointerSize = TD.getTypeSize(L->getType());
262 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
264 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
265 pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType());
268 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
269 pointer = V->getOperand(0);
270 pointerSize = TD.getTypeSize(V->getType());
271 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
272 pointer = F->getPointerOperand();
274 // FreeInsts erase the entire structure
276 } else if (CallSite::get(QI).getInstruction() != 0) {
277 // Call insts need special handling. Check is they can modify our pointer
278 AliasAnalysis::ModRefResult MR = AA.getModRefInfo(CallSite::get(QI),
279 dependee, dependeeSize);
281 if (MR != AliasAnalysis::NoModRef) {
282 // Loads don't depend on read-only calls
283 if (isa<LoadInst>(query) && MR == AliasAnalysis::Ref)
286 if (!start || block) {
287 depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
288 reverseDep.insert(std::make_pair(QI, query));
297 // If we found a pointer, check if it could be the same as our pointer
299 AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize,
300 dependee, dependeeSize);
302 if (R != AliasAnalysis::NoAlias) {
303 // May-alias loads don't depend on each other
304 if (isa<LoadInst>(query) && isa<LoadInst>(QI) &&
305 R == AliasAnalysis::MayAlias)
308 if (!start || block) {
309 depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
310 reverseDep.insert(std::make_pair(QI, query));
318 // If we found nothing, return the non-local flag
319 if (!start || block) {
320 depGraphLocal.insert(std::make_pair(query,
321 std::make_pair(NonLocal, true)));
322 reverseDep.insert(std::make_pair(NonLocal, query));
328 /// removeInstruction - Remove an instruction from the dependence analysis,
329 /// updating the dependence of instructions that previously depended on it.
330 void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
331 // Figure out the new dep for things that currently depend on rem
332 Instruction* newDep = NonLocal;
334 depMapType::iterator depGraphEntry = depGraphLocal.find(rem);
335 // We assume here that it's not in the reverse map if it's not in
336 // the dep map. Checking it could be expensive, so don't do it.
338 if (depGraphEntry != depGraphLocal.end()) {
339 if (depGraphEntry->second.first != NonLocal &&
340 depGraphEntry->second.second) {
341 // If we have dep info for rem, set them to it
342 BasicBlock::iterator RI = depGraphEntry->second.first;
345 } else if (depGraphEntry->second.first == NonLocal &&
346 depGraphEntry->second.second ) {
347 // If we have a confirmed non-local flag, use it
350 // Otherwise, use the immediate successor of rem
351 // NOTE: This is because, when getDependence is called, it will first check
352 // the immediate predecessor of what is in the cache.
353 BasicBlock::iterator RI = rem;
358 std::multimap<Instruction*, Instruction*>::iterator I = reverseDep.find(rem);
359 while (I != reverseDep.end() && I->first == rem) {
360 // Insert the new dependencies
361 // Mark it as unconfirmed as long as it is not the non-local flag
362 depGraphLocal[I->second] = std::make_pair(newDep, !newDep);
364 I = reverseDep.find(rem);
368 getAnalysis<AliasAnalysis>().deleteValue(rem);