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
19 #include "llvm/Analysis/CaptureTracking.h"
20 #include "llvm/Constants.h"
21 #include "llvm/Instructions.h"
22 #include "llvm/Value.h"
23 #include "llvm/Analysis/AliasAnalysis.h"
24 #include "llvm/ADT/SmallSet.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/Support/CallSite.h"
27 using namespace llvm;
28
29 /// As its comment mentions, PointerMayBeCaptured can be expensive.
30 /// However, it's not easy for BasicAA to cache the result, because
31 /// it's an ImmutablePass. To work around this, bound queries at a
32 /// fixed number of uses.
33 ///
34 /// TODO: Write a new FunctionPass AliasAnalysis so that it can keep
35 /// a cache. Then we can move the code from BasicAliasAnalysis into
36 /// that path, and remove this threshold.
37 static int const Threshold = 20;
38
39 /// PointerMayBeCaptured - Return true if this pointer value may be captured
40 /// by the enclosing function (which is required to exist). This routine can
41 /// be expensive, so consider caching the results. The boolean ReturnCaptures
42 /// specifies whether returning the value (or part of it) from the function
43 /// counts as capturing it or not. The boolean StoreCaptures specified whether
44 /// storing the value (or part of it) into memory anywhere automatically
45 /// counts as capturing it or not.
PointerMayBeCaptured(const Value * V,bool ReturnCaptures,bool StoreCaptures)46 bool llvm::PointerMayBeCaptured(const Value *V,
47 bool ReturnCaptures, bool StoreCaptures) {
48 assert(V->getType()->isPointerTy() && "Capture is for pointers only!");
49 SmallVector<Use*, Threshold> Worklist;
50 SmallSet<Use*, Threshold> Visited;
51 int Count = 0;
52
53 for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end();
54 UI != UE; ++UI) {
55 // If there are lots of uses, conservatively say that the value
56 // is captured to avoid taking too much compile time.
57 if (Count++ >= Threshold)
58 return true;
59
60 Use *U = &UI.getUse();
61 Visited.insert(U);
62 Worklist.push_back(U);
63 }
64
65 while (!Worklist.empty()) {
66 Use *U = Worklist.pop_back_val();
67 Instruction *I = cast<Instruction>(U->getUser());
68 V = U->get();
69
70 switch (I->getOpcode()) {
71 case Instruction::Call:
72 case Instruction::Invoke: {
73 CallSite CS(I);
74 // Not captured if the callee is readonly, doesn't return a copy through
75 // its return value and doesn't unwind (a readonly function can leak bits
76 // by throwing an exception or not depending on the input value).
77 if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy())
78 break;
79
80 // Not captured if only passed via 'nocapture' arguments. Note that
81 // calling a function pointer does not in itself cause the pointer to
82 // be captured. This is a subtle point considering that (for example)
83 // the callee might return its own address. It is analogous to saying
84 // that loading a value from a pointer does not cause the pointer to be
85 // captured, even though the loaded value might be the pointer itself
86 // (think of self-referential objects).
87 CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end();
88 for (CallSite::arg_iterator A = B; A != E; ++A)
89 if (A->get() == V && !CS.paramHasAttr(A - B + 1, Attribute::NoCapture))
90 // The parameter is not marked 'nocapture' - captured.
91 return true;
92 // Only passed via 'nocapture' arguments, or is the called function - not
93 // captured.
94 break;
95 }
96 case Instruction::Load:
97 // Loading from a pointer does not cause it to be captured.
98 break;
99 case Instruction::VAArg:
100 // "va-arg" from a pointer does not cause it to be captured.
101 break;
102 case Instruction::Ret:
103 if (ReturnCaptures)
104 return true;
105 break;
106 case Instruction::Store:
107 if (V == I->getOperand(0))
108 // Stored the pointer - conservatively assume it may be captured.
109 // TODO: If StoreCaptures is not true, we could do Fancy analysis
110 // to determine whether this store is not actually an escape point.
111 // In that case, BasicAliasAnalysis should be updated as well to
112 // take advantage of this.
113 return true;
114 // Storing to the pointee does not cause the pointer to be captured.
115 break;
116 case Instruction::BitCast:
117 case Instruction::GetElementPtr:
118 case Instruction::PHI:
119 case Instruction::Select:
120 // The original value is not captured via this if the new value isn't.
121 for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end();
122 UI != UE; ++UI) {
123 Use *U = &UI.getUse();
124 if (Visited.insert(U))
125 Worklist.push_back(U);
126 }
127 break;
128 case Instruction::ICmp:
129 // Don't count comparisons of a no-alias return value against null as
130 // captures. This allows us to ignore comparisons of malloc results
131 // with null, for example.
132 if (isNoAliasCall(V->stripPointerCasts()))
133 if (ConstantPointerNull *CPN =
134 dyn_cast<ConstantPointerNull>(I->getOperand(1)))
135 if (CPN->getType()->getAddressSpace() == 0)
136 break;
137 // Otherwise, be conservative. There are crazy ways to capture pointers
138 // using comparisons.
139 return true;
140 default:
141 // Something else - be conservative and say it is captured.
142 return true;
143 }
144 }
145
146 // All uses examined - not captured.
147 return false;
148 }
149