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