Starting from:
$24.99
Lab 06 Control Flow Graphs
Lab 06
Control Flow Graphs
Control flow graphs (CFGs) are flow diagrams for computer programs. We have actually been writing basic blocks the whole time so far without formally describing them. From Wikipedia: “... a basic block is a straight-line code sequence with no branches in except to the entry and no branches out except at the exit. Thisrestrictedformmakesabasicblockhighlyamenabletoanalysis. Compilersusuallydecomposeprograms into their basic blocks as a first step in the analysis process. Basic blocks form the vertices or nodes in a control flow graph.” With MIPS instructions, when we encounter a beq instruction for example, we either jump to the label or go to the next instruction. In this lab, we are going to use branch/jump pairs to force explicit flow control. In the event that we don’t follow our branch condition, we will jump to another basic block. Therefore, the following code will arrive at either the next label or the after label.
bne $s0, $t0, next j after
This is very helpful when dealing with loops. Loops have three primary basic blocks: the loop header, the latch, and then one or more basic blocks composing the loop body. The loop header determines whether or not to continue the loop body (for example, whether i < 5 evaluates to true). The latch is where the iteratorvariableismodified(e.g., i++). Insidethebodyweperformourcomputationincludingotherlooping constructs. The loop body performs some operations and jumps directly to the latch block; the latch block modifies the loop variable and jumps directly to the loop header. Construct a program following the CFG on the following page that requests an integer n and outputs 0, 1, ... n-1 on its own line.
MIPS Triangle (part 1) In Lab 01 we had a problem that asks you to program a triangle: What is n? 4 * ** *** **** Draw the CFG corresponding to this program using the guidelines given above and the example CFG.
MIPS Triangle (part 2) Implement this following the CFG you constructed from the previous checkpoint.
1
Figure 1: CFG
Control Flow Graphs
Control flow graphs (CFGs) are flow diagrams for computer programs. We have actually been writing basic blocks the whole time so far without formally describing them. From Wikipedia: “... a basic block is a straight-line code sequence with no branches in except to the entry and no branches out except at the exit. Thisrestrictedformmakesabasicblockhighlyamenabletoanalysis. Compilersusuallydecomposeprograms into their basic blocks as a first step in the analysis process. Basic blocks form the vertices or nodes in a control flow graph.” With MIPS instructions, when we encounter a beq instruction for example, we either jump to the label or go to the next instruction. In this lab, we are going to use branch/jump pairs to force explicit flow control. In the event that we don’t follow our branch condition, we will jump to another basic block. Therefore, the following code will arrive at either the next label or the after label.
bne $s0, $t0, next j after
This is very helpful when dealing with loops. Loops have three primary basic blocks: the loop header, the latch, and then one or more basic blocks composing the loop body. The loop header determines whether or not to continue the loop body (for example, whether i < 5 evaluates to true). The latch is where the iteratorvariableismodified(e.g., i++). Insidethebodyweperformourcomputationincludingotherlooping constructs. The loop body performs some operations and jumps directly to the latch block; the latch block modifies the loop variable and jumps directly to the loop header. Construct a program following the CFG on the following page that requests an integer n and outputs 0, 1, ... n-1 on its own line.
MIPS Triangle (part 1) In Lab 01 we had a problem that asks you to program a triangle: What is n? 4 * ** *** **** Draw the CFG corresponding to this program using the guidelines given above and the example CFG.
MIPS Triangle (part 2) Implement this following the CFG you constructed from the previous checkpoint.
1
Figure 1: CFG
1 file (34.4KB)
