Register swap bug when generating Phi moves

Furkan commented

2026-08-11 18:08:55 +00:00

I couldn't simplify the code so I'm gonna provide the code as is

import io

const {
    TOTAL = 4096
    L = 1 << 31
}

global {
    freq []uint
    cum []uint
}

calc_freqs(freq []uint) {
    freq['a'] = 335
    freq['b'] = 61
    freq['c'] = 114
    freq['d'] = 174
    freq['e'] = 520
    freq['f'] = 91
    freq['g'] = 83
    freq['h'] = 250
    freq['i'] = 285
    freq['j'] = 6
    freq['k'] = 32
    freq['l'] = 165
    freq['m'] = 99
    freq['n'] = 276
    freq['o'] = 307
    freq['p'] = 79
    freq['q'] = 4
    freq['r'] = 245
    freq['s'] = 259
    freq['t'] = 371
    freq['u'] = 113
    freq['v'] = 40
    freq['w'] = 97
    freq['x'] = 6
    freq['y'] = 81
    freq['z'] = 3
}

calc_cums(cum []uint) {
    cum['a'] = 0
    cum['b'] = 335
    cum['c'] = 396
    cum['d'] = 510
    cum['e'] = 684
    cum['f'] = 1204
    cum['g'] = 1295
    cum['h'] = 1378
    cum['i'] = 1628
    cum['j'] = 1913
    cum['k'] = 1919
    cum['l'] = 1951
    cum['m'] = 2116
    cum['n'] = 2215
    cum['o'] = 2491
    cum['p'] = 2798
    cum['q'] = 2877
    cum['r'] = 2881
    cum['s'] = 3126
    cum['t'] = 3385
    cum['u'] = 3756
    cum['v'] = 3869
    cum['w'] = 3909
    cum['x'] = 4006
    cum['y'] = 4012
    cum['z'] = 4093
}

encode(state uint, output []byte, output_pos uint, value byte) -> (uint, uint) {
    f := freq[value]

    x_max := 134217728 as uint
    x_max *= f

    loop {
        if state < x_max {
            loop.stop()
        }

        output[output_pos] = (state & 255) as byte
        output_pos += 1
        state >>= 8
    }

    q := state / f
    r := state % f

    state = q * TOTAL + r + cum[value]

    return state, output_pos
}

decode(state uint, input []byte, input_pos uint) -> (uint, byte, uint) {
    slot := state % TOTAL

    symbol := 0

    loop i := 0..128 {
        if freq[i] != 0 {
            if slot >= cum[i] {
                if slot < cum[i] + freq[i] {
                    symbol = i
                    loop.stop()
                }
            }
        }
    }

    f := freq[symbol]

    q := state / TOTAL
    r := slot - cum[symbol]

    state = q * f + r

    loop {
        if state >= L {
            loop.stop()
        }

        input_pos -= 1

        x := input[input_pos] as uint

        state = (state << 8) + x
    }

    return state, symbol as byte, input_pos
}

main() {
    freq = new(uint, 128)
    cum = new(uint, 128)

    calc_freqs(freq)
    calc_cums(cum)

    data := "aaaaaaaaasdsad"
    state := L as uint

    output := new(byte, data.len * 2)
    output_pos := 0 as uint

    loop i := 0..data.len {
        c := data[data.len - i - 1]
        state, output_pos = encode(state, output, output_pos, c)
    }

    io.writeLine(output_pos)

    decoded := new(byte, data.len)

    d := 0 as byte

    loop i := 0..data.len {
        state, d, output_pos = decode(state, output, output_pos)
        decoded[i] = d
    }

    io.writeLine(decoded)
    io.writeLine(output_pos) // try commenting out this line
}

when I comment out io.writeLine(output_pos) program crashes

here is some variations of this program only print changes

I have no idea how printing some numbers effect the calculation of other numbers I'm really confused

I couldn't simplify the code so I'm gonna provide the code as is ``` import io const { TOTAL = 4096 L = 1 << 31 } global { freq []uint cum []uint } calc_freqs(freq []uint) { freq['a'] = 335 freq['b'] = 61 freq['c'] = 114 freq['d'] = 174 freq['e'] = 520 freq['f'] = 91 freq['g'] = 83 freq['h'] = 250 freq['i'] = 285 freq['j'] = 6 freq['k'] = 32 freq['l'] = 165 freq['m'] = 99 freq['n'] = 276 freq['o'] = 307 freq['p'] = 79 freq['q'] = 4 freq['r'] = 245 freq['s'] = 259 freq['t'] = 371 freq['u'] = 113 freq['v'] = 40 freq['w'] = 97 freq['x'] = 6 freq['y'] = 81 freq['z'] = 3 } calc_cums(cum []uint) { cum['a'] = 0 cum['b'] = 335 cum['c'] = 396 cum['d'] = 510 cum['e'] = 684 cum['f'] = 1204 cum['g'] = 1295 cum['h'] = 1378 cum['i'] = 1628 cum['j'] = 1913 cum['k'] = 1919 cum['l'] = 1951 cum['m'] = 2116 cum['n'] = 2215 cum['o'] = 2491 cum['p'] = 2798 cum['q'] = 2877 cum['r'] = 2881 cum['s'] = 3126 cum['t'] = 3385 cum['u'] = 3756 cum['v'] = 3869 cum['w'] = 3909 cum['x'] = 4006 cum['y'] = 4012 cum['z'] = 4093 } encode(state uint, output []byte, output_pos uint, value byte) -> (uint, uint) { f := freq[value] x_max := 134217728 as uint x_max *= f loop { if state < x_max { loop.stop() } output[output_pos] = (state & 255) as byte output_pos += 1 state >>= 8 } q := state / f r := state % f state = q * TOTAL + r + cum[value] return state, output_pos } decode(state uint, input []byte, input_pos uint) -> (uint, byte, uint) { slot := state % TOTAL symbol := 0 loop i := 0..128 { if freq[i] != 0 { if slot >= cum[i] { if slot < cum[i] + freq[i] { symbol = i loop.stop() } } } } f := freq[symbol] q := state / TOTAL r := slot - cum[symbol] state = q * f + r loop { if state >= L { loop.stop() } input_pos -= 1 x := input[input_pos] as uint state = (state << 8) + x } return state, symbol as byte, input_pos } main() { freq = new(uint, 128) cum = new(uint, 128) calc_freqs(freq) calc_cums(cum) data := "aaaaaaaaasdsad" state := L as uint output := new(byte, data.len * 2) output_pos := 0 as uint loop i := 0..data.len { c := data[data.len - i - 1] state, output_pos = encode(state, output, output_pos, c) } io.writeLine(output_pos) decoded := new(byte, data.len) d := 0 as byte loop i := 0..data.len { state, d, output_pos = decode(state, output, output_pos) decoded[i] = d } io.writeLine(decoded) io.writeLine(output_pos) // try commenting out this line } ``` when I comment out `io.writeLine(output_pos)` program crashes here is some variations of this program only print changes ![Screenshot 2026-08-11 210436](/attachments/6b5c606d-5cce-4767-9f9b-5f76b6385972) ![Screenshot 2026-08-11 210450](/attachments/ceaf8bdf-6442-4a7b-8876-65574469c6ff) ![Screenshot 2026-08-11 210514](/attachments/fa6326e5-ae21-4a4e-8cf6-a5a37deb3942) ![Screenshot 2026-08-11 210523](/attachments/15a89afa-43c5-4d7a-8acd-8a7043adf919) I have no idea how printing some numbers effect the calculation of other numbers I'm really confused

Screenshot 2026-08-11 210436.png

47 KiB

Screenshot 2026-08-11 210450.png

43 KiB

Screenshot 2026-08-11 210514.png

59 KiB

Screenshot 2026-08-11 210523.png

61 KiB

ed commented

2026-08-13 07:02:20 +00:00

Owner

This seems to be the result of an optimization.
There is some code in the assembler that will recognize patterns like these:

mov a, b
mov b, a

think of it as

a = b
b = a

...and it will drop the 2nd instruction because it is effectively a no-op.
However, this pattern is actually searched in the cycle detection and it should have caused a compiler panic, saying "cycle detected" because the automatic addition of a temporary register is not implemented yet.

The optimization dropped the second instruction which prevented the detection of the cycle.

To fix this, 2 things need to be implemented:

Skip this optimization in the parts of the code that rely on cycle detection.
Find a temporary register to resolve the cycle.

This seems to be the result of an optimization. There is some code in the assembler that will recognize patterns like these: ``` mov a, b mov b, a ``` think of it as ``` a = b b = a ``` ...and it will drop the 2nd instruction because it is effectively a no-op. However, this pattern is actually searched in the cycle detection and it should have caused a compiler panic, saying "cycle detected" because the automatic addition of a temporary register is not implemented yet. The optimization dropped the second instruction which prevented the detection of the cycle. To fix this, 2 things need to be implemented: 1. Skip this optimization in the parts of the code that rely on cycle detection. 2. Find a temporary register to resolve the cycle.

ed added the

bug

label

2026-08-14 10:40:01 +00:00

ed self-assigned this

2026-08-14 10:40:06 +00:00

ed commented

2026-08-20 15:44:07 +00:00

Owner

Fixed in aea6a304c4.

Fixed in https://git.urbach.dev/cli/q/commit/aea6a304c481b63fad869386d41d3fd3e9b41502.

👍 1

ed added spent time

2026-08-20 15:44:39 +00:00

8 hours

ed changed title from ~~Lifetime Bug~~ to Register swap bug when generating Phi moves

2026-08-20 15:46:10 +00:00

Furkan closed this issue

2026-08-21 19:47:28 +00:00

ed commented

2026-08-27 08:56:47 +00:00

Owner

Reopening because it's actually not completely fixed yet.
The move reordering ignores loads and stores from memory which causes x86-64 with only 16 registers to produce incorrect values, given enough register pressure.
The fix is to handle loads and stores during reordering.

Reopening because it's actually not completely fixed yet. The move reordering ignores loads and stores from memory which causes x86-64 with only 16 registers to produce incorrect values, given enough register pressure. The fix is to handle loads and stores during reordering.

ed reopened this issue

2026-08-27 08:56:47 +00:00

ed commented

2026-08-27 09:08:47 +00:00

Owner

Fixed in 6a59c5a371.

Fixed in https://git.urbach.dev/cli/q/commit/6a59c5a3716545f67c93c28fbc09db0b869a9369.

ed closed this issue

2026-08-27 09:10:30 +00:00

Furkan commented

2026-08-27 11:04:29 +00:00

Author

Can confirm code is now working

ed commented

2026-08-27 13:44:56 +00:00

Owner

Further improvements to the move scheduler in 48c81d0d9e, hopefully the last commit in regard to this problem.

Further improvements to the move scheduler in https://git.urbach.dev/cli/q/commit/48c81d0d9e0ff7a7b7e75baeb94c091bca9020a2, hopefully the last commit in regard to this problem.

Rows
Columns

Register swap bug when generating Phi moves #44