267 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8/// \file9///10/// This file defines special dependency analysis routines used in Objective C11/// ARC Optimizations.12///13/// WARNING: This file knows about certain library functions. It recognizes them14/// by name, and hardwires knowledge of their semantics.15///16/// WARNING: This file knows about how certain Objective-C library functions are17/// used. Naive LLVM IR transformations which would otherwise be18/// 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 28using namespace llvm;29using namespace llvm::objcarc;30 31#define DEBUG_TYPE "objc-arc-dependency"32 33/// Test whether the given instruction can result in a reference count34/// modification (positive or negative) for the pointer's object.35bool 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 MemoryEffects ME = PA.getAA()->getMemoryEffects(Call);52 if (ME.onlyReadsMemory())53 return false;54 if (ME.onlyAccessesArgPointees()) {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 66bool 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 a79/// way that requires the reference count to be positive.80bool llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr,81 ProvenanceAnalysis &PA, ARCInstKind Class) {82 // ARCInstKind::Call operations (as opposed to83 // 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 are88 // 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 values92 // 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, just103 // the store address.104 const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand());105 // If we can't tell what the underlying object was, assume there is a106 // 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 only120/// tests dependencies relevant for removing pairs of calls.121bool122llvm::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 different173 // 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 interrupts193 // 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 and203/// non-local dependencies on Arg.204///205/// TODO: Cache results?206static 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 if (pred_empty(LocalStartBB))224 // Return if we've reached the function entry.225 return false;226 // Add the predecessors to the worklist.227 for (BasicBlock *PredBB : predecessors(LocalStartBB))228 if (Visited.insert(PredBB).second)229 Worklist.push_back(std::make_pair(PredBB, PredBB->end()));230 break;231 }232 233 Instruction *Inst = &*--LocalStartPos;234 if (Depends(Flavor, Inst, Arg, PA)) {235 DependingInsts.insert(Inst);236 break;237 }238 }239 } while (!Worklist.empty());240 241 // Determine whether the original StartBB post-dominates all of the blocks we242 // visited. If not, insert a sentinel indicating that most optimizations are243 // not safe.244 for (const BasicBlock *BB : Visited) {245 if (BB == StartBB)246 continue;247 for (const BasicBlock *Succ : successors(BB))248 if (Succ != StartBB && !Visited.count(Succ))249 return false;250 }251 252 return true;253}254 255llvm::Instruction *llvm::objcarc::findSingleDependency(DependenceKind Flavor,256 const Value *Arg,257 BasicBlock *StartBB,258 Instruction *StartInst,259 ProvenanceAnalysis &PA) {260 SmallPtrSet<Instruction *, 4> DependingInsts;261 262 if (!findDependencies(Flavor, Arg, StartBB, StartInst, DependingInsts, PA) ||263 DependingInsts.size() != 1)264 return nullptr;265 return *DependingInsts.begin();266}267