lib/Transforms/ObjCARC/ObjCARCOpts.cpp

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