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 GetRCIdentityRoot 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(GetBasicARCInstKind(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() || GetRCIdentityRoot(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                                    ARCInstKind &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 = GetArgRCIdentityRoot(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 (GetBasicARCInstKind(I) == ARCInstKind::AutoreleaseRV &&
01220         GetArgRCIdentityRoot(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 ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F,
01252                                            Instruction *AutoreleaseRV,
01253                                            ARCInstKind &Class) {
01254   // Check for a return of the pointer value.
01255   const Value *Ptr = GetArgRCIdentityRoot(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) || GetBasicARCInstKind(U) == ARCInstKind::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 = ARCInstKind::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     ARCInstKind Class = GetBasicARCInstKind(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 ARCInstKind::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 ARCInstKind::StoreWeak:
01321     case ARCInstKind::LoadWeak:
01322     case ARCInstKind::LoadWeakRetained:
01323     case ARCInstKind::InitWeak:
01324     case ARCInstKind::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 ARCInstKind::CopyWeak:
01342     case ARCInstKind::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 ARCInstKind::RetainRV:
01363       if (OptimizeRetainRVCall(F, Inst))
01364         continue;
01365       break;
01366     case ARCInstKind::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 = ARCInstKind::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 << unsigned(Class);
01426       continue;
01427     }
01428 
01429     const Value *Arg = GetArgRCIdentityRoot(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 << unsigned(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           GetRCIdentityRoot(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 ARCInstKind::Retain:
01484         case ARCInstKind::RetainBlock:
01485           // These can always be moved up.
01486           break;
01487         case ARCInstKind::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 ARCInstKind::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 ARCInstKind::RetainRV:
01501         case ARCInstKind::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               GetRCIdentityRoot(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   ARCInstKind Class = GetARCInstKind(Inst);
01715   const Value *Arg = nullptr;
01716 
01717   DEBUG(dbgs() << "Class: " << Class << "\n");
01718 
01719   switch (Class) {
01720   case ARCInstKind::Release: {
01721     Arg = GetArgRCIdentityRoot(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 ARCInstKind::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 ARCInstKind::Retain:
01754   case ARCInstKind::RetainRV: {
01755     Arg = GetArgRCIdentityRoot(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 ARCInstKind::RetainRV,
01773       // because it's
01774       // better to let it remain as the first instruction after a call.
01775       if (Class != ARCInstKind::RetainRV)
01776         Retains[Inst] = S.GetRRInfo();
01777       S.ClearSequenceProgress();
01778       break;
01779     case S_None:
01780       break;
01781     case S_Retain:
01782       llvm_unreachable("bottom-up pointer in retain state!");
01783     }
01784     ANNOTATE_BOTTOMUP(Inst, Arg, OldSeq, S.GetSeq());
01785     // A retain moving bottom up can be a use.
01786     break;
01787   }
01788   case ARCInstKind::AutoreleasepoolPop:
01789     // Conservatively, clear MyStates for all known pointers.
01790     MyStates.clearBottomUpPointers();
01791     return NestingDetected;
01792   case ARCInstKind::AutoreleasepoolPush:
01793   case ARCInstKind::None:
01794     // These are irrelevant.
01795     return NestingDetected;
01796   case ARCInstKind::User:
01797     // If we have a store into an alloca of a pointer we are tracking, the
01798     // pointer has multiple owners implying that we must be more conservative.
01799     //
01800     // This comes up in the context of a pointer being ``KnownSafe''. In the
01801     // presence of a block being initialized, the frontend will emit the
01802     // objc_retain on the original pointer and the release on the pointer loaded
01803     // from the alloca. The optimizer will through the provenance analysis
01804     // realize that the two are related, but since we only require KnownSafe in
01805     // one direction, will match the inner retain on the original pointer with
01806     // the guard release on the original pointer. This is fixed by ensuring that
01807     // in the presence of allocas we only unconditionally remove pointers if
01808     // both our retain and our release are KnownSafe.
01809     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
01810       if (AreAnyUnderlyingObjectsAnAlloca(SI->getPointerOperand())) {
01811         BBState::ptr_iterator I = MyStates.findPtrBottomUpState(
01812           GetRCIdentityRoot(SI->getValueOperand()));
01813         if (I != MyStates.bottom_up_ptr_end())
01814           MultiOwnersSet.insert(I->first);
01815       }
01816     }
01817     break;
01818   default:
01819     break;
01820   }
01821 
01822   // Consider any other possible effects of this instruction on each
01823   // pointer being tracked.
01824   for (BBState::ptr_iterator MI = MyStates.bottom_up_ptr_begin(),
01825        ME = MyStates.bottom_up_ptr_end(); MI != ME; ++MI) {
01826     const Value *Ptr = MI->first;
01827     if (Ptr == Arg)
01828       continue; // Handled above.
01829     PtrState &S = MI->second;
01830     Sequence Seq = S.GetSeq();
01831 
01832     // Check for possible releases.
01833     if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
01834       DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr
01835             << "\n");
01836       S.ClearKnownPositiveRefCount();
01837       switch (Seq) {
01838       case S_Use:
01839         S.SetSeq(S_CanRelease);
01840         ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S.GetSeq());
01841         continue;
01842       case S_CanRelease:
01843       case S_Release:
01844       case S_MovableRelease:
01845       case S_Stop:
01846       case S_None:
01847         break;
01848       case S_Retain:
01849         llvm_unreachable("bottom-up pointer in retain state!");
01850       }
01851     }
01852 
01853     // Check for possible direct uses.
01854     switch (Seq) {
01855     case S_Release:
01856     case S_MovableRelease:
01857       if (CanUse(Inst, Ptr, PA, Class)) {
01858         DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr
01859               << "\n");
01860         assert(!S.HasReverseInsertPts());
01861         // If this is an invoke instruction, we're scanning it as part of
01862         // one of its successor blocks, since we can't insert code after it
01863         // in its own block, and we don't want to split critical edges.
01864         if (isa<InvokeInst>(Inst))
01865           S.InsertReverseInsertPt(BB->getFirstInsertionPt());
01866         else
01867           S.InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst)));
01868         S.SetSeq(S_Use);
01869         ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S_Use);
01870       } else if (Seq == S_Release && IsUser(Class)) {
01871         DEBUG(dbgs() << "PreciseReleaseUse: Seq: " << Seq << "; " << *Ptr
01872               << "\n");
01873         // Non-movable releases depend on any possible objc pointer use.
01874         S.SetSeq(S_Stop);
01875         ANNOTATE_BOTTOMUP(Inst, Ptr, S_Release, S_Stop);
01876         assert(!S.HasReverseInsertPts());
01877         // As above; handle invoke specially.
01878         if (isa<InvokeInst>(Inst))
01879           S.InsertReverseInsertPt(BB->getFirstInsertionPt());
01880         else
01881           S.InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst)));
01882       }
01883       break;
01884     case S_Stop:
01885       if (CanUse(Inst, Ptr, PA, Class)) {
01886         DEBUG(dbgs() << "PreciseStopUse: Seq: " << Seq << "; " << *Ptr
01887               << "\n");
01888         S.SetSeq(S_Use);
01889         ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S_Use);
01890       }
01891       break;
01892     case S_CanRelease:
01893     case S_Use:
01894     case S_None:
01895       break;
01896     case S_Retain:
01897       llvm_unreachable("bottom-up pointer in retain state!");
01898     }
01899   }
01900 
01901   return NestingDetected;
01902 }
01903 
01904 bool
01905 ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
01906                           DenseMap<const BasicBlock *, BBState> &BBStates,
01907                           MapVector<Value *, RRInfo> &Retains) {
01908 
01909   DEBUG(dbgs() << "\n== ObjCARCOpt::VisitBottomUp ==\n");
01910 
01911   bool NestingDetected = false;
01912   BBState &MyStates = BBStates[BB];
01913 
01914   // Merge the states from each successor to compute the initial state
01915   // for the current block.
01916   BBState::edge_iterator SI(MyStates.succ_begin()),
01917                          SE(MyStates.succ_end());
01918   if (SI != SE) {
01919     const BasicBlock *Succ = *SI;
01920     DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ);
01921     assert(I != BBStates.end());
01922     MyStates.InitFromSucc(I->second);
01923     ++SI;
01924     for (; SI != SE; ++SI) {
01925       Succ = *SI;
01926       I = BBStates.find(Succ);
01927       assert(I != BBStates.end());
01928       MyStates.MergeSucc(I->second);
01929     }
01930   }
01931 
01932   // If ARC Annotations are enabled, output the current state of pointers at the
01933   // bottom of the basic block.
01934   ANNOTATE_BOTTOMUP_BBEND(MyStates, BB);
01935 
01936   // Visit all the instructions, bottom-up.
01937   for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
01938     Instruction *Inst = std::prev(I);
01939 
01940     // Invoke instructions are visited as part of their successors (below).
01941     if (isa<InvokeInst>(Inst))
01942       continue;
01943 
01944     DEBUG(dbgs() << "Visiting " << *Inst << "\n");
01945 
01946     NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates);
01947   }
01948 
01949   // If there's a predecessor with an invoke, visit the invoke as if it were
01950   // part of this block, since we can't insert code after an invoke in its own
01951   // block, and we don't want to split critical edges.
01952   for (BBState::edge_iterator PI(MyStates.pred_begin()),
01953        PE(MyStates.pred_end()); PI != PE; ++PI) {
01954     BasicBlock *Pred = *PI;
01955     if (InvokeInst *II = dyn_cast<InvokeInst>(&Pred->back()))
01956       NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates);
01957   }
01958 
01959   // If ARC Annotations are enabled, output the current state of pointers at the
01960   // top of the basic block.
01961   ANNOTATE_BOTTOMUP_BBSTART(MyStates, BB);
01962 
01963   return NestingDetected;
01964 }
01965 
01966 bool
01967 ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst,
01968                                     DenseMap<Value *, RRInfo> &Releases,
01969                                     BBState &MyStates) {
01970   bool NestingDetected = false;
01971   ARCInstKind Class = GetARCInstKind(Inst);
01972   const Value *Arg = nullptr;
01973 
01974   switch (Class) {
01975   case ARCInstKind::RetainBlock:
01976     // In OptimizeIndividualCalls, we have strength reduced all optimizable
01977     // objc_retainBlocks to objc_retains. Thus at this point any
01978     // objc_retainBlocks that we see are not optimizable.
01979     break;
01980   case ARCInstKind::Retain:
01981   case ARCInstKind::RetainRV: {
01982     Arg = GetArgRCIdentityRoot(Inst);
01983 
01984     PtrState &S = MyStates.getPtrTopDownState(Arg);
01985 
01986     // Don't do retain+release tracking for ARCInstKind::RetainRV, because
01987     // it's
01988     // better to let it remain as the first instruction after a call.
01989     if (Class != ARCInstKind::RetainRV) {
01990       // If we see two retains in a row on the same pointer. If so, make
01991       // a note, and we'll cicle back to revisit it after we've
01992       // hopefully eliminated the second retain, which may allow us to
01993       // eliminate the first retain too.
01994       // Theoretically we could implement removal of nested retain+release
01995       // pairs by making PtrState hold a stack of states, but this is
01996       // simple and avoids adding overhead for the non-nested case.
01997       if (S.GetSeq() == S_Retain)
01998         NestingDetected = true;
01999 
02000       ANNOTATE_TOPDOWN(Inst, Arg, S.GetSeq(), S_Retain);
02001       S.ResetSequenceProgress(S_Retain);
02002       S.SetKnownSafe(S.HasKnownPositiveRefCount());
02003       S.InsertCall(Inst);
02004     }
02005 
02006     S.SetKnownPositiveRefCount();
02007 
02008     // A retain can be a potential use; procede to the generic checking
02009     // code below.
02010     break;
02011   }
02012   case ARCInstKind::Release: {
02013     Arg = GetArgRCIdentityRoot(Inst);
02014 
02015     PtrState &S = MyStates.getPtrTopDownState(Arg);
02016     S.ClearKnownPositiveRefCount();
02017 
02018     Sequence OldSeq = S.GetSeq();
02019 
02020     MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind);
02021 
02022     switch (OldSeq) {
02023     case S_Retain:
02024     case S_CanRelease:
02025       if (OldSeq == S_Retain || ReleaseMetadata != nullptr)
02026         S.ClearReverseInsertPts();
02027       // FALL THROUGH
02028     case S_Use:
02029       S.SetReleaseMetadata(ReleaseMetadata);
02030       S.SetTailCallRelease(cast<CallInst>(Inst)->isTailCall());
02031       Releases[Inst] = S.GetRRInfo();
02032       ANNOTATE_TOPDOWN(Inst, Arg, S.GetSeq(), S_None);
02033       S.ClearSequenceProgress();
02034       break;
02035     case S_None:
02036       break;
02037     case S_Stop:
02038     case S_Release:
02039     case S_MovableRelease:
02040       llvm_unreachable("top-down pointer in release state!");
02041     }
02042     break;
02043   }
02044   case ARCInstKind::AutoreleasepoolPop:
02045     // Conservatively, clear MyStates for all known pointers.
02046     MyStates.clearTopDownPointers();
02047     return NestingDetected;
02048   case ARCInstKind::AutoreleasepoolPush:
02049   case ARCInstKind::None:
02050     // These are irrelevant.
02051     return NestingDetected;
02052   default:
02053     break;
02054   }
02055 
02056   // Consider any other possible effects of this instruction on each
02057   // pointer being tracked.
02058   for (BBState::ptr_iterator MI = MyStates.top_down_ptr_begin(),
02059        ME = MyStates.top_down_ptr_end(); MI != ME; ++MI) {
02060     const Value *Ptr = MI->first;
02061     if (Ptr == Arg)
02062       continue; // Handled above.
02063     PtrState &S = MI->second;
02064     Sequence Seq = S.GetSeq();
02065 
02066     // Check for possible releases.
02067     if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
02068       DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr
02069             << "\n");
02070       S.ClearKnownPositiveRefCount();
02071       switch (Seq) {
02072       case S_Retain:
02073         S.SetSeq(S_CanRelease);
02074         ANNOTATE_TOPDOWN(Inst, Ptr, Seq, S_CanRelease);
02075         assert(!S.HasReverseInsertPts());
02076         S.InsertReverseInsertPt(Inst);
02077 
02078         // One call can't cause a transition from S_Retain to S_CanRelease
02079         // and S_CanRelease to S_Use. If we've made the first transition,
02080         // we're done.
02081         continue;
02082       case S_Use:
02083       case S_CanRelease:
02084       case S_None:
02085         break;
02086       case S_Stop:
02087       case S_Release:
02088       case S_MovableRelease:
02089         llvm_unreachable("top-down pointer in release state!");
02090       }
02091     }
02092 
02093     // Check for possible direct uses.
02094     switch (Seq) {
02095     case S_CanRelease:
02096       if (CanUse(Inst, Ptr, PA, Class)) {
02097         DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr
02098               << "\n");
02099         S.SetSeq(S_Use);
02100         ANNOTATE_TOPDOWN(Inst, Ptr, Seq, S_Use);
02101       }
02102       break;
02103     case S_Retain:
02104     case S_Use:
02105     case S_None:
02106       break;
02107     case S_Stop:
02108     case S_Release:
02109     case S_MovableRelease:
02110       llvm_unreachable("top-down pointer in release state!");
02111     }
02112   }
02113 
02114   return NestingDetected;
02115 }
02116 
02117 bool
02118 ObjCARCOpt::VisitTopDown(BasicBlock *BB,
02119                          DenseMap<const BasicBlock *, BBState> &BBStates,
02120                          DenseMap<Value *, RRInfo> &Releases) {
02121   DEBUG(dbgs() << "\n== ObjCARCOpt::VisitTopDown ==\n");
02122   bool NestingDetected = false;
02123   BBState &MyStates = BBStates[BB];
02124 
02125   // Merge the states from each predecessor to compute the initial state
02126   // for the current block.
02127   BBState::edge_iterator PI(MyStates.pred_begin()),
02128                          PE(MyStates.pred_end());
02129   if (PI != PE) {
02130     const BasicBlock *Pred = *PI;
02131     DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred);
02132     assert(I != BBStates.end());
02133     MyStates.InitFromPred(I->second);
02134     ++PI;
02135     for (; PI != PE; ++PI) {
02136       Pred = *PI;
02137       I = BBStates.find(Pred);
02138       assert(I != BBStates.end());
02139       MyStates.MergePred(I->second);
02140     }
02141   }
02142 
02143   // If ARC Annotations are enabled, output the current state of pointers at the
02144   // top of the basic block.
02145   ANNOTATE_TOPDOWN_BBSTART(MyStates, BB);
02146 
02147   // Visit all the instructions, top-down.
02148   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
02149     Instruction *Inst = I;
02150 
02151     DEBUG(dbgs() << "Visiting " << *Inst << "\n");
02152 
02153     NestingDetected |= VisitInstructionTopDown(Inst, Releases, MyStates);
02154   }
02155 
02156   // If ARC Annotations are enabled, output the current state of pointers at the
02157   // bottom of the basic block.
02158   ANNOTATE_TOPDOWN_BBEND(MyStates, BB);
02159 
02160 #ifdef ARC_ANNOTATIONS
02161   if (!(EnableARCAnnotations && DisableCheckForCFGHazards))
02162 #endif
02163   CheckForCFGHazards(BB, BBStates, MyStates);
02164   return NestingDetected;
02165 }
02166 
02167 static void
02168 ComputePostOrders(Function &F,
02169                   SmallVectorImpl<BasicBlock *> &PostOrder,
02170                   SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder,
02171                   unsigned NoObjCARCExceptionsMDKind,
02172                   DenseMap<const BasicBlock *, BBState> &BBStates) {
02173   /// The visited set, for doing DFS walks.
02174   SmallPtrSet<BasicBlock *, 16> Visited;
02175 
02176   // Do DFS, computing the PostOrder.
02177   SmallPtrSet<BasicBlock *, 16> OnStack;
02178   SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack;
02179 
02180   // Functions always have exactly one entry block, and we don't have
02181   // any other block that we treat like an entry block.
02182   BasicBlock *EntryBB = &F.getEntryBlock();
02183   BBState &MyStates = BBStates[EntryBB];
02184   MyStates.SetAsEntry();
02185   TerminatorInst *EntryTI = cast<TerminatorInst>(&EntryBB->back());
02186   SuccStack.push_back(std::make_pair(EntryBB, succ_iterator(EntryTI)));
02187   Visited.insert(EntryBB);
02188   OnStack.insert(EntryBB);
02189   do {
02190   dfs_next_succ:
02191     BasicBlock *CurrBB = SuccStack.back().first;
02192     TerminatorInst *TI = cast<TerminatorInst>(&CurrBB->back());
02193     succ_iterator SE(TI, false);
02194 
02195     while (SuccStack.back().second != SE) {
02196       BasicBlock *SuccBB = *SuccStack.back().second++;
02197       if (Visited.insert(SuccBB).second) {
02198         TerminatorInst *TI = cast<TerminatorInst>(&SuccBB->back());
02199         SuccStack.push_back(std::make_pair(SuccBB, succ_iterator(TI)));
02200         BBStates[CurrBB].addSucc(SuccBB);
02201         BBState &SuccStates = BBStates[SuccBB];
02202         SuccStates.addPred(CurrBB);
02203         OnStack.insert(SuccBB);
02204         goto dfs_next_succ;
02205       }
02206 
02207       if (!OnStack.count(SuccBB)) {
02208         BBStates[CurrBB].addSucc(SuccBB);
02209         BBStates[SuccBB].addPred(CurrBB);
02210       }
02211     }
02212     OnStack.erase(CurrBB);
02213     PostOrder.push_back(CurrBB);
02214     SuccStack.pop_back();
02215   } while (!SuccStack.empty());
02216 
02217   Visited.clear();
02218 
02219   // Do reverse-CFG DFS, computing the reverse-CFG PostOrder.
02220   // Functions may have many exits, and there also blocks which we treat
02221   // as exits due to ignored edges.
02222   SmallVector<std::pair<BasicBlock *, BBState::edge_iterator>, 16> PredStack;
02223   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
02224     BasicBlock *ExitBB = I;
02225     BBState &MyStates = BBStates[ExitBB];
02226     if (!MyStates.isExit())
02227       continue;
02228 
02229     MyStates.SetAsExit();
02230 
02231     PredStack.push_back(std::make_pair(ExitBB, MyStates.pred_begin()));
02232     Visited.insert(ExitBB);
02233     while (!PredStack.empty()) {
02234     reverse_dfs_next_succ:
02235       BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end();
02236       while (PredStack.back().second != PE) {
02237         BasicBlock *BB = *PredStack.back().second++;
02238         if (Visited.insert(BB).second) {
02239           PredStack.push_back(std::make_pair(BB, BBStates[BB].pred_begin()));
02240           goto reverse_dfs_next_succ;
02241         }
02242       }
02243       ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first);
02244     }
02245   }
02246 }
02247 
02248 // Visit the function both top-down and bottom-up.
02249 bool
02250 ObjCARCOpt::Visit(Function &F,
02251                   DenseMap<const BasicBlock *, BBState> &BBStates,
02252                   MapVector<Value *, RRInfo> &Retains,
02253                   DenseMap<Value *, RRInfo> &Releases) {
02254 
02255   // Use reverse-postorder traversals, because we magically know that loops
02256   // will be well behaved, i.e. they won't repeatedly call retain on a single
02257   // pointer without doing a release. We can't use the ReversePostOrderTraversal
02258   // class here because we want the reverse-CFG postorder to consider each
02259   // function exit point, and we want to ignore selected cycle edges.
02260   SmallVector<BasicBlock *, 16> PostOrder;
02261   SmallVector<BasicBlock *, 16> ReverseCFGPostOrder;
02262   ComputePostOrders(F, PostOrder, ReverseCFGPostOrder,
02263                     NoObjCARCExceptionsMDKind,
02264                     BBStates);
02265 
02266   // Use reverse-postorder on the reverse CFG for bottom-up.
02267   bool BottomUpNestingDetected = false;
02268   for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
02269        ReverseCFGPostOrder.rbegin(), E = ReverseCFGPostOrder.rend();
02270        I != E; ++I)
02271     BottomUpNestingDetected |= VisitBottomUp(*I, BBStates, Retains);
02272 
02273   // Use reverse-postorder for top-down.
02274   bool TopDownNestingDetected = false;
02275   for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
02276        PostOrder.rbegin(), E = PostOrder.rend();
02277        I != E; ++I)
02278     TopDownNestingDetected |= VisitTopDown(*I, BBStates, Releases);
02279 
02280   return TopDownNestingDetected && BottomUpNestingDetected;
02281 }
02282 
02283 /// Move the calls in RetainsToMove and ReleasesToMove.
02284 void ObjCARCOpt::MoveCalls(Value *Arg,
02285                            RRInfo &RetainsToMove,
02286                            RRInfo &ReleasesToMove,
02287                            MapVector<Value *, RRInfo> &Retains,
02288                            DenseMap<Value *, RRInfo> &Releases,
02289                            SmallVectorImpl<Instruction *> &DeadInsts,
02290                            Module *M) {
02291   Type *ArgTy = Arg->getType();
02292   Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext()));
02293 
02294   DEBUG(dbgs() << "== ObjCARCOpt::MoveCalls ==\n");
02295 
02296   // Insert the new retain and release calls.
02297   for (Instruction *InsertPt : ReleasesToMove.ReverseInsertPts) {
02298     Value *MyArg = ArgTy == ParamTy ? Arg :
02299                    new BitCastInst(Arg, ParamTy, "", InsertPt);
02300     Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Retain);
02301     CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt);
02302     Call->setDoesNotThrow();
02303     Call->setTailCall();
02304 
02305     DEBUG(dbgs() << "Inserting new Retain: " << *Call << "\n"
02306                     "At insertion point: " << *InsertPt << "\n");
02307   }
02308   for (Instruction *InsertPt : RetainsToMove.ReverseInsertPts) {
02309     Value *MyArg = ArgTy == ParamTy ? Arg :
02310                    new BitCastInst(Arg, ParamTy, "", InsertPt);
02311     Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Release);
02312     CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt);
02313     // Attach a clang.imprecise_release metadata tag, if appropriate.
02314     if (MDNode *M = ReleasesToMove.ReleaseMetadata)
02315       Call->setMetadata(ImpreciseReleaseMDKind, M);
02316     Call->setDoesNotThrow();
02317     if (ReleasesToMove.IsTailCallRelease)
02318       Call->setTailCall();
02319 
02320     DEBUG(dbgs() << "Inserting new Release: " << *Call << "\n"
02321                     "At insertion point: " << *InsertPt << "\n");
02322   }
02323 
02324   // Delete the original retain and release calls.
02325   for (Instruction *OrigRetain : RetainsToMove.Calls) {
02326     Retains.blot(OrigRetain);
02327     DeadInsts.push_back(OrigRetain);
02328     DEBUG(dbgs() << "Deleting retain: " << *OrigRetain << "\n");
02329   }
02330   for (Instruction *OrigRelease : ReleasesToMove.Calls) {
02331     Releases.erase(OrigRelease);
02332     DeadInsts.push_back(OrigRelease);
02333     DEBUG(dbgs() << "Deleting release: " << *OrigRelease << "\n");
02334   }
02335 
02336 }
02337 
02338 bool
02339 ObjCARCOpt::ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState>
02340                                     &BBStates,
02341                                   MapVector<Value *, RRInfo> &Retains,
02342                                   DenseMap<Value *, RRInfo> &Releases,
02343                                   Module *M,
02344                                   SmallVectorImpl<Instruction *> &NewRetains,
02345                                   SmallVectorImpl<Instruction *> &NewReleases,
02346                                   SmallVectorImpl<Instruction *> &DeadInsts,
02347                                   RRInfo &RetainsToMove,
02348                                   RRInfo &ReleasesToMove,
02349                                   Value *Arg,
02350                                   bool KnownSafe,
02351                                   bool &AnyPairsCompletelyEliminated) {
02352   // If a pair happens in a region where it is known that the reference count
02353   // is already incremented, we can similarly ignore possible decrements unless
02354   // we are dealing with a retainable object with multiple provenance sources.
02355   bool KnownSafeTD = true, KnownSafeBU = true;
02356   bool MultipleOwners = false;
02357   bool CFGHazardAfflicted = false;
02358 
02359   // Connect the dots between the top-down-collected RetainsToMove and
02360   // bottom-up-collected ReleasesToMove to form sets of related calls.
02361   // This is an iterative process so that we connect multiple releases
02362   // to multiple retains if needed.
02363   unsigned OldDelta = 0;
02364   unsigned NewDelta = 0;
02365   unsigned OldCount = 0;
02366   unsigned NewCount = 0;
02367   bool FirstRelease = true;
02368   for (;;) {
02369     for (SmallVectorImpl<Instruction *>::const_iterator
02370            NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) {
02371       Instruction *NewRetain = *NI;
02372       MapVector<Value *, RRInfo>::const_iterator It = Retains.find(NewRetain);
02373       assert(It != Retains.end());
02374       const RRInfo &NewRetainRRI = It->second;
02375       KnownSafeTD &= NewRetainRRI.KnownSafe;
02376       MultipleOwners =
02377         MultipleOwners || MultiOwnersSet.count(GetArgRCIdentityRoot(NewRetain));
02378       for (Instruction *NewRetainRelease : NewRetainRRI.Calls) {
02379         DenseMap<Value *, RRInfo>::const_iterator Jt =
02380           Releases.find(NewRetainRelease);
02381         if (Jt == Releases.end())
02382           return false;
02383         const RRInfo &NewRetainReleaseRRI = Jt->second;
02384 
02385         // If the release does not have a reference to the retain as well,
02386         // something happened which is unaccounted for. Do not do anything.
02387         //
02388         // This can happen if we catch an additive overflow during path count
02389         // merging.
02390         if (!NewRetainReleaseRRI.Calls.count(NewRetain))
02391           return false;
02392 
02393         if (ReleasesToMove.Calls.insert(NewRetainRelease).second) {
02394 
02395           // If we overflow when we compute the path count, don't remove/move
02396           // anything.
02397           const BBState &NRRBBState = BBStates[NewRetainRelease->getParent()];
02398           unsigned PathCount = BBState::OverflowOccurredValue;
02399           if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
02400             return false;
02401           assert(PathCount != BBState::OverflowOccurredValue &&
02402                  "PathCount at this point can not be "
02403                  "OverflowOccurredValue.");
02404           OldDelta -= PathCount;
02405 
02406           // Merge the ReleaseMetadata and IsTailCallRelease values.
02407           if (FirstRelease) {
02408             ReleasesToMove.ReleaseMetadata =
02409               NewRetainReleaseRRI.ReleaseMetadata;
02410             ReleasesToMove.IsTailCallRelease =
02411               NewRetainReleaseRRI.IsTailCallRelease;
02412             FirstRelease = false;
02413           } else {
02414             if (ReleasesToMove.ReleaseMetadata !=
02415                 NewRetainReleaseRRI.ReleaseMetadata)
02416               ReleasesToMove.ReleaseMetadata = nullptr;
02417             if (ReleasesToMove.IsTailCallRelease !=
02418                 NewRetainReleaseRRI.IsTailCallRelease)
02419               ReleasesToMove.IsTailCallRelease = false;
02420           }
02421 
02422           // Collect the optimal insertion points.
02423           if (!KnownSafe)
02424             for (Instruction *RIP : NewRetainReleaseRRI.ReverseInsertPts) {
02425               if (ReleasesToMove.ReverseInsertPts.insert(RIP).second) {
02426                 // If we overflow when we compute the path count, don't
02427                 // remove/move anything.
02428                 const BBState &RIPBBState = BBStates[RIP->getParent()];
02429                 PathCount = BBState::OverflowOccurredValue;
02430                 if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
02431                   return false;
02432                 assert(PathCount != BBState::OverflowOccurredValue &&
02433                        "PathCount at this point can not be "
02434                        "OverflowOccurredValue.");
02435                 NewDelta -= PathCount;
02436               }
02437             }
02438           NewReleases.push_back(NewRetainRelease);
02439         }
02440       }
02441     }
02442     NewRetains.clear();
02443     if (NewReleases.empty()) break;
02444 
02445     // Back the other way.
02446     for (SmallVectorImpl<Instruction *>::const_iterator
02447            NI = NewReleases.begin(), NE = NewReleases.end(); NI != NE; ++NI) {
02448       Instruction *NewRelease = *NI;
02449       DenseMap<Value *, RRInfo>::const_iterator It =
02450         Releases.find(NewRelease);
02451       assert(It != Releases.end());
02452       const RRInfo &NewReleaseRRI = It->second;
02453       KnownSafeBU &= NewReleaseRRI.KnownSafe;
02454       CFGHazardAfflicted |= NewReleaseRRI.CFGHazardAfflicted;
02455       for (Instruction *NewReleaseRetain : NewReleaseRRI.Calls) {
02456         MapVector<Value *, RRInfo>::const_iterator Jt =
02457           Retains.find(NewReleaseRetain);
02458         if (Jt == Retains.end())
02459           return false;
02460         const RRInfo &NewReleaseRetainRRI = Jt->second;
02461 
02462         // If the retain does not have a reference to the release as well,
02463         // something happened which is unaccounted for. Do not do anything.
02464         //
02465         // This can happen if we catch an additive overflow during path count
02466         // merging.
02467         if (!NewReleaseRetainRRI.Calls.count(NewRelease))
02468           return false;
02469 
02470         if (RetainsToMove.Calls.insert(NewReleaseRetain).second) {
02471           // If we overflow when we compute the path count, don't remove/move
02472           // anything.
02473           const BBState &NRRBBState = BBStates[NewReleaseRetain->getParent()];
02474           unsigned PathCount = BBState::OverflowOccurredValue;
02475           if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
02476             return false;
02477           assert(PathCount != BBState::OverflowOccurredValue &&
02478                  "PathCount at this point can not be "
02479                  "OverflowOccurredValue.");
02480           OldDelta += PathCount;
02481           OldCount += PathCount;
02482 
02483           // Collect the optimal insertion points.
02484           if (!KnownSafe)
02485             for (Instruction *RIP : NewReleaseRetainRRI.ReverseInsertPts) {
02486               if (RetainsToMove.ReverseInsertPts.insert(RIP).second) {
02487                 // If we overflow when we compute the path count, don't
02488                 // remove/move anything.
02489                 const BBState &RIPBBState = BBStates[RIP->getParent()];
02490 
02491                 PathCount = BBState::OverflowOccurredValue;
02492                 if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
02493                   return false;
02494                 assert(PathCount != BBState::OverflowOccurredValue &&
02495                        "PathCount at this point can not be "
02496                        "OverflowOccurredValue.");
02497                 NewDelta += PathCount;
02498                 NewCount += PathCount;
02499               }
02500             }
02501           NewRetains.push_back(NewReleaseRetain);
02502         }
02503       }
02504     }
02505     NewReleases.clear();
02506     if (NewRetains.empty()) break;
02507   }
02508 
02509   // If the pointer is known incremented in 1 direction and we do not have
02510   // MultipleOwners, we can safely remove the retain/releases. Otherwise we need
02511   // to be known safe in both directions.
02512   bool UnconditionallySafe = (KnownSafeTD && KnownSafeBU) ||
02513     ((KnownSafeTD || KnownSafeBU) && !MultipleOwners);
02514   if (UnconditionallySafe) {
02515     RetainsToMove.ReverseInsertPts.clear();
02516     ReleasesToMove.ReverseInsertPts.clear();
02517     NewCount = 0;
02518   } else {
02519     // Determine whether the new insertion points we computed preserve the
02520     // balance of retain and release calls through the program.
02521     // TODO: If the fully aggressive solution isn't valid, try to find a
02522     // less aggressive solution which is.
02523     if (NewDelta != 0)
02524       return false;
02525 
02526     // At this point, we are not going to remove any RR pairs, but we still are
02527     // able to move RR pairs. If one of our pointers is afflicted with
02528     // CFGHazards, we cannot perform such code motion so exit early.
02529     const bool WillPerformCodeMotion = RetainsToMove.ReverseInsertPts.size() ||
02530       ReleasesToMove.ReverseInsertPts.size();
02531     if (CFGHazardAfflicted && WillPerformCodeMotion)
02532       return false;
02533   }
02534 
02535   // Determine whether the original call points are balanced in the retain and
02536   // release calls through the program. If not, conservatively don't touch
02537   // them.
02538   // TODO: It's theoretically possible to do code motion in this case, as
02539   // long as the existing imbalances are maintained.
02540   if (OldDelta != 0)
02541     return false;
02542 
02543 #ifdef ARC_ANNOTATIONS
02544   // Do not move calls if ARC annotations are requested.
02545   if (EnableARCAnnotations)
02546     return false;
02547 #endif // ARC_ANNOTATIONS
02548 
02549   Changed = true;
02550   assert(OldCount != 0 && "Unreachable code?");
02551   NumRRs += OldCount - NewCount;
02552   // Set to true if we completely removed any RR pairs.
02553   AnyPairsCompletelyEliminated = NewCount == 0;
02554 
02555   // We can move calls!
02556   return true;
02557 }
02558 
02559 /// Identify pairings between the retains and releases, and delete and/or move
02560 /// them.
02561 bool
02562 ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState>
02563                                    &BBStates,
02564                                  MapVector<Value *, RRInfo> &Retains,
02565                                  DenseMap<Value *, RRInfo> &Releases,
02566                                  Module *M) {
02567   DEBUG(dbgs() << "\n== ObjCARCOpt::PerformCodePlacement ==\n");
02568 
02569   bool AnyPairsCompletelyEliminated = false;
02570   RRInfo RetainsToMove;
02571   RRInfo ReleasesToMove;
02572   SmallVector<Instruction *, 4> NewRetains;
02573   SmallVector<Instruction *, 4> NewReleases;
02574   SmallVector<Instruction *, 8> DeadInsts;
02575 
02576   // Visit each retain.
02577   for (MapVector<Value *, RRInfo>::const_iterator I = Retains.begin(),
02578        E = Retains.end(); I != E; ++I) {
02579     Value *V = I->first;
02580     if (!V) continue; // blotted
02581 
02582     Instruction *Retain = cast<Instruction>(V);
02583 
02584     DEBUG(dbgs() << "Visiting: " << *Retain << "\n");
02585 
02586     Value *Arg = GetArgRCIdentityRoot(Retain);
02587 
02588     // If the object being released is in static or stack storage, we know it's
02589     // not being managed by ObjC reference counting, so we can delete pairs
02590     // regardless of what possible decrements or uses lie between them.
02591     bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg);
02592 
02593     // A constant pointer can't be pointing to an object on the heap. It may
02594     // be reference-counted, but it won't be deleted.
02595     if (const LoadInst *LI = dyn_cast<LoadInst>(Arg))
02596       if (const GlobalVariable *GV =
02597             dyn_cast<GlobalVariable>(
02598               GetRCIdentityRoot(LI->getPointerOperand())))
02599         if (GV->isConstant())
02600           KnownSafe = true;
02601 
02602     // Connect the dots between the top-down-collected RetainsToMove and
02603     // bottom-up-collected ReleasesToMove to form sets of related calls.
02604     NewRetains.push_back(Retain);
02605     bool PerformMoveCalls =
02606       ConnectTDBUTraversals(BBStates, Retains, Releases, M, NewRetains,
02607                             NewReleases, DeadInsts, RetainsToMove,
02608                             ReleasesToMove, Arg, KnownSafe,
02609                             AnyPairsCompletelyEliminated);
02610 
02611     if (PerformMoveCalls) {
02612       // Ok, everything checks out and we're all set. Let's move/delete some
02613       // code!
02614       MoveCalls(Arg, RetainsToMove, ReleasesToMove,
02615                 Retains, Releases, DeadInsts, M);
02616     }
02617 
02618     // Clean up state for next retain.
02619     NewReleases.clear();
02620     NewRetains.clear();
02621     RetainsToMove.clear();
02622     ReleasesToMove.clear();
02623   }
02624 
02625   // Now that we're done moving everything, we can delete the newly dead
02626   // instructions, as we no longer need them as insert points.
02627   while (!DeadInsts.empty())
02628     EraseInstruction(DeadInsts.pop_back_val());
02629 
02630   return AnyPairsCompletelyEliminated;
02631 }
02632 
02633 /// Weak pointer optimizations.
02634 void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
02635   DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeWeakCalls ==\n");
02636 
02637   // First, do memdep-style RLE and S2L optimizations. We can't use memdep
02638   // itself because it uses AliasAnalysis and we need to do provenance
02639   // queries instead.
02640   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
02641     Instruction *Inst = &*I++;
02642 
02643     DEBUG(dbgs() << "Visiting: " << *Inst << "\n");
02644 
02645     ARCInstKind Class = GetBasicARCInstKind(Inst);
02646     if (Class != ARCInstKind::LoadWeak &&
02647         Class != ARCInstKind::LoadWeakRetained)
02648       continue;
02649 
02650     // Delete objc_loadWeak calls with no users.
02651     if (Class == ARCInstKind::LoadWeak && Inst->use_empty()) {
02652       Inst->eraseFromParent();
02653       continue;
02654     }
02655 
02656     // TODO: For now, just look for an earlier available version of this value
02657     // within the same block. Theoretically, we could do memdep-style non-local
02658     // analysis too, but that would want caching. A better approach would be to
02659     // use the technique that EarlyCSE uses.
02660     inst_iterator Current = std::prev(I);
02661     BasicBlock *CurrentBB = Current.getBasicBlockIterator();
02662     for (BasicBlock::iterator B = CurrentBB->begin(),
02663                               J = Current.getInstructionIterator();
02664          J != B; --J) {
02665       Instruction *EarlierInst = &*std::prev(J);
02666       ARCInstKind EarlierClass = GetARCInstKind(EarlierInst);
02667       switch (EarlierClass) {
02668       case ARCInstKind::LoadWeak:
02669       case ARCInstKind::LoadWeakRetained: {
02670         // If this is loading from the same pointer, replace this load's value
02671         // with that one.
02672         CallInst *Call = cast<CallInst>(Inst);
02673         CallInst *EarlierCall = cast<CallInst>(EarlierInst);
02674         Value *Arg = Call->getArgOperand(0);
02675         Value *EarlierArg = EarlierCall->getArgOperand(0);
02676         switch (PA.getAA()->alias(Arg, EarlierArg)) {
02677         case AliasAnalysis::MustAlias:
02678           Changed = true;
02679           // If the load has a builtin retain, insert a plain retain for it.
02680           if (Class == ARCInstKind::LoadWeakRetained) {
02681             Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Retain);
02682             CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call);
02683             CI->setTailCall();
02684           }
02685           // Zap the fully redundant load.
02686           Call->replaceAllUsesWith(EarlierCall);
02687           Call->eraseFromParent();
02688           goto clobbered;
02689         case AliasAnalysis::MayAlias:
02690         case AliasAnalysis::PartialAlias:
02691           goto clobbered;
02692         case AliasAnalysis::NoAlias:
02693           break;
02694         }
02695         break;
02696       }
02697       case ARCInstKind::StoreWeak:
02698       case ARCInstKind::InitWeak: {
02699         // If this is storing to the same pointer and has the same size etc.
02700         // replace this load's value with the stored value.
02701         CallInst *Call = cast<CallInst>(Inst);
02702         CallInst *EarlierCall = cast<CallInst>(EarlierInst);
02703         Value *Arg = Call->getArgOperand(0);
02704         Value *EarlierArg = EarlierCall->getArgOperand(0);
02705         switch (PA.getAA()->alias(Arg, EarlierArg)) {
02706         case AliasAnalysis::MustAlias:
02707           Changed = true;
02708           // If the load has a builtin retain, insert a plain retain for it.
02709           if (Class == ARCInstKind::LoadWeakRetained) {
02710             Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Retain);
02711             CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call);
02712             CI->setTailCall();
02713           }
02714           // Zap the fully redundant load.
02715           Call->replaceAllUsesWith(EarlierCall->getArgOperand(1));
02716           Call->eraseFromParent();
02717           goto clobbered;
02718         case AliasAnalysis::MayAlias:
02719         case AliasAnalysis::PartialAlias:
02720           goto clobbered;
02721         case AliasAnalysis::NoAlias:
02722           break;
02723         }
02724         break;
02725       }
02726       case ARCInstKind::MoveWeak:
02727       case ARCInstKind::CopyWeak:
02728         // TOOD: Grab the copied value.
02729         goto clobbered;
02730       case ARCInstKind::AutoreleasepoolPush:
02731       case ARCInstKind::None:
02732       case ARCInstKind::IntrinsicUser:
02733       case ARCInstKind::User:
02734         // Weak pointers are only modified through the weak entry points
02735         // (and arbitrary calls, which could call the weak entry points).
02736         break;
02737       default:
02738         // Anything else could modify the weak pointer.
02739         goto clobbered;
02740       }
02741     }
02742   clobbered:;
02743   }
02744 
02745   // Then, for each destroyWeak with an alloca operand, check to see if
02746   // the alloca and all its users can be zapped.
02747   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
02748     Instruction *Inst = &*I++;
02749     ARCInstKind Class = GetBasicARCInstKind(Inst);
02750     if (Class != ARCInstKind::DestroyWeak)
02751       continue;
02752 
02753     CallInst *Call = cast<CallInst>(Inst);
02754     Value *Arg = Call->getArgOperand(0);
02755     if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) {
02756       for (User *U : Alloca->users()) {
02757         const Instruction *UserInst = cast<Instruction>(U);
02758         switch (GetBasicARCInstKind(UserInst)) {
02759         case ARCInstKind::InitWeak:
02760         case ARCInstKind::StoreWeak:
02761         case ARCInstKind::DestroyWeak:
02762           continue;
02763         default:
02764           goto done;
02765         }
02766       }
02767       Changed = true;
02768       for (auto UI = Alloca->user_begin(), UE = Alloca->user_end(); UI != UE;) {
02769         CallInst *UserInst = cast<CallInst>(*UI++);
02770         switch (GetBasicARCInstKind(UserInst)) {
02771         case ARCInstKind::InitWeak:
02772         case ARCInstKind::StoreWeak:
02773           // These functions return their second argument.
02774           UserInst->replaceAllUsesWith(UserInst->getArgOperand(1));
02775           break;
02776         case ARCInstKind::DestroyWeak:
02777           // No return value.
02778           break;
02779         default:
02780           llvm_unreachable("alloca really is used!");
02781         }
02782         UserInst->eraseFromParent();
02783       }
02784       Alloca->eraseFromParent();
02785     done:;
02786     }
02787   }
02788 }
02789 
02790 /// Identify program paths which execute sequences of retains and releases which
02791 /// can be eliminated.
02792 bool ObjCARCOpt::OptimizeSequences(Function &F) {
02793   // Releases, Retains - These are used to store the results of the main flow
02794   // analysis. These use Value* as the key instead of Instruction* so that the
02795   // map stays valid when we get around to rewriting code and calls get
02796   // replaced by arguments.
02797   DenseMap<Value *, RRInfo> Releases;
02798   MapVector<Value *, RRInfo> Retains;
02799 
02800   // This is used during the traversal of the function to track the
02801   // states for each identified object at each block.
02802   DenseMap<const BasicBlock *, BBState> BBStates;
02803 
02804   // Analyze the CFG of the function, and all instructions.
02805   bool NestingDetected = Visit(F, BBStates, Retains, Releases);
02806 
02807   // Transform.
02808   bool AnyPairsCompletelyEliminated = PerformCodePlacement(BBStates, Retains,
02809                                                            Releases,
02810                                                            F.getParent());
02811 
02812   // Cleanup.
02813   MultiOwnersSet.clear();
02814 
02815   return AnyPairsCompletelyEliminated && NestingDetected;
02816 }
02817 
02818 /// Check if there is a dependent call earlier that does not have anything in
02819 /// between the Retain and the call that can affect the reference count of their
02820 /// shared pointer argument. Note that Retain need not be in BB.
02821 static bool
02822 HasSafePathToPredecessorCall(const Value *Arg, Instruction *Retain,
02823                              SmallPtrSetImpl<Instruction *> &DepInsts,
02824                              SmallPtrSetImpl<const BasicBlock *> &Visited,
02825                              ProvenanceAnalysis &PA) {
02826   FindDependencies(CanChangeRetainCount, Arg, Retain->getParent(), Retain,
02827                    DepInsts, Visited, PA);
02828   if (DepInsts.size() != 1)
02829     return false;
02830 
02831   CallInst *Call =
02832     dyn_cast_or_null<CallInst>(*DepInsts.begin());
02833 
02834   // Check that the pointer is the return value of the call.
02835   if (!Call || Arg != Call)
02836     return false;
02837 
02838   // Check that the call is a regular call.
02839   ARCInstKind Class = GetBasicARCInstKind(Call);
02840   if (Class != ARCInstKind::CallOrUser && Class != ARCInstKind::Call)
02841     return false;
02842 
02843   return true;
02844 }
02845 
02846 /// Find a dependent retain that precedes the given autorelease for which there
02847 /// is nothing in between the two instructions that can affect the ref count of
02848 /// Arg.
02849 static CallInst *
02850 FindPredecessorRetainWithSafePath(const Value *Arg, BasicBlock *BB,
02851                                   Instruction *Autorelease,
02852                                   SmallPtrSetImpl<Instruction *> &DepInsts,
02853                                   SmallPtrSetImpl<const BasicBlock *> &Visited,
02854                                   ProvenanceAnalysis &PA) {
02855   FindDependencies(CanChangeRetainCount, Arg,
02856                    BB, Autorelease, DepInsts, Visited, PA);
02857   if (DepInsts.size() != 1)
02858     return nullptr;
02859 
02860   CallInst *Retain =
02861     dyn_cast_or_null<CallInst>(*DepInsts.begin());
02862 
02863   // Check that we found a retain with the same argument.
02864   if (!Retain || !IsRetain(GetBasicARCInstKind(Retain)) ||
02865       GetArgRCIdentityRoot(Retain) != Arg) {
02866     return nullptr;
02867   }
02868 
02869   return Retain;
02870 }
02871 
02872 /// Look for an ``autorelease'' instruction dependent on Arg such that there are
02873 /// no instructions dependent on Arg that need a positive ref count in between
02874 /// the autorelease and the ret.
02875 static CallInst *
02876 FindPredecessorAutoreleaseWithSafePath(const Value *Arg, BasicBlock *BB,
02877                                        ReturnInst *Ret,
02878                                        SmallPtrSetImpl<Instruction *> &DepInsts,
02879                                        SmallPtrSetImpl<const BasicBlock *> &V,
02880                                        ProvenanceAnalysis &PA) {
02881   FindDependencies(NeedsPositiveRetainCount, Arg,
02882                    BB, Ret, DepInsts, V, PA);
02883   if (DepInsts.size() != 1)
02884     return nullptr;
02885 
02886   CallInst *Autorelease =
02887     dyn_cast_or_null<CallInst>(*DepInsts.begin());
02888   if (!Autorelease)
02889     return nullptr;
02890   ARCInstKind AutoreleaseClass = GetBasicARCInstKind(Autorelease);
02891   if (!IsAutorelease(AutoreleaseClass))
02892     return nullptr;
02893   if (GetArgRCIdentityRoot(Autorelease) != Arg)
02894     return nullptr;
02895 
02896   return Autorelease;
02897 }
02898 
02899 /// Look for this pattern:
02900 /// \code
02901 ///    %call = call i8* @something(...)
02902 ///    %2 = call i8* @objc_retain(i8* %call)
02903 ///    %3 = call i8* @objc_autorelease(i8* %2)
02904 ///    ret i8* %3
02905 /// \endcode
02906 /// And delete the retain and autorelease.
02907 void ObjCARCOpt::OptimizeReturns(Function &F) {
02908   if (!F.getReturnType()->isPointerTy())
02909     return;
02910 
02911   DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeReturns ==\n");
02912 
02913   SmallPtrSet<Instruction *, 4> DependingInstructions;
02914   SmallPtrSet<const BasicBlock *, 4> Visited;
02915   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
02916     BasicBlock *BB = FI;
02917     ReturnInst *Ret = dyn_cast<ReturnInst>(&BB->back());
02918 
02919     DEBUG(dbgs() << "Visiting: " << *Ret << "\n");
02920 
02921     if (!Ret)
02922       continue;
02923 
02924     const Value *Arg = GetRCIdentityRoot(Ret->getOperand(0));
02925 
02926     // Look for an ``autorelease'' instruction that is a predecessor of Ret and
02927     // dependent on Arg such that there are no instructions dependent on Arg
02928     // that need a positive ref count in between the autorelease and Ret.
02929     CallInst *Autorelease =
02930       FindPredecessorAutoreleaseWithSafePath(Arg, BB, Ret,
02931                                              DependingInstructions, Visited,
02932                                              PA);
02933     DependingInstructions.clear();
02934     Visited.clear();
02935 
02936     if (!Autorelease)
02937       continue;
02938 
02939     CallInst *Retain =
02940       FindPredecessorRetainWithSafePath(Arg, BB, Autorelease,
02941                                         DependingInstructions, Visited, PA);
02942     DependingInstructions.clear();
02943     Visited.clear();
02944 
02945     if (!Retain)
02946       continue;
02947 
02948     // Check that there is nothing that can affect the reference count
02949     // between the retain and the call.  Note that Retain need not be in BB.
02950     bool HasSafePathToCall = HasSafePathToPredecessorCall(Arg, Retain,
02951                                                           DependingInstructions,
02952                                                           Visited, PA);
02953     DependingInstructions.clear();
02954     Visited.clear();
02955 
02956     if (!HasSafePathToCall)
02957       continue;
02958 
02959     // If so, we can zap the retain and autorelease.
02960     Changed = true;
02961     ++NumRets;
02962     DEBUG(dbgs() << "Erasing: " << *Retain << "\nErasing: "
02963           << *Autorelease << "\n");
02964     EraseInstruction(Retain);
02965     EraseInstruction(Autorelease);
02966   }
02967 }
02968 
02969 #ifndef NDEBUG
02970 void
02971 ObjCARCOpt::GatherStatistics(Function &F, bool AfterOptimization) {
02972   llvm::Statistic &NumRetains =
02973     AfterOptimization? NumRetainsAfterOpt : NumRetainsBeforeOpt;
02974   llvm::Statistic &NumReleases =
02975     AfterOptimization? NumReleasesAfterOpt : NumReleasesBeforeOpt;
02976 
02977   for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
02978     Instruction *Inst = &*I++;
02979     switch (GetBasicARCInstKind(Inst)) {
02980     default:
02981       break;
02982     case ARCInstKind::Retain:
02983       ++NumRetains;
02984       break;
02985     case ARCInstKind::Release:
02986       ++NumReleases;
02987       break;
02988     }
02989   }
02990 }
02991 #endif
02992 
02993 bool ObjCARCOpt::doInitialization(Module &M) {
02994   if (!EnableARCOpts)
02995     return false;
02996 
02997   // If nothing in the Module uses ARC, don't do anything.
02998   Run = ModuleHasARC(M);
02999   if (!Run)
03000     return false;
03001 
03002   // Identify the imprecise release metadata kind.
03003   ImpreciseReleaseMDKind =
03004     M.getContext().getMDKindID("clang.imprecise_release");
03005   CopyOnEscapeMDKind =
03006     M.getContext().getMDKindID("clang.arc.copy_on_escape");
03007   NoObjCARCExceptionsMDKind =
03008     M.getContext().getMDKindID("clang.arc.no_objc_arc_exceptions");
03009 #ifdef ARC_ANNOTATIONS
03010   ARCAnnotationBottomUpMDKind =
03011     M.getContext().getMDKindID("llvm.arc.annotation.bottomup");
03012   ARCAnnotationTopDownMDKind =
03013     M.getContext().getMDKindID("llvm.arc.annotation.topdown");
03014   ARCAnnotationProvenanceSourceMDKind =
03015     M.getContext().getMDKindID("llvm.arc.annotation.provenancesource");
03016 #endif // ARC_ANNOTATIONS
03017 
03018   // Intuitively, objc_retain and others are nocapture, however in practice
03019   // they are not, because they return their argument value. And objc_release
03020   // calls finalizers which can have arbitrary side effects.
03021 
03022   // Initialize our runtime entry point cache.
03023   EP.Initialize(&M);
03024 
03025   return false;
03026 }
03027 
03028 bool ObjCARCOpt::runOnFunction(Function &F) {
03029   if (!EnableARCOpts)
03030     return false;
03031 
03032   // If nothing in the Module uses ARC, don't do anything.
03033   if (!Run)
03034     return false;
03035 
03036   Changed = false;
03037 
03038   DEBUG(dbgs() << "<<< ObjCARCOpt: Visiting Function: " << F.getName() << " >>>"
03039         "\n");
03040 
03041   PA.setAA(&getAnalysis<AliasAnalysis>());
03042 
03043 #ifndef NDEBUG
03044   if (AreStatisticsEnabled()) {
03045     GatherStatistics(F, false);
03046   }
03047 #endif
03048 
03049   // This pass performs several distinct transformations. As a compile-time aid
03050   // when compiling code that isn't ObjC, skip these if the relevant ObjC
03051   // library functions aren't declared.
03052 
03053   // Preliminary optimizations. This also computes UsedInThisFunction.
03054   OptimizeIndividualCalls(F);
03055 
03056   // Optimizations for weak pointers.
03057   if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::LoadWeak)) |
03058                             (1 << unsigned(ARCInstKind::LoadWeakRetained)) |
03059                             (1 << unsigned(ARCInstKind::StoreWeak)) |
03060                             (1 << unsigned(ARCInstKind::InitWeak)) |
03061                             (1 << unsigned(ARCInstKind::CopyWeak)) |
03062                             (1 << unsigned(ARCInstKind::MoveWeak)) |
03063                             (1 << unsigned(ARCInstKind::DestroyWeak))))
03064     OptimizeWeakCalls(F);
03065 
03066   // Optimizations for retain+release pairs.
03067   if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Retain)) |
03068                             (1 << unsigned(ARCInstKind::RetainRV)) |
03069                             (1 << unsigned(ARCInstKind::RetainBlock))))
03070     if (UsedInThisFunction & (1 << unsigned(ARCInstKind::Release)))
03071       // Run OptimizeSequences until it either stops making changes or
03072       // no retain+release pair nesting is detected.
03073       while (OptimizeSequences(F)) {}
03074 
03075   // Optimizations if objc_autorelease is used.
03076   if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Autorelease)) |
03077                             (1 << unsigned(ARCInstKind::AutoreleaseRV))))
03078     OptimizeReturns(F);
03079 
03080   // Gather statistics after optimization.
03081 #ifndef NDEBUG
03082   if (AreStatisticsEnabled()) {
03083     GatherStatistics(F, true);
03084   }
03085 #endif
03086 
03087   DEBUG(dbgs() << "\n");
03088 
03089   return Changed;
03090 }
03091 
03092 void ObjCARCOpt::releaseMemory() {
03093   PA.clear();
03094 }
03095 
03096 /// @}
03097 ///