1 //===- ObjCARCOpts.cpp - ObjC ARC Optimization ----------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 /// This file defines ObjC ARC optimizations. ARC stands for Automatic
11 /// Reference Counting and is a system for managing reference counts for objects
14 /// The optimizations performed include elimination of redundant, partially
15 /// redundant, and inconsequential reference count operations, elimination of
16 /// redundant weak pointer operations, pattern-matching and replacement of
17 /// low-level operations into higher-level operations, and numerous minor
20 /// This file also defines a simple ARC-aware AliasAnalysis.
22 /// WARNING: This file knows about certain library functions. It recognizes them
23 /// by name, and hardwires knowledge of their semantics.
25 /// WARNING: This file knows about how certain Objective-C library functions are
26 /// used. Naive LLVM IR transformations which would otherwise be
27 /// behavior-preserving may break these assumptions.
29 //===----------------------------------------------------------------------===//
31 #define DEBUG_TYPE "objc-arc-opts"
33 #include "DependencyAnalysis.h"
34 #include "ObjCARCAliasAnalysis.h"
35 #include "ProvenanceAnalysis.h"
36 #include "llvm/ADT/DenseMap.h"
37 #include "llvm/ADT/STLExtras.h"
38 #include "llvm/ADT/SmallPtrSet.h"
39 #include "llvm/ADT/Statistic.h"
40 #include "llvm/IR/LLVMContext.h"
41 #include "llvm/Support/CFG.h"
42 #include "llvm/Support/Debug.h"
43 #include "llvm/Support/raw_ostream.h"
46 using namespace llvm::objcarc;
48 /// \defgroup MiscUtils Miscellaneous utilities that are not ARC specific.
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>
56 /// Map keys to indices in Vector.
57 typedef DenseMap<KeyT, size_t> MapTy;
60 typedef std::vector<std::pair<KeyT, ValueT> > VectorTy;
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(); }
74 assert(Vector.size() >= Map.size()); // May differ due to blotting.
75 for (typename MapTy::const_iterator I = Map.begin(), E = Map.end();
77 assert(I->second < Vector.size());
78 assert(Vector[I->second].first == I->first);
80 for (typename VectorTy::const_iterator I = Vector.begin(),
81 E = Vector.end(); I != E; ++I)
83 (Map.count(I->first) &&
84 Map[I->first] == size_t(I - Vector.begin())));
88 ValueT &operator[](const KeyT &Arg) {
89 std::pair<typename MapTy::iterator, bool> Pair =
90 Map.insert(std::make_pair(Arg, size_t(0)));
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;
97 return Vector[Pair.first->second].second;
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)));
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);
110 return std::make_pair(Vector.begin() + Pair.first->second, false);
113 const_iterator find(const KeyT &Key) const {
114 typename MapTy::const_iterator It = Map.find(Key);
115 if (It == Map.end()) return Vector.end();
116 return Vector.begin() + It->second;
119 /// This is similar to erase, but instead of removing the element from the
120 /// vector, it just zeros out the key in the vector. This leaves iterators
121 /// intact, but clients must be prepared for zeroed-out keys when iterating.
122 void blot(const KeyT &Key) {
123 typename MapTy::iterator It = Map.find(Key);
124 if (It == Map.end()) return;
125 Vector[It->second].first = KeyT();
138 /// \defgroup ARCUtilities Utility declarations/definitions specific to ARC.
141 /// \brief This is similar to StripPointerCastsAndObjCCalls but it stops as soon
142 /// as it finds a value with multiple uses.
143 static const Value *FindSingleUseIdentifiedObject(const Value *Arg) {
144 if (Arg->hasOneUse()) {
145 if (const BitCastInst *BC = dyn_cast<BitCastInst>(Arg))
146 return FindSingleUseIdentifiedObject(BC->getOperand(0));
147 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Arg))
148 if (GEP->hasAllZeroIndices())
149 return FindSingleUseIdentifiedObject(GEP->getPointerOperand());
150 if (IsForwarding(GetBasicInstructionClass(Arg)))
151 return FindSingleUseIdentifiedObject(
152 cast<CallInst>(Arg)->getArgOperand(0));
153 if (!IsObjCIdentifiedObject(Arg))
158 // If we found an identifiable object but it has multiple uses, but they are
159 // trivial uses, we can still consider this to be a single-use value.
160 if (IsObjCIdentifiedObject(Arg)) {
161 for (Value::const_use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
164 if (!U->use_empty() || StripPointerCastsAndObjCCalls(U) != Arg)
174 /// \brief Test whether the given retainable object pointer escapes.
176 /// This differs from regular escape analysis in that a use as an
177 /// argument to a call is not considered an escape.
179 static bool DoesRetainableObjPtrEscape(const User *Ptr) {
180 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Target: " << *Ptr << "\n");
182 // Walk the def-use chains.
183 SmallVector<const Value *, 4> Worklist;
184 Worklist.push_back(Ptr);
185 // If Ptr has any operands add them as well.
186 for (User::const_op_iterator I = Ptr->op_begin(), E = Ptr->op_end(); I != E;
188 Worklist.push_back(*I);
191 // Ensure we do not visit any value twice.
192 SmallPtrSet<const Value *, 8> VisitedSet;
195 const Value *V = Worklist.pop_back_val();
197 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Visiting: " << *V << "\n");
199 for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end();
201 const User *UUser = *UI;
203 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: User: " << *UUser << "\n");
205 // Special - Use by a call (callee or argument) is not considered
207 switch (GetBasicInstructionClass(UUser)) {
212 case IC_AutoreleaseRV: {
213 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: User copies pointer "
214 "arguments. Pointer Escapes!\n");
215 // These special functions make copies of their pointer arguments.
220 // Use by an instruction which copies the value is an escape if the
221 // result is an escape.
222 if (isa<BitCastInst>(UUser) || isa<GetElementPtrInst>(UUser) ||
223 isa<PHINode>(UUser) || isa<SelectInst>(UUser)) {
225 if (!VisitedSet.insert(UUser)) {
226 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: User copies value. "
227 "Ptr escapes if result escapes. Adding to list.\n");
228 Worklist.push_back(UUser);
230 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Already visited node."
235 // Use by a load is not an escape.
236 if (isa<LoadInst>(UUser))
238 // Use by a store is not an escape if the use is the address.
239 if (const StoreInst *SI = dyn_cast<StoreInst>(UUser))
240 if (V != SI->getValueOperand())
244 // Regular calls and other stuff are not considered escapes.
247 // Otherwise, conservatively assume an escape.
248 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Assuming ptr escapes.\n");
251 } while (!Worklist.empty());
254 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Ptr does not escape.\n");
260 /// \defgroup ARCOpt ARC Optimization.
263 // TODO: On code like this:
266 // stuff_that_cannot_release()
267 // objc_autorelease(%x)
268 // stuff_that_cannot_release()
270 // stuff_that_cannot_release()
271 // objc_autorelease(%x)
273 // The second retain and autorelease can be deleted.
275 // TODO: It should be possible to delete
276 // objc_autoreleasePoolPush and objc_autoreleasePoolPop
277 // pairs if nothing is actually autoreleased between them. Also, autorelease
278 // calls followed by objc_autoreleasePoolPop calls (perhaps in ObjC++ code
279 // after inlining) can be turned into plain release calls.
281 // TODO: Critical-edge splitting. If the optimial insertion point is
282 // a critical edge, the current algorithm has to fail, because it doesn't
283 // know how to split edges. It should be possible to make the optimizer
284 // think in terms of edges, rather than blocks, and then split critical
287 // TODO: OptimizeSequences could generalized to be Interprocedural.
289 // TODO: Recognize that a bunch of other objc runtime calls have
290 // non-escaping arguments and non-releasing arguments, and may be
291 // non-autoreleasing.
293 // TODO: Sink autorelease calls as far as possible. Unfortunately we
294 // usually can't sink them past other calls, which would be the main
295 // case where it would be useful.
297 // TODO: The pointer returned from objc_loadWeakRetained is retained.
299 // TODO: Delete release+retain pairs (rare).
301 STATISTIC(NumNoops, "Number of no-op objc calls eliminated");
302 STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated");
303 STATISTIC(NumAutoreleases,"Number of autoreleases converted to releases");
304 STATISTIC(NumRets, "Number of return value forwarding "
305 "retain+autoreleaes eliminated");
306 STATISTIC(NumRRs, "Number of retain+release paths eliminated");
307 STATISTIC(NumPeeps, "Number of calls peephole-optimized");
312 /// \brief A sequence of states that a pointer may go through in which an
313 /// objc_retain and objc_release are actually needed.
316 S_Retain, ///< objc_retain(x).
317 S_CanRelease, ///< foo(x) -- x could possibly see a ref count decrement.
318 S_Use, ///< any use of x.
319 S_Stop, ///< like S_Release, but code motion is stopped.
320 S_Release, ///< objc_release(x).
321 S_MovableRelease ///< objc_release(x), !clang.imprecise_release.
324 raw_ostream &operator<<(raw_ostream &OS, const Sequence S)
325 LLVM_ATTRIBUTE_UNUSED;
326 raw_ostream &operator<<(raw_ostream &OS, const Sequence S) {
329 return OS << "S_None";
331 return OS << "S_Retain";
333 return OS << "S_CanRelease";
335 return OS << "S_Use";
337 return OS << "S_Release";
338 case S_MovableRelease:
339 return OS << "S_MovableRelease";
341 return OS << "S_Stop";
343 llvm_unreachable("Unknown sequence type.");
347 static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) {
351 if (A == S_None || B == S_None)
354 if (A > B) std::swap(A, B);
356 // Choose the side which is further along in the sequence.
357 if ((A == S_Retain || A == S_CanRelease) &&
358 (B == S_CanRelease || B == S_Use))
361 // Choose the side which is further along in the sequence.
362 if ((A == S_Use || A == S_CanRelease) &&
363 (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease))
365 // If both sides are releases, choose the more conservative one.
366 if (A == S_Stop && (B == S_Release || B == S_MovableRelease))
368 if (A == S_Release && B == S_MovableRelease)
376 /// \brief Unidirectional information about either a
377 /// retain-decrement-use-release sequence or release-use-decrement-retain
378 /// reverese sequence.
380 /// After an objc_retain, the reference count of the referenced
381 /// object is known to be positive. Similarly, before an objc_release, the
382 /// reference count of the referenced object is known to be positive. If
383 /// there are retain-release pairs in code regions where the retain count
384 /// is known to be positive, they can be eliminated, regardless of any side
385 /// effects between them.
387 /// Also, a retain+release pair nested within another retain+release
388 /// pair all on the known same pointer value can be eliminated, regardless
389 /// of any intervening side effects.
391 /// KnownSafe is true when either of these conditions is satisfied.
394 /// True if the Calls are objc_retainBlock calls (as opposed to objc_retain
398 /// True of the objc_release calls are all marked with the "tail" keyword.
399 bool IsTailCallRelease;
401 /// If the Calls are objc_release calls and they all have a
402 /// clang.imprecise_release tag, this is the metadata tag.
403 MDNode *ReleaseMetadata;
405 /// For a top-down sequence, the set of objc_retains or
406 /// objc_retainBlocks. For bottom-up, the set of objc_releases.
407 SmallPtrSet<Instruction *, 2> Calls;
409 /// The set of optimal insert positions for moving calls in the opposite
411 SmallPtrSet<Instruction *, 2> ReverseInsertPts;
414 KnownSafe(false), IsRetainBlock(false),
415 IsTailCallRelease(false),
416 ReleaseMetadata(0) {}
422 void RRInfo::clear() {
424 IsRetainBlock = false;
425 IsTailCallRelease = false;
428 ReverseInsertPts.clear();
432 /// \brief This class summarizes several per-pointer runtime properties which
433 /// are propogated through the flow graph.
435 /// True if the reference count is known to be incremented.
436 bool KnownPositiveRefCount;
438 /// True of we've seen an opportunity for partial RR elimination, such as
439 /// pushing calls into a CFG triangle or into one side of a CFG diamond.
442 /// The current position in the sequence.
446 /// Unidirectional information about the current sequence.
448 /// TODO: Encapsulate this better.
451 PtrState() : KnownPositiveRefCount(false), Partial(false),
454 void SetKnownPositiveRefCount() {
455 KnownPositiveRefCount = true;
458 void ClearRefCount() {
459 KnownPositiveRefCount = false;
462 bool IsKnownIncremented() const {
463 return KnownPositiveRefCount;
466 void SetSeq(Sequence NewSeq) {
470 Sequence GetSeq() const {
474 void ClearSequenceProgress() {
475 ResetSequenceProgress(S_None);
478 void ResetSequenceProgress(Sequence NewSeq) {
484 void Merge(const PtrState &Other, bool TopDown);
489 PtrState::Merge(const PtrState &Other, bool TopDown) {
490 Seq = MergeSeqs(Seq, Other.Seq, TopDown);
491 KnownPositiveRefCount = KnownPositiveRefCount && Other.KnownPositiveRefCount;
493 // We can't merge a plain objc_retain with an objc_retainBlock.
494 if (RRI.IsRetainBlock != Other.RRI.IsRetainBlock)
497 // If we're not in a sequence (anymore), drop all associated state.
501 } else if (Partial || Other.Partial) {
502 // If we're doing a merge on a path that's previously seen a partial
503 // merge, conservatively drop the sequence, to avoid doing partial
504 // RR elimination. If the branch predicates for the two merge differ,
505 // mixing them is unsafe.
506 ClearSequenceProgress();
508 // Conservatively merge the ReleaseMetadata information.
509 if (RRI.ReleaseMetadata != Other.RRI.ReleaseMetadata)
510 RRI.ReleaseMetadata = 0;
512 RRI.KnownSafe = RRI.KnownSafe && Other.RRI.KnownSafe;
513 RRI.IsTailCallRelease = RRI.IsTailCallRelease &&
514 Other.RRI.IsTailCallRelease;
515 RRI.Calls.insert(Other.RRI.Calls.begin(), Other.RRI.Calls.end());
517 // Merge the insert point sets. If there are any differences,
518 // that makes this a partial merge.
519 Partial = RRI.ReverseInsertPts.size() != Other.RRI.ReverseInsertPts.size();
520 for (SmallPtrSet<Instruction *, 2>::const_iterator
521 I = Other.RRI.ReverseInsertPts.begin(),
522 E = Other.RRI.ReverseInsertPts.end(); I != E; ++I)
523 Partial |= RRI.ReverseInsertPts.insert(*I);
528 /// \brief Per-BasicBlock state.
530 /// The number of unique control paths from the entry which can reach this
532 unsigned TopDownPathCount;
534 /// The number of unique control paths to exits from this block.
535 unsigned BottomUpPathCount;
537 /// A type for PerPtrTopDown and PerPtrBottomUp.
538 typedef MapVector<const Value *, PtrState> MapTy;
540 /// The top-down traversal uses this to record information known about a
541 /// pointer at the bottom of each block.
544 /// The bottom-up traversal uses this to record information known about a
545 /// pointer at the top of each block.
546 MapTy PerPtrBottomUp;
548 /// Effective predecessors of the current block ignoring ignorable edges and
549 /// ignored backedges.
550 SmallVector<BasicBlock *, 2> Preds;
551 /// Effective successors of the current block ignoring ignorable edges and
552 /// ignored backedges.
553 SmallVector<BasicBlock *, 2> Succs;
556 BBState() : TopDownPathCount(0), BottomUpPathCount(0) {}
558 typedef MapTy::iterator ptr_iterator;
559 typedef MapTy::const_iterator ptr_const_iterator;
561 ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); }
562 ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); }
563 ptr_const_iterator top_down_ptr_begin() const {
564 return PerPtrTopDown.begin();
566 ptr_const_iterator top_down_ptr_end() const {
567 return PerPtrTopDown.end();
570 ptr_iterator bottom_up_ptr_begin() { return PerPtrBottomUp.begin(); }
571 ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); }
572 ptr_const_iterator bottom_up_ptr_begin() const {
573 return PerPtrBottomUp.begin();
575 ptr_const_iterator bottom_up_ptr_end() const {
576 return PerPtrBottomUp.end();
579 /// Mark this block as being an entry block, which has one path from the
580 /// entry by definition.
581 void SetAsEntry() { TopDownPathCount = 1; }
583 /// Mark this block as being an exit block, which has one path to an exit by
585 void SetAsExit() { BottomUpPathCount = 1; }
587 PtrState &getPtrTopDownState(const Value *Arg) {
588 return PerPtrTopDown[Arg];
591 PtrState &getPtrBottomUpState(const Value *Arg) {
592 return PerPtrBottomUp[Arg];
595 void clearBottomUpPointers() {
596 PerPtrBottomUp.clear();
599 void clearTopDownPointers() {
600 PerPtrTopDown.clear();
603 void InitFromPred(const BBState &Other);
604 void InitFromSucc(const BBState &Other);
605 void MergePred(const BBState &Other);
606 void MergeSucc(const BBState &Other);
608 /// Return the number of possible unique paths from an entry to an exit
609 /// which pass through this block. This is only valid after both the
610 /// top-down and bottom-up traversals are complete.
611 unsigned GetAllPathCount() const {
612 assert(TopDownPathCount != 0);
613 assert(BottomUpPathCount != 0);
614 return TopDownPathCount * BottomUpPathCount;
617 // Specialized CFG utilities.
618 typedef SmallVectorImpl<BasicBlock *>::const_iterator edge_iterator;
619 edge_iterator pred_begin() { return Preds.begin(); }
620 edge_iterator pred_end() { return Preds.end(); }
621 edge_iterator succ_begin() { return Succs.begin(); }
622 edge_iterator succ_end() { return Succs.end(); }
624 void addSucc(BasicBlock *Succ) { Succs.push_back(Succ); }
625 void addPred(BasicBlock *Pred) { Preds.push_back(Pred); }
627 bool isExit() const { return Succs.empty(); }
631 void BBState::InitFromPred(const BBState &Other) {
632 PerPtrTopDown = Other.PerPtrTopDown;
633 TopDownPathCount = Other.TopDownPathCount;
636 void BBState::InitFromSucc(const BBState &Other) {
637 PerPtrBottomUp = Other.PerPtrBottomUp;
638 BottomUpPathCount = Other.BottomUpPathCount;
641 /// The top-down traversal uses this to merge information about predecessors to
642 /// form the initial state for a new block.
643 void BBState::MergePred(const BBState &Other) {
644 // Other.TopDownPathCount can be 0, in which case it is either dead or a
645 // loop backedge. Loop backedges are special.
646 TopDownPathCount += Other.TopDownPathCount;
648 // Check for overflow. If we have overflow, fall back to conservative
650 if (TopDownPathCount < Other.TopDownPathCount) {
651 clearTopDownPointers();
655 // For each entry in the other set, if our set has an entry with the same key,
656 // merge the entries. Otherwise, copy the entry and merge it with an empty
658 for (ptr_const_iterator MI = Other.top_down_ptr_begin(),
659 ME = Other.top_down_ptr_end(); MI != ME; ++MI) {
660 std::pair<ptr_iterator, bool> Pair = PerPtrTopDown.insert(*MI);
661 Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
665 // For each entry in our set, if the other set doesn't have an entry with the
666 // same key, force it to merge with an empty entry.
667 for (ptr_iterator MI = top_down_ptr_begin(),
668 ME = top_down_ptr_end(); MI != ME; ++MI)
669 if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end())
670 MI->second.Merge(PtrState(), /*TopDown=*/true);
673 /// The bottom-up traversal uses this to merge information about successors to
674 /// form the initial state for a new block.
675 void BBState::MergeSucc(const BBState &Other) {
676 // Other.BottomUpPathCount can be 0, in which case it is either dead or a
677 // loop backedge. Loop backedges are special.
678 BottomUpPathCount += Other.BottomUpPathCount;
680 // Check for overflow. If we have overflow, fall back to conservative
682 if (BottomUpPathCount < Other.BottomUpPathCount) {
683 clearBottomUpPointers();
687 // For each entry in the other set, if our set has an entry with the
688 // same key, merge the entries. Otherwise, copy the entry and merge
689 // it with an empty entry.
690 for (ptr_const_iterator MI = Other.bottom_up_ptr_begin(),
691 ME = Other.bottom_up_ptr_end(); MI != ME; ++MI) {
692 std::pair<ptr_iterator, bool> Pair = PerPtrBottomUp.insert(*MI);
693 Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
697 // For each entry in our set, if the other set doesn't have an entry
698 // with the same key, force it to merge with an empty entry.
699 for (ptr_iterator MI = bottom_up_ptr_begin(),
700 ME = bottom_up_ptr_end(); MI != ME; ++MI)
701 if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end())
702 MI->second.Merge(PtrState(), /*TopDown=*/false);
706 /// \brief The main ARC optimization pass.
707 class ObjCARCOpt : public FunctionPass {
709 ProvenanceAnalysis PA;
711 /// A flag indicating whether this optimization pass should run.
714 /// Declarations for ObjC runtime functions, for use in creating calls to
715 /// them. These are initialized lazily to avoid cluttering up the Module
716 /// with unused declarations.
718 /// Declaration for ObjC runtime function
719 /// objc_retainAutoreleasedReturnValue.
720 Constant *RetainRVCallee;
721 /// Declaration for ObjC runtime function objc_autoreleaseReturnValue.
722 Constant *AutoreleaseRVCallee;
723 /// Declaration for ObjC runtime function objc_release.
724 Constant *ReleaseCallee;
725 /// Declaration for ObjC runtime function objc_retain.
726 Constant *RetainCallee;
727 /// Declaration for ObjC runtime function objc_retainBlock.
728 Constant *RetainBlockCallee;
729 /// Declaration for ObjC runtime function objc_autorelease.
730 Constant *AutoreleaseCallee;
732 /// Flags which determine whether each of the interesting runtine functions
733 /// is in fact used in the current function.
734 unsigned UsedInThisFunction;
736 /// The Metadata Kind for clang.imprecise_release metadata.
737 unsigned ImpreciseReleaseMDKind;
739 /// The Metadata Kind for clang.arc.copy_on_escape metadata.
740 unsigned CopyOnEscapeMDKind;
742 /// The Metadata Kind for clang.arc.no_objc_arc_exceptions metadata.
743 unsigned NoObjCARCExceptionsMDKind;
745 Constant *getRetainRVCallee(Module *M);
746 Constant *getAutoreleaseRVCallee(Module *M);
747 Constant *getReleaseCallee(Module *M);
748 Constant *getRetainCallee(Module *M);
749 Constant *getRetainBlockCallee(Module *M);
750 Constant *getAutoreleaseCallee(Module *M);
752 bool IsRetainBlockOptimizable(const Instruction *Inst);
754 void OptimizeRetainCall(Function &F, Instruction *Retain);
755 bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV);
756 void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV,
757 InstructionClass &Class);
758 void OptimizeIndividualCalls(Function &F);
760 void CheckForCFGHazards(const BasicBlock *BB,
761 DenseMap<const BasicBlock *, BBState> &BBStates,
762 BBState &MyStates) const;
763 bool VisitInstructionBottomUp(Instruction *Inst,
765 MapVector<Value *, RRInfo> &Retains,
767 bool VisitBottomUp(BasicBlock *BB,
768 DenseMap<const BasicBlock *, BBState> &BBStates,
769 MapVector<Value *, RRInfo> &Retains);
770 bool VisitInstructionTopDown(Instruction *Inst,
771 DenseMap<Value *, RRInfo> &Releases,
773 bool VisitTopDown(BasicBlock *BB,
774 DenseMap<const BasicBlock *, BBState> &BBStates,
775 DenseMap<Value *, RRInfo> &Releases);
776 bool Visit(Function &F,
777 DenseMap<const BasicBlock *, BBState> &BBStates,
778 MapVector<Value *, RRInfo> &Retains,
779 DenseMap<Value *, RRInfo> &Releases);
781 void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove,
782 MapVector<Value *, RRInfo> &Retains,
783 DenseMap<Value *, RRInfo> &Releases,
784 SmallVectorImpl<Instruction *> &DeadInsts,
787 bool ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState> &BBStates,
788 MapVector<Value *, RRInfo> &Retains,
789 DenseMap<Value *, RRInfo> &Releases,
791 SmallVector<Instruction *, 4> &NewRetains,
792 SmallVector<Instruction *, 4> &NewReleases,
793 SmallVector<Instruction *, 8> &DeadInsts,
794 RRInfo &RetainsToMove,
795 RRInfo &ReleasesToMove,
798 bool &AnyPairsCompletelyEliminated);
800 bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates,
801 MapVector<Value *, RRInfo> &Retains,
802 DenseMap<Value *, RRInfo> &Releases,
805 void OptimizeWeakCalls(Function &F);
807 bool OptimizeSequences(Function &F);
809 void OptimizeReturns(Function &F);
811 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
812 virtual bool doInitialization(Module &M);
813 virtual bool runOnFunction(Function &F);
814 virtual void releaseMemory();
818 ObjCARCOpt() : FunctionPass(ID) {
819 initializeObjCARCOptPass(*PassRegistry::getPassRegistry());
824 char ObjCARCOpt::ID = 0;
825 INITIALIZE_PASS_BEGIN(ObjCARCOpt,
826 "objc-arc", "ObjC ARC optimization", false, false)
827 INITIALIZE_PASS_DEPENDENCY(ObjCARCAliasAnalysis)
828 INITIALIZE_PASS_END(ObjCARCOpt,
829 "objc-arc", "ObjC ARC optimization", false, false)
831 Pass *llvm::createObjCARCOptPass() {
832 return new ObjCARCOpt();
835 void ObjCARCOpt::getAnalysisUsage(AnalysisUsage &AU) const {
836 AU.addRequired<ObjCARCAliasAnalysis>();
837 AU.addRequired<AliasAnalysis>();
838 // ARC optimization doesn't currently split critical edges.
839 AU.setPreservesCFG();
842 bool ObjCARCOpt::IsRetainBlockOptimizable(const Instruction *Inst) {
843 // Without the magic metadata tag, we have to assume this might be an
844 // objc_retainBlock call inserted to convert a block pointer to an id,
845 // in which case it really is needed.
846 if (!Inst->getMetadata(CopyOnEscapeMDKind))
849 // If the pointer "escapes" (not including being used in a call),
850 // the copy may be needed.
851 if (DoesRetainableObjPtrEscape(Inst))
854 // Otherwise, it's not needed.
858 Constant *ObjCARCOpt::getRetainRVCallee(Module *M) {
859 if (!RetainRVCallee) {
860 LLVMContext &C = M->getContext();
861 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
862 Type *Params[] = { I8X };
863 FunctionType *FTy = FunctionType::get(I8X, Params, /*isVarArg=*/false);
864 AttributeSet Attribute =
865 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
866 Attribute::NoUnwind);
868 M->getOrInsertFunction("objc_retainAutoreleasedReturnValue", FTy,
871 return RetainRVCallee;
874 Constant *ObjCARCOpt::getAutoreleaseRVCallee(Module *M) {
875 if (!AutoreleaseRVCallee) {
876 LLVMContext &C = M->getContext();
877 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
878 Type *Params[] = { I8X };
879 FunctionType *FTy = FunctionType::get(I8X, Params, /*isVarArg=*/false);
880 AttributeSet Attribute =
881 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
882 Attribute::NoUnwind);
883 AutoreleaseRVCallee =
884 M->getOrInsertFunction("objc_autoreleaseReturnValue", FTy,
887 return AutoreleaseRVCallee;
890 Constant *ObjCARCOpt::getReleaseCallee(Module *M) {
891 if (!ReleaseCallee) {
892 LLVMContext &C = M->getContext();
893 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
894 AttributeSet Attribute =
895 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
896 Attribute::NoUnwind);
898 M->getOrInsertFunction(
900 FunctionType::get(Type::getVoidTy(C), Params, /*isVarArg=*/false),
903 return ReleaseCallee;
906 Constant *ObjCARCOpt::getRetainCallee(Module *M) {
908 LLVMContext &C = M->getContext();
909 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
910 AttributeSet Attribute =
911 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
912 Attribute::NoUnwind);
914 M->getOrInsertFunction(
916 FunctionType::get(Params[0], Params, /*isVarArg=*/false),
922 Constant *ObjCARCOpt::getRetainBlockCallee(Module *M) {
923 if (!RetainBlockCallee) {
924 LLVMContext &C = M->getContext();
925 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
926 // objc_retainBlock is not nounwind because it calls user copy constructors
927 // which could theoretically throw.
929 M->getOrInsertFunction(
931 FunctionType::get(Params[0], Params, /*isVarArg=*/false),
934 return RetainBlockCallee;
937 Constant *ObjCARCOpt::getAutoreleaseCallee(Module *M) {
938 if (!AutoreleaseCallee) {
939 LLVMContext &C = M->getContext();
940 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
941 AttributeSet Attribute =
942 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
943 Attribute::NoUnwind);
945 M->getOrInsertFunction(
947 FunctionType::get(Params[0], Params, /*isVarArg=*/false),
950 return AutoreleaseCallee;
953 /// Turn objc_retain into objc_retainAutoreleasedReturnValue if the operand is a
956 ObjCARCOpt::OptimizeRetainCall(Function &F, Instruction *Retain) {
957 ImmutableCallSite CS(GetObjCArg(Retain));
958 const Instruction *Call = CS.getInstruction();
960 if (Call->getParent() != Retain->getParent()) return;
962 // Check that the call is next to the retain.
963 BasicBlock::const_iterator I = Call;
965 while (isNoopInstruction(I)) ++I;
969 // Turn it to an objc_retainAutoreleasedReturnValue..
973 DEBUG(dbgs() << "ObjCARCOpt::OptimizeRetainCall: Transforming "
974 "objc_retain => objc_retainAutoreleasedReturnValue"
975 " since the operand is a return value.\n"
979 cast<CallInst>(Retain)->setCalledFunction(getRetainRVCallee(F.getParent()));
981 DEBUG(dbgs() << " New: "
985 /// Turn objc_retainAutoreleasedReturnValue into objc_retain if the operand is
986 /// not a return value. Or, if it can be paired with an
987 /// objc_autoreleaseReturnValue, delete the pair and return true.
989 ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) {
990 // Check for the argument being from an immediately preceding call or invoke.
991 const Value *Arg = GetObjCArg(RetainRV);
992 ImmutableCallSite CS(Arg);
993 if (const Instruction *Call = CS.getInstruction()) {
994 if (Call->getParent() == RetainRV->getParent()) {
995 BasicBlock::const_iterator I = Call;
997 while (isNoopInstruction(I)) ++I;
1000 } else if (const InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
1001 BasicBlock *RetainRVParent = RetainRV->getParent();
1002 if (II->getNormalDest() == RetainRVParent) {
1003 BasicBlock::const_iterator I = RetainRVParent->begin();
1004 while (isNoopInstruction(I)) ++I;
1005 if (&*I == RetainRV)
1011 // Check for being preceded by an objc_autoreleaseReturnValue on the same
1012 // pointer. In this case, we can delete the pair.
1013 BasicBlock::iterator I = RetainRV, Begin = RetainRV->getParent()->begin();
1015 do --I; while (I != Begin && isNoopInstruction(I));
1016 if (GetBasicInstructionClass(I) == IC_AutoreleaseRV &&
1017 GetObjCArg(I) == Arg) {
1021 DEBUG(dbgs() << "ObjCARCOpt::OptimizeRetainRVCall: Erasing " << *I << "\n"
1022 << " Erasing " << *RetainRV
1025 EraseInstruction(I);
1026 EraseInstruction(RetainRV);
1031 // Turn it to a plain objc_retain.
1035 DEBUG(dbgs() << "ObjCARCOpt::OptimizeRetainRVCall: Transforming "
1036 "objc_retainAutoreleasedReturnValue => "
1037 "objc_retain since the operand is not a return value.\n"
1039 << *RetainRV << "\n");
1041 cast<CallInst>(RetainRV)->setCalledFunction(getRetainCallee(F.getParent()));
1043 DEBUG(dbgs() << " New: "
1044 << *RetainRV << "\n");
1049 /// Turn objc_autoreleaseReturnValue into objc_autorelease if the result is not
1050 /// used as a return value.
1052 ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV,
1053 InstructionClass &Class) {
1054 // Check for a return of the pointer value.
1055 const Value *Ptr = GetObjCArg(AutoreleaseRV);
1056 SmallVector<const Value *, 2> Users;
1057 Users.push_back(Ptr);
1059 Ptr = Users.pop_back_val();
1060 for (Value::const_use_iterator UI = Ptr->use_begin(), UE = Ptr->use_end();
1062 const User *I = *UI;
1063 if (isa<ReturnInst>(I) || GetBasicInstructionClass(I) == IC_RetainRV)
1065 if (isa<BitCastInst>(I))
1068 } while (!Users.empty());
1073 DEBUG(dbgs() << "ObjCARCOpt::OptimizeAutoreleaseRVCall: Transforming "
1074 "objc_autoreleaseReturnValue => "
1075 "objc_autorelease since its operand is not used as a return "
1078 << *AutoreleaseRV << "\n");
1080 CallInst *AutoreleaseRVCI = cast<CallInst>(AutoreleaseRV);
1082 setCalledFunction(getAutoreleaseCallee(F.getParent()));
1083 AutoreleaseRVCI->setTailCall(false); // Never tail call objc_autorelease.
1084 Class = IC_Autorelease;
1086 DEBUG(dbgs() << " New: "
1087 << *AutoreleaseRV << "\n");
1091 /// Visit each call, one at a time, and make simplifications without doing any
1092 /// additional analysis.
1093 void ObjCARCOpt::OptimizeIndividualCalls(Function &F) {
1094 // Reset all the flags in preparation for recomputing them.
1095 UsedInThisFunction = 0;
1097 // Visit all objc_* calls in F.
1098 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
1099 Instruction *Inst = &*I++;
1101 InstructionClass Class = GetBasicInstructionClass(Inst);
1103 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Visiting: Class: "
1104 << Class << "; " << *Inst << "\n");
1109 // Delete no-op casts. These function calls have special semantics, but
1110 // the semantics are entirely implemented via lowering in the front-end,
1111 // so by the time they reach the optimizer, they are just no-op calls
1112 // which return their argument.
1114 // There are gray areas here, as the ability to cast reference-counted
1115 // pointers to raw void* and back allows code to break ARC assumptions,
1116 // however these are currently considered to be unimportant.
1120 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Erasing no-op cast:"
1121 " " << *Inst << "\n");
1122 EraseInstruction(Inst);
1125 // If the pointer-to-weak-pointer is null, it's undefined behavior.
1128 case IC_LoadWeakRetained:
1130 case IC_DestroyWeak: {
1131 CallInst *CI = cast<CallInst>(Inst);
1132 if (isNullOrUndef(CI->getArgOperand(0))) {
1134 Type *Ty = CI->getArgOperand(0)->getType();
1135 new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
1136 Constant::getNullValue(Ty),
1138 llvm::Value *NewValue = UndefValue::get(CI->getType());
1139 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: A null "
1140 "pointer-to-weak-pointer is undefined behavior.\n"
1144 CI->replaceAllUsesWith(NewValue);
1145 CI->eraseFromParent();
1152 CallInst *CI = cast<CallInst>(Inst);
1153 if (isNullOrUndef(CI->getArgOperand(0)) ||
1154 isNullOrUndef(CI->getArgOperand(1))) {
1156 Type *Ty = CI->getArgOperand(0)->getType();
1157 new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
1158 Constant::getNullValue(Ty),
1161 llvm::Value *NewValue = UndefValue::get(CI->getType());
1162 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: A null "
1163 "pointer-to-weak-pointer is undefined behavior.\n"
1168 CI->replaceAllUsesWith(NewValue);
1169 CI->eraseFromParent();
1175 OptimizeRetainCall(F, Inst);
1178 if (OptimizeRetainRVCall(F, Inst))
1181 case IC_AutoreleaseRV:
1182 OptimizeAutoreleaseRVCall(F, Inst, Class);
1186 // objc_autorelease(x) -> objc_release(x) if x is otherwise unused.
1187 if (IsAutorelease(Class) && Inst->use_empty()) {
1188 CallInst *Call = cast<CallInst>(Inst);
1189 const Value *Arg = Call->getArgOperand(0);
1190 Arg = FindSingleUseIdentifiedObject(Arg);
1195 // Create the declaration lazily.
1196 LLVMContext &C = Inst->getContext();
1198 CallInst::Create(getReleaseCallee(F.getParent()),
1199 Call->getArgOperand(0), "", Call);
1200 NewCall->setMetadata(ImpreciseReleaseMDKind,
1201 MDNode::get(C, ArrayRef<Value *>()));
1203 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Replacing "
1204 "objc_autorelease(x) with objc_release(x) since x is "
1205 "otherwise unused.\n"
1206 " Old: " << *Call <<
1210 EraseInstruction(Call);
1216 // For functions which can never be passed stack arguments, add
1218 if (IsAlwaysTail(Class)) {
1220 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Adding tail keyword"
1221 " to function since it can never be passed stack args: " << *Inst <<
1223 cast<CallInst>(Inst)->setTailCall();
1226 // Ensure that functions that can never have a "tail" keyword due to the
1227 // semantics of ARC truly do not do so.
1228 if (IsNeverTail(Class)) {
1230 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Removing tail "
1231 "keyword from function: " << *Inst <<
1233 cast<CallInst>(Inst)->setTailCall(false);
1236 // Set nounwind as needed.
1237 if (IsNoThrow(Class)) {
1239 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Found no throw"
1240 " class. Setting nounwind on: " << *Inst << "\n");
1241 cast<CallInst>(Inst)->setDoesNotThrow();
1244 if (!IsNoopOnNull(Class)) {
1245 UsedInThisFunction |= 1 << Class;
1249 const Value *Arg = GetObjCArg(Inst);
1251 // ARC calls with null are no-ops. Delete them.
1252 if (isNullOrUndef(Arg)) {
1255 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: ARC calls with "
1256 " null are no-ops. Erasing: " << *Inst << "\n");
1257 EraseInstruction(Inst);
1261 // Keep track of which of retain, release, autorelease, and retain_block
1262 // are actually present in this function.
1263 UsedInThisFunction |= 1 << Class;
1265 // If Arg is a PHI, and one or more incoming values to the
1266 // PHI are null, and the call is control-equivalent to the PHI, and there
1267 // are no relevant side effects between the PHI and the call, the call
1268 // could be pushed up to just those paths with non-null incoming values.
1269 // For now, don't bother splitting critical edges for this.
1270 SmallVector<std::pair<Instruction *, const Value *>, 4> Worklist;
1271 Worklist.push_back(std::make_pair(Inst, Arg));
1273 std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val();
1277 const PHINode *PN = dyn_cast<PHINode>(Arg);
1280 // Determine if the PHI has any null operands, or any incoming
1282 bool HasNull = false;
1283 bool HasCriticalEdges = false;
1284 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1286 StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
1287 if (isNullOrUndef(Incoming))
1289 else if (cast<TerminatorInst>(PN->getIncomingBlock(i)->back())
1290 .getNumSuccessors() != 1) {
1291 HasCriticalEdges = true;
1295 // If we have null operands and no critical edges, optimize.
1296 if (!HasCriticalEdges && HasNull) {
1297 SmallPtrSet<Instruction *, 4> DependingInstructions;
1298 SmallPtrSet<const BasicBlock *, 4> Visited;
1300 // Check that there is nothing that cares about the reference
1301 // count between the call and the phi.
1304 case IC_RetainBlock:
1305 // These can always be moved up.
1308 // These can't be moved across things that care about the retain
1310 FindDependencies(NeedsPositiveRetainCount, Arg,
1311 Inst->getParent(), Inst,
1312 DependingInstructions, Visited, PA);
1314 case IC_Autorelease:
1315 // These can't be moved across autorelease pool scope boundaries.
1316 FindDependencies(AutoreleasePoolBoundary, Arg,
1317 Inst->getParent(), Inst,
1318 DependingInstructions, Visited, PA);
1321 case IC_AutoreleaseRV:
1322 // Don't move these; the RV optimization depends on the autoreleaseRV
1323 // being tail called, and the retainRV being immediately after a call
1324 // (which might still happen if we get lucky with codegen layout, but
1325 // it's not worth taking the chance).
1328 llvm_unreachable("Invalid dependence flavor");
1331 if (DependingInstructions.size() == 1 &&
1332 *DependingInstructions.begin() == PN) {
1335 // Clone the call into each predecessor that has a non-null value.
1336 CallInst *CInst = cast<CallInst>(Inst);
1337 Type *ParamTy = CInst->getArgOperand(0)->getType();
1338 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1340 StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
1341 if (!isNullOrUndef(Incoming)) {
1342 CallInst *Clone = cast<CallInst>(CInst->clone());
1343 Value *Op = PN->getIncomingValue(i);
1344 Instruction *InsertPos = &PN->getIncomingBlock(i)->back();
1345 if (Op->getType() != ParamTy)
1346 Op = new BitCastInst(Op, ParamTy, "", InsertPos);
1347 Clone->setArgOperand(0, Op);
1348 Clone->insertBefore(InsertPos);
1350 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Cloning "
1353 "clone at " << *InsertPos << "\n");
1354 Worklist.push_back(std::make_pair(Clone, Incoming));
1357 // Erase the original call.
1358 DEBUG(dbgs() << "Erasing: " << *CInst << "\n");
1359 EraseInstruction(CInst);
1363 } while (!Worklist.empty());
1365 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Finished List.\n");
1368 /// Check for critical edges, loop boundaries, irreducible control flow, or
1369 /// other CFG structures where moving code across the edge would result in it
1370 /// being executed more.
1372 ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB,
1373 DenseMap<const BasicBlock *, BBState> &BBStates,
1374 BBState &MyStates) const {
1375 // If any top-down local-use or possible-dec has a succ which is earlier in
1376 // the sequence, forget it.
1377 for (BBState::ptr_iterator I = MyStates.top_down_ptr_begin(),
1378 E = MyStates.top_down_ptr_end(); I != E; ++I)
1379 switch (I->second.GetSeq()) {
1382 const Value *Arg = I->first;
1383 const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
1384 bool SomeSuccHasSame = false;
1385 bool AllSuccsHaveSame = true;
1386 PtrState &S = I->second;
1387 succ_const_iterator SI(TI), SE(TI, false);
1389 for (; SI != SE; ++SI) {
1390 Sequence SuccSSeq = S_None;
1391 bool SuccSRRIKnownSafe = false;
1392 // If VisitBottomUp has pointer information for this successor, take
1393 // what we know about it.
1394 DenseMap<const BasicBlock *, BBState>::iterator BBI =
1396 assert(BBI != BBStates.end());
1397 const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);
1398 SuccSSeq = SuccS.GetSeq();
1399 SuccSRRIKnownSafe = SuccS.RRI.KnownSafe;
1402 case S_CanRelease: {
1403 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe) {
1404 S.ClearSequenceProgress();
1410 SomeSuccHasSame = true;
1414 case S_MovableRelease:
1415 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe)
1416 AllSuccsHaveSame = false;
1419 llvm_unreachable("bottom-up pointer in retain state!");
1422 // If the state at the other end of any of the successor edges
1423 // matches the current state, require all edges to match. This
1424 // guards against loops in the middle of a sequence.
1425 if (SomeSuccHasSame && !AllSuccsHaveSame)
1426 S.ClearSequenceProgress();
1429 case S_CanRelease: {
1430 const Value *Arg = I->first;
1431 const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
1432 bool SomeSuccHasSame = false;
1433 bool AllSuccsHaveSame = true;
1434 PtrState &S = I->second;
1435 succ_const_iterator SI(TI), SE(TI, false);
1437 for (; SI != SE; ++SI) {
1438 Sequence SuccSSeq = S_None;
1439 bool SuccSRRIKnownSafe = false;
1440 // If VisitBottomUp has pointer information for this successor, take
1441 // what we know about it.
1442 DenseMap<const BasicBlock *, BBState>::iterator BBI =
1444 assert(BBI != BBStates.end());
1445 const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);
1446 SuccSSeq = SuccS.GetSeq();
1447 SuccSRRIKnownSafe = SuccS.RRI.KnownSafe;
1450 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe) {
1451 S.ClearSequenceProgress();
1457 SomeSuccHasSame = true;
1461 case S_MovableRelease:
1463 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe)
1464 AllSuccsHaveSame = false;
1467 llvm_unreachable("bottom-up pointer in retain state!");
1470 // If the state at the other end of any of the successor edges
1471 // matches the current state, require all edges to match. This
1472 // guards against loops in the middle of a sequence.
1473 if (SomeSuccHasSame && !AllSuccsHaveSame)
1474 S.ClearSequenceProgress();
1481 ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst,
1483 MapVector<Value *, RRInfo> &Retains,
1484 BBState &MyStates) {
1485 bool NestingDetected = false;
1486 InstructionClass Class = GetInstructionClass(Inst);
1487 const Value *Arg = 0;
1491 Arg = GetObjCArg(Inst);
1493 PtrState &S = MyStates.getPtrBottomUpState(Arg);
1495 // If we see two releases in a row on the same pointer. If so, make
1496 // a note, and we'll cicle back to revisit it after we've
1497 // hopefully eliminated the second release, which may allow us to
1498 // eliminate the first release too.
1499 // Theoretically we could implement removal of nested retain+release
1500 // pairs by making PtrState hold a stack of states, but this is
1501 // simple and avoids adding overhead for the non-nested case.
1502 if (S.GetSeq() == S_Release || S.GetSeq() == S_MovableRelease) {
1503 DEBUG(dbgs() << "ObjCARCOpt::VisitInstructionBottomUp: Found nested "
1504 "releases (i.e. a release pair)\n");
1505 NestingDetected = true;
1508 MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind);
1509 S.ResetSequenceProgress(ReleaseMetadata ? S_MovableRelease : S_Release);
1510 S.RRI.ReleaseMetadata = ReleaseMetadata;
1511 S.RRI.KnownSafe = S.IsKnownIncremented();
1512 S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
1513 S.RRI.Calls.insert(Inst);
1515 S.SetKnownPositiveRefCount();
1518 case IC_RetainBlock:
1519 // An objc_retainBlock call with just a use may need to be kept,
1520 // because it may be copying a block from the stack to the heap.
1521 if (!IsRetainBlockOptimizable(Inst))
1526 Arg = GetObjCArg(Inst);
1528 PtrState &S = MyStates.getPtrBottomUpState(Arg);
1529 S.SetKnownPositiveRefCount();
1531 switch (S.GetSeq()) {
1534 case S_MovableRelease:
1536 S.RRI.ReverseInsertPts.clear();
1539 // Don't do retain+release tracking for IC_RetainRV, because it's
1540 // better to let it remain as the first instruction after a call.
1541 if (Class != IC_RetainRV) {
1542 S.RRI.IsRetainBlock = Class == IC_RetainBlock;
1543 Retains[Inst] = S.RRI;
1545 S.ClearSequenceProgress();
1550 llvm_unreachable("bottom-up pointer in retain state!");
1552 return NestingDetected;
1554 case IC_AutoreleasepoolPop:
1555 // Conservatively, clear MyStates for all known pointers.
1556 MyStates.clearBottomUpPointers();
1557 return NestingDetected;
1558 case IC_AutoreleasepoolPush:
1560 // These are irrelevant.
1561 return NestingDetected;
1566 // Consider any other possible effects of this instruction on each
1567 // pointer being tracked.
1568 for (BBState::ptr_iterator MI = MyStates.bottom_up_ptr_begin(),
1569 ME = MyStates.bottom_up_ptr_end(); MI != ME; ++MI) {
1570 const Value *Ptr = MI->first;
1572 continue; // Handled above.
1573 PtrState &S = MI->second;
1574 Sequence Seq = S.GetSeq();
1576 // Check for possible releases.
1577 if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
1581 S.SetSeq(S_CanRelease);
1585 case S_MovableRelease:
1590 llvm_unreachable("bottom-up pointer in retain state!");
1594 // Check for possible direct uses.
1597 case S_MovableRelease:
1598 if (CanUse(Inst, Ptr, PA, Class)) {
1599 assert(S.RRI.ReverseInsertPts.empty());
1600 // If this is an invoke instruction, we're scanning it as part of
1601 // one of its successor blocks, since we can't insert code after it
1602 // in its own block, and we don't want to split critical edges.
1603 if (isa<InvokeInst>(Inst))
1604 S.RRI.ReverseInsertPts.insert(BB->getFirstInsertionPt());
1606 S.RRI.ReverseInsertPts.insert(llvm::next(BasicBlock::iterator(Inst)));
1608 } else if (Seq == S_Release &&
1609 (Class == IC_User || Class == IC_CallOrUser)) {
1610 // Non-movable releases depend on any possible objc pointer use.
1612 assert(S.RRI.ReverseInsertPts.empty());
1613 // As above; handle invoke specially.
1614 if (isa<InvokeInst>(Inst))
1615 S.RRI.ReverseInsertPts.insert(BB->getFirstInsertionPt());
1617 S.RRI.ReverseInsertPts.insert(llvm::next(BasicBlock::iterator(Inst)));
1621 if (CanUse(Inst, Ptr, PA, Class))
1629 llvm_unreachable("bottom-up pointer in retain state!");
1633 return NestingDetected;
1637 ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
1638 DenseMap<const BasicBlock *, BBState> &BBStates,
1639 MapVector<Value *, RRInfo> &Retains) {
1640 bool NestingDetected = false;
1641 BBState &MyStates = BBStates[BB];
1643 // Merge the states from each successor to compute the initial state
1644 // for the current block.
1645 BBState::edge_iterator SI(MyStates.succ_begin()),
1646 SE(MyStates.succ_end());
1648 const BasicBlock *Succ = *SI;
1649 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ);
1650 assert(I != BBStates.end());
1651 MyStates.InitFromSucc(I->second);
1653 for (; SI != SE; ++SI) {
1655 I = BBStates.find(Succ);
1656 assert(I != BBStates.end());
1657 MyStates.MergeSucc(I->second);
1661 // Visit all the instructions, bottom-up.
1662 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
1663 Instruction *Inst = llvm::prior(I);
1665 // Invoke instructions are visited as part of their successors (below).
1666 if (isa<InvokeInst>(Inst))
1669 DEBUG(dbgs() << "ObjCARCOpt::VisitButtonUp: Visiting " << *Inst << "\n");
1671 NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates);
1674 // If there's a predecessor with an invoke, visit the invoke as if it were
1675 // part of this block, since we can't insert code after an invoke in its own
1676 // block, and we don't want to split critical edges.
1677 for (BBState::edge_iterator PI(MyStates.pred_begin()),
1678 PE(MyStates.pred_end()); PI != PE; ++PI) {
1679 BasicBlock *Pred = *PI;
1680 if (InvokeInst *II = dyn_cast<InvokeInst>(&Pred->back()))
1681 NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates);
1684 return NestingDetected;
1688 ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst,
1689 DenseMap<Value *, RRInfo> &Releases,
1690 BBState &MyStates) {
1691 bool NestingDetected = false;
1692 InstructionClass Class = GetInstructionClass(Inst);
1693 const Value *Arg = 0;
1696 case IC_RetainBlock:
1697 // An objc_retainBlock call with just a use may need to be kept,
1698 // because it may be copying a block from the stack to the heap.
1699 if (!IsRetainBlockOptimizable(Inst))
1704 Arg = GetObjCArg(Inst);
1706 PtrState &S = MyStates.getPtrTopDownState(Arg);
1708 // Don't do retain+release tracking for IC_RetainRV, because it's
1709 // better to let it remain as the first instruction after a call.
1710 if (Class != IC_RetainRV) {
1711 // If we see two retains in a row on the same pointer. If so, make
1712 // a note, and we'll cicle back to revisit it after we've
1713 // hopefully eliminated the second retain, which may allow us to
1714 // eliminate the first retain too.
1715 // Theoretically we could implement removal of nested retain+release
1716 // pairs by making PtrState hold a stack of states, but this is
1717 // simple and avoids adding overhead for the non-nested case.
1718 if (S.GetSeq() == S_Retain)
1719 NestingDetected = true;
1721 S.ResetSequenceProgress(S_Retain);
1722 S.RRI.IsRetainBlock = Class == IC_RetainBlock;
1723 S.RRI.KnownSafe = S.IsKnownIncremented();
1724 S.RRI.Calls.insert(Inst);
1727 S.SetKnownPositiveRefCount();
1729 // A retain can be a potential use; procede to the generic checking
1734 Arg = GetObjCArg(Inst);
1736 PtrState &S = MyStates.getPtrTopDownState(Arg);
1739 switch (S.GetSeq()) {
1742 S.RRI.ReverseInsertPts.clear();
1745 S.RRI.ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind);
1746 S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
1747 Releases[Inst] = S.RRI;
1748 S.ClearSequenceProgress();
1754 case S_MovableRelease:
1755 llvm_unreachable("top-down pointer in release state!");
1759 case IC_AutoreleasepoolPop:
1760 // Conservatively, clear MyStates for all known pointers.
1761 MyStates.clearTopDownPointers();
1762 return NestingDetected;
1763 case IC_AutoreleasepoolPush:
1765 // These are irrelevant.
1766 return NestingDetected;
1771 // Consider any other possible effects of this instruction on each
1772 // pointer being tracked.
1773 for (BBState::ptr_iterator MI = MyStates.top_down_ptr_begin(),
1774 ME = MyStates.top_down_ptr_end(); MI != ME; ++MI) {
1775 const Value *Ptr = MI->first;
1777 continue; // Handled above.
1778 PtrState &S = MI->second;
1779 Sequence Seq = S.GetSeq();
1781 // Check for possible releases.
1782 if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
1786 S.SetSeq(S_CanRelease);
1787 assert(S.RRI.ReverseInsertPts.empty());
1788 S.RRI.ReverseInsertPts.insert(Inst);
1790 // One call can't cause a transition from S_Retain to S_CanRelease
1791 // and S_CanRelease to S_Use. If we've made the first transition,
1800 case S_MovableRelease:
1801 llvm_unreachable("top-down pointer in release state!");
1805 // Check for possible direct uses.
1808 if (CanUse(Inst, Ptr, PA, Class))
1817 case S_MovableRelease:
1818 llvm_unreachable("top-down pointer in release state!");
1822 return NestingDetected;
1826 ObjCARCOpt::VisitTopDown(BasicBlock *BB,
1827 DenseMap<const BasicBlock *, BBState> &BBStates,
1828 DenseMap<Value *, RRInfo> &Releases) {
1829 bool NestingDetected = false;
1830 BBState &MyStates = BBStates[BB];
1832 // Merge the states from each predecessor to compute the initial state
1833 // for the current block.
1834 BBState::edge_iterator PI(MyStates.pred_begin()),
1835 PE(MyStates.pred_end());
1837 const BasicBlock *Pred = *PI;
1838 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred);
1839 assert(I != BBStates.end());
1840 MyStates.InitFromPred(I->second);
1842 for (; PI != PE; ++PI) {
1844 I = BBStates.find(Pred);
1845 assert(I != BBStates.end());
1846 MyStates.MergePred(I->second);
1850 // Visit all the instructions, top-down.
1851 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
1852 Instruction *Inst = I;
1854 DEBUG(dbgs() << "ObjCARCOpt::VisitTopDown: Visiting " << *Inst << "\n");
1856 NestingDetected |= VisitInstructionTopDown(Inst, Releases, MyStates);
1859 CheckForCFGHazards(BB, BBStates, MyStates);
1860 return NestingDetected;
1864 ComputePostOrders(Function &F,
1865 SmallVectorImpl<BasicBlock *> &PostOrder,
1866 SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder,
1867 unsigned NoObjCARCExceptionsMDKind,
1868 DenseMap<const BasicBlock *, BBState> &BBStates) {
1869 /// The visited set, for doing DFS walks.
1870 SmallPtrSet<BasicBlock *, 16> Visited;
1872 // Do DFS, computing the PostOrder.
1873 SmallPtrSet<BasicBlock *, 16> OnStack;
1874 SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack;
1876 // Functions always have exactly one entry block, and we don't have
1877 // any other block that we treat like an entry block.
1878 BasicBlock *EntryBB = &F.getEntryBlock();
1879 BBState &MyStates = BBStates[EntryBB];
1880 MyStates.SetAsEntry();
1881 TerminatorInst *EntryTI = cast<TerminatorInst>(&EntryBB->back());
1882 SuccStack.push_back(std::make_pair(EntryBB, succ_iterator(EntryTI)));
1883 Visited.insert(EntryBB);
1884 OnStack.insert(EntryBB);
1887 BasicBlock *CurrBB = SuccStack.back().first;
1888 TerminatorInst *TI = cast<TerminatorInst>(&CurrBB->back());
1889 succ_iterator SE(TI, false);
1891 while (SuccStack.back().second != SE) {
1892 BasicBlock *SuccBB = *SuccStack.back().second++;
1893 if (Visited.insert(SuccBB)) {
1894 TerminatorInst *TI = cast<TerminatorInst>(&SuccBB->back());
1895 SuccStack.push_back(std::make_pair(SuccBB, succ_iterator(TI)));
1896 BBStates[CurrBB].addSucc(SuccBB);
1897 BBState &SuccStates = BBStates[SuccBB];
1898 SuccStates.addPred(CurrBB);
1899 OnStack.insert(SuccBB);
1903 if (!OnStack.count(SuccBB)) {
1904 BBStates[CurrBB].addSucc(SuccBB);
1905 BBStates[SuccBB].addPred(CurrBB);
1908 OnStack.erase(CurrBB);
1909 PostOrder.push_back(CurrBB);
1910 SuccStack.pop_back();
1911 } while (!SuccStack.empty());
1915 // Do reverse-CFG DFS, computing the reverse-CFG PostOrder.
1916 // Functions may have many exits, and there also blocks which we treat
1917 // as exits due to ignored edges.
1918 SmallVector<std::pair<BasicBlock *, BBState::edge_iterator>, 16> PredStack;
1919 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
1920 BasicBlock *ExitBB = I;
1921 BBState &MyStates = BBStates[ExitBB];
1922 if (!MyStates.isExit())
1925 MyStates.SetAsExit();
1927 PredStack.push_back(std::make_pair(ExitBB, MyStates.pred_begin()));
1928 Visited.insert(ExitBB);
1929 while (!PredStack.empty()) {
1930 reverse_dfs_next_succ:
1931 BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end();
1932 while (PredStack.back().second != PE) {
1933 BasicBlock *BB = *PredStack.back().second++;
1934 if (Visited.insert(BB)) {
1935 PredStack.push_back(std::make_pair(BB, BBStates[BB].pred_begin()));
1936 goto reverse_dfs_next_succ;
1939 ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first);
1944 // Visit the function both top-down and bottom-up.
1946 ObjCARCOpt::Visit(Function &F,
1947 DenseMap<const BasicBlock *, BBState> &BBStates,
1948 MapVector<Value *, RRInfo> &Retains,
1949 DenseMap<Value *, RRInfo> &Releases) {
1951 // Use reverse-postorder traversals, because we magically know that loops
1952 // will be well behaved, i.e. they won't repeatedly call retain on a single
1953 // pointer without doing a release. We can't use the ReversePostOrderTraversal
1954 // class here because we want the reverse-CFG postorder to consider each
1955 // function exit point, and we want to ignore selected cycle edges.
1956 SmallVector<BasicBlock *, 16> PostOrder;
1957 SmallVector<BasicBlock *, 16> ReverseCFGPostOrder;
1958 ComputePostOrders(F, PostOrder, ReverseCFGPostOrder,
1959 NoObjCARCExceptionsMDKind,
1962 // Use reverse-postorder on the reverse CFG for bottom-up.
1963 bool BottomUpNestingDetected = false;
1964 for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
1965 ReverseCFGPostOrder.rbegin(), E = ReverseCFGPostOrder.rend();
1967 BottomUpNestingDetected |= VisitBottomUp(*I, BBStates, Retains);
1969 // Use reverse-postorder for top-down.
1970 bool TopDownNestingDetected = false;
1971 for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
1972 PostOrder.rbegin(), E = PostOrder.rend();
1974 TopDownNestingDetected |= VisitTopDown(*I, BBStates, Releases);
1976 return TopDownNestingDetected && BottomUpNestingDetected;
1979 /// Move the calls in RetainsToMove and ReleasesToMove.
1980 void ObjCARCOpt::MoveCalls(Value *Arg,
1981 RRInfo &RetainsToMove,
1982 RRInfo &ReleasesToMove,
1983 MapVector<Value *, RRInfo> &Retains,
1984 DenseMap<Value *, RRInfo> &Releases,
1985 SmallVectorImpl<Instruction *> &DeadInsts,
1987 Type *ArgTy = Arg->getType();
1988 Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext()));
1990 // Insert the new retain and release calls.
1991 for (SmallPtrSet<Instruction *, 2>::const_iterator
1992 PI = ReleasesToMove.ReverseInsertPts.begin(),
1993 PE = ReleasesToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
1994 Instruction *InsertPt = *PI;
1995 Value *MyArg = ArgTy == ParamTy ? Arg :
1996 new BitCastInst(Arg, ParamTy, "", InsertPt);
1998 CallInst::Create(RetainsToMove.IsRetainBlock ?
1999 getRetainBlockCallee(M) : getRetainCallee(M),
2000 MyArg, "", InsertPt);
2001 Call->setDoesNotThrow();
2002 if (RetainsToMove.IsRetainBlock)
2003 Call->setMetadata(CopyOnEscapeMDKind,
2004 MDNode::get(M->getContext(), ArrayRef<Value *>()));
2006 Call->setTailCall();
2008 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Inserting new Release: " << *Call
2010 " At insertion point: " << *InsertPt
2013 for (SmallPtrSet<Instruction *, 2>::const_iterator
2014 PI = RetainsToMove.ReverseInsertPts.begin(),
2015 PE = RetainsToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
2016 Instruction *InsertPt = *PI;
2017 Value *MyArg = ArgTy == ParamTy ? Arg :
2018 new BitCastInst(Arg, ParamTy, "", InsertPt);
2019 CallInst *Call = CallInst::Create(getReleaseCallee(M), MyArg,
2021 // Attach a clang.imprecise_release metadata tag, if appropriate.
2022 if (MDNode *M = ReleasesToMove.ReleaseMetadata)
2023 Call->setMetadata(ImpreciseReleaseMDKind, M);
2024 Call->setDoesNotThrow();
2025 if (ReleasesToMove.IsTailCallRelease)
2026 Call->setTailCall();
2028 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Inserting new Retain: " << *Call
2030 " At insertion point: " << *InsertPt
2034 // Delete the original retain and release calls.
2035 for (SmallPtrSet<Instruction *, 2>::const_iterator
2036 AI = RetainsToMove.Calls.begin(),
2037 AE = RetainsToMove.Calls.end(); AI != AE; ++AI) {
2038 Instruction *OrigRetain = *AI;
2039 Retains.blot(OrigRetain);
2040 DeadInsts.push_back(OrigRetain);
2041 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Deleting retain: " << *OrigRetain <<
2044 for (SmallPtrSet<Instruction *, 2>::const_iterator
2045 AI = ReleasesToMove.Calls.begin(),
2046 AE = ReleasesToMove.Calls.end(); AI != AE; ++AI) {
2047 Instruction *OrigRelease = *AI;
2048 Releases.erase(OrigRelease);
2049 DeadInsts.push_back(OrigRelease);
2050 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Deleting release: " << *OrigRelease
2056 ObjCARCOpt::ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState>
2058 MapVector<Value *, RRInfo> &Retains,
2059 DenseMap<Value *, RRInfo> &Releases,
2061 SmallVector<Instruction *, 4> &NewRetains,
2062 SmallVector<Instruction *, 4> &NewReleases,
2063 SmallVector<Instruction *, 8> &DeadInsts,
2064 RRInfo &RetainsToMove,
2065 RRInfo &ReleasesToMove,
2068 bool &AnyPairsCompletelyEliminated) {
2069 // If a pair happens in a region where it is known that the reference count
2070 // is already incremented, we can similarly ignore possible decrements.
2071 bool KnownSafeTD = true, KnownSafeBU = true;
2073 // Connect the dots between the top-down-collected RetainsToMove and
2074 // bottom-up-collected ReleasesToMove to form sets of related calls.
2075 // This is an iterative process so that we connect multiple releases
2076 // to multiple retains if needed.
2077 unsigned OldDelta = 0;
2078 unsigned NewDelta = 0;
2079 unsigned OldCount = 0;
2080 unsigned NewCount = 0;
2081 bool FirstRelease = true;
2082 bool FirstRetain = true;
2084 for (SmallVectorImpl<Instruction *>::const_iterator
2085 NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) {
2086 Instruction *NewRetain = *NI;
2087 MapVector<Value *, RRInfo>::const_iterator It = Retains.find(NewRetain);
2088 assert(It != Retains.end());
2089 const RRInfo &NewRetainRRI = It->second;
2090 KnownSafeTD &= NewRetainRRI.KnownSafe;
2091 for (SmallPtrSet<Instruction *, 2>::const_iterator
2092 LI = NewRetainRRI.Calls.begin(),
2093 LE = NewRetainRRI.Calls.end(); LI != LE; ++LI) {
2094 Instruction *NewRetainRelease = *LI;
2095 DenseMap<Value *, RRInfo>::const_iterator Jt =
2096 Releases.find(NewRetainRelease);
2097 if (Jt == Releases.end())
2099 const RRInfo &NewRetainReleaseRRI = Jt->second;
2100 assert(NewRetainReleaseRRI.Calls.count(NewRetain));
2101 if (ReleasesToMove.Calls.insert(NewRetainRelease)) {
2103 BBStates[NewRetainRelease->getParent()].GetAllPathCount();
2105 // Merge the ReleaseMetadata and IsTailCallRelease values.
2107 ReleasesToMove.ReleaseMetadata =
2108 NewRetainReleaseRRI.ReleaseMetadata;
2109 ReleasesToMove.IsTailCallRelease =
2110 NewRetainReleaseRRI.IsTailCallRelease;
2111 FirstRelease = false;
2113 if (ReleasesToMove.ReleaseMetadata !=
2114 NewRetainReleaseRRI.ReleaseMetadata)
2115 ReleasesToMove.ReleaseMetadata = 0;
2116 if (ReleasesToMove.IsTailCallRelease !=
2117 NewRetainReleaseRRI.IsTailCallRelease)
2118 ReleasesToMove.IsTailCallRelease = false;
2121 // Collect the optimal insertion points.
2123 for (SmallPtrSet<Instruction *, 2>::const_iterator
2124 RI = NewRetainReleaseRRI.ReverseInsertPts.begin(),
2125 RE = NewRetainReleaseRRI.ReverseInsertPts.end();
2127 Instruction *RIP = *RI;
2128 if (ReleasesToMove.ReverseInsertPts.insert(RIP))
2129 NewDelta -= BBStates[RIP->getParent()].GetAllPathCount();
2131 NewReleases.push_back(NewRetainRelease);
2136 if (NewReleases.empty()) break;
2138 // Back the other way.
2139 for (SmallVectorImpl<Instruction *>::const_iterator
2140 NI = NewReleases.begin(), NE = NewReleases.end(); NI != NE; ++NI) {
2141 Instruction *NewRelease = *NI;
2142 DenseMap<Value *, RRInfo>::const_iterator It =
2143 Releases.find(NewRelease);
2144 assert(It != Releases.end());
2145 const RRInfo &NewReleaseRRI = It->second;
2146 KnownSafeBU &= NewReleaseRRI.KnownSafe;
2147 for (SmallPtrSet<Instruction *, 2>::const_iterator
2148 LI = NewReleaseRRI.Calls.begin(),
2149 LE = NewReleaseRRI.Calls.end(); LI != LE; ++LI) {
2150 Instruction *NewReleaseRetain = *LI;
2151 MapVector<Value *, RRInfo>::const_iterator Jt =
2152 Retains.find(NewReleaseRetain);
2153 if (Jt == Retains.end())
2155 const RRInfo &NewReleaseRetainRRI = Jt->second;
2156 assert(NewReleaseRetainRRI.Calls.count(NewRelease));
2157 if (RetainsToMove.Calls.insert(NewReleaseRetain)) {
2158 unsigned PathCount =
2159 BBStates[NewReleaseRetain->getParent()].GetAllPathCount();
2160 OldDelta += PathCount;
2161 OldCount += PathCount;
2163 // Merge the IsRetainBlock values.
2165 RetainsToMove.IsRetainBlock = NewReleaseRetainRRI.IsRetainBlock;
2166 FirstRetain = false;
2167 } else if (ReleasesToMove.IsRetainBlock !=
2168 NewReleaseRetainRRI.IsRetainBlock)
2169 // It's not possible to merge the sequences if one uses
2170 // objc_retain and the other uses objc_retainBlock.
2173 // Collect the optimal insertion points.
2175 for (SmallPtrSet<Instruction *, 2>::const_iterator
2176 RI = NewReleaseRetainRRI.ReverseInsertPts.begin(),
2177 RE = NewReleaseRetainRRI.ReverseInsertPts.end();
2179 Instruction *RIP = *RI;
2180 if (RetainsToMove.ReverseInsertPts.insert(RIP)) {
2181 PathCount = BBStates[RIP->getParent()].GetAllPathCount();
2182 NewDelta += PathCount;
2183 NewCount += PathCount;
2186 NewRetains.push_back(NewReleaseRetain);
2190 NewReleases.clear();
2191 if (NewRetains.empty()) break;
2194 // If the pointer is known incremented or nested, we can safely delete the
2195 // pair regardless of what's between them.
2196 if (KnownSafeTD || KnownSafeBU) {
2197 RetainsToMove.ReverseInsertPts.clear();
2198 ReleasesToMove.ReverseInsertPts.clear();
2201 // Determine whether the new insertion points we computed preserve the
2202 // balance of retain and release calls through the program.
2203 // TODO: If the fully aggressive solution isn't valid, try to find a
2204 // less aggressive solution which is.
2209 // Determine whether the original call points are balanced in the retain and
2210 // release calls through the program. If not, conservatively don't touch
2212 // TODO: It's theoretically possible to do code motion in this case, as
2213 // long as the existing imbalances are maintained.
2218 assert(OldCount != 0 && "Unreachable code?");
2219 NumRRs += OldCount - NewCount;
2220 // Set to true if we completely removed any RR pairs.
2221 AnyPairsCompletelyEliminated = NewCount == 0;
2223 // We can move calls!
2227 /// Identify pairings between the retains and releases, and delete and/or move
2230 ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState>
2232 MapVector<Value *, RRInfo> &Retains,
2233 DenseMap<Value *, RRInfo> &Releases,
2235 bool AnyPairsCompletelyEliminated = false;
2236 RRInfo RetainsToMove;
2237 RRInfo ReleasesToMove;
2238 SmallVector<Instruction *, 4> NewRetains;
2239 SmallVector<Instruction *, 4> NewReleases;
2240 SmallVector<Instruction *, 8> DeadInsts;
2242 // Visit each retain.
2243 for (MapVector<Value *, RRInfo>::const_iterator I = Retains.begin(),
2244 E = Retains.end(); I != E; ++I) {
2245 Value *V = I->first;
2246 if (!V) continue; // blotted
2248 Instruction *Retain = cast<Instruction>(V);
2250 DEBUG(dbgs() << "ObjCARCOpt::PerformCodePlacement: Visiting: " << *Retain
2253 Value *Arg = GetObjCArg(Retain);
2255 // If the object being released is in static or stack storage, we know it's
2256 // not being managed by ObjC reference counting, so we can delete pairs
2257 // regardless of what possible decrements or uses lie between them.
2258 bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg);
2260 // A constant pointer can't be pointing to an object on the heap. It may
2261 // be reference-counted, but it won't be deleted.
2262 if (const LoadInst *LI = dyn_cast<LoadInst>(Arg))
2263 if (const GlobalVariable *GV =
2264 dyn_cast<GlobalVariable>(
2265 StripPointerCastsAndObjCCalls(LI->getPointerOperand())))
2266 if (GV->isConstant())
2269 // Connect the dots between the top-down-collected RetainsToMove and
2270 // bottom-up-collected ReleasesToMove to form sets of related calls.
2271 NewRetains.push_back(Retain);
2272 bool PerformMoveCalls =
2273 ConnectTDBUTraversals(BBStates, Retains, Releases, M, NewRetains,
2274 NewReleases, DeadInsts, RetainsToMove,
2275 ReleasesToMove, Arg, KnownSafe,
2276 AnyPairsCompletelyEliminated);
2278 if (PerformMoveCalls) {
2279 // Ok, everything checks out and we're all set. Let's move/delete some
2281 MoveCalls(Arg, RetainsToMove, ReleasesToMove,
2282 Retains, Releases, DeadInsts, M);
2285 // Clean up state for next retain.
2286 NewReleases.clear();
2288 RetainsToMove.clear();
2289 ReleasesToMove.clear();
2292 // Now that we're done moving everything, we can delete the newly dead
2293 // instructions, as we no longer need them as insert points.
2294 while (!DeadInsts.empty())
2295 EraseInstruction(DeadInsts.pop_back_val());
2297 return AnyPairsCompletelyEliminated;
2300 /// Weak pointer optimizations.
2301 void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
2302 // First, do memdep-style RLE and S2L optimizations. We can't use memdep
2303 // itself because it uses AliasAnalysis and we need to do provenance
2305 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2306 Instruction *Inst = &*I++;
2308 DEBUG(dbgs() << "ObjCARCOpt::OptimizeWeakCalls: Visiting: " << *Inst <<
2311 InstructionClass Class = GetBasicInstructionClass(Inst);
2312 if (Class != IC_LoadWeak && Class != IC_LoadWeakRetained)
2315 // Delete objc_loadWeak calls with no users.
2316 if (Class == IC_LoadWeak && Inst->use_empty()) {
2317 Inst->eraseFromParent();
2321 // TODO: For now, just look for an earlier available version of this value
2322 // within the same block. Theoretically, we could do memdep-style non-local
2323 // analysis too, but that would want caching. A better approach would be to
2324 // use the technique that EarlyCSE uses.
2325 inst_iterator Current = llvm::prior(I);
2326 BasicBlock *CurrentBB = Current.getBasicBlockIterator();
2327 for (BasicBlock::iterator B = CurrentBB->begin(),
2328 J = Current.getInstructionIterator();
2330 Instruction *EarlierInst = &*llvm::prior(J);
2331 InstructionClass EarlierClass = GetInstructionClass(EarlierInst);
2332 switch (EarlierClass) {
2334 case IC_LoadWeakRetained: {
2335 // If this is loading from the same pointer, replace this load's value
2337 CallInst *Call = cast<CallInst>(Inst);
2338 CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2339 Value *Arg = Call->getArgOperand(0);
2340 Value *EarlierArg = EarlierCall->getArgOperand(0);
2341 switch (PA.getAA()->alias(Arg, EarlierArg)) {
2342 case AliasAnalysis::MustAlias:
2344 // If the load has a builtin retain, insert a plain retain for it.
2345 if (Class == IC_LoadWeakRetained) {
2347 CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
2351 // Zap the fully redundant load.
2352 Call->replaceAllUsesWith(EarlierCall);
2353 Call->eraseFromParent();
2355 case AliasAnalysis::MayAlias:
2356 case AliasAnalysis::PartialAlias:
2358 case AliasAnalysis::NoAlias:
2365 // If this is storing to the same pointer and has the same size etc.
2366 // replace this load's value with the stored value.
2367 CallInst *Call = cast<CallInst>(Inst);
2368 CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2369 Value *Arg = Call->getArgOperand(0);
2370 Value *EarlierArg = EarlierCall->getArgOperand(0);
2371 switch (PA.getAA()->alias(Arg, EarlierArg)) {
2372 case AliasAnalysis::MustAlias:
2374 // If the load has a builtin retain, insert a plain retain for it.
2375 if (Class == IC_LoadWeakRetained) {
2377 CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
2381 // Zap the fully redundant load.
2382 Call->replaceAllUsesWith(EarlierCall->getArgOperand(1));
2383 Call->eraseFromParent();
2385 case AliasAnalysis::MayAlias:
2386 case AliasAnalysis::PartialAlias:
2388 case AliasAnalysis::NoAlias:
2395 // TOOD: Grab the copied value.
2397 case IC_AutoreleasepoolPush:
2400 // Weak pointers are only modified through the weak entry points
2401 // (and arbitrary calls, which could call the weak entry points).
2404 // Anything else could modify the weak pointer.
2411 // Then, for each destroyWeak with an alloca operand, check to see if
2412 // the alloca and all its users can be zapped.
2413 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2414 Instruction *Inst = &*I++;
2415 InstructionClass Class = GetBasicInstructionClass(Inst);
2416 if (Class != IC_DestroyWeak)
2419 CallInst *Call = cast<CallInst>(Inst);
2420 Value *Arg = Call->getArgOperand(0);
2421 if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) {
2422 for (Value::use_iterator UI = Alloca->use_begin(),
2423 UE = Alloca->use_end(); UI != UE; ++UI) {
2424 const Instruction *UserInst = cast<Instruction>(*UI);
2425 switch (GetBasicInstructionClass(UserInst)) {
2428 case IC_DestroyWeak:
2435 for (Value::use_iterator UI = Alloca->use_begin(),
2436 UE = Alloca->use_end(); UI != UE; ) {
2437 CallInst *UserInst = cast<CallInst>(*UI++);
2438 switch (GetBasicInstructionClass(UserInst)) {
2441 // These functions return their second argument.
2442 UserInst->replaceAllUsesWith(UserInst->getArgOperand(1));
2444 case IC_DestroyWeak:
2448 llvm_unreachable("alloca really is used!");
2450 UserInst->eraseFromParent();
2452 Alloca->eraseFromParent();
2457 DEBUG(dbgs() << "ObjCARCOpt::OptimizeWeakCalls: Finished List.\n\n");
2461 /// Identify program paths which execute sequences of retains and releases which
2462 /// can be eliminated.
2463 bool ObjCARCOpt::OptimizeSequences(Function &F) {
2464 /// Releases, Retains - These are used to store the results of the main flow
2465 /// analysis. These use Value* as the key instead of Instruction* so that the
2466 /// map stays valid when we get around to rewriting code and calls get
2467 /// replaced by arguments.
2468 DenseMap<Value *, RRInfo> Releases;
2469 MapVector<Value *, RRInfo> Retains;
2471 /// This is used during the traversal of the function to track the
2472 /// states for each identified object at each block.
2473 DenseMap<const BasicBlock *, BBState> BBStates;
2475 // Analyze the CFG of the function, and all instructions.
2476 bool NestingDetected = Visit(F, BBStates, Retains, Releases);
2479 return PerformCodePlacement(BBStates, Retains, Releases, F.getParent()) &&
2483 /// Look for this pattern:
2485 /// %call = call i8* @something(...)
2486 /// %2 = call i8* @objc_retain(i8* %call)
2487 /// %3 = call i8* @objc_autorelease(i8* %2)
2490 /// And delete the retain and autorelease.
2492 /// Otherwise if it's just this:
2494 /// %3 = call i8* @objc_autorelease(i8* %2)
2497 /// convert the autorelease to autoreleaseRV.
2498 void ObjCARCOpt::OptimizeReturns(Function &F) {
2499 if (!F.getReturnType()->isPointerTy())
2502 SmallPtrSet<Instruction *, 4> DependingInstructions;
2503 SmallPtrSet<const BasicBlock *, 4> Visited;
2504 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
2505 BasicBlock *BB = FI;
2506 ReturnInst *Ret = dyn_cast<ReturnInst>(&BB->back());
2508 DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Visiting: " << *Ret << "\n");
2512 const Value *Arg = StripPointerCastsAndObjCCalls(Ret->getOperand(0));
2513 FindDependencies(NeedsPositiveRetainCount, Arg,
2514 BB, Ret, DependingInstructions, Visited, PA);
2515 if (DependingInstructions.size() != 1)
2519 CallInst *Autorelease =
2520 dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
2523 InstructionClass AutoreleaseClass = GetBasicInstructionClass(Autorelease);
2524 if (!IsAutorelease(AutoreleaseClass))
2526 if (GetObjCArg(Autorelease) != Arg)
2529 DependingInstructions.clear();
2532 // Check that there is nothing that can affect the reference
2533 // count between the autorelease and the retain.
2534 FindDependencies(CanChangeRetainCount, Arg,
2535 BB, Autorelease, DependingInstructions, Visited, PA);
2536 if (DependingInstructions.size() != 1)
2541 dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
2543 // Check that we found a retain with the same argument.
2545 !IsRetain(GetBasicInstructionClass(Retain)) ||
2546 GetObjCArg(Retain) != Arg)
2549 DependingInstructions.clear();
2552 // Convert the autorelease to an autoreleaseRV, since it's
2553 // returning the value.
2554 if (AutoreleaseClass == IC_Autorelease) {
2555 DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Converting autorelease "
2556 "=> autoreleaseRV since it's returning a value.\n"
2557 " In: " << *Autorelease
2559 Autorelease->setCalledFunction(getAutoreleaseRVCallee(F.getParent()));
2560 DEBUG(dbgs() << " Out: " << *Autorelease
2562 Autorelease->setTailCall(); // Always tail call autoreleaseRV.
2563 AutoreleaseClass = IC_AutoreleaseRV;
2566 // Check that there is nothing that can affect the reference
2567 // count between the retain and the call.
2568 // Note that Retain need not be in BB.
2569 FindDependencies(CanChangeRetainCount, Arg, Retain->getParent(), Retain,
2570 DependingInstructions, Visited, PA);
2571 if (DependingInstructions.size() != 1)
2576 dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
2578 // Check that the pointer is the return value of the call.
2579 if (!Call || Arg != Call)
2582 // Check that the call is a regular call.
2583 InstructionClass Class = GetBasicInstructionClass(Call);
2584 if (Class != IC_CallOrUser && Class != IC_Call)
2587 // If so, we can zap the retain and autorelease.
2590 DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Erasing: " << *Retain
2592 << *Autorelease << "\n");
2593 EraseInstruction(Retain);
2594 EraseInstruction(Autorelease);
2600 DependingInstructions.clear();
2604 DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Finished List.\n\n");
2608 bool ObjCARCOpt::doInitialization(Module &M) {
2612 // If nothing in the Module uses ARC, don't do anything.
2613 Run = ModuleHasARC(M);
2617 // Identify the imprecise release metadata kind.
2618 ImpreciseReleaseMDKind =
2619 M.getContext().getMDKindID("clang.imprecise_release");
2620 CopyOnEscapeMDKind =
2621 M.getContext().getMDKindID("clang.arc.copy_on_escape");
2622 NoObjCARCExceptionsMDKind =
2623 M.getContext().getMDKindID("clang.arc.no_objc_arc_exceptions");
2625 // Intuitively, objc_retain and others are nocapture, however in practice
2626 // they are not, because they return their argument value. And objc_release
2627 // calls finalizers which can have arbitrary side effects.
2629 // These are initialized lazily.
2631 AutoreleaseRVCallee = 0;
2634 RetainBlockCallee = 0;
2635 AutoreleaseCallee = 0;
2640 bool ObjCARCOpt::runOnFunction(Function &F) {
2644 // If nothing in the Module uses ARC, don't do anything.
2650 DEBUG(dbgs() << "ObjCARCOpt: Visiting Function: " << F.getName() << "\n");
2652 PA.setAA(&getAnalysis<AliasAnalysis>());
2654 // This pass performs several distinct transformations. As a compile-time aid
2655 // when compiling code that isn't ObjC, skip these if the relevant ObjC
2656 // library functions aren't declared.
2658 // Preliminary optimizations. This also computs UsedInThisFunction.
2659 OptimizeIndividualCalls(F);
2661 // Optimizations for weak pointers.
2662 if (UsedInThisFunction & ((1 << IC_LoadWeak) |
2663 (1 << IC_LoadWeakRetained) |
2664 (1 << IC_StoreWeak) |
2665 (1 << IC_InitWeak) |
2666 (1 << IC_CopyWeak) |
2667 (1 << IC_MoveWeak) |
2668 (1 << IC_DestroyWeak)))
2669 OptimizeWeakCalls(F);
2671 // Optimizations for retain+release pairs.
2672 if (UsedInThisFunction & ((1 << IC_Retain) |
2673 (1 << IC_RetainRV) |
2674 (1 << IC_RetainBlock)))
2675 if (UsedInThisFunction & (1 << IC_Release))
2676 // Run OptimizeSequences until it either stops making changes or
2677 // no retain+release pair nesting is detected.
2678 while (OptimizeSequences(F)) {}
2680 // Optimizations if objc_autorelease is used.
2681 if (UsedInThisFunction & ((1 << IC_Autorelease) |
2682 (1 << IC_AutoreleaseRV)))
2685 DEBUG(dbgs() << "\n");
2690 void ObjCARCOpt::releaseMemory() {