Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Compiler bug uncovered by BaseBenchmarks #29107

Closed
Keno opened this issue Sep 9, 2018 · 8 comments · Fixed by #29140
Closed

Compiler bug uncovered by BaseBenchmarks #29107

Keno opened this issue Sep 9, 2018 · 8 comments · Fixed by #29140
Labels
bug Indicates an unexpected problem or unintended behavior compiler:optimizer Optimization passes (mostly in base/compiler/ssair/)

Comments

@Keno
Copy link
Member

Keno commented Sep 9, 2018

Last night's nanosolider run showed regressions in the perf_sumvector benchmarks. Running those locally, we see that they in fact trigger a compiler error:

julia> function perf_sumvector(A)
           s = zero(eltype(A))
           nrows = size(A, 1)
           ncols = size(A, 2)
           r = rand(1:nrows, 5)
           @simd for i = 1:ncols
               val = Base.unsafe_getindex(A, r, i)
               s += first(val)
           end
           return s
       end
perf_sumvector (generic function with 1 method)

julia> using BenchmarkTools
[ Info: Recompiling stale cache file /home/keno/.julia/compiled/v1.1/BenchmarkTools/ZXPQo.ji for BenchmarkTools [6e4b80f9-dd63-53aa-95a3-0cdb28fa8baf]

julia> @btime perf_sumvector($(1:100000))
Internal error: encountered unexpected error in runtime:
BoundsError(a=Array{Core.Compiler.NewNode, (0,)}[], i=(1,))
rec_backtrace at /home/keno/julia-1.0/src/stackwalk.c:94
record_backtrace at /home/keno/julia-1.0/src/task.c:249
jl_throw at /home/keno/julia-1.0/src/task.c:580
jl_bounds_error_ints at /home/keno/julia-1.0/src/rtutils.c:187
getindex at ./array.jl:731 [inlined]
abstract_eval_ssavalue at ./compiler/ssair/queries.jl:59 [inlined]
argextype at ./compiler/utilities.jl:181
argextype at ./compiler/utilities.jl:167 [inlined]
stmt_effect_free at ./compiler/ssair/queries.jl:28
maybe_erase_unused! at ./compiler/ssair/ir.jl:1130
maybe_erase_unused! at ./compiler/ssair/ir.jl:1125 [inlined]
@ararslan ararslan added bug Indicates an unexpected problem or unintended behavior compiler:optimizer Optimization passes (mostly in base/compiler/ssair/) labels Sep 9, 2018
@Keno Keno changed the title Compiler uncovered by BaseBenchmarks Compiler bug uncovered by BaseBenchmarks Sep 9, 2018
@Keno
Copy link
Member Author

Keno commented Sep 9, 2018

For my own reference:

bench = BenchmarkTools.@benchmarkable perf_sumvector($(1:100))
@NI.code_typed BenchmarkTools._run(bench, bench.params)

The issue seems to be that the pass is looking at invalid IR in dead code (which I explicitly allowed in the CFG transform PR to avoid having to figure out instantaneously what code is dead). I guess I do have to track that.

@Keno
Copy link
Member Author

Keno commented Sep 9, 2018

My intuition says we should compute and keep dfs numbers and update them on edge deletion, but that doesn't seem like a super great option, so I'm open to other suggestions.

@Keno
Copy link
Member Author

Keno commented Sep 10, 2018

Of course we could also consider just keeping the domtree updated.

@macd
Copy link
Contributor

macd commented Sep 11, 2018

It looks like I have run into the same (or similar) problem with ApproxFun. This error started happening on master on Friday (I think?) Here is the trigger and the top of the stack trace. It looks like the error is occuring when eval'ing what will become sinh for the Funs. It actually completes and on subsequent call to tanh, sinh everything is fine so it is in the eval, I think, located at
sinh at /home/macd/jlang/ApproxFun.jl/src/Extras/specialfunctions.jl:429
Here's the dump:

               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.1.0-DEV.232 (2018-09-10)
 _/ |\__'_|_|_|\__'_|  |  Commit 6caabc9d8b (0 days old master)
|__/                   |

julia (v1.1)> using ApproxFun

julia (v1.1)> x = Fun()
Fun(Chebyshev(【-1.0,1.0】),[0.0, 1.0])

julia (v1.1)> f = tanh(4x - 1)
Internal error: encountered unexpected error in runtime:
BoundsError(a=Array{Int64, (55,)}[0, 1, 1, 1, 4, 5, 6, 7, 8, 9, 9, 11, 11, 11, 9, 15, 16, 17, 18, 18, 18, 21, 22, 23, 24, 25, 26, 27, 0, 0, 0, 0, 28, 33, 33, 34, 36, 37, 38, 39, 40, 41, 41, 42, 44, 45, 46, 24, 22, 49, 49, 49, 52, 21, 5], i=(0,))
rec_backtrace at /home/macd/julia/src/stackwalk.c:94
record_backtrace at /home/macd/julia/src/task.c:249
jl_throw at /home/macd/julia/src/task.c:580
jl_bounds_error_ints at /home/macd/julia/src/rtutils.c:187
getindex at ./array.jl:731 [inlined]
find_curblock at ./compiler/ssair/passes.jl:58
compute_value_for_use at ./compiler/ssair/passes.jl:86
getfield_elim_pass! at ./compiler/ssair/passes.jl:771
run_passes at ./compiler/ssair/driver.jl:123
optimize at ./compiler/optimize.jl:162
typeinf at ./compiler/typeinfer.jl:35
typeinf_edge at ./compiler/typeinfer.jl:492
abstract_call_method at ./compiler/abstractinterpretation.jl:342
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:81
abstract_call at ./compiler/abstractinterpretation.jl:790
abstract_eval_call at ./compiler/abstractinterpretation.jl:819
abstract_eval at ./compiler/abstractinterpretation.jl:904
typeinf_local at ./compiler/abstractinterpretation.jl:1128
typeinf_nocycle at ./compiler/abstractinterpretation.jl:1184
typeinf at ./compiler/typeinfer.jl:15
typeinf_edge at ./compiler/typeinfer.jl:492
abstract_call_method at ./compiler/abstractinterpretation.jl:342
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:81
abstract_call at ./compiler/abstractinterpretation.jl:790
abstract_eval_call at ./compiler/abstractinterpretation.jl:819
abstract_eval at ./compiler/abstractinterpretation.jl:904
typeinf_local at ./compiler/abstractinterpretation.jl:1128
typeinf_nocycle at ./compiler/abstractinterpretation.jl:1184
typeinf at ./compiler/typeinfer.jl:15
typeinf_edge at ./compiler/typeinfer.jl:492
abstract_call_method at ./compiler/abstractinterpretation.jl:342
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:81
abstract_call at ./compiler/abstractinterpretation.jl:790
abstract_eval_call at ./compiler/abstractinterpretation.jl:819
abstract_eval at ./compiler/abstractinterpretation.jl:904
typeinf_local at ./compiler/abstractinterpretation.jl:1128
typeinf_nocycle at ./compiler/abstractinterpretation.jl:1184
typeinf at ./compiler/typeinfer.jl:15
typeinf_edge at ./compiler/typeinfer.jl:492
abstract_call_method at ./compiler/abstractinterpretation.jl:342
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:81
abstract_call at ./compiler/abstractinterpretation.jl:790
abstract_eval_call at ./compiler/abstractinterpretation.jl:819
abstract_eval at ./compiler/abstractinterpretation.jl:904
typeinf_local at ./compiler/abstractinterpretation.jl:1128
typeinf_nocycle at ./compiler/abstractinterpretation.jl:1184
typeinf at ./compiler/typeinfer.jl:15
typeinf_edge at ./compiler/typeinfer.jl:492
abstract_call_method at ./compiler/abstractinterpretation.jl:342
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:81
abstract_call at ./compiler/abstractinterpretation.jl:790
abstract_eval_call at ./compiler/abstractinterpretation.jl:819
abstract_eval at ./compiler/abstractinterpretation.jl:904
typeinf_local at ./compiler/abstractinterpretation.jl:1128
typeinf_nocycle at ./compiler/abstractinterpretation.jl:1184
typeinf at ./compiler/typeinfer.jl:15
typeinf_edge at ./compiler/typeinfer.jl:492
abstract_call_method at ./compiler/abstractinterpretation.jl:342
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:81
abstract_call at ./compiler/abstractinterpretation.jl:790
abstract_eval_call at ./compiler/abstractinterpretation.jl:819
abstract_eval at ./compiler/abstractinterpretation.jl:904
typeinf_local at ./compiler/abstractinterpretation.jl:1128
typeinf_nocycle at ./compiler/abstractinterpretation.jl:1184
typeinf at ./compiler/typeinfer.jl:15
typeinf_edge at ./compiler/typeinfer.jl:492
abstract_call_method at ./compiler/abstractinterpretation.jl:342
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:81
abstract_call at ./compiler/abstractinterpretation.jl:790
abstract_eval_call at ./compiler/abstractinterpretation.jl:819
abstract_eval at ./compiler/abstractinterpretation.jl:904
typeinf_local at ./compiler/abstractinterpretation.jl:1128
typeinf_nocycle at ./compiler/abstractinterpretation.jl:1184
typeinf at ./compiler/typeinfer.jl:15
typeinf_edge at ./compiler/typeinfer.jl:492
abstract_call_method at ./compiler/abstractinterpretation.jl:342
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:81
abstract_call at ./compiler/abstractinterpretation.jl:790
abstract_eval_call at ./compiler/abstractinterpretation.jl:819
abstract_eval at ./compiler/abstractinterpretation.jl:904
typeinf_local at ./compiler/abstractinterpretation.jl:1128
typeinf_nocycle at ./compiler/abstractinterpretation.jl:1184
typeinf at ./compiler/typeinfer.jl:15
typeinf_ext at ./compiler/typeinfer.jl:567
typeinf_ext at ./compiler/typeinfer.jl:604
jfptr_typeinf_ext_1 at /home/macd/julia/usr/lib/julia/sys.so (unknown line)
jl_apply_generic at /home/macd/julia/src/gf.c:2198
jl_apply at /home/macd/julia/src/julia.h:1559 [inlined]
jl_apply_with_saved_exception_state at /home/macd/julia/src/rtutils.c:257
jl_type_infer at /home/macd/julia/src/gf.c:275
jl_compile_method_internal at /home/macd/julia/src/gf.c:1798 [inlined]
jl_fptr_trampoline at /home/macd/julia/src/gf.c:1842
jl_apply_generic at /home/macd/julia/src/gf.c:2198
sinh at /home/macd/jlang/ApproxFun.jl/src/Extras/specialfunctions.jl:429
tanh at /home/macd/jlang/ApproxFun.jl/src/Extras/specialfunctions.jl:481
jl_fptr_trampoline at /home/macd/julia/src/gf.c:1843
jl_apply_generic at /home/macd/julia/src/gf.c:2198
do_call at /home/macd/julia/src/interpreter.c:324
eval_value at /home/macd/julia/src/interpreter.c:430
eval_stmt_value at /home/macd/julia/src/interpreter.c:363 [inlined]
eval_body at /home/macd/julia/src/interpreter.c:688
jl_interpret_toplevel_thunk_callback at /home/macd/julia/src/interpreter.c:803

Keno added a commit that referenced this issue Sep 11, 2018
@Keno
WIP: Better dominators
addfc97 
This commit replaces the naive algorithm for replacing dominator
trees by a faster implementation based on the Semi-NCA algorithm
(reference in the code comments). LLVM recently switched to this
algorithm and found it to be faster in practice than SLT (which
it used before). It is also slightly easier to implement. More
importantly though, it should easily extend to dynamic dominators.

I'm hoping this will fix the performance problems with constructing
dominators noted in #25927 as well as providing the basis for a
dynamic dominator implementation to fix #29107.
@Keno Keno mentioned this issue Sep 11, 2018
Merged
Keno added a commit that referenced this issue Sep 12, 2018
@Keno
WIP: Better dominators
e88b69f 
This commit replaces the naive algorithm for replacing dominator
trees by a faster implementation based on the Semi-NCA algorithm
(reference in the code comments). LLVM recently switched to this
algorithm and found it to be faster in practice than SLT (which
it used before). It is also slightly easier to implement. More
importantly though, it should easily extend to dynamic dominators.

I'm hoping this will fix the performance problems with constructing
dominators noted in #25927 as well as providing the basis for a
dynamic dominator implementation to fix #29107.
@thofma
Copy link
Contributor

thofma commented Sep 17, 2018

I am seeing the following error in Hecke on julia master. Is this the same?

Internal error: encountered unexpected error in runtime:
BoundsError(a=Array{Any, (512,)}[
 ...
 rec_backtrace at /tmpbig/thofmann/juliagit/src/stackwalk.c:94
record_backtrace at /tmpbig/thofmann/juliagit/src/task.c:249
jl_throw at /tmpbig/thofmann/juliagit/src/task.c:580
jl_bounds_error_ints at /tmpbig/thofmann/juliagit/src/rtutils.c:187
getindex at ./array.jl:731 [inlined]
fixup_phinode_values! at ./compiler/ssair/ir.jl:1159
fixup_node at ./compiler/ssair/ir.jl:1173
just_fixup! at ./compiler/ssair/ir.jl:1198
non_dce_finish! at ./compiler/ssair/ir.jl:1231
finish at ./compiler/ssair/ir.jl:1240 [inlined]
batch_inline! at ./compiler/ssair/inlining.jl:557
ssa_inlining_pass! at ./compiler/ssair/inlining.jl:63 [inlined]
run_passes at ./compiler/ssair/driver.jl:118
optimize at ./compiler/optimize.jl:162
typeinf at ./compiler/typeinfer.jl:35
typeinf_edge at ./compiler/typeinfer.jl:492
abstract_call_method at ./compiler/abstractinterpretation.jl:342

@Keno
Copy link
Member Author

Keno commented Sep 17, 2018

Yes, could be related, but not necessarily. I'm hoping to have this fixed properly shortly. If not resolved afterwards, please file as a separate issue.

Keno added a commit that referenced this issue Sep 19, 2018
@Keno
Disable CFG transforms for now
e7e238f 
CFG transforms can currently cause issues like #29107,
but I'm still a few days away from fixing this properly. In the meantime,
disable the transform.
This was referenced Sep 19, 2018
Merged
Closed
Keno added a commit that referenced this issue Sep 21, 2018
@Keno
Disable CFG transforms for now
cbc1922 
CFG transforms can currently cause issues like #29107,
but I'm still a few days away from fixing this properly. In the meantime,
disable the transform.
Keno added a commit that referenced this issue Sep 21, 2018
@Keno
Disable CFG transforms for now (#29265)
2fd386c 
CFG transforms can currently cause issues like #29107,
but I'm still a few days away from fixing this properly. In the meantime,
disable the transform.
@mbauman
Copy link
Sponsor Member

mbauman commented Sep 21, 2018

I saw a very similar issue with CSV#master and can confirm that #29265 fixed it. Can this issue be closed?

julia> using CSV
[ Info: Precompiling CSV [336ed68f-0bac-5ca0-87d4-7b16caf5d00b]
Internal error: encountered unexpected error in runtime:
BoundsError(a=Array{Int64, (7,)}[1, 2, 3, 4, 5, 6, 7], i=(0,))
rec_backtrace at /home/mbauman/julia/src/stackwalk.c:94
record_backtrace at /home/mbauman/julia/src/task.c:249
jl_throw at /home/mbauman/julia/src/task.c:580
jl_bounds_error_ints at /home/mbauman/julia/src/rtutils.c:182
getindex at ./array.jl:731 [inlined]
#235 at ./compiler/ssair/ir.jl:924
jfptr_#235_2351 at /home/mbauman/julia/usr/lib/julia/sys.so (unknown line)
jl_apply_generic at /home/mbauman/julia/src/gf.c:2198
map! at ./abstractarray.jl:1990
process_node! at ./compiler/ssair/ir.jl:924
process_node! at ./compiler/ssair/ir.jl:945 [inlined]
iterate at ./compiler/ssair/ir.jl:1109
getfield_elim_pass! at ./compiler/ssair/passes.jl:688
run_passes at ./compiler/ssair/driver.jl:123
optimize at ./compiler/optimize.jl:162

@Keno
Copy link
Member Author

Keno commented Sep 21, 2018

I do want to fix this, so I'll leave this issue open. That PR just reverted the compiler improvement that uncovered this.

@quinnj quinnj mentioned this issue Sep 22, 2018
Closed
@mschauer mschauer mentioned this issue Sep 30, 2018
Closed
Keno added a commit that referenced this issue Oct 3, 2018
@Keno
WIP: Better dominators
c3703e7 
This commit replaces the naive algorithm for replacing dominator
trees by a faster implementation based on the Semi-NCA algorithm
(reference in the code comments). LLVM recently switched to this
algorithm and found it to be faster in practice than SLT (which
it used before). It is also slightly easier to implement. More
importantly though, it should easily extend to dynamic dominators.

I'm hoping this will fix the performance problems with constructing
dominators noted in #25927 as well as providing the basis for a
dynamic dominator implementation to fix #29107.
Keno added a commit that referenced this issue Oct 4, 2018
@Keno
Better dominators
12a948c 
This commit replaces the naive algorithm for replacing dominator
trees by a faster implementation based on the Semi-NCA algorithm
(reference in the code comments). LLVM recently switched to this
algorithm and found it to be faster in practice than SLT (which
it used before). It is also slightly easier to implement. More
importantly though, it should easily extend to dynamic dominators.

This fixes the preformance problems in dominator construction noted
in #25927 and should provide a basis for a dynamic dominator
implementation to fix #29107.
Keno added a commit that referenced this issue Oct 5, 2018
@Keno
Better dominators
8ff75ad 
This commit replaces the naive algorithm for replacing dominator
trees by a faster implementation based on the Semi-NCA algorithm
(reference in the code comments). LLVM recently switched to this
algorithm and found it to be faster in practice than SLT (which
it used before). It is also slightly easier to implement. More
importantly though, it should easily extend to dynamic dominators.

This fixes the preformance problems in dominator construction noted
in #25927 and should provide a basis for a dynamic dominator
implementation to fix #29107.
jrevels pushed a commit that referenced this issue Dec 31, 2018
@Keno @jrevels
Disable CFG transforms for now (#29265)
ae4221f 
CFG transforms can currently cause issues like #29107,
but I'm still a few days away from fixing this properly. In the meantime,
disable the transform.
yhls added a commit to yhls/julia that referenced this issue Oct 15, 2019
@yhls
Decline to remove phi nodes when this might cause forward references
2e6848a 
Phi nodes are optimized away when there is only one predecessor, but this can
cause problems in dead loops because forward references can be created, leading
to issues with optimization passes that look at all code, dead or not. This
addresses issue JuliaLang#29107 when DCE is turned on.
yhls added a commit to yhls/julia that referenced this issue Oct 31, 2019
@yhls
Decline to remove phi nodes when this might cause forward references
761dbdf 
Phi nodes are optimized away when there is only one predecessor, but this can
cause problems in dead loops because forward references can be created, leading
to issues with optimization passes that look at all code, dead or not. This
addresses issue JuliaLang#29107 when DCE is turned on.
@yhls yhls mentioned this issue Oct 31, 2019
Closed
yhls added a commit to yhls/julia that referenced this issue Nov 1, 2019
@yhls
Decline to remove phi nodes when this might cause forward references
720bf3e 
Phi nodes are optimized away when there is only one predecessor, but this can
cause problems in dead loops because forward references can be created, leading
to issues with optimization passes that look at all code, dead or not. This
addresses issue JuliaLang#29107 when DCE is turned on.
yhls added a commit to yhls/julia that referenced this issue Nov 25, 2019
@yhls
Decline to remove phi nodes when this might cause forward references
6542194 
Phi nodes are optimized away when there is only one predecessor, but this can
cause problems in dead loops because forward references can be created, leading
to issues with optimization passes that look at all code, dead or not. This
addresses issue JuliaLang#29107 when DCE is turned on.
yhls added a commit to yhls/julia that referenced this issue Dec 15, 2019
@yhls
Decline to remove phi nodes when this might cause forward references
38344b4 
Phi nodes are optimized away when there is only one predecessor, but this can
cause problems in dead loops because forward references can be created, leading
to issues with optimization passes that look at all code, dead or not. This
fixes issue JuliaLang#29107 when DCE is turned on.
yhls added a commit to yhls/julia that referenced this issue Dec 17, 2019
@yhls
Decline to remove phi nodes when this might cause forward references
4b146f2 
Phi nodes are optimized away when there is only one predecessor, but this can
cause problems in dead loops because forward references can be created, leading
to issues with optimization passes that look at all code, dead or not. This
fixes issue JuliaLang#29107 when DCE is turned on.
yhls added a commit to yhls/julia that referenced this issue Mar 11, 2020
@yhls
Decline to remove phi nodes when this might cause forward references
38b67dd 
Phi nodes are optimized away when there is only one predecessor, but this can
cause problems in dead loops because forward references can be created, leading
to issues with optimization passes that look at all code, dead or not. This
fixes issue JuliaLang#29107 when DCE is turned on.
yhls added a commit to yhls/julia that referenced this issue Apr 1, 2020
@yhls
Decline to remove phi nodes when this might cause forward references
4924675 
Phi nodes are optimized away when there is only one predecessor, but this can
cause problems in dead loops because forward references can be created, leading
to issues with optimization passes that look at all code, dead or not. This
fixes issue JuliaLang#29107 when DCE is turned on.
yhls added a commit to yhls/julia that referenced this issue Aug 3, 2020
@yhls
Decline to remove phi nodes when this might cause forward references
bb6e299 
Phi nodes are optimized away when there is only one predecessor, but this can
cause problems in dead loops because forward references can be created, leading
to issues with optimization passes that look at all code, dead or not. This
fixes issue JuliaLang#29107 when DCE is turned on.
vchuravy pushed a commit that referenced this issue Aug 21, 2020
@yhls @vchuravy
Decline to remove phi nodes when this might cause forward references
219791f 
Phi nodes are optimized away when there is only one predecessor, but this can
cause problems in dead loops because forward references can be created, leading
to issues with optimization passes that look at all code, dead or not. This
fixes issue #29107 when DCE is turned on.
simeonschaub pushed a commit to simeonschaub/julia that referenced this issue Aug 29, 2020
@yhls @simeonschaub
Decline to remove phi nodes when this might cause forward references
fd4b96c 
Phi nodes are optimized away when there is only one predecessor, but this can
cause problems in dead loops because forward references can be created, leading
to issues with optimization passes that look at all code, dead or not. This
fixes issue JuliaLang#29107 when DCE is turned on.
vchuravy pushed a commit that referenced this issue Oct 5, 2020
@yhls @vchuravy
Decline to remove phi nodes when this might cause forward references
567d832 
Phi nodes are optimized away when there is only one predecessor, but this can
cause problems in dead loops because forward references can be created, leading
to issues with optimization passes that look at all code, dead or not. This
fixes issue #29107 when DCE is turned on.
@topolarity topolarity mentioned this issue Jan 23, 2024
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug Indicates an unexpected problem or unintended behavior compiler:optimizer Optimization passes (mostly in base/compiler/ssair/)
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Better dominators JuliaLang/julia
5 participants
@mbauman @macd @Keno @ararslan @thofma