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