`julia.gc_preserve_end: Instruction does not dominate all uses!` when testing some packages

[KristofferC]

When testing:

"Hecke" "HiddenMarkovModels" "Rimu"

an assertion similar to

Instruction does not dominate all uses!
  %52 = call token (...) @llvm.julia.gc_preserve_begin({} addrspace(10)* nonnull %43), !dbg !78
  call void @llvm.julia.gc_preserve_end(token %52), !dbg !93
Instruction does not dominate all uses!
  %52 = call token (...) @llvm.julia.gc_preserve_begin({} addrspace(10)* nonnull %43), !dbg !78
  call void @llvm.julia.gc_preserve_end(token %52), !dbg !93
Instruction does not dominate all uses!
  %52 = call token (...) @llvm.julia.gc_preserve_begin({} addrspace(10)* nonnull %43), !dbg !78
  call void @llvm.julia.gc_preserve_end(token %52), !dbg !93
julia: /source/src/llvm-alloc-opt.cpp:1250: bool {anonymous}::AllocOpt::runOnFunction(llvm::Function&, llvm::function_ref<llvm::DominatorTree&()>): Assertion `!verifyFunction(F, &errs())' failed.

[24] signal (6.-6): Aborted
in expression starting at /home/pkgeval/.julia/packages/Hecke/r2bEE/system/precompile.jl:20

is hit.

PkgEval log https://s3.amazonaws.com/julialang-reports/nanosoldier/pkgeval/by_hash/c9a32f4_vs_e4ee485/Hecke.primary.log

[maleadt]

Bisected to 310f59019856749fb85bc56a1e3c2e0592a134ad/#49865. That probably just exposes a pre-existing bug, so I'll try to reduce.

[maleadt]

Partially reduced to:

using LinearAlgebra
function backward!(fb, A)
    @views for t in mul!([], A, fb[:])
    end
end
forward_backward!(fb, hmm) = backward!(fb, hmm)
forward_backward_from_loglikelihoods(hmm) = forward_backward!(Matrix(undef, N, T), hmm)

using StaticArrays
A = MMatrix{5,5}(rand(5,5))
forward_backward_from_loglikelihoods(A)

[gbaraldi]

I'm not sure if it's the same thing as in https://github.com/JuliaLang/julia/issues/48918#issuecomment-1460662896 , both have StaticArrays.

[maleadt]

Further reduced:

using LinearAlgebra
abstract type StaticArray{Tuple, T, N} <: AbstractArray{T, N} end
mutable struct MArray{S, T, N, L} <: StaticArray{S, T, N} end
MArray{S,T,N}(x) where {S,T,N} = MArray{S,T,N,1}()
MMatrix{S1, S2, T } = MArray{Tuple{S1, S2}, T, 2}
struct Size{S} end
Size(s) = Size{tuple(s.parameters...)}()
Size(::T) where T<: StaticArray{S} where S= Size(S)
(::Type{Tuple})(::Size{S}) where S = S
function Base.getindex(v::MArray, Int)
    GC.@preserve v unsafe_load0
end
construct_type(::Type{SA}, x) where SA= adapt_eltype(SA, x)
adapt_eltype(::Type{SA}, x) where SA= typeintersect(SA, AbstractArray{eltype(x)})
(T::Type)(a) = convert(T, a)
function convert(::Type{SA}, a) where SA
    SA′ = construct_type(SA, a)
    SA′(0)
end
Base.size(a) = Tuple(Size(a))
Base.IndexStyle(::T) where T<:StaticArray = IndexLinear()
LinearAlgebra.transpose(::StaticArray) = _transpose()
_transpose(StaticArray) = nothing
LinearAlgebra.adjoint(::StaticArray) = _adjoint()
_adjoint(StaticArray) = nothing
function backward!(fb, A)
    @views for t in mul!([], A, fb[:])
    end
end
forward_backward_from_loglikelihoods(hmm) = backward!(Matrix(undef, N, T), hmm)
forward_backward_from_loglikelihoods(MMatrix{5,5}(5))

Requires running an asserts build, with Julia optimizations enabled (i.e. not using -O0) and using --check-bounds=yes. Annoyingly, still bisects to #49865, but at least this should make it easier to fix.

[topolarity]

Hmm, the MWE doesn't reproduce for me. Any idea what I've done wrong?

$ cat test.jl
using LinearAlgebra
function backward!(fb, A)
    @views for t in mul!([], A, fb[:])
    end
end
forward_backward!(fb, hmm) = backward!(fb, hmm)
forward_backward_from_loglikelihoods(hmm) = forward_backward!(Matrix(undef, N, T), hmm)

using StaticArrays
A = MMatrix{5,5}(rand(5,5))
forward_backward_from_loglikelihoods(A)

$ manyjulias --asserts 310f590 test.jl
[ Info: Updating Julia repository...
[ Info: Translated requested revision 310f590 to commit 310f59019856749fb85bc56a1e3c2e0592a134ad
A       1682 files
D       0 files
M       0 files
Extracted 'julia-1_10_0-DEV_1250:310f59019856749fb85bc56a1e3c2e0592a134ad'
ERROR: LoadError: UndefVarError: `N` not defined
Stacktrace:
 [1] forward_backward_from_loglikelihoods(hmm::MMatrix{5, 5, Float64, 25})
   @ Main ~/julia/test.jl:7
 [2] top-level scope
   @ ~/julia/test.jl:11
in expression starting at /home/topolarity/julia/test.jl:11

[gbaraldi]

Are you running with --checkbounds=yes?

[topolarity]

Thanks @gbaraldi , that was it.

The bad transformation happens in IRCEPass. Here's a relevant portion of the diff:

@@ -2055,68 +2055,104 @@
   %349 = bitcast {} addrspace(10)* %"C::Array" to {} addrspace(10)* addrspace(10)*
   %350 = addrspacecast {} addrspace(10)* addrspace(10)* %349 to {} addrspace(10)* addrspace(11)*
   %351 = getelementptr inbounds {} addrspace(10)*, {} addrspace(10)* addrspace(11)* %350, i64 5
+  %smin = call i64 @llvm.smin.i64(i64 %"B::SubArray.indices_ptr.<unknown field>_ptr.indices_ptr.stop_ptr.unbox585", i64 0), !dbg !489
+  %352 = sub i64 %"B::SubArray.indices_ptr.<unknown field>_ptr.indices_ptr.stop_ptr.unbox585", %smin, !dbg !489
+  %smax = call i64 @llvm.smax.i64(i64 %smin, i64 -1), !dbg !489
+  %353 = add nsw i64 %smax, 1, !dbg !489
+  %354 = mul i64 %352, %353, !dbg !489
+  %exit.mainloop.at = call i64 @llvm.umin.i64(i64 %value_phi586, i64 %354), !dbg !489
+  %355 = icmp ult i64 0, %exit.mainloop.at, !dbg !489
+  br i1 %355, label %L1634.preheader1496, label %main.pseudo.exit, !dbg !489
+
+L1634.preheader1496:                              ; preds = %L1634.preheader
   br label %L1634, !dbg !489

Full IR: before_irce.ll.txt after_irce.ll.txt diff.ll.patch

[topolarity]

Looks to be a duplicate of https://github.com/JuliaLang/julia/issues/48918 (thanks to @gbaraldi for the heads up)

Reduced ir (fails with opt-15 ir.ll --irce):

; ModuleID = 'bugpoint-reduced-simplified.bc'
source_filename = "_generic_matvecmul!"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:10:11:12:13"
target triple = "x86_64-pc-linux-gnu"

define swiftcc void @"julia__generic_matvecmul!_1420"() #0 {
top:
  br label %L1618

L1618:                                            ; preds = %top
  %0 = icmp slt i64 undef, 1
  br i1 %0, label %L1843, label %L1634.preheader

L1634.preheader:                                  ; preds = %L1618
  br label %L1634

L1634:                                            ; preds = %L1830, %L1634.preheader
  %value_phi590 = phi i64 [ %5, %L1830 ], [ 1, %L1634.preheader ]
  %1 = add i64 %value_phi590, -1
  %.not1038 = icmp ult i64 %1, undef
  br i1 %.not1038, label %L1655, label %L1652

L1652:                                            ; preds = %L1634
  unreachable

L1655:                                            ; preds = %L1634
  %2 = call token (...) @llvm.julia.gc_preserve_begin({} addrspace(10)* nonnull undef)
  %3 = call token (...) @llvm.julia.gc_preserve_begin({} addrspace(10)* nonnull undef)
  %4 = call token (...) @llvm.julia.gc_preserve_begin({} addrspace(10)* nonnull undef)
  br label %pass625

L1711:                                            ; preds = %pass625
  call void @llvm.julia.gc_preserve_end(token %4)
  unreachable

L1714:                                            ; preds = %pass625
  br label %L1830

L1830:                                            ; preds = %L1714
  %.not1049.not = icmp eq i64 %value_phi590, undef
  %5 = add i64 %value_phi590, 1
  br i1 %.not1049.not, label %L1843.loopexit1105, label %L1634

L1843.loopexit1105:                               ; preds = %L1830
  unreachable

L1843:                                            ; preds = %L1618
  ret void

pass625:                                          ; preds = %L1655
  br i1 undef, label %L1711, label %L1714
}

declare token @llvm.julia.gc_preserve_begin(...)

declare void @llvm.julia.gc_preserve_end(token)

attributes #0 = { "probe-stack"="inline-asm" }

!llvm.module.flags = !{!0}

!0 = !{i32 2, !"julia.debug_level", i32 1}

[topolarity]

Upstream bug filed: https://github.com/llvm/llvm-project/issues/63984

[JeffBezanson]

Triage decided this is a pre-existing bug, and only shows symptoms when running with assertions, so does not need to be release-blocking. We should still fix it eventually though.

[topolarity]

Why is this assigned to me?

[vchuravy]

Sorry! Since you looked at this last you had emotionally licked the cookie ;) and I didn't want to presume that this wasn't on your todo list. I will try to have a look at this soon.

[topolarity]

Ah no, all yours 🙂 I was just happy to have the bug identified upstream