LLVM API Documentation

ObjCARCOpts.cpp
Go to the documentation of this file.
00001 //===- ObjCARCOpts.cpp - ObjC ARC Optimization ----------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 /// \file
00010 /// This file defines ObjC ARC optimizations. ARC stands for Automatic
00011 /// Reference Counting and is a system for managing reference counts for objects
00012 /// in Objective C.
00013 ///
00014 /// The optimizations performed include elimination of redundant, partially
00015 /// redundant, and inconsequential reference count operations, elimination of
00016 /// redundant weak pointer operations, and numerous minor simplifications.
00017 ///
00018 /// WARNING: This file knows about certain library functions. It recognizes them
00019 /// by name, and hardwires knowledge of their semantics.
00020 ///
00021 /// WARNING: This file knows about how certain Objective-C library functions are
00022 /// used. Naive LLVM IR transformations which would otherwise be
00023 /// behavior-preserving may break these assumptions.
00024 ///
00025 //===----------------------------------------------------------------------===//
00026 
00027 #include "ObjCARC.h"
00028 #include "ARCRuntimeEntryPoints.h"
00029 #include "DependencyAnalysis.h"
00030 #include "ObjCARCAliasAnalysis.h"
00031 #include "ProvenanceAnalysis.h"
00032 #include "llvm/ADT/DenseMap.h"
00033 #include "llvm/ADT/DenseSet.h"
00034 #include "llvm/ADT/STLExtras.h"
00035 #include "llvm/ADT/SmallPtrSet.h"
00036 #include "llvm/ADT/Statistic.h"
00037 #include "llvm/IR/CFG.h"
00038 #include "llvm/IR/IRBuilder.h"
00039 #include "llvm/IR/LLVMContext.h"
00040 #include "llvm/Support/Debug.h"
00041 #include "llvm/Support/raw_ostream.h"
00042 
00043 using namespace llvm;
00044 using namespace llvm::objcarc;
00045 
00046 #define DEBUG_TYPE "objc-arc-opts"
00047 
00048 /// \defgroup MiscUtils Miscellaneous utilities that are not ARC specific.
00049 /// @{
00050 
00051 namespace {
00052   /// \brief An associative container with fast insertion-order (deterministic)
00053   /// iteration over its elements. Plus the special blot operation.
00054   template<class KeyT, class ValueT>
00055   class MapVector {
00056     /// Map keys to indices in Vector.
00057     typedef DenseMap<KeyT, size_t> MapTy;
00058     MapTy Map;
00059 
00060     typedef std::vector<std::pair<KeyT, ValueT> > VectorTy;
00061     /// Keys and values.
00062     VectorTy Vector;
00063 
00064   public:
00065     typedef typename VectorTy::iterator iterator;
00066     typedef typename VectorTy::const_iterator const_iterator;
00067     iterator begin() { return Vector.begin(); }
00068     iterator end() { return Vector.end(); }
00069     const_iterator begin() const { return Vector.begin(); }
00070     const_iterator end() const { return Vector.end(); }
00071 
00072 #ifdef XDEBUG
00073     ~MapVector() {
00074       assert(Vector.size() >= Map.size()); // May differ due to blotting.
00075       for (typename MapTy::const_iterator I = Map.begin(), E = Map.end();
00076            I != E; ++I) {
00077         assert(I->second < Vector.size());
00078         assert(Vector[I->second].first == I->first);
00079       }
00080       for (typename VectorTy::const_iterator I = Vector.begin(),
00081            E = Vector.end(); I != E; ++I)
00082         assert(!I->first ||
00083                (Map.count(I->first) &&
00084                 Map[I->first] == size_t(I - Vector.begin())));
00085     }
00086 #endif
00087 
00088     ValueT &operator[](const KeyT &Arg) {
00089       std::pair<typename MapTy::iterator, bool> Pair =
00090         Map.insert(std::make_pair(Arg, size_t(0)));
00091       if (Pair.second) {
00092         size_t Num = Vector.size();
00093         Pair.first->second = Num;
00094         Vector.push_back(std::make_pair(Arg, ValueT()));
00095         return Vector[Num].second;
00096       }
00097       return Vector[Pair.first->second].second;
00098     }
00099 
00100     std::pair<iterator, bool>
00101     insert(const std::pair<KeyT, ValueT> &InsertPair) {
00102       std::pair<typename MapTy::iterator, bool> Pair =
00103         Map.insert(std::make_pair(InsertPair.first, size_t(0)));
00104       if (Pair.second) {
00105         size_t Num = Vector.size();
00106         Pair.first->second = Num;
00107         Vector.push_back(InsertPair);
00108         return std::make_pair(Vector.begin() + Num, true);
00109       }
00110       return std::make_pair(Vector.begin() + Pair.first->second, false);
00111     }
00112 
00113     iterator find(const KeyT &Key) {
00114       typename MapTy::iterator It = Map.find(Key);
00115       if (It == Map.end()) return Vector.end();
00116       return Vector.begin() + It->second;
00117     }
00118 
00119     const_iterator find(const KeyT &Key) const {
00120       typename MapTy::const_iterator It = Map.find(Key);
00121       if (It == Map.end()) return Vector.end();
00122       return Vector.begin() + It->second;
00123     }
00124 
00125     /// This is similar to erase, but instead of removing the element from the
00126     /// vector, it just zeros out the key in the vector. This leaves iterators
00127     /// intact, but clients must be prepared for zeroed-out keys when iterating.
00128     void blot(const KeyT &Key) {
00129       typename MapTy::iterator It = Map.find(Key);
00130       if (It == Map.end()) return;
00131       Vector[It->second].first = KeyT();
00132       Map.erase(It);
00133     }
00134 
00135     void clear() {
00136       Map.clear();
00137       Vector.clear();
00138     }
00139   };
00140 }
00141 
00142 /// @}
00143 ///
00144 /// \defgroup ARCUtilities Utility declarations/definitions specific to ARC.
00145 /// @{
00146 
00147 /// \brief This is similar to StripPointerCastsAndObjCCalls but it stops as soon
00148 /// as it finds a value with multiple uses.
00149 static const Value *FindSingleUseIdentifiedObject(const Value *Arg) {
00150   if (Arg->hasOneUse()) {
00151     if (const BitCastInst *BC = dyn_cast<BitCastInst>(Arg))
00152       return FindSingleUseIdentifiedObject(BC->getOperand(0));
00153     if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Arg))
00154       if (GEP->hasAllZeroIndices())
00155         return FindSingleUseIdentifiedObject(GEP->getPointerOperand());
00156     if (IsForwarding(GetBasicInstructionClass(Arg)))
00157       return FindSingleUseIdentifiedObject(
00158                cast<CallInst>(Arg)->getArgOperand(0));
00159     if (!IsObjCIdentifiedObject(Arg))
00160       return nullptr;
00161     return Arg;
00162   }
00163 
00164   // If we found an identifiable object but it has multiple uses, but they are
00165   // trivial uses, we can still consider this to be a single-use value.
00166   if (IsObjCIdentifiedObject(Arg)) {
00167     for (const User *U : Arg->users())
00168       if (!U->use_empty() || StripPointerCastsAndObjCCalls(U) != Arg)
00169          return nullptr;
00170 
00171     return Arg;
00172   }
00173 
00174   return nullptr;
00175 }
00176 
00177 /// This is a wrapper around getUnderlyingObjCPtr along the lines of
00178 /// GetUnderlyingObjects except that it returns early when it sees the first
00179 /// alloca.
00180 static inline bool AreAnyUnderlyingObjectsAnAlloca(const Value *V) {
00181   SmallPtrSet<const Value *, 4> Visited;
00182   SmallVector<const Value *, 4> Worklist;
00183   Worklist.push_back(V);
00184   do {
00185     const Value *P = Worklist.pop_back_val();
00186     P = GetUnderlyingObjCPtr(P);
00187 
00188     if (isa<AllocaInst>(P))
00189       return true;
00190 
00191     if (!Visited.insert(P).second)
00192       continue;
00193 
00194     if (const SelectInst *SI = dyn_cast<const SelectInst>(P)) {
00195       Worklist.push_back(SI->getTrueValue());
00196       Worklist.push_back(SI->getFalseValue());
00197       continue;
00198     }
00199 
00200     if (const PHINode *PN = dyn_cast<const PHINode>(P)) {
00201       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00202         Worklist.push_back(PN->getIncomingValue(i));
00203       continue;
00204     }
00205   } while (!Worklist.empty());
00206 
00207   return false;
00208 }
00209 
00210 
00211 /// @}
00212 ///
00213 /// \defgroup ARCOpt ARC Optimization.
00214 /// @{
00215 
00216 // TODO: On code like this:
00217 //
00218 // objc_retain(%x)
00219 // stuff_that_cannot_release()
00220 // objc_autorelease(%x)
00221 // stuff_that_cannot_release()
00222 // objc_retain(%x)
00223 // stuff_that_cannot_release()
00224 // objc_autorelease(%x)
00225 //
00226 // The second retain and autorelease can be deleted.
00227 
00228 // TODO: It should be possible to delete
00229 // objc_autoreleasePoolPush and objc_autoreleasePoolPop
00230 // pairs if nothing is actually autoreleased between them. Also, autorelease
00231 // calls followed by objc_autoreleasePoolPop calls (perhaps in ObjC++ code
00232 // after inlining) can be turned into plain release calls.
00233 
00234 // TODO: Critical-edge splitting. If the optimial insertion point is
00235 // a critical edge, the current algorithm has to fail, because it doesn't
00236 // know how to split edges. It should be possible to make the optimizer
00237 // think in terms of edges, rather than blocks, and then split critical
00238 // edges on demand.
00239 
00240 // TODO: OptimizeSequences could generalized to be Interprocedural.
00241 
00242 // TODO: Recognize that a bunch of other objc runtime calls have
00243 // non-escaping arguments and non-releasing arguments, and may be
00244 // non-autoreleasing.
00245 
00246 // TODO: Sink autorelease calls as far as possible. Unfortunately we
00247 // usually can't sink them past other calls, which would be the main
00248 // case where it would be useful.
00249 
00250 // TODO: The pointer returned from objc_loadWeakRetained is retained.
00251 
00252 // TODO: Delete release+retain pairs (rare).
00253 
00254 STATISTIC(NumNoops,       "Number of no-op objc calls eliminated");
00255 STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated");
00256 STATISTIC(NumAutoreleases,"Number of autoreleases converted to releases");
00257 STATISTIC(NumRets,        "Number of return value forwarding "
00258                           "retain+autoreleases eliminated");
00259 STATISTIC(NumRRs,         "Number of retain+release paths eliminated");
00260 STATISTIC(NumPeeps,       "Number of calls peephole-optimized");
00261 #ifndef NDEBUG
00262 STATISTIC(NumRetainsBeforeOpt,
00263           "Number of retains before optimization");
00264 STATISTIC(NumReleasesBeforeOpt,
00265           "Number of releases before optimization");
00266 STATISTIC(NumRetainsAfterOpt,
00267           "Number of retains after optimization");
00268 STATISTIC(NumReleasesAfterOpt,
00269           "Number of releases after optimization");
00270 #endif
00271 
00272 namespace {
00273   /// \enum Sequence
00274   ///
00275   /// \brief A sequence of states that a pointer may go through in which an
00276   /// objc_retain and objc_release are actually needed.
00277   enum Sequence {
00278     S_None,
00279     S_Retain,         ///< objc_retain(x).
00280     S_CanRelease,     ///< foo(x) -- x could possibly see a ref count decrement.
00281     S_Use,            ///< any use of x.
00282     S_Stop,           ///< like S_Release, but code motion is stopped.
00283     S_Release,        ///< objc_release(x).
00284     S_MovableRelease  ///< objc_release(x), !clang.imprecise_release.
00285   };
00286 
00287   raw_ostream &operator<<(raw_ostream &OS, const Sequence S)
00288     LLVM_ATTRIBUTE_UNUSED;
00289   raw_ostream &operator<<(raw_ostream &OS, const Sequence S) {
00290     switch (S) {
00291     case S_None:
00292       return OS << "S_None";
00293     case S_Retain:
00294       return OS << "S_Retain";
00295     case S_CanRelease:
00296       return OS << "S_CanRelease";
00297     case S_Use:
00298       return OS << "S_Use";
00299     case S_Release:
00300       return OS << "S_Release";
00301     case S_MovableRelease:
00302       return OS << "S_MovableRelease";
00303     case S_Stop:
00304       return OS << "S_Stop";
00305     }
00306     llvm_unreachable("Unknown sequence type.");
00307   }
00308 }
00309 
00310 static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) {
00311   // The easy cases.
00312   if (A == B)
00313     return A;
00314   if (A == S_None || B == S_None)
00315     return S_None;
00316 
00317   if (A > B) std::swap(A, B);
00318   if (TopDown) {
00319     // Choose the side which is further along in the sequence.
00320     if ((A == S_Retain || A == S_CanRelease) &&
00321         (B == S_CanRelease || B == S_Use))
00322       return B;
00323   } else {
00324     // Choose the side which is further along in the sequence.
00325     if ((A == S_Use || A == S_CanRelease) &&
00326         (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease))
00327       return A;
00328     // If both sides are releases, choose the more conservative one.
00329     if (A == S_Stop && (B == S_Release || B == S_MovableRelease))
00330       return A;
00331     if (A == S_Release && B == S_MovableRelease)
00332       return A;
00333   }
00334 
00335   return S_None;
00336 }
00337 
00338 namespace {
00339   /// \brief Unidirectional information about either a
00340   /// retain-decrement-use-release sequence or release-use-decrement-retain
00341   /// reverse sequence.
00342   struct RRInfo {
00343     /// After an objc_retain, the reference count of the referenced
00344     /// object is known to be positive. Similarly, before an objc_release, the
00345     /// reference count of the referenced object is known to be positive. If
00346     /// there are retain-release pairs in code regions where the retain count
00347     /// is known to be positive, they can be eliminated, regardless of any side
00348     /// effects between them.
00349     ///
00350     /// Also, a retain+release pair nested within another retain+release
00351     /// pair all on the known same pointer value can be eliminated, regardless
00352     /// of any intervening side effects.
00353     ///
00354     /// KnownSafe is true when either of these conditions is satisfied.
00355     bool KnownSafe;
00356 
00357     /// True of the objc_release calls are all marked with the "tail" keyword.
00358     bool IsTailCallRelease;
00359 
00360     /// If the Calls are objc_release calls and they all have a
00361     /// clang.imprecise_release tag, this is the metadata tag.
00362     MDNode *ReleaseMetadata;
00363 
00364     /// For a top-down sequence, the set of objc_retains or
00365     /// objc_retainBlocks. For bottom-up, the set of objc_releases.
00366     SmallPtrSet<Instruction *, 2> Calls;
00367 
00368     /// The set of optimal insert positions for moving calls in the opposite
00369     /// sequence.
00370     SmallPtrSet<Instruction *, 2> ReverseInsertPts;
00371 
00372     /// If this is true, we cannot perform code motion but can still remove
00373     /// retain/release pairs.
00374     bool CFGHazardAfflicted;
00375 
00376     RRInfo() :
00377       KnownSafe(false), IsTailCallRelease(false), ReleaseMetadata(nullptr),
00378       CFGHazardAfflicted(false) {}
00379 
00380     void clear();
00381 
00382     /// Conservatively merge the two RRInfo. Returns true if a partial merge has
00383     /// occurred, false otherwise.
00384     bool Merge(const RRInfo &Other);
00385 
00386   };
00387 }
00388 
00389 void RRInfo::clear() {
00390   KnownSafe = false;
00391   IsTailCallRelease = false;
00392   ReleaseMetadata = nullptr;
00393   Calls.clear();
00394   ReverseInsertPts.clear();
00395   CFGHazardAfflicted = false;
00396 }
00397 
00398 bool RRInfo::Merge(const RRInfo &Other) {
00399     // Conservatively merge the ReleaseMetadata information.
00400     if (ReleaseMetadata != Other.ReleaseMetadata)
00401       ReleaseMetadata = nullptr;
00402 
00403     // Conservatively merge the boolean state.
00404     KnownSafe &= Other.KnownSafe;
00405     IsTailCallRelease &= Other.IsTailCallRelease;
00406     CFGHazardAfflicted |= Other.CFGHazardAfflicted;
00407 
00408     // Merge the call sets.
00409     Calls.insert(Other.Calls.begin(), Other.Calls.end());
00410 
00411     // Merge the insert point sets. If there are any differences,
00412     // that makes this a partial merge.
00413     bool Partial = ReverseInsertPts.size() != Other.ReverseInsertPts.size();
00414     for (Instruction *Inst : Other.ReverseInsertPts)
00415       Partial |= ReverseInsertPts.insert(Inst).second;
00416     return Partial;
00417 }
00418 
00419 namespace {
00420   /// \brief This class summarizes several per-pointer runtime properties which
00421   /// are propogated through the flow graph.
00422   class PtrState {
00423     /// True if the reference count is known to be incremented.
00424     bool KnownPositiveRefCount;
00425 
00426     /// True if we've seen an opportunity for partial RR elimination, such as
00427     /// pushing calls into a CFG triangle or into one side of a CFG diamond.
00428     bool Partial;
00429 
00430     /// The current position in the sequence.
00431     unsigned char Seq : 8;
00432 
00433     /// Unidirectional information about the current sequence.
00434     RRInfo RRI;
00435 
00436   public:
00437     PtrState() : KnownPositiveRefCount(false), Partial(false),
00438                  Seq(S_None) {}
00439 
00440 
00441     bool IsKnownSafe() const {
00442       return RRI.KnownSafe;
00443     }
00444 
00445     void SetKnownSafe(const bool NewValue) {
00446       RRI.KnownSafe = NewValue;
00447     }
00448 
00449     bool IsTailCallRelease() const {
00450       return RRI.IsTailCallRelease;
00451     }
00452 
00453     void SetTailCallRelease(const bool NewValue) {
00454       RRI.IsTailCallRelease = NewValue;
00455     }
00456 
00457     bool IsTrackingImpreciseReleases() const {
00458       return RRI.ReleaseMetadata != nullptr;
00459     }
00460 
00461     const MDNode *GetReleaseMetadata() const {
00462       return RRI.ReleaseMetadata;
00463     }
00464 
00465     void SetReleaseMetadata(MDNode *NewValue) {
00466       RRI.ReleaseMetadata = NewValue;
00467     }
00468 
00469     bool IsCFGHazardAfflicted() const {
00470       return RRI.CFGHazardAfflicted;
00471     }
00472 
00473     void SetCFGHazardAfflicted(const bool NewValue) {
00474       RRI.CFGHazardAfflicted = NewValue;
00475     }
00476 
00477     void SetKnownPositiveRefCount() {
00478       DEBUG(dbgs() << "Setting Known Positive.\n");
00479       KnownPositiveRefCount = true;
00480     }
00481 
00482     void ClearKnownPositiveRefCount() {
00483       DEBUG(dbgs() << "Clearing Known Positive.\n");
00484       KnownPositiveRefCount = false;
00485     }
00486 
00487     bool HasKnownPositiveRefCount() const {
00488       return KnownPositiveRefCount;
00489     }
00490 
00491     void SetSeq(Sequence NewSeq) {
00492       DEBUG(dbgs() << "Old: " << Seq << "; New: " << NewSeq << "\n");
00493       Seq = NewSeq;
00494     }
00495 
00496     Sequence GetSeq() const {
00497       return static_cast<Sequence>(Seq);
00498     }
00499 
00500     void ClearSequenceProgress() {
00501       ResetSequenceProgress(S_None);
00502     }
00503 
00504     void ResetSequenceProgress(Sequence NewSeq) {
00505       DEBUG(dbgs() << "Resetting sequence progress.\n");
00506       SetSeq(NewSeq);
00507       Partial = false;
00508       RRI.clear();
00509     }
00510 
00511     void Merge(const PtrState &Other, bool TopDown);
00512 
00513     void InsertCall(Instruction *I) {
00514       RRI.Calls.insert(I);
00515     }
00516 
00517     void InsertReverseInsertPt(Instruction *I) {
00518       RRI.ReverseInsertPts.insert(I);
00519     }
00520 
00521     void ClearReverseInsertPts() {
00522       RRI.ReverseInsertPts.clear();
00523     }
00524 
00525     bool HasReverseInsertPts() const {
00526       return !RRI.ReverseInsertPts.empty();
00527     }
00528 
00529     const RRInfo &GetRRInfo() const {
00530       return RRI;
00531     }
00532   };
00533 }
00534 
00535 void
00536 PtrState::Merge(const PtrState &Other, bool TopDown) {
00537   Seq = MergeSeqs(GetSeq(), Other.GetSeq(), TopDown);
00538   KnownPositiveRefCount &= Other.KnownPositiveRefCount;
00539 
00540   // If we're not in a sequence (anymore), drop all associated state.
00541   if (Seq == S_None) {
00542     Partial = false;
00543     RRI.clear();
00544   } else if (Partial || Other.Partial) {
00545     // If we're doing a merge on a path that's previously seen a partial
00546     // merge, conservatively drop the sequence, to avoid doing partial
00547     // RR elimination. If the branch predicates for the two merge differ,
00548     // mixing them is unsafe.
00549     ClearSequenceProgress();
00550   } else {
00551     // Otherwise merge the other PtrState's RRInfo into our RRInfo. At this
00552     // point, we know that currently we are not partial. Stash whether or not
00553     // the merge operation caused us to undergo a partial merging of reverse
00554     // insertion points.
00555     Partial = RRI.Merge(Other.RRI);
00556   }
00557 }
00558 
00559 namespace {
00560   /// \brief Per-BasicBlock state.
00561   class BBState {
00562     /// The number of unique control paths from the entry which can reach this
00563     /// block.
00564     unsigned TopDownPathCount;
00565 
00566     /// The number of unique control paths to exits from this block.
00567     unsigned BottomUpPathCount;
00568 
00569     /// A type for PerPtrTopDown and PerPtrBottomUp.
00570     typedef MapVector<const Value *, PtrState> MapTy;
00571 
00572     /// The top-down traversal uses this to record information known about a
00573     /// pointer at the bottom of each block.
00574     MapTy PerPtrTopDown;
00575 
00576     /// The bottom-up traversal uses this to record information known about a
00577     /// pointer at the top of each block.
00578     MapTy PerPtrBottomUp;
00579 
00580     /// Effective predecessors of the current block ignoring ignorable edges and
00581     /// ignored backedges.
00582     SmallVector<BasicBlock *, 2> Preds;
00583     /// Effective successors of the current block ignoring ignorable edges and
00584     /// ignored backedges.
00585     SmallVector<BasicBlock *, 2> Succs;
00586 
00587   public:
00588     static const unsigned OverflowOccurredValue;
00589 
00590     BBState() : TopDownPathCount(0), BottomUpPathCount(0) { }
00591 
00592     typedef MapTy::iterator ptr_iterator;
00593     typedef MapTy::const_iterator ptr_const_iterator;
00594 
00595     ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); }
00596     ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); }
00597     ptr_const_iterator top_down_ptr_begin() const {
00598       return PerPtrTopDown.begin();
00599     }
00600     ptr_const_iterator top_down_ptr_end() const {
00601       return PerPtrTopDown.end();
00602     }
00603 
00604     ptr_iterator bottom_up_ptr_begin() { return PerPtrBottomUp.begin(); }
00605     ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); }
00606     ptr_const_iterator bottom_up_ptr_begin() const {
00607       return PerPtrBottomUp.begin();
00608     }
00609     ptr_const_iterator bottom_up_ptr_end() const {
00610       return PerPtrBottomUp.end();
00611     }
00612 
00613     /// Mark this block as being an entry block, which has one path from the
00614     /// entry by definition.
00615     void SetAsEntry() { TopDownPathCount = 1; }
00616 
00617     /// Mark this block as being an exit block, which has one path to an exit by
00618     /// definition.
00619     void SetAsExit()  { BottomUpPathCount = 1; }
00620 
00621     /// Attempt to find the PtrState object describing the top down state for
00622     /// pointer Arg. Return a new initialized PtrState describing the top down
00623     /// state for Arg if we do not find one.
00624     PtrState &getPtrTopDownState(const Value *Arg) {
00625       return PerPtrTopDown[Arg];
00626     }
00627 
00628     /// Attempt to find the PtrState object describing the bottom up state for
00629     /// pointer Arg. Return a new initialized PtrState describing the bottom up
00630     /// state for Arg if we do not find one.
00631     PtrState &getPtrBottomUpState(const Value *Arg) {
00632       return PerPtrBottomUp[Arg];
00633     }
00634 
00635     /// Attempt to find the PtrState object describing the bottom up state for
00636     /// pointer Arg.
00637     ptr_iterator findPtrBottomUpState(const Value *Arg) {
00638       return PerPtrBottomUp.find(Arg);
00639     }
00640 
00641     void clearBottomUpPointers() {
00642       PerPtrBottomUp.clear();
00643     }
00644 
00645     void clearTopDownPointers() {
00646       PerPtrTopDown.clear();
00647     }
00648 
00649     void InitFromPred(const BBState &Other);
00650     void InitFromSucc(const BBState &Other);
00651     void MergePred(const BBState &Other);
00652     void MergeSucc(const BBState &Other);
00653 
00654     /// Compute the number of possible unique paths from an entry to an exit
00655     /// which pass through this block. This is only valid after both the
00656     /// top-down and bottom-up traversals are complete.
00657     ///
00658     /// Returns true if overflow occurred. Returns false if overflow did not
00659     /// occur.
00660     bool GetAllPathCountWithOverflow(unsigned &PathCount) const {
00661       if (TopDownPathCount == OverflowOccurredValue ||
00662           BottomUpPathCount == OverflowOccurredValue)
00663         return true;
00664       unsigned long long Product =
00665         (unsigned long long)TopDownPathCount*BottomUpPathCount;
00666       // Overflow occurred if any of the upper bits of Product are set or if all
00667       // the lower bits of Product are all set.
00668       return (Product >> 32) ||
00669              ((PathCount = Product) == OverflowOccurredValue);
00670     }
00671 
00672     // Specialized CFG utilities.
00673     typedef SmallVectorImpl<BasicBlock *>::const_iterator edge_iterator;
00674     edge_iterator pred_begin() const { return Preds.begin(); }
00675     edge_iterator pred_end() const { return Preds.end(); }
00676     edge_iterator succ_begin() const { return Succs.begin(); }
00677     edge_iterator succ_end() const { return Succs.end(); }
00678 
00679     void addSucc(BasicBlock *Succ) { Succs.push_back(Succ); }
00680     void addPred(BasicBlock *Pred) { Preds.push_back(Pred); }
00681 
00682     bool isExit() const { return Succs.empty(); }
00683   };
00684 
00685   const unsigned BBState::OverflowOccurredValue = 0xffffffff;
00686 }
00687 
00688 void BBState::InitFromPred(const BBState &Other) {
00689   PerPtrTopDown = Other.PerPtrTopDown;
00690   TopDownPathCount = Other.TopDownPathCount;
00691 }
00692 
00693 void BBState::InitFromSucc(const BBState &Other) {
00694   PerPtrBottomUp = Other.PerPtrBottomUp;
00695   BottomUpPathCount = Other.BottomUpPathCount;
00696 }
00697 
00698 /// The top-down traversal uses this to merge information about predecessors to
00699 /// form the initial state for a new block.
00700 void BBState::MergePred(const BBState &Other) {
00701   if (TopDownPathCount == OverflowOccurredValue)
00702     return;
00703 
00704   // Other.TopDownPathCount can be 0, in which case it is either dead or a
00705   // loop backedge. Loop backedges are special.
00706   TopDownPathCount += Other.TopDownPathCount;
00707 
00708   // In order to be consistent, we clear the top down pointers when by adding
00709   // TopDownPathCount becomes OverflowOccurredValue even though "true" overflow
00710   // has not occurred.
00711   if (TopDownPathCount == OverflowOccurredValue) {
00712     clearTopDownPointers();
00713     return;
00714   }
00715 
00716   // Check for overflow. If we have overflow, fall back to conservative
00717   // behavior.
00718   if (TopDownPathCount < Other.TopDownPathCount) {
00719     TopDownPathCount = OverflowOccurredValue;
00720     clearTopDownPointers();
00721     return;
00722   }
00723 
00724   // For each entry in the other set, if our set has an entry with the same key,
00725   // merge the entries. Otherwise, copy the entry and merge it with an empty
00726   // entry.
00727   for (ptr_const_iterator MI = Other.top_down_ptr_begin(),
00728        ME = Other.top_down_ptr_end(); MI != ME; ++MI) {
00729     std::pair<ptr_iterator, bool> Pair = PerPtrTopDown.insert(*MI);
00730     Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
00731                              /*TopDown=*/true);
00732   }
00733 
00734   // For each entry in our set, if the other set doesn't have an entry with the
00735   // same key, force it to merge with an empty entry.
00736   for (ptr_iterator MI = top_down_ptr_begin(),
00737        ME = top_down_ptr_end(); MI != ME; ++MI)
00738     if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end())
00739       MI->second.Merge(PtrState(), /*TopDown=*/true);
00740 }
00741 
00742 /// The bottom-up traversal uses this to merge information about successors to
00743 /// form the initial state for a new block.
00744 void BBState::MergeSucc(const BBState &Other) {
00745   if (BottomUpPathCount == OverflowOccurredValue)
00746     return;
00747 
00748   // Other.BottomUpPathCount can be 0, in which case it is either dead or a
00749   // loop backedge. Loop backedges are special.
00750   BottomUpPathCount += Other.BottomUpPathCount;
00751 
00752   // In order to be consistent, we clear the top down pointers when by adding
00753   // BottomUpPathCount becomes OverflowOccurredValue even though "true" overflow
00754   // has not occurred.
00755   if (BottomUpPathCount == OverflowOccurredValue) {
00756     clearBottomUpPointers();
00757     return;
00758   }
00759 
00760   // Check for overflow. If we have overflow, fall back to conservative
00761   // behavior.
00762   if (BottomUpPathCount < Other.BottomUpPathCount) {
00763     BottomUpPathCount = OverflowOccurredValue;
00764     clearBottomUpPointers();
00765     return;
00766   }
00767 
00768   // For each entry in the other set, if our set has an entry with the
00769   // same key, merge the entries. Otherwise, copy the entry and merge
00770   // it with an empty entry.
00771   for (ptr_const_iterator MI = Other.bottom_up_ptr_begin(),
00772        ME = Other.bottom_up_ptr_end(); MI != ME; ++MI) {
00773     std::pair<ptr_iterator, bool> Pair = PerPtrBottomUp.insert(*MI);
00774     Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
00775                              /*TopDown=*/false);
00776   }
00777 
00778   // For each entry in our set, if the other set doesn't have an entry
00779   // with the same key, force it to merge with an empty entry.
00780   for (ptr_iterator MI = bottom_up_ptr_begin(),
00781        ME = bottom_up_ptr_end(); MI != ME; ++MI)
00782     if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end())
00783       MI->second.Merge(PtrState(), /*TopDown=*/false);
00784 }
00785 
00786 // Only enable ARC Annotations if we are building a debug version of
00787 // libObjCARCOpts.
00788 #ifndef NDEBUG
00789 #define ARC_ANNOTATIONS
00790 #endif
00791 
00792 // Define some macros along the lines of DEBUG and some helper functions to make
00793 // it cleaner to create annotations in the source code and to no-op when not
00794 // building in debug mode.
00795 #ifdef ARC_ANNOTATIONS
00796 
00797 #include "llvm/Support/CommandLine.h"
00798 
00799 /// Enable/disable ARC sequence annotations.
00800 static cl::opt<bool>
00801 EnableARCAnnotations("enable-objc-arc-annotations", cl::init(false),
00802                      cl::desc("Enable emission of arc data flow analysis "
00803                               "annotations"));
00804 static cl::opt<bool>
00805 DisableCheckForCFGHazards("disable-objc-arc-checkforcfghazards", cl::init(false),
00806                           cl::desc("Disable check for cfg hazards when "
00807                                    "annotating"));
00808 static cl::opt<std::string>
00809 ARCAnnotationTargetIdentifier("objc-arc-annotation-target-identifier",
00810                               cl::init(""),
00811                               cl::desc("filter out all data flow annotations "
00812                                        "but those that apply to the given "
00813                                        "target llvm identifier."));
00814 
00815 /// This function appends a unique ARCAnnotationProvenanceSourceMDKind id to an
00816 /// instruction so that we can track backwards when post processing via the llvm
00817 /// arc annotation processor tool. If the function is an
00818 static MDString *AppendMDNodeToSourcePtr(unsigned NodeId,
00819                                          Value *Ptr) {
00820   MDString *Hash = nullptr;
00821 
00822   // If pointer is a result of an instruction and it does not have a source
00823   // MDNode it, attach a new MDNode onto it. If pointer is a result of
00824   // an instruction and does have a source MDNode attached to it, return a
00825   // reference to said Node. Otherwise just return 0.
00826   if (Instruction *Inst = dyn_cast<Instruction>(Ptr)) {
00827     MDNode *Node;
00828     if (!(Node = Inst->getMetadata(NodeId))) {
00829       // We do not have any node. Generate and attatch the hash MDString to the
00830       // instruction.
00831 
00832       // We just use an MDString to ensure that this metadata gets written out
00833       // of line at the module level and to provide a very simple format
00834       // encoding the information herein. Both of these makes it simpler to
00835       // parse the annotations by a simple external program.
00836       std::string Str;
00837       raw_string_ostream os(Str);
00838       os << "(" << Inst->getParent()->getParent()->getName() << ",%"
00839          << Inst->getName() << ")";
00840 
00841       Hash = MDString::get(Inst->getContext(), os.str());
00842       Inst->setMetadata(NodeId, MDNode::get(Inst->getContext(),Hash));
00843     } else {
00844       // We have a node. Grab its hash and return it.
00845       assert(Node->getNumOperands() == 1 &&
00846         "An ARCAnnotationProvenanceSourceMDKind can only have 1 operand.");
00847       Hash = cast<MDString>(Node->getOperand(0));
00848     }
00849   } else if (Argument *Arg = dyn_cast<Argument>(Ptr)) {
00850     std::string str;
00851     raw_string_ostream os(str);
00852     os << "(" << Arg->getParent()->getName() << ",%" << Arg->getName()
00853        << ")";
00854     Hash = MDString::get(Arg->getContext(), os.str());
00855   }
00856 
00857   return Hash;
00858 }
00859 
00860 static std::string SequenceToString(Sequence A) {
00861   std::string str;
00862   raw_string_ostream os(str);
00863   os << A;
00864   return os.str();
00865 }
00866 
00867 /// Helper function to change a Sequence into a String object using our overload
00868 /// for raw_ostream so we only have printing code in one location.
00869 static MDString *SequenceToMDString(LLVMContext &Context,
00870                                     Sequence A) {
00871   return MDString::get(Context, SequenceToString(A));
00872 }
00873 
00874 /// A simple function to generate a MDNode which describes the change in state
00875 /// for Value *Ptr caused by Instruction *Inst.
00876 static void AppendMDNodeToInstForPtr(unsigned NodeId,
00877                                      Instruction *Inst,
00878                                      Value *Ptr,
00879                                      MDString *PtrSourceMDNodeID,
00880                                      Sequence OldSeq,
00881                                      Sequence NewSeq) {
00882   MDNode *Node = nullptr;
00883   Metadata *tmp[3] = {PtrSourceMDNodeID,
00884                       SequenceToMDString(Inst->getContext(), OldSeq),
00885                       SequenceToMDString(Inst->getContext(), NewSeq)};
00886   Node = MDNode::get(Inst->getContext(), tmp);
00887 
00888   Inst->setMetadata(NodeId, Node);
00889 }
00890 
00891 /// Add to the beginning of the basic block llvm.ptr.annotations which show the
00892 /// state of a pointer at the entrance to a basic block.
00893 static void GenerateARCBBEntranceAnnotation(const char *Name, BasicBlock *BB,
00894                                             Value *Ptr, Sequence Seq) {
00895   // If we have a target identifier, make sure that we match it before
00896   // continuing.
00897   if(!ARCAnnotationTargetIdentifier.empty() &&
00898      !Ptr->getName().equals(ARCAnnotationTargetIdentifier))
00899     return;
00900 
00901   Module *M = BB->getParent()->getParent();
00902   LLVMContext &C = M->getContext();
00903   Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
00904   Type *I8XX = PointerType::getUnqual(I8X);
00905   Type *Params[] = {I8XX, I8XX};
00906   FunctionType *FTy = FunctionType::get(Type::getVoidTy(C), Params,
00907                                         /*isVarArg=*/false);
00908   Constant *Callee = M->getOrInsertFunction(Name, FTy);
00909 
00910   IRBuilder<> Builder(BB, BB->getFirstInsertionPt());
00911 
00912   Value *PtrName;
00913   StringRef Tmp = Ptr->getName();
00914   if (nullptr == (PtrName = M->getGlobalVariable(Tmp, true))) {
00915     Value *ActualPtrName = Builder.CreateGlobalStringPtr(Tmp,
00916                                                          Tmp + "_STR");
00917     PtrName = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage,
00918                                  cast<Constant>(ActualPtrName), Tmp);
00919   }
00920 
00921   Value *S;
00922   std::string SeqStr = SequenceToString(Seq);
00923   if (nullptr == (S = M->getGlobalVariable(SeqStr, true))) {
00924     Value *ActualPtrName = Builder.CreateGlobalStringPtr(SeqStr,
00925                                                          SeqStr + "_STR");
00926     S = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage,
00927                            cast<Constant>(ActualPtrName), SeqStr);
00928   }
00929 
00930   Builder.CreateCall2(Callee, PtrName, S);
00931 }
00932 
00933 /// Add to the end of the basic block llvm.ptr.annotations which show the state
00934 /// of the pointer at the bottom of the basic block.
00935 static void GenerateARCBBTerminatorAnnotation(const char *Name, BasicBlock *BB,
00936                                               Value *Ptr, Sequence Seq) {
00937   // If we have a target identifier, make sure that we match it before emitting
00938   // an annotation.
00939   if(!ARCAnnotationTargetIdentifier.empty() &&
00940      !Ptr->getName().equals(ARCAnnotationTargetIdentifier))
00941     return;
00942 
00943   Module *M = BB->getParent()->getParent();
00944   LLVMContext &C = M->getContext();
00945   Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
00946   Type *I8XX = PointerType::getUnqual(I8X);
00947   Type *Params[] = {I8XX, I8XX};
00948   FunctionType *FTy = FunctionType::get(Type::getVoidTy(C), Params,
00949                                         /*isVarArg=*/false);
00950   Constant *Callee = M->getOrInsertFunction(Name, FTy);
00951 
00952   IRBuilder<> Builder(BB, std::prev(BB->end()));
00953 
00954   Value *PtrName;
00955   StringRef Tmp = Ptr->getName();
00956   if (nullptr == (PtrName = M->getGlobalVariable(Tmp, true))) {
00957     Value *ActualPtrName = Builder.CreateGlobalStringPtr(Tmp,
00958                                                          Tmp + "_STR");
00959     PtrName = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage,
00960                                  cast<Constant>(ActualPtrName), Tmp);
00961   }
00962 
00963   Value *S;
00964   std::string SeqStr = SequenceToString(Seq);
00965   if (nullptr == (S = M->getGlobalVariable(SeqStr, true))) {
00966     Value *ActualPtrName = Builder.CreateGlobalStringPtr(SeqStr,
00967                                                          SeqStr + "_STR");
00968     S = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage,
00969                            cast<Constant>(ActualPtrName), SeqStr);
00970   }
00971   Builder.CreateCall2(Callee, PtrName, S);
00972 }
00973 
00974 /// Adds a source annotation to pointer and a state change annotation to Inst
00975 /// referencing the source annotation and the old/new state of pointer.
00976 static void GenerateARCAnnotation(unsigned InstMDId,
00977                                   unsigned PtrMDId,
00978                                   Instruction *Inst,
00979                                   Value *Ptr,
00980                                   Sequence OldSeq,
00981                                   Sequence NewSeq) {
00982   if (EnableARCAnnotations) {
00983     // If we have a target identifier, make sure that we match it before
00984     // emitting an annotation.
00985     if(!ARCAnnotationTargetIdentifier.empty() &&
00986        !Ptr->getName().equals(ARCAnnotationTargetIdentifier))
00987       return;
00988 
00989     // First generate the source annotation on our pointer. This will return an
00990     // MDString* if Ptr actually comes from an instruction implying we can put
00991     // in a source annotation. If AppendMDNodeToSourcePtr returns 0 (i.e. NULL),
00992     // then we know that our pointer is from an Argument so we put a reference
00993     // to the argument number.
00994     //
00995     // The point of this is to make it easy for the
00996     // llvm-arc-annotation-processor tool to cross reference where the source
00997     // pointer is in the LLVM IR since the LLVM IR parser does not submit such
00998     // information via debug info for backends to use (since why would anyone
00999     // need such a thing from LLVM IR besides in non-standard cases
01000     // [i.e. this]).
01001     MDString *SourcePtrMDNode =
01002       AppendMDNodeToSourcePtr(PtrMDId, Ptr);
01003     AppendMDNodeToInstForPtr(InstMDId, Inst, Ptr, SourcePtrMDNode, OldSeq,
01004                              NewSeq);
01005   }
01006 }
01007 
01008 // The actual interface for accessing the above functionality is defined via
01009 // some simple macros which are defined below. We do this so that the user does
01010 // not need to pass in what metadata id is needed resulting in cleaner code and
01011 // additionally since it provides an easy way to conditionally no-op all
01012 // annotation support in a non-debug build.
01013 
01014 /// Use this macro to annotate a sequence state change when processing
01015 /// instructions bottom up,
01016 #define ANNOTATE_BOTTOMUP(inst, ptr, old, new)                          \
01017   GenerateARCAnnotation(ARCAnnotationBottomUpMDKind,                    \
01018                         ARCAnnotationProvenanceSourceMDKind, (inst),    \
01019                         const_cast<Value*>(ptr), (old), (new))
01020 /// Use this macro to annotate a sequence state change when processing
01021 /// instructions top down.
01022 #define ANNOTATE_TOPDOWN(inst, ptr, old, new)                           \
01023   GenerateARCAnnotation(ARCAnnotationTopDownMDKind,                     \
01024                         ARCAnnotationProvenanceSourceMDKind, (inst),    \
01025                         const_cast<Value*>(ptr), (old), (new))
01026 
01027 #define ANNOTATE_BB(_states, _bb, _name, _type, _direction)                   \
01028   do {                                                                        \
01029     if (EnableARCAnnotations) {                                               \
01030       for(BBState::ptr_const_iterator I = (_states)._direction##_ptr_begin(), \
01031           E = (_states)._direction##_ptr_end(); I != E; ++I) {                \
01032         Value *Ptr = const_cast<Value*>(I->first);                            \
01033         Sequence Seq = I->second.GetSeq();                                    \
01034         GenerateARCBB ## _type ## Annotation(_name, (_bb), Ptr, Seq);         \
01035       }                                                                       \
01036     }                                                                         \
01037   } while (0)
01038 
01039 #define ANNOTATE_BOTTOMUP_BBSTART(_states, _basicblock)                       \
01040     ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.bottomup.bbstart", \
01041                 Entrance, bottom_up)
01042 #define ANNOTATE_BOTTOMUP_BBEND(_states, _basicblock)                         \
01043     ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.bottomup.bbend",   \
01044                 Terminator, bottom_up)
01045 #define ANNOTATE_TOPDOWN_BBSTART(_states, _basicblock)                        \
01046     ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.topdown.bbstart",  \
01047                 Entrance, top_down)
01048 #define ANNOTATE_TOPDOWN_BBEND(_states, _basicblock)                          \
01049     ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.topdown.bbend",    \
01050                 Terminator, top_down)
01051 
01052 #else // !ARC_ANNOTATION
01053 // If annotations are off, noop.
01054 #define ANNOTATE_BOTTOMUP(inst, ptr, old, new)
01055 #define ANNOTATE_TOPDOWN(inst, ptr, old, new)
01056 #define ANNOTATE_BOTTOMUP_BBSTART(states, basicblock)
01057 #define ANNOTATE_BOTTOMUP_BBEND(states, basicblock)
01058 #define ANNOTATE_TOPDOWN_BBSTART(states, basicblock)
01059 #define ANNOTATE_TOPDOWN_BBEND(states, basicblock)
01060 #endif // !ARC_ANNOTATION
01061 
01062 namespace {
01063   /// \brief The main ARC optimization pass.
01064   class ObjCARCOpt : public FunctionPass {
01065     bool Changed;
01066     ProvenanceAnalysis PA;
01067     ARCRuntimeEntryPoints EP;
01068 
01069     // This is used to track if a pointer is stored into an alloca.
01070     DenseSet<const Value *> MultiOwnersSet;
01071 
01072     /// A flag indicating whether this optimization pass should run.
01073     bool Run;
01074 
01075     /// Flags which determine whether each of the interesting runtine functions
01076     /// is in fact used in the current function.
01077     unsigned UsedInThisFunction;
01078 
01079     /// The Metadata Kind for clang.imprecise_release metadata.
01080     unsigned ImpreciseReleaseMDKind;
01081 
01082     /// The Metadata Kind for clang.arc.copy_on_escape metadata.
01083     unsigned CopyOnEscapeMDKind;
01084 
01085     /// The Metadata Kind for clang.arc.no_objc_arc_exceptions metadata.
01086     unsigned NoObjCARCExceptionsMDKind;
01087 
01088 #ifdef ARC_ANNOTATIONS
01089     /// The Metadata Kind for llvm.arc.annotation.bottomup metadata.
01090     unsigned ARCAnnotationBottomUpMDKind;
01091     /// The Metadata Kind for llvm.arc.annotation.topdown metadata.
01092     unsigned ARCAnnotationTopDownMDKind;
01093     /// The Metadata Kind for llvm.arc.annotation.provenancesource metadata.
01094     unsigned ARCAnnotationProvenanceSourceMDKind;
01095 #endif // ARC_ANNOATIONS
01096 
01097     bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV);
01098     void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV,
01099                                    InstructionClass &Class);
01100     void OptimizeIndividualCalls(Function &F);
01101 
01102     void CheckForCFGHazards(const BasicBlock *BB,
01103                             DenseMap<const BasicBlock *, BBState> &BBStates,
01104                             BBState &MyStates) const;
01105     bool VisitInstructionBottomUp(Instruction *Inst,
01106                                   BasicBlock *BB,
01107                                   MapVector<Value *, RRInfo> &Retains,
01108                                   BBState &MyStates);
01109     bool VisitBottomUp(BasicBlock *BB,
01110                        DenseMap<const BasicBlock *, BBState> &BBStates,
01111                        MapVector<Value *, RRInfo> &Retains);
01112     bool VisitInstructionTopDown(Instruction *Inst,
01113                                  DenseMap<Value *, RRInfo> &Releases,
01114                                  BBState &MyStates);
01115     bool VisitTopDown(BasicBlock *BB,
01116                       DenseMap<const BasicBlock *, BBState> &BBStates,
01117                       DenseMap<Value *, RRInfo> &Releases);
01118     bool Visit(Function &F,
01119                DenseMap<const BasicBlock *, BBState> &BBStates,
01120                MapVector<Value *, RRInfo> &Retains,
01121                DenseMap<Value *, RRInfo> &Releases);
01122 
01123     void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove,
01124                    MapVector<Value *, RRInfo> &Retains,
01125                    DenseMap<Value *, RRInfo> &Releases,
01126                    SmallVectorImpl<Instruction *> &DeadInsts,
01127                    Module *M);
01128 
01129     bool ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState> &BBStates,
01130                                MapVector<Value *, RRInfo> &Retains,
01131                                DenseMap<Value *, RRInfo> &Releases,
01132                                Module *M,
01133                                SmallVectorImpl<Instruction *> &NewRetains,
01134                                SmallVectorImpl<Instruction *> &NewReleases,
01135                                SmallVectorImpl<Instruction *> &DeadInsts,
01136                                RRInfo &RetainsToMove,
01137                                RRInfo &ReleasesToMove,
01138                                Value *Arg,
01139                                bool KnownSafe,
01140                                bool &AnyPairsCompletelyEliminated);
01141 
01142     bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates,
01143                               MapVector<Value *, RRInfo> &Retains,
01144                               DenseMap<Value *, RRInfo> &Releases,
01145                               Module *M);
01146 
01147     void OptimizeWeakCalls(Function &F);
01148 
01149     bool OptimizeSequences(Function &F);
01150 
01151     void OptimizeReturns(Function &F);
01152 
01153 #ifndef NDEBUG
01154     void GatherStatistics(Function &F, bool AfterOptimization = false);
01155 #endif
01156 
01157     void getAnalysisUsage(AnalysisUsage &AU) const override;
01158     bool doInitialization(Module &M) override;
01159     bool runOnFunction(Function &F) override;
01160     void releaseMemory() override;
01161 
01162   public:
01163     static char ID;
01164     ObjCARCOpt() : FunctionPass(ID) {
01165       initializeObjCARCOptPass(*PassRegistry::getPassRegistry());
01166     }
01167   };
01168 }
01169 
01170 char ObjCARCOpt::ID = 0;
01171 INITIALIZE_PASS_BEGIN(ObjCARCOpt,
01172                       "objc-arc", "ObjC ARC optimization", false, false)
01173 INITIALIZE_PASS_DEPENDENCY(ObjCARCAliasAnalysis)
01174 INITIALIZE_PASS_END(ObjCARCOpt,
01175                     "objc-arc", "ObjC ARC optimization", false, false)
01176 
01177 Pass *llvm::createObjCARCOptPass() {
01178   return new ObjCARCOpt();
01179 }
01180 
01181 void ObjCARCOpt::getAnalysisUsage(AnalysisUsage &AU) const {
01182   AU.addRequired<ObjCARCAliasAnalysis>();
01183   AU.addRequired<AliasAnalysis>();
01184   // ARC optimization doesn't currently split critical edges.
01185   AU.setPreservesCFG();
01186 }
01187 
01188 /// Turn objc_retainAutoreleasedReturnValue into objc_retain if the operand is
01189 /// not a return value.  Or, if it can be paired with an
01190 /// objc_autoreleaseReturnValue, delete the pair and return true.
01191 bool
01192 ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) {
01193   // Check for the argument being from an immediately preceding call or invoke.
01194   const Value *Arg = GetObjCArg(RetainRV);
01195   ImmutableCallSite CS(Arg);
01196   if (const Instruction *Call = CS.getInstruction()) {
01197     if (Call->getParent() == RetainRV->getParent()) {
01198       BasicBlock::const_iterator I = Call;
01199       ++I;
01200       while (IsNoopInstruction(I)) ++I;
01201       if (&*I == RetainRV)
01202         return false;
01203     } else if (const InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
01204       BasicBlock *RetainRVParent = RetainRV->getParent();
01205       if (II->getNormalDest() == RetainRVParent) {
01206         BasicBlock::const_iterator I = RetainRVParent->begin();
01207         while (IsNoopInstruction(I)) ++I;
01208         if (&*I == RetainRV)
01209           return false;
01210       }
01211     }
01212   }
01213 
01214   // Check for being preceded by an objc_autoreleaseReturnValue on the same
01215   // pointer. In this case, we can delete the pair.
01216   BasicBlock::iterator I = RetainRV, Begin = RetainRV->getParent()->begin();
01217   if (I != Begin) {
01218     do --I; while (I != Begin && IsNoopInstruction(I));
01219     if (GetBasicInstructionClass(I) == IC_AutoreleaseRV &&
01220         GetObjCArg(I) == Arg) {
01221       Changed = true;
01222       ++NumPeeps;
01223 
01224       DEBUG(dbgs() << "Erasing autoreleaseRV,retainRV pair: " << *I << "\n"
01225                    << "Erasing " << *RetainRV << "\n");
01226 
01227       EraseInstruction(I);
01228       EraseInstruction(RetainRV);
01229       return true;
01230     }
01231   }
01232 
01233   // Turn it to a plain objc_retain.
01234   Changed = true;
01235   ++NumPeeps;
01236 
01237   DEBUG(dbgs() << "Transforming objc_retainAutoreleasedReturnValue => "
01238                   "objc_retain since the operand is not a return value.\n"
01239                   "Old = " << *RetainRV << "\n");
01240 
01241   Constant *NewDecl = EP.get(ARCRuntimeEntryPoints::EPT_Retain);
01242   cast<CallInst>(RetainRV)->setCalledFunction(NewDecl);
01243 
01244   DEBUG(dbgs() << "New = " << *RetainRV << "\n");
01245 
01246   return false;
01247 }
01248 
01249 /// Turn objc_autoreleaseReturnValue into objc_autorelease if the result is not
01250 /// used as a return value.
01251 void
01252 ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV,
01253                                       InstructionClass &Class) {
01254   // Check for a return of the pointer value.
01255   const Value *Ptr = GetObjCArg(AutoreleaseRV);
01256   SmallVector<const Value *, 2> Users;
01257   Users.push_back(Ptr);
01258   do {
01259     Ptr = Users.pop_back_val();
01260     for (const User *U : Ptr->users()) {
01261       if (isa<ReturnInst>(U) || GetBasicInstructionClass(U) == IC_RetainRV)
01262         return;
01263       if (isa<BitCastInst>(U))
01264         Users.push_back(U);
01265     }
01266   } while (!Users.empty());
01267 
01268   Changed = true;
01269   ++NumPeeps;
01270 
01271   DEBUG(dbgs() << "Transforming objc_autoreleaseReturnValue => "
01272                   "objc_autorelease since its operand is not used as a return "
01273                   "value.\n"
01274                   "Old = " << *AutoreleaseRV << "\n");
01275 
01276   CallInst *AutoreleaseRVCI = cast<CallInst>(AutoreleaseRV);
01277   Constant *NewDecl = EP.get(ARCRuntimeEntryPoints::EPT_Autorelease);
01278   AutoreleaseRVCI->setCalledFunction(NewDecl);
01279   AutoreleaseRVCI->setTailCall(false); // Never tail call objc_autorelease.
01280   Class = IC_Autorelease;
01281 
01282   DEBUG(dbgs() << "New: " << *AutoreleaseRV << "\n");
01283 
01284 }
01285 
01286 /// Visit each call, one at a time, and make simplifications without doing any
01287 /// additional analysis.
01288 void ObjCARCOpt::OptimizeIndividualCalls(Function &F) {
01289   DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeIndividualCalls ==\n");
01290   // Reset all the flags in preparation for recomputing them.
01291   UsedInThisFunction = 0;
01292 
01293   // Visit all objc_* calls in F.
01294   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
01295     Instruction *Inst = &*I++;
01296 
01297     InstructionClass Class = GetBasicInstructionClass(Inst);
01298 
01299     DEBUG(dbgs() << "Visiting: Class: " << Class << "; " << *Inst << "\n");
01300 
01301     switch (Class) {
01302     default: break;
01303 
01304     // Delete no-op casts. These function calls have special semantics, but
01305     // the semantics are entirely implemented via lowering in the front-end,
01306     // so by the time they reach the optimizer, they are just no-op calls
01307     // which return their argument.
01308     //
01309     // There are gray areas here, as the ability to cast reference-counted
01310     // pointers to raw void* and back allows code to break ARC assumptions,
01311     // however these are currently considered to be unimportant.
01312     case IC_NoopCast:
01313       Changed = true;
01314       ++NumNoops;
01315       DEBUG(dbgs() << "Erasing no-op cast: " << *Inst << "\n");
01316       EraseInstruction(Inst);
01317       continue;
01318 
01319     // If the pointer-to-weak-pointer is null, it's undefined behavior.
01320     case IC_StoreWeak:
01321     case IC_LoadWeak:
01322     case IC_LoadWeakRetained:
01323     case IC_InitWeak:
01324     case IC_DestroyWeak: {
01325       CallInst *CI = cast<CallInst>(Inst);
01326       if (IsNullOrUndef(CI->getArgOperand(0))) {
01327         Changed = true;
01328         Type *Ty = CI->getArgOperand(0)->getType();
01329         new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
01330                       Constant::getNullValue(Ty),
01331                       CI);
01332         llvm::Value *NewValue = UndefValue::get(CI->getType());
01333         DEBUG(dbgs() << "A null pointer-to-weak-pointer is undefined behavior."
01334                        "\nOld = " << *CI << "\nNew = " << *NewValue << "\n");
01335         CI->replaceAllUsesWith(NewValue);
01336         CI->eraseFromParent();
01337         continue;
01338       }
01339       break;
01340     }
01341     case IC_CopyWeak:
01342     case IC_MoveWeak: {
01343       CallInst *CI = cast<CallInst>(Inst);
01344       if (IsNullOrUndef(CI->getArgOperand(0)) ||
01345           IsNullOrUndef(CI->getArgOperand(1))) {
01346         Changed = true;
01347         Type *Ty = CI->getArgOperand(0)->getType();
01348         new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
01349                       Constant::getNullValue(Ty),
01350                       CI);
01351 
01352         llvm::Value *NewValue = UndefValue::get(CI->getType());
01353         DEBUG(dbgs() << "A null pointer-to-weak-pointer is undefined behavior."
01354                         "\nOld = " << *CI << "\nNew = " << *NewValue << "\n");
01355 
01356         CI->replaceAllUsesWith(NewValue);
01357         CI->eraseFromParent();
01358         continue;
01359       }
01360       break;
01361     }
01362     case IC_RetainRV:
01363       if (OptimizeRetainRVCall(F, Inst))
01364         continue;
01365       break;
01366     case IC_AutoreleaseRV:
01367       OptimizeAutoreleaseRVCall(F, Inst, Class);
01368       break;
01369     }
01370 
01371     // objc_autorelease(x) -> objc_release(x) if x is otherwise unused.
01372     if (IsAutorelease(Class) && Inst->use_empty()) {
01373       CallInst *Call = cast<CallInst>(Inst);
01374       const Value *Arg = Call->getArgOperand(0);
01375       Arg = FindSingleUseIdentifiedObject(Arg);
01376       if (Arg) {
01377         Changed = true;
01378         ++NumAutoreleases;
01379 
01380         // Create the declaration lazily.
01381         LLVMContext &C = Inst->getContext();
01382 
01383         Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Release);
01384         CallInst *NewCall = CallInst::Create(Decl, Call->getArgOperand(0), "",
01385                                              Call);
01386         NewCall->setMetadata(ImpreciseReleaseMDKind, MDNode::get(C, None));
01387 
01388         DEBUG(dbgs() << "Replacing autorelease{,RV}(x) with objc_release(x) "
01389               "since x is otherwise unused.\nOld: " << *Call << "\nNew: "
01390               << *NewCall << "\n");
01391 
01392         EraseInstruction(Call);
01393         Inst = NewCall;
01394         Class = IC_Release;
01395       }
01396     }
01397 
01398     // For functions which can never be passed stack arguments, add
01399     // a tail keyword.
01400     if (IsAlwaysTail(Class)) {
01401       Changed = true;
01402       DEBUG(dbgs() << "Adding tail keyword to function since it can never be "
01403                       "passed stack args: " << *Inst << "\n");
01404       cast<CallInst>(Inst)->setTailCall();
01405     }
01406 
01407     // Ensure that functions that can never have a "tail" keyword due to the
01408     // semantics of ARC truly do not do so.
01409     if (IsNeverTail(Class)) {
01410       Changed = true;
01411       DEBUG(dbgs() << "Removing tail keyword from function: " << *Inst <<
01412             "\n");
01413       cast<CallInst>(Inst)->setTailCall(false);
01414     }
01415 
01416     // Set nounwind as needed.
01417     if (IsNoThrow(Class)) {
01418       Changed = true;
01419       DEBUG(dbgs() << "Found no throw class. Setting nounwind on: " << *Inst
01420                    << "\n");
01421       cast<CallInst>(Inst)->setDoesNotThrow();
01422     }
01423 
01424     if (!IsNoopOnNull(Class)) {
01425       UsedInThisFunction |= 1 << Class;
01426       continue;
01427     }
01428 
01429     const Value *Arg = GetObjCArg(Inst);
01430 
01431     // ARC calls with null are no-ops. Delete them.
01432     if (IsNullOrUndef(Arg)) {
01433       Changed = true;
01434       ++NumNoops;
01435       DEBUG(dbgs() << "ARC calls with  null are no-ops. Erasing: " << *Inst
01436             << "\n");
01437       EraseInstruction(Inst);
01438       continue;
01439     }
01440 
01441     // Keep track of which of retain, release, autorelease, and retain_block
01442     // are actually present in this function.
01443     UsedInThisFunction |= 1 << Class;
01444 
01445     // If Arg is a PHI, and one or more incoming values to the
01446     // PHI are null, and the call is control-equivalent to the PHI, and there
01447     // are no relevant side effects between the PHI and the call, the call
01448     // could be pushed up to just those paths with non-null incoming values.
01449     // For now, don't bother splitting critical edges for this.
01450     SmallVector<std::pair<Instruction *, const Value *>, 4> Worklist;
01451     Worklist.push_back(std::make_pair(Inst, Arg));
01452     do {
01453       std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val();
01454       Inst = Pair.first;
01455       Arg = Pair.second;
01456 
01457       const PHINode *PN = dyn_cast<PHINode>(Arg);
01458       if (!PN) continue;
01459 
01460       // Determine if the PHI has any null operands, or any incoming
01461       // critical edges.
01462       bool HasNull = false;
01463       bool HasCriticalEdges = false;
01464       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
01465         Value *Incoming =
01466           StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
01467         if (IsNullOrUndef(Incoming))
01468           HasNull = true;
01469         else if (cast<TerminatorInst>(PN->getIncomingBlock(i)->back())
01470                    .getNumSuccessors() != 1) {
01471           HasCriticalEdges = true;
01472           break;
01473         }
01474       }
01475       // If we have null operands and no critical edges, optimize.
01476       if (!HasCriticalEdges && HasNull) {
01477         SmallPtrSet<Instruction *, 4> DependingInstructions;
01478         SmallPtrSet<const BasicBlock *, 4> Visited;
01479 
01480         // Check that there is nothing that cares about the reference
01481         // count between the call and the phi.
01482         switch (Class) {
01483         case IC_Retain:
01484         case IC_RetainBlock:
01485           // These can always be moved up.
01486           break;
01487         case IC_Release:
01488           // These can't be moved across things that care about the retain
01489           // count.
01490           FindDependencies(NeedsPositiveRetainCount, Arg,
01491                            Inst->getParent(), Inst,
01492                            DependingInstructions, Visited, PA);
01493           break;
01494         case IC_Autorelease:
01495           // These can't be moved across autorelease pool scope boundaries.
01496           FindDependencies(AutoreleasePoolBoundary, Arg,
01497                            Inst->getParent(), Inst,
01498                            DependingInstructions, Visited, PA);
01499           break;
01500         case IC_RetainRV:
01501         case IC_AutoreleaseRV:
01502           // Don't move these; the RV optimization depends on the autoreleaseRV
01503           // being tail called, and the retainRV being immediately after a call
01504           // (which might still happen if we get lucky with codegen layout, but
01505           // it's not worth taking the chance).
01506           continue;
01507         default:
01508           llvm_unreachable("Invalid dependence flavor");
01509         }
01510 
01511         if (DependingInstructions.size() == 1 &&
01512             *DependingInstructions.begin() == PN) {
01513           Changed = true;
01514           ++NumPartialNoops;
01515           // Clone the call into each predecessor that has a non-null value.
01516           CallInst *CInst = cast<CallInst>(Inst);
01517           Type *ParamTy = CInst->getArgOperand(0)->getType();
01518           for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
01519             Value *Incoming =
01520               StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
01521             if (!IsNullOrUndef(Incoming)) {
01522               CallInst *Clone = cast<CallInst>(CInst->clone());
01523               Value *Op = PN->getIncomingValue(i);
01524               Instruction *InsertPos = &PN->getIncomingBlock(i)->back();
01525               if (Op->getType() != ParamTy)
01526                 Op = new BitCastInst(Op, ParamTy, "", InsertPos);
01527               Clone->setArgOperand(0, Op);
01528               Clone->insertBefore(InsertPos);
01529 
01530               DEBUG(dbgs() << "Cloning "
01531                            << *CInst << "\n"
01532                            "And inserting clone at " << *InsertPos << "\n");
01533               Worklist.push_back(std::make_pair(Clone, Incoming));
01534             }
01535           }
01536           // Erase the original call.
01537           DEBUG(dbgs() << "Erasing: " << *CInst << "\n");
01538           EraseInstruction(CInst);
01539           continue;
01540         }
01541       }
01542     } while (!Worklist.empty());
01543   }
01544 }
01545 
01546 /// If we have a top down pointer in the S_Use state, make sure that there are
01547 /// no CFG hazards by checking the states of various bottom up pointers.
01548 static void CheckForUseCFGHazard(const Sequence SuccSSeq,
01549                                  const bool SuccSRRIKnownSafe,
01550                                  PtrState &S,
01551                                  bool &SomeSuccHasSame,
01552                                  bool &AllSuccsHaveSame,
01553                                  bool &NotAllSeqEqualButKnownSafe,
01554                                  bool &ShouldContinue) {
01555   switch (SuccSSeq) {
01556   case S_CanRelease: {
01557     if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) {
01558       S.ClearSequenceProgress();
01559       break;
01560     }
01561     S.SetCFGHazardAfflicted(true);
01562     ShouldContinue = true;
01563     break;
01564   }
01565   case S_Use:
01566     SomeSuccHasSame = true;
01567     break;
01568   case S_Stop:
01569   case S_Release:
01570   case S_MovableRelease:
01571     if (!S.IsKnownSafe() && !SuccSRRIKnownSafe)
01572       AllSuccsHaveSame = false;
01573     else
01574       NotAllSeqEqualButKnownSafe = true;
01575     break;
01576   case S_Retain:
01577     llvm_unreachable("bottom-up pointer in retain state!");
01578   case S_None:
01579     llvm_unreachable("This should have been handled earlier.");
01580   }
01581 }
01582 
01583 /// If we have a Top Down pointer in the S_CanRelease state, make sure that
01584 /// there are no CFG hazards by checking the states of various bottom up
01585 /// pointers.
01586 static void CheckForCanReleaseCFGHazard(const Sequence SuccSSeq,
01587                                         const bool SuccSRRIKnownSafe,
01588                                         PtrState &S,
01589                                         bool &SomeSuccHasSame,
01590                                         bool &AllSuccsHaveSame,
01591                                         bool &NotAllSeqEqualButKnownSafe) {
01592   switch (SuccSSeq) {
01593   case S_CanRelease:
01594     SomeSuccHasSame = true;
01595     break;
01596   case S_Stop:
01597   case S_Release:
01598   case S_MovableRelease:
01599   case S_Use:
01600     if (!S.IsKnownSafe() && !SuccSRRIKnownSafe)
01601       AllSuccsHaveSame = false;
01602     else
01603       NotAllSeqEqualButKnownSafe = true;
01604     break;
01605   case S_Retain:
01606     llvm_unreachable("bottom-up pointer in retain state!");
01607   case S_None:
01608     llvm_unreachable("This should have been handled earlier.");
01609   }
01610 }
01611 
01612 /// Check for critical edges, loop boundaries, irreducible control flow, or
01613 /// other CFG structures where moving code across the edge would result in it
01614 /// being executed more.
01615 void
01616 ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB,
01617                                DenseMap<const BasicBlock *, BBState> &BBStates,
01618                                BBState &MyStates) const {
01619   // If any top-down local-use or possible-dec has a succ which is earlier in
01620   // the sequence, forget it.
01621   for (BBState::ptr_iterator I = MyStates.top_down_ptr_begin(),
01622          E = MyStates.top_down_ptr_end(); I != E; ++I) {
01623     PtrState &S = I->second;
01624     const Sequence Seq = I->second.GetSeq();
01625 
01626     // We only care about S_Retain, S_CanRelease, and S_Use.
01627     if (Seq == S_None)
01628       continue;
01629 
01630     // Make sure that if extra top down states are added in the future that this
01631     // code is updated to handle it.
01632     assert((Seq == S_Retain || Seq == S_CanRelease || Seq == S_Use) &&
01633            "Unknown top down sequence state.");
01634 
01635     const Value *Arg = I->first;
01636     const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
01637     bool SomeSuccHasSame = false;
01638     bool AllSuccsHaveSame = true;
01639     bool NotAllSeqEqualButKnownSafe = false;
01640 
01641     succ_const_iterator SI(TI), SE(TI, false);
01642 
01643     for (; SI != SE; ++SI) {
01644       // If VisitBottomUp has pointer information for this successor, take
01645       // what we know about it.
01646       const DenseMap<const BasicBlock *, BBState>::iterator BBI =
01647         BBStates.find(*SI);
01648       assert(BBI != BBStates.end());
01649       const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);
01650       const Sequence SuccSSeq = SuccS.GetSeq();
01651 
01652       // If bottom up, the pointer is in an S_None state, clear the sequence
01653       // progress since the sequence in the bottom up state finished
01654       // suggesting a mismatch in between retains/releases. This is true for
01655       // all three cases that we are handling here: S_Retain, S_Use, and
01656       // S_CanRelease.
01657       if (SuccSSeq == S_None) {
01658         S.ClearSequenceProgress();
01659         continue;
01660       }
01661 
01662       // If we have S_Use or S_CanRelease, perform our check for cfg hazard
01663       // checks.
01664       const bool SuccSRRIKnownSafe = SuccS.IsKnownSafe();
01665 
01666       // *NOTE* We do not use Seq from above here since we are allowing for
01667       // S.GetSeq() to change while we are visiting basic blocks.
01668       switch(S.GetSeq()) {
01669       case S_Use: {
01670         bool ShouldContinue = false;
01671         CheckForUseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S, SomeSuccHasSame,
01672                              AllSuccsHaveSame, NotAllSeqEqualButKnownSafe,
01673                              ShouldContinue);
01674         if (ShouldContinue)
01675           continue;
01676         break;
01677       }
01678       case S_CanRelease: {
01679         CheckForCanReleaseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S,
01680                                     SomeSuccHasSame, AllSuccsHaveSame,
01681                                     NotAllSeqEqualButKnownSafe);
01682         break;
01683       }
01684       case S_Retain:
01685       case S_None:
01686       case S_Stop:
01687       case S_Release:
01688       case S_MovableRelease:
01689         break;
01690       }
01691     }
01692 
01693     // If the state at the other end of any of the successor edges
01694     // matches the current state, require all edges to match. This
01695     // guards against loops in the middle of a sequence.
01696     if (SomeSuccHasSame && !AllSuccsHaveSame) {
01697       S.ClearSequenceProgress();
01698     } else if (NotAllSeqEqualButKnownSafe) {
01699       // If we would have cleared the state foregoing the fact that we are known
01700       // safe, stop code motion. This is because whether or not it is safe to
01701       // remove RR pairs via KnownSafe is an orthogonal concept to whether we
01702       // are allowed to perform code motion.
01703       S.SetCFGHazardAfflicted(true);
01704     }
01705   }
01706 }
01707 
01708 bool
01709 ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst,
01710                                      BasicBlock *BB,
01711                                      MapVector<Value *, RRInfo> &Retains,
01712                                      BBState &MyStates) {
01713   bool NestingDetected = false;
01714   InstructionClass Class = GetInstructionClass(Inst);
01715   const Value *Arg = nullptr;
01716 
01717   DEBUG(dbgs() << "Class: " << Class << "\n");
01718 
01719   switch (Class) {
01720   case IC_Release: {
01721     Arg = GetObjCArg(Inst);
01722 
01723     PtrState &S = MyStates.getPtrBottomUpState(Arg);
01724 
01725     // If we see two releases in a row on the same pointer. If so, make
01726     // a note, and we'll cicle back to revisit it after we've
01727     // hopefully eliminated the second release, which may allow us to
01728     // eliminate the first release too.
01729     // Theoretically we could implement removal of nested retain+release
01730     // pairs by making PtrState hold a stack of states, but this is
01731     // simple and avoids adding overhead for the non-nested case.
01732     if (S.GetSeq() == S_Release || S.GetSeq() == S_MovableRelease) {
01733       DEBUG(dbgs() << "Found nested releases (i.e. a release pair)\n");
01734       NestingDetected = true;
01735     }
01736 
01737     MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind);
01738     Sequence NewSeq = ReleaseMetadata ? S_MovableRelease : S_Release;
01739     ANNOTATE_BOTTOMUP(Inst, Arg, S.GetSeq(), NewSeq);
01740     S.ResetSequenceProgress(NewSeq);
01741     S.SetReleaseMetadata(ReleaseMetadata);
01742     S.SetKnownSafe(S.HasKnownPositiveRefCount());
01743     S.SetTailCallRelease(cast<CallInst>(Inst)->isTailCall());
01744     S.InsertCall(Inst);
01745     S.SetKnownPositiveRefCount();
01746     break;
01747   }
01748   case IC_RetainBlock:
01749     // In OptimizeIndividualCalls, we have strength reduced all optimizable
01750     // objc_retainBlocks to objc_retains. Thus at this point any
01751     // objc_retainBlocks that we see are not optimizable.
01752     break;
01753   case IC_Retain:
01754   case IC_RetainRV: {
01755     Arg = GetObjCArg(Inst);
01756 
01757     PtrState &S = MyStates.getPtrBottomUpState(Arg);
01758     S.SetKnownPositiveRefCount();
01759 
01760     Sequence OldSeq = S.GetSeq();
01761     switch (OldSeq) {
01762     case S_Stop:
01763     case S_Release:
01764     case S_MovableRelease:
01765     case S_Use:
01766       // If OldSeq is not S_Use or OldSeq is S_Use and we are tracking an
01767       // imprecise release, clear our reverse insertion points.
01768       if (OldSeq != S_Use || S.IsTrackingImpreciseReleases())
01769         S.ClearReverseInsertPts();
01770       // FALL THROUGH
01771     case S_CanRelease:
01772       // Don't do retain+release tracking for IC_RetainRV, because it's
01773       // better to let it remain as the first instruction after a call.
01774       if (Class != IC_RetainRV)
01775         Retains[Inst] = S.GetRRInfo();
01776       S.ClearSequenceProgress();
01777       break;
01778     case S_None:
01779       break;
01780     case S_Retain:
01781       llvm_unreachable("bottom-up pointer in retain state!");
01782     }
01783     ANNOTATE_BOTTOMUP(Inst, Arg, OldSeq, S.GetSeq());
01784     // A retain moving bottom up can be a use.
01785     break;
01786   }
01787   case IC_AutoreleasepoolPop:
01788     // Conservatively, clear MyStates for all known pointers.
01789     MyStates.clearBottomUpPointers();
01790     return NestingDetected;
01791   case IC_AutoreleasepoolPush:
01792   case IC_None:
01793     // These are irrelevant.
01794     return NestingDetected;
01795   case IC_User:
01796     // If we have a store into an alloca of a pointer we are tracking, the
01797     // pointer has multiple owners implying that we must be more conservative.
01798     //
01799     // This comes up in the context of a pointer being ``KnownSafe''. In the
01800     // presence of a block being initialized, the frontend will emit the
01801     // objc_retain on the original pointer and the release on the pointer loaded
01802     // from the alloca. The optimizer will through the provenance analysis
01803     // realize that the two are related, but since we only require KnownSafe in
01804     // one direction, will match the inner retain on the original pointer with
01805     // the guard release on the original pointer. This is fixed by ensuring that
01806     // in the presence of allocas we only unconditionally remove pointers if
01807     // both our retain and our release are KnownSafe.
01808     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
01809       if (AreAnyUnderlyingObjectsAnAlloca(SI->getPointerOperand())) {
01810         BBState::ptr_iterator I = MyStates.findPtrBottomUpState(
01811           StripPointerCastsAndObjCCalls(SI->getValueOperand()));
01812         if (I != MyStates.bottom_up_ptr_end())
01813           MultiOwnersSet.insert(I->first);
01814       }
01815     }
01816     break;
01817   default:
01818     break;
01819   }
01820 
01821   // Consider any other possible effects of this instruction on each
01822   // pointer being tracked.
01823   for (BBState::ptr_iterator MI = MyStates.bottom_up_ptr_begin(),
01824        ME = MyStates.bottom_up_ptr_end(); MI != ME; ++MI) {
01825     const Value *Ptr = MI->first;
01826     if (Ptr == Arg)
01827       continue; // Handled above.
01828     PtrState &S = MI->second;
01829     Sequence Seq = S.GetSeq();
01830 
01831     // Check for possible releases.
01832     if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
01833       DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr
01834             << "\n");
01835       S.ClearKnownPositiveRefCount();
01836       switch (Seq) {
01837       case S_Use:
01838         S.SetSeq(S_CanRelease);
01839         ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S.GetSeq());
01840         continue;
01841       case S_CanRelease:
01842       case S_Release:
01843       case S_MovableRelease:
01844       case S_Stop:
01845       case S_None:
01846         break;
01847       case S_Retain:
01848         llvm_unreachable("bottom-up pointer in retain state!");
01849       }
01850     }
01851 
01852     // Check for possible direct uses.
01853     switch (Seq) {
01854     case S_Release:
01855     case S_MovableRelease:
01856       if (CanUse(Inst, Ptr, PA, Class)) {
01857         DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr
01858               << "\n");
01859         assert(!S.HasReverseInsertPts());
01860         // If this is an invoke instruction, we're scanning it as part of
01861         // one of its successor blocks, since we can't insert code after it
01862         // in its own block, and we don't want to split critical edges.
01863         if (isa<InvokeInst>(Inst))
01864           S.InsertReverseInsertPt(BB->getFirstInsertionPt());
01865         else
01866           S.InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst)));
01867         S.SetSeq(S_Use);
01868         ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S_Use);
01869       } else if (Seq == S_Release && IsUser(Class)) {
01870         DEBUG(dbgs() << "PreciseReleaseUse: Seq: " << Seq << "; " << *Ptr
01871               << "\n");
01872         // Non-movable releases depend on any possible objc pointer use.
01873         S.SetSeq(S_Stop);
01874         ANNOTATE_BOTTOMUP(Inst, Ptr, S_Release, S_Stop);
01875         assert(!S.HasReverseInsertPts());
01876         // As above; handle invoke specially.
01877         if (isa<InvokeInst>(Inst))
01878           S.InsertReverseInsertPt(BB->getFirstInsertionPt());
01879         else
01880           S.InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst)));
01881       }
01882       break;
01883     case S_Stop:
01884       if (CanUse(Inst, Ptr, PA, Class)) {
01885         DEBUG(dbgs() << "PreciseStopUse: Seq: " << Seq << "; " << *Ptr
01886               << "\n");
01887         S.SetSeq(S_Use);
01888         ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S_Use);
01889       }
01890       break;
01891     case S_CanRelease:
01892     case S_Use:
01893     case S_None:
01894       break;
01895     case S_Retain:
01896       llvm_unreachable("bottom-up pointer in retain state!");
01897     }
01898   }
01899 
01900   return NestingDetected;
01901 }
01902 
01903 bool
01904 ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
01905                           DenseMap<const BasicBlock *, BBState> &BBStates,
01906                           MapVector<Value *, RRInfo> &Retains) {
01907 
01908   DEBUG(dbgs() << "\n== ObjCARCOpt::VisitBottomUp ==\n");
01909 
01910   bool NestingDetected = false;
01911   BBState &MyStates = BBStates[BB];
01912 
01913   // Merge the states from each successor to compute the initial state
01914   // for the current block.
01915   BBState::edge_iterator SI(MyStates.succ_begin()),
01916                          SE(MyStates.succ_end());
01917   if (SI != SE) {
01918     const BasicBlock *Succ = *SI;
01919     DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ);
01920     assert(I != BBStates.end());
01921     MyStates.InitFromSucc(I->second);
01922     ++SI;
01923     for (; SI != SE; ++SI) {
01924       Succ = *SI;
01925       I = BBStates.find(Succ);
01926       assert(I != BBStates.end());
01927       MyStates.MergeSucc(I->second);
01928     }
01929   }
01930 
01931   // If ARC Annotations are enabled, output the current state of pointers at the
01932   // bottom of the basic block.
01933   ANNOTATE_BOTTOMUP_BBEND(MyStates, BB);
01934 
01935   // Visit all the instructions, bottom-up.
01936   for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
01937     Instruction *Inst = std::prev(I);
01938 
01939     // Invoke instructions are visited as part of their successors (below).
01940     if (isa<InvokeInst>(Inst))
01941       continue;
01942 
01943     DEBUG(dbgs() << "Visiting " << *Inst << "\n");
01944 
01945     NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates);
01946   }
01947 
01948   // If there's a predecessor with an invoke, visit the invoke as if it were
01949   // part of this block, since we can't insert code after an invoke in its own
01950   // block, and we don't want to split critical edges.
01951   for (BBState::edge_iterator PI(MyStates.pred_begin()),
01952        PE(MyStates.pred_end()); PI != PE; ++PI) {
01953     BasicBlock *Pred = *PI;
01954     if (InvokeInst *II = dyn_cast<InvokeInst>(&Pred->back()))
01955       NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates);
01956   }
01957 
01958   // If ARC Annotations are enabled, output the current state of pointers at the
01959   // top of the basic block.
01960   ANNOTATE_BOTTOMUP_BBSTART(MyStates, BB);
01961 
01962   return NestingDetected;
01963 }
01964 
01965 bool
01966 ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst,
01967                                     DenseMap<Value *, RRInfo> &Releases,
01968                                     BBState &MyStates) {
01969   bool NestingDetected = false;
01970   InstructionClass Class = GetInstructionClass(Inst);
01971   const Value *Arg = nullptr;
01972 
01973   switch (Class) {
01974   case IC_RetainBlock:
01975     // In OptimizeIndividualCalls, we have strength reduced all optimizable
01976     // objc_retainBlocks to objc_retains. Thus at this point any
01977     // objc_retainBlocks that we see are not optimizable.
01978     break;
01979   case IC_Retain:
01980   case IC_RetainRV: {
01981     Arg = GetObjCArg(Inst);
01982 
01983     PtrState &S = MyStates.getPtrTopDownState(Arg);
01984 
01985     // Don't do retain+release tracking for IC_RetainRV, because it's
01986     // better to let it remain as the first instruction after a call.
01987     if (Class != IC_RetainRV) {
01988       // If we see two retains in a row on the same pointer. If so, make
01989       // a note, and we'll cicle back to revisit it after we've
01990       // hopefully eliminated the second retain, which may allow us to
01991       // eliminate the first retain too.
01992       // Theoretically we could implement removal of nested retain+release
01993       // pairs by making PtrState hold a stack of states, but this is
01994       // simple and avoids adding overhead for the non-nested case.
01995       if (S.GetSeq() == S_Retain)
01996         NestingDetected = true;
01997 
01998       ANNOTATE_TOPDOWN(Inst, Arg, S.GetSeq(), S_Retain);
01999       S.ResetSequenceProgress(S_Retain);
02000       S.SetKnownSafe(S.HasKnownPositiveRefCount());
02001       S.InsertCall(Inst);
02002     }
02003 
02004     S.SetKnownPositiveRefCount();
02005 
02006     // A retain can be a potential use; procede to the generic checking
02007     // code below.
02008     break;
02009   }
02010   case IC_Release: {
02011     Arg = GetObjCArg(Inst);
02012 
02013     PtrState &S = MyStates.getPtrTopDownState(Arg);
02014     S.ClearKnownPositiveRefCount();
02015 
02016     Sequence OldSeq = S.GetSeq();
02017 
02018     MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind);
02019 
02020     switch (OldSeq) {
02021     case S_Retain:
02022     case S_CanRelease:
02023       if (OldSeq == S_Retain || ReleaseMetadata != nullptr)
02024         S.ClearReverseInsertPts();
02025       // FALL THROUGH
02026     case S_Use:
02027       S.SetReleaseMetadata(ReleaseMetadata);
02028       S.SetTailCallRelease(cast<CallInst>(Inst)->isTailCall());
02029       Releases[Inst] = S.GetRRInfo();
02030       ANNOTATE_TOPDOWN(Inst, Arg, S.GetSeq(), S_None);
02031       S.ClearSequenceProgress();
02032       break;
02033     case S_None:
02034       break;
02035     case S_Stop:
02036     case S_Release:
02037     case S_MovableRelease:
02038       llvm_unreachable("top-down pointer in release state!");
02039     }
02040     break;
02041   }
02042   case IC_AutoreleasepoolPop:
02043     // Conservatively, clear MyStates for all known pointers.
02044     MyStates.clearTopDownPointers();
02045     return NestingDetected;
02046   case IC_AutoreleasepoolPush:
02047   case IC_None:
02048     // These are irrelevant.
02049     return NestingDetected;
02050   default:
02051     break;
02052   }
02053 
02054   // Consider any other possible effects of this instruction on each
02055   // pointer being tracked.
02056   for (BBState::ptr_iterator MI = MyStates.top_down_ptr_begin(),
02057        ME = MyStates.top_down_ptr_end(); MI != ME; ++MI) {
02058     const Value *Ptr = MI->first;
02059     if (Ptr == Arg)
02060       continue; // Handled above.
02061     PtrState &S = MI->second;
02062     Sequence Seq = S.GetSeq();
02063 
02064     // Check for possible releases.
02065     if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
02066       DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr
02067             << "\n");
02068       S.ClearKnownPositiveRefCount();
02069       switch (Seq) {
02070       case S_Retain:
02071         S.SetSeq(S_CanRelease);
02072         ANNOTATE_TOPDOWN(Inst, Ptr, Seq, S_CanRelease);
02073         assert(!S.HasReverseInsertPts());
02074         S.InsertReverseInsertPt(Inst);
02075 
02076         // One call can't cause a transition from S_Retain to S_CanRelease
02077         // and S_CanRelease to S_Use. If we've made the first transition,
02078         // we're done.
02079         continue;
02080       case S_Use:
02081       case S_CanRelease:
02082       case S_None:
02083         break;
02084       case S_Stop:
02085       case S_Release:
02086       case S_MovableRelease:
02087         llvm_unreachable("top-down pointer in release state!");
02088       }
02089     }
02090 
02091     // Check for possible direct uses.
02092     switch (Seq) {
02093     case S_CanRelease:
02094       if (CanUse(Inst, Ptr, PA, Class)) {
02095         DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr
02096               << "\n");
02097         S.SetSeq(S_Use);
02098         ANNOTATE_TOPDOWN(Inst, Ptr, Seq, S_Use);
02099       }
02100       break;
02101     case S_Retain:
02102     case S_Use:
02103     case S_None:
02104       break;
02105     case S_Stop:
02106     case S_Release:
02107     case S_MovableRelease:
02108       llvm_unreachable("top-down pointer in release state!");
02109     }
02110   }
02111 
02112   return NestingDetected;
02113 }
02114 
02115 bool
02116 ObjCARCOpt::VisitTopDown(BasicBlock *BB,
02117                          DenseMap<const BasicBlock *, BBState> &BBStates,
02118                          DenseMap<Value *, RRInfo> &Releases) {
02119   DEBUG(dbgs() << "\n== ObjCARCOpt::VisitTopDown ==\n");
02120   bool NestingDetected = false;
02121   BBState &MyStates = BBStates[BB];
02122 
02123   // Merge the states from each predecessor to compute the initial state
02124   // for the current block.
02125   BBState::edge_iterator PI(MyStates.pred_begin()),
02126                          PE(MyStates.pred_end());
02127   if (PI != PE) {
02128     const BasicBlock *Pred = *PI;
02129     DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred);
02130     assert(I != BBStates.end());
02131     MyStates.InitFromPred(I->second);
02132     ++PI;
02133     for (; PI != PE; ++PI) {
02134       Pred = *PI;
02135       I = BBStates.find(Pred);
02136       assert(I != BBStates.end());
02137       MyStates.MergePred(I->second);
02138     }
02139   }
02140 
02141   // If ARC Annotations are enabled, output the current state of pointers at the
02142   // top of the basic block.
02143   ANNOTATE_TOPDOWN_BBSTART(MyStates, BB);
02144 
02145   // Visit all the instructions, top-down.
02146   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
02147     Instruction *Inst = I;
02148 
02149     DEBUG(dbgs() << "Visiting " << *Inst << "\n");
02150 
02151     NestingDetected |= VisitInstructionTopDown(Inst, Releases, MyStates);
02152   }
02153 
02154   // If ARC Annotations are enabled, output the current state of pointers at the
02155   // bottom of the basic block.
02156   ANNOTATE_TOPDOWN_BBEND(MyStates, BB);
02157 
02158 #ifdef ARC_ANNOTATIONS
02159   if (!(EnableARCAnnotations && DisableCheckForCFGHazards))
02160 #endif
02161   CheckForCFGHazards(BB, BBStates, MyStates);
02162   return NestingDetected;
02163 }
02164 
02165 static void
02166 ComputePostOrders(Function &F,
02167                   SmallVectorImpl<BasicBlock *> &PostOrder,
02168                   SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder,
02169                   unsigned NoObjCARCExceptionsMDKind,
02170                   DenseMap<const BasicBlock *, BBState> &BBStates) {
02171   /// The visited set, for doing DFS walks.
02172   SmallPtrSet<BasicBlock *, 16> Visited;
02173 
02174   // Do DFS, computing the PostOrder.
02175   SmallPtrSet<BasicBlock *, 16> OnStack;
02176   SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack;
02177 
02178   // Functions always have exactly one entry block, and we don't have
02179   // any other block that we treat like an entry block.
02180   BasicBlock *EntryBB = &F.getEntryBlock();
02181   BBState &MyStates = BBStates[EntryBB];
02182   MyStates.SetAsEntry();
02183   TerminatorInst *EntryTI = cast<TerminatorInst>(&EntryBB->back());
02184   SuccStack.push_back(std::make_pair(EntryBB, succ_iterator(EntryTI)));
02185   Visited.insert(EntryBB);
02186   OnStack.insert(EntryBB);
02187   do {
02188   dfs_next_succ:
02189     BasicBlock *CurrBB = SuccStack.back().first;
02190     TerminatorInst *TI = cast<TerminatorInst>(&CurrBB->back());
02191     succ_iterator SE(TI, false);
02192 
02193     while (SuccStack.back().second != SE) {
02194       BasicBlock *SuccBB = *SuccStack.back().second++;
02195       if (Visited.insert(SuccBB).second) {
02196         TerminatorInst *TI = cast<TerminatorInst>(&SuccBB->back());
02197         SuccStack.push_back(std::make_pair(SuccBB, succ_iterator(TI)));
02198         BBStates[CurrBB].addSucc(SuccBB);
02199         BBState &SuccStates = BBStates[SuccBB];
02200         SuccStates.addPred(CurrBB);
02201         OnStack.insert(SuccBB);
02202         goto dfs_next_succ;
02203       }
02204 
02205       if (!OnStack.count(SuccBB)) {
02206         BBStates[CurrBB].addSucc(SuccBB);
02207         BBStates[SuccBB].addPred(CurrBB);
02208       }
02209     }
02210     OnStack.erase(CurrBB);
02211     PostOrder.push_back(CurrBB);
02212     SuccStack.pop_back();
02213   } while (!SuccStack.empty());
02214 
02215   Visited.clear();
02216 
02217   // Do reverse-CFG DFS, computing the reverse-CFG PostOrder.
02218   // Functions may have many exits, and there also blocks which we treat
02219   // as exits due to ignored edges.
02220   SmallVector<std::pair<BasicBlock *, BBState::edge_iterator>, 16> PredStack;
02221   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
02222     BasicBlock *ExitBB = I;
02223     BBState &MyStates = BBStates[ExitBB];
02224     if (!MyStates.isExit())
02225       continue;
02226 
02227     MyStates.SetAsExit();
02228 
02229     PredStack.push_back(std::make_pair(ExitBB, MyStates.pred_begin()));
02230     Visited.insert(ExitBB);
02231     while (!PredStack.empty()) {
02232     reverse_dfs_next_succ:
02233       BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end();
02234       while (PredStack.back().second != PE) {
02235         BasicBlock *BB = *PredStack.back().second++;
02236         if (Visited.insert(BB).second) {
02237           PredStack.push_back(std::make_pair(BB, BBStates[BB].pred_begin()));
02238           goto reverse_dfs_next_succ;
02239         }
02240       }
02241       ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first);
02242     }
02243   }
02244 }
02245 
02246 // Visit the function both top-down and bottom-up.
02247 bool
02248 ObjCARCOpt::Visit(Function &F,
02249                   DenseMap<const BasicBlock *, BBState> &BBStates,
02250                   MapVector<Value *, RRInfo> &Retains,
02251                   DenseMap<Value *, RRInfo> &Releases) {
02252 
02253   // Use reverse-postorder traversals, because we magically know that loops
02254   // will be well behaved, i.e. they won't repeatedly call retain on a single
02255   // pointer without doing a release. We can't use the ReversePostOrderTraversal
02256   // class here because we want the reverse-CFG postorder to consider each
02257   // function exit point, and we want to ignore selected cycle edges.
02258   SmallVector<BasicBlock *, 16> PostOrder;
02259   SmallVector<BasicBlock *, 16> ReverseCFGPostOrder;
02260   ComputePostOrders(F, PostOrder, ReverseCFGPostOrder,
02261                     NoObjCARCExceptionsMDKind,
02262                     BBStates);
02263 
02264   // Use reverse-postorder on the reverse CFG for bottom-up.
02265   bool BottomUpNestingDetected = false;
02266   for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
02267        ReverseCFGPostOrder.rbegin(), E = ReverseCFGPostOrder.rend();
02268        I != E; ++I)
02269     BottomUpNestingDetected |= VisitBottomUp(*I, BBStates, Retains);
02270 
02271   // Use reverse-postorder for top-down.
02272   bool TopDownNestingDetected = false;
02273   for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
02274        PostOrder.rbegin(), E = PostOrder.rend();
02275        I != E; ++I)
02276     TopDownNestingDetected |= VisitTopDown(*I, BBStates, Releases);
02277 
02278   return TopDownNestingDetected && BottomUpNestingDetected;
02279 }
02280 
02281 /// Move the calls in RetainsToMove and ReleasesToMove.
02282 void ObjCARCOpt::MoveCalls(Value *Arg,
02283                            RRInfo &RetainsToMove,
02284                            RRInfo &ReleasesToMove,
02285                            MapVector<Value *, RRInfo> &Retains,
02286                            DenseMap<Value *, RRInfo> &Releases,
02287                            SmallVectorImpl<Instruction *> &DeadInsts,
02288                            Module *M) {
02289   Type *ArgTy = Arg->getType();
02290   Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext()));
02291 
02292   DEBUG(dbgs() << "== ObjCARCOpt::MoveCalls ==\n");
02293 
02294   // Insert the new retain and release calls.
02295   for (Instruction *InsertPt : ReleasesToMove.ReverseInsertPts) {
02296     Value *MyArg = ArgTy == ParamTy ? Arg :
02297                    new BitCastInst(Arg, ParamTy, "", InsertPt);
02298     Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Retain);
02299     CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt);
02300     Call->setDoesNotThrow();
02301     Call->setTailCall();
02302 
02303     DEBUG(dbgs() << "Inserting new Retain: " << *Call << "\n"
02304                     "At insertion point: " << *InsertPt << "\n");
02305   }
02306   for (Instruction *InsertPt : RetainsToMove.ReverseInsertPts) {
02307     Value *MyArg = ArgTy == ParamTy ? Arg :
02308                    new BitCastInst(Arg, ParamTy, "", InsertPt);
02309     Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Release);
02310     CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt);
02311     // Attach a clang.imprecise_release metadata tag, if appropriate.
02312     if (MDNode *M = ReleasesToMove.ReleaseMetadata)
02313       Call->setMetadata(ImpreciseReleaseMDKind, M);
02314     Call->setDoesNotThrow();
02315     if (ReleasesToMove.IsTailCallRelease)
02316       Call->setTailCall();
02317 
02318     DEBUG(dbgs() << "Inserting new Release: " << *Call << "\n"
02319                     "At insertion point: " << *InsertPt << "\n");
02320   }
02321 
02322   // Delete the original retain and release calls.
02323   for (Instruction *OrigRetain : RetainsToMove.Calls) {
02324     Retains.blot(OrigRetain);
02325     DeadInsts.push_back(OrigRetain);
02326     DEBUG(dbgs() << "Deleting retain: " << *OrigRetain << "\n");
02327   }
02328   for (Instruction *OrigRelease : ReleasesToMove.Calls) {
02329     Releases.erase(OrigRelease);
02330     DeadInsts.push_back(OrigRelease);
02331     DEBUG(dbgs() << "Deleting release: " << *OrigRelease << "\n");
02332   }
02333 
02334 }
02335 
02336 bool
02337 ObjCARCOpt::ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState>
02338                                     &BBStates,
02339                                   MapVector<Value *, RRInfo> &Retains,
02340                                   DenseMap<Value *, RRInfo> &Releases,
02341                                   Module *M,
02342                                   SmallVectorImpl<Instruction *> &NewRetains,
02343                                   SmallVectorImpl<Instruction *> &NewReleases,
02344                                   SmallVectorImpl<Instruction *> &DeadInsts,
02345                                   RRInfo &RetainsToMove,
02346                                   RRInfo &ReleasesToMove,
02347                                   Value *Arg,
02348                                   bool KnownSafe,
02349                                   bool &AnyPairsCompletelyEliminated) {
02350   // If a pair happens in a region where it is known that the reference count
02351   // is already incremented, we can similarly ignore possible decrements unless
02352   // we are dealing with a retainable object with multiple provenance sources.
02353   bool KnownSafeTD = true, KnownSafeBU = true;
02354   bool MultipleOwners = false;
02355   bool CFGHazardAfflicted = false;
02356 
02357   // Connect the dots between the top-down-collected RetainsToMove and
02358   // bottom-up-collected ReleasesToMove to form sets of related calls.
02359   // This is an iterative process so that we connect multiple releases
02360   // to multiple retains if needed.
02361   unsigned OldDelta = 0;
02362   unsigned NewDelta = 0;
02363   unsigned OldCount = 0;
02364   unsigned NewCount = 0;
02365   bool FirstRelease = true;
02366   for (;;) {
02367     for (SmallVectorImpl<Instruction *>::const_iterator
02368            NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) {
02369       Instruction *NewRetain = *NI;
02370       MapVector<Value *, RRInfo>::const_iterator It = Retains.find(NewRetain);
02371       assert(It != Retains.end());
02372       const RRInfo &NewRetainRRI = It->second;
02373       KnownSafeTD &= NewRetainRRI.KnownSafe;
02374       MultipleOwners =
02375         MultipleOwners || MultiOwnersSet.count(GetObjCArg(NewRetain));
02376       for (Instruction *NewRetainRelease : NewRetainRRI.Calls) {
02377         DenseMap<Value *, RRInfo>::const_iterator Jt =
02378           Releases.find(NewRetainRelease);
02379         if (Jt == Releases.end())
02380           return false;
02381         const RRInfo &NewRetainReleaseRRI = Jt->second;
02382 
02383         // If the release does not have a reference to the retain as well,
02384         // something happened which is unaccounted for. Do not do anything.
02385         //
02386         // This can happen if we catch an additive overflow during path count
02387         // merging.
02388         if (!NewRetainReleaseRRI.Calls.count(NewRetain))
02389           return false;
02390 
02391         if (ReleasesToMove.Calls.insert(NewRetainRelease).second) {
02392 
02393           // If we overflow when we compute the path count, don't remove/move
02394           // anything.
02395           const BBState &NRRBBState = BBStates[NewRetainRelease->getParent()];
02396           unsigned PathCount = BBState::OverflowOccurredValue;
02397           if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
02398             return false;
02399           assert(PathCount != BBState::OverflowOccurredValue &&
02400                  "PathCount at this point can not be "
02401                  "OverflowOccurredValue.");
02402           OldDelta -= PathCount;
02403 
02404           // Merge the ReleaseMetadata and IsTailCallRelease values.
02405           if (FirstRelease) {
02406             ReleasesToMove.ReleaseMetadata =
02407               NewRetainReleaseRRI.ReleaseMetadata;
02408             ReleasesToMove.IsTailCallRelease =
02409               NewRetainReleaseRRI.IsTailCallRelease;
02410             FirstRelease = false;
02411           } else {
02412             if (ReleasesToMove.ReleaseMetadata !=
02413                 NewRetainReleaseRRI.ReleaseMetadata)
02414               ReleasesToMove.ReleaseMetadata = nullptr;
02415             if (ReleasesToMove.IsTailCallRelease !=
02416                 NewRetainReleaseRRI.IsTailCallRelease)
02417               ReleasesToMove.IsTailCallRelease = false;
02418           }
02419 
02420           // Collect the optimal insertion points.
02421           if (!KnownSafe)
02422             for (Instruction *RIP : NewRetainReleaseRRI.ReverseInsertPts) {
02423               if (ReleasesToMove.ReverseInsertPts.insert(RIP).second) {
02424                 // If we overflow when we compute the path count, don't
02425                 // remove/move anything.
02426                 const BBState &RIPBBState = BBStates[RIP->getParent()];
02427                 PathCount = BBState::OverflowOccurredValue;
02428                 if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
02429                   return false;
02430                 assert(PathCount != BBState::OverflowOccurredValue &&
02431                        "PathCount at this point can not be "
02432                        "OverflowOccurredValue.");
02433                 NewDelta -= PathCount;
02434               }
02435             }
02436           NewReleases.push_back(NewRetainRelease);
02437         }
02438       }
02439     }
02440     NewRetains.clear();
02441     if (NewReleases.empty()) break;
02442 
02443     // Back the other way.
02444     for (SmallVectorImpl<Instruction *>::const_iterator
02445            NI = NewReleases.begin(), NE = NewReleases.end(); NI != NE; ++NI) {
02446       Instruction *NewRelease = *NI;
02447       DenseMap<Value *, RRInfo>::const_iterator It =
02448         Releases.find(NewRelease);
02449       assert(It != Releases.end());
02450       const RRInfo &NewReleaseRRI = It->second;
02451       KnownSafeBU &= NewReleaseRRI.KnownSafe;
02452       CFGHazardAfflicted |= NewReleaseRRI.CFGHazardAfflicted;
02453       for (Instruction *NewReleaseRetain : NewReleaseRRI.Calls) {
02454         MapVector<Value *, RRInfo>::const_iterator Jt =
02455           Retains.find(NewReleaseRetain);
02456         if (Jt == Retains.end())
02457           return false;
02458         const RRInfo &NewReleaseRetainRRI = Jt->second;
02459 
02460         // If the retain does not have a reference to the release as well,
02461         // something happened which is unaccounted for. Do not do anything.
02462         //
02463         // This can happen if we catch an additive overflow during path count
02464         // merging.
02465         if (!NewReleaseRetainRRI.Calls.count(NewRelease))
02466           return false;
02467 
02468         if (RetainsToMove.Calls.insert(NewReleaseRetain).second) {
02469           // If we overflow when we compute the path count, don't remove/move
02470           // anything.
02471           const BBState &NRRBBState = BBStates[NewReleaseRetain->getParent()];
02472           unsigned PathCount = BBState::OverflowOccurredValue;
02473           if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
02474             return false;
02475           assert(PathCount != BBState::OverflowOccurredValue &&
02476                  "PathCount at this point can not be "
02477                  "OverflowOccurredValue.");
02478           OldDelta += PathCount;
02479           OldCount += PathCount;
02480 
02481           // Collect the optimal insertion points.
02482           if (!KnownSafe)
02483             for (Instruction *RIP : NewReleaseRetainRRI.ReverseInsertPts) {
02484               if (RetainsToMove.ReverseInsertPts.insert(RIP).second) {
02485                 // If we overflow when we compute the path count, don't
02486                 // remove/move anything.
02487                 const BBState &RIPBBState = BBStates[RIP->getParent()];
02488 
02489                 PathCount = BBState::OverflowOccurredValue;
02490                 if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
02491                   return false;
02492                 assert(PathCount != BBState::OverflowOccurredValue &&
02493                        "PathCount at this point can not be "
02494                        "OverflowOccurredValue.");
02495                 NewDelta += PathCount;
02496                 NewCount += PathCount;
02497               }
02498             }
02499           NewRetains.push_back(NewReleaseRetain);
02500         }
02501       }
02502     }
02503     NewReleases.clear();
02504     if (NewRetains.empty()) break;
02505   }
02506 
02507   // If the pointer is known incremented in 1 direction and we do not have
02508   // MultipleOwners, we can safely remove the retain/releases. Otherwise we need
02509   // to be known safe in both directions.
02510   bool UnconditionallySafe = (KnownSafeTD && KnownSafeBU) ||
02511     ((KnownSafeTD || KnownSafeBU) && !MultipleOwners);
02512   if (UnconditionallySafe) {
02513     RetainsToMove.ReverseInsertPts.clear();
02514     ReleasesToMove.ReverseInsertPts.clear();
02515     NewCount = 0;
02516   } else {
02517     // Determine whether the new insertion points we computed preserve the
02518     // balance of retain and release calls through the program.
02519     // TODO: If the fully aggressive solution isn't valid, try to find a
02520     // less aggressive solution which is.
02521     if (NewDelta != 0)
02522       return false;
02523 
02524     // At this point, we are not going to remove any RR pairs, but we still are
02525     // able to move RR pairs. If one of our pointers is afflicted with
02526     // CFGHazards, we cannot perform such code motion so exit early.
02527     const bool WillPerformCodeMotion = RetainsToMove.ReverseInsertPts.size() ||
02528       ReleasesToMove.ReverseInsertPts.size();
02529     if (CFGHazardAfflicted && WillPerformCodeMotion)
02530       return false;
02531   }
02532 
02533   // Determine whether the original call points are balanced in the retain and
02534   // release calls through the program. If not, conservatively don't touch
02535   // them.
02536   // TODO: It's theoretically possible to do code motion in this case, as
02537   // long as the existing imbalances are maintained.
02538   if (OldDelta != 0)
02539     return false;
02540 
02541 #ifdef ARC_ANNOTATIONS
02542   // Do not move calls if ARC annotations are requested.
02543   if (EnableARCAnnotations)
02544     return false;
02545 #endif // ARC_ANNOTATIONS
02546 
02547   Changed = true;
02548   assert(OldCount != 0 && "Unreachable code?");
02549   NumRRs += OldCount - NewCount;
02550   // Set to true if we completely removed any RR pairs.
02551   AnyPairsCompletelyEliminated = NewCount == 0;
02552 
02553   // We can move calls!
02554   return true;
02555 }
02556 
02557 /// Identify pairings between the retains and releases, and delete and/or move
02558 /// them.
02559 bool
02560 ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState>
02561                                    &BBStates,
02562                                  MapVector<Value *, RRInfo> &Retains,
02563                                  DenseMap<Value *, RRInfo> &Releases,
02564                                  Module *M) {
02565   DEBUG(dbgs() << "\n== ObjCARCOpt::PerformCodePlacement ==\n");
02566 
02567   bool AnyPairsCompletelyEliminated = false;
02568   RRInfo RetainsToMove;
02569   RRInfo ReleasesToMove;
02570   SmallVector<Instruction *, 4> NewRetains;
02571   SmallVector<Instruction *, 4> NewReleases;
02572   SmallVector<Instruction *, 8> DeadInsts;
02573 
02574   // Visit each retain.
02575   for (MapVector<Value *, RRInfo>::const_iterator I = Retains.begin(),
02576        E = Retains.end(); I != E; ++I) {
02577     Value *V = I->first;
02578     if (!V) continue; // blotted
02579 
02580     Instruction *Retain = cast<Instruction>(V);
02581 
02582     DEBUG(dbgs() << "Visiting: " << *Retain << "\n");
02583 
02584     Value *Arg = GetObjCArg(Retain);
02585 
02586     // If the object being released is in static or stack storage, we know it's
02587     // not being managed by ObjC reference counting, so we can delete pairs
02588     // regardless of what possible decrements or uses lie between them.
02589     bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg);
02590 
02591     // A constant pointer can't be pointing to an object on the heap. It may
02592     // be reference-counted, but it won't be deleted.
02593     if (const LoadInst *LI = dyn_cast<LoadInst>(Arg))
02594       if (const GlobalVariable *GV =
02595             dyn_cast<GlobalVariable>(
02596               StripPointerCastsAndObjCCalls(LI->getPointerOperand())))
02597         if (GV->isConstant())
02598           KnownSafe = true;
02599 
02600     // Connect the dots between the top-down-collected RetainsToMove and
02601     // bottom-up-collected ReleasesToMove to form sets of related calls.
02602     NewRetains.push_back(Retain);
02603     bool PerformMoveCalls =
02604       ConnectTDBUTraversals(BBStates, Retains, Releases, M, NewRetains,
02605                             NewReleases, DeadInsts, RetainsToMove,
02606                             ReleasesToMove, Arg, KnownSafe,
02607                             AnyPairsCompletelyEliminated);
02608 
02609     if (PerformMoveCalls) {
02610       // Ok, everything checks out and we're all set. Let's move/delete some
02611       // code!
02612       MoveCalls(Arg, RetainsToMove, ReleasesToMove,
02613                 Retains, Releases, DeadInsts, M);
02614     }
02615 
02616     // Clean up state for next retain.
02617     NewReleases.clear();
02618     NewRetains.clear();
02619     RetainsToMove.clear();
02620     ReleasesToMove.clear();
02621   }
02622 
02623   // Now that we're done moving everything, we can delete the newly dead
02624   // instructions, as we no longer need them as insert points.
02625   while (!DeadInsts.empty())
02626     EraseInstruction(DeadInsts.pop_back_val());
02627 
02628   return AnyPairsCompletelyEliminated;
02629 }
02630 
02631 /// Weak pointer optimizations.
02632 void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
02633   DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeWeakCalls ==\n");
02634 
02635   // First, do memdep-style RLE and S2L optimizations. We can't use memdep
02636   // itself because it uses AliasAnalysis and we need to do provenance
02637   // queries instead.
02638   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
02639     Instruction *Inst = &*I++;
02640 
02641     DEBUG(dbgs() << "Visiting: " << *Inst << "\n");
02642 
02643     InstructionClass Class = GetBasicInstructionClass(Inst);
02644     if (Class != IC_LoadWeak && Class != IC_LoadWeakRetained)
02645       continue;
02646 
02647     // Delete objc_loadWeak calls with no users.
02648     if (Class == IC_LoadWeak && Inst->use_empty()) {
02649       Inst->eraseFromParent();
02650       continue;
02651     }
02652 
02653     // TODO: For now, just look for an earlier available version of this value
02654     // within the same block. Theoretically, we could do memdep-style non-local
02655     // analysis too, but that would want caching. A better approach would be to
02656     // use the technique that EarlyCSE uses.
02657     inst_iterator Current = std::prev(I);
02658     BasicBlock *CurrentBB = Current.getBasicBlockIterator();
02659     for (BasicBlock::iterator B = CurrentBB->begin(),
02660                               J = Current.getInstructionIterator();
02661          J != B; --J) {
02662       Instruction *EarlierInst = &*std::prev(J);
02663       InstructionClass EarlierClass = GetInstructionClass(EarlierInst);
02664       switch (EarlierClass) {
02665       case IC_LoadWeak:
02666       case IC_LoadWeakRetained: {
02667         // If this is loading from the same pointer, replace this load's value
02668         // with that one.
02669         CallInst *Call = cast<CallInst>(Inst);
02670         CallInst *EarlierCall = cast<CallInst>(EarlierInst);
02671         Value *Arg = Call->getArgOperand(0);
02672         Value *EarlierArg = EarlierCall->getArgOperand(0);
02673         switch (PA.getAA()->alias(Arg, EarlierArg)) {
02674         case AliasAnalysis::MustAlias:
02675           Changed = true;
02676           // If the load has a builtin retain, insert a plain retain for it.
02677           if (Class == IC_LoadWeakRetained) {
02678             Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Retain);
02679             CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call);
02680             CI->setTailCall();
02681           }
02682           // Zap the fully redundant load.
02683           Call->replaceAllUsesWith(EarlierCall);
02684           Call->eraseFromParent();
02685           goto clobbered;
02686         case AliasAnalysis::MayAlias:
02687         case AliasAnalysis::PartialAlias:
02688           goto clobbered;
02689         case AliasAnalysis::NoAlias:
02690           break;
02691         }
02692         break;
02693       }
02694       case IC_StoreWeak:
02695       case IC_InitWeak: {
02696         // If this is storing to the same pointer and has the same size etc.
02697         // replace this load's value with the stored value.
02698         CallInst *Call = cast<CallInst>(Inst);
02699         CallInst *EarlierCall = cast<CallInst>(EarlierInst);
02700         Value *Arg = Call->getArgOperand(0);
02701         Value *EarlierArg = EarlierCall->getArgOperand(0);
02702         switch (PA.getAA()->alias(Arg, EarlierArg)) {
02703         case AliasAnalysis::MustAlias:
02704           Changed = true;
02705           // If the load has a builtin retain, insert a plain retain for it.
02706           if (Class == IC_LoadWeakRetained) {
02707             Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Retain);
02708             CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call);
02709             CI->setTailCall();
02710           }
02711           // Zap the fully redundant load.
02712           Call->replaceAllUsesWith(EarlierCall->getArgOperand(1));
02713           Call->eraseFromParent();
02714           goto clobbered;
02715         case AliasAnalysis::MayAlias:
02716         case AliasAnalysis::PartialAlias:
02717           goto clobbered;
02718         case AliasAnalysis::NoAlias:
02719           break;
02720         }
02721         break;
02722       }
02723       case IC_MoveWeak:
02724       case IC_CopyWeak:
02725         // TOOD: Grab the copied value.
02726         goto clobbered;
02727       case IC_AutoreleasepoolPush:
02728       case IC_None:
02729       case IC_IntrinsicUser:
02730       case IC_User:
02731         // Weak pointers are only modified through the weak entry points
02732         // (and arbitrary calls, which could call the weak entry points).
02733         break;
02734       default:
02735         // Anything else could modify the weak pointer.
02736         goto clobbered;
02737       }
02738     }
02739   clobbered:;
02740   }
02741 
02742   // Then, for each destroyWeak with an alloca operand, check to see if
02743   // the alloca and all its users can be zapped.
02744   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
02745     Instruction *Inst = &*I++;
02746     InstructionClass Class = GetBasicInstructionClass(Inst);
02747     if (Class != IC_DestroyWeak)
02748       continue;
02749 
02750     CallInst *Call = cast<CallInst>(Inst);
02751     Value *Arg = Call->getArgOperand(0);
02752     if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) {
02753       for (User *U : Alloca->users()) {
02754         const Instruction *UserInst = cast<Instruction>(U);
02755         switch (GetBasicInstructionClass(UserInst)) {
02756         case IC_InitWeak:
02757         case IC_StoreWeak:
02758         case IC_DestroyWeak:
02759           continue;
02760         default:
02761           goto done;
02762         }
02763       }
02764       Changed = true;
02765       for (auto UI = Alloca->user_begin(), UE = Alloca->user_end(); UI != UE;) {
02766         CallInst *UserInst = cast<CallInst>(*UI++);
02767         switch (GetBasicInstructionClass(UserInst)) {
02768         case IC_InitWeak:
02769         case IC_StoreWeak:
02770           // These functions return their second argument.
02771           UserInst->replaceAllUsesWith(UserInst->getArgOperand(1));
02772           break;
02773         case IC_DestroyWeak:
02774           // No return value.
02775           break;
02776         default:
02777           llvm_unreachable("alloca really is used!");
02778         }
02779         UserInst->eraseFromParent();
02780       }
02781       Alloca->eraseFromParent();
02782     done:;
02783     }
02784   }
02785 }
02786 
02787 /// Identify program paths which execute sequences of retains and releases which
02788 /// can be eliminated.
02789 bool ObjCARCOpt::OptimizeSequences(Function &F) {
02790   // Releases, Retains - These are used to store the results of the main flow
02791   // analysis. These use Value* as the key instead of Instruction* so that the
02792   // map stays valid when we get around to rewriting code and calls get
02793   // replaced by arguments.
02794   DenseMap<Value *, RRInfo> Releases;
02795   MapVector<Value *, RRInfo> Retains;
02796 
02797   // This is used during the traversal of the function to track the
02798   // states for each identified object at each block.
02799   DenseMap<const BasicBlock *, BBState> BBStates;
02800 
02801   // Analyze the CFG of the function, and all instructions.
02802   bool NestingDetected = Visit(F, BBStates, Retains, Releases);
02803 
02804   // Transform.
02805   bool AnyPairsCompletelyEliminated = PerformCodePlacement(BBStates, Retains,
02806                                                            Releases,
02807                                                            F.getParent());
02808 
02809   // Cleanup.
02810   MultiOwnersSet.clear();
02811 
02812   return AnyPairsCompletelyEliminated && NestingDetected;
02813 }
02814 
02815 /// Check if there is a dependent call earlier that does not have anything in
02816 /// between the Retain and the call that can affect the reference count of their
02817 /// shared pointer argument. Note that Retain need not be in BB.
02818 static bool
02819 HasSafePathToPredecessorCall(const Value *Arg, Instruction *Retain,
02820                              SmallPtrSetImpl<Instruction *> &DepInsts,
02821                              SmallPtrSetImpl<const BasicBlock *> &Visited,
02822                              ProvenanceAnalysis &PA) {
02823   FindDependencies(CanChangeRetainCount, Arg, Retain->getParent(), Retain,
02824                    DepInsts, Visited, PA);
02825   if (DepInsts.size() != 1)
02826     return false;
02827 
02828   CallInst *Call =
02829     dyn_cast_or_null<CallInst>(*DepInsts.begin());
02830 
02831   // Check that the pointer is the return value of the call.
02832   if (!Call || Arg != Call)
02833     return false;
02834 
02835   // Check that the call is a regular call.
02836   InstructionClass Class = GetBasicInstructionClass(Call);
02837   if (Class != IC_CallOrUser && Class != IC_Call)
02838     return false;
02839 
02840   return true;
02841 }
02842 
02843 /// Find a dependent retain that precedes the given autorelease for which there
02844 /// is nothing in between the two instructions that can affect the ref count of
02845 /// Arg.
02846 static CallInst *
02847 FindPredecessorRetainWithSafePath(const Value *Arg, BasicBlock *BB,
02848                                   Instruction *Autorelease,
02849                                   SmallPtrSetImpl<Instruction *> &DepInsts,
02850                                   SmallPtrSetImpl<const BasicBlock *> &Visited,
02851                                   ProvenanceAnalysis &PA) {
02852   FindDependencies(CanChangeRetainCount, Arg,
02853                    BB, Autorelease, DepInsts, Visited, PA);
02854   if (DepInsts.size() != 1)
02855     return nullptr;
02856 
02857   CallInst *Retain =
02858     dyn_cast_or_null<CallInst>(*DepInsts.begin());
02859 
02860   // Check that we found a retain with the same argument.
02861   if (!Retain ||
02862       !IsRetain(GetBasicInstructionClass(Retain)) ||
02863       GetObjCArg(Retain) != Arg) {
02864     return nullptr;
02865   }
02866 
02867   return Retain;
02868 }
02869 
02870 /// Look for an ``autorelease'' instruction dependent on Arg such that there are
02871 /// no instructions dependent on Arg that need a positive ref count in between
02872 /// the autorelease and the ret.
02873 static CallInst *
02874 FindPredecessorAutoreleaseWithSafePath(const Value *Arg, BasicBlock *BB,
02875                                        ReturnInst *Ret,
02876                                        SmallPtrSetImpl<Instruction *> &DepInsts,
02877                                        SmallPtrSetImpl<const BasicBlock *> &V,
02878                                        ProvenanceAnalysis &PA) {
02879   FindDependencies(NeedsPositiveRetainCount, Arg,
02880                    BB, Ret, DepInsts, V, PA);
02881   if (DepInsts.size() != 1)
02882     return nullptr;
02883 
02884   CallInst *Autorelease =
02885     dyn_cast_or_null<CallInst>(*DepInsts.begin());
02886   if (!Autorelease)
02887     return nullptr;
02888   InstructionClass AutoreleaseClass = GetBasicInstructionClass(Autorelease);
02889   if (!IsAutorelease(AutoreleaseClass))
02890     return nullptr;
02891   if (GetObjCArg(Autorelease) != Arg)
02892     return nullptr;
02893 
02894   return Autorelease;
02895 }
02896 
02897 /// Look for this pattern:
02898 /// \code
02899 ///    %call = call i8* @something(...)
02900 ///    %2 = call i8* @objc_retain(i8* %call)
02901 ///    %3 = call i8* @objc_autorelease(i8* %2)
02902 ///    ret i8* %3
02903 /// \endcode
02904 /// And delete the retain and autorelease.
02905 void ObjCARCOpt::OptimizeReturns(Function &F) {
02906   if (!F.getReturnType()->isPointerTy())
02907     return;
02908 
02909   DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeReturns ==\n");
02910 
02911   SmallPtrSet<Instruction *, 4> DependingInstructions;
02912   SmallPtrSet<const BasicBlock *, 4> Visited;
02913   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
02914     BasicBlock *BB = FI;
02915     ReturnInst *Ret = dyn_cast<ReturnInst>(&BB->back());
02916 
02917     DEBUG(dbgs() << "Visiting: " << *Ret << "\n");
02918 
02919     if (!Ret)
02920       continue;
02921 
02922     const Value *Arg = StripPointerCastsAndObjCCalls(Ret->getOperand(0));
02923 
02924     // Look for an ``autorelease'' instruction that is a predecessor of Ret and
02925     // dependent on Arg such that there are no instructions dependent on Arg
02926     // that need a positive ref count in between the autorelease and Ret.
02927     CallInst *Autorelease =
02928       FindPredecessorAutoreleaseWithSafePath(Arg, BB, Ret,
02929                                              DependingInstructions, Visited,
02930                                              PA);
02931     DependingInstructions.clear();
02932     Visited.clear();
02933 
02934     if (!Autorelease)
02935       continue;
02936 
02937     CallInst *Retain =
02938       FindPredecessorRetainWithSafePath(Arg, BB, Autorelease,
02939                                         DependingInstructions, Visited, PA);
02940     DependingInstructions.clear();
02941     Visited.clear();
02942 
02943     if (!Retain)
02944       continue;
02945 
02946     // Check that there is nothing that can affect the reference count
02947     // between the retain and the call.  Note that Retain need not be in BB.
02948     bool HasSafePathToCall = HasSafePathToPredecessorCall(Arg, Retain,
02949                                                           DependingInstructions,
02950                                                           Visited, PA);
02951     DependingInstructions.clear();
02952     Visited.clear();
02953 
02954     if (!HasSafePathToCall)
02955       continue;
02956 
02957     // If so, we can zap the retain and autorelease.
02958     Changed = true;
02959     ++NumRets;
02960     DEBUG(dbgs() << "Erasing: " << *Retain << "\nErasing: "
02961           << *Autorelease << "\n");
02962     EraseInstruction(Retain);
02963     EraseInstruction(Autorelease);
02964   }
02965 }
02966 
02967 #ifndef NDEBUG
02968 void
02969 ObjCARCOpt::GatherStatistics(Function &F, bool AfterOptimization) {
02970   llvm::Statistic &NumRetains =
02971     AfterOptimization? NumRetainsAfterOpt : NumRetainsBeforeOpt;
02972   llvm::Statistic &NumReleases =
02973     AfterOptimization? NumReleasesAfterOpt : NumReleasesBeforeOpt;
02974 
02975   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
02976     Instruction *Inst = &*I++;
02977     switch (GetBasicInstructionClass(Inst)) {
02978     default:
02979       break;
02980     case IC_Retain:
02981       ++NumRetains;
02982       break;
02983     case IC_Release:
02984       ++NumReleases;
02985       break;
02986     }
02987   }
02988 }
02989 #endif
02990 
02991 bool ObjCARCOpt::doInitialization(Module &M) {
02992   if (!EnableARCOpts)
02993     return false;
02994 
02995   // If nothing in the Module uses ARC, don't do anything.
02996   Run = ModuleHasARC(M);
02997   if (!Run)
02998     return false;
02999 
03000   // Identify the imprecise release metadata kind.
03001   ImpreciseReleaseMDKind =
03002     M.getContext().getMDKindID("clang.imprecise_release");
03003   CopyOnEscapeMDKind =
03004     M.getContext().getMDKindID("clang.arc.copy_on_escape");
03005   NoObjCARCExceptionsMDKind =
03006     M.getContext().getMDKindID("clang.arc.no_objc_arc_exceptions");
03007 #ifdef ARC_ANNOTATIONS
03008   ARCAnnotationBottomUpMDKind =
03009     M.getContext().getMDKindID("llvm.arc.annotation.bottomup");
03010   ARCAnnotationTopDownMDKind =
03011     M.getContext().getMDKindID("llvm.arc.annotation.topdown");
03012   ARCAnnotationProvenanceSourceMDKind =
03013     M.getContext().getMDKindID("llvm.arc.annotation.provenancesource");
03014 #endif // ARC_ANNOTATIONS
03015 
03016   // Intuitively, objc_retain and others are nocapture, however in practice
03017   // they are not, because they return their argument value. And objc_release
03018   // calls finalizers which can have arbitrary side effects.
03019 
03020   // Initialize our runtime entry point cache.
03021   EP.Initialize(&M);
03022 
03023   return false;
03024 }
03025 
03026 bool ObjCARCOpt::runOnFunction(Function &F) {
03027   if (!EnableARCOpts)
03028     return false;
03029 
03030   // If nothing in the Module uses ARC, don't do anything.
03031   if (!Run)
03032     return false;
03033 
03034   Changed = false;
03035 
03036   DEBUG(dbgs() << "<<< ObjCARCOpt: Visiting Function: " << F.getName() << " >>>"
03037         "\n");
03038 
03039   PA.setAA(&getAnalysis<AliasAnalysis>());
03040 
03041 #ifndef NDEBUG
03042   if (AreStatisticsEnabled()) {
03043     GatherStatistics(F, false);
03044   }
03045 #endif
03046 
03047   // This pass performs several distinct transformations. As a compile-time aid
03048   // when compiling code that isn't ObjC, skip these if the relevant ObjC
03049   // library functions aren't declared.
03050 
03051   // Preliminary optimizations. This also computes UsedInThisFunction.
03052   OptimizeIndividualCalls(F);
03053 
03054   // Optimizations for weak pointers.
03055   if (UsedInThisFunction & ((1 << IC_LoadWeak) |
03056                             (1 << IC_LoadWeakRetained) |
03057                             (1 << IC_StoreWeak) |
03058                             (1 << IC_InitWeak) |
03059                             (1 << IC_CopyWeak) |
03060                             (1 << IC_MoveWeak) |
03061                             (1 << IC_DestroyWeak)))
03062     OptimizeWeakCalls(F);
03063 
03064   // Optimizations for retain+release pairs.
03065   if (UsedInThisFunction & ((1 << IC_Retain) |
03066                             (1 << IC_RetainRV) |
03067                             (1 << IC_RetainBlock)))
03068     if (UsedInThisFunction & (1 << IC_Release))
03069       // Run OptimizeSequences until it either stops making changes or
03070       // no retain+release pair nesting is detected.
03071       while (OptimizeSequences(F)) {}
03072 
03073   // Optimizations if objc_autorelease is used.
03074   if (UsedInThisFunction & ((1 << IC_Autorelease) |
03075                             (1 << IC_AutoreleaseRV)))
03076     OptimizeReturns(F);
03077 
03078   // Gather statistics after optimization.
03079 #ifndef NDEBUG
03080   if (AreStatisticsEnabled()) {
03081     GatherStatistics(F, true);
03082   }
03083 #endif
03084 
03085   DEBUG(dbgs() << "\n");
03086 
03087   return Changed;
03088 }
03089 
03090 void ObjCARCOpt::releaseMemory() {
03091   PA.clear();
03092 }
03093 
03094 /// @}
03095 ///