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