contrib/llvm-project/llvm/lib/Analysis/CaptureTracking.cpp

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