X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FObjCARC%2FObjCARCOpts.cpp;h=48fe7c1440395f3fd4dec3c27b062f104a82c9ec;hb=722b0a4d293b16eebaed94ae65d5f11743cbcea5;hp=e6cd1a7ca9c8c8253c0f285148529421219a77c1;hpb=da6bf1d8bbf8e787f7c0edffbad40531dd520446;p=oota-llvm.git diff --git a/lib/Transforms/ObjCARC/ObjCARCOpts.cpp b/lib/Transforms/ObjCARC/ObjCARCOpts.cpp index e6cd1a7ca9c..48fe7c14403 100644 --- a/lib/Transforms/ObjCARC/ObjCARCOpts.cpp +++ b/lib/Transforms/ObjCARC/ObjCARCOpts.cpp @@ -13,11 +13,7 @@ /// /// The optimizations performed include elimination of redundant, partially /// redundant, and inconsequential reference count operations, elimination of -/// redundant weak pointer operations, pattern-matching and replacement of -/// low-level operations into higher-level operations, and numerous minor -/// simplifications. -/// -/// This file also defines a simple ARC-aware AliasAnalysis. +/// redundant weak pointer operations, and numerous minor simplifications. /// /// WARNING: This file knows about certain library functions. It recognizes them /// by name, and hardwires knowledge of their semantics. @@ -34,9 +30,11 @@ #include "ObjCARCAliasAnalysis.h" #include "ProvenanceAnalysis.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" +#include "llvm/IR/IRBuilder.h" #include "llvm/IR/LLVMContext.h" #include "llvm/Support/CFG.h" #include "llvm/Support/Debug.h" @@ -110,6 +108,12 @@ namespace { return std::make_pair(Vector.begin() + Pair.first->second, false); } + iterator find(const KeyT &Key) { + typename MapTy::iterator It = Map.find(Key); + if (It == Map.end()) return Vector.end(); + return Vector.begin() + It->second; + } + const_iterator find(const KeyT &Key) const { typename MapTy::const_iterator It = Map.find(Key); if (It == Map.end()) return Vector.end(); @@ -194,13 +198,13 @@ static bool DoesRetainableObjPtrEscape(const User *Ptr) { do { const Value *V = Worklist.pop_back_val(); - DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Visiting: " << *V << "\n"); + DEBUG(dbgs() << "Visiting: " << *V << "\n"); for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE; ++UI) { const User *UUser = *UI; - DEBUG(dbgs() << "DoesRetainableObjPtrEscape: User: " << *UUser << "\n"); + DEBUG(dbgs() << "User: " << *UUser << "\n"); // Special - Use by a call (callee or argument) is not considered // to be an escape. @@ -210,11 +214,13 @@ static bool DoesRetainableObjPtrEscape(const User *Ptr) { case IC_StoreStrong: case IC_Autorelease: case IC_AutoreleaseRV: { - DEBUG(dbgs() << "DoesRetainableObjPtrEscape: User copies pointer " - "arguments. Pointer Escapes!\n"); + DEBUG(dbgs() << "User copies pointer arguments. Pointer Escapes!\n"); // These special functions make copies of their pointer arguments. return true; } + case IC_IntrinsicUser: + // Use by the use intrinsic is not an escape. + continue; case IC_User: case IC_None: // Use by an instruction which copies the value is an escape if the @@ -222,13 +228,12 @@ static bool DoesRetainableObjPtrEscape(const User *Ptr) { if (isa(UUser) || isa(UUser) || isa(UUser) || isa(UUser)) { - if (!VisitedSet.insert(UUser)) { - DEBUG(dbgs() << "DoesRetainableObjPtrEscape: User copies value. " - "Ptr escapes if result escapes. Adding to list.\n"); + if (VisitedSet.insert(UUser)) { + DEBUG(dbgs() << "User copies value. Ptr escapes if result escapes." + " Adding to list.\n"); Worklist.push_back(UUser); } else { - DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Already visited node." - "\n"); + DEBUG(dbgs() << "Already visited node.\n"); } continue; } @@ -245,16 +250,50 @@ static bool DoesRetainableObjPtrEscape(const User *Ptr) { continue; } // Otherwise, conservatively assume an escape. - DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Assuming ptr escapes.\n"); + DEBUG(dbgs() << "Assuming ptr escapes.\n"); return true; } } while (!Worklist.empty()); // No escapes found. - DEBUG(dbgs() << "DoesRetainableObjPtrEscape: Ptr does not escape.\n"); + DEBUG(dbgs() << "Ptr does not escape.\n"); + return false; +} + +/// This is a wrapper around getUnderlyingObjCPtr along the lines of +/// GetUnderlyingObjects except that it returns early when it sees the first +/// alloca. +static inline bool AreAnyUnderlyingObjectsAnAlloca(const Value *V) { + SmallPtrSet Visited; + SmallVector Worklist; + Worklist.push_back(V); + do { + const Value *P = Worklist.pop_back_val(); + P = GetUnderlyingObjCPtr(P); + + if (isa(P)) + return true; + + if (!Visited.insert(P)) + continue; + + if (const SelectInst *SI = dyn_cast(P)) { + Worklist.push_back(SI->getTrueValue()); + Worklist.push_back(SI->getFalseValue()); + continue; + } + + if (const PHINode *PN = dyn_cast(P)) { + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) + Worklist.push_back(PN->getIncomingValue(i)); + continue; + } + } while (!Worklist.empty()); + return false; } + /// @} /// /// \defgroup ARCOpt ARC Optimization. @@ -302,9 +341,19 @@ STATISTIC(NumNoops, "Number of no-op objc calls eliminated"); STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated"); STATISTIC(NumAutoreleases,"Number of autoreleases converted to releases"); STATISTIC(NumRets, "Number of return value forwarding " - "retain+autoreleaes eliminated"); + "retain+autoreleases eliminated"); STATISTIC(NumRRs, "Number of retain+release paths eliminated"); STATISTIC(NumPeeps, "Number of calls peephole-optimized"); +#ifndef NDEBUG +STATISTIC(NumRetainsBeforeOpt, + "Number of retains before optimization"); +STATISTIC(NumReleasesBeforeOpt, + "Number of releases before optimization"); +STATISTIC(NumRetainsAfterOpt, + "Number of retains after optimization"); +STATISTIC(NumReleasesAfterOpt, + "Number of releases after optimization"); +#endif namespace { /// \enum Sequence @@ -375,7 +424,7 @@ static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) { namespace { /// \brief Unidirectional information about either a /// retain-decrement-use-release sequence or release-use-decrement-retain - /// reverese sequence. + /// reverse sequence. struct RRInfo { /// After an objc_retain, the reference count of the referenced /// object is known to be positive. Similarly, before an objc_release, the @@ -391,10 +440,6 @@ namespace { /// KnownSafe is true when either of these conditions is satisfied. bool KnownSafe; - /// True if the Calls are objc_retainBlock calls (as opposed to objc_retain - /// calls). - bool IsRetainBlock; - /// True of the objc_release calls are all marked with the "tail" keyword. bool IsTailCallRelease; @@ -410,22 +455,53 @@ namespace { /// sequence. SmallPtrSet ReverseInsertPts; + /// If this is true, we cannot perform code motion but can still remove + /// retain/release pairs. + bool CFGHazardAfflicted; + RRInfo() : - KnownSafe(false), IsRetainBlock(false), - IsTailCallRelease(false), - ReleaseMetadata(0) {} + KnownSafe(false), IsTailCallRelease(false), ReleaseMetadata(0), + CFGHazardAfflicted(false) {} void clear(); + + /// Conservatively merge the two RRInfo. Returns true if a partial merge has + /// occured, false otherwise. + bool Merge(const RRInfo &Other); + }; } void RRInfo::clear() { KnownSafe = false; - IsRetainBlock = false; IsTailCallRelease = false; ReleaseMetadata = 0; Calls.clear(); ReverseInsertPts.clear(); + CFGHazardAfflicted = false; +} + +bool RRInfo::Merge(const RRInfo &Other) { + // Conservatively merge the ReleaseMetadata information. + if (ReleaseMetadata != Other.ReleaseMetadata) + ReleaseMetadata = 0; + + // Conservatively merge the boolean state. + KnownSafe &= Other.KnownSafe; + IsTailCallRelease &= Other.IsTailCallRelease; + CFGHazardAfflicted |= Other.CFGHazardAfflicted; + + // Merge the call sets. + Calls.insert(Other.Calls.begin(), Other.Calls.end()); + + // Merge the insert point sets. If there are any differences, + // that makes this a partial merge. + bool Partial = ReverseInsertPts.size() != Other.ReverseInsertPts.size(); + for (SmallPtrSet::const_iterator + I = Other.ReverseInsertPts.begin(), + E = Other.ReverseInsertPts.end(); I != E; ++I) + Partial |= ReverseInsertPts.insert(*I); + return Partial; } namespace { @@ -435,35 +511,73 @@ namespace { /// True if the reference count is known to be incremented. bool KnownPositiveRefCount; - /// True of we've seen an opportunity for partial RR elimination, such as + /// True if we've seen an opportunity for partial RR elimination, such as /// pushing calls into a CFG triangle or into one side of a CFG diamond. bool Partial; /// The current position in the sequence. Sequence Seq : 8; - public: /// Unidirectional information about the current sequence. - /// - /// TODO: Encapsulate this better. RRInfo RRI; + public: PtrState() : KnownPositiveRefCount(false), Partial(false), Seq(S_None) {} + + bool IsKnownSafe() const { + return RRI.KnownSafe; + } + + void SetKnownSafe(const bool NewValue) { + RRI.KnownSafe = NewValue; + } + + bool IsTailCallRelease() const { + return RRI.IsTailCallRelease; + } + + void SetTailCallRelease(const bool NewValue) { + RRI.IsTailCallRelease = NewValue; + } + + bool IsTrackingImpreciseReleases() const { + return RRI.ReleaseMetadata != 0; + } + + const MDNode *GetReleaseMetadata() const { + return RRI.ReleaseMetadata; + } + + void SetReleaseMetadata(MDNode *NewValue) { + RRI.ReleaseMetadata = NewValue; + } + + bool IsCFGHazardAfflicted() const { + return RRI.CFGHazardAfflicted; + } + + void SetCFGHazardAfflicted(const bool NewValue) { + RRI.CFGHazardAfflicted = NewValue; + } + void SetKnownPositiveRefCount() { + DEBUG(dbgs() << "Setting Known Positive.\n"); KnownPositiveRefCount = true; } - void ClearRefCount() { + void ClearKnownPositiveRefCount() { + DEBUG(dbgs() << "Clearing Known Positive.\n"); KnownPositiveRefCount = false; } - bool IsKnownIncremented() const { + bool HasKnownPositiveRefCount() const { return KnownPositiveRefCount; } void SetSeq(Sequence NewSeq) { + DEBUG(dbgs() << "Old: " << Seq << "; New: " << NewSeq << "\n"); Seq = NewSeq; } @@ -476,23 +590,40 @@ namespace { } void ResetSequenceProgress(Sequence NewSeq) { - Seq = NewSeq; + DEBUG(dbgs() << "Resetting sequence progress.\n"); + SetSeq(NewSeq); Partial = false; RRI.clear(); } void Merge(const PtrState &Other, bool TopDown); + + void InsertCall(Instruction *I) { + RRI.Calls.insert(I); + } + + void InsertReverseInsertPt(Instruction *I) { + RRI.ReverseInsertPts.insert(I); + } + + void ClearReverseInsertPts() { + RRI.ReverseInsertPts.clear(); + } + + bool HasReverseInsertPts() const { + return !RRI.ReverseInsertPts.empty(); + } + + const RRInfo &GetRRInfo() const { + return RRI; + } }; } void PtrState::Merge(const PtrState &Other, bool TopDown) { Seq = MergeSeqs(Seq, Other.Seq, TopDown); - KnownPositiveRefCount = KnownPositiveRefCount && Other.KnownPositiveRefCount; - - // We can't merge a plain objc_retain with an objc_retainBlock. - if (RRI.IsRetainBlock != Other.RRI.IsRetainBlock) - Seq = S_None; + KnownPositiveRefCount &= Other.KnownPositiveRefCount; // If we're not in a sequence (anymore), drop all associated state. if (Seq == S_None) { @@ -505,22 +636,11 @@ PtrState::Merge(const PtrState &Other, bool TopDown) { // mixing them is unsafe. ClearSequenceProgress(); } else { - // Conservatively merge the ReleaseMetadata information. - if (RRI.ReleaseMetadata != Other.RRI.ReleaseMetadata) - RRI.ReleaseMetadata = 0; - - RRI.KnownSafe = RRI.KnownSafe && Other.RRI.KnownSafe; - RRI.IsTailCallRelease = RRI.IsTailCallRelease && - Other.RRI.IsTailCallRelease; - RRI.Calls.insert(Other.RRI.Calls.begin(), Other.RRI.Calls.end()); - - // Merge the insert point sets. If there are any differences, - // that makes this a partial merge. - Partial = RRI.ReverseInsertPts.size() != Other.RRI.ReverseInsertPts.size(); - for (SmallPtrSet::const_iterator - I = Other.RRI.ReverseInsertPts.begin(), - E = Other.RRI.ReverseInsertPts.end(); I != E; ++I) - Partial |= RRI.ReverseInsertPts.insert(*I); + // Otherwise merge the other PtrState's RRInfo into our RRInfo. At this + // point, we know that currently we are not partial. Stash whether or not + // the merge operation caused us to undergo a partial merging of reverse + // insertion points. + Partial = RRI.Merge(Other.RRI); } } @@ -584,14 +704,26 @@ namespace { /// definition. void SetAsExit() { BottomUpPathCount = 1; } + /// Attempt to find the PtrState object describing the top down state for + /// pointer Arg. Return a new initialized PtrState describing the top down + /// state for Arg if we do not find one. PtrState &getPtrTopDownState(const Value *Arg) { return PerPtrTopDown[Arg]; } + /// Attempt to find the PtrState object describing the bottom up state for + /// pointer Arg. Return a new initialized PtrState describing the bottom up + /// state for Arg if we do not find one. PtrState &getPtrBottomUpState(const Value *Arg) { return PerPtrBottomUp[Arg]; } + /// Attempt to find the PtrState object describing the bottom up state for + /// pointer Arg. + ptr_iterator findPtrBottomUpState(const Value *Arg) { + return PerPtrBottomUp.find(Arg); + } + void clearBottomUpPointers() { PerPtrBottomUp.clear(); } @@ -605,13 +737,20 @@ namespace { void MergePred(const BBState &Other); void MergeSucc(const BBState &Other); - /// Return the number of possible unique paths from an entry to an exit + /// Compute the number of possible unique paths from an entry to an exit /// which pass through this block. This is only valid after both the /// top-down and bottom-up traversals are complete. - unsigned GetAllPathCount() const { + /// + /// Returns true if overflow occured. Returns false if overflow did not + /// occur. + bool GetAllPathCountWithOverflow(unsigned &PathCount) const { assert(TopDownPathCount != 0); assert(BottomUpPathCount != 0); - return TopDownPathCount * BottomUpPathCount; + unsigned long long Product = + (unsigned long long)TopDownPathCount*BottomUpPathCount; + PathCount = Product; + // Overflow occured if any of the upper bits of Product are set. + return Product >> 32; } // Specialized CFG utilities. @@ -702,12 +841,296 @@ void BBState::MergeSucc(const BBState &Other) { MI->second.Merge(PtrState(), /*TopDown=*/false); } +// Only enable ARC Annotations if we are building a debug version of +// libObjCARCOpts. +#ifndef NDEBUG +#define ARC_ANNOTATIONS +#endif + +// Define some macros along the lines of DEBUG and some helper functions to make +// it cleaner to create annotations in the source code and to no-op when not +// building in debug mode. +#ifdef ARC_ANNOTATIONS + +#include "llvm/Support/CommandLine.h" + +/// Enable/disable ARC sequence annotations. +static cl::opt +EnableARCAnnotations("enable-objc-arc-annotations", cl::init(false), + cl::desc("Enable emission of arc data flow analysis " + "annotations")); +static cl::opt +DisableCheckForCFGHazards("disable-objc-arc-checkforcfghazards", cl::init(false), + cl::desc("Disable check for cfg hazards when " + "annotating")); +static cl::opt +ARCAnnotationTargetIdentifier("objc-arc-annotation-target-identifier", + cl::init(""), + cl::desc("filter out all data flow annotations " + "but those that apply to the given " + "target llvm identifier.")); + +/// This function appends a unique ARCAnnotationProvenanceSourceMDKind id to an +/// instruction so that we can track backwards when post processing via the llvm +/// arc annotation processor tool. If the function is an +static MDString *AppendMDNodeToSourcePtr(unsigned NodeId, + Value *Ptr) { + MDString *Hash = 0; + + // If pointer is a result of an instruction and it does not have a source + // MDNode it, attach a new MDNode onto it. If pointer is a result of + // an instruction and does have a source MDNode attached to it, return a + // reference to said Node. Otherwise just return 0. + if (Instruction *Inst = dyn_cast(Ptr)) { + MDNode *Node; + if (!(Node = Inst->getMetadata(NodeId))) { + // We do not have any node. Generate and attatch the hash MDString to the + // instruction. + + // We just use an MDString to ensure that this metadata gets written out + // of line at the module level and to provide a very simple format + // encoding the information herein. Both of these makes it simpler to + // parse the annotations by a simple external program. + std::string Str; + raw_string_ostream os(Str); + os << "(" << Inst->getParent()->getParent()->getName() << ",%" + << Inst->getName() << ")"; + + Hash = MDString::get(Inst->getContext(), os.str()); + Inst->setMetadata(NodeId, MDNode::get(Inst->getContext(),Hash)); + } else { + // We have a node. Grab its hash and return it. + assert(Node->getNumOperands() == 1 && + "An ARCAnnotationProvenanceSourceMDKind can only have 1 operand."); + Hash = cast(Node->getOperand(0)); + } + } else if (Argument *Arg = dyn_cast(Ptr)) { + std::string str; + raw_string_ostream os(str); + os << "(" << Arg->getParent()->getName() << ",%" << Arg->getName() + << ")"; + Hash = MDString::get(Arg->getContext(), os.str()); + } + + return Hash; +} + +static std::string SequenceToString(Sequence A) { + std::string str; + raw_string_ostream os(str); + os << A; + return os.str(); +} + +/// Helper function to change a Sequence into a String object using our overload +/// for raw_ostream so we only have printing code in one location. +static MDString *SequenceToMDString(LLVMContext &Context, + Sequence A) { + return MDString::get(Context, SequenceToString(A)); +} + +/// A simple function to generate a MDNode which describes the change in state +/// for Value *Ptr caused by Instruction *Inst. +static void AppendMDNodeToInstForPtr(unsigned NodeId, + Instruction *Inst, + Value *Ptr, + MDString *PtrSourceMDNodeID, + Sequence OldSeq, + Sequence NewSeq) { + MDNode *Node = 0; + Value *tmp[3] = {PtrSourceMDNodeID, + SequenceToMDString(Inst->getContext(), + OldSeq), + SequenceToMDString(Inst->getContext(), + NewSeq)}; + Node = MDNode::get(Inst->getContext(), + ArrayRef(tmp, 3)); + + Inst->setMetadata(NodeId, Node); +} + +/// Add to the beginning of the basic block llvm.ptr.annotations which show the +/// state of a pointer at the entrance to a basic block. +static void GenerateARCBBEntranceAnnotation(const char *Name, BasicBlock *BB, + Value *Ptr, Sequence Seq) { + // If we have a target identifier, make sure that we match it before + // continuing. + if(!ARCAnnotationTargetIdentifier.empty() && + !Ptr->getName().equals(ARCAnnotationTargetIdentifier)) + return; + + Module *M = BB->getParent()->getParent(); + LLVMContext &C = M->getContext(); + Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); + Type *I8XX = PointerType::getUnqual(I8X); + Type *Params[] = {I8XX, I8XX}; + FunctionType *FTy = FunctionType::get(Type::getVoidTy(C), + ArrayRef(Params, 2), + /*isVarArg=*/false); + Constant *Callee = M->getOrInsertFunction(Name, FTy); + + IRBuilder<> Builder(BB, BB->getFirstInsertionPt()); + + Value *PtrName; + StringRef Tmp = Ptr->getName(); + if (0 == (PtrName = M->getGlobalVariable(Tmp, true))) { + Value *ActualPtrName = Builder.CreateGlobalStringPtr(Tmp, + Tmp + "_STR"); + PtrName = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage, + cast(ActualPtrName), Tmp); + } + + Value *S; + std::string SeqStr = SequenceToString(Seq); + if (0 == (S = M->getGlobalVariable(SeqStr, true))) { + Value *ActualPtrName = Builder.CreateGlobalStringPtr(SeqStr, + SeqStr + "_STR"); + S = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage, + cast(ActualPtrName), SeqStr); + } + + Builder.CreateCall2(Callee, PtrName, S); +} + +/// Add to the end of the basic block llvm.ptr.annotations which show the state +/// of the pointer at the bottom of the basic block. +static void GenerateARCBBTerminatorAnnotation(const char *Name, BasicBlock *BB, + Value *Ptr, Sequence Seq) { + // If we have a target identifier, make sure that we match it before emitting + // an annotation. + if(!ARCAnnotationTargetIdentifier.empty() && + !Ptr->getName().equals(ARCAnnotationTargetIdentifier)) + return; + + Module *M = BB->getParent()->getParent(); + LLVMContext &C = M->getContext(); + Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); + Type *I8XX = PointerType::getUnqual(I8X); + Type *Params[] = {I8XX, I8XX}; + FunctionType *FTy = FunctionType::get(Type::getVoidTy(C), + ArrayRef(Params, 2), + /*isVarArg=*/false); + Constant *Callee = M->getOrInsertFunction(Name, FTy); + + IRBuilder<> Builder(BB, llvm::prior(BB->end())); + + Value *PtrName; + StringRef Tmp = Ptr->getName(); + if (0 == (PtrName = M->getGlobalVariable(Tmp, true))) { + Value *ActualPtrName = Builder.CreateGlobalStringPtr(Tmp, + Tmp + "_STR"); + PtrName = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage, + cast(ActualPtrName), Tmp); + } + + Value *S; + std::string SeqStr = SequenceToString(Seq); + if (0 == (S = M->getGlobalVariable(SeqStr, true))) { + Value *ActualPtrName = Builder.CreateGlobalStringPtr(SeqStr, + SeqStr + "_STR"); + S = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage, + cast(ActualPtrName), SeqStr); + } + Builder.CreateCall2(Callee, PtrName, S); +} + +/// Adds a source annotation to pointer and a state change annotation to Inst +/// referencing the source annotation and the old/new state of pointer. +static void GenerateARCAnnotation(unsigned InstMDId, + unsigned PtrMDId, + Instruction *Inst, + Value *Ptr, + Sequence OldSeq, + Sequence NewSeq) { + if (EnableARCAnnotations) { + // If we have a target identifier, make sure that we match it before + // emitting an annotation. + if(!ARCAnnotationTargetIdentifier.empty() && + !Ptr->getName().equals(ARCAnnotationTargetIdentifier)) + return; + + // First generate the source annotation on our pointer. This will return an + // MDString* if Ptr actually comes from an instruction implying we can put + // in a source annotation. If AppendMDNodeToSourcePtr returns 0 (i.e. NULL), + // then we know that our pointer is from an Argument so we put a reference + // to the argument number. + // + // The point of this is to make it easy for the + // llvm-arc-annotation-processor tool to cross reference where the source + // pointer is in the LLVM IR since the LLVM IR parser does not submit such + // information via debug info for backends to use (since why would anyone + // need such a thing from LLVM IR besides in non standard cases + // [i.e. this]). + MDString *SourcePtrMDNode = + AppendMDNodeToSourcePtr(PtrMDId, Ptr); + AppendMDNodeToInstForPtr(InstMDId, Inst, Ptr, SourcePtrMDNode, OldSeq, + NewSeq); + } +} + +// The actual interface for accessing the above functionality is defined via +// some simple macros which are defined below. We do this so that the user does +// not need to pass in what metadata id is needed resulting in cleaner code and +// additionally since it provides an easy way to conditionally no-op all +// annotation support in a non-debug build. + +/// Use this macro to annotate a sequence state change when processing +/// instructions bottom up, +#define ANNOTATE_BOTTOMUP(inst, ptr, old, new) \ + GenerateARCAnnotation(ARCAnnotationBottomUpMDKind, \ + ARCAnnotationProvenanceSourceMDKind, (inst), \ + const_cast(ptr), (old), (new)) +/// Use this macro to annotate a sequence state change when processing +/// instructions top down. +#define ANNOTATE_TOPDOWN(inst, ptr, old, new) \ + GenerateARCAnnotation(ARCAnnotationTopDownMDKind, \ + ARCAnnotationProvenanceSourceMDKind, (inst), \ + const_cast(ptr), (old), (new)) + +#define ANNOTATE_BB(_states, _bb, _name, _type, _direction) \ + do { \ + if (EnableARCAnnotations) { \ + for(BBState::ptr_const_iterator I = (_states)._direction##_ptr_begin(), \ + E = (_states)._direction##_ptr_end(); I != E; ++I) { \ + Value *Ptr = const_cast(I->first); \ + Sequence Seq = I->second.GetSeq(); \ + GenerateARCBB ## _type ## Annotation(_name, (_bb), Ptr, Seq); \ + } \ + } \ + } while (0) + +#define ANNOTATE_BOTTOMUP_BBSTART(_states, _basicblock) \ + ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.bottomup.bbstart", \ + Entrance, bottom_up) +#define ANNOTATE_BOTTOMUP_BBEND(_states, _basicblock) \ + ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.bottomup.bbend", \ + Terminator, bottom_up) +#define ANNOTATE_TOPDOWN_BBSTART(_states, _basicblock) \ + ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.topdown.bbstart", \ + Entrance, top_down) +#define ANNOTATE_TOPDOWN_BBEND(_states, _basicblock) \ + ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.topdown.bbend", \ + Terminator, top_down) + +#else // !ARC_ANNOTATION +// If annotations are off, noop. +#define ANNOTATE_BOTTOMUP(inst, ptr, old, new) +#define ANNOTATE_TOPDOWN(inst, ptr, old, new) +#define ANNOTATE_BOTTOMUP_BBSTART(states, basicblock) +#define ANNOTATE_BOTTOMUP_BBEND(states, basicblock) +#define ANNOTATE_TOPDOWN_BBSTART(states, basicblock) +#define ANNOTATE_TOPDOWN_BBEND(states, basicblock) +#endif // !ARC_ANNOTATION + namespace { /// \brief The main ARC optimization pass. class ObjCARCOpt : public FunctionPass { bool Changed; ProvenanceAnalysis PA; + // This is used to track if a pointer is stored into an alloca. + DenseSet MultiOwnersSet; + /// A flag indicating whether this optimization pass should run. bool Run; @@ -715,9 +1138,6 @@ namespace { /// them. These are initialized lazily to avoid cluttering up the Module /// with unused declarations. - /// Declaration for ObjC runtime function - /// objc_retainAutoreleasedReturnValue. - Constant *RetainRVCallee; /// Declaration for ObjC runtime function objc_autoreleaseReturnValue. Constant *AutoreleaseRVCallee; /// Declaration for ObjC runtime function objc_release. @@ -742,7 +1162,15 @@ namespace { /// The Metadata Kind for clang.arc.no_objc_arc_exceptions metadata. unsigned NoObjCARCExceptionsMDKind; - Constant *getRetainRVCallee(Module *M); +#ifdef ARC_ANNOTATIONS + /// The Metadata Kind for llvm.arc.annotation.bottomup metadata. + unsigned ARCAnnotationBottomUpMDKind; + /// The Metadata Kind for llvm.arc.annotation.topdown metadata. + unsigned ARCAnnotationTopDownMDKind; + /// The Metadata Kind for llvm.arc.annotation.provenancesource metadata. + unsigned ARCAnnotationProvenanceSourceMDKind; +#endif // ARC_ANNOATIONS + Constant *getAutoreleaseRVCallee(Module *M); Constant *getReleaseCallee(Module *M); Constant *getRetainCallee(Module *M); @@ -751,10 +1179,11 @@ namespace { bool IsRetainBlockOptimizable(const Instruction *Inst); - void OptimizeRetainCall(Function &F, Instruction *Retain); bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV); void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV, InstructionClass &Class); + bool OptimizeRetainBlockCall(Function &F, Instruction *RetainBlock, + InstructionClass &Class); void OptimizeIndividualCalls(Function &F); void CheckForCFGHazards(const BasicBlock *BB, @@ -808,6 +1237,10 @@ namespace { void OptimizeReturns(Function &F); +#ifndef NDEBUG + void GatherStatistics(Function &F, bool AfterOptimization = false); +#endif + virtual void getAnalysisUsage(AnalysisUsage &AU) const; virtual bool doInitialization(Module &M); virtual bool runOnFunction(Function &F); @@ -855,22 +1288,6 @@ bool ObjCARCOpt::IsRetainBlockOptimizable(const Instruction *Inst) { return true; } -Constant *ObjCARCOpt::getRetainRVCallee(Module *M) { - if (!RetainRVCallee) { - LLVMContext &C = M->getContext(); - Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); - Type *Params[] = { I8X }; - FunctionType *FTy = FunctionType::get(I8X, Params, /*isVarArg=*/false); - AttributeSet Attribute = - AttributeSet().addAttribute(M->getContext(), AttributeSet::FunctionIndex, - Attribute::NoUnwind); - RetainRVCallee = - M->getOrInsertFunction("objc_retainAutoreleasedReturnValue", FTy, - Attribute); - } - return RetainRVCallee; -} - Constant *ObjCARCOpt::getAutoreleaseRVCallee(Module *M) { if (!AutoreleaseRVCallee) { LLVMContext &C = M->getContext(); @@ -950,38 +1367,6 @@ Constant *ObjCARCOpt::getAutoreleaseCallee(Module *M) { return AutoreleaseCallee; } -/// Turn objc_retain into objc_retainAutoreleasedReturnValue if the operand is a -/// return value. -void -ObjCARCOpt::OptimizeRetainCall(Function &F, Instruction *Retain) { - ImmutableCallSite CS(GetObjCArg(Retain)); - const Instruction *Call = CS.getInstruction(); - if (!Call) return; - if (Call->getParent() != Retain->getParent()) return; - - // Check that the call is next to the retain. - BasicBlock::const_iterator I = Call; - ++I; - while (isNoopInstruction(I)) ++I; - if (&*I != Retain) - return; - - // Turn it to an objc_retainAutoreleasedReturnValue.. - Changed = true; - ++NumPeeps; - - DEBUG(dbgs() << "ObjCARCOpt::OptimizeRetainCall: Transforming " - "objc_retain => objc_retainAutoreleasedReturnValue" - " since the operand is a return value.\n" - " Old: " - << *Retain << "\n"); - - cast(Retain)->setCalledFunction(getRetainRVCallee(F.getParent())); - - DEBUG(dbgs() << " New: " - << *Retain << "\n"); -} - /// Turn objc_retainAutoreleasedReturnValue into objc_retain if the operand is /// not a return value. Or, if it can be paired with an /// objc_autoreleaseReturnValue, delete the pair and return true. @@ -994,14 +1379,14 @@ ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) { if (Call->getParent() == RetainRV->getParent()) { BasicBlock::const_iterator I = Call; ++I; - while (isNoopInstruction(I)) ++I; + while (IsNoopInstruction(I)) ++I; if (&*I == RetainRV) return false; } else if (const InvokeInst *II = dyn_cast(Call)) { BasicBlock *RetainRVParent = RetainRV->getParent(); if (II->getNormalDest() == RetainRVParent) { BasicBlock::const_iterator I = RetainRVParent->begin(); - while (isNoopInstruction(I)) ++I; + while (IsNoopInstruction(I)) ++I; if (&*I == RetainRV) return false; } @@ -1012,15 +1397,14 @@ ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) { // pointer. In this case, we can delete the pair. BasicBlock::iterator I = RetainRV, Begin = RetainRV->getParent()->begin(); if (I != Begin) { - do --I; while (I != Begin && isNoopInstruction(I)); + do --I; while (I != Begin && IsNoopInstruction(I)); if (GetBasicInstructionClass(I) == IC_AutoreleaseRV && GetObjCArg(I) == Arg) { Changed = true; ++NumPeeps; - DEBUG(dbgs() << "ObjCARCOpt::OptimizeRetainRVCall: Erasing " << *I << "\n" - << " Erasing " << *RetainRV - << "\n"); + DEBUG(dbgs() << "Erasing autoreleaseRV,retainRV pair: " << *I << "\n" + << "Erasing " << *RetainRV << "\n"); EraseInstruction(I); EraseInstruction(RetainRV); @@ -1032,16 +1416,13 @@ ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) { Changed = true; ++NumPeeps; - DEBUG(dbgs() << "ObjCARCOpt::OptimizeRetainRVCall: Transforming " - "objc_retainAutoreleasedReturnValue => " + DEBUG(dbgs() << "Transforming objc_retainAutoreleasedReturnValue => " "objc_retain since the operand is not a return value.\n" - " Old: " - << *RetainRV << "\n"); + "Old = " << *RetainRV << "\n"); cast(RetainRV)->setCalledFunction(getRetainCallee(F.getParent())); - DEBUG(dbgs() << " New: " - << *RetainRV << "\n"); + DEBUG(dbgs() << "New = " << *RetainRV << "\n"); return false; } @@ -1070,12 +1451,10 @@ ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV, Changed = true; ++NumPeeps; - DEBUG(dbgs() << "ObjCARCOpt::OptimizeAutoreleaseRVCall: Transforming " - "objc_autoreleaseReturnValue => " + DEBUG(dbgs() << "Transforming objc_autoreleaseReturnValue => " "objc_autorelease since its operand is not used as a return " "value.\n" - " Old: " - << *AutoreleaseRV << "\n"); + "Old = " << *AutoreleaseRV << "\n"); CallInst *AutoreleaseRVCI = cast(AutoreleaseRV); AutoreleaseRVCI-> @@ -1083,14 +1462,48 @@ ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV, AutoreleaseRVCI->setTailCall(false); // Never tail call objc_autorelease. Class = IC_Autorelease; - DEBUG(dbgs() << " New: " - << *AutoreleaseRV << "\n"); + DEBUG(dbgs() << "New: " << *AutoreleaseRV << "\n"); } +// \brief Attempt to strength reduce objc_retainBlock calls to objc_retain +// calls. +// +// Specifically: If an objc_retainBlock call has the copy_on_escape metadata and +// does not escape (following the rules of block escaping), strength reduce the +// objc_retainBlock to an objc_retain. +// +// TODO: If an objc_retainBlock call is dominated period by a previous +// objc_retainBlock call, strength reduce the objc_retainBlock to an +// objc_retain. +bool +ObjCARCOpt::OptimizeRetainBlockCall(Function &F, Instruction *Inst, + InstructionClass &Class) { + assert(GetBasicInstructionClass(Inst) == Class); + assert(IC_RetainBlock == Class); + + // If we can not optimize Inst, return false. + if (!IsRetainBlockOptimizable(Inst)) + return false; + + Changed = true; + ++NumPeeps; + + DEBUG(dbgs() << "Strength reduced retainBlock => retain.\n"); + DEBUG(dbgs() << "Old: " << *Inst << "\n"); + CallInst *RetainBlock = cast(Inst); + RetainBlock->setCalledFunction(getRetainCallee(F.getParent())); + // Remove copy_on_escape metadata. + RetainBlock->setMetadata(CopyOnEscapeMDKind, 0); + Class = IC_Retain; + DEBUG(dbgs() << "New: " << *Inst << "\n"); + return true; +} + /// Visit each call, one at a time, and make simplifications without doing any /// additional analysis. void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { + DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeIndividualCalls ==\n"); // Reset all the flags in preparation for recomputing them. UsedInThisFunction = 0; @@ -1100,8 +1513,7 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { InstructionClass Class = GetBasicInstructionClass(Inst); - DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Visiting: Class: " - << Class << "; " << *Inst << "\n"); + DEBUG(dbgs() << "Visiting: Class: " << Class << "; " << *Inst << "\n"); switch (Class) { default: break; @@ -1117,8 +1529,7 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { case IC_NoopCast: Changed = true; ++NumNoops; - DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Erasing no-op cast:" - " " << *Inst << "\n"); + DEBUG(dbgs() << "Erasing no-op cast: " << *Inst << "\n"); EraseInstruction(Inst); continue; @@ -1129,18 +1540,15 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { case IC_InitWeak: case IC_DestroyWeak: { CallInst *CI = cast(Inst); - if (isNullOrUndef(CI->getArgOperand(0))) { + if (IsNullOrUndef(CI->getArgOperand(0))) { Changed = true; Type *Ty = CI->getArgOperand(0)->getType(); new StoreInst(UndefValue::get(cast(Ty)->getElementType()), Constant::getNullValue(Ty), CI); llvm::Value *NewValue = UndefValue::get(CI->getType()); - DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: A null " - "pointer-to-weak-pointer is undefined behavior.\n" - " Old = " << *CI << - "\n New = " << - *NewValue << "\n"); + DEBUG(dbgs() << "A null pointer-to-weak-pointer is undefined behavior." + "\nOld = " << *CI << "\nNew = " << *NewValue << "\n"); CI->replaceAllUsesWith(NewValue); CI->eraseFromParent(); continue; @@ -1150,8 +1558,8 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { case IC_CopyWeak: case IC_MoveWeak: { CallInst *CI = cast(Inst); - if (isNullOrUndef(CI->getArgOperand(0)) || - isNullOrUndef(CI->getArgOperand(1))) { + if (IsNullOrUndef(CI->getArgOperand(0)) || + IsNullOrUndef(CI->getArgOperand(1))) { Changed = true; Type *Ty = CI->getArgOperand(0)->getType(); new StoreInst(UndefValue::get(cast(Ty)->getElementType()), @@ -1159,11 +1567,8 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { CI); llvm::Value *NewValue = UndefValue::get(CI->getType()); - DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: A null " - "pointer-to-weak-pointer is undefined behavior.\n" - " Old = " << *CI << - "\n New = " << - *NewValue << "\n"); + DEBUG(dbgs() << "A null pointer-to-weak-pointer is undefined behavior." + "\nOld = " << *CI << "\nNew = " << *NewValue << "\n"); CI->replaceAllUsesWith(NewValue); CI->eraseFromParent(); @@ -1171,8 +1576,10 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { } break; } - case IC_Retain: - OptimizeRetainCall(F, Inst); + case IC_RetainBlock: + // If we strength reduce an objc_retainBlock to an objc_retain, continue + // onto the objc_retain peephole optimizations. Otherwise break. + OptimizeRetainBlockCall(F, Inst, Class); break; case IC_RetainRV: if (OptimizeRetainRVCall(F, Inst)) @@ -1197,15 +1604,11 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { CallInst *NewCall = CallInst::Create(getReleaseCallee(F.getParent()), Call->getArgOperand(0), "", Call); - NewCall->setMetadata(ImpreciseReleaseMDKind, - MDNode::get(C, ArrayRef())); + NewCall->setMetadata(ImpreciseReleaseMDKind, MDNode::get(C, None)); - DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Replacing " - "objc_autorelease(x) with objc_release(x) since x is " - "otherwise unused.\n" - " Old: " << *Call << - "\n New: " << - *NewCall << "\n"); + DEBUG(dbgs() << "Replacing autorelease{,RV}(x) with objc_release(x) " + "since x is otherwise unused.\nOld: " << *Call << "\nNew: " + << *NewCall << "\n"); EraseInstruction(Call); Inst = NewCall; @@ -1217,9 +1620,8 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { // a tail keyword. if (IsAlwaysTail(Class)) { Changed = true; - DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Adding tail keyword" - " to function since it can never be passed stack args: " << *Inst << - "\n"); + DEBUG(dbgs() << "Adding tail keyword to function since it can never be " + "passed stack args: " << *Inst << "\n"); cast(Inst)->setTailCall(); } @@ -1227,8 +1629,7 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { // semantics of ARC truly do not do so. if (IsNeverTail(Class)) { Changed = true; - DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Removing tail " - "keyword from function: " << *Inst << + DEBUG(dbgs() << "Removing tail keyword from function: " << *Inst << "\n"); cast(Inst)->setTailCall(false); } @@ -1236,8 +1637,8 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { // Set nounwind as needed. if (IsNoThrow(Class)) { Changed = true; - DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Found no throw" - " class. Setting nounwind on: " << *Inst << "\n"); + DEBUG(dbgs() << "Found no throw class. Setting nounwind on: " << *Inst + << "\n"); cast(Inst)->setDoesNotThrow(); } @@ -1249,11 +1650,11 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { const Value *Arg = GetObjCArg(Inst); // ARC calls with null are no-ops. Delete them. - if (isNullOrUndef(Arg)) { + if (IsNullOrUndef(Arg)) { Changed = true; ++NumNoops; - DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: ARC calls with " - " null are no-ops. Erasing: " << *Inst << "\n"); + DEBUG(dbgs() << "ARC calls with null are no-ops. Erasing: " << *Inst + << "\n"); EraseInstruction(Inst); continue; } @@ -1284,7 +1685,7 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { Value *Incoming = StripPointerCastsAndObjCCalls(PN->getIncomingValue(i)); - if (isNullOrUndef(Incoming)) + if (IsNullOrUndef(Incoming)) HasNull = true; else if (cast(PN->getIncomingBlock(i)->back()) .getNumSuccessors() != 1) { @@ -1338,7 +1739,7 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { Value *Incoming = StripPointerCastsAndObjCCalls(PN->getIncomingValue(i)); - if (!isNullOrUndef(Incoming)) { + if (!IsNullOrUndef(Incoming)) { CallInst *Clone = cast(CInst->clone()); Value *Op = PN->getIncomingValue(i); Instruction *InsertPos = &PN->getIncomingBlock(i)->back(); @@ -1347,10 +1748,9 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { Clone->setArgOperand(0, Op); Clone->insertBefore(InsertPos); - DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Cloning " + DEBUG(dbgs() << "Cloning " << *CInst << "\n" - " And inserting " - "clone at " << *InsertPos << "\n"); + "And inserting clone at " << *InsertPos << "\n"); Worklist.push_back(std::make_pair(Clone, Incoming)); } } @@ -1362,7 +1762,72 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { } } while (!Worklist.empty()); } - DEBUG(dbgs() << "ObjCARCOpt::OptimizeIndividualCalls: Finished List.\n"); +} + +/// If we have a top down pointer in the S_Use state, make sure that there are +/// no CFG hazards by checking the states of various bottom up pointers. +static void CheckForUseCFGHazard(const Sequence SuccSSeq, + const bool SuccSRRIKnownSafe, + PtrState &S, + bool &SomeSuccHasSame, + bool &AllSuccsHaveSame, + bool &NotAllSeqEqualButKnownSafe, + bool &ShouldContinue) { + switch (SuccSSeq) { + case S_CanRelease: { + if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) { + S.ClearSequenceProgress(); + break; + } + S.SetCFGHazardAfflicted(true); + ShouldContinue = true; + break; + } + case S_Use: + SomeSuccHasSame = true; + break; + case S_Stop: + case S_Release: + case S_MovableRelease: + if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) + AllSuccsHaveSame = false; + else + NotAllSeqEqualButKnownSafe = true; + break; + case S_Retain: + llvm_unreachable("bottom-up pointer in retain state!"); + case S_None: + llvm_unreachable("This should have been handled earlier."); + } +} + +/// If we have a Top Down pointer in the S_CanRelease state, make sure that +/// there are no CFG hazards by checking the states of various bottom up +/// pointers. +static void CheckForCanReleaseCFGHazard(const Sequence SuccSSeq, + const bool SuccSRRIKnownSafe, + PtrState &S, + bool &SomeSuccHasSame, + bool &AllSuccsHaveSame, + bool &NotAllSeqEqualButKnownSafe) { + switch (SuccSSeq) { + case S_CanRelease: + SomeSuccHasSame = true; + break; + case S_Stop: + case S_Release: + case S_MovableRelease: + case S_Use: + if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) + AllSuccsHaveSame = false; + else + NotAllSeqEqualButKnownSafe = true; + break; + case S_Retain: + llvm_unreachable("bottom-up pointer in retain state!"); + case S_None: + llvm_unreachable("This should have been handled earlier."); + } } /// Check for critical edges, loop boundaries, irreducible control flow, or @@ -1375,106 +1840,90 @@ ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB, // If any top-down local-use or possible-dec has a succ which is earlier in // the sequence, forget it. for (BBState::ptr_iterator I = MyStates.top_down_ptr_begin(), - E = MyStates.top_down_ptr_end(); I != E; ++I) - switch (I->second.GetSeq()) { - default: break; - case S_Use: { - const Value *Arg = I->first; - const TerminatorInst *TI = cast(&BB->back()); - bool SomeSuccHasSame = false; - bool AllSuccsHaveSame = true; - PtrState &S = I->second; - succ_const_iterator SI(TI), SE(TI, false); - - for (; SI != SE; ++SI) { - Sequence SuccSSeq = S_None; - bool SuccSRRIKnownSafe = false; - // If VisitBottomUp has pointer information for this successor, take - // what we know about it. - DenseMap::iterator BBI = - BBStates.find(*SI); - assert(BBI != BBStates.end()); - const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg); - SuccSSeq = SuccS.GetSeq(); - SuccSRRIKnownSafe = SuccS.RRI.KnownSafe; - switch (SuccSSeq) { - case S_None: - case S_CanRelease: { - if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe) { - S.ClearSequenceProgress(); - break; - } - continue; - } - case S_Use: - SomeSuccHasSame = true; - break; - case S_Stop: - case S_Release: - case S_MovableRelease: - if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe) - AllSuccsHaveSame = false; - break; - case S_Retain: - llvm_unreachable("bottom-up pointer in retain state!"); - } - } - // If the state at the other end of any of the successor edges - // matches the current state, require all edges to match. This - // guards against loops in the middle of a sequence. - if (SomeSuccHasSame && !AllSuccsHaveSame) + E = MyStates.top_down_ptr_end(); I != E; ++I) { + PtrState &S = I->second; + const Sequence Seq = I->second.GetSeq(); + + // We only care about S_Retain, S_CanRelease, and S_Use. + if (Seq == S_None) + continue; + + // Make sure that if extra top down states are added in the future that this + // code is updated to handle it. + assert((Seq == S_Retain || Seq == S_CanRelease || Seq == S_Use) && + "Unknown top down sequence state."); + + const Value *Arg = I->first; + const TerminatorInst *TI = cast(&BB->back()); + bool SomeSuccHasSame = false; + bool AllSuccsHaveSame = true; + bool NotAllSeqEqualButKnownSafe = false; + + succ_const_iterator SI(TI), SE(TI, false); + + for (; SI != SE; ++SI) { + // If VisitBottomUp has pointer information for this successor, take + // what we know about it. + const DenseMap::iterator BBI = + BBStates.find(*SI); + assert(BBI != BBStates.end()); + const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg); + const Sequence SuccSSeq = SuccS.GetSeq(); + + // If bottom up, the pointer is in an S_None state, clear the sequence + // progress since the sequence in the bottom up state finished + // suggesting a mismatch in between retains/releases. This is true for + // all three cases that we are handling here: S_Retain, S_Use, and + // S_CanRelease. + if (SuccSSeq == S_None) { S.ClearSequenceProgress(); - break; - } - case S_CanRelease: { - const Value *Arg = I->first; - const TerminatorInst *TI = cast(&BB->back()); - bool SomeSuccHasSame = false; - bool AllSuccsHaveSame = true; - PtrState &S = I->second; - succ_const_iterator SI(TI), SE(TI, false); - - for (; SI != SE; ++SI) { - Sequence SuccSSeq = S_None; - bool SuccSRRIKnownSafe = false; - // If VisitBottomUp has pointer information for this successor, take - // what we know about it. - DenseMap::iterator BBI = - BBStates.find(*SI); - assert(BBI != BBStates.end()); - const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg); - SuccSSeq = SuccS.GetSeq(); - SuccSRRIKnownSafe = SuccS.RRI.KnownSafe; - switch (SuccSSeq) { - case S_None: { - if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe) { - S.ClearSequenceProgress(); - break; - } + continue; + } + + // If we have S_Use or S_CanRelease, perform our check for cfg hazard + // checks. + const bool SuccSRRIKnownSafe = SuccS.IsKnownSafe(); + + // *NOTE* We do not use Seq from above here since we are allowing for + // S.GetSeq() to change while we are visiting basic blocks. + switch(S.GetSeq()) { + case S_Use: { + bool ShouldContinue = false; + CheckForUseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S, SomeSuccHasSame, + AllSuccsHaveSame, NotAllSeqEqualButKnownSafe, + ShouldContinue); + if (ShouldContinue) continue; - } - case S_CanRelease: - SomeSuccHasSame = true; - break; - case S_Stop: - case S_Release: - case S_MovableRelease: - case S_Use: - if (!S.RRI.KnownSafe && !SuccSRRIKnownSafe) - AllSuccsHaveSame = false; - break; - case S_Retain: - llvm_unreachable("bottom-up pointer in retain state!"); - } + break; + } + case S_CanRelease: { + CheckForCanReleaseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S, + SomeSuccHasSame, AllSuccsHaveSame, + NotAllSeqEqualButKnownSafe); + break; + } + case S_Retain: + case S_None: + case S_Stop: + case S_Release: + case S_MovableRelease: + break; } - // If the state at the other end of any of the successor edges - // matches the current state, require all edges to match. This - // guards against loops in the middle of a sequence. - if (SomeSuccHasSame && !AllSuccsHaveSame) - S.ClearSequenceProgress(); - break; } + + // If the state at the other end of any of the successor edges + // matches the current state, require all edges to match. This + // guards against loops in the middle of a sequence. + if (SomeSuccHasSame && !AllSuccsHaveSame) { + S.ClearSequenceProgress(); + } else if (NotAllSeqEqualButKnownSafe) { + // If we would have cleared the state foregoing the fact that we are known + // safe, stop code motion. This is because whether or not it is safe to + // remove RR pairs via KnownSafe is an orthogonal concept to whether we + // are allowed to perform code motion. + S.SetCFGHazardAfflicted(true); } + } } bool @@ -1486,6 +1935,8 @@ ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst, InstructionClass Class = GetInstructionClass(Inst); const Value *Arg = 0; + DEBUG(dbgs() << "Class: " << Class << "\n"); + switch (Class) { case IC_Release: { Arg = GetObjCArg(Inst); @@ -1500,27 +1951,26 @@ ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst, // pairs by making PtrState hold a stack of states, but this is // simple and avoids adding overhead for the non-nested case. if (S.GetSeq() == S_Release || S.GetSeq() == S_MovableRelease) { - DEBUG(dbgs() << "ObjCARCOpt::VisitInstructionBottomUp: Found nested " - "releases (i.e. a release pair)\n"); + DEBUG(dbgs() << "Found nested releases (i.e. a release pair)\n"); NestingDetected = true; } MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind); - S.ResetSequenceProgress(ReleaseMetadata ? S_MovableRelease : S_Release); - S.RRI.ReleaseMetadata = ReleaseMetadata; - S.RRI.KnownSafe = S.IsKnownIncremented(); - S.RRI.IsTailCallRelease = cast(Inst)->isTailCall(); - S.RRI.Calls.insert(Inst); - + Sequence NewSeq = ReleaseMetadata ? S_MovableRelease : S_Release; + ANNOTATE_BOTTOMUP(Inst, Arg, S.GetSeq(), NewSeq); + S.ResetSequenceProgress(NewSeq); + S.SetReleaseMetadata(ReleaseMetadata); + S.SetKnownSafe(S.HasKnownPositiveRefCount()); + S.SetTailCallRelease(cast(Inst)->isTailCall()); + S.InsertCall(Inst); S.SetKnownPositiveRefCount(); break; } case IC_RetainBlock: - // An objc_retainBlock call with just a use may need to be kept, - // because it may be copying a block from the stack to the heap. - if (!IsRetainBlockOptimizable(Inst)) - break; - // FALLTHROUGH + // In OptimizeIndividualCalls, we have strength reduced all optimizable + // objc_retainBlocks to objc_retains. Thus at this point any + // objc_retainBlocks that we see are not optimizable. + break; case IC_Retain: case IC_RetainRV: { Arg = GetObjCArg(Inst); @@ -1528,20 +1978,22 @@ ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst, PtrState &S = MyStates.getPtrBottomUpState(Arg); S.SetKnownPositiveRefCount(); - switch (S.GetSeq()) { + Sequence OldSeq = S.GetSeq(); + switch (OldSeq) { case S_Stop: case S_Release: case S_MovableRelease: case S_Use: - S.RRI.ReverseInsertPts.clear(); + // If OldSeq is not S_Use or OldSeq is S_Use and we are tracking an + // imprecise release, clear our reverse insertion points. + if (OldSeq != S_Use || S.IsTrackingImpreciseReleases()) + S.ClearReverseInsertPts(); // FALL THROUGH case S_CanRelease: // Don't do retain+release tracking for IC_RetainRV, because it's // better to let it remain as the first instruction after a call. - if (Class != IC_RetainRV) { - S.RRI.IsRetainBlock = Class == IC_RetainBlock; - Retains[Inst] = S.RRI; - } + if (Class != IC_RetainRV) + Retains[Inst] = S.GetRRInfo(); S.ClearSequenceProgress(); break; case S_None: @@ -1549,7 +2001,9 @@ ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst, case S_Retain: llvm_unreachable("bottom-up pointer in retain state!"); } - return NestingDetected; + ANNOTATE_BOTTOMUP(Inst, Arg, OldSeq, S.GetSeq()); + // A retain moving bottom up can be a use. + break; } case IC_AutoreleasepoolPop: // Conservatively, clear MyStates for all known pointers. @@ -1559,6 +2013,28 @@ ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst, case IC_None: // These are irrelevant. return NestingDetected; + case IC_User: + // If we have a store into an alloca of a pointer we are tracking, the + // pointer has multiple owners implying that we must be more conservative. + // + // This comes up in the context of a pointer being ``KnownSafe''. In the + // presense of a block being initialized, the frontend will emit the + // objc_retain on the original pointer and the release on the pointer loaded + // from the alloca. The optimizer will through the provenance analysis + // realize that the two are related, but since we only require KnownSafe in + // one direction, will match the inner retain on the original pointer with + // the guard release on the original pointer. This is fixed by ensuring that + // in the presense of allocas we only unconditionally remove pointers if + // both our retain and our release are KnownSafe. + if (StoreInst *SI = dyn_cast(Inst)) { + if (AreAnyUnderlyingObjectsAnAlloca(SI->getPointerOperand())) { + BBState::ptr_iterator I = MyStates.findPtrBottomUpState( + StripPointerCastsAndObjCCalls(SI->getValueOperand())); + if (I != MyStates.bottom_up_ptr_end()) + MultiOwnersSet.insert(I->first); + } + } + break; default: break; } @@ -1575,10 +2051,13 @@ ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst, // Check for possible releases. if (CanAlterRefCount(Inst, Ptr, PA, Class)) { - S.ClearRefCount(); + DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr + << "\n"); + S.ClearKnownPositiveRefCount(); switch (Seq) { case S_Use: S.SetSeq(S_CanRelease); + ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S.GetSeq()); continue; case S_CanRelease: case S_Release: @@ -1596,30 +2075,39 @@ ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst, case S_Release: case S_MovableRelease: if (CanUse(Inst, Ptr, PA, Class)) { - assert(S.RRI.ReverseInsertPts.empty()); + DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr + << "\n"); + assert(!S.HasReverseInsertPts()); // If this is an invoke instruction, we're scanning it as part of // one of its successor blocks, since we can't insert code after it // in its own block, and we don't want to split critical edges. if (isa(Inst)) - S.RRI.ReverseInsertPts.insert(BB->getFirstInsertionPt()); + S.InsertReverseInsertPt(BB->getFirstInsertionPt()); else - S.RRI.ReverseInsertPts.insert(llvm::next(BasicBlock::iterator(Inst))); + S.InsertReverseInsertPt(llvm::next(BasicBlock::iterator(Inst))); S.SetSeq(S_Use); - } else if (Seq == S_Release && - (Class == IC_User || Class == IC_CallOrUser)) { + ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S_Use); + } else if (Seq == S_Release && IsUser(Class)) { + DEBUG(dbgs() << "PreciseReleaseUse: Seq: " << Seq << "; " << *Ptr + << "\n"); // Non-movable releases depend on any possible objc pointer use. S.SetSeq(S_Stop); - assert(S.RRI.ReverseInsertPts.empty()); + ANNOTATE_BOTTOMUP(Inst, Ptr, S_Release, S_Stop); + assert(!S.HasReverseInsertPts()); // As above; handle invoke specially. if (isa(Inst)) - S.RRI.ReverseInsertPts.insert(BB->getFirstInsertionPt()); + S.InsertReverseInsertPt(BB->getFirstInsertionPt()); else - S.RRI.ReverseInsertPts.insert(llvm::next(BasicBlock::iterator(Inst))); + S.InsertReverseInsertPt(llvm::next(BasicBlock::iterator(Inst))); } break; case S_Stop: - if (CanUse(Inst, Ptr, PA, Class)) + if (CanUse(Inst, Ptr, PA, Class)) { + DEBUG(dbgs() << "PreciseStopUse: Seq: " << Seq << "; " << *Ptr + << "\n"); S.SetSeq(S_Use); + ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S_Use); + } break; case S_CanRelease: case S_Use: @@ -1637,6 +2125,9 @@ bool ObjCARCOpt::VisitBottomUp(BasicBlock *BB, DenseMap &BBStates, MapVector &Retains) { + + DEBUG(dbgs() << "\n== ObjCARCOpt::VisitBottomUp ==\n"); + bool NestingDetected = false; BBState &MyStates = BBStates[BB]; @@ -1658,6 +2149,10 @@ ObjCARCOpt::VisitBottomUp(BasicBlock *BB, } } + // If ARC Annotations are enabled, output the current state of pointers at the + // bottom of the basic block. + ANNOTATE_BOTTOMUP_BBEND(MyStates, BB); + // Visit all the instructions, bottom-up. for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) { Instruction *Inst = llvm::prior(I); @@ -1666,7 +2161,7 @@ ObjCARCOpt::VisitBottomUp(BasicBlock *BB, if (isa(Inst)) continue; - DEBUG(dbgs() << "ObjCARCOpt::VisitButtonUp: Visiting " << *Inst << "\n"); + DEBUG(dbgs() << "Visiting " << *Inst << "\n"); NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates); } @@ -1681,6 +2176,10 @@ ObjCARCOpt::VisitBottomUp(BasicBlock *BB, NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates); } + // If ARC Annotations are enabled, output the current state of pointers at the + // top of the basic block. + ANNOTATE_BOTTOMUP_BBSTART(MyStates, BB); + return NestingDetected; } @@ -1694,11 +2193,10 @@ ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst, switch (Class) { case IC_RetainBlock: - // An objc_retainBlock call with just a use may need to be kept, - // because it may be copying a block from the stack to the heap. - if (!IsRetainBlockOptimizable(Inst)) - break; - // FALLTHROUGH + // In OptimizeIndividualCalls, we have strength reduced all optimizable + // objc_retainBlocks to objc_retains. Thus at this point any + // objc_retainBlocks that we see are not optimizable. + break; case IC_Retain: case IC_RetainRV: { Arg = GetObjCArg(Inst); @@ -1718,10 +2216,10 @@ ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst, if (S.GetSeq() == S_Retain) NestingDetected = true; + ANNOTATE_TOPDOWN(Inst, Arg, S.GetSeq(), S_Retain); S.ResetSequenceProgress(S_Retain); - S.RRI.IsRetainBlock = Class == IC_RetainBlock; - S.RRI.KnownSafe = S.IsKnownIncremented(); - S.RRI.Calls.insert(Inst); + S.SetKnownSafe(S.HasKnownPositiveRefCount()); + S.InsertCall(Inst); } S.SetKnownPositiveRefCount(); @@ -1734,17 +2232,23 @@ ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst, Arg = GetObjCArg(Inst); PtrState &S = MyStates.getPtrTopDownState(Arg); - S.ClearRefCount(); + S.ClearKnownPositiveRefCount(); + + Sequence OldSeq = S.GetSeq(); - switch (S.GetSeq()) { + MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind); + + switch (OldSeq) { case S_Retain: case S_CanRelease: - S.RRI.ReverseInsertPts.clear(); + if (OldSeq == S_Retain || ReleaseMetadata != 0) + S.ClearReverseInsertPts(); // FALL THROUGH case S_Use: - S.RRI.ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind); - S.RRI.IsTailCallRelease = cast(Inst)->isTailCall(); - Releases[Inst] = S.RRI; + S.SetReleaseMetadata(ReleaseMetadata); + S.SetTailCallRelease(cast(Inst)->isTailCall()); + Releases[Inst] = S.GetRRInfo(); + ANNOTATE_TOPDOWN(Inst, Arg, S.GetSeq(), S_None); S.ClearSequenceProgress(); break; case S_None: @@ -1780,12 +2284,15 @@ ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst, // Check for possible releases. if (CanAlterRefCount(Inst, Ptr, PA, Class)) { - S.ClearRefCount(); + DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr + << "\n"); + S.ClearKnownPositiveRefCount(); switch (Seq) { case S_Retain: S.SetSeq(S_CanRelease); - assert(S.RRI.ReverseInsertPts.empty()); - S.RRI.ReverseInsertPts.insert(Inst); + ANNOTATE_TOPDOWN(Inst, Ptr, Seq, S_CanRelease); + assert(!S.HasReverseInsertPts()); + S.InsertReverseInsertPt(Inst); // One call can't cause a transition from S_Retain to S_CanRelease // and S_CanRelease to S_Use. If we've made the first transition, @@ -1805,8 +2312,12 @@ ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst, // Check for possible direct uses. switch (Seq) { case S_CanRelease: - if (CanUse(Inst, Ptr, PA, Class)) + if (CanUse(Inst, Ptr, PA, Class)) { + DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr + << "\n"); S.SetSeq(S_Use); + ANNOTATE_TOPDOWN(Inst, Ptr, Seq, S_Use); + } break; case S_Retain: case S_Use: @@ -1826,6 +2337,7 @@ bool ObjCARCOpt::VisitTopDown(BasicBlock *BB, DenseMap &BBStates, DenseMap &Releases) { + DEBUG(dbgs() << "\n== ObjCARCOpt::VisitTopDown ==\n"); bool NestingDetected = false; BBState &MyStates = BBStates[BB]; @@ -1847,15 +2359,26 @@ ObjCARCOpt::VisitTopDown(BasicBlock *BB, } } + // If ARC Annotations are enabled, output the current state of pointers at the + // top of the basic block. + ANNOTATE_TOPDOWN_BBSTART(MyStates, BB); + // Visit all the instructions, top-down. for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { Instruction *Inst = I; - DEBUG(dbgs() << "ObjCARCOpt::VisitTopDown: Visiting " << *Inst << "\n"); + DEBUG(dbgs() << "Visiting " << *Inst << "\n"); NestingDetected |= VisitInstructionTopDown(Inst, Releases, MyStates); } + // If ARC Annotations are enabled, output the current state of pointers at the + // bottom of the basic block. + ANNOTATE_TOPDOWN_BBEND(MyStates, BB); + +#ifdef ARC_ANNOTATIONS + if (!(EnableARCAnnotations && DisableCheckForCFGHazards)) +#endif CheckForCFGHazards(BB, BBStates, MyStates); return NestingDetected; } @@ -1987,6 +2510,8 @@ void ObjCARCOpt::MoveCalls(Value *Arg, Type *ArgTy = Arg->getType(); Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext())); + DEBUG(dbgs() << "== ObjCARCOpt::MoveCalls ==\n"); + // Insert the new retain and release calls. for (SmallPtrSet::const_iterator PI = ReleasesToMove.ReverseInsertPts.begin(), @@ -1995,20 +2520,12 @@ void ObjCARCOpt::MoveCalls(Value *Arg, Value *MyArg = ArgTy == ParamTy ? Arg : new BitCastInst(Arg, ParamTy, "", InsertPt); CallInst *Call = - CallInst::Create(RetainsToMove.IsRetainBlock ? - getRetainBlockCallee(M) : getRetainCallee(M), - MyArg, "", InsertPt); + CallInst::Create(getRetainCallee(M), MyArg, "", InsertPt); Call->setDoesNotThrow(); - if (RetainsToMove.IsRetainBlock) - Call->setMetadata(CopyOnEscapeMDKind, - MDNode::get(M->getContext(), ArrayRef())); - else - Call->setTailCall(); + Call->setTailCall(); - DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Inserting new Release: " << *Call - << "\n" - " At insertion point: " << *InsertPt - << "\n"); + DEBUG(dbgs() << "Inserting new Retain: " << *Call << "\n" + "At insertion point: " << *InsertPt << "\n"); } for (SmallPtrSet::const_iterator PI = RetainsToMove.ReverseInsertPts.begin(), @@ -2025,10 +2542,8 @@ void ObjCARCOpt::MoveCalls(Value *Arg, if (ReleasesToMove.IsTailCallRelease) Call->setTailCall(); - DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Inserting new Retain: " << *Call - << "\n" - " At insertion point: " << *InsertPt - << "\n"); + DEBUG(dbgs() << "Inserting new Release: " << *Call << "\n" + "At insertion point: " << *InsertPt << "\n"); } // Delete the original retain and release calls. @@ -2038,8 +2553,7 @@ void ObjCARCOpt::MoveCalls(Value *Arg, Instruction *OrigRetain = *AI; Retains.blot(OrigRetain); DeadInsts.push_back(OrigRetain); - DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Deleting retain: " << *OrigRetain << - "\n"); + DEBUG(dbgs() << "Deleting retain: " << *OrigRetain << "\n"); } for (SmallPtrSet::const_iterator AI = ReleasesToMove.Calls.begin(), @@ -2047,9 +2561,9 @@ void ObjCARCOpt::MoveCalls(Value *Arg, Instruction *OrigRelease = *AI; Releases.erase(OrigRelease); DeadInsts.push_back(OrigRelease); - DEBUG(dbgs() << "ObjCARCOpt::MoveCalls: Deleting release: " << *OrigRelease - << "\n"); + DEBUG(dbgs() << "Deleting release: " << *OrigRelease << "\n"); } + } bool @@ -2067,8 +2581,11 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap bool KnownSafe, bool &AnyPairsCompletelyEliminated) { // If a pair happens in a region where it is known that the reference count - // is already incremented, we can similarly ignore possible decrements. + // is already incremented, we can similarly ignore possible decrements unless + // we are dealing with a retainable object with multiple provenance sources. bool KnownSafeTD = true, KnownSafeBU = true; + bool MultipleOwners = false; + bool CFGHazardAfflicted = false; // Connect the dots between the top-down-collected RetainsToMove and // bottom-up-collected ReleasesToMove to form sets of related calls. @@ -2079,7 +2596,6 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap unsigned OldCount = 0; unsigned NewCount = 0; bool FirstRelease = true; - bool FirstRetain = true; for (;;) { for (SmallVectorImpl::const_iterator NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) { @@ -2088,6 +2604,8 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap assert(It != Retains.end()); const RRInfo &NewRetainRRI = It->second; KnownSafeTD &= NewRetainRRI.KnownSafe; + MultipleOwners = + MultipleOwners || MultiOwnersSet.count(GetObjCArg(NewRetain)); for (SmallPtrSet::const_iterator LI = NewRetainRRI.Calls.begin(), LE = NewRetainRRI.Calls.end(); LI != LE; ++LI) { @@ -2099,8 +2617,14 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap const RRInfo &NewRetainReleaseRRI = Jt->second; assert(NewRetainReleaseRRI.Calls.count(NewRetain)); if (ReleasesToMove.Calls.insert(NewRetainRelease)) { - OldDelta -= - BBStates[NewRetainRelease->getParent()].GetAllPathCount(); + + // If we overflow when we compute the path count, don't remove/move + // anything. + const BBState &NRRBBState = BBStates[NewRetainRelease->getParent()]; + unsigned PathCount; + if (NRRBBState.GetAllPathCountWithOverflow(PathCount)) + return false; + OldDelta -= PathCount; // Merge the ReleaseMetadata and IsTailCallRelease values. if (FirstRelease) { @@ -2125,8 +2649,14 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap RE = NewRetainReleaseRRI.ReverseInsertPts.end(); RI != RE; ++RI) { Instruction *RIP = *RI; - if (ReleasesToMove.ReverseInsertPts.insert(RIP)) - NewDelta -= BBStates[RIP->getParent()].GetAllPathCount(); + if (ReleasesToMove.ReverseInsertPts.insert(RIP)) { + // If we overflow when we compute the path count, don't + // remove/move anything. + const BBState &RIPBBState = BBStates[RIP->getParent()]; + if (RIPBBState.GetAllPathCountWithOverflow(PathCount)) + return false; + NewDelta -= PathCount; + } } NewReleases.push_back(NewRetainRelease); } @@ -2144,6 +2674,7 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap assert(It != Releases.end()); const RRInfo &NewReleaseRRI = It->second; KnownSafeBU &= NewReleaseRRI.KnownSafe; + CFGHazardAfflicted |= NewReleaseRRI.CFGHazardAfflicted; for (SmallPtrSet::const_iterator LI = NewReleaseRRI.Calls.begin(), LE = NewReleaseRRI.Calls.end(); LI != LE; ++LI) { @@ -2155,20 +2686,15 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap const RRInfo &NewReleaseRetainRRI = Jt->second; assert(NewReleaseRetainRRI.Calls.count(NewRelease)); if (RetainsToMove.Calls.insert(NewReleaseRetain)) { - unsigned PathCount = - BBStates[NewReleaseRetain->getParent()].GetAllPathCount(); - OldDelta += PathCount; - OldCount += PathCount; - // Merge the IsRetainBlock values. - if (FirstRetain) { - RetainsToMove.IsRetainBlock = NewReleaseRetainRRI.IsRetainBlock; - FirstRetain = false; - } else if (ReleasesToMove.IsRetainBlock != - NewReleaseRetainRRI.IsRetainBlock) - // It's not possible to merge the sequences if one uses - // objc_retain and the other uses objc_retainBlock. + // If we overflow when we compute the path count, don't remove/move + // anything. + const BBState &NRRBBState = BBStates[NewReleaseRetain->getParent()]; + unsigned PathCount; + if (NRRBBState.GetAllPathCountWithOverflow(PathCount)) return false; + OldDelta += PathCount; + OldCount += PathCount; // Collect the optimal insertion points. if (!KnownSafe) @@ -2178,7 +2704,11 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap RI != RE; ++RI) { Instruction *RIP = *RI; if (RetainsToMove.ReverseInsertPts.insert(RIP)) { - PathCount = BBStates[RIP->getParent()].GetAllPathCount(); + // If we overflow when we compute the path count, don't + // remove/move anything. + const BBState &RIPBBState = BBStates[RIP->getParent()]; + if (RIPBBState.GetAllPathCountWithOverflow(PathCount)) + return false; NewDelta += PathCount; NewCount += PathCount; } @@ -2191,9 +2721,12 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap if (NewRetains.empty()) break; } - // If the pointer is known incremented or nested, we can safely delete the - // pair regardless of what's between them. - if (KnownSafeTD || KnownSafeBU) { + // If the pointer is known incremented in 1 direction and we do not have + // MultipleOwners, we can safely remove the retain/releases. Otherwise we need + // to be known safe in both directions. + bool UnconditionallySafe = (KnownSafeTD && KnownSafeBU) || + ((KnownSafeTD || KnownSafeBU) && !MultipleOwners); + if (UnconditionallySafe) { RetainsToMove.ReverseInsertPts.clear(); ReleasesToMove.ReverseInsertPts.clear(); NewCount = 0; @@ -2204,6 +2737,14 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap // less aggressive solution which is. if (NewDelta != 0) return false; + + // At this point, we are not going to remove any RR pairs, but we still are + // able to move RR pairs. If one of our pointers is afflicted with + // CFGHazards, we cannot perform such code motion so exit early. + const bool WillPerformCodeMotion = RetainsToMove.ReverseInsertPts.size() || + ReleasesToMove.ReverseInsertPts.size(); + if (CFGHazardAfflicted && WillPerformCodeMotion) + return false; } // Determine whether the original call points are balanced in the retain and @@ -2214,6 +2755,12 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap if (OldDelta != 0) return false; +#ifdef ARC_ANNOTATIONS + // Do not move calls if ARC annotations are requested. + if (EnableARCAnnotations) + return false; +#endif // ARC_ANNOTATIONS + Changed = true; assert(OldCount != 0 && "Unreachable code?"); NumRRs += OldCount - NewCount; @@ -2232,6 +2779,8 @@ ObjCARCOpt::PerformCodePlacement(DenseMap MapVector &Retains, DenseMap &Releases, Module *M) { + DEBUG(dbgs() << "\n== ObjCARCOpt::PerformCodePlacement ==\n"); + bool AnyPairsCompletelyEliminated = false; RRInfo RetainsToMove; RRInfo ReleasesToMove; @@ -2247,8 +2796,7 @@ ObjCARCOpt::PerformCodePlacement(DenseMap Instruction *Retain = cast(V); - DEBUG(dbgs() << "ObjCARCOpt::PerformCodePlacement: Visiting: " << *Retain - << "\n"); + DEBUG(dbgs() << "Visiting: " << *Retain << "\n"); Value *Arg = GetObjCArg(Retain); @@ -2299,14 +2847,15 @@ ObjCARCOpt::PerformCodePlacement(DenseMap /// Weak pointer optimizations. void ObjCARCOpt::OptimizeWeakCalls(Function &F) { + DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeWeakCalls ==\n"); + // First, do memdep-style RLE and S2L optimizations. We can't use memdep // itself because it uses AliasAnalysis and we need to do provenance // queries instead. for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { Instruction *Inst = &*I++; - DEBUG(dbgs() << "ObjCARCOpt::OptimizeWeakCalls: Visiting: " << *Inst << - "\n"); + DEBUG(dbgs() << "Visiting: " << *Inst << "\n"); InstructionClass Class = GetBasicInstructionClass(Inst); if (Class != IC_LoadWeak && Class != IC_LoadWeakRetained) @@ -2396,6 +2945,7 @@ void ObjCARCOpt::OptimizeWeakCalls(Function &F) { goto clobbered; case IC_AutoreleasepoolPush: case IC_None: + case IC_IntrinsicUser: case IC_User: // Weak pointers are only modified through the weak entry points // (and arbitrary calls, which could call the weak entry points). @@ -2453,31 +3003,116 @@ void ObjCARCOpt::OptimizeWeakCalls(Function &F) { done:; } } - - DEBUG(dbgs() << "ObjCARCOpt::OptimizeWeakCalls: Finished List.\n\n"); - } /// Identify program paths which execute sequences of retains and releases which /// can be eliminated. bool ObjCARCOpt::OptimizeSequences(Function &F) { - /// Releases, Retains - These are used to store the results of the main flow - /// analysis. These use Value* as the key instead of Instruction* so that the - /// map stays valid when we get around to rewriting code and calls get - /// replaced by arguments. + // Releases, Retains - These are used to store the results of the main flow + // analysis. These use Value* as the key instead of Instruction* so that the + // map stays valid when we get around to rewriting code and calls get + // replaced by arguments. DenseMap Releases; MapVector Retains; - /// This is used during the traversal of the function to track the - /// states for each identified object at each block. + // This is used during the traversal of the function to track the + // states for each identified object at each block. DenseMap BBStates; // Analyze the CFG of the function, and all instructions. bool NestingDetected = Visit(F, BBStates, Retains, Releases); // Transform. - return PerformCodePlacement(BBStates, Retains, Releases, F.getParent()) && - NestingDetected; + bool AnyPairsCompletelyEliminated = PerformCodePlacement(BBStates, Retains, + Releases, + F.getParent()); + + // Cleanup. + MultiOwnersSet.clear(); + + return AnyPairsCompletelyEliminated && NestingDetected; +} + +/// Check if there is a dependent call earlier that does not have anything in +/// between the Retain and the call that can affect the reference count of their +/// shared pointer argument. Note that Retain need not be in BB. +static bool +HasSafePathToPredecessorCall(const Value *Arg, Instruction *Retain, + SmallPtrSet &DepInsts, + SmallPtrSet &Visited, + ProvenanceAnalysis &PA) { + FindDependencies(CanChangeRetainCount, Arg, Retain->getParent(), Retain, + DepInsts, Visited, PA); + if (DepInsts.size() != 1) + return false; + + CallInst *Call = + dyn_cast_or_null(*DepInsts.begin()); + + // Check that the pointer is the return value of the call. + if (!Call || Arg != Call) + return false; + + // Check that the call is a regular call. + InstructionClass Class = GetBasicInstructionClass(Call); + if (Class != IC_CallOrUser && Class != IC_Call) + return false; + + return true; +} + +/// Find a dependent retain that precedes the given autorelease for which there +/// is nothing in between the two instructions that can affect the ref count of +/// Arg. +static CallInst * +FindPredecessorRetainWithSafePath(const Value *Arg, BasicBlock *BB, + Instruction *Autorelease, + SmallPtrSet &DepInsts, + SmallPtrSet &Visited, + ProvenanceAnalysis &PA) { + FindDependencies(CanChangeRetainCount, Arg, + BB, Autorelease, DepInsts, Visited, PA); + if (DepInsts.size() != 1) + return 0; + + CallInst *Retain = + dyn_cast_or_null(*DepInsts.begin()); + + // Check that we found a retain with the same argument. + if (!Retain || + !IsRetain(GetBasicInstructionClass(Retain)) || + GetObjCArg(Retain) != Arg) { + return 0; + } + + return Retain; +} + +/// Look for an ``autorelease'' instruction dependent on Arg such that there are +/// no instructions dependent on Arg that need a positive ref count in between +/// the autorelease and the ret. +static CallInst * +FindPredecessorAutoreleaseWithSafePath(const Value *Arg, BasicBlock *BB, + ReturnInst *Ret, + SmallPtrSet &DepInsts, + SmallPtrSet &V, + ProvenanceAnalysis &PA) { + FindDependencies(NeedsPositiveRetainCount, Arg, + BB, Ret, DepInsts, V, PA); + if (DepInsts.size() != 1) + return 0; + + CallInst *Autorelease = + dyn_cast_or_null(*DepInsts.begin()); + if (!Autorelease) + return 0; + InstructionClass AutoreleaseClass = GetBasicInstructionClass(Autorelease); + if (!IsAutorelease(AutoreleaseClass)) + return 0; + if (GetObjCArg(Autorelease) != Arg) + return 0; + + return Autorelease; } /// Look for this pattern: @@ -2488,122 +3123,91 @@ bool ObjCARCOpt::OptimizeSequences(Function &F) { /// ret i8* %3 /// \endcode /// And delete the retain and autorelease. -/// -/// Otherwise if it's just this: -/// \code -/// %3 = call i8* @objc_autorelease(i8* %2) -/// ret i8* %3 -/// \endcode -/// convert the autorelease to autoreleaseRV. void ObjCARCOpt::OptimizeReturns(Function &F) { if (!F.getReturnType()->isPointerTy()) return; + DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeReturns ==\n"); + SmallPtrSet DependingInstructions; SmallPtrSet Visited; for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { BasicBlock *BB = FI; ReturnInst *Ret = dyn_cast(&BB->back()); - DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Visiting: " << *Ret << "\n"); + DEBUG(dbgs() << "Visiting: " << *Ret << "\n"); - if (!Ret) continue; + if (!Ret) + continue; const Value *Arg = StripPointerCastsAndObjCCalls(Ret->getOperand(0)); - FindDependencies(NeedsPositiveRetainCount, Arg, - BB, Ret, DependingInstructions, Visited, PA); - if (DependingInstructions.size() != 1) - goto next_block; - - { - CallInst *Autorelease = - dyn_cast_or_null(*DependingInstructions.begin()); - if (!Autorelease) - goto next_block; - InstructionClass AutoreleaseClass = GetBasicInstructionClass(Autorelease); - if (!IsAutorelease(AutoreleaseClass)) - goto next_block; - if (GetObjCArg(Autorelease) != Arg) - goto next_block; - - DependingInstructions.clear(); - Visited.clear(); - - // Check that there is nothing that can affect the reference - // count between the autorelease and the retain. - FindDependencies(CanChangeRetainCount, Arg, - BB, Autorelease, DependingInstructions, Visited, PA); - if (DependingInstructions.size() != 1) - goto next_block; - - { - CallInst *Retain = - dyn_cast_or_null(*DependingInstructions.begin()); - - // Check that we found a retain with the same argument. - if (!Retain || - !IsRetain(GetBasicInstructionClass(Retain)) || - GetObjCArg(Retain) != Arg) - goto next_block; - - DependingInstructions.clear(); - Visited.clear(); - - // Convert the autorelease to an autoreleaseRV, since it's - // returning the value. - if (AutoreleaseClass == IC_Autorelease) { - DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Converting autorelease " - "=> autoreleaseRV since it's returning a value.\n" - " In: " << *Autorelease - << "\n"); - Autorelease->setCalledFunction(getAutoreleaseRVCallee(F.getParent())); - DEBUG(dbgs() << " Out: " << *Autorelease - << "\n"); - Autorelease->setTailCall(); // Always tail call autoreleaseRV. - AutoreleaseClass = IC_AutoreleaseRV; - } - // Check that there is nothing that can affect the reference - // count between the retain and the call. - // Note that Retain need not be in BB. - FindDependencies(CanChangeRetainCount, Arg, Retain->getParent(), Retain, - DependingInstructions, Visited, PA); - if (DependingInstructions.size() != 1) - goto next_block; - - { - CallInst *Call = - dyn_cast_or_null(*DependingInstructions.begin()); + // Look for an ``autorelease'' instruction that is a predecessor of Ret and + // dependent on Arg such that there are no instructions dependent on Arg + // that need a positive ref count in between the autorelease and Ret. + CallInst *Autorelease = + FindPredecessorAutoreleaseWithSafePath(Arg, BB, Ret, + DependingInstructions, Visited, + PA); + DependingInstructions.clear(); + Visited.clear(); - // Check that the pointer is the return value of the call. - if (!Call || Arg != Call) - goto next_block; + if (!Autorelease) + continue; - // Check that the call is a regular call. - InstructionClass Class = GetBasicInstructionClass(Call); - if (Class != IC_CallOrUser && Class != IC_Call) - goto next_block; + CallInst *Retain = + FindPredecessorRetainWithSafePath(Arg, BB, Autorelease, + DependingInstructions, Visited, PA); + DependingInstructions.clear(); + Visited.clear(); - // If so, we can zap the retain and autorelease. - Changed = true; - ++NumRets; - DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Erasing: " << *Retain - << "\n Erasing: " - << *Autorelease << "\n"); - EraseInstruction(Retain); - EraseInstruction(Autorelease); - } - } - } + if (!Retain) + continue; - next_block: + // Check that there is nothing that can affect the reference count + // between the retain and the call. Note that Retain need not be in BB. + bool HasSafePathToCall = HasSafePathToPredecessorCall(Arg, Retain, + DependingInstructions, + Visited, PA); DependingInstructions.clear(); Visited.clear(); + + if (!HasSafePathToCall) + continue; + + // If so, we can zap the retain and autorelease. + Changed = true; + ++NumRets; + DEBUG(dbgs() << "Erasing: " << *Retain << "\nErasing: " + << *Autorelease << "\n"); + EraseInstruction(Retain); + EraseInstruction(Autorelease); } +} - DEBUG(dbgs() << "ObjCARCOpt::OptimizeReturns: Finished List.\n\n"); +#ifndef NDEBUG +void +ObjCARCOpt::GatherStatistics(Function &F, bool AfterOptimization) { + llvm::Statistic &NumRetains = + AfterOptimization? NumRetainsAfterOpt : NumRetainsBeforeOpt; + llvm::Statistic &NumReleases = + AfterOptimization? NumReleasesAfterOpt : NumReleasesBeforeOpt; + for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { + Instruction *Inst = &*I++; + switch (GetBasicInstructionClass(Inst)) { + default: + break; + case IC_Retain: + ++NumRetains; + break; + case IC_Release: + ++NumReleases; + break; + } + } } +#endif bool ObjCARCOpt::doInitialization(Module &M) { if (!EnableARCOpts) @@ -2621,13 +3225,20 @@ bool ObjCARCOpt::doInitialization(Module &M) { M.getContext().getMDKindID("clang.arc.copy_on_escape"); NoObjCARCExceptionsMDKind = M.getContext().getMDKindID("clang.arc.no_objc_arc_exceptions"); +#ifdef ARC_ANNOTATIONS + ARCAnnotationBottomUpMDKind = + M.getContext().getMDKindID("llvm.arc.annotation.bottomup"); + ARCAnnotationTopDownMDKind = + M.getContext().getMDKindID("llvm.arc.annotation.topdown"); + ARCAnnotationProvenanceSourceMDKind = + M.getContext().getMDKindID("llvm.arc.annotation.provenancesource"); +#endif // ARC_ANNOTATIONS // Intuitively, objc_retain and others are nocapture, however in practice // they are not, because they return their argument value. And objc_release // calls finalizers which can have arbitrary side effects. // These are initialized lazily. - RetainRVCallee = 0; AutoreleaseRVCallee = 0; ReleaseCallee = 0; RetainCallee = 0; @@ -2647,15 +3258,22 @@ bool ObjCARCOpt::runOnFunction(Function &F) { Changed = false; - DEBUG(dbgs() << "ObjCARCOpt: Visiting Function: " << F.getName() << "\n"); + DEBUG(dbgs() << "<<< ObjCARCOpt: Visiting Function: " << F.getName() << " >>>" + "\n"); PA.setAA(&getAnalysis()); +#ifndef NDEBUG + if (AreStatisticsEnabled()) { + GatherStatistics(F, false); + } +#endif + // This pass performs several distinct transformations. As a compile-time aid // when compiling code that isn't ObjC, skip these if the relevant ObjC // library functions aren't declared. - // Preliminary optimizations. This also computs UsedInThisFunction. + // Preliminary optimizations. This also computes UsedInThisFunction. OptimizeIndividualCalls(F); // Optimizations for weak pointers. @@ -2682,6 +3300,13 @@ bool ObjCARCOpt::runOnFunction(Function &F) { (1 << IC_AutoreleaseRV))) OptimizeReturns(F); + // Gather statistics after optimization. +#ifndef NDEBUG + if (AreStatisticsEnabled()) { + GatherStatistics(F, true); + } +#endif + DEBUG(dbgs() << "\n"); return Changed;