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