編譯爲程序集時最小化跳轉的數量

假設我們已經編譯了一些程序給了一些抽象的中間語言：我們的程序是執行下一個操作（基本上是一棵樹）的一系列操作和決策（分支）。例如：編譯爲程序集時最小化跳轉的數量

a(); 
if (bla) then c(); 
else b(); d(); 
e();

現在我們需要「包裝」該序列我們的線性內存，並通過這樣做，我們的代碼必須分支（有條件，而不是）。舉例來說，可能性之一：

 CALL A 
     TEST bla 
     BRANCH else 
     CALL C 
     JMP esc 
else: CALL B 
     CALL D 
esc: CALL E

當然也有關於如何安排線性存儲這些塊的多種可能性，他們都在分行的量不同/跳躍。我們的目標是儘量減少它們。
問題：
a）如何調用這個問題？有一個通用名稱嗎？（這是BDD構建的一個實例嗎？）
b）這種問題的複雜性是什麼（尋找塊的排列使得跳轉/分支的數量最小）？

來源

2016-09-21 artemonster

你有什麼是一堆基本塊，在每個基本塊的末尾將控制權從一個控制到另一個。

您可以使用有向圖很容易地對此進行建模。節點是基本塊。從一個節點到另一個節點的定向弧代表（wlog）從一個塊到另一個塊的條件分支（有時條件爲「真」）。您應該考慮將異常提升爲分支，並將處理程序視爲塊。

線性化一系列塊基本上是選擇一系列的弧。這樣的序列以沒有分支的塊（例如，函數返回或應用程序退出）結束。

你想要做的是選擇一組弧形序列（想象你將這些藍色染色），使其餘的弧線（想象成紅色）最小。

我不知道複雜性是什麼，但由於您可以在每個節點上有兩個選擇，它看起來像指數級的困難。（在最壞的情況下，你可以有一個完全連通的圖表，通常對這樣的圖表進行推理非常昂貴）。

我期望一個人可以用貪婪的方案來實現它，並獲得相當不錯的結果：重複查找最長的弧序列，將其着色爲藍色。

最大順序化可能不是你真正想要的。想象一下，基於概要分析數據，算法知識，假設異常很少出現，因此概率很低，甚至程序員提供了提示，我們將概率附加到每個弧上。現在你想要的是具有最大概率的長弧鏈。這種路徑在文獻中被稱爲「痕跡」。這確保代碼中的熱路徑在內存中是連續的，從而最大化指令高速緩存的值。以這種方式定義的偏序分支是低概率的，例如冷路徑。

您仍然具有相同的複雜度選擇。但貪婪的方案可能會更好：通過簡單地從序列中已經存在的每個節點中選擇最高概率弧來形成序列。

由於弧序列有顏色，因此很容易以「正確」的順序生成代碼。

這個paper更正式地討論了使用跟蹤的「代碼佈置」，特別是爲了減少緩存未命中的代價。它討論了一個貪婪的選擇過程，它產生了相當不錯的結果，以及一個更復雜但相當昂貴的時間方面的「本地搜索」方案，可以產生出色的結果。

來源

2016-09-21 10:20:30

編譯爲程序集時最小化跳轉的數量

回答

相關問題