示例：动态规划代码生成.pptVIP

代码生成 动态规划代码生成算法 动态规划代码生成算法可以适用于更广泛的机器类型：具有r个可交换的寄存器，具有加载、保存和运算等指令形式；并且， 将表达式生成最优代码的问题分解为若干子表达式生成最优代码的子问题。如表达式E为E1+E2，则E的一个最优程序可以由E1和E2的最优程序以某种顺序组合而成，然后是对+的求值代码。 动态规划代码生成算法 所产生的最优代码具有连续求值的特征。所谓程序连续计算一棵树T（如表达式E = E1 OP E2对应的树T，其子树分别为T1、T2），先计算那些需要将结果存入内存的T的子树（如T1），然后再计算T的其余子树；计算的次序是T1?T2?OP根（或者T2?T1?OP根）。 在寄存器机器上，对于任意一个计算树T的程序P，可以证明，总能找到一个等价且采用连续计算方式的T的计算程序Q。Q所使用的寄存器数与代价不超过P中的对应值。由此，确保使用动态规划算法为树T产生最优代码! 动态规划代码生成算法 算法有三个步骤（设r个寄存器可用）： 自底向上计算表达式树中每个结点n的代价数组C。C[ i ]表示有i（1≤i ≤ r）个寄存器可用时，计算以结点n为根的子树且结果存入一个寄存器的最优代价。显然，C[0]表示在所有r个寄存器可用时，计算并将结果放入内存的最优代价。 遍历树T，使用代价数组来决定选择哪棵子树须被计算且结果放入内存； 遍历树T，使用代价数组和相关指令生成最终的目标代码。而那些结果放入内存的子树须被优先处理并生成代码。 示例：动态规划代码生成 表达式（树）： (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 示例：动态规划代码生成 + - * a b c / d e 算法步骤一：自底向上计算各个结点的代价数组。 ( 0,1,1) ( 0,1,1) ( 3,2,2) ( 0,1,1) ( 0,1,1) ( 0,1,1) ( 3,2,2) ( 5,5,4) ( 8,9,7) 示例：动态规划代码生成 叶子结点a的代价为(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)。 内部运算结点的代价的计算 如减运算结点的代价(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 b ( 0,1,1) ( 0,1,1) ( 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 //根计算指令 示例