Compilers: Program 5

IR-code generation

Due: Friday, May 8 at 5pm

The goal of this programming assignment is to complete intermediate code generation from Jest abstract syntax so that it can be output as C-compilable C_ (“C flat”).


Download the starter project, unzip it and familiarize yourself with the files associated with this project:

app/Main.hs             invokes translate, irToCflat; messages to stderr
c-support/              new folder for C_ standard library (.h and .c)
examples/               focus on a few larger examples
src/Ast.hs              minor changes (mostly to support push and pop)
src/AstToIr.hs          new (where all your coding should take place)
src/AstUnparse.hs       minor change  (mostly to support push and pop)
src/BuildAst.hs         minor changes (")
src/Ir.hs               new
src/IrState.hs          new
src/IrToCflat.hs        new
src/JestBasis.hs        small addition of basis objects/functions
src/Parse.hs            support for push and pop
src/ParseTree.hs        added Push and Pop
src/Region.hs           as before
src/Scan.x              minor changes (mostly to support push and pop)
src/SemTy.hs            as before
src/Tag.hs              as before
src/Token.hs            added Push and Pop tokens
src/TypeEnvToString.hs  as before
src/TypeCheck.hs        minor changes (mostly to support push and pop)
src/TypeState.hs        as before

Examine the supplied code, in particular, the modules Ir, IrState, IrToCflat and AstToIr. You should only modify the last of those four.

Try building and running the project. As it stands, it works on a fair amount of abstract syntax. In particular, it can handle while loops and functions but only for simple assignments that use simple expressions. Here is an example of what can be run out of the box:

% stack run ir-gen
let s = 0;
let i = 0;
while (i < 5) {
    s += i;

Source code scanned and parsed successfully.
AST built without error.
AST typechecked.
AST translated to IR.
IR output as C_

#include "cflat_stdlib.c"

cf_int t0, t1;

int main() {
    cf_int t2, t3, t4, t5, t6;
    t2 = 0;
    t0 = 0;
    t1 = 0;
    if (t1 >= 5) goto looper_end_3;
    t0 = t0 + t1;
    t1 = t1 + 1;
    goto looper_start_2;
    t3 = (cf_int)(*(((cf_addr)_stdlib_console) + 0));
    t4 = (cf_int)(*(((cf_addr)_stdlib_Jest) + 2));
    t5 = ((cf_fun)t4)(t0);
    t6 = ((cf_fun)t3)(t5);
    return t2;

What to do

  1. Implement translation for do-while loops. They are very similar to while loops, though the order (of the test relative to the body) matters and the branch statements have different destinations.

  2. Modify binary operations on integer operands so that they “flatten” their translations when necessary. The idea is that a binary expression in IR should be on two atomic expressions; otherwise or more new move statements may need to be inserted. This is much easier than it sounds: use trAtomExp or trSimpleExp (defined within AstToIr).

  3. Explain (in comments at top of your file): Why do we not support translation of floating-point expressions?

  4. Modify assignment statements so that they follow a similar rule as binary expressions. In this case, at most one of the left-hand side or the right-hand side can be simple, the other side must be atomic.

  5. Implement the rest of string-typed binary operations.

  6. Explain (in comments at top of your file): Why do we not need separate library functions that correspond to “not equal” and “less than or equal to” for strings?

  7. Implement translation for unary minus.

  8. Implement translation for if statements. Loosely follow the model for while. Remember that it is easier to have the branch jump to the “then” block and have the code “fall through” to the else block. Both blocks need to “merge” at the conclusion of the conditional statement.

  9. Implement translation for Boolean connectives (&& and ||). This is slightly trickier than might first appear because they are short circuiting: the second operand should only be evaluated if need be.

  10. Explain (in comments at top of your file): Why would it be incorrect to implement && and || in the same way that arithmetic operations are implemented?

  11. Implement translation for array-subscript expressions.

  12. Explain (in comments at top of your file): Why did I modify the syntax of Jest so that push and pop are language constructs rather than standard methods or library functions?

  13. Implement record constructions.

  14. Explain (in comments at top of your file): Why do we need type information at this stage of the compiler in order to translate record constructions? `

Submitting your work

Submit by replying to the email officially announcing the assignment and attaching just the one file, AstToIr.hs. Any questions and explanation should be included as part of your comments at the top of that file.

The body of your email should be left blank. Any specifics about your assignment you think I should require (for example, known bugs or what you did not have time to complete) should be included in proofread comments near the top of your file.