6.代码最优化.

Presentation on theme: "6.代码最优化."— Presentation transcript:

1 6.代码最优化

2 背景知识 二叉树遍历算法的应用 递归遍历算法 先序遍历（根左右） 中序遍历（左根右） 后序遍历（左右根） 类后序遍历解决问题 根右左 右左根
二叉树遍历算法的应用 递归遍历算法 先序遍历（根左右） 中序遍历（左根右） 后序遍历（左右根） 类后序遍历解决问题 根右左 右左根 左右根

3 一、代码最优化问题描述 将给定算术表达式翻译成汇编语言代码，如何翻译得到最优编码？
汇编语言特点：面向机器的低级语言，机器不同，汇编语言指令系统不同， 因此针对不同的机器研究算术表达式的最优化编码问题

4 模型机A下的最优化代码 模型机A结构如下： 一个累加寄存器R 指令系统包括： 存入指令：store M；将寄存器R的值存入存储单元M
装入指令：load M；将存储单元M的值存入寄存器R 算术运算指令：op M；R⊙M→R 其中，⊙可以是：add （+），sub（-），mul（*），div（/）

5 例1 (a+b)/(c+d)的两段代码 LOAD a ADD b STORE T1 LOAD c ADD d STORE T2
LOAD T1 DIV T2 LOAD c ADD d STORE T1 LOAD a ADD b DIV T1

6 定义6.1表达式E翻译成某给定机器语言或汇编语言是最优的，当且仅当这一翻译有最少的指令条数。
对于(a+b)/(c+d)显然第二段代码更优。 影响表达式指令长度的因素？

7 例2 a+b*c的两段代码 LOAD b MPY c STORE T1 LOAD a ADD T1 LOAD b MPY c ADD a
利用了加法的交换律 b*c+a

8 例3 a*b+c*b的两段代码 LOAD c MPY b STORE T1 LOAD a ADD T1 LOAD a ADD c MPY b
2 LOAD c MPY b STORE T1 LOAD a ADD T1 LOAD a ADD c MPY b 利用了运算的分配律（a+c）*b=a*b+c*b

9 例4 a*(b*c)+d*c的两段代码 LOAD b MPY c STORE T1 LOAD a MPY T1 LOAD d
2 LOAD b MPY c STORE T1 LOAD a MPY T1 LOAD d STORE T2 LOAD T1 ADD T2 LOAD a MPY b ADD d MPY c 利用了运算的结合律和分配律 a*(b*c)+d*c =(a*b)*c+d*c =(a*b+d)*c

10 影响表达式代码长度的因素 表达式本身的长度 表达式中运算的可交换-----交换律 表达式中运算的可分配性-----分配律
表达式中运算的可结合性------结合律 其中：+ - * /,运算中，加法和乘法具有交换、分配和结合性

11 二、表达式的中缀形式和表达式树 运算符出现在运算量之间的表达式的形式称为中缀形式。 用二元树表示中缀表达式，形成表达式树
二元树的每个非叶结点（内部结点）表示一个运算符 内部结点的左子树表示它的左运算量，右子树表示其右运算量。 叶结点表示一个常数或一个变量。

12 a+b*c a*b+c*b + b c * a + c b a *

13 表达式树的构造 a*b+c*b 确定算术表达式中运算符的优先级 优先级最低的算符作为树根 左边的是左运算量，构造左子树
右边的是右运算量，构造右子树 + * * + a b b c

14 三、求解方案 一般约定： 下面的研究将限定于简单机器A 不对表达式进行化简 不使用交换律、分配律和结合律

15 2.只有装入和存入指令条数可变，且是有规律的：除第一条指令外，每一条装入指令都紧跟在一条存存入指令之后，即
在上述约定的前提下，得到： 1.表达式中算术运算指令是确定的，不能减少 2.只有装入和存入指令条数可变，且是有规律的：除第一条指令外，每一条装入指令都紧跟在一条存存入指令之后，即 装入指令数=存入指令数+1 3.最优代码中含有最少数目的装入指令 4.表达式树任意一内结点P， L是P的左子树，R是P的右子树， ⊙表示运算符，分析L⊙R的可能情况，得到最优方案。

16 表达式树基本结构 L叶子、R叶子 L叶子，R子树 L子树，R叶子 L子树，R子树 其中：结点用圆形表示、子树用三角形表示 OP L R

17 最优求解步骤 求解步骤 load a op b L叶子、R叶子 op a b

18 最优求解步骤 求解方案一：（先左后右） L叶子、R子树 求解方案二：（先右后左） 子树结果存在R中，CR store M1 load a
op M1 OP a R

19 最优求解步骤 CL ;左子树求解，结果 ; 在R中 op b L子树，R叶子 OP L b

20 最优求解步骤 1先左后右： CL； store M1 CR; store M2 load M1 op M2 2先右后左： CR;
L、R均为子树 OP L R

21 机器A下的最优代码方案 如果右子树不是叶子，先处理右子树再左子树 如果右子树是叶子，先处理左子树再右子树 对左右子树按同样规则进行处理
右左根 左右根

22 递归过程 procedure code1(T)
if T是叶子then print(“load ”,data(T)); return endif f=0; if rchild(T)不是叶子 then call code1(rchild(T)); call temp(i); print (“store”,i); f=1; endif call code1(lchild(T)); if f=1 then print (data(T),i); call retemp(i); else print (data(T),data(rchild(T))); end code1 递归出口 递归过程

23 例 a+(b+(c+d)) load c add d store t1 load b add t1 load a + a b c d

24 四、机器B下的最优化代码 机器B结构如下： 有N个寄存器Ri N>=1 指令：load M,R ;M→R
Store R,M ;R → M OP R1，M,R2 ;R1 ⊙ M → R2 OP R1,R2,R ;R1⊙R2 → R3 其中，op代表加减乘除算术运算，寄存器R1R2R3可以是同一个寄存器

25 机器B上，代码中算术运算指令与表达式中运算符数量一致，但load指令和store指令否则存在差一的关系呢？

26 (a+b)/(c*d) 无store指令 N=2 N=1 load c,r1 load c,r1 mpy r1,d,r1
store r1,t1 load a,r1 add r1,b,r1 div r1,t1,r1 N=2 load c,r1 mpy r1,d,r1 load a,r2 add r2,b,r2 div r2,r1,r1 无store指令

27 由例子可以看出：当寄存器数量足够时，可以不需要store指令。

28 定理1 设P是度至少为2的表达式树T的结点，函数MR(P)定义如下:
MR(P)= P是右叶子 max{L1,L2} P是内结点,且L1 ≠ L2 L L1=L2 其中，L1=MR(Lchild(P));L2=MR(Rchild(P)) 若结点P是树的根结点，则MR(P)是所需的最小寄存器数。

29 L1L2分别表示左子树和右子树所需的最小寄存器数，当L1≠L2
证明 OP b a 当只有一个内结点时： 左叶子需要存入R 右叶子不需要存入R 当有多个内结点时： L1L2分别表示左子树和右子树所需的最小寄存器数，当L1≠L2 不妨设L1>L2，先计算左子树，用一个寄存器存储左子树的值，L1-1≥L2，可以计算右子树 ∴MR(P)=L1 若L2>L1，先计算右子树，再左子树，同理MR(P)=L2 ∴MR(P)=max{L1，L2} load a,r1 op r1,b,r1

30 不管先计算左子树还是右子树，一个寄存器用来保存中间结果，剩下的L-1﹤L1或L2，应最少增加1个寄存器。
∴ MR(P)=L+1

31 对于任意一颗表达式树T，都可以用后根次序计算各节点的MR值，树根T的MR值表示表达式不用store指令时，需要最少的寄存器数。
当N≥MR(T),不需要store指令 当N﹤MR(T),需要store+load指令数最少

32 例 a+(b+(c+d)) 2 MR(T)=2 + a b c d 1 2 1 1 1

33 解决方案 MR(R)=0：处理左子树，结果存入Ri 中 输出op Ri，R，Ri MR(L) ≥N且MR(R) ≥N:
先处理右子树，存入Ti中，然后处理左子树，并输出op Ri， Ti ，Ri MR(L) <MR(R)且至少有一个小于N: 先处理右子树再处理左子树 MR(L) ≥ MR(R)且至少有一个小于N 先处理左子树再处理右子树

34 procedure code2(T) if T是叶子then Print(load data(T),R,i);return ;endif L=Lchild(T);R=Rchild(T); case :MR(R)=0:call code2(L,i);print(data(T),Ri,data(R),Ri); :MR(L) ≥N and MR(R) ≥N:call code2(R,i);call temp(s); print(“store”,Ri,s);call code2(L,i); print(data(T),Ri,s,Ri); :MR(L) <MR(R):call code2(R,i);call code2(L,i+1); print(data(T),Ri+1,Ri,Ri); :else:call code2(L,i);call code2(R, i+1); print(data(T),Ri,Ri+1,Ri); endcase end code2

35 例 a+(b+(c+d)) MR(T)=2 若N=2不需要store指令 load b,r1 load c,r2 add r2,d,r2
add r1,r2,r1 load a,r2 add r2,r1,r1 2 + a b c d 1 2 1 1 1

36 例 a+(b+(c+d)) MR(T)=2 若N=1需要store指令 load c,r1 add r1,d,r1 store r1,s1
load b,r1 add r1,s1,r1 load a,r1 2 + a b c d 1 2 1 1 1

37 总结 在机器A下的最优编码方案 在机器B下的最优编码方案 充分利用了二元树结构分析和求解问题 算法充分应用了递归思想