#37632

Committed 26 Sep 2023 06:44AM UTC coverage: 86.999% (-0.9%) from 87.914%

Build # #37632

Build Type

push

local

Committed by

web-flow

Commit Message

inference: make `throw` block deoptimization concrete-eval friendly (#49235)

The deoptimization can sometimes destroy the effects analysis and
disable [semi-]concrete evaluation that is otherwise possible. This is
because the deoptimization was designed with the type domain
profitability in mind (#35982), and hasn't been adequately considering
the effects domain.

This commit makes the deoptimization aware of the effects domain more
and enables the `throw` block deoptimization only when the effects
already known to be ineligible for concrete-evaluation.

In our current effect system, `ALWAYS_FALSE`/`false` means that the
effect can not be refined to `ALWAYS_TRUE`/`true` anymore (unless given
user annotation later). Therefore we can enable the `throw` block
deoptimization without hindering the chance of concrete-evaluation when
any of the following conditions are met:
- `effects.consistent === ALWAYS_FALSE`
- `effects.effect_free === ALWAYS_FALSE`
- `effects.terminates === false`
- `effects.nonoverlayed === false`

Here are some numbers:

| Metric | master | this commit | #35982 reverted (set
`unoptimize_throw_blocks=false`) |

|-------------------------|-----------|-------------|--------------------------------------------|
| Base (seconds) | 15.579300 | 15.206645 | 15.296319 |
| Stdlibs (seconds) | 17.919013 | 17.667094 | 17.738128 |
| Total (seconds) | 33.499279 | 32.874737 | 33.035448 |
| Precompilation (seconds) | 49.967516 | 49.421121 | 49.999998 |
| First time `plot(rand(10,3))` [^1] | `2.476678 seconds (11.74 M
allocations)` | `2.430355 seconds (11.77 M allocations)` | `2.514874
seconds (11.64 M allocations)` |
| First time `solve(prob, QNDF())(5.0)` [^2] | `4.469492 seconds (15.32
M allocations)` | `4.499217 seconds (15.41 M allocations)` | `4.470772
seconds (15.38 M allocations)` |

[^1]: With disabling precompilation of Plots.jl.
[^2]: With disabling precompilation of OrdinaryDiffEq.

These numbers ma... (continued)

Run Details

7 of 7 new or added lines in 1 file covered. (100.0%)

73407 of 84377 relevant lines covered (87.0%)

11275130.05 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

82.14

/base/hashing.jl

# This file is a part of Julia. License is MIT: https://julialang.org/license

## hashing a single value ##

"""
    hash(x[, h::UInt]) -> UInt

Compute an integer hash code such that `isequal(x,y)` implies `hash(x)==hash(y)`. The
optional second argument `h` is another hash code to be mixed with the result.

New types should implement the 2-argument form, typically by calling the 2-argument `hash`
method recursively in order to mix hashes of the contents with each other (and with `h`).
Typically, any type that implements `hash` should also implement its own [`==`](@ref) (hence
[`isequal`](@ref)) to guarantee the property mentioned above. Types supporting subtraction
(operator `-`) should also implement [`widen`](@ref), which is required to hash
values inside heterogeneous arrays.

The hash value may change when a new Julia process is started.

```jldoctest
julia> a = hash(10)
0x95ea2955abd45275

julia> hash(10, a) # only use the output of another hash function as the second argument
0xd42bad54a8575b16
```

See also: [`objectid`](@ref), [`Dict`](@ref), [`Set`](@ref).
"""
hash(x::Any) = hash(x, zero(UInt))
hash(w::WeakRef, h::UInt) = hash(w.value, h)
hash(T::Type, h::UInt) = hash_uint(3h - ccall(:jl_type_hash, UInt, (Any,), T))

## hashing general objects ##

hash(@nospecialize(x), h::UInt) = hash_uint(3h - objectid(x))

hash(x::Symbol) = objectid(x)

## core data hashing functions ##

function hash_64_64(n::UInt64)
    a::UInt64 = n
    a = ~a + a << 21
    a =  a ⊻ a >> 24
    a =  a + a << 3 + a << 8
    a =  a ⊻ a >> 14
    a =  a + a << 2 + a << 4
    a =  a ⊻ a >> 28
    a =  a + a << 31
    return a
end

function hash_64_32(n::UInt64)
    a::UInt64 = n
    a = ~a + a << 18
    a =  a ⊻ a >> 31
    a =  a * 21
    a =  a ⊻ a >> 11
    a =  a + a << 6
    a =  a ⊻ a >> 22
    return a % UInt32
end

function hash_32_32(n::UInt32)
    a::UInt32 = n
    a = a + 0x7ed55d16 + a << 12
    a = a ⊻ 0xc761c23c ⊻ a >> 19
    a = a + 0x165667b1 + a << 5
    a = a + 0xd3a2646c ⊻ a << 9
    a = a + 0xfd7046c5 + a << 3
    a = a ⊻ 0xb55a4f09 ⊻ a >> 16
    return a
end

if UInt === UInt64
    hash_uint64(x::UInt64) = hash_64_64(x)
    hash_uint(x::UInt)     = hash_64_64(x)
else
    hash_uint64(x::UInt64) = hash_64_32(x)
    hash_uint(x::UInt)     = hash_32_32(x)
end

## efficient value-based hashing of integers ##

hash(x::Int64,  h::UInt) = hash_uint64(bitcast(UInt64, x)) - 3h
hash(x::UInt64, h::UInt) = hash_uint64(x) - 3h
hash(x::Union{Bool,Int8,UInt8,Int16,UInt16,Int32,UInt32}, h::UInt) = hash(Int64(x), h)

function hash_integer(n::Integer, h::UInt)
    h ⊻= hash_uint((n % UInt) ⊻ h)
    n = abs(n)
    n >>>= sizeof(UInt) << 3
    while n != 0
        h ⊻= hash_uint((n % UInt) ⊻ h)
        n >>>= sizeof(UInt) << 3
    end
    return h
end

## symbol & expression hashing ##

if UInt === UInt64
    hash(x::Expr, h::UInt) = hash(x.args, hash(x.head, h + 0x83c7900696d26dc6))
    hash(x::QuoteNode, h::UInt) = hash(x.value, h + 0x2c97bf8b3de87020)
else
    hash(x::Expr, h::UInt) = hash(x.args, hash(x.head, h + 0x96d26dc6))
    hash(x::QuoteNode, h::UInt) = hash(x.value, h + 0x469d72af)
end

## hashing strings ##

const memhash = UInt === UInt64 ? :memhash_seed : :memhash32_seed
const memhash_seed = UInt === UInt64 ? 0x71e729fd56419c81 : 0x56419c81

@assume_effects :total function hash(s::String, h::UInt)
    h += memhash_seed
    ccall(memhash, UInt, (Ptr{UInt8}, Csize_t, UInt32), s, sizeof(s), h % UInt32) + h
end

1	# This file is a part of Julia. License is MIT: https://julialang.org/license
2
3	## hashing a single value ##
4
5	"""
6	hash(x[, h::UInt]) -> UInt
7
8	Compute an integer hash code such that `isequal(x,y)` implies `hash(x)==hash(y)`. The
9	optional second argument `h` is another hash code to be mixed with the result.
10
11	New types should implement the 2-argument form, typically by calling the 2-argument `hash`
12	method recursively in order to mix hashes of the contents with each other (and with `h`).
13	Typically, any type that implements `hash` should also implement its own [`==`](@ref) (hence
14	[`isequal`](@ref)) to guarantee the property mentioned above. Types supporting subtraction
15	(operator `-`) should also implement [`widen`](@ref), which is required to hash
16	values inside heterogeneous arrays.
17
18	The hash value may change when a new Julia process is started.
19
20	```jldoctest
21	julia> a = hash(10)
22	0x95ea2955abd45275
23
24	julia> hash(10, a) # only use the output of another hash function as the second argument
25	0xd42bad54a8575b16
26	```
27
28	See also: [`objectid`](@ref), [`Dict`](@ref), [`Set`](@ref).
29	"""
30	hash(x::Any) = hash(x, zero(UInt))	21,726,544✔
31	hash(w::WeakRef, h::UInt) = hash(w.value, h)	162,691✔
32	hash(T::Type, h::UInt) = hash_uint(3h - ccall(:jl_type_hash, UInt, (Any,), T))	188,890✔
33
34	## hashing general objects ##
35
36	hash(@nospecialize(x), h::UInt) = hash_uint(3h - objectid(x))	3,318,810✔
37
38	hash(x::Symbol) = objectid(x)	481,874✔
39
40	## core data hashing functions ##
41
42	function hash_64_64(n::UInt64)	×
43	a::UInt64 = n	×
44	a = ~a + a << 21	26,388,496✔
45	a = a ⊻ a >> 24	26,388,488✔
46	a = a + a << 3 + a << 8	26,388,487✔
47	a = a ⊻ a >> 14	26,388,476✔
48	a = a + a << 2 + a << 4	26,388,483✔
49	a = a ⊻ a >> 28	26,388,479✔
50	a = a + a << 31	26,388,486✔
51	return a	×
52	end
53
54	function hash_64_32(n::UInt64)	162✔
55	a::UInt64 = n	162✔
56	a = ~a + a << 18	162✔
57	a = a ⊻ a >> 31	162✔
58	a = a * 21	162✔
59	a = a ⊻ a >> 11	162✔
60	a = a + a << 6	162✔
61	a = a ⊻ a >> 22	162✔
62	return a % UInt32	162✔
63	end
64
65	function hash_32_32(n::UInt32)	162✔
66	a::UInt32 = n	162✔
67	a = a + 0x7ed55d16 + a << 12	162✔
68	a = a ⊻ 0xc761c23c ⊻ a >> 19	162✔
69	a = a + 0x165667b1 + a << 5	162✔
70	a = a + 0xd3a2646c ⊻ a << 9	162✔
71	a = a + 0xfd7046c5 + a << 3	162✔
72	a = a ⊻ 0xb55a4f09 ⊻ a >> 16	162✔
73	return a	162✔
74	end
75
76	if UInt === UInt64
77	hash_uint64(x::UInt64) = hash_64_64(x)	22,880,769✔
78	hash_uint(x::UInt) = hash_64_64(x)	3,507,727✔
79	else
80	hash_uint64(x::UInt64) = hash_64_32(x)	×
81	hash_uint(x::UInt) = hash_32_32(x)	×
82	end
83
84	## efficient value-based hashing of integers ##
85
86	hash(x::Int64, h::UInt) = hash_uint64(bitcast(UInt64, x)) - 3h	9,170,692✔
87	hash(x::UInt64, h::UInt) = hash_uint64(x) - 3h	11,247,142✔
88	hash(x::Union{Bool,Int8,UInt8,Int16,UInt16,Int32,UInt32}, h::UInt) = hash(Int64(x), h)	3,326,716✔
89
90	function hash_integer(n::Integer, h::UInt)	25✔
91	h ⊻= hash_uint((n % UInt) ⊻ h)	25✔
92	n = abs(n)	25✔
93	n >>>= sizeof(UInt) << 3	25✔
94	while n != 0	25✔
95	h ⊻= hash_uint((n % UInt) ⊻ h)	×
96	n >>>= sizeof(UInt) << 3	×
97	end	×
98	return h	25✔
99	end
100
101	## symbol & expression hashing ##
102
103	if UInt === UInt64
104	hash(x::Expr, h::UInt) = hash(x.args, hash(x.head, h + 0x83c7900696d26dc6))	56✔
105	hash(x::QuoteNode, h::UInt) = hash(x.value, h + 0x2c97bf8b3de87020)	46✔
106	else
107	hash(x::Expr, h::UInt) = hash(x.args, hash(x.head, h + 0x96d26dc6))	×
108	hash(x::QuoteNode, h::UInt) = hash(x.value, h + 0x469d72af)	×
109	end
110
111	## hashing strings ##
112
113	const memhash = UInt === UInt64 ? :memhash_seed : :memhash32_seed
114	const memhash_seed = UInt === UInt64 ? 0x71e729fd56419c81 : 0x56419c81
115
116	@assume_effects :total function hash(s::String, h::UInt)	1,841✔
117	h += memhash_seed	4,831,444✔
118	ccall(memhash, UInt, (Ptr{UInt8}, Csize_t, UInt32), s, sizeof(s), h % UInt32) + h	4,831,444✔
119	end

JuliaLang / julia / #37632

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous