https://github.com/JuliaLang/julia
Tip revision: 23e29fe99b777c4eff18a0c658fedeee46a4aa97 authored by Jameson Nash on 27 July 2016, 15:35:44 UTC
eliminate c implementation of ObjectIdDict
eliminate c implementation of ObjectIdDict
Tip revision: 23e29fe
checked.jl
# This file is a part of Julia. License is MIT: http://julialang.org/license
# Support for checked integer arithmetic
module Checked
export checked_neg, checked_abs, checked_add, checked_sub, checked_mul,
checked_div, checked_rem, checked_fld, checked_mod, checked_cld
import Core.Intrinsics: box, unbox,
checked_sadd_int, checked_ssub_int, checked_smul_int, checked_sdiv_int,
checked_srem_int,
checked_uadd_int, checked_usub_int, checked_umul_int, checked_udiv_int,
checked_urem_int
import Base: no_op_err
# define promotion behavior for checked operations
checked_add(x::Integer, y::Integer) = checked_add(promote(x,y)...)
checked_sub(x::Integer, y::Integer) = checked_sub(promote(x,y)...)
checked_mul(x::Integer, y::Integer) = checked_mul(promote(x,y)...)
checked_div(x::Integer, y::Integer) = checked_div(promote(x,y)...)
checked_rem(x::Integer, y::Integer) = checked_rem(promote(x,y)...)
checked_fld(x::Integer, y::Integer) = checked_fld(promote(x,y)...)
checked_mod(x::Integer, y::Integer) = checked_mod(promote(x,y)...)
checked_cld(x::Integer, y::Integer) = checked_cld(promote(x,y)...)
# fallback catchall rules to prevent infinite recursion if promotion succeeds,
# but no method exists to handle those types
checked_neg{T<:Integer}(x::T) = no_op_err("checked_neg", T)
checked_abs{T<:Integer}(x::T) = no_op_err("checked_abs", T)
checked_add{T<:Integer}(x::T, y::T) = no_op_err("checked_add", T)
checked_sub{T<:Integer}(x::T, y::T) = no_op_err("checked_sub", T)
checked_mul{T<:Integer}(x::T, y::T) = no_op_err("checked_mul", T)
checked_div{T<:Integer}(x::T, y::T) = no_op_err("checked_div", T)
checked_rem{T<:Integer}(x::T, y::T) = no_op_err("checked_rem", T)
checked_fld{T<:Integer}(x::T, y::T) = no_op_err("checked_fld", T)
checked_mod{T<:Integer}(x::T, y::T) = no_op_err("checked_mod", T)
checked_cld{T<:Integer}(x::T, y::T) = no_op_err("checked_cld", T)
typealias SignedInt Union{Int8,Int16,Int32,Int64,Int128}
typealias UnsignedInt Union{UInt8,UInt16,UInt32,UInt64,UInt128,Bool}
# LLVM has several code generation bugs for checked integer arithmetic (see e.g.
# #4905). We thus distinguish between operations that can be implemented via
# intrinsics, and operations for which we have to provide work-arounds.
# Note: As far as this code has been tested, most checked_* functions are
# working fine in LLVM. (Note that division is still handled via `base/int.jl`,
# which always checks for overflow, and which provides its own sets of
# work-arounds for LLVM codegen bugs.) However, the comments in `base/int.jl`
# and in issue #4905 are more pessimistic. For the time being, we thus retain
# the ability to handle codegen bugs in LLVM, until the code here has been
# tested on more systems and architectures. It also seems that things depend on
# which compiler that was used to build LLVM (i.e. either gcc or clang).
# These unions are used for most checked functions:
# BrokenSignedInt
# BrokenUnsignedInt
# These unions are used for checked_{mul,div,rem}:
# BrokenSignedIntMul
# BrokenUnsignedIntMul
# This code runs early during bootstrap, and we can't use Julia's version
# strings yet
const llvm_version = Int(ccall(:jl_get_LLVM_VERSION, UInt32, ()))
brokenSignedInt = Union{}
brokenUnsignedInt = Union{}
brokenSignedIntMul = Int128
brokenUnsignedIntMul = UInt128
if Core.sizeof(Ptr{Void}) == 4
brokenSignedIntMul = Union{brokenSignedIntMul, Int64}
brokenUnsignedIntMul = Union{brokenUnsignedIntMul, UInt64}
end
if llvm_version < 30500
brokenSignedIntMul = Union{brokenSignedIntMul, Int8}
brokenUnsignedIntMul = Union{brokenUnsignedIntMul, UInt8}
end
typealias BrokenSignedInt brokenSignedInt
typealias BrokenUnsignedInt brokenUnsignedInt
typealias BrokenSignedIntMul brokenSignedIntMul
typealias BrokenUnsignedIntMul brokenUnsignedIntMul
# Use these definitions to test the non-LLVM implementations
# typealias BrokenSignedInt SignedInt
# typealias BrokenUnsignedInt UnsignedInt
# typealias BrokenSignedIntMul SignedInt
# typealias BrokenUnsignedIntMul UnsignedInt
"""
Base.checked_neg(x)
Calculates `-x`, checking for overflow errors where applicable. For
example, standard two's complement signed integers (e.g. `Int`) cannot
represent `-typemin(Int)`, thus leading to an overflow.
The overflow protection may impose a perceptible performance penalty.
"""
function checked_neg end
function checked_neg{T<:SignedInt}(x::T)
checked_sub(T(0), x)
end
function checked_neg{T<:UnsignedInt}(x::T)
checked_sub(T(0), x)
end
if BrokenSignedInt != Union{}
function checked_neg{T<:BrokenSignedInt}(x::T)
r = -x
(x<0) & (r<0) && throw(OverflowError())
r
end
end
if BrokenUnsignedInt != Union{}
function checked_neg{T<:BrokenUnsignedInt}(x::T)
x != 0 && throw(OverflowError())
T(0)
end
end
"""
Base.checked_abs(x)
Calculates `abs(x)`, checking for overflow errors where applicable.
For example, standard two's complement signed integers (e.g. `Int`)
cannot represent `abs(typemin(Int))`, thus leading to an overflow.
The overflow protection may impose a perceptible performance penalty.
"""
function checked_abs end
function checked_abs(x::SignedInt)
r = ifelse(x<0, -x, x)
r<0 && throw(OverflowError())
r
end
checked_abs(x::UnsignedInt) = x
"""
Base.checked_add(x, y)
Calculates `x+y`, checking for overflow errors where applicable.
The overflow protection may impose a perceptible performance penalty.
"""
function checked_add end
function checked_add{T<:SignedInt}(x::T, y::T)
box(T, checked_sadd_int(unbox(T,x), unbox(T,y)))
end
function checked_add{T<:UnsignedInt}(x::T, y::T)
box(T, checked_uadd_int(unbox(T,x), unbox(T,y)))
end
if BrokenSignedInt != Union{}
function checked_add{T<:BrokenSignedInt}(x::T, y::T)
r = x + y
# x and y have the same sign, and the result has a different sign
(x<0) == (y<0) != (r<0) && throw(OverflowError())
r
end
end
if BrokenUnsignedInt != Union{}
function checked_add{T<:BrokenUnsignedInt}(x::T, y::T)
# x + y > typemax(T)
# Note: ~y == -y-1
x > ~y && throw(OverflowError())
x + y
end
end
checked_add(x::Bool, y::Bool) = x + y
checked_add(x::Bool) = +x
# Handle multiple arguments
checked_add(x) = x
checked_add{T}(x1::T, x2::T, x3::T) =
checked_add(checked_add(x1, x2), x3)
checked_add{T}(x1::T, x2::T, x3::T, x4::T) =
checked_add(checked_add(x1, x2), x3, x4)
checked_add{T}(x1::T, x2::T, x3::T, x4::T, x5::T) =
checked_add(checked_add(x1, x2), x3, x4, x5)
checked_add{T}(x1::T, x2::T, x3::T, x4::T, x5::T, x6::T) =
checked_add(checked_add(x1, x2), x3, x4, x5, x6)
checked_add{T}(x1::T, x2::T, x3::T, x4::T, x5::T, x6::T, x7::T) =
checked_add(checked_add(x1, x2), x3, x4, x5, x6, x7)
checked_add{T}(x1::T, x2::T, x3::T, x4::T, x5::T, x6::T, x7::T, x8::T) =
checked_add(checked_add(x1, x2), x3, x4, x5, x6, x7, x8)
"""
Base.checked_sub(x, y)
Calculates `x-y`, checking for overflow errors where applicable.
The overflow protection may impose a perceptible performance penalty.
"""
function checked_sub end
function checked_sub{T<:SignedInt}(x::T, y::T)
box(T, checked_ssub_int(unbox(T,x), unbox(T,y)))
end
function checked_sub{T<:UnsignedInt}(x::T, y::T)
box(T, checked_usub_int(unbox(T,x), unbox(T,y)))
end
if BrokenSignedInt != Union{}
function checked_sub{T<:BrokenSignedInt}(x::T, y::T)
r = x - y
# x and y have different signs, and the result has a different sign than x
(x<0) != (y<0) == (r<0) && throw(OverflowError())
r
end
end
if BrokenUnsignedInt != Union{}
function checked_sub{T<:BrokenUnsignedInt}(x::T, y::T)
# x - y < 0
x < y && throw(OverflowError())
x - y
end
end
checked_sub(x::Bool, y::Bool) = x - y
checked_sub(x::Bool) = -x
"""
Base.checked_mul(x, y)
Calculates `x*y`, checking for overflow errors where applicable.
The overflow protection may impose a perceptible performance penalty.
"""
function checked_mul end
function checked_mul{T<:SignedInt}(x::T, y::T)
box(T, checked_smul_int(unbox(T,x), unbox(T,y)))
end
function checked_mul{T<:UnsignedInt}(x::T, y::T)
box(T, checked_umul_int(unbox(T,x), unbox(T,y)))
end
if BrokenSignedIntMul != Union{} && BrokenSignedIntMul != Int128
function checked_mul{T<:BrokenSignedIntMul}(x::T, y::T)
r = widemul(x, y)
r % T != r && throw(OverflowError())
r % T
end
end
if BrokenUnsignedIntMul != Union{} && BrokenUnsignedIntMul != UInt128
function checked_mul{T<:BrokenUnsignedIntMul}(x::T, y::T)
r = widemul(x, y)
r % T != r && throw(OverflowError())
r % T
end
end
if Int128 <: BrokenSignedIntMul
# Avoid BigInt
function checked_mul{T<:Int128}(x::T, y::T)
if y > 0
# x * y > typemax(T)
# x * y < typemin(T)
x > fld(typemax(T), y) && throw(OverflowError())
x < cld(typemin(T), y) && throw(OverflowError())
elseif y < 0
# x * y > typemax(T)
# x * y < typemin(T)
x < cld(typemax(T), y) && throw(OverflowError())
# y == -1 can overflow fld
y != -1 && x > fld(typemin(T), y) && throw(OverflowError())
end
x * y
end
end
if UInt128 <: BrokenUnsignedIntMul
# Avoid BigInt
function checked_mul{T<:UInt128}(x::T, y::T)
# x * y > typemax(T)
y > 0 && x > fld(typemax(T), y) && throw(OverflowError())
x * y
end
end
# Handle multiple arguments
checked_mul(x) = x
checked_mul{T}(x1::T, x2::T, x3::T) =
checked_mul(checked_mul(x1, x2), x3)
checked_mul{T}(x1::T, x2::T, x3::T, x4::T) =
checked_mul(checked_mul(x1, x2), x3, x4)
checked_mul{T}(x1::T, x2::T, x3::T, x4::T, x5::T) =
checked_mul(checked_mul(x1, x2), x3, x4, x5)
checked_mul{T}(x1::T, x2::T, x3::T, x4::T, x5::T, x6::T) =
checked_mul(checked_mul(x1, x2), x3, x4, x5, x6)
checked_mul{T}(x1::T, x2::T, x3::T, x4::T, x5::T, x6::T, x7::T) =
checked_mul(checked_mul(x1, x2), x3, x4, x5, x6, x7)
checked_mul{T}(x1::T, x2::T, x3::T, x4::T, x5::T, x6::T, x7::T, x8::T) =
checked_mul(checked_mul(x1, x2), x3, x4, x5, x6, x7, x8)
"""
Base.checked_div(x, y)
Calculates `div(x,y)`, checking for overflow errors where applicable.
The overflow protection may impose a perceptible performance penalty.
"""
function checked_div end
# Base.div already checks; nothing to do here
checked_div{T<:SignedInt}(x::T, y::T) = div(x, y)
checked_div{T<:UnsignedInt}(x::T, y::T) = div(x, y)
"""
Base.checked_rem(x, y)
Calculates `x%y`, checking for overflow errors where applicable.
The overflow protection may impose a perceptible performance penalty.
"""
function checked_rem end
# Base.rem already checks; nothing to do here
checked_rem{T<:SignedInt}(x::T, y::T) = rem(x, y)
checked_rem{T<:UnsignedInt}(x::T, y::T) = rem(x, y)
"""
Base.checked_fld(x, y)
Calculates `fld(x,y)`, checking for overflow errors where applicable.
The overflow protection may impose a perceptible performance penalty.
"""
function checked_fld end
# Base.fld already checks; nothing to do here
checked_fld{T<:SignedInt}(x::T, y::T) = fld(x, y)
checked_fld{T<:UnsignedInt}(x::T, y::T) = fld(x, y)
"""
Base.checked_mod(x, y)
Calculates `mod(x,y)`, checking for overflow errors where applicable.
The overflow protection may impose a perceptible performance penalty.
"""
function checked_mod end
# Base.mod already checks; nothing to do here
checked_mod{T<:SignedInt}(x::T, y::T) = mod(x, y)
checked_mod{T<:UnsignedInt}(x::T, y::T) = mod(x, y)
"""
Base.checked_cld(x, y)
Calculates `cld(x,y)`, checking for overflow errors where applicable.
The overflow protection may impose a perceptible performance penalty.
"""
function checked_cld end
# Base.cld already checks; nothing to do here
checked_cld{T<:SignedInt}(x::T, y::T) = cld(x, y)
checked_cld{T<:UnsignedInt}(x::T, y::T) = cld(x, y)
end