1249259Sdim//===- ObjCARCOpts.cpp - ObjC ARC Optimization ----------------------------===// 2249259Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6249259Sdim// 7249259Sdim//===----------------------------------------------------------------------===// 8327952Sdim// 9249259Sdim/// \file 10249259Sdim/// This file defines ObjC ARC optimizations. ARC stands for Automatic 11249259Sdim/// Reference Counting and is a system for managing reference counts for objects 12249259Sdim/// in Objective C. 13249259Sdim/// 14249259Sdim/// The optimizations performed include elimination of redundant, partially 15249259Sdim/// redundant, and inconsequential reference count operations, elimination of 16249259Sdim/// redundant weak pointer operations, and numerous minor simplifications. 17249259Sdim/// 18249259Sdim/// WARNING: This file knows about certain library functions. It recognizes them 19249259Sdim/// by name, and hardwires knowledge of their semantics. 20249259Sdim/// 21249259Sdim/// WARNING: This file knows about how certain Objective-C library functions are 22249259Sdim/// used. Naive LLVM IR transformations which would otherwise be 23249259Sdim/// behavior-preserving may break these assumptions. 24327952Sdim// 25249259Sdim//===----------------------------------------------------------------------===// 26249259Sdim 27261991Sdim#include "ARCRuntimeEntryPoints.h" 28288943Sdim#include "BlotMapVector.h" 29249259Sdim#include "DependencyAnalysis.h" 30321369Sdim#include "ObjCARC.h" 31249259Sdim#include "ProvenanceAnalysis.h" 32288943Sdim#include "PtrState.h" 33249259Sdim#include "llvm/ADT/DenseMap.h" 34327952Sdim#include "llvm/ADT/None.h" 35249259Sdim#include "llvm/ADT/STLExtras.h" 36249259Sdim#include "llvm/ADT/SmallPtrSet.h" 37327952Sdim#include "llvm/ADT/SmallVector.h" 38249259Sdim#include "llvm/ADT/Statistic.h" 39327952Sdim#include "llvm/Analysis/AliasAnalysis.h" 40341825Sdim#include "llvm/Analysis/EHPersonalities.h" 41296417Sdim#include "llvm/Analysis/ObjCARCAliasAnalysis.h" 42327952Sdim#include "llvm/Analysis/ObjCARCAnalysisUtils.h" 43327952Sdim#include "llvm/Analysis/ObjCARCInstKind.h" 44327952Sdim#include "llvm/IR/BasicBlock.h" 45276479Sdim#include "llvm/IR/CFG.h" 46327952Sdim#include "llvm/IR/CallSite.h" 47327952Sdim#include "llvm/IR/Constant.h" 48327952Sdim#include "llvm/IR/Constants.h" 49327952Sdim#include "llvm/IR/DerivedTypes.h" 50327952Sdim#include "llvm/IR/Function.h" 51327952Sdim#include "llvm/IR/GlobalVariable.h" 52327952Sdim#include "llvm/IR/InstIterator.h" 53327952Sdim#include "llvm/IR/InstrTypes.h" 54327952Sdim#include "llvm/IR/Instruction.h" 55327952Sdim#include "llvm/IR/Instructions.h" 56249259Sdim#include "llvm/IR/LLVMContext.h" 57327952Sdim#include "llvm/IR/Metadata.h" 58327952Sdim#include "llvm/IR/Type.h" 59327952Sdim#include "llvm/IR/User.h" 60327952Sdim#include "llvm/IR/Value.h" 61360784Sdim#include "llvm/InitializePasses.h" 62327952Sdim#include "llvm/Pass.h" 63327952Sdim#include "llvm/Support/Casting.h" 64360784Sdim#include "llvm/Support/CommandLine.h" 65327952Sdim#include "llvm/Support/Compiler.h" 66249259Sdim#include "llvm/Support/Debug.h" 67327952Sdim#include "llvm/Support/ErrorHandling.h" 68249259Sdim#include "llvm/Support/raw_ostream.h" 69327952Sdim#include <cassert> 70327952Sdim#include <iterator> 71327952Sdim#include <utility> 72249259Sdim 73249259Sdimusing namespace llvm; 74249259Sdimusing namespace llvm::objcarc; 75249259Sdim 76276479Sdim#define DEBUG_TYPE "objc-arc-opts" 77276479Sdim 78353358Sdimstatic cl::opt<unsigned> MaxPtrStates("arc-opt-max-ptr-states", 79353358Sdim cl::Hidden, 80353358Sdim cl::desc("Maximum number of ptr states the optimizer keeps track of"), 81353358Sdim cl::init(4095)); 82353358Sdim 83249259Sdim/// \defgroup ARCUtilities Utility declarations/definitions specific to ARC. 84249259Sdim/// @{ 85249259Sdim 86341825Sdim/// This is similar to GetRCIdentityRoot but it stops as soon 87249259Sdim/// as it finds a value with multiple uses. 88249259Sdimstatic const Value *FindSingleUseIdentifiedObject(const Value *Arg) { 89314564Sdim // ConstantData (like ConstantPointerNull and UndefValue) is used across 90314564Sdim // modules. It's never a single-use value. 91314564Sdim if (isa<ConstantData>(Arg)) 92314564Sdim return nullptr; 93314564Sdim 94249259Sdim if (Arg->hasOneUse()) { 95249259Sdim if (const BitCastInst *BC = dyn_cast<BitCastInst>(Arg)) 96249259Sdim return FindSingleUseIdentifiedObject(BC->getOperand(0)); 97249259Sdim if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Arg)) 98249259Sdim if (GEP->hasAllZeroIndices()) 99249259Sdim return FindSingleUseIdentifiedObject(GEP->getPointerOperand()); 100288943Sdim if (IsForwarding(GetBasicARCInstKind(Arg))) 101249259Sdim return FindSingleUseIdentifiedObject( 102249259Sdim cast<CallInst>(Arg)->getArgOperand(0)); 103249259Sdim if (!IsObjCIdentifiedObject(Arg)) 104276479Sdim return nullptr; 105249259Sdim return Arg; 106249259Sdim } 107249259Sdim 108249259Sdim // If we found an identifiable object but it has multiple uses, but they are 109249259Sdim // trivial uses, we can still consider this to be a single-use value. 110249259Sdim if (IsObjCIdentifiedObject(Arg)) { 111276479Sdim for (const User *U : Arg->users()) 112288943Sdim if (!U->use_empty() || GetRCIdentityRoot(U) != Arg) 113276479Sdim return nullptr; 114249259Sdim 115249259Sdim return Arg; 116249259Sdim } 117249259Sdim 118276479Sdim return nullptr; 119249259Sdim} 120249259Sdim 121249259Sdim/// @} 122249259Sdim/// 123249259Sdim/// \defgroup ARCOpt ARC Optimization. 124249259Sdim/// @{ 125249259Sdim 126249259Sdim// TODO: On code like this: 127249259Sdim// 128249259Sdim// objc_retain(%x) 129249259Sdim// stuff_that_cannot_release() 130249259Sdim// objc_autorelease(%x) 131249259Sdim// stuff_that_cannot_release() 132249259Sdim// objc_retain(%x) 133249259Sdim// stuff_that_cannot_release() 134249259Sdim// objc_autorelease(%x) 135249259Sdim// 136249259Sdim// The second retain and autorelease can be deleted. 137249259Sdim 138249259Sdim// TODO: It should be possible to delete 139249259Sdim// objc_autoreleasePoolPush and objc_autoreleasePoolPop 140249259Sdim// pairs if nothing is actually autoreleased between them. Also, autorelease 141249259Sdim// calls followed by objc_autoreleasePoolPop calls (perhaps in ObjC++ code 142249259Sdim// after inlining) can be turned into plain release calls. 143249259Sdim 144249259Sdim// TODO: Critical-edge splitting. If the optimial insertion point is 145249259Sdim// a critical edge, the current algorithm has to fail, because it doesn't 146249259Sdim// know how to split edges. It should be possible to make the optimizer 147249259Sdim// think in terms of edges, rather than blocks, and then split critical 148249259Sdim// edges on demand. 149249259Sdim 150249259Sdim// TODO: OptimizeSequences could generalized to be Interprocedural. 151249259Sdim 152249259Sdim// TODO: Recognize that a bunch of other objc runtime calls have 153249259Sdim// non-escaping arguments and non-releasing arguments, and may be 154249259Sdim// non-autoreleasing. 155249259Sdim 156249259Sdim// TODO: Sink autorelease calls as far as possible. Unfortunately we 157249259Sdim// usually can't sink them past other calls, which would be the main 158249259Sdim// case where it would be useful. 159249259Sdim 160249259Sdim// TODO: The pointer returned from objc_loadWeakRetained is retained. 161249259Sdim 162249259Sdim// TODO: Delete release+retain pairs (rare). 163249259Sdim 164249259SdimSTATISTIC(NumNoops, "Number of no-op objc calls eliminated"); 165249259SdimSTATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated"); 166249259SdimSTATISTIC(NumAutoreleases,"Number of autoreleases converted to releases"); 167249259SdimSTATISTIC(NumRets, "Number of return value forwarding " 168261991Sdim "retain+autoreleases eliminated"); 169249259SdimSTATISTIC(NumRRs, "Number of retain+release paths eliminated"); 170249259SdimSTATISTIC(NumPeeps, "Number of calls peephole-optimized"); 171261991Sdim#ifndef NDEBUG 172251662SdimSTATISTIC(NumRetainsBeforeOpt, 173261991Sdim "Number of retains before optimization"); 174251662SdimSTATISTIC(NumReleasesBeforeOpt, 175261991Sdim "Number of releases before optimization"); 176251662SdimSTATISTIC(NumRetainsAfterOpt, 177261991Sdim "Number of retains after optimization"); 178251662SdimSTATISTIC(NumReleasesAfterOpt, 179261991Sdim "Number of releases after optimization"); 180251662Sdim#endif 181249259Sdim 182249259Sdimnamespace { 183327952Sdim 184341825Sdim /// Per-BasicBlock state. 185249259Sdim class BBState { 186249259Sdim /// The number of unique control paths from the entry which can reach this 187249259Sdim /// block. 188327952Sdim unsigned TopDownPathCount = 0; 189249259Sdim 190249259Sdim /// The number of unique control paths to exits from this block. 191327952Sdim unsigned BottomUpPathCount = 0; 192249259Sdim 193249259Sdim /// The top-down traversal uses this to record information known about a 194249259Sdim /// pointer at the bottom of each block. 195288943Sdim BlotMapVector<const Value *, TopDownPtrState> PerPtrTopDown; 196249259Sdim 197249259Sdim /// The bottom-up traversal uses this to record information known about a 198249259Sdim /// pointer at the top of each block. 199288943Sdim BlotMapVector<const Value *, BottomUpPtrState> PerPtrBottomUp; 200249259Sdim 201249259Sdim /// Effective predecessors of the current block ignoring ignorable edges and 202249259Sdim /// ignored backedges. 203249259Sdim SmallVector<BasicBlock *, 2> Preds; 204288943Sdim 205249259Sdim /// Effective successors of the current block ignoring ignorable edges and 206249259Sdim /// ignored backedges. 207249259Sdim SmallVector<BasicBlock *, 2> Succs; 208249259Sdim 209249259Sdim public: 210261991Sdim static const unsigned OverflowOccurredValue; 211249259Sdim 212327952Sdim BBState() = default; 213261991Sdim 214327952Sdim using top_down_ptr_iterator = decltype(PerPtrTopDown)::iterator; 215327952Sdim using const_top_down_ptr_iterator = decltype(PerPtrTopDown)::const_iterator; 216249259Sdim 217288943Sdim top_down_ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); } 218288943Sdim top_down_ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); } 219288943Sdim const_top_down_ptr_iterator top_down_ptr_begin() const { 220249259Sdim return PerPtrTopDown.begin(); 221249259Sdim } 222288943Sdim const_top_down_ptr_iterator top_down_ptr_end() const { 223249259Sdim return PerPtrTopDown.end(); 224249259Sdim } 225288943Sdim bool hasTopDownPtrs() const { 226288943Sdim return !PerPtrTopDown.empty(); 227288943Sdim } 228249259Sdim 229353358Sdim unsigned top_down_ptr_list_size() const { 230353358Sdim return std::distance(top_down_ptr_begin(), top_down_ptr_end()); 231353358Sdim } 232353358Sdim 233327952Sdim using bottom_up_ptr_iterator = decltype(PerPtrBottomUp)::iterator; 234327952Sdim using const_bottom_up_ptr_iterator = 235327952Sdim decltype(PerPtrBottomUp)::const_iterator; 236288943Sdim 237288943Sdim bottom_up_ptr_iterator bottom_up_ptr_begin() { 238249259Sdim return PerPtrBottomUp.begin(); 239249259Sdim } 240288943Sdim bottom_up_ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); } 241288943Sdim const_bottom_up_ptr_iterator bottom_up_ptr_begin() const { 242288943Sdim return PerPtrBottomUp.begin(); 243288943Sdim } 244288943Sdim const_bottom_up_ptr_iterator bottom_up_ptr_end() const { 245249259Sdim return PerPtrBottomUp.end(); 246249259Sdim } 247288943Sdim bool hasBottomUpPtrs() const { 248288943Sdim return !PerPtrBottomUp.empty(); 249288943Sdim } 250249259Sdim 251353358Sdim unsigned bottom_up_ptr_list_size() const { 252353358Sdim return std::distance(bottom_up_ptr_begin(), bottom_up_ptr_end()); 253353358Sdim } 254353358Sdim 255249259Sdim /// Mark this block as being an entry block, which has one path from the 256249259Sdim /// entry by definition. 257249259Sdim void SetAsEntry() { TopDownPathCount = 1; } 258249259Sdim 259249259Sdim /// Mark this block as being an exit block, which has one path to an exit by 260249259Sdim /// definition. 261249259Sdim void SetAsExit() { BottomUpPathCount = 1; } 262249259Sdim 263261991Sdim /// Attempt to find the PtrState object describing the top down state for 264261991Sdim /// pointer Arg. Return a new initialized PtrState describing the top down 265261991Sdim /// state for Arg if we do not find one. 266288943Sdim TopDownPtrState &getPtrTopDownState(const Value *Arg) { 267249259Sdim return PerPtrTopDown[Arg]; 268249259Sdim } 269249259Sdim 270261991Sdim /// Attempt to find the PtrState object describing the bottom up state for 271261991Sdim /// pointer Arg. Return a new initialized PtrState describing the bottom up 272261991Sdim /// state for Arg if we do not find one. 273288943Sdim BottomUpPtrState &getPtrBottomUpState(const Value *Arg) { 274249259Sdim return PerPtrBottomUp[Arg]; 275249259Sdim } 276249259Sdim 277261991Sdim /// Attempt to find the PtrState object describing the bottom up state for 278261991Sdim /// pointer Arg. 279288943Sdim bottom_up_ptr_iterator findPtrBottomUpState(const Value *Arg) { 280261991Sdim return PerPtrBottomUp.find(Arg); 281261991Sdim } 282261991Sdim 283249259Sdim void clearBottomUpPointers() { 284249259Sdim PerPtrBottomUp.clear(); 285249259Sdim } 286249259Sdim 287249259Sdim void clearTopDownPointers() { 288249259Sdim PerPtrTopDown.clear(); 289249259Sdim } 290249259Sdim 291249259Sdim void InitFromPred(const BBState &Other); 292249259Sdim void InitFromSucc(const BBState &Other); 293249259Sdim void MergePred(const BBState &Other); 294249259Sdim void MergeSucc(const BBState &Other); 295249259Sdim 296261991Sdim /// Compute the number of possible unique paths from an entry to an exit 297249259Sdim /// which pass through this block. This is only valid after both the 298249259Sdim /// top-down and bottom-up traversals are complete. 299261991Sdim /// 300276479Sdim /// Returns true if overflow occurred. Returns false if overflow did not 301261991Sdim /// occur. 302261991Sdim bool GetAllPathCountWithOverflow(unsigned &PathCount) const { 303261991Sdim if (TopDownPathCount == OverflowOccurredValue || 304261991Sdim BottomUpPathCount == OverflowOccurredValue) 305261991Sdim return true; 306261991Sdim unsigned long long Product = 307261991Sdim (unsigned long long)TopDownPathCount*BottomUpPathCount; 308276479Sdim // Overflow occurred if any of the upper bits of Product are set or if all 309261991Sdim // the lower bits of Product are all set. 310261991Sdim return (Product >> 32) || 311261991Sdim ((PathCount = Product) == OverflowOccurredValue); 312249259Sdim } 313249259Sdim 314249259Sdim // Specialized CFG utilities. 315327952Sdim using edge_iterator = SmallVectorImpl<BasicBlock *>::const_iterator; 316327952Sdim 317261991Sdim edge_iterator pred_begin() const { return Preds.begin(); } 318261991Sdim edge_iterator pred_end() const { return Preds.end(); } 319261991Sdim edge_iterator succ_begin() const { return Succs.begin(); } 320261991Sdim edge_iterator succ_end() const { return Succs.end(); } 321249259Sdim 322249259Sdim void addSucc(BasicBlock *Succ) { Succs.push_back(Succ); } 323249259Sdim void addPred(BasicBlock *Pred) { Preds.push_back(Pred); } 324249259Sdim 325249259Sdim bool isExit() const { return Succs.empty(); } 326249259Sdim }; 327261991Sdim 328327952Sdim} // end anonymous namespace 329249259Sdim 330327952Sdimconst unsigned BBState::OverflowOccurredValue = 0xffffffff; 331327952Sdim 332288943Sdimnamespace llvm { 333327952Sdim 334288943Sdimraw_ostream &operator<<(raw_ostream &OS, 335288943Sdim BBState &BBState) LLVM_ATTRIBUTE_UNUSED; 336288943Sdim 337327952Sdim} // end namespace llvm 338327952Sdim 339249259Sdimvoid BBState::InitFromPred(const BBState &Other) { 340249259Sdim PerPtrTopDown = Other.PerPtrTopDown; 341249259Sdim TopDownPathCount = Other.TopDownPathCount; 342249259Sdim} 343249259Sdim 344249259Sdimvoid BBState::InitFromSucc(const BBState &Other) { 345249259Sdim PerPtrBottomUp = Other.PerPtrBottomUp; 346249259Sdim BottomUpPathCount = Other.BottomUpPathCount; 347249259Sdim} 348249259Sdim 349249259Sdim/// The top-down traversal uses this to merge information about predecessors to 350249259Sdim/// form the initial state for a new block. 351249259Sdimvoid BBState::MergePred(const BBState &Other) { 352261991Sdim if (TopDownPathCount == OverflowOccurredValue) 353261991Sdim return; 354261991Sdim 355249259Sdim // Other.TopDownPathCount can be 0, in which case it is either dead or a 356249259Sdim // loop backedge. Loop backedges are special. 357249259Sdim TopDownPathCount += Other.TopDownPathCount; 358249259Sdim 359261991Sdim // In order to be consistent, we clear the top down pointers when by adding 360261991Sdim // TopDownPathCount becomes OverflowOccurredValue even though "true" overflow 361276479Sdim // has not occurred. 362261991Sdim if (TopDownPathCount == OverflowOccurredValue) { 363261991Sdim clearTopDownPointers(); 364261991Sdim return; 365261991Sdim } 366261991Sdim 367249259Sdim // Check for overflow. If we have overflow, fall back to conservative 368249259Sdim // behavior. 369249259Sdim if (TopDownPathCount < Other.TopDownPathCount) { 370261991Sdim TopDownPathCount = OverflowOccurredValue; 371249259Sdim clearTopDownPointers(); 372249259Sdim return; 373249259Sdim } 374249259Sdim 375249259Sdim // For each entry in the other set, if our set has an entry with the same key, 376249259Sdim // merge the entries. Otherwise, copy the entry and merge it with an empty 377249259Sdim // entry. 378288943Sdim for (auto MI = Other.top_down_ptr_begin(), ME = Other.top_down_ptr_end(); 379288943Sdim MI != ME; ++MI) { 380288943Sdim auto Pair = PerPtrTopDown.insert(*MI); 381288943Sdim Pair.first->second.Merge(Pair.second ? TopDownPtrState() : MI->second, 382249259Sdim /*TopDown=*/true); 383249259Sdim } 384249259Sdim 385249259Sdim // For each entry in our set, if the other set doesn't have an entry with the 386249259Sdim // same key, force it to merge with an empty entry. 387288943Sdim for (auto MI = top_down_ptr_begin(), ME = top_down_ptr_end(); MI != ME; ++MI) 388249259Sdim if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end()) 389288943Sdim MI->second.Merge(TopDownPtrState(), /*TopDown=*/true); 390249259Sdim} 391249259Sdim 392249259Sdim/// The bottom-up traversal uses this to merge information about successors to 393249259Sdim/// form the initial state for a new block. 394249259Sdimvoid BBState::MergeSucc(const BBState &Other) { 395261991Sdim if (BottomUpPathCount == OverflowOccurredValue) 396261991Sdim return; 397261991Sdim 398249259Sdim // Other.BottomUpPathCount can be 0, in which case it is either dead or a 399249259Sdim // loop backedge. Loop backedges are special. 400249259Sdim BottomUpPathCount += Other.BottomUpPathCount; 401249259Sdim 402261991Sdim // In order to be consistent, we clear the top down pointers when by adding 403261991Sdim // BottomUpPathCount becomes OverflowOccurredValue even though "true" overflow 404276479Sdim // has not occurred. 405261991Sdim if (BottomUpPathCount == OverflowOccurredValue) { 406261991Sdim clearBottomUpPointers(); 407261991Sdim return; 408261991Sdim } 409261991Sdim 410249259Sdim // Check for overflow. If we have overflow, fall back to conservative 411249259Sdim // behavior. 412249259Sdim if (BottomUpPathCount < Other.BottomUpPathCount) { 413261991Sdim BottomUpPathCount = OverflowOccurredValue; 414249259Sdim clearBottomUpPointers(); 415249259Sdim return; 416249259Sdim } 417249259Sdim 418249259Sdim // For each entry in the other set, if our set has an entry with the 419249259Sdim // same key, merge the entries. Otherwise, copy the entry and merge 420249259Sdim // it with an empty entry. 421288943Sdim for (auto MI = Other.bottom_up_ptr_begin(), ME = Other.bottom_up_ptr_end(); 422288943Sdim MI != ME; ++MI) { 423288943Sdim auto Pair = PerPtrBottomUp.insert(*MI); 424288943Sdim Pair.first->second.Merge(Pair.second ? BottomUpPtrState() : MI->second, 425249259Sdim /*TopDown=*/false); 426249259Sdim } 427249259Sdim 428249259Sdim // For each entry in our set, if the other set doesn't have an entry 429249259Sdim // with the same key, force it to merge with an empty entry. 430288943Sdim for (auto MI = bottom_up_ptr_begin(), ME = bottom_up_ptr_end(); MI != ME; 431288943Sdim ++MI) 432249259Sdim if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end()) 433288943Sdim MI->second.Merge(BottomUpPtrState(), /*TopDown=*/false); 434249259Sdim} 435249259Sdim 436288943Sdimraw_ostream &llvm::operator<<(raw_ostream &OS, BBState &BBInfo) { 437288943Sdim // Dump the pointers we are tracking. 438288943Sdim OS << " TopDown State:\n"; 439288943Sdim if (!BBInfo.hasTopDownPtrs()) { 440341825Sdim LLVM_DEBUG(dbgs() << " NONE!\n"); 441288943Sdim } else { 442288943Sdim for (auto I = BBInfo.top_down_ptr_begin(), E = BBInfo.top_down_ptr_end(); 443288943Sdim I != E; ++I) { 444288943Sdim const PtrState &P = I->second; 445288943Sdim OS << " Ptr: " << *I->first 446288943Sdim << "\n KnownSafe: " << (P.IsKnownSafe()?"true":"false") 447288943Sdim << "\n ImpreciseRelease: " 448288943Sdim << (P.IsTrackingImpreciseReleases()?"true":"false") << "\n" 449288943Sdim << " HasCFGHazards: " 450288943Sdim << (P.IsCFGHazardAfflicted()?"true":"false") << "\n" 451288943Sdim << " KnownPositive: " 452288943Sdim << (P.HasKnownPositiveRefCount()?"true":"false") << "\n" 453288943Sdim << " Seq: " 454288943Sdim << P.GetSeq() << "\n"; 455249259Sdim } 456249259Sdim } 457249259Sdim 458288943Sdim OS << " BottomUp State:\n"; 459288943Sdim if (!BBInfo.hasBottomUpPtrs()) { 460341825Sdim LLVM_DEBUG(dbgs() << " NONE!\n"); 461288943Sdim } else { 462288943Sdim for (auto I = BBInfo.bottom_up_ptr_begin(), E = BBInfo.bottom_up_ptr_end(); 463288943Sdim I != E; ++I) { 464288943Sdim const PtrState &P = I->second; 465288943Sdim OS << " Ptr: " << *I->first 466288943Sdim << "\n KnownSafe: " << (P.IsKnownSafe()?"true":"false") 467288943Sdim << "\n ImpreciseRelease: " 468288943Sdim << (P.IsTrackingImpreciseReleases()?"true":"false") << "\n" 469288943Sdim << " HasCFGHazards: " 470288943Sdim << (P.IsCFGHazardAfflicted()?"true":"false") << "\n" 471288943Sdim << " KnownPositive: " 472288943Sdim << (P.HasKnownPositiveRefCount()?"true":"false") << "\n" 473288943Sdim << " Seq: " 474288943Sdim << P.GetSeq() << "\n"; 475288943Sdim } 476249259Sdim } 477249259Sdim 478288943Sdim return OS; 479249259Sdim} 480249259Sdim 481288943Sdimnamespace { 482251662Sdim 483341825Sdim /// The main ARC optimization pass. 484249259Sdim class ObjCARCOpt : public FunctionPass { 485249259Sdim bool Changed; 486249259Sdim ProvenanceAnalysis PA; 487288943Sdim 488288943Sdim /// A cache of references to runtime entry point constants. 489261991Sdim ARCRuntimeEntryPoints EP; 490249259Sdim 491288943Sdim /// A cache of MDKinds that can be passed into other functions to propagate 492288943Sdim /// MDKind identifiers. 493288943Sdim ARCMDKindCache MDKindCache; 494288943Sdim 495249259Sdim /// A flag indicating whether this optimization pass should run. 496249259Sdim bool Run; 497249259Sdim 498353358Sdim /// A flag indicating whether the optimization that removes or moves 499353358Sdim /// retain/release pairs should be performed. 500353358Sdim bool DisableRetainReleasePairing = false; 501353358Sdim 502296417Sdim /// Flags which determine whether each of the interesting runtime functions 503249259Sdim /// is in fact used in the current function. 504249259Sdim unsigned UsedInThisFunction; 505249259Sdim 506249259Sdim bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV); 507249259Sdim void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV, 508288943Sdim ARCInstKind &Class); 509249259Sdim void OptimizeIndividualCalls(Function &F); 510249259Sdim 511360784Sdim /// Optimize an individual call, optionally passing the 512360784Sdim /// GetArgRCIdentityRoot if it has already been computed. 513360784Sdim void OptimizeIndividualCallImpl( 514360784Sdim Function &F, DenseMap<BasicBlock *, ColorVector> &BlockColors, 515360784Sdim Instruction *Inst, ARCInstKind Class, const Value *Arg); 516360784Sdim 517360784Sdim /// Try to optimize an AutoreleaseRV with a RetainRV or ClaimRV. If the 518360784Sdim /// optimization occurs, returns true to indicate that the caller should 519360784Sdim /// assume the instructions are dead. 520360784Sdim bool OptimizeInlinedAutoreleaseRVCall( 521360784Sdim Function &F, DenseMap<BasicBlock *, ColorVector> &BlockColors, 522360784Sdim Instruction *Inst, const Value *&Arg, ARCInstKind Class, 523360784Sdim Instruction *AutoreleaseRV, const Value *&AutoreleaseRVArg); 524360784Sdim 525249259Sdim void CheckForCFGHazards(const BasicBlock *BB, 526249259Sdim DenseMap<const BasicBlock *, BBState> &BBStates, 527249259Sdim BBState &MyStates) const; 528288943Sdim bool VisitInstructionBottomUp(Instruction *Inst, BasicBlock *BB, 529288943Sdim BlotMapVector<Value *, RRInfo> &Retains, 530249259Sdim BBState &MyStates); 531249259Sdim bool VisitBottomUp(BasicBlock *BB, 532249259Sdim DenseMap<const BasicBlock *, BBState> &BBStates, 533288943Sdim BlotMapVector<Value *, RRInfo> &Retains); 534249259Sdim bool VisitInstructionTopDown(Instruction *Inst, 535249259Sdim DenseMap<Value *, RRInfo> &Releases, 536249259Sdim BBState &MyStates); 537249259Sdim bool VisitTopDown(BasicBlock *BB, 538249259Sdim DenseMap<const BasicBlock *, BBState> &BBStates, 539249259Sdim DenseMap<Value *, RRInfo> &Releases); 540288943Sdim bool Visit(Function &F, DenseMap<const BasicBlock *, BBState> &BBStates, 541288943Sdim BlotMapVector<Value *, RRInfo> &Retains, 542249259Sdim DenseMap<Value *, RRInfo> &Releases); 543249259Sdim 544249259Sdim void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove, 545288943Sdim BlotMapVector<Value *, RRInfo> &Retains, 546249259Sdim DenseMap<Value *, RRInfo> &Releases, 547288943Sdim SmallVectorImpl<Instruction *> &DeadInsts, Module *M); 548249259Sdim 549288943Sdim bool 550288943Sdim PairUpRetainsAndReleases(DenseMap<const BasicBlock *, BBState> &BBStates, 551288943Sdim BlotMapVector<Value *, RRInfo> &Retains, 552288943Sdim DenseMap<Value *, RRInfo> &Releases, Module *M, 553321369Sdim Instruction * Retain, 554288943Sdim SmallVectorImpl<Instruction *> &DeadInsts, 555288943Sdim RRInfo &RetainsToMove, RRInfo &ReleasesToMove, 556288943Sdim Value *Arg, bool KnownSafe, 557288943Sdim bool &AnyPairsCompletelyEliminated); 558249259Sdim 559249259Sdim bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates, 560288943Sdim BlotMapVector<Value *, RRInfo> &Retains, 561288943Sdim DenseMap<Value *, RRInfo> &Releases, Module *M); 562249259Sdim 563249259Sdim void OptimizeWeakCalls(Function &F); 564249259Sdim 565249259Sdim bool OptimizeSequences(Function &F); 566249259Sdim 567249259Sdim void OptimizeReturns(Function &F); 568249259Sdim 569251662Sdim#ifndef NDEBUG 570251662Sdim void GatherStatistics(Function &F, bool AfterOptimization = false); 571251662Sdim#endif 572251662Sdim 573276479Sdim void getAnalysisUsage(AnalysisUsage &AU) const override; 574276479Sdim bool doInitialization(Module &M) override; 575276479Sdim bool runOnFunction(Function &F) override; 576276479Sdim void releaseMemory() override; 577249259Sdim 578249259Sdim public: 579249259Sdim static char ID; 580327952Sdim 581249259Sdim ObjCARCOpt() : FunctionPass(ID) { 582249259Sdim initializeObjCARCOptPass(*PassRegistry::getPassRegistry()); 583249259Sdim } 584249259Sdim }; 585249259Sdim 586327952Sdim} // end anonymous namespace 587327952Sdim 588249259Sdimchar ObjCARCOpt::ID = 0; 589327952Sdim 590249259SdimINITIALIZE_PASS_BEGIN(ObjCARCOpt, 591249259Sdim "objc-arc", "ObjC ARC optimization", false, false) 592296417SdimINITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass) 593249259SdimINITIALIZE_PASS_END(ObjCARCOpt, 594249259Sdim "objc-arc", "ObjC ARC optimization", false, false) 595249259Sdim 596249259SdimPass *llvm::createObjCARCOptPass() { 597249259Sdim return new ObjCARCOpt(); 598249259Sdim} 599249259Sdim 600249259Sdimvoid ObjCARCOpt::getAnalysisUsage(AnalysisUsage &AU) const { 601296417Sdim AU.addRequired<ObjCARCAAWrapperPass>(); 602296417Sdim AU.addRequired<AAResultsWrapperPass>(); 603249259Sdim // ARC optimization doesn't currently split critical edges. 604249259Sdim AU.setPreservesCFG(); 605249259Sdim} 606249259Sdim 607249259Sdim/// Turn objc_retainAutoreleasedReturnValue into objc_retain if the operand is 608360784Sdim/// not a return value. 609249259Sdimbool 610249259SdimObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) { 611249259Sdim // Check for the argument being from an immediately preceding call or invoke. 612288943Sdim const Value *Arg = GetArgRCIdentityRoot(RetainRV); 613249259Sdim ImmutableCallSite CS(Arg); 614249259Sdim if (const Instruction *Call = CS.getInstruction()) { 615249259Sdim if (Call->getParent() == RetainRV->getParent()) { 616296417Sdim BasicBlock::const_iterator I(Call); 617249259Sdim ++I; 618296417Sdim while (IsNoopInstruction(&*I)) 619296417Sdim ++I; 620249259Sdim if (&*I == RetainRV) 621249259Sdim return false; 622249259Sdim } else if (const InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 623249259Sdim BasicBlock *RetainRVParent = RetainRV->getParent(); 624249259Sdim if (II->getNormalDest() == RetainRVParent) { 625249259Sdim BasicBlock::const_iterator I = RetainRVParent->begin(); 626296417Sdim while (IsNoopInstruction(&*I)) 627296417Sdim ++I; 628249259Sdim if (&*I == RetainRV) 629249259Sdim return false; 630249259Sdim } 631249259Sdim } 632249259Sdim } 633249259Sdim 634249259Sdim // Turn it to a plain objc_retain. 635249259Sdim Changed = true; 636249259Sdim ++NumPeeps; 637249259Sdim 638341825Sdim LLVM_DEBUG(dbgs() << "Transforming objc_retainAutoreleasedReturnValue => " 639341825Sdim "objc_retain since the operand is not a return value.\n" 640341825Sdim "Old = " 641341825Sdim << *RetainRV << "\n"); 642249259Sdim 643353358Sdim Function *NewDecl = EP.get(ARCRuntimeEntryPointKind::Retain); 644261991Sdim cast<CallInst>(RetainRV)->setCalledFunction(NewDecl); 645249259Sdim 646341825Sdim LLVM_DEBUG(dbgs() << "New = " << *RetainRV << "\n"); 647249259Sdim 648249259Sdim return false; 649249259Sdim} 650249259Sdim 651360784Sdimbool ObjCARCOpt::OptimizeInlinedAutoreleaseRVCall( 652360784Sdim Function &F, DenseMap<BasicBlock *, ColorVector> &BlockColors, 653360784Sdim Instruction *Inst, const Value *&Arg, ARCInstKind Class, 654360784Sdim Instruction *AutoreleaseRV, const Value *&AutoreleaseRVArg) { 655360784Sdim // Must be in the same basic block. 656360784Sdim assert(Inst->getParent() == AutoreleaseRV->getParent()); 657360784Sdim 658360784Sdim // Must operate on the same root. 659360784Sdim Arg = GetArgRCIdentityRoot(Inst); 660360784Sdim AutoreleaseRVArg = GetArgRCIdentityRoot(AutoreleaseRV); 661360784Sdim if (Arg != AutoreleaseRVArg) { 662360784Sdim // If there isn't an exact match, check if we have equivalent PHIs. 663360784Sdim const PHINode *PN = dyn_cast<PHINode>(Arg); 664360784Sdim if (!PN) 665360784Sdim return false; 666360784Sdim 667360784Sdim SmallVector<const Value *, 4> ArgUsers; 668360784Sdim getEquivalentPHIs(*PN, ArgUsers); 669360784Sdim if (llvm::find(ArgUsers, AutoreleaseRVArg) == ArgUsers.end()) 670360784Sdim return false; 671360784Sdim } 672360784Sdim 673360784Sdim // Okay, this is a match. Merge them. 674360784Sdim ++NumPeeps; 675360784Sdim LLVM_DEBUG(dbgs() << "Found inlined objc_autoreleaseReturnValue '" 676360784Sdim << *AutoreleaseRV << "' paired with '" << *Inst << "'\n"); 677360784Sdim 678360784Sdim // Delete the RV pair, starting with the AutoreleaseRV. 679360784Sdim AutoreleaseRV->replaceAllUsesWith( 680360784Sdim cast<CallInst>(AutoreleaseRV)->getArgOperand(0)); 681360784Sdim EraseInstruction(AutoreleaseRV); 682360784Sdim if (Class == ARCInstKind::RetainRV) { 683360784Sdim // AutoreleaseRV and RetainRV cancel out. Delete the RetainRV. 684360784Sdim Inst->replaceAllUsesWith(cast<CallInst>(Inst)->getArgOperand(0)); 685360784Sdim EraseInstruction(Inst); 686360784Sdim return true; 687360784Sdim } 688360784Sdim 689360784Sdim // ClaimRV is a frontend peephole for RetainRV + Release. Since the 690360784Sdim // AutoreleaseRV and RetainRV cancel out, replace the ClaimRV with a Release. 691360784Sdim assert(Class == ARCInstKind::ClaimRV); 692360784Sdim Value *CallArg = cast<CallInst>(Inst)->getArgOperand(0); 693360784Sdim CallInst *Release = CallInst::Create( 694360784Sdim EP.get(ARCRuntimeEntryPointKind::Release), CallArg, "", Inst); 695360784Sdim assert(IsAlwaysTail(ARCInstKind::ClaimRV) && 696360784Sdim "Expected ClaimRV to be safe to tail call"); 697360784Sdim Release->setTailCall(); 698360784Sdim Inst->replaceAllUsesWith(CallArg); 699360784Sdim EraseInstruction(Inst); 700360784Sdim 701360784Sdim // Run the normal optimizations on Release. 702360784Sdim OptimizeIndividualCallImpl(F, BlockColors, Release, ARCInstKind::Release, 703360784Sdim Arg); 704360784Sdim return true; 705360784Sdim} 706360784Sdim 707249259Sdim/// Turn objc_autoreleaseReturnValue into objc_autorelease if the result is not 708249259Sdim/// used as a return value. 709288943Sdimvoid ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, 710288943Sdim Instruction *AutoreleaseRV, 711288943Sdim ARCInstKind &Class) { 712249259Sdim // Check for a return of the pointer value. 713288943Sdim const Value *Ptr = GetArgRCIdentityRoot(AutoreleaseRV); 714314564Sdim 715314564Sdim // If the argument is ConstantPointerNull or UndefValue, its other users 716314564Sdim // aren't actually interesting to look at. 717314564Sdim if (isa<ConstantData>(Ptr)) 718314564Sdim return; 719314564Sdim 720249259Sdim SmallVector<const Value *, 2> Users; 721249259Sdim Users.push_back(Ptr); 722341825Sdim 723341825Sdim // Add PHIs that are equivalent to Ptr to Users. 724341825Sdim if (const PHINode *PN = dyn_cast<PHINode>(Ptr)) 725341825Sdim getEquivalentPHIs(*PN, Users); 726341825Sdim 727249259Sdim do { 728249259Sdim Ptr = Users.pop_back_val(); 729276479Sdim for (const User *U : Ptr->users()) { 730288943Sdim if (isa<ReturnInst>(U) || GetBasicARCInstKind(U) == ARCInstKind::RetainRV) 731249259Sdim return; 732276479Sdim if (isa<BitCastInst>(U)) 733276479Sdim Users.push_back(U); 734249259Sdim } 735249259Sdim } while (!Users.empty()); 736249259Sdim 737249259Sdim Changed = true; 738249259Sdim ++NumPeeps; 739249259Sdim 740341825Sdim LLVM_DEBUG( 741341825Sdim dbgs() << "Transforming objc_autoreleaseReturnValue => " 742341825Sdim "objc_autorelease since its operand is not used as a return " 743341825Sdim "value.\n" 744341825Sdim "Old = " 745341825Sdim << *AutoreleaseRV << "\n"); 746249259Sdim 747249259Sdim CallInst *AutoreleaseRVCI = cast<CallInst>(AutoreleaseRV); 748353358Sdim Function *NewDecl = EP.get(ARCRuntimeEntryPointKind::Autorelease); 749261991Sdim AutoreleaseRVCI->setCalledFunction(NewDecl); 750249259Sdim AutoreleaseRVCI->setTailCall(false); // Never tail call objc_autorelease. 751288943Sdim Class = ARCInstKind::Autorelease; 752249259Sdim 753341825Sdim LLVM_DEBUG(dbgs() << "New: " << *AutoreleaseRV << "\n"); 754249259Sdim} 755249259Sdim 756341825Sdimnamespace { 757341825SdimInstruction * 758341825SdimCloneCallInstForBB(CallInst &CI, BasicBlock &BB, 759341825Sdim const DenseMap<BasicBlock *, ColorVector> &BlockColors) { 760341825Sdim SmallVector<OperandBundleDef, 1> OpBundles; 761341825Sdim for (unsigned I = 0, E = CI.getNumOperandBundles(); I != E; ++I) { 762341825Sdim auto Bundle = CI.getOperandBundleAt(I); 763341825Sdim // Funclets will be reassociated in the future. 764341825Sdim if (Bundle.getTagID() == LLVMContext::OB_funclet) 765341825Sdim continue; 766341825Sdim OpBundles.emplace_back(Bundle); 767341825Sdim } 768341825Sdim 769341825Sdim if (!BlockColors.empty()) { 770341825Sdim const ColorVector &CV = BlockColors.find(&BB)->second; 771341825Sdim assert(CV.size() == 1 && "non-unique color for block!"); 772341825Sdim Instruction *EHPad = CV.front()->getFirstNonPHI(); 773341825Sdim if (EHPad->isEHPad()) 774341825Sdim OpBundles.emplace_back("funclet", EHPad); 775341825Sdim } 776341825Sdim 777341825Sdim return CallInst::Create(&CI, OpBundles); 778341825Sdim} 779341825Sdim} 780341825Sdim 781249259Sdim/// Visit each call, one at a time, and make simplifications without doing any 782249259Sdim/// additional analysis. 783249259Sdimvoid ObjCARCOpt::OptimizeIndividualCalls(Function &F) { 784341825Sdim LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeIndividualCalls ==\n"); 785249259Sdim // Reset all the flags in preparation for recomputing them. 786249259Sdim UsedInThisFunction = 0; 787249259Sdim 788341825Sdim DenseMap<BasicBlock *, ColorVector> BlockColors; 789341825Sdim if (F.hasPersonalityFn() && 790341825Sdim isScopedEHPersonality(classifyEHPersonality(F.getPersonalityFn()))) 791341825Sdim BlockColors = colorEHFunclets(F); 792341825Sdim 793360784Sdim // Store any delayed AutoreleaseRV intrinsics, so they can be easily paired 794360784Sdim // with RetainRV and ClaimRV. 795360784Sdim Instruction *DelayedAutoreleaseRV = nullptr; 796360784Sdim const Value *DelayedAutoreleaseRVArg = nullptr; 797360784Sdim auto setDelayedAutoreleaseRV = [&](Instruction *AutoreleaseRV) { 798360784Sdim assert(!DelayedAutoreleaseRV || !AutoreleaseRV); 799360784Sdim DelayedAutoreleaseRV = AutoreleaseRV; 800360784Sdim DelayedAutoreleaseRVArg = nullptr; 801360784Sdim }; 802360784Sdim auto optimizeDelayedAutoreleaseRV = [&]() { 803360784Sdim if (!DelayedAutoreleaseRV) 804360784Sdim return; 805360784Sdim OptimizeIndividualCallImpl(F, BlockColors, DelayedAutoreleaseRV, 806360784Sdim ARCInstKind::AutoreleaseRV, 807360784Sdim DelayedAutoreleaseRVArg); 808360784Sdim setDelayedAutoreleaseRV(nullptr); 809360784Sdim }; 810360784Sdim auto shouldDelayAutoreleaseRV = [&](Instruction *NonARCInst) { 811360784Sdim // Nothing to delay, but we may as well skip the logic below. 812360784Sdim if (!DelayedAutoreleaseRV) 813360784Sdim return true; 814360784Sdim 815360784Sdim // If we hit the end of the basic block we're not going to find an RV-pair. 816360784Sdim // Stop delaying. 817360784Sdim if (NonARCInst->isTerminator()) 818360784Sdim return false; 819360784Sdim 820360784Sdim // Given the frontend rules for emitting AutoreleaseRV, RetainRV, and 821360784Sdim // ClaimRV, it's probably safe to skip over even opaque function calls 822360784Sdim // here since OptimizeInlinedAutoreleaseRVCall will confirm that they 823360784Sdim // have the same RCIdentityRoot. However, what really matters is 824360784Sdim // skipping instructions or intrinsics that the inliner could leave behind; 825360784Sdim // be conservative for now and don't skip over opaque calls, which could 826360784Sdim // potentially include other ARC calls. 827360784Sdim auto *CB = dyn_cast<CallBase>(NonARCInst); 828360784Sdim if (!CB) 829360784Sdim return true; 830360784Sdim return CB->getIntrinsicID() != Intrinsic::not_intrinsic; 831360784Sdim }; 832360784Sdim 833249259Sdim // Visit all objc_* calls in F. 834249259Sdim for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { 835249259Sdim Instruction *Inst = &*I++; 836249259Sdim 837288943Sdim ARCInstKind Class = GetBasicARCInstKind(Inst); 838249259Sdim 839360784Sdim // Skip this loop if this instruction isn't itself an ARC intrinsic. 840360784Sdim const Value *Arg = nullptr; 841360784Sdim switch (Class) { 842360784Sdim default: 843360784Sdim optimizeDelayedAutoreleaseRV(); 844360784Sdim break; 845360784Sdim case ARCInstKind::CallOrUser: 846360784Sdim case ARCInstKind::User: 847360784Sdim case ARCInstKind::None: 848360784Sdim // This is a non-ARC instruction. If we're delaying an AutoreleaseRV, 849360784Sdim // check if it's safe to skip over it; if not, optimize the AutoreleaseRV 850360784Sdim // now. 851360784Sdim if (!shouldDelayAutoreleaseRV(Inst)) 852360784Sdim optimizeDelayedAutoreleaseRV(); 853360784Sdim continue; 854360784Sdim case ARCInstKind::AutoreleaseRV: 855360784Sdim optimizeDelayedAutoreleaseRV(); 856360784Sdim setDelayedAutoreleaseRV(Inst); 857360784Sdim continue; 858360784Sdim case ARCInstKind::RetainRV: 859360784Sdim case ARCInstKind::ClaimRV: 860360784Sdim if (DelayedAutoreleaseRV) { 861360784Sdim // We have a potential RV pair. Check if they cancel out. 862360784Sdim if (OptimizeInlinedAutoreleaseRVCall(F, BlockColors, Inst, Arg, Class, 863360784Sdim DelayedAutoreleaseRV, 864360784Sdim DelayedAutoreleaseRVArg)) { 865360784Sdim setDelayedAutoreleaseRV(nullptr); 866353358Sdim continue; 867353358Sdim } 868360784Sdim optimizeDelayedAutoreleaseRV(); 869249259Sdim } 870249259Sdim break; 871249259Sdim } 872249259Sdim 873360784Sdim OptimizeIndividualCallImpl(F, BlockColors, Inst, Class, Arg); 874360784Sdim } 875249259Sdim 876360784Sdim // Catch the final delayed AutoreleaseRV. 877360784Sdim optimizeDelayedAutoreleaseRV(); 878360784Sdim} 879249259Sdim 880360784Sdimvoid ObjCARCOpt::OptimizeIndividualCallImpl( 881360784Sdim Function &F, DenseMap<BasicBlock *, ColorVector> &BlockColors, 882360784Sdim Instruction *Inst, ARCInstKind Class, const Value *Arg) { 883360784Sdim LLVM_DEBUG(dbgs() << "Visiting: Class: " << Class << "; " << *Inst << "\n"); 884249259Sdim 885360784Sdim // Some of the ARC calls can be deleted if their arguments are global 886360784Sdim // variables that are inert in ARC. 887360784Sdim if (IsNoopOnGlobal(Class)) { 888360784Sdim Value *Opnd = Inst->getOperand(0); 889360784Sdim if (auto *GV = dyn_cast<GlobalVariable>(Opnd->stripPointerCasts())) 890360784Sdim if (GV->hasAttribute("objc_arc_inert")) { 891360784Sdim if (!Inst->getType()->isVoidTy()) 892360784Sdim Inst->replaceAllUsesWith(Opnd); 893360784Sdim Inst->eraseFromParent(); 894360784Sdim return; 895360784Sdim } 896360784Sdim } 897261991Sdim 898360784Sdim switch (Class) { 899360784Sdim default: 900360784Sdim break; 901249259Sdim 902360784Sdim // Delete no-op casts. These function calls have special semantics, but 903360784Sdim // the semantics are entirely implemented via lowering in the front-end, 904360784Sdim // so by the time they reach the optimizer, they are just no-op calls 905360784Sdim // which return their argument. 906360784Sdim // 907360784Sdim // There are gray areas here, as the ability to cast reference-counted 908360784Sdim // pointers to raw void* and back allows code to break ARC assumptions, 909360784Sdim // however these are currently considered to be unimportant. 910360784Sdim case ARCInstKind::NoopCast: 911360784Sdim Changed = true; 912360784Sdim ++NumNoops; 913360784Sdim LLVM_DEBUG(dbgs() << "Erasing no-op cast: " << *Inst << "\n"); 914360784Sdim EraseInstruction(Inst); 915360784Sdim return; 916249259Sdim 917360784Sdim // If the pointer-to-weak-pointer is null, it's undefined behavior. 918360784Sdim case ARCInstKind::StoreWeak: 919360784Sdim case ARCInstKind::LoadWeak: 920360784Sdim case ARCInstKind::LoadWeakRetained: 921360784Sdim case ARCInstKind::InitWeak: 922360784Sdim case ARCInstKind::DestroyWeak: { 923360784Sdim CallInst *CI = cast<CallInst>(Inst); 924360784Sdim if (IsNullOrUndef(CI->getArgOperand(0))) { 925249259Sdim Changed = true; 926360784Sdim Type *Ty = CI->getArgOperand(0)->getType(); 927360784Sdim new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()), 928360784Sdim Constant::getNullValue(Ty), CI); 929360784Sdim Value *NewValue = UndefValue::get(CI->getType()); 930341825Sdim LLVM_DEBUG( 931360784Sdim dbgs() << "A null pointer-to-weak-pointer is undefined behavior." 932360784Sdim "\nOld = " 933360784Sdim << *CI << "\nNew = " << *NewValue << "\n"); 934360784Sdim CI->replaceAllUsesWith(NewValue); 935360784Sdim CI->eraseFromParent(); 936360784Sdim return; 937249259Sdim } 938360784Sdim break; 939360784Sdim } 940360784Sdim case ARCInstKind::CopyWeak: 941360784Sdim case ARCInstKind::MoveWeak: { 942360784Sdim CallInst *CI = cast<CallInst>(Inst); 943360784Sdim if (IsNullOrUndef(CI->getArgOperand(0)) || 944360784Sdim IsNullOrUndef(CI->getArgOperand(1))) { 945360784Sdim Changed = true; 946360784Sdim Type *Ty = CI->getArgOperand(0)->getType(); 947360784Sdim new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()), 948360784Sdim Constant::getNullValue(Ty), CI); 949249259Sdim 950360784Sdim Value *NewValue = UndefValue::get(CI->getType()); 951360784Sdim LLVM_DEBUG( 952360784Sdim dbgs() << "A null pointer-to-weak-pointer is undefined behavior." 953360784Sdim "\nOld = " 954360784Sdim << *CI << "\nNew = " << *NewValue << "\n"); 955360784Sdim 956360784Sdim CI->replaceAllUsesWith(NewValue); 957360784Sdim CI->eraseFromParent(); 958360784Sdim return; 959249259Sdim } 960360784Sdim break; 961360784Sdim } 962360784Sdim case ARCInstKind::RetainRV: 963360784Sdim if (OptimizeRetainRVCall(F, Inst)) 964360784Sdim return; 965360784Sdim break; 966360784Sdim case ARCInstKind::AutoreleaseRV: 967360784Sdim OptimizeAutoreleaseRVCall(F, Inst, Class); 968360784Sdim break; 969360784Sdim } 970249259Sdim 971360784Sdim // objc_autorelease(x) -> objc_release(x) if x is otherwise unused. 972360784Sdim if (IsAutorelease(Class) && Inst->use_empty()) { 973360784Sdim CallInst *Call = cast<CallInst>(Inst); 974360784Sdim const Value *Arg = Call->getArgOperand(0); 975360784Sdim Arg = FindSingleUseIdentifiedObject(Arg); 976360784Sdim if (Arg) { 977249259Sdim Changed = true; 978360784Sdim ++NumAutoreleases; 979249259Sdim 980360784Sdim // Create the declaration lazily. 981360784Sdim LLVMContext &C = Inst->getContext(); 982249259Sdim 983360784Sdim Function *Decl = EP.get(ARCRuntimeEntryPointKind::Release); 984360784Sdim CallInst *NewCall = 985360784Sdim CallInst::Create(Decl, Call->getArgOperand(0), "", Call); 986360784Sdim NewCall->setMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease), 987360784Sdim MDNode::get(C, None)); 988249259Sdim 989360784Sdim LLVM_DEBUG(dbgs() << "Replacing autorelease{,RV}(x) with objc_release(x) " 990360784Sdim "since x is otherwise unused.\nOld: " 991360784Sdim << *Call << "\nNew: " << *NewCall << "\n"); 992360784Sdim 993360784Sdim EraseInstruction(Call); 994360784Sdim Inst = NewCall; 995360784Sdim Class = ARCInstKind::Release; 996249259Sdim } 997360784Sdim } 998249259Sdim 999360784Sdim // For functions which can never be passed stack arguments, add 1000360784Sdim // a tail keyword. 1001360784Sdim if (IsAlwaysTail(Class) && !cast<CallInst>(Inst)->isNoTailCall()) { 1002360784Sdim Changed = true; 1003360784Sdim LLVM_DEBUG( 1004360784Sdim dbgs() << "Adding tail keyword to function since it can never be " 1005360784Sdim "passed stack args: " 1006360784Sdim << *Inst << "\n"); 1007360784Sdim cast<CallInst>(Inst)->setTailCall(); 1008360784Sdim } 1009360784Sdim 1010360784Sdim // Ensure that functions that can never have a "tail" keyword due to the 1011360784Sdim // semantics of ARC truly do not do so. 1012360784Sdim if (IsNeverTail(Class)) { 1013360784Sdim Changed = true; 1014360784Sdim LLVM_DEBUG(dbgs() << "Removing tail keyword from function: " << *Inst 1015360784Sdim << "\n"); 1016360784Sdim cast<CallInst>(Inst)->setTailCall(false); 1017360784Sdim } 1018360784Sdim 1019360784Sdim // Set nounwind as needed. 1020360784Sdim if (IsNoThrow(Class)) { 1021360784Sdim Changed = true; 1022360784Sdim LLVM_DEBUG(dbgs() << "Found no throw class. Setting nounwind on: " << *Inst 1023360784Sdim << "\n"); 1024360784Sdim cast<CallInst>(Inst)->setDoesNotThrow(); 1025360784Sdim } 1026360784Sdim 1027360784Sdim // Note: This catches instructions unrelated to ARC. 1028360784Sdim if (!IsNoopOnNull(Class)) { 1029288943Sdim UsedInThisFunction |= 1 << unsigned(Class); 1030360784Sdim return; 1031360784Sdim } 1032249259Sdim 1033360784Sdim // If we haven't already looked up the root, look it up now. 1034360784Sdim if (!Arg) 1035360784Sdim Arg = GetArgRCIdentityRoot(Inst); 1036327952Sdim 1037360784Sdim // ARC calls with null are no-ops. Delete them. 1038360784Sdim if (IsNullOrUndef(Arg)) { 1039360784Sdim Changed = true; 1040360784Sdim ++NumNoops; 1041360784Sdim LLVM_DEBUG(dbgs() << "ARC calls with null are no-ops. Erasing: " << *Inst 1042360784Sdim << "\n"); 1043360784Sdim EraseInstruction(Inst); 1044360784Sdim return; 1045360784Sdim } 1046249259Sdim 1047360784Sdim // Keep track of which of retain, release, autorelease, and retain_block 1048360784Sdim // are actually present in this function. 1049360784Sdim UsedInThisFunction |= 1 << unsigned(Class); 1050249259Sdim 1051360784Sdim // If Arg is a PHI, and one or more incoming values to the 1052360784Sdim // PHI are null, and the call is control-equivalent to the PHI, and there 1053360784Sdim // are no relevant side effects between the PHI and the call, and the call 1054360784Sdim // is not a release that doesn't have the clang.imprecise_release tag, the 1055360784Sdim // call could be pushed up to just those paths with non-null incoming 1056360784Sdim // values. For now, don't bother splitting critical edges for this. 1057360784Sdim if (Class == ARCInstKind::Release && 1058360784Sdim !Inst->getMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease))) 1059360784Sdim return; 1060360784Sdim 1061360784Sdim SmallVector<std::pair<Instruction *, const Value *>, 4> Worklist; 1062360784Sdim Worklist.push_back(std::make_pair(Inst, Arg)); 1063360784Sdim do { 1064360784Sdim std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val(); 1065360784Sdim Inst = Pair.first; 1066360784Sdim Arg = Pair.second; 1067360784Sdim 1068360784Sdim const PHINode *PN = dyn_cast<PHINode>(Arg); 1069360784Sdim if (!PN) 1070360784Sdim continue; 1071360784Sdim 1072360784Sdim // Determine if the PHI has any null operands, or any incoming 1073360784Sdim // critical edges. 1074360784Sdim bool HasNull = false; 1075360784Sdim bool HasCriticalEdges = false; 1076360784Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1077360784Sdim Value *Incoming = GetRCIdentityRoot(PN->getIncomingValue(i)); 1078360784Sdim if (IsNullOrUndef(Incoming)) 1079360784Sdim HasNull = true; 1080360784Sdim else if (PN->getIncomingBlock(i)->getTerminator()->getNumSuccessors() != 1081360784Sdim 1) { 1082360784Sdim HasCriticalEdges = true; 1083360784Sdim break; 1084249259Sdim } 1085360784Sdim } 1086360784Sdim // If we have null operands and no critical edges, optimize. 1087360784Sdim if (HasCriticalEdges) 1088360784Sdim continue; 1089360784Sdim if (!HasNull) 1090360784Sdim continue; 1091249259Sdim 1092360784Sdim SmallPtrSet<Instruction *, 4> DependingInstructions; 1093360784Sdim SmallPtrSet<const BasicBlock *, 4> Visited; 1094249259Sdim 1095360784Sdim // Check that there is nothing that cares about the reference 1096360784Sdim // count between the call and the phi. 1097360784Sdim switch (Class) { 1098360784Sdim case ARCInstKind::Retain: 1099360784Sdim case ARCInstKind::RetainBlock: 1100360784Sdim // These can always be moved up. 1101360784Sdim break; 1102360784Sdim case ARCInstKind::Release: 1103360784Sdim // These can't be moved across things that care about the retain 1104360784Sdim // count. 1105360784Sdim FindDependencies(NeedsPositiveRetainCount, Arg, Inst->getParent(), Inst, 1106360784Sdim DependingInstructions, Visited, PA); 1107360784Sdim break; 1108360784Sdim case ARCInstKind::Autorelease: 1109360784Sdim // These can't be moved across autorelease pool scope boundaries. 1110360784Sdim FindDependencies(AutoreleasePoolBoundary, Arg, Inst->getParent(), Inst, 1111360784Sdim DependingInstructions, Visited, PA); 1112360784Sdim break; 1113360784Sdim case ARCInstKind::ClaimRV: 1114360784Sdim case ARCInstKind::RetainRV: 1115360784Sdim case ARCInstKind::AutoreleaseRV: 1116360784Sdim // Don't move these; the RV optimization depends on the autoreleaseRV 1117360784Sdim // being tail called, and the retainRV being immediately after a call 1118360784Sdim // (which might still happen if we get lucky with codegen layout, but 1119360784Sdim // it's not worth taking the chance). 1120360784Sdim continue; 1121360784Sdim default: 1122360784Sdim llvm_unreachable("Invalid dependence flavor"); 1123360784Sdim } 1124249259Sdim 1125360784Sdim if (DependingInstructions.size() != 1) 1126360784Sdim continue; 1127360784Sdim if (*DependingInstructions.begin() != PN) 1128360784Sdim continue; 1129360784Sdim 1130360784Sdim Changed = true; 1131360784Sdim ++NumPartialNoops; 1132360784Sdim // Clone the call into each predecessor that has a non-null value. 1133360784Sdim CallInst *CInst = cast<CallInst>(Inst); 1134360784Sdim Type *ParamTy = CInst->getArgOperand(0)->getType(); 1135360784Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1136360784Sdim Value *Incoming = GetRCIdentityRoot(PN->getIncomingValue(i)); 1137360784Sdim if (IsNullOrUndef(Incoming)) 1138360784Sdim continue; 1139360784Sdim Value *Op = PN->getIncomingValue(i); 1140360784Sdim Instruction *InsertPos = &PN->getIncomingBlock(i)->back(); 1141360784Sdim CallInst *Clone = cast<CallInst>( 1142360784Sdim CloneCallInstForBB(*CInst, *InsertPos->getParent(), BlockColors)); 1143360784Sdim if (Op->getType() != ParamTy) 1144360784Sdim Op = new BitCastInst(Op, ParamTy, "", InsertPos); 1145360784Sdim Clone->setArgOperand(0, Op); 1146360784Sdim Clone->insertBefore(InsertPos); 1147360784Sdim 1148360784Sdim LLVM_DEBUG(dbgs() << "Cloning " << *CInst << "\n" 1149360784Sdim "And inserting clone at " 1150360784Sdim << *InsertPos << "\n"); 1151360784Sdim Worklist.push_back(std::make_pair(Clone, Incoming)); 1152360784Sdim } 1153360784Sdim // Erase the original call. 1154360784Sdim LLVM_DEBUG(dbgs() << "Erasing: " << *CInst << "\n"); 1155360784Sdim EraseInstruction(CInst); 1156360784Sdim } while (!Worklist.empty()); 1157249259Sdim} 1158249259Sdim 1159251662Sdim/// If we have a top down pointer in the S_Use state, make sure that there are 1160251662Sdim/// no CFG hazards by checking the states of various bottom up pointers. 1161251662Sdimstatic void CheckForUseCFGHazard(const Sequence SuccSSeq, 1162251662Sdim const bool SuccSRRIKnownSafe, 1163288943Sdim TopDownPtrState &S, 1164251662Sdim bool &SomeSuccHasSame, 1165251662Sdim bool &AllSuccsHaveSame, 1166261991Sdim bool &NotAllSeqEqualButKnownSafe, 1167251662Sdim bool &ShouldContinue) { 1168251662Sdim switch (SuccSSeq) { 1169251662Sdim case S_CanRelease: { 1170261991Sdim if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) { 1171251662Sdim S.ClearSequenceProgress(); 1172251662Sdim break; 1173251662Sdim } 1174261991Sdim S.SetCFGHazardAfflicted(true); 1175251662Sdim ShouldContinue = true; 1176251662Sdim break; 1177251662Sdim } 1178251662Sdim case S_Use: 1179251662Sdim SomeSuccHasSame = true; 1180251662Sdim break; 1181251662Sdim case S_Stop: 1182251662Sdim case S_Release: 1183251662Sdim case S_MovableRelease: 1184261991Sdim if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) 1185251662Sdim AllSuccsHaveSame = false; 1186261991Sdim else 1187261991Sdim NotAllSeqEqualButKnownSafe = true; 1188251662Sdim break; 1189251662Sdim case S_Retain: 1190251662Sdim llvm_unreachable("bottom-up pointer in retain state!"); 1191251662Sdim case S_None: 1192251662Sdim llvm_unreachable("This should have been handled earlier."); 1193251662Sdim } 1194251662Sdim} 1195251662Sdim 1196251662Sdim/// If we have a Top Down pointer in the S_CanRelease state, make sure that 1197251662Sdim/// there are no CFG hazards by checking the states of various bottom up 1198251662Sdim/// pointers. 1199251662Sdimstatic void CheckForCanReleaseCFGHazard(const Sequence SuccSSeq, 1200251662Sdim const bool SuccSRRIKnownSafe, 1201288943Sdim TopDownPtrState &S, 1202251662Sdim bool &SomeSuccHasSame, 1203261991Sdim bool &AllSuccsHaveSame, 1204261991Sdim bool &NotAllSeqEqualButKnownSafe) { 1205251662Sdim switch (SuccSSeq) { 1206251662Sdim case S_CanRelease: 1207251662Sdim SomeSuccHasSame = true; 1208251662Sdim break; 1209251662Sdim case S_Stop: 1210251662Sdim case S_Release: 1211251662Sdim case S_MovableRelease: 1212251662Sdim case S_Use: 1213261991Sdim if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) 1214251662Sdim AllSuccsHaveSame = false; 1215261991Sdim else 1216261991Sdim NotAllSeqEqualButKnownSafe = true; 1217251662Sdim break; 1218251662Sdim case S_Retain: 1219251662Sdim llvm_unreachable("bottom-up pointer in retain state!"); 1220251662Sdim case S_None: 1221251662Sdim llvm_unreachable("This should have been handled earlier."); 1222251662Sdim } 1223251662Sdim} 1224251662Sdim 1225249259Sdim/// Check for critical edges, loop boundaries, irreducible control flow, or 1226249259Sdim/// other CFG structures where moving code across the edge would result in it 1227249259Sdim/// being executed more. 1228249259Sdimvoid 1229249259SdimObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB, 1230249259Sdim DenseMap<const BasicBlock *, BBState> &BBStates, 1231249259Sdim BBState &MyStates) const { 1232249259Sdim // If any top-down local-use or possible-dec has a succ which is earlier in 1233249259Sdim // the sequence, forget it. 1234288943Sdim for (auto I = MyStates.top_down_ptr_begin(), E = MyStates.top_down_ptr_end(); 1235288943Sdim I != E; ++I) { 1236288943Sdim TopDownPtrState &S = I->second; 1237251662Sdim const Sequence Seq = I->second.GetSeq(); 1238249259Sdim 1239251662Sdim // We only care about S_Retain, S_CanRelease, and S_Use. 1240251662Sdim if (Seq == S_None) 1241251662Sdim continue; 1242251662Sdim 1243251662Sdim // Make sure that if extra top down states are added in the future that this 1244251662Sdim // code is updated to handle it. 1245251662Sdim assert((Seq == S_Retain || Seq == S_CanRelease || Seq == S_Use) && 1246251662Sdim "Unknown top down sequence state."); 1247251662Sdim 1248251662Sdim const Value *Arg = I->first; 1249251662Sdim bool SomeSuccHasSame = false; 1250251662Sdim bool AllSuccsHaveSame = true; 1251261991Sdim bool NotAllSeqEqualButKnownSafe = false; 1252251662Sdim 1253344779Sdim for (const BasicBlock *Succ : successors(BB)) { 1254251662Sdim // If VisitBottomUp has pointer information for this successor, take 1255251662Sdim // what we know about it. 1256251662Sdim const DenseMap<const BasicBlock *, BBState>::iterator BBI = 1257344779Sdim BBStates.find(Succ); 1258251662Sdim assert(BBI != BBStates.end()); 1259288943Sdim const BottomUpPtrState &SuccS = BBI->second.getPtrBottomUpState(Arg); 1260251662Sdim const Sequence SuccSSeq = SuccS.GetSeq(); 1261251662Sdim 1262251662Sdim // If bottom up, the pointer is in an S_None state, clear the sequence 1263251662Sdim // progress since the sequence in the bottom up state finished 1264251662Sdim // suggesting a mismatch in between retains/releases. This is true for 1265251662Sdim // all three cases that we are handling here: S_Retain, S_Use, and 1266251662Sdim // S_CanRelease. 1267251662Sdim if (SuccSSeq == S_None) { 1268251662Sdim S.ClearSequenceProgress(); 1269251662Sdim continue; 1270249259Sdim } 1271249259Sdim 1272251662Sdim // If we have S_Use or S_CanRelease, perform our check for cfg hazard 1273251662Sdim // checks. 1274261991Sdim const bool SuccSRRIKnownSafe = SuccS.IsKnownSafe(); 1275251662Sdim 1276251662Sdim // *NOTE* We do not use Seq from above here since we are allowing for 1277251662Sdim // S.GetSeq() to change while we are visiting basic blocks. 1278251662Sdim switch(S.GetSeq()) { 1279251662Sdim case S_Use: { 1280251662Sdim bool ShouldContinue = false; 1281261991Sdim CheckForUseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S, SomeSuccHasSame, 1282261991Sdim AllSuccsHaveSame, NotAllSeqEqualButKnownSafe, 1283251662Sdim ShouldContinue); 1284251662Sdim if (ShouldContinue) 1285249259Sdim continue; 1286251662Sdim break; 1287249259Sdim } 1288327952Sdim case S_CanRelease: 1289261991Sdim CheckForCanReleaseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S, 1290261991Sdim SomeSuccHasSame, AllSuccsHaveSame, 1291261991Sdim NotAllSeqEqualButKnownSafe); 1292251662Sdim break; 1293251662Sdim case S_Retain: 1294251662Sdim case S_None: 1295251662Sdim case S_Stop: 1296251662Sdim case S_Release: 1297251662Sdim case S_MovableRelease: 1298251662Sdim break; 1299251662Sdim } 1300249259Sdim } 1301251662Sdim 1302251662Sdim // If the state at the other end of any of the successor edges 1303251662Sdim // matches the current state, require all edges to match. This 1304251662Sdim // guards against loops in the middle of a sequence. 1305261991Sdim if (SomeSuccHasSame && !AllSuccsHaveSame) { 1306251662Sdim S.ClearSequenceProgress(); 1307261991Sdim } else if (NotAllSeqEqualButKnownSafe) { 1308261991Sdim // If we would have cleared the state foregoing the fact that we are known 1309261991Sdim // safe, stop code motion. This is because whether or not it is safe to 1310261991Sdim // remove RR pairs via KnownSafe is an orthogonal concept to whether we 1311261991Sdim // are allowed to perform code motion. 1312261991Sdim S.SetCFGHazardAfflicted(true); 1313261991Sdim } 1314251662Sdim } 1315249259Sdim} 1316249259Sdim 1317288943Sdimbool ObjCARCOpt::VisitInstructionBottomUp( 1318288943Sdim Instruction *Inst, BasicBlock *BB, BlotMapVector<Value *, RRInfo> &Retains, 1319288943Sdim BBState &MyStates) { 1320249259Sdim bool NestingDetected = false; 1321288943Sdim ARCInstKind Class = GetARCInstKind(Inst); 1322276479Sdim const Value *Arg = nullptr; 1323249259Sdim 1324341825Sdim LLVM_DEBUG(dbgs() << " Class: " << Class << "\n"); 1325251662Sdim 1326249259Sdim switch (Class) { 1327288943Sdim case ARCInstKind::Release: { 1328288943Sdim Arg = GetArgRCIdentityRoot(Inst); 1329249259Sdim 1330288943Sdim BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg); 1331288943Sdim NestingDetected |= S.InitBottomUp(MDKindCache, Inst); 1332249259Sdim break; 1333249259Sdim } 1334288943Sdim case ARCInstKind::RetainBlock: 1335249259Sdim // In OptimizeIndividualCalls, we have strength reduced all optimizable 1336249259Sdim // objc_retainBlocks to objc_retains. Thus at this point any 1337249259Sdim // objc_retainBlocks that we see are not optimizable. 1338249259Sdim break; 1339288943Sdim case ARCInstKind::Retain: 1340288943Sdim case ARCInstKind::RetainRV: { 1341288943Sdim Arg = GetArgRCIdentityRoot(Inst); 1342288943Sdim BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg); 1343288943Sdim if (S.MatchWithRetain()) { 1344288943Sdim // Don't do retain+release tracking for ARCInstKind::RetainRV, because 1345288943Sdim // it's better to let it remain as the first instruction after a call. 1346288943Sdim if (Class != ARCInstKind::RetainRV) { 1347341825Sdim LLVM_DEBUG(dbgs() << " Matching with: " << *Inst << "\n"); 1348261991Sdim Retains[Inst] = S.GetRRInfo(); 1349288943Sdim } 1350249259Sdim S.ClearSequenceProgress(); 1351249259Sdim } 1352251662Sdim // A retain moving bottom up can be a use. 1353251662Sdim break; 1354249259Sdim } 1355288943Sdim case ARCInstKind::AutoreleasepoolPop: 1356249259Sdim // Conservatively, clear MyStates for all known pointers. 1357249259Sdim MyStates.clearBottomUpPointers(); 1358249259Sdim return NestingDetected; 1359288943Sdim case ARCInstKind::AutoreleasepoolPush: 1360288943Sdim case ARCInstKind::None: 1361249259Sdim // These are irrelevant. 1362249259Sdim return NestingDetected; 1363249259Sdim default: 1364249259Sdim break; 1365249259Sdim } 1366249259Sdim 1367249259Sdim // Consider any other possible effects of this instruction on each 1368249259Sdim // pointer being tracked. 1369288943Sdim for (auto MI = MyStates.bottom_up_ptr_begin(), 1370288943Sdim ME = MyStates.bottom_up_ptr_end(); 1371288943Sdim MI != ME; ++MI) { 1372249259Sdim const Value *Ptr = MI->first; 1373249259Sdim if (Ptr == Arg) 1374249259Sdim continue; // Handled above. 1375288943Sdim BottomUpPtrState &S = MI->second; 1376249259Sdim 1377288943Sdim if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class)) 1378288943Sdim continue; 1379249259Sdim 1380288943Sdim S.HandlePotentialUse(BB, Inst, Ptr, PA, Class); 1381249259Sdim } 1382249259Sdim 1383249259Sdim return NestingDetected; 1384249259Sdim} 1385249259Sdim 1386288943Sdimbool ObjCARCOpt::VisitBottomUp(BasicBlock *BB, 1387288943Sdim DenseMap<const BasicBlock *, BBState> &BBStates, 1388288943Sdim BlotMapVector<Value *, RRInfo> &Retains) { 1389341825Sdim LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::VisitBottomUp ==\n"); 1390251662Sdim 1391249259Sdim bool NestingDetected = false; 1392249259Sdim BBState &MyStates = BBStates[BB]; 1393249259Sdim 1394249259Sdim // Merge the states from each successor to compute the initial state 1395249259Sdim // for the current block. 1396249259Sdim BBState::edge_iterator SI(MyStates.succ_begin()), 1397249259Sdim SE(MyStates.succ_end()); 1398249259Sdim if (SI != SE) { 1399249259Sdim const BasicBlock *Succ = *SI; 1400249259Sdim DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ); 1401249259Sdim assert(I != BBStates.end()); 1402249259Sdim MyStates.InitFromSucc(I->second); 1403249259Sdim ++SI; 1404249259Sdim for (; SI != SE; ++SI) { 1405249259Sdim Succ = *SI; 1406249259Sdim I = BBStates.find(Succ); 1407249259Sdim assert(I != BBStates.end()); 1408249259Sdim MyStates.MergeSucc(I->second); 1409249259Sdim } 1410249259Sdim } 1411249259Sdim 1412341825Sdim LLVM_DEBUG(dbgs() << "Before:\n" 1413341825Sdim << BBStates[BB] << "\n" 1414341825Sdim << "Performing Dataflow:\n"); 1415249259Sdim 1416249259Sdim // Visit all the instructions, bottom-up. 1417249259Sdim for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) { 1418296417Sdim Instruction *Inst = &*std::prev(I); 1419249259Sdim 1420249259Sdim // Invoke instructions are visited as part of their successors (below). 1421249259Sdim if (isa<InvokeInst>(Inst)) 1422249259Sdim continue; 1423249259Sdim 1424341825Sdim LLVM_DEBUG(dbgs() << " Visiting " << *Inst << "\n"); 1425249259Sdim 1426249259Sdim NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates); 1427353358Sdim 1428353358Sdim // Bail out if the number of pointers being tracked becomes too large so 1429353358Sdim // that this pass can complete in a reasonable amount of time. 1430353358Sdim if (MyStates.bottom_up_ptr_list_size() > MaxPtrStates) { 1431353358Sdim DisableRetainReleasePairing = true; 1432353358Sdim return false; 1433353358Sdim } 1434249259Sdim } 1435249259Sdim 1436249259Sdim // If there's a predecessor with an invoke, visit the invoke as if it were 1437249259Sdim // part of this block, since we can't insert code after an invoke in its own 1438249259Sdim // block, and we don't want to split critical edges. 1439249259Sdim for (BBState::edge_iterator PI(MyStates.pred_begin()), 1440249259Sdim PE(MyStates.pred_end()); PI != PE; ++PI) { 1441249259Sdim BasicBlock *Pred = *PI; 1442249259Sdim if (InvokeInst *II = dyn_cast<InvokeInst>(&Pred->back())) 1443249259Sdim NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates); 1444249259Sdim } 1445249259Sdim 1446341825Sdim LLVM_DEBUG(dbgs() << "\nFinal State:\n" << BBStates[BB] << "\n"); 1447249259Sdim 1448249259Sdim return NestingDetected; 1449249259Sdim} 1450249259Sdim 1451249259Sdimbool 1452249259SdimObjCARCOpt::VisitInstructionTopDown(Instruction *Inst, 1453249259Sdim DenseMap<Value *, RRInfo> &Releases, 1454249259Sdim BBState &MyStates) { 1455249259Sdim bool NestingDetected = false; 1456288943Sdim ARCInstKind Class = GetARCInstKind(Inst); 1457276479Sdim const Value *Arg = nullptr; 1458249259Sdim 1459341825Sdim LLVM_DEBUG(dbgs() << " Class: " << Class << "\n"); 1460288943Sdim 1461249259Sdim switch (Class) { 1462288943Sdim case ARCInstKind::RetainBlock: 1463249259Sdim // In OptimizeIndividualCalls, we have strength reduced all optimizable 1464249259Sdim // objc_retainBlocks to objc_retains. Thus at this point any 1465288943Sdim // objc_retainBlocks that we see are not optimizable. We need to break since 1466288943Sdim // a retain can be a potential use. 1467249259Sdim break; 1468288943Sdim case ARCInstKind::Retain: 1469288943Sdim case ARCInstKind::RetainRV: { 1470288943Sdim Arg = GetArgRCIdentityRoot(Inst); 1471288943Sdim TopDownPtrState &S = MyStates.getPtrTopDownState(Arg); 1472288943Sdim NestingDetected |= S.InitTopDown(Class, Inst); 1473296417Sdim // A retain can be a potential use; proceed to the generic checking 1474249259Sdim // code below. 1475249259Sdim break; 1476249259Sdim } 1477288943Sdim case ARCInstKind::Release: { 1478288943Sdim Arg = GetArgRCIdentityRoot(Inst); 1479288943Sdim TopDownPtrState &S = MyStates.getPtrTopDownState(Arg); 1480288943Sdim // Try to form a tentative pair in between this release instruction and the 1481288943Sdim // top down pointers that we are tracking. 1482288943Sdim if (S.MatchWithRelease(MDKindCache, Inst)) { 1483288943Sdim // If we succeed, copy S's RRInfo into the Release -> {Retain Set 1484288943Sdim // Map}. Then we clear S. 1485341825Sdim LLVM_DEBUG(dbgs() << " Matching with: " << *Inst << "\n"); 1486261991Sdim Releases[Inst] = S.GetRRInfo(); 1487249259Sdim S.ClearSequenceProgress(); 1488249259Sdim } 1489249259Sdim break; 1490249259Sdim } 1491288943Sdim case ARCInstKind::AutoreleasepoolPop: 1492249259Sdim // Conservatively, clear MyStates for all known pointers. 1493249259Sdim MyStates.clearTopDownPointers(); 1494288943Sdim return false; 1495288943Sdim case ARCInstKind::AutoreleasepoolPush: 1496288943Sdim case ARCInstKind::None: 1497288943Sdim // These can not be uses of 1498288943Sdim return false; 1499249259Sdim default: 1500249259Sdim break; 1501249259Sdim } 1502249259Sdim 1503249259Sdim // Consider any other possible effects of this instruction on each 1504249259Sdim // pointer being tracked. 1505288943Sdim for (auto MI = MyStates.top_down_ptr_begin(), 1506288943Sdim ME = MyStates.top_down_ptr_end(); 1507288943Sdim MI != ME; ++MI) { 1508249259Sdim const Value *Ptr = MI->first; 1509249259Sdim if (Ptr == Arg) 1510249259Sdim continue; // Handled above. 1511288943Sdim TopDownPtrState &S = MI->second; 1512288943Sdim if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class)) 1513288943Sdim continue; 1514249259Sdim 1515288943Sdim S.HandlePotentialUse(Inst, Ptr, PA, Class); 1516249259Sdim } 1517249259Sdim 1518249259Sdim return NestingDetected; 1519249259Sdim} 1520249259Sdim 1521249259Sdimbool 1522249259SdimObjCARCOpt::VisitTopDown(BasicBlock *BB, 1523249259Sdim DenseMap<const BasicBlock *, BBState> &BBStates, 1524249259Sdim DenseMap<Value *, RRInfo> &Releases) { 1525341825Sdim LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::VisitTopDown ==\n"); 1526249259Sdim bool NestingDetected = false; 1527249259Sdim BBState &MyStates = BBStates[BB]; 1528249259Sdim 1529249259Sdim // Merge the states from each predecessor to compute the initial state 1530249259Sdim // for the current block. 1531249259Sdim BBState::edge_iterator PI(MyStates.pred_begin()), 1532249259Sdim PE(MyStates.pred_end()); 1533249259Sdim if (PI != PE) { 1534249259Sdim const BasicBlock *Pred = *PI; 1535249259Sdim DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred); 1536249259Sdim assert(I != BBStates.end()); 1537249259Sdim MyStates.InitFromPred(I->second); 1538249259Sdim ++PI; 1539249259Sdim for (; PI != PE; ++PI) { 1540249259Sdim Pred = *PI; 1541249259Sdim I = BBStates.find(Pred); 1542249259Sdim assert(I != BBStates.end()); 1543249259Sdim MyStates.MergePred(I->second); 1544249259Sdim } 1545249259Sdim } 1546249259Sdim 1547341825Sdim LLVM_DEBUG(dbgs() << "Before:\n" 1548341825Sdim << BBStates[BB] << "\n" 1549341825Sdim << "Performing Dataflow:\n"); 1550249259Sdim 1551249259Sdim // Visit all the instructions, top-down. 1552296417Sdim for (Instruction &Inst : *BB) { 1553341825Sdim LLVM_DEBUG(dbgs() << " Visiting " << Inst << "\n"); 1554249259Sdim 1555296417Sdim NestingDetected |= VisitInstructionTopDown(&Inst, Releases, MyStates); 1556353358Sdim 1557353358Sdim // Bail out if the number of pointers being tracked becomes too large so 1558353358Sdim // that this pass can complete in a reasonable amount of time. 1559353358Sdim if (MyStates.top_down_ptr_list_size() > MaxPtrStates) { 1560353358Sdim DisableRetainReleasePairing = true; 1561353358Sdim return false; 1562353358Sdim } 1563249259Sdim } 1564249259Sdim 1565341825Sdim LLVM_DEBUG(dbgs() << "\nState Before Checking for CFG Hazards:\n" 1566341825Sdim << BBStates[BB] << "\n\n"); 1567249259Sdim CheckForCFGHazards(BB, BBStates, MyStates); 1568341825Sdim LLVM_DEBUG(dbgs() << "Final State:\n" << BBStates[BB] << "\n"); 1569249259Sdim return NestingDetected; 1570249259Sdim} 1571249259Sdim 1572249259Sdimstatic void 1573249259SdimComputePostOrders(Function &F, 1574249259Sdim SmallVectorImpl<BasicBlock *> &PostOrder, 1575249259Sdim SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder, 1576249259Sdim unsigned NoObjCARCExceptionsMDKind, 1577249259Sdim DenseMap<const BasicBlock *, BBState> &BBStates) { 1578249259Sdim /// The visited set, for doing DFS walks. 1579249259Sdim SmallPtrSet<BasicBlock *, 16> Visited; 1580249259Sdim 1581249259Sdim // Do DFS, computing the PostOrder. 1582249259Sdim SmallPtrSet<BasicBlock *, 16> OnStack; 1583249259Sdim SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack; 1584249259Sdim 1585249259Sdim // Functions always have exactly one entry block, and we don't have 1586249259Sdim // any other block that we treat like an entry block. 1587249259Sdim BasicBlock *EntryBB = &F.getEntryBlock(); 1588249259Sdim BBState &MyStates = BBStates[EntryBB]; 1589249259Sdim MyStates.SetAsEntry(); 1590344779Sdim Instruction *EntryTI = EntryBB->getTerminator(); 1591249259Sdim SuccStack.push_back(std::make_pair(EntryBB, succ_iterator(EntryTI))); 1592249259Sdim Visited.insert(EntryBB); 1593249259Sdim OnStack.insert(EntryBB); 1594249259Sdim do { 1595249259Sdim dfs_next_succ: 1596249259Sdim BasicBlock *CurrBB = SuccStack.back().first; 1597344779Sdim succ_iterator SE(CurrBB->getTerminator(), false); 1598249259Sdim 1599249259Sdim while (SuccStack.back().second != SE) { 1600249259Sdim BasicBlock *SuccBB = *SuccStack.back().second++; 1601280031Sdim if (Visited.insert(SuccBB).second) { 1602344779Sdim SuccStack.push_back( 1603344779Sdim std::make_pair(SuccBB, succ_iterator(SuccBB->getTerminator()))); 1604249259Sdim BBStates[CurrBB].addSucc(SuccBB); 1605249259Sdim BBState &SuccStates = BBStates[SuccBB]; 1606249259Sdim SuccStates.addPred(CurrBB); 1607249259Sdim OnStack.insert(SuccBB); 1608249259Sdim goto dfs_next_succ; 1609249259Sdim } 1610249259Sdim 1611249259Sdim if (!OnStack.count(SuccBB)) { 1612249259Sdim BBStates[CurrBB].addSucc(SuccBB); 1613249259Sdim BBStates[SuccBB].addPred(CurrBB); 1614249259Sdim } 1615249259Sdim } 1616249259Sdim OnStack.erase(CurrBB); 1617249259Sdim PostOrder.push_back(CurrBB); 1618249259Sdim SuccStack.pop_back(); 1619249259Sdim } while (!SuccStack.empty()); 1620249259Sdim 1621249259Sdim Visited.clear(); 1622249259Sdim 1623249259Sdim // Do reverse-CFG DFS, computing the reverse-CFG PostOrder. 1624249259Sdim // Functions may have many exits, and there also blocks which we treat 1625249259Sdim // as exits due to ignored edges. 1626249259Sdim SmallVector<std::pair<BasicBlock *, BBState::edge_iterator>, 16> PredStack; 1627296417Sdim for (BasicBlock &ExitBB : F) { 1628296417Sdim BBState &MyStates = BBStates[&ExitBB]; 1629249259Sdim if (!MyStates.isExit()) 1630249259Sdim continue; 1631249259Sdim 1632249259Sdim MyStates.SetAsExit(); 1633249259Sdim 1634296417Sdim PredStack.push_back(std::make_pair(&ExitBB, MyStates.pred_begin())); 1635296417Sdim Visited.insert(&ExitBB); 1636249259Sdim while (!PredStack.empty()) { 1637249259Sdim reverse_dfs_next_succ: 1638249259Sdim BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end(); 1639249259Sdim while (PredStack.back().second != PE) { 1640249259Sdim BasicBlock *BB = *PredStack.back().second++; 1641280031Sdim if (Visited.insert(BB).second) { 1642249259Sdim PredStack.push_back(std::make_pair(BB, BBStates[BB].pred_begin())); 1643249259Sdim goto reverse_dfs_next_succ; 1644249259Sdim } 1645249259Sdim } 1646249259Sdim ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first); 1647249259Sdim } 1648249259Sdim } 1649249259Sdim} 1650249259Sdim 1651249259Sdim// Visit the function both top-down and bottom-up. 1652288943Sdimbool ObjCARCOpt::Visit(Function &F, 1653288943Sdim DenseMap<const BasicBlock *, BBState> &BBStates, 1654288943Sdim BlotMapVector<Value *, RRInfo> &Retains, 1655288943Sdim DenseMap<Value *, RRInfo> &Releases) { 1656249259Sdim // Use reverse-postorder traversals, because we magically know that loops 1657249259Sdim // will be well behaved, i.e. they won't repeatedly call retain on a single 1658249259Sdim // pointer without doing a release. We can't use the ReversePostOrderTraversal 1659249259Sdim // class here because we want the reverse-CFG postorder to consider each 1660249259Sdim // function exit point, and we want to ignore selected cycle edges. 1661249259Sdim SmallVector<BasicBlock *, 16> PostOrder; 1662249259Sdim SmallVector<BasicBlock *, 16> ReverseCFGPostOrder; 1663249259Sdim ComputePostOrders(F, PostOrder, ReverseCFGPostOrder, 1664288943Sdim MDKindCache.get(ARCMDKindID::NoObjCARCExceptions), 1665249259Sdim BBStates); 1666249259Sdim 1667249259Sdim // Use reverse-postorder on the reverse CFG for bottom-up. 1668249259Sdim bool BottomUpNestingDetected = false; 1669353358Sdim for (BasicBlock *BB : llvm::reverse(ReverseCFGPostOrder)) { 1670309124Sdim BottomUpNestingDetected |= VisitBottomUp(BB, BBStates, Retains); 1671353358Sdim if (DisableRetainReleasePairing) 1672353358Sdim return false; 1673353358Sdim } 1674249259Sdim 1675249259Sdim // Use reverse-postorder for top-down. 1676249259Sdim bool TopDownNestingDetected = false; 1677353358Sdim for (BasicBlock *BB : llvm::reverse(PostOrder)) { 1678309124Sdim TopDownNestingDetected |= VisitTopDown(BB, BBStates, Releases); 1679353358Sdim if (DisableRetainReleasePairing) 1680353358Sdim return false; 1681353358Sdim } 1682249259Sdim 1683249259Sdim return TopDownNestingDetected && BottomUpNestingDetected; 1684249259Sdim} 1685249259Sdim 1686249259Sdim/// Move the calls in RetainsToMove and ReleasesToMove. 1687288943Sdimvoid ObjCARCOpt::MoveCalls(Value *Arg, RRInfo &RetainsToMove, 1688249259Sdim RRInfo &ReleasesToMove, 1689288943Sdim BlotMapVector<Value *, RRInfo> &Retains, 1690249259Sdim DenseMap<Value *, RRInfo> &Releases, 1691249259Sdim SmallVectorImpl<Instruction *> &DeadInsts, 1692249259Sdim Module *M) { 1693249259Sdim Type *ArgTy = Arg->getType(); 1694249259Sdim Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext())); 1695249259Sdim 1696341825Sdim LLVM_DEBUG(dbgs() << "== ObjCARCOpt::MoveCalls ==\n"); 1697251662Sdim 1698249259Sdim // Insert the new retain and release calls. 1699280031Sdim for (Instruction *InsertPt : ReleasesToMove.ReverseInsertPts) { 1700249259Sdim Value *MyArg = ArgTy == ParamTy ? Arg : 1701249259Sdim new BitCastInst(Arg, ParamTy, "", InsertPt); 1702353358Sdim Function *Decl = EP.get(ARCRuntimeEntryPointKind::Retain); 1703261991Sdim CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt); 1704249259Sdim Call->setDoesNotThrow(); 1705249259Sdim Call->setTailCall(); 1706249259Sdim 1707341825Sdim LLVM_DEBUG(dbgs() << "Inserting new Retain: " << *Call 1708341825Sdim << "\n" 1709341825Sdim "At insertion point: " 1710341825Sdim << *InsertPt << "\n"); 1711249259Sdim } 1712280031Sdim for (Instruction *InsertPt : RetainsToMove.ReverseInsertPts) { 1713249259Sdim Value *MyArg = ArgTy == ParamTy ? Arg : 1714249259Sdim new BitCastInst(Arg, ParamTy, "", InsertPt); 1715353358Sdim Function *Decl = EP.get(ARCRuntimeEntryPointKind::Release); 1716261991Sdim CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt); 1717249259Sdim // Attach a clang.imprecise_release metadata tag, if appropriate. 1718249259Sdim if (MDNode *M = ReleasesToMove.ReleaseMetadata) 1719288943Sdim Call->setMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease), M); 1720249259Sdim Call->setDoesNotThrow(); 1721249259Sdim if (ReleasesToMove.IsTailCallRelease) 1722249259Sdim Call->setTailCall(); 1723249259Sdim 1724341825Sdim LLVM_DEBUG(dbgs() << "Inserting new Release: " << *Call 1725341825Sdim << "\n" 1726341825Sdim "At insertion point: " 1727341825Sdim << *InsertPt << "\n"); 1728249259Sdim } 1729249259Sdim 1730249259Sdim // Delete the original retain and release calls. 1731280031Sdim for (Instruction *OrigRetain : RetainsToMove.Calls) { 1732249259Sdim Retains.blot(OrigRetain); 1733249259Sdim DeadInsts.push_back(OrigRetain); 1734341825Sdim LLVM_DEBUG(dbgs() << "Deleting retain: " << *OrigRetain << "\n"); 1735249259Sdim } 1736280031Sdim for (Instruction *OrigRelease : ReleasesToMove.Calls) { 1737249259Sdim Releases.erase(OrigRelease); 1738249259Sdim DeadInsts.push_back(OrigRelease); 1739341825Sdim LLVM_DEBUG(dbgs() << "Deleting release: " << *OrigRelease << "\n"); 1740249259Sdim } 1741249259Sdim} 1742249259Sdim 1743288943Sdimbool ObjCARCOpt::PairUpRetainsAndReleases( 1744288943Sdim DenseMap<const BasicBlock *, BBState> &BBStates, 1745288943Sdim BlotMapVector<Value *, RRInfo> &Retains, 1746288943Sdim DenseMap<Value *, RRInfo> &Releases, Module *M, 1747321369Sdim Instruction *Retain, 1748288943Sdim SmallVectorImpl<Instruction *> &DeadInsts, RRInfo &RetainsToMove, 1749288943Sdim RRInfo &ReleasesToMove, Value *Arg, bool KnownSafe, 1750288943Sdim bool &AnyPairsCompletelyEliminated) { 1751249259Sdim // If a pair happens in a region where it is known that the reference count 1752261991Sdim // is already incremented, we can similarly ignore possible decrements unless 1753261991Sdim // we are dealing with a retainable object with multiple provenance sources. 1754249259Sdim bool KnownSafeTD = true, KnownSafeBU = true; 1755261991Sdim bool CFGHazardAfflicted = false; 1756249259Sdim 1757249259Sdim // Connect the dots between the top-down-collected RetainsToMove and 1758249259Sdim // bottom-up-collected ReleasesToMove to form sets of related calls. 1759249259Sdim // This is an iterative process so that we connect multiple releases 1760249259Sdim // to multiple retains if needed. 1761249259Sdim unsigned OldDelta = 0; 1762249259Sdim unsigned NewDelta = 0; 1763249259Sdim unsigned OldCount = 0; 1764249259Sdim unsigned NewCount = 0; 1765249259Sdim bool FirstRelease = true; 1766321369Sdim for (SmallVector<Instruction *, 4> NewRetains{Retain};;) { 1767321369Sdim SmallVector<Instruction *, 4> NewReleases; 1768309124Sdim for (Instruction *NewRetain : NewRetains) { 1769288943Sdim auto It = Retains.find(NewRetain); 1770249259Sdim assert(It != Retains.end()); 1771249259Sdim const RRInfo &NewRetainRRI = It->second; 1772249259Sdim KnownSafeTD &= NewRetainRRI.KnownSafe; 1773341825Sdim CFGHazardAfflicted |= NewRetainRRI.CFGHazardAfflicted; 1774280031Sdim for (Instruction *NewRetainRelease : NewRetainRRI.Calls) { 1775288943Sdim auto Jt = Releases.find(NewRetainRelease); 1776249259Sdim if (Jt == Releases.end()) 1777249259Sdim return false; 1778249259Sdim const RRInfo &NewRetainReleaseRRI = Jt->second; 1779261991Sdim 1780261991Sdim // If the release does not have a reference to the retain as well, 1781261991Sdim // something happened which is unaccounted for. Do not do anything. 1782261991Sdim // 1783261991Sdim // This can happen if we catch an additive overflow during path count 1784261991Sdim // merging. 1785261991Sdim if (!NewRetainReleaseRRI.Calls.count(NewRetain)) 1786261991Sdim return false; 1787261991Sdim 1788280031Sdim if (ReleasesToMove.Calls.insert(NewRetainRelease).second) { 1789261991Sdim // If we overflow when we compute the path count, don't remove/move 1790261991Sdim // anything. 1791261991Sdim const BBState &NRRBBState = BBStates[NewRetainRelease->getParent()]; 1792261991Sdim unsigned PathCount = BBState::OverflowOccurredValue; 1793261991Sdim if (NRRBBState.GetAllPathCountWithOverflow(PathCount)) 1794261991Sdim return false; 1795261991Sdim assert(PathCount != BBState::OverflowOccurredValue && 1796261991Sdim "PathCount at this point can not be " 1797261991Sdim "OverflowOccurredValue."); 1798261991Sdim OldDelta -= PathCount; 1799261991Sdim 1800249259Sdim // Merge the ReleaseMetadata and IsTailCallRelease values. 1801249259Sdim if (FirstRelease) { 1802249259Sdim ReleasesToMove.ReleaseMetadata = 1803249259Sdim NewRetainReleaseRRI.ReleaseMetadata; 1804249259Sdim ReleasesToMove.IsTailCallRelease = 1805249259Sdim NewRetainReleaseRRI.IsTailCallRelease; 1806249259Sdim FirstRelease = false; 1807249259Sdim } else { 1808249259Sdim if (ReleasesToMove.ReleaseMetadata != 1809249259Sdim NewRetainReleaseRRI.ReleaseMetadata) 1810276479Sdim ReleasesToMove.ReleaseMetadata = nullptr; 1811249259Sdim if (ReleasesToMove.IsTailCallRelease != 1812249259Sdim NewRetainReleaseRRI.IsTailCallRelease) 1813249259Sdim ReleasesToMove.IsTailCallRelease = false; 1814249259Sdim } 1815249259Sdim 1816249259Sdim // Collect the optimal insertion points. 1817249259Sdim if (!KnownSafe) 1818280031Sdim for (Instruction *RIP : NewRetainReleaseRRI.ReverseInsertPts) { 1819280031Sdim if (ReleasesToMove.ReverseInsertPts.insert(RIP).second) { 1820261991Sdim // If we overflow when we compute the path count, don't 1821261991Sdim // remove/move anything. 1822261991Sdim const BBState &RIPBBState = BBStates[RIP->getParent()]; 1823261991Sdim PathCount = BBState::OverflowOccurredValue; 1824261991Sdim if (RIPBBState.GetAllPathCountWithOverflow(PathCount)) 1825261991Sdim return false; 1826261991Sdim assert(PathCount != BBState::OverflowOccurredValue && 1827261991Sdim "PathCount at this point can not be " 1828261991Sdim "OverflowOccurredValue."); 1829261991Sdim NewDelta -= PathCount; 1830261991Sdim } 1831249259Sdim } 1832249259Sdim NewReleases.push_back(NewRetainRelease); 1833249259Sdim } 1834249259Sdim } 1835249259Sdim } 1836249259Sdim NewRetains.clear(); 1837249259Sdim if (NewReleases.empty()) break; 1838249259Sdim 1839249259Sdim // Back the other way. 1840309124Sdim for (Instruction *NewRelease : NewReleases) { 1841288943Sdim auto It = Releases.find(NewRelease); 1842249259Sdim assert(It != Releases.end()); 1843249259Sdim const RRInfo &NewReleaseRRI = It->second; 1844249259Sdim KnownSafeBU &= NewReleaseRRI.KnownSafe; 1845261991Sdim CFGHazardAfflicted |= NewReleaseRRI.CFGHazardAfflicted; 1846280031Sdim for (Instruction *NewReleaseRetain : NewReleaseRRI.Calls) { 1847288943Sdim auto Jt = Retains.find(NewReleaseRetain); 1848249259Sdim if (Jt == Retains.end()) 1849249259Sdim return false; 1850249259Sdim const RRInfo &NewReleaseRetainRRI = Jt->second; 1851261991Sdim 1852261991Sdim // If the retain does not have a reference to the release as well, 1853261991Sdim // something happened which is unaccounted for. Do not do anything. 1854261991Sdim // 1855261991Sdim // This can happen if we catch an additive overflow during path count 1856261991Sdim // merging. 1857261991Sdim if (!NewReleaseRetainRRI.Calls.count(NewRelease)) 1858261991Sdim return false; 1859261991Sdim 1860280031Sdim if (RetainsToMove.Calls.insert(NewReleaseRetain).second) { 1861261991Sdim // If we overflow when we compute the path count, don't remove/move 1862261991Sdim // anything. 1863261991Sdim const BBState &NRRBBState = BBStates[NewReleaseRetain->getParent()]; 1864261991Sdim unsigned PathCount = BBState::OverflowOccurredValue; 1865261991Sdim if (NRRBBState.GetAllPathCountWithOverflow(PathCount)) 1866261991Sdim return false; 1867261991Sdim assert(PathCount != BBState::OverflowOccurredValue && 1868261991Sdim "PathCount at this point can not be " 1869261991Sdim "OverflowOccurredValue."); 1870249259Sdim OldDelta += PathCount; 1871249259Sdim OldCount += PathCount; 1872249259Sdim 1873249259Sdim // Collect the optimal insertion points. 1874249259Sdim if (!KnownSafe) 1875280031Sdim for (Instruction *RIP : NewReleaseRetainRRI.ReverseInsertPts) { 1876280031Sdim if (RetainsToMove.ReverseInsertPts.insert(RIP).second) { 1877261991Sdim // If we overflow when we compute the path count, don't 1878261991Sdim // remove/move anything. 1879261991Sdim const BBState &RIPBBState = BBStates[RIP->getParent()]; 1880261991Sdim 1881261991Sdim PathCount = BBState::OverflowOccurredValue; 1882261991Sdim if (RIPBBState.GetAllPathCountWithOverflow(PathCount)) 1883261991Sdim return false; 1884261991Sdim assert(PathCount != BBState::OverflowOccurredValue && 1885261991Sdim "PathCount at this point can not be " 1886261991Sdim "OverflowOccurredValue."); 1887249259Sdim NewDelta += PathCount; 1888249259Sdim NewCount += PathCount; 1889249259Sdim } 1890249259Sdim } 1891249259Sdim NewRetains.push_back(NewReleaseRetain); 1892249259Sdim } 1893249259Sdim } 1894249259Sdim } 1895249259Sdim if (NewRetains.empty()) break; 1896249259Sdim } 1897249259Sdim 1898288943Sdim // We can only remove pointers if we are known safe in both directions. 1899288943Sdim bool UnconditionallySafe = KnownSafeTD && KnownSafeBU; 1900261991Sdim if (UnconditionallySafe) { 1901249259Sdim RetainsToMove.ReverseInsertPts.clear(); 1902249259Sdim ReleasesToMove.ReverseInsertPts.clear(); 1903249259Sdim NewCount = 0; 1904249259Sdim } else { 1905249259Sdim // Determine whether the new insertion points we computed preserve the 1906249259Sdim // balance of retain and release calls through the program. 1907249259Sdim // TODO: If the fully aggressive solution isn't valid, try to find a 1908249259Sdim // less aggressive solution which is. 1909249259Sdim if (NewDelta != 0) 1910249259Sdim return false; 1911261991Sdim 1912261991Sdim // At this point, we are not going to remove any RR pairs, but we still are 1913261991Sdim // able to move RR pairs. If one of our pointers is afflicted with 1914261991Sdim // CFGHazards, we cannot perform such code motion so exit early. 1915327952Sdim const bool WillPerformCodeMotion = 1916327952Sdim !RetainsToMove.ReverseInsertPts.empty() || 1917327952Sdim !ReleasesToMove.ReverseInsertPts.empty(); 1918261991Sdim if (CFGHazardAfflicted && WillPerformCodeMotion) 1919261991Sdim return false; 1920249259Sdim } 1921249259Sdim 1922249259Sdim // Determine whether the original call points are balanced in the retain and 1923249259Sdim // release calls through the program. If not, conservatively don't touch 1924249259Sdim // them. 1925249259Sdim // TODO: It's theoretically possible to do code motion in this case, as 1926249259Sdim // long as the existing imbalances are maintained. 1927249259Sdim if (OldDelta != 0) 1928249259Sdim return false; 1929249259Sdim 1930249259Sdim Changed = true; 1931249259Sdim assert(OldCount != 0 && "Unreachable code?"); 1932249259Sdim NumRRs += OldCount - NewCount; 1933249259Sdim // Set to true if we completely removed any RR pairs. 1934249259Sdim AnyPairsCompletelyEliminated = NewCount == 0; 1935249259Sdim 1936249259Sdim // We can move calls! 1937249259Sdim return true; 1938249259Sdim} 1939249259Sdim 1940249259Sdim/// Identify pairings between the retains and releases, and delete and/or move 1941249259Sdim/// them. 1942288943Sdimbool ObjCARCOpt::PerformCodePlacement( 1943288943Sdim DenseMap<const BasicBlock *, BBState> &BBStates, 1944288943Sdim BlotMapVector<Value *, RRInfo> &Retains, 1945288943Sdim DenseMap<Value *, RRInfo> &Releases, Module *M) { 1946341825Sdim LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::PerformCodePlacement ==\n"); 1947251662Sdim 1948249259Sdim bool AnyPairsCompletelyEliminated = false; 1949249259Sdim SmallVector<Instruction *, 8> DeadInsts; 1950249259Sdim 1951249259Sdim // Visit each retain. 1952288943Sdim for (BlotMapVector<Value *, RRInfo>::const_iterator I = Retains.begin(), 1953288943Sdim E = Retains.end(); 1954288943Sdim I != E; ++I) { 1955249259Sdim Value *V = I->first; 1956249259Sdim if (!V) continue; // blotted 1957249259Sdim 1958249259Sdim Instruction *Retain = cast<Instruction>(V); 1959249259Sdim 1960341825Sdim LLVM_DEBUG(dbgs() << "Visiting: " << *Retain << "\n"); 1961249259Sdim 1962288943Sdim Value *Arg = GetArgRCIdentityRoot(Retain); 1963249259Sdim 1964249259Sdim // If the object being released is in static or stack storage, we know it's 1965249259Sdim // not being managed by ObjC reference counting, so we can delete pairs 1966249259Sdim // regardless of what possible decrements or uses lie between them. 1967249259Sdim bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg); 1968249259Sdim 1969249259Sdim // A constant pointer can't be pointing to an object on the heap. It may 1970249259Sdim // be reference-counted, but it won't be deleted. 1971249259Sdim if (const LoadInst *LI = dyn_cast<LoadInst>(Arg)) 1972249259Sdim if (const GlobalVariable *GV = 1973249259Sdim dyn_cast<GlobalVariable>( 1974288943Sdim GetRCIdentityRoot(LI->getPointerOperand()))) 1975249259Sdim if (GV->isConstant()) 1976249259Sdim KnownSafe = true; 1977249259Sdim 1978249259Sdim // Connect the dots between the top-down-collected RetainsToMove and 1979249259Sdim // bottom-up-collected ReleasesToMove to form sets of related calls. 1980321369Sdim RRInfo RetainsToMove, ReleasesToMove; 1981321369Sdim 1982288943Sdim bool PerformMoveCalls = PairUpRetainsAndReleases( 1983321369Sdim BBStates, Retains, Releases, M, Retain, DeadInsts, 1984288943Sdim RetainsToMove, ReleasesToMove, Arg, KnownSafe, 1985288943Sdim AnyPairsCompletelyEliminated); 1986249259Sdim 1987249259Sdim if (PerformMoveCalls) { 1988249259Sdim // Ok, everything checks out and we're all set. Let's move/delete some 1989249259Sdim // code! 1990249259Sdim MoveCalls(Arg, RetainsToMove, ReleasesToMove, 1991249259Sdim Retains, Releases, DeadInsts, M); 1992249259Sdim } 1993249259Sdim } 1994249259Sdim 1995249259Sdim // Now that we're done moving everything, we can delete the newly dead 1996249259Sdim // instructions, as we no longer need them as insert points. 1997249259Sdim while (!DeadInsts.empty()) 1998249259Sdim EraseInstruction(DeadInsts.pop_back_val()); 1999249259Sdim 2000249259Sdim return AnyPairsCompletelyEliminated; 2001249259Sdim} 2002249259Sdim 2003249259Sdim/// Weak pointer optimizations. 2004249259Sdimvoid ObjCARCOpt::OptimizeWeakCalls(Function &F) { 2005341825Sdim LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeWeakCalls ==\n"); 2006251662Sdim 2007249259Sdim // First, do memdep-style RLE and S2L optimizations. We can't use memdep 2008249259Sdim // itself because it uses AliasAnalysis and we need to do provenance 2009249259Sdim // queries instead. 2010249259Sdim for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { 2011249259Sdim Instruction *Inst = &*I++; 2012249259Sdim 2013341825Sdim LLVM_DEBUG(dbgs() << "Visiting: " << *Inst << "\n"); 2014249259Sdim 2015288943Sdim ARCInstKind Class = GetBasicARCInstKind(Inst); 2016288943Sdim if (Class != ARCInstKind::LoadWeak && 2017288943Sdim Class != ARCInstKind::LoadWeakRetained) 2018249259Sdim continue; 2019249259Sdim 2020249259Sdim // Delete objc_loadWeak calls with no users. 2021288943Sdim if (Class == ARCInstKind::LoadWeak && Inst->use_empty()) { 2022249259Sdim Inst->eraseFromParent(); 2023249259Sdim continue; 2024249259Sdim } 2025249259Sdim 2026249259Sdim // TODO: For now, just look for an earlier available version of this value 2027249259Sdim // within the same block. Theoretically, we could do memdep-style non-local 2028249259Sdim // analysis too, but that would want caching. A better approach would be to 2029249259Sdim // use the technique that EarlyCSE uses. 2030276479Sdim inst_iterator Current = std::prev(I); 2031296417Sdim BasicBlock *CurrentBB = &*Current.getBasicBlockIterator(); 2032249259Sdim for (BasicBlock::iterator B = CurrentBB->begin(), 2033249259Sdim J = Current.getInstructionIterator(); 2034249259Sdim J != B; --J) { 2035276479Sdim Instruction *EarlierInst = &*std::prev(J); 2036288943Sdim ARCInstKind EarlierClass = GetARCInstKind(EarlierInst); 2037249259Sdim switch (EarlierClass) { 2038288943Sdim case ARCInstKind::LoadWeak: 2039288943Sdim case ARCInstKind::LoadWeakRetained: { 2040249259Sdim // If this is loading from the same pointer, replace this load's value 2041249259Sdim // with that one. 2042249259Sdim CallInst *Call = cast<CallInst>(Inst); 2043249259Sdim CallInst *EarlierCall = cast<CallInst>(EarlierInst); 2044249259Sdim Value *Arg = Call->getArgOperand(0); 2045249259Sdim Value *EarlierArg = EarlierCall->getArgOperand(0); 2046249259Sdim switch (PA.getAA()->alias(Arg, EarlierArg)) { 2047288943Sdim case MustAlias: 2048249259Sdim Changed = true; 2049249259Sdim // If the load has a builtin retain, insert a plain retain for it. 2050288943Sdim if (Class == ARCInstKind::LoadWeakRetained) { 2051353358Sdim Function *Decl = EP.get(ARCRuntimeEntryPointKind::Retain); 2052261991Sdim CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call); 2053249259Sdim CI->setTailCall(); 2054249259Sdim } 2055249259Sdim // Zap the fully redundant load. 2056249259Sdim Call->replaceAllUsesWith(EarlierCall); 2057249259Sdim Call->eraseFromParent(); 2058249259Sdim goto clobbered; 2059288943Sdim case MayAlias: 2060288943Sdim case PartialAlias: 2061249259Sdim goto clobbered; 2062288943Sdim case NoAlias: 2063249259Sdim break; 2064249259Sdim } 2065249259Sdim break; 2066249259Sdim } 2067288943Sdim case ARCInstKind::StoreWeak: 2068288943Sdim case ARCInstKind::InitWeak: { 2069249259Sdim // If this is storing to the same pointer and has the same size etc. 2070249259Sdim // replace this load's value with the stored value. 2071249259Sdim CallInst *Call = cast<CallInst>(Inst); 2072249259Sdim CallInst *EarlierCall = cast<CallInst>(EarlierInst); 2073249259Sdim Value *Arg = Call->getArgOperand(0); 2074249259Sdim Value *EarlierArg = EarlierCall->getArgOperand(0); 2075249259Sdim switch (PA.getAA()->alias(Arg, EarlierArg)) { 2076288943Sdim case MustAlias: 2077249259Sdim Changed = true; 2078249259Sdim // If the load has a builtin retain, insert a plain retain for it. 2079288943Sdim if (Class == ARCInstKind::LoadWeakRetained) { 2080353358Sdim Function *Decl = EP.get(ARCRuntimeEntryPointKind::Retain); 2081261991Sdim CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call); 2082249259Sdim CI->setTailCall(); 2083249259Sdim } 2084249259Sdim // Zap the fully redundant load. 2085249259Sdim Call->replaceAllUsesWith(EarlierCall->getArgOperand(1)); 2086249259Sdim Call->eraseFromParent(); 2087249259Sdim goto clobbered; 2088288943Sdim case MayAlias: 2089288943Sdim case PartialAlias: 2090249259Sdim goto clobbered; 2091288943Sdim case NoAlias: 2092249259Sdim break; 2093249259Sdim } 2094249259Sdim break; 2095249259Sdim } 2096288943Sdim case ARCInstKind::MoveWeak: 2097288943Sdim case ARCInstKind::CopyWeak: 2098249259Sdim // TOOD: Grab the copied value. 2099249259Sdim goto clobbered; 2100288943Sdim case ARCInstKind::AutoreleasepoolPush: 2101288943Sdim case ARCInstKind::None: 2102288943Sdim case ARCInstKind::IntrinsicUser: 2103288943Sdim case ARCInstKind::User: 2104249259Sdim // Weak pointers are only modified through the weak entry points 2105249259Sdim // (and arbitrary calls, which could call the weak entry points). 2106249259Sdim break; 2107249259Sdim default: 2108249259Sdim // Anything else could modify the weak pointer. 2109249259Sdim goto clobbered; 2110249259Sdim } 2111249259Sdim } 2112249259Sdim clobbered:; 2113249259Sdim } 2114249259Sdim 2115249259Sdim // Then, for each destroyWeak with an alloca operand, check to see if 2116249259Sdim // the alloca and all its users can be zapped. 2117249259Sdim for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { 2118249259Sdim Instruction *Inst = &*I++; 2119288943Sdim ARCInstKind Class = GetBasicARCInstKind(Inst); 2120288943Sdim if (Class != ARCInstKind::DestroyWeak) 2121249259Sdim continue; 2122249259Sdim 2123249259Sdim CallInst *Call = cast<CallInst>(Inst); 2124249259Sdim Value *Arg = Call->getArgOperand(0); 2125249259Sdim if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) { 2126276479Sdim for (User *U : Alloca->users()) { 2127276479Sdim const Instruction *UserInst = cast<Instruction>(U); 2128288943Sdim switch (GetBasicARCInstKind(UserInst)) { 2129288943Sdim case ARCInstKind::InitWeak: 2130288943Sdim case ARCInstKind::StoreWeak: 2131288943Sdim case ARCInstKind::DestroyWeak: 2132249259Sdim continue; 2133249259Sdim default: 2134249259Sdim goto done; 2135249259Sdim } 2136249259Sdim } 2137249259Sdim Changed = true; 2138276479Sdim for (auto UI = Alloca->user_begin(), UE = Alloca->user_end(); UI != UE;) { 2139249259Sdim CallInst *UserInst = cast<CallInst>(*UI++); 2140288943Sdim switch (GetBasicARCInstKind(UserInst)) { 2141288943Sdim case ARCInstKind::InitWeak: 2142288943Sdim case ARCInstKind::StoreWeak: 2143249259Sdim // These functions return their second argument. 2144249259Sdim UserInst->replaceAllUsesWith(UserInst->getArgOperand(1)); 2145249259Sdim break; 2146288943Sdim case ARCInstKind::DestroyWeak: 2147249259Sdim // No return value. 2148249259Sdim break; 2149249259Sdim default: 2150249259Sdim llvm_unreachable("alloca really is used!"); 2151249259Sdim } 2152249259Sdim UserInst->eraseFromParent(); 2153249259Sdim } 2154249259Sdim Alloca->eraseFromParent(); 2155249259Sdim done:; 2156249259Sdim } 2157249259Sdim } 2158249259Sdim} 2159249259Sdim 2160249259Sdim/// Identify program paths which execute sequences of retains and releases which 2161249259Sdim/// can be eliminated. 2162249259Sdimbool ObjCARCOpt::OptimizeSequences(Function &F) { 2163261991Sdim // Releases, Retains - These are used to store the results of the main flow 2164261991Sdim // analysis. These use Value* as the key instead of Instruction* so that the 2165261991Sdim // map stays valid when we get around to rewriting code and calls get 2166261991Sdim // replaced by arguments. 2167249259Sdim DenseMap<Value *, RRInfo> Releases; 2168288943Sdim BlotMapVector<Value *, RRInfo> Retains; 2169249259Sdim 2170261991Sdim // This is used during the traversal of the function to track the 2171261991Sdim // states for each identified object at each block. 2172249259Sdim DenseMap<const BasicBlock *, BBState> BBStates; 2173249259Sdim 2174249259Sdim // Analyze the CFG of the function, and all instructions. 2175249259Sdim bool NestingDetected = Visit(F, BBStates, Retains, Releases); 2176249259Sdim 2177353358Sdim if (DisableRetainReleasePairing) 2178353358Sdim return false; 2179353358Sdim 2180249259Sdim // Transform. 2181261991Sdim bool AnyPairsCompletelyEliminated = PerformCodePlacement(BBStates, Retains, 2182261991Sdim Releases, 2183261991Sdim F.getParent()); 2184261991Sdim 2185261991Sdim return AnyPairsCompletelyEliminated && NestingDetected; 2186249259Sdim} 2187249259Sdim 2188249259Sdim/// Check if there is a dependent call earlier that does not have anything in 2189249259Sdim/// between the Retain and the call that can affect the reference count of their 2190249259Sdim/// shared pointer argument. Note that Retain need not be in BB. 2191249259Sdimstatic bool 2192249259SdimHasSafePathToPredecessorCall(const Value *Arg, Instruction *Retain, 2193280031Sdim SmallPtrSetImpl<Instruction *> &DepInsts, 2194280031Sdim SmallPtrSetImpl<const BasicBlock *> &Visited, 2195249259Sdim ProvenanceAnalysis &PA) { 2196249259Sdim FindDependencies(CanChangeRetainCount, Arg, Retain->getParent(), Retain, 2197249259Sdim DepInsts, Visited, PA); 2198249259Sdim if (DepInsts.size() != 1) 2199249259Sdim return false; 2200249259Sdim 2201288943Sdim auto *Call = dyn_cast_or_null<CallInst>(*DepInsts.begin()); 2202249259Sdim 2203249259Sdim // Check that the pointer is the return value of the call. 2204249259Sdim if (!Call || Arg != Call) 2205249259Sdim return false; 2206249259Sdim 2207249259Sdim // Check that the call is a regular call. 2208288943Sdim ARCInstKind Class = GetBasicARCInstKind(Call); 2209296417Sdim return Class == ARCInstKind::CallOrUser || Class == ARCInstKind::Call; 2210249259Sdim} 2211249259Sdim 2212249259Sdim/// Find a dependent retain that precedes the given autorelease for which there 2213249259Sdim/// is nothing in between the two instructions that can affect the ref count of 2214249259Sdim/// Arg. 2215249259Sdimstatic CallInst * 2216249259SdimFindPredecessorRetainWithSafePath(const Value *Arg, BasicBlock *BB, 2217249259Sdim Instruction *Autorelease, 2218280031Sdim SmallPtrSetImpl<Instruction *> &DepInsts, 2219280031Sdim SmallPtrSetImpl<const BasicBlock *> &Visited, 2220249259Sdim ProvenanceAnalysis &PA) { 2221249259Sdim FindDependencies(CanChangeRetainCount, Arg, 2222249259Sdim BB, Autorelease, DepInsts, Visited, PA); 2223249259Sdim if (DepInsts.size() != 1) 2224276479Sdim return nullptr; 2225251662Sdim 2226288943Sdim auto *Retain = dyn_cast_or_null<CallInst>(*DepInsts.begin()); 2227251662Sdim 2228249259Sdim // Check that we found a retain with the same argument. 2229288943Sdim if (!Retain || !IsRetain(GetBasicARCInstKind(Retain)) || 2230288943Sdim GetArgRCIdentityRoot(Retain) != Arg) { 2231276479Sdim return nullptr; 2232249259Sdim } 2233251662Sdim 2234249259Sdim return Retain; 2235249259Sdim} 2236249259Sdim 2237249259Sdim/// Look for an ``autorelease'' instruction dependent on Arg such that there are 2238249259Sdim/// no instructions dependent on Arg that need a positive ref count in between 2239249259Sdim/// the autorelease and the ret. 2240249259Sdimstatic CallInst * 2241249259SdimFindPredecessorAutoreleaseWithSafePath(const Value *Arg, BasicBlock *BB, 2242249259Sdim ReturnInst *Ret, 2243280031Sdim SmallPtrSetImpl<Instruction *> &DepInsts, 2244280031Sdim SmallPtrSetImpl<const BasicBlock *> &V, 2245249259Sdim ProvenanceAnalysis &PA) { 2246249259Sdim FindDependencies(NeedsPositiveRetainCount, Arg, 2247249259Sdim BB, Ret, DepInsts, V, PA); 2248249259Sdim if (DepInsts.size() != 1) 2249276479Sdim return nullptr; 2250251662Sdim 2251288943Sdim auto *Autorelease = dyn_cast_or_null<CallInst>(*DepInsts.begin()); 2252249259Sdim if (!Autorelease) 2253276479Sdim return nullptr; 2254288943Sdim ARCInstKind AutoreleaseClass = GetBasicARCInstKind(Autorelease); 2255249259Sdim if (!IsAutorelease(AutoreleaseClass)) 2256276479Sdim return nullptr; 2257288943Sdim if (GetArgRCIdentityRoot(Autorelease) != Arg) 2258276479Sdim return nullptr; 2259251662Sdim 2260249259Sdim return Autorelease; 2261249259Sdim} 2262249259Sdim 2263249259Sdim/// Look for this pattern: 2264249259Sdim/// \code 2265249259Sdim/// %call = call i8* @something(...) 2266249259Sdim/// %2 = call i8* @objc_retain(i8* %call) 2267249259Sdim/// %3 = call i8* @objc_autorelease(i8* %2) 2268249259Sdim/// ret i8* %3 2269249259Sdim/// \endcode 2270249259Sdim/// And delete the retain and autorelease. 2271249259Sdimvoid ObjCARCOpt::OptimizeReturns(Function &F) { 2272249259Sdim if (!F.getReturnType()->isPointerTy()) 2273249259Sdim return; 2274249259Sdim 2275341825Sdim LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeReturns ==\n"); 2276251662Sdim 2277249259Sdim SmallPtrSet<Instruction *, 4> DependingInstructions; 2278249259Sdim SmallPtrSet<const BasicBlock *, 4> Visited; 2279296417Sdim for (BasicBlock &BB: F) { 2280296417Sdim ReturnInst *Ret = dyn_cast<ReturnInst>(&BB.back()); 2281314564Sdim if (!Ret) 2282314564Sdim continue; 2283249259Sdim 2284341825Sdim LLVM_DEBUG(dbgs() << "Visiting: " << *Ret << "\n"); 2285249259Sdim 2286288943Sdim const Value *Arg = GetRCIdentityRoot(Ret->getOperand(0)); 2287251662Sdim 2288251662Sdim // Look for an ``autorelease'' instruction that is a predecessor of Ret and 2289249259Sdim // dependent on Arg such that there are no instructions dependent on Arg 2290249259Sdim // that need a positive ref count in between the autorelease and Ret. 2291296417Sdim CallInst *Autorelease = FindPredecessorAutoreleaseWithSafePath( 2292296417Sdim Arg, &BB, Ret, DependingInstructions, Visited, PA); 2293249259Sdim DependingInstructions.clear(); 2294249259Sdim Visited.clear(); 2295251662Sdim 2296251662Sdim if (!Autorelease) 2297251662Sdim continue; 2298251662Sdim 2299296417Sdim CallInst *Retain = FindPredecessorRetainWithSafePath( 2300327952Sdim Arg, Autorelease->getParent(), Autorelease, DependingInstructions, 2301327952Sdim Visited, PA); 2302251662Sdim DependingInstructions.clear(); 2303251662Sdim Visited.clear(); 2304251662Sdim 2305251662Sdim if (!Retain) 2306251662Sdim continue; 2307251662Sdim 2308251662Sdim // Check that there is nothing that can affect the reference count 2309251662Sdim // between the retain and the call. Note that Retain need not be in BB. 2310251662Sdim bool HasSafePathToCall = HasSafePathToPredecessorCall(Arg, Retain, 2311251662Sdim DependingInstructions, 2312251662Sdim Visited, PA); 2313251662Sdim DependingInstructions.clear(); 2314251662Sdim Visited.clear(); 2315251662Sdim 2316251662Sdim if (!HasSafePathToCall) 2317251662Sdim continue; 2318251662Sdim 2319251662Sdim // If so, we can zap the retain and autorelease. 2320251662Sdim Changed = true; 2321251662Sdim ++NumRets; 2322341825Sdim LLVM_DEBUG(dbgs() << "Erasing: " << *Retain << "\nErasing: " << *Autorelease 2323341825Sdim << "\n"); 2324251662Sdim EraseInstruction(Retain); 2325251662Sdim EraseInstruction(Autorelease); 2326249259Sdim } 2327251662Sdim} 2328249259Sdim 2329251662Sdim#ifndef NDEBUG 2330251662Sdimvoid 2331251662SdimObjCARCOpt::GatherStatistics(Function &F, bool AfterOptimization) { 2332327952Sdim Statistic &NumRetains = 2333327952Sdim AfterOptimization ? NumRetainsAfterOpt : NumRetainsBeforeOpt; 2334327952Sdim Statistic &NumReleases = 2335327952Sdim AfterOptimization ? NumReleasesAfterOpt : NumReleasesBeforeOpt; 2336249259Sdim 2337251662Sdim for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { 2338251662Sdim Instruction *Inst = &*I++; 2339288943Sdim switch (GetBasicARCInstKind(Inst)) { 2340251662Sdim default: 2341251662Sdim break; 2342288943Sdim case ARCInstKind::Retain: 2343251662Sdim ++NumRetains; 2344251662Sdim break; 2345288943Sdim case ARCInstKind::Release: 2346251662Sdim ++NumReleases; 2347251662Sdim break; 2348251662Sdim } 2349251662Sdim } 2350249259Sdim} 2351251662Sdim#endif 2352249259Sdim 2353249259Sdimbool ObjCARCOpt::doInitialization(Module &M) { 2354249259Sdim if (!EnableARCOpts) 2355249259Sdim return false; 2356249259Sdim 2357249259Sdim // If nothing in the Module uses ARC, don't do anything. 2358249259Sdim Run = ModuleHasARC(M); 2359249259Sdim if (!Run) 2360249259Sdim return false; 2361249259Sdim 2362249259Sdim // Intuitively, objc_retain and others are nocapture, however in practice 2363249259Sdim // they are not, because they return their argument value. And objc_release 2364249259Sdim // calls finalizers which can have arbitrary side effects. 2365288943Sdim MDKindCache.init(&M); 2366249259Sdim 2367261991Sdim // Initialize our runtime entry point cache. 2368288943Sdim EP.init(&M); 2369249259Sdim 2370249259Sdim return false; 2371249259Sdim} 2372249259Sdim 2373249259Sdimbool ObjCARCOpt::runOnFunction(Function &F) { 2374249259Sdim if (!EnableARCOpts) 2375249259Sdim return false; 2376249259Sdim 2377249259Sdim // If nothing in the Module uses ARC, don't do anything. 2378249259Sdim if (!Run) 2379249259Sdim return false; 2380249259Sdim 2381249259Sdim Changed = false; 2382249259Sdim 2383341825Sdim LLVM_DEBUG(dbgs() << "<<< ObjCARCOpt: Visiting Function: " << F.getName() 2384341825Sdim << " >>>" 2385341825Sdim "\n"); 2386249259Sdim 2387296417Sdim PA.setAA(&getAnalysis<AAResultsWrapperPass>().getAAResults()); 2388249259Sdim 2389261991Sdim#ifndef NDEBUG 2390261991Sdim if (AreStatisticsEnabled()) { 2391261991Sdim GatherStatistics(F, false); 2392261991Sdim } 2393261991Sdim#endif 2394261991Sdim 2395249259Sdim // This pass performs several distinct transformations. As a compile-time aid 2396249259Sdim // when compiling code that isn't ObjC, skip these if the relevant ObjC 2397249259Sdim // library functions aren't declared. 2398249259Sdim 2399251662Sdim // Preliminary optimizations. This also computes UsedInThisFunction. 2400249259Sdim OptimizeIndividualCalls(F); 2401249259Sdim 2402249259Sdim // Optimizations for weak pointers. 2403288943Sdim if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::LoadWeak)) | 2404288943Sdim (1 << unsigned(ARCInstKind::LoadWeakRetained)) | 2405288943Sdim (1 << unsigned(ARCInstKind::StoreWeak)) | 2406288943Sdim (1 << unsigned(ARCInstKind::InitWeak)) | 2407288943Sdim (1 << unsigned(ARCInstKind::CopyWeak)) | 2408288943Sdim (1 << unsigned(ARCInstKind::MoveWeak)) | 2409288943Sdim (1 << unsigned(ARCInstKind::DestroyWeak)))) 2410249259Sdim OptimizeWeakCalls(F); 2411249259Sdim 2412249259Sdim // Optimizations for retain+release pairs. 2413288943Sdim if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Retain)) | 2414288943Sdim (1 << unsigned(ARCInstKind::RetainRV)) | 2415288943Sdim (1 << unsigned(ARCInstKind::RetainBlock)))) 2416288943Sdim if (UsedInThisFunction & (1 << unsigned(ARCInstKind::Release))) 2417249259Sdim // Run OptimizeSequences until it either stops making changes or 2418249259Sdim // no retain+release pair nesting is detected. 2419249259Sdim while (OptimizeSequences(F)) {} 2420249259Sdim 2421249259Sdim // Optimizations if objc_autorelease is used. 2422288943Sdim if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Autorelease)) | 2423288943Sdim (1 << unsigned(ARCInstKind::AutoreleaseRV)))) 2424249259Sdim OptimizeReturns(F); 2425249259Sdim 2426251662Sdim // Gather statistics after optimization. 2427251662Sdim#ifndef NDEBUG 2428251662Sdim if (AreStatisticsEnabled()) { 2429251662Sdim GatherStatistics(F, true); 2430251662Sdim } 2431251662Sdim#endif 2432251662Sdim 2433341825Sdim LLVM_DEBUG(dbgs() << "\n"); 2434249259Sdim 2435249259Sdim return Changed; 2436249259Sdim} 2437249259Sdim 2438249259Sdimvoid ObjCARCOpt::releaseMemory() { 2439249259Sdim PA.clear(); 2440249259Sdim} 2441249259Sdim 2442249259Sdim/// @} 2443249259Sdim/// 2444