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