基本块的组成部分有哪些？结合MIPS代码实例解析相关定义

基本块的核心定义 #

首先引用教材里的标准定义：

除末尾外无分支指令，除开头外无分支目标或分支标签的指令序列。

一个完整的基本块通常包含三个核心部分：

• 入口：基本块的第一条指令，只能是分支跳转的目标、程序的起始执行指令，或者紧接在其他分支/跳转指令之后的第一条指令
• 主体指令序列：中间连续的非跳转指令，执行过程中不会被外部跳转切入，也不会主动跳出到其他位置
• 出口：基本块的最后一条指令，只能是分支、跳转、程序终止类指令，或者是下一个基本块入口的前一条指令

给定MIPS代码的拆分解析 #

你提到的代码看起来不符合定义是完全正常的，因为整段while循环对应的MIPS代码本身就不是一个单一基本块，而是由多个基本块组成的控制流结构，我们先贴出完整代码：
对应C代码：

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

对应MIPS代码：

LOOP:   sll     $t1, $s3, 2
        add     $t1, $t1, $s6
        lw      $t0, 0($t1)
        bne     $t0, $s5, EXIT
        addi    $s3, $s3, 1
        j       LOOP
EXIT:

先提取你问的几个核心元素：

• 分支指令：包含两条，分别是条件分支bne $t0, $s5, EXIT和无条件跳转j LOOP
• 分支目标：是两个标签对应的位置，LOOP:是j LOOP的跳转目标，EXIT:是bne $t0, $s5, EXIT的跳转目标

我们按照基本块定义拆分后，可以得到3个符合要求的基本块：

1. 基本块1（循环条件判断块）

LOOP:   sll     $t1, $s3, 2
        add     $t1, $t1, $s6
        lw      $t0, 0($t1)
        bne     $t0, $s5, EXIT

入口为LOOP:标签对应的sll指令，出口为末尾的bne分支指令，符合定义：开头是分支目标，中间无分支，仅末尾有分支。
2. 基本块2（循环体执行块）

addi    $s3, $s3, 1
        j       LOOP

入口为bne不跳转时的下一条addi指令，出口为末尾的j跳转指令，符合定义。
3. 基本块3（循环出口块）

EXIT:

入口为EXIT:标签位置，属于空的出口基本块，符合定义。

基本块的正/反例参考 #

符合定义的示例 #

示例1：纯顺序运算块

add $t0, $t1, $t2
sub $t3, $t0, $t4
mul $t5, $t3, $t6

无任何分支指令和标签，入口是第一条add指令，出口是最后一条mul指令，是最典型的基本块。

示例2：末尾带分支的块

FUNC_ENTRY: lw $s0, 0($sp)
            addi $s0, $s0, 1
            sw $s0, 0($sp)
            blt $s0, $s1, NEXT_LABEL

开头是分支目标标签FUNC_ENTRY，中间无分支，仅末尾有条件分支指令，符合定义。

不符合定义的反例 #

反例1：中间存在分支指令

add $t0, $t1, $t2
beq $t0, $zero, L1
sub $t3, $t0, $t4
L1: mul $t5, $t3, $t6

不能作为单一基本块，因为分支指令beq出现在序列中间，不在末尾，需要拆分为3个独立基本块。

反例2：中间存在分支目标

add $t0, $t1, $t2
L2: sub $t3, $t0, $t4
mul $t5, $t3, $t6

不能作为单一基本块，因为分支目标标签L2出现在序列中间，不是基本块的开头。

内容的提问来源于stack exchange，提问作者Display name