COL729 Lab 2 : Lazy Code Motion

Due date - 23:55, 14 April 2023

Weight: 50%

Overview

In this lab, you will implement the Lazy Code Motion algorithm (notes, video). You have already implemented the first part of the algorithm (Anticipated Expressions Analysis) in previous lab. You will implement the remaining bits in this lab. If you didn't complete the previous lab, you might want to do that first.

As with previous lab, you will work with the Compilerai framework.

Instructions

Getting Started

1. Follow Getting started of previous lab to complete initial setup.

2. Pull lab 2 specific changes with git pull origin col729_lab2 in superopt-project directory.

   The merging should happen automatically. If it does not and you are unable to resolve the conflicts manually, post a note on teams.

3. The primary places where you need to make changes have been marked with COL729_LAB2 TODO. Search for them using git grep 'COL729_LAB2 TODO'.

Before starting the implementation, you might want to review material from previous lab for a quick recap.

Implementing the algorithm

You will implement the four analyses of Lazy Code Motion algorithm. We will stop short of the last step where the result of the analyses is used for code transformation. The DFA implementation will remain similar to previous lab, however, you must keep the following representational differences between TFGs and CFGs in mind:

• A basic block in a CFG corresponds to an edge in the TFG.
• Instead of separate IN and OUT values, there is only a single value for a PC (or, program point).
• Because we associate program logic with edges and not instructions (e.g., a conditional branch is represented as two edges and not one instruction), we do not need to add empty basic blocks (as in the preprocessing step of the original algorithm).

As before, the classes corresponding to the four analyses have been created for you, along with all the boilerplate code. You just need to supply the core logic in places marked with COL729_LAB2 TODO:

• Anticipated (or Needed) expresssions analysis: include/graph/anticipated_exprs{,_dfa}.h
• Available (or Missing) expresssions analysis: include/graph/missing_exprs{,_dfa}.h
• Earliest expresssions computation: include/graph/earliest_exprs.h
• Postponable expresssions analysis: include/graph/postponable_exprs{,_dfa}.h
• Latest expresssions computation: include/graph/latest_exprs.h
• Used expresssions analysis: include/graph/used_exprs{,_dfa}.h

Running and testing your changes

Once you have filled-in the required code, you need to uncomment the comment block marked with COL729_LAB2_UNCOMMENT_ME to run the four analyses.

The steps for building and running the code remain same as before except the name of test directory which is lab2_test.

Interpreting the results

The results of your analyses will be available in serialized format in the output TFG file. The format for PC bound results remain same as before.

The format for edge bound results refers to an edge instead of a PC. For example:

=Earliest expressions in src.llvm.sum
=earliest expressions at L0%0%1=>Lentry%1%1 in src.llvm.sum
=earliest_exprs begin
=expr
1 : 0 : BV:32
2 : input.src.llvm-%n : BV:32
3 : bvslt(1, 2) : BOOL
=expr
=earliest_exprs end
...
...
...

The above example represents the following information: for the edge from L0%0%1 to Lentry%1%1, the earliest expressions set contains bvslt(0, input.src.llvm-%n).

Requirements

Turn in

• git diff col729_lab2 | gzip > ${your_group_members_entry_nums}.gz
• Submit ${your_group_members_entry_nums}.gz to moodle

NOTE: It is your responsibility to ensure that a sequence of gunzip -c ${your_group_members_entry_nums}.gz | patch -p1, when executed in superopt-project root with HEAD at col728_lab2, produces a tree equivalent to yours.