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

[giordano]

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]

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]

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]

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