什麼構成基本塊的開始？

Question

彙編代碼中的無條件跳轉之後的指令是否構成新基本塊的開始？假設該指令不是可執行文件中任何分支的目標。

Answer 1

由於計算分支的可能性和條件分支可能總是或永遠不被遵循，所以不可能完全確定構成基本塊的構成。相反，使用兩個假設估計基本塊：

1. 由於其他原因，計算分支只會到達基本塊的開始位置，因此不需要知道它們的目標。
2. 有條件的分支既可以遵循，也可以不遵循。

使用Wikipedia's definition，一個基本塊只能在開始時輸入並在結束時退出，從開始到結束只有一個路徑。因此，任何條件跳轉指令都必須是基本塊的末尾，因爲它創建了兩條路徑。計算分支也是結束，因爲它們可以產生許多不同的路徑。

無條件跳轉是否是基本塊的結束可以使用略有不同的定義進行辯論。如果塊中的所有代碼都必須在內存中連續存在，那麼無條件跳轉總是結束，除非它轉到後面的指令。否則，它遵循與非跳轉指令相同的規則。

對於所有其他指令，如果在它之後執行的指令是基本塊的開始，那麼它必須是一個的結尾。

塊的最簡單的開始是程序的入口點。此外，作爲條件跳轉目標的任何指令都是塊的開始，因爲在跳轉指令之後它可能會或可能不會被執行。如果指令是無條件跳轉的目標，並且基本塊必須在內存中連續，那麼它是塊的開始。否則，如果它是兩個或更多無條件跳轉的目標，或者它是一個目標，並且指令在它不是無條件跳轉之前，則它是塊的開始，因爲有多條路徑進入它。

如果無條件跳轉後的指令不是任何其他跳轉的目標，它仍可能被標記爲基本塊的開始，因爲它的存在表明計算的分支可能會將其作爲目標。

這些基本塊開始的規則基本上簡化爲「在基本塊結束後執行的指令是基本塊的開始」。

一個更簡單的方法有時可能會產生更小的塊，但通常是好的，即任何跳轉都是塊的結束，而其後的指令是一個塊的開始，而任何跳轉的目標是塊的開始和指令的結束之前。

---

如果有更高級別的代碼可用，它可以用來更準確地確定塊邊界。例如，編譯器生成的計算分支通常會有一組已知的可能目標。考慮下面的C代碼：

int i, j, k; 
switch(i) { 
    case 0: 
     j++; 
     // Flow into the next case 
    case 1: 
     k++; 
} 

下面是一個使用算出的分支一些可能的僞彙編此代碼：

jump *(i+jumpTable) 
add  1, j 
add  1, k 

跳轉表將目標的附加指令之一，所以他們都一個基本塊的開始。但是，這不能從程序集中確定，因此使用了第一個假設。第一個添加是基本塊的開始，因爲它在跳轉之後。但是，沒有已知的分支針對第二個添加，所以它不被認爲是這個分析的基本塊的開始。

Answer 2

遵循無條件跳轉並且不是任何分支或跳轉的目標的指令是死代碼或僅僅是數據。