Home | History | Annotate | Download | only in Analysis 
      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/CaptureTracking.h"
     22 using namespace llvm;
     23 
     24 CaptureTracker::~CaptureTracker() {}
     25 
     26 namespace {
     27   struct SimpleCaptureTracker : public CaptureTracker {
     28     explicit SimpleCaptureTracker(bool ReturnCaptures)
     29       : ReturnCaptures(ReturnCaptures), Captured(false) {}
     30 
     31     void tooManyUses() { Captured = true; }
     32 
     33     bool shouldExplore(Use *U) { return true; }
     34 
     35     bool captured(Use *U) {
     36       if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures)
     37 	return false;
     38 
     39       Captured = true;
     40       return true;
     41     }
     42 
     43     bool ReturnCaptures;
     44 
     45     bool Captured;
     46   };
     47 }
     48 
     49 /// PointerMayBeCaptured - Return true if this pointer value may be captured
     50 /// by the enclosing function (which is required to exist).  This routine can
     51 /// be expensive, so consider caching the results.  The boolean ReturnCaptures
     52 /// specifies whether returning the value (or part of it) from the function
     53 /// counts as capturing it or not.  The boolean StoreCaptures specified whether
     54 /// storing the value (or part of it) into memory anywhere automatically
     55 /// counts as capturing it or not.
     56 bool llvm::PointerMayBeCaptured(const Value *V,
     57                                 bool ReturnCaptures, bool StoreCaptures) {
     58   assert(!isa<GlobalValue>(V) &&
     59          "It doesn't make sense to ask whether a global is captured.");
     60 
     61   // TODO: If StoreCaptures is not true, we could do Fancy analysis
     62   // to determine whether this store is not actually an escape point.
     63   // In that case, BasicAliasAnalysis should be updated as well to
     64   // take advantage of this.
     65   (void)StoreCaptures;
     66 
     67   SimpleCaptureTracker SCT(ReturnCaptures);
     68   PointerMayBeCaptured(V, &SCT);
     69   return SCT.Captured;
     70 }
     71 
     72 /// TODO: Write a new FunctionPass AliasAnalysis so that it can keep
     73 /// a cache. Then we can move the code from BasicAliasAnalysis into
     74 /// that path, and remove this threshold.
     75 static int const Threshold = 20;
     76 
     77 void llvm::PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker) {
     78   assert(V->getType()->isPointerTy() && "Capture is for pointers only!");
     79   SmallVector<Use*, Threshold> Worklist;
     80   SmallSet<Use*, Threshold> Visited;
     81   int Count = 0;
     82 
     83   for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end();
     84        UI != UE; ++UI) {
     85     // If there are lots of uses, conservatively say that the value
     86     // is captured to avoid taking too much compile time.
     87     if (Count++ >= Threshold)
     88       return Tracker->tooManyUses();
     89 
     90     Use *U = &UI.getUse();
     91     if (!Tracker->shouldExplore(U)) continue;
     92     Visited.insert(U);
     93     Worklist.push_back(U);
     94   }
     95 
     96   while (!Worklist.empty()) {
     97     Use *U = Worklist.pop_back_val();
     98     Instruction *I = cast<Instruction>(U->getUser());
     99     V = U->get();
    100 
    101     switch (I->getOpcode()) {
    102     case Instruction::Call:
    103     case Instruction::Invoke: {
    104       CallSite CS(I);
    105       // Not captured if the callee is readonly, doesn't return a copy through
    106       // its return value and doesn't unwind (a readonly function can leak bits
    107       // by throwing an exception or not depending on the input value).
    108       if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy())
    109         break;
    110 
    111       // Not captured if only passed via 'nocapture' arguments.  Note that
    112       // calling a function pointer does not in itself cause the pointer to
    113       // be captured.  This is a subtle point considering that (for example)
    114       // the callee might return its own address.  It is analogous to saying
    115       // that loading a value from a pointer does not cause the pointer to be
    116       // captured, even though the loaded value might be the pointer itself
    117       // (think of self-referential objects).
    118       CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end();
    119       for (CallSite::arg_iterator A = B; A != E; ++A)
    120         if (A->get() == V && !CS.doesNotCapture(A - B))
    121           // The parameter is not marked 'nocapture' - captured.
    122           if (Tracker->captured(U))
    123             return;
    124       break;
    125     }
    126     case Instruction::Load:
    127       // Loading from a pointer does not cause it to be captured.
    128       break;
    129     case Instruction::VAArg:
    130       // "va-arg" from a pointer does not cause it to be captured.
    131       break;
    132     case Instruction::Store:
    133       if (V == I->getOperand(0))
    134         // Stored the pointer - conservatively assume it may be captured.
    135         if (Tracker->captured(U))
    136           return;
    137       // Storing to the pointee does not cause the pointer to be captured.
    138       break;
    139     case Instruction::BitCast:
    140     case Instruction::GetElementPtr:
    141     case Instruction::PHI:
    142     case Instruction::Select:
    143       // The original value is not captured via this if the new value isn't.
    144       for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end();
    145            UI != UE; ++UI) {
    146         Use *U = &UI.getUse();
    147         if (Visited.insert(U))
    148           if (Tracker->shouldExplore(U))
    149             Worklist.push_back(U);
    150       }
    151       break;
    152     case Instruction::ICmp:
    153       // Don't count comparisons of a no-alias return value against null as
    154       // captures. This allows us to ignore comparisons of malloc results
    155       // with null, for example.
    156       if (isNoAliasCall(V->stripPointerCasts()))
    157         if (ConstantPointerNull *CPN =
    158               dyn_cast<ConstantPointerNull>(I->getOperand(1)))
    159           if (CPN->getType()->getAddressSpace() == 0)
    160             break;
    161       // Otherwise, be conservative. There are crazy ways to capture pointers
    162       // using comparisons.
    163       if (Tracker->captured(U))
    164         return;
    165       break;
    166     default:
    167       // Something else - be conservative and say it is captured.
    168       if (Tracker->captured(U))
    169         return;
    170       break;
    171     }
    172   }
    173 
    174   // All uses examined.
    175 }
    176