From acfb3584c58159ec20a8379c864c9d644f8d967e Mon Sep 17 00:00:00 2001 From: Michael Gottesman Date: Mon, 13 May 2013 23:49:42 +0000 Subject: [objc-arc-opts] In the presense of an alloca unconditionally remove RR pairs if and only if we are both KnownSafeBU/KnownSafeTD rather than just either or. 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 (albiet different), 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 (i.e. we are KnownSafe in both directions) since we must deal with the possibility that the frontend will emit what (to the optimizer) appears to be unbalanced retain/releases. An example of the miscompile is: %A = alloca retain(%x) retain(%x) <--- Inner Retain store %x, %A %y = load %A ... DO STUFF ... release(%y) call void @use(%x) release(%x) <--- Guarding Release getting optimized to: %A = alloca retain(%x) store %x, %A %y = load %A ... DO STUFF ... release(%y) call void @use(%x) rdar://13750319 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181743 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/ObjCARC/ObjCARCOpts.cpp | 96 +++++++++++++++- test/Transforms/ObjCARC/allocas.ll | 203 +++++++++++++++++++++++++++++++++ 2 files changed, 294 insertions(+), 5 deletions(-) create mode 100644 test/Transforms/ObjCARC/allocas.ll diff --git a/lib/Transforms/ObjCARC/ObjCARCOpts.cpp b/lib/Transforms/ObjCARC/ObjCARCOpts.cpp index bab49e75b7..2932af10c2 100644 --- a/lib/Transforms/ObjCARC/ObjCARCOpts.cpp +++ b/lib/Transforms/ObjCARC/ObjCARCOpts.cpp @@ -107,6 +107,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 +259,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. @@ -414,8 +454,18 @@ namespace { /// sequence. SmallPtrSet ReverseInsertPts; + /// Does this pointer have multiple owners? + /// + /// In the presence of multiple owners with the same provenance caused by + /// allocas, we can not assume that the frontend will emit balanced code + /// since it could put the release on the pointer loaded from the + /// alloca. This confuses the optimizer so we must be more conservative in + /// that case. + bool MultipleOwners; + RRInfo() : - KnownSafe(false), IsTailCallRelease(false), ReleaseMetadata(0) {} + KnownSafe(false), IsTailCallRelease(false), ReleaseMetadata(0), + MultipleOwners(false) {} void clear(); @@ -428,6 +478,7 @@ namespace { void RRInfo::clear() { KnownSafe = false; IsTailCallRelease = false; + MultipleOwners = false; ReleaseMetadata = 0; Calls.clear(); ReverseInsertPts.clear(); @@ -516,6 +567,7 @@ PtrState::Merge(const PtrState &Other, bool TopDown) { RRI.IsTailCallRelease = RRI.IsTailCallRelease && Other.RRI.IsTailCallRelease; RRI.Calls.insert(Other.RRI.Calls.begin(), Other.RRI.Calls.end()); + RRI.MultipleOwners |= Other.RRI.MultipleOwners; // Merge the insert point sets. If there are any differences, // that makes this a partial merge. @@ -601,6 +653,12 @@ namespace { 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(); } @@ -1865,6 +1923,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()) + I->second.RRI.MultipleOwners = true; + } + } + break; default: break; } @@ -2411,8 +2491,10 @@ 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; // Connect the dots between the top-down-collected RetainsToMove and // bottom-up-collected ReleasesToMove to form sets of related calls. @@ -2431,6 +2513,7 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap assert(It != Retains.end()); const RRInfo &NewRetainRRI = It->second; KnownSafeTD &= NewRetainRRI.KnownSafe; + MultipleOwners |= NewRetainRRI.MultipleOwners; for (SmallPtrSet::const_iterator LI = NewRetainRRI.Calls.begin(), LE = NewRetainRRI.Calls.end(); LI != LE; ++LI) { @@ -2524,9 +2607,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; diff --git a/test/Transforms/ObjCARC/allocas.ll b/test/Transforms/ObjCARC/allocas.ll new file mode 100644 index 0000000000..eabd54deb7 --- /dev/null +++ b/test/Transforms/ObjCARC/allocas.ll @@ -0,0 +1,203 @@ +; RUN: opt -objc-arc -S < %s | FileCheck %s + +declare i8* @objc_retain(i8*) +declare i8* @objc_retainAutoreleasedReturnValue(i8*) +declare void @objc_release(i8*) +declare i8* @objc_autorelease(i8*) +declare i8* @objc_autoreleaseReturnValue(i8*) +declare void @objc_autoreleasePoolPop(i8*) +declare i8* @objc_autoreleasePoolPush() +declare i8* @objc_retainBlock(i8*) + +declare i8* @objc_retainedObject(i8*) +declare i8* @objc_unretainedObject(i8*) +declare i8* @objc_unretainedPointer(i8*) + +declare void @use_pointer(i8*) +declare void @callee() +declare void @callee_fnptr(void ()*) +declare void @invokee() +declare i8* @returner() +declare void @bar(i32 ()*) +declare void @use_alloca(i8**) + +declare void @llvm.dbg.value(metadata, i64, metadata) + +declare i8* @objc_msgSend(i8*, i8*, ...) + + +; In the presense of allocas, unconditionally remove retain/release pairs only +; if they are known safe in both directions. This prevents matching up an inner +; retain with the boundary guarding release in the following situation: +; +; %A = alloca +; retain(%x) +; retain(%x) <--- Inner Retain +; store %x, %A +; %y = load %A +; ... DO STUFF ... +; release(%y) +; release(%x) <--- Guarding Release +; +; rdar://13750319 + +; CHECK: define void @test1a(i8* %x) +; CHECK: @objc_retain(i8* %x) +; CHECK: @objc_retain(i8* %x) +; CHECK: @objc_release(i8* %y) +; CHECK: @objc_release(i8* %x) +; CHECK: ret void +; CHECK: } +define void @test1a(i8* %x) { +entry: + %A = alloca i8* + tail call i8* @objc_retain(i8* %x) + tail call i8* @objc_retain(i8* %x) + store i8* %x, i8** %A, align 8 + %y = load i8** %A + call void @use_alloca(i8** %A) + call void @objc_release(i8* %y), !clang.imprecise_release !0 + call void @use_pointer(i8* %x) + call void @objc_release(i8* %x), !clang.imprecise_release !0 + ret void +} + +; CHECK: define void @test1b(i8* %x) +; CHECK: @objc_retain(i8* %x) +; CHECK: @objc_retain(i8* %x) +; CHECK: @objc_release(i8* %y) +; CHECK: @objc_release(i8* %x) +; CHECK: ret void +; CHECK: } +define void @test1b(i8* %x) { +entry: + %A = alloca i8* + %gep = getelementptr i8** %A, i32 0 + tail call i8* @objc_retain(i8* %x) + tail call i8* @objc_retain(i8* %x) + store i8* %x, i8** %gep, align 8 + %y = load i8** %A + call void @use_alloca(i8** %A) + call void @objc_release(i8* %y), !clang.imprecise_release !0 + call void @use_pointer(i8* %x) + call void @objc_release(i8* %x), !clang.imprecise_release !0 + ret void +} + + +; CHECK: define void @test1c(i8* %x) +; CHECK: @objc_retain(i8* %x) +; CHECK: @objc_retain(i8* %x) +; CHECK: @objc_release(i8* %y) +; CHECK: @objc_release(i8* %x) +; CHECK: ret void +; CHECK: } +define void @test1c(i8* %x) { +entry: + %A = alloca i8*, i32 3 + %gep = getelementptr i8** %A, i32 2 + tail call i8* @objc_retain(i8* %x) + tail call i8* @objc_retain(i8* %x) + store i8* %x, i8** %gep, align 8 + %y = load i8** %gep + call void @use_alloca(i8** %A) + call void @objc_release(i8* %y), !clang.imprecise_release !0 + call void @use_pointer(i8* %x) + call void @objc_release(i8* %x), !clang.imprecise_release !0 + ret void +} + + +; CHECK: define void @test1d(i8* %x) +; CHECK: @objc_retain(i8* %x) +; CHECK: @objc_retain(i8* %x) +; CHECK: @objc_release(i8* %y) +; CHECK: @objc_release(i8* %x) +; CHECK: ret void +; CHECK: } +define void @test1d(i8* %x) { +entry: + br i1 undef, label %use_allocaA, label %use_allocaB + +use_allocaA: + %allocaA = alloca i8* + br label %exit + +use_allocaB: + %allocaB = alloca i8* + br label %exit + +exit: + %A = phi i8** [ %allocaA, %use_allocaA ], [ %allocaB, %use_allocaB ] + %gep = getelementptr i8** %A, i32 0 + tail call i8* @objc_retain(i8* %x) + tail call i8* @objc_retain(i8* %x) + store i8* %x, i8** %gep, align 8 + %y = load i8** %gep + call void @use_alloca(i8** %A) + call void @objc_release(i8* %y), !clang.imprecise_release !0 + call void @use_pointer(i8* %x) + call void @objc_release(i8* %x), !clang.imprecise_release !0 + ret void +} + +; CHECK: define void @test1e(i8* %x) +; CHECK: @objc_retain(i8* %x) +; CHECK: @objc_retain(i8* %x) +; CHECK: @objc_release(i8* %y) +; CHECK: @objc_release(i8* %x) +; CHECK: ret void +; CHECK: } +define void @test1e(i8* %x) { +entry: + br i1 undef, label %use_allocaA, label %use_allocaB + +use_allocaA: + %allocaA = alloca i8*, i32 4 + br label %exit + +use_allocaB: + %allocaB = alloca i8*, i32 4 + br label %exit + +exit: + %A = phi i8** [ %allocaA, %use_allocaA ], [ %allocaB, %use_allocaB ] + %gep = getelementptr i8** %A, i32 2 + tail call i8* @objc_retain(i8* %x) + tail call i8* @objc_retain(i8* %x) + store i8* %x, i8** %gep, align 8 + %y = load i8** %gep + call void @use_alloca(i8** %A) + call void @objc_release(i8* %y), !clang.imprecise_release !0 + call void @use_pointer(i8* %x) + call void @objc_release(i8* %x), !clang.imprecise_release !0 + ret void +} + +; CHECK: define void @test1f(i8* %x) +; CHECK: @objc_retain(i8* %x) +; CHECK: @objc_retain(i8* %x) +; CHECK: @objc_release(i8* %y) +; CHECK: @objc_release(i8* %x) +; CHECK: ret void +; CHECK: } +define void @test1f(i8* %x) { +entry: + %allocaOne = alloca i8* + %allocaTwo = alloca i8* + %A = select i1 undef, i8** %allocaOne, i8** %allocaTwo + tail call i8* @objc_retain(i8* %x) + tail call i8* @objc_retain(i8* %x) + store i8* %x, i8** %A, align 8 + %y = load i8** %A + call void @use_alloca(i8** %A) + call void @objc_release(i8* %y), !clang.imprecise_release !0 + call void @use_pointer(i8* %x) + call void @objc_release(i8* %x), !clang.imprecise_release !0 + ret void +} + + +!0 = metadata !{} + +declare i32 @__gxx_personality_v0(...) -- cgit v1.2.3-18-g5258