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