程式分析與優化 - 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
  • 前言 本文將以 C# 語言來實現一個簡單的布隆過濾器,為簡化說明,設計得很簡單,僅供學習使用。 感謝@時總百忙之中的指導。 布隆過濾器簡介 布隆過濾器(Bloom filter)是一種特殊的 Hash Table,能夠以較小的存儲空間較快地判斷出數據是否存在。常用於允許一定誤判率的數據過濾及防止緩存 ...
  • 目錄 一.簡介 二.效果演示 三.源碼下載 四.猜你喜歡 零基礎 OpenGL (ES) 學習路線推薦 : OpenGL (ES) 學習目錄 >> OpenGL ES 基礎 零基礎 OpenGL (ES) 學習路線推薦 : OpenGL (ES) 學習目錄 >> OpenGL ES 轉場 零基礎 O ...
  • 「簡單有價值的事情長期堅持做」 這是成功最簡單,但也最難學的秘訣。不經過訓練,人很難意識到時間複利的威力。 仙劍奇俠傳的「十里坡劍神」和金庸群俠傳的「十級野球拳」,就是簡單的事情持之以恆反覆做,最後就有巨大的威力 唐家三少成為網文收入第一,最重要的一步是十四年從未斷日更 這樣的案例很多,一開始可能成 ...
  • 迎面走來了你的面試官,身穿格子衫,挺著啤酒肚,髮際線嚴重後移的中年男子。 手拿泡著枸杞的保溫杯,胳膊夾著MacBook,MacBook上還貼著公司標語:“我愛加班”。 面試開始,直入正題。 面試官: 看你簡歷上面寫著精通MySQL,我先問你事務的特性是什麼? 老生常談,這個還有誰不會背的嗎? 我: ...
  • 基礎知識 python是一門腳本語言,它是解釋執行的。 python使用縮進做為語法,而且python2環境下同一個py文件中不能同時存在tab和空格縮進,否則會出錯,建議在IDE中顯示縮進符。 python在聲明變數時不寫數據類型,可以type(xx)來獲取欄位的類型,然後可以int(),list ...
  • 為什麼要多線程下載 俗話說要以終為始,那麼我們首先要明確多線程下載的目標是什麼,不外乎是為了更快的下載文件。那麼問題來了,多線程下載文件相比於單線程是不是更快? 對於這個問題可以看下圖。 橫坐標是線程數,縱坐標是使用對應線程數下載對應文件時花費的時間,藍橙綠代表下載文件的大小,每個線程下載對應文件2 ...
  • 詳細講解python爬蟲代碼,爬微博搜索結果的博文數據。 爬取欄位: 頁碼、微博id、微博bid、微博作者、發佈時間、微博內容、轉發數、評論數、點贊數。 爬蟲技術: 1、requests 發送請求 2、datetime 時間格式轉換 3、jsonpath 快速解析json數據 4、re 正則表達式提... ...
  • 背景: 一般我們可以用HashMap做本地緩存,但是HashMap功能比較弱,不支持Key過期,不支持數據範圍查找等。故在此實現了一個簡易的本地緩存,取名叫fastmap。 功能: 1.支持數據過期 2.支持等值查找 3.支持範圍查找 4.支持key排序 實現思路: 1.等值查找採用HashMap2 ...
  • 目錄 一.簡介 二.效果演示 三.源碼下載 四.猜你喜歡 零基礎 OpenGL (ES) 學習路線推薦 : OpenGL (ES) 學習目錄 >> OpenGL ES 基礎 零基礎 OpenGL (ES) 學習路線推薦 : OpenGL (ES) 學習目錄 >> OpenGL ES 轉場 零基礎 O ...
  • 本章是系列文章的第八章,用著色演算法進行寄存器的分配過程。 本文中的所有內容來自學習DCC888的學習筆記或者自己理解的整理,如需轉載請註明出處。周榮華@燧原科技 寄存器分配 寄存器分配是為程式處理的值找到存儲位置的問題 這些值可以存放到寄存器,也可以存放在記憶體中 寄存器更快,但數量有限 記憶體很多,但 ...