如何識別不影響程序輸出的變量？

有時，程序的控制流中訪問的變量的值不可能對其輸出產生任何影響。例如：如何識別不影響程序輸出的變量？

global var_1 
global var_2 

start program hello(var_3, var_4) 
    if (var_2 < 0) then 
     save-log-to-disk (var_1, var_3, var_4) 
    end-if 
    return ("Hello " + var_3 + ", my name is " + var_1) 
end program

這裏只VAR_1和VAR_3對輸出任何影響，而VAR_2和VAR_4僅用於副作用。像var_1和var_3這樣的變量在dataflow-theory/compiler-theory中有一個名字嗎？哪些靜態數據流分析技術可用於發現它們？

有關這方面的學術文獻的參考將特別感激。

來源

2014-06-12 Raul Bertone

假設編譯器可以區分這兩類變量，它可以對這些信息做些什麼？我認爲你一般不會認爲調用'save-log-to-disk'並不比函數結果重要。 –

@內部服務器錯誤：在考慮某個程序時，從功能的角度來看，您通常只將某些輸入和輸出視爲有趣的。該計劃可能會計算/做其他事情，但你不在乎。日誌文件適合這個類別。 –

即使對於以下非常窄的特例，您陳述的問題通常是不可判定的：給定一個例程P（x），其中x是整數類型的參數。 P（x）的輸出與x的值無關，即：P（0）= P（1）= P（2）= ...？

我們可以減少以下仍不可判定版本停機問題上面的問題：給定一個圖靈機M（），做節目 從未停止在空輸入？

我假設我們使用，我們可以建立一個「圖靈機模擬器」一個（圖靈完備）語言：

鑑於程序M（），構建這個程序：

P(x): 
    if x == 0: 
     return 0 
    Run M() for x steps 
    if M() has terminated then: 
     return 1 
    else: 
     return 0

現在：

P(0) = P(1) = P(2) = ... 
=> 
M() does not terminate. 

M() does terminate 
=> P(x) = 1 for a sufficiently large x 
=> P(x) != P(0) = 0

所以，這是非常困難的一個編譯器，以決定是否一個變量實際上不影響日常的返回值;在你的例子中，「副作用例程」可能會操縱它的一個值（或者甚至無限循環，這肯定會改變例程的返回值;-) 當然，過度使用仍然是可能的。例如，有人可能會得出這樣的結論：如果一個變量沒有出現在例程體中，它就不會影響返回值。您還可以看到一些經典的編譯器分析（如表達式簡化，常量傳播），這些分析具有消除此類冗餘變量外觀的副作用。

來源

2016-01-27 00:13:46 Pachelbel

帕切貝爾已經討論過你無法完美地完成這一事實。好的，我是一名工程師，我願意接受我的答案中的一些污點。

回答你問題的經典方法是做數據流從程序輸出回溯到程序輸入。 A 數據流是將程序分配（或副作用）與變量值連接到應用程序中消耗該值的位置。

如果您關心的程序輸出（在您的示例中爲打印文本流）中存在（傳遞式）數據流，那麼該輸入會影響輸出。從您的觀點來看，不會從輸入流向所需輸出的變量是無用的。

如果您只關注數據流中涉及的計算並顯示它們，則會得到通常稱爲「程序片」的內容。有（很少）商業工具可以顯示給你。Grammatech在C和C++方面享有盛譽。

有構建這樣的數據流圖的標準編譯器算法;看任何有能力的編譯器書。

由於Pachelbel指出Turing的不可行性證明，它們都受到一些限制。當你實現這樣的數據流算法時，會有一些地方不知道正確的答案;只需選擇一個。

如果您的算法選擇在某些不確定的地方回答「沒有數據流」，那麼它可能會錯過有效的數據流，並且可能會報告變量不會錯誤地影響答案。（這被稱爲「假否定」）。如果該算法具有其他一些很好的屬性，例如它在數百萬的代碼上運行速度非常快，這種偶然的錯誤可能會令人滿意。（瑣細算法簡單地說，在所有的地方「沒有數據流」，這是真的快速 :)

如果你的算法選擇回答「是的，有一個數據流」，那麼它可能會要求一些變量影響當它沒有時回答。（這被稱爲「誤報」）。

你可以決定哪個更重要;許多人在尋找問題時更喜歡誤報，因爲那樣你就必須至少查看工具檢測到的可能性。假否定意味着它沒有報告你可能關心的事情。因人而異。

這是一個起始參考：http://en.wikipedia.org/wiki/Data-flow_analysis 該頁面上的任何書籍都會非常好。我有Muchnick的書，喜歡它很多。另見本頁面：（http://en.wikipedia.org/wiki/Program_slicing）

你會發現，對於任何真正的語言來說，實現這個功能都是很大的努力。你可能更適合找到一個工具框架，它已經爲你做了大部分或全部工作。

來源

2016-01-27 04:54:14

我使用以下算法：如果變量是參數，或者它出現在表達式中的任何位置（不包括作爲LHS的賦值），則使用變量。首先，計算所有變量的使用次數。刪除未使用的變量並將其分配給未使用的變量。重複，直到沒有變量被刪除。

該算法只實現了OP的一個子集，它的效率非常低，因爲它需要多次通過。垃圾收集可能會更快，但難於編寫：我的算法只需要一個包含使用次數的變量列表。每個程序的大小都是線性的。該算法通過消除分配中結束的流尾，有效地進行有限的數據流分析。

對於我的語言來說，消除RHS中對未使用變量賦值的副作用是由語言規範強制的，因此可能不適用於其他語言。通過在內聯之前運行來降低內聯未使用的函數應用程序的成本，然後再次運行它，從而消除內聯函數的參數，從而提高了效率。

正如語言規範實用程序的一個例子，該庫構造了一個線程池併爲其指定了一個指向全局變量的指針。如果不使用線程池，則分配將被刪除，因此線程池的構造將消失。

恕我直言，編譯器優化幾乎總是啓發式，其性能比實現理論目標（如去除未使用的變量）更有效。簡單的減少是有用的，不僅因爲它們快速且易於編寫，而且因爲使用瞭解編譯器操作基礎的語言的程序員可以利用這些知識來幫助編譯器。最着名的例子可能是重構遞歸函數以將遞歸放在尾部位置：除非程序員知道編譯器可以執行尾遞歸優化，否則毫無意義的練習。

來源

2016-01-28 19:34:49 Yttrill

如何識別不影響程序輸出的變量？

回答

相關問題