mu-impl-fast issueshttps://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues2017-06-23T18:15:34+10:00https://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/19Register allocation validator2017-06-23T18:15:34+10:00Yi LinRegister allocation validatorThis issue describes the algorithm for the register allocation validation in Zebu.
Eliot proposed the approach. I implemented it in Zebu, and put the pseudo code here. I am not exactly confident if I have captured all the ideas from ...This issue describes the algorithm for the register allocation validation in Zebu.
Eliot proposed the approach. I implemented it in Zebu, and put the pseudo code here. I am not exactly confident if I have captured all the ideas from Eliot, and implemented it correctly. This issue serves as a record of how the register allocation validation works. Any discussion is welcome, and it may help future work.
<br /><br />
Input: register assignment `ASSIGNED(reg) -> mreg`, and code. <br/>
Output: `PASS` if `ASSIGNED` is correct; or `ERROR` if it is not.
<br /><br />
Assumptions:
* we have correct liveness information.
* spill code (`SPILL_LOAD`/`SPILL_STORE`) is already inserted, and spilled virtual registers are replaced with short-lived virtual registers, and we know the mapping.
<br /><br />
We are trying to iterate through the code focusing on registers by maintaining an `alive set`, each entry of which is a 3-element tuple `ENTRY(reg, machine_reg, mem)`, meaning `reg` is alive (contains a valid value) at the moment in `machine_reg` and spilled location `mem`.
* `(-, machine_reg, -)` means a machine register is alive, but no virtual register and no spill location is associated.
* `(*, machine_reg, *)` means matching entries that have `machine_reg`
* `(reg?, machine_reg, *)` means matching entries that have `machine_reg`, and naming the first element as `reg` (it may exist or not)
<br /><br />
We have a few primitives about alive set
* `x <- ALIVE[block]` loads alive set for `block` and uses alias `x` for it.
* `x.ADD_ALIVE(r, m, mem)`adds `(r, m, mem)` to alive set `x`.
* `ALIVE[block] <- x` saves alive set `x` with `block`.
* `x.ASSERT_ALIVE(r, m, mem)` tries to match pattern `(r, m, mem)`. If no entry is found, ends with `ERROR`.
* `x.KILL_ALIVE(r, m, mem)` tries to match pattern `(r, m, mem)`. If any entry is found, delete the entries.
* `x.EXIST_ALIVE(r, m, mem)` tries to match pattern `(r, m, mem)`. If any entry is found, it is true.
* `x.TRIM(list)`: for any `r`, `m` in `list`, preserve them in `x`, delete other entries in `x`
* `x.INTERSECT(y)`: if `(r, m, *)` or `(-, m, *)` appear in both `x` and `y`, preserve it in `x`; otherwise delete it from `x`.
* `y <- x.COPY`: copy `x` into `y`
<br /><br />
Pseudo code:
```
// set the initial alive set for a function start
init.ADD_ALIVE(-, stack pointer, -)
init.ADD_ALIVE(-, frame pointer, -)
init.ADD_ALIVE(-, program counter, -)
init.ADD_ALIVE(-, callee saved registers, -)
init.ADD_ALIVE(-, used argument registers, -)
push entry block to work queue
ALIVE[entry block] <- init
while work queue is not empty {
pop work queue -> block
alive <- ALIVE[block]
for each inst in block {
// (1) check spill
// we only care about the variable before spilling
if inst is SPILL_LOAD(mem) -> t for var v {
alive.ASSERT_ALIVE(v, *, mem)
} else if inst is SPILL_STORE(t) -> mem for var v {
alive.ADD_ALIVE(v, -, mem)
}
// (2) check use
// when we use a register, it needs to contain a valid value
for reg in inst.virtual_register_uses() {
mreg = ASSIGNED(reg)
alive.ASSERT_ALIVE(reg, mreg, *)
}
for mreg in inst.real_register_uses() {
alive.ASSERT_ALIVE(*, mreg, *)
}
// (3) kill died regs
// when a register dies, we remove its entry from alive set
for reg in inst.virtual_register_dies() {
alive.KILL_ALIVE(reg, *, *)
}
for mreg in inst.real_register_dies() {
alive.KILL_ALIVE(*, mreg, *)
}
// (4) check and add defines
for reg in inst.virtual_register_defines() {
if reg NOT in inst.liveout() {
// when a register is defined, but doesnt live out of this instruction
// we kill its previous values from alive set (by deleting the entries)
alive.KILL_ALIVE(reg, *, *)
} else {
mreg = ASSIGNED(reg)
if NOT alive.EXIST_ALIVE(*, mreg, *) {
// mreg doesnt hold any value at the moment, we simply add an entry
alive,ADD_ALIVE(reg, mreg, -)
} else {
// we need to ensure assigning mreg will not destroy useful values
for (x?, mreg, *) in ALIVE {
if x NOT exist {
x <- reg
} else {
// we have x in mreg, and we want reg in mreg as well
if x == reg {
// overwrite value (safe)
} else {
if inst is MOVE {
// possible coalescing (safe)
} else {
// we are destroying the value of x
// and x is alive at the moment (otherwise it is killed already in step 3)
ERROR
}
}
}
alive.ADD_ALIVE(reg, mreg, -)
}
}
}
}
for mreg in inst.real_register_defines() {
if mreg NOT in inst.liveout() {
// when a register is defined, but doesnt live out of this instruction
// we kill its previous values from alive set (by deleting the entries)
alive.KILL_ALIVE(*, mreg, *)
} else {
if NOT alive.EXIST_ALIVE(*, mreg, *) {
// mreg doesnt hold any value at the moment, we simply add an entry
alive.ADD_ALIVE(-, mreg, -)
} else {
for (reg?, mreg, -) in ALIVE {
if reg NOT exist {
// we have value in mreg, but it doesnt hold value of any variables
// overwrite the value is safe
} else {
// we are holding reg in mreg, defining mreg will destroy the value of reg
ERROR
}
}
}
}
}
// finishing the block, we only preserve what are alive at the end of the block
alive.TRIM(block.liveout())
if block is NOT visited {
ALIVE[block] <- alive
push_successors = true
} else {
alive_before <- ALIVE[block]
alive.INTERSECT(alive_before)
if alive <> alive_before {
push_successors = true
}
ALIVE[block] <- alive
}
mark block as visited
if push_successors {
if block has 1 successor {
push successor to work queue
ALIVE[successor] <- alive
} else block has 2 successors {
push successor1 to work queue
alive1 <- alive.COPY
ALIVE[successor1] <- alive1.TRIM(successor1.livein())
push successor2 to work queue
alive2 <- alive.COPY
ALIVE[successor2] <- alive2.TRIM(successor2,livein())
}
}
}
}
```https://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/74Ref map generation is wrong2017-08-09T09:49:27+10:00Isaac Garianoisaac@ecs.vuw.ac.nzRef map generation is wrongThe GC appears to be generating incorrect refmaps for types, this is causing test_pypy to fail.
Specifically when dumping an instance of 'stt294' whose structure is:
```
2509@stt294 = Struct:
1213@stt55 = Struct:
121...The GC appears to be generating incorrect refmaps for types, this is causing test_pypy to fail.
Specifically when dumping an instance of 'stt294' whose structure is:
```
2509@stt294 = Struct:
1213@stt55 = Struct:
1214@stt56 = Struct:
1060@stt10 = Struct:
1037@stt3 = Struct:
1012@i64 = Int(64) +0
1032@ptrstt2 = UPtr(1033@stt2 = Struct("@stt2") ) +8
1059@refstt10 = Ref(1060@stt10 = Struct("@stt10") ) *+16
1059@refstt10 = Ref(1060@stt10 = Struct("@stt10") ) *+24
1003@i8 = Int(8) *+32
1036@refstt3 = Ref(1037@stt3 = Struct("@stt3")) +40
1126@refhyb11 = Ref(1127@hyb11 = Hybrid("@hyb11") ) *+48
1059@refstt10 = Ref(1060@stt10 = Struct("@stt10") ) *+56
1003@i8 = Int(8) +64
1010@refhyb1 = Ref(1011@hyb1 = Hybrid("@hyb1")) *+72
1012@i64 = Int(64) +80
1010@refhyb1 = Ref(1011@hyb1 = Hybrid("@hyb1")) *+88
1012@i64 = Int(64) +96
1059@refstt10 = Ref(1060@stt10 = Struct("@stt10")) *+104
1003@i8 = Int(8) *+112
1003@i8 = Int(8) +113
1036@refstt3 = Ref(1037@stt3 = Struct("@stt3")) *+120
1036@refstt3 = Ref(1037@stt3 = Struct("@stt3")) +128
```
(The last column indicates the offset, and a * indicates that Zebu is treating the value at that offset as a reference when dumping). The reported ref map for this type is '1110101011011100', this is clearly completley wrong.
This bug can be reproduced with the following C code (executing it causes a segfault as it tries to dump an object at location '0x101', due to misreading a field as a reference):
```
#include <math.h>
#include <stddef.h>
#include <stdint.h>
#include "muapi.h"
#include "mu-fastimpl.h"
#define G(id, ...) global_ ## id
#define L(id, ...) local_ ## id
MuVM* mvm;
MuCtx* ctx;
MuID G(0, int64_const);
MuID G(1);
MuID G(2, uptr_stt2_const);
MuID G(3, stt2);
MuID G(4);
MuID G(5, int8_const);
MuID G(6);
MuID G(7);
MuID G(8, stt2_cell);
MuID G(9, hyb11);
MuID G(10, hyb11_cell);
MuID G(11, hyb1);
MuID G(12, hyb1_cell);
MuID G(13, stt3);
MuID G(14, stt3_cell);
MuID G(15, stt10);
MuID G(16, stt10_cell);
MuID G(17, stt56);
MuID G(18);
MuID G(19);
MuID G(20, stt55);
MuID G(21);
MuID G(22, stt294);
MuID G(23);
MuID G(24, stt294_cell);
void build_bundle() {
MuIRBuilder* irbuilder = ctx->new_ir_builder(ctx);
G(0, int64_const) = irbuilder->gen_sym(irbuilder, "@int64_const");
G(1) = irbuilder->gen_sym(irbuilder, NULL);
irbuilder->new_type_int(irbuilder, G(1), 64);
irbuilder->new_const_int(irbuilder, G(0, int64_const), G(1), 1);
G(2, uptr_stt2_const) = irbuilder->gen_sym(irbuilder, "@uptr_stt2_const");
G(3, stt2) = irbuilder->gen_sym(irbuilder, "@stt2");
G(4) = irbuilder->gen_sym(irbuilder, NULL);
irbuilder->new_type_uptr(irbuilder, G(4), G(3, stt2));
irbuilder->new_const_null(irbuilder, G(2, uptr_stt2_const), G(4));
G(5, int8_const) = irbuilder->gen_sym(irbuilder, "@int8_const");
G(6) = irbuilder->gen_sym(irbuilder, NULL);
irbuilder->new_type_int(irbuilder, G(6), 8);
irbuilder->new_const_int(irbuilder, G(5, int8_const), G(6), 1);
G(7) = irbuilder->gen_sym(irbuilder, NULL);
irbuilder->new_type_void(irbuilder, G(7));
irbuilder->new_type_struct(irbuilder, G(3, stt2), (MuTypeNode[]){G(7)}, 1);
G(8, stt2_cell) = irbuilder->gen_sym(irbuilder, "@stt2_cell");
irbuilder->new_global_cell(irbuilder, G(8, stt2_cell), G(3, stt2));
G(9, hyb11) = irbuilder->gen_sym(irbuilder, "@hyb11");
irbuilder->new_type_struct(irbuilder, G(9, hyb11), (MuTypeNode[]){G(7)}, 1);
G(10, hyb11_cell) = irbuilder->gen_sym(irbuilder, "@hyb11_cell");
irbuilder->new_global_cell(irbuilder, G(10, hyb11_cell), G(9, hyb11));
G(11, hyb1) = irbuilder->gen_sym(irbuilder, "@hyb1");
irbuilder->new_type_struct(irbuilder, G(11, hyb1), (MuTypeNode[]){G(7)}, 1);
G(12, hyb1_cell) = irbuilder->gen_sym(irbuilder, "@hyb1_cell");
irbuilder->new_global_cell(irbuilder, G(12, hyb1_cell), G(11, hyb1));
G(13, stt3) = irbuilder->gen_sym(irbuilder, "@stt3");
irbuilder->new_type_struct(irbuilder, G(13, stt3), (MuTypeNode[]){G(1), G(4)}, 2);
G(14, stt3_cell) = irbuilder->gen_sym(irbuilder, "@stt3_cell");
irbuilder->new_global_cell(irbuilder, G(14, stt3_cell), G(13, stt3));
G(15, stt10) = irbuilder->gen_sym(irbuilder, "@stt10");
irbuilder->new_type_struct(irbuilder, G(15, stt10), (MuTypeNode[]){G(13, stt3)}, 1);
G(16, stt10_cell) = irbuilder->gen_sym(irbuilder, "@stt10_cell");
irbuilder->new_global_cell(irbuilder, G(16, stt10_cell), G(15, stt10));
G(17, stt56) = irbuilder->gen_sym(irbuilder, "@stt56");
G(18) = irbuilder->gen_sym(irbuilder, NULL);
irbuilder->new_type_ref(irbuilder, G(18), G(15, stt10));
G(19) = irbuilder->gen_sym(irbuilder, NULL);
irbuilder->new_type_ref(irbuilder, G(19), G(13, stt3));
irbuilder->new_type_struct(irbuilder, G(17, stt56), (MuTypeNode[]){G(15, stt10), G(18), G(18), G(6), G(19)}, 5);
G(20, stt55) = irbuilder->gen_sym(irbuilder, "@stt55");
G(21) = irbuilder->gen_sym(irbuilder, NULL);
irbuilder->new_type_ref(irbuilder, G(21), G(9, hyb11));
irbuilder->new_type_struct(irbuilder, G(20, stt55), (MuTypeNode[]){G(17, stt56), G(21), G(18), G(6)}, 4);
G(22, stt294) = irbuilder->gen_sym(irbuilder, "@stt294");
G(23) = irbuilder->gen_sym(irbuilder, NULL);
irbuilder->new_type_ref(irbuilder, G(23), G(11, hyb1));
irbuilder->new_type_struct(irbuilder, G(22, stt294), (MuTypeNode[]){G(20, stt55), G(23), G(1), G(23), G(1), G(18), G(6), G(6), G(19), G(19)}, 10);
G(24, stt294_cell) = irbuilder->gen_sym(irbuilder, "@stt294_cell");
irbuilder->new_global_cell(irbuilder, G(24, stt294_cell), G(22, stt294));
irbuilder->load(irbuilder);
}
MuValue get_global(MuID id) { return ctx->handle_from_global(ctx, id); }
MuValue get_const(MuID id) { return ctx->handle_from_const(ctx, id); }
void store_field(MuIRefValue object, int field, MuValue value) {
MuIRefValue field_ref = ctx->get_field_iref(ctx, object, field);
ctx->store(ctx, MU_ORD_NOT_ATOMIC, field_ref, value);
}
MuIRefValue get_field_iref(MuIRefValue object, int field) {
return ctx->get_field_iref(ctx, object, field);
}
int main() {
mvm = mu_fastimpl_new_with_opts("init_mu --aot-emit-dir=emit");
ctx = mvm->new_context(mvm);
build_bundle();
MuIRefValue stt294_cell = get_global(G(24, stt294_cell));
MuIRefValue hyb1_cell = get_global(G(12, hyb1_cell));
MuIRefValue stt10_cell = get_global(G(16, stt10_cell));
MuIRefValue stt3_cell = get_global(G(14, stt3_cell));
MuIRefValue hyb11_cell = get_global(G(10, hyb11_cell));
MuIRefValue int64_const = get_const(G(0, int64_const));
MuIRefValue int8_const = get_const(G(5, int8_const));
MuIRefValue uptr_stt2_const = get_const(G(2, uptr_stt2_const));
store_field(stt294_cell, 1, hyb1_cell);
store_field(stt294_cell, 2, int64_const);
store_field(stt294_cell, 3, hyb1_cell);
store_field(stt294_cell, 4, int64_const);
store_field(stt294_cell, 5, stt10_cell);
store_field(stt294_cell, 6, int8_const);
store_field(stt294_cell, 7, int8_const);
store_field(stt294_cell, 8, stt3_cell);
store_field(stt294_cell, 9, stt3_cell);
MuIRefValue stt55_part = get_field_iref(stt294_cell, 0);
//.const stt55_const<stt55> = {stt56_const hyb11_cell stt10_cell int8_const}
store_field(stt55_part, 1, hyb11_cell);
store_field(stt55_part, 2, stt10_cell);
store_field(stt55_part, 3, int8_const);
MuIRefValue stt56_part = get_field_iref(stt55_part, 0);
store_field(stt56_part, 1, stt10_cell);
store_field(stt56_part, 2, stt10_cell);
store_field(stt56_part, 3, int8_const);
store_field(stt56_part, 3, stt3_cell);
//.const stt55_const<stt55> = {stt56_const hyb11_cell stt10_cell int8_const}
MuIRefValue stt10_part = get_field_iref(stt56_part, 0);
MuIRefValue stt3_part = get_field_iref(stt10_part, 0);
store_field(stt3_part, 0, int64_const);
store_field(stt3_part, 1, uptr_stt2_const);
ctx->make_boot_image(ctx,
(MuID[]){G(0, int64_const), G(2, uptr_stt2_const), G(3, stt2), G(5, int8_const), G(8, stt2_cell), G(9, hyb11), G(10, hyb11_cell), G(11, hyb1), G(12, hyb1_cell), G(13, stt3), G(14, stt3_cell), G(15, stt10), G(16, stt10_cell), G(17, stt56), G(20, stt55), G(22, stt294), G(24, stt294_cell)}, 17,
NULL, NULL, NULL, NULL, NULL, 0, NULL, NULL, 0,
"test_ref_map");
}
```https://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/39Reduce serialised vm size (large bootimage size)2017-07-12T10:49:35+10:00Yi LinReduce serialised vm size (large bootimage size)For RPySOM interpreter, the boot image (executable) generated by Zebu is 175mb while the executable from the C backend is less than 1 mb. The main reason is that the Zebu's boot image contains a serialised vm (via Rust's serialisation),...For RPySOM interpreter, the boot image (executable) generated by Zebu is 175mb while the executable from the C backend is less than 1 mb. The main reason is that the Zebu's boot image contains a serialised vm (via Rust's serialisation), and I wasn't careful about what should be serialised so that basically everything is included. The serialised VM probably contribute to 99% of the boot image size.
I estimate if I am being careful about what should be serialised (only what will be used at runtime is worth serialising. #18 is part of the issue), the size can be reduced by at least 5-10 times.
And I am not sure how much this may contribute to the big performance slowdown.Yi LinYi Linhttps://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/41persisting VM natively2017-07-12T10:49:35+10:00Yi Linpersisting VM nativelyWe now use Rust's `rustc_serialise` to persist VM as a JSON string in the boot image. This clearly imposes large overhead in both boot image size and loading time. We should persist the VM in a native and relocatable way.We now use Rust's `rustc_serialise` to persist VM as a JSON string in the boot image. This clearly imposes large overhead in both boot image size and loading time. We should persist the VM in a native and relocatable way.https://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/28Name mangling in Zebu, unnamed MuEntity, global/local names2017-07-19T15:05:23+10:00Yi LinName mangling in Zebu, unnamed MuEntity, global/local namesCurrently Zebu makes assumptions about names, and mangles names in a way that is inconsistent and confusing. And it may be inconsistent to the spec.
These are some notes (I need to rethink on these):
* Zebu assumes local names, and man...Currently Zebu makes assumptions about names, and mangles names in a way that is inconsistent and confusing. And it may be inconsistent to the spec.
These are some notes (I need to rethink on these):
* Zebu assumes local names, and mangles it (if needed) in its own way. The spec requires all names used via API are global names (no mangling is needed)
* Zebu checks and transforms each name so the name does not include special character, and can be safely used in assembly
* Zebu assumes some entities such as `Block`, `MuFunction` have a name. These assumption may not be consistent with the spec (the spec requires top-level entities have names). This needs further check.
* Names that start with number is valid as name for a Mu entity, however the name may not be valid to be used directly in the assembly.Yi LinYi Linhttps://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/45mu-perf-benchmarks fib: movq $-2,%ECX2017-07-12T10:49:35+10:00Isaac Garianoisaac@ecs.vuw.ac.nzmu-perf-benchmarks fib: movq $-2,%ECXWhen trying to run my mu_fib_fast benchmark (`python3 -m mubench local ./example/test_mu_fib.yml`, in the latest version of mu-perf-benchmarks) on x86-64 I get the following errror:
```
INFO - executing: "clang" "example/fib_mu_fast-em...When trying to run my mu_fib_fast benchmark (`python3 -m mubench local ./example/test_mu_fib.yml`, in the latest version of mu-perf-benchmarks) on x86-64 I get the following errror:
```
INFO - executing: "clang" "example/fib_mu_fast-emit/mubench$cb_init.s" "example/fib_mu_fast-emit/mubench$cb_begin.s" "example/fib_mu_fast-emit/mubench$cb_end.s" "example/fib_mu_fast-emit/mubench$cb_report.s" "example/fib_mu_fast-emit/clockcb$tspec2dbl.s" "example/fib_mu_fast-emit/fib.s" "example/fib_mu_fast-emit/entry.s" "example/fib_mu_fast-emit/context.s" "example/fib_mu_fast-emit/main.c" "/home/isaacg/mu-impl-fast/target/release/libmu.a" "-ldl" "-lrt" "-lm" "-lpthread" "-rdynamic" "-o" "/root/mu-perf-benchmarks/example/fib-mu_fast"
INFO - ---out---
INFO -
INFO - ---err---
INFO - example/fib_mu_fast-emit/fib.s:44:11: error: invalid operand for instruction
movq $-1,%ECX
^~~~
example/fib_mu_fast-emit/fib.s:52:11: error: invalid operand for instruction
movq $-2,%ECX
^~~~
thread '<unnamed>' panicked at 'assertion failed: output.status.success()', src/testutil/mod.rs:41
stack backtrace:
0: std::sys::imp::backtrace::tracing::imp::unwind_backtrace
at /checkout/src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
1: std::sys_common::backtrace::_print
at /checkout/src/libstd/sys_common/backtrace.rs:71
2: std::panicking::default_hook::{{closure}}
at /checkout/src/libstd/sys_common/backtrace.rs:60
at /checkout/src/libstd/panicking.rs:355
3: std::panicking::default_hook
at /checkout/src/libstd/panicking.rs:371
4: std::panicking::rust_panic_with_hook
at /checkout/src/libstd/panicking.rs:549
5: std::panicking::begin_panic
6: mu::testutil::exec
7: mu::testutil::aot::link_primordial
8: mu::vm::vm::VM::make_boot_image_internal
9: mu::vm::api::api_bridge::_forwarder__MuCtx__make_boot_image
10: main
11: __libc_start_main
12: _start
fatal runtime error: failed to initiate panic, error 5
```
It ran without error on aarch64 (assuming johns code actually checks that fib produces the right result)Yi LinYi Linhttps://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/24Mu IR Type checking2017-11-21T13:54:18+11:00Isaac Garianoisaac@ecs.vuw.ac.nzMu IR Type checkingThe Mu IR compiler currently will compile some invalid mu code, specifically I noticed the following invalid code successfully compiled (which were used in some of the tests) :
* a SHL/LSHR/ASHR instruction where the second argument is...The Mu IR compiler currently will compile some invalid mu code, specifically I noticed the following invalid code successfully compiled (which were used in some of the tests) :
* a SHL/LSHR/ASHR instruction where the second argument is not the same as the first (in the case of the test the first argument was int<64> and the second argument was an int<8>) (this code was generated in tes_shl and test_lshr).
* passing an int<64> as an argument to a C function expecting an int<32> (this was generated by test_pass_1arg_by_stack, and test_pass_2arg_by_stack)
In addition the compiler doesn't seem to check when you use an SSA variable whether it has been assigned to yet.https://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/65More peephole optimisation rules2017-07-20T16:13:13+10:00Yi LinMore peephole optimisation rulesThis issue lists optimisations that we can do in peephole optimisations.
* [ ] a `jump-to-ret` can be replaced with `ret` directly (this would happen often for leaf functions)This issue lists optimisations that we can do in peephole optimisations.
* [ ] a `jump-to-ret` can be replaced with `ret` directly (this would happen often for leaf functions)https://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/51Memory order in store/load API calls2018-09-10T06:31:05+10:00Yi LinMemory order in store/load API callsFor API calls `load()`/`store()`, they take memory order as an argument. However I am uncertain whether we need to do anything special for different memory orders. Current implementation just does a plain load/store in `vm.handle_load()`...For API calls `load()`/`store()`, they take memory order as an argument. However I am uncertain whether we need to do anything special for different memory orders. Current implementation just does a plain load/store in `vm.handle_load()` and `vm.handle_store()`.https://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/83Memory leak when running cargo test2017-08-25T15:30:26+10:00Yi LinMemory leak when running cargo testRunning cargo tests seems to have increasing memory usage over time. It is possible that there is some memory leak (significant). I probably should first check if the memory mmaped for the heap is deallocated properly.Running cargo tests seems to have increasing memory usage over time. It is possible that there is some memory leak (significant). I probably should first check if the memory mmaped for the heap is deallocated properly.Yi LinYi Linhttps://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/87Make IR debug output from Zebu compatible with muc2017-10-09T17:38:55+11:00Yi LinMake IR debug output from Zebu compatible with mucCurrently with `trace` level logging, Zebu outputs IR in its own format. We should make this compatible with the text form that `muc` uses (https://gitlab.anu.edu.au/mu/mu-tool-compiler/blob/master/UIR.g4)Currently with `trace` level logging, Zebu outputs IR in its own format. We should make this compatible with the text form that `muc` uses (https://gitlab.anu.edu.au/mu/mu-tool-compiler/blob/master/UIR.g4)https://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/76Loading from a ref2017-08-09T21:31:30+10:00Isaac Garianoisaac@ecs.vuw.ac.nzLoading from a refAccording to the mu-spec the argument to a LOAD instruction must be an iref or uptr, but in the test
test_heap.py::test_load_ref_from_global, you actually load from a ref. (this was picked up by my new IR checking, as a temporary work a...According to the mu-spec the argument to a LOAD instruction must be an iref or uptr, but in the test
test_heap.py::test_load_ref_from_global, you actually load from a ref. (this was picked up by my new IR checking, as a temporary work around I have allowed refs as well)
You also can't use 'refs' for any of the other memory instructions (store, getelementiref etc...) except ofcourse getiref.John ZhangJohn Zhanghttps://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/88Known issues with PyPy-zebu2017-10-05T13:10:05+11:00Isaac Garianoisaac@ecs.vuw.ac.nzKnown issues with PyPy-zebuTheir are several bugs I have noticed when running pypy-zebu: (unless otherwise specified I have confirmed the errors for both architectures, I have also confirmed that these errors don't occur with the normal pypy):
1. Pypy in intera...Their are several bugs I have noticed when running pypy-zebu: (unless otherwise specified I have confirmed the errors for both architectures, I have also confirmed that these errors don't occur with the normal pypy):
1. Pypy in interactive mode (but not when reading from a file) segfaults when their is a syntax error:
```
$ echo '.' | pypy-zebu -i
Python 2.7.12 (e8da6780d84e, Oct 04 2017, 01:16:24)
[PyPy 5.6.0 with Mu] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>>> Segmentation fault (core dumped)
```
LLDB reports:
```
* thread #2, name = 'Mu Thread #7595', stop reason = signal SIGSEGV: invalid address (fault address: 0x20)
frame #0: 0x0000000000f1a2b2 pypy-zebu`__mu_W_SyntaxError_descr_repr_0Zdblk15ZdZa821942Zccallsite_26
pypy-zebu`__mu_W_SyntaxError_descr_repr_0Zdblk15ZdZa821942Zccallsite_26:
-> 0xf1a2b2 <+0>: movq 0x20(%rax), %rax
0xf1a2b6 <+4>: movq 0x28(%rax), %rdi
```
1. Pypy only reads the first commandline argument, e.g. pypy-zebu <(echo 'print "hello"')' prints 'hello', but 'pypy-zebu -v <(echo 'print "hello"')' dosn't (it can bee seen that the argument is not considered their at all:
```
pypy-zebu -c pass
Argument expected for the '-c' option
usage: /home/isaacg/mu-client-pypy/pypy/bin/pypy-zebu [options]
Try `/home/isaacg/mu-client-pypy/pypy/bin/pypy-zebu -h` for more information.
```
As well as
```
$ echo 'import sys; print sys.argv[1]' | pypy-zebu - 1
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: list index out of range
```
1. Pybench segfaults (when it dosn't run out of gc space) (e.g. `MU_IMMIX_SPACE=40000000000 pypy-zebu pybench.py`), lldb reports:
```
* thread #2, name = 'Mu Thread #7595', stop reason = signal SIGSEGV: invalid address (fault address: 0x0)
frame #0: 0x0000000001002cf1 pypy-zebu`__mu_descr_file_fdopen_0_v1Zcepilogue + 24
pypy-zebu`__mu_descr_file_fdopen_0_v1Zcepilogue:
-> 0x1002cf1 <+24>: retq
```
EDIT: On aarch64 GDB reports:
```
Thread 2 "Mu Thread #9020" received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0xfffb509db030 (LWP 31518)]
0x0000000000000000 in ?? ()
```
or
```
Thread 2 "Mu Thread #9020" received signal SIGBUS, Bus error.
[Switching to Thread 0xfffb509db030 (LWP 31535)]
0x005f5f7472617473 in ?? ()
```
2. `help()` throws a `ValueError`:
```
$ MU_IMMIX_SPACE=40000000000 pypy-zebu
Python 2.7.12 (e8da6780d84e, Oct 04 2017, 01:16:24)
[PyPy 5.6.0 with Mu] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>>> help()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/home/isaacg/mu-client-pypy/lib-python/2.7/site.py", line 472, in __call__
import pydoc
File "/home/isaacg/mu-client-pypy/lib-python/2.7/pydoc.py", line 56, in <module>
import sys, imp, os, re, types, inspect, __builtin__, pkgutil, warnings
File "/home/isaacg/mu-client-pypy/lib-python/2.7/inspect.py", line 39, in <module>
import tokenize
File "/home/isaacg/mu-client-pypy/lib-python/2.7/tokenize.py", line 103, in <module>
re.compile, (Token, PseudoToken, Single3, Double3))
File "/home/isaacg/mu-client-pypy/lib-python/2.7/re.py", line 194, in compile
return _compile(pattern, flags)
File "/home/isaacg/mu-client-pypy/lib-python/2.7/re.py", line 249, in _compile
p = sre_compile.compile(pattern, flags)
File "/home/isaacg/mu-client-pypy/lib-python/2.7/sre_compile.py", line 595, in compile
groupindex, indexgroup
ValueError: cannot convert negative integer to unsigned
>>>>
```
3. (aarch64 only) when it runs out of memory and panics, it segfaults:
```
$ MU_IMMIX_SPACE=1 pypy-zebu
thread 'Mu Thread #9020349' panicked at 'Triggering GC when GC is disabled', /home/isaacg/mu-impl-fast-git/src/gc/src/heap/gc/mod.rs:259:8
Segmentation fault (core dumped)
```
GDB reports:
```
Thread 2 "Mu Thread #9020" received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0xffffb1b31030 (LWP 2811)]
0x0000ffffb75909e0 in ?? () from /lib/aarch64-linux-gnu/libgcc_s.so.1
(gdb) bt
#0 0x0000ffffb75909e0 in ?? () from /lib/aarch64-linux-gnu/libgcc_s.so.1
#1 0x0000ffffb7591234 in _Unwind_Backtrace () from /lib/aarch64-linux-gnu/libgcc_s.so.1
#2 0x0000ffffb7c274d8 in std::sys::imp::backtrace::tracing::imp::unwind_backtrace () at /checkout/src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
#3 0x0000ffffb7c22678 in std::sys_common::backtrace::_print () at /checkout/src/libstd/sys_common/backtrace.rs:71
#4 0x0000ffffb7c32d58 in std::sys_common::backtrace::print () at /checkout/src/libstd/sys_common/backtrace.rs:60
#5 std::panicking::default_hook::{{closure}} () at /checkout/src/libstd/panicking.rs:380
#6 0x0000ffffb7c32968 in std::panicking::default_hook () at /checkout/src/libstd/panicking.rs:396
#7 0x0000ffffb7c33270 in std::panicking::rust_panic_with_hook () at /checkout/src/libstd/panicking.rs:611
#8 0x0000ffffb7a2994c in std::panicking::begin_panic_new::h91c15d79ddd4536b () from /home/isaacg/mu-impl-fast-git/target/release/libmu.so
#9 0x0000ffffb7a3811c in mu_gc::heap::gc::sync_barrier::hebcd16541e55b150 () from /home/isaacg/mu-impl-fast-git/target/release/libmu.so
#10 0x0000ffffb7a3466c in mu_gc::heap::immix::immix_mutator::ImmixMutatorLocal::yieldpoint_slow::h9cccb390ce79aedf () from /home/isaacg/mu-impl-fast-git/target/release/libmu.so
#11 0x0000ffffb7a34888 in mu_gc::heap::immix::immix_mutator::ImmixMutatorLocal::alloc_from_global::h102601e3553ebff9 () from /home/isaacg/mu-impl-fast-git/target/release/libmu.so
#12 0x0000ffffb7a407f4 in muentry_alloc_fast () from /home/isaacg/mu-impl-fast-git/target/release/libmu.so
#13 0x0000000000cdc6e8 in pypy_mu_main_0 ()
#14 0x0000000000cdc69c in entry_point_0 ()
Backtrace stopped: previous frame inner to this frame (corrupt stack?)
```
1. pypy is allocating zero sized object with Zebu. This does not seem correct. The only zero sized type in Mu is `void`. Either the client is allocating `void` object, or there is a bug somewhere. https://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/5JIT Tests2017-07-12T10:49:36+10:00John ZhangJIT TestsA list of tests to do for the JIT.
## Milestone Tests
- [x] constant function
- [x] fibonacci
- [x] two functions (compiling multiple functions)
- [x] RPython SHA1 test
- [ ] RPython GC benchmark
- [x] RPython Richards benchmark
- [x] ...A list of tests to do for the JIT.
## Milestone Tests
- [x] constant function
- [x] fibonacci
- [x] two functions (compiling multiple functions)
- [x] RPython SHA1 test
- [ ] RPython GC benchmark
- [x] RPython Richards benchmark
- [x] RPython NBody benchmark
- [x] RPython SOM interpreter
- [ ] PyPy interpreter with minimum modules
- [ ] PyPy interpreter with compilable modules
## Binary operation tests
- [x] `ADD`
- [x] `SUB`
- [x] `MUL`
- [x] `SDIV`
- [x] `UREM`
- [x] `SHL`
- [x] `LSHR`
- [x] `AND`
- [x] `XOR`
## Compare operation tests
- [x] `EQ`
- [x] `NE`
- [x] `SGE`
- [x] `SGT`
- [x] `SLE`
- [x] `SLT`
## Conversion operation tests
- [x] `TRUNC`
- [x] `ZEXT`
- [x] `SEXT`
- [x] `REFCAST`
- [x] `PTRCAST`
## Control flow operation tests
- [x] `BRANCH`
- [x] `BRANCH2`
- [x] `CALL`
- [x] `RET`
- [x] `SWITCH`
- [x] `CCALL`
- [x] `THROW`
## Memory operation tests
- [x] `NEW`
- [x] `NEWHYBRID`
- [x] `GETIREF`
- [x] `GETFIELDIREF`
- [x] `SHIFTIREF`
- [x] `GETVARPARTIREF`
- [x] `LOAD`
- [x] `STORE`
## `COMMINST` tests
- [x] `COMMINST @uvm.thread_exit`
- [x] `COMMINST @uvm.native.pin`
- [x] `COMMINST @uvm.native.unpin`
- [x] `COMMINST @uvm.get_threadlocal`
- [x] `COMMINST @uvm.set_threadlocal`John ZhangJohn Zhanghttps://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/93Issues before enabling GC2017-11-21T14:37:55+11:00Yi LinIssues before enabling GCThe GC rewrite should have fixed most of the problems, however, there are a few known issues that need to be done before enabling GC.
* https://gitlab.anu.edu.au/mu/mu-impl-fast/issues/21 about some utility functions in C that help f...The GC rewrite should have fixed most of the problems, however, there are a few known issues that need to be done before enabling GC.
* https://gitlab.anu.edu.au/mu/mu-impl-fast/issues/21 about some utility functions in C that help find references in stack/heap. They need to be fixed for correctness. And also `set_low_water_mark()` should be called by the VM to set a limit for stack scanning. Alternatively we may also let GC know about stack bounds so it won't go beyond the stack memory.
* inserting yieldpoint.
* Allowing finding base reference for internal references. As we have 16 bytes min size and 16 bytes min alignment of objects, for any reference we mask it to 16 bytes, and see if it contains a valid object encoding (non-empty, or with certain bits set).https://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/86Issue with rodal on macOS when dynamically linking with boot image2017-09-22T11:10:22+10:00Yi LinIssue with rodal on macOS when dynamically linking with boot imageI am not sure if I fully understood the problem. Isaac @igariano01 may explain more on this.
Generally the issue is that rodal needs to redefine `malloc()` and `free()` that Rust uses to manage heap memory. Those are weak symbols, so r...I am not sure if I fully understood the problem. Isaac @igariano01 may explain more on this.
Generally the issue is that rodal needs to redefine `malloc()` and `free()` that Rust uses to manage heap memory. Those are weak symbols, so rodal redefines them. Thus if an object is dumped by rodal, it cannot be freed by the default `free()`, instead it is freed by rodal.
However on macOS, Rust uses a different allocator when generating dynamic libraries instead of using `malloc()`/`free()`, and those cannot be redefined. Thus when we link to mu as a dynamic library, rodal cannot redefine the `free()` function. However, there seems no issue when linking to mu a as static library.
One solution that seems very hacky is to disable dynamic link with mu in boot image generation. Branch https://gitlab.anu.edu.au/mu/mu-impl-fast/tree/static-link-for-macos has the fix.
The other solution is to use Rust's nightly feature to provide a custom allocator (rodal will implement a custom allocator along with deallocation). Branch https://gitlab.anu.edu.au/mu/mu-impl-fast/tree/global_allocator has a fix. This is a more elegant approach. But my only concern is that this requires us to use nightly Rust. I am concerned the language implementation itself is more buggy in a nightly version, and we will meet problems when debugging (e.g. whether it is our bug, or their bug). And if we switch to nightly Rust, it is very likely that we will start using more nightly features, and we will not be able to go back to stable Rust in the future.https://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/8IR validation pass2017-08-25T09:36:31+10:00Yi LinIR validation passCurrently if the input IR is incorrect, one of the following may happen:
1. some assertion in the compiler may fail
1. Rust safety finds it and panics (such as index out of bounds)
1. the compiler generates correct or incorrect code e...Currently if the input IR is incorrect, one of the following may happen:
1. some assertion in the compiler may fail
1. Rust safety finds it and panics (such as index out of bounds)
1. the compiler generates correct or incorrect code even if input IR is incorrect
We will want a IR validation pass to check the input IR. It includes:
* check if types and numbers of operands and results of each instructions match
* check if function signatures matches parameters and return values
* check if branch arguments matches parameters, and if branch destination is valid
* check if the last instruction for each block is terminating instruction (`BRNACH`, `CALL`, `RET`, etc)
...
(this list will grow when I think up more)Yi LinYi Linhttps://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/6IR rewrite pass before instruction selection2017-11-21T13:50:53+11:00Yi LinIR rewrite pass before instruction selectionSome instructions such as `NEW` will be expanded into a sequence of code (may involve new blocks), and some instructions such as `THREADEXIT` will be expanded into a CCall into runtime service functions. Currently this is done at instruc...Some instructions such as `NEW` will be expanded into a sequence of code (may involve new blocks), and some instructions such as `THREADEXIT` will be expanded into a CCall into runtime service functions. Currently this is done at instruction selection pass, by directly expanding such instructions into machine code. Alternatively, a better choice is to rewrite/expand such instructions into Mu IR before instruction selection. Yi LinYi Linhttps://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/4IR Instruction Implementation2017-07-12T10:49:36+10:00John ZhangIR Instruction ImplementationA list of IR Instruction needed progressively.
Tick them off as you go, and watch for updates.
## IR Instructions
- [x] `ADD`
- [x] `SUB`
- [x] `MUL`
- [x] `SDIV`
- [x] `UDIV`
- [x] `SREM`
- [x] `UREM`
- [x] `SHL`
- [x] `ASHR`
- [x] `L...A list of IR Instruction needed progressively.
Tick them off as you go, and watch for updates.
## IR Instructions
- [x] `ADD`
- [x] `SUB`
- [x] `MUL`
- [x] `SDIV`
- [x] `UDIV`
- [x] `SREM`
- [x] `UREM`
- [x] `SHL`
- [x] `ASHR`
- [x] `LSHR`
- [x] `FADD`
- [x] `FSUB`
- [x] `FDIV`
- [x] `FMUL`
- [x] `AND`
- [x] `OR`
- [x] `XOR`
- [x] `EQ`
- [x] `NE`
- [x] `SGE`
- [x] `SGT`
- [x] `SLE`
- [x] `SLT`
- [x] `ULE`
- [x] `ULT`
- [x] `FOEQ`
- [x] `FOGT`
- [x] `FOLE`
- [x] `FOLT`
- [x] `FONE`
- [x] `TRUNC`
- [x] `ZEXT`
- [x] `SEXT`
- [x] `REFCAST`
- [x] `PTRCAST`
- [x] `FPTOSI`
- [x] `SITOFP`
- [x] `UITOFP`
- [x] `SELECT`
- [x] `BRANCH`
- [x] `BRANCH2`
- [x] `SWITCH`
- [x] `CALL`
- [x] `RET`
- [x] `NEW`
- [x] `NEWHYBRID`
- [x] `GETIREF`
- [x] `GETFIELDIREF`
- [x] `GETELEMIREF`
- [x] `SHIFTIREF`
- [x] `GETVARPARTIREF`
- [x] `LOAD`
- [x] `STORE`
- [x] `CCALL`
- [x] `NEWTHREAD`
- [x] `COMMINST @uvm.thread_exit`
- [x] `THROW`
- [x] `COMMINST @uvm.native.pin`
- [x] `COMMINST @uvm.native.unpin`
- [ ] `COMMINST @uvm.get_threadlocal`
- [x] `COMMINST @uvm.set_threadlocal`
Yi LinYi Linhttps://gitlab.anu.edu.au/mu/mu-impl-fast/-/issues/80IR checker fails to handle loading from weakref2017-08-19T17:05:55+10:00John ZhangIR checker fails to handle loading from weakref## Problem Description
The spec says that when loading from a weak reference field, the result will be a strong reference. My understanding is, if I'm loading from `iref<weakref<void>>`, it should result a `ref<void>`, rather than a `wea...## Problem Description
The spec says that when loading from a weak reference field, the result will be a strong reference. My understanding is, if I'm loading from `iref<weakref<void>>`, it should result a `ref<void>`, rather than a `weakref<void>`.
It seems that the static checker fails to correctly handles this conversion. So when I try to cast the loaded `ref<void>` to `ref<struct>`, it complains of an invalid cast.Isaac Garianoisaac@ecs.vuw.ac.nzIsaac Garianoisaac@ecs.vuw.ac.nz