Shuffling nodes affects scf/ccf behaviour

scf/ccf seems to be susceptible to the order nodes are getting updated in during simulation.

Can be reproduced on https://github.com/kosarev/z80/commit/ec19a48df0cd9c022eeab8f8626e459090578b14, with seemingly any seed, though one time I observed all tests passing with the shuffling enabled on an early version of the patch that didn't support seeding yet, so presumably not all seeds will do.

Feels like this may have something to do with rlca & Co. not having the expected effect on scf/ccf in our simulation as mentioned in https://github.com/kosarev/z80/issues/42#issuecomment-1259959562.

The task is to try to minimise the reproducer and determine the specific conditions that trigger the behaviour change.

xref: https://discord.com/channels/654774470652723220/689220116801650811/1031181913878183966

$ pypy3 z80sim.py --seed=568
17:21:43  8/51 cpl                                                                         
17:25:50  1/51 <alu> (hl)
17:25:52  9/51 daa
17:26:14  6/51 bit (hl)
17:26:29  3/51 <alu> {b, c, d, e, h, l, a}
17:27:28  2/51 <alu> n
17:27:42  7/51 call nn
17:29:23  11/51 ei/di
17:30:08  13/51 ex af, af'
17:30:37  5/51 add hl, <rp>
17:31:10  14/51 ex de, hl
17:31:45  15/51 exx
17:34:46  16/51 im/xim n
17:37:06  12/51 ex (sp), hl
17:37:17  4/51 adc/sbc hl, <rp>
17:38:11  19/51 inc/dec (hl)
17:40:30  17/51 in a, (n)/out (n), a
17:41:05  20/51 inc/dec <rp>
17:42:38  22/51 jp hl
17:43:31  21/51 inc/dec {b, c, d, e, h, l, a}
17:43:55  18/51 in/out r, (c)
17:46:51  23/51 jp nn
17:49:30  28/51 ld (hl), {b, c, d, e, h, l, a}
17:50:13  26/51 ld (<rp>), a/ld a, (<rp>)
17:50:16  27/51 ld (hl), n
17:53:53  25/51 jr d
17:55:18  33/51 ld sp, hl
17:57:17  30/51 ld <rp>, nn
18:00:41  31/51 ld a, (nn)/ld (nn), a
18:01:23  34/51 ld {b, c, d, e, h, l, a}, (hl)
18:02:57  29/51 ld <rp>, (nn)/ld (nn), <rp>
18:03:44  35/51 ld {b, c, d, e, h, l, a}, n
18:05:11  36/51 ld {b, c, d, e, h, l, a}, {b, c, d, e, h, l, a}
18:05:21  32/51 ld hl, (nn)/ld (nn), hl
18:05:33  39/51 nop
18:06:11  38/51 neg/xneg
18:10:10  10/51 djnz d
18:11:34  42/51 ret
18:11:55  37/51 ld {i, r}, a/ld a, {i, r}
18:14:01  44/51 reti/retn/xretn
18:15:00  40/51 pop <rp2>
18:15:09  45/51 rlca/rrca/rla/rra
18:15:34  41/51 push <rp2>
17:17:06  
FAILED: scf/ccf reg_f3 (xf)
  before: f_b3
  after: (and (or is_ex_af_af2 a_b3) (or (not is_ex_af_af2) f_b3))
  expected: (and (or f_b3 a_b3) (or (not is_ex_af_af2) f_b3))
  diff: (and f_b3 (not is_ex_af_af2) (not a_b3))
18:17:58  50/51 Traceback (most recent call last):
  File "./z80sim.py", line 2962, in test_instr_seq
    process_instr(seq, state, test=True)
  File "./z80sim.py", line 2836, in process_instr
    token = test_node(instrs, n, at_start, at_end, before, after)
  File "./z80sim.py", line 2315, in test_node
    return check(Bool.ifelse(ignores_f, a, a | f))
  File "./z80sim.py", line 2144, in check
    raise TestFailure()
TestFailure

18:18:42  49/51 rst n
18:18:46  51/51 xnop
18:20:02  24/51 jr cc, d
18:20:54  48/51 rrd/rld
18:39:00  43/51 ret cc
19:18:08  47/51 rot/res/set (hl)
19:27:45  46/51 rot/bit/res/set {b, c, d, e, h, l, a}
FAILED

Changing the code to update all nodes on every round leads to more failures on xf and yf even without round-level shuffling.

Because updating rounds essentially quantify propagation of signals, thus making the simulation behave more like real hardware, updating all nodes effectively works as cross-round shuffling. The failures we see with that quantification eliminated should probably suggest that all or at least many instructions updating flags 3 and 5 depend on particular propagation timings, technically meaning race condition, with scf/ccf being the case where the balance between possible outcomes is fragile enough to be visible when using actual hardware, as people on the Discord server report.

diff --git a/tests/z80sim/z80sim.py b/tests/z80sim/z80sim.py
index 1333e46..de76120 100755
--- a/tests/z80sim/z80sim.py
+++ b/tests/z80sim/z80sim.py
@@ -1419,7 +1419,7 @@ class Z80Simulator(object):

     def __update_nodes(self, nodes, *, shuffle=True):
         # TODO: Does always updating all nodes lead to any failures?
-        # nodes = list(self.__nodes.values())
+        nodes = list(self.__nodes.values())

         shuffle &= (SEED is not None)
         nodes = list(nodes)
@@ -2141,7 +2141,8 @@ def test_node(instrs, n, at_start, at_end, before, after):
                 f'  expected: {x}',
                 f'  diff: {a ^ x}'))
         print('\n'.join(lines), file=sys.stderr, flush=True)
-        raise TestFailure()
+        # raise TestFailure()
+        return CheckToken()

     phase = len(instrs)
     instr = instrs[-1]

$ pypy3 z80sim.py --single-thread --no-before-after-expected

FAILED: inc/dec {b, c, d, e, h, l, a} reg_f3 (xf)

FAILED: inc/dec {b, c, d, e, h, l, a} reg_f5 (yf)

FAILED: inc/dec {b, c, d, e, h, l, a} reg_ff3 (xf)

FAILED: inc/dec {b, c, d, e, h, l, a} reg_ff5 (yf)
13:17:59  1/51 inc/dec {b, c, d, e, h, l, a}

FAILED: in/out r, (c) reg_f3 (xf)

FAILED: in/out r, (c) reg_f5 (yf)

FAILED: in/out r, (c) reg_ff3 (xf)

FAILED: in/out r, (c) reg_ff5 (yf)
13:18:00  2/51 in/out r, (c)

FAILED: <alu> {b, c, d, e, h, l, a} reg_f3 (xf)

FAILED: <alu> {b, c, d, e, h, l, a} reg_f5 (yf)

FAILED: <alu> {b, c, d, e, h, l, a} reg_ff3 (xf)

FAILED: <alu> {b, c, d, e, h, l, a} reg_ff5 (yf)
13:18:03  3/51 <alu> {b, c, d, e, h, l, a}

FAILED: adc/sbc hl, <rp> reg_f3 (xf)

FAILED: adc/sbc hl, <rp> reg_f5 (yf)

FAILED: adc/sbc hl, <rp> reg_ff3 (xf)

FAILED: adc/sbc hl, <rp> reg_ff5 (yf)
13:18:05  4/51 adc/sbc hl, <rp>

FAILED: add hl, <rp> reg_f3 (xf)

FAILED: add hl, <rp> reg_f5 (yf)

FAILED: add hl, <rp> reg_ff3 (xf)

FAILED: add hl, <rp> reg_ff5 (yf)
13:18:06  5/51 add hl, <rp>

FAILED: <alu> n reg_f3 (xf)

FAILED: <alu> n reg_f5 (yf)

FAILED: <alu> n reg_ff3 (xf)

FAILED: <alu> n reg_ff5 (yf)
13:18:06  6/51 <alu> n

FAILED: <alu> (hl) reg_f3 (xf)

FAILED: <alu> (hl) reg_f5 (yf)

FAILED: <alu> (hl) reg_ff3 (xf)

FAILED: <alu> (hl) reg_ff5 (yf)
13:18:07  7/51 <alu> (hl)

FAILED: bit (hl) reg_f3 (xf)

FAILED: bit (hl) reg_f5 (yf)

FAILED: bit (hl) reg_ff3 (xf)

FAILED: bit (hl) reg_ff5 (yf)
13:18:08  8/51 bit (hl)

FAILED: rot/bit/res/set {b, c, d, e, h, l, a} reg_f3 (xf)

FAILED: rot/bit/res/set {b, c, d, e, h, l, a} reg_f5 (yf)

FAILED: rot/bit/res/set {b, c, d, e, h, l, a} reg_ff3 (xf)

FAILED: rot/bit/res/set {b, c, d, e, h, l, a} reg_ff5 (yf)
13:18:22  9/51 rot/bit/res/set {b, c, d, e, h, l, a}
13:18:25  10/51 rot/res/set (hl)
13:18:26  11/51 ret cc
13:18:26  12/51 djnz d
13:18:27  13/51 jr cc, d
13:18:28  14/51 xnop
13:18:28  15/51 rrd/rld
13:18:28  16/51 rst n

FAILED: scf/ccf reg_f3 (xf)

FAILED: scf/ccf reg_f5 (yf)

FAILED: scf/ccf reg_ff3 (xf)

FAILED: scf/ccf reg_ff5 (yf)
13:18:29  17/51 scf/ccf
13:18:29  18/51 rlca/rrca/rla/rra
13:18:30  19/51 reti/retn/xretn
13:18:30  20/51 pop <rp2>
13:18:30  21/51 ret
13:18:31  22/51 push <rp2>
13:18:31  23/51 ld {i, r}, a/ld a, {i, r}
13:18:32  24/51 neg/xneg
13:18:32  25/51 ld {b, c, d, e, h, l, a}, {b, c, d, e, h, l, a}
13:18:33  26/51 nop
13:18:33  27/51 ld hl, (nn)/ld (nn), hl
13:18:34  28/51 ld {b, c, d, e, h, l, a}, n
13:18:34  29/51 ld <rp>, (nn)/ld (nn), <rp>
13:18:34  30/51 ld {b, c, d, e, h, l, a}, (hl)
13:18:35  31/51 ld a, (nn)/ld (nn), a
13:18:35  32/51 jr d
13:18:36  33/51 ld <rp>, nn
13:18:36  34/51 ld sp, hl
13:18:36  35/51 ld (hl), n
13:18:37  36/51 ld (hl), {b, c, d, e, h, l, a}
13:18:37  37/51 ld (<rp>), a/ld a, (<rp>)
13:18:38  38/51 jp nn
13:18:38  39/51 jp hl
13:18:38  40/51 inc/dec <rp>
13:18:39  41/51 inc/dec (hl)
13:18:39  42/51 daa
13:18:39  43/51 cpl
13:18:40  44/51 call nn
13:18:40  45/51 ex (sp), hl
13:18:41  46/51 in a, (n)/out (n), a
13:18:41  47/51 ei/di
13:18:41  48/51 im/xim n
13:18:42  49/51 exx
13:18:42  50/51 ex de, hl
13:18:42  51/51 ex af, af'

kosarev / z80

Shuffling nodes affects scf/ccf behaviour #51