LLVM API Documentation

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