llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.cpp

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