COL728 : Compiler Design : Labs (programming assignments)

All lab assignments are to be done in groups of at most two people.

Lab 1 : Studying the C parser

Due date

5h February 2018, Monday

Weight

4 marks

Submission Instructions

Combine your reports on the lexical analyzer code and the parser code into one report, and email your combined report to the TA and the Instructor (see administrivia page for contact details).

Lab instructions

  1. Ensure that your environment allows cloning of Github repositories
  2. Clone the GIT repository : https://github.com/iitd-plos/cc
  3. In cc directory, type make to build the cc program
  4. The cc program checks if an input C program is correctly formed (as per the C grammar). The C program should not have any pre-processor directives, and is assumed to have been pre-processed already. Try compiling the hello_world program: Try changing the hello_world.c program to valid and invalid C programs, and check if the compilation succeeds or reports a syntax error appropriately.
  5. Study the generated lexer in file c.lex.cpp, and write a short report (1-5 pages) on the logic of the code produced through the lexical analyser generator. In particular, we are interested in the logic of the function represented by YY_DECL (representing the yylex() function). Keep your report as brief as possible, but do not miss out any interesting fact about the generated code or logic. Your report should reflect your understanding of the logic of the generated lexical analyzer.
  6. Study the generated parser in file c.tab.cpp, and write a short report (1-5 pages) on the logic of the code produced through the parser generator. In particular, we are interested in the logic of the yyparse() function. Keep your report as brief as possible, but do not miss out any interesting fact about the generated code or logic. Your report should reflect your understanding of the logic of the generated parser.
Optional assignment

Lab 2 : Code Generation

Due date

22nd March 2018, Monday.

Weight

12 marks

Submission Instructions

  1. Cleanup the cc directory, so that it only contains the source files.
  2. Compress this directory to EntryNumber.zip file and submit it on course page on moodle.

Lab Instructions

  1. Modify the cc program to emit (unoptimized) LLVM bitcode for the input C program. Start with supporting the most basic C features (e.g., those that can compile the hello_world.c program), and then incrementally add more C features to the LLVM code generator. Please see the references page for some good resources on generating LLVM bitcode. The generated LLVM bitcode should run as expected using the LLVM interpreter lli.
  2. You will be evaluated on the correctness and elegance of your design/code, and on the generality / extensiveness of your handling of different C constructs. You do not need to handle all C constructs, but we would like you to go as far as you can. The elegance of your design is likely to make your code simpler and easier to understand and debug, and is likely to allow you to make your implementation more general/extensive in the same amount of limited time.

Some hints if you are unable to start

  1. You may want to start with creating a syntax tree for a simplified
  2. grammer.
  3. Remove some rules and keep only small number like function declaration.
  4. Define a header file in which you can define structure of nodes for AST.
  5. In c.y file, add C code for returning tree of your defined type along with grammer rules. You can put C code inside braces ({}) in front of grammer rules.
  6. In each class, defining structureof node for your AST, include a function which will generate llvm code for that node. You can take some help from this link for getting started for code generation.

Lab 3 : Local Optimizations at the time of parsing

Due date

6th April 2018, Friday

Weight

4 marks

Submission Instructions

Submit your report and cleaned-up code on moodle.

Lab instructions

  1. Extend your code generator to support some local optimizations, like local constant-folding, local dead-code removal, etc.
  2. Here is an example of a trivial constant propagation optimization.
  3. bool x, y;
    ...
    x = true | y;
    // this last instruction can be changed (at the time of parsing) to
    x = true;

Lab 4 : Implementing an optimization pass for LLVM

Due date

2nd May 2018, Monday

Weight

10 marks

Submission Instructions

Submit your cleaned-up code and report on moodle.

Lab instructions

  1. Use LLVM optimization passes to optimize the generated code.
  2. Implement a custom LLVM optimization pass for common-subexpression elimination.