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/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"
26
27using namespace llvm;
28
29CaptureTracker::~CaptureTracker() {}
30
31bool CaptureTracker::shouldExplore(Use *U) { return true; }
32
33namespace {
34  struct SimpleCaptureTracker : public CaptureTracker {
35    explicit SimpleCaptureTracker(bool ReturnCaptures)
36      : ReturnCaptures(ReturnCaptures), Captured(false) {}
37
38    void tooManyUses() { Captured = true; }
39
40    bool captured(Use *U) {
41      if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
42        return false;
43
44      Captured = true;
45      return true;
46    }
47
48    bool ReturnCaptures;
49
50    bool Captured;
51  };
52}
53
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.
61bool 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.");
65
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.
70  (void)StoreCaptures;
71
72  SimpleCaptureTracker SCT(ReturnCaptures);
73  PointerMayBeCaptured(V, &SCT);
74  return SCT.Captured;
75}
76
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.
80static int const Threshold = 20;
81
82void 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;
86  int Count = 0;
87
88  for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end();
89       UI != UE; ++UI) {
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();
94
95    Use *U = &UI.getUse();
96    if (!Tracker->shouldExplore(U)) continue;
97    Visited.insert(U);
98    Worklist.push_back(U);
99  }
100
101  while (!Worklist.empty()) {
102    Use *U = Worklist.pop_back_val();
103    Instruction *I = cast<Instruction>(U->getUser());
104    V = U->get();
105
106    switch (I->getOpcode()) {
107    case Instruction::Call:
108    case Instruction::Invoke: {
109      CallSite CS(I);
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())
114        break;
115
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))
128            return;
129      break;
130    }
131    case Instruction::Load:
132      // Loading from a pointer does not cause it to be captured.
133      break;
134    case Instruction::VAArg:
135      // "va-arg" from a pointer does not cause it to be captured.
136      break;
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))
141          return;
142      // Storing to the pointee does not cause the pointer to be captured.
143      break;
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      Count = 0;
150      for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end();
151           UI != UE; ++UI) {
152        // If there are lots of uses, conservatively say that the value
153        // is captured to avoid taking too much compile time.
154        if (Count++ >= Threshold)
155          return Tracker->tooManyUses();
156
157        Use *U = &UI.getUse();
158        if (Visited.insert(U))
159          if (Tracker->shouldExplore(U))
160            Worklist.push_back(U);
161      }
162      break;
163    case Instruction::ICmp:
164      // Don't count comparisons of a no-alias return value against null as
165      // captures. This allows us to ignore comparisons of malloc results
166      // with null, for example.
167      if (ConstantPointerNull *CPN =
168          dyn_cast<ConstantPointerNull>(I->getOperand(1)))
169        if (CPN->getType()->getAddressSpace() == 0)
170          if (isNoAliasCall(V->stripPointerCasts()))
171            break;
172      // Otherwise, be conservative. There are crazy ways to capture pointers
173      // using comparisons.
174      if (Tracker->captured(U))
175        return;
176      break;
177    default:
178      // Something else - be conservative and say it is captured.
179      if (Tracker->captured(U))
180        return;
181      break;
182    }
183  }
184
185  // All uses examined.
186}
187