Revision 17e0bbaa6972585199615c5db33a85ce41f37fd2 authored by Shuhei Kadowaki on 21 October 2021, 05:52:25 UTC, committed by GitHub on 21 October 2021, 05:52:25 UTC
Adds a very simple optimization pass to eliminate `typeassert` calls. The motivation is, when SROA replaces `getfield` calls with scalar values, then we can often prove `typeassert` whose first operand is a replaced value is no-op: ```julia julia> struct Foo; x; end julia> code_typed((Int,)) do a x1 = Foo(a) x2 = Foo(x1) typeassert(x2.x, Foo).x end |> only |> first CodeInfo( 1 ─ %1 = Main.Foo::Type{Foo} │ %2 = %new(%1, a)::Foo │ Main.typeassert(%2, Main.Foo)::Foo # can be nullified └── return a ) ``` Nullifying `typeassert` helps succeeding (simple) DCE to eliminate dead allocations, and also allows LLVM to do more aggressive DCE to emit simpler code. Here is a simple benchmarking: > sample target code: ```julia julia> function compute(T, n) r = 0 for i in 1:n x1 = T(i) x2 = T(x1) r += (x2.x::T).x::Int end r end compute (generic function with 1 method) julia> struct Foo; x; end julia> mutable struct Bar; x; end ``` > on master ```julia julia> @benchmark compute(Foo, 1000) BenchmarkTools.Trial: 10000 samples with 8 evaluations. Range (min … max): 3.263 μs … 145.828 μs ┊ GC (min … max): 0.00% … 97.14% Time (median): 3.516 μs ┊ GC (median): 0.00% Time (mean ± σ): 4.015 μs ± 3.726 μs ┊ GC (mean ± σ): 3.16% ± 3.46% ▇█▆▄▅▄▄▃▂▁▂▁ ▂ ▇███████████████▇██▇▇█▇▇▆▇▇▇▇▅▆▅▇▇▅██▇▇▆▇▇▇█▇█▇▇▅▆▆▆▆▅▅▅▅▄▄ █ 3.26 μs Histogram: log(frequency) by time 8.52 μs < Memory estimate: 7.64 KiB, allocs estimate: 489. julia> @benchmark compute(Bar, 1000) BenchmarkTools.Trial: 10000 samples with 4 evaluations. Range (min … max): 6.990 μs … 288.079 μs ┊ GC (min … max): 0.00% … 97.03% Time (median): 7.657 μs ┊ GC (median): 0.00% Time (mean ± σ): 9.019 μs ± 9.710 μs ┊ GC (mean ± σ): 4.59% ± 4.28% ▆█▆▄▃▂▂▁▂▃▂▁ ▁ ▁ ██████████████████████▇▇▇▇▇▆██████▇▇█▇▇▇▆▆▆▆▅▆▅▄▄▄▅▄▄▃▄▄▂▄▅ █ 6.99 μs Histogram: log(frequency) by time 20.7 μs < Memory estimate: 23.27 KiB, allocs estimate: 1489. ``` > on this branch ```julia julia> @benchmark compute(Foo, 1000) BenchmarkTools.Trial: 10000 samples with 1000 evaluations. Range (min … max): 1.234 ns … 116.188 ns ┊ GC (min … max): 0.00% … 0.00% Time (median): 1.246 ns ┊ GC (median): 0.00% Time (mean ± σ): 1.307 ns ± 1.444 ns ┊ GC (mean ± σ): 0.00% ± 0.00% █▇ ▂▂▁ ▂ ▁ ██████▇█▇▅▄▆▇▆▁▃▄▁▁▁▁▁▃▁▃▁▁▄▇▅▃▃▃▁▃▄▁▃▃▁▃▁▁▃▁▁▁▄▃▁▃▇███▇▇▇▆ █ 1.23 ns Histogram: log(frequency) by time 1.94 ns < Memory estimate: 0 bytes, allocs estimate: 0. julia> @benchmark compute(Bar, 1000) BenchmarkTools.Trial: 10000 samples with 1000 evaluations. Range (min … max): 1.234 ns … 33.790 ns ┊ GC (min … max): 0.00% … 0.00% Time (median): 1.245 ns ┊ GC (median): 0.00% Time (mean ± σ): 1.297 ns ± 0.677 ns ┊ GC (mean ± σ): 0.00% ± 0.00% █▇ ▃▂▁ ▁ ██████▆▆▅▁▄▅▅▄▁▄▄▄▃▄▃▁▃▁▃▄▃▁▃▁▃▁▁▁▃▃▁▃▃▁▁▁▁▁▁▁▃▁▄█████▇▇▇▇ █ 1.23 ns Histogram: log(frequency) by time 1.96 ns < Memory estimate: 0 bytes, allocs estimate: 0. ``` This `typeassert` elimination would be much more effective if we implement more aggressive SROA based on strong [alias analysis](https://github.com/aviatesk/EscapeAnalysis.jl) and/or [more aggressive Julia-level DCE](https://github.com/JuliaLang/julia/issues/27547). But this change is so simple that I don't think it hurts anything to have it for now.
1 parent a4903fd
File | Mode | Size |
---|---|---|
.buildkite | ||
.devcontainer | ||
.github | ||
base | ||
cli | ||
contrib | ||
deps | ||
doc | ||
etc | ||
src | ||
stdlib | ||
test | ||
.clang-format | -rw-r--r-- | 3.3 KB |
.codecov.yml | -rw-r--r-- | 52 bytes |
.gitattributes | -rw-r--r-- | 65 bytes |
.gitignore | -rw-r--r-- | 291 bytes |
.mailmap | -rw-r--r-- | 11.1 KB |
CITATION.bib | -rw-r--r-- | 513 bytes |
CITATION.cff | -rw-r--r-- | 942 bytes |
CONTRIBUTING.md | -rw-r--r-- | 19.8 KB |
HISTORY.md | -rw-r--r-- | 333.2 KB |
LICENSE.md | -rw-r--r-- | 1.3 KB |
Make.inc | -rw-r--r-- | 49.1 KB |
Makefile | -rw-r--r-- | 25.5 KB |
NEWS.md | -rw-r--r-- | 5.4 KB |
README.md | -rw-r--r-- | 7.4 KB |
THIRDPARTY.md | -rw-r--r-- | 3.6 KB |
VERSION | -rw-r--r-- | 10 bytes |
sysimage.mk | -rw-r--r-- | 4.0 KB |
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...