Duncan Sands | e0aa0d6 | 2009-01-18 12:19:30 +0000 | [diff] [blame] | 1 | //===--- CaptureTracking.cpp - Determine whether a pointer is captured ----===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file contains routines that help determine which pointers are captured. |
| 11 | // A pointer value is captured if the function makes a copy of any part of the |
| 12 | // pointer that outlives the call. Not being captured means, more or less, that |
| 13 | // the pointer is only dereferenced and not stored in a global. Returning part |
| 14 | // of the pointer as the function return value may or may not count as capturing |
| 15 | // the pointer, depending on the context. |
| 16 | // |
| 17 | //===----------------------------------------------------------------------===// |
| 18 | |
Chandler Carruth | 6bda14b | 2017-06-06 11:49:48 +0000 | [diff] [blame] | 19 | #include "llvm/Analysis/CaptureTracking.h" |
Jakub Staszak | 173bce3 | 2012-01-17 22:16:31 +0000 | [diff] [blame] | 20 | #include "llvm/ADT/SmallSet.h" |
| 21 | #include "llvm/ADT/SmallVector.h" |
Jakub Staszak | c733bf2 | 2013-03-10 00:34:01 +0000 | [diff] [blame] | 22 | #include "llvm/Analysis/AliasAnalysis.h" |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 23 | #include "llvm/Analysis/CFG.h" |
Bruno Cardoso Lopes | dfc1d96 | 2015-07-31 14:31:35 +0000 | [diff] [blame] | 24 | #include "llvm/Analysis/OrderedBasicBlock.h" |
Chandler Carruth | 219b89b | 2014-03-04 11:01:28 +0000 | [diff] [blame] | 25 | #include "llvm/IR/CallSite.h" |
Jakub Staszak | c733bf2 | 2013-03-10 00:34:01 +0000 | [diff] [blame] | 26 | #include "llvm/IR/Constants.h" |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 27 | #include "llvm/IR/Dominators.h" |
Jakub Staszak | c733bf2 | 2013-03-10 00:34:01 +0000 | [diff] [blame] | 28 | #include "llvm/IR/Instructions.h" |
David Majnemer | 7f32420 | 2016-05-26 17:36:22 +0000 | [diff] [blame] | 29 | #include "llvm/IR/IntrinsicInst.h" |
Jakub Staszak | c733bf2 | 2013-03-10 00:34:01 +0000 | [diff] [blame] | 30 | |
Duncan Sands | e0aa0d6 | 2009-01-18 12:19:30 +0000 | [diff] [blame] | 31 | using namespace llvm; |
| 32 | |
Nick Lewycky | aa2a00d | 2011-11-21 18:32:21 +0000 | [diff] [blame] | 33 | CaptureTracker::~CaptureTracker() {} |
| 34 | |
Chandler Carruth | 64e9aa5 | 2014-03-05 10:21:48 +0000 | [diff] [blame] | 35 | bool CaptureTracker::shouldExplore(const Use *U) { return true; } |
Nick Lewycky | 7c3b5d9 | 2012-10-08 22:12:48 +0000 | [diff] [blame] | 36 | |
Nick Lewycky | 7013a19 | 2011-11-14 22:49:42 +0000 | [diff] [blame] | 37 | namespace { |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 38 | struct SimpleCaptureTracker : public CaptureTracker { |
Nick Lewycky | 7013a19 | 2011-11-14 22:49:42 +0000 | [diff] [blame] | 39 | explicit SimpleCaptureTracker(bool ReturnCaptures) |
| 40 | : ReturnCaptures(ReturnCaptures), Captured(false) {} |
| 41 | |
Craig Topper | e9ba759 | 2014-03-05 07:30:04 +0000 | [diff] [blame] | 42 | void tooManyUses() override { Captured = true; } |
Nick Lewycky | 7013a19 | 2011-11-14 22:49:42 +0000 | [diff] [blame] | 43 | |
Chandler Carruth | 64e9aa5 | 2014-03-05 10:21:48 +0000 | [diff] [blame] | 44 | bool captured(const Use *U) override { |
Nick Lewycky | 4c378a4 | 2011-12-28 23:24:21 +0000 | [diff] [blame] | 45 | if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures) |
Chad Rosier | 8244b1d | 2012-05-10 23:38:07 +0000 | [diff] [blame] | 46 | return false; |
Nick Lewycky | 7013a19 | 2011-11-14 22:49:42 +0000 | [diff] [blame] | 47 | |
| 48 | Captured = true; |
| 49 | return true; |
| 50 | } |
| 51 | |
| 52 | bool ReturnCaptures; |
| 53 | |
| 54 | bool Captured; |
| 55 | }; |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 56 | |
| 57 | /// Only find pointer captures which happen before the given instruction. Uses |
| 58 | /// the dominator tree to determine whether one instruction is before another. |
| 59 | /// Only support the case where the Value is defined in the same basic block |
| 60 | /// as the given instruction and the use. |
| 61 | struct CapturesBefore : public CaptureTracker { |
Bruno Cardoso Lopes | 7900ef8 | 2015-06-24 17:53:17 +0000 | [diff] [blame] | 62 | |
Hal Finkel | d32803b | 2014-07-21 21:30:22 +0000 | [diff] [blame] | 63 | CapturesBefore(bool ReturnCaptures, const Instruction *I, DominatorTree *DT, |
Bruno Cardoso Lopes | dfc1d96 | 2015-07-31 14:31:35 +0000 | [diff] [blame] | 64 | bool IncludeI, OrderedBasicBlock *IC) |
| 65 | : OrderedBB(IC), BeforeHere(I), DT(DT), |
Bruno Cardoso Lopes | 7900ef8 | 2015-06-24 17:53:17 +0000 | [diff] [blame] | 66 | ReturnCaptures(ReturnCaptures), IncludeI(IncludeI), Captured(false) {} |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 67 | |
| 68 | void tooManyUses() override { Captured = true; } |
| 69 | |
Bruno Cardoso Lopes | 7900ef8 | 2015-06-24 17:53:17 +0000 | [diff] [blame] | 70 | bool isSafeToPrune(Instruction *I) { |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 71 | BasicBlock *BB = I->getParent(); |
| 72 | // We explore this usage only if the usage can reach "BeforeHere". |
| 73 | // If use is not reachable from entry, there is no need to explore. |
| 74 | if (BeforeHere != I && !DT->isReachableFromEntry(BB)) |
Bruno Cardoso Lopes | 7900ef8 | 2015-06-24 17:53:17 +0000 | [diff] [blame] | 75 | return true; |
| 76 | |
| 77 | // Compute the case where both instructions are inside the same basic |
| 78 | // block. Since instructions in the same BB as BeforeHere are numbered in |
Bruno Cardoso Lopes | dfc1d96 | 2015-07-31 14:31:35 +0000 | [diff] [blame] | 79 | // 'OrderedBB', avoid using 'dominates' and 'isPotentiallyReachable' |
Bruno Cardoso Lopes | 7900ef8 | 2015-06-24 17:53:17 +0000 | [diff] [blame] | 80 | // which are very expensive for large basic blocks. |
| 81 | if (BB == BeforeHere->getParent()) { |
| 82 | // 'I' dominates 'BeforeHere' => not safe to prune. |
| 83 | // |
David Majnemer | 8a1c45d | 2015-12-12 05:38:55 +0000 | [diff] [blame] | 84 | // The value defined by an invoke dominates an instruction only |
David Majnemer | 0bc0eef | 2015-08-15 02:46:08 +0000 | [diff] [blame] | 85 | // if it dominates every instruction in UseBB. A PHI is dominated only |
| 86 | // if the instruction dominates every possible use in the UseBB. Since |
Bruno Cardoso Lopes | 7900ef8 | 2015-06-24 17:53:17 +0000 | [diff] [blame] | 87 | // UseBB == BB, avoid pruning. |
David Majnemer | 8a1c45d | 2015-12-12 05:38:55 +0000 | [diff] [blame] | 88 | if (isa<InvokeInst>(BeforeHere) || isa<PHINode>(I) || I == BeforeHere) |
Bruno Cardoso Lopes | 7900ef8 | 2015-06-24 17:53:17 +0000 | [diff] [blame] | 89 | return false; |
Bruno Cardoso Lopes | dfc1d96 | 2015-07-31 14:31:35 +0000 | [diff] [blame] | 90 | if (!OrderedBB->dominates(BeforeHere, I)) |
Bruno Cardoso Lopes | 7900ef8 | 2015-06-24 17:53:17 +0000 | [diff] [blame] | 91 | return false; |
| 92 | |
| 93 | // 'BeforeHere' comes before 'I', it's safe to prune if we also |
| 94 | // guarantee that 'I' never reaches 'BeforeHere' through a back-edge or |
| 95 | // by its successors, i.e, prune if: |
| 96 | // |
| 97 | // (1) BB is an entry block or have no sucessors. |
| 98 | // (2) There's no path coming back through BB sucessors. |
| 99 | if (BB == &BB->getParent()->getEntryBlock() || |
| 100 | !BB->getTerminator()->getNumSuccessors()) |
| 101 | return true; |
| 102 | |
| 103 | SmallVector<BasicBlock*, 32> Worklist; |
| 104 | Worklist.append(succ_begin(BB), succ_end(BB)); |
Alexander Kornienko | 484e48e3 | 2015-11-05 21:07:12 +0000 | [diff] [blame] | 105 | return !isPotentiallyReachableFromMany(Worklist, BB, DT); |
Bruno Cardoso Lopes | 7900ef8 | 2015-06-24 17:53:17 +0000 | [diff] [blame] | 106 | } |
| 107 | |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 108 | // If the value is defined in the same basic block as use and BeforeHere, |
| 109 | // there is no need to explore the use if BeforeHere dominates use. |
| 110 | // Check whether there is a path from I to BeforeHere. |
| 111 | if (BeforeHere != I && DT->dominates(BeforeHere, I) && |
| 112 | !isPotentiallyReachable(I, BeforeHere, DT)) |
Bruno Cardoso Lopes | 7900ef8 | 2015-06-24 17:53:17 +0000 | [diff] [blame] | 113 | return true; |
| 114 | |
| 115 | return false; |
| 116 | } |
| 117 | |
| 118 | bool shouldExplore(const Use *U) override { |
| 119 | Instruction *I = cast<Instruction>(U->getUser()); |
| 120 | |
| 121 | if (BeforeHere == I && !IncludeI) |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 122 | return false; |
Bruno Cardoso Lopes | 7900ef8 | 2015-06-24 17:53:17 +0000 | [diff] [blame] | 123 | |
| 124 | if (isSafeToPrune(I)) |
| 125 | return false; |
| 126 | |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 127 | return true; |
| 128 | } |
| 129 | |
| 130 | bool captured(const Use *U) override { |
| 131 | if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures) |
| 132 | return false; |
| 133 | |
Bruno Cardoso Lopes | 7900ef8 | 2015-06-24 17:53:17 +0000 | [diff] [blame] | 134 | if (!shouldExplore(U)) |
Hal Finkel | d32803b | 2014-07-21 21:30:22 +0000 | [diff] [blame] | 135 | return false; |
| 136 | |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 137 | Captured = true; |
| 138 | return true; |
| 139 | } |
| 140 | |
Bruno Cardoso Lopes | dfc1d96 | 2015-07-31 14:31:35 +0000 | [diff] [blame] | 141 | OrderedBasicBlock *OrderedBB; |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 142 | const Instruction *BeforeHere; |
| 143 | DominatorTree *DT; |
| 144 | |
| 145 | bool ReturnCaptures; |
Hal Finkel | d32803b | 2014-07-21 21:30:22 +0000 | [diff] [blame] | 146 | bool IncludeI; |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 147 | |
| 148 | bool Captured; |
| 149 | }; |
Alexander Kornienko | f00654e | 2015-06-23 09:49:53 +0000 | [diff] [blame] | 150 | } |
Dan Gohman | 2d27b19 | 2009-12-08 23:59:12 +0000 | [diff] [blame] | 151 | |
Duncan Sands | e0aa0d6 | 2009-01-18 12:19:30 +0000 | [diff] [blame] | 152 | /// PointerMayBeCaptured - Return true if this pointer value may be captured |
| 153 | /// by the enclosing function (which is required to exist). This routine can |
| 154 | /// be expensive, so consider caching the results. The boolean ReturnCaptures |
| 155 | /// specifies whether returning the value (or part of it) from the function |
Dan Gohman | 94e6176 | 2009-11-19 21:57:48 +0000 | [diff] [blame] | 156 | /// counts as capturing it or not. The boolean StoreCaptures specified whether |
| 157 | /// storing the value (or part of it) into memory anywhere automatically |
Duncan Sands | e0aa0d6 | 2009-01-18 12:19:30 +0000 | [diff] [blame] | 158 | /// counts as capturing it or not. |
Dan Gohman | 94e6176 | 2009-11-19 21:57:48 +0000 | [diff] [blame] | 159 | bool llvm::PointerMayBeCaptured(const Value *V, |
| 160 | bool ReturnCaptures, bool StoreCaptures) { |
Nick Lewycky | 063ae58 | 2011-11-21 19:42:56 +0000 | [diff] [blame] | 161 | assert(!isa<GlobalValue>(V) && |
| 162 | "It doesn't make sense to ask whether a global is captured."); |
| 163 | |
Nick Lewycky | 7013a19 | 2011-11-14 22:49:42 +0000 | [diff] [blame] | 164 | // TODO: If StoreCaptures is not true, we could do Fancy analysis |
| 165 | // to determine whether this store is not actually an escape point. |
| 166 | // In that case, BasicAliasAnalysis should be updated as well to |
| 167 | // take advantage of this. |
| 168 | (void)StoreCaptures; |
Duncan Sands | e0aa0d6 | 2009-01-18 12:19:30 +0000 | [diff] [blame] | 169 | |
Nick Lewycky | 7013a19 | 2011-11-14 22:49:42 +0000 | [diff] [blame] | 170 | SimpleCaptureTracker SCT(ReturnCaptures); |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 171 | PointerMayBeCaptured(V, &SCT); |
Nick Lewycky | 7013a19 | 2011-11-14 22:49:42 +0000 | [diff] [blame] | 172 | return SCT.Captured; |
Duncan Sands | e0aa0d6 | 2009-01-18 12:19:30 +0000 | [diff] [blame] | 173 | } |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 174 | |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 175 | /// PointerMayBeCapturedBefore - Return true if this pointer value may be |
| 176 | /// captured by the enclosing function (which is required to exist). If a |
| 177 | /// DominatorTree is provided, only captures which happen before the given |
| 178 | /// instruction are considered. This routine can be expensive, so consider |
| 179 | /// caching the results. The boolean ReturnCaptures specifies whether |
| 180 | /// returning the value (or part of it) from the function counts as capturing |
| 181 | /// it or not. The boolean StoreCaptures specified whether storing the value |
| 182 | /// (or part of it) into memory anywhere automatically counts as capturing it |
Bruno Cardoso Lopes | dfc1d96 | 2015-07-31 14:31:35 +0000 | [diff] [blame] | 183 | /// or not. A ordered basic block \p OBB can be used in order to speed up |
| 184 | /// queries about relative order among instructions in the same basic block. |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 185 | bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, |
| 186 | bool StoreCaptures, const Instruction *I, |
Bruno Cardoso Lopes | dfc1d96 | 2015-07-31 14:31:35 +0000 | [diff] [blame] | 187 | DominatorTree *DT, bool IncludeI, |
| 188 | OrderedBasicBlock *OBB) { |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 189 | assert(!isa<GlobalValue>(V) && |
| 190 | "It doesn't make sense to ask whether a global is captured."); |
Bruno Cardoso Lopes | dfc1d96 | 2015-07-31 14:31:35 +0000 | [diff] [blame] | 191 | bool UseNewOBB = OBB == nullptr; |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 192 | |
| 193 | if (!DT) |
| 194 | return PointerMayBeCaptured(V, ReturnCaptures, StoreCaptures); |
Bruno Cardoso Lopes | dfc1d96 | 2015-07-31 14:31:35 +0000 | [diff] [blame] | 195 | if (UseNewOBB) |
| 196 | OBB = new OrderedBasicBlock(I->getParent()); |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 197 | |
| 198 | // TODO: See comment in PointerMayBeCaptured regarding what could be done |
| 199 | // with StoreCaptures. |
| 200 | |
Bruno Cardoso Lopes | dfc1d96 | 2015-07-31 14:31:35 +0000 | [diff] [blame] | 201 | CapturesBefore CB(ReturnCaptures, I, DT, IncludeI, OBB); |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 202 | PointerMayBeCaptured(V, &CB); |
Bruno Cardoso Lopes | dfc1d96 | 2015-07-31 14:31:35 +0000 | [diff] [blame] | 203 | |
| 204 | if (UseNewOBB) |
| 205 | delete OBB; |
Hal Finkel | b035621 | 2014-07-21 13:15:48 +0000 | [diff] [blame] | 206 | return CB.Captured; |
| 207 | } |
| 208 | |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 209 | /// TODO: Write a new FunctionPass AliasAnalysis so that it can keep |
| 210 | /// a cache. Then we can move the code from BasicAliasAnalysis into |
| 211 | /// that path, and remove this threshold. |
| 212 | static int const Threshold = 20; |
| 213 | |
| 214 | void llvm::PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker) { |
| 215 | assert(V->getType()->isPointerTy() && "Capture is for pointers only!"); |
Chandler Carruth | 64e9aa5 | 2014-03-05 10:21:48 +0000 | [diff] [blame] | 216 | SmallVector<const Use *, Threshold> Worklist; |
| 217 | SmallSet<const Use *, Threshold> Visited; |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 218 | int Count = 0; |
| 219 | |
Chandler Carruth | cdf4788 | 2014-03-09 03:16:01 +0000 | [diff] [blame] | 220 | for (const Use &U : V->uses()) { |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 221 | // If there are lots of uses, conservatively say that the value |
| 222 | // is captured to avoid taking too much compile time. |
| 223 | if (Count++ >= Threshold) |
| 224 | return Tracker->tooManyUses(); |
| 225 | |
Chandler Carruth | cdf4788 | 2014-03-09 03:16:01 +0000 | [diff] [blame] | 226 | if (!Tracker->shouldExplore(&U)) continue; |
| 227 | Visited.insert(&U); |
| 228 | Worklist.push_back(&U); |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 229 | } |
| 230 | |
| 231 | while (!Worklist.empty()) { |
Chandler Carruth | 64e9aa5 | 2014-03-05 10:21:48 +0000 | [diff] [blame] | 232 | const Use *U = Worklist.pop_back_val(); |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 233 | Instruction *I = cast<Instruction>(U->getUser()); |
| 234 | V = U->get(); |
| 235 | |
| 236 | switch (I->getOpcode()) { |
| 237 | case Instruction::Call: |
| 238 | case Instruction::Invoke: { |
| 239 | CallSite CS(I); |
| 240 | // Not captured if the callee is readonly, doesn't return a copy through |
| 241 | // its return value and doesn't unwind (a readonly function can leak bits |
| 242 | // by throwing an exception or not depending on the input value). |
| 243 | if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy()) |
| 244 | break; |
| 245 | |
David Majnemer | 7f32420 | 2016-05-26 17:36:22 +0000 | [diff] [blame] | 246 | // Volatile operations effectively capture the memory location that they |
| 247 | // load and store to. |
| 248 | if (auto *MI = dyn_cast<MemIntrinsic>(I)) |
| 249 | if (MI->isVolatile()) |
| 250 | if (Tracker->captured(U)) |
| 251 | return; |
| 252 | |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 253 | // Not captured if only passed via 'nocapture' arguments. Note that |
| 254 | // calling a function pointer does not in itself cause the pointer to |
| 255 | // be captured. This is a subtle point considering that (for example) |
| 256 | // the callee might return its own address. It is analogous to saying |
| 257 | // that loading a value from a pointer does not cause the pointer to be |
| 258 | // captured, even though the loaded value might be the pointer itself |
| 259 | // (think of self-referential objects). |
Sanjoy Das | ea34382 | 2015-11-04 23:21:06 +0000 | [diff] [blame] | 260 | CallSite::data_operand_iterator B = |
| 261 | CS.data_operands_begin(), E = CS.data_operands_end(); |
| 262 | for (CallSite::data_operand_iterator A = B; A != E; ++A) |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 263 | if (A->get() == V && !CS.doesNotCapture(A - B)) |
| 264 | // The parameter is not marked 'nocapture' - captured. |
Nick Lewycky | 4c378a4 | 2011-12-28 23:24:21 +0000 | [diff] [blame] | 265 | if (Tracker->captured(U)) |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 266 | return; |
| 267 | break; |
| 268 | } |
| 269 | case Instruction::Load: |
David Majnemer | 7f32420 | 2016-05-26 17:36:22 +0000 | [diff] [blame] | 270 | // Volatile loads make the address observable. |
| 271 | if (cast<LoadInst>(I)->isVolatile()) |
| 272 | if (Tracker->captured(U)) |
| 273 | return; |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 274 | break; |
| 275 | case Instruction::VAArg: |
| 276 | // "va-arg" from a pointer does not cause it to be captured. |
| 277 | break; |
| 278 | case Instruction::Store: |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 279 | // Stored the pointer - conservatively assume it may be captured. |
David Majnemer | 7f32420 | 2016-05-26 17:36:22 +0000 | [diff] [blame] | 280 | // Volatile stores make the address observable. |
| 281 | if (V == I->getOperand(0) || cast<StoreInst>(I)->isVolatile()) |
Philip Reames | bd09e86 | 2016-02-18 19:23:27 +0000 | [diff] [blame] | 282 | if (Tracker->captured(U)) |
| 283 | return; |
| 284 | break; |
David Majnemer | 7f32420 | 2016-05-26 17:36:22 +0000 | [diff] [blame] | 285 | case Instruction::AtomicRMW: { |
| 286 | // atomicrmw conceptually includes both a load and store from |
| 287 | // the same location. |
| 288 | // As with a store, the location being accessed is not captured, |
| 289 | // but the value being stored is. |
| 290 | // Volatile stores make the address observable. |
| 291 | auto *ARMWI = cast<AtomicRMWInst>(I); |
| 292 | if (ARMWI->getValOperand() == V || ARMWI->isVolatile()) |
| 293 | if (Tracker->captured(U)) |
| 294 | return; |
| 295 | break; |
| 296 | } |
| 297 | case Instruction::AtomicCmpXchg: { |
| 298 | // cmpxchg conceptually includes both a load and store from |
| 299 | // the same location. |
| 300 | // As with a store, the location being accessed is not captured, |
| 301 | // but the value being stored is. |
| 302 | // Volatile stores make the address observable. |
| 303 | auto *ACXI = cast<AtomicCmpXchgInst>(I); |
| 304 | if (ACXI->getCompareOperand() == V || ACXI->getNewValOperand() == V || |
| 305 | ACXI->isVolatile()) |
| 306 | if (Tracker->captured(U)) |
| 307 | return; |
| 308 | break; |
| 309 | } |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 310 | case Instruction::BitCast: |
| 311 | case Instruction::GetElementPtr: |
| 312 | case Instruction::PHI: |
| 313 | case Instruction::Select: |
Matt Arsenault | e55a2c2 | 2014-01-14 19:11:52 +0000 | [diff] [blame] | 314 | case Instruction::AddrSpaceCast: |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 315 | // The original value is not captured via this if the new value isn't. |
Benjamin Kramer | d2757ba | 2013-10-03 13:24:02 +0000 | [diff] [blame] | 316 | Count = 0; |
Chandler Carruth | cdf4788 | 2014-03-09 03:16:01 +0000 | [diff] [blame] | 317 | for (Use &UU : I->uses()) { |
Benjamin Kramer | d2757ba | 2013-10-03 13:24:02 +0000 | [diff] [blame] | 318 | // If there are lots of uses, conservatively say that the value |
| 319 | // is captured to avoid taking too much compile time. |
| 320 | if (Count++ >= Threshold) |
| 321 | return Tracker->tooManyUses(); |
| 322 | |
David Blaikie | 70573dc | 2014-11-19 07:49:26 +0000 | [diff] [blame] | 323 | if (Visited.insert(&UU).second) |
Chandler Carruth | cdf4788 | 2014-03-09 03:16:01 +0000 | [diff] [blame] | 324 | if (Tracker->shouldExplore(&UU)) |
| 325 | Worklist.push_back(&UU); |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 326 | } |
| 327 | break; |
Anna Thomas | 43d7e1c | 2016-05-03 14:58:21 +0000 | [diff] [blame] | 328 | case Instruction::ICmp: { |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 329 | // Don't count comparisons of a no-alias return value against null as |
| 330 | // captures. This allows us to ignore comparisons of malloc results |
| 331 | // with null, for example. |
Nick Lewycky | c2ec072 | 2013-07-06 00:29:58 +0000 | [diff] [blame] | 332 | if (ConstantPointerNull *CPN = |
| 333 | dyn_cast<ConstantPointerNull>(I->getOperand(1))) |
| 334 | if (CPN->getType()->getAddressSpace() == 0) |
| 335 | if (isNoAliasCall(V->stripPointerCasts())) |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 336 | break; |
Anna Thomas | 43d7e1c | 2016-05-03 14:58:21 +0000 | [diff] [blame] | 337 | // Comparison against value stored in global variable. Given the pointer |
| 338 | // does not escape, its value cannot be guessed and stored separately in a |
| 339 | // global variable. |
| 340 | unsigned OtherIndex = (I->getOperand(0) == V) ? 1 : 0; |
| 341 | auto *LI = dyn_cast<LoadInst>(I->getOperand(OtherIndex)); |
| 342 | if (LI && isa<GlobalVariable>(LI->getPointerOperand())) |
| 343 | break; |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 344 | // Otherwise, be conservative. There are crazy ways to capture pointers |
| 345 | // using comparisons. |
Nick Lewycky | 4c378a4 | 2011-12-28 23:24:21 +0000 | [diff] [blame] | 346 | if (Tracker->captured(U)) |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 347 | return; |
| 348 | break; |
Anna Thomas | 43d7e1c | 2016-05-03 14:58:21 +0000 | [diff] [blame] | 349 | } |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 350 | default: |
| 351 | // Something else - be conservative and say it is captured. |
Nick Lewycky | 4c378a4 | 2011-12-28 23:24:21 +0000 | [diff] [blame] | 352 | if (Tracker->captured(U)) |
Nick Lewycky | 6ae03c3 | 2011-11-20 19:37:06 +0000 | [diff] [blame] | 353 | return; |
| 354 | break; |
| 355 | } |
| 356 | } |
| 357 | |
| 358 | // All uses examined. |
| 359 | } |