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 "ObjCARCAliasAnalysis.h"
34 #include "ProvenanceAnalysis.h"
35 #include "DependencyAnalysis.h"
37 #include "llvm/ADT/DenseMap.h"
38 #include "llvm/ADT/STLExtras.h"
39 #include "llvm/ADT/SmallPtrSet.h"
40 #include "llvm/Support/CFG.h"
43 using namespace llvm::objcarc;
45 /// \defgroup MiscUtils Miscellaneous utilities that are not ARC specific.
49 /// \brief An associative container with fast insertion-order (deterministic)
50 /// iteration over its elements. Plus the special blot operation.
51 template<class KeyT, class ValueT>
53 /// Map keys to indices in Vector.
54 typedef DenseMap<KeyT, size_t> MapTy;
57 typedef std::vector<std::pair<KeyT, ValueT> > VectorTy;
62 typedef typename VectorTy::iterator iterator;
63 typedef typename VectorTy::const_iterator const_iterator;
64 iterator begin() { return Vector.begin(); }
65 iterator end() { return Vector.end(); }
66 const_iterator begin() const { return Vector.begin(); }
67 const_iterator end() const { return Vector.end(); }
71 assert(Vector.size() >= Map.size()); // May differ due to blotting.
72 for (typename MapTy::const_iterator I = Map.begin(), E = Map.end();
74 assert(I->second < Vector.size());
75 assert(Vector[I->second].first == I->first);
77 for (typename VectorTy::const_iterator I = Vector.begin(),
78 E = Vector.end(); I != E; ++I)
80 (Map.count(I->first) &&
81 Map[I->first] == size_t(I - Vector.begin())));
85 ValueT &operator[](const KeyT &Arg) {
86 std::pair<typename MapTy::iterator, bool> Pair =
87 Map.insert(std::make_pair(Arg, size_t(0)));
89 size_t Num = Vector.size();
90 Pair.first->second = Num;
91 Vector.push_back(std::make_pair(Arg, ValueT()));
92 return Vector[Num].second;
94 return Vector[Pair.first->second].second;
97 std::pair<iterator, bool>
98 insert(const std::pair<KeyT, ValueT> &InsertPair) {
99 std::pair<typename MapTy::iterator, bool> Pair =
100 Map.insert(std::make_pair(InsertPair.first, size_t(0)));
102 size_t Num = Vector.size();
103 Pair.first->second = Num;
104 Vector.push_back(InsertPair);
105 return std::make_pair(Vector.begin() + Num, true);
107 return std::make_pair(Vector.begin() + Pair.first->second, false);
110 const_iterator find(const KeyT &Key) const {
111 typename MapTy::const_iterator It = Map.find(Key);
112 if (It == Map.end()) return Vector.end();
113 return Vector.begin() + It->second;
116 /// This is similar to erase, but instead of removing the element from the
117 /// vector, it just zeros out the key in the vector. This leaves iterators
118 /// intact, but clients must be prepared for zeroed-out keys when iterating.
119 void blot(const KeyT &Key) {
120 typename MapTy::iterator It = Map.find(Key);
121 if (It == Map.end()) return;
122 Vector[It->second].first = KeyT();
135 /// \defgroup ARCUtilities Utility declarations/definitions specific to ARC.
138 /// \brief This is similar to StripPointerCastsAndObjCCalls but it stops as soon
139 /// as it finds a value with multiple uses.
140 static const Value *FindSingleUseIdentifiedObject(const Value *Arg) {
141 if (Arg->hasOneUse()) {
142 if (const BitCastInst *BC = dyn_cast<BitCastInst>(Arg))
143 return FindSingleUseIdentifiedObject(BC->getOperand(0));
144 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Arg))
145 if (GEP->hasAllZeroIndices())
146 return FindSingleUseIdentifiedObject(GEP->getPointerOperand());
147 if (IsForwarding(GetBasicInstructionClass(Arg)))
148 return FindSingleUseIdentifiedObject(
149 cast<CallInst>(Arg)->getArgOperand(0));
150 if (!IsObjCIdentifiedObject(Arg))
155 // If we found an identifiable object but it has multiple uses, but they are
156 // trivial uses, we can still consider this to be a single-use value.
157 if (IsObjCIdentifiedObject(Arg)) {
158 for (Value::const_use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
161 if (!U->use_empty() || StripPointerCastsAndObjCCalls(U) != Arg)
171 /// \brief Test whether the given pointer, which is an Objective C block
172 /// pointer, does not "escape".
174 /// This differs from regular escape analysis in that a use as an
175 /// argument to a call is not considered an escape.
177 static bool DoesObjCBlockEscape(const Value *BlockPtr) {
179 DEBUG(dbgs() << "DoesObjCBlockEscape: Target: " << *BlockPtr << "\n");
181 // Walk the def-use chains.
182 SmallVector<const Value *, 4> Worklist;
183 Worklist.push_back(BlockPtr);
185 // Ensure we do not visit any value twice.
186 SmallPtrSet<const Value *, 4> VisitedSet;
189 const Value *V = Worklist.pop_back_val();
191 DEBUG(dbgs() << "DoesObjCBlockEscape: Visiting: " << *V << "\n");
193 for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end();
195 const User *UUser = *UI;
197 DEBUG(dbgs() << "DoesObjCBlockEscape: User: " << *UUser << "\n");
199 // Special - Use by a call (callee or argument) is not considered
201 switch (GetBasicInstructionClass(UUser)) {
206 case IC_AutoreleaseRV: {
207 DEBUG(dbgs() << "DoesObjCBlockEscape: User copies pointer arguments. "
209 // These special functions make copies of their pointer arguments.
214 // Use by an instruction which copies the value is an escape if the
215 // result is an escape.
216 if (isa<BitCastInst>(UUser) || isa<GetElementPtrInst>(UUser) ||
217 isa<PHINode>(UUser) || isa<SelectInst>(UUser)) {
219 if (!VisitedSet.insert(UUser)) {
220 DEBUG(dbgs() << "DoesObjCBlockEscape: User copies value. Escapes "
221 "if result escapes. Adding to list.\n");
222 Worklist.push_back(UUser);
224 DEBUG(dbgs() << "DoesObjCBlockEscape: Already visited node.\n");
228 // Use by a load is not an escape.
229 if (isa<LoadInst>(UUser))
231 // Use by a store is not an escape if the use is the address.
232 if (const StoreInst *SI = dyn_cast<StoreInst>(UUser))
233 if (V != SI->getValueOperand())
237 // Regular calls and other stuff are not considered escapes.
240 // Otherwise, conservatively assume an escape.
241 DEBUG(dbgs() << "DoesObjCBlockEscape: Assuming block escapes.\n");
244 } while (!Worklist.empty());
247 DEBUG(dbgs() << "DoesObjCBlockEscape: Block does not escape.\n");
253 /// \defgroup ARCOpt ARC Optimization.
256 // TODO: On code like this:
259 // stuff_that_cannot_release()
260 // objc_autorelease(%x)
261 // stuff_that_cannot_release()
263 // stuff_that_cannot_release()
264 // objc_autorelease(%x)
266 // The second retain and autorelease can be deleted.
268 // TODO: It should be possible to delete
269 // objc_autoreleasePoolPush and objc_autoreleasePoolPop
270 // pairs if nothing is actually autoreleased between them. Also, autorelease
271 // calls followed by objc_autoreleasePoolPop calls (perhaps in ObjC++ code
272 // after inlining) can be turned into plain release calls.
274 // TODO: Critical-edge splitting. If the optimial insertion point is
275 // a critical edge, the current algorithm has to fail, because it doesn't
276 // know how to split edges. It should be possible to make the optimizer
277 // think in terms of edges, rather than blocks, and then split critical
280 // TODO: OptimizeSequences could generalized to be Interprocedural.
282 // TODO: Recognize that a bunch of other objc runtime calls have
283 // non-escaping arguments and non-releasing arguments, and may be
284 // non-autoreleasing.
286 // TODO: Sink autorelease calls as far as possible. Unfortunately we
287 // usually can't sink them past other calls, which would be the main
288 // case where it would be useful.
290 // TODO: The pointer returned from objc_loadWeakRetained is retained.
292 // TODO: Delete release+retain pairs (rare).
294 #include "llvm/ADT/SmallPtrSet.h"
295 #include "llvm/ADT/Statistic.h"
296 #include "llvm/IR/LLVMContext.h"
298 STATISTIC(NumNoops, "Number of no-op objc calls eliminated");
299 STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated");
300 STATISTIC(NumAutoreleases,"Number of autoreleases converted to releases");
301 STATISTIC(NumRets, "Number of return value forwarding "
302 "retain+autoreleaes eliminated");
303 STATISTIC(NumRRs, "Number of retain+release paths eliminated");
304 STATISTIC(NumPeeps, "Number of calls peephole-optimized");
309 /// \brief A sequence of states that a pointer may go through in which an
310 /// objc_retain and objc_release are actually needed.
313 S_Retain, ///< objc_retain(x)
314 S_CanRelease, ///< foo(x) -- x could possibly see a ref count decrement
315 S_Use, ///< any use of x
316 S_Stop, ///< like S_Release, but code motion is stopped
317 S_Release, ///< objc_release(x)
318 S_MovableRelease ///< objc_release(x), !clang.imprecise_release
322 static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) {
326 if (A == S_None || B == S_None)
329 if (A > B) std::swap(A, B);
331 // Choose the side which is further along in the sequence.
332 if ((A == S_Retain || A == S_CanRelease) &&
333 (B == S_CanRelease || B == S_Use))
336 // Choose the side which is further along in the sequence.
337 if ((A == S_Use || A == S_CanRelease) &&
338 (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease))
340 // If both sides are releases, choose the more conservative one.
341 if (A == S_Stop && (B == S_Release || B == S_MovableRelease))
343 if (A == S_Release && B == S_MovableRelease)
351 /// \brief Unidirectional information about either a
352 /// retain-decrement-use-release sequence or release-use-decrement-retain
353 /// reverese sequence.
355 /// After an objc_retain, the reference count of the referenced
356 /// object is known to be positive. Similarly, before an objc_release, the
357 /// reference count of the referenced object is known to be positive. If
358 /// there are retain-release pairs in code regions where the retain count
359 /// is known to be positive, they can be eliminated, regardless of any side
360 /// effects between them.
362 /// Also, a retain+release pair nested within another retain+release
363 /// pair all on the known same pointer value can be eliminated, regardless
364 /// of any intervening side effects.
366 /// KnownSafe is true when either of these conditions is satisfied.
369 /// True if the Calls are objc_retainBlock calls (as opposed to objc_retain
373 /// True of the objc_release calls are all marked with the "tail" keyword.
374 bool IsTailCallRelease;
376 /// If the Calls are objc_release calls and they all have a
377 /// clang.imprecise_release tag, this is the metadata tag.
378 MDNode *ReleaseMetadata;
380 /// For a top-down sequence, the set of objc_retains or
381 /// objc_retainBlocks. For bottom-up, the set of objc_releases.
382 SmallPtrSet<Instruction *, 2> Calls;
384 /// The set of optimal insert positions for moving calls in the opposite
386 SmallPtrSet<Instruction *, 2> ReverseInsertPts;
389 KnownSafe(false), IsRetainBlock(false),
390 IsTailCallRelease(false),
391 ReleaseMetadata(0) {}
397 void RRInfo::clear() {
399 IsRetainBlock = false;
400 IsTailCallRelease = false;
403 ReverseInsertPts.clear();
407 /// \brief This class summarizes several per-pointer runtime properties which
408 /// are propogated through the flow graph.
410 /// True if the reference count is known to be incremented.
411 bool KnownPositiveRefCount;
413 /// True of we've seen an opportunity for partial RR elimination, such as
414 /// pushing calls into a CFG triangle or into one side of a CFG diamond.
417 /// The current position in the sequence.
421 /// Unidirectional information about the current sequence.
423 /// TODO: Encapsulate this better.
426 PtrState() : KnownPositiveRefCount(false), Partial(false),
429 void SetKnownPositiveRefCount() {
430 KnownPositiveRefCount = true;
433 void ClearRefCount() {
434 KnownPositiveRefCount = false;
437 bool IsKnownIncremented() const {
438 return KnownPositiveRefCount;
441 void SetSeq(Sequence NewSeq) {
445 Sequence GetSeq() const {
449 void ClearSequenceProgress() {
450 ResetSequenceProgress(S_None);
453 void ResetSequenceProgress(Sequence NewSeq) {
459 void Merge(const PtrState &Other, bool TopDown);
464 PtrState::Merge(const PtrState &Other, bool TopDown) {
465 Seq = MergeSeqs(Seq, Other.Seq, TopDown);
466 KnownPositiveRefCount = KnownPositiveRefCount && Other.KnownPositiveRefCount;
468 // We can't merge a plain objc_retain with an objc_retainBlock.
469 if (RRI.IsRetainBlock != Other.RRI.IsRetainBlock)
472 // If we're not in a sequence (anymore), drop all associated state.
476 } else if (Partial || Other.Partial) {
477 // If we're doing a merge on a path that's previously seen a partial
478 // merge, conservatively drop the sequence, to avoid doing partial
479 // RR elimination. If the branch predicates for the two merge differ,
480 // mixing them is unsafe.
481 ClearSequenceProgress();
483 // Conservatively merge the ReleaseMetadata information.
484 if (RRI.ReleaseMetadata != Other.RRI.ReleaseMetadata)
485 RRI.ReleaseMetadata = 0;
487 RRI.KnownSafe = RRI.KnownSafe && Other.RRI.KnownSafe;
488 RRI.IsTailCallRelease = RRI.IsTailCallRelease &&
489 Other.RRI.IsTailCallRelease;
490 RRI.Calls.insert(Other.RRI.Calls.begin(), Other.RRI.Calls.end());
492 // Merge the insert point sets. If there are any differences,
493 // that makes this a partial merge.
494 Partial = RRI.ReverseInsertPts.size() != Other.RRI.ReverseInsertPts.size();
495 for (SmallPtrSet<Instruction *, 2>::const_iterator
496 I = Other.RRI.ReverseInsertPts.begin(),
497 E = Other.RRI.ReverseInsertPts.end(); I != E; ++I)
498 Partial |= RRI.ReverseInsertPts.insert(*I);
503 /// \brief Per-BasicBlock state.
505 /// The number of unique control paths from the entry which can reach this
507 unsigned TopDownPathCount;
509 /// The number of unique control paths to exits from this block.
510 unsigned BottomUpPathCount;
512 /// A type for PerPtrTopDown and PerPtrBottomUp.
513 typedef MapVector<const Value *, PtrState> MapTy;
515 /// The top-down traversal uses this to record information known about a
516 /// pointer at the bottom of each block.
519 /// The bottom-up traversal uses this to record information known about a
520 /// pointer at the top of each block.
521 MapTy PerPtrBottomUp;
523 /// Effective predecessors of the current block ignoring ignorable edges and
524 /// ignored backedges.
525 SmallVector<BasicBlock *, 2> Preds;
526 /// Effective successors of the current block ignoring ignorable edges and
527 /// ignored backedges.
528 SmallVector<BasicBlock *, 2> Succs;
531 BBState() : TopDownPathCount(0), BottomUpPathCount(0) {}
533 typedef MapTy::iterator ptr_iterator;
534 typedef MapTy::const_iterator ptr_const_iterator;
536 ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); }
537 ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); }
538 ptr_const_iterator top_down_ptr_begin() const {
539 return PerPtrTopDown.begin();
541 ptr_const_iterator top_down_ptr_end() const {
542 return PerPtrTopDown.end();
545 ptr_iterator bottom_up_ptr_begin() { return PerPtrBottomUp.begin(); }
546 ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); }
547 ptr_const_iterator bottom_up_ptr_begin() const {
548 return PerPtrBottomUp.begin();
550 ptr_const_iterator bottom_up_ptr_end() const {
551 return PerPtrBottomUp.end();
554 /// Mark this block as being an entry block, which has one path from the
555 /// entry by definition.
556 void SetAsEntry() { TopDownPathCount = 1; }
558 /// Mark this block as being an exit block, which has one path to an exit by
560 void SetAsExit() { BottomUpPathCount = 1; }
562 PtrState &getPtrTopDownState(const Value *Arg) {
563 return PerPtrTopDown[Arg];
566 PtrState &getPtrBottomUpState(const Value *Arg) {
567 return PerPtrBottomUp[Arg];
570 void clearBottomUpPointers() {
571 PerPtrBottomUp.clear();
574 void clearTopDownPointers() {
575 PerPtrTopDown.clear();
578 void InitFromPred(const BBState &Other);
579 void InitFromSucc(const BBState &Other);
580 void MergePred(const BBState &Other);
581 void MergeSucc(const BBState &Other);
583 /// Return the number of possible unique paths from an entry to an exit
584 /// which pass through this block. This is only valid after both the
585 /// top-down and bottom-up traversals are complete.
586 unsigned GetAllPathCount() const {
587 assert(TopDownPathCount != 0);
588 assert(BottomUpPathCount != 0);
589 return TopDownPathCount * BottomUpPathCount;
592 // Specialized CFG utilities.
593 typedef SmallVectorImpl<BasicBlock *>::const_iterator edge_iterator;
594 edge_iterator pred_begin() { return Preds.begin(); }
595 edge_iterator pred_end() { return Preds.end(); }
596 edge_iterator succ_begin() { return Succs.begin(); }
597 edge_iterator succ_end() { return Succs.end(); }
599 void addSucc(BasicBlock *Succ) { Succs.push_back(Succ); }
600 void addPred(BasicBlock *Pred) { Preds.push_back(Pred); }
602 bool isExit() const { return Succs.empty(); }
606 void BBState::InitFromPred(const BBState &Other) {
607 PerPtrTopDown = Other.PerPtrTopDown;
608 TopDownPathCount = Other.TopDownPathCount;
611 void BBState::InitFromSucc(const BBState &Other) {
612 PerPtrBottomUp = Other.PerPtrBottomUp;
613 BottomUpPathCount = Other.BottomUpPathCount;
616 /// The top-down traversal uses this to merge information about predecessors to
617 /// form the initial state for a new block.
618 void BBState::MergePred(const BBState &Other) {
619 // Other.TopDownPathCount can be 0, in which case it is either dead or a
620 // loop backedge. Loop backedges are special.
621 TopDownPathCount += Other.TopDownPathCount;
623 // Check for overflow. If we have overflow, fall back to conservative
625 if (TopDownPathCount < Other.TopDownPathCount) {
626 clearTopDownPointers();
630 // For each entry in the other set, if our set has an entry with the same key,
631 // merge the entries. Otherwise, copy the entry and merge it with an empty
633 for (ptr_const_iterator MI = Other.top_down_ptr_begin(),
634 ME = Other.top_down_ptr_end(); MI != ME; ++MI) {
635 std::pair<ptr_iterator, bool> Pair = PerPtrTopDown.insert(*MI);
636 Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
640 // For each entry in our set, if the other set doesn't have an entry with the
641 // same key, force it to merge with an empty entry.
642 for (ptr_iterator MI = top_down_ptr_begin(),
643 ME = top_down_ptr_end(); MI != ME; ++MI)
644 if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end())
645 MI->second.Merge(PtrState(), /*TopDown=*/true);
648 /// The bottom-up traversal uses this to merge information about successors to
649 /// form the initial state for a new block.
650 void BBState::MergeSucc(const BBState &Other) {
651 // Other.BottomUpPathCount can be 0, in which case it is either dead or a
652 // loop backedge. Loop backedges are special.
653 BottomUpPathCount += Other.BottomUpPathCount;
655 // Check for overflow. If we have overflow, fall back to conservative
657 if (BottomUpPathCount < Other.BottomUpPathCount) {
658 clearBottomUpPointers();
662 // For each entry in the other set, if our set has an entry with the
663 // same key, merge the entries. Otherwise, copy the entry and merge
664 // it with an empty entry.
665 for (ptr_const_iterator MI = Other.bottom_up_ptr_begin(),
666 ME = Other.bottom_up_ptr_end(); MI != ME; ++MI) {
667 std::pair<ptr_iterator, bool> Pair = PerPtrBottomUp.insert(*MI);
668 Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
672 // For each entry in our set, if the other set doesn't have an entry
673 // with the same key, force it to merge with an empty entry.
674 for (ptr_iterator MI = bottom_up_ptr_begin(),
675 ME = bottom_up_ptr_end(); MI != ME; ++MI)
676 if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end())
677 MI->second.Merge(PtrState(), /*TopDown=*/false);
681 /// \brief The main ARC optimization pass.
682 class ObjCARCOpt : public FunctionPass {
684 ProvenanceAnalysis PA;
686 /// A flag indicating whether this optimization pass should run.
689 /// Declarations for ObjC runtime functions, for use in creating calls to
690 /// them. These are initialized lazily to avoid cluttering up the Module
691 /// with unused declarations.
693 /// Declaration for ObjC runtime function
694 /// objc_retainAutoreleasedReturnValue.
695 Constant *RetainRVCallee;
696 /// Declaration for ObjC runtime function objc_autoreleaseReturnValue.
697 Constant *AutoreleaseRVCallee;
698 /// Declaration for ObjC runtime function objc_release.
699 Constant *ReleaseCallee;
700 /// Declaration for ObjC runtime function objc_retain.
701 Constant *RetainCallee;
702 /// Declaration for ObjC runtime function objc_retainBlock.
703 Constant *RetainBlockCallee;
704 /// Declaration for ObjC runtime function objc_autorelease.
705 Constant *AutoreleaseCallee;
707 /// Flags which determine whether each of the interesting runtine functions
708 /// is in fact used in the current function.
709 unsigned UsedInThisFunction;
711 /// The Metadata Kind for clang.imprecise_release metadata.
712 unsigned ImpreciseReleaseMDKind;
714 /// The Metadata Kind for clang.arc.copy_on_escape metadata.
715 unsigned CopyOnEscapeMDKind;
717 /// The Metadata Kind for clang.arc.no_objc_arc_exceptions metadata.
718 unsigned NoObjCARCExceptionsMDKind;
720 Constant *getRetainRVCallee(Module *M);
721 Constant *getAutoreleaseRVCallee(Module *M);
722 Constant *getReleaseCallee(Module *M);
723 Constant *getRetainCallee(Module *M);
724 Constant *getRetainBlockCallee(Module *M);
725 Constant *getAutoreleaseCallee(Module *M);
727 bool IsRetainBlockOptimizable(const Instruction *Inst);
729 void OptimizeRetainCall(Function &F, Instruction *Retain);
730 bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV);
731 void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV,
732 InstructionClass &Class);
733 void OptimizeIndividualCalls(Function &F);
735 void CheckForCFGHazards(const BasicBlock *BB,
736 DenseMap<const BasicBlock *, BBState> &BBStates,
737 BBState &MyStates) const;
738 bool VisitInstructionBottomUp(Instruction *Inst,
740 MapVector<Value *, RRInfo> &Retains,
742 bool VisitBottomUp(BasicBlock *BB,
743 DenseMap<const BasicBlock *, BBState> &BBStates,
744 MapVector<Value *, RRInfo> &Retains);
745 bool VisitInstructionTopDown(Instruction *Inst,
746 DenseMap<Value *, RRInfo> &Releases,
748 bool VisitTopDown(BasicBlock *BB,
749 DenseMap<const BasicBlock *, BBState> &BBStates,
750 DenseMap<Value *, RRInfo> &Releases);
751 bool Visit(Function &F,
752 DenseMap<const BasicBlock *, BBState> &BBStates,
753 MapVector<Value *, RRInfo> &Retains,
754 DenseMap<Value *, RRInfo> &Releases);
756 void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove,
757 MapVector<Value *, RRInfo> &Retains,
758 DenseMap<Value *, RRInfo> &Releases,
759 SmallVectorImpl<Instruction *> &DeadInsts,
762 bool ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState> &BBStates,
763 MapVector<Value *, RRInfo> &Retains,
764 DenseMap<Value *, RRInfo> &Releases,
766 SmallVector<Instruction *, 4> &NewRetains,
767 SmallVector<Instruction *, 4> &NewReleases,
768 SmallVector<Instruction *, 8> &DeadInsts,
769 RRInfo &RetainsToMove,
770 RRInfo &ReleasesToMove,
773 bool &AnyPairsCompletelyEliminated);
775 bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates,
776 MapVector<Value *, RRInfo> &Retains,
777 DenseMap<Value *, RRInfo> &Releases,
780 void OptimizeWeakCalls(Function &F);
782 bool OptimizeSequences(Function &F);
784 void OptimizeReturns(Function &F);
786 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
787 virtual bool doInitialization(Module &M);
788 virtual bool runOnFunction(Function &F);
789 virtual void releaseMemory();
793 ObjCARCOpt() : FunctionPass(ID) {
794 initializeObjCARCOptPass(*PassRegistry::getPassRegistry());
799 char ObjCARCOpt::ID = 0;
800 INITIALIZE_PASS_BEGIN(ObjCARCOpt,
801 "objc-arc", "ObjC ARC optimization", false, false)
802 INITIALIZE_PASS_DEPENDENCY(ObjCARCAliasAnalysis)
803 INITIALIZE_PASS_END(ObjCARCOpt,
804 "objc-arc", "ObjC ARC optimization", false, false)
806 Pass *llvm::createObjCARCOptPass() {
807 return new ObjCARCOpt();
810 void ObjCARCOpt::getAnalysisUsage(AnalysisUsage &AU) const {
811 AU.addRequired<ObjCARCAliasAnalysis>();
812 AU.addRequired<AliasAnalysis>();
813 // ARC optimization doesn't currently split critical edges.
814 AU.setPreservesCFG();
817 bool ObjCARCOpt::IsRetainBlockOptimizable(const Instruction *Inst) {
818 // Without the magic metadata tag, we have to assume this might be an
819 // objc_retainBlock call inserted to convert a block pointer to an id,
820 // in which case it really is needed.
821 if (!Inst->getMetadata(CopyOnEscapeMDKind))
824 // If the pointer "escapes" (not including being used in a call),
825 // the copy may be needed.
826 if (DoesObjCBlockEscape(Inst))
829 // Otherwise, it's not needed.
833 Constant *ObjCARCOpt::getRetainRVCallee(Module *M) {
834 if (!RetainRVCallee) {
835 LLVMContext &C = M->getContext();
836 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
837 Type *Params[] = { I8X };
838 FunctionType *FTy = FunctionType::get(I8X, Params, /*isVarArg=*/false);
839 AttributeSet Attribute =
840 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
841 Attribute::NoUnwind);
843 M->getOrInsertFunction("objc_retainAutoreleasedReturnValue", FTy,
846 return RetainRVCallee;
849 Constant *ObjCARCOpt::getAutoreleaseRVCallee(Module *M) {
850 if (!AutoreleaseRVCallee) {
851 LLVMContext &C = M->getContext();
852 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
853 Type *Params[] = { I8X };
854 FunctionType *FTy = FunctionType::get(I8X, Params, /*isVarArg=*/false);
855 AttributeSet Attribute =
856 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
857 Attribute::NoUnwind);
858 AutoreleaseRVCallee =
859 M->getOrInsertFunction("objc_autoreleaseReturnValue", FTy,
862 return AutoreleaseRVCallee;
865 Constant *ObjCARCOpt::getReleaseCallee(Module *M) {
866 if (!ReleaseCallee) {
867 LLVMContext &C = M->getContext();
868 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
869 AttributeSet Attribute =
870 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
871 Attribute::NoUnwind);
873 M->getOrInsertFunction(
875 FunctionType::get(Type::getVoidTy(C), Params, /*isVarArg=*/false),
878 return ReleaseCallee;
881 Constant *ObjCARCOpt::getRetainCallee(Module *M) {
883 LLVMContext &C = M->getContext();
884 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
885 AttributeSet Attribute =
886 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
887 Attribute::NoUnwind);
889 M->getOrInsertFunction(
891 FunctionType::get(Params[0], Params, /*isVarArg=*/false),
897 Constant *ObjCARCOpt::getRetainBlockCallee(Module *M) {
898 if (!RetainBlockCallee) {
899 LLVMContext &C = M->getContext();
900 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
901 // objc_retainBlock is not nounwind because it calls user copy constructors
902 // which could theoretically throw.
904 M->getOrInsertFunction(
906 FunctionType::get(Params[0], Params, /*isVarArg=*/false),
909 return RetainBlockCallee;
912 Constant *ObjCARCOpt::getAutoreleaseCallee(Module *M) {
913 if (!AutoreleaseCallee) {
914 LLVMContext &C = M->getContext();
915 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
916 AttributeSet Attribute =
917 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
918 Attribute::NoUnwind);
920 M->getOrInsertFunction(
922 FunctionType::get(Params[0], Params, /*isVarArg=*/false),
925 return AutoreleaseCallee;
928 /// Turn objc_retain into objc_retainAutoreleasedReturnValue if the operand is a
931 ObjCARCOpt::OptimizeRetainCall(Function &F, Instruction *Retain) {
932 ImmutableCallSite CS(GetObjCArg(Retain));
933 const Instruction *Call = CS.getInstruction();
935 if (Call->getParent() != Retain->getParent()) return;
937 // Check that the call is next to the retain.
938 BasicBlock::const_iterator I = Call;
940 while (isNoopInstruction(I)) ++I;
944 // Turn it to an objc_retainAutoreleasedReturnValue..
948 DEBUG(dbgs() << "ObjCARCOpt::OptimizeRetainCall: Transforming "
949 "objc_retain => objc_retainAutoreleasedReturnValue"
950 " since the operand is a return value.\n"
954 cast<CallInst>(Retain)->setCalledFunction(getRetainRVCallee(F.getParent()));
956 DEBUG(dbgs() << " New: "
960 /// Turn objc_retainAutoreleasedReturnValue into objc_retain if the operand is
961 /// not a return value. Or, if it can be paired with an
962 /// objc_autoreleaseReturnValue, delete the pair and return true.
964 ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) {
965 // Check for the argument being from an immediately preceding call or invoke.
966 const Value *Arg = GetObjCArg(RetainRV);
967 ImmutableCallSite CS(Arg);
968 if (const Instruction *Call = CS.getInstruction()) {
969 if (Call->getParent() == RetainRV->getParent()) {
970 BasicBlock::const_iterator I = Call;
972 while (isNoopInstruction(I)) ++I;
975 } else if (const InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
976 BasicBlock *RetainRVParent = RetainRV->getParent();
977 if (II->getNormalDest() == RetainRVParent) {
978 BasicBlock::const_iterator I = RetainRVParent->begin();
979 while (isNoopInstruction(I)) ++I;
986 // Check for being preceded by an objc_autoreleaseReturnValue on the same
987 // pointer. In this case, we can delete the pair.
988 BasicBlock::iterator I = RetainRV, Begin = RetainRV->getParent()->begin();
990 do --I; while (I != Begin && isNoopInstruction(I));
991 if (GetBasicInstructionClass(I) == IC_AutoreleaseRV &&
992 GetObjCArg(I) == Arg) {
996 DEBUG(dbgs() << "ObjCARCOpt::OptimizeRetainRVCall: Erasing " << *I << "\n"
997 << " Erasing " << *RetainRV
1000 EraseInstruction(I);
1001 EraseInstruction(RetainRV);
1006 // Turn it to a plain objc_retain.
1010 DEBUG(dbgs() << "ObjCARCOpt::OptimizeRetainRVCall: Transforming "
1011 "objc_retainAutoreleasedReturnValue => "
1012 "objc_retain since the operand is not a return value.\n"
1014 << *RetainRV << "\n");
1016 cast<CallInst>(RetainRV)->setCalledFunction(getRetainCallee(F.getParent()));
1018 DEBUG(dbgs() << " New: "
1019 << *RetainRV << "\n");
1024 /// Turn objc_autoreleaseReturnValue into objc_autorelease if the result is not
1025 /// used as a return value.
1027 ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV,
1028 InstructionClass &Class) {
1029 // Check for a return of the pointer value.
1030 const Value *Ptr = GetObjCArg(AutoreleaseRV);
1031 SmallVector<const Value *, 2> Users;
1032 Users.push_back(Ptr);
1034 Ptr = Users.pop_back_val();
1035 for (Value::const_use_iterator UI = Ptr->use_begin(), UE = Ptr->use_end();
1037 const User *I = *UI;
1038 if (isa<ReturnInst>(I) || GetBasicInstructionClass(I) == IC_RetainRV)
1040 if (isa<BitCastInst>(I))
1043 } while (!Users.empty());
1048 DEBUG(dbgs() << "ObjCARCOpt::OptimizeAutoreleaseRVCall: Transforming "
1049 "objc_autoreleaseReturnValue => "
1050 "objc_autorelease since its operand is not used as a return "
1053 << *AutoreleaseRV << "\n");
1055 CallInst *AutoreleaseRVCI = cast<CallInst>(AutoreleaseRV);
1057 setCalledFunction(getAutoreleaseCallee(F.getParent()));
1058 AutoreleaseRVCI->setTailCall(false); // Never tail call objc_autorelease.
1059 Class = IC_Autorelease;
1061 DEBUG(dbgs() << " New: "
1062 << *AutoreleaseRV << "\n");
1066 /// Visit each call, one at a time, and make simplifications without doing any
1067 /// additional analysis.
1068 void ObjCARCOpt::OptimizeIndividualCalls(Function &F) {
1069 // Reset all the flags in preparation for recomputing them.
1070 UsedInThisFunction = 0;
1072 // Visit all objc_* calls in F.
1073 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
1074 Instruction *Inst = &*I++;
1076 InstructionClass Class = GetBasicInstructionClass(Inst);
1078 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Visiting: Class: "
1079 << Class << "; " << *Inst << "\n");
1084 // Delete no-op casts. These function calls have special semantics, but
1085 // the semantics are entirely implemented via lowering in the front-end,
1086 // so by the time they reach the optimizer, they are just no-op calls
1087 // which return their argument.
1089 // There are gray areas here, as the ability to cast reference-counted
1090 // pointers to raw void* and back allows code to break ARC assumptions,
1091 // however these are currently considered to be unimportant.
1095 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Erasing no-op cast:"
1096 " " << *Inst << "\n");
1097 EraseInstruction(Inst);
1100 // If the pointer-to-weak-pointer is null, it's undefined behavior.
1103 case IC_LoadWeakRetained:
1105 case IC_DestroyWeak: {
1106 CallInst *CI = cast<CallInst>(Inst);
1107 if (isNullOrUndef(CI->getArgOperand(0))) {
1109 Type *Ty = CI->getArgOperand(0)->getType();
1110 new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
1111 Constant::getNullValue(Ty),
1113 llvm::Value *NewValue = UndefValue::get(CI->getType());
1114 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: A null "
1115 "pointer-to-weak-pointer is undefined behavior.\n"
1119 CI->replaceAllUsesWith(NewValue);
1120 CI->eraseFromParent();
1127 CallInst *CI = cast<CallInst>(Inst);
1128 if (isNullOrUndef(CI->getArgOperand(0)) ||
1129 isNullOrUndef(CI->getArgOperand(1))) {
1131 Type *Ty = CI->getArgOperand(0)->getType();
1132 new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
1133 Constant::getNullValue(Ty),
1136 llvm::Value *NewValue = UndefValue::get(CI->getType());
1137 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: A null "
1138 "pointer-to-weak-pointer is undefined behavior.\n"
1143 CI->replaceAllUsesWith(NewValue);
1144 CI->eraseFromParent();
1150 OptimizeRetainCall(F, Inst);
1153 if (OptimizeRetainRVCall(F, Inst))
1156 case IC_AutoreleaseRV:
1157 OptimizeAutoreleaseRVCall(F, Inst, Class);
1161 // objc_autorelease(x) -> objc_release(x) if x is otherwise unused.
1162 if (IsAutorelease(Class) && Inst->use_empty()) {
1163 CallInst *Call = cast<CallInst>(Inst);
1164 const Value *Arg = Call->getArgOperand(0);
1165 Arg = FindSingleUseIdentifiedObject(Arg);
1170 // Create the declaration lazily.
1171 LLVMContext &C = Inst->getContext();
1173 CallInst::Create(getReleaseCallee(F.getParent()),
1174 Call->getArgOperand(0), "", Call);
1175 NewCall->setMetadata(ImpreciseReleaseMDKind,
1176 MDNode::get(C, ArrayRef<Value *>()));
1178 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Replacing "
1179 "objc_autorelease(x) with objc_release(x) since x is "
1180 "otherwise unused.\n"
1181 " Old: " << *Call <<
1185 EraseInstruction(Call);
1191 // For functions which can never be passed stack arguments, add
1193 if (IsAlwaysTail(Class)) {
1195 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Adding tail keyword"
1196 " to function since it can never be passed stack args: " << *Inst <<
1198 cast<CallInst>(Inst)->setTailCall();
1201 // Ensure that functions that can never have a "tail" keyword due to the
1202 // semantics of ARC truly do not do so.
1203 if (IsNeverTail(Class)) {
1205 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Removing tail "
1206 "keyword from function: " << *Inst <<
1208 cast<CallInst>(Inst)->setTailCall(false);
1211 // Set nounwind as needed.
1212 if (IsNoThrow(Class)) {
1214 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Found no throw"
1215 " class. Setting nounwind on: " << *Inst << "\n");
1216 cast<CallInst>(Inst)->setDoesNotThrow();
1219 if (!IsNoopOnNull(Class)) {
1220 UsedInThisFunction |= 1 << Class;
1224 const Value *Arg = GetObjCArg(Inst);
1226 // ARC calls with null are no-ops. Delete them.
1227 if (isNullOrUndef(Arg)) {
1230 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: ARC calls with "
1231 " null are no-ops. Erasing: " << *Inst << "\n");
1232 EraseInstruction(Inst);
1236 // Keep track of which of retain, release, autorelease, and retain_block
1237 // are actually present in this function.
1238 UsedInThisFunction |= 1 << Class;
1240 // If Arg is a PHI, and one or more incoming values to the
1241 // PHI are null, and the call is control-equivalent to the PHI, and there
1242 // are no relevant side effects between the PHI and the call, the call
1243 // could be pushed up to just those paths with non-null incoming values.
1244 // For now, don't bother splitting critical edges for this.
1245 SmallVector<std::pair<Instruction *, const Value *>, 4> Worklist;
1246 Worklist.push_back(std::make_pair(Inst, Arg));
1248 std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val();
1252 const PHINode *PN = dyn_cast<PHINode>(Arg);
1255 // Determine if the PHI has any null operands, or any incoming
1257 bool HasNull = false;
1258 bool HasCriticalEdges = false;
1259 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1261 StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
1262 if (isNullOrUndef(Incoming))
1264 else if (cast<TerminatorInst>(PN->getIncomingBlock(i)->back())
1265 .getNumSuccessors() != 1) {
1266 HasCriticalEdges = true;
1270 // If we have null operands and no critical edges, optimize.
1271 if (!HasCriticalEdges && HasNull) {
1272 SmallPtrSet<Instruction *, 4> DependingInstructions;
1273 SmallPtrSet<const BasicBlock *, 4> Visited;
1275 // Check that there is nothing that cares about the reference
1276 // count between the call and the phi.
1279 case IC_RetainBlock:
1280 // These can always be moved up.
1283 // These can't be moved across things that care about the retain
1285 FindDependencies(NeedsPositiveRetainCount, Arg,
1286 Inst->getParent(), Inst,
1287 DependingInstructions, Visited, PA);
1289 case IC_Autorelease:
1290 // These can't be moved across autorelease pool scope boundaries.
1291 FindDependencies(AutoreleasePoolBoundary, Arg,
1292 Inst->getParent(), Inst,
1293 DependingInstructions, Visited, PA);
1296 case IC_AutoreleaseRV:
1297 // Don't move these; the RV optimization depends on the autoreleaseRV
1298 // being tail called, and the retainRV being immediately after a call
1299 // (which might still happen if we get lucky with codegen layout, but
1300 // it's not worth taking the chance).
1303 llvm_unreachable("Invalid dependence flavor");
1306 if (DependingInstructions.size() == 1 &&
1307 *DependingInstructions.begin() == PN) {
1310 // Clone the call into each predecessor that has a non-null value.
1311 CallInst *CInst = cast<CallInst>(Inst);
1312 Type *ParamTy = CInst->getArgOperand(0)->getType();
1313 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1315 StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
1316 if (!isNullOrUndef(Incoming)) {
1317 CallInst *Clone = cast<CallInst>(CInst->clone());
1318 Value *Op = PN->getIncomingValue(i);
1319 Instruction *InsertPos = &PN->getIncomingBlock(i)->back();
1320 if (Op->getType() != ParamTy)
1321 Op = new BitCastInst(Op, ParamTy, "", InsertPos);
1322 Clone->setArgOperand(0, Op);
1323 Clone->insertBefore(InsertPos);
1325 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Cloning "
1328 "clone at " << *InsertPos << "\n");
1329 Worklist.push_back(std::make_pair(Clone, Incoming));
1332 // Erase the original call.
1333 DEBUG(dbgs() << "Erasing: " << *CInst << "\n");
1334 EraseInstruction(CInst);
1338 } while (!Worklist.empty());
1340 DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Finished List.\n");
1343 /// Check for critical edges, loop boundaries, irreducible control flow, or
1344 /// other CFG structures where moving code across the edge would result in it
1345 /// being executed more.
1347 ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB,
1348 DenseMap<const BasicBlock *, BBState> &BBStates,
1349 BBState &MyStates) const {
1350 // If any top-down local-use or possible-dec has a succ which is earlier in
1351 // the sequence, forget it.
1352 for (BBState::ptr_iterator I = MyStates.top_down_ptr_begin(),
1353 E = MyStates.top_down_ptr_end(); I != E; ++I)
1354 switch (I->second.GetSeq()) {
1357 const Value *Arg = I->first;
1358 const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
1359 bool SomeSuccHasSame = false;
1360 bool AllSuccsHaveSame = true;
1361 PtrState &S = I->second;
1362 succ_const_iterator SI(TI), SE(TI, false);
1364 for (; SI != SE; ++SI) {
1365 Sequence SuccSSeq = S_None;
1366 bool SuccSRRIKnownSafe = false;
1367 // If VisitBottomUp has pointer information for this successor, take
1368 // what we know about it.
1369 DenseMap<const BasicBlock *, BBState>::iterator BBI =
1371 assert(BBI != BBStates.end());
1372 const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);
1373 SuccSSeq = SuccS.GetSeq();
1374 SuccSRRIKnownSafe = SuccS.RRI.KnownSafe;
1377 case S_CanRelease: {
1378 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe) {
1379 S.ClearSequenceProgress();
1385 SomeSuccHasSame = true;
1389 case S_MovableRelease:
1390 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe)
1391 AllSuccsHaveSame = false;
1394 llvm_unreachable("bottom-up pointer in retain state!");
1397 // If the state at the other end of any of the successor edges
1398 // matches the current state, require all edges to match. This
1399 // guards against loops in the middle of a sequence.
1400 if (SomeSuccHasSame && !AllSuccsHaveSame)
1401 S.ClearSequenceProgress();
1404 case S_CanRelease: {
1405 const Value *Arg = I->first;
1406 const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
1407 bool SomeSuccHasSame = false;
1408 bool AllSuccsHaveSame = true;
1409 PtrState &S = I->second;
1410 succ_const_iterator SI(TI), SE(TI, false);
1412 for (; SI != SE; ++SI) {
1413 Sequence SuccSSeq = S_None;
1414 bool SuccSRRIKnownSafe = false;
1415 // If VisitBottomUp has pointer information for this successor, take
1416 // what we know about it.
1417 DenseMap<const BasicBlock *, BBState>::iterator BBI =
1419 assert(BBI != BBStates.end());
1420 const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);
1421 SuccSSeq = SuccS.GetSeq();
1422 SuccSRRIKnownSafe = SuccS.RRI.KnownSafe;
1425 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe) {
1426 S.ClearSequenceProgress();
1432 SomeSuccHasSame = true;
1436 case S_MovableRelease:
1438 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe)
1439 AllSuccsHaveSame = false;
1442 llvm_unreachable("bottom-up pointer in retain state!");
1445 // If the state at the other end of any of the successor edges
1446 // matches the current state, require all edges to match. This
1447 // guards against loops in the middle of a sequence.
1448 if (SomeSuccHasSame && !AllSuccsHaveSame)
1449 S.ClearSequenceProgress();
1456 ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst,
1458 MapVector<Value *, RRInfo> &Retains,
1459 BBState &MyStates) {
1460 bool NestingDetected = false;
1461 InstructionClass Class = GetInstructionClass(Inst);
1462 const Value *Arg = 0;
1466 Arg = GetObjCArg(Inst);
1468 PtrState &S = MyStates.getPtrBottomUpState(Arg);
1470 // If we see two releases in a row on the same pointer. If so, make
1471 // a note, and we'll cicle back to revisit it after we've
1472 // hopefully eliminated the second release, which may allow us to
1473 // eliminate the first release too.
1474 // Theoretically we could implement removal of nested retain+release
1475 // pairs by making PtrState hold a stack of states, but this is
1476 // simple and avoids adding overhead for the non-nested case.
1477 if (S.GetSeq() == S_Release || S.GetSeq() == S_MovableRelease) {
1478 DEBUG(dbgs() << "ObjCARCOpt::VisitInstructionBottomUp: Found nested "
1479 "releases (i.e. a release pair)\n");
1480 NestingDetected = true;
1483 MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind);
1484 S.ResetSequenceProgress(ReleaseMetadata ? S_MovableRelease : S_Release);
1485 S.RRI.ReleaseMetadata = ReleaseMetadata;
1486 S.RRI.KnownSafe = S.IsKnownIncremented();
1487 S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
1488 S.RRI.Calls.insert(Inst);
1490 S.SetKnownPositiveRefCount();
1493 case IC_RetainBlock:
1494 // An objc_retainBlock call with just a use may need to be kept,
1495 // because it may be copying a block from the stack to the heap.
1496 if (!IsRetainBlockOptimizable(Inst))
1501 Arg = GetObjCArg(Inst);
1503 PtrState &S = MyStates.getPtrBottomUpState(Arg);
1504 S.SetKnownPositiveRefCount();
1506 switch (S.GetSeq()) {
1509 case S_MovableRelease:
1511 S.RRI.ReverseInsertPts.clear();
1514 // Don't do retain+release tracking for IC_RetainRV, because it's
1515 // better to let it remain as the first instruction after a call.
1516 if (Class != IC_RetainRV) {
1517 S.RRI.IsRetainBlock = Class == IC_RetainBlock;
1518 Retains[Inst] = S.RRI;
1520 S.ClearSequenceProgress();
1525 llvm_unreachable("bottom-up pointer in retain state!");
1527 return NestingDetected;
1529 case IC_AutoreleasepoolPop:
1530 // Conservatively, clear MyStates for all known pointers.
1531 MyStates.clearBottomUpPointers();
1532 return NestingDetected;
1533 case IC_AutoreleasepoolPush:
1535 // These are irrelevant.
1536 return NestingDetected;
1541 // Consider any other possible effects of this instruction on each
1542 // pointer being tracked.
1543 for (BBState::ptr_iterator MI = MyStates.bottom_up_ptr_begin(),
1544 ME = MyStates.bottom_up_ptr_end(); MI != ME; ++MI) {
1545 const Value *Ptr = MI->first;
1547 continue; // Handled above.
1548 PtrState &S = MI->second;
1549 Sequence Seq = S.GetSeq();
1551 // Check for possible releases.
1552 if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
1556 S.SetSeq(S_CanRelease);
1560 case S_MovableRelease:
1565 llvm_unreachable("bottom-up pointer in retain state!");
1569 // Check for possible direct uses.
1572 case S_MovableRelease:
1573 if (CanUse(Inst, Ptr, PA, Class)) {
1574 assert(S.RRI.ReverseInsertPts.empty());
1575 // If this is an invoke instruction, we're scanning it as part of
1576 // one of its successor blocks, since we can't insert code after it
1577 // in its own block, and we don't want to split critical edges.
1578 if (isa<InvokeInst>(Inst))
1579 S.RRI.ReverseInsertPts.insert(BB->getFirstInsertionPt());
1581 S.RRI.ReverseInsertPts.insert(llvm::next(BasicBlock::iterator(Inst)));
1583 } else if (Seq == S_Release &&
1584 (Class == IC_User || Class == IC_CallOrUser)) {
1585 // Non-movable releases depend on any possible objc pointer use.
1587 assert(S.RRI.ReverseInsertPts.empty());
1588 // As above; handle invoke specially.
1589 if (isa<InvokeInst>(Inst))
1590 S.RRI.ReverseInsertPts.insert(BB->getFirstInsertionPt());
1592 S.RRI.ReverseInsertPts.insert(llvm::next(BasicBlock::iterator(Inst)));
1596 if (CanUse(Inst, Ptr, PA, Class))
1604 llvm_unreachable("bottom-up pointer in retain state!");
1608 return NestingDetected;
1612 ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
1613 DenseMap<const BasicBlock *, BBState> &BBStates,
1614 MapVector<Value *, RRInfo> &Retains) {
1615 bool NestingDetected = false;
1616 BBState &MyStates = BBStates[BB];
1618 // Merge the states from each successor to compute the initial state
1619 // for the current block.
1620 BBState::edge_iterator SI(MyStates.succ_begin()),
1621 SE(MyStates.succ_end());
1623 const BasicBlock *Succ = *SI;
1624 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ);
1625 assert(I != BBStates.end());
1626 MyStates.InitFromSucc(I->second);
1628 for (; SI != SE; ++SI) {
1630 I = BBStates.find(Succ);
1631 assert(I != BBStates.end());
1632 MyStates.MergeSucc(I->second);
1636 // Visit all the instructions, bottom-up.
1637 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
1638 Instruction *Inst = llvm::prior(I);
1640 // Invoke instructions are visited as part of their successors (below).
1641 if (isa<InvokeInst>(Inst))
1644 DEBUG(dbgs() << "ObjCARCOpt::VisitButtonUp: Visiting " << *Inst << "\n");
1646 NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates);
1649 // If there's a predecessor with an invoke, visit the invoke as if it were
1650 // part of this block, since we can't insert code after an invoke in its own
1651 // block, and we don't want to split critical edges.
1652 for (BBState::edge_iterator PI(MyStates.pred_begin()),
1653 PE(MyStates.pred_end()); PI != PE; ++PI) {
1654 BasicBlock *Pred = *PI;
1655 if (InvokeInst *II = dyn_cast<InvokeInst>(&Pred->back()))
1656 NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates);
1659 return NestingDetected;
1663 ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst,
1664 DenseMap<Value *, RRInfo> &Releases,
1665 BBState &MyStates) {
1666 bool NestingDetected = false;
1667 InstructionClass Class = GetInstructionClass(Inst);
1668 const Value *Arg = 0;
1671 case IC_RetainBlock:
1672 // An objc_retainBlock call with just a use may need to be kept,
1673 // because it may be copying a block from the stack to the heap.
1674 if (!IsRetainBlockOptimizable(Inst))
1679 Arg = GetObjCArg(Inst);
1681 PtrState &S = MyStates.getPtrTopDownState(Arg);
1683 // Don't do retain+release tracking for IC_RetainRV, because it's
1684 // better to let it remain as the first instruction after a call.
1685 if (Class != IC_RetainRV) {
1686 // If we see two retains in a row on the same pointer. If so, make
1687 // a note, and we'll cicle back to revisit it after we've
1688 // hopefully eliminated the second retain, which may allow us to
1689 // eliminate the first retain too.
1690 // Theoretically we could implement removal of nested retain+release
1691 // pairs by making PtrState hold a stack of states, but this is
1692 // simple and avoids adding overhead for the non-nested case.
1693 if (S.GetSeq() == S_Retain)
1694 NestingDetected = true;
1696 S.ResetSequenceProgress(S_Retain);
1697 S.RRI.IsRetainBlock = Class == IC_RetainBlock;
1698 S.RRI.KnownSafe = S.IsKnownIncremented();
1699 S.RRI.Calls.insert(Inst);
1702 S.SetKnownPositiveRefCount();
1704 // A retain can be a potential use; procede to the generic checking
1709 Arg = GetObjCArg(Inst);
1711 PtrState &S = MyStates.getPtrTopDownState(Arg);
1714 switch (S.GetSeq()) {
1717 S.RRI.ReverseInsertPts.clear();
1720 S.RRI.ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind);
1721 S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
1722 Releases[Inst] = S.RRI;
1723 S.ClearSequenceProgress();
1729 case S_MovableRelease:
1730 llvm_unreachable("top-down pointer in release state!");
1734 case IC_AutoreleasepoolPop:
1735 // Conservatively, clear MyStates for all known pointers.
1736 MyStates.clearTopDownPointers();
1737 return NestingDetected;
1738 case IC_AutoreleasepoolPush:
1740 // These are irrelevant.
1741 return NestingDetected;
1746 // Consider any other possible effects of this instruction on each
1747 // pointer being tracked.
1748 for (BBState::ptr_iterator MI = MyStates.top_down_ptr_begin(),
1749 ME = MyStates.top_down_ptr_end(); MI != ME; ++MI) {
1750 const Value *Ptr = MI->first;
1752 continue; // Handled above.
1753 PtrState &S = MI->second;
1754 Sequence Seq = S.GetSeq();
1756 // Check for possible releases.
1757 if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
1761 S.SetSeq(S_CanRelease);
1762 assert(S.RRI.ReverseInsertPts.empty());
1763 S.RRI.ReverseInsertPts.insert(Inst);
1765 // One call can't cause a transition from S_Retain to S_CanRelease
1766 // and S_CanRelease to S_Use. If we've made the first transition,
1775 case S_MovableRelease:
1776 llvm_unreachable("top-down pointer in release state!");
1780 // Check for possible direct uses.
1783 if (CanUse(Inst, Ptr, PA, Class))
1792 case S_MovableRelease:
1793 llvm_unreachable("top-down pointer in release state!");
1797 return NestingDetected;
1801 ObjCARCOpt::VisitTopDown(BasicBlock *BB,
1802 DenseMap<const BasicBlock *, BBState> &BBStates,
1803 DenseMap<Value *, RRInfo> &Releases) {
1804 bool NestingDetected = false;
1805 BBState &MyStates = BBStates[BB];
1807 // Merge the states from each predecessor to compute the initial state
1808 // for the current block.
1809 BBState::edge_iterator PI(MyStates.pred_begin()),
1810 PE(MyStates.pred_end());
1812 const BasicBlock *Pred = *PI;
1813 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred);
1814 assert(I != BBStates.end());
1815 MyStates.InitFromPred(I->second);
1817 for (; PI != PE; ++PI) {
1819 I = BBStates.find(Pred);
1820 assert(I != BBStates.end());
1821 MyStates.MergePred(I->second);
1825 // Visit all the instructions, top-down.
1826 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
1827 Instruction *Inst = I;
1829 DEBUG(dbgs() << "ObjCARCOpt::VisitTopDown: Visiting " << *Inst << "\n");
1831 NestingDetected |= VisitInstructionTopDown(Inst, Releases, MyStates);
1834 CheckForCFGHazards(BB, BBStates, MyStates);
1835 return NestingDetected;
1839 ComputePostOrders(Function &F,
1840 SmallVectorImpl<BasicBlock *> &PostOrder,
1841 SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder,
1842 unsigned NoObjCARCExceptionsMDKind,
1843 DenseMap<const BasicBlock *, BBState> &BBStates) {
1844 /// The visited set, for doing DFS walks.
1845 SmallPtrSet<BasicBlock *, 16> Visited;
1847 // Do DFS, computing the PostOrder.
1848 SmallPtrSet<BasicBlock *, 16> OnStack;
1849 SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack;
1851 // Functions always have exactly one entry block, and we don't have
1852 // any other block that we treat like an entry block.
1853 BasicBlock *EntryBB = &F.getEntryBlock();
1854 BBState &MyStates = BBStates[EntryBB];
1855 MyStates.SetAsEntry();
1856 TerminatorInst *EntryTI = cast<TerminatorInst>(&EntryBB->back());
1857 SuccStack.push_back(std::make_pair(EntryBB, succ_iterator(EntryTI)));
1858 Visited.insert(EntryBB);
1859 OnStack.insert(EntryBB);
1862 BasicBlock *CurrBB = SuccStack.back().first;
1863 TerminatorInst *TI = cast<TerminatorInst>(&CurrBB->back());
1864 succ_iterator SE(TI, false);
1866 while (SuccStack.back().second != SE) {
1867 BasicBlock *SuccBB = *SuccStack.back().second++;
1868 if (Visited.insert(SuccBB)) {
1869 TerminatorInst *TI = cast<TerminatorInst>(&SuccBB->back());
1870 SuccStack.push_back(std::make_pair(SuccBB, succ_iterator(TI)));
1871 BBStates[CurrBB].addSucc(SuccBB);
1872 BBState &SuccStates = BBStates[SuccBB];
1873 SuccStates.addPred(CurrBB);
1874 OnStack.insert(SuccBB);
1878 if (!OnStack.count(SuccBB)) {
1879 BBStates[CurrBB].addSucc(SuccBB);
1880 BBStates[SuccBB].addPred(CurrBB);
1883 OnStack.erase(CurrBB);
1884 PostOrder.push_back(CurrBB);
1885 SuccStack.pop_back();
1886 } while (!SuccStack.empty());
1890 // Do reverse-CFG DFS, computing the reverse-CFG PostOrder.
1891 // Functions may have many exits, and there also blocks which we treat
1892 // as exits due to ignored edges.
1893 SmallVector<std::pair<BasicBlock *, BBState::edge_iterator>, 16> PredStack;
1894 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
1895 BasicBlock *ExitBB = I;
1896 BBState &MyStates = BBStates[ExitBB];
1897 if (!MyStates.isExit())
1900 MyStates.SetAsExit();
1902 PredStack.push_back(std::make_pair(ExitBB, MyStates.pred_begin()));
1903 Visited.insert(ExitBB);
1904 while (!PredStack.empty()) {
1905 reverse_dfs_next_succ:
1906 BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end();
1907 while (PredStack.back().second != PE) {
1908 BasicBlock *BB = *PredStack.back().second++;
1909 if (Visited.insert(BB)) {
1910 PredStack.push_back(std::make_pair(BB, BBStates[BB].pred_begin()));
1911 goto reverse_dfs_next_succ;
1914 ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first);
1919 // Visit the function both top-down and bottom-up.
1921 ObjCARCOpt::Visit(Function &F,
1922 DenseMap<const BasicBlock *, BBState> &BBStates,
1923 MapVector<Value *, RRInfo> &Retains,
1924 DenseMap<Value *, RRInfo> &Releases) {
1926 // Use reverse-postorder traversals, because we magically know that loops
1927 // will be well behaved, i.e. they won't repeatedly call retain on a single
1928 // pointer without doing a release. We can't use the ReversePostOrderTraversal
1929 // class here because we want the reverse-CFG postorder to consider each
1930 // function exit point, and we want to ignore selected cycle edges.
1931 SmallVector<BasicBlock *, 16> PostOrder;
1932 SmallVector<BasicBlock *, 16> ReverseCFGPostOrder;
1933 ComputePostOrders(F, PostOrder, ReverseCFGPostOrder,
1934 NoObjCARCExceptionsMDKind,
1937 // Use reverse-postorder on the reverse CFG for bottom-up.
1938 bool BottomUpNestingDetected = false;
1939 for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
1940 ReverseCFGPostOrder.rbegin(), E = ReverseCFGPostOrder.rend();
1942 BottomUpNestingDetected |= VisitBottomUp(*I, BBStates, Retains);
1944 // Use reverse-postorder for top-down.
1945 bool TopDownNestingDetected = false;
1946 for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
1947 PostOrder.rbegin(), E = PostOrder.rend();
1949 TopDownNestingDetected |= VisitTopDown(*I, BBStates, Releases);
1951 return TopDownNestingDetected && BottomUpNestingDetected;
1954 /// Move the calls in RetainsToMove and ReleasesToMove.
1955 void ObjCARCOpt::MoveCalls(Value *Arg,
1956 RRInfo &RetainsToMove,
1957 RRInfo &ReleasesToMove,
1958 MapVector<Value *, RRInfo> &Retains,
1959 DenseMap<Value *, RRInfo> &Releases,
1960 SmallVectorImpl<Instruction *> &DeadInsts,
1962 Type *ArgTy = Arg->getType();
1963 Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext()));
1965 // Insert the new retain and release calls.
1966 for (SmallPtrSet<Instruction *, 2>::const_iterator
1967 PI = ReleasesToMove.ReverseInsertPts.begin(),
1968 PE = ReleasesToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
1969 Instruction *InsertPt = *PI;
1970 Value *MyArg = ArgTy == ParamTy ? Arg :
1971 new BitCastInst(Arg, ParamTy, "", InsertPt);
1973 CallInst::Create(RetainsToMove.IsRetainBlock ?
1974 getRetainBlockCallee(M) : getRetainCallee(M),
1975 MyArg, "", InsertPt);
1976 Call->setDoesNotThrow();
1977 if (RetainsToMove.IsRetainBlock)
1978 Call->setMetadata(CopyOnEscapeMDKind,
1979 MDNode::get(M->getContext(), ArrayRef<Value *>()));
1981 Call->setTailCall();
1983 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Inserting new Release: " << *Call
1985 " At insertion point: " << *InsertPt
1988 for (SmallPtrSet<Instruction *, 2>::const_iterator
1989 PI = RetainsToMove.ReverseInsertPts.begin(),
1990 PE = RetainsToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
1991 Instruction *InsertPt = *PI;
1992 Value *MyArg = ArgTy == ParamTy ? Arg :
1993 new BitCastInst(Arg, ParamTy, "", InsertPt);
1994 CallInst *Call = CallInst::Create(getReleaseCallee(M), MyArg,
1996 // Attach a clang.imprecise_release metadata tag, if appropriate.
1997 if (MDNode *M = ReleasesToMove.ReleaseMetadata)
1998 Call->setMetadata(ImpreciseReleaseMDKind, M);
1999 Call->setDoesNotThrow();
2000 if (ReleasesToMove.IsTailCallRelease)
2001 Call->setTailCall();
2003 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Inserting new Retain: " << *Call
2005 " At insertion point: " << *InsertPt
2009 // Delete the original retain and release calls.
2010 for (SmallPtrSet<Instruction *, 2>::const_iterator
2011 AI = RetainsToMove.Calls.begin(),
2012 AE = RetainsToMove.Calls.end(); AI != AE; ++AI) {
2013 Instruction *OrigRetain = *AI;
2014 Retains.blot(OrigRetain);
2015 DeadInsts.push_back(OrigRetain);
2016 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Deleting retain: " << *OrigRetain <<
2019 for (SmallPtrSet<Instruction *, 2>::const_iterator
2020 AI = ReleasesToMove.Calls.begin(),
2021 AE = ReleasesToMove.Calls.end(); AI != AE; ++AI) {
2022 Instruction *OrigRelease = *AI;
2023 Releases.erase(OrigRelease);
2024 DeadInsts.push_back(OrigRelease);
2025 DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Deleting release: " << *OrigRelease
2031 ObjCARCOpt::ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState>
2033 MapVector<Value *, RRInfo> &Retains,
2034 DenseMap<Value *, RRInfo> &Releases,
2036 SmallVector<Instruction *, 4> &NewRetains,
2037 SmallVector<Instruction *, 4> &NewReleases,
2038 SmallVector<Instruction *, 8> &DeadInsts,
2039 RRInfo &RetainsToMove,
2040 RRInfo &ReleasesToMove,
2043 bool &AnyPairsCompletelyEliminated) {
2044 // If a pair happens in a region where it is known that the reference count
2045 // is already incremented, we can similarly ignore possible decrements.
2046 bool KnownSafeTD = true, KnownSafeBU = true;
2048 // Connect the dots between the top-down-collected RetainsToMove and
2049 // bottom-up-collected ReleasesToMove to form sets of related calls.
2050 // This is an iterative process so that we connect multiple releases
2051 // to multiple retains if needed.
2052 unsigned OldDelta = 0;
2053 unsigned NewDelta = 0;
2054 unsigned OldCount = 0;
2055 unsigned NewCount = 0;
2056 bool FirstRelease = true;
2057 bool FirstRetain = true;
2059 for (SmallVectorImpl<Instruction *>::const_iterator
2060 NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) {
2061 Instruction *NewRetain = *NI;
2062 MapVector<Value *, RRInfo>::const_iterator It = Retains.find(NewRetain);
2063 assert(It != Retains.end());
2064 const RRInfo &NewRetainRRI = It->second;
2065 KnownSafeTD &= NewRetainRRI.KnownSafe;
2066 for (SmallPtrSet<Instruction *, 2>::const_iterator
2067 LI = NewRetainRRI.Calls.begin(),
2068 LE = NewRetainRRI.Calls.end(); LI != LE; ++LI) {
2069 Instruction *NewRetainRelease = *LI;
2070 DenseMap<Value *, RRInfo>::const_iterator Jt =
2071 Releases.find(NewRetainRelease);
2072 if (Jt == Releases.end())
2074 const RRInfo &NewRetainReleaseRRI = Jt->second;
2075 assert(NewRetainReleaseRRI.Calls.count(NewRetain));
2076 if (ReleasesToMove.Calls.insert(NewRetainRelease)) {
2078 BBStates[NewRetainRelease->getParent()].GetAllPathCount();
2080 // Merge the ReleaseMetadata and IsTailCallRelease values.
2082 ReleasesToMove.ReleaseMetadata =
2083 NewRetainReleaseRRI.ReleaseMetadata;
2084 ReleasesToMove.IsTailCallRelease =
2085 NewRetainReleaseRRI.IsTailCallRelease;
2086 FirstRelease = false;
2088 if (ReleasesToMove.ReleaseMetadata !=
2089 NewRetainReleaseRRI.ReleaseMetadata)
2090 ReleasesToMove.ReleaseMetadata = 0;
2091 if (ReleasesToMove.IsTailCallRelease !=
2092 NewRetainReleaseRRI.IsTailCallRelease)
2093 ReleasesToMove.IsTailCallRelease = false;
2096 // Collect the optimal insertion points.
2098 for (SmallPtrSet<Instruction *, 2>::const_iterator
2099 RI = NewRetainReleaseRRI.ReverseInsertPts.begin(),
2100 RE = NewRetainReleaseRRI.ReverseInsertPts.end();
2102 Instruction *RIP = *RI;
2103 if (ReleasesToMove.ReverseInsertPts.insert(RIP))
2104 NewDelta -= BBStates[RIP->getParent()].GetAllPathCount();
2106 NewReleases.push_back(NewRetainRelease);
2111 if (NewReleases.empty()) break;
2113 // Back the other way.
2114 for (SmallVectorImpl<Instruction *>::const_iterator
2115 NI = NewReleases.begin(), NE = NewReleases.end(); NI != NE; ++NI) {
2116 Instruction *NewRelease = *NI;
2117 DenseMap<Value *, RRInfo>::const_iterator It =
2118 Releases.find(NewRelease);
2119 assert(It != Releases.end());
2120 const RRInfo &NewReleaseRRI = It->second;
2121 KnownSafeBU &= NewReleaseRRI.KnownSafe;
2122 for (SmallPtrSet<Instruction *, 2>::const_iterator
2123 LI = NewReleaseRRI.Calls.begin(),
2124 LE = NewReleaseRRI.Calls.end(); LI != LE; ++LI) {
2125 Instruction *NewReleaseRetain = *LI;
2126 MapVector<Value *, RRInfo>::const_iterator Jt =
2127 Retains.find(NewReleaseRetain);
2128 if (Jt == Retains.end())
2130 const RRInfo &NewReleaseRetainRRI = Jt->second;
2131 assert(NewReleaseRetainRRI.Calls.count(NewRelease));
2132 if (RetainsToMove.Calls.insert(NewReleaseRetain)) {
2133 unsigned PathCount =
2134 BBStates[NewReleaseRetain->getParent()].GetAllPathCount();
2135 OldDelta += PathCount;
2136 OldCount += PathCount;
2138 // Merge the IsRetainBlock values.
2140 RetainsToMove.IsRetainBlock = NewReleaseRetainRRI.IsRetainBlock;
2141 FirstRetain = false;
2142 } else if (ReleasesToMove.IsRetainBlock !=
2143 NewReleaseRetainRRI.IsRetainBlock)
2144 // It's not possible to merge the sequences if one uses
2145 // objc_retain and the other uses objc_retainBlock.
2148 // Collect the optimal insertion points.
2150 for (SmallPtrSet<Instruction *, 2>::const_iterator
2151 RI = NewReleaseRetainRRI.ReverseInsertPts.begin(),
2152 RE = NewReleaseRetainRRI.ReverseInsertPts.end();
2154 Instruction *RIP = *RI;
2155 if (RetainsToMove.ReverseInsertPts.insert(RIP)) {
2156 PathCount = BBStates[RIP->getParent()].GetAllPathCount();
2157 NewDelta += PathCount;
2158 NewCount += PathCount;
2161 NewRetains.push_back(NewReleaseRetain);
2165 NewReleases.clear();
2166 if (NewRetains.empty()) break;
2169 // If the pointer is known incremented or nested, we can safely delete the
2170 // pair regardless of what's between them.
2171 if (KnownSafeTD || KnownSafeBU) {
2172 RetainsToMove.ReverseInsertPts.clear();
2173 ReleasesToMove.ReverseInsertPts.clear();
2176 // Determine whether the new insertion points we computed preserve the
2177 // balance of retain and release calls through the program.
2178 // TODO: If the fully aggressive solution isn't valid, try to find a
2179 // less aggressive solution which is.
2184 // Determine whether the original call points are balanced in the retain and
2185 // release calls through the program. If not, conservatively don't touch
2187 // TODO: It's theoretically possible to do code motion in this case, as
2188 // long as the existing imbalances are maintained.
2193 assert(OldCount != 0 && "Unreachable code?");
2194 NumRRs += OldCount - NewCount;
2195 // Set to true if we completely removed any RR pairs.
2196 AnyPairsCompletelyEliminated = NewCount == 0;
2198 // We can move calls!
2202 /// Identify pairings between the retains and releases, and delete and/or move
2205 ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState>
2207 MapVector<Value *, RRInfo> &Retains,
2208 DenseMap<Value *, RRInfo> &Releases,
2210 bool AnyPairsCompletelyEliminated = false;
2211 RRInfo RetainsToMove;
2212 RRInfo ReleasesToMove;
2213 SmallVector<Instruction *, 4> NewRetains;
2214 SmallVector<Instruction *, 4> NewReleases;
2215 SmallVector<Instruction *, 8> DeadInsts;
2217 // Visit each retain.
2218 for (MapVector<Value *, RRInfo>::const_iterator I = Retains.begin(),
2219 E = Retains.end(); I != E; ++I) {
2220 Value *V = I->first;
2221 if (!V) continue; // blotted
2223 Instruction *Retain = cast<Instruction>(V);
2225 DEBUG(dbgs() << "ObjCARCOpt::PerformCodePlacement: Visiting: " << *Retain
2228 Value *Arg = GetObjCArg(Retain);
2230 // If the object being released is in static or stack storage, we know it's
2231 // not being managed by ObjC reference counting, so we can delete pairs
2232 // regardless of what possible decrements or uses lie between them.
2233 bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg);
2235 // A constant pointer can't be pointing to an object on the heap. It may
2236 // be reference-counted, but it won't be deleted.
2237 if (const LoadInst *LI = dyn_cast<LoadInst>(Arg))
2238 if (const GlobalVariable *GV =
2239 dyn_cast<GlobalVariable>(
2240 StripPointerCastsAndObjCCalls(LI->getPointerOperand())))
2241 if (GV->isConstant())
2244 // Connect the dots between the top-down-collected RetainsToMove and
2245 // bottom-up-collected ReleasesToMove to form sets of related calls.
2246 NewRetains.push_back(Retain);
2247 bool PerformMoveCalls =
2248 ConnectTDBUTraversals(BBStates, Retains, Releases, M, NewRetains,
2249 NewReleases, DeadInsts, RetainsToMove,
2250 ReleasesToMove, Arg, KnownSafe,
2251 AnyPairsCompletelyEliminated);
2253 if (PerformMoveCalls) {
2254 // Ok, everything checks out and we're all set. Let's move/delete some
2256 MoveCalls(Arg, RetainsToMove, ReleasesToMove,
2257 Retains, Releases, DeadInsts, M);
2260 // Clean up state for next retain.
2261 NewReleases.clear();
2263 RetainsToMove.clear();
2264 ReleasesToMove.clear();
2267 // Now that we're done moving everything, we can delete the newly dead
2268 // instructions, as we no longer need them as insert points.
2269 while (!DeadInsts.empty())
2270 EraseInstruction(DeadInsts.pop_back_val());
2272 return AnyPairsCompletelyEliminated;
2275 /// Weak pointer optimizations.
2276 void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
2277 // First, do memdep-style RLE and S2L optimizations. We can't use memdep
2278 // itself because it uses AliasAnalysis and we need to do provenance
2280 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2281 Instruction *Inst = &*I++;
2283 DEBUG(dbgs() << "ObjCARCOpt::OptimizeWeakCalls: Visiting: " << *Inst <<
2286 InstructionClass Class = GetBasicInstructionClass(Inst);
2287 if (Class != IC_LoadWeak && Class != IC_LoadWeakRetained)
2290 // Delete objc_loadWeak calls with no users.
2291 if (Class == IC_LoadWeak && Inst->use_empty()) {
2292 Inst->eraseFromParent();
2296 // TODO: For now, just look for an earlier available version of this value
2297 // within the same block. Theoretically, we could do memdep-style non-local
2298 // analysis too, but that would want caching. A better approach would be to
2299 // use the technique that EarlyCSE uses.
2300 inst_iterator Current = llvm::prior(I);
2301 BasicBlock *CurrentBB = Current.getBasicBlockIterator();
2302 for (BasicBlock::iterator B = CurrentBB->begin(),
2303 J = Current.getInstructionIterator();
2305 Instruction *EarlierInst = &*llvm::prior(J);
2306 InstructionClass EarlierClass = GetInstructionClass(EarlierInst);
2307 switch (EarlierClass) {
2309 case IC_LoadWeakRetained: {
2310 // If this is loading from the same pointer, replace this load's value
2312 CallInst *Call = cast<CallInst>(Inst);
2313 CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2314 Value *Arg = Call->getArgOperand(0);
2315 Value *EarlierArg = EarlierCall->getArgOperand(0);
2316 switch (PA.getAA()->alias(Arg, EarlierArg)) {
2317 case AliasAnalysis::MustAlias:
2319 // If the load has a builtin retain, insert a plain retain for it.
2320 if (Class == IC_LoadWeakRetained) {
2322 CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
2326 // Zap the fully redundant load.
2327 Call->replaceAllUsesWith(EarlierCall);
2328 Call->eraseFromParent();
2330 case AliasAnalysis::MayAlias:
2331 case AliasAnalysis::PartialAlias:
2333 case AliasAnalysis::NoAlias:
2340 // If this is storing to the same pointer and has the same size etc.
2341 // replace this load's value with the stored value.
2342 CallInst *Call = cast<CallInst>(Inst);
2343 CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2344 Value *Arg = Call->getArgOperand(0);
2345 Value *EarlierArg = EarlierCall->getArgOperand(0);
2346 switch (PA.getAA()->alias(Arg, EarlierArg)) {
2347 case AliasAnalysis::MustAlias:
2349 // If the load has a builtin retain, insert a plain retain for it.
2350 if (Class == IC_LoadWeakRetained) {
2352 CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
2356 // Zap the fully redundant load.
2357 Call->replaceAllUsesWith(EarlierCall->getArgOperand(1));
2358 Call->eraseFromParent();
2360 case AliasAnalysis::MayAlias:
2361 case AliasAnalysis::PartialAlias:
2363 case AliasAnalysis::NoAlias:
2370 // TOOD: Grab the copied value.
2372 case IC_AutoreleasepoolPush:
2375 // Weak pointers are only modified through the weak entry points
2376 // (and arbitrary calls, which could call the weak entry points).
2379 // Anything else could modify the weak pointer.
2386 // Then, for each destroyWeak with an alloca operand, check to see if
2387 // the alloca and all its users can be zapped.
2388 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2389 Instruction *Inst = &*I++;
2390 InstructionClass Class = GetBasicInstructionClass(Inst);
2391 if (Class != IC_DestroyWeak)
2394 CallInst *Call = cast<CallInst>(Inst);
2395 Value *Arg = Call->getArgOperand(0);
2396 if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) {
2397 for (Value::use_iterator UI = Alloca->use_begin(),
2398 UE = Alloca->use_end(); UI != UE; ++UI) {
2399 const Instruction *UserInst = cast<Instruction>(*UI);
2400 switch (GetBasicInstructionClass(UserInst)) {
2403 case IC_DestroyWeak:
2410 for (Value::use_iterator UI = Alloca->use_begin(),
2411 UE = Alloca->use_end(); UI != UE; ) {
2412 CallInst *UserInst = cast<CallInst>(*UI++);
2413 switch (GetBasicInstructionClass(UserInst)) {
2416 // These functions return their second argument.
2417 UserInst->replaceAllUsesWith(UserInst->getArgOperand(1));
2419 case IC_DestroyWeak:
2423 llvm_unreachable("alloca really is used!");
2425 UserInst->eraseFromParent();
2427 Alloca->eraseFromParent();
2432 DEBUG(dbgs() << "ObjCARCOpt::OptimizeWeakCalls: Finished List.\n\n");
2436 /// Identify program paths which execute sequences of retains and releases which
2437 /// can be eliminated.
2438 bool ObjCARCOpt::OptimizeSequences(Function &F) {
2439 /// Releases, Retains - These are used to store the results of the main flow
2440 /// analysis. These use Value* as the key instead of Instruction* so that the
2441 /// map stays valid when we get around to rewriting code and calls get
2442 /// replaced by arguments.
2443 DenseMap<Value *, RRInfo> Releases;
2444 MapVector<Value *, RRInfo> Retains;
2446 /// This is used during the traversal of the function to track the
2447 /// states for each identified object at each block.
2448 DenseMap<const BasicBlock *, BBState> BBStates;
2450 // Analyze the CFG of the function, and all instructions.
2451 bool NestingDetected = Visit(F, BBStates, Retains, Releases);
2454 return PerformCodePlacement(BBStates, Retains, Releases, F.getParent()) &&
2458 /// Look for this pattern:
2460 /// %call = call i8* @something(...)
2461 /// %2 = call i8* @objc_retain(i8* %call)
2462 /// %3 = call i8* @objc_autorelease(i8* %2)
2465 /// And delete the retain and autorelease.
2467 /// Otherwise if it's just this:
2469 /// %3 = call i8* @objc_autorelease(i8* %2)
2472 /// convert the autorelease to autoreleaseRV.
2473 void ObjCARCOpt::OptimizeReturns(Function &F) {
2474 if (!F.getReturnType()->isPointerTy())
2477 SmallPtrSet<Instruction *, 4> DependingInstructions;
2478 SmallPtrSet<const BasicBlock *, 4> Visited;
2479 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
2480 BasicBlock *BB = FI;
2481 ReturnInst *Ret = dyn_cast<ReturnInst>(&BB->back());
2483 DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Visiting: " << *Ret << "\n");
2487 const Value *Arg = StripPointerCastsAndObjCCalls(Ret->getOperand(0));
2488 FindDependencies(NeedsPositiveRetainCount, Arg,
2489 BB, Ret, DependingInstructions, Visited, PA);
2490 if (DependingInstructions.size() != 1)
2494 CallInst *Autorelease =
2495 dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
2498 InstructionClass AutoreleaseClass = GetBasicInstructionClass(Autorelease);
2499 if (!IsAutorelease(AutoreleaseClass))
2501 if (GetObjCArg(Autorelease) != Arg)
2504 DependingInstructions.clear();
2507 // Check that there is nothing that can affect the reference
2508 // count between the autorelease and the retain.
2509 FindDependencies(CanChangeRetainCount, Arg,
2510 BB, Autorelease, DependingInstructions, Visited, PA);
2511 if (DependingInstructions.size() != 1)
2516 dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
2518 // Check that we found a retain with the same argument.
2520 !IsRetain(GetBasicInstructionClass(Retain)) ||
2521 GetObjCArg(Retain) != Arg)
2524 DependingInstructions.clear();
2527 // Convert the autorelease to an autoreleaseRV, since it's
2528 // returning the value.
2529 if (AutoreleaseClass == IC_Autorelease) {
2530 DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Converting autorelease "
2531 "=> autoreleaseRV since it's returning a value.\n"
2532 " In: " << *Autorelease
2534 Autorelease->setCalledFunction(getAutoreleaseRVCallee(F.getParent()));
2535 DEBUG(dbgs() << " Out: " << *Autorelease
2537 Autorelease->setTailCall(); // Always tail call autoreleaseRV.
2538 AutoreleaseClass = IC_AutoreleaseRV;
2541 // Check that there is nothing that can affect the reference
2542 // count between the retain and the call.
2543 // Note that Retain need not be in BB.
2544 FindDependencies(CanChangeRetainCount, Arg, Retain->getParent(), Retain,
2545 DependingInstructions, Visited, PA);
2546 if (DependingInstructions.size() != 1)
2551 dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
2553 // Check that the pointer is the return value of the call.
2554 if (!Call || Arg != Call)
2557 // Check that the call is a regular call.
2558 InstructionClass Class = GetBasicInstructionClass(Call);
2559 if (Class != IC_CallOrUser && Class != IC_Call)
2562 // If so, we can zap the retain and autorelease.
2565 DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Erasing: " << *Retain
2567 << *Autorelease << "\n");
2568 EraseInstruction(Retain);
2569 EraseInstruction(Autorelease);
2575 DependingInstructions.clear();
2579 DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Finished List.\n\n");
2583 bool ObjCARCOpt::doInitialization(Module &M) {
2587 // If nothing in the Module uses ARC, don't do anything.
2588 Run = ModuleHasARC(M);
2592 // Identify the imprecise release metadata kind.
2593 ImpreciseReleaseMDKind =
2594 M.getContext().getMDKindID("clang.imprecise_release");
2595 CopyOnEscapeMDKind =
2596 M.getContext().getMDKindID("clang.arc.copy_on_escape");
2597 NoObjCARCExceptionsMDKind =
2598 M.getContext().getMDKindID("clang.arc.no_objc_arc_exceptions");
2600 // Intuitively, objc_retain and others are nocapture, however in practice
2601 // they are not, because they return their argument value. And objc_release
2602 // calls finalizers which can have arbitrary side effects.
2604 // These are initialized lazily.
2606 AutoreleaseRVCallee = 0;
2609 RetainBlockCallee = 0;
2610 AutoreleaseCallee = 0;
2615 bool ObjCARCOpt::runOnFunction(Function &F) {
2619 // If nothing in the Module uses ARC, don't do anything.
2625 DEBUG(dbgs() << "ObjCARCOpt: Visiting Function: " << F.getName() << "\n");
2627 PA.setAA(&getAnalysis<AliasAnalysis>());
2629 // This pass performs several distinct transformations. As a compile-time aid
2630 // when compiling code that isn't ObjC, skip these if the relevant ObjC
2631 // library functions aren't declared.
2633 // Preliminary optimizations. This also computs UsedInThisFunction.
2634 OptimizeIndividualCalls(F);
2636 // Optimizations for weak pointers.
2637 if (UsedInThisFunction & ((1 << IC_LoadWeak) |
2638 (1 << IC_LoadWeakRetained) |
2639 (1 << IC_StoreWeak) |
2640 (1 << IC_InitWeak) |
2641 (1 << IC_CopyWeak) |
2642 (1 << IC_MoveWeak) |
2643 (1 << IC_DestroyWeak)))
2644 OptimizeWeakCalls(F);
2646 // Optimizations for retain+release pairs.
2647 if (UsedInThisFunction & ((1 << IC_Retain) |
2648 (1 << IC_RetainRV) |
2649 (1 << IC_RetainBlock)))
2650 if (UsedInThisFunction & (1 << IC_Release))
2651 // Run OptimizeSequences until it either stops making changes or
2652 // no retain+release pair nesting is detected.
2653 while (OptimizeSequences(F)) {}
2655 // Optimizations if objc_autorelease is used.
2656 if (UsedInThisFunction & ((1 << IC_Autorelease) |
2657 (1 << IC_AutoreleaseRV)))
2660 DEBUG(dbgs() << "\n");
2665 void ObjCARCOpt::releaseMemory() {