程式分析與優化 - 3 數據流分析

来源:https://www.cnblogs.com/zhouronghua/archive/2022/05/17/16279465.html
-Advertisement-
Play Games

本章是系列文章的第三章,介紹了基於數據流分析的一些優化方法。包括生命周期管理,可獲得表達式,常用表達式,可達性定義。本章在介紹這4中分析方法的基礎上提取出它們的通用模式。這一章形式化的內容比較多,看的時候有點燒腦,最好自己手工推導一下,要不然基本上看不懂:) 本文中的所有內容來自學習DCC888的學 ...


本章是系列文章的第三章,介紹了基於數據流分析的一些優化方法。包括生命周期管理,可獲得表達式,常用表達式,可達性定義。本章在介紹這4中分析方法的基礎上提取出它們的通用模式。這一章形式化的內容比較多,看的時候有點燒腦,最好自己手工推導一下,要不然基本上看不懂:)

 

本文中的所有內容來自學習DCC888的學習筆記或者自己理解的整理,如需轉載請註明出處。周榮華@燧原科技

3.1 生命周期

對下麵的程式:

 1 var x,y,z;
 2 x = input;
 3 while (x > 1) {
 4     y = x / 2;
 5     if (y > 3)
 6         x = x - y;
 7     z = x - 4;
 8     if (z > 0)
 9         x = x / 2;
10     z = z - 1;
11 }
12 output x;

 

 

可以生成控制流圖如下:

 

 

 

圖對應dot文件內容:

1 digraph "CFG for 3.1"{
2     rankdir=LR
3     "var x,y,z" -> "x = input" -> "x > 1" -> {"output x" "y = x / 2"}
4     "y = x / 2" -> "y > 3" -> {"x = x - y" "z = x - 4"}
5     "x = x - y" -> "z = x - 4" -> "z > 0" -> {"x = x / 2" "z = z - 1"}
6     "x = x / 2" -> "z = z - 1" -> "x > 1"

但僅有控制流分析,還有很多問題無法解決。第一個問題是電腦需要知道這個程式需要多少寄存器,甚至需要控制流執行到某條邊的時候,需要多少個寄存器?有什麼通用的方法能用來回答這個問題?

活躍變數:如果程式在執行點需要使用某個變數,並且該使用不是定義類的使用,那麼程式需要在緊靠該執行點之前就要能訪問這個變數,這種變數稱為活躍變數(alive)。

對每個程式執行點p,我們定義2個集合:

  • IN是在緊靠p之前活著的變數集合。
  • OUT是在緊靠p之後或者的變數集合。

活躍變數的數據流等式:

對 p : v = E

IN(p) = ( OUT(p) \ {v} ) ∪ vars(E)

OUT(p) = ∪ IN(ps), ps ∈ succ(p)

IN(p) :p之前的活躍的變數集合

OUT(p) :p之後的活躍的變數集合

vars(E) :表達式E中出現的所有變數的集合

succ(p) :控制流圖中p的所有後繼的集合

對CFG上的每個點,變數上面2個等式,直到2個集合不再變化,我們就得到了任意點的變數生命周期。

這個等式最早是Albeit用prolog實現的:

 1 diff([], _, []).
 2 diff([H|T], L, LL) :- member(H, L), diff(T, L, LL).
 3 diff([H|T], L, [H|LL])
 4 :- \+member(H, L), diff(T, L, LL).
 5 union([], L, L).
 6 union([H|T], L, LL) :- member(H, L), union(T, L, LL).
 7 union([H|T], L, [H|LL])
 8 :- \+ member(H, L), union(T, L, LL).
 9 in(1, L) :- out(1, Out), diff(Out, [y], L).
10 in(2, L) :- out(2, Out), diff(Out, [x], L).
11 in(3, L) :- out(3, Out), diff(Out, [z], Diff),
12 union(Diff, [x, y], L).
13 in(4, L) :- out(4, Out), union(Out, [z], L).
14 out(1, L) :- in(2, L).
15 out(2, L) :- in(3, L).
16 out(3, L) :- in(4, L).
17 out(4, []).

 

 

上面的控制流圖,給每條邊加上變數的生命周期之後的結果的dot表達是這樣的:

 1 digraph "CFG for 3.2"{
 2     "start" [bgcolor=black color=red style=filled]
 3     "start" -> "var x,y,z" [xlabel="{}"]
 4     "var x,y,z" -> "x = input" [xlabel="{}"]
 5     "x = input" -> "x > 1" [xlabel="{x}"]
 6     "x > 1" -> "output x" [xlabel="{x}"]
 7     "x > 1" -> "y = x / 2" [xlabel="{x}"]
 8     "y = x / 2" -> "y > 3" [xlabel="{x,y}"]
 9     "y > 3" -> "x = x - y" [xlabel="{x,y}"]
10     "y > 3" -> "z = x - 4" [xlabel="{x}"]
11     "x = x - y" -> "z = x - 4" [xlabel="{x}"]
12     "z = x - 4" -> "z > 0" [xlabel="{x,z}"]
13     "z > 0" -> "x = x / 2" [xlabel="{x,z}"]
14     "z > 0" -> "z = z - 1" [xlabel="{x,z}"]
15     "x = x / 2" -> "z = z - 1" [xlabel="{x,z}"]
16     "z = z - 1" -> "x > 1" [xlabel="{x}"]
17     "output x" -> "end" [xlabel="{}"]
18     "end" [bgcolor=black color=red style=filled]
19 }

 

 

dot文件生成的svg圖是這樣的:

 

 

 

3.2 可訪問表達式(Available Expressions)

可訪問表達式:一個表達式E在程式點p是可訪問表達式,當且僅當:

    • E在p之前是可訪問表達式,
    • 並且E的任意一個變數在p未重新定義;

或者:

    • E在p處被使用,
    • E的所有變數沒有在p處重新定義。

可訪問表達式的數據流等式:

對 p : v = E

IN(p) = ∩OUT(ps), ps ∈ pred(p)

OUT(p) = ( IN(p) ∪ {E}) \ {Expr(v)}

IN(p) :p之前的可訪問表達式集合

OUT(p) :p之後的可訪問表達式集合
pred(p) :控制流圖中p的所有前驅的集合

Expr(v) :使用變數v的所有表達式的集合

可訪問表達式的例子:

 

 

3.3 常用表達式(Very Busy Expressions)

常用表達式:當表達式E從p開始到程式結束前的每條路徑上都會計算,則稱表達式E在p處是常用表達式。形式化描述就是:

    • E在p之後是常用表達式,
    • 並且E的所有變數並沒有在p處重新定義;

或者:

    • p處使用了表達式E。

常用表達式的數據流等式:

對 p : v = E

IN(p) = ( OUT(p) \ {Expr(v)}) ∪ {E}

OUT(p) = ∩ IN(ps), ps ∈ succ(p)

IN(p) :p之前的常用表達式集合

OUT(p) :p之後的常用表達式集合

succ(p) :控制流圖中p的所有後繼的集合

 

常用表達式的例子:

 

 

安全的代碼修改(Safe Code Hositing):如果某個修改,在任何場景下都不會導致程式做額外的工作,該修改就是安全的修改。

3.4 可獲得性定義(Reaching Definitions)

可獲得性定義:如果控制流圖上存在一條邊從程式點p到程式點p‘,並且這條邊上沒有任意一個結點對變數v重新定義,則稱為p在程式點p定義的變數v在程式的p'可獲得。

可獲得性的推導:變數v在程式點p可獲得當且僅當:

    • 在p之前v可獲得,
    • 並且v在p處沒有重新定義;

或者

    • p處定義了變數v。

可獲得性定義的數據流等式:

對 p : v = E

IN(p) = ∪ OUT(ps), ps ∈ pred(p)

OUT(p) = ( IN(p) \ {defs(v)} )∪ {(p, v)}

IN(p) :p之前的可獲得性定義集合

OUT(p) :p之後的可獲得性定義集合
defs(v) :程式中所有v的定義集合

(p, v): p處定義的v

可獲得性定義的例子:

 

 

3.5 MONOTONE框架

3.5.1 幾種數據流分析方法的比較

本章學到了四種數據流分析方法:

 

 

數據流分析按彙總方向有正向分析和反向分析兩種。

正向分析是從程式的起始點往結束點方向分析,每次輸入都是通過這之前所有的輸出通過運算(交集或者並集)得到,輸出是基於p點的輸入和p點的表達式計算出來。例如本章講到的可獲得性定義和可訪問表達式的分析。

反向分析相反,需要從程式的結束點往起始點分析,分析方向和數據流動的方向相反。每次先計算輸出,每個p的輸出都是這之後的輸入通過運算得到,輸入是基於p點的輸出和p點的表達式計算出來。例如本章講到的生命周期分析和常用表達式分析。

按彙總方法有可以分為確定性分析(MUST,必須)和可能性分析(MAY,可以)2種。區別在於集合從多點匯聚到一個點的時候應該使用交集還是並集。

3.5.2 轉換函數

數據流分析過程需要對程式進行一些翻譯,數據流分析不能直接分析程式的具體語義(要不然就永遠分析不完了),而是分析一種抽象的語義。轉換函數就是抽取程式的抽象語義的函數。

正向分析的轉換函數是通過輸入生成輸出的函數:

OUT[s] = fs(IN[s])

相反,反向分析的轉換函數是通過輸出計算輸入的函數:

IN[s] = fs(OUT[s])

3.5.3 合併函數

合併函數確定多條岔路匯聚成一條路或者一條路分成多條岔路時的處理過程。

 

 

給定一個轉換函數,一個合併函數,和一個特定的初始化的IN和OUT的集合,能夠證明它必然導致抽象翻譯的正常結束。

數據流分析的過程就是按上面的框架找到一個轉換函數,和一個合併函數,並給定一個IN和OUT的初始集合。

3.5.4 數據流分析簡史

  • Frances Allen got the Turing Award of 2007. Some of her contributions touch dataflow analyses.
  • Allen, F. E., "Program Optimizations", Annual Review in Automatic Programming 5 (1969), pp. 239-307
  • Allen, F. E., "Control Flow Analysis", ACM Sigplan Notices 5:7 (1970), pp. 1-19
  • Kam, J. B. and J. D. Ullman, "Monotone Data Flow Analysis Frameworks", Actal Informatica 7:3 (1977), pp. 305-318
  • Kildall, G. "A Unified Approach to Global Program Optimizations", ACM Symposium on Principles of Programming Languages (1973), pp. 194-206

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 本期 OpenHarmony 開發者故事,我們採訪了 OpenHarmony 啟動子系統的負責人,OpenHarmony PMC 委員會推舉的“代碼貢獻月度之星”——熊磊。 ...
  • 5月17日,2022年搜狐科技峰會成功舉辦,峰會匯聚各界大咖,共同探討AI 技術的深入應用以及行業數字化的發展趨勢。華為終端雲服務應用生態BU總裁望岳發表題為《使能AI智慧體驗,共建創新應用生態》主題演講。 望岳表示,經過多年的發展迭代,華為移動服務HMS生態已成為全球第三大移動應用生態:截止今天, ...
  • 5月18日(周三)晚上19:00,第一期戰“碼”先鋒直播,我們邀請到了潤和資深軟體開發工程師趙海鵬老師,在直播間與大家分享《如何成為一名優秀的OpenHamrony 貢獻者?》 ...
  • HUAWEI Developer Day(簡稱HDD),是華為開發者聯盟與廣大開發者深度交流的平臺。圍繞移動終端的最新技術和產品形態,持續向廣大開發者傳遞華為終端的最新產品和開放服務能力,結合最新的行業發展趨勢,攜手開發者共同打造面向終端消費者的卓越用戶體驗。 5月24日18:50-21:05,HD ...
  • 本文對 CSS 中有關大小的四種自適應大小表現進行瞭解釋與區別,它們分別是 fit-content, min-content, max-content, fill-available。相對而言,本文較為嚴謹,即儘量地無遺漏、無歧義。在嚴謹的同時,也做到儘可能通俗易懂。 ...
  • BOM BOM:Broswer object model,即瀏覽器提供我們開發者在javascript用於操作瀏覽器的對象。 BOM就是瀏覽器對象模型 BOM提供了一些獨立於內容頁面與瀏覽器視窗進行交互的對象介面 BOM的核心是window對象,所以window一般在書寫時是可以省略的. BOM其實 ...
  • 完整項目地址: [email protected]:xsk-walter/myPromise.git // index.js /* 1. Promise 就是一個類 在執行這個類的時候 需要傳遞一個執行器進去 執行器會立即執行 2. Promise 中有三種狀態 分別為 成功 fulfilled 失敗 r ...
  • 前端周刊:2022-7 期 前端開發 videojs-plugin-source-switcher videojs 視頻源切換插件 前端工具箱-免費的 SVG 圖像和圖標 所有內容均在 Creative Commons CC0 下發佈 es6-模塊與-commonjs-模塊的差異 CommonJS ...
一周排行
    -Advertisement-
    Play Games
  • Dapr Outbox 是1.12中的功能。 本文只介紹Dapr Outbox 執行流程,Dapr Outbox基本用法請閱讀官方文檔 。本文中appID=order-processor,topic=orders 本文前提知識:熟悉Dapr狀態管理、Dapr發佈訂閱和Outbox 模式。 Outbo ...
  • 引言 在前幾章我們深度講解了單元測試和集成測試的基礎知識,這一章我們來講解一下代碼覆蓋率,代碼覆蓋率是單元測試運行的度量值,覆蓋率通常以百分比表示,用於衡量代碼被測試覆蓋的程度,幫助開發人員評估測試用例的質量和代碼的健壯性。常見的覆蓋率包括語句覆蓋率(Line Coverage)、分支覆蓋率(Bra ...
  • 前言 本文介紹瞭如何使用S7.NET庫實現對西門子PLC DB塊數據的讀寫,記錄了使用電腦模擬,模擬PLC,自至完成測試的詳細流程,並重點介紹了在這個過程中的易錯點,供參考。 用到的軟體: 1.Windows環境下鏈路層網路訪問的行業標準工具(WinPcap_4_1_3.exe)下載鏈接:http ...
  • 從依賴倒置原則(Dependency Inversion Principle, DIP)到控制反轉(Inversion of Control, IoC)再到依賴註入(Dependency Injection, DI)的演進過程,我們可以理解為一種逐步抽象和解耦的設計思想。這種思想在C#等面向對象的編 ...
  • 關於Python中的私有屬性和私有方法 Python對於類的成員沒有嚴格的訪問控制限制,這與其他面相對對象語言有區別。關於私有屬性和私有方法,有如下要點: 1、通常我們約定,兩個下劃線開頭的屬性是私有的(private)。其他為公共的(public); 2、類內部可以訪問私有屬性(方法); 3、類外 ...
  • C++ 訪問說明符 訪問說明符是 C++ 中控制類成員(屬性和方法)可訪問性的關鍵字。它們用於封裝類數據並保護其免受意外修改或濫用。 三種訪問說明符: public:允許從類外部的任何地方訪問成員。 private:僅允許在類內部訪問成員。 protected:允許在類內部及其派生類中訪問成員。 示 ...
  • 寫這個隨筆說一下C++的static_cast和dynamic_cast用在子類與父類的指針轉換時的一些事宜。首先,【static_cast,dynamic_cast】【父類指針,子類指針】,兩兩一組,共有4種組合:用 static_cast 父類轉子類、用 static_cast 子類轉父類、使用 ...
  • /******************************************************************************************************** * * * 設計雙向鏈表的介面 * * * * Copyright (c) 2023-2 ...
  • 相信接觸過spring做開發的小伙伴們一定使用過@ComponentScan註解 @ComponentScan("com.wangm.lifecycle") public class AppConfig { } @ComponentScan指定basePackage,將包下的類按照一定規則註冊成Be ...
  • 操作系統 :CentOS 7.6_x64 opensips版本: 2.4.9 python版本:2.7.5 python作為腳本語言,使用起來很方便,查了下opensips的文檔,支持使用python腳本寫邏輯代碼。今天整理下CentOS7環境下opensips2.4.9的python模塊筆記及使用 ...