1 //===- DependencyAnalysis.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 /// \file 9 /// 10 /// This file defines special dependency analysis routines used in Objective C 11 /// ARC Optimizations. 12 /// 13 /// WARNING: This file knows about certain library functions. It recognizes them 14 /// by name, and hardwires knowledge of their semantics. 15 /// 16 /// WARNING: This file knows about how certain Objective-C library functions are 17 /// used. Naive LLVM IR transformations which would otherwise be 18 /// behavior-preserving may break these assumptions. 19 /// 20 //===----------------------------------------------------------------------===// 21 22 #include "DependencyAnalysis.h" 23 #include "ObjCARC.h" 24 #include "ProvenanceAnalysis.h" 25 #include "llvm/Analysis/AliasAnalysis.h" 26 #include "llvm/IR/CFG.h" 27 28 using namespace llvm; 29 using namespace llvm::objcarc; 30 31 #define DEBUG_TYPE "objc-arc-dependency" 32 33 /// Test whether the given instruction can result in a reference count 34 /// modification (positive or negative) for the pointer's object. 35 bool llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr, 36 ProvenanceAnalysis &PA, 37 ARCInstKind Class) { 38 switch (Class) { 39 case ARCInstKind::Autorelease: 40 case ARCInstKind::AutoreleaseRV: 41 case ARCInstKind::IntrinsicUser: 42 case ARCInstKind::User: 43 // These operations never directly modify a reference count. 44 return false; 45 default: break; 46 } 47 48 const auto *Call = cast<CallBase>(Inst); 49 50 // See if AliasAnalysis can help us with the call. 51 FunctionModRefBehavior MRB = PA.getAA()->getModRefBehavior(Call); 52 if (AliasAnalysis::onlyReadsMemory(MRB)) 53 return false; 54 if (AliasAnalysis::onlyAccessesArgPointees(MRB)) { 55 for (const Value *Op : Call->args()) { 56 if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op)) 57 return true; 58 } 59 return false; 60 } 61 62 // Assume the worst. 63 return true; 64 } 65 66 bool llvm::objcarc::CanDecrementRefCount(const Instruction *Inst, 67 const Value *Ptr, 68 ProvenanceAnalysis &PA, 69 ARCInstKind Class) { 70 // First perform a quick check if Class can not touch ref counts. 71 if (!CanDecrementRefCount(Class)) 72 return false; 73 74 // Otherwise, just use CanAlterRefCount for now. 75 return CanAlterRefCount(Inst, Ptr, PA, Class); 76 } 77 78 /// Test whether the given instruction can "use" the given pointer's object in a 79 /// way that requires the reference count to be positive. 80 bool llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr, 81 ProvenanceAnalysis &PA, ARCInstKind Class) { 82 // ARCInstKind::Call operations (as opposed to 83 // ARCInstKind::CallOrUser) never "use" objc pointers. 84 if (Class == ARCInstKind::Call) 85 return false; 86 87 // Consider various instructions which may have pointer arguments which are 88 // not "uses". 89 if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) { 90 // Comparing a pointer with null, or any other constant, isn't really a use, 91 // because we don't care what the pointer points to, or about the values 92 // of any other dynamic reference-counted pointers. 93 if (!IsPotentialRetainableObjPtr(ICI->getOperand(1), *PA.getAA())) 94 return false; 95 } else if (const auto *CS = dyn_cast<CallBase>(Inst)) { 96 // For calls, just check the arguments (and not the callee operand). 97 for (const Value *Op : CS->args()) 98 if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op)) 99 return true; 100 return false; 101 } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 102 // Special-case stores, because we don't care about the stored value, just 103 // the store address. 104 const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand()); 105 // If we can't tell what the underlying object was, assume there is a 106 // dependence. 107 return IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Op, Ptr); 108 } 109 110 // Check each operand for a match. 111 for (const Use &U : Inst->operands()) { 112 const Value *Op = U; 113 if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op)) 114 return true; 115 } 116 return false; 117 } 118 119 /// Test if there can be dependencies on Inst through Arg. This function only 120 /// tests dependencies relevant for removing pairs of calls. 121 bool 122 llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst, 123 const Value *Arg, ProvenanceAnalysis &PA) { 124 // If we've reached the definition of Arg, stop. 125 if (Inst == Arg) 126 return true; 127 128 switch (Flavor) { 129 case NeedsPositiveRetainCount: { 130 ARCInstKind Class = GetARCInstKind(Inst); 131 switch (Class) { 132 case ARCInstKind::AutoreleasepoolPop: 133 case ARCInstKind::AutoreleasepoolPush: 134 case ARCInstKind::None: 135 return false; 136 default: 137 return CanUse(Inst, Arg, PA, Class); 138 } 139 } 140 141 case AutoreleasePoolBoundary: { 142 ARCInstKind Class = GetARCInstKind(Inst); 143 switch (Class) { 144 case ARCInstKind::AutoreleasepoolPop: 145 case ARCInstKind::AutoreleasepoolPush: 146 // These mark the end and begin of an autorelease pool scope. 147 return true; 148 default: 149 // Nothing else does this. 150 return false; 151 } 152 } 153 154 case CanChangeRetainCount: { 155 ARCInstKind Class = GetARCInstKind(Inst); 156 switch (Class) { 157 case ARCInstKind::AutoreleasepoolPop: 158 // Conservatively assume this can decrement any count. 159 return true; 160 case ARCInstKind::AutoreleasepoolPush: 161 case ARCInstKind::None: 162 return false; 163 default: 164 return CanAlterRefCount(Inst, Arg, PA, Class); 165 } 166 } 167 168 case RetainAutoreleaseDep: 169 switch (GetBasicARCInstKind(Inst)) { 170 case ARCInstKind::AutoreleasepoolPop: 171 case ARCInstKind::AutoreleasepoolPush: 172 // Don't merge an objc_autorelease with an objc_retain inside a different 173 // autoreleasepool scope. 174 return true; 175 case ARCInstKind::Retain: 176 case ARCInstKind::RetainRV: 177 // Check for a retain of the same pointer for merging. 178 return GetArgRCIdentityRoot(Inst) == Arg; 179 default: 180 // Nothing else matters for objc_retainAutorelease formation. 181 return false; 182 } 183 184 case RetainAutoreleaseRVDep: { 185 ARCInstKind Class = GetBasicARCInstKind(Inst); 186 switch (Class) { 187 case ARCInstKind::Retain: 188 case ARCInstKind::RetainRV: 189 // Check for a retain of the same pointer for merging. 190 return GetArgRCIdentityRoot(Inst) == Arg; 191 default: 192 // Anything that can autorelease interrupts 193 // retainAutoreleaseReturnValue formation. 194 return CanInterruptRV(Class); 195 } 196 } 197 } 198 199 llvm_unreachable("Invalid dependence flavor"); 200 } 201 202 /// Walk up the CFG from StartPos (which is in StartBB) and find local and 203 /// non-local dependencies on Arg. 204 /// 205 /// TODO: Cache results? 206 static bool findDependencies(DependenceKind Flavor, const Value *Arg, 207 BasicBlock *StartBB, Instruction *StartInst, 208 SmallPtrSetImpl<Instruction *> &DependingInsts, 209 ProvenanceAnalysis &PA) { 210 BasicBlock::iterator StartPos = StartInst->getIterator(); 211 212 SmallPtrSet<const BasicBlock *, 4> Visited; 213 SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist; 214 Worklist.push_back(std::make_pair(StartBB, StartPos)); 215 do { 216 std::pair<BasicBlock *, BasicBlock::iterator> Pair = 217 Worklist.pop_back_val(); 218 BasicBlock *LocalStartBB = Pair.first; 219 BasicBlock::iterator LocalStartPos = Pair.second; 220 BasicBlock::iterator StartBBBegin = LocalStartBB->begin(); 221 for (;;) { 222 if (LocalStartPos == StartBBBegin) { 223 pred_iterator PI(LocalStartBB), PE(LocalStartBB, false); 224 if (PI == PE) 225 // Return if we've reached the function entry. 226 return false; 227 // Add the predecessors to the worklist. 228 do { 229 BasicBlock *PredBB = *PI; 230 if (Visited.insert(PredBB).second) 231 Worklist.push_back(std::make_pair(PredBB, PredBB->end())); 232 } while (++PI != PE); 233 break; 234 } 235 236 Instruction *Inst = &*--LocalStartPos; 237 if (Depends(Flavor, Inst, Arg, PA)) { 238 DependingInsts.insert(Inst); 239 break; 240 } 241 } 242 } while (!Worklist.empty()); 243 244 // Determine whether the original StartBB post-dominates all of the blocks we 245 // visited. If not, insert a sentinal indicating that most optimizations are 246 // not safe. 247 for (const BasicBlock *BB : Visited) { 248 if (BB == StartBB) 249 continue; 250 for (const BasicBlock *Succ : successors(BB)) 251 if (Succ != StartBB && !Visited.count(Succ)) 252 return false; 253 } 254 255 return true; 256 } 257 258 llvm::Instruction *llvm::objcarc::findSingleDependency(DependenceKind Flavor, 259 const Value *Arg, 260 BasicBlock *StartBB, 261 Instruction *StartInst, 262 ProvenanceAnalysis &PA) { 263 SmallPtrSet<Instruction *, 4> DependingInsts; 264 265 if (!findDependencies(Flavor, Arg, StartBB, StartInst, DependingInsts, PA) || 266 DependingInsts.size() != 1) 267 return nullptr; 268 return *DependingInsts.begin(); 269 } 270