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