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"
27using 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.
37static 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.
46bool 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