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