<input id="ohw05"></input>
  • <table id="ohw05"><menu id="ohw05"></menu></table>
  • <var id="ohw05"></var>
  • <code id="ohw05"><cite id="ohw05"></cite></code>
    <label id="ohw05"></label>
    <var id="ohw05"></var>
  • 程序分析與優化 - 1 導論

    本章是整個課程的第一章,主要介紹了一下文章的起源,編譯器的歷史和相關概念。

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

     

    1. 導論

    1.1. 什么是DCC888

    DCC是葡萄牙語Departamento de Ciência da Computa??o的簡稱,翻譯成中文就是計算機科學學院。DCC是巴西UFMG(Federal University of Minas Gerais,中文米納斯吉拉斯州聯邦大學)下面的一個學院。DCC888是UFMG里面計算機學院的Fernado教授開通的一個課程,原名是CODE ANALYSIS AND OPTIMIZATION,也可以稱為PROGRAM ANALYSIS AND OPTIMIZATION,翻譯過來就是代碼或者程序的分析和優化,課程結合離散數據、圖論等理論知識講解了代碼的分析和優化的過程和方法,并以LLVM為例子講解了相關實踐過程。

    1.2. 為什么要學習DCC888

    各個學校針對編譯原理相關的課程很多,但編譯優化的可能比較少,結合當前主流的LLVM編譯器的理論聯系實際的可能更有限。DCC888不論從理論,還是從實踐上來說,都是難得的好教程。

    另外,計算機科學從上世紀50年代興起到今天,歷經了早期的專用計算機,到上世紀90年的PC和通用計算機的普及,當前計算機科學面臨從通用計算到各種異構計算并存的時代轉變。為了能在不同芯片上都發揮出代碼的最優性能,一方面,每個芯片設計公司需要專注對自己芯片做專有的優化;另外一方面,提供云基礎設施的集成廠商,也需要做一些通用的編譯優化,已實現跨芯片運算優化;對每個程序設計師而言,了解下層的編譯優化過程,對自己代碼實現的性能最優,也會有比較大的幫助。

    套用LLVM之父Chris Lattner的一句話就是,(現在是)計算機體系架構的黃金時代,也是編譯器的黃金時代。

    1.3. 編譯器締造者

    計算機科學發展到現在,程序員面對的編程語言從最底層的機器碼,到各種匯編語言,基礎的C語言,到各種高級語言,到現在的無代碼平臺,為了提升程序員的生產力,編程語言不斷抽象,越來越接近現實人類世界。

    相對的,物理層面,芯片本身也在不斷更新換代,新的硬件技術層出不窮,怎么讓很久之前寫的老代碼在新的芯片架構上運行,并且發揮出更高的性能,是每個芯片設計商需要特別關注的。

    編譯器就是人類世界和機器世界的橋梁,沒有編譯器編程語言做的任何優化都無法落地,更加談不上更高性能。

     

    1.4. 課程目標

    1.4.1. 了解編譯過程

    • 編譯器如何自動的將程序轉換成計算機可識別的代碼(學習編譯器的前端、中端和后端各自的職責是什么?
    • 轉換過程中要保留原始語義(如何分析代碼的語義?
    • 轉換之后的代碼在時間、空間和能耗上綜合性能更高
    • 我們尤其關注運行時間(當前代碼里面哪些代碼對最終結果是無意義的,可以刪除的?怎么通過一種新的邏輯能實現當前語義但計算量更小?

    Proebsting's Law:編譯器每隔18年可以把代碼的算力提升一倍。

    芯片硬件可以每年把算力提升60%,但編譯器實際上只能每年提升4%,也就是疊加18年才能把算力提升一倍。盡管如此,由于編譯器的優化的低成本,即使是4%,對大規模集群而言,也是非常可觀的,因為軟件優化相對于新增硬件采購的成本而言,基本上可以忽略不計。

    1.4.2. 理解程序的底層語義

    • 代碼的靜態分析技術
    • 通過靜態分析來優化性能
    • 通過靜態分析來證明程序的正確性
    • 通過靜態分析來發現代碼的bug

    代碼性能優化的技術有很多:

    • 刪除冗余拷貝
    • 常量折疊
    • Lazy Code Motion(延遲執行)
    • 寄存器分配
    • 循環展開
    • 值標記
    • 計算強度降維
    • 等等

    哪些bug是編譯器能發現的:

    • 空指針求值
    • 數組越界
    • 非法類轉換
    • 緩沖區溢出漏洞
    • 整數溢出
    • 信息泄漏

    下面代碼里面有個安全漏洞,看看大家能否找出來?

     1 void read_matrix(int* data, char w, char h) {
     2     char buf_size = w * h;
     3     if (buf_size < BUF_SIZE) {
     4         int c0, c1;
     5         int buf[BUF_SIZE];
     6         for (c0 = 0; c0 < h; c0++) {
     7             for (c1 = 0; c1 < w; c1++) {
     8                 int index = c0 * w + c1;
     9                 buf[index] = data[index];
    10             }
    11         }
    12         process(buf);
    13     }
    14 }

     

     

    1.5. 課程主要內容

    本課程的主要內容都可以在http://www.dcc.ufmg.br/~fernando/classes/dcc888 網站下載到,包括培訓膠片,實驗項目,課堂作業,參考鏈接。另外,鏈接里面還有整個課程的更新記錄和之前對課程積分體系的討論。

    課程大綱:

    1.導論
    2.控制流圖CFG
    3.數據流分析
    4.支撐數據流分析的算法
    5.柵格
    6.延遲運行
    7.基于類型的分析
    8.指針分析
    9.循環優化
    10.靜態單賦值SSA
    11.稀疏分析
    12.污染流分析
    13. 取值范圍分析
    14. 程序切片
    15. 寄存器分配
    16. 基于SSA的寄存器分配
    17. 操作語義
    18. 類型系統
    19. 機械證明
    20. 類型推導
    21. JIT編譯
    22. 修正
    23. 分支分析
    24. 自動并行

    當前最新的課程分為3部分27章,基于實用的原則,也考慮到時間成本,我們做了一些精簡,主要講其中的10章,上面被劃掉的章節本次不講,大家可以自己學習。

    1.6. 常見的編譯器的架構

    每個編譯器都有自己的前端、中端和后端,其中前端對接各種編程語言,對編程語言本身進行語法和語義分析,中端負責代碼優化,后端對接各種硬件架構,負責生成對應硬件下的可執行軟件。當前課程主要專注于中端的功能,也就是代碼本身的分析和優化。

     

     

     

    下面是一些常見的編譯器框架,大家哪些框架用的比較多?

     

     

    1.7. 完美編譯器

    完美的編譯器,基于當前的程序P,生成Popt,后者保持同樣的輸入和輸出流,但程序規模最少。

    但由于輸出很難界定,所以不可能存在完美的編譯器。例如一個永不終止的程序的最簡版本是這樣的:

    PleastL: goto L;
    但這個代碼不解決實際問題。

    所以,對于任意一個圖靈完備語言,總是有辦法產生一個更好的編譯器。

    1.8. 為什么要學習編譯器

    1.8.1. 成為更好的程序員

    gcc編譯中有很多優化選項,下圖是gcc5.4的不完全的優化選項列表:

     

     

    如果想要知道這些優化選項分別是什么含義,并且應該在什么場合使用哪些特定的優化選項,什么情況下不能打開某個優化選項?這對程序的性能優化會非常有幫助。

    通過對編譯器的了解,也可以消除一些誤解。

    有的人認為少用變量名,所有變量都復用一個名稱會減少內存占用?

    也有人認為應該少用繼承,這樣函數調用過程中的遍歷會減少?

    使用宏比函數能減少函數調用過程中的開銷?

    1.8.2. 更多的工作機會

    很多高級崗位都要求C/C++專家,熟悉計算機的理論。

    很多大型公司本身就要發布自己的編譯器版本。

    還有一些專門做編譯器或者編譯優化的公司。

    1.8.3. 更好的計算機科學家

    理解編譯器技術在geek圈也是非常酷的事。

    1.9. 能從這次課程中獲得的信息

    編譯器是計算機科學各種理論的綜合系統。

    1.9.1. 編譯器涉及的理論知識

    • 算法(圖論,集合論,動態規劃)
    • 人工智能(貪婪算法,機器學習)
    • 自動機理論(DFA確定有限自動機,解析器生成器,上下文無關語法)
    • 線性代數(柵格,定點理論,伽羅瓦連接,類型系統)
    • 體系架構(流水線管理,內存體系架構,指令集)
    • 優化(運算研究,負荷均衡,打包,調度)

    1.9.2. 動態分析

    • 打點采樣,例如gprof
    • 測試用例生成,例如Klee
    • 仿真,例如valgrind,CFGGrind
    • 編排,例如AddressSanitizer

    1.9.3. 靜態分析

    • 數據流分析
    • 基于屬性的分析
    • 類型分析

    1.10. 理論基礎

    1.10.1. 圖論

    很多地方用到圖論:

    • 控制流圖
    • 屬性圖
    • 依賴圖
    • 強連接組件圖
    • 圖的著色

    1.10.2. 不動點原理

    如果總的信息是有限的,每次迭代都會有新的信息增加的情況下,穩定的算法的迭代是否會終止?

    1.10.3. 結構歸納法

     

    1.10.4. 程序演示方法

    • 抽象語法樹
    • 控制流圖(SSA表)
    • 程序依賴圖
    • 屬性系統

    1.11. 開源社區

    • gcc
    • LLVM
    • Mozilla's Monkey
    • Ocelot
    • Glasgow Haskell 編譯器

    1.12. 會議和雜志

    • PLDI: Programming Languages Design and Implementation
    • POPL: Principles of Programming Languages
    • ASPLOS: Architectural Support for Programming Languages and Operating Systems
    • CGO: Code Generation and Optimization
    • CC: Compiler Construction
    • TOPLAS – ACM Transactions on Programming Languages and Systems

    1.13. 振奮人心的時代

    • Rust編程語言的所有者類型
    • Scala的路徑依賴類型
    • Idris的依賴類型
    • Elixir角色模型中的大規模并行
    • 量子計算
    • 張量編譯器
    • WebAssembly

    1.14. 優化編譯器簡史

    • 1951-1952年,工作在Eckert-Mauchly Computer Corporation的Grace Hopper開發的面向UNIVAC I的A0系統是第一個有文獻記載的編譯器實現。
    • 第一代優化編譯器,Fortran
    • 早期代碼優化,Frances E. Allen和John Cocke引入控制流圖,數據流分析,進程間數據流分析,工作列表算法
    • Gary Kildall,代碼優化和分析之父,數據流單調框架,信息折疊,迭代算法,不動點原理
    • Abstract Interpretation,程序的靜態行為表達
    • 寄存器分配,1981年Gregory Chaitin利用圖著色理論引入了寄存器分配算法;1999年Poletto and Sarkar將線性掃描算法引入JIT編譯器
    • SSA,80年代后期,Cytron et al. 引入SSA表格,這之后SSA經過多次改進,現在被廣泛用到幾乎所有編譯器中
    • 1988年,Olin Shivers在PLDI上引入了控制流分析法,多人創立了指針分析法
    • 類型理論

    1.15. 編譯器的未來

    • 并行計算
    • 動態語言
    • 正確性
    • 安全
    posted @ 2022-05-01 17:09  周榮華  閱讀(151)  評論(0編輯  收藏  舉報
    国产美女a做受大片观看