Compile-time optimization for any() and all()

[nalimilan]

Currently all(x -> true, X) and any(x -> false, X) loop over all entries of X. Could the compiler optimize the loop away when the return value is known?

This would be useful in cases like any(isnull, X), since isnull returns false for non-Nullable entries. That would make this call very efficient when X is a non-nullable array. Cf. JuliaStats/NullableArrays.jl#189.

[TotalVerb]

I think the trouble is either that iteration of arrays can't be proven to be effect free, or that this information isn't being passed to LLVM to allow optimization. Right now even an empty loop can't be optimized away.

julia> f(A) = (for _ in A; end)
f (generic function with 1 method)

julia> @code_llvm f([1, 2, 3])

define void @julia_f_67190(i8**) #0 !dbg !5 {
top:
  %1 = getelementptr inbounds i8*, i8** %0, i64 1
  %2 = bitcast i8** %1 to i64*
  %3 = load i64, i64* %2, align 8
  %4 = icmp eq i64 %3, 0
  br i1 %4, label %L10, label %if.lr.ph

if.lr.ph:                                         ; preds = %top
  %5 = getelementptr i8*, i8** %0, i64 3
  %6 = bitcast i8** %5 to i64*
  %7 = load i64, i64* %6, align 8
  br label %if

if:                                               ; preds = %if.lr.ph, %idxend
  %storemerge3 = phi i64 [ 1, %if.lr.ph ], [ %11, %idxend ]
  %8 = add i64 %storemerge3, -1
  %9 = icmp ult i64 %8, %7
  br i1 %9, label %idxend, label %oob

L10.loopexit:                                     ; preds = %idxend
  br label %L10

L10:                                              ; preds = %L10.loopexit, %top
  ret void

oob:                                              ; preds = %if
  %10 = alloca i64, align 8
  store i64 %storemerge3, i64* %10, align 8
  call void @jl_bounds_error_ints(i8** %0, i64* nonnull %10, i64 1)
  unreachable

idxend:                                           ; preds = %if
  %11 = add i64 %storemerge3, 1
  %12 = icmp eq i64 %storemerge3, %3
  br i1 %12, label %L10.loopexit, label %if
}

[nalimilan]

Good catch! Actually, this is just because of the absence of the @inbounds annotation. Looks like we could add it if we consider that going over an iterator is not supposed to trigger out of bounds accesses. Or we could at least define a specific method for Array or AbstractArray.

[haampie]

There's a regression on master which makes the proposed @inbounds solution fail, as the @propagate_inbounds annotation of all and any have been removed at some point.

At any rate, for all(f, ::Array) and any(f, ::Array) this issue is fixed at its roots via #27386. For ::AbstractArray, I'm not entirely sure!

# using the branch of #27386
julia> f(v) = any(x -> false, v)
julia> g(v) = all(x -> true, v)
julia> @btime f(v) setup = (v = rand(Int, 1_000))
  1.887 ns (0 allocations: 0 bytes)
false
julia> @btime g(v) setup = (v = rand(Int, 1_000))
  3.370 ns (0 allocations: 0 bytes) # this is "slower" due to function call overhead; the call to `_all` is not inlined
true

[nalimilan]

I confirm that #27386 fixes it:

julia> f(v) = any(x -> false, v)
f (generic function with 1 method)

julia> @code_llvm f([1])

; Function f
; Location: REPL[7]:1
define i8 @julia_f_33311(%jl_value_t addrspace(10)* nonnull dereferenceable(40)) {
top:
  ret i8 0
}

julia> g(v) = all(x -> true, v)
g (generic function with 1 method)

julia> @code_llvm g([1])

; Function g
; Location: REPL[9]:1
define i8 @julia_g_33323(%jl_value_t addrspace(10)* nonnull dereferenceable(40)) {
top:
  ret i8 1
}