lib/Transforms/ObjCARC/ProvenanceAnalysis.cpp

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