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
Raw File
.gitattributes
# treat all files as files that should not be modified
* -text
back to top