Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 1 | //===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation --*- C++ -*-===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 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 |
Owen Anderson | 80b1f09 | 2007-08-08 22:01:54 +0000 | [diff] [blame] | 12 | // alias analysis information, and tries to provide a lazy, caching interface to |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 13 | // a common kind of alias information query. |
| 14 | // |
| 15 | //===----------------------------------------------------------------------===// |
| 16 | |
Chris Lattner | 0e575f4 | 2008-11-28 21:45:17 +0000 | [diff] [blame] | 17 | #define DEBUG_TYPE "memdep" |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 18 | #include "llvm/Analysis/MemoryDependenceAnalysis.h" |
Owen Anderson | 7a616a1 | 2007-07-10 17:25:03 +0000 | [diff] [blame] | 19 | #include "llvm/Constants.h" |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 20 | #include "llvm/Instructions.h" |
| 21 | #include "llvm/Function.h" |
| 22 | #include "llvm/Analysis/AliasAnalysis.h" |
Chris Lattner | baad888 | 2008-11-28 22:28:27 +0000 | [diff] [blame] | 23 | #include "llvm/ADT/Statistic.h" |
| 24 | #include "llvm/ADT/STLExtras.h" |
Owen Anderson | 4beedbd | 2007-07-24 21:52:37 +0000 | [diff] [blame] | 25 | #include "llvm/Support/CFG.h" |
Tanya Lattner | 63aa160 | 2008-02-06 00:54:55 +0000 | [diff] [blame] | 26 | #include "llvm/Support/CommandLine.h" |
Chris Lattner | 0e575f4 | 2008-11-28 21:45:17 +0000 | [diff] [blame] | 27 | #include "llvm/Support/Debug.h" |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 28 | #include "llvm/Target/TargetData.h" |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 29 | using namespace llvm; |
| 30 | |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 31 | // Control the calculation of non-local dependencies by only examining the |
| 32 | // predecessors if the basic block has less than X amount (50 by default). |
| 33 | static cl::opt<int> |
| 34 | PredLimit("nonlocaldep-threshold", cl::Hidden, cl::init(50), |
| 35 | cl::desc("Control the calculation of non-local" |
| 36 | "dependencies (default = 50)")); |
Tanya Lattner | 63aa160 | 2008-02-06 00:54:55 +0000 | [diff] [blame] | 37 | |
Owen Anderson | 7fad7e3 | 2007-09-09 21:43:49 +0000 | [diff] [blame] | 38 | STATISTIC(NumCacheNonlocal, "Number of cached non-local responses"); |
| 39 | STATISTIC(NumUncacheNonlocal, "Number of uncached non-local responses"); |
| 40 | |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 41 | char MemoryDependenceAnalysis::ID = 0; |
| 42 | |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 43 | // Register this pass... |
Owen Anderson | 776ee1f | 2007-07-10 20:21:08 +0000 | [diff] [blame] | 44 | static RegisterPass<MemoryDependenceAnalysis> X("memdep", |
Chris Lattner | 0e575f4 | 2008-11-28 21:45:17 +0000 | [diff] [blame] | 45 | "Memory Dependence Analysis", false, true); |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 46 | |
Chris Lattner | 0e575f4 | 2008-11-28 21:45:17 +0000 | [diff] [blame] | 47 | /// verifyRemoved - Verify that the specified instruction does not occur |
| 48 | /// in our internal data structures. |
Chris Lattner | 8b589fa | 2008-11-28 21:42:09 +0000 | [diff] [blame] | 49 | void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const { |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 50 | for (LocalDepMapType::const_iterator I = LocalDeps.begin(), |
| 51 | E = LocalDeps.end(); I != E; ++I) { |
Chris Lattner | 0e575f4 | 2008-11-28 21:45:17 +0000 | [diff] [blame] | 52 | assert(I->first != D && "Inst occurs in data structures"); |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 53 | assert(I->second.getPointer() != D && |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 54 | "Inst occurs in data structures"); |
Owen Anderson | 5fc4aba | 2007-12-08 01:37:09 +0000 | [diff] [blame] | 55 | } |
| 56 | |
Chris Lattner | 8b589fa | 2008-11-28 21:42:09 +0000 | [diff] [blame] | 57 | for (nonLocalDepMapType::const_iterator I = depGraphNonLocal.begin(), |
| 58 | E = depGraphNonLocal.end(); I != E; ++I) { |
Chris Lattner | 0e575f4 | 2008-11-28 21:45:17 +0000 | [diff] [blame] | 59 | assert(I->first != D && "Inst occurs in data structures"); |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 60 | for (DenseMap<BasicBlock*, DepResultTy>::iterator II = I->second.begin(), |
Owen Anderson | d8f34fa | 2008-06-01 20:51:41 +0000 | [diff] [blame] | 61 | EE = I->second.end(); II != EE; ++II) |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 62 | assert(II->second.getPointer() != D && "Inst occurs in data structures"); |
Owen Anderson | 5fc4aba | 2007-12-08 01:37:09 +0000 | [diff] [blame] | 63 | } |
| 64 | |
Chris Lattner | 8b589fa | 2008-11-28 21:42:09 +0000 | [diff] [blame] | 65 | for (reverseDepMapType::const_iterator I = reverseDep.begin(), |
| 66 | E = reverseDep.end(); I != E; ++I) |
| 67 | for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(), |
| 68 | EE = I->second.end(); II != EE; ++II) |
Chris Lattner | 0e575f4 | 2008-11-28 21:45:17 +0000 | [diff] [blame] | 69 | assert(*II != D && "Inst occurs in data structures"); |
Owen Anderson | 5fc4aba | 2007-12-08 01:37:09 +0000 | [diff] [blame] | 70 | |
Chris Lattner | 8b589fa | 2008-11-28 21:42:09 +0000 | [diff] [blame] | 71 | for (reverseDepMapType::const_iterator I = reverseDepNonLocal.begin(), |
| 72 | E = reverseDepNonLocal.end(); |
Owen Anderson | 5fc4aba | 2007-12-08 01:37:09 +0000 | [diff] [blame] | 73 | I != E; ++I) |
Chris Lattner | 8b589fa | 2008-11-28 21:42:09 +0000 | [diff] [blame] | 74 | for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(), |
| 75 | EE = I->second.end(); II != EE; ++II) |
Chris Lattner | 0e575f4 | 2008-11-28 21:45:17 +0000 | [diff] [blame] | 76 | assert(*II != D && "Inst occurs in data structures"); |
Owen Anderson | 5fc4aba | 2007-12-08 01:37:09 +0000 | [diff] [blame] | 77 | } |
| 78 | |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 79 | /// getAnalysisUsage - Does not modify anything. It uses Alias Analysis. |
| 80 | /// |
| 81 | void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { |
| 82 | AU.setPreservesAll(); |
| 83 | AU.addRequiredTransitive<AliasAnalysis>(); |
| 84 | AU.addRequiredTransitive<TargetData>(); |
| 85 | } |
| 86 | |
Owen Anderson | 642a9e3 | 2007-08-08 22:26:03 +0000 | [diff] [blame] | 87 | /// getCallSiteDependency - Private helper for finding the local dependencies |
| 88 | /// of a call site. |
Chris Lattner | 4c72400 | 2008-11-29 02:29:27 +0000 | [diff] [blame] | 89 | MemDepResult MemoryDependenceAnalysis:: |
Chris Lattner | 5391a1d | 2008-11-29 03:47:00 +0000 | [diff] [blame] | 90 | getCallSiteDependency(CallSite C, BasicBlock::iterator ScanIt, |
| 91 | BasicBlock *BB) { |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 92 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
| 93 | TargetData &TD = getAnalysis<TargetData>(); |
Owen Anderson | dbbe816 | 2007-08-07 00:33:45 +0000 | [diff] [blame] | 94 | |
Owen Anderson | 642a9e3 | 2007-08-08 22:26:03 +0000 | [diff] [blame] | 95 | // Walk backwards through the block, looking for dependencies |
Chris Lattner | 5391a1d | 2008-11-29 03:47:00 +0000 | [diff] [blame] | 96 | while (ScanIt != BB->begin()) { |
| 97 | Instruction *Inst = --ScanIt; |
Owen Anderson | 5f32320 | 2007-07-10 17:59:22 +0000 | [diff] [blame] | 98 | |
| 99 | // If this inst is a memory op, get the pointer it accessed |
Chris Lattner | 00314b3 | 2008-11-29 09:15:21 +0000 | [diff] [blame^] | 100 | Value *Pointer = 0; |
| 101 | uint64_t PointerSize = 0; |
| 102 | if (StoreInst *S = dyn_cast<StoreInst>(Inst)) { |
| 103 | Pointer = S->getPointerOperand(); |
| 104 | PointerSize = TD.getTypeStoreSize(S->getOperand(0)->getType()); |
| 105 | } else if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) { |
| 106 | Pointer = AI; |
| 107 | if (ConstantInt *C = dyn_cast<ConstantInt>(AI->getArraySize())) |
| 108 | PointerSize = C->getZExtValue() * |
Chris Lattner | 25a0814 | 2008-11-29 08:51:16 +0000 | [diff] [blame] | 109 | TD.getTypeStoreSize(AI->getAllocatedType()); |
Owen Anderson | 5f32320 | 2007-07-10 17:59:22 +0000 | [diff] [blame] | 110 | else |
Chris Lattner | 00314b3 | 2008-11-29 09:15:21 +0000 | [diff] [blame^] | 111 | PointerSize = ~0UL; |
| 112 | } else if (VAArgInst *V = dyn_cast<VAArgInst>(Inst)) { |
| 113 | Pointer = V->getOperand(0); |
| 114 | PointerSize = TD.getTypeStoreSize(V->getType()); |
| 115 | } else if (FreeInst *F = dyn_cast<FreeInst>(Inst)) { |
| 116 | Pointer = F->getPointerOperand(); |
Owen Anderson | 5f32320 | 2007-07-10 17:59:22 +0000 | [diff] [blame] | 117 | |
| 118 | // FreeInsts erase the entire structure |
Chris Lattner | 00314b3 | 2008-11-29 09:15:21 +0000 | [diff] [blame^] | 119 | PointerSize = ~0UL; |
| 120 | } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) { |
| 121 | if (AA.getModRefBehavior(CallSite::get(Inst)) == |
Chris Lattner | 5391a1d | 2008-11-29 03:47:00 +0000 | [diff] [blame] | 122 | AliasAnalysis::DoesNotAccessMemory) |
Chris Lattner | 00314b3 | 2008-11-29 09:15:21 +0000 | [diff] [blame^] | 123 | continue; |
| 124 | return MemDepResult::get(Inst); |
Owen Anderson | 202da14 | 2007-07-10 20:39:07 +0000 | [diff] [blame] | 125 | } else |
| 126 | continue; |
Owen Anderson | 5f32320 | 2007-07-10 17:59:22 +0000 | [diff] [blame] | 127 | |
Chris Lattner | 00314b3 | 2008-11-29 09:15:21 +0000 | [diff] [blame^] | 128 | if (AA.getModRefInfo(C, Pointer, PointerSize) != AliasAnalysis::NoModRef) |
Chris Lattner | 5391a1d | 2008-11-29 03:47:00 +0000 | [diff] [blame] | 129 | return MemDepResult::get(Inst); |
Owen Anderson | 5f32320 | 2007-07-10 17:59:22 +0000 | [diff] [blame] | 130 | } |
| 131 | |
Chris Lattner | 5391a1d | 2008-11-29 03:47:00 +0000 | [diff] [blame] | 132 | // No dependence found. |
Chris Lattner | 4c72400 | 2008-11-29 02:29:27 +0000 | [diff] [blame] | 133 | return MemDepResult::getNonLocal(); |
Owen Anderson | 5f32320 | 2007-07-10 17:59:22 +0000 | [diff] [blame] | 134 | } |
| 135 | |
Owen Anderson | 642a9e3 | 2007-08-08 22:26:03 +0000 | [diff] [blame] | 136 | /// nonLocalHelper - Private helper used to calculate non-local dependencies |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 137 | /// by doing DFS on the predecessors of a block to find its dependencies. |
Owen Anderson | 9066020 | 2007-08-01 22:01:54 +0000 | [diff] [blame] | 138 | void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query, |
Owen Anderson | 0cd3203 | 2007-07-25 19:57:03 +0000 | [diff] [blame] | 139 | BasicBlock* block, |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 140 | DenseMap<BasicBlock*, DepResultTy> &resp) { |
Owen Anderson | 642a9e3 | 2007-08-08 22:26:03 +0000 | [diff] [blame] | 141 | // Set of blocks that we've already visited in our DFS |
Owen Anderson | 9066020 | 2007-08-01 22:01:54 +0000 | [diff] [blame] | 142 | SmallPtrSet<BasicBlock*, 4> visited; |
Owen Anderson | ce4d88a | 2007-09-21 03:53:52 +0000 | [diff] [blame] | 143 | // If we're updating a dirtied cache entry, we don't need to reprocess |
| 144 | // already computed entries. |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 145 | for (DenseMap<BasicBlock*, DepResultTy>::iterator I = resp.begin(), |
Owen Anderson | ce4d88a | 2007-09-21 03:53:52 +0000 | [diff] [blame] | 146 | E = resp.end(); I != E; ++I) |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 147 | if (I->second.getInt() != Dirty) |
Owen Anderson | ce4d88a | 2007-09-21 03:53:52 +0000 | [diff] [blame] | 148 | visited.insert(I->first); |
| 149 | |
Owen Anderson | 642a9e3 | 2007-08-08 22:26:03 +0000 | [diff] [blame] | 150 | // Current stack of the DFS |
Owen Anderson | 9066020 | 2007-08-01 22:01:54 +0000 | [diff] [blame] | 151 | SmallVector<BasicBlock*, 4> stack; |
Owen Anderson | f062f10 | 2008-04-10 22:13:32 +0000 | [diff] [blame] | 152 | for (pred_iterator PI = pred_begin(block), PE = pred_end(block); |
| 153 | PI != PE; ++PI) |
| 154 | stack.push_back(*PI); |
Owen Anderson | 4beedbd | 2007-07-24 21:52:37 +0000 | [diff] [blame] | 155 | |
Owen Anderson | 642a9e3 | 2007-08-08 22:26:03 +0000 | [diff] [blame] | 156 | // Do a basic DFS |
Owen Anderson | 9066020 | 2007-08-01 22:01:54 +0000 | [diff] [blame] | 157 | while (!stack.empty()) { |
| 158 | BasicBlock* BB = stack.back(); |
| 159 | |
Owen Anderson | 642a9e3 | 2007-08-08 22:26:03 +0000 | [diff] [blame] | 160 | // If we've already visited this block, no need to revist |
Owen Anderson | 1c2763d | 2007-08-02 17:56:05 +0000 | [diff] [blame] | 161 | if (visited.count(BB)) { |
Owen Anderson | 9066020 | 2007-08-01 22:01:54 +0000 | [diff] [blame] | 162 | stack.pop_back(); |
| 163 | continue; |
| 164 | } |
| 165 | |
Owen Anderson | 642a9e3 | 2007-08-08 22:26:03 +0000 | [diff] [blame] | 166 | // If we find a new block with a local dependency for query, |
| 167 | // then we insert the new dependency and backtrack. |
Owen Anderson | 9066020 | 2007-08-01 22:01:54 +0000 | [diff] [blame] | 168 | if (BB != block) { |
Owen Anderson | 1c2763d | 2007-08-02 17:56:05 +0000 | [diff] [blame] | 169 | visited.insert(BB); |
| 170 | |
Chris Lattner | 5391a1d | 2008-11-29 03:47:00 +0000 | [diff] [blame] | 171 | MemDepResult localDep = getDependencyFrom(query, BB->end(), BB); |
Chris Lattner | 4c72400 | 2008-11-29 02:29:27 +0000 | [diff] [blame] | 172 | if (!localDep.isNonLocal()) { |
| 173 | resp.insert(std::make_pair(BB, ConvFromResult(localDep))); |
Owen Anderson | 1c2763d | 2007-08-02 17:56:05 +0000 | [diff] [blame] | 174 | stack.pop_back(); |
Owen Anderson | 9066020 | 2007-08-01 22:01:54 +0000 | [diff] [blame] | 175 | continue; |
| 176 | } |
Owen Anderson | 642a9e3 | 2007-08-08 22:26:03 +0000 | [diff] [blame] | 177 | // If we re-encounter the starting block, we still need to search it |
| 178 | // because there might be a dependency in the starting block AFTER |
| 179 | // the position of the query. This is necessary to get loops right. |
Owen Anderson | f062f10 | 2008-04-10 22:13:32 +0000 | [diff] [blame] | 180 | } else if (BB == block) { |
Owen Anderson | 1c2763d | 2007-08-02 17:56:05 +0000 | [diff] [blame] | 181 | visited.insert(BB); |
| 182 | |
Chris Lattner | 5391a1d | 2008-11-29 03:47:00 +0000 | [diff] [blame] | 183 | MemDepResult localDep = getDependencyFrom(query, BB->end(), BB); |
Chris Lattner | 4c72400 | 2008-11-29 02:29:27 +0000 | [diff] [blame] | 184 | if (localDep.getInst() != query) |
| 185 | resp.insert(std::make_pair(BB, ConvFromResult(localDep))); |
Owen Anderson | 1c2763d | 2007-08-02 17:56:05 +0000 | [diff] [blame] | 186 | |
| 187 | stack.pop_back(); |
Owen Anderson | 1c2763d | 2007-08-02 17:56:05 +0000 | [diff] [blame] | 188 | continue; |
Owen Anderson | 9066020 | 2007-08-01 22:01:54 +0000 | [diff] [blame] | 189 | } |
| 190 | |
Owen Anderson | 642a9e3 | 2007-08-08 22:26:03 +0000 | [diff] [blame] | 191 | // If we didn't find anything, recurse on the precessors of this block |
Tanya Lattner | 63aa160 | 2008-02-06 00:54:55 +0000 | [diff] [blame] | 192 | // Only do this for blocks with a small number of predecessors. |
Owen Anderson | 9066020 | 2007-08-01 22:01:54 +0000 | [diff] [blame] | 193 | bool predOnStack = false; |
| 194 | bool inserted = false; |
Tanya Lattner | 63aa160 | 2008-02-06 00:54:55 +0000 | [diff] [blame] | 195 | if (std::distance(pred_begin(BB), pred_end(BB)) <= PredLimit) { |
| 196 | for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); |
| 197 | PI != PE; ++PI) |
| 198 | if (!visited.count(*PI)) { |
| 199 | stack.push_back(*PI); |
| 200 | inserted = true; |
| 201 | } else |
| 202 | predOnStack = true; |
| 203 | } |
Owen Anderson | 9066020 | 2007-08-01 22:01:54 +0000 | [diff] [blame] | 204 | |
Owen Anderson | 642a9e3 | 2007-08-08 22:26:03 +0000 | [diff] [blame] | 205 | // If we inserted a new predecessor, then we'll come back to this block |
Owen Anderson | 9066020 | 2007-08-01 22:01:54 +0000 | [diff] [blame] | 206 | if (inserted) |
| 207 | continue; |
Owen Anderson | 642a9e3 | 2007-08-08 22:26:03 +0000 | [diff] [blame] | 208 | // If we didn't insert because we have no predecessors, then this |
| 209 | // query has no dependency at all. |
Owen Anderson | 9066020 | 2007-08-01 22:01:54 +0000 | [diff] [blame] | 210 | else if (!inserted && !predOnStack) { |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 211 | resp.insert(std::make_pair(BB, DepResultTy(0, None))); |
Owen Anderson | 642a9e3 | 2007-08-08 22:26:03 +0000 | [diff] [blame] | 212 | // If we didn't insert because our predecessors are already on the stack, |
| 213 | // then we might still have a dependency, but it will be discovered during |
| 214 | // backtracking. |
Owen Anderson | 9066020 | 2007-08-01 22:01:54 +0000 | [diff] [blame] | 215 | } else if (!inserted && predOnStack){ |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 216 | resp.insert(std::make_pair(BB, DepResultTy(0, NonLocal))); |
Owen Anderson | 9066020 | 2007-08-01 22:01:54 +0000 | [diff] [blame] | 217 | } |
| 218 | |
| 219 | stack.pop_back(); |
Owen Anderson | 4beedbd | 2007-07-24 21:52:37 +0000 | [diff] [blame] | 220 | } |
Owen Anderson | 4beedbd | 2007-07-24 21:52:37 +0000 | [diff] [blame] | 221 | } |
| 222 | |
Owen Anderson | 80b1f09 | 2007-08-08 22:01:54 +0000 | [diff] [blame] | 223 | /// getNonLocalDependency - Fills the passed-in map with the non-local |
| 224 | /// dependencies of the queries. The map will contain NonLocal for |
| 225 | /// blocks between the query and its dependencies. |
Owen Anderson | 9066020 | 2007-08-01 22:01:54 +0000 | [diff] [blame] | 226 | void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query, |
Chris Lattner | 4c72400 | 2008-11-29 02:29:27 +0000 | [diff] [blame] | 227 | DenseMap<BasicBlock*, MemDepResult> &resp) { |
Owen Anderson | 4d13de4 | 2007-08-16 21:27:05 +0000 | [diff] [blame] | 228 | if (depGraphNonLocal.count(query)) { |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 229 | DenseMap<BasicBlock*, DepResultTy> &cached = depGraphNonLocal[query]; |
Owen Anderson | 7fad7e3 | 2007-09-09 21:43:49 +0000 | [diff] [blame] | 230 | NumCacheNonlocal++; |
Owen Anderson | ce4d88a | 2007-09-21 03:53:52 +0000 | [diff] [blame] | 231 | |
| 232 | SmallVector<BasicBlock*, 4> dirtied; |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 233 | for (DenseMap<BasicBlock*, DepResultTy>::iterator I = cached.begin(), |
Owen Anderson | ce4d88a | 2007-09-21 03:53:52 +0000 | [diff] [blame] | 234 | E = cached.end(); I != E; ++I) |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 235 | if (I->second.getInt() == Dirty) |
Owen Anderson | ce4d88a | 2007-09-21 03:53:52 +0000 | [diff] [blame] | 236 | dirtied.push_back(I->first); |
| 237 | |
| 238 | for (SmallVector<BasicBlock*, 4>::iterator I = dirtied.begin(), |
| 239 | E = dirtied.end(); I != E; ++I) { |
Chris Lattner | 5391a1d | 2008-11-29 03:47:00 +0000 | [diff] [blame] | 240 | MemDepResult localDep = getDependencyFrom(query, (*I)->end(), *I); |
Chris Lattner | 4c72400 | 2008-11-29 02:29:27 +0000 | [diff] [blame] | 241 | if (!localDep.isNonLocal()) |
| 242 | cached[*I] = ConvFromResult(localDep); |
Owen Anderson | ce4d88a | 2007-09-21 03:53:52 +0000 | [diff] [blame] | 243 | else { |
| 244 | cached.erase(*I); |
| 245 | nonLocalHelper(query, *I, cached); |
| 246 | } |
| 247 | } |
| 248 | |
Chris Lattner | 4c72400 | 2008-11-29 02:29:27 +0000 | [diff] [blame] | 249 | // Update the reverse non-local dependency cache. |
| 250 | for (DenseMap<BasicBlock*, DepResultTy>::iterator I = cached.begin(), |
| 251 | E = cached.end(); I != E; ++I) { |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 252 | if (Instruction *Inst = I->second.getPointer()) |
| 253 | reverseDepNonLocal[Inst].insert(query); |
Chris Lattner | 4c72400 | 2008-11-29 02:29:27 +0000 | [diff] [blame] | 254 | resp[I->first] = ConvToResult(I->second); |
| 255 | } |
Owen Anderson | 6bd15ce | 2008-06-01 21:03:52 +0000 | [diff] [blame] | 256 | |
Owen Anderson | 4d13de4 | 2007-08-16 21:27:05 +0000 | [diff] [blame] | 257 | return; |
Chris Lattner | 4c72400 | 2008-11-29 02:29:27 +0000 | [diff] [blame] | 258 | } |
| 259 | |
| 260 | NumUncacheNonlocal++; |
Owen Anderson | 4d13de4 | 2007-08-16 21:27:05 +0000 | [diff] [blame] | 261 | |
Owen Anderson | 7fad7e3 | 2007-09-09 21:43:49 +0000 | [diff] [blame] | 262 | // If not, go ahead and search for non-local deps. |
Chris Lattner | 4c72400 | 2008-11-29 02:29:27 +0000 | [diff] [blame] | 263 | DenseMap<BasicBlock*, DepResultTy> &cached = depGraphNonLocal[query]; |
| 264 | nonLocalHelper(query, query->getParent(), cached); |
| 265 | |
Owen Anderson | 4d13de4 | 2007-08-16 21:27:05 +0000 | [diff] [blame] | 266 | // Update the non-local dependency cache |
Chris Lattner | 4c72400 | 2008-11-29 02:29:27 +0000 | [diff] [blame] | 267 | for (DenseMap<BasicBlock*, DepResultTy>::iterator I = cached.begin(), |
| 268 | E = cached.end(); I != E; ++I) { |
| 269 | // FIXME: Merge with the code above! |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 270 | if (Instruction *Inst = I->second.getPointer()) |
| 271 | reverseDepNonLocal[Inst].insert(query); |
Chris Lattner | 4c72400 | 2008-11-29 02:29:27 +0000 | [diff] [blame] | 272 | resp[I->first] = ConvToResult(I->second); |
Owen Anderson | 4d13de4 | 2007-08-16 21:27:05 +0000 | [diff] [blame] | 273 | } |
Owen Anderson | 4beedbd | 2007-07-24 21:52:37 +0000 | [diff] [blame] | 274 | } |
| 275 | |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 276 | /// getDependency - Return the instruction on which a memory operation |
Dan Gohman | c04575f | 2008-04-10 23:02:38 +0000 | [diff] [blame] | 277 | /// depends. The local parameter indicates if the query should only |
Owen Anderson | 6b278fc | 2007-07-10 17:08:11 +0000 | [diff] [blame] | 278 | /// evaluate dependencies within the same basic block. |
Chris Lattner | 5391a1d | 2008-11-29 03:47:00 +0000 | [diff] [blame] | 279 | MemDepResult MemoryDependenceAnalysis:: |
| 280 | getDependencyFrom(Instruction *QueryInst, BasicBlock::iterator ScanIt, |
| 281 | BasicBlock *BB) { |
| 282 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
| 283 | TargetData &TD = getAnalysis<TargetData>(); |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 284 | |
| 285 | // Get the pointer value for which dependence will be determined |
Chris Lattner | 25a0814 | 2008-11-29 08:51:16 +0000 | [diff] [blame] | 286 | Value *MemPtr = 0; |
| 287 | uint64_t MemSize = 0; |
| 288 | bool MemVolatile = false; |
Chris Lattner | 5391a1d | 2008-11-29 03:47:00 +0000 | [diff] [blame] | 289 | |
| 290 | if (StoreInst* S = dyn_cast<StoreInst>(QueryInst)) { |
Chris Lattner | 25a0814 | 2008-11-29 08:51:16 +0000 | [diff] [blame] | 291 | MemPtr = S->getPointerOperand(); |
| 292 | MemSize = TD.getTypeStoreSize(S->getOperand(0)->getType()); |
| 293 | MemVolatile = S->isVolatile(); |
Chris Lattner | 5391a1d | 2008-11-29 03:47:00 +0000 | [diff] [blame] | 294 | } else if (LoadInst* L = dyn_cast<LoadInst>(QueryInst)) { |
Chris Lattner | 25a0814 | 2008-11-29 08:51:16 +0000 | [diff] [blame] | 295 | MemPtr = L->getPointerOperand(); |
| 296 | MemSize = TD.getTypeStoreSize(L->getType()); |
| 297 | MemVolatile = L->isVolatile(); |
Chris Lattner | 5391a1d | 2008-11-29 03:47:00 +0000 | [diff] [blame] | 298 | } else if (VAArgInst* V = dyn_cast<VAArgInst>(QueryInst)) { |
Chris Lattner | 25a0814 | 2008-11-29 08:51:16 +0000 | [diff] [blame] | 299 | MemPtr = V->getOperand(0); |
| 300 | MemSize = TD.getTypeStoreSize(V->getType()); |
Chris Lattner | 5391a1d | 2008-11-29 03:47:00 +0000 | [diff] [blame] | 301 | } else if (FreeInst* F = dyn_cast<FreeInst>(QueryInst)) { |
Chris Lattner | 25a0814 | 2008-11-29 08:51:16 +0000 | [diff] [blame] | 302 | MemPtr = F->getPointerOperand(); |
| 303 | // FreeInsts erase the entire structure, not just a field. |
| 304 | MemSize = ~0UL; |
| 305 | } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) |
Chris Lattner | 5391a1d | 2008-11-29 03:47:00 +0000 | [diff] [blame] | 306 | return getCallSiteDependency(CallSite::get(QueryInst), ScanIt, BB); |
Chris Lattner | 25a0814 | 2008-11-29 08:51:16 +0000 | [diff] [blame] | 307 | else // Non-memory instructions depend on nothing. |
Chris Lattner | 4c72400 | 2008-11-29 02:29:27 +0000 | [diff] [blame] | 308 | return MemDepResult::getNone(); |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 309 | |
Owen Anderson | 642a9e3 | 2007-08-08 22:26:03 +0000 | [diff] [blame] | 310 | // Walk backwards through the basic block, looking for dependencies |
Chris Lattner | 5391a1d | 2008-11-29 03:47:00 +0000 | [diff] [blame] | 311 | while (ScanIt != BB->begin()) { |
| 312 | Instruction *Inst = --ScanIt; |
Chris Lattner | a161ab0 | 2008-11-29 09:09:48 +0000 | [diff] [blame] | 313 | |
| 314 | // If the access is volatile and this is a volatile load/store, return a |
| 315 | // dependence. |
| 316 | if (MemVolatile && |
| 317 | ((isa<LoadInst>(Inst) && cast<LoadInst>(Inst)->isVolatile()) || |
| 318 | (isa<StoreInst>(Inst) && cast<StoreInst>(Inst)->isVolatile()))) |
Chris Lattner | 25a0814 | 2008-11-29 08:51:16 +0000 | [diff] [blame] | 319 | return MemDepResult::get(Inst); |
Chris Lattner | a161ab0 | 2008-11-29 09:09:48 +0000 | [diff] [blame] | 320 | |
| 321 | // MemDep is broken w.r.t. loads: it says that two loads of the same pointer |
| 322 | // depend on each other. :( |
| 323 | // FIXME: ELIMINATE THIS! |
| 324 | if (LoadInst *L = dyn_cast<LoadInst>(Inst)) { |
| 325 | Value *Pointer = L->getPointerOperand(); |
| 326 | uint64_t PointerSize = TD.getTypeStoreSize(L->getType()); |
| 327 | |
| 328 | // If we found a pointer, check if it could be the same as our pointer |
| 329 | AliasAnalysis::AliasResult R = |
| 330 | AA.alias(Pointer, PointerSize, MemPtr, MemSize); |
| 331 | |
| 332 | if (R == AliasAnalysis::NoAlias) |
| 333 | continue; |
| 334 | |
| 335 | // May-alias loads don't depend on each other without a dependence. |
| 336 | if (isa<LoadInst>(QueryInst) && R == AliasAnalysis::MayAlias) |
| 337 | continue; |
| 338 | return MemDepResult::get(Inst); |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 339 | } |
| 340 | |
Chris Lattner | a161ab0 | 2008-11-29 09:09:48 +0000 | [diff] [blame] | 341 | // FIXME: This claims that an access depends on the allocation. This may |
| 342 | // make sense, but is dubious at best. It would be better to fix GVN to |
| 343 | // handle a 'None' Query. |
| 344 | if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) { |
| 345 | Value *Pointer = AI; |
| 346 | uint64_t PointerSize; |
| 347 | if (ConstantInt *C = dyn_cast<ConstantInt>(AI->getArraySize())) |
| 348 | PointerSize = C->getZExtValue() * |
| 349 | TD.getTypeStoreSize(AI->getAllocatedType()); |
| 350 | else |
| 351 | PointerSize = ~0UL; |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 352 | |
Chris Lattner | a161ab0 | 2008-11-29 09:09:48 +0000 | [diff] [blame] | 353 | AliasAnalysis::AliasResult R = |
| 354 | AA.alias(Pointer, PointerSize, MemPtr, MemSize); |
| 355 | |
| 356 | if (R == AliasAnalysis::NoAlias) |
| 357 | continue; |
| 358 | return MemDepResult::get(Inst); |
| 359 | } |
| 360 | |
| 361 | |
| 362 | // See if this instruction mod/ref's the pointer. |
| 363 | AliasAnalysis::ModRefResult MRR = AA.getModRefInfo(Inst, MemPtr, MemSize); |
| 364 | |
| 365 | if (MRR == AliasAnalysis::NoModRef) |
Chris Lattner | 25a0814 | 2008-11-29 08:51:16 +0000 | [diff] [blame] | 366 | continue; |
| 367 | |
Chris Lattner | a161ab0 | 2008-11-29 09:09:48 +0000 | [diff] [blame] | 368 | // Loads don't depend on read-only instructions. |
| 369 | if (isa<LoadInst>(QueryInst) && MRR == AliasAnalysis::Ref) |
Chris Lattner | 25a0814 | 2008-11-29 08:51:16 +0000 | [diff] [blame] | 370 | continue; |
Chris Lattner | a161ab0 | 2008-11-29 09:09:48 +0000 | [diff] [blame] | 371 | |
| 372 | // Otherwise, there is a dependence. |
Chris Lattner | 25a0814 | 2008-11-29 08:51:16 +0000 | [diff] [blame] | 373 | return MemDepResult::get(Inst); |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 374 | } |
| 375 | |
Chris Lattner | 5391a1d | 2008-11-29 03:47:00 +0000 | [diff] [blame] | 376 | // If we found nothing, return the non-local flag. |
Chris Lattner | 4c72400 | 2008-11-29 02:29:27 +0000 | [diff] [blame] | 377 | return MemDepResult::getNonLocal(); |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 378 | } |
| 379 | |
Chris Lattner | 5391a1d | 2008-11-29 03:47:00 +0000 | [diff] [blame] | 380 | /// getDependency - Return the instruction on which a memory operation |
| 381 | /// depends. |
| 382 | MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { |
| 383 | Instruction *ScanPos = QueryInst; |
| 384 | |
| 385 | // Check for a cached result |
| 386 | DepResultTy &LocalCache = LocalDeps[QueryInst]; |
| 387 | |
| 388 | // If the cached entry is non-dirty, just return it. |
| 389 | if (LocalCache.getInt() != Dirty) |
| 390 | return ConvToResult(LocalCache); |
| 391 | |
| 392 | // Otherwise, if we have a dirty entry, we know we can start the scan at that |
| 393 | // instruction, which may save us some work. |
| 394 | if (Instruction *Inst = LocalCache.getPointer()) |
| 395 | ScanPos = Inst; |
| 396 | |
| 397 | // Do the scan. |
| 398 | MemDepResult Res = |
| 399 | getDependencyFrom(QueryInst, ScanPos, QueryInst->getParent()); |
| 400 | |
| 401 | // Remember the result! |
| 402 | // FIXME: Don't convert back and forth! Make a shared helper function. |
| 403 | LocalCache = ConvFromResult(Res); |
| 404 | if (Instruction *I = Res.getInst()) |
| 405 | reverseDep[I].insert(QueryInst); |
| 406 | |
| 407 | return Res; |
| 408 | } |
| 409 | |
| 410 | |
Owen Anderson | 30b4bd4 | 2008-02-12 21:15:18 +0000 | [diff] [blame] | 411 | /// dropInstruction - Remove an instruction from the analysis, making |
| 412 | /// absolutely conservative assumptions when updating the cache. This is |
| 413 | /// useful, for example when an instruction is changed rather than removed. |
| 414 | void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) { |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 415 | LocalDepMapType::iterator depGraphEntry = LocalDeps.find(drop); |
| 416 | if (depGraphEntry != LocalDeps.end()) |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 417 | if (Instruction *Inst = depGraphEntry->second.getPointer()) |
| 418 | reverseDep[Inst].erase(drop); |
Owen Anderson | 30b4bd4 | 2008-02-12 21:15:18 +0000 | [diff] [blame] | 419 | |
| 420 | // Drop dependency information for things that depended on this instr |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 421 | SmallPtrSet<Instruction*, 4>& set = reverseDep[drop]; |
Owen Anderson | 30b4bd4 | 2008-02-12 21:15:18 +0000 | [diff] [blame] | 422 | for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); |
| 423 | I != E; ++I) |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 424 | LocalDeps.erase(*I); |
Owen Anderson | 30b4bd4 | 2008-02-12 21:15:18 +0000 | [diff] [blame] | 425 | |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 426 | LocalDeps.erase(drop); |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 427 | reverseDep.erase(drop); |
Owen Anderson | 30b4bd4 | 2008-02-12 21:15:18 +0000 | [diff] [blame] | 428 | |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 429 | for (DenseMap<BasicBlock*, DepResultTy>::iterator DI = |
| 430 | depGraphNonLocal[drop].begin(), DE = depGraphNonLocal[drop].end(); |
Owen Anderson | 30b4bd4 | 2008-02-12 21:15:18 +0000 | [diff] [blame] | 431 | DI != DE; ++DI) |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 432 | if (Instruction *Inst = DI->second.getPointer()) |
| 433 | reverseDepNonLocal[Inst].erase(drop); |
Owen Anderson | 30b4bd4 | 2008-02-12 21:15:18 +0000 | [diff] [blame] | 434 | |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 435 | if (reverseDepNonLocal.count(drop)) { |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 436 | SmallPtrSet<Instruction*, 4>& set = |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 437 | reverseDepNonLocal[drop]; |
Owen Anderson | 30b4bd4 | 2008-02-12 21:15:18 +0000 | [diff] [blame] | 438 | for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); |
| 439 | I != E; ++I) |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 440 | for (DenseMap<BasicBlock*, DepResultTy>::iterator DI = |
Owen Anderson | 30b4bd4 | 2008-02-12 21:15:18 +0000 | [diff] [blame] | 441 | depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end(); |
| 442 | DI != DE; ++DI) |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 443 | if (DI->second == DepResultTy(drop, Normal)) |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 444 | // FIXME: Why not remember the old insertion point?? |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 445 | DI->second = DepResultTy(0, Dirty); |
Owen Anderson | 30b4bd4 | 2008-02-12 21:15:18 +0000 | [diff] [blame] | 446 | } |
| 447 | |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 448 | reverseDepNonLocal.erase(drop); |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 449 | depGraphNonLocal.erase(drop); |
Owen Anderson | 30b4bd4 | 2008-02-12 21:15:18 +0000 | [diff] [blame] | 450 | } |
| 451 | |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 452 | /// removeInstruction - Remove an instruction from the dependence analysis, |
| 453 | /// updating the dependence of instructions that previously depended on it. |
Owen Anderson | 642a9e3 | 2007-08-08 22:26:03 +0000 | [diff] [blame] | 454 | /// This method attempts to keep the cache coherent using the reverse map. |
Chris Lattner | 5f589dc | 2008-11-28 22:04:47 +0000 | [diff] [blame] | 455 | void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { |
Chris Lattner | 5f589dc | 2008-11-28 22:04:47 +0000 | [diff] [blame] | 456 | // Walk through the Non-local dependencies, removing this one as the value |
| 457 | // for any cached queries. |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 458 | for (DenseMap<BasicBlock*, DepResultTy>::iterator DI = |
Chris Lattner | 5f589dc | 2008-11-28 22:04:47 +0000 | [diff] [blame] | 459 | depGraphNonLocal[RemInst].begin(), DE = depGraphNonLocal[RemInst].end(); |
Owen Anderson | 5fc4aba | 2007-12-08 01:37:09 +0000 | [diff] [blame] | 460 | DI != DE; ++DI) |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 461 | if (Instruction *Inst = DI->second.getPointer()) |
| 462 | reverseDepNonLocal[Inst].erase(RemInst); |
Owen Anderson | 5fc4aba | 2007-12-08 01:37:09 +0000 | [diff] [blame] | 463 | |
Chris Lattner | baad888 | 2008-11-28 22:28:27 +0000 | [diff] [blame] | 464 | // Shortly after this, we will look for things that depend on RemInst. In |
| 465 | // order to update these, we'll need a new dependency to base them on. We |
| 466 | // could completely delete any entries that depend on this, but it is better |
| 467 | // to make a more accurate approximation where possible. Compute that better |
| 468 | // approximation if we can. |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 469 | DepResultTy NewDependency; |
Chris Lattner | baad888 | 2008-11-28 22:28:27 +0000 | [diff] [blame] | 470 | |
Chris Lattner | 5f589dc | 2008-11-28 22:04:47 +0000 | [diff] [blame] | 471 | // If we have a cached local dependence query for this instruction, remove it. |
Chris Lattner | baad888 | 2008-11-28 22:28:27 +0000 | [diff] [blame] | 472 | // |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 473 | LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst); |
| 474 | if (LocalDepEntry != LocalDeps.end()) { |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 475 | DepResultTy LocalDep = LocalDepEntry->second; |
Owen Anderson | 9a8ff8c | 2008-01-30 01:24:05 +0000 | [diff] [blame] | 476 | |
Chris Lattner | baad888 | 2008-11-28 22:28:27 +0000 | [diff] [blame] | 477 | // Remove this local dependency info. |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 478 | LocalDeps.erase(LocalDepEntry); |
Chris Lattner | 5f589dc | 2008-11-28 22:04:47 +0000 | [diff] [blame] | 479 | |
Chris Lattner | baad888 | 2008-11-28 22:28:27 +0000 | [diff] [blame] | 480 | // Remove us from DepInst's reverse set now that the local dep info is gone. |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 481 | if (Instruction *Inst = LocalDep.getPointer()) |
| 482 | reverseDep[Inst].erase(RemInst); |
Chris Lattner | baad888 | 2008-11-28 22:28:27 +0000 | [diff] [blame] | 483 | |
| 484 | // If we have unconfirmed info, don't trust it. |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 485 | if (LocalDep.getInt() != Dirty) { |
Chris Lattner | baad888 | 2008-11-28 22:28:27 +0000 | [diff] [blame] | 486 | // If we have a confirmed non-local flag, use it. |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 487 | if (LocalDep.getInt() == NonLocal || LocalDep.getInt() == None) { |
Chris Lattner | d3d12ec | 2008-11-28 22:51:08 +0000 | [diff] [blame] | 488 | // The only time this dependency is confirmed is if it is non-local. |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 489 | NewDependency = LocalDep; |
Chris Lattner | baad888 | 2008-11-28 22:28:27 +0000 | [diff] [blame] | 490 | } else { |
| 491 | // If we have dep info for RemInst, set them to it. |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 492 | Instruction *NDI = next(BasicBlock::iterator(LocalDep.getPointer())); |
| 493 | if (NDI != RemInst) // Don't use RemInst for the new dependency! |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 494 | NewDependency = DepResultTy(NDI, Dirty); |
Chris Lattner | baad888 | 2008-11-28 22:28:27 +0000 | [diff] [blame] | 495 | } |
David Greene | df46419 | 2007-07-31 20:01:27 +0000 | [diff] [blame] | 496 | } |
Owen Anderson | a8701a6 | 2008-02-05 04:34:03 +0000 | [diff] [blame] | 497 | } |
| 498 | |
Chris Lattner | baad888 | 2008-11-28 22:28:27 +0000 | [diff] [blame] | 499 | // If we don't already have a local dependency answer for this instruction, |
| 500 | // use the immediate successor of RemInst. We use the successor because |
| 501 | // getDependence starts by checking the immediate predecessor of what is in |
| 502 | // the cache. |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 503 | if (NewDependency == DepResultTy(0, Dirty)) |
| 504 | NewDependency = DepResultTy(next(BasicBlock::iterator(RemInst)), Dirty); |
Chris Lattner | baad888 | 2008-11-28 22:28:27 +0000 | [diff] [blame] | 505 | |
Chris Lattner | d3d12ec | 2008-11-28 22:51:08 +0000 | [diff] [blame] | 506 | // Loop over all of the things that depend on the instruction we're removing. |
| 507 | // |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 508 | reverseDepMapType::iterator ReverseDepIt = reverseDep.find(RemInst); |
Chris Lattner | d3d12ec | 2008-11-28 22:51:08 +0000 | [diff] [blame] | 509 | if (ReverseDepIt != reverseDep.end()) { |
| 510 | SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second; |
| 511 | for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(), |
| 512 | E = ReverseDeps.end(); I != E; ++I) { |
| 513 | Instruction *InstDependingOnRemInst = *I; |
| 514 | |
| 515 | // If we thought the instruction depended on itself (possible for |
| 516 | // unconfirmed dependencies) ignore the update. |
| 517 | if (InstDependingOnRemInst == RemInst) continue; |
| 518 | |
| 519 | // Insert the new dependencies. |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 520 | LocalDeps[InstDependingOnRemInst] = NewDependency; |
Chris Lattner | d3d12ec | 2008-11-28 22:51:08 +0000 | [diff] [blame] | 521 | |
| 522 | // If our NewDependency is an instruction, make sure to remember that new |
| 523 | // things depend on it. |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 524 | if (Instruction *Inst = NewDependency.getPointer()) |
| 525 | reverseDep[Inst].insert(InstDependingOnRemInst); |
Chris Lattner | d3d12ec | 2008-11-28 22:51:08 +0000 | [diff] [blame] | 526 | } |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 527 | reverseDep.erase(RemInst); |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 528 | } |
Owen Anderson | 4d13de4 | 2007-08-16 21:27:05 +0000 | [diff] [blame] | 529 | |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 530 | ReverseDepIt = reverseDepNonLocal.find(RemInst); |
Chris Lattner | d3d12ec | 2008-11-28 22:51:08 +0000 | [diff] [blame] | 531 | if (ReverseDepIt != reverseDepNonLocal.end()) { |
| 532 | SmallPtrSet<Instruction*, 4>& set = ReverseDepIt->second; |
Owen Anderson | 4d13de4 | 2007-08-16 21:27:05 +0000 | [diff] [blame] | 533 | for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end(); |
| 534 | I != E; ++I) |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 535 | for (DenseMap<BasicBlock*, DepResultTy>::iterator DI = |
Owen Anderson | ce4d88a | 2007-09-21 03:53:52 +0000 | [diff] [blame] | 536 | depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end(); |
| 537 | DI != DE; ++DI) |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 538 | if (DI->second == DepResultTy(RemInst, Normal)) |
Chris Lattner | 7f52422 | 2008-11-29 03:22:12 +0000 | [diff] [blame] | 539 | // FIXME: Why not remember the old insertion point?? |
Chris Lattner | 39f372e | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 540 | DI->second = DepResultTy(0, Dirty); |
| 541 | reverseDepNonLocal.erase(ReverseDepIt); |
Owen Anderson | 4d13de4 | 2007-08-16 21:27:05 +0000 | [diff] [blame] | 542 | } |
Owen Anderson | 5fc4aba | 2007-12-08 01:37:09 +0000 | [diff] [blame] | 543 | |
Chris Lattner | 5f589dc | 2008-11-28 22:04:47 +0000 | [diff] [blame] | 544 | depGraphNonLocal.erase(RemInst); |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 545 | |
Chris Lattner | 5f589dc | 2008-11-28 22:04:47 +0000 | [diff] [blame] | 546 | getAnalysis<AliasAnalysis>().deleteValue(RemInst); |
Chris Lattner | 0e575f4 | 2008-11-28 21:45:17 +0000 | [diff] [blame] | 547 | |
Chris Lattner | 5f589dc | 2008-11-28 22:04:47 +0000 | [diff] [blame] | 548 | DEBUG(verifyRemoved(RemInst)); |
Owen Anderson | 78e02f7 | 2007-07-06 23:14:35 +0000 | [diff] [blame] | 549 | } |