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/CallSite.h"
24#include "llvm/IR/Constants.h"
25#include "llvm/IR/Instructions.h"
26
27using namespace llvm;
28
29CaptureTracker::~CaptureTracker() {}
30
31bool CaptureTracker::shouldExplore(const 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() override { Captured = true; }
39
40    bool captured(const Use *U) override {
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<const Use *, Threshold> Worklist;
85  SmallSet<const Use *, Threshold> Visited;
86  int Count = 0;
87
88  for (const Use &U : V->uses()) {
89    // If there are lots of uses, conservatively say that the value
90    // is captured to avoid taking too much compile time.
91    if (Count++ >= Threshold)
92      return Tracker->tooManyUses();
93
94    if (!Tracker->shouldExplore(&U)) continue;
95    Visited.insert(&U);
96    Worklist.push_back(&U);
97  }
98
99  while (!Worklist.empty()) {
100    const Use *U = Worklist.pop_back_val();
101    Instruction *I = cast<Instruction>(U->getUser());
102    V = U->get();
103
104    switch (I->getOpcode()) {
105    case Instruction::Call:
106    case Instruction::Invoke: {
107      CallSite CS(I);
108      // Not captured if the callee is readonly, doesn't return a copy through
109      // its return value and doesn't unwind (a readonly function can leak bits
110      // by throwing an exception or not depending on the input value).
111      if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy())
112        break;
113
114      // Not captured if only passed via 'nocapture' arguments.  Note that
115      // calling a function pointer does not in itself cause the pointer to
116      // be captured.  This is a subtle point considering that (for example)
117      // the callee might return its own address.  It is analogous to saying
118      // that loading a value from a pointer does not cause the pointer to be
119      // captured, even though the loaded value might be the pointer itself
120      // (think of self-referential objects).
121      CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end();
122      for (CallSite::arg_iterator A = B; A != E; ++A)
123        if (A->get() == V && !CS.doesNotCapture(A - B))
124          // The parameter is not marked 'nocapture' - captured.
125          if (Tracker->captured(U))
126            return;
127      break;
128    }
129    case Instruction::Load:
130      // Loading from a pointer does not cause it to be captured.
131      break;
132    case Instruction::VAArg:
133      // "va-arg" from a pointer does not cause it to be captured.
134      break;
135    case Instruction::Store:
136      if (V == I->getOperand(0))
137        // Stored the pointer - conservatively assume it may be captured.
138        if (Tracker->captured(U))
139          return;
140      // Storing to the pointee does not cause the pointer to be captured.
141      break;
142    case Instruction::BitCast:
143    case Instruction::GetElementPtr:
144    case Instruction::PHI:
145    case Instruction::Select:
146    case Instruction::AddrSpaceCast:
147      // The original value is not captured via this if the new value isn't.
148      Count = 0;
149      for (Use &UU : I->uses()) {
150        // If there are lots of uses, conservatively say that the value
151        // is captured to avoid taking too much compile time.
152        if (Count++ >= Threshold)
153          return Tracker->tooManyUses();
154
155        if (Visited.insert(&UU))
156          if (Tracker->shouldExplore(&UU))
157            Worklist.push_back(&UU);
158      }
159      break;
160    case Instruction::ICmp:
161      // Don't count comparisons of a no-alias return value against null as
162      // captures. This allows us to ignore comparisons of malloc results
163      // with null, for example.
164      if (ConstantPointerNull *CPN =
165          dyn_cast<ConstantPointerNull>(I->getOperand(1)))
166        if (CPN->getType()->getAddressSpace() == 0)
167          if (isNoAliasCall(V->stripPointerCasts()))
168            break;
169      // Otherwise, be conservative. There are crazy ways to capture pointers
170      // using comparisons.
171      if (Tracker->captured(U))
172        return;
173      break;
174    default:
175      // Something else - be conservative and say it is captured.
176      if (Tracker->captured(U))
177        return;
178      break;
179    }
180  }
181
182  // All uses examined.
183}
184