Lesson 2: Representing Programs

• discussion
• representing programs
• getting started with Bril
• tasks due September 14

Gist

• How do you represent a program? The classic options:
  • Concrete syntax.
  • Abstract syntax (AST).
  • Instructions.
• We like the instruction representation for its regularity. To do anything useful with it, however, we need to extract higher-level representations.
  • Control flow graph (CFG).
  • Basic blocks.
  • Terminators (jmp and br, here).
  • Derive the algorithm for forming basic blocks.
  • Successors & predecessors.
  • Derive the algorithm for forming a CFG of basic blocks.
• Bril, the Big Red Intermediate Language, is a language invented just for 6120.
  • Philosophy.
    • The canonical representation is JSON. There is a text format, but that's just a detail. (Remember, this class is not about parsing. If you ever find yourself doing something fancy with the text format, stop—that's not your job.)
    • This way, you can use any language you want to work with Bril (and for 6120 work).
    • A consequence is that you can (and should!) start "from scratch" with Bril. Do not attempt to use my garbage Python stuff; write your own!
  • Getting started with working with Bril.
    • The documentation.
    • The git repository.
    • Lots of examples in the tests and benchmarks directories.
      • An extremely simple example: add.json in the canonical representation, or the equivalent text for your human convenience.
    • How to load up and process a Bril program, using Python as an example, but remember that you can use any language you like.
    • Getting started with generating the CFG.
      • Try it yourself!
      • Afterward, if you're curious, check out a completed implementation (with some added fanciness) in the examples directory (see form_blocks.py, cfg.py, and cfg_dot.py).
• Turnt is a tool you might like for testing compiler tools.

Tasks

Your goal is to get familiar with Bril.

• Write a new benchmark.
  • You can write it by hand, use the TypeScript compiler, or generate it some other way.
  • Try running it with brili.
  • Open a pull request to add your new benchmark.
    • Add your code to the the benchmarks directory.
    • Use turnt --save yours.bril to create the test outputs for your new benchmark. (See the Turnt README for details.)
    • Mention it in the docs.
• Write a program to analyze or transform Bril programs in some small way.
  • Pick your favorite programming language—there is no "starter code," so you can start from scratch.
  • Load up a JSON file. You can start with this tiny one!
  • Read the docs.
  • Do something unambitious with it: count the number of add instructions, or add a print instruction before every jump, or whatever. Pick something small and contrived!
• Use Turnt to test your new tool.
• Along the way, you will run into problems! Ask questions on Zulip, and open issues and pull requests to describe or fix problems. For example, even super simple benchmarks you might imagine probably can't be written easily because Bril is too simple. Mention this on Zulip, and consider pitching in to help add features.
• As with all implementation tasks, submit the URL for your source code on CMS.