动态规划代码生成问题
还是Aho Dragon Book那本书，第二版中文版370，英文版570页关于动态规划代码生成的问题不理解书中的C的设置，实际上我觉得那样设置C 根本就没有含义。按照书中前面说C是有i个寄存器可用的时候的cost，那么c就是没有任何寄存器可用的cost了，但是后面计算的时候c是(min{1<=i<=n}C)+1的值，这就没有任何意思了，因为如果c没有任何寄存器可用时，首先我们要将一部分reg spill用于计算,计算完之后在将结果保存到内存中，将reg恢复，这样代价就不是1，计算方式也不是这样的。
按照我的理解根本就不需要设置c有n个分量，只需要设置两个分量c，c表示该节点放在内存中的代价，c表示放在reg中的代价，假设按照书中的几种指令方式
Ri = Mj
Ri = Ri op Rj
Ri = Ri op Mj
Ri = Rj
Mi = Ri
来产生d/e的结果，这样d开始的cost是,e是
对于/有两种匹配方式Ri = Ri op Rj,Ri = Ri op Mj,如果按照第一种匹配
那么就是d.cost(d.cost=1)+e.cost(e.cost=1)+cost(/)(assume =1)=3
如果按照第二种匹配
d.cost(d.cost=1)+e.cost(e.cost=0)+cost(/)=2
所以d/e的cost=2,由于没有任何直接保存到mem的操作，那么cost=cost+cost(Mi = Ri)(assume =1)=3
所以d/e的cost分量就是。
对于书中的例子，我还特意按照我自己的理解花了一幅图，在附件中，希望你们能够理解我的意思。
[ 本帖最后由 dirtysalt 于 2008-6-12 12:45 编辑 ]
这个问题需要关注
自顶自己的贴,自顶 原书的意思应该是不存在C的C中,必须要有1<=i<=r
r是通用寄存器的个数
回复 #3 cjaizss 的帖子
有的，C的意思是计算到内存的代价。这个问题已经搞清楚了，如果斑竹还有什么疑问的，可以在水木清华smth->计算机体系结构板块里面找到这个问题我和斑竹的讨论。不过那本龙书描述这个问题不清楚，我的理解模型也有错误，看完作者的论文后才明白。谢谢斑竹关注，敬礼 学习:handshake
页:
[1]