IRCE appreciation and gripes (inductive range check elimination)

IRCE is an LLVM pass that aims to loop unswitch range checks. As such, its goal is to reduce the performance impact of bounds checks – especially missing @inbounds should no longer prevent vectorization.

To give a simple example:

function sumRange(arr, start, stop)
  s = zero(eltype(arr))
  for idx = start:stop
    s += arr[idx]
  end
  s
end

It used to be that this checked bounds on every loop iteration, which prevented vectorization and therefore had a huge performance impact (4x+).

Therefore, the old way of writing julia code was:

Base.@propagate_inbounds function sumRange(arr, start, stop)
  @boundscheck checkbounds(arr, start:stop)
  s = zero(eltype(arr))
  @inbounds for idx = start:stop
    s += arr[idx]
  end
  s
end

This is annoying. Enter IRCE, which uses the fact that the loop index and the boundschecks implied by the access are monotone, in order to hoist the bounds-checks out of the loop.

First of all, huge kudos to pchintalapudi who made this work in 2021 (+20/-5 lines over 2 PRs here and here). I had tried the same some years ago, and I failed miserably.

If reliable, then this simple change in the optimization pipeline can change the face of the language. :heart:

It seems that this change has flown under the radar for most people. Really, try out how necessary all the @inbounds are – you might be pleasantly surprised.


That being said, it doesn’t work reliably anymore on master :frowning:

For example,

function fooSum(arr)
  s=zero(eltype(arr))
  for i=1:length(arr)
    s += arr[i]
  end
  s
end

used to vectorize in 1.10.1 (it even managed to remove all boundschecks) and doesn’t vectorize any longer in

julia> versioninfo()
Julia Version 1.12.0-DEV.214
Commit 2775c9a0dc4 (2024-03-19 08:20 UTC)
1 Like

That sounds like a regression for a non-released version; please open an issue.

3 Likes

Note there is a benchmark, BaseBenchmarks.jl/src/array/sumindex.jl at 9e78db8463f01dcbebffc1bccb949a28be52d130 · JuliaCI/BaseBenchmarks.jl · GitHub, that is tracked by CI that is precisely your example.
Oddly there doesn’t seem to be a benchmark run on something like a Vector{Float64}, nevertheless a regression was identified recently and reported 3.5x regression on bounds checking in BaseBenchmarks due to LLVM bump to 15.0.7+10 in #52405 · Issue #53698 · JuliaLang/julia (github.com).

5 Likes

I wonder if it’s having trouble understanding the relation between memory and array

2 Likes