您最喜歡的抽象語法樹優化

Question

如果您正在構建編譯器，那麼AST級別的優化是最好的嗎？

Answer 1

的優化是最容易的AST做的（而不是，比方說，CFG）是尾調用優化：如果你看到表格的子樹：

RETURN 
    CALL f 
     ARGS x, y, ... 

您可以將其替換爲跳轉到f。如果f(a, b)是，尾部調用出現在函數，更換很簡單，只要：

a = x; b = y 
JUMP to root of tree 

我覺得最簡單的表示跳作爲一種特殊的「重啓」說明，該AST-> CFG翻譯視爲第一個節點的邊緣。跳到其他函數有點棘手，因爲你不能只設置局部變量，你需要事先思考如何將參數傳遞給它們，並準備在較低的層次上進行翻譯。例如，AST可能需要一個特殊的節點，它可以指示稍後的傳遞，用參數覆蓋當前的堆棧幀並相應跳轉。

Answer 2

大多數情況下，您不能在AST級別進行有趣的優化，因爲您需要有關數據如何從程序的一部分流向另一部分的信息。雖然數據流隱含在AST的含義中，但通過檢查AST不易確定，這就是爲什麼構建編譯器和優化器的人構建其他程序表示（包括符號表，控制流圖，到達定義，數據流和SSA表格等）。

擁有語言的解析器是分析/操作該語言的簡單部分。 你需要所有其他的東西來做好工作。

如果你做有所有其他的表示，你可以考慮在AST級別做優化。建設編譯器的大多數人不會打擾;他們轉換爲數據流表示並簡單地優化。但是如果你想通過改變來重現源代碼，你需要AST。你還需要一個漂亮的打印機來讓你重新生成源代碼。如果你走這麼遠，你最終將得到一個源到源 程序轉換系統。

DMS Software Reengineering Toolkit是一個轉換AST的系統，使用所有這些其他表示來啓用轉換所需的分析。

Answer 3

在AST中應用優化的一個優點是可以減少某些後端優化傳遞的執行時間。但是，我相信這些優化需要通過簡約性來完成，因爲您可能會阻礙代碼中的進一步優化。這就是說，IMO在AST水平或IR生成過程中應用的一個簡單但有趣的優化是簡化布爾表達式（1 || 2）或（2 < 3 || A），等他們淨結果。我相信一些簡單的窺視孔優化也可能是值得的。