Lab 5
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
Lab_BasicBlock Assignment
Main Idea
Tips
Questions