LLVM  9.0.0svn
CaptureTracking.cpp
Go to the documentation of this file.
1 //===--- CaptureTracking.cpp - Determine whether a pointer is captured ----===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file contains routines that help determine which pointers are captured.
10 // A pointer value is captured if the function makes a copy of any part of the
11 // pointer that outlives the call. Not being captured means, more or less, that
12 // the pointer is only dereferenced and not stored in a global. Returning part
13 // of the pointer as the function return value may or may not count as capturing
14 // the pointer, depending on the context.
15 //
16 //===----------------------------------------------------------------------===//
17 
19 #include "llvm/ADT/SmallSet.h"
20 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/Analysis/CFG.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/Dominators.h"
27 #include "llvm/IR/Instructions.h"
28 #include "llvm/IR/IntrinsicInst.h"
29 
30 using namespace llvm;
31 
33 
34 bool CaptureTracker::shouldExplore(const Use *U) { return true; }
35 
36 namespace {
37  struct SimpleCaptureTracker : public CaptureTracker {
38  explicit SimpleCaptureTracker(bool ReturnCaptures)
39  : ReturnCaptures(ReturnCaptures), Captured(false) {}
40 
41  void tooManyUses() override { Captured = true; }
42 
43  bool captured(const Use *U) override {
44  if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
45  return false;
46 
47  Captured = true;
48  return true;
49  }
50 
51  bool ReturnCaptures;
52 
53  bool Captured;
54  };
55 
56  /// Only find pointer captures which happen before the given instruction. Uses
57  /// the dominator tree to determine whether one instruction is before another.
58  /// Only support the case where the Value is defined in the same basic block
59  /// as the given instruction and the use.
60  struct CapturesBefore : public CaptureTracker {
61 
62  CapturesBefore(bool ReturnCaptures, const Instruction *I, const DominatorTree *DT,
63  bool IncludeI, OrderedBasicBlock *IC)
64  : OrderedBB(IC), BeforeHere(I), DT(DT),
65  ReturnCaptures(ReturnCaptures), IncludeI(IncludeI), Captured(false) {}
66 
67  void tooManyUses() override { Captured = true; }
68 
69  bool isSafeToPrune(Instruction *I) {
70  BasicBlock *BB = I->getParent();
71  // We explore this usage only if the usage can reach "BeforeHere".
72  // If use is not reachable from entry, there is no need to explore.
73  if (BeforeHere != I && !DT->isReachableFromEntry(BB))
74  return true;
75 
76  // Compute the case where both instructions are inside the same basic
77  // block. Since instructions in the same BB as BeforeHere are numbered in
78  // 'OrderedBB', avoid using 'dominates' and 'isPotentiallyReachable'
79  // which are very expensive for large basic blocks.
80  if (BB == BeforeHere->getParent()) {
81  // 'I' dominates 'BeforeHere' => not safe to prune.
82  //
83  // The value defined by an invoke dominates an instruction only
84  // if it dominates every instruction in UseBB. A PHI is dominated only
85  // if the instruction dominates every possible use in the UseBB. Since
86  // UseBB == BB, avoid pruning.
87  if (isa<InvokeInst>(BeforeHere) || isa<PHINode>(I) || I == BeforeHere)
88  return false;
89  if (!OrderedBB->dominates(BeforeHere, I))
90  return false;
91 
92  // 'BeforeHere' comes before 'I', it's safe to prune if we also
93  // guarantee that 'I' never reaches 'BeforeHere' through a back-edge or
94  // by its successors, i.e, prune if:
95  //
96  // (1) BB is an entry block or have no successors.
97  // (2) There's no path coming back through BB successors.
98  if (BB == &BB->getParent()->getEntryBlock() ||
100  return true;
101 
103  Worklist.append(succ_begin(BB), succ_end(BB));
104  return !isPotentiallyReachableFromMany(Worklist, BB, nullptr, DT);
105  }
106 
107  // If the value is defined in the same basic block as use and BeforeHere,
108  // there is no need to explore the use if BeforeHere dominates use.
109  // Check whether there is a path from I to BeforeHere.
110  if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
111  !isPotentiallyReachable(I, BeforeHere, nullptr, DT))
112  return true;
113 
114  return false;
115  }
116 
117  bool shouldExplore(const Use *U) override {
118  Instruction *I = cast<Instruction>(U->getUser());
119 
120  if (BeforeHere == I && !IncludeI)
121  return false;
122 
123  if (isSafeToPrune(I))
124  return false;
125 
126  return true;
127  }
128 
129  bool captured(const Use *U) override {
130  if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
131  return false;
132 
133  if (!shouldExplore(U))
134  return false;
135 
136  Captured = true;
137  return true;
138  }
139 
140  OrderedBasicBlock *OrderedBB;
141  const Instruction *BeforeHere;
142  const DominatorTree *DT;
143 
144  bool ReturnCaptures;
145  bool IncludeI;
146 
147  bool Captured;
148  };
149 }
150 
151 /// PointerMayBeCaptured - Return true if this pointer value may be captured
152 /// by the enclosing function (which is required to exist). This routine can
153 /// be expensive, so consider caching the results. The boolean ReturnCaptures
154 /// specifies whether returning the value (or part of it) from the function
155 /// counts as capturing it or not. The boolean StoreCaptures specified whether
156 /// storing the value (or part of it) into memory anywhere automatically
157 /// counts as capturing it or not.
159  bool ReturnCaptures, bool StoreCaptures,
160  unsigned MaxUsesToExplore) {
161  assert(!isa<GlobalValue>(V) &&
162  "It doesn't make sense to ask whether a global is captured.");
163 
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;
169 
170  SimpleCaptureTracker SCT(ReturnCaptures);
171  PointerMayBeCaptured(V, &SCT, MaxUsesToExplore);
172  return SCT.Captured;
173 }
174 
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
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.
185 bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures,
186  bool StoreCaptures, const Instruction *I,
187  const DominatorTree *DT, bool IncludeI,
188  OrderedBasicBlock *OBB,
189  unsigned MaxUsesToExplore) {
190  assert(!isa<GlobalValue>(V) &&
191  "It doesn't make sense to ask whether a global is captured.");
192  bool UseNewOBB = OBB == nullptr;
193 
194  if (!DT)
195  return PointerMayBeCaptured(V, ReturnCaptures, StoreCaptures,
196  MaxUsesToExplore);
197  if (UseNewOBB)
198  OBB = new OrderedBasicBlock(I->getParent());
199 
200  // TODO: See comment in PointerMayBeCaptured regarding what could be done
201  // with StoreCaptures.
202 
203  CapturesBefore CB(ReturnCaptures, I, DT, IncludeI, OBB);
204  PointerMayBeCaptured(V, &CB, MaxUsesToExplore);
205 
206  if (UseNewOBB)
207  delete OBB;
208  return CB.Captured;
209 }
210 
212  unsigned MaxUsesToExplore) {
213  assert(V->getType()->isPointerTy() && "Capture is for pointers only!");
216 
217  auto AddUses = [&](const Value *V) {
218  unsigned Count = 0;
219  for (const Use &U : V->uses()) {
220  // If there are lots of uses, conservatively say that the value
221  // is captured to avoid taking too much compile time.
222  if (Count++ >= MaxUsesToExplore)
223  return Tracker->tooManyUses();
224  if (!Visited.insert(&U).second)
225  continue;
226  if (!Tracker->shouldExplore(&U))
227  continue;
228  Worklist.push_back(&U);
229  }
230  };
231  AddUses(V);
232 
233  while (!Worklist.empty()) {
234  const Use *U = Worklist.pop_back_val();
235  Instruction *I = cast<Instruction>(U->getUser());
236  V = U->get();
237 
238  switch (I->getOpcode()) {
239  case Instruction::Call:
240  case Instruction::Invoke: {
241  auto *Call = cast<CallBase>(I);
242  // Not captured if the callee is readonly, doesn't return a copy through
243  // its return value and doesn't unwind (a readonly function can leak bits
244  // by throwing an exception or not depending on the input value).
245  if (Call->onlyReadsMemory() && Call->doesNotThrow() &&
246  Call->getType()->isVoidTy())
247  break;
248 
249  // The pointer is not captured if returned pointer is not captured.
250  // NOTE: CaptureTracking users should not assume that only functions
251  // marked with nocapture do not capture. This means that places like
252  // GetUnderlyingObject in ValueTracking or DecomposeGEPExpression
253  // in BasicAA also need to know about this property.
255  AddUses(Call);
256  break;
257  }
258 
259  // Volatile operations effectively capture the memory location that they
260  // load and store to.
261  if (auto *MI = dyn_cast<MemIntrinsic>(Call))
262  if (MI->isVolatile())
263  if (Tracker->captured(U))
264  return;
265 
266  // Not captured if only passed via 'nocapture' arguments. Note that
267  // calling a function pointer does not in itself cause the pointer to
268  // be captured. This is a subtle point considering that (for example)
269  // the callee might return its own address. It is analogous to saying
270  // that loading a value from a pointer does not cause the pointer to be
271  // captured, even though the loaded value might be the pointer itself
272  // (think of self-referential objects).
273  for (auto IdxOpPair : enumerate(Call->data_ops())) {
274  int Idx = IdxOpPair.index();
275  Value *A = IdxOpPair.value();
276  if (A == V && !Call->doesNotCapture(Idx))
277  // The parameter is not marked 'nocapture' - captured.
278  if (Tracker->captured(U))
279  return;
280  }
281  break;
282  }
283  case Instruction::Load:
284  // Volatile loads make the address observable.
285  if (cast<LoadInst>(I)->isVolatile())
286  if (Tracker->captured(U))
287  return;
288  break;
289  case Instruction::VAArg:
290  // "va-arg" from a pointer does not cause it to be captured.
291  break;
292  case Instruction::Store:
293  // Stored the pointer - conservatively assume it may be captured.
294  // Volatile stores make the address observable.
295  if (V == I->getOperand(0) || cast<StoreInst>(I)->isVolatile())
296  if (Tracker->captured(U))
297  return;
298  break;
299  case Instruction::AtomicRMW: {
300  // atomicrmw conceptually includes both a load and store from
301  // the same location.
302  // As with a store, the location being accessed is not captured,
303  // but the value being stored is.
304  // Volatile stores make the address observable.
305  auto *ARMWI = cast<AtomicRMWInst>(I);
306  if (ARMWI->getValOperand() == V || ARMWI->isVolatile())
307  if (Tracker->captured(U))
308  return;
309  break;
310  }
311  case Instruction::AtomicCmpXchg: {
312  // cmpxchg conceptually includes both a load and store from
313  // the same location.
314  // As with a store, the location being accessed is not captured,
315  // but the value being stored is.
316  // Volatile stores make the address observable.
317  auto *ACXI = cast<AtomicCmpXchgInst>(I);
318  if (ACXI->getCompareOperand() == V || ACXI->getNewValOperand() == V ||
319  ACXI->isVolatile())
320  if (Tracker->captured(U))
321  return;
322  break;
323  }
324  case Instruction::BitCast:
325  case Instruction::GetElementPtr:
326  case Instruction::PHI:
327  case Instruction::Select:
328  case Instruction::AddrSpaceCast:
329  // The original value is not captured via this if the new value isn't.
330  AddUses(I);
331  break;
332  case Instruction::ICmp: {
333  if (auto *CPN = dyn_cast<ConstantPointerNull>(I->getOperand(1))) {
334  // Don't count comparisons of a no-alias return value against null as
335  // captures. This allows us to ignore comparisons of malloc results
336  // with null, for example.
337  if (CPN->getType()->getAddressSpace() == 0)
338  if (isNoAliasCall(V->stripPointerCasts()))
339  break;
340  if (!I->getFunction()->nullPointerIsDefined()) {
342  // An inbounds GEP can either be a valid pointer (pointing into
343  // or to the end of an allocation), or be null in the default
344  // address space. So for an inbounds GEPs there is no way to let
345  // the pointer escape using clever GEP hacking because doing so
346  // would make the pointer point outside of the allocated object
347  // and thus make the GEP result a poison value.
348  if (auto *GEP = dyn_cast<GetElementPtrInst>(O))
349  if (GEP->isInBounds())
350  break;
351  // Comparing a dereferenceable_or_null argument against null
352  // cannot lead to pointer escapes, because if it is not null it
353  // must be a valid (in-bounds) pointer.
354  bool CanBeNull;
355  if (O->getPointerDereferenceableBytes(I->getModule()->getDataLayout(), CanBeNull))
356  break;
357  }
358  }
359  // Comparison against value stored in global variable. Given the pointer
360  // does not escape, its value cannot be guessed and stored separately in a
361  // global variable.
362  unsigned OtherIndex = (I->getOperand(0) == V) ? 1 : 0;
363  auto *LI = dyn_cast<LoadInst>(I->getOperand(OtherIndex));
364  if (LI && isa<GlobalVariable>(LI->getPointerOperand()))
365  break;
366  // Otherwise, be conservative. There are crazy ways to capture pointers
367  // using comparisons.
368  if (Tracker->captured(U))
369  return;
370  break;
371  }
372  default:
373  // Something else - be conservative and say it is captured.
374  if (Tracker->captured(U))
375  return;
376  break;
377  }
378  }
379 
380  // All uses examined.
381 }
iterator_range< use_iterator > uses()
Definition: Value.h:354
virtual void tooManyUses()=0
tooManyUses - The depth of traversal has breached a limit.
This callback is used in conjunction with PointerMayBeCaptured.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock *> *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction &#39;To&#39; is reachable from &#39;From&#39;, without passing through any blocks in Ex...
Definition: CFG.cpp:211
bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(const CallBase *Call)
virtual bool shouldExplore(const Use *U)
shouldExplore - This is the use of a value derived from the pointer.
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
An instruction for reading from memory.
Definition: Instructions.h:167
Hexagon Common GEP
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:299
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
virtual bool captured(const Use *U)=0
captured - Information about the pointer was captured by the user of use U.
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:102
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, const DominatorTree *DT, bool IncludeI=false, OrderedBasicBlock *OBB=nullptr, unsigned MaxUsesToExplore=DefaultMaxUsesToExplore)
PointerMayBeCapturedBefore - Return true if this pointer value may be captured by the enclosing funct...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Value * getOperand(unsigned i) const
Definition: User.h:169
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:105
const BasicBlock & getEntryBlock() const
Definition: Function.h:656
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:223
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:180
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:59
const Value * stripPointerCastsSameRepresentation() const
Strip off pointer casts, all-zero GEPs, address space casts, and aliases but ensures the representati...
Definition: Value.cpp:539
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:248
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:55
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:387
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:72
IRTranslator LLVM IR MI
static bool isVolatile(Instruction *Inst)
bool nullPointerIsDefined() const
Check if null pointer dereferencing is considered undefined behavior for the function.
Definition: Function.cpp:1518
bool isPotentiallyReachableFromMany(SmallVectorImpl< BasicBlock *> &Worklist, BasicBlock *StopBB, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether there is at least one path from a block in &#39;Worklist&#39; to &#39;StopBB&#39;, returning true if uncertain.
detail::enumerator< R > enumerate(R &&TheRange)
Given an input range, returns a new range whose values are are pair (A,B) such that A is the 0-based ...
Definition: STLExtras.h:1578
const BasicBlock * getParent() const
Definition: Instruction.h:66
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=DefaultMaxUsesToExplore)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...