Ch4 循环体和条件体的构造与优化

Motivation:

1. 构建 ARM 汇编语言循环和条件体
2. 优化循环体
3. 嵌套条件体和寻址表

1. 构建循环体和条件体

1. if...else 条件体

   我们还是从一个简单的例子开始. 我们考虑构建以下的一个条件体: 如果变量 total 大于 2000, 则将其值减小 100. 使用高级程序设计语言 Python 实现如下:

   1
   2
    if total > 2000:
        total -= 100
   

   条件体执行流程图如下:

   

   一般地, 对于高级程序设计语言, 条件体 if 的基本结构为:

   1
   2
    if condition: 
        action
   

   条件体执行流程图如下:

   

   注:

   在 ARM 汇编语言中, 实现 if 条件体的方式有所不同:

   1. 我们需要使用条件判断指令对特定的条件进行判断.
   2. 随后, 我们需要构造一个条件分支. 注: 一般来说, 在汇编语言中, 条件分支的执行条件是恰好与高级程序语言相反的.

   使用高级程序设计语言实现的 if...else 条件体的一般结构和逻辑流程图如下:

   1
   2
   3
   4
    if condition:
        action
    else:
        alternative
   

   

   然而, 如果我们沿用这样的逻辑, 使用汇编语言实现语句的话, 仍然会得到和预期相反的结果. 汇编语言的 if...else 语句应当如下实现:

   

   依照高级程序设计语言的实现逻辑, 转换为汇编语言的 if...else 循环体实现如下:

   1
   2
   3
   4
   5
            LDR ..., ...    ;loading variables
            CMP ..., ...    ;decide when to branch
            BNE skip ...   ;branch if condition not met
            <operations>    ;'action' operations
    skip    <operations>    ;'alternative' operations
   

2. while 循环体 高级程序设计语言的 while 循环体实现方法如下:

   1
   2
    while condition:
        action
   

   

   依照高级程序设计语言的实现逻辑, 转换为汇编语言的 while 循环体实现方法如下:

   1
   2
   3
   4
   5
    start LDR ..., ...      ;loading variables
          CMP ..., ...      ;decide when to branch
          BGE skip ...; ... ;branch
          <Several data operations>     ;branch when conditions not met
          B     start       ;go back to decide
   

   
   

2. 循环体优化

汇编语言的实现逻辑与特征使得如果我们简单地将高级程序设计语言的循环体/条件体思路套用的话, 将不会得到最高的效率. 为了提高程序运行的效率, 我们需要对循环体进行优化.

优化方式有以下数种:

1. 变换操作顺序

2. 充分利用寄存器

3. 利用运算特性

4. 使用 ARM 的特性, 用条件指令取代分支

优化 for 循环体:

3. 嵌套条件体和寻址表

3.1 嵌套条件体

下面, 我们考虑多个 if...else 条件体的嵌套调用. 首先我们来看一个 Python 下的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def switch(arg):
    mapping = {
        0: "0", 
        2: "2", 
        4: "4"
    }
    print(mapping.get(arg, "?"))

# the code above is equivalent with the following:

def switch(number):
    if number == 0: 
        print("0")
    elif number == 2:
        print("2")
    elif number == 4: 
        print("4")
    else:
        print("?")

下面考虑使用汇编语言实现以上的函数功能. 最简单直接的办法是将变量 number 和三种不同的状况所对应的常量分别进行比较, 并执行相应的函数跳转:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
LDR R0, number

cmp0    CMP R0, #0
        BNE cmp2
        MOV R0, "0"
        SVC 0
        B end

cmp2    CMP R0, #2
        BNE cmp4
        MOV R0, "2"
        SVC 0
        B end

cmp4    CMP R0, #4
        BNE none
        MOV R0, "4"
        SVC 0
        B end

none    MOV R0, "?"
        SVC 0

end     ...
        ...

number DEFW 0

; print("2") == MOV R0, #2; SVC 0

上述的实现方式中有显而易见的重复代码, 且对绝大对数情况而言, 在执行程序时都需要进行多次比对和跳转, 导致程序允许速度缓慢. 一方面, 我们可以将 number 转为 ASCII 码, 将寄存器内容和字符的比对转换为和 ASCII 字符码的比对. 另一方面, 我们可以重构条件分支的判断逻辑, 从而降低程序中分支跳转执行次数的期望值:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ascii_0 EQU 48          ;ASCII code for "0"
LDR R0, number          ;loads the numerical value to R0
ADD R0, R0, ascii_0     ;convert to ascii code

cmp0    CMP R0, #48     ;cmp to ascii "0"
        BEQ print
cmp2    CMP R0, #50     ;cmp to ascii "2"
        BEQ print 
cmp4    CMP R0, #52     ;cmp to ascii "4"
        BEQ print
cmp8    CMP R0, #56     ;cmp to ascii "8"
        BEQ print
        MOV R0, #63     ;default case: set ascii "?"
print   SVC 0
        ...
        ...

number  DEFW 0

我们给出总结: 多重嵌套条件体结构简单易于实现, 且可以基于几乎任何类型的用户输入 (如非数字类型和其余字符) 进行条件判断而无需占用过多寄存器空间; 但不当的实现方式将会导致程序执行过程中分支跳转执行次数的期望值过高, 从而导致程序执行时间过长.

在以上的实现方式中, 我们成功降低了程序中分支跳转执行次数的期望值, 但显然程序中比对寄存器内容次数的期望值仍然很大. 下面, 我们使用寻址表 Address Table 实现一种优化的嵌套条件体:

3.2 寻址表

寻址表的实现方式类似于在第 $7$ 章中所将要介绍的堆栈. 本质上, 寻址表是一列存储有连续内存地址, 并可通过下标访问其存储的内容的列表. 表内每一个元素都存储着指向对应情形下所需要执行的代码的内存地址, 并且每一个元素都对应一个指示不同情况的下标. 在使用寻址表时, 程序将会先基于设定好的规则, 判断用户输入或某个传入的变量来决定当前情形所对应的是预设情况中的哪一种 (即: 需要使用哪一个下标访问寻址表), 并基于对应的下标访问寻址表取得对应的内存地址, 并跳转到那个地址执行该地址所存储的指令.

寻址表的伪代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if (number < 0 ||  number > 4)  B default;
PC = number'th word in the table;

table:  DEFW case0      ;word 0 of table at table+0
        DEFW default    ;word 1 of table at table+4
        DEFW case2      ;word 2 of table at table+8
        DEFW default    ;word 3 of table at table+12
        DEFW case4      ;word 4 of table at table+16

case0: print("0")
        B end;
case2: print("2")
        B end;
case4: print("4")
        B end;
default: print("?")
end

寻址表的 ARM 汇编语言实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
; case part
case0   MOV R0, #'0'
        SVC 0
        B end
case2   MOV R0, #'2'
        SVC 0
        B end
case4   MOV R0, #'4'
        SVC 0
        B end
default MOV R0, #'?'
        SVC 0
        B end
end     ...

; table part
LDR R0, number
CMP R0, #0      ;trap values < 0
BLT default
CMP R0, #4      ;trap values > 4
BGT default

ADR R1, table
LDR PC, [R1, R0, LSL #2]    ;table + (number *4)

table:  DEFW case0      ;word 0 of table at table+0
        DEFW default    ;word 1 of table at table+4
        DEFW case2      ;word 2 of table at table+8
        DEFW default    ;word 3 of table at table+12
        DEFW case4      ;word 4 of table at table+16
        DEFW default    ;word 3 of table at table+20

使用寻址表构造多重条件判断 (嵌套条件体) 的好处在于, 对于不同规模的嵌套条件体, 其嵌套深度 (也就是寻址表的长度) 对程序的执行速度没有显著影响. 但是, 若我们的判断条件局部性较差, 或判断条件为非数字的话, 对寻址表的查表过程就会更加复杂.

除了构造多重条件判断结构外, 寻址表还可用于构造对象, 类, 以及处理对外设的访问问题.

• Previous
  Ch3 编译原理 ARM指令集和数据存储表示法
• Next
  Ch5 编译原理 地址与寻址