南京大學(xué)《軟件分析》-02-IR-創(chuàng)新互聯(lián)

2 - IR

1. Compilers and Static Analyzers
2. AST vs. IR （AST：抽象語(yǔ)法樹，在語(yǔ)法分析、詞法分析之后的中間表示。）
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年的興隆臺(tái)網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。成都全網(wǎng)營(yíng)銷的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整興隆臺(tái)建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。創(chuàng)新互聯(lián)從事“興隆臺(tái)網(wǎng)站設(shè)計(jì)”,“興隆臺(tái)網(wǎng)站推廣”以來(lái)，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。

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

AST vs. IR

• AST

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

• IR - (“3-address” form)

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

Intermediate Representation (IR)

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

• 名稱
• 常量
• 編譯臨時(shí)變量

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

3AC in Real Static Analyzer: Soot

真實(shí)的三地址碼，Java的IR，Jimple in Soot。

https://github.com/Sable/soot

Loop循環(huán)

在這里面x和i在soot中，x被優(yōu)化掉了。所以在三地址碼中看到只有i?！居只蛘哒f(shuō)是，i被優(yōu)化掉了，僅存在一個(gè)x，是不是更加合理？】

Do-while 循環(huán)

Method Call

前面的前幾個(gè)變量（r0,r1,r2,r3）是Jimple翻譯器用來(lái)臨時(shí)使用的聲明的變量，和一些需要用的變量的類型。

r0聲明的是MathodCall3AC這個(gè)類型，this指向當(dāng)前這個(gè)對(duì)象。

Class

在PL中，在引用一個(gè)變量的時(shí)候，它會(huì)將變量給加載進(jìn)來(lái)。例如上圖的

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

Static Single Assignment (SSA)-可選

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

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

為什么不SSA？

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

Basic Block (BB)

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

如何設(shè)計(jì)一個(gè)算法去生成BB塊呢？

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

如何在BB基礎(chǔ)上建立CFG？

添邊。

Control Flow Graphs (CFG)

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

添邊的規(guī)則：

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

小結(jié)

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

文章名稱：南京大學(xué)《軟件分析》-02-IR-創(chuàng)新互聯(lián)
標(biāo)題URL：http://muchs.cn/article30/dsjjpo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供靜態(tài)網(wǎng)站、移動(dòng)網(wǎng)站建設(shè)、手機(jī)網(wǎng)站建設(shè)、關(guān)鍵詞優(yōu)化、營(yíng)銷型網(wǎng)站建設(shè)、網(wǎng)站營(yíng)銷

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)