X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FObjCARC%2FObjCARCOpts.cpp;h=48fe7c1440395f3fd4dec3c27b062f104a82c9ec;hb=722b0a4d293b16eebaed94ae65d5f11743cbcea5;hp=e51ba6817c6638b1cea98250ab336a150428be96;hpb=8a709208ede8eb387a2911c5ba11e5acf8cc69ae;p=oota-llvm.git diff --git a/lib/Transforms/ObjCARC/ObjCARCOpts.cpp b/lib/Transforms/ObjCARC/ObjCARCOpts.cpp index e51ba6817c6..48fe7c14403 100644 --- a/lib/Transforms/ObjCARC/ObjCARCOpts.cpp +++ b/lib/Transforms/ObjCARC/ObjCARCOpts.cpp @@ -30,6 +30,7 @@ #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" @@ -107,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(); @@ -253,6 +260,40 @@ static bool DoesRetainableObjPtrEscape(const User *Ptr) { 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. @@ -300,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 @@ -404,14 +455,20 @@ 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), IsTailCallRelease(false), ReleaseMetadata(0) {} + KnownSafe(false), IsTailCallRelease(false), ReleaseMetadata(0), + CFGHazardAfflicted(false) {} void clear(); - bool IsTrackingImpreciseReleases() { - return ReleaseMetadata != 0; - } + /// Conservatively merge the two RRInfo. Returns true if a partial merge has + /// occured, false otherwise. + bool Merge(const RRInfo &Other); + }; } @@ -421,6 +478,30 @@ void RRInfo::clear() { 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 { @@ -437,20 +518,57 @@ namespace { /// 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 ClearKnownPositiveRefCount() { + DEBUG(dbgs() << "Clearing Known Positive.\n"); KnownPositiveRefCount = false; } @@ -472,19 +590,40 @@ namespace { } void ResetSequenceProgress(Sequence 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; + KnownPositiveRefCount &= Other.KnownPositiveRefCount; // If we're not in a sequence (anymore), drop all associated state. if (Seq == S_None) { @@ -497,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); } } @@ -576,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(); } @@ -597,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. @@ -981,6 +1128,9 @@ namespace { 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; @@ -988,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. @@ -1024,7 +1171,6 @@ namespace { unsigned ARCAnnotationProvenanceSourceMDKind; #endif // ARC_ANNOATIONS - Constant *getRetainRVCallee(Module *M); Constant *getAutoreleaseRVCallee(Module *M); Constant *getReleaseCallee(Module *M); Constant *getRetainCallee(Module *M); @@ -1033,7 +1179,6 @@ 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); @@ -1092,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); @@ -1139,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(); @@ -1234,35 +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() << "Transforming objc_retain => " - "objc_retainAutoreleasedReturnValue since the operand is a " - "return value.\nOld: "<< *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. @@ -1382,12 +1486,17 @@ ObjCARCOpt::OptimizeRetainBlockCall(Function &F, Instruction *Inst, 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; } @@ -1468,13 +1577,9 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { break; } case IC_RetainBlock: - // If we strength reduce an objc_retainBlock to amn objc_retain, continue + // If we strength reduce an objc_retainBlock to an objc_retain, continue // onto the objc_retain peephole optimizations. Otherwise break. - if (!OptimizeRetainBlockCall(F, Inst, Class)) - break; - // FALLTHROUGH - case IC_Retain: - OptimizeRetainCall(F, Inst); + OptimizeRetainBlockCall(F, Inst, Class); break; case IC_RetainRV: if (OptimizeRetainRVCall(F, Inst)) @@ -1499,8 +1604,7 @@ 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() << "Replacing autorelease{,RV}(x) with objc_release(x) " "since x is otherwise unused.\nOld: " << *Call << "\nNew: " @@ -1660,6 +1764,72 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { } } +/// 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 /// other CFG structures where moving code across the edge would result in it /// being executed more. @@ -1670,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 @@ -1805,10 +1959,10 @@ ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst, Sequence NewSeq = ReleaseMetadata ? S_MovableRelease : S_Release; ANNOTATE_BOTTOMUP(Inst, Arg, S.GetSeq(), NewSeq); S.ResetSequenceProgress(NewSeq); - S.RRI.ReleaseMetadata = ReleaseMetadata; - S.RRI.KnownSafe = S.HasKnownPositiveRefCount(); - S.RRI.IsTailCallRelease = cast(Inst)->isTailCall(); - S.RRI.Calls.insert(Inst); + S.SetReleaseMetadata(ReleaseMetadata); + S.SetKnownSafe(S.HasKnownPositiveRefCount()); + S.SetTailCallRelease(cast(Inst)->isTailCall()); + S.InsertCall(Inst); S.SetKnownPositiveRefCount(); break; } @@ -1832,14 +1986,14 @@ ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst, case S_Use: // 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.RRI.IsTrackingImpreciseReleases()) - S.RRI.ReverseInsertPts.clear(); + 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) - Retains[Inst] = S.RRI; + Retains[Inst] = S.GetRRInfo(); S.ClearSequenceProgress(); break; case S_None: @@ -1859,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; } @@ -1901,14 +2077,14 @@ ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst, if (CanUse(Inst, Ptr, PA, Class)) { DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr << "\n"); - assert(S.RRI.ReverseInsertPts.empty()); + 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); ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S_Use); } else if (Seq == S_Release && IsUser(Class)) { @@ -1917,12 +2093,12 @@ ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst, // Non-movable releases depend on any possible objc pointer use. S.SetSeq(S_Stop); ANNOTATE_BOTTOMUP(Inst, Ptr, S_Release, S_Stop); - assert(S.RRI.ReverseInsertPts.empty()); + 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: @@ -2042,8 +2218,8 @@ ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst, ANNOTATE_TOPDOWN(Inst, Arg, S.GetSeq(), S_Retain); S.ResetSequenceProgress(S_Retain); - S.RRI.KnownSafe = S.HasKnownPositiveRefCount(); - S.RRI.Calls.insert(Inst); + S.SetKnownSafe(S.HasKnownPositiveRefCount()); + S.InsertCall(Inst); } S.SetKnownPositiveRefCount(); @@ -2066,12 +2242,12 @@ ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst, case S_Retain: case S_CanRelease: if (OldSeq == S_Retain || ReleaseMetadata != 0) - S.RRI.ReverseInsertPts.clear(); + S.ClearReverseInsertPts(); // FALL THROUGH case S_Use: - S.RRI.ReleaseMetadata = ReleaseMetadata; - 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; @@ -2115,8 +2291,8 @@ ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst, case S_Retain: S.SetSeq(S_CanRelease); ANNOTATE_TOPDOWN(Inst, Ptr, Seq, S_CanRelease); - assert(S.RRI.ReverseInsertPts.empty()); - S.RRI.ReverseInsertPts.insert(Inst); + 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, @@ -2348,7 +2524,7 @@ void ObjCARCOpt::MoveCalls(Value *Arg, Call->setDoesNotThrow(); Call->setTailCall(); - DEBUG(dbgs() << "Inserting new Release: " << *Call << "\n" + DEBUG(dbgs() << "Inserting new Retain: " << *Call << "\n" "At insertion point: " << *InsertPt << "\n"); } for (SmallPtrSet::const_iterator @@ -2405,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. @@ -2425,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) { @@ -2436,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) { @@ -2462,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); } @@ -2481,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) { @@ -2492,8 +2686,13 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap const RRInfo &NewReleaseRetainRRI = Jt->second; assert(NewReleaseRetainRRI.Calls.count(NewRelease)); if (RetainsToMove.Calls.insert(NewReleaseRetain)) { - unsigned PathCount = - BBStates[NewReleaseRetain->getParent()].GetAllPathCount(); + + // 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; @@ -2505,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; } @@ -2518,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; @@ -2531,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 @@ -2541,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; @@ -2603,12 +2823,6 @@ ObjCARCOpt::PerformCodePlacement(DenseMap ReleasesToMove, Arg, KnownSafe, AnyPairsCompletelyEliminated); -#ifdef ARC_ANNOTATIONS - // Do not move calls if ARC annotations are requested. If we were to move - // calls in this case, we would not be able - PerformMoveCalls = PerformMoveCalls && !EnableARCAnnotations; -#endif // ARC_ANNOTATIONS - if (PerformMoveCalls) { // Ok, everything checks out and we're all set. Let's move/delete some // code! @@ -2794,23 +3008,29 @@ void ObjCARCOpt::OptimizeWeakCalls(Function &F) { /// 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 @@ -2922,44 +3142,73 @@ void ObjCARCOpt::OptimizeReturns(Function &F) { const Value *Arg = StripPointerCastsAndObjCCalls(Ret->getOperand(0)); - // Look for an ``autorelease'' instruction that is a predecssor of Ret and + // 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); - if (Autorelease) { - DependingInstructions.clear(); - Visited.clear(); - - CallInst *Retain = - FindPredecessorRetainWithSafePath(Arg, BB, Autorelease, - DependingInstructions, Visited, PA); - if (Retain) { - DependingInstructions.clear(); - Visited.clear(); - - // 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. - if (HasSafePathToPredecessorCall(Arg, Retain, DependingInstructions, - Visited, PA)) { - // If so, we can zap the retain and autorelease. - Changed = true; - ++NumRets; - DEBUG(dbgs() << "Erasing: " << *Retain << "\nErasing: " - << *Autorelease << "\n"); - EraseInstruction(Retain); - EraseInstruction(Autorelease); - } - } - } + DependingInstructions.clear(); + Visited.clear(); + + if (!Autorelease) + continue; + CallInst *Retain = + FindPredecessorRetainWithSafePath(Arg, BB, Autorelease, + DependingInstructions, Visited, PA); DependingInstructions.clear(); Visited.clear(); + + if (!Retain) + continue; + + // 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); } } +#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) return false; @@ -2990,7 +3239,6 @@ bool ObjCARCOpt::doInitialization(Module &M) { // calls finalizers which can have arbitrary side effects. // These are initialized lazily. - RetainRVCallee = 0; AutoreleaseRVCallee = 0; ReleaseCallee = 0; RetainCallee = 0; @@ -3015,11 +3263,17 @@ bool ObjCARCOpt::runOnFunction(Function &F) { 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. @@ -3046,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;