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   // If the values are Selects with the same condition, we can do a more precise
     36   // check: just check for relations between the values on corresponding arms.
     37   if (const SelectInst *SB = dyn_cast<SelectInst>(B))
     38     if (A->getCondition() == SB->getCondition())
     39       return related(A->getTrueValue(), SB->getTrueValue()) ||
     40              related(A->getFalseValue(), SB->getFalseValue());
     41 
     42   // Check both arms of the Select node individually.
     43   return related(A->getTrueValue(), B) ||
     44          related(A->getFalseValue(), B);
     45 }
     46 
     47 bool ProvenanceAnalysis::relatedPHI(const PHINode *A,
     48                                     const Value *B) {
     49   // If the values are PHIs in the same block, we can do a more precise as well
     50   // as efficient check: just check for relations between the values on
     51   // corresponding edges.
     52   if (const PHINode *PNB = dyn_cast<PHINode>(B))
     53     if (PNB->getParent() == A->getParent()) {
     54       for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i)
     55         if (related(A->getIncomingValue(i),
     56                     PNB->getIncomingValueForBlock(A->getIncomingBlock(i))))
     57           return true;
     58       return false;
     59     }
     60 
     61   // Check each unique source of the PHI node against B.
     62   SmallPtrSet<const Value *, 4> UniqueSrc;
     63   for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i) {
     64     const Value *PV1 = A->getIncomingValue(i);
     65     if (UniqueSrc.insert(PV1) && related(PV1, B))
     66       return true;
     67   }
     68 
     69   // All of the arms checked out.
     70   return false;
     71 }
     72 
     73 /// Test if the value of P, or any value covered by its provenance, is ever
     74 /// stored within the function (not counting callees).
     75 static bool IsStoredObjCPointer(const Value *P) {
     76   SmallPtrSet<const Value *, 8> Visited;
     77   SmallVector<const Value *, 8> Worklist;
     78   Worklist.push_back(P);
     79   Visited.insert(P);
     80   do {
     81     P = Worklist.pop_back_val();
     82     for (const Use &U : P->uses()) {
     83       const User *Ur = U.getUser();
     84       if (isa<StoreInst>(Ur)) {
     85         if (U.getOperandNo() == 0)
     86           // The pointer is stored.
     87           return true;
     88         // The pointed is stored through.
     89         continue;
     90       }
     91       if (isa<CallInst>(Ur))
     92         // The pointer is passed as an argument, ignore this.
     93         continue;
     94       if (isa<PtrToIntInst>(P))
     95         // Assume the worst.
     96         return true;
     97       if (Visited.insert(Ur))
     98         Worklist.push_back(Ur);
     99     }
    100   } while (!Worklist.empty());
    101 
    102   // Everything checked out.
    103   return false;
    104 }
    105 
    106 bool ProvenanceAnalysis::relatedCheck(const Value *A,
    107                                       const Value *B) {
    108   // Skip past provenance pass-throughs.
    109   A = GetUnderlyingObjCPtr(A);
    110   B = GetUnderlyingObjCPtr(B);
    111 
    112   // Quick check.
    113   if (A == B)
    114     return true;
    115 
    116   // Ask regular AliasAnalysis, for a first approximation.
    117   switch (AA->alias(A, B)) {
    118   case AliasAnalysis::NoAlias:
    119     return false;
    120   case AliasAnalysis::MustAlias:
    121   case AliasAnalysis::PartialAlias:
    122     return true;
    123   case AliasAnalysis::MayAlias:
    124     break;
    125   }
    126 
    127   bool AIsIdentified = IsObjCIdentifiedObject(A);
    128   bool BIsIdentified = IsObjCIdentifiedObject(B);
    129 
    130   // An ObjC-Identified object can't alias a load if it is never locally stored.
    131   if (AIsIdentified) {
    132     // Check for an obvious escape.
    133     if (isa<LoadInst>(B))
    134       return IsStoredObjCPointer(A);
    135     if (BIsIdentified) {
    136       // Check for an obvious escape.
    137       if (isa<LoadInst>(A))
    138         return IsStoredObjCPointer(B);
    139       // Both pointers are identified and escapes aren't an evident problem.
    140       return false;
    141     }
    142   } else if (BIsIdentified) {
    143     // Check for an obvious escape.
    144     if (isa<LoadInst>(A))
    145       return IsStoredObjCPointer(B);
    146   }
    147 
    148    // Special handling for PHI and Select.
    149   if (const PHINode *PN = dyn_cast<PHINode>(A))
    150     return relatedPHI(PN, B);
    151   if (const PHINode *PN = dyn_cast<PHINode>(B))
    152     return relatedPHI(PN, A);
    153   if (const SelectInst *S = dyn_cast<SelectInst>(A))
    154     return relatedSelect(S, B);
    155   if (const SelectInst *S = dyn_cast<SelectInst>(B))
    156     return relatedSelect(S, A);
    157 
    158   // Conservative.
    159   return true;
    160 }
    161 
    162 bool ProvenanceAnalysis::related(const Value *A,
    163                                  const Value *B) {
    164   // Begin by inserting a conservative value into the map. If the insertion
    165   // fails, we have the answer already. If it succeeds, leave it there until we
    166   // compute the real answer to guard against recursive queries.
    167   if (A > B) std::swap(A, B);
    168   std::pair<CachedResultsTy::iterator, bool> Pair =
    169     CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
    170   if (!Pair.second)
    171     return Pair.first->second;
    172 
    173   bool Result = relatedCheck(A, B);
    174   CachedResults[ValuePairTy(A, B)] = Result;
    175   return Result;
    176 }
    177