A C++ front end and back end for ILOC, the assembly like intermediate language used in Rice's COMP 412 compiler course: it scans, parses, renames registers, allocates registers, and schedules instructions.
Full project report: ILOC compiler report (PDF)
ILOC programs arrive as plain text, so a compiler must first turn characters into tokens, catch lexical and syntactic errors with useful line numbers, and build an intermediate representation before any optimization can happen. On top of that, source code uses an unbounded supply of register names while real machines offer only a few physical registers, and naive instruction order leaves long latency operations (loads, stores, multiplies) stalling the pipeline.
The project is split into two programs that share the same scanner and parser. main.cpp builds the front end binary 412fe: a state machine scanner produces a token stream and reports lexical errors, and the parser checks each instruction against its grammar, reports semantic errors, and emits a human readable intermediate representation. It also renames source registers to virtual registers and performs bottom up register allocation for a target machine with k physical registers (k between 3 and 64). schedule.cpp builds the schedule binary, which constructs a dependence graph over the IR, computes priorities from instruction latencies (longest path to a root), and performs list scheduling that pairs independent instructions so two can issue per cycle. As the project report explains, memory dependences among loads, stores, and outputs are resolved by propagating constants from loadI instructions and emulating memory with a hash map, and false dependence edges through unknown addresses are pruned with a second pass of test value propagation. The ready list is a priority ordered set and the active list is a multiset keyed by finish cycle. Heuristics favor loads over stores on the first functional unit (a store issued before a dependent load costs a 5 cycle latency edge instead of 1), give multiplies top priority on the second unit, and defer outputs, which never unlock other instructions.
The result is a compact, self contained pipeline that demonstrates the core phases of a compiler back end on real ILOC input: precise error reporting during scanning and parsing, correct register allocation under tight register limits, and a reordered schedule that hides operation latency by overlapping independent work. The report's measurements show the scheduler produced correct code on all 24 test blocks and matched or beat the reference scheduler's cycle counts on most of them, with up to 25 percent fewer cycles on the best blocks, doing especially well when memory addresses are unknown in advance. Its run time scales linearly with block size, scheduling a 128,000 line block in about 1.2 seconds after the dependence edge lists were replaced with hash maps. Because each phase is exposed through a command line flag, every stage (tokens, parse result, IR, renamed registers, allocated code, final schedule) can be inspected on its own.
Build the instruction scheduler with the makefile (compiles schedule.cpp with g++ and C++11):
make
./schedule file.i
./schedule -h prints:
Optional flags:
-h prints this message
<file_name> prints optimized reordered ILOC program
Build the scanner and parser front end from main.cpp:
g++ -std=c++11 -O3 -o 412fe main.cpp
./412fe -h
./412fe -h prints:
Optional flags:
-h prints this message
-x renaming source registers to virtual registers
k k - register allocation
-s prints tokens in token stream
-p invokes parser and reports on success or failure
-r prints human readable version of parser's IR
Example invocations, where file.i is an ILOC source file:
./412fe -s file.i # token stream
./412fe -x file.i # IR with virtual registers
./412fe 8 file.i # allocate to 8 physical registers
./schedule file.i # reordered, latency aware schedule
Run make clean to remove the built scheduler.