沖突圖的構(gòu)建

landker

碰到一個(gè)關(guān)于沖突圖構(gòu)建的問(wèn)題（在《現(xiàn)代編譯原理——C語(yǔ)言描述（虎書）》中文版），具體如下：

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

復(fù)制代碼

上面的代碼有2個(gè)基本塊，分別為 L1 和 L2。其中，L1包含2個(gè)算式（c=a+b; z=a-b）；L2也包含2個(gè)算式（e=f*g; s=t/u）。

我的問(wèn)題是，如果要構(gòu)建如《虎書》上提到的沖突圖（第161頁(yè)），那對(duì)于上面的代碼，共需要構(gòu)建多少個(gè)沖突圖？是整個(gè)程序只需構(gòu)建一個(gè)沖突圖，還是“一個(gè)基本塊”構(gòu)建一個(gè)沖突圖，又或者是“一句代碼”構(gòu)建一個(gè)沖突圖？

我的理解為，原來(lái)我是認(rèn)為整個(gè)程序應(yīng)該只有一個(gè)沖突圖，而所有發(fā)生沖突的變量構(gòu)成沖突圖的端點(diǎn)，而這些端點(diǎn)之間的聯(lián)系構(gòu)成沖突圖的邊。但如果只有一個(gè)沖突圖的話，那有些地方就不太好理解，比如：

對(duì)于“代碼”里的第4句（4th），c, a, b之間不應(yīng)該使用相同的寄存器（這里先排除實(shí)際目標(biāo)機(jī)指令，如x86里是將結(jié)果直接存放在前一個(gè)寄存器里的），即會(huì)存在3條沖突邊（c->a, c->b, a->b）。

“代碼”的第5句（5th），對(duì)于 a，它是否可以使用 c 所占用的寄存器 reg3？ 如果c 在后面的程序里是不會(huì)再使用到（也不會(huì)有定值操作），那 a 應(yīng)該可以使用reg3，但在沖突圖中由于存在沖突邊“c->a”，那就決定了a 不能使用 reg3。這不是很矛盾嗎？

landker

回復(fù) 1# landker


   ding

landker

回復(fù) 1# landker

有人知道嗎？