fsm_state changes mid cycle

[BracketMaster]

This "minimal" example is kind of long, but you said you[Whitequark] think you know what buy we're hitting.
I'll keep this example as is for now and try to trim it later.

"""Simple example of a FSM-based ALU

This demonstrates a design that follows the valid/ready protocol of the
ALU, but with a FSM implementation, instead of a pipeline.  It is also
intended to comply with both the CompALU API and the nmutil Pipeline API
(Liskov Substitution Principle)

The basic rules are:

1) p.ready_o is asserted on the initial ("Idle") state, otherwise it keeps low.
2) n.valid_o is asserted on the final ("Done") state, otherwise it keeps low.
3) The FSM stays in the Idle state while p.valid_i is low, otherwise
   it accepts the input data and moves on.
4) The FSM stays in the Done state while n.ready_i is low, otherwise
   it releases the output data and goes back to the Idle state.

"""

from nmigen import Elaboratable, Signal, Module, Cat
cxxsim = True
if cxxsim:
    from nmigen.sim.cxxsim import Simulator, Settle
else:
    from nmigen.back.pysim import Simulator, Settle
from nmigen.cli import rtlil
from math import log2


class Dummy:
    pass


class Shifter(Elaboratable):
    """Simple sequential shifter

    Prev port data:
    * p.data_i.data:  value to be shifted
    * p.data_i.shift: shift amount
    *                 When zero, no shift occurs.
    *                 On POWER, range is 0 to 63 for 32-bit,
    *                 and 0 to 127 for 64-bit.
    *                 Other values wrap around.

    Next port data:
    * n.data_o.data: shifted value
    """
    class PrevData:
        def __init__(self, width):
            self.data = Signal(width, name="p_data_i")
            self.shift = Signal(width, name="p_shift_i")

        def _get_data(self):
            return [self.data, self.shift]

    class NextData:
        def __init__(self, width):
            self.data = Signal(width, name="n_data_o")

        def _get_data(self):
            return [self.data]

    def __init__(self, width):
        self.width = width
        self.p = Dummy()
        self.n = Dummy()
        self.p.valid_i = Signal(name="p_valid_i")
        self.p.ready_o = Signal(name="p_ready_o")
        self.n.ready_i = Signal(name="n_ready_i")
        self.n.valid_o = Signal(name="n_valid_o")

        self.p.data_i = Shifter.PrevData(width)
        self.n.data_o = Shifter.NextData(width)

    def elaborate(self, platform):
        m = Module()

        # Note:
        # It is good practice to design a sequential circuit as
        # a data path and a control path.

        # Data path
        # ---------
        # The idea is to have a register that can be
        # loaded or shifted (left and right).

        # the control signals
        load = Signal()
        shift = Signal()
        # the data flow
        shift_in = Signal(self.width)
        shift_left_by_1 = Signal(self.width)
        next_shift = Signal(self.width)
        # the register
        shift_reg = Signal(self.width, reset_less=True)
        # build the data flow
        m.d.comb += [
            # connect input and output
            shift_in.eq(self.p.data_i.data),
            self.n.data_o.data.eq(shift_reg),
            # generate shifted views of the register
            shift_left_by_1.eq(Cat(0, shift_reg[:-1])),
        ]
        # choose the next value of the register according to the
        # control signals
        # default is no change
        m.d.comb += next_shift.eq(shift_reg)
        with m.If(load):
            m.d.comb += next_shift.eq(shift_in)
        with m.Elif(shift):
            m.d.comb += next_shift.eq(shift_left_by_1)

        # register the next value
        m.d.sync += shift_reg.eq(next_shift)

        # Control path
        # ------------
        # The idea is to have a SHIFT state where the shift register
        # is shifted every cycle, while a counter decrements.
        # This counter is loaded with shift amount in the initial state.
        # The SHIFT state is left when the counter goes to zero.

        # Shift counter
        shift_width = int(log2(self.width)) + 1
        next_count = Signal(shift_width)
        count = Signal(shift_width, reset_less=True)
        m.d.sync += count.eq(next_count)

        #m.d.comb += self.p.ready_o.eq(1)

        with m.FSM():
            with m.State("IDLE"):
                m.d.comb += [
                    # keep p.ready_o active on IDLE
                    self.p.ready_o.eq(1),
                    # keep loading the shift register and shift count
                    load.eq(1),
                    next_count.eq(self.p.data_i.shift),
                ]
                with m.If(self.p.valid_i):
                    # Leave IDLE when data arrives
                    with m.If(next_count == 0):
                        # short-circuit for zero shift
                        m.next = "DONE"
                    with m.Else():
                        m.next = "SHIFT"
            with m.State("SHIFT"):
                m.d.comb += [
                    # keep shifting, while counter is not zero
                    shift.eq(1),
                    # decrement the shift counter
                    next_count.eq(count - 1),
                ]
                with m.If(next_count == 0):
                    # exit when shift counter goes to zero
                    m.next = "DONE"
            with m.State("DONE"):
                # keep n.valid_o active while the data is not accepted
                m.d.comb += self.n.valid_o.eq(1)
                with m.If(self.n.ready_i):
                    # go back to IDLE when the data is accepted
                    m.next = "IDLE"

        return m

    def __iter__(self):
        yield self.p.data_i.data
        yield self.p.data_i.shift
        yield self.p.valid_i
        yield self.p.ready_o
        yield self.n.ready_i
        yield self.n.valid_o
        yield self.n.data_o.data

    def ports(self):
        return list(self)


def test_shifter():
    m = Module()
    m.submodules.shf = dut = Shifter(8)
    print("Shifter port names:")
    for port in dut:
        print("-", port.name)
    # generate RTLIL
    # try "proc; show" in yosys to check the data path
    il = rtlil.convert(dut, ports=dut.ports())
    with open("test_shifter.il", "w") as f:
        f.write(il)
    sim = Simulator(m)
    sim.add_clock(1e-6)

    def send(data, shift):
        yield
        yield
        yield
        yield
        yield
        yield
        yield
        # present input data and assert valid_i
        yield dut.p.data_i.data.eq(data)
        yield dut.p.data_i.shift.eq(shift)
        yield dut.p.valid_i.eq(1)
        yield
        print ("set up signals")
        # wait for p.ready_o to be asserted
        ready_o = yield dut.p.ready_o
        print ("ready_o", ready_o)
        while not (yield dut.p.ready_o):
            ready_o = yield dut.p.ready_o
            print ("ready_o", ready_o)
            yield
        print ("done ready check")
        # clear input data and negate p.valid_i
        yield dut.p.valid_i.eq(0)
        yield dut.p.data_i.data.eq(0)
        yield dut.p.data_i.shift.eq(0)
        print ("done send")

    def receive(expected):
        yield
        # signal readiness to receive data
        yield dut.n.ready_i.eq(1)
        yield
        # wait for n.valid_o to be asserted
        valid_o = yield dut.n.valid_o
        print ("        valid_o", valid_o)
        while not (yield dut.n.valid_o):
            valid_o = yield dut.n.valid_o
            print ("        valid_o", valid_o)
            yield

        # read result
        result = yield dut.n.data_o.data

        # "FIX" the problem with this line:
        #yield    # <---- remove this - pysim "works" but cxxsim does not

        # negate n.ready_i
        yield dut.n.ready_i.eq(0)
        # check result
        assert result == expected
        print ("        done receive")

    def producer():
        print ("start of producer")
        yield from send(3, 4)
        print ("end of producer")

    def consumer():
        yield
        # the consumer is not in step with the producer, but the
        # order of the results are preserved
        # 3 << 4 = 48
        print ("        start of receiver")
        yield from receive(48)
        print ("        end of receiver")

    sim.add_sync_process(producer)
    sim.add_sync_process(consumer)
    sim_writer = sim.write_vcd(
        "test_shifter.vcd",
    )
    with sim_writer:
        sim.run()


if __name__ == "__main__":
    test_shifter()

[cestrauss]

Greetings. I'm Cesar, from libre-SOC.

I'd like to point to the previous discussion on https://bugs.libre-soc.org/show_bug.cgi?id=417#c13, where the issue first arose.

I managed to trim the test case by removing the shift state. Since only two states remain, the next logical step is to replace the FSM with a one-bit register.

"""Simple Handshake Test

1) p_ready_o is asserted on the initial ("Idle") state, otherwise it keeps low.
2) n_valid_o is asserted on the final ("Done") state, otherwise it keeps low.
3) The FSM stays in the Idle state while p_valid_i is low, otherwise
   it goes to Done.
4) The FSM stays in the Done state while n_ready_i is low, otherwise
   it goes back to Idle.
"""

from nmigen import Elaboratable, Signal, Module

cxxsim = True
if cxxsim:
    from nmigen.sim.cxxsim import Simulator, Settle
else:
    from nmigen.sim.pysim import Simulator, Settle


class Handshake(Elaboratable):

    def __init__(self):
        self.p_valid_i = Signal()
        self.p_ready_o = Signal()
        self.n_ready_i = Signal()
        self.n_valid_o = Signal()

    def elaborate(self, platform):
        m = Module()

        with m.FSM():
            with m.State("IDLE"):
                m.d.comb += self.p_ready_o.eq(1)
                with m.If(self.p_valid_i):
                    m.next = "DONE"
            with m.State("DONE"):
                m.d.comb += self.n_valid_o.eq(1)
                with m.If(self.n_ready_i):
                    m.next = "IDLE"

        return m

    def __iter__(self):
        yield self.p_valid_i
        yield self.p_ready_o
        yield self.n_ready_i
        yield self.n_valid_o

    def ports(self):
        return list(self)


def test_handshake():
    m = Module()
    m.submodules.hsk = dut = Handshake()
    sim = Simulator(m)
    sim.add_clock(1e-6)

    def send():
        yield
        yield
        yield
        yield
        yield
        yield
        yield
        # assert p_valid_i
        yield dut.p_valid_i.eq(1)
        yield
        print("set up signals")
        # wait for p_ready_o to be asserted
        ready_o = yield dut.p_ready_o
        print("ready_o", ready_o)
        while not (yield dut.p_ready_o):
            ready_o = yield dut.p_ready_o
            print("ready_o", ready_o)
            yield
        print("done ready check")
        # negate p_valid_i
        yield dut.p_valid_i.eq(0)
        print("done send")

    def receive():
        yield
        # signal readiness to receive data
        yield dut.n_ready_i.eq(1)
        yield
        # wait for n_valid_o to be asserted
        valid_o = yield dut.n_valid_o
        print("        valid_o", valid_o)
        while not (yield dut.n_valid_o):
            valid_o = yield dut.n_valid_o
            print("        valid_o", valid_o)
            yield
        # negate n_ready_i
        yield dut.n_ready_i.eq(0)
        print("        done receive")

    def producer():
        print("start of producer")
        yield from send()
        print("end of producer")

    def consumer():
        yield
        # the consumer is not in step with the producer, but the
        # order of the results are preserved
        # 3 << 4 = 48
        print("        start of receiver")
        yield from receive()
        print("        end of receiver")

    sim.add_sync_process(producer)
    sim.add_sync_process(consumer)
    sim_writer = sim.write_vcd("handshake.vcd")
    with sim_writer:
        sim.run()


if __name__ == "__main__":
    test_handshake()

[BracketMaster]

Thanks Cesar. BracketMaster is Yehowshua BTW.

[whitequark]

This looks much better, thank you! Though it seems like it could be minimized a bit further without much effort?

[cestrauss]

On https://bugs.libre-soc.org/show_bug.cgi?id=417#c15, Luke wrote:

                 m.d.comb += self.n.valid_o.eq(1)
                 with m.If(self.n.ready_i):
                    # go back to IDLE when the data is accepted
                    m.next = "IDLE"

this should set the FSM to "IDLE" on the next cycle, however
the fact that in the unit test ready_i is dropped immediately,
combined with the fact that valid_o is set combinatorially, what
happens instead is:

• valid_o is set to 1 (combinatorially)
• unit test (combinatorially) notices that (in the while yield loop)
• unit test (combinatorially) sets ready_i to 0
• DUT - combinatorially - notices that ready_i has been set to 0
• DUT NO LONGER ASSERTS m.next=IDLE

To which, I replied:

Unit test work sequentially, not combinatorially, unless Settle() is used.
This unit test does not use Settle().

On the other hand, the behavior of cxxsim is consistent with it doing an implicit Settle() after a yield.

The following test demonstrates it:

from nmigen import Elaboratable, Signal, Module
from nmigen.sim.cxxsim import Simulator as CxxSimulator
from nmigen.sim.pysim import Simulator as PySimulator


class SamplePoint(Elaboratable):
    """Just a simple one-bit register"""

    def __init__(self):
        self.data_i = Signal()
        self.data_o = Signal()

    def elaborate(self, _):
        m = Module()
        m.d.sync += self.data_o.eq(self.data_i)
        return m
        
    def ports(self):
        return [self.data_i, self.data_o]


def test_sample_point(sim_type):
    print("Testing", sim_type)

    if sim_type == "cxxsim":
        simulator = CxxSimulator
    else:
        simulator = PySimulator

    m = Module()
    m.submodules.sp = dut = SamplePoint()
    sim = simulator(m)
    sim.add_clock(1e-6)

    def process():
        # present data to register input, to be latched at the next clock
        # rising edge
        yield dut.data_i.eq(1)
        yield
        # at this point, just after the clock rising edge, the register
        # should still hold its previous (reset) value
        assert (yield dut.data_o) == 0

    sim.add_sync_process(process)
    sim_writer = sim.write_vcd(f"{sim_type}.vcd")
    with sim_writer:
        sim.run()
    
    print("PASS")


if __name__ == "__main__":
    test_sample_point("pysim")
    test_sample_point("cxxsim")

[whitequark]

On the other hand, the behavior of cxxsim is consistent with it doing an implicit Settle() after a yield.

This narrows it down enough. Thanks for your effort, I'll fix this soon.

[whitequark]

This issue is now fixed in the cxxsim branch.

[cestrauss]

Greetings.

After a pull of the cxxsim branch (commit 1f8ba74), it looks like the register is not being updated, at all, even after a Settle() or a yield.

I modified the previous test case, to check for this.

from nmigen import Elaboratable, Signal, Module
from nmigen.sim.cxxsim import Simulator as CxxSimulator
from nmigen.sim.cxxsim import Settle as CxxSettle
from nmigen.sim.pysim import Simulator as PySimulator
from nmigen.sim.pysim import Settle as PySettle


class SamplePoint(Elaboratable):
    """Just a simple one-bit register"""

    def __init__(self):
        self.data_i = Signal()
        self.data_o = Signal()

    def elaborate(self, _):
        m = Module()
        m.d.sync += self.data_o.eq(self.data_i)
        return m
        
    def ports(self):
        return [self.data_i, self.data_o]


def test_sample_point(sim_type):
    print("Testing", sim_type)

    if sim_type == "cxxsim":
        simulator = CxxSimulator
        settle = CxxSettle
    else:
        simulator = PySimulator
        settle = PySettle

    m = Module()
    m.submodules.sp = dut = SamplePoint()
    sim = simulator(m)
    sim.add_clock(1e-6)

    def process():
        # present data to register input, to be latched at the next clock
        # rising edge
        yield dut.data_i.eq(1)
        yield
        # at this point, just after the clock rising edge, the register
        # should still hold its previous (reset) value
        assert (yield dut.data_o) == 0
        print("Check reset value: PASS")
        yield settle()
        # now we should see it
        assert (yield dut.data_o) == 1
        print("Check latched value: PASS")

    sim.add_sync_process(process)
    sim_writer = sim.write_vcd(f"{sim_type}.vcd")
    with sim_writer:
        sim.run()
    

if __name__ == "__main__":
    test_sample_point("pysim")
    test_sample_point("cxxsim")