1 //===- ObjCARCOpts.cpp - ObjC ARC Optimization ----------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 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 "ObjCARC.h" 28 #include "ARCRuntimeEntryPoints.h" 29 #include "DependencyAnalysis.h" 30 #include "ObjCARCAliasAnalysis.h" 31 #include "ProvenanceAnalysis.h" 32 #include "llvm/ADT/DenseMap.h" 33 #include "llvm/ADT/DenseSet.h" 34 #include "llvm/ADT/STLExtras.h" 35 #include "llvm/ADT/SmallPtrSet.h" 36 #include "llvm/ADT/Statistic.h" 37 #include "llvm/IR/CFG.h" 38 #include "llvm/IR/IRBuilder.h" 39 #include "llvm/IR/LLVMContext.h" 40 #include "llvm/Support/Debug.h" 41 #include "llvm/Support/raw_ostream.h" 42 43 using namespace llvm; 44 using namespace llvm::objcarc; 45 46 #define DEBUG_TYPE "objc-arc-opts" 47 48 /// \defgroup MiscUtils Miscellaneous utilities that are not ARC specific. 49 /// @{ 50 51 namespace { 52 /// \brief An associative container with fast insertion-order (deterministic) 53 /// iteration over its elements. Plus the special blot operation. 54 template<class KeyT, class ValueT> 55 class MapVector { 56 /// Map keys to indices in Vector. 57 typedef DenseMap<KeyT, size_t> MapTy; 58 MapTy Map; 59 60 typedef std::vector<std::pair<KeyT, ValueT> > VectorTy; 61 /// Keys and values. 62 VectorTy Vector; 63 64 public: 65 typedef typename VectorTy::iterator iterator; 66 typedef typename VectorTy::const_iterator const_iterator; 67 iterator begin() { return Vector.begin(); } 68 iterator end() { return Vector.end(); } 69 const_iterator begin() const { return Vector.begin(); } 70 const_iterator end() const { return Vector.end(); } 71 72 #ifdef XDEBUG 73 ~MapVector() { 74 assert(Vector.size() >= Map.size()); // May differ due to blotting. 75 for (typename MapTy::const_iterator I = Map.begin(), E = Map.end(); 76 I != E; ++I) { 77 assert(I->second < Vector.size()); 78 assert(Vector[I->second].first == I->first); 79 } 80 for (typename VectorTy::const_iterator I = Vector.begin(), 81 E = Vector.end(); I != E; ++I) 82 assert(!I->first || 83 (Map.count(I->first) && 84 Map[I->first] == size_t(I - Vector.begin()))); 85 } 86 #endif 87 88 ValueT &operator[](const KeyT &Arg) { 89 std::pair<typename MapTy::iterator, bool> Pair = 90 Map.insert(std::make_pair(Arg, size_t(0))); 91 if (Pair.second) { 92 size_t Num = Vector.size(); 93 Pair.first->second = Num; 94 Vector.push_back(std::make_pair(Arg, ValueT())); 95 return Vector[Num].second; 96 } 97 return Vector[Pair.first->second].second; 98 } 99 100 std::pair<iterator, bool> 101 insert(const std::pair<KeyT, ValueT> &InsertPair) { 102 std::pair<typename MapTy::iterator, bool> Pair = 103 Map.insert(std::make_pair(InsertPair.first, size_t(0))); 104 if (Pair.second) { 105 size_t Num = Vector.size(); 106 Pair.first->second = Num; 107 Vector.push_back(InsertPair); 108 return std::make_pair(Vector.begin() + Num, true); 109 } 110 return std::make_pair(Vector.begin() + Pair.first->second, false); 111 } 112 113 iterator find(const KeyT &Key) { 114 typename MapTy::iterator It = Map.find(Key); 115 if (It == Map.end()) return Vector.end(); 116 return Vector.begin() + It->second; 117 } 118 119 const_iterator find(const KeyT &Key) const { 120 typename MapTy::const_iterator It = Map.find(Key); 121 if (It == Map.end()) return Vector.end(); 122 return Vector.begin() + It->second; 123 } 124 125 /// This is similar to erase, but instead of removing the element from the 126 /// vector, it just zeros out the key in the vector. This leaves iterators 127 /// intact, but clients must be prepared for zeroed-out keys when iterating. 128 void blot(const KeyT &Key) { 129 typename MapTy::iterator It = Map.find(Key); 130 if (It == Map.end()) return; 131 Vector[It->second].first = KeyT(); 132 Map.erase(It); 133 } 134 135 void clear() { 136 Map.clear(); 137 Vector.clear(); 138 } 139 }; 140 } 141 142 /// @} 143 /// 144 /// \defgroup ARCUtilities Utility declarations/definitions specific to ARC. 145 /// @{ 146 147 /// \brief This is similar to StripPointerCastsAndObjCCalls but it stops as soon 148 /// as it finds a value with multiple uses. 149 static const Value *FindSingleUseIdentifiedObject(const Value *Arg) { 150 if (Arg->hasOneUse()) { 151 if (const BitCastInst *BC = dyn_cast<BitCastInst>(Arg)) 152 return FindSingleUseIdentifiedObject(BC->getOperand(0)); 153 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Arg)) 154 if (GEP->hasAllZeroIndices()) 155 return FindSingleUseIdentifiedObject(GEP->getPointerOperand()); 156 if (IsForwarding(GetBasicInstructionClass(Arg))) 157 return FindSingleUseIdentifiedObject( 158 cast<CallInst>(Arg)->getArgOperand(0)); 159 if (!IsObjCIdentifiedObject(Arg)) 160 return nullptr; 161 return Arg; 162 } 163 164 // If we found an identifiable object but it has multiple uses, but they are 165 // trivial uses, we can still consider this to be a single-use value. 166 if (IsObjCIdentifiedObject(Arg)) { 167 for (const User *U : Arg->users()) 168 if (!U->use_empty() || StripPointerCastsAndObjCCalls(U) != Arg) 169 return nullptr; 170 171 return Arg; 172 } 173 174 return nullptr; 175 } 176 177 /// This is a wrapper around getUnderlyingObjCPtr along the lines of 178 /// GetUnderlyingObjects except that it returns early when it sees the first 179 /// alloca. 180 static inline bool AreAnyUnderlyingObjectsAnAlloca(const Value *V) { 181 SmallPtrSet<const Value *, 4> Visited; 182 SmallVector<const Value *, 4> Worklist; 183 Worklist.push_back(V); 184 do { 185 const Value *P = Worklist.pop_back_val(); 186 P = GetUnderlyingObjCPtr(P); 187 188 if (isa<AllocaInst>(P)) 189 return true; 190 191 if (!Visited.insert(P)) 192 continue; 193 194 if (const SelectInst *SI = dyn_cast<const SelectInst>(P)) { 195 Worklist.push_back(SI->getTrueValue()); 196 Worklist.push_back(SI->getFalseValue()); 197 continue; 198 } 199 200 if (const PHINode *PN = dyn_cast<const PHINode>(P)) { 201 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 202 Worklist.push_back(PN->getIncomingValue(i)); 203 continue; 204 } 205 } while (!Worklist.empty()); 206 207 return false; 208 } 209 210 211 /// @} 212 /// 213 /// \defgroup ARCOpt ARC Optimization. 214 /// @{ 215 216 // TODO: On code like this: 217 // 218 // objc_retain(%x) 219 // stuff_that_cannot_release() 220 // objc_autorelease(%x) 221 // stuff_that_cannot_release() 222 // objc_retain(%x) 223 // stuff_that_cannot_release() 224 // objc_autorelease(%x) 225 // 226 // The second retain and autorelease can be deleted. 227 228 // TODO: It should be possible to delete 229 // objc_autoreleasePoolPush and objc_autoreleasePoolPop 230 // pairs if nothing is actually autoreleased between them. Also, autorelease 231 // calls followed by objc_autoreleasePoolPop calls (perhaps in ObjC++ code 232 // after inlining) can be turned into plain release calls. 233 234 // TODO: Critical-edge splitting. If the optimial insertion point is 235 // a critical edge, the current algorithm has to fail, because it doesn't 236 // know how to split edges. It should be possible to make the optimizer 237 // think in terms of edges, rather than blocks, and then split critical 238 // edges on demand. 239 240 // TODO: OptimizeSequences could generalized to be Interprocedural. 241 242 // TODO: Recognize that a bunch of other objc runtime calls have 243 // non-escaping arguments and non-releasing arguments, and may be 244 // non-autoreleasing. 245 246 // TODO: Sink autorelease calls as far as possible. Unfortunately we 247 // usually can't sink them past other calls, which would be the main 248 // case where it would be useful. 249 250 // TODO: The pointer returned from objc_loadWeakRetained is retained. 251 252 // TODO: Delete release+retain pairs (rare). 253 254 STATISTIC(NumNoops, "Number of no-op objc calls eliminated"); 255 STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated"); 256 STATISTIC(NumAutoreleases,"Number of autoreleases converted to releases"); 257 STATISTIC(NumRets, "Number of return value forwarding " 258 "retain+autoreleases eliminated"); 259 STATISTIC(NumRRs, "Number of retain+release paths eliminated"); 260 STATISTIC(NumPeeps, "Number of calls peephole-optimized"); 261 #ifndef NDEBUG 262 STATISTIC(NumRetainsBeforeOpt, 263 "Number of retains before optimization"); 264 STATISTIC(NumReleasesBeforeOpt, 265 "Number of releases before optimization"); 266 STATISTIC(NumRetainsAfterOpt, 267 "Number of retains after optimization"); 268 STATISTIC(NumReleasesAfterOpt, 269 "Number of releases after optimization"); 270 #endif 271 272 namespace { 273 /// \enum Sequence 274 /// 275 /// \brief A sequence of states that a pointer may go through in which an 276 /// objc_retain and objc_release are actually needed. 277 enum Sequence { 278 S_None, 279 S_Retain, ///< objc_retain(x). 280 S_CanRelease, ///< foo(x) -- x could possibly see a ref count decrement. 281 S_Use, ///< any use of x. 282 S_Stop, ///< like S_Release, but code motion is stopped. 283 S_Release, ///< objc_release(x). 284 S_MovableRelease ///< objc_release(x), !clang.imprecise_release. 285 }; 286 287 raw_ostream &operator<<(raw_ostream &OS, const Sequence S) 288 LLVM_ATTRIBUTE_UNUSED; 289 raw_ostream &operator<<(raw_ostream &OS, const Sequence S) { 290 switch (S) { 291 case S_None: 292 return OS << "S_None"; 293 case S_Retain: 294 return OS << "S_Retain"; 295 case S_CanRelease: 296 return OS << "S_CanRelease"; 297 case S_Use: 298 return OS << "S_Use"; 299 case S_Release: 300 return OS << "S_Release"; 301 case S_MovableRelease: 302 return OS << "S_MovableRelease"; 303 case S_Stop: 304 return OS << "S_Stop"; 305 } 306 llvm_unreachable("Unknown sequence type."); 307 } 308 } 309 310 static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) { 311 // The easy cases. 312 if (A == B) 313 return A; 314 if (A == S_None || B == S_None) 315 return S_None; 316 317 if (A > B) std::swap(A, B); 318 if (TopDown) { 319 // Choose the side which is further along in the sequence. 320 if ((A == S_Retain || A == S_CanRelease) && 321 (B == S_CanRelease || B == S_Use)) 322 return B; 323 } else { 324 // Choose the side which is further along in the sequence. 325 if ((A == S_Use || A == S_CanRelease) && 326 (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease)) 327 return A; 328 // If both sides are releases, choose the more conservative one. 329 if (A == S_Stop && (B == S_Release || B == S_MovableRelease)) 330 return A; 331 if (A == S_Release && B == S_MovableRelease) 332 return A; 333 } 334 335 return S_None; 336 } 337 338 namespace { 339 /// \brief Unidirectional information about either a 340 /// retain-decrement-use-release sequence or release-use-decrement-retain 341 /// reverse sequence. 342 struct RRInfo { 343 /// After an objc_retain, the reference count of the referenced 344 /// object is known to be positive. Similarly, before an objc_release, the 345 /// reference count of the referenced object is known to be positive. If 346 /// there are retain-release pairs in code regions where the retain count 347 /// is known to be positive, they can be eliminated, regardless of any side 348 /// effects between them. 349 /// 350 /// Also, a retain+release pair nested within another retain+release 351 /// pair all on the known same pointer value can be eliminated, regardless 352 /// of any intervening side effects. 353 /// 354 /// KnownSafe is true when either of these conditions is satisfied. 355 bool KnownSafe; 356 357 /// True of the objc_release calls are all marked with the "tail" keyword. 358 bool IsTailCallRelease; 359 360 /// If the Calls are objc_release calls and they all have a 361 /// clang.imprecise_release tag, this is the metadata tag. 362 MDNode *ReleaseMetadata; 363 364 /// For a top-down sequence, the set of objc_retains or 365 /// objc_retainBlocks. For bottom-up, the set of objc_releases. 366 SmallPtrSet<Instruction *, 2> Calls; 367 368 /// The set of optimal insert positions for moving calls in the opposite 369 /// sequence. 370 SmallPtrSet<Instruction *, 2> ReverseInsertPts; 371 372 /// If this is true, we cannot perform code motion but can still remove 373 /// retain/release pairs. 374 bool CFGHazardAfflicted; 375 376 RRInfo() : 377 KnownSafe(false), IsTailCallRelease(false), ReleaseMetadata(nullptr), 378 CFGHazardAfflicted(false) {} 379 380 void clear(); 381 382 /// Conservatively merge the two RRInfo. Returns true if a partial merge has 383 /// occurred, false otherwise. 384 bool Merge(const RRInfo &Other); 385 386 }; 387 } 388 389 void RRInfo::clear() { 390 KnownSafe = false; 391 IsTailCallRelease = false; 392 ReleaseMetadata = nullptr; 393 Calls.clear(); 394 ReverseInsertPts.clear(); 395 CFGHazardAfflicted = false; 396 } 397 398 bool RRInfo::Merge(const RRInfo &Other) { 399 // Conservatively merge the ReleaseMetadata information. 400 if (ReleaseMetadata != Other.ReleaseMetadata) 401 ReleaseMetadata = nullptr; 402 403 // Conservatively merge the boolean state. 404 KnownSafe &= Other.KnownSafe; 405 IsTailCallRelease &= Other.IsTailCallRelease; 406 CFGHazardAfflicted |= Other.CFGHazardAfflicted; 407 408 // Merge the call sets. 409 Calls.insert(Other.Calls.begin(), Other.Calls.end()); 410 411 // Merge the insert point sets. If there are any differences, 412 // that makes this a partial merge. 413 bool Partial = ReverseInsertPts.size() != Other.ReverseInsertPts.size(); 414 for (SmallPtrSet<Instruction *, 2>::const_iterator 415 I = Other.ReverseInsertPts.begin(), 416 E = Other.ReverseInsertPts.end(); I != E; ++I) 417 Partial |= ReverseInsertPts.insert(*I); 418 return Partial; 419 } 420 421 namespace { 422 /// \brief This class summarizes several per-pointer runtime properties which 423 /// are propogated through the flow graph. 424 class PtrState { 425 /// True if the reference count is known to be incremented. 426 bool KnownPositiveRefCount; 427 428 /// True if we've seen an opportunity for partial RR elimination, such as 429 /// pushing calls into a CFG triangle or into one side of a CFG diamond. 430 bool Partial; 431 432 /// The current position in the sequence. 433 unsigned char Seq : 8; 434 435 /// Unidirectional information about the current sequence. 436 RRInfo RRI; 437 438 public: 439 PtrState() : KnownPositiveRefCount(false), Partial(false), 440 Seq(S_None) {} 441 442 443 bool IsKnownSafe() const { 444 return RRI.KnownSafe; 445 } 446 447 void SetKnownSafe(const bool NewValue) { 448 RRI.KnownSafe = NewValue; 449 } 450 451 bool IsTailCallRelease() const { 452 return RRI.IsTailCallRelease; 453 } 454 455 void SetTailCallRelease(const bool NewValue) { 456 RRI.IsTailCallRelease = NewValue; 457 } 458 459 bool IsTrackingImpreciseReleases() const { 460 return RRI.ReleaseMetadata != nullptr; 461 } 462 463 const MDNode *GetReleaseMetadata() const { 464 return RRI.ReleaseMetadata; 465 } 466 467 void SetReleaseMetadata(MDNode *NewValue) { 468 RRI.ReleaseMetadata = NewValue; 469 } 470 471 bool IsCFGHazardAfflicted() const { 472 return RRI.CFGHazardAfflicted; 473 } 474 475 void SetCFGHazardAfflicted(const bool NewValue) { 476 RRI.CFGHazardAfflicted = NewValue; 477 } 478 479 void SetKnownPositiveRefCount() { 480 DEBUG(dbgs() << "Setting Known Positive.\n"); 481 KnownPositiveRefCount = true; 482 } 483 484 void ClearKnownPositiveRefCount() { 485 DEBUG(dbgs() << "Clearing Known Positive.\n"); 486 KnownPositiveRefCount = false; 487 } 488 489 bool HasKnownPositiveRefCount() const { 490 return KnownPositiveRefCount; 491 } 492 493 void SetSeq(Sequence NewSeq) { 494 DEBUG(dbgs() << "Old: " << Seq << "; New: " << NewSeq << "\n"); 495 Seq = NewSeq; 496 } 497 498 Sequence GetSeq() const { 499 return static_cast<Sequence>(Seq); 500 } 501 502 void ClearSequenceProgress() { 503 ResetSequenceProgress(S_None); 504 } 505 506 void ResetSequenceProgress(Sequence NewSeq) { 507 DEBUG(dbgs() << "Resetting sequence progress.\n"); 508 SetSeq(NewSeq); 509 Partial = false; 510 RRI.clear(); 511 } 512 513 void Merge(const PtrState &Other, bool TopDown); 514 515 void InsertCall(Instruction *I) { 516 RRI.Calls.insert(I); 517 } 518 519 void InsertReverseInsertPt(Instruction *I) { 520 RRI.ReverseInsertPts.insert(I); 521 } 522 523 void ClearReverseInsertPts() { 524 RRI.ReverseInsertPts.clear(); 525 } 526 527 bool HasReverseInsertPts() const { 528 return !RRI.ReverseInsertPts.empty(); 529 } 530 531 const RRInfo &GetRRInfo() const { 532 return RRI; 533 } 534 }; 535 } 536 537 void 538 PtrState::Merge(const PtrState &Other, bool TopDown) { 539 Seq = MergeSeqs(GetSeq(), Other.GetSeq(), TopDown); 540 KnownPositiveRefCount &= Other.KnownPositiveRefCount; 541 542 // If we're not in a sequence (anymore), drop all associated state. 543 if (Seq == S_None) { 544 Partial = false; 545 RRI.clear(); 546 } else if (Partial || Other.Partial) { 547 // If we're doing a merge on a path that's previously seen a partial 548 // merge, conservatively drop the sequence, to avoid doing partial 549 // RR elimination. If the branch predicates for the two merge differ, 550 // mixing them is unsafe. 551 ClearSequenceProgress(); 552 } else { 553 // Otherwise merge the other PtrState's RRInfo into our RRInfo. At this 554 // point, we know that currently we are not partial. Stash whether or not 555 // the merge operation caused us to undergo a partial merging of reverse 556 // insertion points. 557 Partial = RRI.Merge(Other.RRI); 558 } 559 } 560 561 namespace { 562 /// \brief Per-BasicBlock state. 563 class BBState { 564 /// The number of unique control paths from the entry which can reach this 565 /// block. 566 unsigned TopDownPathCount; 567 568 /// The number of unique control paths to exits from this block. 569 unsigned BottomUpPathCount; 570 571 /// A type for PerPtrTopDown and PerPtrBottomUp. 572 typedef MapVector<const Value *, PtrState> MapTy; 573 574 /// The top-down traversal uses this to record information known about a 575 /// pointer at the bottom of each block. 576 MapTy PerPtrTopDown; 577 578 /// The bottom-up traversal uses this to record information known about a 579 /// pointer at the top of each block. 580 MapTy PerPtrBottomUp; 581 582 /// Effective predecessors of the current block ignoring ignorable edges and 583 /// ignored backedges. 584 SmallVector<BasicBlock *, 2> Preds; 585 /// Effective successors of the current block ignoring ignorable edges and 586 /// ignored backedges. 587 SmallVector<BasicBlock *, 2> Succs; 588 589 public: 590 static const unsigned OverflowOccurredValue; 591 592 BBState() : TopDownPathCount(0), BottomUpPathCount(0) { } 593 594 typedef MapTy::iterator ptr_iterator; 595 typedef MapTy::const_iterator ptr_const_iterator; 596 597 ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); } 598 ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); } 599 ptr_const_iterator top_down_ptr_begin() const { 600 return PerPtrTopDown.begin(); 601 } 602 ptr_const_iterator top_down_ptr_end() const { 603 return PerPtrTopDown.end(); 604 } 605 606 ptr_iterator bottom_up_ptr_begin() { return PerPtrBottomUp.begin(); } 607 ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); } 608 ptr_const_iterator bottom_up_ptr_begin() const { 609 return PerPtrBottomUp.begin(); 610 } 611 ptr_const_iterator bottom_up_ptr_end() const { 612 return PerPtrBottomUp.end(); 613 } 614 615 /// Mark this block as being an entry block, which has one path from the 616 /// entry by definition. 617 void SetAsEntry() { TopDownPathCount = 1; } 618 619 /// Mark this block as being an exit block, which has one path to an exit by 620 /// definition. 621 void SetAsExit() { BottomUpPathCount = 1; } 622 623 /// Attempt to find the PtrState object describing the top down state for 624 /// pointer Arg. Return a new initialized PtrState describing the top down 625 /// state for Arg if we do not find one. 626 PtrState &getPtrTopDownState(const Value *Arg) { 627 return PerPtrTopDown[Arg]; 628 } 629 630 /// Attempt to find the PtrState object describing the bottom up state for 631 /// pointer Arg. Return a new initialized PtrState describing the bottom up 632 /// state for Arg if we do not find one. 633 PtrState &getPtrBottomUpState(const Value *Arg) { 634 return PerPtrBottomUp[Arg]; 635 } 636 637 /// Attempt to find the PtrState object describing the bottom up state for 638 /// pointer Arg. 639 ptr_iterator findPtrBottomUpState(const Value *Arg) { 640 return PerPtrBottomUp.find(Arg); 641 } 642 643 void clearBottomUpPointers() { 644 PerPtrBottomUp.clear(); 645 } 646 647 void clearTopDownPointers() { 648 PerPtrTopDown.clear(); 649 } 650 651 void InitFromPred(const BBState &Other); 652 void InitFromSucc(const BBState &Other); 653 void MergePred(const BBState &Other); 654 void MergeSucc(const BBState &Other); 655 656 /// Compute the number of possible unique paths from an entry to an exit 657 /// which pass through this block. This is only valid after both the 658 /// top-down and bottom-up traversals are complete. 659 /// 660 /// Returns true if overflow occurred. Returns false if overflow did not 661 /// occur. 662 bool GetAllPathCountWithOverflow(unsigned &PathCount) const { 663 if (TopDownPathCount == OverflowOccurredValue || 664 BottomUpPathCount == OverflowOccurredValue) 665 return true; 666 unsigned long long Product = 667 (unsigned long long)TopDownPathCount*BottomUpPathCount; 668 // Overflow occurred if any of the upper bits of Product are set or if all 669 // the lower bits of Product are all set. 670 return (Product >> 32) || 671 ((PathCount = Product) == OverflowOccurredValue); 672 } 673 674 // Specialized CFG utilities. 675 typedef SmallVectorImpl<BasicBlock *>::const_iterator edge_iterator; 676 edge_iterator pred_begin() const { return Preds.begin(); } 677 edge_iterator pred_end() const { return Preds.end(); } 678 edge_iterator succ_begin() const { return Succs.begin(); } 679 edge_iterator succ_end() const { return Succs.end(); } 680 681 void addSucc(BasicBlock *Succ) { Succs.push_back(Succ); } 682 void addPred(BasicBlock *Pred) { Preds.push_back(Pred); } 683 684 bool isExit() const { return Succs.empty(); } 685 }; 686 687 const unsigned BBState::OverflowOccurredValue = 0xffffffff; 688 } 689 690 void BBState::InitFromPred(const BBState &Other) { 691 PerPtrTopDown = Other.PerPtrTopDown; 692 TopDownPathCount = Other.TopDownPathCount; 693 } 694 695 void BBState::InitFromSucc(const BBState &Other) { 696 PerPtrBottomUp = Other.PerPtrBottomUp; 697 BottomUpPathCount = Other.BottomUpPathCount; 698 } 699 700 /// The top-down traversal uses this to merge information about predecessors to 701 /// form the initial state for a new block. 702 void BBState::MergePred(const BBState &Other) { 703 if (TopDownPathCount == OverflowOccurredValue) 704 return; 705 706 // Other.TopDownPathCount can be 0, in which case it is either dead or a 707 // loop backedge. Loop backedges are special. 708 TopDownPathCount += Other.TopDownPathCount; 709 710 // In order to be consistent, we clear the top down pointers when by adding 711 // TopDownPathCount becomes OverflowOccurredValue even though "true" overflow 712 // has not occurred. 713 if (TopDownPathCount == OverflowOccurredValue) { 714 clearTopDownPointers(); 715 return; 716 } 717 718 // Check for overflow. If we have overflow, fall back to conservative 719 // behavior. 720 if (TopDownPathCount < Other.TopDownPathCount) { 721 TopDownPathCount = OverflowOccurredValue; 722 clearTopDownPointers(); 723 return; 724 } 725 726 // For each entry in the other set, if our set has an entry with the same key, 727 // merge the entries. Otherwise, copy the entry and merge it with an empty 728 // entry. 729 for (ptr_const_iterator MI = Other.top_down_ptr_begin(), 730 ME = Other.top_down_ptr_end(); MI != ME; ++MI) { 731 std::pair<ptr_iterator, bool> Pair = PerPtrTopDown.insert(*MI); 732 Pair.first->second.Merge(Pair.second ? PtrState() : MI->second, 733 /*TopDown=*/true); 734 } 735 736 // For each entry in our set, if the other set doesn't have an entry with the 737 // same key, force it to merge with an empty entry. 738 for (ptr_iterator MI = top_down_ptr_begin(), 739 ME = top_down_ptr_end(); MI != ME; ++MI) 740 if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end()) 741 MI->second.Merge(PtrState(), /*TopDown=*/true); 742 } 743 744 /// The bottom-up traversal uses this to merge information about successors to 745 /// form the initial state for a new block. 746 void BBState::MergeSucc(const BBState &Other) { 747 if (BottomUpPathCount == OverflowOccurredValue) 748 return; 749 750 // Other.BottomUpPathCount can be 0, in which case it is either dead or a 751 // loop backedge. Loop backedges are special. 752 BottomUpPathCount += Other.BottomUpPathCount; 753 754 // In order to be consistent, we clear the top down pointers when by adding 755 // BottomUpPathCount becomes OverflowOccurredValue even though "true" overflow 756 // has not occurred. 757 if (BottomUpPathCount == OverflowOccurredValue) { 758 clearBottomUpPointers(); 759 return; 760 } 761 762 // Check for overflow. If we have overflow, fall back to conservative 763 // behavior. 764 if (BottomUpPathCount < Other.BottomUpPathCount) { 765 BottomUpPathCount = OverflowOccurredValue; 766 clearBottomUpPointers(); 767 return; 768 } 769 770 // For each entry in the other set, if our set has an entry with the 771 // same key, merge the entries. Otherwise, copy the entry and merge 772 // it with an empty entry. 773 for (ptr_const_iterator MI = Other.bottom_up_ptr_begin(), 774 ME = Other.bottom_up_ptr_end(); MI != ME; ++MI) { 775 std::pair<ptr_iterator, bool> Pair = PerPtrBottomUp.insert(*MI); 776 Pair.first->second.Merge(Pair.second ? PtrState() : MI->second, 777 /*TopDown=*/false); 778 } 779 780 // For each entry in our set, if the other set doesn't have an entry 781 // with the same key, force it to merge with an empty entry. 782 for (ptr_iterator MI = bottom_up_ptr_begin(), 783 ME = bottom_up_ptr_end(); MI != ME; ++MI) 784 if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end()) 785 MI->second.Merge(PtrState(), /*TopDown=*/false); 786 } 787 788 // Only enable ARC Annotations if we are building a debug version of 789 // libObjCARCOpts. 790 #ifndef NDEBUG 791 #define ARC_ANNOTATIONS 792 #endif 793 794 // Define some macros along the lines of DEBUG and some helper functions to make 795 // it cleaner to create annotations in the source code and to no-op when not 796 // building in debug mode. 797 #ifdef ARC_ANNOTATIONS 798 799 #include "llvm/Support/CommandLine.h" 800 801 /// Enable/disable ARC sequence annotations. 802 static cl::opt<bool> 803 EnableARCAnnotations("enable-objc-arc-annotations", cl::init(false), 804 cl::desc("Enable emission of arc data flow analysis " 805 "annotations")); 806 static cl::opt<bool> 807 DisableCheckForCFGHazards("disable-objc-arc-checkforcfghazards", cl::init(false), 808 cl::desc("Disable check for cfg hazards when " 809 "annotating")); 810 static cl::opt<std::string> 811 ARCAnnotationTargetIdentifier("objc-arc-annotation-target-identifier", 812 cl::init(""), 813 cl::desc("filter out all data flow annotations " 814 "but those that apply to the given " 815 "target llvm identifier.")); 816 817 /// This function appends a unique ARCAnnotationProvenanceSourceMDKind id to an 818 /// instruction so that we can track backwards when post processing via the llvm 819 /// arc annotation processor tool. If the function is an 820 static MDString *AppendMDNodeToSourcePtr(unsigned NodeId, 821 Value *Ptr) { 822 MDString *Hash = nullptr; 823 824 // If pointer is a result of an instruction and it does not have a source 825 // MDNode it, attach a new MDNode onto it. If pointer is a result of 826 // an instruction and does have a source MDNode attached to it, return a 827 // reference to said Node. Otherwise just return 0. 828 if (Instruction *Inst = dyn_cast<Instruction>(Ptr)) { 829 MDNode *Node; 830 if (!(Node = Inst->getMetadata(NodeId))) { 831 // We do not have any node. Generate and attatch the hash MDString to the 832 // instruction. 833 834 // We just use an MDString to ensure that this metadata gets written out 835 // of line at the module level and to provide a very simple format 836 // encoding the information herein. Both of these makes it simpler to 837 // parse the annotations by a simple external program. 838 std::string Str; 839 raw_string_ostream os(Str); 840 os << "(" << Inst->getParent()->getParent()->getName() << ",%" 841 << Inst->getName() << ")"; 842 843 Hash = MDString::get(Inst->getContext(), os.str()); 844 Inst->setMetadata(NodeId, MDNode::get(Inst->getContext(),Hash)); 845 } else { 846 // We have a node. Grab its hash and return it. 847 assert(Node->getNumOperands() == 1 && 848 "An ARCAnnotationProvenanceSourceMDKind can only have 1 operand."); 849 Hash = cast<MDString>(Node->getOperand(0)); 850 } 851 } else if (Argument *Arg = dyn_cast<Argument>(Ptr)) { 852 std::string str; 853 raw_string_ostream os(str); 854 os << "(" << Arg->getParent()->getName() << ",%" << Arg->getName() 855 << ")"; 856 Hash = MDString::get(Arg->getContext(), os.str()); 857 } 858 859 return Hash; 860 } 861 862 static std::string SequenceToString(Sequence A) { 863 std::string str; 864 raw_string_ostream os(str); 865 os << A; 866 return os.str(); 867 } 868 869 /// Helper function to change a Sequence into a String object using our overload 870 /// for raw_ostream so we only have printing code in one location. 871 static MDString *SequenceToMDString(LLVMContext &Context, 872 Sequence A) { 873 return MDString::get(Context, SequenceToString(A)); 874 } 875 876 /// A simple function to generate a MDNode which describes the change in state 877 /// for Value *Ptr caused by Instruction *Inst. 878 static void AppendMDNodeToInstForPtr(unsigned NodeId, 879 Instruction *Inst, 880 Value *Ptr, 881 MDString *PtrSourceMDNodeID, 882 Sequence OldSeq, 883 Sequence NewSeq) { 884 MDNode *Node = nullptr; 885 Value *tmp[3] = {PtrSourceMDNodeID, 886 SequenceToMDString(Inst->getContext(), 887 OldSeq), 888 SequenceToMDString(Inst->getContext(), 889 NewSeq)}; 890 Node = MDNode::get(Inst->getContext(), 891 ArrayRef<Value*>(tmp, 3)); 892 893 Inst->setMetadata(NodeId, Node); 894 } 895 896 /// Add to the beginning of the basic block llvm.ptr.annotations which show the 897 /// state of a pointer at the entrance to a basic block. 898 static void GenerateARCBBEntranceAnnotation(const char *Name, BasicBlock *BB, 899 Value *Ptr, Sequence Seq) { 900 // If we have a target identifier, make sure that we match it before 901 // continuing. 902 if(!ARCAnnotationTargetIdentifier.empty() && 903 !Ptr->getName().equals(ARCAnnotationTargetIdentifier)) 904 return; 905 906 Module *M = BB->getParent()->getParent(); 907 LLVMContext &C = M->getContext(); 908 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); 909 Type *I8XX = PointerType::getUnqual(I8X); 910 Type *Params[] = {I8XX, I8XX}; 911 FunctionType *FTy = FunctionType::get(Type::getVoidTy(C), 912 ArrayRef<Type*>(Params, 2), 913 /*isVarArg=*/false); 914 Constant *Callee = M->getOrInsertFunction(Name, FTy); 915 916 IRBuilder<> Builder(BB, BB->getFirstInsertionPt()); 917 918 Value *PtrName; 919 StringRef Tmp = Ptr->getName(); 920 if (nullptr == (PtrName = M->getGlobalVariable(Tmp, true))) { 921 Value *ActualPtrName = Builder.CreateGlobalStringPtr(Tmp, 922 Tmp + "_STR"); 923 PtrName = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage, 924 cast<Constant>(ActualPtrName), Tmp); 925 } 926 927 Value *S; 928 std::string SeqStr = SequenceToString(Seq); 929 if (nullptr == (S = M->getGlobalVariable(SeqStr, true))) { 930 Value *ActualPtrName = Builder.CreateGlobalStringPtr(SeqStr, 931 SeqStr + "_STR"); 932 S = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage, 933 cast<Constant>(ActualPtrName), SeqStr); 934 } 935 936 Builder.CreateCall2(Callee, PtrName, S); 937 } 938 939 /// Add to the end of the basic block llvm.ptr.annotations which show the state 940 /// of the pointer at the bottom of the basic block. 941 static void GenerateARCBBTerminatorAnnotation(const char *Name, BasicBlock *BB, 942 Value *Ptr, Sequence Seq) { 943 // If we have a target identifier, make sure that we match it before emitting 944 // an annotation. 945 if(!ARCAnnotationTargetIdentifier.empty() && 946 !Ptr->getName().equals(ARCAnnotationTargetIdentifier)) 947 return; 948 949 Module *M = BB->getParent()->getParent(); 950 LLVMContext &C = M->getContext(); 951 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); 952 Type *I8XX = PointerType::getUnqual(I8X); 953 Type *Params[] = {I8XX, I8XX}; 954 FunctionType *FTy = FunctionType::get(Type::getVoidTy(C), 955 ArrayRef<Type*>(Params, 2), 956 /*isVarArg=*/false); 957 Constant *Callee = M->getOrInsertFunction(Name, FTy); 958 959 IRBuilder<> Builder(BB, std::prev(BB->end())); 960 961 Value *PtrName; 962 StringRef Tmp = Ptr->getName(); 963 if (nullptr == (PtrName = M->getGlobalVariable(Tmp, true))) { 964 Value *ActualPtrName = Builder.CreateGlobalStringPtr(Tmp, 965 Tmp + "_STR"); 966 PtrName = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage, 967 cast<Constant>(ActualPtrName), Tmp); 968 } 969 970 Value *S; 971 std::string SeqStr = SequenceToString(Seq); 972 if (nullptr == (S = M->getGlobalVariable(SeqStr, true))) { 973 Value *ActualPtrName = Builder.CreateGlobalStringPtr(SeqStr, 974 SeqStr + "_STR"); 975 S = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage, 976 cast<Constant>(ActualPtrName), SeqStr); 977 } 978 Builder.CreateCall2(Callee, PtrName, S); 979 } 980 981 /// Adds a source annotation to pointer and a state change annotation to Inst 982 /// referencing the source annotation and the old/new state of pointer. 983 static void GenerateARCAnnotation(unsigned InstMDId, 984 unsigned PtrMDId, 985 Instruction *Inst, 986 Value *Ptr, 987 Sequence OldSeq, 988 Sequence NewSeq) { 989 if (EnableARCAnnotations) { 990 // If we have a target identifier, make sure that we match it before 991 // emitting an annotation. 992 if(!ARCAnnotationTargetIdentifier.empty() && 993 !Ptr->getName().equals(ARCAnnotationTargetIdentifier)) 994 return; 995 996 // First generate the source annotation on our pointer. This will return an 997 // MDString* if Ptr actually comes from an instruction implying we can put 998 // in a source annotation. If AppendMDNodeToSourcePtr returns 0 (i.e. NULL), 999 // then we know that our pointer is from an Argument so we put a reference 1000 // to the argument number. 1001 // 1002 // The point of this is to make it easy for the 1003 // llvm-arc-annotation-processor tool to cross reference where the source 1004 // pointer is in the LLVM IR since the LLVM IR parser does not submit such 1005 // information via debug info for backends to use (since why would anyone 1006 // need such a thing from LLVM IR besides in non-standard cases 1007 // [i.e. this]). 1008 MDString *SourcePtrMDNode = 1009 AppendMDNodeToSourcePtr(PtrMDId, Ptr); 1010 AppendMDNodeToInstForPtr(InstMDId, Inst, Ptr, SourcePtrMDNode, OldSeq, 1011 NewSeq); 1012 } 1013 } 1014 1015 // The actual interface for accessing the above functionality is defined via 1016 // some simple macros which are defined below. We do this so that the user does 1017 // not need to pass in what metadata id is needed resulting in cleaner code and 1018 // additionally since it provides an easy way to conditionally no-op all 1019 // annotation support in a non-debug build. 1020 1021 /// Use this macro to annotate a sequence state change when processing 1022 /// instructions bottom up, 1023 #define ANNOTATE_BOTTOMUP(inst, ptr, old, new) \ 1024 GenerateARCAnnotation(ARCAnnotationBottomUpMDKind, \ 1025 ARCAnnotationProvenanceSourceMDKind, (inst), \ 1026 const_cast<Value*>(ptr), (old), (new)) 1027 /// Use this macro to annotate a sequence state change when processing 1028 /// instructions top down. 1029 #define ANNOTATE_TOPDOWN(inst, ptr, old, new) \ 1030 GenerateARCAnnotation(ARCAnnotationTopDownMDKind, \ 1031 ARCAnnotationProvenanceSourceMDKind, (inst), \ 1032 const_cast<Value*>(ptr), (old), (new)) 1033 1034 #define ANNOTATE_BB(_states, _bb, _name, _type, _direction) \ 1035 do { \ 1036 if (EnableARCAnnotations) { \ 1037 for(BBState::ptr_const_iterator I = (_states)._direction##_ptr_begin(), \ 1038 E = (_states)._direction##_ptr_end(); I != E; ++I) { \ 1039 Value *Ptr = const_cast<Value*>(I->first); \ 1040 Sequence Seq = I->second.GetSeq(); \ 1041 GenerateARCBB ## _type ## Annotation(_name, (_bb), Ptr, Seq); \ 1042 } \ 1043 } \ 1044 } while (0) 1045 1046 #define ANNOTATE_BOTTOMUP_BBSTART(_states, _basicblock) \ 1047 ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.bottomup.bbstart", \ 1048 Entrance, bottom_up) 1049 #define ANNOTATE_BOTTOMUP_BBEND(_states, _basicblock) \ 1050 ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.bottomup.bbend", \ 1051 Terminator, bottom_up) 1052 #define ANNOTATE_TOPDOWN_BBSTART(_states, _basicblock) \ 1053 ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.topdown.bbstart", \ 1054 Entrance, top_down) 1055 #define ANNOTATE_TOPDOWN_BBEND(_states, _basicblock) \ 1056 ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.topdown.bbend", \ 1057 Terminator, top_down) 1058 1059 #else // !ARC_ANNOTATION 1060 // If annotations are off, noop. 1061 #define ANNOTATE_BOTTOMUP(inst, ptr, old, new) 1062 #define ANNOTATE_TOPDOWN(inst, ptr, old, new) 1063 #define ANNOTATE_BOTTOMUP_BBSTART(states, basicblock) 1064 #define ANNOTATE_BOTTOMUP_BBEND(states, basicblock) 1065 #define ANNOTATE_TOPDOWN_BBSTART(states, basicblock) 1066 #define ANNOTATE_TOPDOWN_BBEND(states, basicblock) 1067 #endif // !ARC_ANNOTATION 1068 1069 namespace { 1070 /// \brief The main ARC optimization pass. 1071 class ObjCARCOpt : public FunctionPass { 1072 bool Changed; 1073 ProvenanceAnalysis PA; 1074 ARCRuntimeEntryPoints EP; 1075 1076 // This is used to track if a pointer is stored into an alloca. 1077 DenseSet<const Value *> MultiOwnersSet; 1078 1079 /// A flag indicating whether this optimization pass should run. 1080 bool Run; 1081 1082 /// Flags which determine whether each of the interesting runtine functions 1083 /// is in fact used in the current function. 1084 unsigned UsedInThisFunction; 1085 1086 /// The Metadata Kind for clang.imprecise_release metadata. 1087 unsigned ImpreciseReleaseMDKind; 1088 1089 /// The Metadata Kind for clang.arc.copy_on_escape metadata. 1090 unsigned CopyOnEscapeMDKind; 1091 1092 /// The Metadata Kind for clang.arc.no_objc_arc_exceptions metadata. 1093 unsigned NoObjCARCExceptionsMDKind; 1094 1095 #ifdef ARC_ANNOTATIONS 1096 /// The Metadata Kind for llvm.arc.annotation.bottomup metadata. 1097 unsigned ARCAnnotationBottomUpMDKind; 1098 /// The Metadata Kind for llvm.arc.annotation.topdown metadata. 1099 unsigned ARCAnnotationTopDownMDKind; 1100 /// The Metadata Kind for llvm.arc.annotation.provenancesource metadata. 1101 unsigned ARCAnnotationProvenanceSourceMDKind; 1102 #endif // ARC_ANNOATIONS 1103 1104 bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV); 1105 void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV, 1106 InstructionClass &Class); 1107 void OptimizeIndividualCalls(Function &F); 1108 1109 void CheckForCFGHazards(const BasicBlock *BB, 1110 DenseMap<const BasicBlock *, BBState> &BBStates, 1111 BBState &MyStates) const; 1112 bool VisitInstructionBottomUp(Instruction *Inst, 1113 BasicBlock *BB, 1114 MapVector<Value *, RRInfo> &Retains, 1115 BBState &MyStates); 1116 bool VisitBottomUp(BasicBlock *BB, 1117 DenseMap<const BasicBlock *, BBState> &BBStates, 1118 MapVector<Value *, RRInfo> &Retains); 1119 bool VisitInstructionTopDown(Instruction *Inst, 1120 DenseMap<Value *, RRInfo> &Releases, 1121 BBState &MyStates); 1122 bool VisitTopDown(BasicBlock *BB, 1123 DenseMap<const BasicBlock *, BBState> &BBStates, 1124 DenseMap<Value *, RRInfo> &Releases); 1125 bool Visit(Function &F, 1126 DenseMap<const BasicBlock *, BBState> &BBStates, 1127 MapVector<Value *, RRInfo> &Retains, 1128 DenseMap<Value *, RRInfo> &Releases); 1129 1130 void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove, 1131 MapVector<Value *, RRInfo> &Retains, 1132 DenseMap<Value *, RRInfo> &Releases, 1133 SmallVectorImpl<Instruction *> &DeadInsts, 1134 Module *M); 1135 1136 bool ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState> &BBStates, 1137 MapVector<Value *, RRInfo> &Retains, 1138 DenseMap<Value *, RRInfo> &Releases, 1139 Module *M, 1140 SmallVectorImpl<Instruction *> &NewRetains, 1141 SmallVectorImpl<Instruction *> &NewReleases, 1142 SmallVectorImpl<Instruction *> &DeadInsts, 1143 RRInfo &RetainsToMove, 1144 RRInfo &ReleasesToMove, 1145 Value *Arg, 1146 bool KnownSafe, 1147 bool &AnyPairsCompletelyEliminated); 1148 1149 bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates, 1150 MapVector<Value *, RRInfo> &Retains, 1151 DenseMap<Value *, RRInfo> &Releases, 1152 Module *M); 1153 1154 void OptimizeWeakCalls(Function &F); 1155 1156 bool OptimizeSequences(Function &F); 1157 1158 void OptimizeReturns(Function &F); 1159 1160 #ifndef NDEBUG 1161 void GatherStatistics(Function &F, bool AfterOptimization = false); 1162 #endif 1163 1164 void getAnalysisUsage(AnalysisUsage &AU) const override; 1165 bool doInitialization(Module &M) override; 1166 bool runOnFunction(Function &F) override; 1167 void releaseMemory() override; 1168 1169 public: 1170 static char ID; 1171 ObjCARCOpt() : FunctionPass(ID) { 1172 initializeObjCARCOptPass(*PassRegistry::getPassRegistry()); 1173 } 1174 }; 1175 } 1176 1177 char ObjCARCOpt::ID = 0; 1178 INITIALIZE_PASS_BEGIN(ObjCARCOpt, 1179 "objc-arc", "ObjC ARC optimization", false, false) 1180 INITIALIZE_PASS_DEPENDENCY(ObjCARCAliasAnalysis) 1181 INITIALIZE_PASS_END(ObjCARCOpt, 1182 "objc-arc", "ObjC ARC optimization", false, false) 1183 1184 Pass *llvm::createObjCARCOptPass() { 1185 return new ObjCARCOpt(); 1186 } 1187 1188 void ObjCARCOpt::getAnalysisUsage(AnalysisUsage &AU) const { 1189 AU.addRequired<ObjCARCAliasAnalysis>(); 1190 AU.addRequired<AliasAnalysis>(); 1191 // ARC optimization doesn't currently split critical edges. 1192 AU.setPreservesCFG(); 1193 } 1194 1195 /// Turn objc_retainAutoreleasedReturnValue into objc_retain if the operand is 1196 /// not a return value. Or, if it can be paired with an 1197 /// objc_autoreleaseReturnValue, delete the pair and return true. 1198 bool 1199 ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) { 1200 // Check for the argument being from an immediately preceding call or invoke. 1201 const Value *Arg = GetObjCArg(RetainRV); 1202 ImmutableCallSite CS(Arg); 1203 if (const Instruction *Call = CS.getInstruction()) { 1204 if (Call->getParent() == RetainRV->getParent()) { 1205 BasicBlock::const_iterator I = Call; 1206 ++I; 1207 while (IsNoopInstruction(I)) ++I; 1208 if (&*I == RetainRV) 1209 return false; 1210 } else if (const InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 1211 BasicBlock *RetainRVParent = RetainRV->getParent(); 1212 if (II->getNormalDest() == RetainRVParent) { 1213 BasicBlock::const_iterator I = RetainRVParent->begin(); 1214 while (IsNoopInstruction(I)) ++I; 1215 if (&*I == RetainRV) 1216 return false; 1217 } 1218 } 1219 } 1220 1221 // Check for being preceded by an objc_autoreleaseReturnValue on the same 1222 // pointer. In this case, we can delete the pair. 1223 BasicBlock::iterator I = RetainRV, Begin = RetainRV->getParent()->begin(); 1224 if (I != Begin) { 1225 do --I; while (I != Begin && IsNoopInstruction(I)); 1226 if (GetBasicInstructionClass(I) == IC_AutoreleaseRV && 1227 GetObjCArg(I) == Arg) { 1228 Changed = true; 1229 ++NumPeeps; 1230 1231 DEBUG(dbgs() << "Erasing autoreleaseRV,retainRV pair: " << *I << "\n" 1232 << "Erasing " << *RetainRV << "\n"); 1233 1234 EraseInstruction(I); 1235 EraseInstruction(RetainRV); 1236 return true; 1237 } 1238 } 1239 1240 // Turn it to a plain objc_retain. 1241 Changed = true; 1242 ++NumPeeps; 1243 1244 DEBUG(dbgs() << "Transforming objc_retainAutoreleasedReturnValue => " 1245 "objc_retain since the operand is not a return value.\n" 1246 "Old = " << *RetainRV << "\n"); 1247 1248 Constant *NewDecl = EP.get(ARCRuntimeEntryPoints::EPT_Retain); 1249 cast<CallInst>(RetainRV)->setCalledFunction(NewDecl); 1250 1251 DEBUG(dbgs() << "New = " << *RetainRV << "\n"); 1252 1253 return false; 1254 } 1255 1256 /// Turn objc_autoreleaseReturnValue into objc_autorelease if the result is not 1257 /// used as a return value. 1258 void 1259 ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV, 1260 InstructionClass &Class) { 1261 // Check for a return of the pointer value. 1262 const Value *Ptr = GetObjCArg(AutoreleaseRV); 1263 SmallVector<const Value *, 2> Users; 1264 Users.push_back(Ptr); 1265 do { 1266 Ptr = Users.pop_back_val(); 1267 for (const User *U : Ptr->users()) { 1268 if (isa<ReturnInst>(U) || GetBasicInstructionClass(U) == IC_RetainRV) 1269 return; 1270 if (isa<BitCastInst>(U)) 1271 Users.push_back(U); 1272 } 1273 } while (!Users.empty()); 1274 1275 Changed = true; 1276 ++NumPeeps; 1277 1278 DEBUG(dbgs() << "Transforming objc_autoreleaseReturnValue => " 1279 "objc_autorelease since its operand is not used as a return " 1280 "value.\n" 1281 "Old = " << *AutoreleaseRV << "\n"); 1282 1283 CallInst *AutoreleaseRVCI = cast<CallInst>(AutoreleaseRV); 1284 Constant *NewDecl = EP.get(ARCRuntimeEntryPoints::EPT_Autorelease); 1285 AutoreleaseRVCI->setCalledFunction(NewDecl); 1286 AutoreleaseRVCI->setTailCall(false); // Never tail call objc_autorelease. 1287 Class = IC_Autorelease; 1288 1289 DEBUG(dbgs() << "New: " << *AutoreleaseRV << "\n"); 1290 1291 } 1292 1293 /// Visit each call, one at a time, and make simplifications without doing any 1294 /// additional analysis. 1295 void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { 1296 DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeIndividualCalls ==\n"); 1297 // Reset all the flags in preparation for recomputing them. 1298 UsedInThisFunction = 0; 1299 1300 // Visit all objc_* calls in F. 1301 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { 1302 Instruction *Inst = &*I++; 1303 1304 InstructionClass Class = GetBasicInstructionClass(Inst); 1305 1306 DEBUG(dbgs() << "Visiting: Class: " << Class << "; " << *Inst << "\n"); 1307 1308 switch (Class) { 1309 default: break; 1310 1311 // Delete no-op casts. These function calls have special semantics, but 1312 // the semantics are entirely implemented via lowering in the front-end, 1313 // so by the time they reach the optimizer, they are just no-op calls 1314 // which return their argument. 1315 // 1316 // There are gray areas here, as the ability to cast reference-counted 1317 // pointers to raw void* and back allows code to break ARC assumptions, 1318 // however these are currently considered to be unimportant. 1319 case IC_NoopCast: 1320 Changed = true; 1321 ++NumNoops; 1322 DEBUG(dbgs() << "Erasing no-op cast: " << *Inst << "\n"); 1323 EraseInstruction(Inst); 1324 continue; 1325 1326 // If the pointer-to-weak-pointer is null, it's undefined behavior. 1327 case IC_StoreWeak: 1328 case IC_LoadWeak: 1329 case IC_LoadWeakRetained: 1330 case IC_InitWeak: 1331 case IC_DestroyWeak: { 1332 CallInst *CI = cast<CallInst>(Inst); 1333 if (IsNullOrUndef(CI->getArgOperand(0))) { 1334 Changed = true; 1335 Type *Ty = CI->getArgOperand(0)->getType(); 1336 new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()), 1337 Constant::getNullValue(Ty), 1338 CI); 1339 llvm::Value *NewValue = UndefValue::get(CI->getType()); 1340 DEBUG(dbgs() << "A null pointer-to-weak-pointer is undefined behavior." 1341 "\nOld = " << *CI << "\nNew = " << *NewValue << "\n"); 1342 CI->replaceAllUsesWith(NewValue); 1343 CI->eraseFromParent(); 1344 continue; 1345 } 1346 break; 1347 } 1348 case IC_CopyWeak: 1349 case IC_MoveWeak: { 1350 CallInst *CI = cast<CallInst>(Inst); 1351 if (IsNullOrUndef(CI->getArgOperand(0)) || 1352 IsNullOrUndef(CI->getArgOperand(1))) { 1353 Changed = true; 1354 Type *Ty = CI->getArgOperand(0)->getType(); 1355 new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()), 1356 Constant::getNullValue(Ty), 1357 CI); 1358 1359 llvm::Value *NewValue = UndefValue::get(CI->getType()); 1360 DEBUG(dbgs() << "A null pointer-to-weak-pointer is undefined behavior." 1361 "\nOld = " << *CI << "\nNew = " << *NewValue << "\n"); 1362 1363 CI->replaceAllUsesWith(NewValue); 1364 CI->eraseFromParent(); 1365 continue; 1366 } 1367 break; 1368 } 1369 case IC_RetainRV: 1370 if (OptimizeRetainRVCall(F, Inst)) 1371 continue; 1372 break; 1373 case IC_AutoreleaseRV: 1374 OptimizeAutoreleaseRVCall(F, Inst, Class); 1375 break; 1376 } 1377 1378 // objc_autorelease(x) -> objc_release(x) if x is otherwise unused. 1379 if (IsAutorelease(Class) && Inst->use_empty()) { 1380 CallInst *Call = cast<CallInst>(Inst); 1381 const Value *Arg = Call->getArgOperand(0); 1382 Arg = FindSingleUseIdentifiedObject(Arg); 1383 if (Arg) { 1384 Changed = true; 1385 ++NumAutoreleases; 1386 1387 // Create the declaration lazily. 1388 LLVMContext &C = Inst->getContext(); 1389 1390 Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Release); 1391 CallInst *NewCall = CallInst::Create(Decl, Call->getArgOperand(0), "", 1392 Call); 1393 NewCall->setMetadata(ImpreciseReleaseMDKind, MDNode::get(C, None)); 1394 1395 DEBUG(dbgs() << "Replacing autorelease{,RV}(x) with objc_release(x) " 1396 "since x is otherwise unused.\nOld: " << *Call << "\nNew: " 1397 << *NewCall << "\n"); 1398 1399 EraseInstruction(Call); 1400 Inst = NewCall; 1401 Class = IC_Release; 1402 } 1403 } 1404 1405 // For functions which can never be passed stack arguments, add 1406 // a tail keyword. 1407 if (IsAlwaysTail(Class)) { 1408 Changed = true; 1409 DEBUG(dbgs() << "Adding tail keyword to function since it can never be " 1410 "passed stack args: " << *Inst << "\n"); 1411 cast<CallInst>(Inst)->setTailCall(); 1412 } 1413 1414 // Ensure that functions that can never have a "tail" keyword due to the 1415 // semantics of ARC truly do not do so. 1416 if (IsNeverTail(Class)) { 1417 Changed = true; 1418 DEBUG(dbgs() << "Removing tail keyword from function: " << *Inst << 1419 "\n"); 1420 cast<CallInst>(Inst)->setTailCall(false); 1421 } 1422 1423 // Set nounwind as needed. 1424 if (IsNoThrow(Class)) { 1425 Changed = true; 1426 DEBUG(dbgs() << "Found no throw class. Setting nounwind on: " << *Inst 1427 << "\n"); 1428 cast<CallInst>(Inst)->setDoesNotThrow(); 1429 } 1430 1431 if (!IsNoopOnNull(Class)) { 1432 UsedInThisFunction |= 1 << Class; 1433 continue; 1434 } 1435 1436 const Value *Arg = GetObjCArg(Inst); 1437 1438 // ARC calls with null are no-ops. Delete them. 1439 if (IsNullOrUndef(Arg)) { 1440 Changed = true; 1441 ++NumNoops; 1442 DEBUG(dbgs() << "ARC calls with null are no-ops. Erasing: " << *Inst 1443 << "\n"); 1444 EraseInstruction(Inst); 1445 continue; 1446 } 1447 1448 // Keep track of which of retain, release, autorelease, and retain_block 1449 // are actually present in this function. 1450 UsedInThisFunction |= 1 << Class; 1451 1452 // If Arg is a PHI, and one or more incoming values to the 1453 // PHI are null, and the call is control-equivalent to the PHI, and there 1454 // are no relevant side effects between the PHI and the call, the call 1455 // could be pushed up to just those paths with non-null incoming values. 1456 // For now, don't bother splitting critical edges for this. 1457 SmallVector<std::pair<Instruction *, const Value *>, 4> Worklist; 1458 Worklist.push_back(std::make_pair(Inst, Arg)); 1459 do { 1460 std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val(); 1461 Inst = Pair.first; 1462 Arg = Pair.second; 1463 1464 const PHINode *PN = dyn_cast<PHINode>(Arg); 1465 if (!PN) continue; 1466 1467 // Determine if the PHI has any null operands, or any incoming 1468 // critical edges. 1469 bool HasNull = false; 1470 bool HasCriticalEdges = false; 1471 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1472 Value *Incoming = 1473 StripPointerCastsAndObjCCalls(PN->getIncomingValue(i)); 1474 if (IsNullOrUndef(Incoming)) 1475 HasNull = true; 1476 else if (cast<TerminatorInst>(PN->getIncomingBlock(i)->back()) 1477 .getNumSuccessors() != 1) { 1478 HasCriticalEdges = true; 1479 break; 1480 } 1481 } 1482 // If we have null operands and no critical edges, optimize. 1483 if (!HasCriticalEdges && HasNull) { 1484 SmallPtrSet<Instruction *, 4> DependingInstructions; 1485 SmallPtrSet<const BasicBlock *, 4> Visited; 1486 1487 // Check that there is nothing that cares about the reference 1488 // count between the call and the phi. 1489 switch (Class) { 1490 case IC_Retain: 1491 case IC_RetainBlock: 1492 // These can always be moved up. 1493 break; 1494 case IC_Release: 1495 // These can't be moved across things that care about the retain 1496 // count. 1497 FindDependencies(NeedsPositiveRetainCount, Arg, 1498 Inst->getParent(), Inst, 1499 DependingInstructions, Visited, PA); 1500 break; 1501 case IC_Autorelease: 1502 // These can't be moved across autorelease pool scope boundaries. 1503 FindDependencies(AutoreleasePoolBoundary, Arg, 1504 Inst->getParent(), Inst, 1505 DependingInstructions, Visited, PA); 1506 break; 1507 case IC_RetainRV: 1508 case IC_AutoreleaseRV: 1509 // Don't move these; the RV optimization depends on the autoreleaseRV 1510 // being tail called, and the retainRV being immediately after a call 1511 // (which might still happen if we get lucky with codegen layout, but 1512 // it's not worth taking the chance). 1513 continue; 1514 default: 1515 llvm_unreachable("Invalid dependence flavor"); 1516 } 1517 1518 if (DependingInstructions.size() == 1 && 1519 *DependingInstructions.begin() == PN) { 1520 Changed = true; 1521 ++NumPartialNoops; 1522 // Clone the call into each predecessor that has a non-null value. 1523 CallInst *CInst = cast<CallInst>(Inst); 1524 Type *ParamTy = CInst->getArgOperand(0)->getType(); 1525 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1526 Value *Incoming = 1527 StripPointerCastsAndObjCCalls(PN->getIncomingValue(i)); 1528 if (!IsNullOrUndef(Incoming)) { 1529 CallInst *Clone = cast<CallInst>(CInst->clone()); 1530 Value *Op = PN->getIncomingValue(i); 1531 Instruction *InsertPos = &PN->getIncomingBlock(i)->back(); 1532 if (Op->getType() != ParamTy) 1533 Op = new BitCastInst(Op, ParamTy, "", InsertPos); 1534 Clone->setArgOperand(0, Op); 1535 Clone->insertBefore(InsertPos); 1536 1537 DEBUG(dbgs() << "Cloning " 1538 << *CInst << "\n" 1539 "And inserting clone at " << *InsertPos << "\n"); 1540 Worklist.push_back(std::make_pair(Clone, Incoming)); 1541 } 1542 } 1543 // Erase the original call. 1544 DEBUG(dbgs() << "Erasing: " << *CInst << "\n"); 1545 EraseInstruction(CInst); 1546 continue; 1547 } 1548 } 1549 } while (!Worklist.empty()); 1550 } 1551 } 1552 1553 /// If we have a top down pointer in the S_Use state, make sure that there are 1554 /// no CFG hazards by checking the states of various bottom up pointers. 1555 static void CheckForUseCFGHazard(const Sequence SuccSSeq, 1556 const bool SuccSRRIKnownSafe, 1557 PtrState &S, 1558 bool &SomeSuccHasSame, 1559 bool &AllSuccsHaveSame, 1560 bool &NotAllSeqEqualButKnownSafe, 1561 bool &ShouldContinue) { 1562 switch (SuccSSeq) { 1563 case S_CanRelease: { 1564 if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) { 1565 S.ClearSequenceProgress(); 1566 break; 1567 } 1568 S.SetCFGHazardAfflicted(true); 1569 ShouldContinue = true; 1570 break; 1571 } 1572 case S_Use: 1573 SomeSuccHasSame = true; 1574 break; 1575 case S_Stop: 1576 case S_Release: 1577 case S_MovableRelease: 1578 if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) 1579 AllSuccsHaveSame = false; 1580 else 1581 NotAllSeqEqualButKnownSafe = true; 1582 break; 1583 case S_Retain: 1584 llvm_unreachable("bottom-up pointer in retain state!"); 1585 case S_None: 1586 llvm_unreachable("This should have been handled earlier."); 1587 } 1588 } 1589 1590 /// If we have a Top Down pointer in the S_CanRelease state, make sure that 1591 /// there are no CFG hazards by checking the states of various bottom up 1592 /// pointers. 1593 static void CheckForCanReleaseCFGHazard(const Sequence SuccSSeq, 1594 const bool SuccSRRIKnownSafe, 1595 PtrState &S, 1596 bool &SomeSuccHasSame, 1597 bool &AllSuccsHaveSame, 1598 bool &NotAllSeqEqualButKnownSafe) { 1599 switch (SuccSSeq) { 1600 case S_CanRelease: 1601 SomeSuccHasSame = true; 1602 break; 1603 case S_Stop: 1604 case S_Release: 1605 case S_MovableRelease: 1606 case S_Use: 1607 if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) 1608 AllSuccsHaveSame = false; 1609 else 1610 NotAllSeqEqualButKnownSafe = true; 1611 break; 1612 case S_Retain: 1613 llvm_unreachable("bottom-up pointer in retain state!"); 1614 case S_None: 1615 llvm_unreachable("This should have been handled earlier."); 1616 } 1617 } 1618 1619 /// Check for critical edges, loop boundaries, irreducible control flow, or 1620 /// other CFG structures where moving code across the edge would result in it 1621 /// being executed more. 1622 void 1623 ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB, 1624 DenseMap<const BasicBlock *, BBState> &BBStates, 1625 BBState &MyStates) const { 1626 // If any top-down local-use or possible-dec has a succ which is earlier in 1627 // the sequence, forget it. 1628 for (BBState::ptr_iterator I = MyStates.top_down_ptr_begin(), 1629 E = MyStates.top_down_ptr_end(); I != E; ++I) { 1630 PtrState &S = I->second; 1631 const Sequence Seq = I->second.GetSeq(); 1632 1633 // We only care about S_Retain, S_CanRelease, and S_Use. 1634 if (Seq == S_None) 1635 continue; 1636 1637 // Make sure that if extra top down states are added in the future that this 1638 // code is updated to handle it. 1639 assert((Seq == S_Retain || Seq == S_CanRelease || Seq == S_Use) && 1640 "Unknown top down sequence state."); 1641 1642 const Value *Arg = I->first; 1643 const TerminatorInst *TI = cast<TerminatorInst>(&BB->back()); 1644 bool SomeSuccHasSame = false; 1645 bool AllSuccsHaveSame = true; 1646 bool NotAllSeqEqualButKnownSafe = false; 1647 1648 succ_const_iterator SI(TI), SE(TI, false); 1649 1650 for (; SI != SE; ++SI) { 1651 // If VisitBottomUp has pointer information for this successor, take 1652 // what we know about it. 1653 const DenseMap<const BasicBlock *, BBState>::iterator BBI = 1654 BBStates.find(*SI); 1655 assert(BBI != BBStates.end()); 1656 const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg); 1657 const Sequence SuccSSeq = SuccS.GetSeq(); 1658 1659 // If bottom up, the pointer is in an S_None state, clear the sequence 1660 // progress since the sequence in the bottom up state finished 1661 // suggesting a mismatch in between retains/releases. This is true for 1662 // all three cases that we are handling here: S_Retain, S_Use, and 1663 // S_CanRelease. 1664 if (SuccSSeq == S_None) { 1665 S.ClearSequenceProgress(); 1666 continue; 1667 } 1668 1669 // If we have S_Use or S_CanRelease, perform our check for cfg hazard 1670 // checks. 1671 const bool SuccSRRIKnownSafe = SuccS.IsKnownSafe(); 1672 1673 // *NOTE* We do not use Seq from above here since we are allowing for 1674 // S.GetSeq() to change while we are visiting basic blocks. 1675 switch(S.GetSeq()) { 1676 case S_Use: { 1677 bool ShouldContinue = false; 1678 CheckForUseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S, SomeSuccHasSame, 1679 AllSuccsHaveSame, NotAllSeqEqualButKnownSafe, 1680 ShouldContinue); 1681 if (ShouldContinue) 1682 continue; 1683 break; 1684 } 1685 case S_CanRelease: { 1686 CheckForCanReleaseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S, 1687 SomeSuccHasSame, AllSuccsHaveSame, 1688 NotAllSeqEqualButKnownSafe); 1689 break; 1690 } 1691 case S_Retain: 1692 case S_None: 1693 case S_Stop: 1694 case S_Release: 1695 case S_MovableRelease: 1696 break; 1697 } 1698 } 1699 1700 // If the state at the other end of any of the successor edges 1701 // matches the current state, require all edges to match. This 1702 // guards against loops in the middle of a sequence. 1703 if (SomeSuccHasSame && !AllSuccsHaveSame) { 1704 S.ClearSequenceProgress(); 1705 } else if (NotAllSeqEqualButKnownSafe) { 1706 // If we would have cleared the state foregoing the fact that we are known 1707 // safe, stop code motion. This is because whether or not it is safe to 1708 // remove RR pairs via KnownSafe is an orthogonal concept to whether we 1709 // are allowed to perform code motion. 1710 S.SetCFGHazardAfflicted(true); 1711 } 1712 } 1713 } 1714 1715 bool 1716 ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst, 1717 BasicBlock *BB, 1718 MapVector<Value *, RRInfo> &Retains, 1719 BBState &MyStates) { 1720 bool NestingDetected = false; 1721 InstructionClass Class = GetInstructionClass(Inst); 1722 const Value *Arg = nullptr; 1723 1724 DEBUG(dbgs() << "Class: " << Class << "\n"); 1725 1726 switch (Class) { 1727 case IC_Release: { 1728 Arg = GetObjCArg(Inst); 1729 1730 PtrState &S = MyStates.getPtrBottomUpState(Arg); 1731 1732 // If we see two releases in a row on the same pointer. If so, make 1733 // a note, and we'll cicle back to revisit it after we've 1734 // hopefully eliminated the second release, which may allow us to 1735 // eliminate the first release too. 1736 // Theoretically we could implement removal of nested retain+release 1737 // pairs by making PtrState hold a stack of states, but this is 1738 // simple and avoids adding overhead for the non-nested case. 1739 if (S.GetSeq() == S_Release || S.GetSeq() == S_MovableRelease) { 1740 DEBUG(dbgs() << "Found nested releases (i.e. a release pair)\n"); 1741 NestingDetected = true; 1742 } 1743 1744 MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind); 1745 Sequence NewSeq = ReleaseMetadata ? S_MovableRelease : S_Release; 1746 ANNOTATE_BOTTOMUP(Inst, Arg, S.GetSeq(), NewSeq); 1747 S.ResetSequenceProgress(NewSeq); 1748 S.SetReleaseMetadata(ReleaseMetadata); 1749 S.SetKnownSafe(S.HasKnownPositiveRefCount()); 1750 S.SetTailCallRelease(cast<CallInst>(Inst)->isTailCall()); 1751 S.InsertCall(Inst); 1752 S.SetKnownPositiveRefCount(); 1753 break; 1754 } 1755 case IC_RetainBlock: 1756 // In OptimizeIndividualCalls, we have strength reduced all optimizable 1757 // objc_retainBlocks to objc_retains. Thus at this point any 1758 // objc_retainBlocks that we see are not optimizable. 1759 break; 1760 case IC_Retain: 1761 case IC_RetainRV: { 1762 Arg = GetObjCArg(Inst); 1763 1764 PtrState &S = MyStates.getPtrBottomUpState(Arg); 1765 S.SetKnownPositiveRefCount(); 1766 1767 Sequence OldSeq = S.GetSeq(); 1768 switch (OldSeq) { 1769 case S_Stop: 1770 case S_Release: 1771 case S_MovableRelease: 1772 case S_Use: 1773 // If OldSeq is not S_Use or OldSeq is S_Use and we are tracking an 1774 // imprecise release, clear our reverse insertion points. 1775 if (OldSeq != S_Use || S.IsTrackingImpreciseReleases()) 1776 S.ClearReverseInsertPts(); 1777 // FALL THROUGH 1778 case S_CanRelease: 1779 // Don't do retain+release tracking for IC_RetainRV, because it's 1780 // better to let it remain as the first instruction after a call. 1781 if (Class != IC_RetainRV) 1782 Retains[Inst] = S.GetRRInfo(); 1783 S.ClearSequenceProgress(); 1784 break; 1785 case S_None: 1786 break; 1787 case S_Retain: 1788 llvm_unreachable("bottom-up pointer in retain state!"); 1789 } 1790 ANNOTATE_BOTTOMUP(Inst, Arg, OldSeq, S.GetSeq()); 1791 // A retain moving bottom up can be a use. 1792 break; 1793 } 1794 case IC_AutoreleasepoolPop: 1795 // Conservatively, clear MyStates for all known pointers. 1796 MyStates.clearBottomUpPointers(); 1797 return NestingDetected; 1798 case IC_AutoreleasepoolPush: 1799 case IC_None: 1800 // These are irrelevant. 1801 return NestingDetected; 1802 case IC_User: 1803 // If we have a store into an alloca of a pointer we are tracking, the 1804 // pointer has multiple owners implying that we must be more conservative. 1805 // 1806 // This comes up in the context of a pointer being ``KnownSafe''. In the 1807 // presence of a block being initialized, the frontend will emit the 1808 // objc_retain on the original pointer and the release on the pointer loaded 1809 // from the alloca. The optimizer will through the provenance analysis 1810 // realize that the two are related, but since we only require KnownSafe in 1811 // one direction, will match the inner retain on the original pointer with 1812 // the guard release on the original pointer. This is fixed by ensuring that 1813 // in the presence of allocas we only unconditionally remove pointers if 1814 // both our retain and our release are KnownSafe. 1815 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 1816 if (AreAnyUnderlyingObjectsAnAlloca(SI->getPointerOperand())) { 1817 BBState::ptr_iterator I = MyStates.findPtrBottomUpState( 1818 StripPointerCastsAndObjCCalls(SI->getValueOperand())); 1819 if (I != MyStates.bottom_up_ptr_end()) 1820 MultiOwnersSet.insert(I->first); 1821 } 1822 } 1823 break; 1824 default: 1825 break; 1826 } 1827 1828 // Consider any other possible effects of this instruction on each 1829 // pointer being tracked. 1830 for (BBState::ptr_iterator MI = MyStates.bottom_up_ptr_begin(), 1831 ME = MyStates.bottom_up_ptr_end(); MI != ME; ++MI) { 1832 const Value *Ptr = MI->first; 1833 if (Ptr == Arg) 1834 continue; // Handled above. 1835 PtrState &S = MI->second; 1836 Sequence Seq = S.GetSeq(); 1837 1838 // Check for possible releases. 1839 if (CanAlterRefCount(Inst, Ptr, PA, Class)) { 1840 DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr 1841 << "\n"); 1842 S.ClearKnownPositiveRefCount(); 1843 switch (Seq) { 1844 case S_Use: 1845 S.SetSeq(S_CanRelease); 1846 ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S.GetSeq()); 1847 continue; 1848 case S_CanRelease: 1849 case S_Release: 1850 case S_MovableRelease: 1851 case S_Stop: 1852 case S_None: 1853 break; 1854 case S_Retain: 1855 llvm_unreachable("bottom-up pointer in retain state!"); 1856 } 1857 } 1858 1859 // Check for possible direct uses. 1860 switch (Seq) { 1861 case S_Release: 1862 case S_MovableRelease: 1863 if (CanUse(Inst, Ptr, PA, Class)) { 1864 DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr 1865 << "\n"); 1866 assert(!S.HasReverseInsertPts()); 1867 // If this is an invoke instruction, we're scanning it as part of 1868 // one of its successor blocks, since we can't insert code after it 1869 // in its own block, and we don't want to split critical edges. 1870 if (isa<InvokeInst>(Inst)) 1871 S.InsertReverseInsertPt(BB->getFirstInsertionPt()); 1872 else 1873 S.InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst))); 1874 S.SetSeq(S_Use); 1875 ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S_Use); 1876 } else if (Seq == S_Release && IsUser(Class)) { 1877 DEBUG(dbgs() << "PreciseReleaseUse: Seq: " << Seq << "; " << *Ptr 1878 << "\n"); 1879 // Non-movable releases depend on any possible objc pointer use. 1880 S.SetSeq(S_Stop); 1881 ANNOTATE_BOTTOMUP(Inst, Ptr, S_Release, S_Stop); 1882 assert(!S.HasReverseInsertPts()); 1883 // As above; handle invoke specially. 1884 if (isa<InvokeInst>(Inst)) 1885 S.InsertReverseInsertPt(BB->getFirstInsertionPt()); 1886 else 1887 S.InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst))); 1888 } 1889 break; 1890 case S_Stop: 1891 if (CanUse(Inst, Ptr, PA, Class)) { 1892 DEBUG(dbgs() << "PreciseStopUse: Seq: " << Seq << "; " << *Ptr 1893 << "\n"); 1894 S.SetSeq(S_Use); 1895 ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S_Use); 1896 } 1897 break; 1898 case S_CanRelease: 1899 case S_Use: 1900 case S_None: 1901 break; 1902 case S_Retain: 1903 llvm_unreachable("bottom-up pointer in retain state!"); 1904 } 1905 } 1906 1907 return NestingDetected; 1908 } 1909 1910 bool 1911 ObjCARCOpt::VisitBottomUp(BasicBlock *BB, 1912 DenseMap<const BasicBlock *, BBState> &BBStates, 1913 MapVector<Value *, RRInfo> &Retains) { 1914 1915 DEBUG(dbgs() << "\n== ObjCARCOpt::VisitBottomUp ==\n"); 1916 1917 bool NestingDetected = false; 1918 BBState &MyStates = BBStates[BB]; 1919 1920 // Merge the states from each successor to compute the initial state 1921 // for the current block. 1922 BBState::edge_iterator SI(MyStates.succ_begin()), 1923 SE(MyStates.succ_end()); 1924 if (SI != SE) { 1925 const BasicBlock *Succ = *SI; 1926 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ); 1927 assert(I != BBStates.end()); 1928 MyStates.InitFromSucc(I->second); 1929 ++SI; 1930 for (; SI != SE; ++SI) { 1931 Succ = *SI; 1932 I = BBStates.find(Succ); 1933 assert(I != BBStates.end()); 1934 MyStates.MergeSucc(I->second); 1935 } 1936 } 1937 1938 // If ARC Annotations are enabled, output the current state of pointers at the 1939 // bottom of the basic block. 1940 ANNOTATE_BOTTOMUP_BBEND(MyStates, BB); 1941 1942 // Visit all the instructions, bottom-up. 1943 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) { 1944 Instruction *Inst = std::prev(I); 1945 1946 // Invoke instructions are visited as part of their successors (below). 1947 if (isa<InvokeInst>(Inst)) 1948 continue; 1949 1950 DEBUG(dbgs() << "Visiting " << *Inst << "\n"); 1951 1952 NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates); 1953 } 1954 1955 // If there's a predecessor with an invoke, visit the invoke as if it were 1956 // part of this block, since we can't insert code after an invoke in its own 1957 // block, and we don't want to split critical edges. 1958 for (BBState::edge_iterator PI(MyStates.pred_begin()), 1959 PE(MyStates.pred_end()); PI != PE; ++PI) { 1960 BasicBlock *Pred = *PI; 1961 if (InvokeInst *II = dyn_cast<InvokeInst>(&Pred->back())) 1962 NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates); 1963 } 1964 1965 // If ARC Annotations are enabled, output the current state of pointers at the 1966 // top of the basic block. 1967 ANNOTATE_BOTTOMUP_BBSTART(MyStates, BB); 1968 1969 return NestingDetected; 1970 } 1971 1972 bool 1973 ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst, 1974 DenseMap<Value *, RRInfo> &Releases, 1975 BBState &MyStates) { 1976 bool NestingDetected = false; 1977 InstructionClass Class = GetInstructionClass(Inst); 1978 const Value *Arg = nullptr; 1979 1980 switch (Class) { 1981 case IC_RetainBlock: 1982 // In OptimizeIndividualCalls, we have strength reduced all optimizable 1983 // objc_retainBlocks to objc_retains. Thus at this point any 1984 // objc_retainBlocks that we see are not optimizable. 1985 break; 1986 case IC_Retain: 1987 case IC_RetainRV: { 1988 Arg = GetObjCArg(Inst); 1989 1990 PtrState &S = MyStates.getPtrTopDownState(Arg); 1991 1992 // Don't do retain+release tracking for IC_RetainRV, because it's 1993 // better to let it remain as the first instruction after a call. 1994 if (Class != IC_RetainRV) { 1995 // If we see two retains in a row on the same pointer. If so, make 1996 // a note, and we'll cicle back to revisit it after we've 1997 // hopefully eliminated the second retain, which may allow us to 1998 // eliminate the first retain too. 1999 // Theoretically we could implement removal of nested retain+release 2000 // pairs by making PtrState hold a stack of states, but this is 2001 // simple and avoids adding overhead for the non-nested case. 2002 if (S.GetSeq() == S_Retain) 2003 NestingDetected = true; 2004 2005 ANNOTATE_TOPDOWN(Inst, Arg, S.GetSeq(), S_Retain); 2006 S.ResetSequenceProgress(S_Retain); 2007 S.SetKnownSafe(S.HasKnownPositiveRefCount()); 2008 S.InsertCall(Inst); 2009 } 2010 2011 S.SetKnownPositiveRefCount(); 2012 2013 // A retain can be a potential use; procede to the generic checking 2014 // code below. 2015 break; 2016 } 2017 case IC_Release: { 2018 Arg = GetObjCArg(Inst); 2019 2020 PtrState &S = MyStates.getPtrTopDownState(Arg); 2021 S.ClearKnownPositiveRefCount(); 2022 2023 Sequence OldSeq = S.GetSeq(); 2024 2025 MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind); 2026 2027 switch (OldSeq) { 2028 case S_Retain: 2029 case S_CanRelease: 2030 if (OldSeq == S_Retain || ReleaseMetadata != nullptr) 2031 S.ClearReverseInsertPts(); 2032 // FALL THROUGH 2033 case S_Use: 2034 S.SetReleaseMetadata(ReleaseMetadata); 2035 S.SetTailCallRelease(cast<CallInst>(Inst)->isTailCall()); 2036 Releases[Inst] = S.GetRRInfo(); 2037 ANNOTATE_TOPDOWN(Inst, Arg, S.GetSeq(), S_None); 2038 S.ClearSequenceProgress(); 2039 break; 2040 case S_None: 2041 break; 2042 case S_Stop: 2043 case S_Release: 2044 case S_MovableRelease: 2045 llvm_unreachable("top-down pointer in release state!"); 2046 } 2047 break; 2048 } 2049 case IC_AutoreleasepoolPop: 2050 // Conservatively, clear MyStates for all known pointers. 2051 MyStates.clearTopDownPointers(); 2052 return NestingDetected; 2053 case IC_AutoreleasepoolPush: 2054 case IC_None: 2055 // These are irrelevant. 2056 return NestingDetected; 2057 default: 2058 break; 2059 } 2060 2061 // Consider any other possible effects of this instruction on each 2062 // pointer being tracked. 2063 for (BBState::ptr_iterator MI = MyStates.top_down_ptr_begin(), 2064 ME = MyStates.top_down_ptr_end(); MI != ME; ++MI) { 2065 const Value *Ptr = MI->first; 2066 if (Ptr == Arg) 2067 continue; // Handled above. 2068 PtrState &S = MI->second; 2069 Sequence Seq = S.GetSeq(); 2070 2071 // Check for possible releases. 2072 if (CanAlterRefCount(Inst, Ptr, PA, Class)) { 2073 DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr 2074 << "\n"); 2075 S.ClearKnownPositiveRefCount(); 2076 switch (Seq) { 2077 case S_Retain: 2078 S.SetSeq(S_CanRelease); 2079 ANNOTATE_TOPDOWN(Inst, Ptr, Seq, S_CanRelease); 2080 assert(!S.HasReverseInsertPts()); 2081 S.InsertReverseInsertPt(Inst); 2082 2083 // One call can't cause a transition from S_Retain to S_CanRelease 2084 // and S_CanRelease to S_Use. If we've made the first transition, 2085 // we're done. 2086 continue; 2087 case S_Use: 2088 case S_CanRelease: 2089 case S_None: 2090 break; 2091 case S_Stop: 2092 case S_Release: 2093 case S_MovableRelease: 2094 llvm_unreachable("top-down pointer in release state!"); 2095 } 2096 } 2097 2098 // Check for possible direct uses. 2099 switch (Seq) { 2100 case S_CanRelease: 2101 if (CanUse(Inst, Ptr, PA, Class)) { 2102 DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr 2103 << "\n"); 2104 S.SetSeq(S_Use); 2105 ANNOTATE_TOPDOWN(Inst, Ptr, Seq, S_Use); 2106 } 2107 break; 2108 case S_Retain: 2109 case S_Use: 2110 case S_None: 2111 break; 2112 case S_Stop: 2113 case S_Release: 2114 case S_MovableRelease: 2115 llvm_unreachable("top-down pointer in release state!"); 2116 } 2117 } 2118 2119 return NestingDetected; 2120 } 2121 2122 bool 2123 ObjCARCOpt::VisitTopDown(BasicBlock *BB, 2124 DenseMap<const BasicBlock *, BBState> &BBStates, 2125 DenseMap<Value *, RRInfo> &Releases) { 2126 DEBUG(dbgs() << "\n== ObjCARCOpt::VisitTopDown ==\n"); 2127 bool NestingDetected = false; 2128 BBState &MyStates = BBStates[BB]; 2129 2130 // Merge the states from each predecessor to compute the initial state 2131 // for the current block. 2132 BBState::edge_iterator PI(MyStates.pred_begin()), 2133 PE(MyStates.pred_end()); 2134 if (PI != PE) { 2135 const BasicBlock *Pred = *PI; 2136 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred); 2137 assert(I != BBStates.end()); 2138 MyStates.InitFromPred(I->second); 2139 ++PI; 2140 for (; PI != PE; ++PI) { 2141 Pred = *PI; 2142 I = BBStates.find(Pred); 2143 assert(I != BBStates.end()); 2144 MyStates.MergePred(I->second); 2145 } 2146 } 2147 2148 // If ARC Annotations are enabled, output the current state of pointers at the 2149 // top of the basic block. 2150 ANNOTATE_TOPDOWN_BBSTART(MyStates, BB); 2151 2152 // Visit all the instructions, top-down. 2153 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 2154 Instruction *Inst = I; 2155 2156 DEBUG(dbgs() << "Visiting " << *Inst << "\n"); 2157 2158 NestingDetected |= VisitInstructionTopDown(Inst, Releases, MyStates); 2159 } 2160 2161 // If ARC Annotations are enabled, output the current state of pointers at the 2162 // bottom of the basic block. 2163 ANNOTATE_TOPDOWN_BBEND(MyStates, BB); 2164 2165 #ifdef ARC_ANNOTATIONS 2166 if (!(EnableARCAnnotations && DisableCheckForCFGHazards)) 2167 #endif 2168 CheckForCFGHazards(BB, BBStates, MyStates); 2169 return NestingDetected; 2170 } 2171 2172 static void 2173 ComputePostOrders(Function &F, 2174 SmallVectorImpl<BasicBlock *> &PostOrder, 2175 SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder, 2176 unsigned NoObjCARCExceptionsMDKind, 2177 DenseMap<const BasicBlock *, BBState> &BBStates) { 2178 /// The visited set, for doing DFS walks. 2179 SmallPtrSet<BasicBlock *, 16> Visited; 2180 2181 // Do DFS, computing the PostOrder. 2182 SmallPtrSet<BasicBlock *, 16> OnStack; 2183 SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack; 2184 2185 // Functions always have exactly one entry block, and we don't have 2186 // any other block that we treat like an entry block. 2187 BasicBlock *EntryBB = &F.getEntryBlock(); 2188 BBState &MyStates = BBStates[EntryBB]; 2189 MyStates.SetAsEntry(); 2190 TerminatorInst *EntryTI = cast<TerminatorInst>(&EntryBB->back()); 2191 SuccStack.push_back(std::make_pair(EntryBB, succ_iterator(EntryTI))); 2192 Visited.insert(EntryBB); 2193 OnStack.insert(EntryBB); 2194 do { 2195 dfs_next_succ: 2196 BasicBlock *CurrBB = SuccStack.back().first; 2197 TerminatorInst *TI = cast<TerminatorInst>(&CurrBB->back()); 2198 succ_iterator SE(TI, false); 2199 2200 while (SuccStack.back().second != SE) { 2201 BasicBlock *SuccBB = *SuccStack.back().second++; 2202 if (Visited.insert(SuccBB)) { 2203 TerminatorInst *TI = cast<TerminatorInst>(&SuccBB->back()); 2204 SuccStack.push_back(std::make_pair(SuccBB, succ_iterator(TI))); 2205 BBStates[CurrBB].addSucc(SuccBB); 2206 BBState &SuccStates = BBStates[SuccBB]; 2207 SuccStates.addPred(CurrBB); 2208 OnStack.insert(SuccBB); 2209 goto dfs_next_succ; 2210 } 2211 2212 if (!OnStack.count(SuccBB)) { 2213 BBStates[CurrBB].addSucc(SuccBB); 2214 BBStates[SuccBB].addPred(CurrBB); 2215 } 2216 } 2217 OnStack.erase(CurrBB); 2218 PostOrder.push_back(CurrBB); 2219 SuccStack.pop_back(); 2220 } while (!SuccStack.empty()); 2221 2222 Visited.clear(); 2223 2224 // Do reverse-CFG DFS, computing the reverse-CFG PostOrder. 2225 // Functions may have many exits, and there also blocks which we treat 2226 // as exits due to ignored edges. 2227 SmallVector<std::pair<BasicBlock *, BBState::edge_iterator>, 16> PredStack; 2228 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 2229 BasicBlock *ExitBB = I; 2230 BBState &MyStates = BBStates[ExitBB]; 2231 if (!MyStates.isExit()) 2232 continue; 2233 2234 MyStates.SetAsExit(); 2235 2236 PredStack.push_back(std::make_pair(ExitBB, MyStates.pred_begin())); 2237 Visited.insert(ExitBB); 2238 while (!PredStack.empty()) { 2239 reverse_dfs_next_succ: 2240 BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end(); 2241 while (PredStack.back().second != PE) { 2242 BasicBlock *BB = *PredStack.back().second++; 2243 if (Visited.insert(BB)) { 2244 PredStack.push_back(std::make_pair(BB, BBStates[BB].pred_begin())); 2245 goto reverse_dfs_next_succ; 2246 } 2247 } 2248 ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first); 2249 } 2250 } 2251 } 2252 2253 // Visit the function both top-down and bottom-up. 2254 bool 2255 ObjCARCOpt::Visit(Function &F, 2256 DenseMap<const BasicBlock *, BBState> &BBStates, 2257 MapVector<Value *, RRInfo> &Retains, 2258 DenseMap<Value *, RRInfo> &Releases) { 2259 2260 // Use reverse-postorder traversals, because we magically know that loops 2261 // will be well behaved, i.e. they won't repeatedly call retain on a single 2262 // pointer without doing a release. We can't use the ReversePostOrderTraversal 2263 // class here because we want the reverse-CFG postorder to consider each 2264 // function exit point, and we want to ignore selected cycle edges. 2265 SmallVector<BasicBlock *, 16> PostOrder; 2266 SmallVector<BasicBlock *, 16> ReverseCFGPostOrder; 2267 ComputePostOrders(F, PostOrder, ReverseCFGPostOrder, 2268 NoObjCARCExceptionsMDKind, 2269 BBStates); 2270 2271 // Use reverse-postorder on the reverse CFG for bottom-up. 2272 bool BottomUpNestingDetected = false; 2273 for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I = 2274 ReverseCFGPostOrder.rbegin(), E = ReverseCFGPostOrder.rend(); 2275 I != E; ++I) 2276 BottomUpNestingDetected |= VisitBottomUp(*I, BBStates, Retains); 2277 2278 // Use reverse-postorder for top-down. 2279 bool TopDownNestingDetected = false; 2280 for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I = 2281 PostOrder.rbegin(), E = PostOrder.rend(); 2282 I != E; ++I) 2283 TopDownNestingDetected |= VisitTopDown(*I, BBStates, Releases); 2284 2285 return TopDownNestingDetected && BottomUpNestingDetected; 2286 } 2287 2288 /// Move the calls in RetainsToMove and ReleasesToMove. 2289 void ObjCARCOpt::MoveCalls(Value *Arg, 2290 RRInfo &RetainsToMove, 2291 RRInfo &ReleasesToMove, 2292 MapVector<Value *, RRInfo> &Retains, 2293 DenseMap<Value *, RRInfo> &Releases, 2294 SmallVectorImpl<Instruction *> &DeadInsts, 2295 Module *M) { 2296 Type *ArgTy = Arg->getType(); 2297 Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext())); 2298 2299 DEBUG(dbgs() << "== ObjCARCOpt::MoveCalls ==\n"); 2300 2301 // Insert the new retain and release calls. 2302 for (SmallPtrSet<Instruction *, 2>::const_iterator 2303 PI = ReleasesToMove.ReverseInsertPts.begin(), 2304 PE = ReleasesToMove.ReverseInsertPts.end(); PI != PE; ++PI) { 2305 Instruction *InsertPt = *PI; 2306 Value *MyArg = ArgTy == ParamTy ? Arg : 2307 new BitCastInst(Arg, ParamTy, "", InsertPt); 2308 Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Retain); 2309 CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt); 2310 Call->setDoesNotThrow(); 2311 Call->setTailCall(); 2312 2313 DEBUG(dbgs() << "Inserting new Retain: " << *Call << "\n" 2314 "At insertion point: " << *InsertPt << "\n"); 2315 } 2316 for (SmallPtrSet<Instruction *, 2>::const_iterator 2317 PI = RetainsToMove.ReverseInsertPts.begin(), 2318 PE = RetainsToMove.ReverseInsertPts.end(); PI != PE; ++PI) { 2319 Instruction *InsertPt = *PI; 2320 Value *MyArg = ArgTy == ParamTy ? Arg : 2321 new BitCastInst(Arg, ParamTy, "", InsertPt); 2322 Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Release); 2323 CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt); 2324 // Attach a clang.imprecise_release metadata tag, if appropriate. 2325 if (MDNode *M = ReleasesToMove.ReleaseMetadata) 2326 Call->setMetadata(ImpreciseReleaseMDKind, M); 2327 Call->setDoesNotThrow(); 2328 if (ReleasesToMove.IsTailCallRelease) 2329 Call->setTailCall(); 2330 2331 DEBUG(dbgs() << "Inserting new Release: " << *Call << "\n" 2332 "At insertion point: " << *InsertPt << "\n"); 2333 } 2334 2335 // Delete the original retain and release calls. 2336 for (SmallPtrSet<Instruction *, 2>::const_iterator 2337 AI = RetainsToMove.Calls.begin(), 2338 AE = RetainsToMove.Calls.end(); AI != AE; ++AI) { 2339 Instruction *OrigRetain = *AI; 2340 Retains.blot(OrigRetain); 2341 DeadInsts.push_back(OrigRetain); 2342 DEBUG(dbgs() << "Deleting retain: " << *OrigRetain << "\n"); 2343 } 2344 for (SmallPtrSet<Instruction *, 2>::const_iterator 2345 AI = ReleasesToMove.Calls.begin(), 2346 AE = ReleasesToMove.Calls.end(); AI != AE; ++AI) { 2347 Instruction *OrigRelease = *AI; 2348 Releases.erase(OrigRelease); 2349 DeadInsts.push_back(OrigRelease); 2350 DEBUG(dbgs() << "Deleting release: " << *OrigRelease << "\n"); 2351 } 2352 2353 } 2354 2355 bool 2356 ObjCARCOpt::ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState> 2357 &BBStates, 2358 MapVector<Value *, RRInfo> &Retains, 2359 DenseMap<Value *, RRInfo> &Releases, 2360 Module *M, 2361 SmallVectorImpl<Instruction *> &NewRetains, 2362 SmallVectorImpl<Instruction *> &NewReleases, 2363 SmallVectorImpl<Instruction *> &DeadInsts, 2364 RRInfo &RetainsToMove, 2365 RRInfo &ReleasesToMove, 2366 Value *Arg, 2367 bool KnownSafe, 2368 bool &AnyPairsCompletelyEliminated) { 2369 // If a pair happens in a region where it is known that the reference count 2370 // is already incremented, we can similarly ignore possible decrements unless 2371 // we are dealing with a retainable object with multiple provenance sources. 2372 bool KnownSafeTD = true, KnownSafeBU = true; 2373 bool MultipleOwners = false; 2374 bool CFGHazardAfflicted = false; 2375 2376 // Connect the dots between the top-down-collected RetainsToMove and 2377 // bottom-up-collected ReleasesToMove to form sets of related calls. 2378 // This is an iterative process so that we connect multiple releases 2379 // to multiple retains if needed. 2380 unsigned OldDelta = 0; 2381 unsigned NewDelta = 0; 2382 unsigned OldCount = 0; 2383 unsigned NewCount = 0; 2384 bool FirstRelease = true; 2385 for (;;) { 2386 for (SmallVectorImpl<Instruction *>::const_iterator 2387 NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) { 2388 Instruction *NewRetain = *NI; 2389 MapVector<Value *, RRInfo>::const_iterator It = Retains.find(NewRetain); 2390 assert(It != Retains.end()); 2391 const RRInfo &NewRetainRRI = It->second; 2392 KnownSafeTD &= NewRetainRRI.KnownSafe; 2393 MultipleOwners = 2394 MultipleOwners || MultiOwnersSet.count(GetObjCArg(NewRetain)); 2395 for (SmallPtrSet<Instruction *, 2>::const_iterator 2396 LI = NewRetainRRI.Calls.begin(), 2397 LE = NewRetainRRI.Calls.end(); LI != LE; ++LI) { 2398 Instruction *NewRetainRelease = *LI; 2399 DenseMap<Value *, RRInfo>::const_iterator Jt = 2400 Releases.find(NewRetainRelease); 2401 if (Jt == Releases.end()) 2402 return false; 2403 const RRInfo &NewRetainReleaseRRI = Jt->second; 2404 2405 // If the release does not have a reference to the retain as well, 2406 // something happened which is unaccounted for. Do not do anything. 2407 // 2408 // This can happen if we catch an additive overflow during path count 2409 // merging. 2410 if (!NewRetainReleaseRRI.Calls.count(NewRetain)) 2411 return false; 2412 2413 if (ReleasesToMove.Calls.insert(NewRetainRelease)) { 2414 2415 // If we overflow when we compute the path count, don't remove/move 2416 // anything. 2417 const BBState &NRRBBState = BBStates[NewRetainRelease->getParent()]; 2418 unsigned PathCount = BBState::OverflowOccurredValue; 2419 if (NRRBBState.GetAllPathCountWithOverflow(PathCount)) 2420 return false; 2421 assert(PathCount != BBState::OverflowOccurredValue && 2422 "PathCount at this point can not be " 2423 "OverflowOccurredValue."); 2424 OldDelta -= PathCount; 2425 2426 // Merge the ReleaseMetadata and IsTailCallRelease values. 2427 if (FirstRelease) { 2428 ReleasesToMove.ReleaseMetadata = 2429 NewRetainReleaseRRI.ReleaseMetadata; 2430 ReleasesToMove.IsTailCallRelease = 2431 NewRetainReleaseRRI.IsTailCallRelease; 2432 FirstRelease = false; 2433 } else { 2434 if (ReleasesToMove.ReleaseMetadata != 2435 NewRetainReleaseRRI.ReleaseMetadata) 2436 ReleasesToMove.ReleaseMetadata = nullptr; 2437 if (ReleasesToMove.IsTailCallRelease != 2438 NewRetainReleaseRRI.IsTailCallRelease) 2439 ReleasesToMove.IsTailCallRelease = false; 2440 } 2441 2442 // Collect the optimal insertion points. 2443 if (!KnownSafe) 2444 for (SmallPtrSet<Instruction *, 2>::const_iterator 2445 RI = NewRetainReleaseRRI.ReverseInsertPts.begin(), 2446 RE = NewRetainReleaseRRI.ReverseInsertPts.end(); 2447 RI != RE; ++RI) { 2448 Instruction *RIP = *RI; 2449 if (ReleasesToMove.ReverseInsertPts.insert(RIP)) { 2450 // If we overflow when we compute the path count, don't 2451 // remove/move anything. 2452 const BBState &RIPBBState = BBStates[RIP->getParent()]; 2453 PathCount = BBState::OverflowOccurredValue; 2454 if (RIPBBState.GetAllPathCountWithOverflow(PathCount)) 2455 return false; 2456 assert(PathCount != BBState::OverflowOccurredValue && 2457 "PathCount at this point can not be " 2458 "OverflowOccurredValue."); 2459 NewDelta -= PathCount; 2460 } 2461 } 2462 NewReleases.push_back(NewRetainRelease); 2463 } 2464 } 2465 } 2466 NewRetains.clear(); 2467 if (NewReleases.empty()) break; 2468 2469 // Back the other way. 2470 for (SmallVectorImpl<Instruction *>::const_iterator 2471 NI = NewReleases.begin(), NE = NewReleases.end(); NI != NE; ++NI) { 2472 Instruction *NewRelease = *NI; 2473 DenseMap<Value *, RRInfo>::const_iterator It = 2474 Releases.find(NewRelease); 2475 assert(It != Releases.end()); 2476 const RRInfo &NewReleaseRRI = It->second; 2477 KnownSafeBU &= NewReleaseRRI.KnownSafe; 2478 CFGHazardAfflicted |= NewReleaseRRI.CFGHazardAfflicted; 2479 for (SmallPtrSet<Instruction *, 2>::const_iterator 2480 LI = NewReleaseRRI.Calls.begin(), 2481 LE = NewReleaseRRI.Calls.end(); LI != LE; ++LI) { 2482 Instruction *NewReleaseRetain = *LI; 2483 MapVector<Value *, RRInfo>::const_iterator Jt = 2484 Retains.find(NewReleaseRetain); 2485 if (Jt == Retains.end()) 2486 return false; 2487 const RRInfo &NewReleaseRetainRRI = Jt->second; 2488 2489 // If the retain does not have a reference to the release as well, 2490 // something happened which is unaccounted for. Do not do anything. 2491 // 2492 // This can happen if we catch an additive overflow during path count 2493 // merging. 2494 if (!NewReleaseRetainRRI.Calls.count(NewRelease)) 2495 return false; 2496 2497 if (RetainsToMove.Calls.insert(NewReleaseRetain)) { 2498 // If we overflow when we compute the path count, don't remove/move 2499 // anything. 2500 const BBState &NRRBBState = BBStates[NewReleaseRetain->getParent()]; 2501 unsigned PathCount = BBState::OverflowOccurredValue; 2502 if (NRRBBState.GetAllPathCountWithOverflow(PathCount)) 2503 return false; 2504 assert(PathCount != BBState::OverflowOccurredValue && 2505 "PathCount at this point can not be " 2506 "OverflowOccurredValue."); 2507 OldDelta += PathCount; 2508 OldCount += PathCount; 2509 2510 // Collect the optimal insertion points. 2511 if (!KnownSafe) 2512 for (SmallPtrSet<Instruction *, 2>::const_iterator 2513 RI = NewReleaseRetainRRI.ReverseInsertPts.begin(), 2514 RE = NewReleaseRetainRRI.ReverseInsertPts.end(); 2515 RI != RE; ++RI) { 2516 Instruction *RIP = *RI; 2517 if (RetainsToMove.ReverseInsertPts.insert(RIP)) { 2518 // If we overflow when we compute the path count, don't 2519 // remove/move anything. 2520 const BBState &RIPBBState = BBStates[RIP->getParent()]; 2521 2522 PathCount = BBState::OverflowOccurredValue; 2523 if (RIPBBState.GetAllPathCountWithOverflow(PathCount)) 2524 return false; 2525 assert(PathCount != BBState::OverflowOccurredValue && 2526 "PathCount at this point can not be " 2527 "OverflowOccurredValue."); 2528 NewDelta += PathCount; 2529 NewCount += PathCount; 2530 } 2531 } 2532 NewRetains.push_back(NewReleaseRetain); 2533 } 2534 } 2535 } 2536 NewReleases.clear(); 2537 if (NewRetains.empty()) break; 2538 } 2539 2540 // If the pointer is known incremented in 1 direction and we do not have 2541 // MultipleOwners, we can safely remove the retain/releases. Otherwise we need 2542 // to be known safe in both directions. 2543 bool UnconditionallySafe = (KnownSafeTD && KnownSafeBU) || 2544 ((KnownSafeTD || KnownSafeBU) && !MultipleOwners); 2545 if (UnconditionallySafe) { 2546 RetainsToMove.ReverseInsertPts.clear(); 2547 ReleasesToMove.ReverseInsertPts.clear(); 2548 NewCount = 0; 2549 } else { 2550 // Determine whether the new insertion points we computed preserve the 2551 // balance of retain and release calls through the program. 2552 // TODO: If the fully aggressive solution isn't valid, try to find a 2553 // less aggressive solution which is. 2554 if (NewDelta != 0) 2555 return false; 2556 2557 // At this point, we are not going to remove any RR pairs, but we still are 2558 // able to move RR pairs. If one of our pointers is afflicted with 2559 // CFGHazards, we cannot perform such code motion so exit early. 2560 const bool WillPerformCodeMotion = RetainsToMove.ReverseInsertPts.size() || 2561 ReleasesToMove.ReverseInsertPts.size(); 2562 if (CFGHazardAfflicted && WillPerformCodeMotion) 2563 return false; 2564 } 2565 2566 // Determine whether the original call points are balanced in the retain and 2567 // release calls through the program. If not, conservatively don't touch 2568 // them. 2569 // TODO: It's theoretically possible to do code motion in this case, as 2570 // long as the existing imbalances are maintained. 2571 if (OldDelta != 0) 2572 return false; 2573 2574 #ifdef ARC_ANNOTATIONS 2575 // Do not move calls if ARC annotations are requested. 2576 if (EnableARCAnnotations) 2577 return false; 2578 #endif // ARC_ANNOTATIONS 2579 2580 Changed = true; 2581 assert(OldCount != 0 && "Unreachable code?"); 2582 NumRRs += OldCount - NewCount; 2583 // Set to true if we completely removed any RR pairs. 2584 AnyPairsCompletelyEliminated = NewCount == 0; 2585 2586 // We can move calls! 2587 return true; 2588 } 2589 2590 /// Identify pairings between the retains and releases, and delete and/or move 2591 /// them. 2592 bool 2593 ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState> 2594 &BBStates, 2595 MapVector<Value *, RRInfo> &Retains, 2596 DenseMap<Value *, RRInfo> &Releases, 2597 Module *M) { 2598 DEBUG(dbgs() << "\n== ObjCARCOpt::PerformCodePlacement ==\n"); 2599 2600 bool AnyPairsCompletelyEliminated = false; 2601 RRInfo RetainsToMove; 2602 RRInfo ReleasesToMove; 2603 SmallVector<Instruction *, 4> NewRetains; 2604 SmallVector<Instruction *, 4> NewReleases; 2605 SmallVector<Instruction *, 8> DeadInsts; 2606 2607 // Visit each retain. 2608 for (MapVector<Value *, RRInfo>::const_iterator I = Retains.begin(), 2609 E = Retains.end(); I != E; ++I) { 2610 Value *V = I->first; 2611 if (!V) continue; // blotted 2612 2613 Instruction *Retain = cast<Instruction>(V); 2614 2615 DEBUG(dbgs() << "Visiting: " << *Retain << "\n"); 2616 2617 Value *Arg = GetObjCArg(Retain); 2618 2619 // If the object being released is in static or stack storage, we know it's 2620 // not being managed by ObjC reference counting, so we can delete pairs 2621 // regardless of what possible decrements or uses lie between them. 2622 bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg); 2623 2624 // A constant pointer can't be pointing to an object on the heap. It may 2625 // be reference-counted, but it won't be deleted. 2626 if (const LoadInst *LI = dyn_cast<LoadInst>(Arg)) 2627 if (const GlobalVariable *GV = 2628 dyn_cast<GlobalVariable>( 2629 StripPointerCastsAndObjCCalls(LI->getPointerOperand()))) 2630 if (GV->isConstant()) 2631 KnownSafe = true; 2632 2633 // Connect the dots between the top-down-collected RetainsToMove and 2634 // bottom-up-collected ReleasesToMove to form sets of related calls. 2635 NewRetains.push_back(Retain); 2636 bool PerformMoveCalls = 2637 ConnectTDBUTraversals(BBStates, Retains, Releases, M, NewRetains, 2638 NewReleases, DeadInsts, RetainsToMove, 2639 ReleasesToMove, Arg, KnownSafe, 2640 AnyPairsCompletelyEliminated); 2641 2642 if (PerformMoveCalls) { 2643 // Ok, everything checks out and we're all set. Let's move/delete some 2644 // code! 2645 MoveCalls(Arg, RetainsToMove, ReleasesToMove, 2646 Retains, Releases, DeadInsts, M); 2647 } 2648 2649 // Clean up state for next retain. 2650 NewReleases.clear(); 2651 NewRetains.clear(); 2652 RetainsToMove.clear(); 2653 ReleasesToMove.clear(); 2654 } 2655 2656 // Now that we're done moving everything, we can delete the newly dead 2657 // instructions, as we no longer need them as insert points. 2658 while (!DeadInsts.empty()) 2659 EraseInstruction(DeadInsts.pop_back_val()); 2660 2661 return AnyPairsCompletelyEliminated; 2662 } 2663 2664 /// Weak pointer optimizations. 2665 void ObjCARCOpt::OptimizeWeakCalls(Function &F) { 2666 DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeWeakCalls ==\n"); 2667 2668 // First, do memdep-style RLE and S2L optimizations. We can't use memdep 2669 // itself because it uses AliasAnalysis and we need to do provenance 2670 // queries instead. 2671 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { 2672 Instruction *Inst = &*I++; 2673 2674 DEBUG(dbgs() << "Visiting: " << *Inst << "\n"); 2675 2676 InstructionClass Class = GetBasicInstructionClass(Inst); 2677 if (Class != IC_LoadWeak && Class != IC_LoadWeakRetained) 2678 continue; 2679 2680 // Delete objc_loadWeak calls with no users. 2681 if (Class == IC_LoadWeak && Inst->use_empty()) { 2682 Inst->eraseFromParent(); 2683 continue; 2684 } 2685 2686 // TODO: For now, just look for an earlier available version of this value 2687 // within the same block. Theoretically, we could do memdep-style non-local 2688 // analysis too, but that would want caching. A better approach would be to 2689 // use the technique that EarlyCSE uses. 2690 inst_iterator Current = std::prev(I); 2691 BasicBlock *CurrentBB = Current.getBasicBlockIterator(); 2692 for (BasicBlock::iterator B = CurrentBB->begin(), 2693 J = Current.getInstructionIterator(); 2694 J != B; --J) { 2695 Instruction *EarlierInst = &*std::prev(J); 2696 InstructionClass EarlierClass = GetInstructionClass(EarlierInst); 2697 switch (EarlierClass) { 2698 case IC_LoadWeak: 2699 case IC_LoadWeakRetained: { 2700 // If this is loading from the same pointer, replace this load's value 2701 // with that one. 2702 CallInst *Call = cast<CallInst>(Inst); 2703 CallInst *EarlierCall = cast<CallInst>(EarlierInst); 2704 Value *Arg = Call->getArgOperand(0); 2705 Value *EarlierArg = EarlierCall->getArgOperand(0); 2706 switch (PA.getAA()->alias(Arg, EarlierArg)) { 2707 case AliasAnalysis::MustAlias: 2708 Changed = true; 2709 // If the load has a builtin retain, insert a plain retain for it. 2710 if (Class == IC_LoadWeakRetained) { 2711 Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Retain); 2712 CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call); 2713 CI->setTailCall(); 2714 } 2715 // Zap the fully redundant load. 2716 Call->replaceAllUsesWith(EarlierCall); 2717 Call->eraseFromParent(); 2718 goto clobbered; 2719 case AliasAnalysis::MayAlias: 2720 case AliasAnalysis::PartialAlias: 2721 goto clobbered; 2722 case AliasAnalysis::NoAlias: 2723 break; 2724 } 2725 break; 2726 } 2727 case IC_StoreWeak: 2728 case IC_InitWeak: { 2729 // If this is storing to the same pointer and has the same size etc. 2730 // replace this load's value with the stored value. 2731 CallInst *Call = cast<CallInst>(Inst); 2732 CallInst *EarlierCall = cast<CallInst>(EarlierInst); 2733 Value *Arg = Call->getArgOperand(0); 2734 Value *EarlierArg = EarlierCall->getArgOperand(0); 2735 switch (PA.getAA()->alias(Arg, EarlierArg)) { 2736 case AliasAnalysis::MustAlias: 2737 Changed = true; 2738 // If the load has a builtin retain, insert a plain retain for it. 2739 if (Class == IC_LoadWeakRetained) { 2740 Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Retain); 2741 CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call); 2742 CI->setTailCall(); 2743 } 2744 // Zap the fully redundant load. 2745 Call->replaceAllUsesWith(EarlierCall->getArgOperand(1)); 2746 Call->eraseFromParent(); 2747 goto clobbered; 2748 case AliasAnalysis::MayAlias: 2749 case AliasAnalysis::PartialAlias: 2750 goto clobbered; 2751 case AliasAnalysis::NoAlias: 2752 break; 2753 } 2754 break; 2755 } 2756 case IC_MoveWeak: 2757 case IC_CopyWeak: 2758 // TOOD: Grab the copied value. 2759 goto clobbered; 2760 case IC_AutoreleasepoolPush: 2761 case IC_None: 2762 case IC_IntrinsicUser: 2763 case IC_User: 2764 // Weak pointers are only modified through the weak entry points 2765 // (and arbitrary calls, which could call the weak entry points). 2766 break; 2767 default: 2768 // Anything else could modify the weak pointer. 2769 goto clobbered; 2770 } 2771 } 2772 clobbered:; 2773 } 2774 2775 // Then, for each destroyWeak with an alloca operand, check to see if 2776 // the alloca and all its users can be zapped. 2777 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { 2778 Instruction *Inst = &*I++; 2779 InstructionClass Class = GetBasicInstructionClass(Inst); 2780 if (Class != IC_DestroyWeak) 2781 continue; 2782 2783 CallInst *Call = cast<CallInst>(Inst); 2784 Value *Arg = Call->getArgOperand(0); 2785 if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) { 2786 for (User *U : Alloca->users()) { 2787 const Instruction *UserInst = cast<Instruction>(U); 2788 switch (GetBasicInstructionClass(UserInst)) { 2789 case IC_InitWeak: 2790 case IC_StoreWeak: 2791 case IC_DestroyWeak: 2792 continue; 2793 default: 2794 goto done; 2795 } 2796 } 2797 Changed = true; 2798 for (auto UI = Alloca->user_begin(), UE = Alloca->user_end(); UI != UE;) { 2799 CallInst *UserInst = cast<CallInst>(*UI++); 2800 switch (GetBasicInstructionClass(UserInst)) { 2801 case IC_InitWeak: 2802 case IC_StoreWeak: 2803 // These functions return their second argument. 2804 UserInst->replaceAllUsesWith(UserInst->getArgOperand(1)); 2805 break; 2806 case IC_DestroyWeak: 2807 // No return value. 2808 break; 2809 default: 2810 llvm_unreachable("alloca really is used!"); 2811 } 2812 UserInst->eraseFromParent(); 2813 } 2814 Alloca->eraseFromParent(); 2815 done:; 2816 } 2817 } 2818 } 2819 2820 /// Identify program paths which execute sequences of retains and releases which 2821 /// can be eliminated. 2822 bool ObjCARCOpt::OptimizeSequences(Function &F) { 2823 // Releases, Retains - These are used to store the results of the main flow 2824 // analysis. These use Value* as the key instead of Instruction* so that the 2825 // map stays valid when we get around to rewriting code and calls get 2826 // replaced by arguments. 2827 DenseMap<Value *, RRInfo> Releases; 2828 MapVector<Value *, RRInfo> Retains; 2829 2830 // This is used during the traversal of the function to track the 2831 // states for each identified object at each block. 2832 DenseMap<const BasicBlock *, BBState> BBStates; 2833 2834 // Analyze the CFG of the function, and all instructions. 2835 bool NestingDetected = Visit(F, BBStates, Retains, Releases); 2836 2837 // Transform. 2838 bool AnyPairsCompletelyEliminated = PerformCodePlacement(BBStates, Retains, 2839 Releases, 2840 F.getParent()); 2841 2842 // Cleanup. 2843 MultiOwnersSet.clear(); 2844 2845 return AnyPairsCompletelyEliminated && NestingDetected; 2846 } 2847 2848 /// Check if there is a dependent call earlier that does not have anything in 2849 /// between the Retain and the call that can affect the reference count of their 2850 /// shared pointer argument. Note that Retain need not be in BB. 2851 static bool 2852 HasSafePathToPredecessorCall(const Value *Arg, Instruction *Retain, 2853 SmallPtrSet<Instruction *, 4> &DepInsts, 2854 SmallPtrSet<const BasicBlock *, 4> &Visited, 2855 ProvenanceAnalysis &PA) { 2856 FindDependencies(CanChangeRetainCount, Arg, Retain->getParent(), Retain, 2857 DepInsts, Visited, PA); 2858 if (DepInsts.size() != 1) 2859 return false; 2860 2861 CallInst *Call = 2862 dyn_cast_or_null<CallInst>(*DepInsts.begin()); 2863 2864 // Check that the pointer is the return value of the call. 2865 if (!Call || Arg != Call) 2866 return false; 2867 2868 // Check that the call is a regular call. 2869 InstructionClass Class = GetBasicInstructionClass(Call); 2870 if (Class != IC_CallOrUser && Class != IC_Call) 2871 return false; 2872 2873 return true; 2874 } 2875 2876 /// Find a dependent retain that precedes the given autorelease for which there 2877 /// is nothing in between the two instructions that can affect the ref count of 2878 /// Arg. 2879 static CallInst * 2880 FindPredecessorRetainWithSafePath(const Value *Arg, BasicBlock *BB, 2881 Instruction *Autorelease, 2882 SmallPtrSet<Instruction *, 4> &DepInsts, 2883 SmallPtrSet<const BasicBlock *, 4> &Visited, 2884 ProvenanceAnalysis &PA) { 2885 FindDependencies(CanChangeRetainCount, Arg, 2886 BB, Autorelease, DepInsts, Visited, PA); 2887 if (DepInsts.size() != 1) 2888 return nullptr; 2889 2890 CallInst *Retain = 2891 dyn_cast_or_null<CallInst>(*DepInsts.begin()); 2892 2893 // Check that we found a retain with the same argument. 2894 if (!Retain || 2895 !IsRetain(GetBasicInstructionClass(Retain)) || 2896 GetObjCArg(Retain) != Arg) { 2897 return nullptr; 2898 } 2899 2900 return Retain; 2901 } 2902 2903 /// Look for an ``autorelease'' instruction dependent on Arg such that there are 2904 /// no instructions dependent on Arg that need a positive ref count in between 2905 /// the autorelease and the ret. 2906 static CallInst * 2907 FindPredecessorAutoreleaseWithSafePath(const Value *Arg, BasicBlock *BB, 2908 ReturnInst *Ret, 2909 SmallPtrSet<Instruction *, 4> &DepInsts, 2910 SmallPtrSet<const BasicBlock *, 4> &V, 2911 ProvenanceAnalysis &PA) { 2912 FindDependencies(NeedsPositiveRetainCount, Arg, 2913 BB, Ret, DepInsts, V, PA); 2914 if (DepInsts.size() != 1) 2915 return nullptr; 2916 2917 CallInst *Autorelease = 2918 dyn_cast_or_null<CallInst>(*DepInsts.begin()); 2919 if (!Autorelease) 2920 return nullptr; 2921 InstructionClass AutoreleaseClass = GetBasicInstructionClass(Autorelease); 2922 if (!IsAutorelease(AutoreleaseClass)) 2923 return nullptr; 2924 if (GetObjCArg(Autorelease) != Arg) 2925 return nullptr; 2926 2927 return Autorelease; 2928 } 2929 2930 /// Look for this pattern: 2931 /// \code 2932 /// %call = call i8* @something(...) 2933 /// %2 = call i8* @objc_retain(i8* %call) 2934 /// %3 = call i8* @objc_autorelease(i8* %2) 2935 /// ret i8* %3 2936 /// \endcode 2937 /// And delete the retain and autorelease. 2938 void ObjCARCOpt::OptimizeReturns(Function &F) { 2939 if (!F.getReturnType()->isPointerTy()) 2940 return; 2941 2942 DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeReturns ==\n"); 2943 2944 SmallPtrSet<Instruction *, 4> DependingInstructions; 2945 SmallPtrSet<const BasicBlock *, 4> Visited; 2946 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { 2947 BasicBlock *BB = FI; 2948 ReturnInst *Ret = dyn_cast<ReturnInst>(&BB->back()); 2949 2950 DEBUG(dbgs() << "Visiting: " << *Ret << "\n"); 2951 2952 if (!Ret) 2953 continue; 2954 2955 const Value *Arg = StripPointerCastsAndObjCCalls(Ret->getOperand(0)); 2956 2957 // Look for an ``autorelease'' instruction that is a predecessor of Ret and 2958 // dependent on Arg such that there are no instructions dependent on Arg 2959 // that need a positive ref count in between the autorelease and Ret. 2960 CallInst *Autorelease = 2961 FindPredecessorAutoreleaseWithSafePath(Arg, BB, Ret, 2962 DependingInstructions, Visited, 2963 PA); 2964 DependingInstructions.clear(); 2965 Visited.clear(); 2966 2967 if (!Autorelease) 2968 continue; 2969 2970 CallInst *Retain = 2971 FindPredecessorRetainWithSafePath(Arg, BB, Autorelease, 2972 DependingInstructions, Visited, PA); 2973 DependingInstructions.clear(); 2974 Visited.clear(); 2975 2976 if (!Retain) 2977 continue; 2978 2979 // Check that there is nothing that can affect the reference count 2980 // between the retain and the call. Note that Retain need not be in BB. 2981 bool HasSafePathToCall = HasSafePathToPredecessorCall(Arg, Retain, 2982 DependingInstructions, 2983 Visited, PA); 2984 DependingInstructions.clear(); 2985 Visited.clear(); 2986 2987 if (!HasSafePathToCall) 2988 continue; 2989 2990 // If so, we can zap the retain and autorelease. 2991 Changed = true; 2992 ++NumRets; 2993 DEBUG(dbgs() << "Erasing: " << *Retain << "\nErasing: " 2994 << *Autorelease << "\n"); 2995 EraseInstruction(Retain); 2996 EraseInstruction(Autorelease); 2997 } 2998 } 2999 3000 #ifndef NDEBUG 3001 void 3002 ObjCARCOpt::GatherStatistics(Function &F, bool AfterOptimization) { 3003 llvm::Statistic &NumRetains = 3004 AfterOptimization? NumRetainsAfterOpt : NumRetainsBeforeOpt; 3005 llvm::Statistic &NumReleases = 3006 AfterOptimization? NumReleasesAfterOpt : NumReleasesBeforeOpt; 3007 3008 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { 3009 Instruction *Inst = &*I++; 3010 switch (GetBasicInstructionClass(Inst)) { 3011 default: 3012 break; 3013 case IC_Retain: 3014 ++NumRetains; 3015 break; 3016 case IC_Release: 3017 ++NumReleases; 3018 break; 3019 } 3020 } 3021 } 3022 #endif 3023 3024 bool ObjCARCOpt::doInitialization(Module &M) { 3025 if (!EnableARCOpts) 3026 return false; 3027 3028 // If nothing in the Module uses ARC, don't do anything. 3029 Run = ModuleHasARC(M); 3030 if (!Run) 3031 return false; 3032 3033 // Identify the imprecise release metadata kind. 3034 ImpreciseReleaseMDKind = 3035 M.getContext().getMDKindID("clang.imprecise_release"); 3036 CopyOnEscapeMDKind = 3037 M.getContext().getMDKindID("clang.arc.copy_on_escape"); 3038 NoObjCARCExceptionsMDKind = 3039 M.getContext().getMDKindID("clang.arc.no_objc_arc_exceptions"); 3040 #ifdef ARC_ANNOTATIONS 3041 ARCAnnotationBottomUpMDKind = 3042 M.getContext().getMDKindID("llvm.arc.annotation.bottomup"); 3043 ARCAnnotationTopDownMDKind = 3044 M.getContext().getMDKindID("llvm.arc.annotation.topdown"); 3045 ARCAnnotationProvenanceSourceMDKind = 3046 M.getContext().getMDKindID("llvm.arc.annotation.provenancesource"); 3047 #endif // ARC_ANNOTATIONS 3048 3049 // Intuitively, objc_retain and others are nocapture, however in practice 3050 // they are not, because they return their argument value. And objc_release 3051 // calls finalizers which can have arbitrary side effects. 3052 3053 // Initialize our runtime entry point cache. 3054 EP.Initialize(&M); 3055 3056 return false; 3057 } 3058 3059 bool ObjCARCOpt::runOnFunction(Function &F) { 3060 if (!EnableARCOpts) 3061 return false; 3062 3063 // If nothing in the Module uses ARC, don't do anything. 3064 if (!Run) 3065 return false; 3066 3067 Changed = false; 3068 3069 DEBUG(dbgs() << "<<< ObjCARCOpt: Visiting Function: " << F.getName() << " >>>" 3070 "\n"); 3071 3072 PA.setAA(&getAnalysis<AliasAnalysis>()); 3073 3074 #ifndef NDEBUG 3075 if (AreStatisticsEnabled()) { 3076 GatherStatistics(F, false); 3077 } 3078 #endif 3079 3080 // This pass performs several distinct transformations. As a compile-time aid 3081 // when compiling code that isn't ObjC, skip these if the relevant ObjC 3082 // library functions aren't declared. 3083 3084 // Preliminary optimizations. This also computes UsedInThisFunction. 3085 OptimizeIndividualCalls(F); 3086 3087 // Optimizations for weak pointers. 3088 if (UsedInThisFunction & ((1 << IC_LoadWeak) | 3089 (1 << IC_LoadWeakRetained) | 3090 (1 << IC_StoreWeak) | 3091 (1 << IC_InitWeak) | 3092 (1 << IC_CopyWeak) | 3093 (1 << IC_MoveWeak) | 3094 (1 << IC_DestroyWeak))) 3095 OptimizeWeakCalls(F); 3096 3097 // Optimizations for retain+release pairs. 3098 if (UsedInThisFunction & ((1 << IC_Retain) | 3099 (1 << IC_RetainRV) | 3100 (1 << IC_RetainBlock))) 3101 if (UsedInThisFunction & (1 << IC_Release)) 3102 // Run OptimizeSequences until it either stops making changes or 3103 // no retain+release pair nesting is detected. 3104 while (OptimizeSequences(F)) {} 3105 3106 // Optimizations if objc_autorelease is used. 3107 if (UsedInThisFunction & ((1 << IC_Autorelease) | 3108 (1 << IC_AutoreleaseRV))) 3109 OptimizeReturns(F); 3110 3111 // Gather statistics after optimization. 3112 #ifndef NDEBUG 3113 if (AreStatisticsEnabled()) { 3114 GatherStatistics(F, true); 3115 } 3116 #endif 3117 3118 DEBUG(dbgs() << "\n"); 3119 3120 return Changed; 3121 } 3122 3123 void ObjCARCOpt::releaseMemory() { 3124 PA.clear(); 3125 } 3126 3127 /// @} 3128 /// 3129