动态规划代码生成问题

dirtysalt

还是Aho Dragon Book那本书，第二版中文版370，英文版570页关于动态规划代码生成的问题

不理解书中的C的设置，实际上我觉得那样设置C 根本就没有含义。按照书中前面说C是有i个寄存器可用的时候的cost，那么c[0]就是没有任何寄存器可用的cost了，但是后面计算的时候c[0]是(min{1<=i<=n}C)+1的值，这就没有任何意思了，因为如果c[0]没有任何寄存器可用时，首先我们要将一部分reg spill用于计算,计算完之后在将结果保存到内存中，将reg恢复，这样代价就不是1，计算方式也不是这样的。

按照我的理解根本就不需要设置c有n个分量，只需要设置两个分量c[2]，c[0]表示该节点放在内存中的代价，c[1]表示放在reg中的代价，假设按照书中的几种指令方式
Ri = Mj
Ri = Ri op Rj
Ri = Ri op Mj
Ri = Rj
Mi = Ri
来产生d/e的结果，这样d开始的cost是[0,1],e是[0,1]
对于/有两种匹配方式Ri = Ri op Rj,Ri = Ri op Mj,如果按照第一种匹配
那么就是d.cost[reg](d.cost[1]=1)+e.cost[reg](e.cost[1]=1)+cost(/)(assume =1)=3
如果按照第二种匹配
d.cost[reg](d.cost[1]=1)+e.cost[mem](e.cost[0]=0)+cost(/)=2
所以d/e的cost[reg]=2,由于没有任何直接保存到mem的操作，那么cost[mem]=cost[reg]+cost(Mi = Ri)(assume =1)=3
所以d/e的cost分量就是[3,2]。

对于书中的例子，我还特意按照我自己的理解花了一幅图，在附件中，希望你们能够理解我的意思。

[ 本帖最后由 dirtysalt 于 2008-6-12 12:45 编辑 ]

dirtysalt

自顶自己的贴,自顶

cjaizss

原书的意思应该是不存在C[0]的
C中,必须要有1<=i<=r
r是通用寄存器的个数

dirtysalt

有的，C[0]的意思是计算到内存的代价。
这个问题已经搞清楚了，如果斑竹还有什么疑问的，可以在水木清华smth->计算机体系结构板块里面找到这个问题我和斑竹的讨论。不过那本龙书描述这个问题不清楚，我的理解模型也有错误，看完作者的论文后才明白。谢谢斑竹关注，敬礼

nmap

学习