6.代码最优化

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

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

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

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

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

例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

例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

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

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

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

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

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

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

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

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

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

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

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

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

递归过程 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 递归出口 递归过程

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

四、机器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,R3 ;R1⊙R2 → R3 其中，op代表加减乘除算术运算，寄存器R1R2R3可以是同一个寄存器

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

(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指令

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

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

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

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

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

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

解决方案 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 先处理左子树再处理右子树

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

例 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

例 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

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