LLVM  7.0.0svn
CaptureTracking.cpp
Go to the documentation of this file.
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 
20 #include "llvm/ADT/SmallSet.h"
21 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/Analysis/CFG.h"
26 #include "llvm/IR/CallSite.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/IntrinsicInst.h"
31 
32 using namespace llvm;
33 
35 
36 bool CaptureTracker::shouldExplore(const Use *U) { return true; }
37 
38 namespace {
39  struct SimpleCaptureTracker : public CaptureTracker {
40  explicit SimpleCaptureTracker(bool ReturnCaptures)
41  : ReturnCaptures(ReturnCaptures), Captured(false) {}
42 
43  void tooManyUses() override { Captured = true; }
44 
45  bool captured(const Use *U) override {
46  if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
47  return false;
48 
49  Captured = true;
50  return true;
51  }
52 
53  bool ReturnCaptures;
54 
55  bool Captured;
56  };
57 
58  /// Only find pointer captures which happen before the given instruction. Uses
59  /// the dominator tree to determine whether one instruction is before another.
60  /// Only support the case where the Value is defined in the same basic block
61  /// as the given instruction and the use.
62  struct CapturesBefore : public CaptureTracker {
63 
64  CapturesBefore(bool ReturnCaptures, const Instruction *I, const DominatorTree *DT,
65  bool IncludeI, OrderedBasicBlock *IC)
66  : OrderedBB(IC), BeforeHere(I), DT(DT),
67  ReturnCaptures(ReturnCaptures), IncludeI(IncludeI), Captured(false) {}
68 
69  void tooManyUses() override { Captured = true; }
70 
71  bool isSafeToPrune(Instruction *I) {
72  BasicBlock *BB = I->getParent();
73  // We explore this usage only if the usage can reach "BeforeHere".
74  // If use is not reachable from entry, there is no need to explore.
75  if (BeforeHere != I && !DT->isReachableFromEntry(BB))
76  return true;
77 
78  // Compute the case where both instructions are inside the same basic
79  // block. Since instructions in the same BB as BeforeHere are numbered in
80  // 'OrderedBB', avoid using 'dominates' and 'isPotentiallyReachable'
81  // which are very expensive for large basic blocks.
82  if (BB == BeforeHere->getParent()) {
83  // 'I' dominates 'BeforeHere' => not safe to prune.
84  //
85  // The value defined by an invoke dominates an instruction only
86  // if it dominates every instruction in UseBB. A PHI is dominated only
87  // if the instruction dominates every possible use in the UseBB. Since
88  // UseBB == BB, avoid pruning.
89  if (isa<InvokeInst>(BeforeHere) || isa<PHINode>(I) || I == BeforeHere)
90  return false;
91  if (!OrderedBB->dominates(BeforeHere, I))
92  return false;
93 
94  // 'BeforeHere' comes before 'I', it's safe to prune if we also
95  // guarantee that 'I' never reaches 'BeforeHere' through a back-edge or
96  // by its successors, i.e, prune if:
97  //
98  // (1) BB is an entry block or have no successors.
99  // (2) There's no path coming back through BB successors.
100  if (BB == &BB->getParent()->getEntryBlock() ||
102  return true;
103 
105  Worklist.append(succ_begin(BB), succ_end(BB));
106  return !isPotentiallyReachableFromMany(Worklist, BB, DT);
107  }
108 
109  // If the value is defined in the same basic block as use and BeforeHere,
110  // there is no need to explore the use if BeforeHere dominates use.
111  // Check whether there is a path from I to BeforeHere.
112  if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
113  !isPotentiallyReachable(I, BeforeHere, DT))
114  return true;
115 
116  return false;
117  }
118 
119  bool shouldExplore(const Use *U) override {
120  Instruction *I = cast<Instruction>(U->getUser());
121 
122  if (BeforeHere == I && !IncludeI)
123  return false;
124 
125  if (isSafeToPrune(I))
126  return false;
127 
128  return true;
129  }
130 
131  bool captured(const Use *U) override {
132  if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
133  return false;
134 
135  if (!shouldExplore(U))
136  return false;
137 
138  Captured = true;
139  return true;
140  }
141 
142  OrderedBasicBlock *OrderedBB;
143  const Instruction *BeforeHere;
144  const DominatorTree *DT;
145 
146  bool ReturnCaptures;
147  bool IncludeI;
148 
149  bool Captured;
150  };
151 }
152 
153 /// PointerMayBeCaptured - Return true if this pointer value may be captured
154 /// by the enclosing function (which is required to exist). This routine can
155 /// be expensive, so consider caching the results. The boolean ReturnCaptures
156 /// specifies whether returning the value (or part of it) from the function
157 /// counts as capturing it or not. The boolean StoreCaptures specified whether
158 /// storing the value (or part of it) into memory anywhere automatically
159 /// counts as capturing it or not.
161  bool ReturnCaptures, bool StoreCaptures) {
162  assert(!isa<GlobalValue>(V) &&
163  "It doesn't make sense to ask whether a global is captured.");
164 
165  // TODO: If StoreCaptures is not true, we could do Fancy analysis
166  // to determine whether this store is not actually an escape point.
167  // In that case, BasicAliasAnalysis should be updated as well to
168  // take advantage of this.
169  (void)StoreCaptures;
170 
171  SimpleCaptureTracker SCT(ReturnCaptures);
172  PointerMayBeCaptured(V, &SCT);
173  return SCT.Captured;
174 }
175 
176 /// PointerMayBeCapturedBefore - Return true if this pointer value may be
177 /// captured by the enclosing function (which is required to exist). If a
178 /// DominatorTree is provided, only captures which happen before the given
179 /// instruction are considered. This routine can be expensive, so consider
180 /// caching the results. The boolean ReturnCaptures specifies whether
181 /// returning the value (or part of it) from the function counts as capturing
182 /// it or not. The boolean StoreCaptures specified whether storing the value
183 /// (or part of it) into memory anywhere automatically counts as capturing it
184 /// or not. A ordered basic block \p OBB can be used in order to speed up
185 /// queries about relative order among instructions in the same basic block.
186 bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures,
187  bool StoreCaptures, const Instruction *I,
188  const DominatorTree *DT, bool IncludeI,
189  OrderedBasicBlock *OBB) {
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  if (UseNewOBB)
197  OBB = new OrderedBasicBlock(I->getParent());
198 
199  // TODO: See comment in PointerMayBeCaptured regarding what could be done
200  // with StoreCaptures.
201 
202  CapturesBefore CB(ReturnCaptures, I, DT, IncludeI, OBB);
203  PointerMayBeCaptured(V, &CB);
204 
205  if (UseNewOBB)
206  delete OBB;
207  return CB.Captured;
208 }
209 
210 /// TODO: Write a new FunctionPass AliasAnalysis so that it can keep
211 /// a cache. Then we can move the code from BasicAliasAnalysis into
212 /// that path, and remove this threshold.
213 static int const Threshold = 20;
214 
216  assert(V->getType()->isPointerTy() && "Capture is for pointers only!");
219 
220  auto AddUses = [&](const Value *V) {
221  int Count = 0;
222  for (const Use &U : V->uses()) {
223  // If there are lots of uses, conservatively say that the value
224  // is captured to avoid taking too much compile time.
225  if (Count++ >= Threshold)
226  return Tracker->tooManyUses();
227  if (!Visited.insert(&U).second)
228  continue;
229  if (!Tracker->shouldExplore(&U))
230  continue;
231  Worklist.push_back(&U);
232  }
233  };
234  AddUses(V);
235 
236  while (!Worklist.empty()) {
237  const Use *U = Worklist.pop_back_val();
238  Instruction *I = cast<Instruction>(U->getUser());
239  V = U->get();
240 
241  switch (I->getOpcode()) {
242  case Instruction::Call:
243  case Instruction::Invoke: {
244  CallSite CS(I);
245  // Not captured if the callee is readonly, doesn't return a copy through
246  // its return value and doesn't unwind (a readonly function can leak bits
247  // by throwing an exception or not depending on the input value).
248  if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy())
249  break;
250 
251  // The pointer is not captured if returned pointer is not captured.
252  // NOTE: CaptureTracking users should not assume that only functions
253  // marked with nocapture do not capture. This means that places like
254  // GetUnderlyingObject in ValueTracking or DecomposeGEPExpression
255  // in BasicAA also need to know about this property.
257  AddUses(I);
258  break;
259  }
260 
261  // Volatile operations effectively capture the memory location that they
262  // load and store to.
263  if (auto *MI = dyn_cast<MemIntrinsic>(I))
264  if (MI->isVolatile())
265  if (Tracker->captured(U))
266  return;
267 
268  // Not captured if only passed via 'nocapture' arguments. Note that
269  // calling a function pointer does not in itself cause the pointer to
270  // be captured. This is a subtle point considering that (for example)
271  // the callee might return its own address. It is analogous to saying
272  // that loading a value from a pointer does not cause the pointer to be
273  // captured, even though the loaded value might be the pointer itself
274  // (think of self-referential objects).
277  for (CallSite::data_operand_iterator A = B; A != E; ++A)
278  if (A->get() == V && !CS.doesNotCapture(A - B))
279  // The parameter is not marked 'nocapture' - captured.
280  if (Tracker->captured(U))
281  return;
282  break;
283  }
284  case Instruction::Load:
285  // Volatile loads make the address observable.
286  if (cast<LoadInst>(I)->isVolatile())
287  if (Tracker->captured(U))
288  return;
289  break;
290  case Instruction::VAArg:
291  // "va-arg" from a pointer does not cause it to be captured.
292  break;
293  case Instruction::Store:
294  // Stored the pointer - conservatively assume it may be captured.
295  // Volatile stores make the address observable.
296  if (V == I->getOperand(0) || cast<StoreInst>(I)->isVolatile())
297  if (Tracker->captured(U))
298  return;
299  break;
300  case Instruction::AtomicRMW: {
301  // atomicrmw conceptually includes both a load and store from
302  // the same location.
303  // As with a store, the location being accessed is not captured,
304  // but the value being stored is.
305  // Volatile stores make the address observable.
306  auto *ARMWI = cast<AtomicRMWInst>(I);
307  if (ARMWI->getValOperand() == V || ARMWI->isVolatile())
308  if (Tracker->captured(U))
309  return;
310  break;
311  }
312  case Instruction::AtomicCmpXchg: {
313  // cmpxchg conceptually includes both a load and store from
314  // the same location.
315  // As with a store, the location being accessed is not captured,
316  // but the value being stored is.
317  // Volatile stores make the address observable.
318  auto *ACXI = cast<AtomicCmpXchgInst>(I);
319  if (ACXI->getCompareOperand() == V || ACXI->getNewValOperand() == V ||
320  ACXI->isVolatile())
321  if (Tracker->captured(U))
322  return;
323  break;
324  }
325  case Instruction::BitCast:
326  case Instruction::GetElementPtr:
327  case Instruction::PHI:
328  case Instruction::Select:
329  case Instruction::AddrSpaceCast:
330  // The original value is not captured via this if the new value isn't.
331  AddUses(I);
332  break;
333  case Instruction::ICmp: {
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 (ConstantPointerNull *CPN =
338  dyn_cast<ConstantPointerNull>(I->getOperand(1)))
339  if (CPN->getType()->getAddressSpace() == 0)
340  if (isNoAliasCall(V->stripPointerCasts()))
341  break;
342  // Comparison against value stored in global variable. Given the pointer
343  // does not escape, its value cannot be guessed and stored separately in a
344  // global variable.
345  unsigned OtherIndex = (I->getOperand(0) == V) ? 1 : 0;
346  auto *LI = dyn_cast<LoadInst>(I->getOperand(OtherIndex));
347  if (LI && isa<GlobalVariable>(LI->getPointerOperand()))
348  break;
349  // Otherwise, be conservative. There are crazy ways to capture pointers
350  // using comparisons.
351  if (Tracker->captured(U))
352  return;
353  break;
354  }
355  default:
356  // Something else - be conservative and say it is captured.
357  if (Tracker->captured(U))
358  return;
359  break;
360  }
361  }
362 
363  // All uses examined.
364 }
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.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
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:168
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:295
bool onlyReadsMemory() const
Determine if the call does not access or only reads memory.
Definition: CallSite.h:454
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
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:103
IterTy data_operands_end() const
Definition: CallSite.h:249
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:126
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
Value * getOperand(unsigned i) const
Definition: User.h:170
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:141
const BasicBlock & getEntryBlock() const
Definition: Function.h:626
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:36
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:224
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction &#39;To&#39; is reachable from &#39;From&#39;, returning true if uncertain.
Definition: CFG.cpp:186
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:81
bool doesNotCapture(unsigned OpNo) const
Determine whether this data operand is not captured.
Definition: CallSite.h:593
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:861
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:244
A constant pointer value that points to null.
Definition: Constants.h:535
IterTy data_operands_begin() const
data_operands_begin/data_operands_end - Return iterators iterating over the call / invoke argument li...
Definition: CallSite.h:245
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:395
bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(ImmutableCallSite CS)
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#define I(x, y, z)
Definition: MD5.cpp:58
bool doesNotThrow() const
Determine if the call cannot unwind.
Definition: CallSite.h:505
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:323
bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, const DominatorTree *DT, bool IncludeI=false, OrderedBasicBlock *OBB=nullptr)
PointerMayBeCapturedBefore - Return true if this pointer value may be captured by the enclosing funct...
static int const Threshold
TODO: Write a new FunctionPass AliasAnalysis so that it can keep a cache.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getNumSuccessors() const
Return the number of successors that this terminator has.
LLVM Value Representation.
Definition: Value.h:73
IRTranslator LLVM IR MI
static bool isVolatile(Instruction *Inst)
const TerminatorInst * 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:138
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.
Definition: CFG.cpp:130
const BasicBlock * getParent() const
Definition: Instruction.h:67