lib/Analysis/CaptureTracking.cpp

   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/Analysis/CFG.h"
  24 #include "llvm/IR/CallSite.h"
  25 #include "llvm/IR/Constants.h"
  26 #include "llvm/IR/Dominators.h"
  27 #include "llvm/IR/Instructions.h"
  28
  29 using namespace llvm;
  30
  31 CaptureTracker::~CaptureTracker() {}
  32
  33 bool CaptureTracker::shouldExplore(const Use *U) { return true; }
  34
  35 namespace {
  36   struct SimpleCaptureTracker : public CaptureTracker {
  37     explicit SimpleCaptureTracker(bool ReturnCaptures)
  38       : ReturnCaptures(ReturnCaptures), Captured(false) {}
  39
  40     void tooManyUses() override { Captured = true; }
  41
  42     bool captured(const Use *U) override {
  43       if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
  44         return false;
  45
  46       Captured = true;
  47       return true;
  48     }
  49
  50     bool ReturnCaptures;
  51
  52     bool Captured;
  53   };
  54
  55   /// Only find pointer captures which happen before the given instruction. Uses
  56   /// the dominator tree to determine whether one instruction is before another.
  57   /// Only support the case where the Value is defined in the same basic block
  58   /// as the given instruction and the use.
  59   struct CapturesBefore : public CaptureTracker {
  60     CapturesBefore(bool ReturnCaptures, const Instruction *I, DominatorTree *DT)
  61       : BeforeHere(I), DT(DT), ReturnCaptures(ReturnCaptures),
  62         Captured(false) {}
  63
  64     void tooManyUses() override { Captured = true; }
  65
  66     bool shouldExplore(const Use *U) override {
  67       Instruction *I = cast<Instruction>(U->getUser());
  68       BasicBlock *BB = I->getParent();
  69       // We explore this usage only if the usage can reach "BeforeHere".
  70       // If use is not reachable from entry, there is no need to explore.
  71       if (BeforeHere != I && !DT->isReachableFromEntry(BB))
  72         return false;
  73       // If the value is defined in the same basic block as use and BeforeHere,
  74       // there is no need to explore the use if BeforeHere dominates use.
  75       // Check whether there is a path from I to BeforeHere.
  76       if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
  77           !isPotentiallyReachable(I, BeforeHere, DT))
  78         return false;
  79       return true;
  80     }
  81
  82     bool captured(const Use *U) override {
  83       if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
  84         return false;
  85
  86       Instruction *I = cast<Instruction>(U->getUser());
  87       BasicBlock *BB = I->getParent();
  88       // Same logic as in shouldExplore.
  89       if (BeforeHere != I && !DT->isReachableFromEntry(BB))
  90         return false;
  91       if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
  92           !isPotentiallyReachable(I, BeforeHere, DT))
  93         return false;
  94       Captured = true;
  95       return true;
  96     }
  97
  98     const Instruction *BeforeHere;
  99     DominatorTree *DT;
 100
 101     bool ReturnCaptures;
 102
 103     bool Captured;
 104   };
 105 }
 106
 107 /// PointerMayBeCaptured - Return true if this pointer value may be captured
 108 /// by the enclosing function (which is required to exist).  This routine can
 109 /// be expensive, so consider caching the results.  The boolean ReturnCaptures
 110 /// specifies whether returning the value (or part of it) from the function
 111 /// counts as capturing it or not.  The boolean StoreCaptures specified whether
 112 /// storing the value (or part of it) into memory anywhere automatically
 113 /// counts as capturing it or not.
 114 bool llvm::PointerMayBeCaptured(const Value *V,
 115                                 bool ReturnCaptures, bool StoreCaptures) {
 116   assert(!isa<GlobalValue>(V) &&
 117          "It doesn't make sense to ask whether a global is captured.");
 118
 119   // TODO: If StoreCaptures is not true, we could do Fancy analysis
 120   // to determine whether this store is not actually an escape point.
 121   // In that case, BasicAliasAnalysis should be updated as well to
 122   // take advantage of this.
 123   (void)StoreCaptures;
 124
 125   SimpleCaptureTracker SCT(ReturnCaptures);
 126   PointerMayBeCaptured(V, &SCT);
 127   return SCT.Captured;
 128 }
 129
 130 /// PointerMayBeCapturedBefore - Return true if this pointer value may be
 131 /// captured by the enclosing function (which is required to exist). If a
 132 /// DominatorTree is provided, only captures which happen before the given
 133 /// instruction are considered. This routine can be expensive, so consider
 134 /// caching the results.  The boolean ReturnCaptures specifies whether
 135 /// returning the value (or part of it) from the function counts as capturing
 136 /// it or not.  The boolean StoreCaptures specified whether storing the value
 137 /// (or part of it) into memory anywhere automatically counts as capturing it
 138 /// or not.
 139 bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures,
 140                                       bool StoreCaptures, const Instruction *I,
 141                                       DominatorTree *DT) {
 142   assert(!isa<GlobalValue>(V) &&
 143          "It doesn't make sense to ask whether a global is captured.");
 144
 145   if (!DT)
 146     return PointerMayBeCaptured(V, ReturnCaptures, StoreCaptures);
 147
 148   // TODO: See comment in PointerMayBeCaptured regarding what could be done
 149   // with StoreCaptures.
 150
 151   CapturesBefore CB(ReturnCaptures, I, DT);
 152   PointerMayBeCaptured(V, &CB);
 153   return CB.Captured;
 154 }
 155
 156 /// TODO: Write a new FunctionPass AliasAnalysis so that it can keep
 157 /// a cache. Then we can move the code from BasicAliasAnalysis into
 158 /// that path, and remove this threshold.
 159 static int const Threshold = 20;
 160
 161 void llvm::PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker) {
 162   assert(V->getType()->isPointerTy() && "Capture is for pointers only!");
 163   SmallVector<const Use *, Threshold> Worklist;
 164   SmallSet<const Use *, Threshold> Visited;
 165   int Count = 0;
 166
 167   for (const Use &U : V->uses()) {
 168     // If there are lots of uses, conservatively say that the value
 169     // is captured to avoid taking too much compile time.
 170     if (Count++ >= Threshold)
 171       return Tracker->tooManyUses();
 172
 173     if (!Tracker->shouldExplore(&U)) continue;
 174     Visited.insert(&U);
 175     Worklist.push_back(&U);
 176   }
 177
 178   while (!Worklist.empty()) {
 179     const Use *U = Worklist.pop_back_val();
 180     Instruction *I = cast<Instruction>(U->getUser());
 181     V = U->get();
 182
 183     switch (I->getOpcode()) {
 184     case Instruction::Call:
 185     case Instruction::Invoke: {
 186       CallSite CS(I);
 187       // Not captured if the callee is readonly, doesn't return a copy through
 188       // its return value and doesn't unwind (a readonly function can leak bits
 189       // by throwing an exception or not depending on the input value).
 190       if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy())
 191         break;
 192
 193       // Not captured if only passed via 'nocapture' arguments.  Note that
 194       // calling a function pointer does not in itself cause the pointer to
 195       // be captured.  This is a subtle point considering that (for example)
 196       // the callee might return its own address.  It is analogous to saying
 197       // that loading a value from a pointer does not cause the pointer to be
 198       // captured, even though the loaded value might be the pointer itself
 199       // (think of self-referential objects).
 200       CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end();
 201       for (CallSite::arg_iterator A = B; A != E; ++A)
 202         if (A->get() == V && !CS.doesNotCapture(A - B))
 203           // The parameter is not marked 'nocapture' - captured.
 204           if (Tracker->captured(U))
 205             return;
 206       break;
 207     }
 208     case Instruction::Load:
 209       // Loading from a pointer does not cause it to be captured.
 210       break;
 211     case Instruction::VAArg:
 212       // "va-arg" from a pointer does not cause it to be captured.
 213       break;
 214     case Instruction::Store:
 215       if (V == I->getOperand(0))
 216         // Stored the pointer - conservatively assume it may be captured.
 217         if (Tracker->captured(U))
 218           return;
 219       // Storing to the pointee does not cause the pointer to be captured.
 220       break;
 221     case Instruction::BitCast:
 222     case Instruction::GetElementPtr:
 223     case Instruction::PHI:
 224     case Instruction::Select:
 225     case Instruction::AddrSpaceCast:
 226       // The original value is not captured via this if the new value isn't.
 227       Count = 0;
 228       for (Use &UU : I->uses()) {
 229         // If there are lots of uses, conservatively say that the value
 230         // is captured to avoid taking too much compile time.
 231         if (Count++ >= Threshold)
 232           return Tracker->tooManyUses();
 233
 234         if (Visited.insert(&UU))
 235           if (Tracker->shouldExplore(&UU))
 236             Worklist.push_back(&UU);
 237       }
 238       break;
 239     case Instruction::ICmp:
 240       // Don't count comparisons of a no-alias return value against null as
 241       // captures. This allows us to ignore comparisons of malloc results
 242       // with null, for example.
 243       if (ConstantPointerNull *CPN =
 244           dyn_cast<ConstantPointerNull>(I->getOperand(1)))
 245         if (CPN->getType()->getAddressSpace() == 0)
 246           if (isNoAliasCall(V->stripPointerCasts()))
 247             break;
 248       // Otherwise, be conservative. There are crazy ways to capture pointers
 249       // using comparisons.
 250       if (Tracker->captured(U))
 251         return;
 252       break;
 253     default:
 254       // Something else - be conservative and say it is captured.
 255       if (Tracker->captured(U))
 256         return;
 257       break;
 258     }
 259   }
 260
 261   // All uses examined.
 262 }