1 //===--- CaptureTracking.cpp - Determine whether a pointer is captured ----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
17 //===----------------------------------------------------------------------===//
19 #include "llvm/ADT/SmallSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/Analysis/AliasAnalysis.h"
22 #include "llvm/Analysis/CaptureTracking.h"
23 #include "llvm/IR/Constants.h"
24 #include "llvm/IR/Instructions.h"
25 #include "llvm/Support/CallSite.h"
29 CaptureTracker::~CaptureTracker() {}
31 bool CaptureTracker::shouldExplore(Use *U) { return true; }
34 struct SimpleCaptureTracker : public CaptureTracker {
35 explicit SimpleCaptureTracker(bool ReturnCaptures)
36 : ReturnCaptures(ReturnCaptures), Captured(false) {}
38 void tooManyUses() { Captured = true; }
40 bool captured(Use *U) {
41 if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
54 /// PointerMayBeCaptured - Return true if this pointer value may be captured
55 /// by the enclosing function (which is required to exist). This routine can
56 /// be expensive, so consider caching the results. The boolean ReturnCaptures
57 /// specifies whether returning the value (or part of it) from the function
58 /// counts as capturing it or not. The boolean StoreCaptures specified whether
59 /// storing the value (or part of it) into memory anywhere automatically
60 /// counts as capturing it or not.
61 bool llvm::PointerMayBeCaptured(const Value *V,
62 bool ReturnCaptures, bool StoreCaptures) {
63 assert(!isa<GlobalValue>(V) &&
64 "It doesn't make sense to ask whether a global is captured.");
66 // TODO: If StoreCaptures is not true, we could do Fancy analysis
67 // to determine whether this store is not actually an escape point.
68 // In that case, BasicAliasAnalysis should be updated as well to
69 // take advantage of this.
72 SimpleCaptureTracker SCT(ReturnCaptures);
73 PointerMayBeCaptured(V, &SCT);
77 /// TODO: Write a new FunctionPass AliasAnalysis so that it can keep
78 /// a cache. Then we can move the code from BasicAliasAnalysis into
79 /// that path, and remove this threshold.
80 static int const Threshold = 20;
82 void llvm::PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker) {
83 assert(V->getType()->isPointerTy() && "Capture is for pointers only!");
84 SmallVector<Use*, Threshold> Worklist;
85 SmallSet<Use*, Threshold> Visited;
88 for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end();
90 // If there are lots of uses, conservatively say that the value
91 // is captured to avoid taking too much compile time.
92 if (Count++ >= Threshold)
93 return Tracker->tooManyUses();
95 Use *U = &UI.getUse();
96 if (!Tracker->shouldExplore(U)) continue;
98 Worklist.push_back(U);
101 while (!Worklist.empty()) {
102 Use *U = Worklist.pop_back_val();
103 Instruction *I = cast<Instruction>(U->getUser());
106 switch (I->getOpcode()) {
107 case Instruction::Call:
108 case Instruction::Invoke: {
110 // Not captured if the callee is readonly, doesn't return a copy through
111 // its return value and doesn't unwind (a readonly function can leak bits
112 // by throwing an exception or not depending on the input value).
113 if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy())
116 // Not captured if only passed via 'nocapture' arguments. Note that
117 // calling a function pointer does not in itself cause the pointer to
118 // be captured. This is a subtle point considering that (for example)
119 // the callee might return its own address. It is analogous to saying
120 // that loading a value from a pointer does not cause the pointer to be
121 // captured, even though the loaded value might be the pointer itself
122 // (think of self-referential objects).
123 CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end();
124 for (CallSite::arg_iterator A = B; A != E; ++A)
125 if (A->get() == V && !CS.doesNotCapture(A - B))
126 // The parameter is not marked 'nocapture' - captured.
127 if (Tracker->captured(U))
131 case Instruction::Load:
132 // Loading from a pointer does not cause it to be captured.
134 case Instruction::VAArg:
135 // "va-arg" from a pointer does not cause it to be captured.
137 case Instruction::Store:
138 if (V == I->getOperand(0))
139 // Stored the pointer - conservatively assume it may be captured.
140 if (Tracker->captured(U))
142 // Storing to the pointee does not cause the pointer to be captured.
144 case Instruction::BitCast:
145 case Instruction::GetElementPtr:
146 case Instruction::PHI:
147 case Instruction::Select:
148 // The original value is not captured via this if the new value isn't.
149 for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end();
151 Use *U = &UI.getUse();
152 if (Visited.insert(U))
153 if (Tracker->shouldExplore(U))
154 Worklist.push_back(U);
157 case Instruction::ICmp:
158 // Don't count comparisons of a no-alias return value against null as
159 // captures. This allows us to ignore comparisons of malloc results
160 // with null, for example.
161 if (ConstantPointerNull *CPN =
162 dyn_cast<ConstantPointerNull>(I->getOperand(1)))
163 if (CPN->getType()->getAddressSpace() == 0)
164 if (isNoAliasCall(V->stripPointerCasts()))
166 // Otherwise, be conservative. There are crazy ways to capture pointers
167 // using comparisons.
168 if (Tracker->captured(U))
172 // Something else - be conservative and say it is captured.
173 if (Tracker->captured(U))
179 // All uses examined.