程序代写代做代考 Lab 5

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