編譯代碼生成 - 條件塊內部的寄存器分配

Question

我正在編寫一門課程的編譯器。我遇到了一些優化問題，我不確定如何處理最佳。假設輸入語言有一個while循環，它使用必須保存在寄存器中的N個局部變量（或者應該爲了快速計算）。假設N> K，寄存器的數量。在while循環結束時有可能改變條件寄存器。

例如，假設x的寄存器（比方說，在i386％EAX）確定之前發表聲明如下：

while (x) { x = x - 1 ; /* more statements */ } 

在多個語句代碼，它有可能被溢出的X回到棧上。當代碼跳回到while循環的開始以重新計算x時，它將嘗試使用％eax - 但這可能甚至不會保存x的值。所以我們可以有像我使用的是強制代碼while語句（所以寄存器被視爲空從代碼生成的角度來看）之前，溢出所有修改寄存器

 movl -8(%ebp), %eax  # eax <- x 
     ....      # do stuff but let x stay in %eax 
_LOOP1: cmpl $0, %eax 
     .... 
     movl -12(%ebp), %eax  #eax now holds something else 
     .... 
     jmp _LOOP1 

一種解決方案。在while循環的標籤之後，代碼必須根據需要將所有內容加載到寄存器中。

我的解決辦法是這樣的：

 movl -8(%ebp), %eax  # eax <- x 
     ....      # do stuff but let x stay in %eax 
     movl %eax, -8(%ebp)  # spilling and clearing all registers 
_LOOP1: movl -8(%ebp), %eax  # get a register for x again 
     cmpl $0, %eax 
     .... 
     movl -12(%ebp), %eax  # eax now holds something else 
     .... 
     movl %eax, -8(%ebp)  # spill to prevent overwrite 
     jmp _LOOP1 

好像我的解決辦法是有點多餘的或不必要的。有沒有我在這裏忘記的一些一般優化技巧？

編輯：我還想指出類似的情況發生的條件，如if和if else。發生這種情況是因爲一個寄存器可能被分配給條件塊內的一個變量，但代碼生成器假定它被移動到那裏以後的其他所有內容中。我處理這個案件的方法幾乎相同。

Answer 1

您在這裏尋找的一般技術通常稱爲「活動範圍分裂」。該術語的Google Search會給你指向一堆不同的論文。基本上這個想法是，你想要將一個變量（在你的例子中是x）分成多個變量，這些變量具有不相交的活動範圍，每個變量都被複制到分割點的下一個變量中。所以你需要在循環之前有x.0，它在while之前被複制到x.1中，並在循環中用作它。然後在循環之後，您將x.1複製到x.2並在循環之後使用它。每個拆分變量都可能被分配到不同的寄存器（或棧槽）。

這裏有很多折衷 - 太多的分割會導致代碼中（更多）更多的變量，從而導致寄存器分配速度變慢，並可能導致不必要的副本。