Although not exactly a backward flow problem (depending on the scheduling technique you employ), code scheduling must be applied after dead code removal in order to get the best results. My sample solution to the dead code elimination is bbdead.tgz.
Code scheduling can be very simple or very complex -- here, the intent is to make it very simple. Of course, "very simple" can also be read as "generating suboptimal code." A small fraction of your grade on the project will correspond to how well your code scheduling technique performs: generating better code will reap a slightly higher grade.
If you're an undergrad, target a VLIW. You should assume that certain operations are not involved in parallel execution, i.e., tuples with opcodes LAB and SEL are output as sequential code. KILL tuples are to be ignored (deleted). Further, your scheduling will operate on each block independently. If you're a grad student, you'll target a pipelined machine.
Oddly enough, both VLIW and pipelined machines have fixed parallelism, hence, you need to have a "null-operation" opcode which can be used to fill slots not usable by the program code. Since the intermediate code does not have a special operation to serve this purpose, you should simply use const(0). Hence, your final parallel code will generally contain a number of useless (i.e., unreferenced) const(0) operations.
Scheduling for a VLIW is simply a matter of packing at most N opcodes into each instruction for parallel execution. The rules for this packing are very simple:
Further note that there is no implicit order within a single VLIW instruction (e.g., the result of placing ld(a) and st(a,x) within the same VLIW instruction is undefined, hence, such placement is illegal). Of course, stores that could store into the same object cannot be scheduled in the same VLIW instruction.
How do you pick a VLIW schedule? That's up to you.
When you output the code, the tuples within each VLIW instruction should be listed on the same line separated by semicolons. In addition to output of the code, your program should output the total number of useful tuples generated and the total number of VLIW instructions. Of course, it is expected that there typically will be fewer VLIW instructions than there are useful tuples.
Scheduling for a pipelined machine depends on knowing the pipeline structure. For this project, that structure is given by the following table:
Opcode | Enqueue Time | Latency | Pipeline |
---|---|---|---|
ADD | 1 | 2 | ADDER |
SUB | 1 | 2 | ADDER |
AND | 1 | 1 | - |
OR | 1 | 1 | - |
XOR | 1 | 1 | - |
GT | 1 | 2 | ADDER |
GE | 1 | 2 | ADDER |
EQ | 1 | 1 | - |
SSL | 1 | 1 | - |
SSR | 1 | 1 | - |
CONST | 1 | 1 | - |
LD | 2 | 4 | FETCH |
LDX | 2 | 4 | FETCH |
ST | 1 | 1 | - |
STX | 1 | 1 | - |
LAB | - | - | - |
SEL | 1 | 1 | - |
KILL | 1 | 1 | - |
Hence, there are two separate (independent) pipelines within the processor. The scheduling rules are simply:
ld(a) ldx(b,x)
The due date for this assignment is 11:59PM April 12, 2021. You may submit as many times as you wish, but only the last submission that you make before the final deadline will be counted toward your course grade.
For each project, you will be submitting a tarball (i.e., a file with the name ending in .tar or .tgz) that contains all things relevant to your work on the project. Minimally, each project tarball includes the source code for the project and a semi-formal "implementors notes" document as a PDF named notes.pdf. It also may include test cases, sample output, a make file, etc., but should not include any files that are built by your Makefile (e.g., no binary executables). Make it very clear in your implementor's notes exactly what each file is.
Submit your tarball below. The file can be either an ordinary .tar file created using tar cvf file.tar yourprojectfiles or a compressed .tgz file file created using tar zcvf file.tgz yourprojectfiles. Be careful about using * as a shorthand in listing yourprojectfiles on the command line, because if the output tar file is listed in the expansion, the result can be an infinite file (which is not ok).