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