Static Single Assignment

Can a spreadsheet be a programming language?

Spreadsheet State Machines :: C-to-Verilog

In this section we're going to look at the serial execution model of a normal programming languages versus single assignment in a state machine.

Spreadsheets do not have if-then-else statements, but it is possible to rewrite a program loop so that it uses conditional assignment in place of if statements. The counter in the previous article is a good example. You could compute the next value without an if statement using:

    count = (count == 9) ? 0 : count + 1;

From a Sequential Program to a Moore State Machine
Pretty much all programmers today assume a sequential execution of their program. Programmers break a problem into a series of program steps and then sequentially execute each of these steps. The problem we face going to a Moore state machine approach is that we want to use conditional assignments to update all state variable at once on each iteration through the sheet. This makes conversion to Verilog easy but designing a Moore state machine or spreadsheet program might be challenging to most programmers.

As an example, let's consider the Towers of Hanoi puzzle. We'll solve it as a normal sequential program, then resolve it as if it were one big Moore state machine, and then convert it to Verilog. While the puzzle itself is not important, the steps to convert it to a state machine are.

Towers of Hanoi Puzzle
From Wikipedia

The Towers of Hanoi puzzle can be solved iteratively using three rules. Number the pieces and then:
- Move odd numbered pieces clockwise
- Move even numbered pieces counterclockwise
- Never move the same piece twice in a row

The C program toh0.c (toh0.c toh0.txt)
has a straightforward iterative solution to the puzzle. The three puzzle stacks are modeled as three integers where each bit indicates the presence or absence of a disk on the stack. Imagine the bits of an integer arranged vertically next to the disks in the above picture. Bit 0 is the top disk and bit 1 is the second disk. In the picture above bit 7 represents the bottom disk. Moving a disk means clearing the appropriate bit in the source stack and setting the bit in the destination stack. The top-of-stack variable is a bit mask. That is, if disk #2 is the top of stack A then tosa would be 0x04. The last move is not encoded in the stack integers so it needs a separate state variable. The state variables are:

    uint32_t A, B, C;               // stacks as integers
    uint32_t tosa, tosb, tosc;      // bit set at location of LSB
    uint32_t last;                  // last piece moved

The toh0 program approaches the solution sequentially in that at each step we consider each stack and for each stack can we move the top piece clockwise or counterclockwise. There are three stacks and two directions so the program needs to consider six possibilities. Move the top of stack counterclockwise if ANDing with EVENMASK (0x55) returns non-zero. The first of the six possibilities is shown below.

    //   If the tosa is even and tosa is smaller than tosb then move tosa clockwise: A->B->C->A
    if ((tosa & EVENMASK) && (tosb > tosa) && (tosa != last)) {
        printf("Move %d from A to B\n", tosa);  // Printing bit mask, not disk #
        B =  B | tosa;           // put disk on stack B
        tosb = tosa;         // set top-of-stack B
        last = tosa;
        A = A & ~tosa;          // remove disk from A
        tosa = gettos(A);    // get new top-of-stack of A
    }

Similar code is executed for all six possibilities.

    if ((tosa & EVENMASK) && (tosb > tosa) && (tosa != last)) { // A->B
    else if ((tosa & ODDMASK) && (tosc > tosa) && (tosa != last)) {  // A->C
    else if ((tosb & EVENMASK) && (tosc > tosb) && (tosb != last )) {  // B->C
    else if ((tosb & ODDMASK ) && (tosa > tosb) && (tosb != last)) {  // B->A
    else if ((tosc & EVENMASK) && (tosa > tosc) && (tosc != last)) {  // C->A
    else if ((tosc & ODDMASK) && (tosb > tosc) && (tosc != last)) {  // C->B

The last test is not really necessary since there is always exactly one move available.


The first step in the conversion is to identify state variables and to eliminate non-state variables. The iterative solution keeps the top-of-stack as a variable. If you solve the puzzle manually you do not need to record the top of stack -- you could just look at each stack to see what is on top. The getlsb macro returns an integer with a single bit set corresponding to the least significant set bit in the input. This lets you replace the tosa, tosb, and tosc variables with the following macros:

    #define TOSA getlsb(A)
    #define TOSB getlsb(B)
    #define TOSC getlsb(C)


While not strictly required, replacing the if clause logic with macros will make the code easier to read.

    #define A2B ((TOSA & EVENMASK) && (TOSB > TOSA) && (TOSA != last))
    #define A2C ((TOSA & ODDMASK) && (TOSC > TOSA) && (TOSA != last))
    #define B2C ((TOSB & EVENMASK) && (TOSC > TOSB) && (TOSB != last ))
    #define B2A ((TOSB & ODDMASK ) && (TOSA > TOSB) && (TOSB != last))
    #define C2A ((TOSC & EVENMASK) && (TOSA > TOSC) && (TOSC != last))
    #define C2B ((TOSC & ODDMASK) && (TOSB > TOSC) && (TOSC != last))


The program toh1.c (toh1.c toh1.txt)
eliminates the top-of-stack variables and uses macros to compute the top-of-stack as needed. Note that this program will run slower than the original since the TOS values are computed each time they are used. You won't see any speed gain from the state machine approach until your application runs on a fully parallel machine.

The next step in the conversion is to add shadow variables for all of the state variables in the program. In this example an 's' is prepended to the state variables to indicate a shadow variable. Replace all the left-hand-side assignment targets with their shadow equivalents. Do not change the right-hand-side of the assignments. The first section given above now becomes:

    //   If the tosa is even and tosa is smaller than tosb then move tosa clockwise: A->B->C->A
    if (A2B) {
        printf("Move %d from A to B\n", TOSA);  // Printing bit mask, not disk #
        sB = B | TOSA;        // put disk on stack B
        slast = TOSA;
        sA = A & ~TOSA;     // remove disk from A
    }

At the bottom of the loop, after all the assignments are done, copy the shadow values to the visible values.

    A = sA;
    B = sB;
    C = sC;
    last = slast;

You might want to compile and test the modified code (toh2.c toh2.txt) at this point. It should give output identical to the original code.

The use of shadow variables lets you remove the else from the if statements. The six if clauses become:

    if (A2B) {
    if (A2C) {
    if (B2C) {
    if (B2A) {
    if (C2A) {
    if (C2B) {

The next step is to replace the if blocks with an if condition for each assignment within the block. For example, consider the program block that moves the top of A to stack B:

    if (A2B) {
        printf("Move %d from A to B\n", TOSA);
        sB = B | TOSA;       // put disk on stack B
        slast = TOSA;
        sA = A & ~TOSA;      // remove disk from A
    }

The above code is replaced by four if statements:

    //   If the tos is even move it clockwise:  A->B->C->A
    if (A2B)
        printf("Move %d from A to B\n", TOSA);
    if (A2B)
        sB = B | TOSA;       // put disk on stack B
    if (A2B)
        slast = TOSA;
    if (A2B)
        sA = A & ~TOSA;      // remove disk from A

Each of the assignment statements now has a qualifying if statement. Code with these changes is available as toh3 (toh3.c toh3.txt).

Rearrange the if statements to group together all of the assignments for a variable. For example the if statements assigning a value to variable sA are:

    if (A2B)
        sA = A & ~TOSA;      // remove disk from A
    if (A2C)
        sA = A & ~TOSA;      // remove disk from A
    if (B2A)
        sA = A | TOSB;       // put disk on stack A
    if (C2A)
        sA = A | TOSC;       // put disk on stack A

The final step is to replace the if-assignment statements with assignment-conditional statements. That is, the above is now in a form that let's you easily write a conditional assignment for sA:

    sA = (A2B) ?  A & ~TOSA :    // remove disk from A
         (A2C) ?  A & ~TOSA :    // remove disk from A
         (B2A) ?  A | TOSB :     // put disk on stack A
         (C2A) ?  A | TOSC :     // put disk on stack A
         sA;

The main loop now has a single assignment for each state variable. The fully converted code as a Moore state machine is available as toh4 (toh4.c toh4.txt).


Converting a Moore State Machine to Verilog is fairly easy. Named logic copies almost directly as does any logic for state variables. More effort is needed for the program input/output, start/stop, and initialization. The above toh4.c is converted to Verilog as toh.v (toh.v toh.txt).

A testbench for toh.v is available as toh_tb.v (toh_tb.v toh_tb.txt). You can run the Verilog program by installing Icarus Verilog and running the commands:


    iverilog -o toh_tb.vvp -g2009 toh.v toh_tb.v
    vvp toh_tb.vvp -lxt2

You can view the internal logic of the program as it runs using gtkwave.


    gtkwave toh_tb.xt2

The toh.v file compiles cleanly for Vivado and runs fine on a Digilent Basys3 FPGA board with a clock rate of 100 MHz. While 10 nanoseconds per move seems quick it is actually slower than an x86_64 processor. The original C program is small enough to fit entirely in L1 cache and in 10 nanoseconds a pipelined, hyperthreaded CPU might be able to execute fifty or sixty instruction from L1 cache.


Hopefully this example has shown you that, yes, you really can convert a serial oriented program into a parallel Moore state machine. This example also helps highlight some requirements for a Turing complete spreadsheet, the topic of the next section.

Posted by Bob Smith | on