elide code marked with @boundscheck(...).

[blakejohnson]

This is my attempt to implement @JeffBezanson's suggestion in #7799, which is to say that this teaches the compiler how to elide blocks marked with the @boundscheck macro, with the simple heuristic of allowing an inbounds context to propagate through one layer of inlining.

I haven't yet marked code that does bounds checking with the @boundscheck macro. But, a quick demo:

function foo()
    x = 1
    @boundscheck(x += 1)
    return x
end

function bar()
    x = 1
    @inbounds begin
        @boundscheck(x += 1)
    end
    return x
end

Then,

julia> foo()
2

julia> bar()
1

Comments from Jeff or @vtjnash would be appreciated. I don't grok the details of how inlining works in the compiler yet, so I'm not sure I have properly implemented the inbounds heuristic.

Remaining TODOs:

• Review of the overall approach
• Clean up some AST "noise"
• Mark bounds checking code in base with @boundscheck
• Figure out a deprecation approach (if any) for the existing @boundscheck macro
• Obey the --check-bounds=yes cmd line option, but still have a way to run the tests where we want to override it

[blakejohnson]

Just added some tests. Seems that my attempt to only eliminate bounds checks one level deep isn't working yet (see the final test which is currently failing).

[sjkelly]

checkbounds is already exported. Maybe it would be good to extend that namespace?

[blakejohnson]

The tests should nominally pass now, but that is because of the final commented out test. The issue is definitely related to inlining, so I could use some guidance.

[blakejohnson]

I see that inlining actually happens before the AST even gets passed to codegen. I'll see if I can add what I need.

[blakejohnson]

The latest commit tries to inject the appropriate metadata during inlining, but at the moment it is double injecting which causes the tests to fail.

[JeffBezanson]

Should this be |=?

[blakejohnson]

Ok, I think this is nominally working now, but it produces a lot of boundscheck "noise" in the AST. For example,

julia> code_typed(TestBoundsCheck.A2_inbounds, ())[1]
:($(Expr(:lambda, Any[], Any[Any[Any[:r,Int64,18],Any[symbol("##r#4464"),Int64,2]],Any[],Any[],Any[]], :(begin  # /Users/bjohnson/src/julia-dev/test/boundscheck.jl, line 31:
        $(Expr(:inbounds, true))
        $(Expr(:inbounds, false)) # /Users/bjohnson/src/julia-dev/test/boundscheck.jl, line 8:
        ##r#4464 = 0 # /Users/bjohnson/src/julia-dev/test/boundscheck.jl, line 9:
        $(Expr(:boundscheck, true))
        $(Expr(:inbounds, false))
        $(Expr(:inbounds, :pop))
        ##r#4464 = (Base.box)(Int64,(Base.add_int)(##r#4464::Int64,1))
        $(Expr(:boundscheck, :((top(getfield))(Base,:pop)))) # /Users/bjohnson/src/julia-dev/test/boundscheck.jl, line 10:
        $(Expr(:inbounds, :pop))
        $(Expr(:inbounds, false))
        $(Expr(:inbounds, :pop))
        r = (Base.box)(Int64,(Base.add_int)(##r#4464::Int64,1))
        $(Expr(:inbounds, :((top(getfield))(Base,:pop)))) # /Users/bjohnson/src/julia-dev/test/boundscheck.jl, line 32:
        return r::Int64
    end::Int64))))

At the very least, I'd like to get rid of the clearly unnecessary pairs like:

$(Expr(:inbounds, false))
$(Expr(:inbounds, :pop))

A further refinement would be to only inject these inbounds annotations when they have already appeared earlier in the method AST.

[blakejohnson]

PR updated with what I think are the outstanding issues.

[blakejohnson]

Now failing misc.jl on:

@test @allocated(whos(IOBuffer(), Tmp14173)) < 10000

I'm not sure what's special about 10,000, but I am guessing these extra inbounds expressions in the AST are causing additional memory use.

[JeffBezanson]

That's a really weird test!

We could do some extra filtering of useless expressions after inlining. For example inlining currently filters out empty meta expressions.

[tkelman]

The number on that test is probably too low, it was mostly to make sure that code path didn't try to print every element of the array.

Not sure I can offer much technical review here but wanted to say thank you to @blakejohnson for working on it.

[blakejohnson]

Cleaning up the :inbounds push/pop pairs seems to also fix the failing test in misc.jl.

[blakejohnson]

Hmm... I guess that last commit wasn't so successful. I'll have to think of another way to eliminate some of the AST noise.

Any other comments on the overall approach would be appreciated before I go any further.

[timholy]

I don't know codegen well enough to offer a useful review, but what I see looks good so far. 💯 on the effort!

[blakejohnson]

I guess we have to be fairly careful about what inbounds/boundscheck metadata we remove, because type inference caches ASTs, so it might be valid to remove the metadata when a method is called by itself, but then invalid when that same method gets inlined into a caller. Consequently, the elimination pass I added uses a rather conservative heuristic.

[blakejohnson]

I have been thinking that maybe we should separate the new inbounds/boundscheck compiler functionality from the use of it in getindex, because once you have this capability you can begin to consider a larger re-write of abstractarray.jl that gets rid of unsafe_getindex and unsafe_setindex! altogether.

So, focusing on just the compiler functionality... I've dealt with the issue that @StefanKarpinski raised by requiring that code containing @boundscheck(...) get inlined into whatever context contains the corresponding @inbounds. This allows the LLVM lowering pass to throw away the relevant section of code. Do people feel that requiring inlining is too restrictive? For example, it means that getindex must be inlined. It also means that we can't simply write the checkbounds method as:

function checkbounds(::Type{Bool}, sz::Dims, I...)
    @_inline_meta
    @boundscheck begin
        ...
    end
end

because the getindex->checkbounds chain means that this would be 2-layers of inlining deep, and so would not get ellided by our heuristic. Instead, you must decorate the checkbounds callsite, i.e. getindex would contain a line:

function getindex(A::Array, I)
    @_inline_meta
    ...
    @boundcheck checkbounds(A, I)
    ...

Which isn't bad, but if the former way worked it would be nice because it requires less code decoration.

If we wanted this to work, we'd need an extra piece of machinery to tell the inlining pass that a piece of code should not change the :inbounds context when inlined. Another reason you might want this is that as currently written, many of our getindex methods already contain some indirection, i.e. getindex -> _getindex -> unsafe_getindex.

Thoughts?

@mbauman

[blakejohnson]

@JeffBezanson's 7de4648 immediately solves the deprecation issue with @boundscheck since the prior macro had two arguments. Now that macros are generic functions we can deprecate just the two-argument version.

[timholy]

Very nice!

Hey, is this working now? At first glance it looks really promising!

[blakejohnson]

Well, it is "working" in the sense of the demo at the top, i.e. it will remove blocks of code marked as :boundscheck blocks as long as such blocks are inlined into the caller. I have also not broken the interaction with builtins, so unsafe_getindex which is defined on Arrays as:

unsafe_getindex(A::Array, i1::Real, I::Real...) = @inbounds return arrayref(A, to_index(i1), to_indexes(I...)...)

still skips boundschecking.

Whether or not it is sufficient for extending bounds check removal to other types depends on the issue I tried to explain a few days ago. I'd appreciate your two cents on that, @timholy.

[timholy]

@blakejohnson, sorry to be slow to respond on such an important issue.

To me, it looks like the restrictions you describe (bounds-check removal only for inlined code, needing to annotate the call site for checkbounds) are ones I could imagine living with, for the following reasons:

• The bounds-check removal typically has its biggest performance impact via enabling one to use SIMD; anything not inlined will prevent SIMD anyway
• Personally, I would naively expect to annotate the call to checkbounds rather than within checkbounds itself. So even though this is more annotation, to me it's more intuitive.
• Implementing this functionality so that it doesn't require inlining seems to be hard: you'd have to generate two versions of each method (e.g., one version of checkbounds that has bounds-checking on, and one that has it off), and then dispatch to the appropriate one. Even if we use "decoration" of the method names, this still seems to require some fairly deep surgery to method dispatch because julia would need to know that any time it looks for checkbounds, it should actually look for either checkbounds_withboundschecking or checkbounds_noboundschecking depending on context. This might be as simple as storing an extra bit in the method tables ("this method has versions with bounds-checking on and off"), but even then it's a little nontrivial to sync up all of julia's internal code to make sure that extra bit gets handled the way it should. I'm not sure it's wise to leap immediately to such a complex implementation without first getting some experience with how a simpler version works out.

CC also @simonster, who has thought quite a bit about these issues.

[blakejohnson]

That aligns pretty closely with my thinking, @timholy. The only thing I'd add at this point is that having a mechanism to propagate an inbounds context to a further layer of inlining seems very convenient, and saves us from having to re-write a bunch of code in abstractarray.jl. So, I went ahead and added such a mechanism last night.

[timholy]

Oh, well, looks like you found a simpler solution than I was envisioning!

[eschnett]

Of course, once this works for bounds checking, I want to use the same mechanism for @fast_math. And for non-wrapping integer arithmetic (setting the LLVM nsw / nuw flags). And for overflow checking on integer arithmetic. So, please reserve more than one additional bit of context...

[blakejohnson]

Trying to actually use the new mechanisms in abstractarray.jl now leads to a segfault in testing. The reduced test case looks like this:

A = rand(3,5); x = 1:size(A,1); y = (1:size(A,2))';
broadcast!(Base.MulFun(), Array{Int64,2}(5,3), x, y)

and it bails in codegen when applying LLVM level inling emitting GC pops. I'll have to reduce it further to really understand what is going on.

Update: Looks like I am creating some malformed BasicBlocks.

[blakejohnson]

Another fun way to trigger the segfault:

bf = Base.Broadcast.gen_broadcast_function(Base.Broadcast.gen_broadcast_body_cartesian, 2, 2, *)
code_llvm(bf, (Array{Int64,2},UnitRange{Int64},Array{Int64,2}))

[blakejohnson]

Ok, greatly reduced problem case:

cb(x) = x > 0 || throw("cb:error")

function B1()
    y = [1,2,3] # remove this line and the segfault goes away
    @inbounds begin
        @boundscheck cb(0)
    end
    return 0
end

code_llvm(B1, ()) # produces segfault

[blakejohnson]

I've made the one change Jeff suggested. @StefanKarpinski do you want some more time to take a look? Or should I merge it?

[StefanKarpinski]

This change looks sane to me; since @JeffBezanson is ok with it, go ahead and merge once tests pass.

[vtjnash]

lgtm

@JeffBezanson should we try to prevent this from being able to break type inference if used incorrectly? we could prohibit assignment (and fix the tests accordingly), but i'm thinking maybe we should just say that's part of the contract of marking something as bounds-checked material anyways. (we would also need to prohibit any type of non-local control flow, as goto / fallthough could potentially alter control-flow)

julia> @inline function f()
         x = "hello"
         @boundscheck x = 2
         return x
       end
       g() = (@inbounds x=f(); x)
g (generic function with 1 method)

julia> g()
4576183408

[JeffBezanson]

I think we can merge this now, but @vtjnash you have a good point. We could maybe enforce in the boundscheck macro that the expression must be a simple function call. Although somewhat humorously the tests rely on assignments inside boundscheck expressions :)

[blakejohnson]

I see what you are getting at, @vtjnash. I guess ideally a @boundscheck block would be side-effect free and return a bool. I'm not sure how to enforce that, though, without relying on type inference.

[johnmyleswhite]

Congratulations on merging this, Blake. I found your work on such core compiler code inspirational.

[rfourquet]

I don't understand why B1 and B2 are not used/called in a test, is it an oversight?

[blakejohnson]

Good catch. Those were reduced test cases that previously caused segfaults.

[blakejohnson]

Thanks, John.

[mschauer]

Is this correct or should it be "bounds checks are disabled"?

[blakejohnson]

You are right, true means bounds checks are disabled.