1 //===- ObjCARCOpts.cpp - ObjC ARC Optimization ----------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 /// This file defines ObjC ARC optimizations. ARC stands for Automatic
11 /// Reference Counting and is a system for managing reference counts for objects
14 /// The optimizations performed include elimination of redundant, partially
15 /// redundant, and inconsequential reference count operations, elimination of
16 /// redundant weak pointer operations, and numerous minor simplifications.
18 /// WARNING: This file knows about certain library functions. It recognizes them
19 /// by name, and hardwires knowledge of their semantics.
21 /// WARNING: This file knows about how certain Objective-C library functions are
22 /// used. Naive LLVM IR transformations which would otherwise be
23 /// behavior-preserving may break these assumptions.
25 //===----------------------------------------------------------------------===//
27 #define DEBUG_TYPE "objc-arc-opts"
29 #include "DependencyAnalysis.h"
30 #include "ObjCARCAliasAnalysis.h"
31 #include "ProvenanceAnalysis.h"
32 #include "llvm/ADT/DenseMap.h"
33 #include "llvm/ADT/DenseSet.h"
34 #include "llvm/ADT/STLExtras.h"
35 #include "llvm/ADT/SmallPtrSet.h"
36 #include "llvm/ADT/Statistic.h"
37 #include "llvm/IR/IRBuilder.h"
38 #include "llvm/IR/LLVMContext.h"
39 #include "llvm/Support/CFG.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Support/raw_ostream.h"
44 using namespace llvm::objcarc;
46 /// \defgroup MiscUtils Miscellaneous utilities that are not ARC specific.
50 /// \brief An associative container with fast insertion-order (deterministic)
51 /// iteration over its elements. Plus the special blot operation.
52 template<class KeyT, class ValueT>
54 /// Map keys to indices in Vector.
55 typedef DenseMap<KeyT, size_t> MapTy;
58 typedef std::vector<std::pair<KeyT, ValueT> > VectorTy;
63 typedef typename VectorTy::iterator iterator;
64 typedef typename VectorTy::const_iterator const_iterator;
65 iterator begin() { return Vector.begin(); }
66 iterator end() { return Vector.end(); }
67 const_iterator begin() const { return Vector.begin(); }
68 const_iterator end() const { return Vector.end(); }
72 assert(Vector.size() >= Map.size()); // May differ due to blotting.
73 for (typename MapTy::const_iterator I = Map.begin(), E = Map.end();
75 assert(I->second < Vector.size());
76 assert(Vector[I->second].first == I->first);
78 for (typename VectorTy::const_iterator I = Vector.begin(),
79 E = Vector.end(); I != E; ++I)
81 (Map.count(I->first) &&
82 Map[I->first] == size_t(I - Vector.begin())));
86 ValueT &operator[](const KeyT &Arg) {
87 std::pair<typename MapTy::iterator, bool> Pair =
88 Map.insert(std::make_pair(Arg, size_t(0)));
90 size_t Num = Vector.size();
91 Pair.first->second = Num;
92 Vector.push_back(std::make_pair(Arg, ValueT()));
93 return Vector[Num].second;
95 return Vector[Pair.first->second].second;
98 std::pair<iterator, bool>
99 insert(const std::pair<KeyT, ValueT> &InsertPair) {
100 std::pair<typename MapTy::iterator, bool> Pair =
101 Map.insert(std::make_pair(InsertPair.first, size_t(0)));
103 size_t Num = Vector.size();
104 Pair.first->second = Num;
105 Vector.push_back(InsertPair);
106 return std::make_pair(Vector.begin() + Num, true);
108 return std::make_pair(Vector.begin() + Pair.first->second, false);
111 const_iterator find(const KeyT &Key) const {
112 typename MapTy::const_iterator It = Map.find(Key);
113 if (It == Map.end()) return Vector.end();
114 return Vector.begin() + It->second;
117 /// This is similar to erase, but instead of removing the element from the
118 /// vector, it just zeros out the key in the vector. This leaves iterators
119 /// intact, but clients must be prepared for zeroed-out keys when iterating.
120 void blot(const KeyT &Key) {
121 typename MapTy::iterator It = Map.find(Key);
122 if (It == Map.end()) return;
123 Vector[It->second].first = KeyT();
136 /// \defgroup ARCUtilities Utility declarations/definitions specific to ARC.
139 /// \brief This is similar to StripPointerCastsAndObjCCalls but it stops as soon
140 /// as it finds a value with multiple uses.
141 static const Value *FindSingleUseIdentifiedObject(const Value *Arg) {
142 if (Arg->hasOneUse()) {
143 if (const BitCastInst *BC = dyn_cast<BitCastInst>(Arg))
144 return FindSingleUseIdentifiedObject(BC->getOperand(0));
145 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Arg))
146 if (GEP->hasAllZeroIndices())
147 return FindSingleUseIdentifiedObject(GEP->getPointerOperand());
148 if (IsForwarding(GetBasicInstructionClass(Arg)))
149 return FindSingleUseIdentifiedObject(
150 cast<CallInst>(Arg)->getArgOperand(0));
151 if (!IsObjCIdentifiedObject(Arg))
156 // If we found an identifiable object but it has multiple uses, but they are
157 // trivial uses, we can still consider this to be a single-use value.
158 if (IsObjCIdentifiedObject(Arg)) {
159 for (Value::const_use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
162 if (!U->use_empty() || StripPointerCastsAndObjCCalls(U) != Arg)
172 /// \brief Test whether the given retainable object pointer escapes.
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 DoesRetainableObjPtrEscape(const User *Ptr) {
178 DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Target: " << *Ptr << "\n");
180 // Walk the def-use chains.
181 SmallVector<const Value *, 4> Worklist;
182 Worklist.push_back(Ptr);
183 // If Ptr has any operands add them as well.
184 for (User::const_op_iterator I = Ptr->op_begin(), E = Ptr->op_end(); I != E;
186 Worklist.push_back(*I);
189 // Ensure we do not visit any value twice.
190 SmallPtrSet<const Value *, 8> VisitedSet;
193 const Value *V = Worklist.pop_back_val();
195 DEBUG(dbgs() << "Visiting: " << *V << "\n");
197 for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end();
199 const User *UUser = *UI;
201 DEBUG(dbgs() << "User: " << *UUser << "\n");
203 // Special - Use by a call (callee or argument) is not considered
205 switch (GetBasicInstructionClass(UUser)) {
210 case IC_AutoreleaseRV: {
211 DEBUG(dbgs() << "User copies pointer arguments. Pointer Escapes!\n");
212 // These special functions make copies of their pointer arguments.
215 case IC_IntrinsicUser:
216 // Use by the use intrinsic is not an escape.
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() << "User copies value. Ptr escapes if result escapes."
227 " Adding to list.\n");
228 Worklist.push_back(UUser);
230 DEBUG(dbgs() << "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() << "Assuming ptr escapes.\n");
250 } while (!Worklist.empty());
253 DEBUG(dbgs() << "Ptr does not escape.\n");
259 /// \defgroup ARCOpt ARC Optimization.
262 // TODO: On code like this:
265 // stuff_that_cannot_release()
266 // objc_autorelease(%x)
267 // stuff_that_cannot_release()
269 // stuff_that_cannot_release()
270 // objc_autorelease(%x)
272 // The second retain and autorelease can be deleted.
274 // TODO: It should be possible to delete
275 // objc_autoreleasePoolPush and objc_autoreleasePoolPop
276 // pairs if nothing is actually autoreleased between them. Also, autorelease
277 // calls followed by objc_autoreleasePoolPop calls (perhaps in ObjC++ code
278 // after inlining) can be turned into plain release calls.
280 // TODO: Critical-edge splitting. If the optimial insertion point is
281 // a critical edge, the current algorithm has to fail, because it doesn't
282 // know how to split edges. It should be possible to make the optimizer
283 // think in terms of edges, rather than blocks, and then split critical
286 // TODO: OptimizeSequences could generalized to be Interprocedural.
288 // TODO: Recognize that a bunch of other objc runtime calls have
289 // non-escaping arguments and non-releasing arguments, and may be
290 // non-autoreleasing.
292 // TODO: Sink autorelease calls as far as possible. Unfortunately we
293 // usually can't sink them past other calls, which would be the main
294 // case where it would be useful.
296 // TODO: The pointer returned from objc_loadWeakRetained is retained.
298 // TODO: Delete release+retain pairs (rare).
300 STATISTIC(NumNoops, "Number of no-op objc calls eliminated");
301 STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated");
302 STATISTIC(NumAutoreleases,"Number of autoreleases converted to releases");
303 STATISTIC(NumRets, "Number of return value forwarding "
304 "retain+autoreleaes eliminated");
305 STATISTIC(NumRRs, "Number of retain+release paths eliminated");
306 STATISTIC(NumPeeps, "Number of calls peephole-optimized");
311 /// \brief A sequence of states that a pointer may go through in which an
312 /// objc_retain and objc_release are actually needed.
315 S_Retain, ///< objc_retain(x).
316 S_CanRelease, ///< foo(x) -- x could possibly see a ref count decrement.
317 S_Use, ///< any use of x.
318 S_Stop, ///< like S_Release, but code motion is stopped.
319 S_Release, ///< objc_release(x).
320 S_MovableRelease ///< objc_release(x), !clang.imprecise_release.
323 raw_ostream &operator<<(raw_ostream &OS, const Sequence S)
324 LLVM_ATTRIBUTE_UNUSED;
325 raw_ostream &operator<<(raw_ostream &OS, const Sequence S) {
328 return OS << "S_None";
330 return OS << "S_Retain";
332 return OS << "S_CanRelease";
334 return OS << "S_Use";
336 return OS << "S_Release";
337 case S_MovableRelease:
338 return OS << "S_MovableRelease";
340 return OS << "S_Stop";
342 llvm_unreachable("Unknown sequence type.");
346 static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) {
350 if (A == S_None || B == S_None)
353 if (A > B) std::swap(A, B);
355 // Choose the side which is further along in the sequence.
356 if ((A == S_Retain || A == S_CanRelease) &&
357 (B == S_CanRelease || B == S_Use))
360 // Choose the side which is further along in the sequence.
361 if ((A == S_Use || A == S_CanRelease) &&
362 (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease))
364 // If both sides are releases, choose the more conservative one.
365 if (A == S_Stop && (B == S_Release || B == S_MovableRelease))
367 if (A == S_Release && B == S_MovableRelease)
375 /// \brief Unidirectional information about either a
376 /// retain-decrement-use-release sequence or release-use-decrement-retain
377 /// reverse 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 of the objc_release calls are all marked with the "tail" keyword.
394 bool IsTailCallRelease;
396 /// If the Calls are objc_release calls and they all have a
397 /// clang.imprecise_release tag, this is the metadata tag.
398 MDNode *ReleaseMetadata;
400 /// For a top-down sequence, the set of objc_retains or
401 /// objc_retainBlocks. For bottom-up, the set of objc_releases.
402 SmallPtrSet<Instruction *, 2> Calls;
404 /// The set of optimal insert positions for moving calls in the opposite
406 SmallPtrSet<Instruction *, 2> ReverseInsertPts;
409 KnownSafe(false), IsTailCallRelease(false), ReleaseMetadata(0) {}
413 bool IsTrackingImpreciseReleases() {
414 return ReleaseMetadata != 0;
419 void RRInfo::clear() {
421 IsTailCallRelease = false;
424 ReverseInsertPts.clear();
428 /// \brief This class summarizes several per-pointer runtime properties which
429 /// are propogated through the flow graph.
431 /// True if the reference count is known to be incremented.
432 bool KnownPositiveRefCount;
434 /// True if we've seen an opportunity for partial RR elimination, such as
435 /// pushing calls into a CFG triangle or into one side of a CFG diamond.
438 /// The current position in the sequence.
442 /// Unidirectional information about the current sequence.
444 /// TODO: Encapsulate this better.
447 PtrState() : KnownPositiveRefCount(false), Partial(false),
450 void SetKnownPositiveRefCount() {
451 KnownPositiveRefCount = true;
454 void ClearKnownPositiveRefCount() {
455 KnownPositiveRefCount = false;
458 bool HasKnownPositiveRefCount() const {
459 return KnownPositiveRefCount;
462 void SetSeq(Sequence NewSeq) {
463 DEBUG(dbgs() << "Old: " << Seq << "; New: " << NewSeq << "\n");
467 Sequence GetSeq() const {
471 void ClearSequenceProgress() {
472 ResetSequenceProgress(S_None);
475 void ResetSequenceProgress(Sequence NewSeq) {
476 DEBUG(dbgs() << "Resetting sequence progress.\n");
482 void Merge(const PtrState &Other, bool TopDown);
487 PtrState::Merge(const PtrState &Other, bool TopDown) {
488 Seq = MergeSeqs(Seq, Other.Seq, TopDown);
489 KnownPositiveRefCount = KnownPositiveRefCount && Other.KnownPositiveRefCount;
491 // If we're not in a sequence (anymore), drop all associated state.
495 } else if (Partial || Other.Partial) {
496 // If we're doing a merge on a path that's previously seen a partial
497 // merge, conservatively drop the sequence, to avoid doing partial
498 // RR elimination. If the branch predicates for the two merge differ,
499 // mixing them is unsafe.
500 ClearSequenceProgress();
502 // Conservatively merge the ReleaseMetadata information.
503 if (RRI.ReleaseMetadata != Other.RRI.ReleaseMetadata)
504 RRI.ReleaseMetadata = 0;
506 RRI.KnownSafe = RRI.KnownSafe && Other.RRI.KnownSafe;
507 RRI.IsTailCallRelease = RRI.IsTailCallRelease &&
508 Other.RRI.IsTailCallRelease;
509 RRI.Calls.insert(Other.RRI.Calls.begin(), Other.RRI.Calls.end());
511 // Merge the insert point sets. If there are any differences,
512 // that makes this a partial merge.
513 Partial = RRI.ReverseInsertPts.size() != Other.RRI.ReverseInsertPts.size();
514 for (SmallPtrSet<Instruction *, 2>::const_iterator
515 I = Other.RRI.ReverseInsertPts.begin(),
516 E = Other.RRI.ReverseInsertPts.end(); I != E; ++I)
517 Partial |= RRI.ReverseInsertPts.insert(*I);
522 /// \brief Per-BasicBlock state.
524 /// The number of unique control paths from the entry which can reach this
526 unsigned TopDownPathCount;
528 /// The number of unique control paths to exits from this block.
529 unsigned BottomUpPathCount;
531 /// A type for PerPtrTopDown and PerPtrBottomUp.
532 typedef MapVector<const Value *, PtrState> MapTy;
534 /// The top-down traversal uses this to record information known about a
535 /// pointer at the bottom of each block.
538 /// The bottom-up traversal uses this to record information known about a
539 /// pointer at the top of each block.
540 MapTy PerPtrBottomUp;
542 /// Effective predecessors of the current block ignoring ignorable edges and
543 /// ignored backedges.
544 SmallVector<BasicBlock *, 2> Preds;
545 /// Effective successors of the current block ignoring ignorable edges and
546 /// ignored backedges.
547 SmallVector<BasicBlock *, 2> Succs;
550 BBState() : TopDownPathCount(0), BottomUpPathCount(0) {}
552 typedef MapTy::iterator ptr_iterator;
553 typedef MapTy::const_iterator ptr_const_iterator;
555 ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); }
556 ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); }
557 ptr_const_iterator top_down_ptr_begin() const {
558 return PerPtrTopDown.begin();
560 ptr_const_iterator top_down_ptr_end() const {
561 return PerPtrTopDown.end();
564 ptr_iterator bottom_up_ptr_begin() { return PerPtrBottomUp.begin(); }
565 ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); }
566 ptr_const_iterator bottom_up_ptr_begin() const {
567 return PerPtrBottomUp.begin();
569 ptr_const_iterator bottom_up_ptr_end() const {
570 return PerPtrBottomUp.end();
573 /// Mark this block as being an entry block, which has one path from the
574 /// entry by definition.
575 void SetAsEntry() { TopDownPathCount = 1; }
577 /// Mark this block as being an exit block, which has one path to an exit by
579 void SetAsExit() { BottomUpPathCount = 1; }
581 PtrState &getPtrTopDownState(const Value *Arg) {
582 return PerPtrTopDown[Arg];
585 PtrState &getPtrBottomUpState(const Value *Arg) {
586 return PerPtrBottomUp[Arg];
589 void clearBottomUpPointers() {
590 PerPtrBottomUp.clear();
593 void clearTopDownPointers() {
594 PerPtrTopDown.clear();
597 void InitFromPred(const BBState &Other);
598 void InitFromSucc(const BBState &Other);
599 void MergePred(const BBState &Other);
600 void MergeSucc(const BBState &Other);
602 /// Return the number of possible unique paths from an entry to an exit
603 /// which pass through this block. This is only valid after both the
604 /// top-down and bottom-up traversals are complete.
605 unsigned GetAllPathCount() const {
606 assert(TopDownPathCount != 0);
607 assert(BottomUpPathCount != 0);
608 return TopDownPathCount * BottomUpPathCount;
611 // Specialized CFG utilities.
612 typedef SmallVectorImpl<BasicBlock *>::const_iterator edge_iterator;
613 edge_iterator pred_begin() { return Preds.begin(); }
614 edge_iterator pred_end() { return Preds.end(); }
615 edge_iterator succ_begin() { return Succs.begin(); }
616 edge_iterator succ_end() { return Succs.end(); }
618 void addSucc(BasicBlock *Succ) { Succs.push_back(Succ); }
619 void addPred(BasicBlock *Pred) { Preds.push_back(Pred); }
621 bool isExit() const { return Succs.empty(); }
625 void BBState::InitFromPred(const BBState &Other) {
626 PerPtrTopDown = Other.PerPtrTopDown;
627 TopDownPathCount = Other.TopDownPathCount;
630 void BBState::InitFromSucc(const BBState &Other) {
631 PerPtrBottomUp = Other.PerPtrBottomUp;
632 BottomUpPathCount = Other.BottomUpPathCount;
635 /// The top-down traversal uses this to merge information about predecessors to
636 /// form the initial state for a new block.
637 void BBState::MergePred(const BBState &Other) {
638 // Other.TopDownPathCount can be 0, in which case it is either dead or a
639 // loop backedge. Loop backedges are special.
640 TopDownPathCount += Other.TopDownPathCount;
642 // Check for overflow. If we have overflow, fall back to conservative
644 if (TopDownPathCount < Other.TopDownPathCount) {
645 clearTopDownPointers();
649 // For each entry in the other set, if our set has an entry with the same key,
650 // merge the entries. Otherwise, copy the entry and merge it with an empty
652 for (ptr_const_iterator MI = Other.top_down_ptr_begin(),
653 ME = Other.top_down_ptr_end(); MI != ME; ++MI) {
654 std::pair<ptr_iterator, bool> Pair = PerPtrTopDown.insert(*MI);
655 Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
659 // For each entry in our set, if the other set doesn't have an entry with the
660 // same key, force it to merge with an empty entry.
661 for (ptr_iterator MI = top_down_ptr_begin(),
662 ME = top_down_ptr_end(); MI != ME; ++MI)
663 if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end())
664 MI->second.Merge(PtrState(), /*TopDown=*/true);
667 /// The bottom-up traversal uses this to merge information about successors to
668 /// form the initial state for a new block.
669 void BBState::MergeSucc(const BBState &Other) {
670 // Other.BottomUpPathCount can be 0, in which case it is either dead or a
671 // loop backedge. Loop backedges are special.
672 BottomUpPathCount += Other.BottomUpPathCount;
674 // Check for overflow. If we have overflow, fall back to conservative
676 if (BottomUpPathCount < Other.BottomUpPathCount) {
677 clearBottomUpPointers();
681 // For each entry in the other set, if our set has an entry with the
682 // same key, merge the entries. Otherwise, copy the entry and merge
683 // it with an empty entry.
684 for (ptr_const_iterator MI = Other.bottom_up_ptr_begin(),
685 ME = Other.bottom_up_ptr_end(); MI != ME; ++MI) {
686 std::pair<ptr_iterator, bool> Pair = PerPtrBottomUp.insert(*MI);
687 Pair.first->second.Merge(Pair.second ? PtrState() : MI->second,
691 // For each entry in our set, if the other set doesn't have an entry
692 // with the same key, force it to merge with an empty entry.
693 for (ptr_iterator MI = bottom_up_ptr_begin(),
694 ME = bottom_up_ptr_end(); MI != ME; ++MI)
695 if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end())
696 MI->second.Merge(PtrState(), /*TopDown=*/false);
699 // Only enable ARC Annotations if we are building a debug version of
702 #define ARC_ANNOTATIONS
705 // Define some macros along the lines of DEBUG and some helper functions to make
706 // it cleaner to create annotations in the source code and to no-op when not
707 // building in debug mode.
708 #ifdef ARC_ANNOTATIONS
710 #include "llvm/Support/CommandLine.h"
712 /// Enable/disable ARC sequence annotations.
714 EnableARCAnnotations("enable-objc-arc-annotations", cl::init(false),
715 cl::desc("Enable emission of arc data flow analysis "
718 DisableCheckForCFGHazards("disable-objc-arc-checkforcfghazards", cl::init(false),
719 cl::desc("Disable check for cfg hazards when "
721 static cl::opt<std::string>
722 ARCAnnotationTargetIdentifier("objc-arc-annotation-target-identifier",
724 cl::desc("filter out all data flow annotations "
725 "but those that apply to the given "
726 "target llvm identifier."));
728 /// This function appends a unique ARCAnnotationProvenanceSourceMDKind id to an
729 /// instruction so that we can track backwards when post processing via the llvm
730 /// arc annotation processor tool. If the function is an
731 static MDString *AppendMDNodeToSourcePtr(unsigned NodeId,
735 // If pointer is a result of an instruction and it does not have a source
736 // MDNode it, attach a new MDNode onto it. If pointer is a result of
737 // an instruction and does have a source MDNode attached to it, return a
738 // reference to said Node. Otherwise just return 0.
739 if (Instruction *Inst = dyn_cast<Instruction>(Ptr)) {
741 if (!(Node = Inst->getMetadata(NodeId))) {
742 // We do not have any node. Generate and attatch the hash MDString to the
745 // We just use an MDString to ensure that this metadata gets written out
746 // of line at the module level and to provide a very simple format
747 // encoding the information herein. Both of these makes it simpler to
748 // parse the annotations by a simple external program.
750 raw_string_ostream os(Str);
751 os << "(" << Inst->getParent()->getParent()->getName() << ",%"
752 << Inst->getName() << ")";
754 Hash = MDString::get(Inst->getContext(), os.str());
755 Inst->setMetadata(NodeId, MDNode::get(Inst->getContext(),Hash));
757 // We have a node. Grab its hash and return it.
758 assert(Node->getNumOperands() == 1 &&
759 "An ARCAnnotationProvenanceSourceMDKind can only have 1 operand.");
760 Hash = cast<MDString>(Node->getOperand(0));
762 } else if (Argument *Arg = dyn_cast<Argument>(Ptr)) {
764 raw_string_ostream os(str);
765 os << "(" << Arg->getParent()->getName() << ",%" << Arg->getName()
767 Hash = MDString::get(Arg->getContext(), os.str());
773 static std::string SequenceToString(Sequence A) {
775 raw_string_ostream os(str);
780 /// Helper function to change a Sequence into a String object using our overload
781 /// for raw_ostream so we only have printing code in one location.
782 static MDString *SequenceToMDString(LLVMContext &Context,
784 return MDString::get(Context, SequenceToString(A));
787 /// A simple function to generate a MDNode which describes the change in state
788 /// for Value *Ptr caused by Instruction *Inst.
789 static void AppendMDNodeToInstForPtr(unsigned NodeId,
792 MDString *PtrSourceMDNodeID,
796 Value *tmp[3] = {PtrSourceMDNodeID,
797 SequenceToMDString(Inst->getContext(),
799 SequenceToMDString(Inst->getContext(),
801 Node = MDNode::get(Inst->getContext(),
802 ArrayRef<Value*>(tmp, 3));
804 Inst->setMetadata(NodeId, Node);
807 /// Add to the beginning of the basic block llvm.ptr.annotations which show the
808 /// state of a pointer at the entrance to a basic block.
809 static void GenerateARCBBEntranceAnnotation(const char *Name, BasicBlock *BB,
810 Value *Ptr, Sequence Seq) {
811 // If we have a target identifier, make sure that we match it before
813 if(!ARCAnnotationTargetIdentifier.empty() &&
814 !Ptr->getName().equals(ARCAnnotationTargetIdentifier))
817 Module *M = BB->getParent()->getParent();
818 LLVMContext &C = M->getContext();
819 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
820 Type *I8XX = PointerType::getUnqual(I8X);
821 Type *Params[] = {I8XX, I8XX};
822 FunctionType *FTy = FunctionType::get(Type::getVoidTy(C),
823 ArrayRef<Type*>(Params, 2),
825 Constant *Callee = M->getOrInsertFunction(Name, FTy);
827 IRBuilder<> Builder(BB, BB->getFirstInsertionPt());
830 StringRef Tmp = Ptr->getName();
831 if (0 == (PtrName = M->getGlobalVariable(Tmp, true))) {
832 Value *ActualPtrName = Builder.CreateGlobalStringPtr(Tmp,
834 PtrName = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage,
835 cast<Constant>(ActualPtrName), Tmp);
839 std::string SeqStr = SequenceToString(Seq);
840 if (0 == (S = M->getGlobalVariable(SeqStr, true))) {
841 Value *ActualPtrName = Builder.CreateGlobalStringPtr(SeqStr,
843 S = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage,
844 cast<Constant>(ActualPtrName), SeqStr);
847 Builder.CreateCall2(Callee, PtrName, S);
850 /// Add to the end of the basic block llvm.ptr.annotations which show the state
851 /// of the pointer at the bottom of the basic block.
852 static void GenerateARCBBTerminatorAnnotation(const char *Name, BasicBlock *BB,
853 Value *Ptr, Sequence Seq) {
854 // If we have a target identifier, make sure that we match it before emitting
856 if(!ARCAnnotationTargetIdentifier.empty() &&
857 !Ptr->getName().equals(ARCAnnotationTargetIdentifier))
860 Module *M = BB->getParent()->getParent();
861 LLVMContext &C = M->getContext();
862 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
863 Type *I8XX = PointerType::getUnqual(I8X);
864 Type *Params[] = {I8XX, I8XX};
865 FunctionType *FTy = FunctionType::get(Type::getVoidTy(C),
866 ArrayRef<Type*>(Params, 2),
868 Constant *Callee = M->getOrInsertFunction(Name, FTy);
870 IRBuilder<> Builder(BB, llvm::prior(BB->end()));
873 StringRef Tmp = Ptr->getName();
874 if (0 == (PtrName = M->getGlobalVariable(Tmp, true))) {
875 Value *ActualPtrName = Builder.CreateGlobalStringPtr(Tmp,
877 PtrName = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage,
878 cast<Constant>(ActualPtrName), Tmp);
882 std::string SeqStr = SequenceToString(Seq);
883 if (0 == (S = M->getGlobalVariable(SeqStr, true))) {
884 Value *ActualPtrName = Builder.CreateGlobalStringPtr(SeqStr,
886 S = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage,
887 cast<Constant>(ActualPtrName), SeqStr);
889 Builder.CreateCall2(Callee, PtrName, S);
892 /// Adds a source annotation to pointer and a state change annotation to Inst
893 /// referencing the source annotation and the old/new state of pointer.
894 static void GenerateARCAnnotation(unsigned InstMDId,
900 if (EnableARCAnnotations) {
901 // If we have a target identifier, make sure that we match it before
902 // emitting an annotation.
903 if(!ARCAnnotationTargetIdentifier.empty() &&
904 !Ptr->getName().equals(ARCAnnotationTargetIdentifier))
907 // First generate the source annotation on our pointer. This will return an
908 // MDString* if Ptr actually comes from an instruction implying we can put
909 // in a source annotation. If AppendMDNodeToSourcePtr returns 0 (i.e. NULL),
910 // then we know that our pointer is from an Argument so we put a reference
911 // to the argument number.
913 // The point of this is to make it easy for the
914 // llvm-arc-annotation-processor tool to cross reference where the source
915 // pointer is in the LLVM IR since the LLVM IR parser does not submit such
916 // information via debug info for backends to use (since why would anyone
917 // need such a thing from LLVM IR besides in non standard cases
919 MDString *SourcePtrMDNode =
920 AppendMDNodeToSourcePtr(PtrMDId, Ptr);
921 AppendMDNodeToInstForPtr(InstMDId, Inst, Ptr, SourcePtrMDNode, OldSeq,
926 // The actual interface for accessing the above functionality is defined via
927 // some simple macros which are defined below. We do this so that the user does
928 // not need to pass in what metadata id is needed resulting in cleaner code and
929 // additionally since it provides an easy way to conditionally no-op all
930 // annotation support in a non-debug build.
932 /// Use this macro to annotate a sequence state change when processing
933 /// instructions bottom up,
934 #define ANNOTATE_BOTTOMUP(inst, ptr, old, new) \
935 GenerateARCAnnotation(ARCAnnotationBottomUpMDKind, \
936 ARCAnnotationProvenanceSourceMDKind, (inst), \
937 const_cast<Value*>(ptr), (old), (new))
938 /// Use this macro to annotate a sequence state change when processing
939 /// instructions top down.
940 #define ANNOTATE_TOPDOWN(inst, ptr, old, new) \
941 GenerateARCAnnotation(ARCAnnotationTopDownMDKind, \
942 ARCAnnotationProvenanceSourceMDKind, (inst), \
943 const_cast<Value*>(ptr), (old), (new))
945 #define ANNOTATE_BB(_states, _bb, _name, _type, _direction) \
947 if (EnableARCAnnotations) { \
948 for(BBState::ptr_const_iterator I = (_states)._direction##_ptr_begin(), \
949 E = (_states)._direction##_ptr_end(); I != E; ++I) { \
950 Value *Ptr = const_cast<Value*>(I->first); \
951 Sequence Seq = I->second.GetSeq(); \
952 GenerateARCBB ## _type ## Annotation(_name, (_bb), Ptr, Seq); \
957 #define ANNOTATE_BOTTOMUP_BBSTART(_states, _basicblock) \
958 ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.bottomup.bbstart", \
960 #define ANNOTATE_BOTTOMUP_BBEND(_states, _basicblock) \
961 ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.bottomup.bbend", \
962 Terminator, bottom_up)
963 #define ANNOTATE_TOPDOWN_BBSTART(_states, _basicblock) \
964 ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.topdown.bbstart", \
966 #define ANNOTATE_TOPDOWN_BBEND(_states, _basicblock) \
967 ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.topdown.bbend", \
968 Terminator, top_down)
970 #else // !ARC_ANNOTATION
971 // If annotations are off, noop.
972 #define ANNOTATE_BOTTOMUP(inst, ptr, old, new)
973 #define ANNOTATE_TOPDOWN(inst, ptr, old, new)
974 #define ANNOTATE_BOTTOMUP_BBSTART(states, basicblock)
975 #define ANNOTATE_BOTTOMUP_BBEND(states, basicblock)
976 #define ANNOTATE_TOPDOWN_BBSTART(states, basicblock)
977 #define ANNOTATE_TOPDOWN_BBEND(states, basicblock)
978 #endif // !ARC_ANNOTATION
981 /// \brief The main ARC optimization pass.
982 class ObjCARCOpt : public FunctionPass {
984 ProvenanceAnalysis PA;
986 /// A flag indicating whether this optimization pass should run.
989 /// This set contains references to objc_autorelease calls that at one point
990 /// in time were objc_autoreleaseRV calls. Thus we can disambiguate
991 /// in between objc_autorelease that were inserted from the frontend (which
992 /// we must be very conservative with) and those as a result of strength
993 /// reducing objc_autoreleaseRV calls (which are more flexible).
994 DenseSet<Instruction *> ImpreciseAutoreleaseSet;
996 /// Declarations for ObjC runtime functions, for use in creating calls to
997 /// them. These are initialized lazily to avoid cluttering up the Module
998 /// with unused declarations.
1000 /// Declaration for ObjC runtime function
1001 /// objc_retainAutoreleasedReturnValue.
1002 Constant *RetainRVCallee;
1003 /// Declaration for ObjC runtime function objc_autoreleaseReturnValue.
1004 Constant *AutoreleaseRVCallee;
1005 /// Declaration for ObjC runtime function objc_release.
1006 Constant *ReleaseCallee;
1007 /// Declaration for ObjC runtime function objc_retain.
1008 Constant *RetainCallee;
1009 /// Declaration for ObjC runtime function objc_retainBlock.
1010 Constant *RetainBlockCallee;
1011 /// Declaration for ObjC runtime function objc_autorelease.
1012 Constant *AutoreleaseCallee;
1014 /// Flags which determine whether each of the interesting runtine functions
1015 /// is in fact used in the current function.
1016 unsigned UsedInThisFunction;
1018 /// The Metadata Kind for clang.imprecise_release metadata.
1019 unsigned ImpreciseReleaseMDKind;
1021 /// The Metadata Kind for clang.arc.copy_on_escape metadata.
1022 unsigned CopyOnEscapeMDKind;
1024 /// The Metadata Kind for clang.arc.no_objc_arc_exceptions metadata.
1025 unsigned NoObjCARCExceptionsMDKind;
1027 #ifdef ARC_ANNOTATIONS
1028 /// The Metadata Kind for llvm.arc.annotation.bottomup metadata.
1029 unsigned ARCAnnotationBottomUpMDKind;
1030 /// The Metadata Kind for llvm.arc.annotation.topdown metadata.
1031 unsigned ARCAnnotationTopDownMDKind;
1032 /// The Metadata Kind for llvm.arc.annotation.provenancesource metadata.
1033 unsigned ARCAnnotationProvenanceSourceMDKind;
1034 #endif // ARC_ANNOATIONS
1036 Constant *getRetainRVCallee(Module *M);
1037 Constant *getAutoreleaseRVCallee(Module *M);
1038 Constant *getReleaseCallee(Module *M);
1039 Constant *getRetainCallee(Module *M);
1040 Constant *getRetainBlockCallee(Module *M);
1041 Constant *getAutoreleaseCallee(Module *M);
1043 bool IsRetainBlockOptimizable(const Instruction *Inst);
1045 /// Erase an instruction.
1047 /// This is included separately from the EraseInstruction in ObjCARC.h
1048 /// (which this uses internally) in order to make sure that state is cleaned
1049 /// up. Currently this just means attempting to remove said instruction from
1050 /// ImpreciseAutoreleaseSet if it is an autorelease instruction. This will
1051 /// prevent bugs of the sort where we erase an instruction and forget to
1052 /// remove any associated state.
1054 /// TODO: Maybe remove this, the ImpreciseAutoreleaseSet, the
1055 /// MetadataKind/Callee variables into a separate class.
1056 void EraseInstruction(Instruction *Inst) {
1057 // If Inst is an autorelease instruction, erase it from
1058 // ImpreciseAutoreleaseSet if it is contained there in.
1059 if (GetBasicInstructionClass(Inst) == IC_Autorelease) {
1060 ImpreciseAutoreleaseSet.erase(Inst);
1062 // Invoke the normal EraseInstruction.
1063 llvm::objcarc::EraseInstruction(Inst);
1066 void OptimizeRetainCall(Function &F, Instruction *Retain);
1067 bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV);
1068 void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV,
1069 InstructionClass &Class);
1070 bool OptimizeRetainBlockCall(Function &F, Instruction *RetainBlock,
1071 InstructionClass &Class);
1072 void OptimizeIndividualCalls(Function &F);
1074 void CheckForCFGHazards(const BasicBlock *BB,
1075 DenseMap<const BasicBlock *, BBState> &BBStates,
1076 BBState &MyStates) const;
1077 bool VisitInstructionBottomUp(Instruction *Inst,
1079 MapVector<Value *, RRInfo> &Retains,
1081 bool VisitBottomUp(BasicBlock *BB,
1082 DenseMap<const BasicBlock *, BBState> &BBStates,
1083 MapVector<Value *, RRInfo> &Retains);
1084 bool VisitInstructionTopDown(Instruction *Inst,
1085 DenseMap<Value *, RRInfo> &Releases,
1087 bool VisitTopDown(BasicBlock *BB,
1088 DenseMap<const BasicBlock *, BBState> &BBStates,
1089 DenseMap<Value *, RRInfo> &Releases);
1090 bool Visit(Function &F,
1091 DenseMap<const BasicBlock *, BBState> &BBStates,
1092 MapVector<Value *, RRInfo> &Retains,
1093 DenseMap<Value *, RRInfo> &Releases);
1095 void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove,
1096 MapVector<Value *, RRInfo> &Retains,
1097 DenseMap<Value *, RRInfo> &Releases,
1098 SmallVectorImpl<Instruction *> &DeadInsts,
1101 bool ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState> &BBStates,
1102 MapVector<Value *, RRInfo> &Retains,
1103 DenseMap<Value *, RRInfo> &Releases,
1105 SmallVector<Instruction *, 4> &NewRetains,
1106 SmallVector<Instruction *, 4> &NewReleases,
1107 SmallVector<Instruction *, 8> &DeadInsts,
1108 RRInfo &RetainsToMove,
1109 RRInfo &ReleasesToMove,
1112 bool &AnyPairsCompletelyEliminated);
1114 bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates,
1115 MapVector<Value *, RRInfo> &Retains,
1116 DenseMap<Value *, RRInfo> &Releases,
1119 void OptimizeWeakCalls(Function &F);
1121 bool OptimizeSequences(Function &F);
1123 void OptimizeReturns(Function &F);
1125 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
1126 virtual bool doInitialization(Module &M);
1127 virtual bool runOnFunction(Function &F);
1128 virtual void releaseMemory();
1132 ObjCARCOpt() : FunctionPass(ID) {
1133 initializeObjCARCOptPass(*PassRegistry::getPassRegistry());
1138 char ObjCARCOpt::ID = 0;
1139 INITIALIZE_PASS_BEGIN(ObjCARCOpt,
1140 "objc-arc", "ObjC ARC optimization", false, false)
1141 INITIALIZE_PASS_DEPENDENCY(ObjCARCAliasAnalysis)
1142 INITIALIZE_PASS_END(ObjCARCOpt,
1143 "objc-arc", "ObjC ARC optimization", false, false)
1145 Pass *llvm::createObjCARCOptPass() {
1146 return new ObjCARCOpt();
1149 void ObjCARCOpt::getAnalysisUsage(AnalysisUsage &AU) const {
1150 AU.addRequired<ObjCARCAliasAnalysis>();
1151 AU.addRequired<AliasAnalysis>();
1152 // ARC optimization doesn't currently split critical edges.
1153 AU.setPreservesCFG();
1156 bool ObjCARCOpt::IsRetainBlockOptimizable(const Instruction *Inst) {
1157 // Without the magic metadata tag, we have to assume this might be an
1158 // objc_retainBlock call inserted to convert a block pointer to an id,
1159 // in which case it really is needed.
1160 if (!Inst->getMetadata(CopyOnEscapeMDKind))
1163 // If the pointer "escapes" (not including being used in a call),
1164 // the copy may be needed.
1165 if (DoesRetainableObjPtrEscape(Inst))
1168 // Otherwise, it's not needed.
1172 Constant *ObjCARCOpt::getRetainRVCallee(Module *M) {
1173 if (!RetainRVCallee) {
1174 LLVMContext &C = M->getContext();
1175 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
1176 Type *Params[] = { I8X };
1177 FunctionType *FTy = FunctionType::get(I8X, Params, /*isVarArg=*/false);
1178 AttributeSet Attribute =
1179 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
1180 Attribute::NoUnwind);
1182 M->getOrInsertFunction("objc_retainAutoreleasedReturnValue", FTy,
1185 return RetainRVCallee;
1188 Constant *ObjCARCOpt::getAutoreleaseRVCallee(Module *M) {
1189 if (!AutoreleaseRVCallee) {
1190 LLVMContext &C = M->getContext();
1191 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
1192 Type *Params[] = { I8X };
1193 FunctionType *FTy = FunctionType::get(I8X, Params, /*isVarArg=*/false);
1194 AttributeSet Attribute =
1195 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
1196 Attribute::NoUnwind);
1197 AutoreleaseRVCallee =
1198 M->getOrInsertFunction("objc_autoreleaseReturnValue", FTy,
1201 return AutoreleaseRVCallee;
1204 Constant *ObjCARCOpt::getReleaseCallee(Module *M) {
1205 if (!ReleaseCallee) {
1206 LLVMContext &C = M->getContext();
1207 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
1208 AttributeSet Attribute =
1209 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
1210 Attribute::NoUnwind);
1212 M->getOrInsertFunction(
1214 FunctionType::get(Type::getVoidTy(C), Params, /*isVarArg=*/false),
1217 return ReleaseCallee;
1220 Constant *ObjCARCOpt::getRetainCallee(Module *M) {
1221 if (!RetainCallee) {
1222 LLVMContext &C = M->getContext();
1223 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
1224 AttributeSet Attribute =
1225 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
1226 Attribute::NoUnwind);
1228 M->getOrInsertFunction(
1230 FunctionType::get(Params[0], Params, /*isVarArg=*/false),
1233 return RetainCallee;
1236 Constant *ObjCARCOpt::getRetainBlockCallee(Module *M) {
1237 if (!RetainBlockCallee) {
1238 LLVMContext &C = M->getContext();
1239 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
1240 // objc_retainBlock is not nounwind because it calls user copy constructors
1241 // which could theoretically throw.
1243 M->getOrInsertFunction(
1245 FunctionType::get(Params[0], Params, /*isVarArg=*/false),
1248 return RetainBlockCallee;
1251 Constant *ObjCARCOpt::getAutoreleaseCallee(Module *M) {
1252 if (!AutoreleaseCallee) {
1253 LLVMContext &C = M->getContext();
1254 Type *Params[] = { PointerType::getUnqual(Type::getInt8Ty(C)) };
1255 AttributeSet Attribute =
1256 AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex,
1257 Attribute::NoUnwind);
1259 M->getOrInsertFunction(
1261 FunctionType::get(Params[0], Params, /*isVarArg=*/false),
1264 return AutoreleaseCallee;
1267 /// Turn objc_retain into objc_retainAutoreleasedReturnValue if the operand is a
1270 ObjCARCOpt::OptimizeRetainCall(Function &F, Instruction *Retain) {
1271 ImmutableCallSite CS(GetObjCArg(Retain));
1272 const Instruction *Call = CS.getInstruction();
1274 if (Call->getParent() != Retain->getParent()) return;
1276 // Check that the call is next to the retain.
1277 BasicBlock::const_iterator I = Call;
1279 while (IsNoopInstruction(I)) ++I;
1283 // Turn it to an objc_retainAutoreleasedReturnValue..
1287 DEBUG(dbgs() << "Transforming objc_retain => "
1288 "objc_retainAutoreleasedReturnValue since the operand is a "
1289 "return value.\nOld: "<< *Retain << "\n");
1291 cast<CallInst>(Retain)->setCalledFunction(getRetainRVCallee(F.getParent()));
1293 DEBUG(dbgs() << "New: " << *Retain << "\n");
1296 /// Turn objc_retainAutoreleasedReturnValue into objc_retain if the operand is
1297 /// not a return value. Or, if it can be paired with an
1298 /// objc_autoreleaseReturnValue, delete the pair and return true.
1300 ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) {
1301 // Check for the argument being from an immediately preceding call or invoke.
1302 const Value *Arg = GetObjCArg(RetainRV);
1303 ImmutableCallSite CS(Arg);
1304 if (const Instruction *Call = CS.getInstruction()) {
1305 if (Call->getParent() == RetainRV->getParent()) {
1306 BasicBlock::const_iterator I = Call;
1308 while (IsNoopInstruction(I)) ++I;
1309 if (&*I == RetainRV)
1311 } else if (const InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
1312 BasicBlock *RetainRVParent = RetainRV->getParent();
1313 if (II->getNormalDest() == RetainRVParent) {
1314 BasicBlock::const_iterator I = RetainRVParent->begin();
1315 while (IsNoopInstruction(I)) ++I;
1316 if (&*I == RetainRV)
1322 // Check for being preceded by an objc_autoreleaseReturnValue on the same
1323 // pointer. In this case, we can delete the pair.
1324 BasicBlock::iterator I = RetainRV, Begin = RetainRV->getParent()->begin();
1326 do --I; while (I != Begin && IsNoopInstruction(I));
1327 if (GetBasicInstructionClass(I) == IC_AutoreleaseRV &&
1328 GetObjCArg(I) == Arg) {
1332 DEBUG(dbgs() << "Erasing autoreleaseRV,retainRV pair: " << *I << "\n"
1333 << "Erasing " << *RetainRV << "\n");
1335 EraseInstruction(I);
1336 EraseInstruction(RetainRV);
1341 // Turn it to a plain objc_retain.
1345 DEBUG(dbgs() << "Transforming objc_retainAutoreleasedReturnValue => "
1346 "objc_retain since the operand is not a return value.\n"
1347 "Old = " << *RetainRV << "\n");
1349 cast<CallInst>(RetainRV)->setCalledFunction(getRetainCallee(F.getParent()));
1351 DEBUG(dbgs() << "New = " << *RetainRV << "\n");
1356 /// Turn objc_autoreleaseReturnValue into objc_autorelease if the result is not
1357 /// used as a return value.
1359 ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV,
1360 InstructionClass &Class) {
1361 // Check for a return of the pointer value.
1362 const Value *Ptr = GetObjCArg(AutoreleaseRV);
1363 SmallVector<const Value *, 2> Users;
1364 Users.push_back(Ptr);
1366 Ptr = Users.pop_back_val();
1367 for (Value::const_use_iterator UI = Ptr->use_begin(), UE = Ptr->use_end();
1369 const User *I = *UI;
1370 if (isa<ReturnInst>(I) || GetBasicInstructionClass(I) == IC_RetainRV)
1372 if (isa<BitCastInst>(I))
1375 } while (!Users.empty());
1380 DEBUG(dbgs() << "Transforming objc_autoreleaseReturnValue => "
1381 "objc_autorelease since its operand is not used as a return "
1383 "Old = " << *AutoreleaseRV << "\n");
1385 CallInst *AutoreleaseRVCI = cast<CallInst>(AutoreleaseRV);
1387 setCalledFunction(getAutoreleaseCallee(F.getParent()));
1388 AutoreleaseRVCI->setTailCall(false); // Never tail call objc_autorelease.
1389 Class = IC_Autorelease;
1391 // Stash the given instruction in the ImpreciseAutoreleaseSet so we can check
1392 // later on that this instruction was an autoreleaseRV instruction that was
1393 // converted to an autorelease instead of an autorelease inserted by the
1394 // frontend (which we can not touch).
1395 ImpreciseAutoreleaseSet.insert(AutoreleaseRVCI);
1397 DEBUG(dbgs() << "New: " << *AutoreleaseRV << "\n");
1401 // \brief Attempt to strength reduce objc_retainBlock calls to objc_retain
1404 // Specifically: If an objc_retainBlock call has the copy_on_escape metadata and
1405 // does not escape (following the rules of block escaping), strength reduce the
1406 // objc_retainBlock to an objc_retain.
1408 // TODO: If an objc_retainBlock call is dominated period by a previous
1409 // objc_retainBlock call, strength reduce the objc_retainBlock to an
1412 ObjCARCOpt::OptimizeRetainBlockCall(Function &F, Instruction *Inst,
1413 InstructionClass &Class) {
1414 assert(GetBasicInstructionClass(Inst) == Class);
1415 assert(IC_RetainBlock == Class);
1417 // If we can not optimize Inst, return false.
1418 if (!IsRetainBlockOptimizable(Inst))
1424 DEBUG(dbgs() << "Strength reduced retainBlock => retain.\n");
1425 DEBUG(dbgs() << "Old: " << *Inst << "\n");
1426 CallInst *RetainBlock = cast<CallInst>(Inst);
1427 RetainBlock->setCalledFunction(getRetainCallee(F.getParent()));
1428 // Remove copy_on_escape metadata.
1429 RetainBlock->setMetadata(CopyOnEscapeMDKind, 0);
1431 DEBUG(dbgs() << "New: " << *Inst << "\n");
1435 /// Visit each call, one at a time, and make simplifications without doing any
1436 /// additional analysis.
1437 void ObjCARCOpt::OptimizeIndividualCalls(Function &F) {
1438 DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeIndividualCalls ==\n");
1439 // Reset all the flags in preparation for recomputing them.
1440 UsedInThisFunction = 0;
1442 // Visit all objc_* calls in F.
1443 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
1444 Instruction *Inst = &*I++;
1446 InstructionClass Class = GetBasicInstructionClass(Inst);
1448 DEBUG(dbgs() << "Visiting: Class: " << Class << "; " << *Inst << "\n");
1453 // Delete no-op casts. These function calls have special semantics, but
1454 // the semantics are entirely implemented via lowering in the front-end,
1455 // so by the time they reach the optimizer, they are just no-op calls
1456 // which return their argument.
1458 // There are gray areas here, as the ability to cast reference-counted
1459 // pointers to raw void* and back allows code to break ARC assumptions,
1460 // however these are currently considered to be unimportant.
1464 DEBUG(dbgs() << "Erasing no-op cast: " << *Inst << "\n");
1465 EraseInstruction(Inst);
1468 // If the pointer-to-weak-pointer is null, it's undefined behavior.
1471 case IC_LoadWeakRetained:
1473 case IC_DestroyWeak: {
1474 CallInst *CI = cast<CallInst>(Inst);
1475 if (IsNullOrUndef(CI->getArgOperand(0))) {
1477 Type *Ty = CI->getArgOperand(0)->getType();
1478 new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
1479 Constant::getNullValue(Ty),
1481 llvm::Value *NewValue = UndefValue::get(CI->getType());
1482 DEBUG(dbgs() << "A null pointer-to-weak-pointer is undefined behavior."
1483 "\nOld = " << *CI << "\nNew = " << *NewValue << "\n");
1484 CI->replaceAllUsesWith(NewValue);
1485 CI->eraseFromParent();
1492 CallInst *CI = cast<CallInst>(Inst);
1493 if (IsNullOrUndef(CI->getArgOperand(0)) ||
1494 IsNullOrUndef(CI->getArgOperand(1))) {
1496 Type *Ty = CI->getArgOperand(0)->getType();
1497 new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()),
1498 Constant::getNullValue(Ty),
1501 llvm::Value *NewValue = UndefValue::get(CI->getType());
1502 DEBUG(dbgs() << "A null pointer-to-weak-pointer is undefined behavior."
1503 "\nOld = " << *CI << "\nNew = " << *NewValue << "\n");
1505 CI->replaceAllUsesWith(NewValue);
1506 CI->eraseFromParent();
1511 case IC_RetainBlock:
1512 // If we strength reduce an objc_retainBlock to an objc_retain, continue
1513 // onto the objc_retain peephole optimizations. Otherwise break.
1514 if (!OptimizeRetainBlockCall(F, Inst, Class))
1518 OptimizeRetainCall(F, Inst);
1521 if (OptimizeRetainRVCall(F, Inst))
1524 case IC_AutoreleaseRV:
1525 OptimizeAutoreleaseRVCall(F, Inst, Class);
1529 // objc_autorelease(x) -> objc_release(x) if x is otherwise unused.
1530 if (IsAutorelease(Class) && Inst->use_empty()) {
1531 CallInst *Call = cast<CallInst>(Inst);
1532 const Value *Arg = Call->getArgOperand(0);
1533 Arg = FindSingleUseIdentifiedObject(Arg);
1538 // Create the declaration lazily.
1539 LLVMContext &C = Inst->getContext();
1541 CallInst::Create(getReleaseCallee(F.getParent()),
1542 Call->getArgOperand(0), "", Call);
1543 NewCall->setMetadata(ImpreciseReleaseMDKind,
1544 MDNode::get(C, ArrayRef<Value *>()));
1546 DEBUG(dbgs() << "Replacing autorelease{,RV}(x) with objc_release(x) "
1547 "since x is otherwise unused.\nOld: " << *Call << "\nNew: "
1548 << *NewCall << "\n");
1550 EraseInstruction(Call);
1556 // For functions which can never be passed stack arguments, add
1558 if (IsAlwaysTail(Class)) {
1560 DEBUG(dbgs() << "Adding tail keyword to function since it can never be "
1561 "passed stack args: " << *Inst << "\n");
1562 cast<CallInst>(Inst)->setTailCall();
1565 // Ensure that functions that can never have a "tail" keyword due to the
1566 // semantics of ARC truly do not do so.
1567 if (IsNeverTail(Class)) {
1569 DEBUG(dbgs() << "Removing tail keyword from function: " << *Inst <<
1571 cast<CallInst>(Inst)->setTailCall(false);
1574 // Set nounwind as needed.
1575 if (IsNoThrow(Class)) {
1577 DEBUG(dbgs() << "Found no throw class. Setting nounwind on: " << *Inst
1579 cast<CallInst>(Inst)->setDoesNotThrow();
1582 if (!IsNoopOnNull(Class)) {
1583 UsedInThisFunction |= 1 << Class;
1587 const Value *Arg = GetObjCArg(Inst);
1589 // ARC calls with null are no-ops. Delete them.
1590 if (IsNullOrUndef(Arg)) {
1593 DEBUG(dbgs() << "ARC calls with null are no-ops. Erasing: " << *Inst
1595 EraseInstruction(Inst);
1599 // Keep track of which of retain, release, autorelease, and retain_block
1600 // are actually present in this function.
1601 UsedInThisFunction |= 1 << Class;
1603 // If Arg is a PHI, and one or more incoming values to the
1604 // PHI are null, and the call is control-equivalent to the PHI, and there
1605 // are no relevant side effects between the PHI and the call, the call
1606 // could be pushed up to just those paths with non-null incoming values.
1607 // For now, don't bother splitting critical edges for this.
1608 SmallVector<std::pair<Instruction *, const Value *>, 4> Worklist;
1609 Worklist.push_back(std::make_pair(Inst, Arg));
1611 std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val();
1615 const PHINode *PN = dyn_cast<PHINode>(Arg);
1618 // Determine if the PHI has any null operands, or any incoming
1620 bool HasNull = false;
1621 bool HasCriticalEdges = false;
1622 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1624 StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
1625 if (IsNullOrUndef(Incoming))
1627 else if (cast<TerminatorInst>(PN->getIncomingBlock(i)->back())
1628 .getNumSuccessors() != 1) {
1629 HasCriticalEdges = true;
1633 // If we have null operands and no critical edges, optimize.
1634 if (!HasCriticalEdges && HasNull) {
1635 SmallPtrSet<Instruction *, 4> DependingInstructions;
1636 SmallPtrSet<const BasicBlock *, 4> Visited;
1638 // Check that there is nothing that cares about the reference
1639 // count between the call and the phi.
1642 case IC_RetainBlock:
1643 // These can always be moved up.
1646 // These can't be moved across things that care about the retain
1648 FindDependencies(NeedsPositiveRetainCount, Arg,
1649 Inst->getParent(), Inst,
1650 DependingInstructions, Visited, PA);
1652 case IC_Autorelease:
1653 // These can't be moved across autorelease pool scope boundaries.
1654 FindDependencies(AutoreleasePoolBoundary, Arg,
1655 Inst->getParent(), Inst,
1656 DependingInstructions, Visited, PA);
1659 case IC_AutoreleaseRV:
1660 // Don't move these; the RV optimization depends on the autoreleaseRV
1661 // being tail called, and the retainRV being immediately after a call
1662 // (which might still happen if we get lucky with codegen layout, but
1663 // it's not worth taking the chance).
1666 llvm_unreachable("Invalid dependence flavor");
1669 if (DependingInstructions.size() == 1 &&
1670 *DependingInstructions.begin() == PN) {
1673 // Clone the call into each predecessor that has a non-null value.
1674 CallInst *CInst = cast<CallInst>(Inst);
1675 Type *ParamTy = CInst->getArgOperand(0)->getType();
1676 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1678 StripPointerCastsAndObjCCalls(PN->getIncomingValue(i));
1679 if (!IsNullOrUndef(Incoming)) {
1680 CallInst *Clone = cast<CallInst>(CInst->clone());
1681 Value *Op = PN->getIncomingValue(i);
1682 Instruction *InsertPos = &PN->getIncomingBlock(i)->back();
1683 if (Op->getType() != ParamTy)
1684 Op = new BitCastInst(Op, ParamTy, "", InsertPos);
1685 Clone->setArgOperand(0, Op);
1686 Clone->insertBefore(InsertPos);
1688 DEBUG(dbgs() << "Cloning "
1690 "And inserting clone at " << *InsertPos << "\n");
1691 Worklist.push_back(std::make_pair(Clone, Incoming));
1694 // Erase the original call.
1695 DEBUG(dbgs() << "Erasing: " << *CInst << "\n");
1696 EraseInstruction(CInst);
1700 } while (!Worklist.empty());
1704 /// If we have a top down pointer in the S_Use state, make sure that there are
1705 /// no CFG hazards by checking the states of various bottom up pointers.
1706 static void CheckForUseCFGHazard(const Sequence SuccSSeq,
1707 const bool SuccSRRIKnownSafe,
1709 bool &SomeSuccHasSame,
1710 bool &AllSuccsHaveSame,
1711 bool &ShouldContinue) {
1713 case S_CanRelease: {
1714 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe) {
1715 S.ClearSequenceProgress();
1718 ShouldContinue = true;
1722 SomeSuccHasSame = true;
1726 case S_MovableRelease:
1727 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe)
1728 AllSuccsHaveSame = false;
1731 llvm_unreachable("bottom-up pointer in retain state!");
1733 llvm_unreachable("This should have been handled earlier.");
1737 /// If we have a Top Down pointer in the S_CanRelease state, make sure that
1738 /// there are no CFG hazards by checking the states of various bottom up
1740 static void CheckForCanReleaseCFGHazard(const Sequence SuccSSeq,
1741 const bool SuccSRRIKnownSafe,
1743 bool &SomeSuccHasSame,
1744 bool &AllSuccsHaveSame) {
1747 SomeSuccHasSame = true;
1751 case S_MovableRelease:
1753 if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe)
1754 AllSuccsHaveSame = false;
1757 llvm_unreachable("bottom-up pointer in retain state!");
1759 llvm_unreachable("This should have been handled earlier.");
1763 /// Check for critical edges, loop boundaries, irreducible control flow, or
1764 /// other CFG structures where moving code across the edge would result in it
1765 /// being executed more.
1767 ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB,
1768 DenseMap<const BasicBlock *, BBState> &BBStates,
1769 BBState &MyStates) const {
1770 // If any top-down local-use or possible-dec has a succ which is earlier in
1771 // the sequence, forget it.
1772 for (BBState::ptr_iterator I = MyStates.top_down_ptr_begin(),
1773 E = MyStates.top_down_ptr_end(); I != E; ++I) {
1774 PtrState &S = I->second;
1775 const Sequence Seq = I->second.GetSeq();
1777 // We only care about S_Retain, S_CanRelease, and S_Use.
1781 // Make sure that if extra top down states are added in the future that this
1782 // code is updated to handle it.
1783 assert((Seq == S_Retain || Seq == S_CanRelease || Seq == S_Use) &&
1784 "Unknown top down sequence state.");
1786 const Value *Arg = I->first;
1787 const TerminatorInst *TI = cast<TerminatorInst>(&BB->back());
1788 bool SomeSuccHasSame = false;
1789 bool AllSuccsHaveSame = true;
1791 succ_const_iterator SI(TI), SE(TI, false);
1793 for (; SI != SE; ++SI) {
1794 // If VisitBottomUp has pointer information for this successor, take
1795 // what we know about it.
1796 const DenseMap<const BasicBlock *, BBState>::iterator BBI =
1798 assert(BBI != BBStates.end());
1799 const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);
1800 const Sequence SuccSSeq = SuccS.GetSeq();
1802 // If bottom up, the pointer is in an S_None state, clear the sequence
1803 // progress since the sequence in the bottom up state finished
1804 // suggesting a mismatch in between retains/releases. This is true for
1805 // all three cases that we are handling here: S_Retain, S_Use, and
1807 if (SuccSSeq == S_None) {
1808 S.ClearSequenceProgress();
1812 // If we have S_Use or S_CanRelease, perform our check for cfg hazard
1814 const bool SuccSRRIKnownSafe = SuccS.RRI.KnownSafe;
1816 // *NOTE* We do not use Seq from above here since we are allowing for
1817 // S.GetSeq() to change while we are visiting basic blocks.
1818 switch(S.GetSeq()) {
1820 bool ShouldContinue = false;
1821 CheckForUseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S,
1822 SomeSuccHasSame, AllSuccsHaveSame,
1828 case S_CanRelease: {
1829 CheckForCanReleaseCFGHazard(SuccSSeq, SuccSRRIKnownSafe,
1838 case S_MovableRelease:
1843 // If the state at the other end of any of the successor edges
1844 // matches the current state, require all edges to match. This
1845 // guards against loops in the middle of a sequence.
1846 if (SomeSuccHasSame && !AllSuccsHaveSame)
1847 S.ClearSequenceProgress();
1852 ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst,
1854 MapVector<Value *, RRInfo> &Retains,
1855 BBState &MyStates) {
1856 bool NestingDetected = false;
1857 InstructionClass Class = GetInstructionClass(Inst);
1858 const Value *Arg = 0;
1860 DEBUG(dbgs() << "Class: " << Class << "\n");
1864 Arg = GetObjCArg(Inst);
1866 PtrState &S = MyStates.getPtrBottomUpState(Arg);
1868 // If we see two releases in a row on the same pointer. If so, make
1869 // a note, and we'll cicle back to revisit it after we've
1870 // hopefully eliminated the second release, which may allow us to
1871 // eliminate the first release too.
1872 // Theoretically we could implement removal of nested retain+release
1873 // pairs by making PtrState hold a stack of states, but this is
1874 // simple and avoids adding overhead for the non-nested case.
1875 if (S.GetSeq() == S_Release || S.GetSeq() == S_MovableRelease) {
1876 DEBUG(dbgs() << "Found nested releases (i.e. a release pair)\n");
1877 NestingDetected = true;
1880 MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind);
1881 Sequence NewSeq = ReleaseMetadata ? S_MovableRelease : S_Release;
1882 ANNOTATE_BOTTOMUP(Inst, Arg, S.GetSeq(), NewSeq);
1883 S.ResetSequenceProgress(NewSeq);
1884 S.RRI.ReleaseMetadata = ReleaseMetadata;
1885 S.RRI.KnownSafe = S.HasKnownPositiveRefCount();
1886 S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
1887 S.RRI.Calls.insert(Inst);
1888 S.SetKnownPositiveRefCount();
1891 case IC_RetainBlock:
1892 // In OptimizeIndividualCalls, we have strength reduced all optimizable
1893 // objc_retainBlocks to objc_retains. Thus at this point any
1894 // objc_retainBlocks that we see are not optimizable.
1898 Arg = GetObjCArg(Inst);
1900 PtrState &S = MyStates.getPtrBottomUpState(Arg);
1901 S.SetKnownPositiveRefCount();
1903 Sequence OldSeq = S.GetSeq();
1907 case S_MovableRelease:
1909 // If OldSeq is not S_Use or OldSeq is S_Use and we are tracking an
1910 // imprecise release, clear our reverse insertion points.
1911 if (OldSeq != S_Use || S.RRI.IsTrackingImpreciseReleases())
1912 S.RRI.ReverseInsertPts.clear();
1915 // Don't do retain+release tracking for IC_RetainRV, because it's
1916 // better to let it remain as the first instruction after a call.
1917 if (Class != IC_RetainRV)
1918 Retains[Inst] = S.RRI;
1919 S.ClearSequenceProgress();
1924 llvm_unreachable("bottom-up pointer in retain state!");
1926 ANNOTATE_BOTTOMUP(Inst, Arg, OldSeq, S.GetSeq());
1927 // A retain moving bottom up can be a use.
1930 case IC_AutoreleasepoolPop:
1931 // Conservatively, clear MyStates for all known pointers.
1932 MyStates.clearBottomUpPointers();
1933 return NestingDetected;
1934 case IC_AutoreleasepoolPush:
1936 // These are irrelevant.
1937 return NestingDetected;
1942 // Consider any other possible effects of this instruction on each
1943 // pointer being tracked.
1944 for (BBState::ptr_iterator MI = MyStates.bottom_up_ptr_begin(),
1945 ME = MyStates.bottom_up_ptr_end(); MI != ME; ++MI) {
1946 const Value *Ptr = MI->first;
1948 continue; // Handled above.
1949 PtrState &S = MI->second;
1950 Sequence Seq = S.GetSeq();
1952 // Check for possible releases.
1953 if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
1954 DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr
1956 S.ClearKnownPositiveRefCount();
1959 S.SetSeq(S_CanRelease);
1960 ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S.GetSeq());
1964 case S_MovableRelease:
1969 llvm_unreachable("bottom-up pointer in retain state!");
1973 // Check for possible direct uses.
1976 case S_MovableRelease:
1977 if (CanUse(Inst, Ptr, PA, Class)) {
1978 DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr
1980 assert(S.RRI.ReverseInsertPts.empty());
1981 // If this is an invoke instruction, we're scanning it as part of
1982 // one of its successor blocks, since we can't insert code after it
1983 // in its own block, and we don't want to split critical edges.
1984 if (isa<InvokeInst>(Inst))
1985 S.RRI.ReverseInsertPts.insert(BB->getFirstInsertionPt());
1987 S.RRI.ReverseInsertPts.insert(llvm::next(BasicBlock::iterator(Inst)));
1989 ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S_Use);
1990 } else if (Seq == S_Release && IsUser(Class)) {
1991 DEBUG(dbgs() << "PreciseReleaseUse: Seq: " << Seq << "; " << *Ptr
1993 // Non-movable releases depend on any possible objc pointer use.
1995 ANNOTATE_BOTTOMUP(Inst, Ptr, S_Release, S_Stop);
1996 assert(S.RRI.ReverseInsertPts.empty());
1997 // As above; handle invoke specially.
1998 if (isa<InvokeInst>(Inst))
1999 S.RRI.ReverseInsertPts.insert(BB->getFirstInsertionPt());
2001 S.RRI.ReverseInsertPts.insert(llvm::next(BasicBlock::iterator(Inst)));
2005 if (CanUse(Inst, Ptr, PA, Class)) {
2006 DEBUG(dbgs() << "PreciseStopUse: Seq: " << Seq << "; " << *Ptr
2009 ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S_Use);
2017 llvm_unreachable("bottom-up pointer in retain state!");
2021 return NestingDetected;
2025 ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
2026 DenseMap<const BasicBlock *, BBState> &BBStates,
2027 MapVector<Value *, RRInfo> &Retains) {
2029 DEBUG(dbgs() << "\n== ObjCARCOpt::VisitBottomUp ==\n");
2031 bool NestingDetected = false;
2032 BBState &MyStates = BBStates[BB];
2034 // Merge the states from each successor to compute the initial state
2035 // for the current block.
2036 BBState::edge_iterator SI(MyStates.succ_begin()),
2037 SE(MyStates.succ_end());
2039 const BasicBlock *Succ = *SI;
2040 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ);
2041 assert(I != BBStates.end());
2042 MyStates.InitFromSucc(I->second);
2044 for (; SI != SE; ++SI) {
2046 I = BBStates.find(Succ);
2047 assert(I != BBStates.end());
2048 MyStates.MergeSucc(I->second);
2052 // If ARC Annotations are enabled, output the current state of pointers at the
2053 // bottom of the basic block.
2054 ANNOTATE_BOTTOMUP_BBEND(MyStates, BB);
2056 // Visit all the instructions, bottom-up.
2057 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
2058 Instruction *Inst = llvm::prior(I);
2060 // Invoke instructions are visited as part of their successors (below).
2061 if (isa<InvokeInst>(Inst))
2064 DEBUG(dbgs() << "Visiting " << *Inst << "\n");
2066 NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates);
2069 // If there's a predecessor with an invoke, visit the invoke as if it were
2070 // part of this block, since we can't insert code after an invoke in its own
2071 // block, and we don't want to split critical edges.
2072 for (BBState::edge_iterator PI(MyStates.pred_begin()),
2073 PE(MyStates.pred_end()); PI != PE; ++PI) {
2074 BasicBlock *Pred = *PI;
2075 if (InvokeInst *II = dyn_cast<InvokeInst>(&Pred->back()))
2076 NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates);
2079 // If ARC Annotations are enabled, output the current state of pointers at the
2080 // top of the basic block.
2081 ANNOTATE_BOTTOMUP_BBSTART(MyStates, BB);
2083 return NestingDetected;
2087 ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst,
2088 DenseMap<Value *, RRInfo> &Releases,
2089 BBState &MyStates) {
2090 bool NestingDetected = false;
2091 InstructionClass Class = GetInstructionClass(Inst);
2092 const Value *Arg = 0;
2095 case IC_RetainBlock:
2096 // In OptimizeIndividualCalls, we have strength reduced all optimizable
2097 // objc_retainBlocks to objc_retains. Thus at this point any
2098 // objc_retainBlocks that we see are not optimizable.
2102 Arg = GetObjCArg(Inst);
2104 PtrState &S = MyStates.getPtrTopDownState(Arg);
2106 // Don't do retain+release tracking for IC_RetainRV, because it's
2107 // better to let it remain as the first instruction after a call.
2108 if (Class != IC_RetainRV) {
2109 // If we see two retains in a row on the same pointer. If so, make
2110 // a note, and we'll cicle back to revisit it after we've
2111 // hopefully eliminated the second retain, which may allow us to
2112 // eliminate the first retain too.
2113 // Theoretically we could implement removal of nested retain+release
2114 // pairs by making PtrState hold a stack of states, but this is
2115 // simple and avoids adding overhead for the non-nested case.
2116 if (S.GetSeq() == S_Retain)
2117 NestingDetected = true;
2119 ANNOTATE_TOPDOWN(Inst, Arg, S.GetSeq(), S_Retain);
2120 S.ResetSequenceProgress(S_Retain);
2121 S.RRI.KnownSafe = S.HasKnownPositiveRefCount();
2122 S.RRI.Calls.insert(Inst);
2125 S.SetKnownPositiveRefCount();
2127 // A retain can be a potential use; procede to the generic checking
2132 Arg = GetObjCArg(Inst);
2134 PtrState &S = MyStates.getPtrTopDownState(Arg);
2135 S.ClearKnownPositiveRefCount();
2137 Sequence OldSeq = S.GetSeq();
2139 MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind);
2144 if (OldSeq == S_Retain || ReleaseMetadata != 0)
2145 S.RRI.ReverseInsertPts.clear();
2148 S.RRI.ReleaseMetadata = ReleaseMetadata;
2149 S.RRI.IsTailCallRelease = cast<CallInst>(Inst)->isTailCall();
2150 Releases[Inst] = S.RRI;
2151 ANNOTATE_TOPDOWN(Inst, Arg, S.GetSeq(), S_None);
2152 S.ClearSequenceProgress();
2158 case S_MovableRelease:
2159 llvm_unreachable("top-down pointer in release state!");
2163 case IC_AutoreleasepoolPop:
2164 // Conservatively, clear MyStates for all known pointers.
2165 MyStates.clearTopDownPointers();
2166 return NestingDetected;
2167 case IC_AutoreleasepoolPush:
2169 // These are irrelevant.
2170 return NestingDetected;
2175 // Consider any other possible effects of this instruction on each
2176 // pointer being tracked.
2177 for (BBState::ptr_iterator MI = MyStates.top_down_ptr_begin(),
2178 ME = MyStates.top_down_ptr_end(); MI != ME; ++MI) {
2179 const Value *Ptr = MI->first;
2181 continue; // Handled above.
2182 PtrState &S = MI->second;
2183 Sequence Seq = S.GetSeq();
2185 // Check for possible releases.
2186 if (CanAlterRefCount(Inst, Ptr, PA, Class)) {
2187 DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr
2189 S.ClearKnownPositiveRefCount();
2192 S.SetSeq(S_CanRelease);
2193 ANNOTATE_TOPDOWN(Inst, Ptr, Seq, S_CanRelease);
2194 assert(S.RRI.ReverseInsertPts.empty());
2195 S.RRI.ReverseInsertPts.insert(Inst);
2197 // One call can't cause a transition from S_Retain to S_CanRelease
2198 // and S_CanRelease to S_Use. If we've made the first transition,
2207 case S_MovableRelease:
2208 llvm_unreachable("top-down pointer in release state!");
2212 // Check for possible direct uses.
2215 if (CanUse(Inst, Ptr, PA, Class)) {
2216 DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr
2219 ANNOTATE_TOPDOWN(Inst, Ptr, Seq, S_Use);
2228 case S_MovableRelease:
2229 llvm_unreachable("top-down pointer in release state!");
2233 return NestingDetected;
2237 ObjCARCOpt::VisitTopDown(BasicBlock *BB,
2238 DenseMap<const BasicBlock *, BBState> &BBStates,
2239 DenseMap<Value *, RRInfo> &Releases) {
2240 DEBUG(dbgs() << "\n== ObjCARCOpt::VisitTopDown ==\n");
2241 bool NestingDetected = false;
2242 BBState &MyStates = BBStates[BB];
2244 // Merge the states from each predecessor to compute the initial state
2245 // for the current block.
2246 BBState::edge_iterator PI(MyStates.pred_begin()),
2247 PE(MyStates.pred_end());
2249 const BasicBlock *Pred = *PI;
2250 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred);
2251 assert(I != BBStates.end());
2252 MyStates.InitFromPred(I->second);
2254 for (; PI != PE; ++PI) {
2256 I = BBStates.find(Pred);
2257 assert(I != BBStates.end());
2258 MyStates.MergePred(I->second);
2262 // If ARC Annotations are enabled, output the current state of pointers at the
2263 // top of the basic block.
2264 ANNOTATE_TOPDOWN_BBSTART(MyStates, BB);
2266 // Visit all the instructions, top-down.
2267 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
2268 Instruction *Inst = I;
2270 DEBUG(dbgs() << "Visiting " << *Inst << "\n");
2272 NestingDetected |= VisitInstructionTopDown(Inst, Releases, MyStates);
2275 // If ARC Annotations are enabled, output the current state of pointers at the
2276 // bottom of the basic block.
2277 ANNOTATE_TOPDOWN_BBEND(MyStates, BB);
2279 #ifdef ARC_ANNOTATIONS
2280 if (!(EnableARCAnnotations && DisableCheckForCFGHazards))
2282 CheckForCFGHazards(BB, BBStates, MyStates);
2283 return NestingDetected;
2287 ComputePostOrders(Function &F,
2288 SmallVectorImpl<BasicBlock *> &PostOrder,
2289 SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder,
2290 unsigned NoObjCARCExceptionsMDKind,
2291 DenseMap<const BasicBlock *, BBState> &BBStates) {
2292 /// The visited set, for doing DFS walks.
2293 SmallPtrSet<BasicBlock *, 16> Visited;
2295 // Do DFS, computing the PostOrder.
2296 SmallPtrSet<BasicBlock *, 16> OnStack;
2297 SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack;
2299 // Functions always have exactly one entry block, and we don't have
2300 // any other block that we treat like an entry block.
2301 BasicBlock *EntryBB = &F.getEntryBlock();
2302 BBState &MyStates = BBStates[EntryBB];
2303 MyStates.SetAsEntry();
2304 TerminatorInst *EntryTI = cast<TerminatorInst>(&EntryBB->back());
2305 SuccStack.push_back(std::make_pair(EntryBB, succ_iterator(EntryTI)));
2306 Visited.insert(EntryBB);
2307 OnStack.insert(EntryBB);
2310 BasicBlock *CurrBB = SuccStack.back().first;
2311 TerminatorInst *TI = cast<TerminatorInst>(&CurrBB->back());
2312 succ_iterator SE(TI, false);
2314 while (SuccStack.back().second != SE) {
2315 BasicBlock *SuccBB = *SuccStack.back().second++;
2316 if (Visited.insert(SuccBB)) {
2317 TerminatorInst *TI = cast<TerminatorInst>(&SuccBB->back());
2318 SuccStack.push_back(std::make_pair(SuccBB, succ_iterator(TI)));
2319 BBStates[CurrBB].addSucc(SuccBB);
2320 BBState &SuccStates = BBStates[SuccBB];
2321 SuccStates.addPred(CurrBB);
2322 OnStack.insert(SuccBB);
2326 if (!OnStack.count(SuccBB)) {
2327 BBStates[CurrBB].addSucc(SuccBB);
2328 BBStates[SuccBB].addPred(CurrBB);
2331 OnStack.erase(CurrBB);
2332 PostOrder.push_back(CurrBB);
2333 SuccStack.pop_back();
2334 } while (!SuccStack.empty());
2338 // Do reverse-CFG DFS, computing the reverse-CFG PostOrder.
2339 // Functions may have many exits, and there also blocks which we treat
2340 // as exits due to ignored edges.
2341 SmallVector<std::pair<BasicBlock *, BBState::edge_iterator>, 16> PredStack;
2342 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
2343 BasicBlock *ExitBB = I;
2344 BBState &MyStates = BBStates[ExitBB];
2345 if (!MyStates.isExit())
2348 MyStates.SetAsExit();
2350 PredStack.push_back(std::make_pair(ExitBB, MyStates.pred_begin()));
2351 Visited.insert(ExitBB);
2352 while (!PredStack.empty()) {
2353 reverse_dfs_next_succ:
2354 BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end();
2355 while (PredStack.back().second != PE) {
2356 BasicBlock *BB = *PredStack.back().second++;
2357 if (Visited.insert(BB)) {
2358 PredStack.push_back(std::make_pair(BB, BBStates[BB].pred_begin()));
2359 goto reverse_dfs_next_succ;
2362 ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first);
2367 // Visit the function both top-down and bottom-up.
2369 ObjCARCOpt::Visit(Function &F,
2370 DenseMap<const BasicBlock *, BBState> &BBStates,
2371 MapVector<Value *, RRInfo> &Retains,
2372 DenseMap<Value *, RRInfo> &Releases) {
2374 // Use reverse-postorder traversals, because we magically know that loops
2375 // will be well behaved, i.e. they won't repeatedly call retain on a single
2376 // pointer without doing a release. We can't use the ReversePostOrderTraversal
2377 // class here because we want the reverse-CFG postorder to consider each
2378 // function exit point, and we want to ignore selected cycle edges.
2379 SmallVector<BasicBlock *, 16> PostOrder;
2380 SmallVector<BasicBlock *, 16> ReverseCFGPostOrder;
2381 ComputePostOrders(F, PostOrder, ReverseCFGPostOrder,
2382 NoObjCARCExceptionsMDKind,
2385 // Use reverse-postorder on the reverse CFG for bottom-up.
2386 bool BottomUpNestingDetected = false;
2387 for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
2388 ReverseCFGPostOrder.rbegin(), E = ReverseCFGPostOrder.rend();
2390 BottomUpNestingDetected |= VisitBottomUp(*I, BBStates, Retains);
2392 // Use reverse-postorder for top-down.
2393 bool TopDownNestingDetected = false;
2394 for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I =
2395 PostOrder.rbegin(), E = PostOrder.rend();
2397 TopDownNestingDetected |= VisitTopDown(*I, BBStates, Releases);
2399 return TopDownNestingDetected && BottomUpNestingDetected;
2402 /// Move the calls in RetainsToMove and ReleasesToMove.
2403 void ObjCARCOpt::MoveCalls(Value *Arg,
2404 RRInfo &RetainsToMove,
2405 RRInfo &ReleasesToMove,
2406 MapVector<Value *, RRInfo> &Retains,
2407 DenseMap<Value *, RRInfo> &Releases,
2408 SmallVectorImpl<Instruction *> &DeadInsts,
2410 Type *ArgTy = Arg->getType();
2411 Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext()));
2413 DEBUG(dbgs() << "== ObjCARCOpt::MoveCalls ==\n");
2415 // Insert the new retain and release calls.
2416 for (SmallPtrSet<Instruction *, 2>::const_iterator
2417 PI = ReleasesToMove.ReverseInsertPts.begin(),
2418 PE = ReleasesToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
2419 Instruction *InsertPt = *PI;
2420 Value *MyArg = ArgTy == ParamTy ? Arg :
2421 new BitCastInst(Arg, ParamTy, "", InsertPt);
2423 CallInst::Create(getRetainCallee(M), MyArg, "", InsertPt);
2424 Call->setDoesNotThrow();
2425 Call->setTailCall();
2427 DEBUG(dbgs() << "Inserting new Retain: " << *Call << "\n"
2428 "At insertion point: " << *InsertPt << "\n");
2430 for (SmallPtrSet<Instruction *, 2>::const_iterator
2431 PI = RetainsToMove.ReverseInsertPts.begin(),
2432 PE = RetainsToMove.ReverseInsertPts.end(); PI != PE; ++PI) {
2433 Instruction *InsertPt = *PI;
2434 Value *MyArg = ArgTy == ParamTy ? Arg :
2435 new BitCastInst(Arg, ParamTy, "", InsertPt);
2436 CallInst *Call = CallInst::Create(getReleaseCallee(M), MyArg,
2438 // Attach a clang.imprecise_release metadata tag, if appropriate.
2439 if (MDNode *M = ReleasesToMove.ReleaseMetadata)
2440 Call->setMetadata(ImpreciseReleaseMDKind, M);
2441 Call->setDoesNotThrow();
2442 if (ReleasesToMove.IsTailCallRelease)
2443 Call->setTailCall();
2445 DEBUG(dbgs() << "Inserting new Release: " << *Call << "\n"
2446 "At insertion point: " << *InsertPt << "\n");
2449 // Delete the original retain and release calls.
2450 for (SmallPtrSet<Instruction *, 2>::const_iterator
2451 AI = RetainsToMove.Calls.begin(),
2452 AE = RetainsToMove.Calls.end(); AI != AE; ++AI) {
2453 Instruction *OrigRetain = *AI;
2454 Retains.blot(OrigRetain);
2455 DeadInsts.push_back(OrigRetain);
2456 DEBUG(dbgs() << "Deleting retain: " << *OrigRetain << "\n");
2458 for (SmallPtrSet<Instruction *, 2>::const_iterator
2459 AI = ReleasesToMove.Calls.begin(),
2460 AE = ReleasesToMove.Calls.end(); AI != AE; ++AI) {
2461 Instruction *OrigRelease = *AI;
2462 Releases.erase(OrigRelease);
2463 DeadInsts.push_back(OrigRelease);
2464 DEBUG(dbgs() << "Deleting release: " << *OrigRelease << "\n");
2470 ObjCARCOpt::ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState>
2472 MapVector<Value *, RRInfo> &Retains,
2473 DenseMap<Value *, RRInfo> &Releases,
2475 SmallVector<Instruction *, 4> &NewRetains,
2476 SmallVector<Instruction *, 4> &NewReleases,
2477 SmallVector<Instruction *, 8> &DeadInsts,
2478 RRInfo &RetainsToMove,
2479 RRInfo &ReleasesToMove,
2482 bool &AnyPairsCompletelyEliminated) {
2483 // If a pair happens in a region where it is known that the reference count
2484 // is already incremented, we can similarly ignore possible decrements.
2485 bool KnownSafeTD = true, KnownSafeBU = true;
2487 // Connect the dots between the top-down-collected RetainsToMove and
2488 // bottom-up-collected ReleasesToMove to form sets of related calls.
2489 // This is an iterative process so that we connect multiple releases
2490 // to multiple retains if needed.
2491 unsigned OldDelta = 0;
2492 unsigned NewDelta = 0;
2493 unsigned OldCount = 0;
2494 unsigned NewCount = 0;
2495 bool FirstRelease = true;
2497 for (SmallVectorImpl<Instruction *>::const_iterator
2498 NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) {
2499 Instruction *NewRetain = *NI;
2500 MapVector<Value *, RRInfo>::const_iterator It = Retains.find(NewRetain);
2501 assert(It != Retains.end());
2502 const RRInfo &NewRetainRRI = It->second;
2503 KnownSafeTD &= NewRetainRRI.KnownSafe;
2504 for (SmallPtrSet<Instruction *, 2>::const_iterator
2505 LI = NewRetainRRI.Calls.begin(),
2506 LE = NewRetainRRI.Calls.end(); LI != LE; ++LI) {
2507 Instruction *NewRetainRelease = *LI;
2508 DenseMap<Value *, RRInfo>::const_iterator Jt =
2509 Releases.find(NewRetainRelease);
2510 if (Jt == Releases.end())
2512 const RRInfo &NewRetainReleaseRRI = Jt->second;
2513 assert(NewRetainReleaseRRI.Calls.count(NewRetain));
2514 if (ReleasesToMove.Calls.insert(NewRetainRelease)) {
2516 BBStates[NewRetainRelease->getParent()].GetAllPathCount();
2518 // Merge the ReleaseMetadata and IsTailCallRelease values.
2520 ReleasesToMove.ReleaseMetadata =
2521 NewRetainReleaseRRI.ReleaseMetadata;
2522 ReleasesToMove.IsTailCallRelease =
2523 NewRetainReleaseRRI.IsTailCallRelease;
2524 FirstRelease = false;
2526 if (ReleasesToMove.ReleaseMetadata !=
2527 NewRetainReleaseRRI.ReleaseMetadata)
2528 ReleasesToMove.ReleaseMetadata = 0;
2529 if (ReleasesToMove.IsTailCallRelease !=
2530 NewRetainReleaseRRI.IsTailCallRelease)
2531 ReleasesToMove.IsTailCallRelease = false;
2534 // Collect the optimal insertion points.
2536 for (SmallPtrSet<Instruction *, 2>::const_iterator
2537 RI = NewRetainReleaseRRI.ReverseInsertPts.begin(),
2538 RE = NewRetainReleaseRRI.ReverseInsertPts.end();
2540 Instruction *RIP = *RI;
2541 if (ReleasesToMove.ReverseInsertPts.insert(RIP))
2542 NewDelta -= BBStates[RIP->getParent()].GetAllPathCount();
2544 NewReleases.push_back(NewRetainRelease);
2549 if (NewReleases.empty()) break;
2551 // Back the other way.
2552 for (SmallVectorImpl<Instruction *>::const_iterator
2553 NI = NewReleases.begin(), NE = NewReleases.end(); NI != NE; ++NI) {
2554 Instruction *NewRelease = *NI;
2555 DenseMap<Value *, RRInfo>::const_iterator It =
2556 Releases.find(NewRelease);
2557 assert(It != Releases.end());
2558 const RRInfo &NewReleaseRRI = It->second;
2559 KnownSafeBU &= NewReleaseRRI.KnownSafe;
2560 for (SmallPtrSet<Instruction *, 2>::const_iterator
2561 LI = NewReleaseRRI.Calls.begin(),
2562 LE = NewReleaseRRI.Calls.end(); LI != LE; ++LI) {
2563 Instruction *NewReleaseRetain = *LI;
2564 MapVector<Value *, RRInfo>::const_iterator Jt =
2565 Retains.find(NewReleaseRetain);
2566 if (Jt == Retains.end())
2568 const RRInfo &NewReleaseRetainRRI = Jt->second;
2569 assert(NewReleaseRetainRRI.Calls.count(NewRelease));
2570 if (RetainsToMove.Calls.insert(NewReleaseRetain)) {
2571 unsigned PathCount =
2572 BBStates[NewReleaseRetain->getParent()].GetAllPathCount();
2573 OldDelta += PathCount;
2574 OldCount += PathCount;
2576 // Collect the optimal insertion points.
2578 for (SmallPtrSet<Instruction *, 2>::const_iterator
2579 RI = NewReleaseRetainRRI.ReverseInsertPts.begin(),
2580 RE = NewReleaseRetainRRI.ReverseInsertPts.end();
2582 Instruction *RIP = *RI;
2583 if (RetainsToMove.ReverseInsertPts.insert(RIP)) {
2584 PathCount = BBStates[RIP->getParent()].GetAllPathCount();
2585 NewDelta += PathCount;
2586 NewCount += PathCount;
2589 NewRetains.push_back(NewReleaseRetain);
2593 NewReleases.clear();
2594 if (NewRetains.empty()) break;
2597 // If the pointer is known incremented or nested, we can safely delete the
2598 // pair regardless of what's between them.
2599 if (KnownSafeTD || KnownSafeBU) {
2600 RetainsToMove.ReverseInsertPts.clear();
2601 ReleasesToMove.ReverseInsertPts.clear();
2604 // Determine whether the new insertion points we computed preserve the
2605 // balance of retain and release calls through the program.
2606 // TODO: If the fully aggressive solution isn't valid, try to find a
2607 // less aggressive solution which is.
2612 // Determine whether the original call points are balanced in the retain and
2613 // release calls through the program. If not, conservatively don't touch
2615 // TODO: It's theoretically possible to do code motion in this case, as
2616 // long as the existing imbalances are maintained.
2621 assert(OldCount != 0 && "Unreachable code?");
2622 NumRRs += OldCount - NewCount;
2623 // Set to true if we completely removed any RR pairs.
2624 AnyPairsCompletelyEliminated = NewCount == 0;
2626 // We can move calls!
2630 /// Identify pairings between the retains and releases, and delete and/or move
2633 ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState>
2635 MapVector<Value *, RRInfo> &Retains,
2636 DenseMap<Value *, RRInfo> &Releases,
2638 DEBUG(dbgs() << "\n== ObjCARCOpt::PerformCodePlacement ==\n");
2640 bool AnyPairsCompletelyEliminated = false;
2641 RRInfo RetainsToMove;
2642 RRInfo ReleasesToMove;
2643 SmallVector<Instruction *, 4> NewRetains;
2644 SmallVector<Instruction *, 4> NewReleases;
2645 SmallVector<Instruction *, 8> DeadInsts;
2647 // Visit each retain.
2648 for (MapVector<Value *, RRInfo>::const_iterator I = Retains.begin(),
2649 E = Retains.end(); I != E; ++I) {
2650 Value *V = I->first;
2651 if (!V) continue; // blotted
2653 Instruction *Retain = cast<Instruction>(V);
2655 DEBUG(dbgs() << "Visiting: " << *Retain << "\n");
2657 Value *Arg = GetObjCArg(Retain);
2659 // If the object being released is in static or stack storage, we know it's
2660 // not being managed by ObjC reference counting, so we can delete pairs
2661 // regardless of what possible decrements or uses lie between them.
2662 bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg);
2664 // A constant pointer can't be pointing to an object on the heap. It may
2665 // be reference-counted, but it won't be deleted.
2666 if (const LoadInst *LI = dyn_cast<LoadInst>(Arg))
2667 if (const GlobalVariable *GV =
2668 dyn_cast<GlobalVariable>(
2669 StripPointerCastsAndObjCCalls(LI->getPointerOperand())))
2670 if (GV->isConstant())
2673 // Connect the dots between the top-down-collected RetainsToMove and
2674 // bottom-up-collected ReleasesToMove to form sets of related calls.
2675 NewRetains.push_back(Retain);
2676 bool PerformMoveCalls =
2677 ConnectTDBUTraversals(BBStates, Retains, Releases, M, NewRetains,
2678 NewReleases, DeadInsts, RetainsToMove,
2679 ReleasesToMove, Arg, KnownSafe,
2680 AnyPairsCompletelyEliminated);
2682 #ifdef ARC_ANNOTATIONS
2683 // Do not move calls if ARC annotations are requested. If we were to move
2684 // calls in this case, we would not be able
2685 PerformMoveCalls = PerformMoveCalls && !EnableARCAnnotations;
2686 #endif // ARC_ANNOTATIONS
2688 if (PerformMoveCalls) {
2689 // Ok, everything checks out and we're all set. Let's move/delete some
2691 MoveCalls(Arg, RetainsToMove, ReleasesToMove,
2692 Retains, Releases, DeadInsts, M);
2695 // Clean up state for next retain.
2696 NewReleases.clear();
2698 RetainsToMove.clear();
2699 ReleasesToMove.clear();
2702 // Now that we're done moving everything, we can delete the newly dead
2703 // instructions, as we no longer need them as insert points.
2704 while (!DeadInsts.empty())
2705 EraseInstruction(DeadInsts.pop_back_val());
2707 return AnyPairsCompletelyEliminated;
2710 /// Weak pointer optimizations.
2711 void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
2712 DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeWeakCalls ==\n");
2714 // First, do memdep-style RLE and S2L optimizations. We can't use memdep
2715 // itself because it uses AliasAnalysis and we need to do provenance
2717 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2718 Instruction *Inst = &*I++;
2720 DEBUG(dbgs() << "Visiting: " << *Inst << "\n");
2722 InstructionClass Class = GetBasicInstructionClass(Inst);
2723 if (Class != IC_LoadWeak && Class != IC_LoadWeakRetained)
2726 // Delete objc_loadWeak calls with no users.
2727 if (Class == IC_LoadWeak && Inst->use_empty()) {
2728 Inst->eraseFromParent();
2732 // TODO: For now, just look for an earlier available version of this value
2733 // within the same block. Theoretically, we could do memdep-style non-local
2734 // analysis too, but that would want caching. A better approach would be to
2735 // use the technique that EarlyCSE uses.
2736 inst_iterator Current = llvm::prior(I);
2737 BasicBlock *CurrentBB = Current.getBasicBlockIterator();
2738 for (BasicBlock::iterator B = CurrentBB->begin(),
2739 J = Current.getInstructionIterator();
2741 Instruction *EarlierInst = &*llvm::prior(J);
2742 InstructionClass EarlierClass = GetInstructionClass(EarlierInst);
2743 switch (EarlierClass) {
2745 case IC_LoadWeakRetained: {
2746 // If this is loading from the same pointer, replace this load's value
2748 CallInst *Call = cast<CallInst>(Inst);
2749 CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2750 Value *Arg = Call->getArgOperand(0);
2751 Value *EarlierArg = EarlierCall->getArgOperand(0);
2752 switch (PA.getAA()->alias(Arg, EarlierArg)) {
2753 case AliasAnalysis::MustAlias:
2755 // If the load has a builtin retain, insert a plain retain for it.
2756 if (Class == IC_LoadWeakRetained) {
2758 CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
2762 // Zap the fully redundant load.
2763 Call->replaceAllUsesWith(EarlierCall);
2764 Call->eraseFromParent();
2766 case AliasAnalysis::MayAlias:
2767 case AliasAnalysis::PartialAlias:
2769 case AliasAnalysis::NoAlias:
2776 // If this is storing to the same pointer and has the same size etc.
2777 // replace this load's value with the stored value.
2778 CallInst *Call = cast<CallInst>(Inst);
2779 CallInst *EarlierCall = cast<CallInst>(EarlierInst);
2780 Value *Arg = Call->getArgOperand(0);
2781 Value *EarlierArg = EarlierCall->getArgOperand(0);
2782 switch (PA.getAA()->alias(Arg, EarlierArg)) {
2783 case AliasAnalysis::MustAlias:
2785 // If the load has a builtin retain, insert a plain retain for it.
2786 if (Class == IC_LoadWeakRetained) {
2788 CallInst::Create(getRetainCallee(F.getParent()), EarlierCall,
2792 // Zap the fully redundant load.
2793 Call->replaceAllUsesWith(EarlierCall->getArgOperand(1));
2794 Call->eraseFromParent();
2796 case AliasAnalysis::MayAlias:
2797 case AliasAnalysis::PartialAlias:
2799 case AliasAnalysis::NoAlias:
2806 // TOOD: Grab the copied value.
2808 case IC_AutoreleasepoolPush:
2810 case IC_IntrinsicUser:
2812 // Weak pointers are only modified through the weak entry points
2813 // (and arbitrary calls, which could call the weak entry points).
2816 // Anything else could modify the weak pointer.
2823 // Then, for each destroyWeak with an alloca operand, check to see if
2824 // the alloca and all its users can be zapped.
2825 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2826 Instruction *Inst = &*I++;
2827 InstructionClass Class = GetBasicInstructionClass(Inst);
2828 if (Class != IC_DestroyWeak)
2831 CallInst *Call = cast<CallInst>(Inst);
2832 Value *Arg = Call->getArgOperand(0);
2833 if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) {
2834 for (Value::use_iterator UI = Alloca->use_begin(),
2835 UE = Alloca->use_end(); UI != UE; ++UI) {
2836 const Instruction *UserInst = cast<Instruction>(*UI);
2837 switch (GetBasicInstructionClass(UserInst)) {
2840 case IC_DestroyWeak:
2847 for (Value::use_iterator UI = Alloca->use_begin(),
2848 UE = Alloca->use_end(); UI != UE; ) {
2849 CallInst *UserInst = cast<CallInst>(*UI++);
2850 switch (GetBasicInstructionClass(UserInst)) {
2853 // These functions return their second argument.
2854 UserInst->replaceAllUsesWith(UserInst->getArgOperand(1));
2856 case IC_DestroyWeak:
2860 llvm_unreachable("alloca really is used!");
2862 UserInst->eraseFromParent();
2864 Alloca->eraseFromParent();
2870 /// Identify program paths which execute sequences of retains and releases which
2871 /// can be eliminated.
2872 bool ObjCARCOpt::OptimizeSequences(Function &F) {
2873 /// Releases, Retains - These are used to store the results of the main flow
2874 /// analysis. These use Value* as the key instead of Instruction* so that the
2875 /// map stays valid when we get around to rewriting code and calls get
2876 /// replaced by arguments.
2877 DenseMap<Value *, RRInfo> Releases;
2878 MapVector<Value *, RRInfo> Retains;
2880 /// This is used during the traversal of the function to track the
2881 /// states for each identified object at each block.
2882 DenseMap<const BasicBlock *, BBState> BBStates;
2884 // Analyze the CFG of the function, and all instructions.
2885 bool NestingDetected = Visit(F, BBStates, Retains, Releases);
2888 return PerformCodePlacement(BBStates, Retains, Releases, F.getParent()) &&
2892 /// Check if there is a dependent call earlier that does not have anything in
2893 /// between the Retain and the call that can affect the reference count of their
2894 /// shared pointer argument. Note that Retain need not be in BB.
2896 HasSafePathToPredecessorCall(const Value *Arg, Instruction *Retain,
2897 SmallPtrSet<Instruction *, 4> &DepInsts,
2898 SmallPtrSet<const BasicBlock *, 4> &Visited,
2899 ProvenanceAnalysis &PA) {
2900 FindDependencies(CanChangeRetainCount, Arg, Retain->getParent(), Retain,
2901 DepInsts, Visited, PA);
2902 if (DepInsts.size() != 1)
2906 dyn_cast_or_null<CallInst>(*DepInsts.begin());
2908 // Check that the pointer is the return value of the call.
2909 if (!Call || Arg != Call)
2912 // Check that the call is a regular call.
2913 InstructionClass Class = GetBasicInstructionClass(Call);
2914 if (Class != IC_CallOrUser && Class != IC_Call)
2920 /// Find a dependent retain that precedes the given autorelease for which there
2921 /// is nothing in between the two instructions that can affect the ref count of
2924 FindPredecessorRetainWithSafePath(const Value *Arg, BasicBlock *BB,
2925 Instruction *Autorelease,
2926 SmallPtrSet<Instruction *, 4> &DepInsts,
2927 SmallPtrSet<const BasicBlock *, 4> &Visited,
2928 ProvenanceAnalysis &PA) {
2929 FindDependencies(CanChangeRetainCount, Arg,
2930 BB, Autorelease, DepInsts, Visited, PA);
2931 if (DepInsts.size() != 1)
2935 dyn_cast_or_null<CallInst>(*DepInsts.begin());
2937 // Check that we found a retain with the same argument.
2939 !IsRetain(GetBasicInstructionClass(Retain)) ||
2940 GetObjCArg(Retain) != Arg) {
2947 /// Look for an ``autorelease'' instruction dependent on Arg such that there are
2948 /// no instructions dependent on Arg that need a positive ref count in between
2949 /// the autorelease and the ret.
2951 FindPredecessorAutoreleaseWithSafePath(const Value *Arg, BasicBlock *BB,
2953 SmallPtrSet<Instruction *, 4> &DepInsts,
2954 SmallPtrSet<const BasicBlock *, 4> &V,
2955 ProvenanceAnalysis &PA) {
2956 FindDependencies(NeedsPositiveRetainCount, Arg,
2957 BB, Ret, DepInsts, V, PA);
2958 if (DepInsts.size() != 1)
2961 CallInst *Autorelease =
2962 dyn_cast_or_null<CallInst>(*DepInsts.begin());
2965 InstructionClass AutoreleaseClass = GetBasicInstructionClass(Autorelease);
2966 if (!IsAutorelease(AutoreleaseClass))
2968 if (GetObjCArg(Autorelease) != Arg)
2974 /// Look for this pattern:
2976 /// %call = call i8* @something(...)
2977 /// %2 = call i8* @objc_retain(i8* %call)
2978 /// %3 = call i8* @objc_autorelease(i8* %2)
2981 /// And delete the retain and autorelease.
2982 void ObjCARCOpt::OptimizeReturns(Function &F) {
2983 if (!F.getReturnType()->isPointerTy())
2986 DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeReturns ==\n");
2988 SmallPtrSet<Instruction *, 4> DependingInstructions;
2989 SmallPtrSet<const BasicBlock *, 4> Visited;
2990 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
2991 BasicBlock *BB = FI;
2992 ReturnInst *Ret = dyn_cast<ReturnInst>(&BB->back());
2994 DEBUG(dbgs() << "Visiting: " << *Ret << "\n");
2999 const Value *Arg = StripPointerCastsAndObjCCalls(Ret->getOperand(0));
3001 // Look for an ``autorelease'' instruction that is a predecessor of Ret and
3002 // dependent on Arg such that there are no instructions dependent on Arg
3003 // that need a positive ref count in between the autorelease and Ret.
3004 CallInst *Autorelease =
3005 FindPredecessorAutoreleaseWithSafePath(Arg, BB, Ret,
3006 DependingInstructions, Visited,
3008 DependingInstructions.clear();
3015 FindPredecessorRetainWithSafePath(Arg, BB, Autorelease,
3016 DependingInstructions, Visited, PA);
3017 DependingInstructions.clear();
3023 // Check that there is nothing that can affect the reference count
3024 // between the retain and the call. Note that Retain need not be in BB.
3025 bool HasSafePathToCall = HasSafePathToPredecessorCall(Arg, Retain,
3026 DependingInstructions,
3028 DependingInstructions.clear();
3031 if (!HasSafePathToCall)
3034 // If so, we can zap the retain and autorelease.
3037 DEBUG(dbgs() << "Erasing: " << *Retain << "\nErasing: "
3038 << *Autorelease << "\n");
3039 EraseInstruction(Retain);
3040 EraseInstruction(Autorelease);
3044 bool ObjCARCOpt::doInitialization(Module &M) {
3048 // If nothing in the Module uses ARC, don't do anything.
3049 Run = ModuleHasARC(M);
3053 // Identify the imprecise release metadata kind.
3054 ImpreciseReleaseMDKind =
3055 M.getContext().getMDKindID("clang.imprecise_release");
3056 CopyOnEscapeMDKind =
3057 M.getContext().getMDKindID("clang.arc.copy_on_escape");
3058 NoObjCARCExceptionsMDKind =
3059 M.getContext().getMDKindID("clang.arc.no_objc_arc_exceptions");
3060 #ifdef ARC_ANNOTATIONS
3061 ARCAnnotationBottomUpMDKind =
3062 M.getContext().getMDKindID("llvm.arc.annotation.bottomup");
3063 ARCAnnotationTopDownMDKind =
3064 M.getContext().getMDKindID("llvm.arc.annotation.topdown");
3065 ARCAnnotationProvenanceSourceMDKind =
3066 M.getContext().getMDKindID("llvm.arc.annotation.provenancesource");
3067 #endif // ARC_ANNOTATIONS
3069 // Intuitively, objc_retain and others are nocapture, however in practice
3070 // they are not, because they return their argument value. And objc_release
3071 // calls finalizers which can have arbitrary side effects.
3073 // These are initialized lazily.
3075 AutoreleaseRVCallee = 0;
3078 RetainBlockCallee = 0;
3079 AutoreleaseCallee = 0;
3084 bool ObjCARCOpt::runOnFunction(Function &F) {
3088 // If nothing in the Module uses ARC, don't do anything.
3094 DEBUG(dbgs() << "<<< ObjCARCOpt: Visiting Function: " << F.getName() << " >>>"
3097 PA.setAA(&getAnalysis<AliasAnalysis>());
3099 // This pass performs several distinct transformations. As a compile-time aid
3100 // when compiling code that isn't ObjC, skip these if the relevant ObjC
3101 // library functions aren't declared.
3103 // Preliminary optimizations. This also computes UsedInThisFunction.
3104 OptimizeIndividualCalls(F);
3106 // Optimizations for weak pointers.
3107 if (UsedInThisFunction & ((1 << IC_LoadWeak) |
3108 (1 << IC_LoadWeakRetained) |
3109 (1 << IC_StoreWeak) |
3110 (1 << IC_InitWeak) |
3111 (1 << IC_CopyWeak) |
3112 (1 << IC_MoveWeak) |
3113 (1 << IC_DestroyWeak)))
3114 OptimizeWeakCalls(F);
3116 // Optimizations for retain+release pairs.
3117 if (UsedInThisFunction & ((1 << IC_Retain) |
3118 (1 << IC_RetainRV) |
3119 (1 << IC_RetainBlock)))
3120 if (UsedInThisFunction & (1 << IC_Release))
3121 // Run OptimizeSequences until it either stops making changes or
3122 // no retain+release pair nesting is detected.
3123 while (OptimizeSequences(F)) {}
3125 // Optimizations if objc_autorelease is used.
3126 if (UsedInThisFunction & ((1 << IC_Autorelease) |
3127 (1 << IC_AutoreleaseRV)))
3130 DEBUG(dbgs() << "\n");
3132 ImpreciseAutoreleaseSet.clear();
3137 void ObjCARCOpt::releaseMemory() {
3139 ImpreciseAutoreleaseSet.clear();