Clone the repository using
git clone https://github.com/Joel-Hecht/compilers-class-project
The compiler is written in Janet - you can install janet on the official website, or install to your ~/.local/bin directory by using
make janet
Then, assuming ~/.local/bin is in your path, you can build by running:
make
from the project directory. The resulting binary can be found at build/comp
The version which meets all requirements for Milestone 4 can be found in the milestone-4 branch.
Milestone 4 adds yield statements, where a function including a line of the form yield <expression> will instead return an object that acts as a generator, instead of the specified return value. The type of the object returned by this class will be called a generate<method-name><class-name>, and can be iterated and accessed by using the MoveNext() method (which returns 1 if there was a new value, and 0 otherwise), and CurrentValue() (which returns the value that the last call to MoveNext() accessed).
For example, a method m() returning an integer in a class FOO that contains a yield statement would return an object of class generatemFOO. The currentValue() method of such a class would then return an integer, since that was the return type of the original method.
I have also included error handling in the case of any id in the source program being named yeild instead of yield, as I have had the misfortune of doing many times in my variable names during development. This alone has made me regret my decision not to use a statically typed language for this project.
Code for milestone 4 can mainly be found in src/yielder.janet, although many modifications were made to ASTClasses.janet and parser.janet to allow yield statements (and returns from yielding methods) to be converted into their AST equivalents in the AST stage. Also modified were CFGClasses.janet and CFG.janet, which enable the branching required at the beginning of a MoveNext() to resume from the current state (i.e. we need to save the basic block to jump to, which obviously cannot be done at the AST stage).
An example program using the new yield functionality is provided in ex/yield.441, which switches control between the main routine (which prints '5') and the generator, which prints a bunch of other numbers.
The version which meets all requirements for Milestone 3 can be found in the milestone-3 branch.
Milestone 3 adds a type checker and removes integer tagging, which signifigantly speeds up the program run.
The improved functionality can be demonstrated by running ex/nontrivialprogram.441, which has an analog in the milestone-2 branch. Signifigantly fewer computations are needed to reach the end result.
The version which meets all requirements for Milestone 2 can be found in the milestone-2 branch.
Milestone 2 adds functionality for dominator-based SSA. Use the flag -oldSSA to use the outdated SSA from milestone 1 (the default behavior is the new SSA).
The improved functionality can be demonstrated when compiling the ex/phi-loop.441. Compiling using the -oldSSA flag (./build/comp -oldSSA ex/phi-loop.441) yields an IR with 3 phi functions, while compiling without the flag yeilds an IR with none. This is a result of a single assignment to the variable being at the top of main, meaning it dominates everything (and since it is the only assignment, no phi functions are needed).
Milestone 2 also adds functionality for local value numbering. Use the flag -no-vn to disable value numbering.
The improved functionality can be demonstated in vn-comparisons.441. Compiling using the -no-vn flag yields more complex instructions on 11 lines, compared to when compiled using value numbering. This is a result of some algebraic identities I implemented, which cut out zero addition, zero multiplication, and identity multiplication. Additionally, the compiler realizes that the two comparisons are the same, and is able to set one equal to the previously calculated value.
Right now, I am not removing trivial instructions (I didn't think I needed to given the assignment instructions). Even though it would be possible with SSA, I figured it could be a huge pain with tracking a removed variable across phi functions, so I didn't bother.
The version which meets all requirements for Milestone 1 can be found in the milestone-1 branch.
For Milestone 1, I implemented the peephole optimization which removed tag checks for this in methods. This seems to be working fine, and output from the optimization runs in ir441 in all testing I did.
Code for this optimization can be found in src/peephole.janet.
In this directory are several programs which this optimization alters.
- The first example,
ex/p.441, is the example provided in the spec. The optimization removes the tag check forthis, but keeps the tag check for the field. - The second example,
ex/p2.441, is a more robust example, and shows that the blocks will get combined in the middle of a bunch of tag checks/tag arithmetic - I wanted to show an example where phi functions would need to be merged, since I tried to implement this functionality, but I was unable to contrive one (I think it may not be possible with the given spec due to the way we are implementing field/method tag checks).