1 //===- ObjCARCOpts.cpp - ObjC ARC Optimization ----------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 /// This file defines ObjC ARC optimizations. ARC stands for Automatic
11 /// Reference Counting and is a system for managing reference counts for objects
14 /// The optimizations performed include elimination of redundant, partially
15 /// redundant, and inconsequential reference count operations, elimination of
16 /// redundant weak pointer operations, pattern-matching and replacement of
17 /// low-level operations into higher-level operations, and numerous minor
20 /// This file also defines a simple ARC-aware AliasAnalysis.
22 /// WARNING: This file knows about certain library functions. It recognizes them
23 /// by name, and hardwires knowledge of their semantics.
25 /// WARNING: This file knows about how certain Objective-C library functions are
26 /// used. Naive LLVM IR transformations which would otherwise be
27 /// behavior-preserving may break these assumptions.
29 //===----------------------------------------------------------------------===//
31 #define DEBUG_TYPE "objc-arc-opts"
33 #include "DependencyAnalysis.h"
34 #include "ObjCARCAliasAnalysis.h"
35 #include "ProvenanceAnalysis.h"
36 #include "llvm/ADT/DenseMap.h"
37 #include "llvm/ADT/STLExtras.h"
38 #include "llvm/ADT/SmallPtrSet.h"
39 #include "llvm/ADT/Statistic.h"
40 #include "llvm/IR/LLVMContext.h"
41 #include "llvm/Support/CFG.h"
42 #include "llvm/Support/Debug.h"
43 #include "llvm/Support/raw_ostream.h"
46 using namespace llvm::objcarc;
48 /// \defgroup MiscUtils Miscellaneous utilities that are not ARC specific.
52 /// \brief An associative container with fast insertion-order (deterministic)
53 /// iteration over its elements. Plus the special blot operation.
54 template<class KeyT, class ValueT>
56 /// Map keys to indices in Vector.
57 typedef DenseMap<KeyT, size_t> MapTy;
60 typedef std::vector<std::pair<KeyT, ValueT> > VectorTy;
65 typedef typename VectorTy::iterator iterator;
66 typedef typename VectorTy::const_iterator const_iterator;
67 iterator begin() { return Vector.begin(); }
68 iterator end() { return Vector.end(); }
69 const_iterator begin() const { return Vector.begin(); }
70 const_iterator end() const { return Vector.end(); }
74 assert(Vector.size() >= Map.size()); // May differ due to blotting.
75 for (typename MapTy::const_iterator I = Map.begin(), E = Map.end();
77 assert(I->second < Vector.size());
78 assert(Vector[I->second].first == I->first);
80 for (typename VectorTy::const_iterator I = Vector.begin(),
81 E = Vector.end(); I != E; ++I)
83 (Map.count(I->first) &&
84 Map[I->first] == size_t(I - Vector.begin())));
88 ValueT &operator[](const KeyT &Arg) {
89 std::pair<typename MapTy::iterator, bool> Pair =
90 Map.insert(std::make_pair(Arg, size_t(0)));
92 size_t Num = Vector.size();
93 Pair.first->second = Num;
94 Vector.push_back(std::make_pair(Arg, ValueT()));
95 return Vector[Num].second;
97 return Vector[Pair.first->second].second;
100 std::pair<iterator, bool>
101 insert(const std::pair<KeyT, ValueT> &InsertPair) {
102 std::pair<typename MapTy::iterator, bool> Pair =
103 Map.insert(std::make_pair(InsertPair.first, size_t(0)));
105 size_t Num = Vector.size();
106 Pair.first->second = Num;
107 Vector.push_back(InsertPair);
108 return std::make_pair(Vector.begin() + Num, true);
110 return std::make_pair(Vector.begin() + Pair.first->second, false);
113 const_iterator find(const KeyT &Key) const {
114 typename MapTy::const_iterator It = Map.find(Key);
115 if (It == Map.end()) return Vector.end();
116 return Vector.begin() + It->second;
119 /// This is similar to erase, but instead of removing the element from the
120 /// vector, it just zeros out the key in the vector. This leaves iterators
121 /// intact, but clients must be prepared for zeroed-out keys when iterating.
122 void blot(const KeyT &Key) {
123 typename MapTy::iterator It = Map.find(Key);
124 if (It == Map.end()) return;
125 Vector[It->second].first = KeyT();
138 /// \defgroup ARCUtilities Utility declarations/definitions specific to ARC.
141 /// \brief This is similar to StripPointerCastsAndObjCCalls but it stops as soon
142 /// as it finds a value with multiple uses.
143 static const Value *FindSingleUseIdentifiedObject(const Value *Arg) {
144 if (Arg->hasOneUse()) {
145 if (const BitCastInst *BC = dyn_cast<BitCastInst>(Arg))
146 return FindSingleUseIdentifiedObject(BC->getOperand(0));
147 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Arg))
148 if (GEP->hasAllZeroIndices())
149 return FindSingleUseIdentifiedObject(GEP->getPointerOperand());
150 if (IsForwarding(GetBasicInstructionClass(Arg)))
151 return FindSingleUseIdentifiedObject(
152 cast<CallInst>(Arg)->getArgOperand(0));
153 if (!IsObjCIdentifiedObject(Arg))
158 // If we found an identifiable object but it has multiple uses, but they are
159 // trivial uses, we can still consider this to be a single-use value.
160 if (IsObjCIdentifiedObject(Arg)) {
161 for (Value::const_use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
164 if (!U->use_empty() || StripPointerCastsAndObjCCalls(U) != Arg)
174 /// \brief Test whether the given retainable object pointer escapes.
176 /// This differs from regular escape analysis in that a use as an
177 /// argument to a call is not considered an escape.
179 static bool DoesRetainableObjPtrEscape(const User *Ptr) {
181 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Target: " << *Ptr << "\n");
183 // Walk the def-use chains.
184 SmallVector<const Value *, 4> Worklist;
185 Worklist.push_back(Ptr);
186 // If Ptr has any operands add them as well.
187 for (User::const_op_iterator I = Ptr->op_begin(), E = Ptr->op_end(); I != E; ++I) {
188 Worklist.push_back(*I);
191 // Ensure we do not visit any value twice.
192 SmallPtrSet<const Value *, 8> VisitedSet;
195 const Value *V = Worklist.pop_back_val();
197 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Visiting: " << *V << "\n");
199 for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end();
201 const User *UUser = *UI;
203 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: User: " << *UUser << "\n");
205 // Special - Use by a call (callee or argument) is not considered
207 switch (GetBasicInstructionClass(UUser)) {
212 case IC_AutoreleaseRV: {
213 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: User copies pointer arguments. "
215 // These special functions make copies of their pointer arguments.
220 // Use by an instruction which copies the value is an escape if the
221 // result is an escape.
222 if (isa<BitCastInst>(UUser) || isa<GetElementPtrInst>(UUser) ||
223 isa<PHINode>(UUser) || isa<SelectInst>(UUser)) {
225 if (!VisitedSet.insert(UUser)) {
226 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: User copies value. Escapes "
227 "if result escapes. Adding to list.\n");
228 Worklist.push_back(UUser);
230 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Already visited node.\n");
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 block escapes.\n");
250 } while (!Worklist.empty());
253 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Block 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_Release, ///< objc_release(x).
319 S_MovableRelease, ///< objc_release(x), !clang.imprecise_release.
320 S_Stop ///< like S_Release, but code motion is stopped.
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 ClearRefCount() {
458 KnownPositiveRefCount = false;
461 bool IsKnownIncremented() 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.IsKnownIncremented();
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)) {
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 &&
1608 (Class == IC_User || Class == IC_CallOrUser)) {
1609 // Non-movable releases depend on any possible objc pointer use.
1611 assert(S.RRI.ReverseInsertPts.empty());
1612 // As above; handle invoke specially.
1613 if (isa<InvokeInst>(Inst))
1614 S.RRI.ReverseInsertPts.insert(BB->getFirstInsertionPt());
1616 S.RRI.ReverseInsertPts.insert(llvm::next(BasicBlock::iterator(Inst)));
1620 if (CanUse(Inst, Ptr, PA, Class))
1628 llvm_unreachable("bottom-up pointer in retain state!");
1632 return NestingDetected;
1636 ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
1637 DenseMap<const BasicBlock *, BBState> &BBStates,
1638 MapVector<Value *, RRInfo> &Retains) {
1639 bool NestingDetected = false;
1640 BBState &MyStates = BBStates[BB];
1642 // Merge the states from each successor to compute the initial state
1643 // for the current block.
1644 BBState::edge_iterator SI(MyStates.succ_begin()),
1645 SE(MyStates.succ_end());
1647 const BasicBlock *Succ = *SI;
1648 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ);
1649 assert(I != BBStates.end());
1650 MyStates.InitFromSucc(I->second);
1652 for (; SI != SE; ++SI) {
1654 I = BBStates.find(Succ);
1655 assert(I != BBStates.end());
1656 MyStates.MergeSucc(I->second);
1660 // Visit all the instructions, bottom-up.
1661 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
1662 Instruction *Inst = llvm::prior(I);
1664 // Invoke instructions are visited as part of their successors (below).
1665 if (isa<InvokeInst>(Inst))
1668 DEBUG(dbgs() << "ObjCARCOpt::VisitButtonUp: Visiting " << *Inst << "\n");
1670 NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates);
1673 // If there's a predecessor with an invoke, visit the invoke as if it were
1674 // part of this block, since we can't insert code after an invoke in its own
1675 // block, and we don't want to split critical edges.
1676 for (BBState::edge_iterator PI(MyStates.pred_begin()),
1677 PE(MyStates.pred_end()); PI != PE; ++PI) {
1678 BasicBlock *Pred = *PI;
1679 if (InvokeInst *II = dyn_cast<InvokeInst>(&Pred->back()))
1680 NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates);
1683 return NestingDetected;
1687 ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst,
1688 DenseMap<Value *, RRInfo> &Releases,
1689 BBState &MyStates) {
1690 bool NestingDetected = false;
1691 InstructionClass Class = GetInstructionClass(Inst);
1692 const Value *Arg = 0;
1695 case IC_RetainBlock:
1696 // An objc_retainBlock call with just a use may need to be kept,
1697 // because it may be copying a block from the stack to the heap.
1698 if (!IsRetainBlockOptimizable(Inst))
1703 Arg = GetObjCArg(Inst);
1705 PtrState &S = MyStates.getPtrTopDownState(Arg);
1707 // Don't do retain+release tracking for IC_RetainRV, because it's
1708 // better to let it remain as the first instruction after a call.
1709 if (Class != IC_RetainRV) {
1710 // If we see two retains in a row on the same pointer. If so, make
1711 // a note, and we'll cicle back to revisit it after we've
1712 // hopefully eliminated the second retain, which may allow us to
1713 // eliminate the first retain too.
1714 // Theoretically we could implement removal of nested retain+release
1715 // pairs by making PtrState hold a stack of states, but this is
1716 // simple and avoids adding overhead for the non-nested case.
1717 if (S.GetSeq() == S_Retain)
1718 NestingDetected = true;
1720 S.ResetSequenceProgress(S_Retain);
1721 S.RRI.IsRetainBlock = Class == IC_RetainBlock;
1722 S.RRI.KnownSafe = S.IsKnownIncremented();
1723 S.RRI.Calls.insert(Inst);
1726 S.SetKnownPositiveRefCount();
1728 // A retain can be a potential use; procede to the generic checking
1733 Arg = GetObjCArg(Inst);
1735 PtrState &S = MyStates.getPtrTopDownState(Arg);
1738 switch (S.GetSeq()) {
1741 S.RRI.ReverseInsertPts.clear();
1744 S.RRI.ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind);
1745 S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
1746 Releases[Inst] = S.RRI;
1747 S.ClearSequenceProgress();
1753 case S_MovableRelease:
1754 llvm_unreachable("top-down pointer in release state!");
1758 case IC_AutoreleasepoolPop:
1759 // Conservatively, clear MyStates for all known pointers.
1760 MyStates.clearTopDownPointers();
1761 return NestingDetected;
1762 case IC_AutoreleasepoolPush:
1764 // These are irrelevant.
1765 return NestingDetected;
1770 // Consider any other possible effects of this instruction on each
1771 // pointer being tracked.
1772 for (BBState::ptr_iterator MI = MyStates.top_down_ptr_begin(),
1773 ME = MyStates.top_down_ptr_end(); MI != ME; ++MI) {
1774 const Value *Ptr = MI->first;
1776 continue; // Handled above.
1777 PtrState &S = MI->second;
1778 Sequence Seq = S.GetSeq();
1780 // Check for possible releases.
1781 if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
1785 S.SetSeq(S_CanRelease);
1786 assert(S.RRI.ReverseInsertPts.empty());
1787 S.RRI.ReverseInsertPts.insert(Inst);
1789 // One call can't cause a transition from S_Retain to S_CanRelease
1790 // and S_CanRelease to S_Use. If we've made the first transition,
1799 case S_MovableRelease:
1800 llvm_unreachable("top-down pointer in release state!");
1804 // Check for possible direct uses.
1807 if (CanUse(Inst, Ptr, PA, Class))
1816 case S_MovableRelease:
1817 llvm_unreachable("top-down pointer in release state!");
1821 return NestingDetected;
1825 ObjCARCOpt::VisitTopDown(BasicBlock *BB,
1826 DenseMap<const BasicBlock *, BBState> &BBStates,
1827 DenseMap<Value *, RRInfo> &Releases) {
1828 bool NestingDetected = false;
1829 BBState &MyStates = BBStates[BB];
1831 // Merge the states from each predecessor to compute the initial state
1832 // for the current block.
1833 BBState::edge_iterator PI(MyStates.pred_begin()),
1834 PE(MyStates.pred_end());
1836 const BasicBlock *Pred = *PI;
1837 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred);
1838 assert(I != BBStates.end());
1839 MyStates.InitFromPred(I->second);
1841 for (; PI != PE; ++PI) {
1843 I = BBStates.find(Pred);
1844 assert(I != BBStates.end());
1845 MyStates.MergePred(I->second);
1849 // Visit all the instructions, top-down.
1850 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
1851 Instruction *Inst = I;
1853 DEBUG(dbgs() << "ObjCARCOpt::VisitTopDown: Visiting " << *Inst << "\n");
1855 NestingDetected |= VisitInstructionTopDown(Inst, Releases, MyStates);
1858 CheckForCFGHazards(BB, BBStates, MyStates);
1859 return NestingDetected;
1863 ComputePostOrders(Function &F,
1864 SmallVectorImpl<BasicBlock *> &PostOrder,
1865 SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder,
1866 unsigned NoObjCARCExceptionsMDKind,
1867 DenseMap<const BasicBlock *, BBState> &BBStates) {
1868 /// The visited set, for doing DFS walks.
1869 SmallPtrSet<BasicBlock *, 16> Visited;
1871 // Do DFS, computing the PostOrder.
1872 SmallPtrSet<BasicBlock *, 16> OnStack;
1873 SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack;
1875 // Functions always have exactly one entry block, and we don't have
1876 // any other block that we treat like an entry block.
1877 BasicBlock *EntryBB = &F.getEntryBlock();
1878 BBState &MyStates = BBStates[EntryBB];
1879 MyStates.SetAsEntry();
1880 TerminatorInst *EntryTI = cast<TerminatorInst>(&EntryBB->back());
1881 SuccStack.push_back(std::make_pair(EntryBB, succ_iterator(EntryTI)));
1882 Visited.insert(EntryBB);
1883 OnStack.insert(EntryBB);
1886 BasicBlock *CurrBB = SuccStack.back().first;
1887 TerminatorInst *TI = cast<TerminatorInst>(&CurrBB->back());
1888 succ_iterator SE(TI, false);
1890 while (SuccStack.back().second != SE) {
1891 BasicBlock *SuccBB = *SuccStack.back().second++;
1892 if (Visited.insert(SuccBB)) {
1893 TerminatorInst *TI = cast<TerminatorInst>(&SuccBB->back());
1894 SuccStack.push_back(std::make_pair(SuccBB, succ_iterator(TI)));
1895 BBStates[CurrBB].addSucc(SuccBB);
1896 BBState &SuccStates = BBStates[SuccBB];
1897 SuccStates.addPred(CurrBB);
1898 OnStack.insert(SuccBB);
1902 if (!OnStack.count(SuccBB)) {
1903 BBStates[CurrBB].addSucc(SuccBB);
1904 BBStates[SuccBB].addPred(CurrBB);
1907 OnStack.erase(CurrBB);
1908 PostOrder.push_back(CurrBB);
1909 SuccStack.pop_back();
1910 } while (!SuccStack.empty());
1914 // Do reverse-CFG DFS, computing the reverse-CFG PostOrder.
1915 // Functions may have many exits, and there also blocks which we treat
1916 // as exits due to ignored edges.
1917 SmallVector<std::pair<BasicBlock *, BBState::edge_iterator>, 16> PredStack;
1918 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
1919 BasicBlock *ExitBB = I;
1920 BBState &MyStates = BBStates[ExitBB];
1921 if (!MyStates.isExit())
1924 MyStates.SetAsExit();
1926 PredStack.push_back(std::make_pair(ExitBB, MyStates.pred_begin()));
1927 Visited.insert(ExitBB);
1928 while (!PredStack.empty()) {
1929 reverse_dfs_next_succ:
1930 BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end();
1931 while (PredStack.back().second != PE) {
1932 BasicBlock *BB = *PredStack.back().second++;
1933 if (Visited.insert(BB)) {
1934 PredStack.push_back(std::make_pair(BB, BBStates[BB].pred_begin()));
1935 goto reverse_dfs_next_succ;
1938 ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first);
1943 // Visit the function both top-down and bottom-up.
1945 ObjCARCOpt::Visit(Function &F,
1946 DenseMap<const BasicBlock *, BBState> &BBStates,
1947 MapVector<Value *, RRInfo> &Retains,
1948 DenseMap<Value *, RRInfo> &Releases) {
1950 // Use reverse-postorder traversals, because we magically know that loops
1951 // will be well behaved, i.e. they won't repeatedly call retain on a single
1952 // pointer without doing a release. We can't use the ReversePostOrderTraversal
1953 // class here because we want the reverse-CFG postorder to consider each
1954 // function exit point, and we want to ignore selected cycle edges.
1955 SmallVector<BasicBlock *, 16> PostOrder;
1956 SmallVector<BasicBlock *, 16> ReverseCFGPostOrder;
1957 ComputePostOrders(F, PostOrder, ReverseCFGPostOrder,
1958 NoObjCARCExceptionsMDKind,
1961 // Use reverse-postorder on the reverse CFG for bottom-up.
1962 bool BottomUpNestingDetected = false;
1963 for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
1964 ReverseCFGPostOrder.rbegin(), E = ReverseCFGPostOrder.rend();
1966 BottomUpNestingDetected |= VisitBottomUp(*I, BBStates, Retains);
1968 // Use reverse-postorder for top-down.
1969 bool TopDownNestingDetected = false;
1970 for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
1971 PostOrder.rbegin(), E = PostOrder.rend();
1973 TopDownNestingDetected |= VisitTopDown(*I, BBStates, Releases);
1975 return TopDownNestingDetected && BottomUpNestingDetected;
1978 /// Move the calls in RetainsToMove and ReleasesToMove.
1979 void ObjCARCOpt::MoveCalls(Value *Arg,
1980 RRInfo &RetainsToMove,
1981 RRInfo &ReleasesToMove,
1982 MapVector<Value *, RRInfo> &Retains,
1983 DenseMap<Value *, RRInfo> &Releases,
1984 SmallVectorImpl<Instruction *> &DeadInsts,
1986 Type *ArgTy = Arg->getType();
1987 Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext()));
1989 // Insert the new retain and release calls.
1990 for (SmallPtrSet<Instruction *, 2>::const_iterator
1991 PI = ReleasesToMove.ReverseInsertPts.begin(),
1992 PE = ReleasesToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
1993 Instruction *InsertPt = *PI;
1994 Value *MyArg = ArgTy == ParamTy ? Arg :
1995 new BitCastInst(Arg, ParamTy, "", InsertPt);
1997 CallInst::Create(RetainsToMove.IsRetainBlock ?
1998 getRetainBlockCallee(M) : getRetainCallee(M),
1999 MyArg, "", InsertPt);
2000 Call->setDoesNotThrow();
2001 if (RetainsToMove.IsRetainBlock)
2002 Call->setMetadata(CopyOnEscapeMDKind,
2003 MDNode::get(M->getContext(), ArrayRef<Value *>()));
2005 Call->setTailCall();
2007 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Inserting new Release: " << *Call
2009 " At insertion point: " << *InsertPt
2012 for (SmallPtrSet<Instruction *, 2>::const_iterator
2013 PI = RetainsToMove.ReverseInsertPts.begin(),
2014 PE = RetainsToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
2015 Instruction *InsertPt = *PI;
2016 Value *MyArg = ArgTy == ParamTy ? Arg :
2017 new BitCastInst(Arg, ParamTy, "", InsertPt);
2018 CallInst *Call = CallInst::Create(getReleaseCallee(M), MyArg,
2020 // Attach a clang.imprecise_release metadata tag, if appropriate.
2021 if (MDNode *M = ReleasesToMove.ReleaseMetadata)
2022 Call->setMetadata(ImpreciseReleaseMDKind, M);
2023 Call->setDoesNotThrow();
2024 if (ReleasesToMove.IsTailCallRelease)
2025 Call->setTailCall();
2027 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Inserting new Retain: " << *Call
2029 " At insertion point: " << *InsertPt
2033 // Delete the original retain and release calls.
2034 for (SmallPtrSet<Instruction *, 2>::const_iterator
2035 AI = RetainsToMove.Calls.begin(),
2036 AE = RetainsToMove.Calls.end(); AI != AE; ++AI) {
2037 Instruction *OrigRetain = *AI;
2038 Retains.blot(OrigRetain);
2039 DeadInsts.push_back(OrigRetain);
2040 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Deleting retain: " << *OrigRetain <<
2043 for (SmallPtrSet<Instruction *, 2>::const_iterator
2044 AI = ReleasesToMove.Calls.begin(),
2045 AE = ReleasesToMove.Calls.end(); AI != AE; ++AI) {
2046 Instruction *OrigRelease = *AI;
2047 Releases.erase(OrigRelease);
2048 DeadInsts.push_back(OrigRelease);
2049 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Deleting release: " << *OrigRelease
2055 ObjCARCOpt::ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState>
2057 MapVector<Value *, RRInfo> &Retains,
2058 DenseMap<Value *, RRInfo> &Releases,
2060 SmallVector<Instruction *, 4> &NewRetains,
2061 SmallVector<Instruction *, 4> &NewReleases,
2062 SmallVector<Instruction *, 8> &DeadInsts,
2063 RRInfo &RetainsToMove,
2064 RRInfo &ReleasesToMove,
2067 bool &AnyPairsCompletelyEliminated) {
2068 // If a pair happens in a region where it is known that the reference count
2069 // is already incremented, we can similarly ignore possible decrements.
2070 bool KnownSafeTD = true, KnownSafeBU = true;
2072 // Connect the dots between the top-down-collected RetainsToMove and
2073 // bottom-up-collected ReleasesToMove to form sets of related calls.
2074 // This is an iterative process so that we connect multiple releases
2075 // to multiple retains if needed.
2076 unsigned OldDelta = 0;
2077 unsigned NewDelta = 0;
2078 unsigned OldCount = 0;
2079 unsigned NewCount = 0;
2080 bool FirstRelease = true;
2081 bool FirstRetain = true;
2083 for (SmallVectorImpl<Instruction *>::const_iterator
2084 NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) {
2085 Instruction *NewRetain = *NI;
2086 MapVector<Value *, RRInfo>::const_iterator It = Retains.find(NewRetain);
2087 assert(It != Retains.end());
2088 const RRInfo &NewRetainRRI = It->second;
2089 KnownSafeTD &= NewRetainRRI.KnownSafe;
2090 for (SmallPtrSet<Instruction *, 2>::const_iterator
2091 LI = NewRetainRRI.Calls.begin(),
2092 LE = NewRetainRRI.Calls.end(); LI != LE; ++LI) {
2093 Instruction *NewRetainRelease = *LI;
2094 DenseMap<Value *, RRInfo>::const_iterator Jt =
2095 Releases.find(NewRetainRelease);
2096 if (Jt == Releases.end())
2098 const RRInfo &NewRetainReleaseRRI = Jt->second;
2099 assert(NewRetainReleaseRRI.Calls.count(NewRetain));
2100 if (ReleasesToMove.Calls.insert(NewRetainRelease)) {
2102 BBStates[NewRetainRelease->getParent()].GetAllPathCount();
2104 // Merge the ReleaseMetadata and IsTailCallRelease values.
2106 ReleasesToMove.ReleaseMetadata =
2107 NewRetainReleaseRRI.ReleaseMetadata;
2108 ReleasesToMove.IsTailCallRelease =
2109 NewRetainReleaseRRI.IsTailCallRelease;
2110 FirstRelease = false;
2112 if (ReleasesToMove.ReleaseMetadata !=
2113 NewRetainReleaseRRI.ReleaseMetadata)
2114 ReleasesToMove.ReleaseMetadata = 0;
2115 if (ReleasesToMove.IsTailCallRelease !=
2116 NewRetainReleaseRRI.IsTailCallRelease)
2117 ReleasesToMove.IsTailCallRelease = false;
2120 // Collect the optimal insertion points.
2122 for (SmallPtrSet<Instruction *, 2>::const_iterator
2123 RI = NewRetainReleaseRRI.ReverseInsertPts.begin(),
2124 RE = NewRetainReleaseRRI.ReverseInsertPts.end();
2126 Instruction *RIP = *RI;
2127 if (ReleasesToMove.ReverseInsertPts.insert(RIP))
2128 NewDelta -= BBStates[RIP->getParent()].GetAllPathCount();
2130 NewReleases.push_back(NewRetainRelease);
2135 if (NewReleases.empty()) break;
2137 // Back the other way.
2138 for (SmallVectorImpl<Instruction *>::const_iterator
2139 NI = NewReleases.begin(), NE = NewReleases.end(); NI != NE; ++NI) {
2140 Instruction *NewRelease = *NI;
2141 DenseMap<Value *, RRInfo>::const_iterator It =
2142 Releases.find(NewRelease);
2143 assert(It != Releases.end());
2144 const RRInfo &NewReleaseRRI = It->second;
2145 KnownSafeBU &= NewReleaseRRI.KnownSafe;
2146 for (SmallPtrSet<Instruction *, 2>::const_iterator
2147 LI = NewReleaseRRI.Calls.begin(),
2148 LE = NewReleaseRRI.Calls.end(); LI != LE; ++LI) {
2149 Instruction *NewReleaseRetain = *LI;
2150 MapVector<Value *, RRInfo>::const_iterator Jt =
2151 Retains.find(NewReleaseRetain);
2152 if (Jt == Retains.end())
2154 const RRInfo &NewReleaseRetainRRI = Jt->second;
2155 assert(NewReleaseRetainRRI.Calls.count(NewRelease));
2156 if (RetainsToMove.Calls.insert(NewReleaseRetain)) {
2157 unsigned PathCount =
2158 BBStates[NewReleaseRetain->getParent()].GetAllPathCount();
2159 OldDelta += PathCount;
2160 OldCount += PathCount;
2162 // Merge the IsRetainBlock values.
2164 RetainsToMove.IsRetainBlock = NewReleaseRetainRRI.IsRetainBlock;
2165 FirstRetain = false;
2166 } else if (ReleasesToMove.IsRetainBlock !=
2167 NewReleaseRetainRRI.IsRetainBlock)
2168 // It's not possible to merge the sequences if one uses
2169 // objc_retain and the other uses objc_retainBlock.
2172 // Collect the optimal insertion points.
2174 for (SmallPtrSet<Instruction *, 2>::const_iterator
2175 RI = NewReleaseRetainRRI.ReverseInsertPts.begin(),
2176 RE = NewReleaseRetainRRI.ReverseInsertPts.end();
2178 Instruction *RIP = *RI;
2179 if (RetainsToMove.ReverseInsertPts.insert(RIP)) {
2180 PathCount = BBStates[RIP->getParent()].GetAllPathCount();
2181 NewDelta += PathCount;
2182 NewCount += PathCount;
2185 NewRetains.push_back(NewReleaseRetain);
2189 NewReleases.clear();
2190 if (NewRetains.empty()) break;
2193 // If the pointer is known incremented or nested, we can safely delete the
2194 // pair regardless of what's between them.
2195 if (KnownSafeTD || KnownSafeBU) {
2196 RetainsToMove.ReverseInsertPts.clear();
2197 ReleasesToMove.ReverseInsertPts.clear();
2200 // Determine whether the new insertion points we computed preserve the
2201 // balance of retain and release calls through the program.
2202 // TODO: If the fully aggressive solution isn't valid, try to find a
2203 // less aggressive solution which is.
2208 // Determine whether the original call points are balanced in the retain and
2209 // release calls through the program. If not, conservatively don't touch
2211 // TODO: It's theoretically possible to do code motion in this case, as
2212 // long as the existing imbalances are maintained.
2217 assert(OldCount != 0 && "Unreachable code?");
2218 NumRRs += OldCount - NewCount;
2219 // Set to true if we completely removed any RR pairs.
2220 AnyPairsCompletelyEliminated = NewCount == 0;
2222 // We can move calls!
2226 /// Identify pairings between the retains and releases, and delete and/or move
2229 ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState>
2231 MapVector<Value *, RRInfo> &Retains,
2232 DenseMap<Value *, RRInfo> &Releases,
2234 bool AnyPairsCompletelyEliminated = false;
2235 RRInfo RetainsToMove;
2236 RRInfo ReleasesToMove;
2237 SmallVector<Instruction *, 4> NewRetains;
2238 SmallVector<Instruction *, 4> NewReleases;
2239 SmallVector<Instruction *, 8> DeadInsts;
2241 // Visit each retain.
2242 for (MapVector<Value *, RRInfo>::const_iterator I = Retains.begin(),
2243 E = Retains.end(); I != E; ++I) {
2244 Value *V = I->first;
2245 if (!V) continue; // blotted
2247 Instruction *Retain = cast<Instruction>(V);
2249 DEBUG(dbgs() << "ObjCARCOpt::PerformCodePlacement: Visiting: " << *Retain
2252 Value *Arg = GetObjCArg(Retain);
2254 // If the object being released is in static or stack storage, we know it's
2255 // not being managed by ObjC reference counting, so we can delete pairs
2256 // regardless of what possible decrements or uses lie between them.
2257 bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg);
2259 // A constant pointer can't be pointing to an object on the heap. It may
2260 // be reference-counted, but it won't be deleted.
2261 if (const LoadInst *LI = dyn_cast<LoadInst>(Arg))
2262 if (const GlobalVariable *GV =
2263 dyn_cast<GlobalVariable>(
2264 StripPointerCastsAndObjCCalls(LI->getPointerOperand())))
2265 if (GV->isConstant())
2268 // Connect the dots between the top-down-collected RetainsToMove and
2269 // bottom-up-collected ReleasesToMove to form sets of related calls.
2270 NewRetains.push_back(Retain);
2271 bool PerformMoveCalls =
2272 ConnectTDBUTraversals(BBStates, Retains, Releases, M, NewRetains,
2273 NewReleases, DeadInsts, RetainsToMove,
2274 ReleasesToMove, Arg, KnownSafe,
2275 AnyPairsCompletelyEliminated);
2277 if (PerformMoveCalls) {
2278 // Ok, everything checks out and we're all set. Let's move/delete some
2280 MoveCalls(Arg, RetainsToMove, ReleasesToMove,
2281 Retains, Releases, DeadInsts, M);
2284 // Clean up state for next retain.
2285 NewReleases.clear();
2287 RetainsToMove.clear();
2288 ReleasesToMove.clear();
2291 // Now that we're done moving everything, we can delete the newly dead
2292 // instructions, as we no longer need them as insert points.
2293 while (!DeadInsts.empty())
2294 EraseInstruction(DeadInsts.pop_back_val());
2296 return AnyPairsCompletelyEliminated;
2299 /// Weak pointer optimizations.
2300 void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
2301 // First, do memdep-style RLE and S2L optimizations. We can't use memdep
2302 // itself because it uses AliasAnalysis and we need to do provenance
2304 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2305 Instruction *Inst = &*I++;
2307 DEBUG(dbgs() << "ObjCARCOpt::OptimizeWeakCalls: Visiting: " << *Inst <<
2310 InstructionClass Class = GetBasicInstructionClass(Inst);
2311 if (Class != IC_LoadWeak && Class != IC_LoadWeakRetained)
2314 // Delete objc_loadWeak calls with no users.
2315 if (Class == IC_LoadWeak && Inst->use_empty()) {
2316 Inst->eraseFromParent();
2320 // TODO: For now, just look for an earlier available version of this value
2321 // within the same block. Theoretically, we could do memdep-style non-local
2322 // analysis too, but that would want caching. A better approach would be to
2323 // use the technique that EarlyCSE uses.
2324 inst_iterator Current = llvm::prior(I);
2325 BasicBlock *CurrentBB = Current.getBasicBlockIterator();
2326 for (BasicBlock::iterator B = CurrentBB->begin(),
2327 J = Current.getInstructionIterator();
2329 Instruction *EarlierInst = &*llvm::prior(J);
2330 InstructionClass EarlierClass = GetInstructionClass(EarlierInst);
2331 switch (EarlierClass) {
2333 case IC_LoadWeakRetained: {
2334 // If this is loading from the same pointer, replace this load's value
2336 CallInst *Call = cast<CallInst>(Inst);
2337 CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2338 Value *Arg = Call->getArgOperand(0);
2339 Value *EarlierArg = EarlierCall->getArgOperand(0);
2340 switch (PA.getAA()->alias(Arg, EarlierArg)) {
2341 case AliasAnalysis::MustAlias:
2343 // If the load has a builtin retain, insert a plain retain for it.
2344 if (Class == IC_LoadWeakRetained) {
2346 CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
2350 // Zap the fully redundant load.
2351 Call->replaceAllUsesWith(EarlierCall);
2352 Call->eraseFromParent();
2354 case AliasAnalysis::MayAlias:
2355 case AliasAnalysis::PartialAlias:
2357 case AliasAnalysis::NoAlias:
2364 // If this is storing to the same pointer and has the same size etc.
2365 // replace this load's value with the stored value.
2366 CallInst *Call = cast<CallInst>(Inst);
2367 CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2368 Value *Arg = Call->getArgOperand(0);
2369 Value *EarlierArg = EarlierCall->getArgOperand(0);
2370 switch (PA.getAA()->alias(Arg, EarlierArg)) {
2371 case AliasAnalysis::MustAlias:
2373 // If the load has a builtin retain, insert a plain retain for it.
2374 if (Class == IC_LoadWeakRetained) {
2376 CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
2380 // Zap the fully redundant load.
2381 Call->replaceAllUsesWith(EarlierCall->getArgOperand(1));
2382 Call->eraseFromParent();
2384 case AliasAnalysis::MayAlias:
2385 case AliasAnalysis::PartialAlias:
2387 case AliasAnalysis::NoAlias:
2394 // TOOD: Grab the copied value.
2396 case IC_AutoreleasepoolPush:
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() {