tiger-rs

Following along with Andrew Appel's Modern Compiler Implementation in ML.

Progress

• Lexing

Handwritten lexer.

• Parsing

Using LALRPOP as an LR(1) parser generator.

• Type checking

• IR translation

• Abstract assembly generation

• Register allocation

• Optimization

TODO

• Lexing

  • Add pretty-printing for tokens
  • Decouple lexer from parser
  • Integrate lexing phase into CLI
  • Implement string unescaping
  • Handle MIN_INT - might have to store literal ints as strings?
  • Write test cases for lexing

• Parsing

  • Implement or find global symbol table library (EDIT: see sym)
  • Convert all allocated String fields into cached symbols
  • Implement to_span functions for AST nodes for better errors
  • Add more span fields to AST where necessary (e.g. saving function name in Call node)

• Type checking

  • Write test cases
  • Check for variable mutability
  • Check for uniqueness of type and function names within a mutually recursive group
  • Check for invalid type cycles
  • Upgrade TypeError variants with more information
  • Use codespan::Label to display better errors
  • Possibly use macros to clean up repeated code, or reduce the number of clone calls

• IR translation

  • Implement Appel's Tree enum
  • Implement AST translation functions
  • Attach AST translation to type checking phase
  • Implement canonization
  • Implement interpreter for testing purposes
  • Write test cases for interpreted IR
  • Make sure commuting logic is sound (i.e. pure vs. impure expressions)
  • Implement constant folding
  • Implement finding escaping variables
  • Implement static link traversal
  • Construct control flow graph from canonized IR
  • Reorder IR using control flow graph to remove unnecessary jumps

• Abstract assembly generation

  • Design instruction types for assembly
  • Implement AT&T and Intel syntax in separate traits for easy swapping
  • Implement tiling using maximal munch
  • Implement trivial register allocation
  • Figure out how to write a C runtime for Tiger
  • Clean up command-line interface
  • Organize compiler passes into distinct phases (maybe use a Phase trait?)
  • Write assembly test suite

• Register allocation

  • Research different allocation algorithms
  • Implement one

• Optimization

  • Implement dataflow analysis framework(s) (IR level? Assembly level? Basic blocks or individual statements?)
  • Research different optimizations (e.g. constant propagation, dead code elimination, common subexpression elimination)
  • Write benchmark Tiger programs

Deviations

• Allow comparison operators to associate (e.g. (a = b = c) evaluates as ((a = b) = c))
• Allow assignment to for loop index variable (e.g. for i := 0 to 10 do i := i + 1)
• Implement modulo operator (%)
• Rename print runtime function to prints; implement printi function to print integers