2 - IR

1. Compilers and Static Analyzers
2. AST vs. IR （AST：抽象語法樹，在語法分析、詞法分析之后的中間表示。）
3. IR: Three-Address Code (3AC)
4. 3AC in Real Static Analyzer: Soot
5. Static Single Assignment (SSA)
6. Basic Block (BB)
7. Control Flow Graphs (CFG)

Compilers

輸入為 SourceCode

10年的興隆臺網(wǎng)站建設經(jīng)驗，針對設計、前端、開發(fā)、售后、文案、推廣等六對一服務，響應快，48小時及時工作處理。成都全網(wǎng)營銷的優(yōu)勢是能夠根據(jù)用戶設備顯示端的尺寸不同，自動調(diào)整興隆臺建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設計，從而大程度地提升瀏覽體驗。創(chuàng)新互聯(lián)從事“興隆臺網(wǎng)站設計”,“興隆臺網(wǎng)站推廣”以來，每個客戶項目都認真落實執(zhí)行。

• Scanner - 詞法分析-Lexical Analysis - 檢查每一個單詞（不一定是英文單詞）- 里面用到了正則表達式（Regular Expression）- 最后生成Tokens作為語法分析的輸入。
• Parser - 語法分析 - Syntax Analysis - 檢查單詞之間的語法規(guī)則 - Context-Free Grammar（上下無關(guān)語法）- 最后生成AST（抽象語法樹）。
• Type Checker - 語義分析 - Sementic Analysis - 檢查類型處理合理 - Attribute Grammar - 最后生成Decorated AST（裝飾的抽象語法樹）。
• Translator - 翻譯 - 最后生成IR（一般是指3D碼）。
• Code Generator - 代碼生成器 - 最后生成機器碼。

AST vs. IR

• AST

  • 表達層次比較高，與語法樹非常貼合
  • 依賴于不同的語言
  • 適合快速的類型檢查
  • 在控制流信息流分析

• IR - (“3-address” form)

  • 表達層次比較低，與機器碼相近，與匯編相近
  • 與語言相關(guān)性不強
  • 壓縮且簡潔
  • 包含控制流信息
  • 經(jīng)常被考慮作為靜態(tài)分析的基礎
    

Intermediate Representation (IR)

3-Address Code 三地址碼。引入臨時變量，一般包含三個信息：

• 名稱
• 常量
• 編譯臨時變量

每種指令都有他們自己的三地址碼。

3AC in Real Static Analyzer: Soot

真實的三地址碼，Java的IR，Jimple in Soot。

https://github.com/Sable/soot

Loop循環(huán)

在這里面x和i在soot中，x被優(yōu)化掉了。所以在三地址碼中看到只有i。【又或者說是，i被優(yōu)化掉了，僅存在一個x，是不是更加合理？】

Do-while 循環(huán)

Method Call

前面的前幾個變量（r0,r1,r2,r3）是Jimple翻譯器用來臨時使用的聲明的變量，和一些需要用的變量的類型。

r0聲明的是MathodCall3AC這個類型，this指向當前這個對象。

Class

在PL中，在引用一個變量的時候，它會將變量給加載進來。例如上圖的

public static void()
{= 3.14;
    return;
}

Static Single Assignment (SSA)-可選

SSA是IR里面一種經(jīng)典的轉(zhuǎn)化模式。

• 給每一個定義一個新的命名。
• 傳遞新的變量名到后續(xù)的式子使用。
• 一個變量只有一個精確的定義。
  
  
  以上PPT，針對x0和x1會引入φ（phi-function）這個函數(shù)進行統(tǒng)合。
  SSA有典型的特征：
• 每一個變量（variable）都有自己的一個定義。
• 如果要用多重的x，會引入一個φ函數(shù)。

為什么不SSA？

• 可能太多φ函數(shù)。

Basic Block (BB)

• 一個BB的入口一定是第一條指令。
• 一個BB的出口一定是最后一條指令。
• 滿足以上兩個條件之后的大的指令集合。

如何設計一個算法去生成BB塊呢？

• 確定每個BB的入口（Leader）
  • 程序當中的第一個指令是入口（Leader）
  • 任何跳轉(zhuǎn)指令（jump/goto）的目標指令（target）
  • 緊跟在所有跳轉(zhuǎn)指令的后面一條指令
• 建立BB
  • 一個BB包括一個入口（leader）和Leader后面所有跟隨的指令，知道遇到下一個Leader。

如何在BB基礎上建立CFG？

添邊。

Control Flow Graphs (CFG)

三地址碼最終還是要轉(zhuǎn)化為控制流圖CFG。

添邊的規(guī)則：

• CFG的結(jié)點是BB。
• 滿足跳轉(zhuǎn)指令：從A的結(jié)尾到B的開始，添邊。
• 不滿足跳轉(zhuǎn)指令的（緊接在跳轉(zhuǎn)指令后的一條指令）需要添加一條邊。
• B緊接著A之后，添邊。
  • 除非A的最后一條指令是一條無條件跳轉(zhuǎn)指令（jmp/goto)
• 將跳轉(zhuǎn)到塊替換跳轉(zhuǎn)到指令是合理的。
• 一個BB可以有多個前驅(qū)，也可以有多個后繼。
• 最后需要添加兩個結(jié)點：Entry和Exit。
  • 入邊（Entry）只有一個
  • 出邊（Exit）可以有多個

小結(jié)

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁題目：南京大學《軟件分析》-02-IR-創(chuàng)新互聯(lián)
網(wǎng)頁地址：http://weahome.cn/article/dsjjpo.html