Arya

第九章 代码优化 note
第九章 代码优化 note[+] 感冒好难受啊,一直拖到了今天才把所有的更新完成[+] 希望我可以顺利的考上我报考...
扫描右侧二维码阅读全文
10
2019/02

第九章 代码优化 note

第九章 代码优化 note

[+] 感冒好难受啊,一直拖到了今天才把所有的更新完成
[+] 希望我可以顺利的考上我报考的大学啊

代码生成器的主要任务

指令选择

  • 选择适当的目标机指令来实现中间表示语句(IR)语句
    例:
    三地址语句:x=y+z
    目标代码
LD R0,y /* 把y的值加载到寄存器R0中 */
ADD R0,R0 , z /* z加到R0上 */
ST x , R0 /* 把R0的值保存到x中 */

这种逐条语句生成目标代码的方法,虽然能生成正确的目标代码,但是常常会生成一些冗余的加载或保存指令,比如,三地址语句序列为

a=b+c

d=a+e

目标代码为

LD R0,b // R0 = b
ADD R0,R0, c // R0 = R0 + c
ST a , R0 // a = R0

LD R0,a // R0 = a
ADD R0,R0,e // R0 = R0 + e
ST d , R0 // d = R0

我们可以看出LD R0,a这条指令是一条冗余的加载指令,因为我们可以从第三条指令看出a的值已经在寄存器R0中了

  • 寄存器分配和指派
    把哪个值放在哪个寄存器中
  • 指令排序
    按照什么顺序来安排指令的执行

一个简单的目标模型

三地址机器模型

  • 加载、保存、运算、跳转等操作
  • 内存按字节寻址
  • n个通用寄存器R0, R1, …, Rn-1
  • 假设所有的运算分量都是整数
  • 指令之间可能有一个标号

目标机器的主要指令

  • 加载指令 LD dst, addr
    LD r, x
    LD r1, r2
  • 保存指令 ST x, r
  • 运算指令 OP dst, src1, src2
  • 无条件跳转指令 BR L
  • 条件跳转指令 Bcond r, L
    例: BLTZ r, L //当寄存器L中的值小于0的时候,控制转向标号为L的指令,否则继续执行下一条指令

寻址模式

  • 变量名a
    例:LD R1 , a
    R1=contents(a)
  • a(r)
    a是一个变量,r是一个寄存器
    例:LD R1 , a(R2)
    R1 = contents ( a + contents(R2) )
  • c(r)
    c是一个整数
    例:LD R1 , 100 (R2)
    R1 = contents (contents(R2) + 100 )
  • r
    在寄存器r的内容所表示的位置上存放的内存位置
    例:LD R1 ,
    R2
    R1 = conents (contents (contents (R2) ) )
  • c(r)
    在寄存器r中内容加上c后所表示的位置上存放的内存位置
    例:LD R1 ,
    100(R2)
    R1 = conents (contents (contents(R2) + 100 ) )
  • c
    例:LD R1 , #100
    R1 = 100

指令选择

所谓指令选择,就是为中间表示语句选择合适的目标指令序列

运算语句的目标代码
三地址语句

x=y-z

对应的目标代码如下

LD R1 , y // R1 = y
LD R2 , z // R2 = z
SUB R1 , R1 , R2 // R1 = R1 - R2
ST x , R1 // x = R1

一个优秀的代码生成算法的目标之一,即,尽可能避免使用用上面的全部四个指令,如果
√ 所需的运算分量已经在寄存器中了
√ 运算结果不需要存放回内存

数组寻址语句的目标代码
三地址语句

b = a[ i ]//a是一个实数数组,每个实数占8个字节

目标代码

LD R1 , i // R1 = i
MUL R1 , R1, 8 // R1=R1 * 8,计算偏移地址
LD R2 , a(R1) // R2=contents ( a + contents(R1) )
ST b , R2 // b = R2

类似的还有给数组元素赋值的语句
三地址语句

a [ j ] = c//a是一个实数数组,每个实数占8个字节

目标代码

LD R1 , c // R1 = c
LD R2 , j // R2 = j
MUL R2 , R2 , 8 // R2 = R2 * 8
ST a(R2) , R1 // contents(a+contents(R2))=R1

指针存取语句的目标代码
三地址语句

x = *p

目标代码

LD R1, p // R1 = p
LD R2, 0 (R1) // R2 = contents ( 0 + contents (R1) )
ST x , R2 // x = R2

对应的赋值语句代码如下

三地址语句

*p = y

目标代码

LD R1 , p // R1 = p
LD R2 , y // R2 = y
ST 0(R1), R2 //contents ( 0 + contents ( R1 ) ) = R2

条件跳转语句的目标代码
三地址语句

if x < y goto L

目标代码

LD R1 , x // R1 = x
LD R2 , y // R2 = y
SUB R1 , R1 , R2 // R1=R1 - R2
BLTZ R1 , M // if R1 < 0 jump to M

M是标号为L的三地址指令所产生的目标代码中的第一个指令的标号

过程调用和返回的目标代码

Image11-1.png

如果在活动记录的存储过程中使用的地址是相对地址,那么我们就可以使用栈式存储分配,但是在栈式存储分配中,只有在运行时刻才能知道过程在活动记录中的位置。该位置通常存放在寄存器SP中

Image11-2.png

此处的caller.recordsize表示调用过程活动记录的大小

寄存器的选择

三地址语句额的目标代码生成
对每个形如x = y op z的三地址指令I,执行如下动作

  • 调用函数getreg( I )来为x、y、z选择寄存器,把这些寄存器称为Rx、Ry、Rz
  • 如果 Ry中存放的不是 y ,则生成指令“LD Ry , y′”。y′是存放y的内存位置之一
  • 类似的,如果 Rz中存放的不是z,生成指令“LD Rz, z′
  • 生成目标指令“OP Rx, Ry, Rz

在代码生成过程中,我们需要一定的数据结构来说明哪些变量的值当前存放在哪些寄存器中;此外,我们还需要知道,一个变量的内存地址中存放的值,是否是该变量的正确值,因为该变量的最新值可能刚在寄存器中计算出来,还未保存回它的内存地址中,为此我们需要定义两种数据结构,分别是寄存器描述符地址描述符

寄存器描述符 ( register descriptor )

  • 记录每个寄存器当前存放的是哪些变量的值

地址描述符 ( address descriptor )

  • 记录运行时每个名字的当前值存放在哪个或哪些位置
  • 该位置可能是寄存器、栈单元、内存地址或者是它们的某个集合
  • 这些信息可以存放在该变量名对应的符号表条目中

另外在基本块的结尾处,我们可能需要一些收尾处理

  • 对于一个在基本块的出口处可能活跃的变量x , 如果它的地址描述符表明它的值没有存放在x的内存位置上, 则生成指令“ST x, R” ( R是在基本块结尾处存放 x值的寄存器 )

管理寄存器和地址描述符
当代码生成算法生成加载、保存和其他指令时,它必须同时更新寄存器和地址描述符

对于指令“LD R , x”

  • 修改R的寄存器描述符,使之只包含x
  • 修改x的地址描述符,把 R 作为新增位置加入到x的位置集合中
  • 从任何不同于x的地址描述符中删除 R

对于指令“OP Rx , Ry , Rz”

  • 修改Rx的寄存器描述符,使之只包含 x
  • 由于x的值已经存放在了Rx中,因此从任何不同于Rx的寄存器描述符中删除 x
  • 修改x的地址描述符,使之只包含位置 Rx
  • 从任何不同于x的地址描述符中删除 Rx

对于指令“ST x , R”

  • 修改x的地址描述符,使之包含自己的内存位置

对于复制语句x=y,如果需要生成加载指令“LD Ry , y′”则

  • 修改 Ry的寄存器描述符,使之只包含 y
  • 修改 y的地址描述符,把Ry作为新增位置加入到 y的位置集合中
  • 从任何不同于y的变量的地址描述符中删除Ry
  • 修改 Ry的寄存器描述符,使之也包含x
  • 修改 x的地址描述符,使之只包含 Ry

代码生成寄存器选择函数getReg的设计

Image11-3.png

Image11-4.png

寄存器Rx的选择

比如对于x = y op z 选择方法与Ry类似,区别之处在于

  • 因为x的一个新值正在被计算,因此只存放了x的值的寄存器对Rx来说总是可接受的,即使 x就是 y或 z之一(因为我们的机器指令允许一个指令中的两个寄存器相同)
  • 如果 y在指令I之后不再使用,且(在必要时加载 y之后) Ry仅仅保存了y的值,那么, Ry同时也可以用作Rx 。对z和Rz也有类似选择

当I是复制指令x=y时,选择好Ry后,令Rx =Ry

窥孔优化

窥孔优化

  • 窥孔(peephole)是程序上的一个小的滑动窗口
  • 窥孔优化是指在优化的时候,检查目标指令的一个滑动窗口(即窥孔) ,并且只要有可能就在窥孔内用更快或更短的指令来替换窗口中的指令序列
  • 也可以在中间代码生成之后直接应用窥孔优化来提高中间表示形式的质量

具有窥孔优化特点的程序变换的例子

  • 冗余指令删除
  • 控制流优化
  • 代数优化
  • 机器特有指令的使用

冗余指令的删除

  • 消除冗余的加载和保存指令

Image11-5.png

此处的有标号的意思是:该段代码前有跳转指令可以跳转到第四条指令,也就是说不能总保证第三条指令在第四条指令之前,所以不可以删除

  • 消除不可达代码
    一个紧跟在无条件跳转之后的不带标号的指令可以被删除

Image11-6.png

控制流优化

  • 在代码中出现跳转到跳转指令的指令时,某些条件下可以使用一个跳转指令来代替

Image11-7.png

代数优化

  • 代数恒等式
    消除窥孔中类似于x=x+0或x=x * 1的运算指令
  • 强度削弱
    对于乘数(除数)是2的幂的定点数乘法(除法) ,用移位运算实现代价比较低
    除数为常量的浮点数除法可以通过乘数为该常量倒
    数的乘法来求近似值

特殊指令的使用
充分利用目标系统的某些高效的特殊指令来
提高代码效率

  • 例如:INC指令可以用来替代加1的操作
Last modification:February 10th, 2019 at 08:28 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment