What constitutes the parts of a basic block? (e.g. branches, targets, entry, exit)

user_5390845 0
Viewed 105

The following example is from Computer Organization and Design: the Hardware/Software Interface: Fifth Edition. In the book, the author describes the resulting MIPS code, from compiling the C code, as a "basic block", which they define as

a sequence of instructions without branches, except possibly at the end, and without branch targets or branch labels, except possibly at the beginning.

So, given the following C code and the resulting MIPS code, what part(s) of the MIPS code is the entry, exit, branches, or branch targets? This code seems to not meet the definition because there is a branch statement before the end of the loop. It would help me to understand the definition if someone could provide another example of a basic block, or even better a non-example.

while (save[i] == k)
      i += 1;

LOOP:   sll     $t1, $s3, 2
        add     $t1, $t1, $s6
        lw      $t0, 0($t1)
        bne     $t0, $s5, EXIT
        addi    $s3, $s3, 1
        j       LOOP
EXIT:
mips compiler-optimization structure assembly c
1 Answers

It's easier if you understand what and how are they used for. They are used for control flow analysis.

A basic bloc is a series of instructions that within it the control of the program cannot branch in and cannot branch out. I.e. execution cannot start from the middle of a basic block and once the first instruction is executed all instructions in the basic block are executed.

So this is the control flow chart of your example:

LOOP
 |
 |
 |  +---------+
 +->| Block 1 | <---+
    | ------- |     |
    | sll     |     |
    | add     |     |
    | lw      |     |
    | bne     |     |
    +---------+     |
       |            |
 +-----+            |
 |     |            |              
 |     \/           |
 |  +---------+     |
 |  | Block 2 |     |
 |  | ------- |     |
 |  | addi    |     |
 |  | j       |     |
 |  +---------+     |
 |     |            |
 |     +------------+
 |
 \/
EXIT

Also to note is that in an executable labels don't exist. When an assembly instruction says jump to a label, in binary it will be jump to the address of the instruction under that label.

user_28053050
Related