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 bool MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
106 DenseMap<BasicBlock*, Value*>& resp,
107 SmallPtrSet<BasicBlock*, 4>& visited) {
108 if (resp.count(block))
109 return resp[block] != None;
111 Instruction* localDep = getDependency(query, 0, block);
112 if (localDep != NonLocal) {
113 resp.insert(std::make_pair(block, localDep));
117 visited.insert(block);
119 bool inserted = false;
120 bool predOnStack = false;
121 for (pred_iterator PI = pred_begin(block), PE = pred_end(block);
123 if (!visited.count(*PI))
124 inserted |= nonLocalHelper(query, *PI, resp, visited);
128 visited.erase(block);
130 if (!inserted && !predOnStack)
131 resp.insert(std::make_pair(block, None));
132 else if (inserted && predOnStack)
133 resp.insert(std::make_pair(block, NonLocal));
138 bool MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
139 DenseMap<BasicBlock*, Value*>& resp) {
140 Instruction* localDep = getDependency(query);
141 if (localDep != NonLocal) {
142 resp.insert(std::make_pair(query->getParent(), localDep));
146 bool inserted = false;
147 SmallPtrSet<BasicBlock*, 4> visited;
148 visited.insert(query->getParent());
150 BasicBlock* parent = query->getParent();
151 for (pred_iterator PI = pred_begin(parent), PE = pred_end(parent);
153 if (!visited.count(*PI))
154 inserted |= nonLocalHelper(query, *PI, resp, visited);
158 resp.insert(std::make_pair(query->getParent(), None));
163 /// getDependency - Return the instruction on which a memory operation
164 /// depends. The local paramter indicates if the query should only
165 /// evaluate dependencies within the same basic block.
166 Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
169 // Start looking for dependencies with the queried inst
170 BasicBlock::iterator QI = query;
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;
177 else if (cachedResult.first && cachedResult.first != NonLocal)
178 // If we have an unconfirmed cached entry, we can start our search from there
179 QI = cachedResult.first;
183 else if (!start && block)
186 AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
187 TargetData& TD = getAnalysis<TargetData>();
189 // Get the pointer value for which dependence will be determined
191 uint64_t dependeeSize = 0;
192 bool queryIsVolatile = false;
193 if (StoreInst* S = dyn_cast<StoreInst>(query)) {
194 dependee = S->getPointerOperand();
195 dependeeSize = TD.getTypeSize(S->getOperand(0)->getType());
196 queryIsVolatile = S->isVolatile();
197 } else if (LoadInst* L = dyn_cast<LoadInst>(query)) {
198 dependee = L->getPointerOperand();
199 dependeeSize = TD.getTypeSize(L->getType());
200 queryIsVolatile = L->isVolatile();
201 } else if (VAArgInst* V = dyn_cast<VAArgInst>(query)) {
202 dependee = V->getOperand(0);
203 dependeeSize = TD.getTypeSize(V->getType());
204 } else if (FreeInst* F = dyn_cast<FreeInst>(query)) {
205 dependee = F->getPointerOperand();
207 // FreeInsts erase the entire structure, not just a field
209 } else if (CallSite::get(query).getInstruction() != 0)
210 return getCallSiteDependency(CallSite::get(query), start);
211 else if (isa<AllocationInst>(query))
216 BasicBlock::iterator blockBegin = block ? block->begin()
217 : query->getParent()->begin();
219 while (QI != blockBegin) {
222 // If this inst is a memory op, get the pointer it accessed
224 uint64_t pointerSize = 0;
225 if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
226 // All volatile loads/stores depend on each other
227 if (queryIsVolatile && S->isVolatile()) {
228 if (!start || block) {
229 depGraphLocal.insert(std::make_pair(query, std::make_pair(S, true)));
230 reverseDep.insert(std::make_pair(S, query));
236 pointer = S->getPointerOperand();
237 pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
238 } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
239 // All volatile loads/stores depend on each other
240 if (queryIsVolatile && L->isVolatile()) {
241 if (!start || block) {
242 depGraphLocal.insert(std::make_pair(query, std::make_pair(L, true)));
243 reverseDep.insert(std::make_pair(L, query));
249 pointer = L->getPointerOperand();
250 pointerSize = TD.getTypeSize(L->getType());
251 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
253 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
254 pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType());
257 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
258 pointer = V->getOperand(0);
259 pointerSize = TD.getTypeSize(V->getType());
260 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
261 pointer = F->getPointerOperand();
263 // FreeInsts erase the entire structure
265 } else if (CallSite::get(QI).getInstruction() != 0) {
266 // Call insts need special handling. Check is they can modify our pointer
267 if (AA.getModRefInfo(CallSite::get(QI), dependee, dependeeSize) !=
268 AliasAnalysis::NoModRef) {
269 if (!start || block) {
270 depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
271 reverseDep.insert(std::make_pair(QI, query));
280 // If we found a pointer, check if it could be the same as our pointer
282 AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize,
283 dependee, dependeeSize);
285 if (R != AliasAnalysis::NoAlias) {
286 if (!start || block) {
287 depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
288 reverseDep.insert(std::make_pair(QI, query));
296 // If we found nothing, return the non-local flag
297 if (!start || block) {
298 depGraphLocal.insert(std::make_pair(query,
299 std::make_pair(NonLocal, true)));
300 reverseDep.insert(std::make_pair(NonLocal, query));
306 /// removeInstruction - Remove an instruction from the dependence analysis,
307 /// updating the dependence of instructions that previously depended on it.
308 void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
309 // Figure out the new dep for things that currently depend on rem
310 Instruction* newDep = NonLocal;
311 if (depGraphLocal[rem].first != NonLocal &&
312 depGraphLocal[rem].second) {
313 // If we have dep info for rem, set them to it
314 BasicBlock::iterator RI = depGraphLocal[rem].first;
317 } else if (depGraphLocal[rem].first == NonLocal &&
318 depGraphLocal[rem].second ) {
319 // If we have a confirmed non-local flag, use it
322 // Otherwise, use the immediate successor of rem
323 // NOTE: This is because, when getDependence is called, it will first check
324 // the immediate predecessor of what is in the cache.
325 BasicBlock::iterator RI = rem;
330 std::multimap<Instruction*, Instruction*>::iterator I = reverseDep.find(rem);
331 while (I->first == rem) {
332 // Insert the new dependencies
333 // Mark it as unconfirmed as long as it is not the non-local flag
334 depGraphLocal[I->second] = std::make_pair(newDep, !newDep);
336 I = reverseDep.find(rem);
339 getAnalysis<AliasAnalysis>().deleteValue(rem);