冲突图的构建

landker

碰到一个关于冲突图构建的问题（在《现代编译原理——C语言描述（虎书）》中文版），具体如下：

1. 伪代码：
   
2.        
   
3. L1:
   
4. ;(1) c = a + b
   
5. ;1th:        mov        reg1, dword[a]
   
6. ;2th:        mov        reg2, dword[b]
   
7. ;3th:        mov        reg3, c
   
8. ;4th:        add        dword[reg3], reg1, reg2
   
9.        
   
10. ;(2) z = a - b
    
11. ;5th:        mov        reg4, dword[a]
    
12. ;6th:        mov        reg5, dword[b]
    
13. ;7th:        mov        reg6, z
    
14. ;8th:        sub        dword[reg6], reg4, reg5
    
15. ;9th:        jump        L2
    
16. 
    
17. L2:
    
18. ;(1) e = f * g
    
19. ;10th:        mov        reg7, dword[f]
    
20. ;11th:        mov        reg8, dword[g]
    
21. ;12th:        mov        reg9, e
    
22. ;13th:        mul        dword[reg9], reg7, reg8
    
23.        
    
24. ;(2) s = t / u
    
25. ;14th:        mov        reg10, dword[t]
    
26. ;15th:        mov        reg11, dword[u]
    
27. ;16th:        mov        reg12, s
    
28. ;17th:        div        dword[reg12], reg10, reg11
    
29. ;18th:        jump        L3

复制代码

上面的代码有2个基本块，分别为 L1 和 L2。其中，L1包含2个算式（c=a+b; z=a-b）；L2也包含2个算式（e=f*g; s=t/u）。

我的问题是，如果要构建如《虎书》上提到的冲突图（第161页），那对于上面的代码，共需要构建多少个冲突图？是整个程序只需构建一个冲突图，还是“一个基本块”构建一个冲突图，又或者是“一句代码”构建一个冲突图？

我的理解为，原来我是认为整个程序应该只有一个冲突图，而所有发生冲突的变量构成冲突图的端点，而这些端点之间的联系构成冲突图的边。但如果只有一个冲突图的话，那有些地方就不太好理解，比如：

对于“代码”里的第4句（4th），c, a, b之间不应该使用相同的寄存器（这里先排除实际目标机指令，如x86里是将结果直接存放在前一个寄存器里的），即会存在3条冲突边（c->a, c->b, a->b）。

“代码”的第5句（5th），对于 a，它是否可以使用 c 所占用的寄存器 reg3？ 如果c 在后面的程序里是不会再使用到（也不会有定值操作），那 a 应该可以使用reg3，但在冲突图中由于存在冲突边“c->a”，那就决定了a 不能使用 reg3。这不是很矛盾吗？

landker

回复 1# landker


   ding

landker

回复 1# landker

有人知道吗？