Lab 5
CMPUT 229
University of Alberta
CMPUT 229 (University of Alberta) Lab 5 1 / 7
Outline
1 Lab BasicBlock Assignment Main Idea
Tips Questions
CMPUT 229 (University of Alberta) Lab 5 2 / 7
Lab BasicBlock Assignment
Main Idea
Lab BasicBlock: The Main Idea
Compute leaders (use your Lab Offsets solution). Compute the basic blocks corresponding to the leaders. Compute the Control Flow Graph for the procedure. Compute the Dominator Set for each basic block.
Allocate memory for: Basic block list
Control Flow Graph list Dominator set list
Adjust stack pointer and put addresses in correct places
CMPUT 229 (University of Alberta) Lab 5 3 / 7
Lab BasicBlock Assignment
Main Idea
Lab BasicBlock: Compute Leaders
The two main options for storing the leaders are:
A list of instruction addresses, where each element is the address of a
leader;
A binary vector where each bit corresponds to an instruction in the program. Bits equal 1 in this vector signal leaders.
CMPUT 229 (University of Alberta) Lab 5 4 / 7
Lab BasicBlock Assignment
Main Idea
Lab BasicBlock: Bit Vector
The best strategy is to implement the binary vector as a separate set of subroutines.
It will be simpler to call a subroutine to set a bit, reset a bit, to AND two vectors, or to OR two vectors.
Even if the subroutine calls make the implementation sligthly less efficient, it will be worth the lower complexity of the code and lower chance of errors.
The CMPUT 229 midterm in Fall 2012 had a question that consisted on the implementation of some of the typical functions to manipulate an arbitrary lenght bit vector.
CMPUT 229 (University of Alberta) Lab 5 5 / 7
Lab BasicBlock Assignment
Tips
Lab BasicBlocks: Tips
The specification states that the value of $sp is changed by getControlFlow
The order of the basic blocks in the list matters.
The order of the Control Flow Graph edges in the list also matters.
Produce and submit test cases early. Everyone will benefit.
Code is provided for you to ¡°pretty print¡± your solutions and compare with test cases.
Do not wait until the last week to start working on this lab.
CMPUT 229 (University of Alberta) Lab 5 6 / 7
Lab BasicBlock Assignment
Questions
Lab 5 Questions?
CMPUT 229 (University of Alberta) Lab 5 7 / 7