一千萬個為什麽

搜索

確定最大堆棧深度

想象一下,我有一個基於堆棧的玩具語言,包括Push,Pop,Jump和If操作。

我有一個程序,它的輸入是玩具語言。例如,我得到序列

Push 1
Push 1
Pop
Pop

在這種情況下,最大堆棧將是2.更復雜的示例將使用分支。

Push 1
Push true
If   .success
Pop
Jump .continue
.success:
Push 1
Push 1
Pop
Pop
Pop
.continue:

在這種情況下,最大堆棧將是3.但是,如本例所示,不可能通過從上到下行走來獲得最大堆棧,因為它實際上會導致堆棧下溢錯誤。

CFG拯救你可以建立一個圖表並走你所擁有的基本塊的每條可能的路徑。但是,由於n個頂點的路徑數量可以快速增長(n-1)!可能的路徑。

My current approach is to simplify the graph as much as possible and to have less possible paths. This works but I would consider it ugly. Is there a better (read: faster) way to attack this problem? I am fine if the algorithm produces a stack depth that is not optimal. If the correct stack size is m then my only constraint is that the result n is n >= m. Is there maybe a greedy algorithm available that would produce a good result here?

Update: I am aware of cycles and the invariant that all controlf flow merges have the same stack depth. I thought I write down a simple toy-like language to illustrate the issue. Basically I have a deterministic stack-based language (JVM bytecode), so each operation has a known stack-delta.

請註意,我確實有一個解決這個問題的工作解決方案,可以產生良好的結果(簡化cfg),但我正在尋找更好/更快的方法。

最佳答案

鑒於您的語言似乎沒有任何用戶輸入,所有程序將始終以相同的方式進行計算。因此,您可以執行程序並在執行期間跟蹤最大堆棧大小。可能不是你想要的。

至於你的路徑論證:要註意,跳躍允許循環,因此,無需進一步分析,循環可能意味著非終止和堆棧溢出(即在每個循環執行後堆棧大小增加)。 [如果有一個循環,n個節點仍然意味著無限多個路徑]

您可以使用某種形式的抽象解釋,而不是實際執行代碼。

關於IVlad的評論:由於存在可能的周期,僅僅計算推動是錯誤的。

我不確定你的if語句的語義是什麽,所以這也是有用的:假設if語句的標簽只能是一個前向標簽(即,你永遠不能跳回到你的代碼中)。在這種情況下,您的路徑計數參數將恢復生機。實際上,生成的CFG將是樹(如果不復制代碼,則為DAG)。在這種情況下,您可以通過自下而上計算推送次數來進行近似計數,然後在if語句的情況下獲取兩個分支的最大推送次數。它仍然不是最佳的正確結果,但產生了比簡單推送語句更好的近似值。

轉載註明原文: 確定最大堆棧深度