Optimization result is non-deterministic when compiling abc

[dtcxzyw]

Reduced test case:

target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

define ptr @Vec_PtrAllocExact(i32 %0) {
  %2 = call ptr @malloc(i64 16)
  %3 = getelementptr i8, ptr %2, i64 4
  store i32 0, ptr %3, align 4
  store i32 %0, ptr %2, align 8
  %4 = getelementptr i8, ptr %2, i64 8
  store ptr null, ptr %4, align 8
  ret ptr %2
}

define internal void @Vec_PtrPush(ptr %0, ptr %1) {
  store i32 0, ptr %0, align 4
  ret void
}

declare i32 @Vec_PtrSize()

declare ptr @Abc_NtkObj()

declare ptr @Ptr_AbcDeriveOutputs()

define ptr @Ptr_AbcDeriveNtk() {
  %1 = call ptr @Vec_PtrAllocExact(i32 1)
  call void @Vec_PtrPush(ptr %1, ptr null)
  %2 = call ptr @Vec_PtrAllocExact(i32 0)
  store volatile ptr %2, ptr %1, align 8
  ret ptr null
}

declare ptr @malloc(i64)

Reproduction script:

#!/usr/bin/bash

bin/opt -O3 $1 -S -o diff1.ll
for i in $(seq 1 10);
do
    bin/opt -O3 $1 -S -o diff2.ll
    diff -q diff1.ll diff2.ll
    if [ $? -ne 0 ]; then
        exit 0
    fi
done

exit 1

Version1:

; ModuleID = 'reduced.ll'
source_filename = "reduced.ll"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

; Function Attrs: mustprogress nofree nounwind willreturn memory(write, argmem: none, inaccessiblemem: readwrite)
define noalias noundef ptr @Vec_PtrAllocExact(i32 %0) local_unnamed_addr #0 {
  %2 = tail call dereferenceable_or_null(16) ptr @malloc(i64 16)
  %3 = getelementptr i8, ptr %2, i64 4
  store i32 0, ptr %3, align 4
  store i32 %0, ptr %2, align 8
  %4 = getelementptr i8, ptr %2, i64 8
  store ptr null, ptr %4, align 8
  ret ptr %2
}

; Function Attrs: nofree nounwind memory(readwrite, argmem: none)
define noalias noundef ptr @Ptr_AbcDeriveNtk() local_unnamed_addr #1 {
  %1 = tail call dereferenceable_or_null(16) ptr @malloc(i64 16)
  %2 = getelementptr i8, ptr %1, i64 8
  store ptr null, ptr %2, align 8
  %calloc = tail call dereferenceable_or_null(16) ptr @calloc(i64 1, i64 16)
  store volatile ptr %calloc, ptr %1, align 8
  ret ptr null
}

; Function Attrs: mustprogress nofree nounwind willreturn allockind("alloc,uninitialized") allocsize(0) memory(inaccessiblemem: readwrite)
declare noalias noundef ptr @malloc(i64 noundef) local_unnamed_addr #2

; Function Attrs: nofree nounwind willreturn allockind("alloc,zeroed") allocsize(0,1) memory(inaccessiblemem: readwrite)
declare noalias noundef ptr @calloc(i64 noundef, i64 noundef) local_unnamed_addr #3

attributes #0 = { mustprogress nofree nounwind willreturn memory(write, argmem: none, inaccessiblemem: readwrite) }
attributes #1 = { nofree nounwind memory(readwrite, argmem: none) }
attributes #2 = { mustprogress nofree nounwind willreturn allockind("alloc,uninitialized") allocsize(0) memory(inaccessiblemem: readwrite) "alloc-family"="malloc" }
attributes #3 = { nofree nounwind willreturn allockind("alloc,zeroed") allocsize(0,1) memory(inaccessiblemem: readwrite) "alloc-family"="malloc" }

Version2:

; ModuleID = 'reduced.ll'
source_filename = "reduced.ll"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

; Function Attrs: mustprogress nofree nounwind willreturn memory(write, argmem: none, inaccessiblemem: readwrite)
define noalias noundef ptr @Vec_PtrAllocExact(i32 %0) local_unnamed_addr #0 {
  %2 = tail call dereferenceable_or_null(16) ptr @malloc(i64 16)
  %3 = getelementptr i8, ptr %2, i64 4
  store i32 0, ptr %3, align 4
  store i32 %0, ptr %2, align 8
  %4 = getelementptr i8, ptr %2, i64 8
  store ptr null, ptr %4, align 8
  ret ptr %2
}

; Function Attrs: nofree nounwind memory(readwrite, argmem: none)
define noalias noundef ptr @Ptr_AbcDeriveNtk() local_unnamed_addr #1 {
  %1 = tail call dereferenceable_or_null(16) ptr @malloc(i64 16)
  %2 = getelementptr i8, ptr %1, i64 4
  store i32 0, ptr %2, align 4
  %3 = getelementptr i8, ptr %1, i64 8
  store ptr null, ptr %3, align 8
  store i32 0, ptr %1, align 4
  %calloc = tail call dereferenceable_or_null(16) ptr @calloc(i64 1, i64 16)
  store volatile ptr %calloc, ptr %1, align 8
  ret ptr null
}

; Function Attrs: mustprogress nofree nounwind willreturn allockind("alloc,uninitialized") allocsize(0) memory(inaccessiblemem: readwrite)
declare noalias noundef ptr @malloc(i64 noundef) local_unnamed_addr #2

; Function Attrs: nofree nounwind willreturn allockind("alloc,zeroed") allocsize(0,1) memory(inaccessiblemem: readwrite)
declare noalias noundef ptr @calloc(i64 noundef, i64 noundef) local_unnamed_addr #3

attributes #0 = { mustprogress nofree nounwind willreturn memory(write, argmem: none, inaccessiblemem: readwrite) }
attributes #1 = { nofree nounwind memory(readwrite, argmem: none) }
attributes #2 = { mustprogress nofree nounwind willreturn allockind("alloc,uninitialized") allocsize(0) memory(inaccessiblemem: readwrite) "alloc-family"="malloc" }
attributes #3 = { nofree nounwind willreturn allockind("alloc,zeroed") allocsize(0,1) memory(inaccessiblemem: readwrite) "alloc-family"="malloc" }

I found this bug in my benchmark.
See also dtcxzyw/llvm-opt-benchmark#334.

cc @nikic

[llvmbot]

@llvm/issue-subscribers-bug

Author: Yingwei Zheng (dtcxzyw)

Reduced test case: ``` target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128" target triple = "x86_64-pc-linux-gnu"

define ptr @Vec_PtrAllocExact(i32 %0) {
%2 = call ptr @malloc(i64 16)
%3 = getelementptr i8, ptr %2, i64 4
store i32 0, ptr %3, align 4
store i32 %0, ptr %2, align 8
%4 = getelementptr i8, ptr %2, i64 8
store ptr null, ptr %4, align 8
ret ptr %2
}

define internal void @Vec_PtrPush(ptr %0, ptr %1) {
store i32 0, ptr %0, align 4
ret void
}

declare i32 @Vec_PtrSize()

declare ptr @Abc_NtkObj()

declare ptr @Ptr_AbcDeriveOutputs()

define ptr @Ptr_AbcDeriveNtk() {
%1 = call ptr @Vec_PtrAllocExact(i32 1)
call void @Vec_PtrPush(ptr %1, ptr null)
%2 = call ptr @Vec_PtrAllocExact(i32 0)
store volatile ptr %2, ptr %1, align 8
ret ptr null
}

declare ptr @malloc(i64)

Reproduction script:

#!/usr/bin/bash

bin/opt -O3 $1 -S -o diff1.ll
for i in $(seq 1 10);
do
bin/opt -O3 $1 -S -o diff2.ll
diff -q diff1.ll diff2.ll
if [ $? -ne 0 ]; then
exit 0
fi
done

exit 1

Version1:

; ModuleID = 'reduced.ll'
source_filename = "reduced.ll"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

; Function Attrs: mustprogress nofree nounwind willreturn memory(write, argmem: none, inaccessiblemem: readwrite)
define noalias noundef ptr @Vec_PtrAllocExact(i32 %0) local_unnamed_addr #0 {
%2 = tail call dereferenceable_or_null(16) ptr @malloc(i64 16)
%3 = getelementptr i8, ptr %2, i64 4
store i32 0, ptr %3, align 4
store i32 %0, ptr %2, align 8
%4 = getelementptr i8, ptr %2, i64 8
store ptr null, ptr %4, align 8
ret ptr %2
}

; Function Attrs: nofree nounwind memory(readwrite, argmem: none)
define noalias noundef ptr @Ptr_AbcDeriveNtk() local_unnamed_addr #1 {
%1 = tail call dereferenceable_or_null(16) ptr @malloc(i64 16)
%2 = getelementptr i8, ptr %1, i64 8
store ptr null, ptr %2, align 8
%calloc = tail call dereferenceable_or_null(16) ptr @calloc(i64 1, i64 16)
store volatile ptr %calloc, ptr %1, align 8
ret ptr null
}

; Function Attrs: mustprogress nofree nounwind willreturn allockind("alloc,uninitialized") allocsize(0) memory(inaccessiblemem: readwrite)
declare noalias noundef ptr @malloc(i64 noundef) local_unnamed_addr #2

; Function Attrs: nofree nounwind willreturn allockind("alloc,zeroed") allocsize(0,1) memory(inaccessiblemem: readwrite)
declare noalias noundef ptr @calloc(i64 noundef, i64 noundef) local_unnamed_addr #3

attributes #0 = { mustprogress nofree nounwind willreturn memory(write, argmem: none, inaccessiblemem: readwrite) }
attributes #1 = { nofree nounwind memory(readwrite, argmem: none) }
attributes #2 = { mustprogress nofree nounwind willreturn allockind("alloc,uninitialized") allocsize(0) memory(inaccessiblemem: readwrite) "alloc-family"="malloc" }
attributes #3 = { nofree nounwind willreturn allockind("alloc,zeroed") allocsize(0,1) memory(inaccessiblemem: readwrite) "alloc-family"="malloc" }

Version2:

; ModuleID = 'reduced.ll'
source_filename = "reduced.ll"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

; Function Attrs: mustprogress nofree nounwind willreturn memory(write, argmem: none, inaccessiblemem: readwrite)
define noalias noundef ptr @Vec_PtrAllocExact(i32 %0) local_unnamed_addr #0 {
%2 = tail call dereferenceable_or_null(16) ptr @malloc(i64 16)
%3 = getelementptr i8, ptr %2, i64 4
store i32 0, ptr %3, align 4
store i32 %0, ptr %2, align 8
%4 = getelementptr i8, ptr %2, i64 8
store ptr null, ptr %4, align 8
ret ptr %2
}

; Function Attrs: nofree nounwind memory(readwrite, argmem: none)
define noalias noundef ptr @Ptr_AbcDeriveNtk() local_unnamed_addr #1 {
%1 = tail call dereferenceable_or_null(16) ptr @malloc(i64 16)
%2 = getelementptr i8, ptr %1, i64 4
store i32 0, ptr %2, align 4
%3 = getelementptr i8, ptr %1, i64 8
store ptr null, ptr %3, align 8
store i32 0, ptr %1, align 4
%calloc = tail call dereferenceable_or_null(16) ptr @calloc(i64 1, i64 16)
store volatile ptr %calloc, ptr %1, align 8
ret ptr null
}

; Function Attrs: mustprogress nofree nounwind willreturn allockind("alloc,uninitialized") allocsize(0) memory(inaccessiblemem: readwrite)
declare noalias noundef ptr @malloc(i64 noundef) local_unnamed_addr #2

; Function Attrs: nofree nounwind willreturn allockind("alloc,zeroed") allocsize(0,1) memory(inaccessiblemem: readwrite)
declare noalias noundef ptr @calloc(i64 noundef, i64 noundef) local_unnamed_addr #3

attributes #0 = { mustprogress nofree nounwind willreturn memory(write, argmem: none, inaccessiblemem: readwrite) }
attributes #1 = { nofree nounwind memory(readwrite, argmem: none) }
attributes #2 = { mustprogress nofree nounwind willreturn allockind("alloc,uninitialized") allocsize(0) memory(inaccessiblemem: readwrite) "alloc-family"="malloc" }
attributes #3 = { nofree nounwind willreturn allockind("alloc,zeroed") allocsize(0,1) memory(inaccessiblemem: readwrite) "alloc-family"="malloc" }

I found this bug in my [benchmark](https://github.com/dtcxzyw/llvm-opt-benchmark/blob/main/bench/abc/original/bacPtrAbc.c.ll).
See also https://github.com/dtcxzyw/llvm-opt-benchmark/issues/334.

cc @<!-- -->nikic
</details>

[nikic]

Annoyingly the difference does not occur when adding -print-after-all :(

[nikic]

I believe the problem is that tryFoldIntoCalloc creates a new MemoryAccess, which may have the same address as a previously deleted MemoryAccess that is part of SkippedStores.