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