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.
214 case IC_IntrinsicUser:
215 // Use by the use intrinsic is not an escape.
219 // Use by an instruction which copies the value is an escape if the
220 // result is an escape.
221 if (isa<BitCastInst>(UUser) || isa<GetElementPtrInst>(UUser) ||
222 isa<PHINode>(UUser) || isa<SelectInst>(UUser)) {
224 if (VisitedSet.insert(UUser)) {
225 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: User copies value. "
226 "Ptr escapes if result escapes. Adding to list.\n");
227 Worklist.push_back(UUser);
229 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Already visited node."
234 // Use by a load is not an escape.
235 if (isa<LoadInst>(UUser))
237 // Use by a store is not an escape if the use is the address.
238 if (const StoreInst *SI = dyn_cast<StoreInst>(UUser))
239 if (V != SI->getValueOperand())
243 // Regular calls and other stuff are not considered escapes.
246 // Otherwise, conservatively assume an escape.
247 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Assuming ptr escapes.\n");
250 } while (!Worklist.empty());
253 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Ptr does not escape.\n");
259 /// \defgroup ARCOpt ARC Optimization.
262 // TODO: On code like this:
265 // stuff_that_cannot_release()
266 // objc_autorelease(%x)
267 // stuff_that_cannot_release()
269 // stuff_that_cannot_release()
270 // objc_autorelease(%x)
272 // The second retain and autorelease can be deleted.
274 // TODO: It should be possible to delete
275 // objc_autoreleasePoolPush and objc_autoreleasePoolPop
276 // pairs if nothing is actually autoreleased between them. Also, autorelease
277 // calls followed by objc_autoreleasePoolPop calls (perhaps in ObjC++ code
278 // after inlining) can be turned into plain release calls.
280 // TODO: Critical-edge splitting. If the optimial insertion point is
281 // a critical edge, the current algorithm has to fail, because it doesn't
282 // know how to split edges. It should be possible to make the optimizer
283 // think in terms of edges, rather than blocks, and then split critical
286 // TODO: OptimizeSequences could generalized to be Interprocedural.
288 // TODO: Recognize that a bunch of other objc runtime calls have
289 // non-escaping arguments and non-releasing arguments, and may be
290 // non-autoreleasing.
292 // TODO: Sink autorelease calls as far as possible. Unfortunately we
293 // usually can't sink them past other calls, which would be the main
294 // case where it would be useful.
296 // TODO: The pointer returned from objc_loadWeakRetained is retained.
298 // TODO: Delete release+retain pairs (rare).
300 STATISTIC(NumNoops, "Number of no-op objc calls eliminated");
301 STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated");
302 STATISTIC(NumAutoreleases,"Number of autoreleases converted to releases");
303 STATISTIC(NumRets, "Number of return value forwarding "
304 "retain+autoreleaes eliminated");
305 STATISTIC(NumRRs, "Number of retain+release paths eliminated");
306 STATISTIC(NumPeeps, "Number of calls peephole-optimized");
311 /// \brief A sequence of states that a pointer may go through in which an
312 /// objc_retain and objc_release are actually needed.
315 S_Retain, ///< objc_retain(x).
316 S_CanRelease, ///< foo(x) -- x could possibly see a ref count decrement.
317 S_Use, ///< any use of x.
318 S_Stop, ///< like S_Release, but code motion is stopped.
319 S_Release, ///< objc_release(x).
320 S_MovableRelease ///< objc_release(x), !clang.imprecise_release.
323 raw_ostream &operator<<(raw_ostream &OS, const Sequence S)
324 LLVM_ATTRIBUTE_UNUSED;
325 raw_ostream &operator<<(raw_ostream &OS, const Sequence S) {
328 return OS << "S_None";
330 return OS << "S_Retain";
332 return OS << "S_CanRelease";
334 return OS << "S_Use";
336 return OS << "S_Release";
337 case S_MovableRelease:
338 return OS << "S_MovableRelease";
340 return OS << "S_Stop";
342 llvm_unreachable("Unknown sequence type.");
346 static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) {
350 if (A == S_None || B == S_None)
353 if (A > B) std::swap(A, B);
355 // Choose the side which is further along in the sequence.
356 if ((A == S_Retain || A == S_CanRelease) &&
357 (B == S_CanRelease || B == S_Use))
360 // Choose the side which is further along in the sequence.
361 if ((A == S_Use || A == S_CanRelease) &&
362 (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease))
364 // If both sides are releases, choose the more conservative one.
365 if (A == S_Stop && (B == S_Release || B == S_MovableRelease))
367 if (A == S_Release && B == S_MovableRelease)
375 /// \brief Unidirectional information about either a
376 /// retain-decrement-use-release sequence or release-use-decrement-retain
377 /// reverese sequence.
379 /// After an objc_retain, the reference count of the referenced
380 /// object is known to be positive. Similarly, before an objc_release, the
381 /// reference count of the referenced object is known to be positive. If
382 /// there are retain-release pairs in code regions where the retain count
383 /// is known to be positive, they can be eliminated, regardless of any side
384 /// effects between them.
386 /// Also, a retain+release pair nested within another retain+release
387 /// pair all on the known same pointer value can be eliminated, regardless
388 /// of any intervening side effects.
390 /// KnownSafe is true when either of these conditions is satisfied.
393 /// True if the Calls are objc_retainBlock calls (as opposed to objc_retain
397 /// True of the objc_release calls are all marked with the "tail" keyword.
398 bool IsTailCallRelease;
400 /// If the Calls are objc_release calls and they all have a
401 /// clang.imprecise_release tag, this is the metadata tag.
402 MDNode *ReleaseMetadata;
404 /// For a top-down sequence, the set of objc_retains or
405 /// objc_retainBlocks. For bottom-up, the set of objc_releases.
406 SmallPtrSet<Instruction *, 2> Calls;
408 /// The set of optimal insert positions for moving calls in the opposite
410 SmallPtrSet<Instruction *, 2> ReverseInsertPts;
413 KnownSafe(false), IsRetainBlock(false),
414 IsTailCallRelease(false),
415 ReleaseMetadata(0) {}
421 void RRInfo::clear() {
423 IsRetainBlock = false;
424 IsTailCallRelease = false;
427 ReverseInsertPts.clear();
431 /// \brief This class summarizes several per-pointer runtime properties which
432 /// are propogated through the flow graph.
434 /// True if the reference count is known to be incremented.
435 bool KnownPositiveRefCount;
437 /// True of we've seen an opportunity for partial RR elimination, such as
438 /// pushing calls into a CFG triangle or into one side of a CFG diamond.
441 /// The current position in the sequence.
445 /// Unidirectional information about the current sequence.
447 /// TODO: Encapsulate this better.
450 PtrState() : KnownPositiveRefCount(false), Partial(false),
453 void SetKnownPositiveRefCount() {
454 KnownPositiveRefCount = true;
457 void ClearKnownPositiveRefCount() {
458 KnownPositiveRefCount = false;
461 bool HasKnownPositiveRefCount() const {
462 return KnownPositiveRefCount;
465 void SetSeq(Sequence NewSeq) {
469 Sequence GetSeq() const {
473 void ClearSequenceProgress() {
474 ResetSequenceProgress(S_None);
477 void ResetSequenceProgress(Sequence NewSeq) {
483 void Merge(const PtrState &Other, bool TopDown);
488 PtrState::Merge(const PtrState &Other, bool TopDown) {
489 Seq = MergeSeqs(Seq, Other.Seq, TopDown);
490 KnownPositiveRefCount = KnownPositiveRefCount && Other.KnownPositiveRefCount;
492 // We can't merge a plain objc_retain with an objc_retainBlock.
493 if (RRI.IsRetainBlock != Other.RRI.IsRetainBlock)
496 // If we're not in a sequence (anymore), drop all associated state.
500 } else if (Partial || Other.Partial) {
501 // If we're doing a merge on a path that's previously seen a partial
502 // merge, conservatively drop the sequence, to avoid doing partial
503 // RR elimination. If the branch predicates for the two merge differ,
504 // mixing them is unsafe.
505 ClearSequenceProgress();
507 // Conservatively merge the ReleaseMetadata information.
508 if (RRI.ReleaseMetadata != Other.RRI.ReleaseMetadata)
509 RRI.ReleaseMetadata = 0;
511 RRI.KnownSafe = RRI.KnownSafe && Other.RRI.KnownSafe;
512 RRI.IsTailCallRelease = RRI.IsTailCallRelease &&
513 Other.RRI.IsTailCallRelease;
514 RRI.Calls.insert(Other.RRI.Calls.begin(), Other.RRI.Calls.end());
516 // Merge the insert point sets. If there are any differences,
517 // that makes this a partial merge.
518 Partial = RRI.ReverseInsertPts.size() != Other.RRI.ReverseInsertPts.size();
519 for (SmallPtrSet<Instruction *, 2>::const_iterator
520 I = Other.RRI.ReverseInsertPts.begin(),
521 E = Other.RRI.ReverseInsertPts.end(); I != E; ++I)
522 Partial |= RRI.ReverseInsertPts.insert(*I);
527 /// \brief Per-BasicBlock state.
529 /// The number of unique control paths from the entry which can reach this
531 unsigned TopDownPathCount;
533 /// The number of unique control paths to exits from this block.
534 unsigned BottomUpPathCount;
536 /// A type for PerPtrTopDown and PerPtrBottomUp.
537 typedef MapVector<const Value *, PtrState> MapTy;
539 /// The top-down traversal uses this to record information known about a
540 /// pointer at the bottom of each block.
543 /// The bottom-up traversal uses this to record information known about a
544 /// pointer at the top of each block.
545 MapTy PerPtrBottomUp;
547 /// Effective predecessors of the current block ignoring ignorable edges and
548 /// ignored backedges.
549 SmallVector<BasicBlock *, 2> Preds;
550 /// Effective successors of the current block ignoring ignorable edges and
551 /// ignored backedges.
552 SmallVector<BasicBlock *, 2> Succs;
555 BBState() : TopDownPathCount(0), BottomUpPathCount(0) {}
557 typedef MapTy::iterator ptr_iterator;
558 typedef MapTy::const_iterator ptr_const_iterator;
560 ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); }
561 ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); }
562 ptr_const_iterator top_down_ptr_begin() const {
563 return PerPtrTopDown.begin();
565 ptr_const_iterator top_down_ptr_end() const {
566 return PerPtrTopDown.end();
569 ptr_iterator bottom_up_ptr_begin() { return PerPtrBottomUp.begin(); }
570 ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); }
571 ptr_const_iterator bottom_up_ptr_begin() const {
572 return PerPtrBottomUp.begin();
574 ptr_const_iterator bottom_up_ptr_end() const {
575 return PerPtrBottomUp.end();
578 /// Mark this block as being an entry block, which has one path from the
579 /// entry by definition.
580 void SetAsEntry() { TopDownPathCount = 1; }
582 /// Mark this block as being an exit block, which has one path to an exit by
584 void SetAsExit() { BottomUpPathCount = 1; }
586 PtrState &getPtrTopDownState(const Value *Arg) {
587 return PerPtrTopDown[Arg];
590 PtrState &getPtrBottomUpState(const Value *Arg) {
591 return PerPtrBottomUp[Arg];
594 void clearBottomUpPointers() {
595 PerPtrBottomUp.clear();
598 void clearTopDownPointers() {
599 PerPtrTopDown.clear();
602 void InitFromPred(const BBState &Other);
603 void InitFromSucc(const BBState &Other);
604 void MergePred(const BBState &Other);
605 void MergeSucc(const BBState &Other);
607 /// Return the number of possible unique paths from an entry to an exit
608 /// which pass through this block. This is only valid after both the
609 /// top-down and bottom-up traversals are complete.
610 unsigned GetAllPathCount() const {
611 assert(TopDownPathCount != 0);
612 assert(BottomUpPathCount != 0);
613 return TopDownPathCount * BottomUpPathCount;
616 // Specialized CFG utilities.
617 typedef SmallVectorImpl<BasicBlock *>::const_iterator edge_iterator;
618 edge_iterator pred_begin() { return Preds.begin(); }
619 edge_iterator pred_end() { return Preds.end(); }
620 edge_iterator succ_begin() { return Succs.begin(); }
621 edge_iterator succ_end() { return Succs.end(); }
623 void addSucc(BasicBlock *Succ) { Succs.push_back(Succ); }
624 void addPred(BasicBlock *Pred) { Preds.push_back(Pred); }
626 bool isExit() const { return Succs.empty(); }
630 void BBState::InitFromPred(const BBState &Other) {
631 PerPtrTopDown = Other.PerPtrTopDown;
632 TopDownPathCount = Other.TopDownPathCount;
635 void BBState::InitFromSucc(const BBState &Other) {
636 PerPtrBottomUp = Other.PerPtrBottomUp;
637 BottomUpPathCount = Other.BottomUpPathCount;
640 /// The top-down traversal uses this to merge information about predecessors to
641 /// form the initial state for a new block.
642 void BBState::MergePred(const BBState &Other) {
643 // Other.TopDownPathCount can be 0, in which case it is either dead or a
644 // loop backedge. Loop backedges are special.
645 TopDownPathCount += Other.TopDownPathCount;
647 // Check for overflow. If we have overflow, fall back to conservative
649 if (TopDownPathCount < Other.TopDownPathCount) {
650 clearTopDownPointers();
654 // For each entry in the other set, if our set has an entry with the same key,
655 // merge the entries. Otherwise, copy the entry and merge it with an empty
657 for (ptr_const_iterator MI = Other.top_down_ptr_begin(),
658 ME = Other.top_down_ptr_end(); MI != ME; ++MI) {
659 std::pair<ptr_iterator, bool> Pair = PerPtrTopDown.insert(*MI);
660 Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
664 // For each entry in our set, if the other set doesn't have an entry with the
665 // same key, force it to merge with an empty entry.
666 for (ptr_iterator MI = top_down_ptr_begin(),
667 ME = top_down_ptr_end(); MI != ME; ++MI)
668 if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end())
669 MI->second.Merge(PtrState(), /*TopDown=*/true);
672 /// The bottom-up traversal uses this to merge information about successors to
673 /// form the initial state for a new block.
674 void BBState::MergeSucc(const BBState &Other) {
675 // Other.BottomUpPathCount can be 0, in which case it is either dead or a
676 // loop backedge. Loop backedges are special.
677 BottomUpPathCount += Other.BottomUpPathCount;
679 // Check for overflow. If we have overflow, fall back to conservative
681 if (BottomUpPathCount < Other.BottomUpPathCount) {
682 clearBottomUpPointers();
686 // For each entry in the other set, if our set has an entry with the
687 // same key, merge the entries. Otherwise, copy the entry and merge
688 // it with an empty entry.
689 for (ptr_const_iterator MI = Other.bottom_up_ptr_begin(),
690 ME = Other.bottom_up_ptr_end(); MI != ME; ++MI) {
691 std::pair<ptr_iterator, bool> Pair = PerPtrBottomUp.insert(*MI);
692 Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
696 // For each entry in our set, if the other set doesn't have an entry
697 // with the same key, force it to merge with an empty entry.
698 for (ptr_iterator MI = bottom_up_ptr_begin(),
699 ME = bottom_up_ptr_end(); MI != ME; ++MI)
700 if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end())
701 MI->second.Merge(PtrState(), /*TopDown=*/false);
705 /// \brief The main ARC optimization pass.
706 class ObjCARCOpt : public FunctionPass {
708 ProvenanceAnalysis PA;
710 /// A flag indicating whether this optimization pass should run.
713 /// Declarations for ObjC runtime functions, for use in creating calls to
714 /// them. These are initialized lazily to avoid cluttering up the Module
715 /// with unused declarations.
717 /// Declaration for ObjC runtime function
718 /// objc_retainAutoreleasedReturnValue.
719 Constant *RetainRVCallee;
720 /// Declaration for ObjC runtime function objc_autoreleaseReturnValue.
721 Constant *AutoreleaseRVCallee;
722 /// Declaration for ObjC runtime function objc_release.
723 Constant *ReleaseCallee;
724 /// Declaration for ObjC runtime function objc_retain.
725 Constant *RetainCallee;
726 /// Declaration for ObjC runtime function objc_retainBlock.
727 Constant *RetainBlockCallee;
728 /// Declaration for ObjC runtime function objc_autorelease.
729 Constant *AutoreleaseCallee;
731 /// Flags which determine whether each of the interesting runtine functions
732 /// is in fact used in the current function.
733 unsigned UsedInThisFunction;
735 /// The Metadata Kind for clang.imprecise_release metadata.
736 unsigned ImpreciseReleaseMDKind;
738 /// The Metadata Kind for clang.arc.copy_on_escape metadata.
739 unsigned CopyOnEscapeMDKind;
741 /// The Metadata Kind for clang.arc.no_objc_arc_exceptions metadata.
742 unsigned NoObjCARCExceptionsMDKind;
744 Constant *getRetainRVCallee(Module *M);
745 Constant *getAutoreleaseRVCallee(Module *M);
746 Constant *getReleaseCallee(Module *M);
747 Constant *getRetainCallee(Module *M);
748 Constant *getRetainBlockCallee(Module *M);
749 Constant *getAutoreleaseCallee(Module *M);
751 bool IsRetainBlockOptimizable(const Instruction *Inst);
753 void OptimizeRetainCall(Function &F, Instruction *Retain);
754 bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV);
755 void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV,
756 InstructionClass &Class);
757 void OptimizeIndividualCalls(Function &F);
759 void CheckForCFGHazards(const BasicBlock *BB,
760 DenseMap<const BasicBlock *, BBState> &BBStates,
761 BBState &MyStates) const;
762 bool VisitInstructionBottomUp(Instruction *Inst,
764 MapVector<Value *, RRInfo> &Retains,
766 bool VisitBottomUp(BasicBlock *BB,
767 DenseMap<const BasicBlock *, BBState> &BBStates,
768 MapVector<Value *, RRInfo> &Retains);
769 bool VisitInstructionTopDown(Instruction *Inst,
770 DenseMap<Value *, RRInfo> &Releases,
772 bool VisitTopDown(BasicBlock *BB,
773 DenseMap<const BasicBlock *, BBState> &BBStates,
774 DenseMap<Value *, RRInfo> &Releases);
775 bool Visit(Function &F,
776 DenseMap<const BasicBlock *, BBState> &BBStates,
777 MapVector<Value *, RRInfo> &Retains,
778 DenseMap<Value *, RRInfo> &Releases);
780 void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove,
781 MapVector<Value *, RRInfo> &Retains,
782 DenseMap<Value *, RRInfo> &Releases,
783 SmallVectorImpl<Instruction *> &DeadInsts,
786 bool ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState> &BBStates,
787 MapVector<Value *, RRInfo> &Retains,
788 DenseMap<Value *, RRInfo> &Releases,
790 SmallVector<Instruction *, 4> &NewRetains,
791 SmallVector<Instruction *, 4> &NewReleases,
792 SmallVector<Instruction *, 8> &DeadInsts,
793 RRInfo &RetainsToMove,
794 RRInfo &ReleasesToMove,
797 bool &AnyPairsCompletelyEliminated);
799 bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates,
800 MapVector<Value *, RRInfo> &Retains,
801 DenseMap<Value *, RRInfo> &Releases,
804 void OptimizeWeakCalls(Function &F);
806 bool OptimizeSequences(Function &F);
808 void OptimizeReturns(Function &F);
810 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
811 virtual bool doInitialization(Module &M);
812 virtual bool runOnFunction(Function &F);
813 virtual void releaseMemory();
817 ObjCARCOpt() : FunctionPass(ID) {
818 initializeObjCARCOptPass(*PassRegistry::getPassRegistry());
823 char ObjCARCOpt::ID = 0;
824 INITIALIZE_PASS_BEGIN(ObjCARCOpt,
825 "objc-arc", "ObjC ARC optimization", false, false)
826 INITIALIZE_PASS_DEPENDENCY(ObjCARCAliasAnalysis)
827 INITIALIZE_PASS_END(ObjCARCOpt,
828 "objc-arc", "ObjC ARC optimization", false, false)
830 Pass *llvm::createObjCARCOptPass() {
831 return new ObjCARCOpt();
834 void ObjCARCOpt::getAnalysisUsage(AnalysisUsage &AU) const {
835 AU.addRequired<ObjCARCAliasAnalysis>();
836 AU.addRequired<AliasAnalysis>();
837 // ARC optimization doesn't currently split critical edges.
838 AU.setPreservesCFG();
841 bool ObjCARCOpt::IsRetainBlockOptimizable(const Instruction *Inst) {
842 // Without the magic metadata tag, we have to assume this might be an
843 // objc_retainBlock call inserted to convert a block pointer to an id,
844 // in which case it really is needed.
845 if (!Inst->getMetadata(CopyOnEscapeMDKind))
848 // If the pointer "escapes" (not including being used in a call),
849 // the copy may be needed.
850 if (DoesRetainableObjPtrEscape(Inst))
853 // Otherwise, it's not needed.
857 Constant *ObjCARCOpt::getRetainRVCallee(Module *M) {
858 if (!RetainRVCallee) {
859 LLVMContext &C = M->getContext();
860 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
861 Type *Params[] = { I8X };
862 FunctionType *FTy = FunctionType::get(I8X, Params, /*isVarArg=*/false);
863 AttributeSet Attribute =
864 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
865 Attribute::NoUnwind);
867 M->getOrInsertFunction("objc_retainAutoreleasedReturnValue", FTy,
870 return RetainRVCallee;
873 Constant *ObjCARCOpt::getAutoreleaseRVCallee(Module *M) {
874 if (!AutoreleaseRVCallee) {
875 LLVMContext &C = M->getContext();
876 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
877 Type *Params[] = { I8X };
878 FunctionType *FTy = FunctionType::get(I8X, Params, /*isVarArg=*/false);
879 AttributeSet Attribute =
880 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
881 Attribute::NoUnwind);
882 AutoreleaseRVCallee =
883 M->getOrInsertFunction("objc_autoreleaseReturnValue", FTy,
886 return AutoreleaseRVCallee;
889 Constant *ObjCARCOpt::getReleaseCallee(Module *M) {
890 if (!ReleaseCallee) {
891 LLVMContext &C = M->getContext();
892 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
893 AttributeSet Attribute =
894 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
895 Attribute::NoUnwind);
897 M->getOrInsertFunction(
899 FunctionType::get(Type::getVoidTy(C), Params, /*isVarArg=*/false),
902 return ReleaseCallee;
905 Constant *ObjCARCOpt::getRetainCallee(Module *M) {
907 LLVMContext &C = M->getContext();
908 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
909 AttributeSet Attribute =
910 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
911 Attribute::NoUnwind);
913 M->getOrInsertFunction(
915 FunctionType::get(Params[0], Params, /*isVarArg=*/false),
921 Constant *ObjCARCOpt::getRetainBlockCallee(Module *M) {
922 if (!RetainBlockCallee) {
923 LLVMContext &C = M->getContext();
924 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
925 // objc_retainBlock is not nounwind because it calls user copy constructors
926 // which could theoretically throw.
928 M->getOrInsertFunction(
930 FunctionType::get(Params[0], Params, /*isVarArg=*/false),
933 return RetainBlockCallee;
936 Constant *ObjCARCOpt::getAutoreleaseCallee(Module *M) {
937 if (!AutoreleaseCallee) {
938 LLVMContext &C = M->getContext();
939 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
940 AttributeSet Attribute =
941 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
942 Attribute::NoUnwind);
944 M->getOrInsertFunction(
946 FunctionType::get(Params[0], Params, /*isVarArg=*/false),
949 return AutoreleaseCallee;
952 /// Turn objc_retain into objc_retainAutoreleasedReturnValue if the operand is a
955 ObjCARCOpt::OptimizeRetainCall(Function &F, Instruction *Retain) {
956 ImmutableCallSite CS(GetObjCArg(Retain));
957 const Instruction *Call = CS.getInstruction();
959 if (Call->getParent() != Retain->getParent()) return;
961 // Check that the call is next to the retain.
962 BasicBlock::const_iterator I = Call;
964 while (isNoopInstruction(I)) ++I;
968 // Turn it to an objc_retainAutoreleasedReturnValue..
972 DEBUG(dbgs() << "ObjCARCOpt::OptimizeRetainCall: Transforming "
973 "objc_retain => objc_retainAutoreleasedReturnValue"
974 " since the operand is a return value.\n"
978 cast<CallInst>(Retain)->setCalledFunction(getRetainRVCallee(F.getParent()));
980 DEBUG(dbgs() << " New: "
984 /// Turn objc_retainAutoreleasedReturnValue into objc_retain if the operand is
985 /// not a return value. Or, if it can be paired with an
986 /// objc_autoreleaseReturnValue, delete the pair and return true.
988 ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) {
989 // Check for the argument being from an immediately preceding call or invoke.
990 const Value *Arg = GetObjCArg(RetainRV);
991 ImmutableCallSite CS(Arg);
992 if (const Instruction *Call = CS.getInstruction()) {
993 if (Call->getParent() == RetainRV->getParent()) {
994 BasicBlock::const_iterator I = Call;
996 while (isNoopInstruction(I)) ++I;
999 } else if (const InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
1000 BasicBlock *RetainRVParent = RetainRV->getParent();
1001 if (II->getNormalDest() == RetainRVParent) {
1002 BasicBlock::const_iterator I = RetainRVParent->begin();
1003 while (isNoopInstruction(I)) ++I;
1004 if (&*I == RetainRV)
1010 // Check for being preceded by an objc_autoreleaseReturnValue on the same
1011 // pointer. In this case, we can delete the pair.
1012 BasicBlock::iterator I = RetainRV, Begin = RetainRV->getParent()->begin();
1014 do --I; while (I != Begin && isNoopInstruction(I));
1015 if (GetBasicInstructionClass(I) == IC_AutoreleaseRV &&
1016 GetObjCArg(I) == Arg) {
1020 DEBUG(dbgs() << "ObjCARCOpt::OptimizeRetainRVCall: Erasing " << *I << "\n"
1021 << " Erasing " << *RetainRV
1024 EraseInstruction(I);
1025 EraseInstruction(RetainRV);
1030 // Turn it to a plain objc_retain.
1034 DEBUG(dbgs() << "ObjCARCOpt::OptimizeRetainRVCall: Transforming "
1035 "objc_retainAutoreleasedReturnValue => "
1036 "objc_retain since the operand is not a return value.\n"
1038 << *RetainRV << "\n");
1040 cast<CallInst>(RetainRV)->setCalledFunction(getRetainCallee(F.getParent()));
1042 DEBUG(dbgs() << " New: "
1043 << *RetainRV << "\n");
1048 /// Turn objc_autoreleaseReturnValue into objc_autorelease if the result is not
1049 /// used as a return value.
1051 ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV,
1052 InstructionClass &Class) {
1053 // Check for a return of the pointer value.
1054 const Value *Ptr = GetObjCArg(AutoreleaseRV);
1055 SmallVector<const Value *, 2> Users;
1056 Users.push_back(Ptr);
1058 Ptr = Users.pop_back_val();
1059 for (Value::const_use_iterator UI = Ptr->use_begin(), UE = Ptr->use_end();
1061 const User *I = *UI;
1062 if (isa<ReturnInst>(I) || GetBasicInstructionClass(I) == IC_RetainRV)
1064 if (isa<BitCastInst>(I))
1067 } while (!Users.empty());
1072 DEBUG(dbgs() << "ObjCARCOpt::OptimizeAutoreleaseRVCall: Transforming "
1073 "objc_autoreleaseReturnValue => "
1074 "objc_autorelease since its operand is not used as a return "
1077 << *AutoreleaseRV << "\n");
1079 CallInst *AutoreleaseRVCI = cast<CallInst>(AutoreleaseRV);
1081 setCalledFunction(getAutoreleaseCallee(F.getParent()));
1082 AutoreleaseRVCI->setTailCall(false); // Never tail call objc_autorelease.
1083 Class = IC_Autorelease;
1085 DEBUG(dbgs() << " New: "
1086 << *AutoreleaseRV << "\n");
1090 /// Visit each call, one at a time, and make simplifications without doing any
1091 /// additional analysis.
1092 void ObjCARCOpt::OptimizeIndividualCalls(Function &F) {
1093 // Reset all the flags in preparation for recomputing them.
1094 UsedInThisFunction = 0;
1096 // Visit all objc_* calls in F.
1097 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
1098 Instruction *Inst = &*I++;
1100 InstructionClass Class = GetBasicInstructionClass(Inst);
1102 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Visiting: Class: "
1103 << Class << "; " << *Inst << "\n");
1108 // Delete no-op casts. These function calls have special semantics, but
1109 // the semantics are entirely implemented via lowering in the front-end,
1110 // so by the time they reach the optimizer, they are just no-op calls
1111 // which return their argument.
1113 // There are gray areas here, as the ability to cast reference-counted
1114 // pointers to raw void* and back allows code to break ARC assumptions,
1115 // however these are currently considered to be unimportant.
1119 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Erasing no-op cast:"
1120 " " << *Inst << "\n");
1121 EraseInstruction(Inst);
1124 // If the pointer-to-weak-pointer is null, it's undefined behavior.
1127 case IC_LoadWeakRetained:
1129 case IC_DestroyWeak: {
1130 CallInst *CI = cast<CallInst>(Inst);
1131 if (isNullOrUndef(CI->getArgOperand(0))) {
1133 Type *Ty = CI->getArgOperand(0)->getType();
1134 new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
1135 Constant::getNullValue(Ty),
1137 llvm::Value *NewValue = UndefValue::get(CI->getType());
1138 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: A null "
1139 "pointer-to-weak-pointer is undefined behavior.\n"
1143 CI->replaceAllUsesWith(NewValue);
1144 CI->eraseFromParent();
1151 CallInst *CI = cast<CallInst>(Inst);
1152 if (isNullOrUndef(CI->getArgOperand(0)) ||
1153 isNullOrUndef(CI->getArgOperand(1))) {
1155 Type *Ty = CI->getArgOperand(0)->getType();
1156 new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
1157 Constant::getNullValue(Ty),
1160 llvm::Value *NewValue = UndefValue::get(CI->getType());
1161 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: A null "
1162 "pointer-to-weak-pointer is undefined behavior.\n"
1167 CI->replaceAllUsesWith(NewValue);
1168 CI->eraseFromParent();
1174 OptimizeRetainCall(F, Inst);
1177 if (OptimizeRetainRVCall(F, Inst))
1180 case IC_AutoreleaseRV:
1181 OptimizeAutoreleaseRVCall(F, Inst, Class);
1185 // objc_autorelease(x) -> objc_release(x) if x is otherwise unused.
1186 if (IsAutorelease(Class) && Inst->use_empty()) {
1187 CallInst *Call = cast<CallInst>(Inst);
1188 const Value *Arg = Call->getArgOperand(0);
1189 Arg = FindSingleUseIdentifiedObject(Arg);
1194 // Create the declaration lazily.
1195 LLVMContext &C = Inst->getContext();
1197 CallInst::Create(getReleaseCallee(F.getParent()),
1198 Call->getArgOperand(0), "", Call);
1199 NewCall->setMetadata(ImpreciseReleaseMDKind,
1200 MDNode::get(C, ArrayRef<Value *>()));
1202 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Replacing "
1203 "objc_autorelease(x) with objc_release(x) since x is "
1204 "otherwise unused.\n"
1205 " Old: " << *Call <<
1209 EraseInstruction(Call);
1215 // For functions which can never be passed stack arguments, add
1217 if (IsAlwaysTail(Class)) {
1219 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Adding tail keyword"
1220 " to function since it can never be passed stack args: " << *Inst <<
1222 cast<CallInst>(Inst)->setTailCall();
1225 // Ensure that functions that can never have a "tail" keyword due to the
1226 // semantics of ARC truly do not do so.
1227 if (IsNeverTail(Class)) {
1229 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Removing tail "
1230 "keyword from function: " << *Inst <<
1232 cast<CallInst>(Inst)->setTailCall(false);
1235 // Set nounwind as needed.
1236 if (IsNoThrow(Class)) {
1238 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Found no throw"
1239 " class. Setting nounwind on: " << *Inst << "\n");
1240 cast<CallInst>(Inst)->setDoesNotThrow();
1243 if (!IsNoopOnNull(Class)) {
1244 UsedInThisFunction |= 1 << Class;
1248 const Value *Arg = GetObjCArg(Inst);
1250 // ARC calls with null are no-ops. Delete them.
1251 if (isNullOrUndef(Arg)) {
1254 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: ARC calls with "
1255 " null are no-ops. Erasing: " << *Inst << "\n");
1256 EraseInstruction(Inst);
1260 // Keep track of which of retain, release, autorelease, and retain_block
1261 // are actually present in this function.
1262 UsedInThisFunction |= 1 << Class;
1264 // If Arg is a PHI, and one or more incoming values to the
1265 // PHI are null, and the call is control-equivalent to the PHI, and there
1266 // are no relevant side effects between the PHI and the call, the call
1267 // could be pushed up to just those paths with non-null incoming values.
1268 // For now, don't bother splitting critical edges for this.
1269 SmallVector<std::pair<Instruction *, const Value *>, 4> Worklist;
1270 Worklist.push_back(std::make_pair(Inst, Arg));
1272 std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val();
1276 const PHINode *PN = dyn_cast<PHINode>(Arg);
1279 // Determine if the PHI has any null operands, or any incoming
1281 bool HasNull = false;
1282 bool HasCriticalEdges = false;
1283 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1285 StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
1286 if (isNullOrUndef(Incoming))
1288 else if (cast<TerminatorInst>(PN->getIncomingBlock(i)->back())
1289 .getNumSuccessors() != 1) {
1290 HasCriticalEdges = true;
1294 // If we have null operands and no critical edges, optimize.
1295 if (!HasCriticalEdges && HasNull) {
1296 SmallPtrSet<Instruction *, 4> DependingInstructions;
1297 SmallPtrSet<const BasicBlock *, 4> Visited;
1299 // Check that there is nothing that cares about the reference
1300 // count between the call and the phi.
1303 case IC_RetainBlock:
1304 // These can always be moved up.
1307 // These can't be moved across things that care about the retain
1309 FindDependencies(NeedsPositiveRetainCount, Arg,
1310 Inst->getParent(), Inst,
1311 DependingInstructions, Visited, PA);
1313 case IC_Autorelease:
1314 // These can't be moved across autorelease pool scope boundaries.
1315 FindDependencies(AutoreleasePoolBoundary, Arg,
1316 Inst->getParent(), Inst,
1317 DependingInstructions, Visited, PA);
1320 case IC_AutoreleaseRV:
1321 // Don't move these; the RV optimization depends on the autoreleaseRV
1322 // being tail called, and the retainRV being immediately after a call
1323 // (which might still happen if we get lucky with codegen layout, but
1324 // it's not worth taking the chance).
1327 llvm_unreachable("Invalid dependence flavor");
1330 if (DependingInstructions.size() == 1 &&
1331 *DependingInstructions.begin() == PN) {
1334 // Clone the call into each predecessor that has a non-null value.
1335 CallInst *CInst = cast<CallInst>(Inst);
1336 Type *ParamTy = CInst->getArgOperand(0)->getType();
1337 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1339 StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
1340 if (!isNullOrUndef(Incoming)) {
1341 CallInst *Clone = cast<CallInst>(CInst->clone());
1342 Value *Op = PN->getIncomingValue(i);
1343 Instruction *InsertPos = &PN->getIncomingBlock(i)->back();
1344 if (Op->getType() != ParamTy)
1345 Op = new BitCastInst(Op, ParamTy, "", InsertPos);
1346 Clone->setArgOperand(0, Op);
1347 Clone->insertBefore(InsertPos);
1349 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Cloning "
1352 "clone at " << *InsertPos << "\n");
1353 Worklist.push_back(std::make_pair(Clone, Incoming));
1356 // Erase the original call.
1357 DEBUG(dbgs() << "Erasing: " << *CInst << "\n");
1358 EraseInstruction(CInst);
1362 } while (!Worklist.empty());
1364 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Finished List.\n");
1367 /// Check for critical edges, loop boundaries, irreducible control flow, or
1368 /// other CFG structures where moving code across the edge would result in it
1369 /// being executed more.
1371 ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB,
1372 DenseMap<const BasicBlock *, BBState> &BBStates,
1373 BBState &MyStates) const {
1374 // If any top-down local-use or possible-dec has a succ which is earlier in
1375 // the sequence, forget it.
1376 for (BBState::ptr_iterator I = MyStates.top_down_ptr_begin(),
1377 E = MyStates.top_down_ptr_end(); I != E; ++I)
1378 switch (I->second.GetSeq()) {
1381 const Value *Arg = I->first;
1382 const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
1383 bool SomeSuccHasSame = false;
1384 bool AllSuccsHaveSame = true;
1385 PtrState &S = I->second;
1386 succ_const_iterator SI(TI), SE(TI, false);
1388 for (; SI != SE; ++SI) {
1389 Sequence SuccSSeq = S_None;
1390 bool SuccSRRIKnownSafe = false;
1391 // If VisitBottomUp has pointer information for this successor, take
1392 // what we know about it.
1393 DenseMap<const BasicBlock *, BBState>::iterator BBI =
1395 assert(BBI != BBStates.end());
1396 const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);
1397 SuccSSeq = SuccS.GetSeq();
1398 SuccSRRIKnownSafe = SuccS.RRI.KnownSafe;
1401 case S_CanRelease: {
1402 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe) {
1403 S.ClearSequenceProgress();
1409 SomeSuccHasSame = true;
1413 case S_MovableRelease:
1414 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe)
1415 AllSuccsHaveSame = false;
1418 llvm_unreachable("bottom-up pointer in retain state!");
1421 // If the state at the other end of any of the successor edges
1422 // matches the current state, require all edges to match. This
1423 // guards against loops in the middle of a sequence.
1424 if (SomeSuccHasSame && !AllSuccsHaveSame)
1425 S.ClearSequenceProgress();
1428 case S_CanRelease: {
1429 const Value *Arg = I->first;
1430 const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
1431 bool SomeSuccHasSame = false;
1432 bool AllSuccsHaveSame = true;
1433 PtrState &S = I->second;
1434 succ_const_iterator SI(TI), SE(TI, false);
1436 for (; SI != SE; ++SI) {
1437 Sequence SuccSSeq = S_None;
1438 bool SuccSRRIKnownSafe = false;
1439 // If VisitBottomUp has pointer information for this successor, take
1440 // what we know about it.
1441 DenseMap<const BasicBlock *, BBState>::iterator BBI =
1443 assert(BBI != BBStates.end());
1444 const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);
1445 SuccSSeq = SuccS.GetSeq();
1446 SuccSRRIKnownSafe = SuccS.RRI.KnownSafe;
1449 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe) {
1450 S.ClearSequenceProgress();
1456 SomeSuccHasSame = true;
1460 case S_MovableRelease:
1462 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe)
1463 AllSuccsHaveSame = false;
1466 llvm_unreachable("bottom-up pointer in retain state!");
1469 // If the state at the other end of any of the successor edges
1470 // matches the current state, require all edges to match. This
1471 // guards against loops in the middle of a sequence.
1472 if (SomeSuccHasSame && !AllSuccsHaveSame)
1473 S.ClearSequenceProgress();
1480 ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst,
1482 MapVector<Value *, RRInfo> &Retains,
1483 BBState &MyStates) {
1484 bool NestingDetected = false;
1485 InstructionClass Class = GetInstructionClass(Inst);
1486 const Value *Arg = 0;
1490 Arg = GetObjCArg(Inst);
1492 PtrState &S = MyStates.getPtrBottomUpState(Arg);
1494 // If we see two releases in a row on the same pointer. If so, make
1495 // a note, and we'll cicle back to revisit it after we've
1496 // hopefully eliminated the second release, which may allow us to
1497 // eliminate the first release too.
1498 // Theoretically we could implement removal of nested retain+release
1499 // pairs by making PtrState hold a stack of states, but this is
1500 // simple and avoids adding overhead for the non-nested case.
1501 if (S.GetSeq() == S_Release || S.GetSeq() == S_MovableRelease) {
1502 DEBUG(dbgs() << "ObjCARCOpt::VisitInstructionBottomUp: Found nested "
1503 "releases (i.e. a release pair)\n");
1504 NestingDetected = true;
1507 MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind);
1508 S.ResetSequenceProgress(ReleaseMetadata ? S_MovableRelease : S_Release);
1509 S.RRI.ReleaseMetadata = ReleaseMetadata;
1510 S.RRI.KnownSafe = S.HasKnownPositiveRefCount();
1511 S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
1512 S.RRI.Calls.insert(Inst);
1514 S.SetKnownPositiveRefCount();
1517 case IC_RetainBlock:
1518 // An objc_retainBlock call with just a use may need to be kept,
1519 // because it may be copying a block from the stack to the heap.
1520 if (!IsRetainBlockOptimizable(Inst))
1525 Arg = GetObjCArg(Inst);
1527 PtrState &S = MyStates.getPtrBottomUpState(Arg);
1528 S.SetKnownPositiveRefCount();
1530 switch (S.GetSeq()) {
1533 case S_MovableRelease:
1535 S.RRI.ReverseInsertPts.clear();
1538 // Don't do retain+release tracking for IC_RetainRV, because it's
1539 // better to let it remain as the first instruction after a call.
1540 if (Class != IC_RetainRV) {
1541 S.RRI.IsRetainBlock = Class == IC_RetainBlock;
1542 Retains[Inst] = S.RRI;
1544 S.ClearSequenceProgress();
1549 llvm_unreachable("bottom-up pointer in retain state!");
1551 return NestingDetected;
1553 case IC_AutoreleasepoolPop:
1554 // Conservatively, clear MyStates for all known pointers.
1555 MyStates.clearBottomUpPointers();
1556 return NestingDetected;
1557 case IC_AutoreleasepoolPush:
1559 // These are irrelevant.
1560 return NestingDetected;
1565 // Consider any other possible effects of this instruction on each
1566 // pointer being tracked.
1567 for (BBState::ptr_iterator MI = MyStates.bottom_up_ptr_begin(),
1568 ME = MyStates.bottom_up_ptr_end(); MI != ME; ++MI) {
1569 const Value *Ptr = MI->first;
1571 continue; // Handled above.
1572 PtrState &S = MI->second;
1573 Sequence Seq = S.GetSeq();
1575 // Check for possible releases.
1576 if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
1577 S.ClearKnownPositiveRefCount();
1580 S.SetSeq(S_CanRelease);
1584 case S_MovableRelease:
1589 llvm_unreachable("bottom-up pointer in retain state!");
1593 // Check for possible direct uses.
1596 case S_MovableRelease:
1597 if (CanUse(Inst, Ptr, PA, Class)) {
1598 assert(S.RRI.ReverseInsertPts.empty());
1599 // If this is an invoke instruction, we're scanning it as part of
1600 // one of its successor blocks, since we can't insert code after it
1601 // in its own block, and we don't want to split critical edges.
1602 if (isa<InvokeInst>(Inst))
1603 S.RRI.ReverseInsertPts.insert(BB->getFirstInsertionPt());
1605 S.RRI.ReverseInsertPts.insert(llvm::next(BasicBlock::iterator(Inst)));
1607 } else if (Seq == S_Release && IsUser(Class)) {
1608 // Non-movable releases depend on any possible objc pointer use.
1610 assert(S.RRI.ReverseInsertPts.empty());
1611 // As above; handle invoke specially.
1612 if (isa<InvokeInst>(Inst))
1613 S.RRI.ReverseInsertPts.insert(BB->getFirstInsertionPt());
1615 S.RRI.ReverseInsertPts.insert(llvm::next(BasicBlock::iterator(Inst)));
1619 if (CanUse(Inst, Ptr, PA, Class))
1627 llvm_unreachable("bottom-up pointer in retain state!");
1631 return NestingDetected;
1635 ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
1636 DenseMap<const BasicBlock *, BBState> &BBStates,
1637 MapVector<Value *, RRInfo> &Retains) {
1638 bool NestingDetected = false;
1639 BBState &MyStates = BBStates[BB];
1641 // Merge the states from each successor to compute the initial state
1642 // for the current block.
1643 BBState::edge_iterator SI(MyStates.succ_begin()),
1644 SE(MyStates.succ_end());
1646 const BasicBlock *Succ = *SI;
1647 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ);
1648 assert(I != BBStates.end());
1649 MyStates.InitFromSucc(I->second);
1651 for (; SI != SE; ++SI) {
1653 I = BBStates.find(Succ);
1654 assert(I != BBStates.end());
1655 MyStates.MergeSucc(I->second);
1659 // Visit all the instructions, bottom-up.
1660 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
1661 Instruction *Inst = llvm::prior(I);
1663 // Invoke instructions are visited as part of their successors (below).
1664 if (isa<InvokeInst>(Inst))
1667 DEBUG(dbgs() << "ObjCARCOpt::VisitButtonUp: Visiting " << *Inst << "\n");
1669 NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates);
1672 // If there's a predecessor with an invoke, visit the invoke as if it were
1673 // part of this block, since we can't insert code after an invoke in its own
1674 // block, and we don't want to split critical edges.
1675 for (BBState::edge_iterator PI(MyStates.pred_begin()),
1676 PE(MyStates.pred_end()); PI != PE; ++PI) {
1677 BasicBlock *Pred = *PI;
1678 if (InvokeInst *II = dyn_cast<InvokeInst>(&Pred->back()))
1679 NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates);
1682 return NestingDetected;
1686 ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst,
1687 DenseMap<Value *, RRInfo> &Releases,
1688 BBState &MyStates) {
1689 bool NestingDetected = false;
1690 InstructionClass Class = GetInstructionClass(Inst);
1691 const Value *Arg = 0;
1694 case IC_RetainBlock:
1695 // An objc_retainBlock call with just a use may need to be kept,
1696 // because it may be copying a block from the stack to the heap.
1697 if (!IsRetainBlockOptimizable(Inst))
1702 Arg = GetObjCArg(Inst);
1704 PtrState &S = MyStates.getPtrTopDownState(Arg);
1706 // Don't do retain+release tracking for IC_RetainRV, because it's
1707 // better to let it remain as the first instruction after a call.
1708 if (Class != IC_RetainRV) {
1709 // If we see two retains in a row on the same pointer. If so, make
1710 // a note, and we'll cicle back to revisit it after we've
1711 // hopefully eliminated the second retain, which may allow us to
1712 // eliminate the first retain too.
1713 // Theoretically we could implement removal of nested retain+release
1714 // pairs by making PtrState hold a stack of states, but this is
1715 // simple and avoids adding overhead for the non-nested case.
1716 if (S.GetSeq() == S_Retain)
1717 NestingDetected = true;
1719 S.ResetSequenceProgress(S_Retain);
1720 S.RRI.IsRetainBlock = Class == IC_RetainBlock;
1721 S.RRI.KnownSafe = S.HasKnownPositiveRefCount();
1722 S.RRI.Calls.insert(Inst);
1725 S.SetKnownPositiveRefCount();
1727 // A retain can be a potential use; procede to the generic checking
1732 Arg = GetObjCArg(Inst);
1734 PtrState &S = MyStates.getPtrTopDownState(Arg);
1735 S.ClearKnownPositiveRefCount();
1737 switch (S.GetSeq()) {
1740 S.RRI.ReverseInsertPts.clear();
1743 S.RRI.ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind);
1744 S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
1745 Releases[Inst] = S.RRI;
1746 S.ClearSequenceProgress();
1752 case S_MovableRelease:
1753 llvm_unreachable("top-down pointer in release state!");
1757 case IC_AutoreleasepoolPop:
1758 // Conservatively, clear MyStates for all known pointers.
1759 MyStates.clearTopDownPointers();
1760 return NestingDetected;
1761 case IC_AutoreleasepoolPush:
1763 // These are irrelevant.
1764 return NestingDetected;
1769 // Consider any other possible effects of this instruction on each
1770 // pointer being tracked.
1771 for (BBState::ptr_iterator MI = MyStates.top_down_ptr_begin(),
1772 ME = MyStates.top_down_ptr_end(); MI != ME; ++MI) {
1773 const Value *Ptr = MI->first;
1775 continue; // Handled above.
1776 PtrState &S = MI->second;
1777 Sequence Seq = S.GetSeq();
1779 // Check for possible releases.
1780 if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
1781 S.ClearKnownPositiveRefCount();
1784 S.SetSeq(S_CanRelease);
1785 assert(S.RRI.ReverseInsertPts.empty());
1786 S.RRI.ReverseInsertPts.insert(Inst);
1788 // One call can't cause a transition from S_Retain to S_CanRelease
1789 // and S_CanRelease to S_Use. If we've made the first transition,
1798 case S_MovableRelease:
1799 llvm_unreachable("top-down pointer in release state!");
1803 // Check for possible direct uses.
1806 if (CanUse(Inst, Ptr, PA, Class))
1815 case S_MovableRelease:
1816 llvm_unreachable("top-down pointer in release state!");
1820 return NestingDetected;
1824 ObjCARCOpt::VisitTopDown(BasicBlock *BB,
1825 DenseMap<const BasicBlock *, BBState> &BBStates,
1826 DenseMap<Value *, RRInfo> &Releases) {
1827 bool NestingDetected = false;
1828 BBState &MyStates = BBStates[BB];
1830 // Merge the states from each predecessor to compute the initial state
1831 // for the current block.
1832 BBState::edge_iterator PI(MyStates.pred_begin()),
1833 PE(MyStates.pred_end());
1835 const BasicBlock *Pred = *PI;
1836 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred);
1837 assert(I != BBStates.end());
1838 MyStates.InitFromPred(I->second);
1840 for (; PI != PE; ++PI) {
1842 I = BBStates.find(Pred);
1843 assert(I != BBStates.end());
1844 MyStates.MergePred(I->second);
1848 // Visit all the instructions, top-down.
1849 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
1850 Instruction *Inst = I;
1852 DEBUG(dbgs() << "ObjCARCOpt::VisitTopDown: Visiting " << *Inst << "\n");
1854 NestingDetected |= VisitInstructionTopDown(Inst, Releases, MyStates);
1857 CheckForCFGHazards(BB, BBStates, MyStates);
1858 return NestingDetected;
1862 ComputePostOrders(Function &F,
1863 SmallVectorImpl<BasicBlock *> &PostOrder,
1864 SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder,
1865 unsigned NoObjCARCExceptionsMDKind,
1866 DenseMap<const BasicBlock *, BBState> &BBStates) {
1867 /// The visited set, for doing DFS walks.
1868 SmallPtrSet<BasicBlock *, 16> Visited;
1870 // Do DFS, computing the PostOrder.
1871 SmallPtrSet<BasicBlock *, 16> OnStack;
1872 SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack;
1874 // Functions always have exactly one entry block, and we don't have
1875 // any other block that we treat like an entry block.
1876 BasicBlock *EntryBB = &F.getEntryBlock();
1877 BBState &MyStates = BBStates[EntryBB];
1878 MyStates.SetAsEntry();
1879 TerminatorInst *EntryTI = cast<TerminatorInst>(&EntryBB->back());
1880 SuccStack.push_back(std::make_pair(EntryBB, succ_iterator(EntryTI)));
1881 Visited.insert(EntryBB);
1882 OnStack.insert(EntryBB);
1885 BasicBlock *CurrBB = SuccStack.back().first;
1886 TerminatorInst *TI = cast<TerminatorInst>(&CurrBB->back());
1887 succ_iterator SE(TI, false);
1889 while (SuccStack.back().second != SE) {
1890 BasicBlock *SuccBB = *SuccStack.back().second++;
1891 if (Visited.insert(SuccBB)) {
1892 TerminatorInst *TI = cast<TerminatorInst>(&SuccBB->back());
1893 SuccStack.push_back(std::make_pair(SuccBB, succ_iterator(TI)));
1894 BBStates[CurrBB].addSucc(SuccBB);
1895 BBState &SuccStates = BBStates[SuccBB];
1896 SuccStates.addPred(CurrBB);
1897 OnStack.insert(SuccBB);
1901 if (!OnStack.count(SuccBB)) {
1902 BBStates[CurrBB].addSucc(SuccBB);
1903 BBStates[SuccBB].addPred(CurrBB);
1906 OnStack.erase(CurrBB);
1907 PostOrder.push_back(CurrBB);
1908 SuccStack.pop_back();
1909 } while (!SuccStack.empty());
1913 // Do reverse-CFG DFS, computing the reverse-CFG PostOrder.
1914 // Functions may have many exits, and there also blocks which we treat
1915 // as exits due to ignored edges.
1916 SmallVector<std::pair<BasicBlock *, BBState::edge_iterator>, 16> PredStack;
1917 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
1918 BasicBlock *ExitBB = I;
1919 BBState &MyStates = BBStates[ExitBB];
1920 if (!MyStates.isExit())
1923 MyStates.SetAsExit();
1925 PredStack.push_back(std::make_pair(ExitBB, MyStates.pred_begin()));
1926 Visited.insert(ExitBB);
1927 while (!PredStack.empty()) {
1928 reverse_dfs_next_succ:
1929 BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end();
1930 while (PredStack.back().second != PE) {
1931 BasicBlock *BB = *PredStack.back().second++;
1932 if (Visited.insert(BB)) {
1933 PredStack.push_back(std::make_pair(BB, BBStates[BB].pred_begin()));
1934 goto reverse_dfs_next_succ;
1937 ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first);
1942 // Visit the function both top-down and bottom-up.
1944 ObjCARCOpt::Visit(Function &F,
1945 DenseMap<const BasicBlock *, BBState> &BBStates,
1946 MapVector<Value *, RRInfo> &Retains,
1947 DenseMap<Value *, RRInfo> &Releases) {
1949 // Use reverse-postorder traversals, because we magically know that loops
1950 // will be well behaved, i.e. they won't repeatedly call retain on a single
1951 // pointer without doing a release. We can't use the ReversePostOrderTraversal
1952 // class here because we want the reverse-CFG postorder to consider each
1953 // function exit point, and we want to ignore selected cycle edges.
1954 SmallVector<BasicBlock *, 16> PostOrder;
1955 SmallVector<BasicBlock *, 16> ReverseCFGPostOrder;
1956 ComputePostOrders(F, PostOrder, ReverseCFGPostOrder,
1957 NoObjCARCExceptionsMDKind,
1960 // Use reverse-postorder on the reverse CFG for bottom-up.
1961 bool BottomUpNestingDetected = false;
1962 for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
1963 ReverseCFGPostOrder.rbegin(), E = ReverseCFGPostOrder.rend();
1965 BottomUpNestingDetected |= VisitBottomUp(*I, BBStates, Retains);
1967 // Use reverse-postorder for top-down.
1968 bool TopDownNestingDetected = false;
1969 for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
1970 PostOrder.rbegin(), E = PostOrder.rend();
1972 TopDownNestingDetected |= VisitTopDown(*I, BBStates, Releases);
1974 return TopDownNestingDetected && BottomUpNestingDetected;
1977 /// Move the calls in RetainsToMove and ReleasesToMove.
1978 void ObjCARCOpt::MoveCalls(Value *Arg,
1979 RRInfo &RetainsToMove,
1980 RRInfo &ReleasesToMove,
1981 MapVector<Value *, RRInfo> &Retains,
1982 DenseMap<Value *, RRInfo> &Releases,
1983 SmallVectorImpl<Instruction *> &DeadInsts,
1985 Type *ArgTy = Arg->getType();
1986 Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext()));
1988 // Insert the new retain and release calls.
1989 for (SmallPtrSet<Instruction *, 2>::const_iterator
1990 PI = ReleasesToMove.ReverseInsertPts.begin(),
1991 PE = ReleasesToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
1992 Instruction *InsertPt = *PI;
1993 Value *MyArg = ArgTy == ParamTy ? Arg :
1994 new BitCastInst(Arg, ParamTy, "", InsertPt);
1996 CallInst::Create(RetainsToMove.IsRetainBlock ?
1997 getRetainBlockCallee(M) : getRetainCallee(M),
1998 MyArg, "", InsertPt);
1999 Call->setDoesNotThrow();
2000 if (RetainsToMove.IsRetainBlock)
2001 Call->setMetadata(CopyOnEscapeMDKind,
2002 MDNode::get(M->getContext(), ArrayRef<Value *>()));
2004 Call->setTailCall();
2006 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Inserting new Release: " << *Call
2008 " At insertion point: " << *InsertPt
2011 for (SmallPtrSet<Instruction *, 2>::const_iterator
2012 PI = RetainsToMove.ReverseInsertPts.begin(),
2013 PE = RetainsToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
2014 Instruction *InsertPt = *PI;
2015 Value *MyArg = ArgTy == ParamTy ? Arg :
2016 new BitCastInst(Arg, ParamTy, "", InsertPt);
2017 CallInst *Call = CallInst::Create(getReleaseCallee(M), MyArg,
2019 // Attach a clang.imprecise_release metadata tag, if appropriate.
2020 if (MDNode *M = ReleasesToMove.ReleaseMetadata)
2021 Call->setMetadata(ImpreciseReleaseMDKind, M);
2022 Call->setDoesNotThrow();
2023 if (ReleasesToMove.IsTailCallRelease)
2024 Call->setTailCall();
2026 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Inserting new Retain: " << *Call
2028 " At insertion point: " << *InsertPt
2032 // Delete the original retain and release calls.
2033 for (SmallPtrSet<Instruction *, 2>::const_iterator
2034 AI = RetainsToMove.Calls.begin(),
2035 AE = RetainsToMove.Calls.end(); AI != AE; ++AI) {
2036 Instruction *OrigRetain = *AI;
2037 Retains.blot(OrigRetain);
2038 DeadInsts.push_back(OrigRetain);
2039 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Deleting retain: " << *OrigRetain <<
2042 for (SmallPtrSet<Instruction *, 2>::const_iterator
2043 AI = ReleasesToMove.Calls.begin(),
2044 AE = ReleasesToMove.Calls.end(); AI != AE; ++AI) {
2045 Instruction *OrigRelease = *AI;
2046 Releases.erase(OrigRelease);
2047 DeadInsts.push_back(OrigRelease);
2048 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Deleting release: " << *OrigRelease
2054 ObjCARCOpt::ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState>
2056 MapVector<Value *, RRInfo> &Retains,
2057 DenseMap<Value *, RRInfo> &Releases,
2059 SmallVector<Instruction *, 4> &NewRetains,
2060 SmallVector<Instruction *, 4> &NewReleases,
2061 SmallVector<Instruction *, 8> &DeadInsts,
2062 RRInfo &RetainsToMove,
2063 RRInfo &ReleasesToMove,
2066 bool &AnyPairsCompletelyEliminated) {
2067 // If a pair happens in a region where it is known that the reference count
2068 // is already incremented, we can similarly ignore possible decrements.
2069 bool KnownSafeTD = true, KnownSafeBU = true;
2071 // Connect the dots between the top-down-collected RetainsToMove and
2072 // bottom-up-collected ReleasesToMove to form sets of related calls.
2073 // This is an iterative process so that we connect multiple releases
2074 // to multiple retains if needed.
2075 unsigned OldDelta = 0;
2076 unsigned NewDelta = 0;
2077 unsigned OldCount = 0;
2078 unsigned NewCount = 0;
2079 bool FirstRelease = true;
2080 bool FirstRetain = true;
2082 for (SmallVectorImpl<Instruction *>::const_iterator
2083 NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) {
2084 Instruction *NewRetain = *NI;
2085 MapVector<Value *, RRInfo>::const_iterator It = Retains.find(NewRetain);
2086 assert(It != Retains.end());
2087 const RRInfo &NewRetainRRI = It->second;
2088 KnownSafeTD &= NewRetainRRI.KnownSafe;
2089 for (SmallPtrSet<Instruction *, 2>::const_iterator
2090 LI = NewRetainRRI.Calls.begin(),
2091 LE = NewRetainRRI.Calls.end(); LI != LE; ++LI) {
2092 Instruction *NewRetainRelease = *LI;
2093 DenseMap<Value *, RRInfo>::const_iterator Jt =
2094 Releases.find(NewRetainRelease);
2095 if (Jt == Releases.end())
2097 const RRInfo &NewRetainReleaseRRI = Jt->second;
2098 assert(NewRetainReleaseRRI.Calls.count(NewRetain));
2099 if (ReleasesToMove.Calls.insert(NewRetainRelease)) {
2101 BBStates[NewRetainRelease->getParent()].GetAllPathCount();
2103 // Merge the ReleaseMetadata and IsTailCallRelease values.
2105 ReleasesToMove.ReleaseMetadata =
2106 NewRetainReleaseRRI.ReleaseMetadata;
2107 ReleasesToMove.IsTailCallRelease =
2108 NewRetainReleaseRRI.IsTailCallRelease;
2109 FirstRelease = false;
2111 if (ReleasesToMove.ReleaseMetadata !=
2112 NewRetainReleaseRRI.ReleaseMetadata)
2113 ReleasesToMove.ReleaseMetadata = 0;
2114 if (ReleasesToMove.IsTailCallRelease !=
2115 NewRetainReleaseRRI.IsTailCallRelease)
2116 ReleasesToMove.IsTailCallRelease = false;
2119 // Collect the optimal insertion points.
2121 for (SmallPtrSet<Instruction *, 2>::const_iterator
2122 RI = NewRetainReleaseRRI.ReverseInsertPts.begin(),
2123 RE = NewRetainReleaseRRI.ReverseInsertPts.end();
2125 Instruction *RIP = *RI;
2126 if (ReleasesToMove.ReverseInsertPts.insert(RIP))
2127 NewDelta -= BBStates[RIP->getParent()].GetAllPathCount();
2129 NewReleases.push_back(NewRetainRelease);
2134 if (NewReleases.empty()) break;
2136 // Back the other way.
2137 for (SmallVectorImpl<Instruction *>::const_iterator
2138 NI = NewReleases.begin(), NE = NewReleases.end(); NI != NE; ++NI) {
2139 Instruction *NewRelease = *NI;
2140 DenseMap<Value *, RRInfo>::const_iterator It =
2141 Releases.find(NewRelease);
2142 assert(It != Releases.end());
2143 const RRInfo &NewReleaseRRI = It->second;
2144 KnownSafeBU &= NewReleaseRRI.KnownSafe;
2145 for (SmallPtrSet<Instruction *, 2>::const_iterator
2146 LI = NewReleaseRRI.Calls.begin(),
2147 LE = NewReleaseRRI.Calls.end(); LI != LE; ++LI) {
2148 Instruction *NewReleaseRetain = *LI;
2149 MapVector<Value *, RRInfo>::const_iterator Jt =
2150 Retains.find(NewReleaseRetain);
2151 if (Jt == Retains.end())
2153 const RRInfo &NewReleaseRetainRRI = Jt->second;
2154 assert(NewReleaseRetainRRI.Calls.count(NewRelease));
2155 if (RetainsToMove.Calls.insert(NewReleaseRetain)) {
2156 unsigned PathCount =
2157 BBStates[NewReleaseRetain->getParent()].GetAllPathCount();
2158 OldDelta += PathCount;
2159 OldCount += PathCount;
2161 // Merge the IsRetainBlock values.
2163 RetainsToMove.IsRetainBlock = NewReleaseRetainRRI.IsRetainBlock;
2164 FirstRetain = false;
2165 } else if (ReleasesToMove.IsRetainBlock !=
2166 NewReleaseRetainRRI.IsRetainBlock)
2167 // It's not possible to merge the sequences if one uses
2168 // objc_retain and the other uses objc_retainBlock.
2171 // Collect the optimal insertion points.
2173 for (SmallPtrSet<Instruction *, 2>::const_iterator
2174 RI = NewReleaseRetainRRI.ReverseInsertPts.begin(),
2175 RE = NewReleaseRetainRRI.ReverseInsertPts.end();
2177 Instruction *RIP = *RI;
2178 if (RetainsToMove.ReverseInsertPts.insert(RIP)) {
2179 PathCount = BBStates[RIP->getParent()].GetAllPathCount();
2180 NewDelta += PathCount;
2181 NewCount += PathCount;
2184 NewRetains.push_back(NewReleaseRetain);
2188 NewReleases.clear();
2189 if (NewRetains.empty()) break;
2192 // If the pointer is known incremented or nested, we can safely delete the
2193 // pair regardless of what's between them.
2194 if (KnownSafeTD || KnownSafeBU) {
2195 RetainsToMove.ReverseInsertPts.clear();
2196 ReleasesToMove.ReverseInsertPts.clear();
2199 // Determine whether the new insertion points we computed preserve the
2200 // balance of retain and release calls through the program.
2201 // TODO: If the fully aggressive solution isn't valid, try to find a
2202 // less aggressive solution which is.
2207 // Determine whether the original call points are balanced in the retain and
2208 // release calls through the program. If not, conservatively don't touch
2210 // TODO: It's theoretically possible to do code motion in this case, as
2211 // long as the existing imbalances are maintained.
2216 assert(OldCount != 0 && "Unreachable code?");
2217 NumRRs += OldCount - NewCount;
2218 // Set to true if we completely removed any RR pairs.
2219 AnyPairsCompletelyEliminated = NewCount == 0;
2221 // We can move calls!
2225 /// Identify pairings between the retains and releases, and delete and/or move
2228 ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState>
2230 MapVector<Value *, RRInfo> &Retains,
2231 DenseMap<Value *, RRInfo> &Releases,
2233 bool AnyPairsCompletelyEliminated = false;
2234 RRInfo RetainsToMove;
2235 RRInfo ReleasesToMove;
2236 SmallVector<Instruction *, 4> NewRetains;
2237 SmallVector<Instruction *, 4> NewReleases;
2238 SmallVector<Instruction *, 8> DeadInsts;
2240 // Visit each retain.
2241 for (MapVector<Value *, RRInfo>::const_iterator I = Retains.begin(),
2242 E = Retains.end(); I != E; ++I) {
2243 Value *V = I->first;
2244 if (!V) continue; // blotted
2246 Instruction *Retain = cast<Instruction>(V);
2248 DEBUG(dbgs() << "ObjCARCOpt::PerformCodePlacement: Visiting: " << *Retain
2251 Value *Arg = GetObjCArg(Retain);
2253 // If the object being released is in static or stack storage, we know it's
2254 // not being managed by ObjC reference counting, so we can delete pairs
2255 // regardless of what possible decrements or uses lie between them.
2256 bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg);
2258 // A constant pointer can't be pointing to an object on the heap. It may
2259 // be reference-counted, but it won't be deleted.
2260 if (const LoadInst *LI = dyn_cast<LoadInst>(Arg))
2261 if (const GlobalVariable *GV =
2262 dyn_cast<GlobalVariable>(
2263 StripPointerCastsAndObjCCalls(LI->getPointerOperand())))
2264 if (GV->isConstant())
2267 // Connect the dots between the top-down-collected RetainsToMove and
2268 // bottom-up-collected ReleasesToMove to form sets of related calls.
2269 NewRetains.push_back(Retain);
2270 bool PerformMoveCalls =
2271 ConnectTDBUTraversals(BBStates, Retains, Releases, M, NewRetains,
2272 NewReleases, DeadInsts, RetainsToMove,
2273 ReleasesToMove, Arg, KnownSafe,
2274 AnyPairsCompletelyEliminated);
2276 if (PerformMoveCalls) {
2277 // Ok, everything checks out and we're all set. Let's move/delete some
2279 MoveCalls(Arg, RetainsToMove, ReleasesToMove,
2280 Retains, Releases, DeadInsts, M);
2283 // Clean up state for next retain.
2284 NewReleases.clear();
2286 RetainsToMove.clear();
2287 ReleasesToMove.clear();
2290 // Now that we're done moving everything, we can delete the newly dead
2291 // instructions, as we no longer need them as insert points.
2292 while (!DeadInsts.empty())
2293 EraseInstruction(DeadInsts.pop_back_val());
2295 return AnyPairsCompletelyEliminated;
2298 /// Weak pointer optimizations.
2299 void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
2300 // First, do memdep-style RLE and S2L optimizations. We can't use memdep
2301 // itself because it uses AliasAnalysis and we need to do provenance
2303 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2304 Instruction *Inst = &*I++;
2306 DEBUG(dbgs() << "ObjCARCOpt::OptimizeWeakCalls: Visiting: " << *Inst <<
2309 InstructionClass Class = GetBasicInstructionClass(Inst);
2310 if (Class != IC_LoadWeak && Class != IC_LoadWeakRetained)
2313 // Delete objc_loadWeak calls with no users.
2314 if (Class == IC_LoadWeak && Inst->use_empty()) {
2315 Inst->eraseFromParent();
2319 // TODO: For now, just look for an earlier available version of this value
2320 // within the same block. Theoretically, we could do memdep-style non-local
2321 // analysis too, but that would want caching. A better approach would be to
2322 // use the technique that EarlyCSE uses.
2323 inst_iterator Current = llvm::prior(I);
2324 BasicBlock *CurrentBB = Current.getBasicBlockIterator();
2325 for (BasicBlock::iterator B = CurrentBB->begin(),
2326 J = Current.getInstructionIterator();
2328 Instruction *EarlierInst = &*llvm::prior(J);
2329 InstructionClass EarlierClass = GetInstructionClass(EarlierInst);
2330 switch (EarlierClass) {
2332 case IC_LoadWeakRetained: {
2333 // If this is loading from the same pointer, replace this load's value
2335 CallInst *Call = cast<CallInst>(Inst);
2336 CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2337 Value *Arg = Call->getArgOperand(0);
2338 Value *EarlierArg = EarlierCall->getArgOperand(0);
2339 switch (PA.getAA()->alias(Arg, EarlierArg)) {
2340 case AliasAnalysis::MustAlias:
2342 // If the load has a builtin retain, insert a plain retain for it.
2343 if (Class == IC_LoadWeakRetained) {
2345 CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
2349 // Zap the fully redundant load.
2350 Call->replaceAllUsesWith(EarlierCall);
2351 Call->eraseFromParent();
2353 case AliasAnalysis::MayAlias:
2354 case AliasAnalysis::PartialAlias:
2356 case AliasAnalysis::NoAlias:
2363 // If this is storing to the same pointer and has the same size etc.
2364 // replace this load's value with the stored value.
2365 CallInst *Call = cast<CallInst>(Inst);
2366 CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2367 Value *Arg = Call->getArgOperand(0);
2368 Value *EarlierArg = EarlierCall->getArgOperand(0);
2369 switch (PA.getAA()->alias(Arg, EarlierArg)) {
2370 case AliasAnalysis::MustAlias:
2372 // If the load has a builtin retain, insert a plain retain for it.
2373 if (Class == IC_LoadWeakRetained) {
2375 CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
2379 // Zap the fully redundant load.
2380 Call->replaceAllUsesWith(EarlierCall->getArgOperand(1));
2381 Call->eraseFromParent();
2383 case AliasAnalysis::MayAlias:
2384 case AliasAnalysis::PartialAlias:
2386 case AliasAnalysis::NoAlias:
2393 // TOOD: Grab the copied value.
2395 case IC_AutoreleasepoolPush:
2397 case IC_IntrinsicUser:
2399 // Weak pointers are only modified through the weak entry points
2400 // (and arbitrary calls, which could call the weak entry points).
2403 // Anything else could modify the weak pointer.
2410 // Then, for each destroyWeak with an alloca operand, check to see if
2411 // the alloca and all its users can be zapped.
2412 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2413 Instruction *Inst = &*I++;
2414 InstructionClass Class = GetBasicInstructionClass(Inst);
2415 if (Class != IC_DestroyWeak)
2418 CallInst *Call = cast<CallInst>(Inst);
2419 Value *Arg = Call->getArgOperand(0);
2420 if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) {
2421 for (Value::use_iterator UI = Alloca->use_begin(),
2422 UE = Alloca->use_end(); UI != UE; ++UI) {
2423 const Instruction *UserInst = cast<Instruction>(*UI);
2424 switch (GetBasicInstructionClass(UserInst)) {
2427 case IC_DestroyWeak:
2434 for (Value::use_iterator UI = Alloca->use_begin(),
2435 UE = Alloca->use_end(); UI != UE; ) {
2436 CallInst *UserInst = cast<CallInst>(*UI++);
2437 switch (GetBasicInstructionClass(UserInst)) {
2440 // These functions return their second argument.
2441 UserInst->replaceAllUsesWith(UserInst->getArgOperand(1));
2443 case IC_DestroyWeak:
2447 llvm_unreachable("alloca really is used!");
2449 UserInst->eraseFromParent();
2451 Alloca->eraseFromParent();
2456 DEBUG(dbgs() << "ObjCARCOpt::OptimizeWeakCalls: Finished List.\n\n");
2460 /// Identify program paths which execute sequences of retains and releases which
2461 /// can be eliminated.
2462 bool ObjCARCOpt::OptimizeSequences(Function &F) {
2463 /// Releases, Retains - These are used to store the results of the main flow
2464 /// analysis. These use Value* as the key instead of Instruction* so that the
2465 /// map stays valid when we get around to rewriting code and calls get
2466 /// replaced by arguments.
2467 DenseMap<Value *, RRInfo> Releases;
2468 MapVector<Value *, RRInfo> Retains;
2470 /// This is used during the traversal of the function to track the
2471 /// states for each identified object at each block.
2472 DenseMap<const BasicBlock *, BBState> BBStates;
2474 // Analyze the CFG of the function, and all instructions.
2475 bool NestingDetected = Visit(F, BBStates, Retains, Releases);
2478 return PerformCodePlacement(BBStates, Retains, Releases, F.getParent()) &&
2482 /// Look for this pattern:
2484 /// %call = call i8* @something(...)
2485 /// %2 = call i8* @objc_retain(i8* %call)
2486 /// %3 = call i8* @objc_autorelease(i8* %2)
2489 /// And delete the retain and autorelease.
2491 /// Otherwise if it's just this:
2493 /// %3 = call i8* @objc_autorelease(i8* %2)
2496 /// convert the autorelease to autoreleaseRV.
2497 void ObjCARCOpt::OptimizeReturns(Function &F) {
2498 if (!F.getReturnType()->isPointerTy())
2501 SmallPtrSet<Instruction *, 4> DependingInstructions;
2502 SmallPtrSet<const BasicBlock *, 4> Visited;
2503 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
2504 BasicBlock *BB = FI;
2505 ReturnInst *Ret = dyn_cast<ReturnInst>(&BB->back());
2507 DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Visiting: " << *Ret << "\n");
2511 const Value *Arg = StripPointerCastsAndObjCCalls(Ret->getOperand(0));
2512 FindDependencies(NeedsPositiveRetainCount, Arg,
2513 BB, Ret, DependingInstructions, Visited, PA);
2514 if (DependingInstructions.size() != 1)
2518 CallInst *Autorelease =
2519 dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
2522 InstructionClass AutoreleaseClass = GetBasicInstructionClass(Autorelease);
2523 if (!IsAutorelease(AutoreleaseClass))
2525 if (GetObjCArg(Autorelease) != Arg)
2528 DependingInstructions.clear();
2531 // Check that there is nothing that can affect the reference
2532 // count between the autorelease and the retain.
2533 FindDependencies(CanChangeRetainCount, Arg,
2534 BB, Autorelease, DependingInstructions, Visited, PA);
2535 if (DependingInstructions.size() != 1)
2540 dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
2542 // Check that we found a retain with the same argument.
2544 !IsRetain(GetBasicInstructionClass(Retain)) ||
2545 GetObjCArg(Retain) != Arg)
2548 DependingInstructions.clear();
2551 // Convert the autorelease to an autoreleaseRV, since it's
2552 // returning the value.
2553 if (AutoreleaseClass == IC_Autorelease) {
2554 DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Converting autorelease "
2555 "=> autoreleaseRV since it's returning a value.\n"
2556 " In: " << *Autorelease
2558 Autorelease->setCalledFunction(getAutoreleaseRVCallee(F.getParent()));
2559 DEBUG(dbgs() << " Out: " << *Autorelease
2561 Autorelease->setTailCall(); // Always tail call autoreleaseRV.
2562 AutoreleaseClass = IC_AutoreleaseRV;
2565 // Check that there is nothing that can affect the reference
2566 // count between the retain and the call.
2567 // Note that Retain need not be in BB.
2568 FindDependencies(CanChangeRetainCount, Arg, Retain->getParent(), Retain,
2569 DependingInstructions, Visited, PA);
2570 if (DependingInstructions.size() != 1)
2575 dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
2577 // Check that the pointer is the return value of the call.
2578 if (!Call || Arg != Call)
2581 // Check that the call is a regular call.
2582 InstructionClass Class = GetBasicInstructionClass(Call);
2583 if (Class != IC_CallOrUser && Class != IC_Call)
2586 // If so, we can zap the retain and autorelease.
2589 DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Erasing: " << *Retain
2591 << *Autorelease << "\n");
2592 EraseInstruction(Retain);
2593 EraseInstruction(Autorelease);
2599 DependingInstructions.clear();
2603 DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Finished List.\n\n");
2607 bool ObjCARCOpt::doInitialization(Module &M) {
2611 // If nothing in the Module uses ARC, don't do anything.
2612 Run = ModuleHasARC(M);
2616 // Identify the imprecise release metadata kind.
2617 ImpreciseReleaseMDKind =
2618 M.getContext().getMDKindID("clang.imprecise_release");
2619 CopyOnEscapeMDKind =
2620 M.getContext().getMDKindID("clang.arc.copy_on_escape");
2621 NoObjCARCExceptionsMDKind =
2622 M.getContext().getMDKindID("clang.arc.no_objc_arc_exceptions");
2624 // Intuitively, objc_retain and others are nocapture, however in practice
2625 // they are not, because they return their argument value. And objc_release
2626 // calls finalizers which can have arbitrary side effects.
2628 // These are initialized lazily.
2630 AutoreleaseRVCallee = 0;
2633 RetainBlockCallee = 0;
2634 AutoreleaseCallee = 0;
2639 bool ObjCARCOpt::runOnFunction(Function &F) {
2643 // If nothing in the Module uses ARC, don't do anything.
2649 DEBUG(dbgs() << "ObjCARCOpt: Visiting Function: " << F.getName() << "\n");
2651 PA.setAA(&getAnalysis<AliasAnalysis>());
2653 // This pass performs several distinct transformations. As a compile-time aid
2654 // when compiling code that isn't ObjC, skip these if the relevant ObjC
2655 // library functions aren't declared.
2657 // Preliminary optimizations. This also computs UsedInThisFunction.
2658 OptimizeIndividualCalls(F);
2660 // Optimizations for weak pointers.
2661 if (UsedInThisFunction & ((1 << IC_LoadWeak) |
2662 (1 << IC_LoadWeakRetained) |
2663 (1 << IC_StoreWeak) |
2664 (1 << IC_InitWeak) |
2665 (1 << IC_CopyWeak) |
2666 (1 << IC_MoveWeak) |
2667 (1 << IC_DestroyWeak)))
2668 OptimizeWeakCalls(F);
2670 // Optimizations for retain+release pairs.
2671 if (UsedInThisFunction & ((1 << IC_Retain) |
2672 (1 << IC_RetainRV) |
2673 (1 << IC_RetainBlock)))
2674 if (UsedInThisFunction & (1 << IC_Release))
2675 // Run OptimizeSequences until it either stops making changes or
2676 // no retain+release pair nesting is detected.
2677 while (OptimizeSequences(F)) {}
2679 // Optimizations if objc_autorelease is used.
2680 if (UsedInThisFunction & ((1 << IC_Autorelease) |
2681 (1 << IC_AutoreleaseRV)))
2684 DEBUG(dbgs() << "\n");
2689 void ObjCARCOpt::releaseMemory() {