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
sysimage.mk
SRCDIR := $(abspath $(dir $(lastword $(MAKEFILE_LIST))))
BUILDDIR := .
JULIAHOME := $(SRCDIR)
include $(JULIAHOME)/Make.inc
default: sysimg-$(JULIA_BUILD_MODE) # contains either "debug" or "release"
all: sysimg-release sysimg-debug
sysimg-ji: $(build_private_libdir)/sys.ji
sysimg-bc: $(build_private_libdir)/sys-bc.a
sysimg-release: $(build_private_libdir)/sys.$(SHLIB_EXT)
sysimg-debug: $(build_private_libdir)/sys-debug.$(SHLIB_EXT)
VERSDIR := v`cut -d. -f1-2 < $(JULIAHOME)/VERSION`
$(build_private_libdir)/%.$(SHLIB_EXT): $(build_private_libdir)/%-o.a
@$(call PRINT_LINK, $(CXX) $(LDFLAGS) -shared $(fPIC) -L$(build_private_libdir) -L$(build_libdir) -L$(build_shlibdir) -o $@ \
$(WHOLE_ARCHIVE) $< $(NO_WHOLE_ARCHIVE) \
$(if $(findstring -debug,$(notdir $@)),-ljulia-internal-debug -ljulia-debug,-ljulia-internal -ljulia) \
$$([ $(OS) = WINNT ] && echo '' -lssp))
@$(INSTALL_NAME_CMD)$(notdir $@) $@
@$(DSYMUTIL) $@
COMPILER_SRCS := $(addprefix $(JULIAHOME)/, \
base/boot.jl \
base/docs/core.jl \
base/abstractarray.jl \
base/abstractdict.jl \
base/array.jl \
base/bitarray.jl \
base/bitset.jl \
base/bool.jl \
base/ctypes.jl \
base/error.jl \
base/essentials.jl \
base/expr.jl \
base/generator.jl \
base/int.jl \
base/indices.jl \
base/iterators.jl \
base/namedtuple.jl \
base/number.jl \
base/operators.jl \
base/options.jl \
base/pair.jl \
base/pointer.jl \
base/promotion.jl \
base/range.jl \
base/reflection.jl \
base/traits.jl \
base/refvalue.jl \
base/tuple.jl)
COMPILER_SRCS += $(shell find $(JULIAHOME)/base/compiler -name \*.jl)
# sort these to remove duplicates
BASE_SRCS := $(sort $(shell find $(JULIAHOME)/base -name \*.jl -and -not -name sysimg.jl) \
$(shell find $(BUILDROOT)/base -name \*.jl -and -not -name sysimg.jl))
STDLIB_SRCS := $(JULIAHOME)/base/sysimg.jl $(shell find $(build_datarootdir)/julia/stdlib/$(VERSDIR)/*/src -name \*.jl) \
$(build_prefix)/manifest/Pkg
RELBUILDROOT := $(call rel_path,$(JULIAHOME)/base,$(BUILDROOT)/base)/ # <-- make sure this always has a trailing slash
$(build_private_libdir)/corecompiler.ji: $(COMPILER_SRCS)
@$(call PRINT_JULIA, cd $(JULIAHOME)/base && \
$(call spawn,$(JULIA_EXECUTABLE)) -C "$(JULIA_CPU_TARGET)" --output-ji $(call cygpath_w,$@).tmp \
--startup-file=no --warn-overwrite=yes -g0 -O0 compiler/compiler.jl)
@mv $@.tmp $@
$(build_private_libdir)/sys.ji: $(build_private_libdir)/corecompiler.ji $(JULIAHOME)/VERSION $(BASE_SRCS) $(STDLIB_SRCS)
@$(call PRINT_JULIA, cd $(JULIAHOME)/base && \
if ! JULIA_BINDIR=$(call cygpath_w,$(build_bindir)) WINEPATH="$(call cygpath_w,$(build_bindir));$$WINEPATH" \
$(call spawn, $(JULIA_EXECUTABLE)) -g1 -O0 -C "$(JULIA_CPU_TARGET)" --output-ji $(call cygpath_w,$@).tmp $(JULIA_SYSIMG_BUILD_FLAGS) \
--startup-file=no --warn-overwrite=yes --sysimage $(call cygpath_w,$<) sysimg.jl $(RELBUILDROOT); then \
echo '*** This error might be fixed by running `make clean`. If the error persists$(COMMA) try `make cleanall`. ***'; \
false; \
fi )
@mv $@.tmp $@
define sysimg_builder
$$(build_private_libdir)/sys$1-o.a $$(build_private_libdir)/sys$1-bc.a : $$(build_private_libdir)/sys$1-%.a : $$(build_private_libdir)/sys.ji
@$$(call PRINT_JULIA, cd $$(JULIAHOME)/base && \
if ! JULIA_BINDIR=$$(call cygpath_w,$(build_bindir)) WINEPATH="$$(call cygpath_w,$$(build_bindir));$$$$WINEPATH" \
$$(call spawn, $3) $2 -C "$$(JULIA_CPU_TARGET)" --output-$$* $$(call cygpath_w,$$@).tmp $$(JULIA_SYSIMG_BUILD_FLAGS) \
--startup-file=no --warn-overwrite=yes --sysimage $$(call cygpath_w,$$<) $$(call cygpath_w,$$(JULIAHOME)/contrib/generate_precompile.jl) $(JULIA_PRECOMPILE); then \
echo '*** This error is usually fixed by running `make clean`. If the error persists$$(COMMA) try `make cleanall`. ***'; \
false; \
fi )
@mv $$@.tmp $$@
.SECONDARY: $$(build_private_libdir)/sys$1-o.a $(build_private_libdir)/sys$1-bc.a # request Make to keep these files around
endef
$(eval $(call sysimg_builder,,-O3,$(JULIA_EXECUTABLE_release)))
$(eval $(call sysimg_builder,-debug,-O0,$(JULIA_EXECUTABLE_debug)))
Computing file changes ...
