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, and numerous minor simplifications.
18 /// WARNING: This file knows about certain library functions. It recognizes them
19 /// by name, and hardwires knowledge of their semantics.
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.
25 //===----------------------------------------------------------------------===//
27 #define DEBUG_TYPE "objc-arc-opts"
29 #include "DependencyAnalysis.h"
30 #include "ObjCARCAliasAnalysis.h"
31 #include "ProvenanceAnalysis.h"
32 #include "llvm/ADT/DenseMap.h"
33 #include "llvm/ADT/STLExtras.h"
34 #include "llvm/ADT/SmallPtrSet.h"
35 #include "llvm/ADT/Statistic.h"
36 #include "llvm/IR/LLVMContext.h"
37 #include "llvm/Support/CFG.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/raw_ostream.h"
42 using namespace llvm::objcarc;
44 /// \defgroup MiscUtils Miscellaneous utilities that are not ARC specific.
48 /// \brief An associative container with fast insertion-order (deterministic)
49 /// iteration over its elements. Plus the special blot operation.
50 template<class KeyT, class ValueT>
52 /// Map keys to indices in Vector.
53 typedef DenseMap<KeyT, size_t> MapTy;
56 typedef std::vector<std::pair<KeyT, ValueT> > VectorTy;
61 typedef typename VectorTy::iterator iterator;
62 typedef typename VectorTy::const_iterator const_iterator;
63 iterator begin() { return Vector.begin(); }
64 iterator end() { return Vector.end(); }
65 const_iterator begin() const { return Vector.begin(); }
66 const_iterator end() const { return Vector.end(); }
70 assert(Vector.size() >= Map.size()); // May differ due to blotting.
71 for (typename MapTy::const_iterator I = Map.begin(), E = Map.end();
73 assert(I->second < Vector.size());
74 assert(Vector[I->second].first == I->first);
76 for (typename VectorTy::const_iterator I = Vector.begin(),
77 E = Vector.end(); I != E; ++I)
79 (Map.count(I->first) &&
80 Map[I->first] == size_t(I - Vector.begin())));
84 ValueT &operator[](const KeyT &Arg) {
85 std::pair<typename MapTy::iterator, bool> Pair =
86 Map.insert(std::make_pair(Arg, size_t(0)));
88 size_t Num = Vector.size();
89 Pair.first->second = Num;
90 Vector.push_back(std::make_pair(Arg, ValueT()));
91 return Vector[Num].second;
93 return Vector[Pair.first->second].second;
96 std::pair<iterator, bool>
97 insert(const std::pair<KeyT, ValueT> &InsertPair) {
98 std::pair<typename MapTy::iterator, bool> Pair =
99 Map.insert(std::make_pair(InsertPair.first, size_t(0)));
101 size_t Num = Vector.size();
102 Pair.first->second = Num;
103 Vector.push_back(InsertPair);
104 return std::make_pair(Vector.begin() + Num, true);
106 return std::make_pair(Vector.begin() + Pair.first->second, false);
109 const_iterator find(const KeyT &Key) const {
110 typename MapTy::const_iterator It = Map.find(Key);
111 if (It == Map.end()) return Vector.end();
112 return Vector.begin() + It->second;
115 /// This is similar to erase, but instead of removing the element from the
116 /// vector, it just zeros out the key in the vector. This leaves iterators
117 /// intact, but clients must be prepared for zeroed-out keys when iterating.
118 void blot(const KeyT &Key) {
119 typename MapTy::iterator It = Map.find(Key);
120 if (It == Map.end()) return;
121 Vector[It->second].first = KeyT();
134 /// \defgroup ARCUtilities Utility declarations/definitions specific to ARC.
137 /// \brief This is similar to StripPointerCastsAndObjCCalls but it stops as soon
138 /// as it finds a value with multiple uses.
139 static const Value *FindSingleUseIdentifiedObject(const Value *Arg) {
140 if (Arg->hasOneUse()) {
141 if (const BitCastInst *BC = dyn_cast<BitCastInst>(Arg))
142 return FindSingleUseIdentifiedObject(BC->getOperand(0));
143 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Arg))
144 if (GEP->hasAllZeroIndices())
145 return FindSingleUseIdentifiedObject(GEP->getPointerOperand());
146 if (IsForwarding(GetBasicInstructionClass(Arg)))
147 return FindSingleUseIdentifiedObject(
148 cast<CallInst>(Arg)->getArgOperand(0));
149 if (!IsObjCIdentifiedObject(Arg))
154 // If we found an identifiable object but it has multiple uses, but they are
155 // trivial uses, we can still consider this to be a single-use value.
156 if (IsObjCIdentifiedObject(Arg)) {
157 for (Value::const_use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
160 if (!U->use_empty() || StripPointerCastsAndObjCCalls(U) != Arg)
170 /// \brief Test whether the given retainable object pointer escapes.
172 /// This differs from regular escape analysis in that a use as an
173 /// argument to a call is not considered an escape.
175 static bool DoesRetainableObjPtrEscape(const User *Ptr) {
176 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Target: " << *Ptr << "\n");
178 // Walk the def-use chains.
179 SmallVector<const Value *, 4> Worklist;
180 Worklist.push_back(Ptr);
181 // If Ptr has any operands add them as well.
182 for (User::const_op_iterator I = Ptr->op_begin(), E = Ptr->op_end(); I != E;
184 Worklist.push_back(*I);
187 // Ensure we do not visit any value twice.
188 SmallPtrSet<const Value *, 8> VisitedSet;
191 const Value *V = Worklist.pop_back_val();
193 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Visiting: " << *V << "\n");
195 for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end();
197 const User *UUser = *UI;
199 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: User: " << *UUser << "\n");
201 // Special - Use by a call (callee or argument) is not considered
203 switch (GetBasicInstructionClass(UUser)) {
208 case IC_AutoreleaseRV: {
209 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: User copies pointer "
210 "arguments. Pointer Escapes!\n");
211 // These special functions make copies of their pointer arguments.
216 // Use by an instruction which copies the value is an escape if the
217 // result is an escape.
218 if (isa<BitCastInst>(UUser) || isa<GetElementPtrInst>(UUser) ||
219 isa<PHINode>(UUser) || isa<SelectInst>(UUser)) {
221 if (!VisitedSet.insert(UUser)) {
222 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: User copies value. "
223 "Ptr escapes if result escapes. Adding to list.\n");
224 Worklist.push_back(UUser);
226 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Already visited node."
231 // Use by a load is not an escape.
232 if (isa<LoadInst>(UUser))
234 // Use by a store is not an escape if the use is the address.
235 if (const StoreInst *SI = dyn_cast<StoreInst>(UUser))
236 if (V != SI->getValueOperand())
240 // Regular calls and other stuff are not considered escapes.
243 // Otherwise, conservatively assume an escape.
244 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Assuming ptr escapes.\n");
247 } while (!Worklist.empty());
250 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Ptr does not escape.\n");
256 /// \defgroup ARCOpt ARC Optimization.
259 // TODO: On code like this:
262 // stuff_that_cannot_release()
263 // objc_autorelease(%x)
264 // stuff_that_cannot_release()
266 // stuff_that_cannot_release()
267 // objc_autorelease(%x)
269 // The second retain and autorelease can be deleted.
271 // TODO: It should be possible to delete
272 // objc_autoreleasePoolPush and objc_autoreleasePoolPop
273 // pairs if nothing is actually autoreleased between them. Also, autorelease
274 // calls followed by objc_autoreleasePoolPop calls (perhaps in ObjC++ code
275 // after inlining) can be turned into plain release calls.
277 // TODO: Critical-edge splitting. If the optimial insertion point is
278 // a critical edge, the current algorithm has to fail, because it doesn't
279 // know how to split edges. It should be possible to make the optimizer
280 // think in terms of edges, rather than blocks, and then split critical
283 // TODO: OptimizeSequences could generalized to be Interprocedural.
285 // TODO: Recognize that a bunch of other objc runtime calls have
286 // non-escaping arguments and non-releasing arguments, and may be
287 // non-autoreleasing.
289 // TODO: Sink autorelease calls as far as possible. Unfortunately we
290 // usually can't sink them past other calls, which would be the main
291 // case where it would be useful.
293 // TODO: The pointer returned from objc_loadWeakRetained is retained.
295 // TODO: Delete release+retain pairs (rare).
297 STATISTIC(NumNoops, "Number of no-op objc calls eliminated");
298 STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated");
299 STATISTIC(NumAutoreleases,"Number of autoreleases converted to releases");
300 STATISTIC(NumRets, "Number of return value forwarding "
301 "retain+autoreleaes eliminated");
302 STATISTIC(NumRRs, "Number of retain+release paths eliminated");
303 STATISTIC(NumPeeps, "Number of calls peephole-optimized");
308 /// \brief A sequence of states that a pointer may go through in which an
309 /// objc_retain and objc_release are actually needed.
312 S_Retain, ///< objc_retain(x).
313 S_CanRelease, ///< foo(x) -- x could possibly see a ref count decrement.
314 S_Use, ///< any use of x.
315 S_Stop, ///< like S_Release, but code motion is stopped.
316 S_Release, ///< objc_release(x).
317 S_MovableRelease ///< objc_release(x), !clang.imprecise_release.
320 raw_ostream &operator<<(raw_ostream &OS, const Sequence S)
321 LLVM_ATTRIBUTE_UNUSED;
322 raw_ostream &operator<<(raw_ostream &OS, const Sequence S) {
325 return OS << "S_None";
327 return OS << "S_Retain";
329 return OS << "S_CanRelease";
331 return OS << "S_Use";
333 return OS << "S_Release";
334 case S_MovableRelease:
335 return OS << "S_MovableRelease";
337 return OS << "S_Stop";
339 llvm_unreachable("Unknown sequence type.");
343 static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) {
347 if (A == S_None || B == S_None)
350 if (A > B) std::swap(A, B);
352 // Choose the side which is further along in the sequence.
353 if ((A == S_Retain || A == S_CanRelease) &&
354 (B == S_CanRelease || B == S_Use))
357 // Choose the side which is further along in the sequence.
358 if ((A == S_Use || A == S_CanRelease) &&
359 (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease))
361 // If both sides are releases, choose the more conservative one.
362 if (A == S_Stop && (B == S_Release || B == S_MovableRelease))
364 if (A == S_Release && B == S_MovableRelease)
372 /// \brief Unidirectional information about either a
373 /// retain-decrement-use-release sequence or release-use-decrement-retain
374 /// reverese sequence.
376 /// After an objc_retain, the reference count of the referenced
377 /// object is known to be positive. Similarly, before an objc_release, the
378 /// reference count of the referenced object is known to be positive. If
379 /// there are retain-release pairs in code regions where the retain count
380 /// is known to be positive, they can be eliminated, regardless of any side
381 /// effects between them.
383 /// Also, a retain+release pair nested within another retain+release
384 /// pair all on the known same pointer value can be eliminated, regardless
385 /// of any intervening side effects.
387 /// KnownSafe is true when either of these conditions is satisfied.
390 /// True if the Calls are objc_retainBlock calls (as opposed to objc_retain
394 /// True of the objc_release calls are all marked with the "tail" keyword.
395 bool IsTailCallRelease;
397 /// If the Calls are objc_release calls and they all have a
398 /// clang.imprecise_release tag, this is the metadata tag.
399 MDNode *ReleaseMetadata;
401 /// For a top-down sequence, the set of objc_retains or
402 /// objc_retainBlocks. For bottom-up, the set of objc_releases.
403 SmallPtrSet<Instruction *, 2> Calls;
405 /// The set of optimal insert positions for moving calls in the opposite
407 SmallPtrSet<Instruction *, 2> ReverseInsertPts;
410 KnownSafe(false), IsRetainBlock(false),
411 IsTailCallRelease(false),
412 ReleaseMetadata(0) {}
418 void RRInfo::clear() {
420 IsRetainBlock = false;
421 IsTailCallRelease = false;
424 ReverseInsertPts.clear();
428 /// \brief This class summarizes several per-pointer runtime properties which
429 /// are propogated through the flow graph.
431 /// True if the reference count is known to be incremented.
432 bool KnownPositiveRefCount;
434 /// True of we've seen an opportunity for partial RR elimination, such as
435 /// pushing calls into a CFG triangle or into one side of a CFG diamond.
438 /// The current position in the sequence.
442 /// Unidirectional information about the current sequence.
444 /// TODO: Encapsulate this better.
447 PtrState() : KnownPositiveRefCount(false), Partial(false),
450 void SetKnownPositiveRefCount() {
451 KnownPositiveRefCount = true;
454 void ClearRefCount() {
455 KnownPositiveRefCount = false;
458 bool IsKnownIncremented() const {
459 return KnownPositiveRefCount;
462 void SetSeq(Sequence NewSeq) {
466 Sequence GetSeq() const {
470 void ClearSequenceProgress() {
471 ResetSequenceProgress(S_None);
474 void ResetSequenceProgress(Sequence NewSeq) {
480 void Merge(const PtrState &Other, bool TopDown);
485 PtrState::Merge(const PtrState &Other, bool TopDown) {
486 Seq = MergeSeqs(Seq, Other.Seq, TopDown);
487 KnownPositiveRefCount = KnownPositiveRefCount && Other.KnownPositiveRefCount;
489 // We can't merge a plain objc_retain with an objc_retainBlock.
490 if (RRI.IsRetainBlock != Other.RRI.IsRetainBlock)
493 // If we're not in a sequence (anymore), drop all associated state.
497 } else if (Partial || Other.Partial) {
498 // If we're doing a merge on a path that's previously seen a partial
499 // merge, conservatively drop the sequence, to avoid doing partial
500 // RR elimination. If the branch predicates for the two merge differ,
501 // mixing them is unsafe.
502 ClearSequenceProgress();
504 // Conservatively merge the ReleaseMetadata information.
505 if (RRI.ReleaseMetadata != Other.RRI.ReleaseMetadata)
506 RRI.ReleaseMetadata = 0;
508 RRI.KnownSafe = RRI.KnownSafe && Other.RRI.KnownSafe;
509 RRI.IsTailCallRelease = RRI.IsTailCallRelease &&
510 Other.RRI.IsTailCallRelease;
511 RRI.Calls.insert(Other.RRI.Calls.begin(), Other.RRI.Calls.end());
513 // Merge the insert point sets. If there are any differences,
514 // that makes this a partial merge.
515 Partial = RRI.ReverseInsertPts.size() != Other.RRI.ReverseInsertPts.size();
516 for (SmallPtrSet<Instruction *, 2>::const_iterator
517 I = Other.RRI.ReverseInsertPts.begin(),
518 E = Other.RRI.ReverseInsertPts.end(); I != E; ++I)
519 Partial |= RRI.ReverseInsertPts.insert(*I);
524 /// \brief Per-BasicBlock state.
526 /// The number of unique control paths from the entry which can reach this
528 unsigned TopDownPathCount;
530 /// The number of unique control paths to exits from this block.
531 unsigned BottomUpPathCount;
533 /// A type for PerPtrTopDown and PerPtrBottomUp.
534 typedef MapVector<const Value *, PtrState> MapTy;
536 /// The top-down traversal uses this to record information known about a
537 /// pointer at the bottom of each block.
540 /// The bottom-up traversal uses this to record information known about a
541 /// pointer at the top of each block.
542 MapTy PerPtrBottomUp;
544 /// Effective predecessors of the current block ignoring ignorable edges and
545 /// ignored backedges.
546 SmallVector<BasicBlock *, 2> Preds;
547 /// Effective successors of the current block ignoring ignorable edges and
548 /// ignored backedges.
549 SmallVector<BasicBlock *, 2> Succs;
552 BBState() : TopDownPathCount(0), BottomUpPathCount(0) {}
554 typedef MapTy::iterator ptr_iterator;
555 typedef MapTy::const_iterator ptr_const_iterator;
557 ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); }
558 ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); }
559 ptr_const_iterator top_down_ptr_begin() const {
560 return PerPtrTopDown.begin();
562 ptr_const_iterator top_down_ptr_end() const {
563 return PerPtrTopDown.end();
566 ptr_iterator bottom_up_ptr_begin() { return PerPtrBottomUp.begin(); }
567 ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); }
568 ptr_const_iterator bottom_up_ptr_begin() const {
569 return PerPtrBottomUp.begin();
571 ptr_const_iterator bottom_up_ptr_end() const {
572 return PerPtrBottomUp.end();
575 /// Mark this block as being an entry block, which has one path from the
576 /// entry by definition.
577 void SetAsEntry() { TopDownPathCount = 1; }
579 /// Mark this block as being an exit block, which has one path to an exit by
581 void SetAsExit() { BottomUpPathCount = 1; }
583 PtrState &getPtrTopDownState(const Value *Arg) {
584 return PerPtrTopDown[Arg];
587 PtrState &getPtrBottomUpState(const Value *Arg) {
588 return PerPtrBottomUp[Arg];
591 void clearBottomUpPointers() {
592 PerPtrBottomUp.clear();
595 void clearTopDownPointers() {
596 PerPtrTopDown.clear();
599 void InitFromPred(const BBState &Other);
600 void InitFromSucc(const BBState &Other);
601 void MergePred(const BBState &Other);
602 void MergeSucc(const BBState &Other);
604 /// Return the number of possible unique paths from an entry to an exit
605 /// which pass through this block. This is only valid after both the
606 /// top-down and bottom-up traversals are complete.
607 unsigned GetAllPathCount() const {
608 assert(TopDownPathCount != 0);
609 assert(BottomUpPathCount != 0);
610 return TopDownPathCount * BottomUpPathCount;
613 // Specialized CFG utilities.
614 typedef SmallVectorImpl<BasicBlock *>::const_iterator edge_iterator;
615 edge_iterator pred_begin() { return Preds.begin(); }
616 edge_iterator pred_end() { return Preds.end(); }
617 edge_iterator succ_begin() { return Succs.begin(); }
618 edge_iterator succ_end() { return Succs.end(); }
620 void addSucc(BasicBlock *Succ) { Succs.push_back(Succ); }
621 void addPred(BasicBlock *Pred) { Preds.push_back(Pred); }
623 bool isExit() const { return Succs.empty(); }
627 void BBState::InitFromPred(const BBState &Other) {
628 PerPtrTopDown = Other.PerPtrTopDown;
629 TopDownPathCount = Other.TopDownPathCount;
632 void BBState::InitFromSucc(const BBState &Other) {
633 PerPtrBottomUp = Other.PerPtrBottomUp;
634 BottomUpPathCount = Other.BottomUpPathCount;
637 /// The top-down traversal uses this to merge information about predecessors to
638 /// form the initial state for a new block.
639 void BBState::MergePred(const BBState &Other) {
640 // Other.TopDownPathCount can be 0, in which case it is either dead or a
641 // loop backedge. Loop backedges are special.
642 TopDownPathCount += Other.TopDownPathCount;
644 // Check for overflow. If we have overflow, fall back to conservative
646 if (TopDownPathCount < Other.TopDownPathCount) {
647 clearTopDownPointers();
651 // For each entry in the other set, if our set has an entry with the same key,
652 // merge the entries. Otherwise, copy the entry and merge it with an empty
654 for (ptr_const_iterator MI = Other.top_down_ptr_begin(),
655 ME = Other.top_down_ptr_end(); MI != ME; ++MI) {
656 std::pair<ptr_iterator, bool> Pair = PerPtrTopDown.insert(*MI);
657 Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
661 // For each entry in our set, if the other set doesn't have an entry with the
662 // same key, force it to merge with an empty entry.
663 for (ptr_iterator MI = top_down_ptr_begin(),
664 ME = top_down_ptr_end(); MI != ME; ++MI)
665 if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end())
666 MI->second.Merge(PtrState(), /*TopDown=*/true);
669 /// The bottom-up traversal uses this to merge information about successors to
670 /// form the initial state for a new block.
671 void BBState::MergeSucc(const BBState &Other) {
672 // Other.BottomUpPathCount can be 0, in which case it is either dead or a
673 // loop backedge. Loop backedges are special.
674 BottomUpPathCount += Other.BottomUpPathCount;
676 // Check for overflow. If we have overflow, fall back to conservative
678 if (BottomUpPathCount < Other.BottomUpPathCount) {
679 clearBottomUpPointers();
683 // For each entry in the other set, if our set has an entry with the
684 // same key, merge the entries. Otherwise, copy the entry and merge
685 // it with an empty entry.
686 for (ptr_const_iterator MI = Other.bottom_up_ptr_begin(),
687 ME = Other.bottom_up_ptr_end(); MI != ME; ++MI) {
688 std::pair<ptr_iterator, bool> Pair = PerPtrBottomUp.insert(*MI);
689 Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
693 // For each entry in our set, if the other set doesn't have an entry
694 // with the same key, force it to merge with an empty entry.
695 for (ptr_iterator MI = bottom_up_ptr_begin(),
696 ME = bottom_up_ptr_end(); MI != ME; ++MI)
697 if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end())
698 MI->second.Merge(PtrState(), /*TopDown=*/false);
702 /// \brief The main ARC optimization pass.
703 class ObjCARCOpt : public FunctionPass {
705 ProvenanceAnalysis PA;
707 /// A flag indicating whether this optimization pass should run.
710 /// Declarations for ObjC runtime functions, for use in creating calls to
711 /// them. These are initialized lazily to avoid cluttering up the Module
712 /// with unused declarations.
714 /// Declaration for ObjC runtime function
715 /// objc_retainAutoreleasedReturnValue.
716 Constant *RetainRVCallee;
717 /// Declaration for ObjC runtime function objc_autoreleaseReturnValue.
718 Constant *AutoreleaseRVCallee;
719 /// Declaration for ObjC runtime function objc_release.
720 Constant *ReleaseCallee;
721 /// Declaration for ObjC runtime function objc_retain.
722 Constant *RetainCallee;
723 /// Declaration for ObjC runtime function objc_retainBlock.
724 Constant *RetainBlockCallee;
725 /// Declaration for ObjC runtime function objc_autorelease.
726 Constant *AutoreleaseCallee;
728 /// Flags which determine whether each of the interesting runtine functions
729 /// is in fact used in the current function.
730 unsigned UsedInThisFunction;
732 /// The Metadata Kind for clang.imprecise_release metadata.
733 unsigned ImpreciseReleaseMDKind;
735 /// The Metadata Kind for clang.arc.copy_on_escape metadata.
736 unsigned CopyOnEscapeMDKind;
738 /// The Metadata Kind for clang.arc.no_objc_arc_exceptions metadata.
739 unsigned NoObjCARCExceptionsMDKind;
741 Constant *getRetainRVCallee(Module *M);
742 Constant *getAutoreleaseRVCallee(Module *M);
743 Constant *getReleaseCallee(Module *M);
744 Constant *getRetainCallee(Module *M);
745 Constant *getRetainBlockCallee(Module *M);
746 Constant *getAutoreleaseCallee(Module *M);
748 bool IsRetainBlockOptimizable(const Instruction *Inst);
750 void OptimizeRetainCall(Function &F, Instruction *Retain);
751 bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV);
752 void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV,
753 InstructionClass &Class);
754 void OptimizeIndividualCalls(Function &F);
756 void CheckForCFGHazards(const BasicBlock *BB,
757 DenseMap<const BasicBlock *, BBState> &BBStates,
758 BBState &MyStates) const;
759 bool VisitInstructionBottomUp(Instruction *Inst,
761 MapVector<Value *, RRInfo> &Retains,
763 bool VisitBottomUp(BasicBlock *BB,
764 DenseMap<const BasicBlock *, BBState> &BBStates,
765 MapVector<Value *, RRInfo> &Retains);
766 bool VisitInstructionTopDown(Instruction *Inst,
767 DenseMap<Value *, RRInfo> &Releases,
769 bool VisitTopDown(BasicBlock *BB,
770 DenseMap<const BasicBlock *, BBState> &BBStates,
771 DenseMap<Value *, RRInfo> &Releases);
772 bool Visit(Function &F,
773 DenseMap<const BasicBlock *, BBState> &BBStates,
774 MapVector<Value *, RRInfo> &Retains,
775 DenseMap<Value *, RRInfo> &Releases);
777 void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove,
778 MapVector<Value *, RRInfo> &Retains,
779 DenseMap<Value *, RRInfo> &Releases,
780 SmallVectorImpl<Instruction *> &DeadInsts,
783 bool ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState> &BBStates,
784 MapVector<Value *, RRInfo> &Retains,
785 DenseMap<Value *, RRInfo> &Releases,
787 SmallVector<Instruction *, 4> &NewRetains,
788 SmallVector<Instruction *, 4> &NewReleases,
789 SmallVector<Instruction *, 8> &DeadInsts,
790 RRInfo &RetainsToMove,
791 RRInfo &ReleasesToMove,
794 bool &AnyPairsCompletelyEliminated);
796 bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates,
797 MapVector<Value *, RRInfo> &Retains,
798 DenseMap<Value *, RRInfo> &Releases,
801 void OptimizeWeakCalls(Function &F);
803 bool OptimizeSequences(Function &F);
805 void OptimizeReturns(Function &F);
807 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
808 virtual bool doInitialization(Module &M);
809 virtual bool runOnFunction(Function &F);
810 virtual void releaseMemory();
814 ObjCARCOpt() : FunctionPass(ID) {
815 initializeObjCARCOptPass(*PassRegistry::getPassRegistry());
820 char ObjCARCOpt::ID = 0;
821 INITIALIZE_PASS_BEGIN(ObjCARCOpt,
822 "objc-arc", "ObjC ARC optimization", false, false)
823 INITIALIZE_PASS_DEPENDENCY(ObjCARCAliasAnalysis)
824 INITIALIZE_PASS_END(ObjCARCOpt,
825 "objc-arc", "ObjC ARC optimization", false, false)
827 Pass *llvm::createObjCARCOptPass() {
828 return new ObjCARCOpt();
831 void ObjCARCOpt::getAnalysisUsage(AnalysisUsage &AU) const {
832 AU.addRequired<ObjCARCAliasAnalysis>();
833 AU.addRequired<AliasAnalysis>();
834 // ARC optimization doesn't currently split critical edges.
835 AU.setPreservesCFG();
838 bool ObjCARCOpt::IsRetainBlockOptimizable(const Instruction *Inst) {
839 // Without the magic metadata tag, we have to assume this might be an
840 // objc_retainBlock call inserted to convert a block pointer to an id,
841 // in which case it really is needed.
842 if (!Inst->getMetadata(CopyOnEscapeMDKind))
845 // If the pointer "escapes" (not including being used in a call),
846 // the copy may be needed.
847 if (DoesRetainableObjPtrEscape(Inst))
850 // Otherwise, it's not needed.
854 Constant *ObjCARCOpt::getRetainRVCallee(Module *M) {
855 if (!RetainRVCallee) {
856 LLVMContext &C = M->getContext();
857 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
858 Type *Params[] = { I8X };
859 FunctionType *FTy = FunctionType::get(I8X, Params, /*isVarArg=*/false);
860 AttributeSet Attribute =
861 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
862 Attribute::NoUnwind);
864 M->getOrInsertFunction("objc_retainAutoreleasedReturnValue", FTy,
867 return RetainRVCallee;
870 Constant *ObjCARCOpt::getAutoreleaseRVCallee(Module *M) {
871 if (!AutoreleaseRVCallee) {
872 LLVMContext &C = M->getContext();
873 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
874 Type *Params[] = { I8X };
875 FunctionType *FTy = FunctionType::get(I8X, Params, /*isVarArg=*/false);
876 AttributeSet Attribute =
877 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
878 Attribute::NoUnwind);
879 AutoreleaseRVCallee =
880 M->getOrInsertFunction("objc_autoreleaseReturnValue", FTy,
883 return AutoreleaseRVCallee;
886 Constant *ObjCARCOpt::getReleaseCallee(Module *M) {
887 if (!ReleaseCallee) {
888 LLVMContext &C = M->getContext();
889 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
890 AttributeSet Attribute =
891 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
892 Attribute::NoUnwind);
894 M->getOrInsertFunction(
896 FunctionType::get(Type::getVoidTy(C), Params, /*isVarArg=*/false),
899 return ReleaseCallee;
902 Constant *ObjCARCOpt::getRetainCallee(Module *M) {
904 LLVMContext &C = M->getContext();
905 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
906 AttributeSet Attribute =
907 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
908 Attribute::NoUnwind);
910 M->getOrInsertFunction(
912 FunctionType::get(Params[0], Params, /*isVarArg=*/false),
918 Constant *ObjCARCOpt::getRetainBlockCallee(Module *M) {
919 if (!RetainBlockCallee) {
920 LLVMContext &C = M->getContext();
921 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
922 // objc_retainBlock is not nounwind because it calls user copy constructors
923 // which could theoretically throw.
925 M->getOrInsertFunction(
927 FunctionType::get(Params[0], Params, /*isVarArg=*/false),
930 return RetainBlockCallee;
933 Constant *ObjCARCOpt::getAutoreleaseCallee(Module *M) {
934 if (!AutoreleaseCallee) {
935 LLVMContext &C = M->getContext();
936 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
937 AttributeSet Attribute =
938 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
939 Attribute::NoUnwind);
941 M->getOrInsertFunction(
943 FunctionType::get(Params[0], Params, /*isVarArg=*/false),
946 return AutoreleaseCallee;
949 /// Turn objc_retain into objc_retainAutoreleasedReturnValue if the operand is a
952 ObjCARCOpt::OptimizeRetainCall(Function &F, Instruction *Retain) {
953 ImmutableCallSite CS(GetObjCArg(Retain));
954 const Instruction *Call = CS.getInstruction();
956 if (Call->getParent() != Retain->getParent()) return;
958 // Check that the call is next to the retain.
959 BasicBlock::const_iterator I = Call;
961 while (isNoopInstruction(I)) ++I;
965 // Turn it to an objc_retainAutoreleasedReturnValue..
969 DEBUG(dbgs() << "ObjCARCOpt::OptimizeRetainCall: Transforming "
970 "objc_retain => objc_retainAutoreleasedReturnValue"
971 " since the operand is a return value.\n"
975 cast<CallInst>(Retain)->setCalledFunction(getRetainRVCallee(F.getParent()));
977 DEBUG(dbgs() << " New: "
981 /// Turn objc_retainAutoreleasedReturnValue into objc_retain if the operand is
982 /// not a return value. Or, if it can be paired with an
983 /// objc_autoreleaseReturnValue, delete the pair and return true.
985 ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) {
986 // Check for the argument being from an immediately preceding call or invoke.
987 const Value *Arg = GetObjCArg(RetainRV);
988 ImmutableCallSite CS(Arg);
989 if (const Instruction *Call = CS.getInstruction()) {
990 if (Call->getParent() == RetainRV->getParent()) {
991 BasicBlock::const_iterator I = Call;
993 while (isNoopInstruction(I)) ++I;
996 } else if (const InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
997 BasicBlock *RetainRVParent = RetainRV->getParent();
998 if (II->getNormalDest() == RetainRVParent) {
999 BasicBlock::const_iterator I = RetainRVParent->begin();
1000 while (isNoopInstruction(I)) ++I;
1001 if (&*I == RetainRV)
1007 // Check for being preceded by an objc_autoreleaseReturnValue on the same
1008 // pointer. In this case, we can delete the pair.
1009 BasicBlock::iterator I = RetainRV, Begin = RetainRV->getParent()->begin();
1011 do --I; while (I != Begin && isNoopInstruction(I));
1012 if (GetBasicInstructionClass(I) == IC_AutoreleaseRV &&
1013 GetObjCArg(I) == Arg) {
1017 DEBUG(dbgs() << "ObjCARCOpt::OptimizeRetainRVCall: Erasing " << *I << "\n"
1018 << " Erasing " << *RetainRV
1021 EraseInstruction(I);
1022 EraseInstruction(RetainRV);
1027 // Turn it to a plain objc_retain.
1031 DEBUG(dbgs() << "ObjCARCOpt::OptimizeRetainRVCall: Transforming "
1032 "objc_retainAutoreleasedReturnValue => "
1033 "objc_retain since the operand is not a return value.\n"
1035 << *RetainRV << "\n");
1037 cast<CallInst>(RetainRV)->setCalledFunction(getRetainCallee(F.getParent()));
1039 DEBUG(dbgs() << " New: "
1040 << *RetainRV << "\n");
1045 /// Turn objc_autoreleaseReturnValue into objc_autorelease if the result is not
1046 /// used as a return value.
1048 ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV,
1049 InstructionClass &Class) {
1050 // Check for a return of the pointer value.
1051 const Value *Ptr = GetObjCArg(AutoreleaseRV);
1052 SmallVector<const Value *, 2> Users;
1053 Users.push_back(Ptr);
1055 Ptr = Users.pop_back_val();
1056 for (Value::const_use_iterator UI = Ptr->use_begin(), UE = Ptr->use_end();
1058 const User *I = *UI;
1059 if (isa<ReturnInst>(I) || GetBasicInstructionClass(I) == IC_RetainRV)
1061 if (isa<BitCastInst>(I))
1064 } while (!Users.empty());
1069 DEBUG(dbgs() << "ObjCARCOpt::OptimizeAutoreleaseRVCall: Transforming "
1070 "objc_autoreleaseReturnValue => "
1071 "objc_autorelease since its operand is not used as a return "
1074 << *AutoreleaseRV << "\n");
1076 CallInst *AutoreleaseRVCI = cast<CallInst>(AutoreleaseRV);
1078 setCalledFunction(getAutoreleaseCallee(F.getParent()));
1079 AutoreleaseRVCI->setTailCall(false); // Never tail call objc_autorelease.
1080 Class = IC_Autorelease;
1082 DEBUG(dbgs() << " New: "
1083 << *AutoreleaseRV << "\n");
1087 /// Visit each call, one at a time, and make simplifications without doing any
1088 /// additional analysis.
1089 void ObjCARCOpt::OptimizeIndividualCalls(Function &F) {
1090 // Reset all the flags in preparation for recomputing them.
1091 UsedInThisFunction = 0;
1093 // Visit all objc_* calls in F.
1094 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
1095 Instruction *Inst = &*I++;
1097 InstructionClass Class = GetBasicInstructionClass(Inst);
1099 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Visiting: Class: "
1100 << Class << "; " << *Inst << "\n");
1105 // Delete no-op casts. These function calls have special semantics, but
1106 // the semantics are entirely implemented via lowering in the front-end,
1107 // so by the time they reach the optimizer, they are just no-op calls
1108 // which return their argument.
1110 // There are gray areas here, as the ability to cast reference-counted
1111 // pointers to raw void* and back allows code to break ARC assumptions,
1112 // however these are currently considered to be unimportant.
1116 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Erasing no-op cast:"
1117 " " << *Inst << "\n");
1118 EraseInstruction(Inst);
1121 // If the pointer-to-weak-pointer is null, it's undefined behavior.
1124 case IC_LoadWeakRetained:
1126 case IC_DestroyWeak: {
1127 CallInst *CI = cast<CallInst>(Inst);
1128 if (isNullOrUndef(CI->getArgOperand(0))) {
1130 Type *Ty = CI->getArgOperand(0)->getType();
1131 new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
1132 Constant::getNullValue(Ty),
1134 llvm::Value *NewValue = UndefValue::get(CI->getType());
1135 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: A null "
1136 "pointer-to-weak-pointer is undefined behavior.\n"
1140 CI->replaceAllUsesWith(NewValue);
1141 CI->eraseFromParent();
1148 CallInst *CI = cast<CallInst>(Inst);
1149 if (isNullOrUndef(CI->getArgOperand(0)) ||
1150 isNullOrUndef(CI->getArgOperand(1))) {
1152 Type *Ty = CI->getArgOperand(0)->getType();
1153 new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
1154 Constant::getNullValue(Ty),
1157 llvm::Value *NewValue = UndefValue::get(CI->getType());
1158 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: A null "
1159 "pointer-to-weak-pointer is undefined behavior.\n"
1164 CI->replaceAllUsesWith(NewValue);
1165 CI->eraseFromParent();
1171 OptimizeRetainCall(F, Inst);
1174 if (OptimizeRetainRVCall(F, Inst))
1177 case IC_AutoreleaseRV:
1178 OptimizeAutoreleaseRVCall(F, Inst, Class);
1182 // objc_autorelease(x) -> objc_release(x) if x is otherwise unused.
1183 if (IsAutorelease(Class) && Inst->use_empty()) {
1184 CallInst *Call = cast<CallInst>(Inst);
1185 const Value *Arg = Call->getArgOperand(0);
1186 Arg = FindSingleUseIdentifiedObject(Arg);
1191 // Create the declaration lazily.
1192 LLVMContext &C = Inst->getContext();
1194 CallInst::Create(getReleaseCallee(F.getParent()),
1195 Call->getArgOperand(0), "", Call);
1196 NewCall->setMetadata(ImpreciseReleaseMDKind,
1197 MDNode::get(C, ArrayRef<Value *>()));
1199 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Replacing "
1200 "objc_autorelease(x) with objc_release(x) since x is "
1201 "otherwise unused.\n"
1202 " Old: " << *Call <<
1206 EraseInstruction(Call);
1212 // For functions which can never be passed stack arguments, add
1214 if (IsAlwaysTail(Class)) {
1216 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Adding tail keyword"
1217 " to function since it can never be passed stack args: " << *Inst <<
1219 cast<CallInst>(Inst)->setTailCall();
1222 // Ensure that functions that can never have a "tail" keyword due to the
1223 // semantics of ARC truly do not do so.
1224 if (IsNeverTail(Class)) {
1226 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Removing tail "
1227 "keyword from function: " << *Inst <<
1229 cast<CallInst>(Inst)->setTailCall(false);
1232 // Set nounwind as needed.
1233 if (IsNoThrow(Class)) {
1235 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Found no throw"
1236 " class. Setting nounwind on: " << *Inst << "\n");
1237 cast<CallInst>(Inst)->setDoesNotThrow();
1240 if (!IsNoopOnNull(Class)) {
1241 UsedInThisFunction |= 1 << Class;
1245 const Value *Arg = GetObjCArg(Inst);
1247 // ARC calls with null are no-ops. Delete them.
1248 if (isNullOrUndef(Arg)) {
1251 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: ARC calls with "
1252 " null are no-ops. Erasing: " << *Inst << "\n");
1253 EraseInstruction(Inst);
1257 // Keep track of which of retain, release, autorelease, and retain_block
1258 // are actually present in this function.
1259 UsedInThisFunction |= 1 << Class;
1261 // If Arg is a PHI, and one or more incoming values to the
1262 // PHI are null, and the call is control-equivalent to the PHI, and there
1263 // are no relevant side effects between the PHI and the call, the call
1264 // could be pushed up to just those paths with non-null incoming values.
1265 // For now, don't bother splitting critical edges for this.
1266 SmallVector<std::pair<Instruction *, const Value *>, 4> Worklist;
1267 Worklist.push_back(std::make_pair(Inst, Arg));
1269 std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val();
1273 const PHINode *PN = dyn_cast<PHINode>(Arg);
1276 // Determine if the PHI has any null operands, or any incoming
1278 bool HasNull = false;
1279 bool HasCriticalEdges = false;
1280 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1282 StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
1283 if (isNullOrUndef(Incoming))
1285 else if (cast<TerminatorInst>(PN->getIncomingBlock(i)->back())
1286 .getNumSuccessors() != 1) {
1287 HasCriticalEdges = true;
1291 // If we have null operands and no critical edges, optimize.
1292 if (!HasCriticalEdges && HasNull) {
1293 SmallPtrSet<Instruction *, 4> DependingInstructions;
1294 SmallPtrSet<const BasicBlock *, 4> Visited;
1296 // Check that there is nothing that cares about the reference
1297 // count between the call and the phi.
1300 case IC_RetainBlock:
1301 // These can always be moved up.
1304 // These can't be moved across things that care about the retain
1306 FindDependencies(NeedsPositiveRetainCount, Arg,
1307 Inst->getParent(), Inst,
1308 DependingInstructions, Visited, PA);
1310 case IC_Autorelease:
1311 // These can't be moved across autorelease pool scope boundaries.
1312 FindDependencies(AutoreleasePoolBoundary, Arg,
1313 Inst->getParent(), Inst,
1314 DependingInstructions, Visited, PA);
1317 case IC_AutoreleaseRV:
1318 // Don't move these; the RV optimization depends on the autoreleaseRV
1319 // being tail called, and the retainRV being immediately after a call
1320 // (which might still happen if we get lucky with codegen layout, but
1321 // it's not worth taking the chance).
1324 llvm_unreachable("Invalid dependence flavor");
1327 if (DependingInstructions.size() == 1 &&
1328 *DependingInstructions.begin() == PN) {
1331 // Clone the call into each predecessor that has a non-null value.
1332 CallInst *CInst = cast<CallInst>(Inst);
1333 Type *ParamTy = CInst->getArgOperand(0)->getType();
1334 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1336 StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
1337 if (!isNullOrUndef(Incoming)) {
1338 CallInst *Clone = cast<CallInst>(CInst->clone());
1339 Value *Op = PN->getIncomingValue(i);
1340 Instruction *InsertPos = &PN->getIncomingBlock(i)->back();
1341 if (Op->getType() != ParamTy)
1342 Op = new BitCastInst(Op, ParamTy, "", InsertPos);
1343 Clone->setArgOperand(0, Op);
1344 Clone->insertBefore(InsertPos);
1346 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Cloning "
1349 "clone at " << *InsertPos << "\n");
1350 Worklist.push_back(std::make_pair(Clone, Incoming));
1353 // Erase the original call.
1354 DEBUG(dbgs() << "Erasing: " << *CInst << "\n");
1355 EraseInstruction(CInst);
1359 } while (!Worklist.empty());
1361 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Finished List.\n");
1364 /// Check for critical edges, loop boundaries, irreducible control flow, or
1365 /// other CFG structures where moving code across the edge would result in it
1366 /// being executed more.
1368 ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB,
1369 DenseMap<const BasicBlock *, BBState> &BBStates,
1370 BBState &MyStates) const {
1371 // If any top-down local-use or possible-dec has a succ which is earlier in
1372 // the sequence, forget it.
1373 for (BBState::ptr_iterator I = MyStates.top_down_ptr_begin(),
1374 E = MyStates.top_down_ptr_end(); I != E; ++I)
1375 switch (I->second.GetSeq()) {
1378 const Value *Arg = I->first;
1379 const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
1380 bool SomeSuccHasSame = false;
1381 bool AllSuccsHaveSame = true;
1382 PtrState &S = I->second;
1383 succ_const_iterator SI(TI), SE(TI, false);
1385 for (; SI != SE; ++SI) {
1386 Sequence SuccSSeq = S_None;
1387 bool SuccSRRIKnownSafe = false;
1388 // If VisitBottomUp has pointer information for this successor, take
1389 // what we know about it.
1390 DenseMap<const BasicBlock *, BBState>::iterator BBI =
1392 assert(BBI != BBStates.end());
1393 const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);
1394 SuccSSeq = SuccS.GetSeq();
1395 SuccSRRIKnownSafe = SuccS.RRI.KnownSafe;
1398 case S_CanRelease: {
1399 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe) {
1400 S.ClearSequenceProgress();
1406 SomeSuccHasSame = true;
1410 case S_MovableRelease:
1411 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe)
1412 AllSuccsHaveSame = false;
1415 llvm_unreachable("bottom-up pointer in retain state!");
1418 // If the state at the other end of any of the successor edges
1419 // matches the current state, require all edges to match. This
1420 // guards against loops in the middle of a sequence.
1421 if (SomeSuccHasSame && !AllSuccsHaveSame)
1422 S.ClearSequenceProgress();
1425 case S_CanRelease: {
1426 const Value *Arg = I->first;
1427 const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
1428 bool SomeSuccHasSame = false;
1429 bool AllSuccsHaveSame = true;
1430 PtrState &S = I->second;
1431 succ_const_iterator SI(TI), SE(TI, false);
1433 for (; SI != SE; ++SI) {
1434 Sequence SuccSSeq = S_None;
1435 bool SuccSRRIKnownSafe = false;
1436 // If VisitBottomUp has pointer information for this successor, take
1437 // what we know about it.
1438 DenseMap<const BasicBlock *, BBState>::iterator BBI =
1440 assert(BBI != BBStates.end());
1441 const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);
1442 SuccSSeq = SuccS.GetSeq();
1443 SuccSRRIKnownSafe = SuccS.RRI.KnownSafe;
1446 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe) {
1447 S.ClearSequenceProgress();
1453 SomeSuccHasSame = true;
1457 case S_MovableRelease:
1459 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe)
1460 AllSuccsHaveSame = false;
1463 llvm_unreachable("bottom-up pointer in retain state!");
1466 // If the state at the other end of any of the successor edges
1467 // matches the current state, require all edges to match. This
1468 // guards against loops in the middle of a sequence.
1469 if (SomeSuccHasSame && !AllSuccsHaveSame)
1470 S.ClearSequenceProgress();
1477 ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst,
1479 MapVector<Value *, RRInfo> &Retains,
1480 BBState &MyStates) {
1481 bool NestingDetected = false;
1482 InstructionClass Class = GetInstructionClass(Inst);
1483 const Value *Arg = 0;
1487 Arg = GetObjCArg(Inst);
1489 PtrState &S = MyStates.getPtrBottomUpState(Arg);
1491 // If we see two releases in a row on the same pointer. If so, make
1492 // a note, and we'll cicle back to revisit it after we've
1493 // hopefully eliminated the second release, which may allow us to
1494 // eliminate the first release too.
1495 // Theoretically we could implement removal of nested retain+release
1496 // pairs by making PtrState hold a stack of states, but this is
1497 // simple and avoids adding overhead for the non-nested case.
1498 if (S.GetSeq() == S_Release || S.GetSeq() == S_MovableRelease) {
1499 DEBUG(dbgs() << "ObjCARCOpt::VisitInstructionBottomUp: Found nested "
1500 "releases (i.e. a release pair)\n");
1501 NestingDetected = true;
1504 MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind);
1505 S.ResetSequenceProgress(ReleaseMetadata ? S_MovableRelease : S_Release);
1506 S.RRI.ReleaseMetadata = ReleaseMetadata;
1507 S.RRI.KnownSafe = S.IsKnownIncremented();
1508 S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
1509 S.RRI.Calls.insert(Inst);
1511 S.SetKnownPositiveRefCount();
1514 case IC_RetainBlock:
1515 // An objc_retainBlock call with just a use may need to be kept,
1516 // because it may be copying a block from the stack to the heap.
1517 if (!IsRetainBlockOptimizable(Inst))
1522 Arg = GetObjCArg(Inst);
1524 PtrState &S = MyStates.getPtrBottomUpState(Arg);
1525 S.SetKnownPositiveRefCount();
1527 switch (S.GetSeq()) {
1530 case S_MovableRelease:
1532 S.RRI.ReverseInsertPts.clear();
1535 // Don't do retain+release tracking for IC_RetainRV, because it's
1536 // better to let it remain as the first instruction after a call.
1537 if (Class != IC_RetainRV) {
1538 S.RRI.IsRetainBlock = Class == IC_RetainBlock;
1539 Retains[Inst] = S.RRI;
1541 S.ClearSequenceProgress();
1546 llvm_unreachable("bottom-up pointer in retain state!");
1548 return NestingDetected;
1550 case IC_AutoreleasepoolPop:
1551 // Conservatively, clear MyStates for all known pointers.
1552 MyStates.clearBottomUpPointers();
1553 return NestingDetected;
1554 case IC_AutoreleasepoolPush:
1556 // These are irrelevant.
1557 return NestingDetected;
1562 // Consider any other possible effects of this instruction on each
1563 // pointer being tracked.
1564 for (BBState::ptr_iterator MI = MyStates.bottom_up_ptr_begin(),
1565 ME = MyStates.bottom_up_ptr_end(); MI != ME; ++MI) {
1566 const Value *Ptr = MI->first;
1568 continue; // Handled above.
1569 PtrState &S = MI->second;
1570 Sequence Seq = S.GetSeq();
1572 // Check for possible releases.
1573 if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
1577 S.SetSeq(S_CanRelease);
1581 case S_MovableRelease:
1586 llvm_unreachable("bottom-up pointer in retain state!");
1590 // Check for possible direct uses.
1593 case S_MovableRelease:
1594 if (CanUse(Inst, Ptr, PA, Class)) {
1595 assert(S.RRI.ReverseInsertPts.empty());
1596 // If this is an invoke instruction, we're scanning it as part of
1597 // one of its successor blocks, since we can't insert code after it
1598 // in its own block, and we don't want to split critical edges.
1599 if (isa<InvokeInst>(Inst))
1600 S.RRI.ReverseInsertPts.insert(BB->getFirstInsertionPt());
1602 S.RRI.ReverseInsertPts.insert(llvm::next(BasicBlock::iterator(Inst)));
1604 } else if (Seq == S_Release &&
1605 (Class == IC_User || Class == IC_CallOrUser)) {
1606 // Non-movable releases depend on any possible objc pointer use.
1608 assert(S.RRI.ReverseInsertPts.empty());
1609 // As above; handle invoke specially.
1610 if (isa<InvokeInst>(Inst))
1611 S.RRI.ReverseInsertPts.insert(BB->getFirstInsertionPt());
1613 S.RRI.ReverseInsertPts.insert(llvm::next(BasicBlock::iterator(Inst)));
1617 if (CanUse(Inst, Ptr, PA, Class))
1625 llvm_unreachable("bottom-up pointer in retain state!");
1629 return NestingDetected;
1633 ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
1634 DenseMap<const BasicBlock *, BBState> &BBStates,
1635 MapVector<Value *, RRInfo> &Retains) {
1636 bool NestingDetected = false;
1637 BBState &MyStates = BBStates[BB];
1639 // Merge the states from each successor to compute the initial state
1640 // for the current block.
1641 BBState::edge_iterator SI(MyStates.succ_begin()),
1642 SE(MyStates.succ_end());
1644 const BasicBlock *Succ = *SI;
1645 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ);
1646 assert(I != BBStates.end());
1647 MyStates.InitFromSucc(I->second);
1649 for (; SI != SE; ++SI) {
1651 I = BBStates.find(Succ);
1652 assert(I != BBStates.end());
1653 MyStates.MergeSucc(I->second);
1657 // Visit all the instructions, bottom-up.
1658 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
1659 Instruction *Inst = llvm::prior(I);
1661 // Invoke instructions are visited as part of their successors (below).
1662 if (isa<InvokeInst>(Inst))
1665 DEBUG(dbgs() << "ObjCARCOpt::VisitButtonUp: Visiting " << *Inst << "\n");
1667 NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates);
1670 // If there's a predecessor with an invoke, visit the invoke as if it were
1671 // part of this block, since we can't insert code after an invoke in its own
1672 // block, and we don't want to split critical edges.
1673 for (BBState::edge_iterator PI(MyStates.pred_begin()),
1674 PE(MyStates.pred_end()); PI != PE; ++PI) {
1675 BasicBlock *Pred = *PI;
1676 if (InvokeInst *II = dyn_cast<InvokeInst>(&Pred->back()))
1677 NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates);
1680 return NestingDetected;
1684 ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst,
1685 DenseMap<Value *, RRInfo> &Releases,
1686 BBState &MyStates) {
1687 bool NestingDetected = false;
1688 InstructionClass Class = GetInstructionClass(Inst);
1689 const Value *Arg = 0;
1692 case IC_RetainBlock:
1693 // An objc_retainBlock call with just a use may need to be kept,
1694 // because it may be copying a block from the stack to the heap.
1695 if (!IsRetainBlockOptimizable(Inst))
1700 Arg = GetObjCArg(Inst);
1702 PtrState &S = MyStates.getPtrTopDownState(Arg);
1704 // Don't do retain+release tracking for IC_RetainRV, because it's
1705 // better to let it remain as the first instruction after a call.
1706 if (Class != IC_RetainRV) {
1707 // If we see two retains in a row on the same pointer. If so, make
1708 // a note, and we'll cicle back to revisit it after we've
1709 // hopefully eliminated the second retain, which may allow us to
1710 // eliminate the first retain too.
1711 // Theoretically we could implement removal of nested retain+release
1712 // pairs by making PtrState hold a stack of states, but this is
1713 // simple and avoids adding overhead for the non-nested case.
1714 if (S.GetSeq() == S_Retain)
1715 NestingDetected = true;
1717 S.ResetSequenceProgress(S_Retain);
1718 S.RRI.IsRetainBlock = Class == IC_RetainBlock;
1719 S.RRI.KnownSafe = S.IsKnownIncremented();
1720 S.RRI.Calls.insert(Inst);
1723 S.SetKnownPositiveRefCount();
1725 // A retain can be a potential use; procede to the generic checking
1730 Arg = GetObjCArg(Inst);
1732 PtrState &S = MyStates.getPtrTopDownState(Arg);
1735 switch (S.GetSeq()) {
1738 S.RRI.ReverseInsertPts.clear();
1741 S.RRI.ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind);
1742 S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
1743 Releases[Inst] = S.RRI;
1744 S.ClearSequenceProgress();
1750 case S_MovableRelease:
1751 llvm_unreachable("top-down pointer in release state!");
1755 case IC_AutoreleasepoolPop:
1756 // Conservatively, clear MyStates for all known pointers.
1757 MyStates.clearTopDownPointers();
1758 return NestingDetected;
1759 case IC_AutoreleasepoolPush:
1761 // These are irrelevant.
1762 return NestingDetected;
1767 // Consider any other possible effects of this instruction on each
1768 // pointer being tracked.
1769 for (BBState::ptr_iterator MI = MyStates.top_down_ptr_begin(),
1770 ME = MyStates.top_down_ptr_end(); MI != ME; ++MI) {
1771 const Value *Ptr = MI->first;
1773 continue; // Handled above.
1774 PtrState &S = MI->second;
1775 Sequence Seq = S.GetSeq();
1777 // Check for possible releases.
1778 if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
1782 S.SetSeq(S_CanRelease);
1783 assert(S.RRI.ReverseInsertPts.empty());
1784 S.RRI.ReverseInsertPts.insert(Inst);
1786 // One call can't cause a transition from S_Retain to S_CanRelease
1787 // and S_CanRelease to S_Use. If we've made the first transition,
1796 case S_MovableRelease:
1797 llvm_unreachable("top-down pointer in release state!");
1801 // Check for possible direct uses.
1804 if (CanUse(Inst, Ptr, PA, Class))
1813 case S_MovableRelease:
1814 llvm_unreachable("top-down pointer in release state!");
1818 return NestingDetected;
1822 ObjCARCOpt::VisitTopDown(BasicBlock *BB,
1823 DenseMap<const BasicBlock *, BBState> &BBStates,
1824 DenseMap<Value *, RRInfo> &Releases) {
1825 bool NestingDetected = false;
1826 BBState &MyStates = BBStates[BB];
1828 // Merge the states from each predecessor to compute the initial state
1829 // for the current block.
1830 BBState::edge_iterator PI(MyStates.pred_begin()),
1831 PE(MyStates.pred_end());
1833 const BasicBlock *Pred = *PI;
1834 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred);
1835 assert(I != BBStates.end());
1836 MyStates.InitFromPred(I->second);
1838 for (; PI != PE; ++PI) {
1840 I = BBStates.find(Pred);
1841 assert(I != BBStates.end());
1842 MyStates.MergePred(I->second);
1846 // Visit all the instructions, top-down.
1847 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
1848 Instruction *Inst = I;
1850 DEBUG(dbgs() << "ObjCARCOpt::VisitTopDown: Visiting " << *Inst << "\n");
1852 NestingDetected |= VisitInstructionTopDown(Inst, Releases, MyStates);
1855 CheckForCFGHazards(BB, BBStates, MyStates);
1856 return NestingDetected;
1860 ComputePostOrders(Function &F,
1861 SmallVectorImpl<BasicBlock *> &PostOrder,
1862 SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder,
1863 unsigned NoObjCARCExceptionsMDKind,
1864 DenseMap<const BasicBlock *, BBState> &BBStates) {
1865 /// The visited set, for doing DFS walks.
1866 SmallPtrSet<BasicBlock *, 16> Visited;
1868 // Do DFS, computing the PostOrder.
1869 SmallPtrSet<BasicBlock *, 16> OnStack;
1870 SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack;
1872 // Functions always have exactly one entry block, and we don't have
1873 // any other block that we treat like an entry block.
1874 BasicBlock *EntryBB = &F.getEntryBlock();
1875 BBState &MyStates = BBStates[EntryBB];
1876 MyStates.SetAsEntry();
1877 TerminatorInst *EntryTI = cast<TerminatorInst>(&EntryBB->back());
1878 SuccStack.push_back(std::make_pair(EntryBB, succ_iterator(EntryTI)));
1879 Visited.insert(EntryBB);
1880 OnStack.insert(EntryBB);
1883 BasicBlock *CurrBB = SuccStack.back().first;
1884 TerminatorInst *TI = cast<TerminatorInst>(&CurrBB->back());
1885 succ_iterator SE(TI, false);
1887 while (SuccStack.back().second != SE) {
1888 BasicBlock *SuccBB = *SuccStack.back().second++;
1889 if (Visited.insert(SuccBB)) {
1890 TerminatorInst *TI = cast<TerminatorInst>(&SuccBB->back());
1891 SuccStack.push_back(std::make_pair(SuccBB, succ_iterator(TI)));
1892 BBStates[CurrBB].addSucc(SuccBB);
1893 BBState &SuccStates = BBStates[SuccBB];
1894 SuccStates.addPred(CurrBB);
1895 OnStack.insert(SuccBB);
1899 if (!OnStack.count(SuccBB)) {
1900 BBStates[CurrBB].addSucc(SuccBB);
1901 BBStates[SuccBB].addPred(CurrBB);
1904 OnStack.erase(CurrBB);
1905 PostOrder.push_back(CurrBB);
1906 SuccStack.pop_back();
1907 } while (!SuccStack.empty());
1911 // Do reverse-CFG DFS, computing the reverse-CFG PostOrder.
1912 // Functions may have many exits, and there also blocks which we treat
1913 // as exits due to ignored edges.
1914 SmallVector<std::pair<BasicBlock *, BBState::edge_iterator>, 16> PredStack;
1915 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
1916 BasicBlock *ExitBB = I;
1917 BBState &MyStates = BBStates[ExitBB];
1918 if (!MyStates.isExit())
1921 MyStates.SetAsExit();
1923 PredStack.push_back(std::make_pair(ExitBB, MyStates.pred_begin()));
1924 Visited.insert(ExitBB);
1925 while (!PredStack.empty()) {
1926 reverse_dfs_next_succ:
1927 BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end();
1928 while (PredStack.back().second != PE) {
1929 BasicBlock *BB = *PredStack.back().second++;
1930 if (Visited.insert(BB)) {
1931 PredStack.push_back(std::make_pair(BB, BBStates[BB].pred_begin()));
1932 goto reverse_dfs_next_succ;
1935 ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first);
1940 // Visit the function both top-down and bottom-up.
1942 ObjCARCOpt::Visit(Function &F,
1943 DenseMap<const BasicBlock *, BBState> &BBStates,
1944 MapVector<Value *, RRInfo> &Retains,
1945 DenseMap<Value *, RRInfo> &Releases) {
1947 // Use reverse-postorder traversals, because we magically know that loops
1948 // will be well behaved, i.e. they won't repeatedly call retain on a single
1949 // pointer without doing a release. We can't use the ReversePostOrderTraversal
1950 // class here because we want the reverse-CFG postorder to consider each
1951 // function exit point, and we want to ignore selected cycle edges.
1952 SmallVector<BasicBlock *, 16> PostOrder;
1953 SmallVector<BasicBlock *, 16> ReverseCFGPostOrder;
1954 ComputePostOrders(F, PostOrder, ReverseCFGPostOrder,
1955 NoObjCARCExceptionsMDKind,
1958 // Use reverse-postorder on the reverse CFG for bottom-up.
1959 bool BottomUpNestingDetected = false;
1960 for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
1961 ReverseCFGPostOrder.rbegin(), E = ReverseCFGPostOrder.rend();
1963 BottomUpNestingDetected |= VisitBottomUp(*I, BBStates, Retains);
1965 // Use reverse-postorder for top-down.
1966 bool TopDownNestingDetected = false;
1967 for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
1968 PostOrder.rbegin(), E = PostOrder.rend();
1970 TopDownNestingDetected |= VisitTopDown(*I, BBStates, Releases);
1972 return TopDownNestingDetected && BottomUpNestingDetected;
1975 /// Move the calls in RetainsToMove and ReleasesToMove.
1976 void ObjCARCOpt::MoveCalls(Value *Arg,
1977 RRInfo &RetainsToMove,
1978 RRInfo &ReleasesToMove,
1979 MapVector<Value *, RRInfo> &Retains,
1980 DenseMap<Value *, RRInfo> &Releases,
1981 SmallVectorImpl<Instruction *> &DeadInsts,
1983 Type *ArgTy = Arg->getType();
1984 Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext()));
1986 // Insert the new retain and release calls.
1987 for (SmallPtrSet<Instruction *, 2>::const_iterator
1988 PI = ReleasesToMove.ReverseInsertPts.begin(),
1989 PE = ReleasesToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
1990 Instruction *InsertPt = *PI;
1991 Value *MyArg = ArgTy == ParamTy ? Arg :
1992 new BitCastInst(Arg, ParamTy, "", InsertPt);
1994 CallInst::Create(RetainsToMove.IsRetainBlock ?
1995 getRetainBlockCallee(M) : getRetainCallee(M),
1996 MyArg, "", InsertPt);
1997 Call->setDoesNotThrow();
1998 if (RetainsToMove.IsRetainBlock)
1999 Call->setMetadata(CopyOnEscapeMDKind,
2000 MDNode::get(M->getContext(), ArrayRef<Value *>()));
2002 Call->setTailCall();
2004 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Inserting new Release: " << *Call
2006 " At insertion point: " << *InsertPt
2009 for (SmallPtrSet<Instruction *, 2>::const_iterator
2010 PI = RetainsToMove.ReverseInsertPts.begin(),
2011 PE = RetainsToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
2012 Instruction *InsertPt = *PI;
2013 Value *MyArg = ArgTy == ParamTy ? Arg :
2014 new BitCastInst(Arg, ParamTy, "", InsertPt);
2015 CallInst *Call = CallInst::Create(getReleaseCallee(M), MyArg,
2017 // Attach a clang.imprecise_release metadata tag, if appropriate.
2018 if (MDNode *M = ReleasesToMove.ReleaseMetadata)
2019 Call->setMetadata(ImpreciseReleaseMDKind, M);
2020 Call->setDoesNotThrow();
2021 if (ReleasesToMove.IsTailCallRelease)
2022 Call->setTailCall();
2024 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Inserting new Retain: " << *Call
2026 " At insertion point: " << *InsertPt
2030 // Delete the original retain and release calls.
2031 for (SmallPtrSet<Instruction *, 2>::const_iterator
2032 AI = RetainsToMove.Calls.begin(),
2033 AE = RetainsToMove.Calls.end(); AI != AE; ++AI) {
2034 Instruction *OrigRetain = *AI;
2035 Retains.blot(OrigRetain);
2036 DeadInsts.push_back(OrigRetain);
2037 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Deleting retain: " << *OrigRetain <<
2040 for (SmallPtrSet<Instruction *, 2>::const_iterator
2041 AI = ReleasesToMove.Calls.begin(),
2042 AE = ReleasesToMove.Calls.end(); AI != AE; ++AI) {
2043 Instruction *OrigRelease = *AI;
2044 Releases.erase(OrigRelease);
2045 DeadInsts.push_back(OrigRelease);
2046 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Deleting release: " << *OrigRelease
2052 ObjCARCOpt::ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState>
2054 MapVector<Value *, RRInfo> &Retains,
2055 DenseMap<Value *, RRInfo> &Releases,
2057 SmallVector<Instruction *, 4> &NewRetains,
2058 SmallVector<Instruction *, 4> &NewReleases,
2059 SmallVector<Instruction *, 8> &DeadInsts,
2060 RRInfo &RetainsToMove,
2061 RRInfo &ReleasesToMove,
2064 bool &AnyPairsCompletelyEliminated) {
2065 // If a pair happens in a region where it is known that the reference count
2066 // is already incremented, we can similarly ignore possible decrements.
2067 bool KnownSafeTD = true, KnownSafeBU = true;
2069 // Connect the dots between the top-down-collected RetainsToMove and
2070 // bottom-up-collected ReleasesToMove to form sets of related calls.
2071 // This is an iterative process so that we connect multiple releases
2072 // to multiple retains if needed.
2073 unsigned OldDelta = 0;
2074 unsigned NewDelta = 0;
2075 unsigned OldCount = 0;
2076 unsigned NewCount = 0;
2077 bool FirstRelease = true;
2078 bool FirstRetain = true;
2080 for (SmallVectorImpl<Instruction *>::const_iterator
2081 NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) {
2082 Instruction *NewRetain = *NI;
2083 MapVector<Value *, RRInfo>::const_iterator It = Retains.find(NewRetain);
2084 assert(It != Retains.end());
2085 const RRInfo &NewRetainRRI = It->second;
2086 KnownSafeTD &= NewRetainRRI.KnownSafe;
2087 for (SmallPtrSet<Instruction *, 2>::const_iterator
2088 LI = NewRetainRRI.Calls.begin(),
2089 LE = NewRetainRRI.Calls.end(); LI != LE; ++LI) {
2090 Instruction *NewRetainRelease = *LI;
2091 DenseMap<Value *, RRInfo>::const_iterator Jt =
2092 Releases.find(NewRetainRelease);
2093 if (Jt == Releases.end())
2095 const RRInfo &NewRetainReleaseRRI = Jt->second;
2096 assert(NewRetainReleaseRRI.Calls.count(NewRetain));
2097 if (ReleasesToMove.Calls.insert(NewRetainRelease)) {
2099 BBStates[NewRetainRelease->getParent()].GetAllPathCount();
2101 // Merge the ReleaseMetadata and IsTailCallRelease values.
2103 ReleasesToMove.ReleaseMetadata =
2104 NewRetainReleaseRRI.ReleaseMetadata;
2105 ReleasesToMove.IsTailCallRelease =
2106 NewRetainReleaseRRI.IsTailCallRelease;
2107 FirstRelease = false;
2109 if (ReleasesToMove.ReleaseMetadata !=
2110 NewRetainReleaseRRI.ReleaseMetadata)
2111 ReleasesToMove.ReleaseMetadata = 0;
2112 if (ReleasesToMove.IsTailCallRelease !=
2113 NewRetainReleaseRRI.IsTailCallRelease)
2114 ReleasesToMove.IsTailCallRelease = false;
2117 // Collect the optimal insertion points.
2119 for (SmallPtrSet<Instruction *, 2>::const_iterator
2120 RI = NewRetainReleaseRRI.ReverseInsertPts.begin(),
2121 RE = NewRetainReleaseRRI.ReverseInsertPts.end();
2123 Instruction *RIP = *RI;
2124 if (ReleasesToMove.ReverseInsertPts.insert(RIP))
2125 NewDelta -= BBStates[RIP->getParent()].GetAllPathCount();
2127 NewReleases.push_back(NewRetainRelease);
2132 if (NewReleases.empty()) break;
2134 // Back the other way.
2135 for (SmallVectorImpl<Instruction *>::const_iterator
2136 NI = NewReleases.begin(), NE = NewReleases.end(); NI != NE; ++NI) {
2137 Instruction *NewRelease = *NI;
2138 DenseMap<Value *, RRInfo>::const_iterator It =
2139 Releases.find(NewRelease);
2140 assert(It != Releases.end());
2141 const RRInfo &NewReleaseRRI = It->second;
2142 KnownSafeBU &= NewReleaseRRI.KnownSafe;
2143 for (SmallPtrSet<Instruction *, 2>::const_iterator
2144 LI = NewReleaseRRI.Calls.begin(),
2145 LE = NewReleaseRRI.Calls.end(); LI != LE; ++LI) {
2146 Instruction *NewReleaseRetain = *LI;
2147 MapVector<Value *, RRInfo>::const_iterator Jt =
2148 Retains.find(NewReleaseRetain);
2149 if (Jt == Retains.end())
2151 const RRInfo &NewReleaseRetainRRI = Jt->second;
2152 assert(NewReleaseRetainRRI.Calls.count(NewRelease));
2153 if (RetainsToMove.Calls.insert(NewReleaseRetain)) {
2154 unsigned PathCount =
2155 BBStates[NewReleaseRetain->getParent()].GetAllPathCount();
2156 OldDelta += PathCount;
2157 OldCount += PathCount;
2159 // Merge the IsRetainBlock values.
2161 RetainsToMove.IsRetainBlock = NewReleaseRetainRRI.IsRetainBlock;
2162 FirstRetain = false;
2163 } else if (ReleasesToMove.IsRetainBlock !=
2164 NewReleaseRetainRRI.IsRetainBlock)
2165 // It's not possible to merge the sequences if one uses
2166 // objc_retain and the other uses objc_retainBlock.
2169 // Collect the optimal insertion points.
2171 for (SmallPtrSet<Instruction *, 2>::const_iterator
2172 RI = NewReleaseRetainRRI.ReverseInsertPts.begin(),
2173 RE = NewReleaseRetainRRI.ReverseInsertPts.end();
2175 Instruction *RIP = *RI;
2176 if (RetainsToMove.ReverseInsertPts.insert(RIP)) {
2177 PathCount = BBStates[RIP->getParent()].GetAllPathCount();
2178 NewDelta += PathCount;
2179 NewCount += PathCount;
2182 NewRetains.push_back(NewReleaseRetain);
2186 NewReleases.clear();
2187 if (NewRetains.empty()) break;
2190 // If the pointer is known incremented or nested, we can safely delete the
2191 // pair regardless of what's between them.
2192 if (KnownSafeTD || KnownSafeBU) {
2193 RetainsToMove.ReverseInsertPts.clear();
2194 ReleasesToMove.ReverseInsertPts.clear();
2197 // Determine whether the new insertion points we computed preserve the
2198 // balance of retain and release calls through the program.
2199 // TODO: If the fully aggressive solution isn't valid, try to find a
2200 // less aggressive solution which is.
2205 // Determine whether the original call points are balanced in the retain and
2206 // release calls through the program. If not, conservatively don't touch
2208 // TODO: It's theoretically possible to do code motion in this case, as
2209 // long as the existing imbalances are maintained.
2214 assert(OldCount != 0 && "Unreachable code?");
2215 NumRRs += OldCount - NewCount;
2216 // Set to true if we completely removed any RR pairs.
2217 AnyPairsCompletelyEliminated = NewCount == 0;
2219 // We can move calls!
2223 /// Identify pairings between the retains and releases, and delete and/or move
2226 ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState>
2228 MapVector<Value *, RRInfo> &Retains,
2229 DenseMap<Value *, RRInfo> &Releases,
2231 bool AnyPairsCompletelyEliminated = false;
2232 RRInfo RetainsToMove;
2233 RRInfo ReleasesToMove;
2234 SmallVector<Instruction *, 4> NewRetains;
2235 SmallVector<Instruction *, 4> NewReleases;
2236 SmallVector<Instruction *, 8> DeadInsts;
2238 // Visit each retain.
2239 for (MapVector<Value *, RRInfo>::const_iterator I = Retains.begin(),
2240 E = Retains.end(); I != E; ++I) {
2241 Value *V = I->first;
2242 if (!V) continue; // blotted
2244 Instruction *Retain = cast<Instruction>(V);
2246 DEBUG(dbgs() << "ObjCARCOpt::PerformCodePlacement: Visiting: " << *Retain
2249 Value *Arg = GetObjCArg(Retain);
2251 // If the object being released is in static or stack storage, we know it's
2252 // not being managed by ObjC reference counting, so we can delete pairs
2253 // regardless of what possible decrements or uses lie between them.
2254 bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg);
2256 // A constant pointer can't be pointing to an object on the heap. It may
2257 // be reference-counted, but it won't be deleted.
2258 if (const LoadInst *LI = dyn_cast<LoadInst>(Arg))
2259 if (const GlobalVariable *GV =
2260 dyn_cast<GlobalVariable>(
2261 StripPointerCastsAndObjCCalls(LI->getPointerOperand())))
2262 if (GV->isConstant())
2265 // Connect the dots between the top-down-collected RetainsToMove and
2266 // bottom-up-collected ReleasesToMove to form sets of related calls.
2267 NewRetains.push_back(Retain);
2268 bool PerformMoveCalls =
2269 ConnectTDBUTraversals(BBStates, Retains, Releases, M, NewRetains,
2270 NewReleases, DeadInsts, RetainsToMove,
2271 ReleasesToMove, Arg, KnownSafe,
2272 AnyPairsCompletelyEliminated);
2274 if (PerformMoveCalls) {
2275 // Ok, everything checks out and we're all set. Let's move/delete some
2277 MoveCalls(Arg, RetainsToMove, ReleasesToMove,
2278 Retains, Releases, DeadInsts, M);
2281 // Clean up state for next retain.
2282 NewReleases.clear();
2284 RetainsToMove.clear();
2285 ReleasesToMove.clear();
2288 // Now that we're done moving everything, we can delete the newly dead
2289 // instructions, as we no longer need them as insert points.
2290 while (!DeadInsts.empty())
2291 EraseInstruction(DeadInsts.pop_back_val());
2293 return AnyPairsCompletelyEliminated;
2296 /// Weak pointer optimizations.
2297 void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
2298 // First, do memdep-style RLE and S2L optimizations. We can't use memdep
2299 // itself because it uses AliasAnalysis and we need to do provenance
2301 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2302 Instruction *Inst = &*I++;
2304 DEBUG(dbgs() << "ObjCARCOpt::OptimizeWeakCalls: Visiting: " << *Inst <<
2307 InstructionClass Class = GetBasicInstructionClass(Inst);
2308 if (Class != IC_LoadWeak && Class != IC_LoadWeakRetained)
2311 // Delete objc_loadWeak calls with no users.
2312 if (Class == IC_LoadWeak && Inst->use_empty()) {
2313 Inst->eraseFromParent();
2317 // TODO: For now, just look for an earlier available version of this value
2318 // within the same block. Theoretically, we could do memdep-style non-local
2319 // analysis too, but that would want caching. A better approach would be to
2320 // use the technique that EarlyCSE uses.
2321 inst_iterator Current = llvm::prior(I);
2322 BasicBlock *CurrentBB = Current.getBasicBlockIterator();
2323 for (BasicBlock::iterator B = CurrentBB->begin(),
2324 J = Current.getInstructionIterator();
2326 Instruction *EarlierInst = &*llvm::prior(J);
2327 InstructionClass EarlierClass = GetInstructionClass(EarlierInst);
2328 switch (EarlierClass) {
2330 case IC_LoadWeakRetained: {
2331 // If this is loading from the same pointer, replace this load's value
2333 CallInst *Call = cast<CallInst>(Inst);
2334 CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2335 Value *Arg = Call->getArgOperand(0);
2336 Value *EarlierArg = EarlierCall->getArgOperand(0);
2337 switch (PA.getAA()->alias(Arg, EarlierArg)) {
2338 case AliasAnalysis::MustAlias:
2340 // If the load has a builtin retain, insert a plain retain for it.
2341 if (Class == IC_LoadWeakRetained) {
2343 CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
2347 // Zap the fully redundant load.
2348 Call->replaceAllUsesWith(EarlierCall);
2349 Call->eraseFromParent();
2351 case AliasAnalysis::MayAlias:
2352 case AliasAnalysis::PartialAlias:
2354 case AliasAnalysis::NoAlias:
2361 // If this is storing to the same pointer and has the same size etc.
2362 // replace this load's value with the stored value.
2363 CallInst *Call = cast<CallInst>(Inst);
2364 CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2365 Value *Arg = Call->getArgOperand(0);
2366 Value *EarlierArg = EarlierCall->getArgOperand(0);
2367 switch (PA.getAA()->alias(Arg, EarlierArg)) {
2368 case AliasAnalysis::MustAlias:
2370 // If the load has a builtin retain, insert a plain retain for it.
2371 if (Class == IC_LoadWeakRetained) {
2373 CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
2377 // Zap the fully redundant load.
2378 Call->replaceAllUsesWith(EarlierCall->getArgOperand(1));
2379 Call->eraseFromParent();
2381 case AliasAnalysis::MayAlias:
2382 case AliasAnalysis::PartialAlias:
2384 case AliasAnalysis::NoAlias:
2391 // TOOD: Grab the copied value.
2393 case IC_AutoreleasepoolPush:
2396 // Weak pointers are only modified through the weak entry points
2397 // (and arbitrary calls, which could call the weak entry points).
2400 // Anything else could modify the weak pointer.
2407 // Then, for each destroyWeak with an alloca operand, check to see if
2408 // the alloca and all its users can be zapped.
2409 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2410 Instruction *Inst = &*I++;
2411 InstructionClass Class = GetBasicInstructionClass(Inst);
2412 if (Class != IC_DestroyWeak)
2415 CallInst *Call = cast<CallInst>(Inst);
2416 Value *Arg = Call->getArgOperand(0);
2417 if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) {
2418 for (Value::use_iterator UI = Alloca->use_begin(),
2419 UE = Alloca->use_end(); UI != UE; ++UI) {
2420 const Instruction *UserInst = cast<Instruction>(*UI);
2421 switch (GetBasicInstructionClass(UserInst)) {
2424 case IC_DestroyWeak:
2431 for (Value::use_iterator UI = Alloca->use_begin(),
2432 UE = Alloca->use_end(); UI != UE; ) {
2433 CallInst *UserInst = cast<CallInst>(*UI++);
2434 switch (GetBasicInstructionClass(UserInst)) {
2437 // These functions return their second argument.
2438 UserInst->replaceAllUsesWith(UserInst->getArgOperand(1));
2440 case IC_DestroyWeak:
2444 llvm_unreachable("alloca really is used!");
2446 UserInst->eraseFromParent();
2448 Alloca->eraseFromParent();
2453 DEBUG(dbgs() << "ObjCARCOpt::OptimizeWeakCalls: Finished List.\n\n");
2457 /// Identify program paths which execute sequences of retains and releases which
2458 /// can be eliminated.
2459 bool ObjCARCOpt::OptimizeSequences(Function &F) {
2460 /// Releases, Retains - These are used to store the results of the main flow
2461 /// analysis. These use Value* as the key instead of Instruction* so that the
2462 /// map stays valid when we get around to rewriting code and calls get
2463 /// replaced by arguments.
2464 DenseMap<Value *, RRInfo> Releases;
2465 MapVector<Value *, RRInfo> Retains;
2467 /// This is used during the traversal of the function to track the
2468 /// states for each identified object at each block.
2469 DenseMap<const BasicBlock *, BBState> BBStates;
2471 // Analyze the CFG of the function, and all instructions.
2472 bool NestingDetected = Visit(F, BBStates, Retains, Releases);
2475 return PerformCodePlacement(BBStates, Retains, Releases, F.getParent()) &&
2479 /// Look for this pattern:
2481 /// %call = call i8* @something(...)
2482 /// %2 = call i8* @objc_retain(i8* %call)
2483 /// %3 = call i8* @objc_autorelease(i8* %2)
2486 /// And delete the retain and autorelease.
2488 /// Otherwise if it's just this:
2490 /// %3 = call i8* @objc_autorelease(i8* %2)
2493 /// convert the autorelease to autoreleaseRV.
2494 void ObjCARCOpt::OptimizeReturns(Function &F) {
2495 if (!F.getReturnType()->isPointerTy())
2498 SmallPtrSet<Instruction *, 4> DependingInstructions;
2499 SmallPtrSet<const BasicBlock *, 4> Visited;
2500 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
2501 BasicBlock *BB = FI;
2502 ReturnInst *Ret = dyn_cast<ReturnInst>(&BB->back());
2504 DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Visiting: " << *Ret << "\n");
2508 const Value *Arg = StripPointerCastsAndObjCCalls(Ret->getOperand(0));
2509 FindDependencies(NeedsPositiveRetainCount, Arg,
2510 BB, Ret, DependingInstructions, Visited, PA);
2511 if (DependingInstructions.size() != 1)
2515 CallInst *Autorelease =
2516 dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
2519 InstructionClass AutoreleaseClass = GetBasicInstructionClass(Autorelease);
2520 if (!IsAutorelease(AutoreleaseClass))
2522 if (GetObjCArg(Autorelease) != Arg)
2525 DependingInstructions.clear();
2528 // Check that there is nothing that can affect the reference
2529 // count between the autorelease and the retain.
2530 FindDependencies(CanChangeRetainCount, Arg,
2531 BB, Autorelease, DependingInstructions, Visited, PA);
2532 if (DependingInstructions.size() != 1)
2537 dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
2539 // Check that we found a retain with the same argument.
2541 !IsRetain(GetBasicInstructionClass(Retain)) ||
2542 GetObjCArg(Retain) != Arg)
2545 DependingInstructions.clear();
2548 // Convert the autorelease to an autoreleaseRV, since it's
2549 // returning the value.
2550 if (AutoreleaseClass == IC_Autorelease) {
2551 DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Converting autorelease "
2552 "=> autoreleaseRV since it's returning a value.\n"
2553 " In: " << *Autorelease
2555 Autorelease->setCalledFunction(getAutoreleaseRVCallee(F.getParent()));
2556 DEBUG(dbgs() << " Out: " << *Autorelease
2558 Autorelease->setTailCall(); // Always tail call autoreleaseRV.
2559 AutoreleaseClass = IC_AutoreleaseRV;
2562 // Check that there is nothing that can affect the reference
2563 // count between the retain and the call.
2564 // Note that Retain need not be in BB.
2565 FindDependencies(CanChangeRetainCount, Arg, Retain->getParent(), Retain,
2566 DependingInstructions, Visited, PA);
2567 if (DependingInstructions.size() != 1)
2572 dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
2574 // Check that the pointer is the return value of the call.
2575 if (!Call || Arg != Call)
2578 // Check that the call is a regular call.
2579 InstructionClass Class = GetBasicInstructionClass(Call);
2580 if (Class != IC_CallOrUser && Class != IC_Call)
2583 // If so, we can zap the retain and autorelease.
2586 DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Erasing: " << *Retain
2588 << *Autorelease << "\n");
2589 EraseInstruction(Retain);
2590 EraseInstruction(Autorelease);
2596 DependingInstructions.clear();
2600 DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Finished List.\n\n");
2604 bool ObjCARCOpt::doInitialization(Module &M) {
2608 // If nothing in the Module uses ARC, don't do anything.
2609 Run = ModuleHasARC(M);
2613 // Identify the imprecise release metadata kind.
2614 ImpreciseReleaseMDKind =
2615 M.getContext().getMDKindID("clang.imprecise_release");
2616 CopyOnEscapeMDKind =
2617 M.getContext().getMDKindID("clang.arc.copy_on_escape");
2618 NoObjCARCExceptionsMDKind =
2619 M.getContext().getMDKindID("clang.arc.no_objc_arc_exceptions");
2621 // Intuitively, objc_retain and others are nocapture, however in practice
2622 // they are not, because they return their argument value. And objc_release
2623 // calls finalizers which can have arbitrary side effects.
2625 // These are initialized lazily.
2627 AutoreleaseRVCallee = 0;
2630 RetainBlockCallee = 0;
2631 AutoreleaseCallee = 0;
2636 bool ObjCARCOpt::runOnFunction(Function &F) {
2640 // If nothing in the Module uses ARC, don't do anything.
2646 DEBUG(dbgs() << "ObjCARCOpt: Visiting Function: " << F.getName() << "\n");
2648 PA.setAA(&getAnalysis<AliasAnalysis>());
2650 // This pass performs several distinct transformations. As a compile-time aid
2651 // when compiling code that isn't ObjC, skip these if the relevant ObjC
2652 // library functions aren't declared.
2654 // Preliminary optimizations. This also computs UsedInThisFunction.
2655 OptimizeIndividualCalls(F);
2657 // Optimizations for weak pointers.
2658 if (UsedInThisFunction & ((1 << IC_LoadWeak) |
2659 (1 << IC_LoadWeakRetained) |
2660 (1 << IC_StoreWeak) |
2661 (1 << IC_InitWeak) |
2662 (1 << IC_CopyWeak) |
2663 (1 << IC_MoveWeak) |
2664 (1 << IC_DestroyWeak)))
2665 OptimizeWeakCalls(F);
2667 // Optimizations for retain+release pairs.
2668 if (UsedInThisFunction & ((1 << IC_Retain) |
2669 (1 << IC_RetainRV) |
2670 (1 << IC_RetainBlock)))
2671 if (UsedInThisFunction & (1 << IC_Release))
2672 // Run OptimizeSequences until it either stops making changes or
2673 // no retain+release pair nesting is detected.
2674 while (OptimizeSequences(F)) {}
2676 // Optimizations if objc_autorelease is used.
2677 if (UsedInThisFunction & ((1 << IC_Autorelease) |
2678 (1 << IC_AutoreleaseRV)))
2681 DEBUG(dbgs() << "\n");
2686 void ObjCARCOpt::releaseMemory() {