基于 全局代碼靜態(tài)分析 第 1 頁 共 5 頁 基于 全局代碼靜態(tài)分析 摘要 本次畢業(yè)設計的目標是改良 譯系統(tǒng)的工具鏈 兼容性 并在此基礎上設計并實現(xiàn)基于全局代碼靜態(tài)分析中使用加強的二階段鎖協(xié)議達成死鎖規(guī)避。 全局代碼靜態(tài)分析是編譯階段針對完整程序的分析，也稱作全程序靜態(tài)分析。而 本次畢業(yè)設計選擇 基于 統(tǒng)的全程序分析 是由于該系統(tǒng)的全局靜態(tài)分析 能夠脫離原程序語言而獨立于 平臺的中間表達式分析，使得其應用范圍更廣泛，移植性強 。 統(tǒng)提供了完整而成熟的中間代碼分析框架，擴展性好，性能強大，為廣大開發(fā)研究人員編寫靜態(tài)分析程序打下了堅實的 基礎。美中不足的是， 統(tǒng)中的編譯工具鏈尚在初步開發(fā)階段，其兼容性遠不如已然成熟的 得相當多的標準工程無法便利地使用 一方面， 統(tǒng)中絕大多數(shù)的分析手段均集中在過程內優(yōu)化，對于全局代碼的優(yōu)化手段相當有限。本次畢業(yè)設計的任務就是改良 譯工具鏈，提高其兼容性以及為 首先通過改善 具鏈而更容易得到工程的全局中間代碼，然后在此 間代碼上進行全局分析，將所有的加鎖解鎖信息統(tǒng)籌 規(guī)劃并修改成符合二階段鎖的具體規(guī)范的新代碼，從而實現(xiàn)死鎖規(guī)避，提高并行程序代碼的可靠性。 靜態(tài)代碼分析是諸多程序分析中最常用的方法，能夠在編譯時就發(fā)現(xiàn)程序中存在的缺陷，潛伏的問題，能夠優(yōu)化的部分以及可預測的效率等等 程序中的各種屬性特征。相對動態(tài)代碼分析，即運行時代碼分析而言，靜態(tài)代碼分析從程序的文本表現(xiàn)，也就是代碼本身出發(fā)，采取類似于三歲看到老的觀點去審視，嗅探，揣摩和把握程序。在理論基礎和運用層面上靜態(tài)代碼分析和動態(tài)代碼分析相輔相成， 都是 為 了 構建更為高效安全的程序。這其中編譯器家族所吸收集成的大量靜態(tài)分析 手法經(jīng)過多年的發(fā)展已經(jīng)日漸成熟并且不斷有新的突破?，F(xiàn)在的各大編譯器世家都把靜態(tài)代碼分析視為最重要的組成部分，把缺陷規(guī)避和深度優(yōu)化作為首要任務來設計實現(xiàn)更為強大的編譯器。當然，編譯器整合的優(yōu)化和分析畢竟還會受到編譯器自身編譯語言的部分限制，還會牽涉到不少 程序語言自身相關的依賴關系。那么作為靜態(tài)代碼分析中重要的一部分，平臺無關 分析 就 自然而然 地成為了理論研究的核心地帶，負責支撐起廣大編譯器和分析工具的跨語言能力，并可以顯著提高編譯器本身代碼的可重用性，加速編譯器的開發(fā)和演化。更進一步，有的編譯系統(tǒng)更是完全建立在平 臺無關的中間代碼之上，創(chuàng)造出以中間 代碼 為分析核心的深度優(yōu)化體系，充分擴張編譯時的分析優(yōu)化階段，最后才實現(xiàn)編譯目標代碼實現(xiàn)完整的編譯過程。這其中的佼佼者就是統(tǒng)。 統(tǒng)始于 2002 年，一直致力于中間代碼深度分析優(yōu)化。 但其中不足 的是，其編譯工具鏈仍然處于 初步開發(fā) 之中，對于許多工程項目無法實現(xiàn)兼容的編譯行為。當然這個也相當大程度上和 統(tǒng)編譯出的中間代碼不是本地可執(zhí)行代碼不無關系，造成編譯腳本的命令和實際編譯行為造成沖突。另外一點是，編譯 腳本，一般來說是 程，所依賴的編譯工具鏈是 者 G+這樣的成熟而強大的編譯工具鏈。與它們無與倫比的兼容 基于 全局代碼靜態(tài)分析 第 2 頁 共 5 頁 性能夠相提并論的編譯工具鏈 屈指可數(shù) 。這 主要是因為編譯開關 的 不兼容 而 造成 不成熟 的編譯工具鏈無法消化而只能報告錯誤 ，引起編譯終止 。由于修改工程中的編譯腳本相當費時費力而且容易出錯，我們不如改良 統(tǒng)的編譯工具鏈，提升其兼容性來適應那些工程項目，為能夠采用 個系統(tǒng)的深度優(yōu)化而做這一部分的工作。 主要的任務就是攔截并修改編譯命令，去除 具鏈所 不適應的編譯開關，修改 部分 譯工具鏈的默認行為以適應多數(shù)工程項目，然后借助于用例測試來保障編譯工具鏈的普適性。這項工作是為了 統(tǒng)能在更多的項目中展開身手，受到更少的束縛而所必需的。就目前情況而言，效果是非常明顯的，包括 大型項目也可以在不修改或者非常有限的修改編譯腳本的前提下順利編譯成中間代碼了。 有了改善的編譯工具鏈之后， 靜態(tài)代碼分析系統(tǒng)終于可以 在眾多項目中進行其計劃的深度多次分析優(yōu)化了 。既然能夠編譯出全程序中間代碼，我們自然會把目光投向于全局分析 和優(yōu)化上。 合實驗室提出了并行程序中的死鎖規(guī)避問題，這個死鎖規(guī)避的措施是在全程序的靜態(tài)分析中運用數(shù)據(jù)庫中很早提出的二階段鎖的技術，運用到靜態(tài)代碼的分析修改上從而實現(xiàn)的。并行程序的工程一般比較龐大，而 合實驗室現(xiàn)有的工具無法對于分散的源代碼進行分析， 而 全程序中間代碼分析可以被 充分利用 。那么在 們需要做的就是統(tǒng)計規(guī)劃全局的加鎖和解鎖信息，把中間代碼修改成符合二階段鎖的規(guī)范就可以實現(xiàn)這一目的。我們的目標是，所有的線程都必須只存在一個只能獲得鎖的階段，以及一個只能釋放鎖的階段，而且 所有線程獲得鎖和釋放鎖的順序都是全局規(guī)定好的，否則在并發(fā)的時候就可能出現(xiàn)循環(huán)等待的情況而死鎖。這一技術是打破了死鎖四要素之一的循環(huán)等待而達成死鎖規(guī)避的。而且把加鎖和解鎖集中之后會擴展開臨界區(qū)，會不可避免地對性能造成一定的影響。但是對于死鎖代價十分高的高可靠應用領域來說，性能上的犧牲是工程妥協(xié)，權衡利弊之后還是需要 接受 的。 至此，從 統(tǒng)的編譯工具鏈兼容整合到應用全局靜態(tài)分析這一整條流水線已經(jīng)完成， 這也是本次畢業(yè)設計所期望達到的目標。 關鍵詞： 態(tài)分析，全局代碼分析，死鎖規(guī)避 ，二階段鎖 協(xié)議 基于 全局代碼靜態(tài)分析 第 3 頁 共 5 頁 N he of is to of a a in to is at as is it to of a It of is in it a as a is is no CC a of is in So is to of a is by is to it in to of is It of at to on to of 基于 全局代碼靜態(tài)分析 第 4 頁 共 5 頁 in to of a an of a to in to to on to to on of to It to on It of of by to on is is of 002 on of is it to We it on CC + to a of CC in It an to an To up in it of is a of is to If is it on a of to to of is to to a + We to 基于 全局代碼靜態(tài)分析 第 5 頁 共 5 頁 is of to of be as in of So is to be to be in to a in to of a of a we be no on a of on HP a to to on an of in to a to to of P an to to do is is to to it in is on a to of Of in a or of be we to a on is 基于 全局代碼靜態(tài)分析 第 1 頁 共 5 頁 目 錄 第一章 緒論 局代碼靜態(tài)分析 統(tǒng) 統(tǒng)架構 擬指令集 基于 優(yōu)化 鎖和 二階段鎖 技術 靜態(tài)程序分析中的死鎖規(guī)避 二階段鎖協(xié)議和死鎖規(guī)避 二階段鎖協(xié)議在全局代碼靜態(tài)分析中的改良 章小結 二章 譯工具鏈的兼容整合 始編譯工具鏈 特性 .1 編譯開關 .2 行為 模式 的特性 特性 .1 鏈接開關 .2 行為模式 譯工具鏈的改良 具鏈改良的需求設計 命令行為 解析 部分的分析設計 命令開關解析部分的分析設計 三章 基于二階段鎖的死鎖規(guī)避 階段鎖 協(xié)議的不足和特定改良 二階段鎖協(xié)議下的死鎖 二階段鎖的全局加鎖順序 態(tài)分析 全局 統(tǒng)籌鎖 限和進一步的工作 加鎖和解鎖語句的返回值 加鎖和解鎖語句的位置和臨界區(qū)域壓縮 加鎖和解鎖語句的移動位置和程序行為改變 鎖的別名 四 章 設計原型和實驗數(shù)據(jù) 實驗數(shù)據(jù) 9基于 全局代碼靜態(tài)分析 第 2 頁 共 5 頁 1） 局靜態(tài)分析死鎖規(guī)避的原型實現(xiàn) 和實驗結果 五章 結論 考文獻 辭 于 全局代碼靜態(tài)分析 第 1 頁 共 25 頁 第一章 緒論 全局代碼靜態(tài)分析在程序分析理論研究領域歷史最為悠久，而且還能夠不斷有著新的進步和突破。 當然，局部代碼分析也是百家爭鳴，一片興旺。過程內部的優(yōu)化簡明扼要而且局部效果非常顯著，是代價小而且收效高的分析手段。和局部代碼靜態(tài)分析的焦點不同，全局代碼分析必須站在更高的起點上，從整個代碼的有機體出發(fā)，看到 全局的聯(lián)系才能對于全代碼分析優(yōu)化產(chǎn)生更加具有影響力的全面效果。就算是再優(yōu)秀的過程內部優(yōu)化，如果僅僅從程序的片段出發(fā)，看不到別處，必然視野受到了限制而致使其無法做出更進一步的考慮，然而它們欠缺的縱觀全局的能力就是全局代碼分析的著眼點和戰(zhàn)略定位。 全局代碼靜態(tài)分析 其中一部分研究領域是依賴于程序語言設計本身的，并將靜態(tài)分析研究和程序語言設計緊密結合，致力于創(chuàng)造出更優(yōu)良的程序語言和分析設計。另一部分反其道而行之，相對當今程序設計語言的多樣性和多元化發(fā)展趨勢而選擇了能夠適應更多平臺的語言無關分析。當分析手段和程序語言 本身脫離了緊密的結合之后，雖然可能會造成一部分針對某些程序語言的特效分析手法沒有施展的空間，但是類似于光譜藥和特效藥的功能特點一般，夸平臺語言的全局代碼靜態(tài)分析仍然是 穩(wěn)穩(wěn)當當?shù)卣紦?jù)了程序分析方法的一席之地。 統(tǒng) 是中間代碼分析優(yōu)化框架的佼佼者。它的 全名叫做低層虛擬機，聽上去比較像虛擬技術。但是其實低層虛擬機是 統(tǒng)中核心的中間代碼所依賴的低層 指令集架構 （ ， 統(tǒng)本身是為了把程序轉換成其特有的中間代碼而進行平臺無關的深度分析優(yōu)化。在 統(tǒng)里面雖然不乏全局分析和優(yōu)化，但是從整個 系統(tǒng)的優(yōu)化分析工具的組成來看，過程內部優(yōu)化仍然占了大多數(shù)。全局代碼分析也是 統(tǒng)支持良好的一種分析手段， 在 合實驗室的提案下，基于 全局死鎖規(guī)避分析應運而生。 局代碼靜態(tài)分析 全局代碼靜態(tài)分析問世已經(jīng)很久了，其難度和立足點之高讓很多研究 進展緩慢。 由于現(xiàn)代程序語言 為了突出工程性，減少邏輯復雜度，逼近人性化等等其他富有影響力的因素而采取了諸如強化面向對象設計，模塊化，構件化，提升抽象度的手段來削弱編寫程序的人員成本。但是這個工程決策的負面影響必然是牽扯到了運行時的程序性能。程序的龐大 化和復雜度上升很大程度上增加了編譯器方面的壓力，造成了很多優(yōu)秀的分析優(yōu)化方法無法在零散的程序片段上施展。全局代碼分析在這方面受到的壓力是最明顯的。除了上述工程人力成本方面的考慮，還有各種因素會影響著全程序分析難以實現(xiàn)。比如分布式程序通過遠距離信息交流完成功能，但是各個組件之間僅存有限的接口可以訪問，出于安全以及設計的要求考慮，它們互相之間并不了解對方內部運行的機制。 分布式系統(tǒng)的全局優(yōu)化只能借助優(yōu)秀的架構師來統(tǒng)籌，全局代碼在這類系統(tǒng)中是無法觸及的。又或者，含有第三方外包軟件的應用程序越來越多，而第三方所開發(fā)的 軟件庫不一定是可見的，也會出現(xiàn)類似于組件之間可見度非常低的情況。那么對于全代碼分析來說，就算運用技術手段使得第三方庫繞過分析的范圍，或者部分進行分析，也還是會出現(xiàn)一部分的黑盒從而無法達成最理想的效果。 即便如此，近年來多核技術的發(fā)展造成了并行計算領域的加速進化，而傳統(tǒng)的過程內部優(yōu)化是難以勝任并行程序復雜的并發(fā)關系分析的。那么全局代碼分析由此機會重新得到了 基于 全局代碼靜態(tài)分析 第 2 頁 共 25 頁 充分的重視而生機勃勃。并行程序之間的協(xié)議和行為只能夠在過程間分析優(yōu)化中取得效果，不僅僅是增強程序的并行性 這類應用更是需要站在全代碼的角度進行分析才能更加精準 地把握并行線程的互動 ，例如在全局尋找符合代碼交換律的代碼段 1等提高程序并行率的研究 ，死鎖嗅探和規(guī)避也需要如此 。 于是，全局代碼分析在計算機界推進并行計算技術的同時得到了進一步的關注，能夠綻放出新的光芒。 統(tǒng) 統(tǒng)是一套獨特的編譯基礎架構，它支持多層次（ 化 2。這個設計的初衷是為了能夠支持深度的過程間優(yōu)化和配置驅動（ 化，并且在這過程中保持商業(yè)強度的性能。 虛擬指令集是整個系統(tǒng)的核心，它既有低層的指令特征，又有高級的 類型信息，使得低層代碼的變換優(yōu)化和高層的激進的過程間優(yōu)化同時成為可能。 譯框架也同時被設計和實現(xiàn)出來，并且成為了諸多學術研究的孵化地。 統(tǒng)架構 統(tǒng)本身從多層次深度優(yōu)化的出發(fā)點而設計，意圖讓非常具有侵略性的優(yōu)化貫穿整個程序的生命周期，并且同時保持優(yōu)化的實用性。 傳統(tǒng)的編譯器把編譯程序分開為編譯和鏈接兩個階段：首先編譯單個的源程序文件，產(chǎn)出目標的 件；然后，通過鏈接器把相互關聯(lián)的 件有組織地拼接成一個整體的目標可執(zhí)行代碼。如果系統(tǒng)足夠簡單的話，基本上大部分的工作都 是由編譯器完成的，鏈接器頂多只需要按照要求填充符號標記和相關地址再拼接文件就可以了。 然保留了這個傳統(tǒng)的編譯器鏈接器分工，是為了將源文件互不干涉地被編譯這個好處留著。但是編譯好的源代碼并不是直接變成本地機器所熟識的可執(zhí)行代碼，而是編譯成 擬指令集。 鏈接器把虛擬指令集連接起來， 運行優(yōu)化步驟，然后才會把虛擬指令集轉換成本地可執(zhí)行代碼。這么做是為了 夠運行復雜的全局優(yōu)化，而這對于整個優(yōu)化系統(tǒng)是至關重要的。 在優(yōu)化過程中有一部分的優(yōu)化變換代價十分高昂，不適合在運行時出現(xiàn)，所以當機 器處于閑時就能利用線下的優(yōu)化器運行這些復雜的優(yōu)化，改善目標代碼的性能，在下一次運行目標代碼之前做好事先準備。 統(tǒng)的運行時優(yōu)化避免了傳統(tǒng) 運行時優(yōu)化的兩個弊端：一是它采集的信息主要是從開發(fā)者方面得到的，而不是最終用戶；二是開發(fā)者很少真的用到采集來的信息。 且開發(fā)者從中也不需要額外的工作就可以完成優(yōu)化工作。 擬指令集 統(tǒng)和其他的系統(tǒng)相比，很重要一個區(qū)別就是它使用的代碼表現(xiàn)形式。為了達到期望的深度優(yōu)化目標，其代碼表 現(xiàn)形式必須要具有低層的容易產(chǎn)生變換的簡單指令，又需要高層的類型信息等等來支持 鏈接時和鏈接后的深度優(yōu)化。 擬指令集代表了一個虛擬的架構，其中組成的元素是普通處理器內最關鍵并且常用的指令，但是避開了特定機器類型的限制，例如物理寄存器，流水線，底層調用規(guī)范和陷阱等。 擬指令集采用三地址代碼，是 構和語言無關編譯器長年使用的代碼類型。從相貌上看來，三地址代碼具有小型，操作正交等特性，和機器碼非常相像，而且可以很容易被壓縮以減小 代碼體積。而且 用 態(tài)單定義）形式作為 代碼的主要形式。 式規(guī)定每個變量定義恰好一次，并且所有的引用全被該次定義所影響。 式能夠大大簡化許多數(shù)據(jù)流分析。 取強類型系統(tǒng)，每個 量和內存分配都是擁有類型標記的，而且所有的操作都是按照嚴格的類型規(guī)則運行的。這個信息使得非常廣泛的高級變換能夠在低級代碼 基于 全局代碼靜態(tài)分析 第 3 頁 共 25 頁 上發(fā)生。而且嚴格類型也致使一致性檢查能夠探測出各中的類型不匹配錯誤。 顯示內存分配和統(tǒng)一內存模型也是一大特點。牽涉到內存的優(yōu)化通常能讓編譯器十分頭疼，顯示的內存分配可以把內存分配信息更好地傳遞給編譯器，所以分配內存的指令 被加入了虛擬指令集中。 指令集中也包含了異常處