From d877e3fe71676b0ff10410d80456b35cdd5bf796 Mon Sep 17 00:00:00 2001 From: Argyrios Kyrtzidis Date: Thu, 6 Oct 2022 10:02:19 -0700 Subject: [PATCH] [Transforms/ObjCARC] Fix non-deterministic output of `ObjCARCOptPass` `ProvenanceAnalysis::related()` was assuming that the order of parameters for `relatedCheck()` was not affecting the result but this was not the case when both parameters were `PHINode`s. Due to this assumption `ProvenanceAnalysis::related()` was ordering the parameters based on pointer value which resulted in non-deterministic behavior. To address this change `relatedPHI()` so that it gives the same result independent of the parameter order. rdar://100325456 Differential Revision: https://reviews.llvm.org/D135376 --- llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.cpp | 33 +++-- llvm/test/Transforms/ObjCARC/related-check.ll | 150 +++++++++++++++++++++ 2 files changed, 172 insertions(+), 11 deletions(-) create mode 100644 llvm/test/Transforms/ObjCARC/related-check.ll diff --git a/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.cpp b/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.cpp index 6731b84..f447c2a 100644 --- a/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.cpp +++ b/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.cpp @@ -53,10 +53,23 @@ bool ProvenanceAnalysis::relatedSelect(const SelectInst *A, bool ProvenanceAnalysis::relatedPHI(const PHINode *A, const Value *B) { - // If the values are PHIs in the same block, we can do a more precise as well - // as efficient check: just check for relations between the values on - // corresponding edges. - if (const PHINode *PNB = dyn_cast(B)) + + auto comparePHISources = [this](const PHINode *PNA, const Value *B) -> bool { + // Check each unique source of the PHI node against B. + SmallPtrSet UniqueSrc; + for (Value *PV1 : PNA->incoming_values()) { + if (UniqueSrc.insert(PV1).second && related(PV1, B)) + return true; + } + + // All of the arms checked out. + return false; + }; + + if (const PHINode *PNB = dyn_cast(B)) { + // If the values are PHIs in the same block, we can do a more precise as + // well as efficient check: just check for relations between the values on + // corresponding edges. if (PNB->getParent() == A->getParent()) { for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i) if (related(A->getIncomingValue(i), @@ -65,15 +78,11 @@ bool ProvenanceAnalysis::relatedPHI(const PHINode *A, return false; } - // Check each unique source of the PHI node against B. - SmallPtrSet UniqueSrc; - for (Value *PV1 : A->incoming_values()) { - if (UniqueSrc.insert(PV1).second && related(PV1, B)) - return true; + if (!comparePHISources(PNB, A)) + return false; } - // All of the arms checked out. - return false; + return comparePHISources(A, B); } /// Test if the value of P, or any value covered by its provenance, is ever @@ -174,6 +183,8 @@ bool ProvenanceAnalysis::related(const Value *A, const Value *B) { return Pair.first->second; bool Result = relatedCheck(A, B); + assert(relatedCheck(B, A) == Result && + "relatedCheck result depending on order of parameters!"); CachedResults[ValuePairTy(A, B)] = Result; return Result; } diff --git a/llvm/test/Transforms/ObjCARC/related-check.ll b/llvm/test/Transforms/ObjCARC/related-check.ll new file mode 100644 index 0000000..376ce66 --- /dev/null +++ b/llvm/test/Transforms/ObjCARC/related-check.ll @@ -0,0 +1,150 @@ +; Make sure this succeeds without hitting an assertion and the output is deterministic +; RUN: mkdir -p %t +; RUN: opt -objc-arc %s -S -o %t/out1.ll +; RUN: opt -objc-arc %s -S -o %t/out2.ll +; RUN: diff -u %t/out1.ll %t/out2.ll + +%0 = type opaque +%struct._class_t = type { %struct._class_t*, %struct._class_t*, %struct._objc_cache*, i8* (i8*, i8*)**, %struct._class_ro_t* } +%struct._objc_cache = type opaque +%struct._class_ro_t = type { i32, i32, i32, i8*, i8*, %struct.__method_list_t*, %struct._objc_protocol_list*, %struct._ivar_list_t*, i8*, %struct._prop_list_t* } +%struct.__method_list_t = type { i32, i32, [0 x %struct._objc_method] } +%struct._objc_method = type { i8*, i8*, i8* } +%struct._objc_protocol_list = type { i64, [0 x %struct._protocol_t*] } +%struct._protocol_t = type { i8*, i8*, %struct._objc_protocol_list*, %struct.__method_list_t*, %struct.__method_list_t*, %struct.__method_list_t*, %struct.__method_list_t*, %struct._prop_list_t*, i32, i32, i8**, i8*, %struct._prop_list_t* } +%struct._ivar_list_t = type { i32, i32, [0 x %struct._ivar_t] } +%struct._ivar_t = type { i32*, i8*, i8*, i32, i32 } +%struct._prop_list_t = type { i32, i32, [0 x %struct._prop_t] } +%struct._prop_t = type { i8*, i8* } +%struct.__NSConstantString_tag = type { i32*, i32, i8*, i64 } + +@.str = private unnamed_addr constant [8 x i8] c"%s: %s\0A\00", align 1 +@OBJC_METH_VAR_NAME_ = private unnamed_addr constant [25 x i8] c"fileSystemRepresentation\00", section "__TEXT,__objc_methname,cstring_literals", align 1 +@OBJC_SELECTOR_REFERENCES_ = internal externally_initialized global i8* getelementptr inbounds ([25 x i8], [25 x i8]* @OBJC_METH_VAR_NAME_, i32 0, i32 0), section "__DATA,__objc_selrefs,literal_pointers,no_dead_strip", align 8 +@"OBJC_CLASS_$_NSString" = external global %struct._class_t +@"OBJC_CLASSLIST_REFERENCES_$_" = internal global %struct._class_t* @"OBJC_CLASS_$_NSString", section "__DATA,__objc_classrefs,regular,no_dead_strip", align 8 +@__CFConstantStringClassReference = external global [0 x i32] +@.str.1 = private unnamed_addr constant [3 x i8] c"%@\00", section "__TEXT,__cstring,cstring_literals", align 1 +@_unnamed_cfstring_ = private global %struct.__NSConstantString_tag { i32* getelementptr inbounds ([0 x i32], [0 x i32]* @__CFConstantStringClassReference, i32 0, i32 0), i32 1992, i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str.1, i32 0, i32 0), i64 2 }, section "__DATA,__cfstring", align 8 #0 +@OBJC_METH_VAR_NAME_.2 = private unnamed_addr constant [18 x i8] c"stringWithFormat:\00", section "__TEXT,__objc_methname,cstring_literals", align 1 +@OBJC_SELECTOR_REFERENCES_.3 = internal externally_initialized global i8* getelementptr inbounds ([18 x i8], [18 x i8]* @OBJC_METH_VAR_NAME_.2, i32 0, i32 0), section "__DATA,__objc_selrefs,literal_pointers,no_dead_strip", align 8 +@llvm.compiler.used = appending global [5 x i8*] [i8* getelementptr inbounds ([25 x i8], [25 x i8]* @OBJC_METH_VAR_NAME_, i32 0, i32 0), i8* bitcast (i8** @OBJC_SELECTOR_REFERENCES_ to i8*), i8* bitcast (%struct._class_t** @"OBJC_CLASSLIST_REFERENCES_$_" to i8*), i8* getelementptr inbounds ([18 x i8], [18 x i8]* @OBJC_METH_VAR_NAME_.2, i32 0, i32 0), i8* bitcast (i8** @OBJC_SELECTOR_REFERENCES_.3 to i8*)], section "llvm.metadata" + +; Function Attrs: optsize ssp uwtable(sync) +define i32 @main(i32 noundef %argc, i8** nocapture noundef readnone %argv) local_unnamed_addr #1 { +entry: + %persistent = alloca i32, align 4 + %personalized = alloca i32, align 4 + %cmp31 = icmp sgt i32 %argc, 1 + br i1 %cmp31, label %for.body.lr.ph, label %for.cond.cleanup + +for.body.lr.ph: ; preds = %entry + %0 = bitcast i32* %persistent to i8* + %1 = bitcast i32* %personalized to i8* + %2 = load i8*, i8** @OBJC_SELECTOR_REFERENCES_, align 8 + %3 = load i8*, i8** @OBJC_SELECTOR_REFERENCES_.3, align 8 + br label %for.body + +for.cond.cleanup.loopexit: ; preds = %if.end19 + br label %for.cond.cleanup + +for.cond.cleanup: ; preds = %for.cond.cleanup.loopexit, %entry + ret i32 0 + +for.body: ; preds = %for.body.lr.ph, %if.end19 + %i.032 = phi i32 [ 1, %for.body.lr.ph ], [ %inc, %if.end19 ] + call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %0) #4 + store i32 0, i32* %persistent, align 4 + call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %1) #4 + store i32 0, i32* %personalized, align 4 + %call = call zeroext i1 @lookupType(i32* noundef nonnull %persistent, i32* noundef nonnull %personalized) #8, !clang.arc.no_objc_arc_exceptions !15 + br i1 %call, label %if.then, label %if.end19 + +if.then: ; preds = %for.body + %4 = load i32, i32* %persistent, align 4 + %cmp1.not = icmp eq i32 %4, 0 + br i1 %cmp1.not, label %if.end, label %if.then2 + +if.then2: ; preds = %if.then + %call34 = call %0* bitcast (%0* (...)* @getnsstr to %0* ()*)() #8 [ "clang.arc.attachedcall"(i8* (i8*)* @llvm.objc.retainAutoreleasedReturnValue) ], !clang.arc.no_objc_arc_exceptions !15 + call void (...) @llvm.objc.clang.arc.noop.use(%0* %call34) #4 + call void @llvm.objc.release(i8* null) #4, !clang.imprecise_release !15 + %call56 = call %0* bitcast (%0* (...)* @getnsstr to %0* ()*)() #8 [ "clang.arc.attachedcall"(i8* (i8*)* @llvm.objc.retainAutoreleasedReturnValue) ], !clang.arc.no_objc_arc_exceptions !15 + call void (...) @llvm.objc.clang.arc.noop.use(%0* %call56) #4 + call void @llvm.objc.release(i8* null) #4, !clang.imprecise_release !15 + br label %if.end + +if.end: ; preds = %if.then2, %if.then + %path.0 = phi %0* [ %call34, %if.then2 ], [ null, %if.then ] + %name.0 = phi %0* [ %call56, %if.then2 ], [ null, %if.then ] + %5 = load i32, i32* %personalized, align 4 + %cmp7.not = icmp eq i32 %5, 0 + br i1 %cmp7.not, label %if.end11, label %if.then8 + +if.then8: ; preds = %if.end + %call910 = call %0* bitcast (%0* (...)* @getnsstr to %0* ()*)() #8 [ "clang.arc.attachedcall"(i8* (i8*)* @llvm.objc.retainAutoreleasedReturnValue) ], !clang.arc.no_objc_arc_exceptions !15 + call void (...) @llvm.objc.clang.arc.noop.use(%0* %call910) #4 + %6 = bitcast %0* %path.0 to i8* + call void @llvm.objc.release(i8* %6) #4, !clang.imprecise_release !15 + br label %if.end11 + +if.end11: ; preds = %if.then8, %if.end + %path.1 = phi %0* [ %call910, %if.then8 ], [ %path.0, %if.end ] + %cmp12.not = icmp eq %0* %path.1, null + br i1 %cmp12.not, label %if.else, label %if.then13 + +if.then13: ; preds = %if.end11 + %7 = bitcast %0* %path.1 to i8* + %call14 = call i8* bitcast (i8* (i8*, i8*, ...)* @objc_msgSend to i8* (i8*, i8*)*)(i8* noundef nonnull %7, i8* noundef %2) #8, !clang.arc.no_objc_arc_exceptions !15 + %call15 = call i32 (i8*, ...) @printf(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([8 x i8], [8 x i8]* @.str, i64 0, i64 0), i8* noundef %call14) #8, !clang.arc.no_objc_arc_exceptions !15 + br label %if.end18 + +if.else: ; preds = %if.end11 + %8 = load i8*, i8** bitcast (%struct._class_t** @"OBJC_CLASSLIST_REFERENCES_$_" to i8**), align 8 + %call1617 = call i8* (i8*, i8*, %0*, ...) bitcast (i8* (i8*, i8*, ...)* @objc_msgSend to i8* (i8*, i8*, %0*, ...)*)(i8* noundef %8, i8* noundef %3, %0* noundef nonnull bitcast (%struct.__NSConstantString_tag* @_unnamed_cfstring_ to %0*), %0* noundef null) #8 [ "clang.arc.attachedcall"(i8* (i8*)* @llvm.objc.retainAutoreleasedReturnValue) ], !clang.arc.no_objc_arc_exceptions !15 + call void (...) @llvm.objc.clang.arc.noop.use(i8* %call1617) #4 + call void @llvm.objc.release(i8* %call1617) #4, !clang.imprecise_release !15 + br label %if.end18 + +if.end18: ; preds = %if.else, %if.then13 + %.pre-phi = phi i8* [ null, %if.else ], [ %7, %if.then13 ] + %9 = bitcast %0* %name.0 to i8* + call void @llvm.objc.release(i8* %9) #4, !clang.imprecise_release !15 + call void @llvm.objc.release(i8* %.pre-phi) #4, !clang.imprecise_release !15 + br label %if.end19 + +if.end19: ; preds = %if.end18, %for.body + call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %1) #4 + call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %0) #4 + %inc = add nuw nsw i32 %i.032, 1 + %exitcond.not = icmp eq i32 %inc, %argc + br i1 %exitcond.not, label %for.cond.cleanup.loopexit, label %for.body +} + +; Function Attrs: argmemonly mustprogress nocallback nofree nosync nounwind willreturn +declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #2 + +; Function Attrs: argmemonly mustprogress nocallback nofree nosync nounwind willreturn +declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture) #2 + +; Function Attrs: inaccessiblememonly mustprogress nocallback nofree nosync nounwind willreturn +declare void @llvm.objc.clang.arc.noop.use(...) #5 + +declare zeroext i1 @lookupType(i32* noundef, i32* noundef) #2 + +declare %0* @getnsstr(...) #2 + +; Function Attrs: nounwind +declare i8* @llvm.objc.retainAutoreleasedReturnValue(i8*) #3 + +; Function Attrs: nounwind +declare void @llvm.objc.release(i8*) #3 + +declare i32 @printf(i8* noundef, ...) #2 + +; Function Attrs: nonlazybind +declare i8* @objc_msgSend(i8*, i8*, ...) #4 + +attributes #0 = { "objc_arc_inert" } + +!15 = !{} -- 2.7.4