This is the website for a prior semester's offering of CS 3330.

Changelog:

You can download hclrs.tar here. (Last updated: 9 Sep 2018.)

Using HCLRS

Setup

When you first untar hclrs.tar (with tar xvf hclrs.tar), enter the hclrs directory and run make with no arguments.

If you get any error messages, see Installation of C from lab 0. If you are on Windows, see the sections below (but you probably will have an easier time using Linux via a VM or by SSHing nto a lab machine).

Recompiling HCLRS

The distribution we have supplied includes a precompiled binary of the HCL interpreter for Linux (64- and 32-bit) and OS X (64- and 32-bit). We have not tested the OS X binaries. To instead compile the HCL interpreter yourself, follow the instructions here to install an implementation of the programming language Rust, then run make compile-hclrs.

Windows Binaries

There are also Windows binaries in the two .zip files in the tools directory. You will need to extract these manually; make will not do it for you.

Note that we have not tested anything on Windows, and do not recommend this.

Updating HCLRS binaries

You can run the command make update-hclrs to download new copies of the HCLRS binaries from the instructor’s website. This command will require you to have the tool curl installed.

Checking .hcl for errors

To test tiny.hcl for compilation errors, run

      ./hclrs --check tiny.hcl

If no errors are output, the syntax was OK.

Running .hcl on .yo

To test an HCL file tiny.hcl on y86/alu.yo,

  1. Make sure you are in the hclrs directory; the Makefile depends on this
  2. Make sure tiny.hcl is also in the hclrs directory

  3. Run

    ./hclrs tiny.hcl y86/alu.yo
  4. You can also give ./hclrs various flags, like -q and -d; running ./hclrs with no arguments will list the permitted flags.

Turning a .ys into .yo

To turn a Y86 assembly file toy.ys into loadable memory image toy.yo,

  1. Make sure you are in either the hclrs directory or the hclrs/y86; the Makefile depends on this
  2. Run make toy.yo{.bash}

Seeing what a .yo file is supposed to do

In the tools folder is a program called yis; running this on a yo file will show a summary of its correct results.

      ./tools/yis y86/alu.yo

This will list any registers that should be changed by the program, along with their initial and final values, and any memory locations that should be changed by the program, along with their initial and final values.

For example, the above command outputs:

      Stopped in 10 steps at PC = 0x40.  Status 'HLT', CC Z=0 S=0 O=0
Changes to registers:
%rax:   0x0000000000000000      0x0000000000000314
%rcx:   0x0000000000000000      0x000000000000bba3
%rbx:   0x0000000000000000      0x00000000000000a3

Changes to memory:
0x0060: 0x0000000000000000      0x0000bba300000000

meaning that:

Our flavor of HCL

We use a variant of HCL we created that is similar to, but not the same as, the book’s variant.

Like the book’s flavor, our HCL has muxes (case expresssions) with [ condition : value; ] syntax; comparisons (==, <, etc), boolean (&&, !, ||) and set membership (x in {y,z}) operators.

Unlike the book’s flavor, we declare things differently:

Unlike the book’s flavor, we also have more operators:

Order of code usually does not matter: all statements are executed in parallel and shuffling the order of lines in your code does not change your code’s meaning. As an exception to this rule, the cases of a mux are evaluated in order, so [ x==1 : 3; 1 : 4 ] will have different values if x is 1 than if it is not, but [ 1: 4; x==1 : 3 ] will always evaluate to 4, no matter the value of x. Similarly, non-commutative operators like - and <= have the same order-dependent meaning in HCLRS that they have in C.

Built-in functionality of the simulators

Part of the goal of this flavor of HCL was to give greater freedom to re-wire what in the textbook author’s version was built-in functionality. However, we still provide hard-wired some components, such as memory and the register file.

View 1: Wires and constants

This section and the following section contain the same information, but presented in a different way.

The simulator provides the following built-in signals and constants:

      ###################### begin builtin signals ##########################

### constants:

const STAT_BUB = 0b000, STAT_AOK = 0b001, STAT_HLT = 0b010;  # expected behavior
const STAT_ADR = 0b011, STAT_INS = 0b100, STAT_PIP = 0b110;  # error conditions

const REG_RAX = 0b0000, REG_RCX = 0b0001, REG_RDX = 0b0010, REG_RBX = 0b0011;
const REG_RSP = 0b0100, REG_RBP = 0b0101, REG_RSI = 0b0110, REG_RDI = 0b0111;
const REG_R8  = 0b1000, REG_R9  = 0b1001, REG_R10 = 0b1010, REG_R11 = 0b1011;
const REG_R12 = 0b1100, REG_R13 = 0b1101, REG_R14 = 0b1110, REG_NONE= 0b1111;

# icodes; see figure 4.2
const HALT   = 0b0000, NOP    = 0b0001, RRMOVQ = 0b0010, IRMOVQ = 0b0011;
const RMMOVQ = 0b0100, MRMOVQ = 0b0101, OPQ    = 0b0110, JXX    = 0b0111;
const CALL   = 0b1000, RET    = 0b1001, PUSHQ  = 0b1010, POPQ   = 0b1011;
const CMOVXX = RRMOVQ;

# ifuns; see figure 4.3
const ALWAYS = 0b0000, LE   = 0b0001, LT   = 0b0010, EQ   = 0b0011;
const NE     = 0b0100, GE   = 0b0101, GT   = 0b0110;
const ADDQ   = 0b0000, SUBQ = 0b0001, ANDQ = 0b0010, XORQ = 0b0011;

### fixed-functionality inputs (things you should assign to in your HCL)

wire Stat:3;              # should be one of the STAT_... constants
wire pc:64;               # put the address of the next instruction into this

wire reg_srcA:4, reg_srcB:4;         # use to pick which program registers to read from
wire reg_dstE:4, reg_dstM:4;         # use to pick which program registers to write to
wire reg_inputE:64, reg_inputM:64;   # use to provide values to write to program registers

wire mem_writebit:1, mem_readbit:1;  # set at most one of these two to 1 to access memory
wire mem_addr:64;                    # if accessing memory, put the address accessed here
wire mem_input:64;                   # if writing to memory, put the value to write here

### fixed-functionality outputs (things you should use but not assign to)

wire i10bytes:80;                    # output value of instruction read; linked to pc
wire reg_outputA:64, reg_outputB:64; # values from registers; linked to reg_srcA and reg_srcB
wire mem_output:64;                  # value read from memory; linked to mem_readbit and mem_addr

####################### end builtin signals ###########################

Because these are provided, they cannot be redeclared in your files but can (and should) be used to interact with the register file, memory system, and to tell the simulator when to halt your program.

View 2: provided components

This section and the preceding section contain the same information, but presented in a different way.

There are several built-in components; they have built-in names and you have to use those names to interact with them. We do not use the same names as the textbook in part because the book sometimes uses the same name for 2+ things. For example, the book uses valM to be both the output of data memory and one of the write-inputs to the register file. The block above lists all of our names; we repeat them below by component.

Instruction Memory
The input to the instruction memory is called pc. pc is a 64-bit number and is treated as containing a memory address from which to read an instruction.

The output of the instruction memory is called i10bytes. i10bytes is an 80-bit number and contains the little-endian value read from memory at the address specified in pc.

Typically we want to split out parts of i10bytes. We do this with the “slice” operator:

wire icode:4;
icode = i10bytes[4..8];

The bits are numbered from 0 (least-significant byte) to 79 (most significant byte). i10bytes[4..8] selects bits 4, 5, 6, and 7 and returns them as a 4-bit number.

The book does not refer to i10bytes by any name, and uses pc to mean several things, including what we are using it to mean here.

Data Memory
The data memory has four inputs and one output.

Inputs:

mem_readbit
A 1-bit value. 0 means don’t read, 1 means do read. It is an error for both mem_readbit and mem_writebit to be set to 1 at the same time.
mem_writebit
A 1-bit value. 0 means don’t write, 1 means do write. It is an error for both mem_readbit and mem_writebit to be set to 1 at the same time.
mem_addr
A 64-bit value which should contain a memory address if either mem_readbit or mem_writebit is 1. It is the address at which memory is read or written.
mem_input
A 64-bit value which will be written (in little-endian) to mem_addr if and only if mem_writebit is 1.

Outputs:

mem_output
A 64-bit value read (in little-endian) from mem_addr if mem_readbit was 1; or the number 0x0000000000000000 if mem_readbit was 0.

The book refers to mem_addr as just “addr”, mem_input as “data”, and mem_output as “valM”. Note that they (confusingly) also use “valM” as the name of an input to the Register File.

Register File
The register file has six inputs and two outputs. These represent two “read ports” (called A and B to match the book’s naming) and two “write ports” (called E and M to match the book’s naming).

Read Ports:

Inputs reg_srcA and reg_srcB
4-bit inputs containing a register number to read from.
Outputs reg_outputA and reg_outputB
64-bit values containing the contents of the registers named in reg_srcA and reg_srcB, respectively. Thus, if reg_srcA is REG_RSP then reg_outputA will be the value stored in %rsp.

If a source was REG_NONE, the corresponding output will be the number 0x0000000000000000.

Write Ports:

Inputs reg_dstE and reg_dstM
4-bit inputs containing a register number to write to. REG_NONE means “don’t write”.
Inputs reg_inputE and reg_inputM
64-bit values to be stored in the registers named in reg_dstE and reg_dstM, respectively. Thus, if reg_dstE is REG_RSP then the value from reg_inputE will be the stored into %rsp.

These names are related to the names in the book as follows:

  • The book does not have reg_ prefixes; we added them because students were getting confused which signals were attached to what.
  • The book calls both inputX and outputX just “valX”; we distinguish between inputs and outputs for clarity.

Note that the book (confusingly) uses “valM” as both the name of an input to the Register File and the name of an output from the Data Memory. It also uses “valE” as both the name of an input to the Register File and the name of an output from the ALU.

Status
The status block has a single input named Stat. It should be set to one of the named constants beginning STAT_. Notably, Stat = STAT_AOK means “keep running;” any other value means “stop running” (possibly with an error).

The book also calls this Stat.

ALU, Condition Codes, and register to store the PC
The book has several components “built-in” (shown in blue in their pictures) that we’ll let you implement yourself. These include the ALU, the condition codes, and the register that stores the current program counter.

Supplied testing scripts

We supply scripts to test submissions for each of the HCL assignments. These are accessed using make test-pc, make test-irrr, make test-seqlab, and so on (depending on the assignment). These tests work by comparing expected output in the testdata directory to actual output from your HCLRS submission. They do this by running the Python 3 script testing_tool.py.

When the supplied output and the actual output disagree, the testing tool will show the differences using a format which deserves some explanation. For example, here’s part of the output from running a broken version of irrr.hcl with ‘make test-irrr’:

      output did not match for jmp.yo:
*** expected output for jmp.yo
--- your output for jmp.yo
***************
*** 23,29 ****
  +-----------------------------------------------------------------------+
  pc = 0xa; loaded [70 1e 00 00 00 00 00 00 00 : jmp 0x1e]
  +------------------- between cycles    2 and    3 ----------------------+
! | RAX:              bad   RCX:                0   RDX:                0 |
  | RBX:                0   RSP:                0   RBP:                0 |
  | RSI:                0   RDI:                0   R8:                 0 |
  | R9:                 0   R10:                0   R11:                0 |
--- 23,29 ----
  +-----------------------------------------------------------------------+
  pc = 0xa; loaded [70 1e 00 00 00 00 00 00 00 : jmp 0x1e]
  +------------------- between cycles    2 and    3 ----------------------+
! | RAX:                0   RCX:                0   RDX:                0 |
  | RBX:                0   RSP:                0   RBP:                0 |
  | RSI:                0   RDI:                0   R8:                 0 |
  | R9:                 0   R10:                0   R11:                0 |

In this case, there are two excerpts of HCLRS output. One is marked with *s. As indicated by the line *** expected output for jmp.yo, these are excerpts from the reference files. Another is marked with -s. These are excerpts from my broken program’s output.

The header line *** 23,29 ***. Indicates the following output is from lines 23-39 of the expected output. Similarly, the header line --- 23,29 --- means the following output is from lines 23-29 of the broken’s program’s output. (HCLRS is run with -t to get each of these outputs, to not include the names and values of register banks you have defined, because they may differ between implementations.)

Within the output, some lines are marked with !s. These lines are the ones which differ between the two outputs. In this case, you can see the line with the values of the registers RAX, RCX, and RDX differed, because the value of RAX differed.

Generally, the testing scripts are configured to run simpler tests before more complicated tests, so we recommend looking at the first difference output before later ones.

Sending output to a file

Often HCLRS will produce a lot of output, and it would be better to write it to a file and open it up in a text editor later. You can use the shell’s output redirection features to do this, like:

      ./hclrs -d file.hcl file.yo >output.txt 2>&1

Then open output.txt in a text editor. (>output.txt sends normal output to the file output.txt instead of the normal output file. 2>&1 means to redirect error output where normal output is going.) This redirection support is a shell feature that works with any command, not just hclrs.

Less-common Options

Running code the hard way

If you don’t have make (e.g., because you are running in Windows), then you will need to compile things manually:

  1. go to the tools directory

  2. run your C compiler to make yas and yis, as e.g.

    gcc -O2 yas.c isa.c yas-grammar.c -o yas
gcc -O2 yis.c isa.c               -o yis

  3. choose the appropriate precompiled copy of HCLRS from the .tar.gz and .zip archives in the tools directory for your When you find the archive, extract the hclrs executable from it. (On OS X and Linux, it will not have any extension.)

    If you do not find a precompiled version of HCLRS for your platform, first install rustup as described on this website. Then, install git. Then run:

    git clone -b cs3330-current https://github.com/woggle/hclrs.git ./tools/hclrs-src

    to extract the HCLRS source code to tools/hclrs-src. Go to that directory, then run:

    cargo build --release

    Then copy the executable target/release/hclrs to the base directory.

HCLRS changelog (recent only)

License and Copyright

yis, yas, and most of the provided .ys files are from

Y86 Tools (Student Distribution)
Copyright (c) 2002, 2010, 2015 R. Bryant and D. O’Hallaron, All rights reserved. May not be used, modified, or copied without permission.

Permission to distribute unmodified versions of these sources was obtained by Luther Tychonievich from the authors in July 2014 and renewed August 2015. That permission does not extend to you; you may obtain them, but not redistribute them without first obtaining permission from the copyright holders.

The provided .yo files were generated by yas from the .ys files and I believe that they fall under the same copyright and distribution rules.

hclrs is original to this package

Copyright (c) 2017 Charles Reiss Released into the public domain.
Attribution is appreciated but not required.

hclrs makes use of the lalrpop parser library by Niko Matsaksi, which is available undr the MIT and Apache 2.0 licenses.

hclrs makes use of the extprim math library by kennytm, which is available under the MIT and Apache 2.0 licenses.

hclrs makes use of various parts of the Rust standard library, which is available under the MIT and Apache 2.0 licenses