Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Iterating over eachindex doesn't remove out-of-bounds error #65

Closed
giordano opened this issue Oct 7, 2024 · 3 comments · Fixed by #68
Closed

Iterating over eachindex doesn't remove out-of-bounds error #65

giordano opened this issue Oct 7, 2024 · 3 comments · Fixed by #68

Comments

@giordano
Copy link
Collaborator

giordano commented Oct 7, 2024

Maybe this is something deep in Julia internals, but iterating over eachindex of an array doesn't help removing bounds errors:

julia> code_llvm((Vector{Float64},)) do v
           for idx in eachindex(v)
               v[idx] = idx
           end
       end
LLVM IR 
; Function Signature: var"#68"(Array{Float64, 1})
;  @ REPL[37]:2 within `#68`
define void @"julia_#68_4002"(ptr noundef nonnull align 8 dereferenceable(24) %"v::Array") #0 {
top:
; ┌ @ abstractarray.jl:321 within `eachindex`
; │┌ @ abstractarray.jl:137 within `axes1`
; ││┌ @ abstractarray.jl:98 within `axes`
; │││┌ @ array.jl:194 within `size`
      %"v::Array.size_ptr" = getelementptr inbounds i8, ptr %"v::Array", i64 16
      %"v::Array.size.0.copyload" = load i64, ptr %"v::Array.size_ptr", align 8
; └└└└
; ┌ @ range.jl:911 within `iterate`
; │┌ @ range.jl:688 within `isempty`
; ││┌ @ operators.jl:425 within `>`
; │││┌ @ int.jl:83 within `<`
      %0 = icmp slt i64 %"v::Array.size.0.copyload", 1
; └└└└
  br i1 %0, label %L45, label %L13.preheader17

L13.preheader17:                                  ; preds = %top
  %memoryref_data = load ptr, ptr %"v::Array", align 8
;  @ REPL[37]:3 within `#68`
; ┌ @ array.jl:984 within `setindex!`
   %invariant.gep = getelementptr i8, ptr %memoryref_data, i64 -8
   %min.iters.check = icmp ult i64 %"v::Array.size.0.copyload", 8
   br i1 %min.iters.check, label %scalar.ph, label %vector.ph

vector.ph:                                        ; preds = %L13.preheader17
   %n.vec = and i64 %"v::Array.size.0.copyload", 9223372036854775800
   %ind.end = or disjoint i64 %n.vec, 1
   br label %vector.body

vector.body:                                      ; preds = %vector.body, %vector.ph
   %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
   %vec.ind = phi <2 x i64> [ <i64 1, i64 2>, %vector.ph ], [ %vec.ind.next, %vector.body ]
   %step.add = add <2 x i64> %vec.ind, <i64 2, i64 2>
   %step.add22 = add <2 x i64> %vec.ind, <i64 4, i64 4>
   %step.add23 = add <2 x i64> %vec.ind, <i64 6, i64 6>
; │ @ array.jl:985 within `setindex!`
   %offset.idx = shl i64 %index, 3
   %1 = or disjoint i64 %offset.idx, 8
; │┌ @ number.jl:7 within `convert`
; ││┌ @ float.jl:239 within `Float64`
     %2 = sitofp <2 x i64> %vec.ind to <2 x double>
     %3 = sitofp <2 x i64> %step.add to <2 x double>
     %4 = sitofp <2 x i64> %step.add22 to <2 x double>
     %5 = sitofp <2 x i64> %step.add23 to <2 x double>
; │└└
   %6 = getelementptr i8, ptr %invariant.gep, i64 %1
   %7 = getelementptr double, ptr %6, i64 2
   %8 = getelementptr double, ptr %6, i64 4
   %9 = getelementptr double, ptr %6, i64 6
   store <2 x double> %2, ptr %6, align 8
   store <2 x double> %3, ptr %7, align 8
   store <2 x double> %4, ptr %8, align 8
   store <2 x double> %5, ptr %9, align 8
   %index.next = add nuw i64 %index, 8
   %vec.ind.next = add <2 x i64> %vec.ind, <i64 8, i64 8>
   %10 = icmp eq i64 %index.next, %n.vec
   br i1 %10, label %middle.block, label %vector.body

middle.block:                                     ; preds = %vector.body
; └
;  @ REPL[37]:4 within `#68`
  %cmp.n = icmp eq i64 %"v::Array.size.0.copyload", %n.vec
  br i1 %cmp.n, label %L45, label %scalar.ph

scalar.ph:                                        ; preds = %middle.block, %L13.preheader17
  %bc.resume.val = phi i64 [ %ind.end, %middle.block ], [ 1, %L13.preheader17 ]
;  @ REPL[37]:3 within `#68`
; ┌ @ array.jl:984 within `setindex!`
   br label %L29

L29:                                              ; preds = %L29, %scalar.ph
   %value_phi3 = phi i64 [ %12, %L29 ], [ %bc.resume.val, %scalar.ph ]
; │ @ array.jl:985 within `setindex!`
   %memoryref_offset = shl i64 %value_phi3, 3
; │┌ @ number.jl:7 within `convert`
; ││┌ @ float.jl:239 within `Float64`
     %11 = sitofp i64 %value_phi3 to double
; │└└
   %gep = getelementptr i8, ptr %invariant.gep, i64 %memoryref_offset
   store double %11, ptr %gep, align 8
; └
;  @ REPL[37]:4 within `#68`
; ┌ @ range.jl:915 within `iterate`
   %12 = add nuw i64 %value_phi3, 1
; └
  %13 = icmp ult i64 %value_phi3, %"v::Array.size.0.copyload"
  br i1 %13, label %L29, label %L45

L45:                                              ; preds = %L29, %middle.block, %top
  ret void
}
julia> code_llvm((FixedSizeVector{Float64,Memory{Float64}},)) do v
           for idx in eachindex(v)
               v[idx] = idx
           end
       end
Details 
; Function Signature: var"#65"(FixedSizeArrays.FixedSizeArray{Float64, 1, Memory{Float64}})
;  @ REPL[36]:2 within `#65`
define void @"julia_#65_3999"(ptr nocapture noundef nonnull readonly align 8 dereferenceable(16) %"v::FixedSizeArray", ptr nocapture readonly %.roots.v) #0 {
top:
  %pgcstack = call ptr inttoptr (i64 4298882828 to ptr)(i64 4298882864) #11
  %memoryref_mem = load ptr, ptr %.roots.v, align 8
; ┌ @ abstractarray.jl:321 within `eachindex`
; │┌ @ abstractarray.jl:137 within `axes1`
; ││┌ @ abstractarray.jl:98 within `axes`
; │││┌ @ /Users/mose/.julia/dev/FixedSizeArrays/src/FixedSizeArrays.jl:60 within `size`
; ││││┌ @ Base.jl:49 within `getproperty`
       %0 = getelementptr inbounds i8, ptr %"v::FixedSizeArray", i64 8
; └└└└└
; ┌ @ range.jl:911 within `iterate`
; │┌ @ range.jl:688 within `isempty`
; ││┌ @ operators.jl:425 within `>`
; │││┌ @ int.jl:83 within `<`
      %.unbox = load i64, ptr %0, align 8
      %1 = icmp slt i64 %.unbox, 1
; └└└└
  br i1 %1, label %L33, label %L13.preheader

L13.preheader:                                    ; preds = %top
  %memory_data_ptr = getelementptr inbounds { i64, ptr }, ptr %memoryref_mem, i64 0, i32 1
  %memoryref_data = load ptr, ptr %memory_data_ptr, align 8
  %memory_len = load i64, ptr %memoryref_mem, align 8
  %memory_len.fr = freeze i64 %memory_len
  %2 = shl i64 %memory_len.fr, 1
  %memoryref_bytelen = shl nuw nsw i64 %memory_len.fr, 3
  %3 = icmp eq i64 %memory_len.fr, 0
;  @ REPL[36]:3 within `#65`
; ┌ @ /Users/mose/.julia/dev/FixedSizeArrays/src/FixedSizeArrays.jl:58 within `setindex!` @ genericmemory.jl:241
   br i1 %3, label %oob, label %L13.preheader.split

L13.preheader.split:                              ; preds = %L13.preheader
; │ @ /Users/mose/.julia/dev/FixedSizeArrays/src/FixedSizeArrays.jl:58 within `setindex!` @ genericmemory.jl:240
   %smin = call i64 @llvm.smin.i64(i64 %memory_len.fr, i64 %2)
   %4 = sub i64 %2, %smin
   %exit.mainloop.at = call i64 @llvm.umin.i64(i64 %.unbox, i64 %4)
   %.not.not = icmp sgt i64 %2, %memory_len.fr
   br i1 %.not.not, label %L13.preheader25, label %main.pseudo.exit

L13.preheader25:                                  ; preds = %L13.preheader.split
   %5 = add nuw nsw i64 %memory_len.fr, 1
   %umax = call i64 @llvm.umax.i64(i64 %exit.mainloop.at, i64 1)
   %6 = add nsw i64 %umax, -1
   %umin = call i64 @llvm.umin.i64(i64 %memory_len.fr, i64 %6)
   %min.iters.check = icmp ult i64 %umin, 8
   br i1 %min.iters.check, label %scalar.ph, label %vector.ph

vector.ph:                                        ; preds = %L13.preheader25
   %7 = add nuw i64 %umin, 1
   %n.mod.vf = and i64 %7, 7
   %8 = icmp eq i64 %n.mod.vf, 0
   %9 = select i1 %8, i64 8, i64 %n.mod.vf
   %n.vec = sub i64 %7, %9
   %ind.end = add i64 %n.vec, 1
   br label %vector.body

vector.body:                                      ; preds = %vector.body, %vector.ph
   %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
   %vec.ind = phi <2 x i64> [ <i64 1, i64 2>, %vector.ph ], [ %vec.ind.next, %vector.body ]
   %step.add = add <2 x i64> %vec.ind, <i64 2, i64 2>
   %step.add36 = add <2 x i64> %vec.ind, <i64 4, i64 4>
   %step.add37 = add <2 x i64> %vec.ind, <i64 6, i64 6>
   %offset.idx = shl i64 %index, 3
   %10 = or disjoint i64 %offset.idx, 8
; │ @ /Users/mose/.julia/dev/FixedSizeArrays/src/FixedSizeArrays.jl:58 within `setindex!` @ genericmemory.jl:239
; │┌ @ number.jl:7 within `convert`
; ││┌ @ float.jl:239 within `Float64`
     %11 = sitofp <2 x i64> %vec.ind to <2 x double>
     %12 = sitofp <2 x i64> %step.add to <2 x double>
     %13 = sitofp <2 x i64> %step.add36 to <2 x double>
     %14 = sitofp <2 x i64> %step.add37 to <2 x double>
; │└└
; │ @ /Users/mose/.julia/dev/FixedSizeArrays/src/FixedSizeArrays.jl:58 within `setindex!` @ genericmemory.jl:241
   %15 = getelementptr i8, ptr %memoryref_data, i64 %10
   %16 = getelementptr i8, ptr %15, i64 -8
   %17 = getelementptr i8, ptr %15, i64 8
   %18 = getelementptr i8, ptr %15, i64 24
   %19 = getelementptr i8, ptr %15, i64 40
   store <2 x double> %11, ptr %16, align 8
   store <2 x double> %12, ptr %17, align 8
   store <2 x double> %13, ptr %18, align 8
   store <2 x double> %14, ptr %19, align 8
   %index.next = add nuw i64 %index, 8
   %vec.ind.next = add <2 x i64> %vec.ind, <i64 8, i64 8>
   %20 = icmp eq i64 %index.next, %n.vec
   br i1 %20, label %scalar.ph, label %vector.body

scalar.ph:                                        ; preds = %vector.body, %L13.preheader25
   %bc.resume.val = phi i64 [ 1, %L13.preheader25 ], [ %ind.end, %vector.body ]
; │ @ /Users/mose/.julia/dev/FixedSizeArrays/src/FixedSizeArrays.jl:58 within `setindex!` @ genericmemory.jl:240
   br label %L13

L13:                                              ; preds = %idxend, %scalar.ph
   %value_phi3 = phi i64 [ %23, %idxend ], [ %bc.resume.val, %scalar.ph ]
   %exitcond.not = icmp eq i64 %value_phi3, %5
   br i1 %exitcond.not, label %oob, label %idxend

L33:                                              ; preds = %idxend.postloop, %main.exit.selector, %top
; └
;  @ REPL[36]:4 within `#65`
  ret void

oob:                                              ; preds = %L13.postloop, %L13, %L13.preheader
  %.us-phi = phi i64 [ 1, %L13.preheader ], [ %value_phi3.postloop, %L13.postloop ], [ %5, %L13 ]
;  @ REPL[36]:3 within `#65`
; ┌ @ /Users/mose/.julia/dev/FixedSizeArrays/src/FixedSizeArrays.jl:58 within `setindex!` @ genericmemory.jl:240
   %ptls_field = getelementptr inbounds i8, ptr %pgcstack, i64 16
   %ptls_load = load ptr, ptr %ptls_field, align 8
   %"box::GenericMemoryRef" = call noalias nonnull align 8 dereferenceable(32) ptr @ijl_gc_small_alloc(ptr %ptls_load, i32 616, i32 32, i64 5244796336) #9
   %"box::GenericMemoryRef.tag_addr" = getelementptr inbounds i64, ptr %"box::GenericMemoryRef", i64 -1
   store atomic i64 5244796336, ptr %"box::GenericMemoryRef.tag_addr" unordered, align 8
   store ptr %memoryref_data, ptr %"box::GenericMemoryRef", align 8
   %.repack17 = getelementptr inbounds { ptr, ptr }, ptr %"box::GenericMemoryRef", i64 0, i32 1
   store ptr %memoryref_mem, ptr %.repack17, align 8
   call void @ijl_bounds_error_int(ptr nonnull %"box::GenericMemoryRef", i64 %.us-phi)
   unreachable

idxend:                                           ; preds = %L13
   %memoryref_offset = shl i64 %value_phi3, 3
; │ @ /Users/mose/.julia/dev/FixedSizeArrays/src/FixedSizeArrays.jl:58 within `setindex!` @ genericmemory.jl:239
; │┌ @ number.jl:7 within `convert`
; ││┌ @ float.jl:239 within `Float64`
     %21 = sitofp i64 %value_phi3 to double
; │└└
; │ @ /Users/mose/.julia/dev/FixedSizeArrays/src/FixedSizeArrays.jl:58 within `setindex!` @ genericmemory.jl:241
   %22 = getelementptr i8, ptr %memoryref_data, i64 %memoryref_offset
   %memoryref_data11 = getelementptr i8, ptr %22, i64 -8
   store double %21, ptr %memoryref_data11, align 8
; └
;  @ REPL[36]:4 within `#65`
; ┌ @ range.jl:915 within `iterate`
   %23 = add nuw nsw i64 %value_phi3, 1
; └
  %.not32 = icmp ult i64 %value_phi3, %exit.mainloop.at
  br i1 %.not32, label %L13, label %main.exit.selector

main.exit.selector:                               ; preds = %idxend
  %24 = icmp ult i64 %value_phi3, %.unbox
  br i1 %24, label %main.pseudo.exit, label %L33

main.pseudo.exit:                                 ; preds = %main.exit.selector, %L13.preheader.split
  %value_phi3.copy = phi i64 [ 1, %L13.preheader.split ], [ %23, %main.exit.selector ]
  br label %L13.postloop

L13.postloop:                                     ; preds = %idxend.postloop, %main.pseudo.exit
  %value_phi3.postloop = phi i64 [ %27, %idxend.postloop ], [ %value_phi3.copy, %main.pseudo.exit ]
;  @ REPL[36]:3 within `#65`
; ┌ @ /Users/mose/.julia/dev/FixedSizeArrays/src/FixedSizeArrays.jl:58 within `setindex!` @ genericmemory.jl:240
   %memoryref_offset.postloop = add nsw i64 %value_phi3.postloop, -1
   %25 = add i64 %memory_len.fr, %memoryref_offset.postloop
   %memoryref_ovflw.not.postloop = icmp ult i64 %25, %2
   %memoryref_byteoffset.postloop = shl i64 %memoryref_offset.postloop, 3
   %memoryref_isinbounds.postloop = icmp ult i64 %memoryref_byteoffset.postloop, %memoryref_bytelen
   %"memoryref_isinbounds&notovflw.postloop" = and i1 %memoryref_ovflw.not.postloop, %memoryref_isinbounds.postloop
   br i1 %"memoryref_isinbounds&notovflw.postloop", label %idxend.postloop, label %oob

idxend.postloop:                                  ; preds = %L13.postloop
; │ @ /Users/mose/.julia/dev/FixedSizeArrays/src/FixedSizeArrays.jl:58 within `setindex!` @ genericmemory.jl:239
; │┌ @ number.jl:7 within `convert`
; ││┌ @ float.jl:239 within `Float64`
     %26 = sitofp i64 %value_phi3.postloop to double
; │└└
; │ @ /Users/mose/.julia/dev/FixedSizeArrays/src/FixedSizeArrays.jl:58 within `setindex!` @ genericmemory.jl:241
   %memoryref_data11.postloop = getelementptr inbounds i8, ptr %memoryref_data, i64 %memoryref_byteoffset.postloop
   store double %26, ptr %memoryref_data11.postloop, align 8
; └
;  @ REPL[36]:4 within `#65`
; ┌ @ range.jl:915 within `iterate`
; │┌ @ promotion.jl:639 within `==`
    %.not.not.postloop = icmp eq i64 %value_phi3.postloop, %.unbox
; │└
   %27 = add nuw nsw i64 %value_phi3.postloop, 1
; └
  br i1 %.not.not.postloop, label %L33, label %L13.postloop
}
@giordano giordano changed the title Iterating over eachindex doesn't remove oit-of-bounds error Iterating over eachindex doesn't remove out-of-bounds error Oct 7, 2024
@giordano
Copy link
Collaborator Author

giordano commented Oct 7, 2024

Based on the debuginfo shown in the LLVM IR above, I believe this happens because the method setindex!(A::Memory{T}, x, i1::Int) always does bound checking unless there's an explicit @inbounds. Instead the method for Array does defensive bounds checks and then an unsafe memory set, with the bounds checks potentially lifted if guaranteed from outside:

function setindex!(A::Array{T}, x, i::Int) where {T}
    @_noub_if_noinbounds_meta
    @boundscheck (i - 1)%UInt < length(A)%UInt || throw_boundserror(A, (i,))
    memoryrefset!(memoryrefnew(A.ref, i, false), x isa T ? x : convert(T,x)::T, :not_atomic, false)
    return A
end

Changing our definition of setindex! to

function Base.setindex!(A::FixedSizeArray{T}, x, i::Int) where {T}
    Base.@_noub_if_noinbounds_meta
    @boundscheck (i - 1)%UInt < length(A)%UInt || Base.throw_boundserror(A, (i,))
    @inbounds A.mem[i] = x
    return A
end

does seem to help quite a bit. I'm not sure what Base.@_noub_if_noinbounds_meta exactly does though (maybe we can just remove it?)

@nsajko
Copy link
Collaborator

nsajko commented Oct 7, 2024

Pretty sure Base.@assume_effects :noub_if_noinbounds is Base.@_noub_if_noinbounds_meta for users. I guess it's like Base.@assume_effects :noub, but it only has an effect when @inbounds isn't in effect.

:noub is required for :foldable, so we probably want to have it.

@giordano giordano mentioned this issue Oct 7, 2024
Merged
@giordano
Copy link
Collaborator Author

giordano commented Oct 7, 2024 •
edited
Loading

I opened the PR before reading your message here, sorry! Do suggest improvements about the effect macros (I'm not particularly familiar with all their meanings), but as far as I can tell the proposed change is relatively safe, and I'm pretty sure the line

    memoryrefset!(memoryrefnew(A.ref, i, false), x isa T ? x : convert(T,x)::T, :not_atomic, false)

in the setindex!(::Array) method is basically equivalent to

    @inbounds A.ref[i] = x

(maybe not true when using --check-bounds=yes?). Edit: comparing code_llvm((FixedSizeVector{Float64,Memory{Float64}},)) do v @inbounds(v[1] = 1) end vs code_llvm((Vector{Float64},)) do v @inbounds(v[1] = 1) end with julia --check-bounds=yes I don't think there's a difference in this situation, they both still do bounds checks, so I'm more convinced the two lines are equivalent.

Edit: on a closer inspection, I believe that for a FixedSizeArray, which uses a Memory instead of a MemoryRef, the actually equivalent code would be the slightly convoluted

    Base.memoryrefset!(Base.memoryrefnew(Base.memoryrefnew(A.mem), i, false), x isa T ? x : convert(T,x)::T, :not_atomic, false)

but when inbounds is propagated correctly then this should be pretty much the same as

    @inbounds A.ref[i] = x

@nsajko nsajko mentioned this issue Oct 13, 2024
Open
This was referenced Oct 13, 2024
Open
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Automatically skip boundschecks in setindex! when safe to do so JuliaArrays/FixedSizeArrays.jl
2 participants
@giordano @nsajko