Revision f442e4230a41d0d40f81346c1707f946f743cbcf authored by Jeff Bezanson on 09 June 2021, 02:51:34 UTC, committed by GitHub on 09 June 2021, 02:51:34 UTC
This PR implements a way to keep tables of methods that are not part of the internal method table, but still participate in the special support we have for keeping tables of methods, in particular unification through precompilation and efficient lookup. The intended design use case is to allow for method overlay tables for various non-CPU backends (e.g. GPU and TPU). These backends would like to modify basic function like `sin` to perform better on the device in question (or in the case of TPU to define them over non-LLVM intrinsics). It is worth noting that this PR only gives the ability to keep these tables of methods. It assigns no particular meaning to them and the runtime (and regular inference) do not look at them. They are designed as an implementation detail for external compilers and similar tools. # Demo ```julia julia> using Base.Experimental: @overlay, @MethodTable julia> @MethodTable(mt) # 0 methods: julia> @overlay mt function sin(x::Float64) 1 end julia> @overlay mt function cos(x::Float64) 1 end julia> mt # 2 methods: [1] cos(x::Float64) in Main at REPL[5]:1 [2] sin(x::Float64) in Main at REPL[4]:1 julia> Base._methods_by_ftype(Tuple{typeof(sin), Float64}, mt, 1, typemax(UInt)) 1-element Vector{Any}: Core.MethodMatch(Tuple{typeof(sin), Float64}, svec(), sin(x::Float64) in Main at REPL[4]:1, true) julia> Base._methods_by_ftype(Tuple{typeof(sin), Float64}, 1, typemax(UInt)) 1-element Vector{Any}: Core.MethodMatch(Tuple{typeof(sin), Float64}, svec(Float64), sin(x::T) where T<:Union{Float32, Float64} in Base.Math at special/trig.jl:29, true) ``` Co-authored-by: Tim Besard <tim.besard@gmail.com> Co-authored-by: Julian P Samaroo <jpsamaroo@jpsamaroo.me> Co-authored-by: Keno Fischer <keno@juliacomputing.com>
1 parent 0e3276c
checked.jl
# This file is a part of Julia. License is MIT: https://julialang.org/license
# Checked integer arithmetic
import Base: checked_abs, checked_neg, checked_add, checked_sub, checked_mul,
checked_div, checked_rem, checked_fld, checked_mod, checked_cld,
add_with_overflow, sub_with_overflow, mul_with_overflow
# checked operations
@testset for T in (Int8, Int16, Int32, Int64, Int128)
# regular cases
@test checked_abs(T(0)) === T(0)
@test checked_neg(T(0)) === T(0)
@test checked_add(T(0)) === T(0)
@test checked_mul(T(0)) === T(0)
for s in (-1, +1)
@test checked_abs(T(3s)) === T(abs(3s))
@test checked_neg(T(3s)) === T(-3s)
@test checked_add(T(3s)) === T(3s)
@test checked_mul(T(3s)) === T(3s)
@test checked_abs(T(s*typemax(T))) === typemax(T)
@test checked_neg(T(s*typemax(T))) === T(-s*typemax(T))
@test checked_add(T(s*typemax(T))) === T(s*typemax(T))
@test checked_mul(T(s*typemax(T))) === T(s*typemax(T))
end
# corner cases
@test_throws OverflowError checked_abs(typemin(T))
@test_throws OverflowError checked_neg(typemin(T))
# regular cases
for s1 in (-1, +1), s2 in (-1, +1)
@test checked_add(T(4s1), T(3s2)) === T(4s1 + 3s2)
@test checked_sub(T(4s1), T(3s2)) === T(4s1 - 3s2)
@test checked_mul(T(4s1), T(3s2)) === T(4s1 * 3s2)
@test checked_div(T(4s1), T(3s2)) === T(div(4s1, 3s2))
@test checked_rem(T(4s1), T(3s2)) === T(rem(4s1, 3s2))
@test checked_fld(T(4s1), T(3s2)) === T(fld(4s1, 3s2))
@test checked_mod(T(4s1), T(3s2)) === T(mod(4s1, 3s2))
@test checked_cld(T(4s1), T(3s2)) === T(cld(4s1, 3s2))
end
# corner cases
halfmax = T(typemax(T)÷2)
halfmax_plus1 = T(halfmax+1)
halfmin = T(typemin(T)÷2)
halfmin_minus1 = T(halfmin-1)
sqrtmax = T(1) << T(sizeof(T)*4)
half_sqrtmax = sqrtmax >> T(1)
half_sqrtmax_plus1 = half_sqrtmax + T(1)
@test checked_add(typemax(T), T(-1)) === T(typemax(T) - 1)
@test_throws OverflowError checked_add(typemin(T), T(-1))
@test checked_add(typemax(T), T(0)) === typemax(T)
@test checked_add(typemin(T), T(0)) === typemin(T)
@test_throws OverflowError checked_add(typemax(T), T(1))
@test checked_add(typemin(T), T(1)) === T(typemin(T) + 1)
@test checked_add(T(-1), typemax(T)) === T(typemax(T) - 1)
@test_throws OverflowError checked_add(T(-1), typemin(T))
@test checked_add(T(0), typemax(T)) === typemax(T)
@test checked_add(T(0), typemin(T)) === typemin(T)
@test_throws OverflowError checked_add(T(1), typemax(T))
@test checked_add(T(1), typemin(T)) === T(typemin(T) + 1)
@test checked_add(typemax(T), typemin(T)) === T(-1)
@test checked_add(typemin(T), typemax(T)) === T(-1)
@test_throws OverflowError checked_add(halfmax_plus1, halfmax_plus1)
@test_throws OverflowError checked_add(halfmin, halfmin_minus1)
@test add_with_overflow(typemax(T), T(-1)) === (T(typemax(T) - 1), false)
@test add_with_overflow(typemin(T), T(-1)) === (T(typemax(T)), true)
@test add_with_overflow(typemax(T), T(0)) === (typemax(T), false)
@test add_with_overflow(typemin(T), T(0)) === (typemin(T), false)
@test add_with_overflow(typemax(T), T(1)) === (typemin(T), true)
@test add_with_overflow(typemin(T), T(1)) === (T(typemin(T) + 1), false)
@test add_with_overflow(T(-1), typemax(T)) === (T(typemax(T) - 1), false)
@test add_with_overflow(T(-1), typemin(T)) === (typemax(T), true)
@test add_with_overflow(T(0), typemax(T)) === (typemax(T), false)
@test add_with_overflow(T(0), typemin(T)) === (typemin(T), false)
@test add_with_overflow(T(1), typemax(T)) === (typemin(T), true)
@test add_with_overflow(T(1), typemin(T)) === (T(typemin(T) + 1), false)
@test add_with_overflow(typemax(T), typemin(T)) === (T(-1), false)
@test add_with_overflow(typemin(T), typemax(T)) === (T(-1), false)
@test add_with_overflow(halfmax_plus1, halfmax_plus1) === (typemin(T), true)
@test add_with_overflow(halfmin, halfmin_minus1) === (typemax(T), true)
@test_throws OverflowError checked_sub(typemax(T), T(-1))
@test checked_sub(typemax(T), T(0)) === typemax(T)
@test checked_sub(typemax(T), T(1)) === T(typemax(T) - 1)
@test checked_sub(typemin(T), T(-1)) === T(typemin(T) + 1)
@test checked_sub(typemin(T), T(0)) === typemin(T)
@test_throws OverflowError checked_sub(typemin(T), T(1))
@test checked_sub(T(0), typemax(T)) === T(typemin(T) + 1)
@test checked_sub(T(1), typemax(T)) === T(typemin(T) + 2)
@test checked_sub(T(-1), typemin(T)) === typemax(T)
@test_throws OverflowError checked_sub(T(0), typemin(T))
@test checked_sub(typemax(T), typemax(T)) === T(0)
@test checked_sub(typemin(T), typemin(T)) === T(0)
@test checked_sub(halfmax, T(-halfmin)) === T(-1)
@test_throws OverflowError checked_sub(halfmin, T(-halfmin_minus1))
@test sub_with_overflow(typemax(T), T(-1)) === (typemin(T), true)
@test sub_with_overflow(typemax(T), T(0)) === (typemax(T), false)
@test sub_with_overflow(typemax(T), T(1)) === (T(typemax(T) - 1), false)
@test sub_with_overflow(typemin(T), T(-1)) === (T(typemin(T) + 1), false)
@test sub_with_overflow(typemin(T), T(0)) === (typemin(T), false)
@test sub_with_overflow(typemin(T), T(1)) === (typemax(T), true)
@test sub_with_overflow(T(0), typemax(T)) === (T(typemin(T) + 1), false)
@test sub_with_overflow(T(1), typemax(T)) === (T(typemin(T) + 2), false)
@test sub_with_overflow(T(-1), typemin(T)) === (typemax(T), false)
@test sub_with_overflow(T(0), typemin(T)) === (typemin(T), true)
@test sub_with_overflow(typemax(T), typemax(T)) === (T(0), false)
@test sub_with_overflow(typemin(T), typemin(T)) === (T(0), false)
@test sub_with_overflow(halfmax, T(-halfmin)) === (T(-1), false)
@test sub_with_overflow(halfmin, T(-halfmin_minus1)) === (typemax(T), true)
@test checked_mul(typemax(T), T(0)) === T(0)
@test checked_mul(typemin(T), T(0)) === T(0)
@test checked_mul(typemax(T), T(1)) === typemax(T)
@test checked_mul(typemin(T), T(1)) === typemin(T)
@test_throws OverflowError checked_mul(sqrtmax, half_sqrtmax)
@test checked_mul(sqrtmax, -half_sqrtmax) === T(sqrtmax * -half_sqrtmax)
@test_throws OverflowError checked_mul(sqrtmax, -half_sqrtmax_plus1)
@test checked_mul(-sqrtmax, half_sqrtmax) === T(-sqrtmax * half_sqrtmax)
@test_throws OverflowError checked_mul(-sqrtmax, half_sqrtmax_plus1)
@test_throws OverflowError checked_mul(-sqrtmax, -half_sqrtmax)
@test mul_with_overflow(typemax(T), T(0)) === (T(0), false)
@test mul_with_overflow(typemin(T), T(0)) === (T(0), false)
@test mul_with_overflow(typemax(T), T(1)) === (typemax(T), false)
@test mul_with_overflow(typemin(T), T(1)) === (typemin(T), false)
@test mul_with_overflow(sqrtmax, half_sqrtmax) === (typemin(T), true)
@test mul_with_overflow(sqrtmax, -half_sqrtmax) === (T(sqrtmax * -half_sqrtmax), false)
@test mul_with_overflow(sqrtmax, -half_sqrtmax_plus1) === (T(sqrtmax * -half_sqrtmax_plus1), true)
@test mul_with_overflow(-sqrtmax, half_sqrtmax) === (T(-sqrtmax * half_sqrtmax), false)
@test mul_with_overflow(-sqrtmax, half_sqrtmax_plus1) === (T(-sqrtmax * half_sqrtmax_plus1), true)
@test mul_with_overflow(-sqrtmax, -half_sqrtmax) === (T(-sqrtmax * -half_sqrtmax), true)
@test checked_div(typemax(T), T(1)) === typemax(T)
@test_throws DivideError checked_div(typemax(T), T(0))
@test checked_div(typemax(T), T(-1)) === T(-typemax(T))
@test checked_div(typemin(T), T(1)) === typemin(T)
@test_throws DivideError checked_div(typemin(T), T(0))
@test_throws DivideError checked_div(typemin(T), T(-1))
@test checked_rem(typemax(T), T(1)) === T(0)
@test_throws DivideError checked_rem(typemax(T), T(0))
@test checked_rem(typemax(T), T(-1)) === T(0)
@test checked_rem(typemin(T), T(1)) === T(0)
@test_throws DivideError checked_rem(typemin(T), T(0))
@test checked_rem(typemin(T), T(-1)) === T(0)
@test checked_fld(typemax(T), T(1)) === typemax(T)
@test_throws DivideError checked_fld(typemax(T), T(0))
@test checked_fld(typemax(T), T(-1)) === T(-typemax(T))
@test checked_fld(typemin(T), T(1)) === typemin(T)
@test_throws DivideError checked_fld(typemin(T), T(0))
@test_throws DivideError checked_fld(typemin(T), T(-1))
@test checked_mod(typemax(T), T(1)) === T(0)
@test_throws DivideError checked_mod(typemax(T), T(0))
@test checked_mod(typemax(T), T(-1)) === T(0)
@test checked_mod(typemin(T), T(1)) === T(0)
@test_throws DivideError checked_mod(typemin(T), T(0))
@test checked_mod(typemin(T), T(-1)) === T(0)
@test_throws DivideError checked_cld(typemax(T), T(0))
@test checked_cld(typemax(T), T(-1)) === T(-typemax(T))
@test checked_cld(typemin(T), T(1)) === typemin(T)
@test_throws DivideError checked_cld(typemin(T), T(0))
@test_throws DivideError checked_cld(typemin(T), T(-1))
end
@testset for T in (UInt8, UInt16, UInt32, UInt64, UInt128)
# regular cases
@test checked_abs(T(0)) === T(0)
@test checked_neg(T(0)) === T(0)
@test checked_add(T(0)) === T(0)
@test checked_mul(T(0)) === T(0)
@test checked_abs(T(3)) === T(3)
@test_throws OverflowError checked_neg(T(3))
@test checked_add(T(3)) === T(3)
@test checked_mul(T(3)) === T(3)
# regular cases
@test checked_add(T(4), T(3)) === T(7)
@test checked_sub(T(4), T(3)) === T(1)
@test checked_mul(T(4), T(3)) === T(12)
# corner cases
halfmax = T(typemax(T)÷2)
halfmax_plus1 = T(halfmax+1)
sqrtmax = T(1) << T(sizeof(T)*4)
@test checked_add(typemax(T), T(0)) === typemax(T)
@test checked_add(T(0), T(0)) === T(0)
@test_throws OverflowError checked_add(typemax(T), T(1))
@test checked_add(T(0), T(1)) === T(T(0) + 1)
@test checked_add(T(0), typemax(T)) === typemax(T)
@test checked_add(T(0), T(0)) === T(0)
@test_throws OverflowError checked_add(T(1), typemax(T))
@test checked_add(T(1), T(0)) === T(T(0) + 1)
@test checked_add(typemax(T), T(0)) === typemax(T)
@test checked_add(T(0), typemax(T)) === typemax(T)
@test_throws OverflowError checked_add(halfmax_plus1, halfmax_plus1)
@test add_with_overflow(typemax(T), T(0)) === (typemax(T), false)
@test add_with_overflow(T(0), T(0)) === (T(0), false)
@test add_with_overflow(typemax(T), T(1)) === (T(0), true)
@test add_with_overflow(T(0), T(1)) === (T(T(0) + 1), false)
@test add_with_overflow(T(0), typemax(T)) === (typemax(T), false)
@test add_with_overflow(T(0), T(0)) === (T(0), false)
@test add_with_overflow(T(1), typemax(T)) === (T(0), true)
@test add_with_overflow(T(1), T(0)) === (T(T(0) + 1), false)
@test add_with_overflow(typemax(T), T(0)) === (typemax(T), false)
@test add_with_overflow(T(0), typemax(T)) === (typemax(T), false)
@test add_with_overflow(halfmax_plus1, halfmax_plus1) === (T(0), true)
@test checked_sub(typemax(T), T(0)) === typemax(T)
@test checked_sub(typemax(T), T(1)) === T(typemax(T) - 1)
@test checked_sub(T(0), T(0)) === T(0)
@test_throws OverflowError checked_sub(T(0), T(1))
@test_throws OverflowError checked_sub(T(0), typemax(T))
@test_throws OverflowError checked_sub(T(1), typemax(T))
@test checked_sub(T(0), T(0)) === T(0)
@test checked_sub(typemax(T), typemax(T)) === T(0)
@test sub_with_overflow(typemax(T), T(0)) === (typemax(T), false)
@test sub_with_overflow(typemax(T), T(1)) === (T(typemax(T) - 1), false)
@test sub_with_overflow(T(0), T(0)) === (T(0), false)
@test sub_with_overflow(T(0), T(1)) === (typemax(T), true)
@test sub_with_overflow(T(0), typemax(T)) === (T(1), true)
@test sub_with_overflow(T(1), typemax(T)) === (T(2), true)
@test sub_with_overflow(T(0), T(0)) === (T(0), false)
@test sub_with_overflow(typemax(T), typemax(T)) === (T(0), false)
@test checked_mul(typemax(T), T(0)) === T(0)
@test checked_mul(T(0), T(0)) === T(0)
@test checked_mul(typemax(T), T(1)) === typemax(T)
@test checked_mul(T(0), T(1)) === T(0)
@test_throws OverflowError checked_mul(sqrtmax, sqrtmax)
@test mul_with_overflow(typemax(T), T(0)) === (T(0), false)
@test mul_with_overflow(T(0), T(0)) === (T(0), false)
@test mul_with_overflow(typemax(T), T(1)) === (typemax(T), false)
@test mul_with_overflow(T(0), T(1)) === (T(0), false)
@test mul_with_overflow(sqrtmax, sqrtmax) === (T(0), true)
@test checked_div(typemax(T), T(1)) === typemax(T)
@test_throws DivideError checked_div(typemax(T), T(0))
@test checked_rem(typemax(T), T(1)) === T(0)
@test_throws DivideError checked_rem(typemax(T), T(0))
@test checked_fld(typemax(T), T(1)) === typemax(T)
@test_throws DivideError checked_fld(typemax(T), T(0))
@test checked_mod(typemax(T), T(1)) === T(0)
@test_throws DivideError checked_mod(typemax(T), T(0))
@test checked_cld(typemax(T), T(1)) === typemax(T)
@test_throws DivideError checked_cld(typemax(T), T(0))
end
@testset "Boolean" begin
@test checked_add(false) === 0
@test checked_add(true) === 1
@test checked_neg(false) === 0
@test checked_neg(true) === -1
@test checked_abs(true) === true
@test checked_abs(false) === false
@test checked_mul(false) === false
@test checked_mul(true) === true
@test checked_add(true, true) === 2
@test checked_add(true, false) === 1
@test checked_add(false, false) === 0
@test checked_add(false, true) === 1
@test checked_sub(true, true) === 0
@test checked_sub(true, false) === 1
@test checked_sub(false, false) === 0
@test checked_sub(false, true) === -1
@test checked_mul(true, false) === false
@test checked_mul(false, false) === false
@test checked_mul(true, true) === true
@test checked_mul(false, true) === false
@test checked_div(true, true) === true
@test checked_div(false, true) === false
@test_throws DivideError checked_div(true, false)
@test checked_rem(true, true) === false
@test checked_rem(false, true) === false
@test_throws DivideError checked_rem(true, false)
@test checked_fld(true, true) === true
@test checked_fld(false, true) === false
@test_throws DivideError checked_fld(true, false)
@test checked_mod(true, true) === false
@test checked_mod(false, true) === false
@test_throws DivideError checked_mod(true, false)
@test checked_cld(true, true) === true
@test checked_cld(false, true) === false
@test_throws DivideError checked_cld(true, false)
end
@testset "BigInt" begin
@test checked_abs(BigInt(-1)) == BigInt(1)
@test checked_abs(BigInt(1)) == BigInt(1)
@test checked_neg(BigInt(-1)) == BigInt(1)
@test checked_neg(BigInt(1)) == BigInt(-1)
@test checked_add(BigInt(1), BigInt(1)) == BigInt(2)
@test checked_sub(BigInt(1), BigInt(2)) == BigInt(-1)
@test checked_mul(BigInt(2), BigInt(10)) == BigInt(20)
@test checked_div(BigInt(10), BigInt(2)) == BigInt(5)
@test checked_rem(BigInt(9), BigInt(4)) == BigInt(1)
@test checked_fld(BigInt(10), BigInt(3)) == BigInt(3)
@test checked_mod(BigInt(9), BigInt(4)) == BigInt(1)
@test checked_cld(BigInt(10), BigInt(3)) == BigInt(4)
end
@testset "Additional tests" begin
# test promotions
@test checked_add(UInt(4), UInt8(3)) === UInt(7)
@test checked_sub(UInt(4), UInt8(3)) === UInt(1)
@test checked_mul(UInt(4), UInt8(3)) === UInt(12)
@test checked_div(UInt(4), UInt8(2)) === UInt(2)
@test checked_mod(UInt(4), UInt8(2)) === UInt(0)
@test checked_rem(UInt(5), UInt8(2)) === UInt(1)
@test checked_fld(UInt(5), UInt8(1)) === UInt(5)
@test checked_cld(UInt(5), UInt8(1)) === UInt(5)
@test checked_sub(UInt(4), UInt(3)) === UInt(1)
@test_throws OverflowError checked_sub(UInt(5), UInt(6))
@test checked_mul(UInt(4), UInt(3)) === UInt(12)
@test checked_sub(Int128(-1),Int128(-2)) === Int128(1)
@test_throws OverflowError checked_mul(UInt32(2)^30, UInt32(2)^2)
@test_throws OverflowError checked_mul(UInt64(2)^62, UInt64(2)^2)
@test checked_add(UInt128(1), UInt128(2)) === UInt128(3)
@test_throws OverflowError checked_add(UInt128(2)^127, UInt128(2)^127)
@test checked_sub(UInt128(2), UInt128(1)) === UInt128(1)
@test_throws OverflowError checked_sub(UInt128(3), UInt128(4))
@test checked_mul(UInt128(3), UInt128(4)) === UInt128(12)
@test_throws OverflowError checked_mul(UInt128(2)^127, UInt128(2))
end
@testset "Multiple arguments for add, mul" begin
@test checked_add(1, 2, 3) === 6
@test checked_add(1, 2, 3, 4) === 10
@test checked_add(1, 2, 3, 4, 5) === 15
@test checked_add(1, 2, 3, 4, 5, 6) === 21
@test checked_add(1, 2, 3, 4, 5, 6, 7) === 28
@test checked_add(1, 2, 3, 4, 5, 6, 7, 8) === 36
@test checked_mul(1, 2, 3) === 6
@test checked_mul(1, 2, 3, 4) === 24
@test checked_mul(1, 2, 3, 4, 5) === 120
@test checked_mul(1, 2, 3, 4, 5, 6) === 720
@test checked_mul(1, 2, 3, 4, 5, 6, 7) === 5040
@test checked_mul(1, 2, 3, 4, 5, 6, 7, 8) === 40320
end
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...