# Princeton University COS 217: Introduction to Programming Systems

## Assignment 8: A Digital Circuit Simulator: Compiled Version

### Purpose

The purpose of this assignment is to help you learn about SPARC machine language. It also will give you more experience with advanced C programming and the GNU/UNIX programming tools.

### Background

This assignment is a follow-on to the previous one.

Fundamentally, a digital circuit simulator consists of two phases: a parsing phase followed by a simulation phase. The simulation phase can be very time consuming, especially if the circuit has many flip flops and inputs, or if the simulation runs for many clock pulses. Thus it is desirable that the simulation phase be efficient. One way to make the simulation phase efficient is to translate (or "compile") it into machine language.

Your job in this assignment is to modify your program from the previous assignment so the core of its simulation phase is expressed in SPARC machine language.

Specifically, to compute the next state of its circuit your simulation phase should (recursively) traverse the circuit internal form, generating SPARC machine language instructions in an array. The machine language instructions should define a subroutine that simulates the circuit during a single clock pulse. The subroutine should accept as parameters (1) an array filled with the current input values, (2) an array filled with current flip flop values, and (3) an array that the subroutine should fill with the "next" set of flip flop values.  The subroutine should use the first two arrays to compute the values within the third, and then return. After generating the machine language subroutine, your program should repeatedly call it -- once for each clock cycle.

More specifically...

Your Simulator from the previous assignment uses this (informally stated) algorithm:

For each clock pulse...

For each flip flop F...

Traverse F's expression tree to compute its next state.

Your Simulator for this assignment should use this (informally stated) algorithm:

Add a "save" instruction, expressed in SPARC machine language, to the beginning of an array.  Thus the array contains the beginning of a subroutine.

For each flip flop F...

Traverse F's expression tree, adding to the array SPARC machine language instructions that compute F's next state. Those instructions should assume that the subroutine's first formal parameter is an array of input values, that its second formal parameter is an array of current flip flop values, and that its third formal parameter is the array of next flip flop values that it should compute.

Add "ret" and "restore" instructions, expressed in SPARC machine language, to end of the array.  Thus the array contains a complete subroutine.

For each clock pulse...

Call the subroutine that resides in the array with three actual parameters: an array of current input values, and array of current flip flop values, and an array of next flip flop values.

### An Example

Suppose you give your digital circuit simulator this "two-bit counter" circuit description:

```INPUT x ;
FLIPFLOP A B ;
NEXT A (~A & ~B & ~x) | (~A & B & x) | (A & ~B & x) | (A & B & ~x) ;
NEXT B (~A & ~B & ~x) | (~A & ~B & x) | (A & ~B & ~x) | (A & ~B & x) ;```

Then your program's simulation phase might generate this array:

 Index Contents Explanation `0` `9DE3BFA0` `save %sp, -96, %sp` `1` `E0066000` `ld [%i1 + 0], %l0 ! Load A` `2` `A01C2001` `xor %l0, 1, %l0 ! Compute ~A` `3` `E2066004` `ld [%i1 + 4], %l1 ! Load B` `4` `A21C6001` `xor %l1, 1, %l1 ! Compute ~B` `5` `A00C0011` `and %l0, %l1, %l0 ! Compute ~A & ~B` `6` `E2062000` `ld [%i0 + 0], %l1 ! Load x` `7` `A21C6001` `xor %l1, 1, %l1 ! Compute ~x` `8` `A00C0011` `and %l0, %l1, %l0 ! Compute ~A & ~B & ~x` `9` `E2066000` `ld [%i1 + 0], %l1 ! Load A` `10` `A21C6001` `xor %l1, 1, %l1 ! Compute ~A` `11` `E4066004` `ld [%i1 + 4], %l2 ! Load B` `12` `A20C4012` `and %l1, %l2, %l1 ! Compute ~A & B` `13` `E4062000` `ld [%i0 + 0], %l2 ! Load x` `14` `A20C4012` `and %l1, %l2, %l1 ! Compute ~A & B & x` `15` `A0140011` `or %l0, %l1, %l0 ! Compute (~A & ~B & ~x) | (~A & B & x)` `16` `E2066000` `ld [%i1 + 0], %l1 ! Load A` `17` `E4066004` `ld [%i1 + 4], %l2 ! Load B` `18` `A41CA001` `xor %l2, 1, %l2 ! Compute ~B` `19` `A20C4012` `and %l1, %l2, %l1 ! Compute A & ~B` `20` `E4062000` `ld [%i0 + 0], %l2 ! Load x` `21` `A20C4012` `and %l1, %l2, %l1 ! Compute A & ~B & x` `22` `A0140011` `or %l0, %l1, %l0 ! Compute (~A & ~B & ~x) | (~A & B & x) | (A & ~B & x)` `23` `E2066000` `ld [%i1 + 0], %l1 ! Load A` `24` `E4066004` `ld [%i1 + 4], %l2 ! Load B` `25` `A20C4012` `and %l1, %l2, %l1 ! Compute A & B` `26` `E4062000` `ld [%i0 + 0], %l2 ! Load x` `27` `A41CA001` `xor %l2, 1, %l2 ! Compute ~x` `28` `A20C4012` `and %l1, %l2, %l1 ! Compute A & B & ~x` `29` `A0140011` `or %l0, %l1, %l0 ! Compute (~A & ~B & ~x) | (~A & B & x) | (A & ~B & x) | (A & B & ~x)` `30` `E026A000` `st %l0, [%i2 + 0] ! Store the result as the next value of A ` `31` `E0066000` `ld [%i1 + 0], %l0 ! Load A` `32` `A01C2001` `xor %l0, 1, %l0 ! Compute ~A` `33` `E2066004` `ld [%i1 + 4], %l1 ! Load B` `34` `A21C6001` `xor %l1, 1, %l1 ! Compute ~B` `35` `A00C0011` `and %l0, %l1, %l0 ! Compute ~A & ~B` `36` `E2062000` `ld [%i0 + 0], %l1 ! Load x` `37` `A21C6001` `xor %l1, 1, %l1 ! Compute ~x` `38` `A00C0011` `and %l0, %l1, %l0 ! Compute ~A & ~B & ~x` `39` `E2066000` `ld [%i1 + 0], %l1 ! Load A` `40` `A21C6001` `xor %l1, 1, %l1 ! Compute ~A` `41` `E4066004` `ld [%i1 + 4], %l2 ! Load B` `42` `A41CA001` `xor %l2, 1, %l2 ! Compute ~B` `43` `A20C4012` `and %l1, %l2, %l1 ! Compute ~A & ~B` `44` `E4062000` `ld [%i0 + 0], %l2 ! Load x` `45` `A20C4012` `and %l1, %l2, %l1 ! Compute ~A & ~B & x` `46` `A0140011` `or %l0, %l1, %l0 ! Compute (~A & ~B & ~x) | (~A & ~B & x)` `47` `E2066000` `ld [%i1 + 0], %l1 ! Load A` `48` `E4066004` `ld [%i1 + 4], %l2 ! Load B` `49` `A41CA001` `xor %l2, 1, %l2 ! Compute ~B` `50` `A20C4012` `and %l1, %l2, %l1 ! Compute A & ~B` `51` `E4062000` `ld [%i0 + 0], %l2 ! Load x` `52` `A41CA001` `xor %l2, 1, %l2 ! Compute ~x` `53` `A20C4012` `and %l1, %l2, %l1 ! Compute A & ~B & ~x` `54` `A0140011` `or %l0, %l1, %l0 ! Compute (~A & ~B & ~x) | (~A & ~B & x) | (A & ~B & ~x)` `55` `E2066000` `ld [%i1 + 0], %l1 ! Load A` `56` `E4066004` `ld [%i1 + 4], %l2 ! Load B` `57` `A41CA001` `xor %l2, 1, %l2 ! Compute ~B` `58` `A20C4012` `and %l1, %l2, %l1 ! Compute A & ~B` `59` `E4062000` `ld [%i0 + 0], %l2 ! Load x` `60` `A20C4012` `and %l1, %l2, %l1 ! Compute A & ~B & x` `61` `A0140011` `or %l0, %l1, %l0 ! Compute (~A & ~B & ~x) | (~A & ~B & x) | (A & ~B & ~x) | (A & ~B & x)` `62` `E026A004` `st %l0, [%i2 + 4] ! Store the result as the next value of B` `63` `81C7E008` `ret` `64` `81E80000` `restore`

Note that it is column 2 of the table -- the SPARC machine language instructions that define a subroutine -- that your program should generate. The table contains the first and third columns only to help you interpret column 2.

### Flushing the Instruction Cache

For reasons that will be described in precepts, your program should flush the memory in which your array/subroutine resides before it calls the subroutine for the first time. To do that, your program should call the provided flushICache function.

### Logistics

You should develop on arizona. Use Emacs to create source code. Use gdb to debug.

The file /u/cs217/Assignment8/iflush.h contains the declaration of the flushICache function. In that same directory, the file iflush.S contains the definition of the flushICache function, in SPARC assembly language.

You should submit:

• The source code files (.h and .c) that comprise your program. You should not submit the given lexer.h, lexer.c, parser.h, parser.c, iflush.h, or iflush.S files.
• A makefile. The first rule in the makefile should command the make utility to build a file named circuitsim containing the executable version of your program. Your makefile should use the "-Wall", "-ansi", and "-pedantic" compiler options. Your makefile should maintain object (.o) files to allow for partial builds.

`/u/cs217/bin/submit 8 yoursourcecodefiles makefile readme`