contrib/llvm/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/Analysis/CaptureTracking.h"
  20 #include "llvm/ADT/SmallSet.h"
  21 #include "llvm/ADT/SmallVector.h"
  22 #include "llvm/Analysis/AliasAnalysis.h"
  23 #include "llvm/Analysis/CFG.h"
  24 #include "llvm/Analysis/OrderedBasicBlock.h"
  25 #include "llvm/Analysis/ValueTracking.h"
  26 #include "llvm/IR/CallSite.h"
  27 #include "llvm/IR/Constants.h"
  28 #include "llvm/IR/Dominators.h"
  29 #include "llvm/IR/Instructions.h"
  30 #include "llvm/IR/IntrinsicInst.h"
  31
  32 using namespace llvm;
  33
  34 CaptureTracker::~CaptureTracker() {}
  35
  36 bool CaptureTracker::shouldExplore(const Use *U) { return true; }
  37
  38 namespace {
  39   struct SimpleCaptureTracker : public CaptureTracker {
  40     explicit SimpleCaptureTracker(bool ReturnCaptures)
  41       : ReturnCaptures(ReturnCaptures), Captured(false) {}
  42
  43     void tooManyUses() override { Captured = true; }
  44
  45     bool captured(const Use *U) override {
  46       if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
  47         return false;
  48
  49       Captured = true;
  50       return true;
  51     }
  52
  53     bool ReturnCaptures;
  54
  55     bool Captured;
  56   };
  57
  58   /// Only find pointer captures which happen before the given instruction. Uses
  59   /// the dominator tree to determine whether one instruction is before another.
  60   /// Only support the case where the Value is defined in the same basic block
  61   /// as the given instruction and the use.
  62   struct CapturesBefore : public CaptureTracker {
  63
  64     CapturesBefore(bool ReturnCaptures, const Instruction *I, const DominatorTree *DT,
  65                    bool IncludeI, OrderedBasicBlock *IC)
  66       : OrderedBB(IC), BeforeHere(I), DT(DT),
  67         ReturnCaptures(ReturnCaptures), IncludeI(IncludeI), Captured(false) {}
  68
  69     void tooManyUses() override { Captured = true; }
  70
  71     bool isSafeToPrune(Instruction *I) {
  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 true;
  77
  78       // Compute the case where both instructions are inside the same basic
  79       // block. Since instructions in the same BB as BeforeHere are numbered in
  80       // 'OrderedBB', avoid using 'dominates' and 'isPotentiallyReachable'
  81       // which are very expensive for large basic blocks.
  82       if (BB == BeforeHere->getParent()) {
  83         // 'I' dominates 'BeforeHere' => not safe to prune.
  84         //
  85         // The value defined by an invoke dominates an instruction only
  86         // if it dominates every instruction in UseBB. A PHI is dominated only
  87         // if the instruction dominates every possible use in the UseBB. Since
  88         // UseBB == BB, avoid pruning.
  89         if (isa<InvokeInst>(BeforeHere) || isa<PHINode>(I) || I == BeforeHere)
  90           return false;
  91         if (!OrderedBB->dominates(BeforeHere, I))
  92           return false;
  93
  94         // 'BeforeHere' comes before 'I', it's safe to prune if we also
  95         // guarantee that 'I' never reaches 'BeforeHere' through a back-edge or
  96         // by its successors, i.e, prune if:
  97         //
  98         //  (1) BB is an entry block or have no successors.
  99         //  (2) There's no path coming back through BB successors.
 100         if (BB == &BB->getParent()->getEntryBlock() ||
 101             !BB->getTerminator()->getNumSuccessors())
 102           return true;
 103
 104         SmallVector<BasicBlock*, 32> Worklist;
 105         Worklist.append(succ_begin(BB), succ_end(BB));
 106         return !isPotentiallyReachableFromMany(Worklist, BB, DT);
 107       }
 108
 109       // If the value is defined in the same basic block as use and BeforeHere,
 110       // there is no need to explore the use if BeforeHere dominates use.
 111       // Check whether there is a path from I to BeforeHere.
 112       if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
 113           !isPotentiallyReachable(I, BeforeHere, DT))
 114         return true;
 115
 116       return false;
 117     }
 118
 119     bool shouldExplore(const Use *U) override {
 120       Instruction *I = cast<Instruction>(U->getUser());
 121
 122       if (BeforeHere == I && !IncludeI)
 123         return false;
 124
 125       if (isSafeToPrune(I))
 126         return false;
 127
 128       return true;
 129     }
 130
 131     bool captured(const Use *U) override {
 132       if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
 133         return false;
 134
 135       if (!shouldExplore(U))
 136         return false;
 137
 138       Captured = true;
 139       return true;
 140     }
 141
 142     OrderedBasicBlock *OrderedBB;
 143     const Instruction *BeforeHere;
 144     const DominatorTree *DT;
 145
 146     bool ReturnCaptures;
 147     bool IncludeI;
 148
 149     bool Captured;
 150   };
 151 }
 152
 153 /// PointerMayBeCaptured - Return true if this pointer value may be captured
 154 /// by the enclosing function (which is required to exist).  This routine can
 155 /// be expensive, so consider caching the results.  The boolean ReturnCaptures
 156 /// specifies whether returning the value (or part of it) from the function
 157 /// counts as capturing it or not.  The boolean StoreCaptures specified whether
 158 /// storing the value (or part of it) into memory anywhere automatically
 159 /// counts as capturing it or not.
 160 bool llvm::PointerMayBeCaptured(const Value *V,
 161                                 bool ReturnCaptures, bool StoreCaptures) {
 162   assert(!isa<GlobalValue>(V) &&
 163          "It doesn't make sense to ask whether a global is captured.");
 164
 165   // TODO: If StoreCaptures is not true, we could do Fancy analysis
 166   // to determine whether this store is not actually an escape point.
 167   // In that case, BasicAliasAnalysis should be updated as well to
 168   // take advantage of this.
 169   (void)StoreCaptures;
 170
 171   SimpleCaptureTracker SCT(ReturnCaptures);
 172   PointerMayBeCaptured(V, &SCT);
 173   return SCT.Captured;
 174 }
 175
 176 /// PointerMayBeCapturedBefore - Return true if this pointer value may be
 177 /// captured by the enclosing function (which is required to exist). If a
 178 /// DominatorTree is provided, only captures which happen before the given
 179 /// instruction are considered. This routine can be expensive, so consider
 180 /// caching the results.  The boolean ReturnCaptures specifies whether
 181 /// returning the value (or part of it) from the function counts as capturing
 182 /// it or not.  The boolean StoreCaptures specified whether storing the value
 183 /// (or part of it) into memory anywhere automatically counts as capturing it
 184 /// or not. A ordered basic block \p OBB can be used in order to speed up
 185 /// queries about relative order among instructions in the same basic block.
 186 bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures,
 187                                       bool StoreCaptures, const Instruction *I,
 188                                       const DominatorTree *DT, bool IncludeI,
 189                                       OrderedBasicBlock *OBB) {
 190   assert(!isa<GlobalValue>(V) &&
 191          "It doesn't make sense to ask whether a global is captured.");
 192   bool UseNewOBB = OBB == nullptr;
 193
 194   if (!DT)
 195     return PointerMayBeCaptured(V, ReturnCaptures, StoreCaptures);
 196   if (UseNewOBB)
 197     OBB = new OrderedBasicBlock(I->getParent());
 198
 199   // TODO: See comment in PointerMayBeCaptured regarding what could be done
 200   // with StoreCaptures.
 201
 202   CapturesBefore CB(ReturnCaptures, I, DT, IncludeI, OBB);
 203   PointerMayBeCaptured(V, &CB);
 204
 205   if (UseNewOBB)
 206     delete OBB;
 207   return CB.Captured;
 208 }
 209
 210 /// TODO: Write a new FunctionPass AliasAnalysis so that it can keep
 211 /// a cache. Then we can move the code from BasicAliasAnalysis into
 212 /// that path, and remove this threshold.
 213 static int const Threshold = 20;
 214
 215 void llvm::PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker) {
 216   assert(V->getType()->isPointerTy() && "Capture is for pointers only!");
 217   SmallVector<const Use *, Threshold> Worklist;
 218   SmallSet<const Use *, Threshold> Visited;
 219
 220   auto AddUses = [&](const Value *V) {
 221     int Count = 0;
 222     for (const Use &U : V->uses()) {
 223       // If there are lots of uses, conservatively say that the value
 224       // is captured to avoid taking too much compile time.
 225       if (Count++ >= Threshold)
 226         return Tracker->tooManyUses();
 227       if (!Visited.insert(&U).second)
 228         continue;
 229       if (!Tracker->shouldExplore(&U))
 230         continue;
 231       Worklist.push_back(&U);
 232     }
 233   };
 234   AddUses(V);
 235
 236   while (!Worklist.empty()) {
 237     const Use *U = Worklist.pop_back_val();
 238     Instruction *I = cast<Instruction>(U->getUser());
 239     V = U->get();
 240
 241     switch (I->getOpcode()) {
 242     case Instruction::Call:
 243     case Instruction::Invoke: {
 244       CallSite CS(I);
 245       // Not captured if the callee is readonly, doesn't return a copy through
 246       // its return value and doesn't unwind (a readonly function can leak bits
 247       // by throwing an exception or not depending on the input value).
 248       if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy())
 249         break;
 250
 251       // The pointer is not captured if returned pointer is not captured.
 252       // NOTE: CaptureTracking users should not assume that only functions
 253       // marked with nocapture do not capture. This means that places like
 254       // GetUnderlyingObject in ValueTracking or DecomposeGEPExpression
 255       // in BasicAA also need to know about this property.
 256       if (isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(CS)) {
 257         AddUses(I);
 258         break;
 259       }
 260
 261       // Volatile operations effectively capture the memory location that they
 262       // load and store to.
 263       if (auto *MI = dyn_cast<MemIntrinsic>(I))
 264         if (MI->isVolatile())
 265           if (Tracker->captured(U))
 266             return;
 267
 268       // Not captured if only passed via 'nocapture' arguments.  Note that
 269       // calling a function pointer does not in itself cause the pointer to
 270       // be captured.  This is a subtle point considering that (for example)
 271       // the callee might return its own address.  It is analogous to saying
 272       // that loading a value from a pointer does not cause the pointer to be
 273       // captured, even though the loaded value might be the pointer itself
 274       // (think of self-referential objects).
 275       CallSite::data_operand_iterator B =
 276         CS.data_operands_begin(), E = CS.data_operands_end();
 277       for (CallSite::data_operand_iterator A = B; A != E; ++A)
 278         if (A->get() == V && !CS.doesNotCapture(A - B))
 279           // The parameter is not marked 'nocapture' - captured.
 280           if (Tracker->captured(U))
 281             return;
 282       break;
 283     }
 284     case Instruction::Load:
 285       // Volatile loads make the address observable.
 286       if (cast<LoadInst>(I)->isVolatile())
 287         if (Tracker->captured(U))
 288           return;
 289       break;
 290     case Instruction::VAArg:
 291       // "va-arg" from a pointer does not cause it to be captured.
 292       break;
 293     case Instruction::Store:
 294         // Stored the pointer - conservatively assume it may be captured.
 295         // Volatile stores make the address observable.
 296       if (V == I->getOperand(0) || cast<StoreInst>(I)->isVolatile())
 297         if (Tracker->captured(U))
 298           return;
 299       break;
 300     case Instruction::AtomicRMW: {
 301       // atomicrmw conceptually includes both a load and store from
 302       // the same location.
 303       // As with a store, the location being accessed is not captured,
 304       // but the value being stored is.
 305       // Volatile stores make the address observable.
 306       auto *ARMWI = cast<AtomicRMWInst>(I);
 307       if (ARMWI->getValOperand() == V || ARMWI->isVolatile())
 308         if (Tracker->captured(U))
 309           return;
 310       break;
 311     }
 312     case Instruction::AtomicCmpXchg: {
 313       // cmpxchg conceptually includes both a load and store from
 314       // the same location.
 315       // As with a store, the location being accessed is not captured,
 316       // but the value being stored is.
 317       // Volatile stores make the address observable.
 318       auto *ACXI = cast<AtomicCmpXchgInst>(I);
 319       if (ACXI->getCompareOperand() == V || ACXI->getNewValOperand() == V ||
 320           ACXI->isVolatile())
 321         if (Tracker->captured(U))
 322           return;
 323       break;
 324     }
 325     case Instruction::BitCast:
 326     case Instruction::GetElementPtr:
 327     case Instruction::PHI:
 328     case Instruction::Select:
 329     case Instruction::AddrSpaceCast:
 330       // The original value is not captured via this if the new value isn't.
 331       AddUses(I);
 332       break;
 333     case Instruction::ICmp: {
 334       // Don't count comparisons of a no-alias return value against null as
 335       // captures. This allows us to ignore comparisons of malloc results
 336       // with null, for example.
 337       if (ConstantPointerNull *CPN =
 338           dyn_cast<ConstantPointerNull>(I->getOperand(1)))
 339         if (CPN->getType()->getAddressSpace() == 0)
 340           if (isNoAliasCall(V->stripPointerCasts()))
 341             break;
 342       // Comparison against value stored in global variable. Given the pointer
 343       // does not escape, its value cannot be guessed and stored separately in a
 344       // global variable.
 345       unsigned OtherIndex = (I->getOperand(0) == V) ? 1 : 0;
 346       auto *LI = dyn_cast<LoadInst>(I->getOperand(OtherIndex));
 347       if (LI && isa<GlobalVariable>(LI->getPointerOperand()))
 348         break;
 349       // Otherwise, be conservative. There are crazy ways to capture pointers
 350       // using comparisons.
 351       if (Tracker->captured(U))
 352         return;
 353       break;
 354     }
 355     default:
 356       // Something else - be conservative and say it is captured.
 357       if (Tracker->captured(U))
 358         return;
 359       break;
 360     }
 361   }
 362
 363   // All uses examined.
 364 }