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