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

Shuffling nodes affects scf/ccf behaviour #51

Open
kosarev opened this issue Oct 15, 2022 · 1 comment
Open

Shuffling nodes affects scf/ccf behaviour #51

kosarev opened this issue Oct 15, 2022 · 1 comment
Assignees

Comments

@kosarev
Copy link
Owner

kosarev commented Oct 15, 2022

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

Can be reproduced on ec19a48, 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 #42 (comment).

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    
@kosarev
Copy link
Owner Author

kosarev commented Oct 16, 2022

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 kosarev self-assigned this Mar 22, 2023
kosarev added a commit that referenced this issue Jul 1, 2023
This prevents unnecessary updates of nodes that were previously
members of these groups.
kosarev added a commit that referenced this issue Jul 1, 2023
kosarev added a commit that referenced this issue Jul 1, 2023
This makes it easier to consider various orders in which gates
are getting updates.
kosarev added a commit that referenced this issue Jul 1, 2023
This should simplify computing and accessing dependencies between
nodes.
kosarev added a commit that referenced this issue Jul 17, 2024
Needed to keep the old states available, whuch in turn is needed
to consider different orders of updating gate states.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant