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.

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

panic: Ran out of registers in GPR #335

Closed
Amanieu opened this issue May 17, 2018 · 4 comments

Comments

3 participants
@Amanieu
Copy link
Contributor

commented May 17, 2018

Cretonne crashes when trying to compile AngryBots1.wasm from wasm-collection:

RUST_BACKTRACE=1 target/release/cton-util wasm -T --set is_64bit=1 --isa x86 ../wasm-collection/misc-valid/AngryBots1.wasm
thread 'main' panicked at 'Invalid type for vsplit', libcore/option.rs:914:5
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
   1: std::sys_common::backtrace::print
             at libstd/sys_common/backtrace.rs:71
             at libstd/sys_common/backtrace.rs:59
   2: std::panicking::default_hook::{{closure}}
             at libstd/panicking.rs:211
   3: std::panicking::default_hook
             at libstd/panicking.rs:227
   4: std::panicking::rust_panic_with_hook
             at libstd/panicking.rs:463
   5: std::panicking::begin_panic_fmt
             at libstd/panicking.rs:350
   6: rust_begin_unwind
             at libstd/panicking.rs:328
   7: core::panicking::panic_fmt
             at libcore/panicking.rs:71
   8: core::option::expect_failed
             at libcore/option.rs:914
   9: cretonne_codegen::legalizer::split::split_value
             at /checkout/src/libcore/option.rs:302
             at lib/codegen/src/legalizer/split.rs:216
  10: cretonne_codegen::legalizer::split::split_any
             at lib/codegen/src/legalizer/split.rs:125
  11: cretonne_codegen::legalizer::boundary::convert_to_abi
             at lib/codegen/src/legalizer/split.rs:0
  12: cretonne_codegen::legalizer::boundary::handle_call_abi
             at lib/codegen/src/legalizer/boundary.rs:476
             at lib/codegen/src/legalizer/boundary.rs:505
  13: cretonne_codegen::legalizer::legalize_function
             at lib/codegen/src/legalizer/mod.rs:47
             at lib/codegen/src/legalizer/mod.rs:101
  14: cretonne_codegen::context::Context::compile
             at lib/codegen/src/context.rs:231
             at lib/codegen/src/context.rs:131
  15: cton_util::wasm::run
             at src/wasm.rs:161
             at src/wasm.rs:52
  16: cton_util::main
             at src/cton-util.rs:117
             at src/cton-util.rs:140
  17: std::rt::lang_start::{{closure}}
             at /checkout/src/libstd/rt.rs:74
  18: std::panicking::try::do_call
             at libstd/rt.rs:59
             at libstd/panicking.rs:310
  19: __rust_maybe_catch_panic
             at libpanic_unwind/lib.rs:105
  20: std::rt::lang_start_internal
             at libstd/panicking.rs:289
             at libstd/panic.rs:374
             at libstd/rt.rs:58
  21: main
  22: __libc_start_main
  23: _start
@sunfishcode

This comment has been minimized.

Copy link
Member

commented May 29, 2018

The original crash was fixed in #353, but AngryBots1.wasm still fails:

thread 'main' panicked at 'Ran out of registers in GPR', lib/codegen/src/regalloc/coloring.rs:846:21
stack backtrace:
[...]
   5: std::panicking::begin_panic_fmt
             at libstd/panicking.rs:349
   6: cretonne_codegen::regalloc::coloring::Context::iterate_solution
             at lib/codegen/src/regalloc/coloring.rs:846
   7: cretonne_codegen::regalloc::coloring::Context::visit_inst::{{closure}}
             at lib/codegen/src/regalloc/coloring.rs:423
   8: <core::result::Result<T, E>>::unwrap_or_else
             at /checkout/src/libcore/result.rs:748
   9: cretonne_codegen::regalloc::coloring::Context::visit_inst
             at lib/codegen/src/regalloc/coloring.rs:421
  10: cretonne_codegen::regalloc::coloring::Context::visit_ebb
             at lib/codegen/src/regalloc/coloring.rs:170
  11: cretonne_codegen::regalloc::coloring::Context::run
             at lib/codegen/src/regalloc/coloring.rs:153
  12: cretonne_codegen::regalloc::coloring::Coloring::run
             at lib/codegen/src/regalloc/coloring.rs:138
  13: cretonne_codegen::regalloc::context::Context::run
             at lib/codegen/src/regalloc/context.rs:143
  14: cretonne_codegen::context::Context::regalloc
             at lib/codegen/src/context.rs:292
  15: cretonne_codegen::context::Context::compile
             at lib/codegen/src/context.rs:146
  16: cton_util::wasm::handle_module
             at src/wasm.rs:149
  17: cton_util::wasm::run
             at src/wasm.rs:49
  18: cton_util::cton_util
             at src/cton-util.rs:119
  19: cton_util::main
             at src/cton-util.rs:147
@sunfishcode

This comment has been minimized.

Copy link
Member

commented Jun 26, 2018

Here's a reduced testcase:

target x86_64

function u0:587() fast {
ebb0:
    v97 = iconst.i32 0
    v169 = iconst.i32 0
    v1729 = iconst.i32 0
    jump ebb100(v97, v97, v97, v97, v97)

ebb100(v1758: i32, v1784: i32, v1845: i32, v1856: i32, v1870: i32):
    v1762 = iconst.i32 0
    v1769 = iconst.i32 0
    v1774 = iconst.i32 0
    v1864 = iconst.i32 0
    v1897 = iconst.i32 0
    jump ebb102(v1774, v1784, v1845, v1856, v1870, v1758, v1762, v169, v1729, v97, v169, v169, v169, v169)

ebb102(v1785: i32, v1789: i32, v1843: i32, v1854: i32, v1868: i32, v1882: i32, v1890: i32, v1901: i32, v1921: i32, v1933: i32, v2058: i32, v2124: i32, v2236: i32, v2366: i32):
    v1929 = iconst.i32 0
    v1943 = iconst.i32 0
    v1949 = iconst.i32 0
    jump ebb123(v1897, v1769)

ebb123(v1950: i32, v1979: i32):
    v1955 = iconst.i32 0
    brz v1955, ebb125
    jump ebb122(v1929, v1843, v1864, v2058, v1882, v1897, v1943, v1868, v2124, v1901)

ebb125:
    v1961 = iadd.i32 v1949, v169
    v1952 = iconst.i32 0
    v1962 = iconst.i64 0
    v1963 = load.i32 v1962
    brz v1963, ebb123(v1952, v1961)
    jump ebb127

ebb127:
    v1966 = iconst.i32 0
    jump ebb122(v1963, v1966, v1966, v1966, v1966, v1966, v1966, v1966, v1966, v1966)

ebb122(v1967: i32, v1971: i32, v1972: i32, v1978: i32, v2032: i32, v2041: i32, v2053: i32, v2076: i32, v2085: i32, v2096: i32):
    trap user0
}
cton-util compile test.cton 
thread 'main' panicked at 'Ran out of registers in GPR', lib/codegen/src/regalloc/coloring.rs:846:21

The problem is that the coloring pass is unable to solve the constraint system. My current thinking is that the current regalloc design defers too many regalloc concerns until the coloring pass, which then has to solve them all at once.

@sunfishcode sunfishcode changed the title Invalid type for vsplit panic: Ran out of registers in GPR Jun 26, 2018

@sunfishcode

This comment has been minimized.

Copy link
Member

commented Sep 6, 2018

The strategy in SSA register allocation is to first spill values to the stack, and then perform coloring to assign registers to values. It's the spilling pass's job to ensure that coloring will have enough registers to do its job.

This is usually straightforward, because the spiller knows how many registers are live at any given point and knows how many registers the machine has. However, the spiller doesn't know about special register class constraints. It knows how many GPRs there are, but doesn't know that some instructions need GPR_ZERO_DEREF_SAFE, which is a subset of the GPRs that excludes r12 and r13.

r12 and r13 make memory operands a different size on x86:

$ cat t.s
movq (%r10), %rcx
movq (%r11), %rcx
movq (%r12), %rcx
movq (%r13), %rcx
movq (%r14), %rcx
$ objdump  -dr t.o

t.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <.text>:
   0:	49 8b 0a             	mov    (%r10),%rcx
   3:	49 8b 0b             	mov    (%r11),%rcx
   6:	49 8b 0c 24          	mov    (%r12),%rcx
   a:	49 8b 4d 00          	mov    0x0(%r13),%rcx
   e:	49 8b 0e             	mov    (%r14),%rcx

Ideally, the register allocator shouldn't worry too much about this (though it may be interesting as a heuristic). However, Cranelift's instruction recipes are limited to a single fixed size, and are selected before register allocation. They don't support having a size which depends on which registers are selected. So the result is that we're pushing these extra constraints onto the coloring pass, where even if it could handle them in all cases, sometimes does suboptimal things.

We should consider:

  • Refine the concept of "recipes" to have a maximum size, rather than a single fixed size, so that we can eliminate the "*_DEREF_SAFE" register classes and just let memory instructions be sized according to their registers, or
  • Drop the concept of "recipes" and move to more conventional instruction definitions.
@bnjbvr

This comment has been minimized.

Copy link
Member

commented Oct 3, 2018

I'm looking at this now. For what it's worth, r13 and rbp still can't be used when the (load|store) offset is null, because they require a displacement, which is always non-zero, if I understand correctly. So even if we can remove GPR_DEREF_SAFE (i.e. all regs without rsp/r12), could the same issue still happen with r13/rbp?

bnjbvr added a commit to bnjbvr/cranelift that referenced this issue Oct 8, 2018

bnjbvr added a commit to bnjbvr/cranelift that referenced this issue Oct 8, 2018

bnjbvr added a commit to bnjbvr/cranelift that referenced this issue Oct 8, 2018

bnjbvr added a commit to bnjbvr/cranelift that referenced this issue Oct 11, 2018

bnjbvr added a commit to bnjbvr/cranelift that referenced this issue Oct 12, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.