2687 lines · cpp
1//===- ObjCARCOpts.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/// This file defines ObjC ARC optimizations. ARC stands for Automatic11/// Reference Counting and is a system for managing reference counts for objects12/// in Objective C.13///14/// The optimizations performed include elimination of redundant, partially15/// redundant, and inconsequential reference count operations, elimination of16/// redundant weak pointer operations, and numerous minor simplifications.17///18/// WARNING: This file knows about certain library functions. It recognizes them19/// by name, and hardwires knowledge of their semantics.20///21/// WARNING: This file knows about how certain Objective-C library functions are22/// used. Naive LLVM IR transformations which would otherwise be23/// behavior-preserving may break these assumptions.24//25//===----------------------------------------------------------------------===//26 27#include "ARCRuntimeEntryPoints.h"28#include "BlotMapVector.h"29#include "DependencyAnalysis.h"30#include "ObjCARC.h"31#include "ProvenanceAnalysis.h"32#include "PtrState.h"33#include "llvm/ADT/DenseMap.h"34#include "llvm/ADT/STLExtras.h"35#include "llvm/ADT/SmallPtrSet.h"36#include "llvm/ADT/SmallVector.h"37#include "llvm/ADT/Statistic.h"38#include "llvm/Analysis/AliasAnalysis.h"39#include "llvm/Analysis/ObjCARCAnalysisUtils.h"40#include "llvm/Analysis/ObjCARCInstKind.h"41#include "llvm/Analysis/ObjCARCUtil.h"42#include "llvm/Analysis/OptimizationRemarkEmitter.h"43#include "llvm/IR/BasicBlock.h"44#include "llvm/IR/CFG.h"45#include "llvm/IR/Constant.h"46#include "llvm/IR/Constants.h"47#include "llvm/IR/DerivedTypes.h"48#include "llvm/IR/EHPersonalities.h"49#include "llvm/IR/Function.h"50#include "llvm/IR/GlobalVariable.h"51#include "llvm/IR/InstIterator.h"52#include "llvm/IR/InstrTypes.h"53#include "llvm/IR/Instruction.h"54#include "llvm/IR/Instructions.h"55#include "llvm/IR/LLVMContext.h"56#include "llvm/IR/Metadata.h"57#include "llvm/IR/Type.h"58#include "llvm/IR/User.h"59#include "llvm/IR/Value.h"60#include "llvm/Support/Casting.h"61#include "llvm/Support/CommandLine.h"62#include "llvm/Support/Compiler.h"63#include "llvm/Support/Debug.h"64#include "llvm/Support/ErrorHandling.h"65#include "llvm/Support/raw_ostream.h"66#include "llvm/Transforms/ObjCARC.h"67#include <cassert>68#include <iterator>69#include <utility>70 71using namespace llvm;72using namespace llvm::objcarc;73 74#define DEBUG_TYPE "objc-arc-opts"75 76static cl::opt<unsigned> MaxPtrStates("arc-opt-max-ptr-states",77 cl::Hidden,78 cl::desc("Maximum number of ptr states the optimizer keeps track of"),79 cl::init(4095));80 81/// \defgroup ARCUtilities Utility declarations/definitions specific to ARC.82/// @{83 84/// This is similar to GetRCIdentityRoot but it stops as soon85/// as it finds a value with multiple uses.86static const Value *FindSingleUseIdentifiedObject(const Value *Arg) {87 // ConstantData (like ConstantPointerNull and UndefValue) is used across88 // modules. It's never a single-use value.89 if (isa<ConstantData>(Arg))90 return nullptr;91 92 if (Arg->hasOneUse()) {93 if (const BitCastInst *BC = dyn_cast<BitCastInst>(Arg))94 return FindSingleUseIdentifiedObject(BC->getOperand(0));95 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Arg))96 if (GEP->hasAllZeroIndices())97 return FindSingleUseIdentifiedObject(GEP->getPointerOperand());98 if (IsForwarding(GetBasicARCInstKind(Arg)))99 return FindSingleUseIdentifiedObject(100 cast<CallInst>(Arg)->getArgOperand(0));101 if (!IsObjCIdentifiedObject(Arg))102 return nullptr;103 return Arg;104 }105 106 // If we found an identifiable object but it has multiple uses, but they are107 // trivial uses, we can still consider this to be a single-use value.108 if (IsObjCIdentifiedObject(Arg)) {109 for (const User *U : Arg->users())110 if (!U->use_empty() || GetRCIdentityRoot(U) != Arg)111 return nullptr;112 113 return Arg;114 }115 116 return nullptr;117}118 119/// @}120///121/// \defgroup ARCOpt ARC Optimization.122/// @{123 124// TODO: On code like this:125//126// objc_retain(%x)127// stuff_that_cannot_release()128// objc_autorelease(%x)129// stuff_that_cannot_release()130// objc_retain(%x)131// stuff_that_cannot_release()132// objc_autorelease(%x)133//134// The second retain and autorelease can be deleted.135 136// TODO: Autorelease calls followed by objc_autoreleasePoolPop calls (perhaps in137// ObjC++ code after inlining) can be turned into plain release calls.138 139// TODO: Critical-edge splitting. If the optimial insertion point is140// a critical edge, the current algorithm has to fail, because it doesn't141// know how to split edges. It should be possible to make the optimizer142// think in terms of edges, rather than blocks, and then split critical143// edges on demand.144 145// TODO: OptimizeSequences could generalized to be Interprocedural.146 147// TODO: Recognize that a bunch of other objc runtime calls have148// non-escaping arguments and non-releasing arguments, and may be149// non-autoreleasing.150 151// TODO: Sink autorelease calls as far as possible. Unfortunately we152// usually can't sink them past other calls, which would be the main153// case where it would be useful.154 155// TODO: The pointer returned from objc_loadWeakRetained is retained.156 157// TODO: Delete release+retain pairs (rare).158 159STATISTIC(NumNoops, "Number of no-op objc calls eliminated");160STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated");161STATISTIC(NumAutoreleases,"Number of autoreleases converted to releases");162STATISTIC(NumRets, "Number of return value forwarding "163 "retain+autoreleases eliminated");164STATISTIC(NumRRs, "Number of retain+release paths eliminated");165STATISTIC(NumPeeps, "Number of calls peephole-optimized");166#ifndef NDEBUG167STATISTIC(NumRetainsBeforeOpt,168 "Number of retains before optimization");169STATISTIC(NumReleasesBeforeOpt,170 "Number of releases before optimization");171STATISTIC(NumRetainsAfterOpt,172 "Number of retains after optimization");173STATISTIC(NumReleasesAfterOpt,174 "Number of releases after optimization");175#endif176 177namespace {178 179 /// Per-BasicBlock state.180 class BBState {181 /// The number of unique control paths from the entry which can reach this182 /// block.183 unsigned TopDownPathCount = 0;184 185 /// The number of unique control paths to exits from this block.186 unsigned BottomUpPathCount = 0;187 188 /// The top-down traversal uses this to record information known about a189 /// pointer at the bottom of each block.190 BlotMapVector<const Value *, TopDownPtrState> PerPtrTopDown;191 192 /// The bottom-up traversal uses this to record information known about a193 /// pointer at the top of each block.194 BlotMapVector<const Value *, BottomUpPtrState> PerPtrBottomUp;195 196 /// Effective predecessors of the current block ignoring ignorable edges and197 /// ignored backedges.198 SmallVector<BasicBlock *, 2> Preds;199 200 /// Effective successors of the current block ignoring ignorable edges and201 /// ignored backedges.202 SmallVector<BasicBlock *, 2> Succs;203 204 public:205 static const unsigned OverflowOccurredValue;206 207 BBState() = default;208 209 using top_down_ptr_iterator = decltype(PerPtrTopDown)::iterator;210 using const_top_down_ptr_iterator = decltype(PerPtrTopDown)::const_iterator;211 212 top_down_ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); }213 top_down_ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); }214 const_top_down_ptr_iterator top_down_ptr_begin() const {215 return PerPtrTopDown.begin();216 }217 const_top_down_ptr_iterator top_down_ptr_end() const {218 return PerPtrTopDown.end();219 }220 bool hasTopDownPtrs() const {221 return !PerPtrTopDown.empty();222 }223 224 unsigned top_down_ptr_list_size() const {225 return std::distance(top_down_ptr_begin(), top_down_ptr_end());226 }227 228 using bottom_up_ptr_iterator = decltype(PerPtrBottomUp)::iterator;229 using const_bottom_up_ptr_iterator =230 decltype(PerPtrBottomUp)::const_iterator;231 232 bottom_up_ptr_iterator bottom_up_ptr_begin() {233 return PerPtrBottomUp.begin();234 }235 bottom_up_ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); }236 const_bottom_up_ptr_iterator bottom_up_ptr_begin() const {237 return PerPtrBottomUp.begin();238 }239 const_bottom_up_ptr_iterator bottom_up_ptr_end() const {240 return PerPtrBottomUp.end();241 }242 bool hasBottomUpPtrs() const {243 return !PerPtrBottomUp.empty();244 }245 246 unsigned bottom_up_ptr_list_size() const {247 return std::distance(bottom_up_ptr_begin(), bottom_up_ptr_end());248 }249 250 /// Mark this block as being an entry block, which has one path from the251 /// entry by definition.252 void SetAsEntry() { TopDownPathCount = 1; }253 254 /// Mark this block as being an exit block, which has one path to an exit by255 /// definition.256 void SetAsExit() { BottomUpPathCount = 1; }257 258 /// Attempt to find the PtrState object describing the top down state for259 /// pointer Arg. Return a new initialized PtrState describing the top down260 /// state for Arg if we do not find one.261 TopDownPtrState &getPtrTopDownState(const Value *Arg) {262 return PerPtrTopDown[Arg];263 }264 265 /// Attempt to find the PtrState object describing the bottom up state for266 /// pointer Arg. Return a new initialized PtrState describing the bottom up267 /// state for Arg if we do not find one.268 BottomUpPtrState &getPtrBottomUpState(const Value *Arg) {269 return PerPtrBottomUp[Arg];270 }271 272 /// Attempt to find the PtrState object describing the bottom up state for273 /// pointer Arg.274 bottom_up_ptr_iterator findPtrBottomUpState(const Value *Arg) {275 return PerPtrBottomUp.find(Arg);276 }277 278 void clearBottomUpPointers() {279 PerPtrBottomUp.clear();280 }281 282 void clearTopDownPointers() {283 PerPtrTopDown.clear();284 }285 286 void InitFromPred(const BBState &Other);287 void InitFromSucc(const BBState &Other);288 void MergePred(const BBState &Other);289 void MergeSucc(const BBState &Other);290 291 /// Compute the number of possible unique paths from an entry to an exit292 /// which pass through this block. This is only valid after both the293 /// top-down and bottom-up traversals are complete.294 ///295 /// Returns true if overflow occurred. Returns false if overflow did not296 /// occur.297 bool GetAllPathCountWithOverflow(unsigned &PathCount) const {298 if (TopDownPathCount == OverflowOccurredValue ||299 BottomUpPathCount == OverflowOccurredValue)300 return true;301 unsigned long long Product =302 (unsigned long long)TopDownPathCount*BottomUpPathCount;303 // Overflow occurred if any of the upper bits of Product are set or if all304 // the lower bits of Product are all set.305 return (Product >> 32) ||306 ((PathCount = Product) == OverflowOccurredValue);307 }308 309 // Specialized CFG utilities.310 using edge_iterator = SmallVectorImpl<BasicBlock *>::const_iterator;311 312 edge_iterator pred_begin() const { return Preds.begin(); }313 edge_iterator pred_end() const { return Preds.end(); }314 edge_iterator succ_begin() const { return Succs.begin(); }315 edge_iterator succ_end() const { return Succs.end(); }316 317 void addSucc(BasicBlock *Succ) { Succs.push_back(Succ); }318 void addPred(BasicBlock *Pred) { Preds.push_back(Pred); }319 320 bool isExit() const { return Succs.empty(); }321 };322 323} // end anonymous namespace324 325const unsigned BBState::OverflowOccurredValue = 0xffffffff;326 327namespace llvm {328 329[[maybe_unused]] raw_ostream &operator<<(raw_ostream &OS, BBState &BBState);330 331} // end namespace llvm332 333void BBState::InitFromPred(const BBState &Other) {334 PerPtrTopDown = Other.PerPtrTopDown;335 TopDownPathCount = Other.TopDownPathCount;336}337 338void BBState::InitFromSucc(const BBState &Other) {339 PerPtrBottomUp = Other.PerPtrBottomUp;340 BottomUpPathCount = Other.BottomUpPathCount;341}342 343/// The top-down traversal uses this to merge information about predecessors to344/// form the initial state for a new block.345void BBState::MergePred(const BBState &Other) {346 if (TopDownPathCount == OverflowOccurredValue)347 return;348 349 // Other.TopDownPathCount can be 0, in which case it is either dead or a350 // loop backedge. Loop backedges are special.351 TopDownPathCount += Other.TopDownPathCount;352 353 // In order to be consistent, we clear the top down pointers when by adding354 // TopDownPathCount becomes OverflowOccurredValue even though "true" overflow355 // has not occurred.356 if (TopDownPathCount == OverflowOccurredValue) {357 clearTopDownPointers();358 return;359 }360 361 // Check for overflow. If we have overflow, fall back to conservative362 // behavior.363 if (TopDownPathCount < Other.TopDownPathCount) {364 TopDownPathCount = OverflowOccurredValue;365 clearTopDownPointers();366 return;367 }368 369 // For each entry in the other set, if our set has an entry with the same key,370 // merge the entries. Otherwise, copy the entry and merge it with an empty371 // entry.372 for (auto MI = Other.top_down_ptr_begin(), ME = Other.top_down_ptr_end();373 MI != ME; ++MI) {374 auto Pair = PerPtrTopDown.insert(*MI);375 Pair.first->second.Merge(Pair.second ? TopDownPtrState() : MI->second,376 /*TopDown=*/true);377 }378 379 // For each entry in our set, if the other set doesn't have an entry with the380 // same key, force it to merge with an empty entry.381 for (auto MI = top_down_ptr_begin(), ME = top_down_ptr_end(); MI != ME; ++MI)382 if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end())383 MI->second.Merge(TopDownPtrState(), /*TopDown=*/true);384}385 386/// The bottom-up traversal uses this to merge information about successors to387/// form the initial state for a new block.388void BBState::MergeSucc(const BBState &Other) {389 if (BottomUpPathCount == OverflowOccurredValue)390 return;391 392 // Other.BottomUpPathCount can be 0, in which case it is either dead or a393 // loop backedge. Loop backedges are special.394 BottomUpPathCount += Other.BottomUpPathCount;395 396 // In order to be consistent, we clear the top down pointers when by adding397 // BottomUpPathCount becomes OverflowOccurredValue even though "true" overflow398 // has not occurred.399 if (BottomUpPathCount == OverflowOccurredValue) {400 clearBottomUpPointers();401 return;402 }403 404 // Check for overflow. If we have overflow, fall back to conservative405 // behavior.406 if (BottomUpPathCount < Other.BottomUpPathCount) {407 BottomUpPathCount = OverflowOccurredValue;408 clearBottomUpPointers();409 return;410 }411 412 // For each entry in the other set, if our set has an entry with the413 // same key, merge the entries. Otherwise, copy the entry and merge414 // it with an empty entry.415 for (auto MI = Other.bottom_up_ptr_begin(), ME = Other.bottom_up_ptr_end();416 MI != ME; ++MI) {417 auto Pair = PerPtrBottomUp.insert(*MI);418 Pair.first->second.Merge(Pair.second ? BottomUpPtrState() : MI->second,419 /*TopDown=*/false);420 }421 422 // For each entry in our set, if the other set doesn't have an entry423 // with the same key, force it to merge with an empty entry.424 for (auto MI = bottom_up_ptr_begin(), ME = bottom_up_ptr_end(); MI != ME;425 ++MI)426 if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end())427 MI->second.Merge(BottomUpPtrState(), /*TopDown=*/false);428}429 430raw_ostream &llvm::operator<<(raw_ostream &OS, BBState &BBInfo) {431 // Dump the pointers we are tracking.432 OS << " TopDown State:\n";433 if (!BBInfo.hasTopDownPtrs()) {434 LLVM_DEBUG(dbgs() << " NONE!\n");435 } else {436 for (auto I = BBInfo.top_down_ptr_begin(), E = BBInfo.top_down_ptr_end();437 I != E; ++I) {438 const PtrState &P = I->second;439 OS << " Ptr: " << *I->first440 << "\n KnownSafe: " << (P.IsKnownSafe()?"true":"false")441 << "\n ImpreciseRelease: "442 << (P.IsTrackingImpreciseReleases()?"true":"false") << "\n"443 << " HasCFGHazards: "444 << (P.IsCFGHazardAfflicted()?"true":"false") << "\n"445 << " KnownPositive: "446 << (P.HasKnownPositiveRefCount()?"true":"false") << "\n"447 << " Seq: "448 << P.GetSeq() << "\n";449 }450 }451 452 OS << " BottomUp State:\n";453 if (!BBInfo.hasBottomUpPtrs()) {454 LLVM_DEBUG(dbgs() << " NONE!\n");455 } else {456 for (auto I = BBInfo.bottom_up_ptr_begin(), E = BBInfo.bottom_up_ptr_end();457 I != E; ++I) {458 const PtrState &P = I->second;459 OS << " Ptr: " << *I->first460 << "\n KnownSafe: " << (P.IsKnownSafe()?"true":"false")461 << "\n ImpreciseRelease: "462 << (P.IsTrackingImpreciseReleases()?"true":"false") << "\n"463 << " HasCFGHazards: "464 << (P.IsCFGHazardAfflicted()?"true":"false") << "\n"465 << " KnownPositive: "466 << (P.HasKnownPositiveRefCount()?"true":"false") << "\n"467 << " Seq: "468 << P.GetSeq() << "\n";469 }470 }471 472 return OS;473}474 475namespace {476 477 /// The main ARC optimization pass.478class ObjCARCOpt {479 bool Changed = false;480 bool CFGChanged = false;481 ProvenanceAnalysis PA;482 483 /// A cache of references to runtime entry point constants.484 ARCRuntimeEntryPoints EP;485 486 /// A cache of MDKinds that can be passed into other functions to propagate487 /// MDKind identifiers.488 ARCMDKindCache MDKindCache;489 490 BundledRetainClaimRVs *BundledInsts = nullptr;491 492 /// A flag indicating whether the optimization that removes or moves493 /// retain/release pairs should be performed.494 bool DisableRetainReleasePairing = false;495 496 /// Flags which determine whether each of the interesting runtime functions497 /// is in fact used in the current function.498 unsigned UsedInThisFunction;499 500 DenseMap<BasicBlock *, ColorVector> BlockEHColors;501 502 bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV);503 void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV,504 ARCInstKind &Class);505 void OptimizeIndividualCalls(Function &F);506 507 /// Optimize an individual call, optionally passing the508 /// GetArgRCIdentityRoot if it has already been computed.509 void OptimizeIndividualCallImpl(Function &F, Instruction *Inst,510 ARCInstKind Class, const Value *Arg);511 512 /// Try to optimize an AutoreleaseRV with a RetainRV or UnsafeClaimRV. If the513 /// optimization occurs, returns true to indicate that the caller should514 /// assume the instructions are dead.515 bool OptimizeInlinedAutoreleaseRVCall(Function &F, Instruction *Inst,516 const Value *&Arg, ARCInstKind Class,517 Instruction *AutoreleaseRV,518 const Value *&AutoreleaseRVArg);519 520 void CheckForCFGHazards(const BasicBlock *BB,521 DenseMap<const BasicBlock *, BBState> &BBStates,522 BBState &MyStates) const;523 bool VisitInstructionBottomUp(Instruction *Inst, BasicBlock *BB,524 BlotMapVector<Value *, RRInfo> &Retains,525 BBState &MyStates);526 bool VisitBottomUp(BasicBlock *BB,527 DenseMap<const BasicBlock *, BBState> &BBStates,528 BlotMapVector<Value *, RRInfo> &Retains);529 bool VisitInstructionTopDown(530 Instruction *Inst, DenseMap<Value *, RRInfo> &Releases, BBState &MyStates,531 const DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>532 &ReleaseInsertPtToRCIdentityRoots);533 bool VisitTopDown(534 BasicBlock *BB, DenseMap<const BasicBlock *, BBState> &BBStates,535 DenseMap<Value *, RRInfo> &Releases,536 const DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>537 &ReleaseInsertPtToRCIdentityRoots);538 bool Visit(Function &F, DenseMap<const BasicBlock *, BBState> &BBStates,539 BlotMapVector<Value *, RRInfo> &Retains,540 DenseMap<Value *, RRInfo> &Releases);541 542 void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove,543 BlotMapVector<Value *, RRInfo> &Retains,544 DenseMap<Value *, RRInfo> &Releases,545 SmallVectorImpl<Instruction *> &DeadInsts, Module *M);546 547 bool PairUpRetainsAndReleases(DenseMap<const BasicBlock *, BBState> &BBStates,548 BlotMapVector<Value *, RRInfo> &Retains,549 DenseMap<Value *, RRInfo> &Releases, Module *M,550 Instruction *Retain,551 SmallVectorImpl<Instruction *> &DeadInsts,552 RRInfo &RetainsToMove, RRInfo &ReleasesToMove,553 Value *Arg, bool KnownSafe,554 bool &AnyPairsCompletelyEliminated);555 556 bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates,557 BlotMapVector<Value *, RRInfo> &Retains,558 DenseMap<Value *, RRInfo> &Releases, Module *M);559 560 void OptimizeWeakCalls(Function &F);561 562 bool OptimizeSequences(Function &F);563 564 void OptimizeReturns(Function &F);565 566 void OptimizeAutoreleasePools(Function &F);567 568 template <typename PredicateT>569 static void cloneOpBundlesIf(CallBase *CI,570 SmallVectorImpl<OperandBundleDef> &OpBundles,571 PredicateT Predicate) {572 for (unsigned I = 0, E = CI->getNumOperandBundles(); I != E; ++I) {573 OperandBundleUse B = CI->getOperandBundleAt(I);574 if (Predicate(B))575 OpBundles.emplace_back(B);576 }577 }578 579 void addOpBundleForFunclet(BasicBlock *BB,580 SmallVectorImpl<OperandBundleDef> &OpBundles) {581 if (!BlockEHColors.empty()) {582 const ColorVector &CV = BlockEHColors.find(BB)->second;583 assert(CV.size() > 0 && "Uncolored block");584 for (BasicBlock *EHPadBB : CV)585 if (auto *EHPad =586 dyn_cast<FuncletPadInst>(EHPadBB->getFirstNonPHIIt())) {587 OpBundles.emplace_back("funclet", EHPad);588 return;589 }590 }591 }592 593#ifndef NDEBUG594 void GatherStatistics(Function &F, bool AfterOptimization = false);595#endif596 597 public:598 void init(Function &F);599 bool run(Function &F, AAResults &AA);600 bool hasCFGChanged() const { return CFGChanged; }601};602} // end anonymous namespace603 604/// Turn objc_retainAutoreleasedReturnValue into objc_retain if the operand is605/// not a return value.606bool607ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) {608 // Check for the argument being from an immediately preceding call or invoke.609 const Value *Arg = GetArgRCIdentityRoot(RetainRV);610 if (const Instruction *Call = dyn_cast<CallBase>(Arg)) {611 if (Call->getParent() == RetainRV->getParent()) {612 BasicBlock::const_iterator I(Call);613 ++I;614 while (IsNoopInstruction(&*I))615 ++I;616 if (&*I == RetainRV)617 return false;618 } else if (const InvokeInst *II = dyn_cast<InvokeInst>(Call)) {619 BasicBlock *RetainRVParent = RetainRV->getParent();620 if (II->getNormalDest() == RetainRVParent) {621 BasicBlock::const_iterator I = RetainRVParent->begin();622 while (IsNoopInstruction(&*I))623 ++I;624 if (&*I == RetainRV)625 return false;626 }627 }628 }629 630 assert(!BundledInsts->contains(RetainRV) &&631 "a bundled retainRV's argument should be a call");632 633 // Turn it to a plain objc_retain.634 Changed = true;635 ++NumPeeps;636 637 LLVM_DEBUG(dbgs() << "Transforming objc_retainAutoreleasedReturnValue => "638 "objc_retain since the operand is not a return value.\n"639 "Old = "640 << *RetainRV << "\n");641 642 Function *NewDecl = EP.get(ARCRuntimeEntryPointKind::Retain);643 cast<CallInst>(RetainRV)->setCalledFunction(NewDecl);644 645 LLVM_DEBUG(dbgs() << "New = " << *RetainRV << "\n");646 647 return false;648}649 650bool ObjCARCOpt::OptimizeInlinedAutoreleaseRVCall(651 Function &F, Instruction *Inst, const Value *&Arg, ARCInstKind Class,652 Instruction *AutoreleaseRV, const Value *&AutoreleaseRVArg) {653 if (BundledInsts->contains(Inst))654 return false;655 656 // Must be in the same basic block.657 assert(Inst->getParent() == AutoreleaseRV->getParent());658 659 // Must operate on the same root.660 Arg = GetArgRCIdentityRoot(Inst);661 AutoreleaseRVArg = GetArgRCIdentityRoot(AutoreleaseRV);662 if (Arg != AutoreleaseRVArg) {663 // If there isn't an exact match, check if we have equivalent PHIs.664 const PHINode *PN = dyn_cast<PHINode>(Arg);665 if (!PN)666 return false;667 668 SmallVector<const Value *, 4> ArgUsers;669 getEquivalentPHIs(*PN, ArgUsers);670 if (!llvm::is_contained(ArgUsers, AutoreleaseRVArg))671 return false;672 }673 674 // Okay, this is a match. Merge them.675 ++NumPeeps;676 LLVM_DEBUG(dbgs() << "Found inlined objc_autoreleaseReturnValue '"677 << *AutoreleaseRV << "' paired with '" << *Inst << "'\n");678 679 // Delete the RV pair, starting with the AutoreleaseRV.680 AutoreleaseRV->replaceAllUsesWith(681 cast<CallInst>(AutoreleaseRV)->getArgOperand(0));682 Changed = true;683 EraseInstruction(AutoreleaseRV);684 if (Class == ARCInstKind::RetainRV) {685 // AutoreleaseRV and RetainRV cancel out. Delete the RetainRV.686 Inst->replaceAllUsesWith(cast<CallInst>(Inst)->getArgOperand(0));687 EraseInstruction(Inst);688 return true;689 }690 691 // UnsafeClaimRV is a frontend peephole for RetainRV + Release. Since the692 // AutoreleaseRV and RetainRV cancel out, replace UnsafeClaimRV with Release.693 assert(Class == ARCInstKind::UnsafeClaimRV);694 Value *CallArg = cast<CallInst>(Inst)->getArgOperand(0);695 CallInst *Release =696 CallInst::Create(EP.get(ARCRuntimeEntryPointKind::Release), CallArg, "",697 Inst->getIterator());698 assert(IsAlwaysTail(ARCInstKind::UnsafeClaimRV) &&699 "Expected UnsafeClaimRV to be safe to tail call");700 Release->setTailCall();701 Inst->replaceAllUsesWith(CallArg);702 EraseInstruction(Inst);703 704 // Run the normal optimizations on Release.705 OptimizeIndividualCallImpl(F, Release, ARCInstKind::Release, Arg);706 return true;707}708 709/// Turn objc_autoreleaseReturnValue into objc_autorelease if the result is not710/// used as a return value.711void ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F,712 Instruction *AutoreleaseRV,713 ARCInstKind &Class) {714 // Check for a return of the pointer value.715 const Value *Ptr = GetArgRCIdentityRoot(AutoreleaseRV);716 717 // If the argument is ConstantPointerNull or UndefValue, its other users718 // aren't actually interesting to look at.719 if (isa<ConstantData>(Ptr))720 return;721 722 SmallVector<const Value *, 2> Users;723 Users.push_back(Ptr);724 725 // Add PHIs that are equivalent to Ptr to Users.726 if (const PHINode *PN = dyn_cast<PHINode>(Ptr))727 getEquivalentPHIs(*PN, Users);728 729 do {730 Ptr = Users.pop_back_val();731 for (const User *U : Ptr->users()) {732 if (isa<ReturnInst>(U) || GetBasicARCInstKind(U) == ARCInstKind::RetainRV)733 return;734 if (isa<BitCastInst>(U))735 Users.push_back(U);736 }737 } while (!Users.empty());738 739 Changed = true;740 ++NumPeeps;741 742 LLVM_DEBUG(743 dbgs() << "Transforming objc_autoreleaseReturnValue => "744 "objc_autorelease since its operand is not used as a return "745 "value.\n"746 "Old = "747 << *AutoreleaseRV << "\n");748 749 CallInst *AutoreleaseRVCI = cast<CallInst>(AutoreleaseRV);750 Function *NewDecl = EP.get(ARCRuntimeEntryPointKind::Autorelease);751 AutoreleaseRVCI->setCalledFunction(NewDecl);752 AutoreleaseRVCI->setTailCall(false); // Never tail call objc_autorelease.753 Class = ARCInstKind::Autorelease;754 755 LLVM_DEBUG(dbgs() << "New: " << *AutoreleaseRV << "\n");756}757 758/// Visit each call, one at a time, and make simplifications without doing any759/// additional analysis.760void ObjCARCOpt::OptimizeIndividualCalls(Function &F) {761 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeIndividualCalls ==\n");762 // Reset all the flags in preparation for recomputing them.763 UsedInThisFunction = 0;764 765 // Store any delayed AutoreleaseRV intrinsics, so they can be easily paired766 // with RetainRV and UnsafeClaimRV.767 Instruction *DelayedAutoreleaseRV = nullptr;768 const Value *DelayedAutoreleaseRVArg = nullptr;769 auto setDelayedAutoreleaseRV = [&](Instruction *AutoreleaseRV) {770 assert(!DelayedAutoreleaseRV || !AutoreleaseRV);771 DelayedAutoreleaseRV = AutoreleaseRV;772 DelayedAutoreleaseRVArg = nullptr;773 };774 auto optimizeDelayedAutoreleaseRV = [&]() {775 if (!DelayedAutoreleaseRV)776 return;777 OptimizeIndividualCallImpl(F, DelayedAutoreleaseRV,778 ARCInstKind::AutoreleaseRV,779 DelayedAutoreleaseRVArg);780 setDelayedAutoreleaseRV(nullptr);781 };782 auto shouldDelayAutoreleaseRV = [&](Instruction *NonARCInst) {783 // Nothing to delay, but we may as well skip the logic below.784 if (!DelayedAutoreleaseRV)785 return true;786 787 // If we hit the end of the basic block we're not going to find an RV-pair.788 // Stop delaying.789 if (NonARCInst->isTerminator())790 return false;791 792 // Given the frontend rules for emitting AutoreleaseRV, RetainRV, and793 // UnsafeClaimRV, it's probably safe to skip over even opaque function calls794 // here since OptimizeInlinedAutoreleaseRVCall will confirm that they795 // have the same RCIdentityRoot. However, what really matters is796 // skipping instructions or intrinsics that the inliner could leave behind;797 // be conservative for now and don't skip over opaque calls, which could798 // potentially include other ARC calls.799 auto *CB = dyn_cast<CallBase>(NonARCInst);800 if (!CB)801 return true;802 return CB->getIntrinsicID() != Intrinsic::not_intrinsic;803 };804 805 // Visit all objc_* calls in F.806 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {807 Instruction *Inst = &*I++;808 809 if (auto *CI = dyn_cast<CallInst>(Inst))810 if (objcarc::hasAttachedCallOpBundle(CI)) {811 BundledInsts->insertRVCall(I->getIterator(), CI);812 Changed = true;813 }814 815 ARCInstKind Class = GetBasicARCInstKind(Inst);816 817 // Skip this loop if this instruction isn't itself an ARC intrinsic.818 const Value *Arg = nullptr;819 switch (Class) {820 default:821 optimizeDelayedAutoreleaseRV();822 break;823 case ARCInstKind::CallOrUser:824 case ARCInstKind::User:825 case ARCInstKind::None:826 // This is a non-ARC instruction. If we're delaying an AutoreleaseRV,827 // check if it's safe to skip over it; if not, optimize the AutoreleaseRV828 // now.829 if (!shouldDelayAutoreleaseRV(Inst))830 optimizeDelayedAutoreleaseRV();831 continue;832 case ARCInstKind::AutoreleaseRV:833 optimizeDelayedAutoreleaseRV();834 setDelayedAutoreleaseRV(Inst);835 continue;836 case ARCInstKind::RetainRV:837 case ARCInstKind::UnsafeClaimRV:838 if (DelayedAutoreleaseRV) {839 // We have a potential RV pair. Check if they cancel out.840 if (OptimizeInlinedAutoreleaseRVCall(F, Inst, Arg, Class,841 DelayedAutoreleaseRV,842 DelayedAutoreleaseRVArg)) {843 setDelayedAutoreleaseRV(nullptr);844 continue;845 }846 optimizeDelayedAutoreleaseRV();847 }848 break;849 }850 851 OptimizeIndividualCallImpl(F, Inst, Class, Arg);852 }853 854 // Catch the final delayed AutoreleaseRV.855 optimizeDelayedAutoreleaseRV();856}857 858/// This function returns true if the value is inert. An ObjC ARC runtime call859/// taking an inert operand can be safely deleted.860static bool isInertARCValue(Value *V, SmallPtrSet<Value *, 1> &VisitedPhis) {861 V = V->stripPointerCasts();862 863 if (IsNullOrUndef(V))864 return true;865 866 // See if this is a global attribute annotated with an 'objc_arc_inert'.867 if (auto *GV = dyn_cast<GlobalVariable>(V))868 if (GV->hasAttribute("objc_arc_inert"))869 return true;870 871 if (auto PN = dyn_cast<PHINode>(V)) {872 // Ignore this phi if it has already been discovered.873 if (!VisitedPhis.insert(PN).second)874 return true;875 // Look through phis's operands.876 for (Value *Opnd : PN->incoming_values())877 if (!isInertARCValue(Opnd, VisitedPhis))878 return false;879 return true;880 }881 882 return false;883}884 885void ObjCARCOpt::OptimizeIndividualCallImpl(Function &F, Instruction *Inst,886 ARCInstKind Class,887 const Value *Arg) {888 LLVM_DEBUG(dbgs() << "Visiting: Class: " << Class << "; " << *Inst << "\n");889 890 // We can delete this call if it takes an inert value.891 SmallPtrSet<Value *, 1> VisitedPhis;892 893 if (BundledInsts->contains(Inst)) {894 UsedInThisFunction |= 1 << unsigned(Class);895 return;896 }897 898 if (IsNoopOnGlobal(Class))899 if (isInertARCValue(Inst->getOperand(0), VisitedPhis)) {900 if (!Inst->getType()->isVoidTy())901 Inst->replaceAllUsesWith(Inst->getOperand(0));902 Inst->eraseFromParent();903 Changed = true;904 return;905 }906 907 switch (Class) {908 default:909 break;910 911 // Delete no-op casts. These function calls have special semantics, but912 // the semantics are entirely implemented via lowering in the front-end,913 // so by the time they reach the optimizer, they are just no-op calls914 // which return their argument.915 //916 // There are gray areas here, as the ability to cast reference-counted917 // pointers to raw void* and back allows code to break ARC assumptions,918 // however these are currently considered to be unimportant.919 case ARCInstKind::NoopCast:920 Changed = true;921 ++NumNoops;922 LLVM_DEBUG(dbgs() << "Erasing no-op cast: " << *Inst << "\n");923 EraseInstruction(Inst);924 return;925 926 // If the pointer-to-weak-pointer is null, it's undefined behavior.927 case ARCInstKind::StoreWeak:928 case ARCInstKind::LoadWeak:929 case ARCInstKind::LoadWeakRetained:930 case ARCInstKind::InitWeak:931 case ARCInstKind::DestroyWeak: {932 CallInst *CI = cast<CallInst>(Inst);933 if (IsNullOrUndef(CI->getArgOperand(0))) {934 Changed = true;935 new StoreInst(ConstantInt::getTrue(CI->getContext()),936 PoisonValue::get(PointerType::getUnqual(CI->getContext())),937 CI->getIterator());938 Value *NewValue = PoisonValue::get(CI->getType());939 LLVM_DEBUG(940 dbgs() << "A null pointer-to-weak-pointer is undefined behavior."941 "\nOld = "942 << *CI << "\nNew = " << *NewValue << "\n");943 CI->replaceAllUsesWith(NewValue);944 CI->eraseFromParent();945 return;946 }947 break;948 }949 case ARCInstKind::CopyWeak:950 case ARCInstKind::MoveWeak: {951 CallInst *CI = cast<CallInst>(Inst);952 if (IsNullOrUndef(CI->getArgOperand(0)) ||953 IsNullOrUndef(CI->getArgOperand(1))) {954 Changed = true;955 new StoreInst(ConstantInt::getTrue(CI->getContext()),956 PoisonValue::get(PointerType::getUnqual(CI->getContext())),957 CI->getIterator());958 959 Value *NewValue = PoisonValue::get(CI->getType());960 LLVM_DEBUG(961 dbgs() << "A null pointer-to-weak-pointer is undefined behavior."962 "\nOld = "963 << *CI << "\nNew = " << *NewValue << "\n");964 965 CI->replaceAllUsesWith(NewValue);966 CI->eraseFromParent();967 return;968 }969 break;970 }971 case ARCInstKind::RetainRV:972 if (OptimizeRetainRVCall(F, Inst))973 return;974 break;975 case ARCInstKind::AutoreleaseRV:976 OptimizeAutoreleaseRVCall(F, Inst, Class);977 break;978 }979 980 // objc_autorelease(x) -> objc_release(x) if x is otherwise unused.981 if (IsAutorelease(Class) && Inst->use_empty()) {982 CallInst *Call = cast<CallInst>(Inst);983 const Value *Arg = Call->getArgOperand(0);984 Arg = FindSingleUseIdentifiedObject(Arg);985 if (Arg) {986 Changed = true;987 ++NumAutoreleases;988 989 // Create the declaration lazily.990 LLVMContext &C = Inst->getContext();991 992 Function *Decl = EP.get(ARCRuntimeEntryPointKind::Release);993 CallInst *NewCall = CallInst::Create(Decl, Call->getArgOperand(0), "",994 Call->getIterator());995 NewCall->setMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease),996 MDNode::get(C, {}));997 998 LLVM_DEBUG(dbgs() << "Replacing autorelease{,RV}(x) with objc_release(x) "999 "since x is otherwise unused.\nOld: "1000 << *Call << "\nNew: " << *NewCall << "\n");1001 1002 EraseInstruction(Call);1003 Inst = NewCall;1004 Class = ARCInstKind::Release;1005 }1006 }1007 1008 // For functions which can never be passed stack arguments, add1009 // a tail keyword.1010 if (IsAlwaysTail(Class) && !cast<CallInst>(Inst)->isNoTailCall()) {1011 Changed = true;1012 LLVM_DEBUG(1013 dbgs() << "Adding tail keyword to function since it can never be "1014 "passed stack args: "1015 << *Inst << "\n");1016 cast<CallInst>(Inst)->setTailCall();1017 }1018 1019 // Ensure that functions that can never have a "tail" keyword due to the1020 // semantics of ARC truly do not do so.1021 if (IsNeverTail(Class)) {1022 Changed = true;1023 LLVM_DEBUG(dbgs() << "Removing tail keyword from function: " << *Inst1024 << "\n");1025 cast<CallInst>(Inst)->setTailCall(false);1026 }1027 1028 // Set nounwind as needed.1029 if (IsNoThrow(Class)) {1030 Changed = true;1031 LLVM_DEBUG(dbgs() << "Found no throw class. Setting nounwind on: " << *Inst1032 << "\n");1033 cast<CallInst>(Inst)->setDoesNotThrow();1034 }1035 1036 // Note: This catches instructions unrelated to ARC.1037 if (!IsNoopOnNull(Class)) {1038 UsedInThisFunction |= 1 << unsigned(Class);1039 return;1040 }1041 1042 // If we haven't already looked up the root, look it up now.1043 if (!Arg)1044 Arg = GetArgRCIdentityRoot(Inst);1045 1046 // ARC calls with null are no-ops. Delete them.1047 if (IsNullOrUndef(Arg)) {1048 Changed = true;1049 ++NumNoops;1050 LLVM_DEBUG(dbgs() << "ARC calls with null are no-ops. Erasing: " << *Inst1051 << "\n");1052 EraseInstruction(Inst);1053 return;1054 }1055 1056 // Keep track of which of retain, release, autorelease, and retain_block1057 // are actually present in this function.1058 UsedInThisFunction |= 1 << unsigned(Class);1059 1060 // If Arg is a PHI, and one or more incoming values to the1061 // PHI are null, and the call is control-equivalent to the PHI, and there1062 // are no relevant side effects between the PHI and the call, and the call1063 // is not a release that doesn't have the clang.imprecise_release tag, the1064 // call could be pushed up to just those paths with non-null incoming1065 // values. For now, don't bother splitting critical edges for this.1066 if (Class == ARCInstKind::Release &&1067 !Inst->getMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease)))1068 return;1069 1070 SmallVector<std::pair<Instruction *, const Value *>, 4> Worklist;1071 Worklist.push_back(std::make_pair(Inst, Arg));1072 do {1073 std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val();1074 Inst = Pair.first;1075 Arg = Pair.second;1076 1077 const PHINode *PN = dyn_cast<PHINode>(Arg);1078 if (!PN)1079 continue;1080 1081 // Determine if the PHI has any null operands, or any incoming1082 // critical edges.1083 bool HasNull = false;1084 bool HasCriticalEdges = false;1085 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {1086 Value *Incoming = GetRCIdentityRoot(PN->getIncomingValue(i));1087 if (IsNullOrUndef(Incoming))1088 HasNull = true;1089 else if (PN->getIncomingBlock(i)->getTerminator()->getNumSuccessors() !=1090 1) {1091 HasCriticalEdges = true;1092 break;1093 }1094 }1095 // If we have null operands and no critical edges, optimize.1096 if (HasCriticalEdges)1097 continue;1098 if (!HasNull)1099 continue;1100 1101 Instruction *DepInst = nullptr;1102 1103 // Check that there is nothing that cares about the reference1104 // count between the call and the phi.1105 switch (Class) {1106 case ARCInstKind::Retain:1107 case ARCInstKind::RetainBlock:1108 // These can always be moved up.1109 break;1110 case ARCInstKind::Release:1111 // These can't be moved across things that care about the retain1112 // count.1113 DepInst = findSingleDependency(NeedsPositiveRetainCount, Arg,1114 Inst->getParent(), Inst, PA);1115 break;1116 case ARCInstKind::Autorelease:1117 // These can't be moved across autorelease pool scope boundaries.1118 DepInst = findSingleDependency(AutoreleasePoolBoundary, Arg,1119 Inst->getParent(), Inst, PA);1120 break;1121 case ARCInstKind::UnsafeClaimRV:1122 case ARCInstKind::RetainRV:1123 case ARCInstKind::AutoreleaseRV:1124 // Don't move these; the RV optimization depends on the autoreleaseRV1125 // being tail called, and the retainRV being immediately after a call1126 // (which might still happen if we get lucky with codegen layout, but1127 // it's not worth taking the chance).1128 continue;1129 default:1130 llvm_unreachable("Invalid dependence flavor");1131 }1132 1133 if (DepInst != PN)1134 continue;1135 1136 Changed = true;1137 ++NumPartialNoops;1138 // Clone the call into each predecessor that has a non-null value.1139 CallInst *CInst = cast<CallInst>(Inst);1140 Type *ParamTy = CInst->getArgOperand(0)->getType();1141 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {1142 Value *Incoming = GetRCIdentityRoot(PN->getIncomingValue(i));1143 if (IsNullOrUndef(Incoming))1144 continue;1145 Value *Op = PN->getIncomingValue(i);1146 BasicBlock::iterator InsertPos =1147 PN->getIncomingBlock(i)->back().getIterator();1148 SmallVector<OperandBundleDef, 1> OpBundles;1149 cloneOpBundlesIf(CInst, OpBundles, [](const OperandBundleUse &B) {1150 return B.getTagID() != LLVMContext::OB_funclet;1151 });1152 addOpBundleForFunclet(InsertPos->getParent(), OpBundles);1153 CallInst *Clone = CallInst::Create(CInst, OpBundles);1154 if (Op->getType() != ParamTy)1155 Op = new BitCastInst(Op, ParamTy, "", InsertPos);1156 Clone->setArgOperand(0, Op);1157 Clone->insertBefore(*InsertPos->getParent(), InsertPos);1158 1159 LLVM_DEBUG(dbgs() << "Cloning " << *CInst << "\n"1160 "And inserting clone at "1161 << *InsertPos << "\n");1162 Worklist.push_back(std::make_pair(Clone, Incoming));1163 }1164 // Erase the original call.1165 LLVM_DEBUG(dbgs() << "Erasing: " << *CInst << "\n");1166 EraseInstruction(CInst);1167 } while (!Worklist.empty());1168}1169 1170/// If we have a top down pointer in the S_Use state, make sure that there are1171/// no CFG hazards by checking the states of various bottom up pointers.1172static void CheckForUseCFGHazard(const Sequence SuccSSeq,1173 const bool SuccSRRIKnownSafe,1174 TopDownPtrState &S,1175 bool &SomeSuccHasSame,1176 bool &AllSuccsHaveSame,1177 bool &NotAllSeqEqualButKnownSafe,1178 bool &ShouldContinue) {1179 switch (SuccSSeq) {1180 case S_CanRelease: {1181 if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) {1182 S.ClearSequenceProgress();1183 break;1184 }1185 S.SetCFGHazardAfflicted(true);1186 ShouldContinue = true;1187 break;1188 }1189 case S_Use:1190 SomeSuccHasSame = true;1191 break;1192 case S_Stop:1193 case S_MovableRelease:1194 if (!S.IsKnownSafe() && !SuccSRRIKnownSafe)1195 AllSuccsHaveSame = false;1196 else1197 NotAllSeqEqualButKnownSafe = true;1198 break;1199 case S_Retain:1200 llvm_unreachable("bottom-up pointer in retain state!");1201 case S_None:1202 llvm_unreachable("This should have been handled earlier.");1203 }1204}1205 1206/// If we have a Top Down pointer in the S_CanRelease state, make sure that1207/// there are no CFG hazards by checking the states of various bottom up1208/// pointers.1209static void CheckForCanReleaseCFGHazard(const Sequence SuccSSeq,1210 const bool SuccSRRIKnownSafe,1211 TopDownPtrState &S,1212 bool &SomeSuccHasSame,1213 bool &AllSuccsHaveSame,1214 bool &NotAllSeqEqualButKnownSafe) {1215 switch (SuccSSeq) {1216 case S_CanRelease:1217 SomeSuccHasSame = true;1218 break;1219 case S_Stop:1220 case S_MovableRelease:1221 case S_Use:1222 if (!S.IsKnownSafe() && !SuccSRRIKnownSafe)1223 AllSuccsHaveSame = false;1224 else1225 NotAllSeqEqualButKnownSafe = true;1226 break;1227 case S_Retain:1228 llvm_unreachable("bottom-up pointer in retain state!");1229 case S_None:1230 llvm_unreachable("This should have been handled earlier.");1231 }1232}1233 1234/// Check for critical edges, loop boundaries, irreducible control flow, or1235/// other CFG structures where moving code across the edge would result in it1236/// being executed more.1237void1238ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB,1239 DenseMap<const BasicBlock *, BBState> &BBStates,1240 BBState &MyStates) const {1241 // If any top-down local-use or possible-dec has a succ which is earlier in1242 // the sequence, forget it.1243 for (auto I = MyStates.top_down_ptr_begin(), E = MyStates.top_down_ptr_end();1244 I != E; ++I) {1245 TopDownPtrState &S = I->second;1246 const Sequence Seq = I->second.GetSeq();1247 1248 // We only care about S_Retain, S_CanRelease, and S_Use.1249 if (Seq == S_None)1250 continue;1251 1252 // Make sure that if extra top down states are added in the future that this1253 // code is updated to handle it.1254 assert((Seq == S_Retain || Seq == S_CanRelease || Seq == S_Use) &&1255 "Unknown top down sequence state.");1256 1257 const Value *Arg = I->first;1258 bool SomeSuccHasSame = false;1259 bool AllSuccsHaveSame = true;1260 bool NotAllSeqEqualButKnownSafe = false;1261 1262 for (const BasicBlock *Succ : successors(BB)) {1263 // If VisitBottomUp has pointer information for this successor, take1264 // what we know about it.1265 const DenseMap<const BasicBlock *, BBState>::iterator BBI =1266 BBStates.find(Succ);1267 assert(BBI != BBStates.end());1268 const BottomUpPtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);1269 const Sequence SuccSSeq = SuccS.GetSeq();1270 1271 // If bottom up, the pointer is in an S_None state, clear the sequence1272 // progress since the sequence in the bottom up state finished1273 // suggesting a mismatch in between retains/releases. This is true for1274 // all three cases that we are handling here: S_Retain, S_Use, and1275 // S_CanRelease.1276 if (SuccSSeq == S_None) {1277 S.ClearSequenceProgress();1278 continue;1279 }1280 1281 // If we have S_Use or S_CanRelease, perform our check for cfg hazard1282 // checks.1283 const bool SuccSRRIKnownSafe = SuccS.IsKnownSafe();1284 1285 // *NOTE* We do not use Seq from above here since we are allowing for1286 // S.GetSeq() to change while we are visiting basic blocks.1287 switch(S.GetSeq()) {1288 case S_Use: {1289 bool ShouldContinue = false;1290 CheckForUseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S, SomeSuccHasSame,1291 AllSuccsHaveSame, NotAllSeqEqualButKnownSafe,1292 ShouldContinue);1293 if (ShouldContinue)1294 continue;1295 break;1296 }1297 case S_CanRelease:1298 CheckForCanReleaseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S,1299 SomeSuccHasSame, AllSuccsHaveSame,1300 NotAllSeqEqualButKnownSafe);1301 break;1302 case S_Retain:1303 case S_None:1304 case S_Stop:1305 case S_MovableRelease:1306 break;1307 }1308 }1309 1310 // If the state at the other end of any of the successor edges1311 // matches the current state, require all edges to match. This1312 // guards against loops in the middle of a sequence.1313 if (SomeSuccHasSame && !AllSuccsHaveSame) {1314 S.ClearSequenceProgress();1315 } else if (NotAllSeqEqualButKnownSafe) {1316 // If we would have cleared the state foregoing the fact that we are known1317 // safe, stop code motion. This is because whether or not it is safe to1318 // remove RR pairs via KnownSafe is an orthogonal concept to whether we1319 // are allowed to perform code motion.1320 S.SetCFGHazardAfflicted(true);1321 }1322 }1323}1324 1325bool ObjCARCOpt::VisitInstructionBottomUp(1326 Instruction *Inst, BasicBlock *BB, BlotMapVector<Value *, RRInfo> &Retains,1327 BBState &MyStates) {1328 bool NestingDetected = false;1329 ARCInstKind Class = GetARCInstKind(Inst);1330 const Value *Arg = nullptr;1331 1332 LLVM_DEBUG(dbgs() << " Class: " << Class << "\n");1333 1334 switch (Class) {1335 case ARCInstKind::Release: {1336 Arg = GetArgRCIdentityRoot(Inst);1337 1338 BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg);1339 NestingDetected |= S.InitBottomUp(MDKindCache, Inst);1340 break;1341 }1342 case ARCInstKind::RetainBlock:1343 // In OptimizeIndividualCalls, we have strength reduced all optimizable1344 // objc_retainBlocks to objc_retains. Thus at this point any1345 // objc_retainBlocks that we see are not optimizable.1346 break;1347 case ARCInstKind::Retain:1348 case ARCInstKind::RetainRV: {1349 Arg = GetArgRCIdentityRoot(Inst);1350 BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg);1351 if (S.MatchWithRetain()) {1352 // Don't do retain+release tracking for ARCInstKind::RetainRV, because1353 // it's better to let it remain as the first instruction after a call.1354 if (Class != ARCInstKind::RetainRV) {1355 LLVM_DEBUG(dbgs() << " Matching with: " << *Inst << "\n");1356 Retains[Inst] = S.GetRRInfo();1357 }1358 S.ClearSequenceProgress();1359 }1360 // A retain moving bottom up can be a use.1361 break;1362 }1363 case ARCInstKind::AutoreleasepoolPop:1364 // Conservatively, clear MyStates for all known pointers.1365 MyStates.clearBottomUpPointers();1366 return NestingDetected;1367 case ARCInstKind::AutoreleasepoolPush:1368 case ARCInstKind::None:1369 // These are irrelevant.1370 return NestingDetected;1371 default:1372 break;1373 }1374 1375 // Consider any other possible effects of this instruction on each1376 // pointer being tracked.1377 for (auto MI = MyStates.bottom_up_ptr_begin(),1378 ME = MyStates.bottom_up_ptr_end();1379 MI != ME; ++MI) {1380 const Value *Ptr = MI->first;1381 if (Ptr == Arg)1382 continue; // Handled above.1383 BottomUpPtrState &S = MI->second;1384 1385 if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class))1386 continue;1387 1388 S.HandlePotentialUse(BB, Inst, Ptr, PA, Class);1389 }1390 1391 return NestingDetected;1392}1393 1394bool ObjCARCOpt::VisitBottomUp(BasicBlock *BB,1395 DenseMap<const BasicBlock *, BBState> &BBStates,1396 BlotMapVector<Value *, RRInfo> &Retains) {1397 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::VisitBottomUp ==\n");1398 1399 bool NestingDetected = false;1400 BBState &MyStates = BBStates[BB];1401 1402 // Merge the states from each successor to compute the initial state1403 // for the current block.1404 BBState::edge_iterator SI(MyStates.succ_begin()),1405 SE(MyStates.succ_end());1406 if (SI != SE) {1407 const BasicBlock *Succ = *SI;1408 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ);1409 assert(I != BBStates.end());1410 MyStates.InitFromSucc(I->second);1411 ++SI;1412 for (; SI != SE; ++SI) {1413 Succ = *SI;1414 I = BBStates.find(Succ);1415 assert(I != BBStates.end());1416 MyStates.MergeSucc(I->second);1417 }1418 }1419 1420 LLVM_DEBUG(dbgs() << "Before:\n"1421 << BBStates[BB] << "\n"1422 << "Performing Dataflow:\n");1423 1424 // Visit all the instructions, bottom-up.1425 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {1426 Instruction *Inst = &*std::prev(I);1427 1428 // Invoke instructions are visited as part of their successors (below).1429 if (isa<InvokeInst>(Inst))1430 continue;1431 1432 LLVM_DEBUG(dbgs() << " Visiting " << *Inst << "\n");1433 1434 NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates);1435 1436 // Bail out if the number of pointers being tracked becomes too large so1437 // that this pass can complete in a reasonable amount of time.1438 if (MyStates.bottom_up_ptr_list_size() > MaxPtrStates) {1439 DisableRetainReleasePairing = true;1440 return false;1441 }1442 }1443 1444 // If there's a predecessor with an invoke, visit the invoke as if it were1445 // part of this block, since we can't insert code after an invoke in its own1446 // block, and we don't want to split critical edges.1447 for (BBState::edge_iterator PI(MyStates.pred_begin()),1448 PE(MyStates.pred_end()); PI != PE; ++PI) {1449 BasicBlock *Pred = *PI;1450 if (InvokeInst *II = dyn_cast<InvokeInst>(&Pred->back()))1451 NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates);1452 }1453 1454 LLVM_DEBUG(dbgs() << "\nFinal State:\n" << BBStates[BB] << "\n");1455 1456 return NestingDetected;1457}1458 1459// Fill ReleaseInsertPtToRCIdentityRoots, which is a map from insertion points1460// to the set of RC identity roots that would be released by the release calls1461// moved to the insertion points.1462static void collectReleaseInsertPts(1463 const BlotMapVector<Value *, RRInfo> &Retains,1464 DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>1465 &ReleaseInsertPtToRCIdentityRoots) {1466 for (const auto &P : Retains) {1467 // Retains is a map from an objc_retain call to a RRInfo of the RC identity1468 // root of the call. Get the RC identity root of the objc_retain call.1469 Instruction *Retain = cast<Instruction>(P.first);1470 Value *Root = GetRCIdentityRoot(Retain->getOperand(0));1471 // Collect all the insertion points of the objc_release calls that release1472 // the RC identity root of the objc_retain call.1473 for (const Instruction *InsertPt : P.second.ReverseInsertPts)1474 ReleaseInsertPtToRCIdentityRoots[InsertPt].insert(Root);1475 }1476}1477 1478// Get the RC identity roots from an insertion point of an objc_release call.1479// Return nullptr if the passed instruction isn't an insertion point.1480static const SmallPtrSet<const Value *, 2> *1481getRCIdentityRootsFromReleaseInsertPt(1482 const Instruction *InsertPt,1483 const DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>1484 &ReleaseInsertPtToRCIdentityRoots) {1485 auto I = ReleaseInsertPtToRCIdentityRoots.find(InsertPt);1486 if (I == ReleaseInsertPtToRCIdentityRoots.end())1487 return nullptr;1488 return &I->second;1489}1490 1491bool ObjCARCOpt::VisitInstructionTopDown(1492 Instruction *Inst, DenseMap<Value *, RRInfo> &Releases, BBState &MyStates,1493 const DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>1494 &ReleaseInsertPtToRCIdentityRoots) {1495 bool NestingDetected = false;1496 ARCInstKind Class = GetARCInstKind(Inst);1497 const Value *Arg = nullptr;1498 1499 // Make sure a call to objc_retain isn't moved past insertion points of calls1500 // to objc_release.1501 if (const SmallPtrSet<const Value *, 2> *Roots =1502 getRCIdentityRootsFromReleaseInsertPt(1503 Inst, ReleaseInsertPtToRCIdentityRoots))1504 for (const auto *Root : *Roots) {1505 TopDownPtrState &S = MyStates.getPtrTopDownState(Root);1506 // Disable code motion if the current position is S_Retain to prevent1507 // moving the objc_retain call past objc_release calls. If it's1508 // S_CanRelease or larger, it's not necessary to disable code motion as1509 // the insertion points that prevent the objc_retain call from moving down1510 // should have been set already.1511 if (S.GetSeq() == S_Retain)1512 S.SetCFGHazardAfflicted(true);1513 }1514 1515 LLVM_DEBUG(dbgs() << " Class: " << Class << "\n");1516 1517 switch (Class) {1518 case ARCInstKind::RetainBlock:1519 // In OptimizeIndividualCalls, we have strength reduced all optimizable1520 // objc_retainBlocks to objc_retains. Thus at this point any1521 // objc_retainBlocks that we see are not optimizable. We need to break since1522 // a retain can be a potential use.1523 break;1524 case ARCInstKind::Retain:1525 case ARCInstKind::RetainRV: {1526 Arg = GetArgRCIdentityRoot(Inst);1527 TopDownPtrState &S = MyStates.getPtrTopDownState(Arg);1528 NestingDetected |= S.InitTopDown(Class, Inst);1529 // A retain can be a potential use; proceed to the generic checking1530 // code below.1531 break;1532 }1533 case ARCInstKind::Release: {1534 Arg = GetArgRCIdentityRoot(Inst);1535 TopDownPtrState &S = MyStates.getPtrTopDownState(Arg);1536 // Try to form a tentative pair in between this release instruction and the1537 // top down pointers that we are tracking.1538 if (S.MatchWithRelease(MDKindCache, Inst)) {1539 // If we succeed, copy S's RRInfo into the Release -> {Retain Set1540 // Map}. Then we clear S.1541 LLVM_DEBUG(dbgs() << " Matching with: " << *Inst << "\n");1542 Releases[Inst] = S.GetRRInfo();1543 S.ClearSequenceProgress();1544 }1545 break;1546 }1547 case ARCInstKind::AutoreleasepoolPop:1548 // Conservatively, clear MyStates for all known pointers.1549 MyStates.clearTopDownPointers();1550 return false;1551 case ARCInstKind::AutoreleasepoolPush:1552 case ARCInstKind::None:1553 // These can not be uses of1554 return false;1555 default:1556 break;1557 }1558 1559 // Consider any other possible effects of this instruction on each1560 // pointer being tracked.1561 for (auto MI = MyStates.top_down_ptr_begin(),1562 ME = MyStates.top_down_ptr_end();1563 MI != ME; ++MI) {1564 const Value *Ptr = MI->first;1565 if (Ptr == Arg)1566 continue; // Handled above.1567 TopDownPtrState &S = MI->second;1568 if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class, *BundledInsts))1569 continue;1570 1571 S.HandlePotentialUse(Inst, Ptr, PA, Class);1572 }1573 1574 return NestingDetected;1575}1576 1577bool ObjCARCOpt::VisitTopDown(1578 BasicBlock *BB, DenseMap<const BasicBlock *, BBState> &BBStates,1579 DenseMap<Value *, RRInfo> &Releases,1580 const DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>1581 &ReleaseInsertPtToRCIdentityRoots) {1582 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::VisitTopDown ==\n");1583 bool NestingDetected = false;1584 BBState &MyStates = BBStates[BB];1585 1586 // Merge the states from each predecessor to compute the initial state1587 // for the current block.1588 BBState::edge_iterator PI(MyStates.pred_begin()),1589 PE(MyStates.pred_end());1590 if (PI != PE) {1591 const BasicBlock *Pred = *PI;1592 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred);1593 assert(I != BBStates.end());1594 MyStates.InitFromPred(I->second);1595 ++PI;1596 for (; PI != PE; ++PI) {1597 Pred = *PI;1598 I = BBStates.find(Pred);1599 assert(I != BBStates.end());1600 MyStates.MergePred(I->second);1601 }1602 }1603 1604 // Check that BB and MyStates have the same number of predecessors. This1605 // prevents retain calls that live outside a loop from being moved into the1606 // loop.1607 if (!BB->hasNPredecessors(MyStates.pred_end() - MyStates.pred_begin()))1608 for (auto I = MyStates.top_down_ptr_begin(),1609 E = MyStates.top_down_ptr_end();1610 I != E; ++I)1611 I->second.SetCFGHazardAfflicted(true);1612 1613 LLVM_DEBUG(dbgs() << "Before:\n"1614 << BBStates[BB] << "\n"1615 << "Performing Dataflow:\n");1616 1617 // Visit all the instructions, top-down.1618 for (Instruction &Inst : *BB) {1619 LLVM_DEBUG(dbgs() << " Visiting " << Inst << "\n");1620 1621 NestingDetected |= VisitInstructionTopDown(1622 &Inst, Releases, MyStates, ReleaseInsertPtToRCIdentityRoots);1623 1624 // Bail out if the number of pointers being tracked becomes too large so1625 // that this pass can complete in a reasonable amount of time.1626 if (MyStates.top_down_ptr_list_size() > MaxPtrStates) {1627 DisableRetainReleasePairing = true;1628 return false;1629 }1630 }1631 1632 LLVM_DEBUG(dbgs() << "\nState Before Checking for CFG Hazards:\n"1633 << BBStates[BB] << "\n\n");1634 CheckForCFGHazards(BB, BBStates, MyStates);1635 LLVM_DEBUG(dbgs() << "Final State:\n" << BBStates[BB] << "\n");1636 return NestingDetected;1637}1638 1639static void1640ComputePostOrders(Function &F,1641 SmallVectorImpl<BasicBlock *> &PostOrder,1642 SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder,1643 unsigned NoObjCARCExceptionsMDKind,1644 DenseMap<const BasicBlock *, BBState> &BBStates) {1645 /// The visited set, for doing DFS walks.1646 SmallPtrSet<BasicBlock *, 16> Visited;1647 1648 // Do DFS, computing the PostOrder.1649 SmallPtrSet<BasicBlock *, 16> OnStack;1650 SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack;1651 1652 // Functions always have exactly one entry block, and we don't have1653 // any other block that we treat like an entry block.1654 BasicBlock *EntryBB = &F.getEntryBlock();1655 BBState &MyStates = BBStates[EntryBB];1656 MyStates.SetAsEntry();1657 Instruction *EntryTI = EntryBB->getTerminator();1658 SuccStack.push_back(std::make_pair(EntryBB, succ_iterator(EntryTI)));1659 Visited.insert(EntryBB);1660 OnStack.insert(EntryBB);1661 do {1662 dfs_next_succ:1663 BasicBlock *CurrBB = SuccStack.back().first;1664 succ_iterator SE(CurrBB->getTerminator(), false);1665 1666 while (SuccStack.back().second != SE) {1667 BasicBlock *SuccBB = *SuccStack.back().second++;1668 if (Visited.insert(SuccBB).second) {1669 SuccStack.push_back(1670 std::make_pair(SuccBB, succ_iterator(SuccBB->getTerminator())));1671 BBStates[CurrBB].addSucc(SuccBB);1672 BBState &SuccStates = BBStates[SuccBB];1673 SuccStates.addPred(CurrBB);1674 OnStack.insert(SuccBB);1675 goto dfs_next_succ;1676 }1677 1678 if (!OnStack.count(SuccBB)) {1679 BBStates[CurrBB].addSucc(SuccBB);1680 BBStates[SuccBB].addPred(CurrBB);1681 }1682 }1683 OnStack.erase(CurrBB);1684 PostOrder.push_back(CurrBB);1685 SuccStack.pop_back();1686 } while (!SuccStack.empty());1687 1688 Visited.clear();1689 1690 // Do reverse-CFG DFS, computing the reverse-CFG PostOrder.1691 // Functions may have many exits, and there also blocks which we treat1692 // as exits due to ignored edges.1693 SmallVector<std::pair<BasicBlock *, BBState::edge_iterator>, 16> PredStack;1694 for (BasicBlock &ExitBB : F) {1695 BBState &MyStates = BBStates[&ExitBB];1696 if (!MyStates.isExit())1697 continue;1698 1699 MyStates.SetAsExit();1700 1701 PredStack.push_back(std::make_pair(&ExitBB, MyStates.pred_begin()));1702 Visited.insert(&ExitBB);1703 while (!PredStack.empty()) {1704 reverse_dfs_next_succ:1705 BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end();1706 while (PredStack.back().second != PE) {1707 BasicBlock *BB = *PredStack.back().second++;1708 if (Visited.insert(BB).second) {1709 PredStack.push_back(std::make_pair(BB, BBStates[BB].pred_begin()));1710 goto reverse_dfs_next_succ;1711 }1712 }1713 ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first);1714 }1715 }1716}1717 1718// Visit the function both top-down and bottom-up.1719bool ObjCARCOpt::Visit(Function &F,1720 DenseMap<const BasicBlock *, BBState> &BBStates,1721 BlotMapVector<Value *, RRInfo> &Retains,1722 DenseMap<Value *, RRInfo> &Releases) {1723 // Use reverse-postorder traversals, because we magically know that loops1724 // will be well behaved, i.e. they won't repeatedly call retain on a single1725 // pointer without doing a release. We can't use the ReversePostOrderTraversal1726 // class here because we want the reverse-CFG postorder to consider each1727 // function exit point, and we want to ignore selected cycle edges.1728 SmallVector<BasicBlock *, 16> PostOrder;1729 SmallVector<BasicBlock *, 16> ReverseCFGPostOrder;1730 ComputePostOrders(F, PostOrder, ReverseCFGPostOrder,1731 MDKindCache.get(ARCMDKindID::NoObjCARCExceptions),1732 BBStates);1733 1734 // Use reverse-postorder on the reverse CFG for bottom-up.1735 bool BottomUpNestingDetected = false;1736 for (BasicBlock *BB : llvm::reverse(ReverseCFGPostOrder)) {1737 BottomUpNestingDetected |= VisitBottomUp(BB, BBStates, Retains);1738 if (DisableRetainReleasePairing)1739 return false;1740 }1741 1742 DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>1743 ReleaseInsertPtToRCIdentityRoots;1744 collectReleaseInsertPts(Retains, ReleaseInsertPtToRCIdentityRoots);1745 1746 // Use reverse-postorder for top-down.1747 bool TopDownNestingDetected = false;1748 for (BasicBlock *BB : llvm::reverse(PostOrder)) {1749 TopDownNestingDetected |=1750 VisitTopDown(BB, BBStates, Releases, ReleaseInsertPtToRCIdentityRoots);1751 if (DisableRetainReleasePairing)1752 return false;1753 }1754 1755 return TopDownNestingDetected && BottomUpNestingDetected;1756}1757 1758/// Move the calls in RetainsToMove and ReleasesToMove.1759void ObjCARCOpt::MoveCalls(Value *Arg, RRInfo &RetainsToMove,1760 RRInfo &ReleasesToMove,1761 BlotMapVector<Value *, RRInfo> &Retains,1762 DenseMap<Value *, RRInfo> &Releases,1763 SmallVectorImpl<Instruction *> &DeadInsts,1764 Module *M) {1765 LLVM_DEBUG(dbgs() << "== ObjCARCOpt::MoveCalls ==\n");1766 1767 // Insert the new retain and release calls.1768 for (Instruction *InsertPt : ReleasesToMove.ReverseInsertPts) {1769 Function *Decl = EP.get(ARCRuntimeEntryPointKind::Retain);1770 SmallVector<OperandBundleDef, 1> BundleList;1771 addOpBundleForFunclet(InsertPt->getParent(), BundleList);1772 CallInst *Call =1773 CallInst::Create(Decl, Arg, BundleList, "", InsertPt->getIterator());1774 Call->setDoesNotThrow();1775 Call->setTailCall();1776 1777 LLVM_DEBUG(dbgs() << "Inserting new Retain: " << *Call1778 << "\n"1779 "At insertion point: "1780 << *InsertPt << "\n");1781 }1782 for (Instruction *InsertPt : RetainsToMove.ReverseInsertPts) {1783 Function *Decl = EP.get(ARCRuntimeEntryPointKind::Release);1784 SmallVector<OperandBundleDef, 1> BundleList;1785 addOpBundleForFunclet(InsertPt->getParent(), BundleList);1786 CallInst *Call =1787 CallInst::Create(Decl, Arg, BundleList, "", InsertPt->getIterator());1788 // Attach a clang.imprecise_release metadata tag, if appropriate.1789 if (MDNode *M = ReleasesToMove.ReleaseMetadata)1790 Call->setMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease), M);1791 Call->setDoesNotThrow();1792 if (ReleasesToMove.IsTailCallRelease)1793 Call->setTailCall();1794 1795 LLVM_DEBUG(dbgs() << "Inserting new Release: " << *Call1796 << "\n"1797 "At insertion point: "1798 << *InsertPt << "\n");1799 }1800 1801 // Delete the original retain and release calls.1802 for (Instruction *OrigRetain : RetainsToMove.Calls) {1803 Retains.blot(OrigRetain);1804 DeadInsts.push_back(OrigRetain);1805 LLVM_DEBUG(dbgs() << "Deleting retain: " << *OrigRetain << "\n");1806 }1807 for (Instruction *OrigRelease : ReleasesToMove.Calls) {1808 Releases.erase(OrigRelease);1809 DeadInsts.push_back(OrigRelease);1810 LLVM_DEBUG(dbgs() << "Deleting release: " << *OrigRelease << "\n");1811 }1812}1813 1814bool ObjCARCOpt::PairUpRetainsAndReleases(1815 DenseMap<const BasicBlock *, BBState> &BBStates,1816 BlotMapVector<Value *, RRInfo> &Retains,1817 DenseMap<Value *, RRInfo> &Releases, Module *M,1818 Instruction *Retain,1819 SmallVectorImpl<Instruction *> &DeadInsts, RRInfo &RetainsToMove,1820 RRInfo &ReleasesToMove, Value *Arg, bool KnownSafe,1821 bool &AnyPairsCompletelyEliminated) {1822 // If a pair happens in a region where it is known that the reference count1823 // is already incremented, we can similarly ignore possible decrements unless1824 // we are dealing with a retainable object with multiple provenance sources.1825 bool KnownSafeTD = true, KnownSafeBU = true;1826 bool CFGHazardAfflicted = false;1827 1828 // Connect the dots between the top-down-collected RetainsToMove and1829 // bottom-up-collected ReleasesToMove to form sets of related calls.1830 // This is an iterative process so that we connect multiple releases1831 // to multiple retains if needed.1832 unsigned OldDelta = 0;1833 unsigned NewDelta = 0;1834 unsigned OldCount = 0;1835 unsigned NewCount = 0;1836 bool FirstRelease = true;1837 for (SmallVector<Instruction *, 4> NewRetains{Retain};;) {1838 SmallVector<Instruction *, 4> NewReleases;1839 for (Instruction *NewRetain : NewRetains) {1840 auto It = Retains.find(NewRetain);1841 assert(It != Retains.end());1842 const RRInfo &NewRetainRRI = It->second;1843 KnownSafeTD &= NewRetainRRI.KnownSafe;1844 CFGHazardAfflicted |= NewRetainRRI.CFGHazardAfflicted;1845 for (Instruction *NewRetainRelease : NewRetainRRI.Calls) {1846 auto Jt = Releases.find(NewRetainRelease);1847 if (Jt == Releases.end())1848 return false;1849 const RRInfo &NewRetainReleaseRRI = Jt->second;1850 1851 // If the release does not have a reference to the retain as well,1852 // something happened which is unaccounted for. Do not do anything.1853 //1854 // This can happen if we catch an additive overflow during path count1855 // merging.1856 if (!NewRetainReleaseRRI.Calls.count(NewRetain))1857 return false;1858 1859 if (ReleasesToMove.Calls.insert(NewRetainRelease).second) {1860 // If we overflow when we compute the path count, don't remove/move1861 // anything.1862 const BBState &NRRBBState = BBStates[NewRetainRelease->getParent()];1863 unsigned PathCount = BBState::OverflowOccurredValue;1864 if (NRRBBState.GetAllPathCountWithOverflow(PathCount))1865 return false;1866 assert(PathCount != BBState::OverflowOccurredValue &&1867 "PathCount at this point can not be "1868 "OverflowOccurredValue.");1869 OldDelta -= PathCount;1870 1871 // Merge the ReleaseMetadata and IsTailCallRelease values.1872 if (FirstRelease) {1873 ReleasesToMove.ReleaseMetadata =1874 NewRetainReleaseRRI.ReleaseMetadata;1875 ReleasesToMove.IsTailCallRelease =1876 NewRetainReleaseRRI.IsTailCallRelease;1877 FirstRelease = false;1878 } else {1879 if (ReleasesToMove.ReleaseMetadata !=1880 NewRetainReleaseRRI.ReleaseMetadata)1881 ReleasesToMove.ReleaseMetadata = nullptr;1882 if (ReleasesToMove.IsTailCallRelease !=1883 NewRetainReleaseRRI.IsTailCallRelease)1884 ReleasesToMove.IsTailCallRelease = false;1885 }1886 1887 // Collect the optimal insertion points.1888 if (!KnownSafe)1889 for (Instruction *RIP : NewRetainReleaseRRI.ReverseInsertPts) {1890 if (ReleasesToMove.ReverseInsertPts.insert(RIP).second) {1891 // If we overflow when we compute the path count, don't1892 // remove/move anything.1893 const BBState &RIPBBState = BBStates[RIP->getParent()];1894 PathCount = BBState::OverflowOccurredValue;1895 if (RIPBBState.GetAllPathCountWithOverflow(PathCount))1896 return false;1897 assert(PathCount != BBState::OverflowOccurredValue &&1898 "PathCount at this point can not be "1899 "OverflowOccurredValue.");1900 NewDelta -= PathCount;1901 }1902 }1903 NewReleases.push_back(NewRetainRelease);1904 }1905 }1906 }1907 NewRetains.clear();1908 if (NewReleases.empty()) break;1909 1910 // Back the other way.1911 for (Instruction *NewRelease : NewReleases) {1912 auto It = Releases.find(NewRelease);1913 assert(It != Releases.end());1914 const RRInfo &NewReleaseRRI = It->second;1915 KnownSafeBU &= NewReleaseRRI.KnownSafe;1916 CFGHazardAfflicted |= NewReleaseRRI.CFGHazardAfflicted;1917 for (Instruction *NewReleaseRetain : NewReleaseRRI.Calls) {1918 auto Jt = Retains.find(NewReleaseRetain);1919 if (Jt == Retains.end())1920 return false;1921 const RRInfo &NewReleaseRetainRRI = Jt->second;1922 1923 // If the retain does not have a reference to the release as well,1924 // something happened which is unaccounted for. Do not do anything.1925 //1926 // This can happen if we catch an additive overflow during path count1927 // merging.1928 if (!NewReleaseRetainRRI.Calls.count(NewRelease))1929 return false;1930 1931 if (RetainsToMove.Calls.insert(NewReleaseRetain).second) {1932 // If we overflow when we compute the path count, don't remove/move1933 // anything.1934 const BBState &NRRBBState = BBStates[NewReleaseRetain->getParent()];1935 unsigned PathCount = BBState::OverflowOccurredValue;1936 if (NRRBBState.GetAllPathCountWithOverflow(PathCount))1937 return false;1938 assert(PathCount != BBState::OverflowOccurredValue &&1939 "PathCount at this point can not be "1940 "OverflowOccurredValue.");1941 OldDelta += PathCount;1942 OldCount += PathCount;1943 1944 // Collect the optimal insertion points.1945 if (!KnownSafe)1946 for (Instruction *RIP : NewReleaseRetainRRI.ReverseInsertPts) {1947 if (RetainsToMove.ReverseInsertPts.insert(RIP).second) {1948 // If we overflow when we compute the path count, don't1949 // remove/move anything.1950 const BBState &RIPBBState = BBStates[RIP->getParent()];1951 1952 PathCount = BBState::OverflowOccurredValue;1953 if (RIPBBState.GetAllPathCountWithOverflow(PathCount))1954 return false;1955 assert(PathCount != BBState::OverflowOccurredValue &&1956 "PathCount at this point can not be "1957 "OverflowOccurredValue.");1958 NewDelta += PathCount;1959 NewCount += PathCount;1960 }1961 }1962 NewRetains.push_back(NewReleaseRetain);1963 }1964 }1965 }1966 if (NewRetains.empty()) break;1967 }1968 1969 // We can only remove pointers if we are known safe in both directions.1970 bool UnconditionallySafe = KnownSafeTD && KnownSafeBU;1971 if (UnconditionallySafe) {1972 RetainsToMove.ReverseInsertPts.clear();1973 ReleasesToMove.ReverseInsertPts.clear();1974 NewCount = 0;1975 } else {1976 // Determine whether the new insertion points we computed preserve the1977 // balance of retain and release calls through the program.1978 // TODO: If the fully aggressive solution isn't valid, try to find a1979 // less aggressive solution which is.1980 if (NewDelta != 0)1981 return false;1982 1983 // At this point, we are not going to remove any RR pairs, but we still are1984 // able to move RR pairs. If one of our pointers is afflicted with1985 // CFGHazards, we cannot perform such code motion so exit early.1986 const bool WillPerformCodeMotion =1987 !RetainsToMove.ReverseInsertPts.empty() ||1988 !ReleasesToMove.ReverseInsertPts.empty();1989 if (CFGHazardAfflicted && WillPerformCodeMotion)1990 return false;1991 }1992 1993 // Determine whether the original call points are balanced in the retain and1994 // release calls through the program. If not, conservatively don't touch1995 // them.1996 // TODO: It's theoretically possible to do code motion in this case, as1997 // long as the existing imbalances are maintained.1998 if (OldDelta != 0)1999 return false;2000 2001 Changed = true;2002 assert(OldCount != 0 && "Unreachable code?");2003 NumRRs += OldCount - NewCount;2004 // Set to true if we completely removed any RR pairs.2005 AnyPairsCompletelyEliminated = NewCount == 0;2006 2007 // We can move calls!2008 return true;2009}2010 2011/// Identify pairings between the retains and releases, and delete and/or move2012/// them.2013bool ObjCARCOpt::PerformCodePlacement(2014 DenseMap<const BasicBlock *, BBState> &BBStates,2015 BlotMapVector<Value *, RRInfo> &Retains,2016 DenseMap<Value *, RRInfo> &Releases, Module *M) {2017 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::PerformCodePlacement ==\n");2018 2019 bool AnyPairsCompletelyEliminated = false;2020 SmallVector<Instruction *, 8> DeadInsts;2021 2022 // Visit each retain.2023 for (BlotMapVector<Value *, RRInfo>::const_iterator I = Retains.begin(),2024 E = Retains.end();2025 I != E; ++I) {2026 Value *V = I->first;2027 if (!V) continue; // blotted2028 2029 Instruction *Retain = cast<Instruction>(V);2030 2031 LLVM_DEBUG(dbgs() << "Visiting: " << *Retain << "\n");2032 2033 Value *Arg = GetArgRCIdentityRoot(Retain);2034 2035 // If the object being released is in static or stack storage, we know it's2036 // not being managed by ObjC reference counting, so we can delete pairs2037 // regardless of what possible decrements or uses lie between them.2038 bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg);2039 2040 // A constant pointer can't be pointing to an object on the heap. It may2041 // be reference-counted, but it won't be deleted.2042 if (const LoadInst *LI = dyn_cast<LoadInst>(Arg))2043 if (const GlobalVariable *GV =2044 dyn_cast<GlobalVariable>(2045 GetRCIdentityRoot(LI->getPointerOperand())))2046 if (GV->isConstant())2047 KnownSafe = true;2048 2049 // Connect the dots between the top-down-collected RetainsToMove and2050 // bottom-up-collected ReleasesToMove to form sets of related calls.2051 RRInfo RetainsToMove, ReleasesToMove;2052 2053 bool PerformMoveCalls = PairUpRetainsAndReleases(2054 BBStates, Retains, Releases, M, Retain, DeadInsts,2055 RetainsToMove, ReleasesToMove, Arg, KnownSafe,2056 AnyPairsCompletelyEliminated);2057 2058 if (PerformMoveCalls) {2059 // Ok, everything checks out and we're all set. Let's move/delete some2060 // code!2061 MoveCalls(Arg, RetainsToMove, ReleasesToMove,2062 Retains, Releases, DeadInsts, M);2063 }2064 }2065 2066 // Now that we're done moving everything, we can delete the newly dead2067 // instructions, as we no longer need them as insert points.2068 while (!DeadInsts.empty())2069 EraseInstruction(DeadInsts.pop_back_val());2070 2071 return AnyPairsCompletelyEliminated;2072}2073 2074/// Weak pointer optimizations.2075void ObjCARCOpt::OptimizeWeakCalls(Function &F) {2076 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeWeakCalls ==\n");2077 2078 // First, do memdep-style RLE and S2L optimizations. We can't use memdep2079 // itself because it uses AliasAnalysis and we need to do provenance2080 // queries instead.2081 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {2082 Instruction *Inst = &*I++;2083 2084 LLVM_DEBUG(dbgs() << "Visiting: " << *Inst << "\n");2085 2086 ARCInstKind Class = GetBasicARCInstKind(Inst);2087 if (Class != ARCInstKind::LoadWeak &&2088 Class != ARCInstKind::LoadWeakRetained)2089 continue;2090 2091 // Delete objc_loadWeak calls with no users.2092 if (Class == ARCInstKind::LoadWeak && Inst->use_empty()) {2093 Inst->eraseFromParent();2094 Changed = true;2095 continue;2096 }2097 2098 // TODO: For now, just look for an earlier available version of this value2099 // within the same block. Theoretically, we could do memdep-style non-local2100 // analysis too, but that would want caching. A better approach would be to2101 // use the technique that EarlyCSE uses.2102 inst_iterator Current = std::prev(I);2103 BasicBlock *CurrentBB = &*Current.getBasicBlockIterator();2104 for (BasicBlock::iterator B = CurrentBB->begin(),2105 J = Current.getInstructionIterator();2106 J != B; --J) {2107 Instruction *EarlierInst = &*std::prev(J);2108 ARCInstKind EarlierClass = GetARCInstKind(EarlierInst);2109 switch (EarlierClass) {2110 case ARCInstKind::LoadWeak:2111 case ARCInstKind::LoadWeakRetained: {2112 // If this is loading from the same pointer, replace this load's value2113 // with that one.2114 CallInst *Call = cast<CallInst>(Inst);2115 CallInst *EarlierCall = cast<CallInst>(EarlierInst);2116 Value *Arg = Call->getArgOperand(0);2117 Value *EarlierArg = EarlierCall->getArgOperand(0);2118 switch (PA.getAA()->alias(Arg, EarlierArg)) {2119 case AliasResult::MustAlias:2120 Changed = true;2121 // If the load has a builtin retain, insert a plain retain for it.2122 if (Class == ARCInstKind::LoadWeakRetained) {2123 Function *Decl = EP.get(ARCRuntimeEntryPointKind::Retain);2124 CallInst *CI =2125 CallInst::Create(Decl, EarlierCall, "", Call->getIterator());2126 CI->setTailCall();2127 }2128 // Zap the fully redundant load.2129 Call->replaceAllUsesWith(EarlierCall);2130 Call->eraseFromParent();2131 goto clobbered;2132 case AliasResult::MayAlias:2133 case AliasResult::PartialAlias:2134 goto clobbered;2135 case AliasResult::NoAlias:2136 break;2137 }2138 break;2139 }2140 case ARCInstKind::StoreWeak:2141 case ARCInstKind::InitWeak: {2142 // If this is storing to the same pointer and has the same size etc.2143 // replace this load's value with the stored value.2144 CallInst *Call = cast<CallInst>(Inst);2145 CallInst *EarlierCall = cast<CallInst>(EarlierInst);2146 Value *Arg = Call->getArgOperand(0);2147 Value *EarlierArg = EarlierCall->getArgOperand(0);2148 switch (PA.getAA()->alias(Arg, EarlierArg)) {2149 case AliasResult::MustAlias:2150 Changed = true;2151 // If the load has a builtin retain, insert a plain retain for it.2152 if (Class == ARCInstKind::LoadWeakRetained) {2153 Function *Decl = EP.get(ARCRuntimeEntryPointKind::Retain);2154 CallInst *CI =2155 CallInst::Create(Decl, EarlierCall, "", Call->getIterator());2156 CI->setTailCall();2157 }2158 // Zap the fully redundant load.2159 Call->replaceAllUsesWith(EarlierCall->getArgOperand(1));2160 Call->eraseFromParent();2161 goto clobbered;2162 case AliasResult::MayAlias:2163 case AliasResult::PartialAlias:2164 goto clobbered;2165 case AliasResult::NoAlias:2166 break;2167 }2168 break;2169 }2170 case ARCInstKind::MoveWeak:2171 case ARCInstKind::CopyWeak:2172 // TOOD: Grab the copied value.2173 goto clobbered;2174 case ARCInstKind::AutoreleasepoolPush:2175 case ARCInstKind::None:2176 case ARCInstKind::IntrinsicUser:2177 case ARCInstKind::User:2178 // Weak pointers are only modified through the weak entry points2179 // (and arbitrary calls, which could call the weak entry points).2180 break;2181 default:2182 // Anything else could modify the weak pointer.2183 goto clobbered;2184 }2185 }2186 clobbered:;2187 }2188 2189 // Then, for each destroyWeak with an alloca operand, check to see if2190 // the alloca and all its users can be zapped.2191 for (Instruction &Inst : llvm::make_early_inc_range(instructions(F))) {2192 ARCInstKind Class = GetBasicARCInstKind(&Inst);2193 if (Class != ARCInstKind::DestroyWeak)2194 continue;2195 2196 CallInst *Call = cast<CallInst>(&Inst);2197 Value *Arg = Call->getArgOperand(0);2198 if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) {2199 for (User *U : Alloca->users()) {2200 const Instruction *UserInst = cast<Instruction>(U);2201 switch (GetBasicARCInstKind(UserInst)) {2202 case ARCInstKind::InitWeak:2203 case ARCInstKind::StoreWeak:2204 case ARCInstKind::DestroyWeak:2205 continue;2206 default:2207 goto done;2208 }2209 }2210 Changed = true;2211 for (User *U : llvm::make_early_inc_range(Alloca->users())) {2212 CallInst *UserInst = cast<CallInst>(U);2213 switch (GetBasicARCInstKind(UserInst)) {2214 case ARCInstKind::InitWeak:2215 case ARCInstKind::StoreWeak:2216 // These functions return their second argument.2217 UserInst->replaceAllUsesWith(UserInst->getArgOperand(1));2218 break;2219 case ARCInstKind::DestroyWeak:2220 // No return value.2221 break;2222 default:2223 llvm_unreachable("alloca really is used!");2224 }2225 UserInst->eraseFromParent();2226 }2227 Alloca->eraseFromParent();2228 done:;2229 }2230 }2231}2232 2233/// Identify program paths which execute sequences of retains and releases which2234/// can be eliminated.2235bool ObjCARCOpt::OptimizeSequences(Function &F) {2236 // Releases, Retains - These are used to store the results of the main flow2237 // analysis. These use Value* as the key instead of Instruction* so that the2238 // map stays valid when we get around to rewriting code and calls get2239 // replaced by arguments.2240 DenseMap<Value *, RRInfo> Releases;2241 BlotMapVector<Value *, RRInfo> Retains;2242 2243 // This is used during the traversal of the function to track the2244 // states for each identified object at each block.2245 DenseMap<const BasicBlock *, BBState> BBStates;2246 2247 // Analyze the CFG of the function, and all instructions.2248 bool NestingDetected = Visit(F, BBStates, Retains, Releases);2249 2250 if (DisableRetainReleasePairing)2251 return false;2252 2253 // Transform.2254 bool AnyPairsCompletelyEliminated = PerformCodePlacement(BBStates, Retains,2255 Releases,2256 F.getParent());2257 2258 return AnyPairsCompletelyEliminated && NestingDetected;2259}2260 2261/// Check if there is a dependent call earlier that does not have anything in2262/// between the Retain and the call that can affect the reference count of their2263/// shared pointer argument. Note that Retain need not be in BB.2264static CallInst *HasSafePathToPredecessorCall(const Value *Arg,2265 Instruction *Retain,2266 ProvenanceAnalysis &PA) {2267 auto *Call = dyn_cast_or_null<CallInst>(findSingleDependency(2268 CanChangeRetainCount, Arg, Retain->getParent(), Retain, PA));2269 2270 // Check that the pointer is the return value of the call.2271 if (!Call || Arg != Call)2272 return nullptr;2273 2274 // Check that the call is a regular call.2275 ARCInstKind Class = GetBasicARCInstKind(Call);2276 return Class == ARCInstKind::CallOrUser || Class == ARCInstKind::Call2277 ? Call2278 : nullptr;2279}2280 2281/// Find a dependent retain that precedes the given autorelease for which there2282/// is nothing in between the two instructions that can affect the ref count of2283/// Arg.2284static CallInst *2285FindPredecessorRetainWithSafePath(const Value *Arg, BasicBlock *BB,2286 Instruction *Autorelease,2287 ProvenanceAnalysis &PA) {2288 auto *Retain = dyn_cast_or_null<CallInst>(2289 findSingleDependency(CanChangeRetainCount, Arg, BB, Autorelease, PA));2290 2291 // Check that we found a retain with the same argument.2292 if (!Retain || !IsRetain(GetBasicARCInstKind(Retain)) ||2293 GetArgRCIdentityRoot(Retain) != Arg) {2294 return nullptr;2295 }2296 2297 return Retain;2298}2299 2300/// Look for an ``autorelease'' instruction dependent on Arg such that there are2301/// no instructions dependent on Arg that need a positive ref count in between2302/// the autorelease and the ret.2303static CallInst *FindPredecessorAutoreleaseWithSafePath(2304 const Value *Arg, BasicBlock *BB, ReturnInst *Ret, ProvenanceAnalysis &PA) {2305 auto *Autorelease = dyn_cast_or_null<CallInst>(2306 findSingleDependency(NeedsPositiveRetainCount, Arg, BB, Ret, PA));2307 2308 if (!Autorelease)2309 return nullptr;2310 ARCInstKind AutoreleaseClass = GetBasicARCInstKind(Autorelease);2311 if (!IsAutorelease(AutoreleaseClass))2312 return nullptr;2313 if (GetArgRCIdentityRoot(Autorelease) != Arg)2314 return nullptr;2315 2316 return Autorelease;2317}2318 2319/// Look for this pattern:2320/// \code2321/// %call = call i8* @something(...)2322/// %2 = call i8* @objc_retain(i8* %call)2323/// %3 = call i8* @objc_autorelease(i8* %2)2324/// ret i8* %32325/// \endcode2326/// And delete the retain and autorelease.2327void ObjCARCOpt::OptimizeReturns(Function &F) {2328 if (!F.getReturnType()->isPointerTy())2329 return;2330 2331 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeReturns ==\n");2332 2333 for (BasicBlock &BB: F) {2334 ReturnInst *Ret = dyn_cast<ReturnInst>(&BB.back());2335 if (!Ret)2336 continue;2337 2338 LLVM_DEBUG(dbgs() << "Visiting: " << *Ret << "\n");2339 2340 const Value *Arg = GetRCIdentityRoot(Ret->getOperand(0));2341 2342 // Look for an ``autorelease'' instruction that is a predecessor of Ret and2343 // dependent on Arg such that there are no instructions dependent on Arg2344 // that need a positive ref count in between the autorelease and Ret.2345 CallInst *Autorelease =2346 FindPredecessorAutoreleaseWithSafePath(Arg, &BB, Ret, PA);2347 2348 if (!Autorelease)2349 continue;2350 2351 CallInst *Retain = FindPredecessorRetainWithSafePath(2352 Arg, Autorelease->getParent(), Autorelease, PA);2353 2354 if (!Retain)2355 continue;2356 2357 // Check that there is nothing that can affect the reference count2358 // between the retain and the call. Note that Retain need not be in BB.2359 CallInst *Call = HasSafePathToPredecessorCall(Arg, Retain, PA);2360 2361 // Don't remove retainRV/autoreleaseRV pairs if the call isn't a tail call.2362 if (!Call ||2363 (!Call->isTailCall() &&2364 GetBasicARCInstKind(Retain) == ARCInstKind::RetainRV &&2365 GetBasicARCInstKind(Autorelease) == ARCInstKind::AutoreleaseRV))2366 continue;2367 2368 // If so, we can zap the retain and autorelease.2369 Changed = true;2370 ++NumRets;2371 LLVM_DEBUG(dbgs() << "Erasing: " << *Retain << "\nErasing: " << *Autorelease2372 << "\n");2373 BundledInsts->eraseInst(Retain);2374 EraseInstruction(Autorelease);2375 }2376}2377 2378#ifndef NDEBUG2379void2380ObjCARCOpt::GatherStatistics(Function &F, bool AfterOptimization) {2381 Statistic &NumRetains =2382 AfterOptimization ? NumRetainsAfterOpt : NumRetainsBeforeOpt;2383 Statistic &NumReleases =2384 AfterOptimization ? NumReleasesAfterOpt : NumReleasesBeforeOpt;2385 2386 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {2387 Instruction *Inst = &*I++;2388 switch (GetBasicARCInstKind(Inst)) {2389 default:2390 break;2391 case ARCInstKind::Retain:2392 ++NumRetains;2393 break;2394 case ARCInstKind::Release:2395 ++NumReleases;2396 break;2397 }2398 }2399}2400#endif2401 2402void ObjCARCOpt::init(Function &F) {2403 if (!EnableARCOpts)2404 return;2405 2406 // Intuitively, objc_retain and others are nocapture, however in practice2407 // they are not, because they return their argument value. And objc_release2408 // calls finalizers which can have arbitrary side effects.2409 MDKindCache.init(F.getParent());2410 2411 // Initialize our runtime entry point cache.2412 EP.init(F.getParent());2413 2414 // Compute which blocks are in which funclet.2415 if (F.hasPersonalityFn() &&2416 isScopedEHPersonality(classifyEHPersonality(F.getPersonalityFn())))2417 BlockEHColors = colorEHFunclets(F);2418}2419 2420bool ObjCARCOpt::run(Function &F, AAResults &AA) {2421 if (!EnableARCOpts)2422 return false;2423 2424 Changed = CFGChanged = false;2425 BundledRetainClaimRVs BRV(EP, /*ContractPass=*/false, /*UseClaimRV=*/false);2426 BundledInsts = &BRV;2427 2428 LLVM_DEBUG(dbgs() << "<<< ObjCARCOpt: Visiting Function: " << F.getName()2429 << " >>>"2430 "\n");2431 2432 std::pair<bool, bool> R = BundledInsts->insertAfterInvokes(F, nullptr);2433 Changed |= R.first;2434 CFGChanged |= R.second;2435 2436 PA.setAA(&AA);2437 2438#ifndef NDEBUG2439 if (AreStatisticsEnabled()) {2440 GatherStatistics(F, false);2441 }2442#endif2443 2444 // This pass performs several distinct transformations. As a compile-time aid2445 // when compiling code that isn't ObjC, skip these if the relevant ObjC2446 // library functions aren't declared.2447 2448 // Preliminary optimizations. This also computes UsedInThisFunction.2449 OptimizeIndividualCalls(F);2450 2451 // Optimizations for weak pointers.2452 if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::LoadWeak)) |2453 (1 << unsigned(ARCInstKind::LoadWeakRetained)) |2454 (1 << unsigned(ARCInstKind::StoreWeak)) |2455 (1 << unsigned(ARCInstKind::InitWeak)) |2456 (1 << unsigned(ARCInstKind::CopyWeak)) |2457 (1 << unsigned(ARCInstKind::MoveWeak)) |2458 (1 << unsigned(ARCInstKind::DestroyWeak))))2459 OptimizeWeakCalls(F);2460 2461 // Optimizations for retain+release pairs.2462 if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Retain)) |2463 (1 << unsigned(ARCInstKind::RetainRV)) |2464 (1 << unsigned(ARCInstKind::RetainBlock))))2465 if (UsedInThisFunction & (1 << unsigned(ARCInstKind::Release)))2466 // Run OptimizeSequences until it either stops making changes or2467 // no retain+release pair nesting is detected.2468 while (OptimizeSequences(F)) {}2469 2470 // Optimizations if objc_autorelease is used.2471 if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Autorelease)) |2472 (1 << unsigned(ARCInstKind::AutoreleaseRV))))2473 OptimizeReturns(F);2474 2475 // Optimizations for autorelease pools.2476 if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::AutoreleasepoolPush)) |2477 (1 << unsigned(ARCInstKind::AutoreleasepoolPop))))2478 OptimizeAutoreleasePools(F);2479 2480 // Gather statistics after optimization.2481#ifndef NDEBUG2482 if (AreStatisticsEnabled()) {2483 GatherStatistics(F, true);2484 }2485#endif2486 2487 LLVM_DEBUG(dbgs() << "\n");2488 2489 return Changed;2490}2491 2492/// Interprocedurally determine if calls made by the given call site can2493/// possibly produce autoreleases.2494bool MayAutorelease(const CallBase &CB, unsigned Depth = 0) {2495 if (CB.onlyReadsMemory())2496 return false;2497 2498 // This recursion depth limit is arbitrary. It's just great2499 // enough to cover known interesting testcases.2500 if (Depth > 5)2501 return true;2502 2503 if (const Function *Callee = CB.getCalledFunction()) {2504 if (!Callee->hasExactDefinition())2505 return true;2506 for (const BasicBlock &BB : *Callee) {2507 for (const Instruction &I : BB) {2508 // TODO: Ignore all instructions between autorelease pools2509 ARCInstKind InstKind = GetBasicARCInstKind(&I);2510 switch (InstKind) {2511 case ARCInstKind::Autorelease:2512 case ARCInstKind::AutoreleaseRV:2513 case ARCInstKind::FusedRetainAutorelease:2514 case ARCInstKind::FusedRetainAutoreleaseRV:2515 case ARCInstKind::LoadWeak:2516 // These may produce autoreleases2517 return true;2518 2519 case ARCInstKind::Retain:2520 case ARCInstKind::RetainRV:2521 case ARCInstKind::UnsafeClaimRV:2522 case ARCInstKind::RetainBlock:2523 case ARCInstKind::Release:2524 case ARCInstKind::NoopCast:2525 case ARCInstKind::LoadWeakRetained:2526 case ARCInstKind::StoreWeak:2527 case ARCInstKind::InitWeak:2528 case ARCInstKind::MoveWeak:2529 case ARCInstKind::CopyWeak:2530 case ARCInstKind::DestroyWeak:2531 case ARCInstKind::StoreStrong:2532 case ARCInstKind::AutoreleasepoolPush:2533 case ARCInstKind::AutoreleasepoolPop:2534 // These ObjC runtime functions don't produce autoreleases2535 break;2536 2537 case ARCInstKind::CallOrUser:2538 case ARCInstKind::Call:2539 // For non-ObjC function calls, recursively analyze2540 if (MayAutorelease(cast<CallBase>(I), Depth + 1))2541 return true;2542 break;2543 2544 case ARCInstKind::IntrinsicUser:2545 case ARCInstKind::User:2546 case ARCInstKind::None:2547 // These are not relevant for autorelease analysis2548 break;2549 }2550 }2551 }2552 return false;2553 }2554 2555 return true;2556}2557 2558/// Optimize autorelease pools by eliminating empty push/pop pairs.2559void ObjCARCOpt::OptimizeAutoreleasePools(Function &F) {2560 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeAutoreleasePools ==\n");2561 2562 OptimizationRemarkEmitter ORE(&F);2563 2564 // Process each basic block independently.2565 // TODO: Can we optimize inter-block autorelease pool pairs?2566 // This would involve tracking autorelease pool state across blocks.2567 for (BasicBlock &BB : F) {2568 // Use a stack to track nested autorelease pools2569 SmallVector<std::pair<CallInst *, bool>, 4>2570 PoolStack; // {push_inst, has_autorelease_in_scope}2571 2572 for (Instruction &Inst : llvm::make_early_inc_range(BB)) {2573 ARCInstKind Class = GetBasicARCInstKind(&Inst);2574 2575 switch (Class) {2576 case ARCInstKind::AutoreleasepoolPush: {2577 // Start tracking a new autorelease pool scope2578 auto *Push = cast<CallInst>(&Inst);2579 PoolStack.push_back(2580 {Push, false}); // {push_inst, has_autorelease_in_scope}2581 LLVM_DEBUG(dbgs() << "Found autorelease pool push: " << *Push << "\n");2582 break;2583 }2584 2585 case ARCInstKind::AutoreleasepoolPop: {2586 auto *Pop = cast<CallInst>(&Inst);2587 2588 if (PoolStack.empty())2589 break;2590 2591 auto &TopPool = PoolStack.back();2592 CallInst *PendingPush = TopPool.first;2593 bool HasAutoreleaseInScope = TopPool.second;2594 2595 // Pop the stack - remove this pool scope2596 PoolStack.pop_back();2597 2598 // Bail if this pop doesn't match the pending push2599 if (Pop->getArgOperand(0)->stripPointerCasts() != PendingPush)2600 break;2601 2602 // Bail if there were autoreleases in this scope2603 if (HasAutoreleaseInScope)2604 break;2605 2606 // Optimize: eliminate this empty autorelease pool pair2607 ORE.emit([&]() {2608 return OptimizationRemark(DEBUG_TYPE, "AutoreleasePoolElimination",2609 PendingPush)2610 << "eliminated empty autorelease pool pair";2611 });2612 2613 // Replace all uses of push with poison before deletion2614 PendingPush->replaceAllUsesWith(2615 PoisonValue::get(PendingPush->getType()));2616 2617 Pop->eraseFromParent();2618 PendingPush->eraseFromParent();2619 2620 Changed = true;2621 ++NumNoops;2622 break;2623 }2624 case ARCInstKind::CallOrUser:2625 case ARCInstKind::Call:2626 if (!MayAutorelease(cast<CallBase>(Inst)))2627 break;2628 [[fallthrough]];2629 case ARCInstKind::Autorelease:2630 case ARCInstKind::AutoreleaseRV:2631 case ARCInstKind::FusedRetainAutorelease:2632 case ARCInstKind::FusedRetainAutoreleaseRV:2633 case ARCInstKind::LoadWeak: {2634 // Track that we have autorelease calls in the current pool scope2635 if (!PoolStack.empty()) {2636 PoolStack.back().second = true; // Set has_autorelease_in_scope = true2637 LLVM_DEBUG(2638 dbgs()2639 << "Found autorelease or potential autorelease in pool scope: "2640 << Inst << "\n");2641 }2642 break;2643 }2644 2645 // Enumerate all remaining ARCInstKind cases explicitly2646 case ARCInstKind::Retain:2647 case ARCInstKind::RetainRV:2648 case ARCInstKind::UnsafeClaimRV:2649 case ARCInstKind::RetainBlock:2650 case ARCInstKind::Release:2651 case ARCInstKind::NoopCast:2652 case ARCInstKind::LoadWeakRetained:2653 case ARCInstKind::StoreWeak:2654 case ARCInstKind::InitWeak:2655 case ARCInstKind::MoveWeak:2656 case ARCInstKind::CopyWeak:2657 case ARCInstKind::DestroyWeak:2658 case ARCInstKind::StoreStrong:2659 case ARCInstKind::IntrinsicUser:2660 case ARCInstKind::User:2661 case ARCInstKind::None:2662 // These instruction kinds don't affect autorelease pool optimization2663 break;2664 }2665 }2666 }2667}2668 2669/// @}2670///2671 2672PreservedAnalyses ObjCARCOptPass::run(Function &F,2673 FunctionAnalysisManager &AM) {2674 ObjCARCOpt OCAO;2675 OCAO.init(F);2676 2677 bool Changed = OCAO.run(F, AM.getResult<AAManager>(F));2678 bool CFGChanged = OCAO.hasCFGChanged();2679 if (Changed) {2680 PreservedAnalyses PA;2681 if (!CFGChanged)2682 PA.preserveSet<CFGAnalyses>();2683 return PA;2684 }2685 return PreservedAnalyses::all();2686}2687