Home | History | Annotate | Download | only in ObjCARC 
      1 //===- ProvenanceAnalysis.cpp - ObjC ARC Optimization ---------------------===//
      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 /// \file
     10 ///
     11 /// This file defines a special form of Alias Analysis called ``Provenance
     12 /// Analysis''. The word ``provenance'' refers to the history of the ownership
     13 /// of an object. Thus ``Provenance Analysis'' is an analysis which attempts to
     14 /// use various techniques to determine if locally
     15 ///
     16 /// WARNING: This file knows about certain library functions. It recognizes them
     17 /// by name, and hardwires knowledge of their semantics.
     18 ///
     19 /// WARNING: This file knows about how certain Objective-C library functions are
     20 /// used. Naive LLVM IR transformations which would otherwise be
     21 /// behavior-preserving may break these assumptions.
     22 ///
     23 //===----------------------------------------------------------------------===//
     24 
     25 #include "ObjCARC.h"
     26 #include "ProvenanceAnalysis.h"
     27 #include "llvm/ADT/STLExtras.h"
     28 #include "llvm/ADT/SmallPtrSet.h"
     29 
     30 using namespace llvm;
     31 using namespace llvm::objcarc;
     32 
     33 bool ProvenanceAnalysis::relatedSelect(const SelectInst *A,
     34                                        const Value *B) {
     35   const DataLayout &DL = A->getModule()->getDataLayout();
     36   // If the values are Selects with the same condition, we can do a more precise
     37   // check: just check for relations between the values on corresponding arms.
     38   if (const SelectInst *SB = dyn_cast<SelectInst>(B))
     39     if (A->getCondition() == SB->getCondition())
     40       return related(A->getTrueValue(), SB->getTrueValue(), DL) ||
     41              related(A->getFalseValue(), SB->getFalseValue(), DL);
     42 
     43   // Check both arms of the Select node individually.
     44   return related(A->getTrueValue(), B, DL) ||
     45          related(A->getFalseValue(), B, DL);
     46 }
     47 
     48 bool ProvenanceAnalysis::relatedPHI(const PHINode *A,
     49                                     const Value *B) {
     50   const DataLayout &DL = A->getModule()->getDataLayout();
     51   // If the values are PHIs in the same block, we can do a more precise as well
     52   // as efficient check: just check for relations between the values on
     53   // corresponding edges.
     54   if (const PHINode *PNB = dyn_cast<PHINode>(B))
     55     if (PNB->getParent() == A->getParent()) {
     56       for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i)
     57         if (related(A->getIncomingValue(i),
     58                     PNB->getIncomingValueForBlock(A->getIncomingBlock(i)), DL))
     59           return true;
     60       return false;
     61     }
     62 
     63   // Check each unique source of the PHI node against B.
     64   SmallPtrSet<const Value *, 4> UniqueSrc;
     65   for (Value *PV1 : A->incoming_values()) {
     66     if (UniqueSrc.insert(PV1).second && related(PV1, B, DL))
     67       return true;
     68   }
     69 
     70   // All of the arms checked out.
     71   return false;
     72 }
     73 
     74 /// Test if the value of P, or any value covered by its provenance, is ever
     75 /// stored within the function (not counting callees).
     76 static bool IsStoredObjCPointer(const Value *P) {
     77   SmallPtrSet<const Value *, 8> Visited;
     78   SmallVector<const Value *, 8> Worklist;
     79   Worklist.push_back(P);
     80   Visited.insert(P);
     81   do {
     82     P = Worklist.pop_back_val();
     83     for (const Use &U : P->uses()) {
     84       const User *Ur = U.getUser();
     85       if (isa<StoreInst>(Ur)) {
     86         if (U.getOperandNo() == 0)
     87           // The pointer is stored.
     88           return true;
     89         // The pointed is stored through.
     90         continue;
     91       }
     92       if (isa<CallInst>(Ur))
     93         // The pointer is passed as an argument, ignore this.
     94         continue;
     95       if (isa<PtrToIntInst>(P))
     96         // Assume the worst.
     97         return true;
     98       if (Visited.insert(Ur).second)
     99         Worklist.push_back(Ur);
    100     }
    101   } while (!Worklist.empty());
    102 
    103   // Everything checked out.
    104   return false;
    105 }
    106 
    107 bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B,
    108                                       const DataLayout &DL) {
    109   // Skip past provenance pass-throughs.
    110   A = GetUnderlyingObjCPtr(A, DL);
    111   B = GetUnderlyingObjCPtr(B, DL);
    112 
    113   // Quick check.
    114   if (A == B)
    115     return true;
    116 
    117   // Ask regular AliasAnalysis, for a first approximation.
    118   switch (AA->alias(A, B)) {
    119   case NoAlias:
    120     return false;
    121   case MustAlias:
    122   case PartialAlias:
    123     return true;
    124   case MayAlias:
    125     break;
    126   }
    127 
    128   bool AIsIdentified = IsObjCIdentifiedObject(A);
    129   bool BIsIdentified = IsObjCIdentifiedObject(B);
    130 
    131   // An ObjC-Identified object can't alias a load if it is never locally stored.
    132   if (AIsIdentified) {
    133     // Check for an obvious escape.
    134     if (isa<LoadInst>(B))
    135       return IsStoredObjCPointer(A);
    136     if (BIsIdentified) {
    137       // Check for an obvious escape.
    138       if (isa<LoadInst>(A))
    139         return IsStoredObjCPointer(B);
    140       // Both pointers are identified and escapes aren't an evident problem.
    141       return false;
    142     }
    143   } else if (BIsIdentified) {
    144     // Check for an obvious escape.
    145     if (isa<LoadInst>(A))
    146       return IsStoredObjCPointer(B);
    147   }
    148 
    149    // Special handling for PHI and Select.
    150   if (const PHINode *PN = dyn_cast<PHINode>(A))
    151     return relatedPHI(PN, B);
    152   if (const PHINode *PN = dyn_cast<PHINode>(B))
    153     return relatedPHI(PN, A);
    154   if (const SelectInst *S = dyn_cast<SelectInst>(A))
    155     return relatedSelect(S, B);
    156   if (const SelectInst *S = dyn_cast<SelectInst>(B))
    157     return relatedSelect(S, A);
    158 
    159   // Conservative.
    160   return true;
    161 }
    162 
    163 bool ProvenanceAnalysis::related(const Value *A, const Value *B,
    164                                  const DataLayout &DL) {
    165   // Begin by inserting a conservative value into the map. If the insertion
    166   // fails, we have the answer already. If it succeeds, leave it there until we
    167   // compute the real answer to guard against recursive queries.
    168   if (A > B) std::swap(A, B);
    169   std::pair<CachedResultsTy::iterator, bool> Pair =
    170     CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
    171   if (!Pair.second)
    172     return Pair.first->second;
    173 
    174   bool Result = relatedCheck(A, B, DL);
    175   CachedResults[ValuePairTy(A, B)] = Result;
    176   return Result;
    177 }
    178