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