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/Target/TargetData.h"
26 char MemoryDependenceAnalysis::ID = 0;
28 Instruction* MemoryDependenceAnalysis::NonLocal = (Instruction*)0;
29 Instruction* MemoryDependenceAnalysis::None = (Instruction*)~0;
31 // Register this pass...
32 static RegisterPass<MemoryDependenceAnalysis> X("memdep",
33 "Memory Dependence Analysis");
35 /// getAnalysisUsage - Does not modify anything. It uses Alias Analysis.
37 void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
39 AU.addRequiredTransitive<AliasAnalysis>();
40 AU.addRequiredTransitive<TargetData>();
43 // Find the dependency of a CallSite
44 Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, bool local) {
45 assert(local && "Non-local memory dependence analysis not yet implemented");
47 AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
48 TargetData& TD = getAnalysis<TargetData>();
49 BasicBlock::iterator blockBegin = C.getInstruction()->getParent()->begin();
50 BasicBlock::iterator QI = C.getInstruction();
52 while (QI != blockBegin) {
55 // If this inst is a memory op, get the pointer it accessed
57 uint64_t pointerSize = 0;
58 if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
59 pointer = S->getPointerOperand();
60 pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
61 } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
62 pointer = L->getPointerOperand();
63 pointerSize = TD.getTypeSize(L->getType());
64 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
66 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
67 pointerSize = C->getZExtValue();
70 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
71 pointer = V->getOperand(0);
72 pointerSize = TD.getTypeSize(V->getType());
73 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
74 pointer = F->getPointerOperand();
76 // FreeInsts erase the entire structure
78 } else if (CallSite::get(QI).getInstruction() != 0) {
79 if (AA.getModRefInfo(C, CallSite::get(QI)) != AliasAnalysis::NoModRef) {
80 depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(QI, true)));
81 reverseDep.insert(std::make_pair(QI, C.getInstruction()));
89 if (AA.getModRefInfo(C, pointer, pointerSize) != AliasAnalysis::NoModRef) {
90 depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(QI, true)));
91 reverseDep.insert(std::make_pair(QI, C.getInstruction()));
96 // No dependence found
97 depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(NonLocal, true)));
98 reverseDep.insert(std::make_pair(NonLocal, C.getInstruction()));
102 /// getDependency - Return the instruction on which a memory operation
103 /// depends. The local paramter indicates if the query should only
104 /// evaluate dependencies within the same basic block.
105 Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
108 assert(0 && "Non-local memory dependence is not yet supported.");
110 // Start looking for dependencies with the queried inst
111 BasicBlock::iterator QI = query;
113 // Check for a cached result
114 std::pair<Instruction*, bool> cachedResult = depGraphLocal[query];
115 // If we have a _confirmed_ cached entry, return it
116 if (cachedResult.second)
117 return cachedResult.first;
118 else if (cachedResult.first != NonLocal)
119 // If we have an unconfirmed cached entry, we can start our search from there
120 QI = cachedResult.first;
122 AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
123 TargetData& TD = getAnalysis<TargetData>();
125 // Get the pointer value for which dependence will be determined
127 uint64_t dependeeSize = 0;
128 bool queryIsVolatile = false;
129 if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
130 dependee = S->getPointerOperand();
131 dependeeSize = TD.getTypeSize(S->getOperand(0)->getType());
132 queryIsVolatile = S->isVolatile();
133 } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
134 dependee = L->getPointerOperand();
135 dependeeSize = TD.getTypeSize(L->getType());
136 queryIsVolatile = L->isVolatile();
137 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
138 dependee = V->getOperand(0);
139 dependeeSize = TD.getTypeSize(V->getType());
140 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
141 dependee = F->getPointerOperand();
143 // FreeInsts erase the entire structure, not just a field
145 } else if (CallSite::get(QI).getInstruction() != 0)
146 return getCallSiteDependency(CallSite::get(QI));
147 else if (isa<AllocationInst>(query))
152 BasicBlock::iterator blockBegin = query->getParent()->begin();
154 while (QI != blockBegin) {
157 // If this inst is a memory op, get the pointer it accessed
159 uint64_t pointerSize = 0;
160 if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
161 // All volatile loads/stores depend on each other
162 if (queryIsVolatile && S->isVolatile()) {
163 depGraphLocal.insert(std::make_pair(query, std::make_pair(S, true)));
164 reverseDep.insert(std::make_pair(S, query));
168 pointer = S->getPointerOperand();
169 pointerSize = TD.getTypeSize(S->getOperand(0)->getType());
170 } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
171 // All volatile loads/stores depend on each other
172 if (queryIsVolatile && L->isVolatile()) {
173 depGraphLocal.insert(std::make_pair(query, std::make_pair(L, true)));
174 reverseDep.insert(std::make_pair(L, query));
178 pointer = L->getPointerOperand();
179 pointerSize = TD.getTypeSize(L->getType());
180 } else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
182 if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
183 pointerSize = C->getZExtValue();
186 } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
187 pointer = V->getOperand(0);
188 pointerSize = TD.getTypeSize(V->getType());
189 } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
190 pointer = F->getPointerOperand();
192 // FreeInsts erase the entire structure
194 } else if (CallSite::get(QI).getInstruction() != 0) {
195 // Call insts need special handling. Check is they can modify our pointer
196 if (AA.getModRefInfo(CallSite::get(QI), dependee, dependeeSize) !=
197 AliasAnalysis::NoModRef) {
198 depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
199 reverseDep.insert(std::make_pair(QI, query));
206 // If we found a pointer, check if it could be the same as our pointer
208 AliasAnalysis::AliasResult R = AA.alias(pointer, pointerSize,
209 dependee, dependeeSize);
211 if (R != AliasAnalysis::NoAlias) {
212 depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
213 reverseDep.insert(std::make_pair(QI, query));
219 // If we found nothing, return the non-local flag
220 depGraphLocal.insert(std::make_pair(query,
221 std::make_pair(NonLocal, true)));
222 reverseDep.insert(std::make_pair(NonLocal, query));
227 /// removeInstruction - Remove an instruction from the dependence analysis,
228 /// updating the dependence of instructions that previously depended on it.
229 void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
230 // Figure out the new dep for things that currently depend on rem
231 Instruction* newDep = NonLocal;
232 if (depGraphLocal[rem].first != NonLocal) {
233 // If we have dep info for rem, set them to it
234 BasicBlock::iterator RI = depGraphLocal[rem].first;
237 } else if (depGraphLocal[rem].first == NonLocal &&
238 depGraphLocal[rem].second ) {
239 // If we have a confirmed non-local flag, use it
242 // Otherwise, use the immediate successor of rem
243 // NOTE: This is because, when getDependence is called, it will first check
244 // the immediate predecessor of what is in the cache.
245 BasicBlock::iterator RI = rem;
250 std::multimap<Instruction*, Instruction*>::iterator I = reverseDep.find(rem);
251 while (I->first == rem) {
252 // Insert the new dependencies
253 // Mark it as unconfirmed as long as it is not the non-local flag
254 depGraphLocal[I->second] = std::make_pair(newDep, !newDep);
256 I = reverseDep.find(rem);