代码生成.

Presentation on theme: "代码生成."— Presentation transcript:

1 代码生成

2 动态规划代码生成算法 动态规划代码生成算法可以适用于更广泛的机器类型：具有r个可交换的寄存器，具有加载、保存和运算等指令形式；并且，
将表达式生成最优代码的问题分解为若干子表达式生成最优代码的子问题。如表达式E为E1+E2，则E的一个最优程序可以由E1和E2的最优程序以某种顺序组合而成，然后是对+的求值代码。

3 动态规划代码生成算法 所产生的最优代码具有连续求值的特征。所谓程序连续计算一棵树T（如表达式E = E1 OP E2对应的树T，其子树分别为T1、T2），先计算那些需要将结果存入内存的T的子树（如T1），然后再计算T的其余子树；计算的次序是T1T2OP根（或者T2T1OP根）。 在寄存器机器上，对于任意一个计算树T的程序P，可以证明，总能找到一个等价且采用连续计算方式的T的计算程序Q。Q所使用的寄存器数与代价不超过P中的对应值。由此，确保使用动态规划算法为树T产生最优代码!

4 动态规划代码生成算法 算法有三个步骤（设r个寄存器可用）：
自底向上计算表达式树中每个结点n的代价数组C。C[ i ]表示有i（1≤i ≤ r）个寄存器可用时，计算以结点n为根的子树且结果存入一个寄存器的最优代价。显然，C[0]表示在所有r个寄存器可用时，计算并将结果放入内存的最优代价。 遍历树T，使用代价数组来决定选择哪棵子树须被计算且结果放入内存； 遍历树T，使用代价数组和相关指令生成最终的目标代码。而那些结果放入内存的子树须被优先处理并生成代码。

5 示例：动态规划代码生成 表达式（树）： (a – b) + c * (d / e) 机器指令： LD Ri，Mj // Ri = Mj
op Ri，Rj，Rk // Ri = Rj op Rk op Ri，Rj，Mj // Ri = Rj op Mj LD Ri，Rj // Ri = Rj ST Mi，Rj // Mi = Rj （假设以上指令代价均为1， 且有两个寄存器R0、R1可用） + - * a b c / d e

6 示例：动态规划代码生成 算法步骤一：自底向上计算各个结点的代价数组。 ( 8,9,7) + * ( 5,5,4) - ( 3,2,2) a
( 0,1,1) b ( 0,1,1) c ( 0,1,1) / ( 3,2,2) d ( 0,1,1) e ( 0,1,1) 算法步骤一：自底向上计算各个结点的代价数组。

7 示例：动态规划代码生成 叶子结点a的代价为(0, 1, 1): 类似地，叶子结点b、c、d和e的代价均为 (0, 1, 1)。
C[0]: 计算a且放入内存的代价。a初始在内存中，故代价为0； C[1]:有1个寄存器可用时计算a且存入寄存器的代价，可由指令LD R0，a完成，代价为1； C[2]:在2个寄存器可用时，计算a且存入寄存器的代价，显然，也可由类似指令：LD R0，a完成，代价为1。 类似地，叶子结点b、c、d和e的代价均为 (0, 1, 1)。

8 示例：动态规划代码生成 内部运算结点的代价的计算 如减运算结点的代价(3,2,2) 计算如下：
- ( 3,2,2) 内部运算结点的代价的计算 如减运算结点的代价(3,2,2) 计算如下： C[1]：1个寄存器可用时，计算且结果存入寄存器的代价。此时，仅指令 op Ri，Ri，Mj与根结点计算需求最佳匹配。因此，根结点的代价是：寄存器数为1时左运算分量被计算且结果存入寄存器的代价＋寄存器数为1时右运算分量被计算且结果放入内存的代价＋1（上述运算指令的代价），即C[1] = 1+0+1=2 而此时，对应的指令序列是（右运算量须先计算）：（R可选R0或R1） // 右运算量b已在内存中，无需生成代码 LD R，a // 左运算分量计算、放入寄存器 SUB R，R，b //计算根、放入寄存器；右运算量在内存中 a ( 0,1,1) b ( 0,1,1)

9 示例：动态规划代码生成 内部运算结点的代价的计算 如减运算结点的代价(3,2,2) 计算如下：
- ( 3,2,2) 内部运算结点的代价的计算 如减运算结点的代价(3,2,2) 计算如下： C[2]：2个寄存器可用时，计算且结果存入寄存器的代价。此时，有两种指令： op Ri，Ri，Mj和op Ri，Ri，Rj分别与根结点计算需求匹配。因此，左、右运算分量计算过程中使用寄存器数和结果存放有以下三种情形： （1）左：2个寄存器且结果在寄存器中；右（须先计算） ：2个寄存器且结果在内存中，此时，根计算代价=1+0+1=2; （2）左（须先计算）：2个寄存器且结果在寄存器中；右：1个寄存器且结果在寄存器中；此时，根计算代价=1+1+1=3; （3）左：1个寄存器且结果在寄存器中；右（须先计算）：2个寄存器且结果在寄存器中；此时，根计算代价=1+1+1=3; 显然，针对此减运算，情形（1）代价最优，其代码序列为： // 右：b就在内存中，无需生成代码 LD R0，a // 左：加载a到寄存器 SUB R0，R0，b //根计算指令 a ( 0,1,1) b ( 0,1,1)

10 // 计算且结果存入寄存器R的代码（使用全部寄存器） ST M，R // 保存寄存器R到内存 类似地，可以计算出其他内部运算节点的代价向量
示例：动态规划代码生成 - ( 3,2,2) 内部运算结点的代价的计算 如减运算结点的代价(3,2,2) 计算如下： C[0]：2个寄存器可用时，计算且结果存入内存的代价。显然，最优的代码序列应该是在2个寄存器可用时计算且结果存入寄存器；然后再将结果保存到内存。因此代价=C[2]+1=2+1=3；其指令序列如下： // 计算且结果存入寄存器R的代码（使用全部寄存器） ST M，R // 保存寄存器R到内存 类似地，可以计算出其他内部运算节点的代价向量 （数组）。 a ( 0,1,1) b ( 0,1,1)

11 示例：动态规划代码生成 表达式树中各结点的代价向量（分量）的计算过程，其实就是寻找最优代价的计算路径，然后可以根据该路径生成最优代价的代码序列。而这也就是动态规划代码生成算法的第二与第三步！ 如果某个代价分量的计算具有多种组合情况，则可能存在多条最终的最优代价相同的计算路径。例如，在上述C[2]计算时，存在三种组合情形，算法只选择代价最小的，但如果三种情形中的代价相同，则存在多种选择，可以任选其一。 在结点左右分量的计算次序上，首先考虑结果放入内存的分量须优先计算（此时将使用全部的寄存器），其次是按使用寄存器多少安排分量的计算次序。

12 示例：动态规划代码生成 在2个寄存器 可用时，计算 该表达式树 的最优计算 路径如图所示。 （结点标号从小 到大） 最优代码序列如下：
LD R1，d DIV R1，R1，e LD R0，c MUL R0，R0，R1 LD R1，a SUB R1，R1，b ADD R1，R1，R0 9 + ( 8,9,7) 5 8 - * ( 5,5,4) ( 3,2,2) 3 a b c ( 0,1,1) ( 0,1,1) ( 0,1,1) / ( 3,2,2) 7 6 4 d e ( 0,1,1) ( 0,1,1) 2 1