如何利用Python實(shí)現(xiàn)簡單C++程序范圍分析
1. 實(shí)驗(yàn)說明
問題要求：針對靜態(tài)單賦值（SSA）形式的函數(shù)中間代碼輸入，輸出函數(shù)返回值的范圍
實(shí)現(xiàn)思路： 基本根據(jù) 2013年在CGO會議上提出的“三步法”范圍分析法加以實(shí)現(xiàn)[3]，求得各個(gè)變量的范圍
算法優(yōu)勢：空間復(fù)雜度和時(shí)間復(fù)雜度都是 O(n)，效率高
算法瓶頸： “三步法”的功能存在較大局限，它只能分析各個(gè)變量的最大范圍，對活躍變量只做了最簡單的考慮，因此最終得到的范圍比較不準(zhǔn)確，往往只能得到范圍的一個(gè)界
2. 項(xiàng)目使用
python main.py （ssa文件路徑在main.py中設(shè)置）
不需要安裝任何庫。
3. 算法原理
簡單概括：采用三步法（2013年在CGO會議上提出）
3.1 構(gòu)建CFG
代碼：\src\eSSAConstraintGraph.py; \src\structure.py
功能：解析SSA，構(gòu)建CFG。
由于函數(shù)之間存在調(diào)用關(guān)系，因此首先把SSA劃分成不同的函數(shù)的SSA，再分別構(gòu)建CFG。CFG中保留了每一個(gè)函數(shù)的語句、Block之間的關(guān)系，為下一步構(gòu)建Constraint Graph打基礎(chǔ)。
CFG的結(jié)構(gòu)如下：
# CFG類 ? ? ? class CFG: ? ? def __init__(self): ? ? ? ? self.name = '' ? ? ? ? self.Blocks = [] ? ? ? ? self.Edges = [] ? ? ? ? self.Arguments = []
3.2 構(gòu)建Constraint Graph
代碼：\src\eSSAConstraintGraph.py
三步法的前提是構(gòu)建Constraint Graph。數(shù)據(jù)結(jié)構(gòu)如下。在這一步中，我用自己定義的數(shù)據(jù)類型MyNode來表示一條Constraint。
# Constraint Graph類 ? ? ? class ConstraintGraph: ? ? def __init__(self, cfg): ? ? ? ? self.MyNodes = []?? ??? ??? ?#基本節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)是一個(gè)Constraint ? ? ? ? self.MyConditions = []?? ??? ?#用于后面E-SSA Constraint Graph補(bǔ)充條件 ? ? ? ? self.cfg = cfg?? ??? ??? ?? ? ? ? ? self.Arguments = []?? ??? ??? ?#輸入?yún)?shù) ? ? ? ? self.returnName = ''?? ??? ?#輸出參數(shù) # MyNode : Constraint Graph的節(jié)點(diǎn)，也就是保存變量范圍的地方 class MyNode: ? ? def __init__(self, t= "", name = "", ?args = [], result = [], fromBlock = 0, Statement = ''): ? ? ? ? self.type = t ?? ??? ??? ?#節(jié)點(diǎn)類型：leave 葉節(jié)點(diǎn)存放范圍和值 #op運(yùn)算符 #var變量名 ? ? ? ? self.name = name.strip() ?#節(jié)點(diǎn)名稱：運(yùn)算名稱，或變量名稱 ? ? ? ? self.args = args?? ?#參數(shù)，一個(gè)節(jié)點(diǎn)是另一個(gè)節(jié)點(diǎn)的argument，意味著二者之間有邊相連 ? ? ? ? self.result = result ? ? ? ?#被用到哪，一個(gè)節(jié)點(diǎn)是另一個(gè)節(jié)點(diǎn)的result，意味著二者之間有邊相連 ? ? ? ? self.Conditions = [] ? ? ? ?#約束條件， 在后面E-SSA Constraint Graph中補(bǔ)充條件 ? ? ? ? self.fromBlock = fromBlock ?#在CFG的哪個(gè)Block中定義的 ? ? ? ? self.Statement = Statement ?#在SSA中的哪條Statement中 ? ? ? ? self.Range = Range()?? ??? ?#節(jié)點(diǎn)范圍 ? ? ? ? self.size = '' ? ? ? ? self.input = False # Range由兩個(gè)Bound組成? class Range: ? ? def __init__(self ): ? ? ? ? self.lowBound = Bound() ? ? ? ? self.highBound = Bound() # Bound由值和類型組成 class Bound: ? ? def __init__(self): ? ? ? ? self.value = 'None' ? ? ?# inf 最大值 ； -inf 最小值; None 未設(shè)置； Not Exists 不存在 ? ? ? ? self.size = 'None' ? ? ? #邊界是 int or float
需要注意的是，在解決兩個(gè)函數(shù)之間的調(diào)用關(guān)系時(shí)，將被調(diào)用的函數(shù)**內(nèi)聯(lián)進(jìn)原函數(shù)**。我將被調(diào)用的函數(shù)的所有變量名都加入相應(yīng)的后綴，比如`foo`調(diào)用`bar`函數(shù)，那么`bar`中的變量`i_1`將被更名保存為`i_1#bar$1`，其中#是變量原名和后綴分割符，$是函數(shù)名和一個(gè)隨機(jī)數(shù)的分割符，\$的作用是為了區(qū)分多次調(diào)用同一個(gè)函數(shù)的情況。
3.3 構(gòu)建E-SSA Constraint Graph
代碼：`\src\eSSAConstraintGraph.py`
這一步用于解決條件的添加。諸如`if (i_2 < j_3)`這樣的條件。在MyNode節(jié)點(diǎn)類型中，我設(shè)置了Conditions結(jié)構(gòu)用于保存條件。Condition的數(shù)據(jù)結(jié)構(gòu)如下：
Class Description : Constraint Graph中的條件，附加在MyNode中
class MyCondition:
? ? def __init__(self, condition, index):
? ? ? ? self.condition = condition
? ? ? ? self.arg1 = re.sub("\(.*\)", "",condition.split()[0].strip())
? ? ? ? self.arg2 = re.sub("\(.*\)", "",condition.split()[2].strip())
? ? ? ? self.op = condition.split()[1].strip()
? ? ? ? self.index = index其中，arg1和arg2分別表示條件的兩個(gè)參數(shù)，op表示條件的比較運(yùn)算符。在Future Resolution這一步會進(jìn)行比較，進(jìn)行范圍的約束。
以t7.ssa為例，得到的E-SSA Constraint Graph如下：
call bar$1 ?in 2 : |Arguments: i_2,|Result: |Conditions:? var i_2 ?in 2 : |Arguments: |Result: bar$1,i#bar$1,i_2#bar$1,|Conditions:? var j_4 ?in 2 : |Arguments: _1#bar$1,|Result: bar$2,i#bar$2,i_2#bar$2,|Conditions:? ret bar$1 ?in 2 : |Arguments: |Result: j_4,|Conditions:? call bar$2 ?in 2 : |Arguments: j_4,|Result: |Conditions:? var k_6 ?in 2 : |Arguments: _1#bar$2,|Result: _7,|Conditions:? ret bar$2 ?in 2 : |Arguments: |Result: k_6,|Conditions:? var _7 ?in 2 : |Arguments: k_6,|Result: |Conditions:? var i_2#bar$1 ?in 3 : |Arguments: i_2,|Result: +,-,|Conditions: 0#bar$1 0| leaf 10 ?in 3 : |Arguments: |Result: +,|Conditions:? op + ?in 3 : |Arguments: i_2#bar$1,10,|Result: _3#bar$1,|Conditions: 0#bar$1 0| var _3#bar$1 ?in 3 : |Arguments: +,|Result: PHI,|Conditions: 0#bar$1 0| leaf 5 ?in 4 : |Arguments: |Result: -,|Conditions:? op - ?in 4 : |Arguments: 5,i_2#bar$1,|Result: _4#bar$1,|Conditions: 0#bar$1 1| var _4#bar$1 ?in 4 : |Arguments: -,|Result: PHI,|Conditions: 0#bar$1 1| op PHI ?in 4 : |Arguments: _3#bar$1,_4#bar$1,|Result: _1#bar$1,|Conditions: 0#bar$1 1| var _1#bar$1 ?in 4 : |Arguments: PHI,|Result: j_4,|Conditions: 0#bar$1 1| leaf i#bar$1 ?in ?: |Arguments: i_2,|Result: |Conditions:? var i_2#bar$2 ?in 3 : |Arguments: j_4,|Result: +,-,|Conditions: 0#bar$2 0| leaf 10 ?in 3 : |Arguments: |Result: +,|Conditions:? op + ?in 3 : |Arguments: i_2#bar$2,10,|Result: _3#bar$2,|Conditions: 0#bar$2 0| var _3#bar$2 ?in 3 : |Arguments: +,|Result: PHI,|Conditions: 0#bar$2 0| leaf 5 ?in 4 : |Arguments: |Result: -,|Conditions:? op - ?in 4 : |Arguments: 5,i_2#bar$2,|Result: _4#bar$2,|Conditions: 0#bar$2 1| var _4#bar$2 ?in 4 : |Arguments: -,|Result: PHI,|Conditions: 0#bar$2 1| op PHI ?in 4 : |Arguments: _3#bar$2,_4#bar$2,|Result: _1#bar$2,|Conditions: 0#bar$2 1| var _1#bar$2 ?in 4 : |Arguments: PHI,|Result: k_6,|Conditions: 0#bar$2 1| leaf i#bar$2 ?in ?: |Arguments: j_4,|Result: |Conditions:? Conditions: i_2(D) >= 0#bar$1 0#bar$1,i_2(D) >= 0#bar$2 0#bar$2, ```http://www.biyezuopin.vip
3.4 三步法
3.4.1 Widen
代碼：`\src\rangeAnalysis.py`
Widen 步驟用于將 變量范圍擴(kuò)大。此步驟可以在O(n)階段內(nèi)完成。基于原理如下：可以形象的理解為：在進(jìn)行Φ操作時(shí)，如果發(fā)現(xiàn)變量范圍向上增加，就直接擴(kuò)大到inf，如果發(fā)現(xiàn)變量范圍向下減小，就直接減小到-inf。
這樣下來后，每一個(gè)MyNode的范圍都會擴(kuò)大到最大。
3.4.2 Future Resolution & Narrow
代碼：`\src\rangeAnalysis.py`
在Widen步驟中，只能解決每一個(gè)變量內(nèi)部之間的賦值行為，在Future Resolution步驟，可以對變量之間的運(yùn)算、以及條件進(jìn)行處理。
我用了復(fù)雜的`ConditionHandle()`函數(shù)來解決條件變量的Constraint問題。我在每一個(gè)MyNode中添加了Conditions結(jié)構(gòu)，用Condition約束來代替變量替換。這樣可以大大減少變量替換帶來的麻煩。
在`ConditionHandle()`中，我將條件拆分成`arg1` `arg2`和`op`三部分，將他們組合成條件為真的范圍，和條件為假的范圍。并把相應(yīng)的范圍賦給相應(yīng)的變量，以及檢查此路徑是否可以相通。
以`t7.ssa`為例，三步法得到的所有變量的范圍如下：
Enter Range For i: -10 10 bar$1 None None | Range: ?Not Exists Not Exists i_2 int int | Range: ?-10 10 j_4 int int | Range: ?0 20 bar$1 None None | Range: ?Not Exists Not Exists bar$2 None None | Range: ?Not Exists Not Exists k_6 int int | Range: ?5 30 bar$2 None None | Range: ?Not Exists Not Exists _7 int int | Range: ?5 30 i_2#bar$1 int int | Range: ?-10 10 10 None None | Range: ?10 10 + int int | Range: ?0 20 _3#bar$1 int int | Range: ?0 20 5 None None | Range: ?5 5 - int int | Range: ?Not Exists Not Exists _4#bar$1 int int | Range: ?15 -5 PHI int int | Range: ?0 20 _1#bar$1 int int | Range: ?0 20 i#bar$1 None None | Range: ?Not Exists Not Exists i_2#bar$2 int int | Range: ?0 20 10 None None | Range: ?10 10 + int int | Range: ?10 30 _3#bar$2 int int | Range: ?10 30 5 None None | Range: ?5 5 - int int | Range: ?Not Exists Not Exists _4#bar$2 int int | Range: ?5 -15 PHI int int | Range: ?5 30 _1#bar$2 int int | Range: ?5 30 i#bar$2 None None | Range: ?Not Exists Not Exists
可以直接得到結(jié)果變量_7的范圍為：_7 int int | Range: 5 30
4. 實(shí)驗(yàn)結(jié)果
# t1.SSA Reference Range:[100, 100] Output Range: [100, +inf] # t2.SSA Reference Range:[200, 300] Output Range: [200, +inf] # t3.SSA Reference Range:[20, 50] Output Range: [20, +inf] # t4.SSA Reference Range:[0, +inf] Output Range: [0, +inf] # t5.SSA Reference Range:[210, 210] Output Range: [0, +inf] # t6.SSA Reference Range:[-9, 10] Output Range: [-9, 10] # t7.SSA Reference Range:[16, 30] Output Range: [5, 30] # t8.SSA Reference Range:[-3.2192308, 5.94230769] Output Range: [-0.41923075526423315, 14.700000286102295] # t9.SSA Reference Range:[9791, 9791] Output Range: [-10, +inf] # t10.SSA Reference Range:[-10, 40] Output Range: [1, 1]
5. 總結(jié)
在本實(shí)驗(yàn)中，我采用python語言對SSA形式的C程序進(jìn)行解析，并采用三步法針對特定輸入進(jìn)行了相應(yīng)的范圍分析。收貨了寫代碼的樂趣，也為最后的效果遺憾。
最后的效果中，10個(gè)benchmark的結(jié)果中準(zhǔn)確結(jié)果寥寥無幾。尤其是上界，很多都直接到無窮了。這一方面是為了追求時(shí)間效率和空間效率，放棄了模擬執(zhí)行采用三步法的缺陷，另一方面也是因?yàn)槲覜]有想到合適的改進(jìn)方法。
到此這篇關(guān)于如何利用Python實(shí)現(xiàn)簡單C++程序范圍分析的文章就介紹到這了,更多相關(guān)Python實(shí)現(xiàn)簡單C++程序范圍分析內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- Python與C++中梯度方向直方圖的實(shí)現(xiàn)
- C++和python實(shí)現(xiàn)單鏈表及其原理
- c++與python實(shí)現(xiàn)二分查找的原理及實(shí)現(xiàn)
- c++和python實(shí)現(xiàn)順序查找實(shí)例
- python?與c++相互調(diào)用實(shí)現(xiàn)
- python直接調(diào)用和使用swig法方調(diào)用c++庫
- 如何在C++中調(diào)用python代碼你知道嗎
- C++調(diào)用python(執(zhí)行py文件)的全過程
- C++通過內(nèi)嵌解釋器調(diào)用Python及間接調(diào)用Python三方庫
- Python 調(diào)用 C++ 傳遞numpy 數(shù)據(jù)詳情
相關(guān)文章
這篇文章主要介紹了Python讀寫壓縮文件的方法，文中講解非常細(xì)致，代碼幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-07-07
Python中在for循環(huán)中嵌套使用if和else語句的技巧
Python的語法糖非常強(qiáng)大,比如Python中在for循環(huán)中嵌套使用if和else語句的技巧便十分給力,下面我們就舉幾個(gè)例子來看詳細(xì)的用法:2016-06-06
教你使用Python寫一個(gè)簡單的JSONParser
這篇文章主要介紹了教你使用Python寫一個(gè)簡單的JSONParser,它的整個(gè)效果，有點(diǎn)類似于 python 標(biāo)準(zhǔn)庫 json 的 json.load() 方法,需要的朋友可以參考下2023-04-04
今天小編就為大家分享一篇python 拼接文件路徑的方法，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-10-10
使用python統(tǒng)計(jì)文件行數(shù)示例分享
當(dāng)文件的尺寸非常大的時(shí)候（10G之上吧），想知道行數(shù)是個(gè)問題，提供一個(gè)使用python統(tǒng)計(jì)文件行數(shù)的示例,需要的朋友可以參考下2014-02-02
Python字符串和二進(jìn)制字符串之間的轉(zhuǎn)換方法示例
python中沒有0-1形式的二進(jìn)制類型,但我們依然可以存儲二進(jìn)制類型的數(shù)據(jù),下面這篇文章主要給大家介紹了關(guān)于Python字符串和二進(jìn)制字符串之間的轉(zhuǎn)換方法,需要的朋友可以參考下2023-06-06
聽歌識曲--用python實(shí)現(xiàn)一個(gè)音樂檢索器的功能
本篇文章中主要介紹了用python實(shí)現(xiàn)一個(gè)音樂檢索器，類似于QQ音樂的搖一搖識曲，有興趣的同學(xué)可以了解一下。2016-11-11
處理字符串時(shí)經(jīng)常要定制化去掉無用的空格,python 中要么用存在的常規(guī)方法,或者用正則處理,下面這篇文章主要給大家介紹了python去掉空格的一些常用方式,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-01-01
在Python實(shí)際開發(fā)中會經(jīng)常需要用到對列表進(jìn)行排序,下面這篇文章主要給大家介紹了關(guān)于python列表中常見的一些排序方法,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-09-09
Python語言功能非常強(qiáng)大，除了類之外，還有模塊和包的概念，這有點(diǎn)像perl，本文主要介紹了包和模塊,需要的朋友可以參考下2014-06-06