溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容主要講解“怎么用Python實現(xiàn)簡單的C++程序范圍”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“怎么用Python實現(xiàn)簡單的C++程序范圍”吧!
問題要求：針對靜態(tài)單賦值（SSA）形式的函數(shù)中間代碼輸入，輸出函數(shù)返回值的范圍
實現(xiàn)思路： 基本根據 2013年在CGO會議上提出的“三步法”范圍分析法加以實現(xiàn)[3]，求得各個變量的范圍
算法優(yōu)勢：空間復雜度和時間復雜度都是 O(n)，效率高
算法瓶頸： “三步法”的功能存在較大局限，它只能分析各個變量的最大范圍，對活躍變量只做了最簡單的考慮，因此最終得到的范圍比較不準確，往往只能得到范圍的一個界
python main.py （ssa文件路徑在main.py中設置）
不需要安裝任何庫。
簡單概括：采用三步法（2013年在CGO會議上提出）
代碼：\src\eSSAConstraintGraph.py; \src\structure.py
功能：解析SSA，構建CFG。
由于函數(shù)之間存在調用關系，因此首先把SSA劃分成不同的函數(shù)的SSA，再分別構建CFG。CFG中保留了每一個函數(shù)的語句、Block之間的關系，為下一步構建Constraint Graph打基礎。
CFG的結構如下：
# CFG類 class CFG: def __init__(self): self.name = '' self.Blocks = [] self.Edges = [] self.Arguments = []
代碼：\src\eSSAConstraintGraph.py
三步法的前提是構建Constraint Graph。數(shù)據結構如下。在這一步中，我用自己定義的數(shù)據類型MyNode來表示一條Constraint。
# Constraint Graph類 class ConstraintGraph: def __init__(self, cfg): self.MyNodes = [] #基本節(jié)點，每一個節(jié)點是一個Constraint self.MyConditions = [] #用于后面E-SSA Constraint Graph補充條件 self.cfg = cfg self.Arguments = [] #輸入參數(shù) self.returnName = '' #輸出參數(shù) # MyNode : Constraint Graph的節(jié)點，也就是保存變量范圍的地方 class MyNode: def __init__(self, t= "", name = "", args = [], result = [], fromBlock = 0, Statement = ''): self.type = t #節(jié)點類型：leave 葉節(jié)點存放范圍和值 #op運算符 #var變量名 self.name = name.strip() #節(jié)點名稱：運算名稱，或變量名稱 self.args = args #參數(shù)，一個節(jié)點是另一個節(jié)點的argument，意味著二者之間有邊相連 self.result = result #被用到哪，一個節(jié)點是另一個節(jié)點的result，意味著二者之間有邊相連 self.Conditions = [] #約束條件， 在后面E-SSA Constraint Graph中補充條件 self.fromBlock = fromBlock #在CFG的哪個Block中定義的 self.Statement = Statement #在SSA中的哪條Statement中 self.Range = Range() #節(jié)點范圍 self.size = '' self.input = False # Range由兩個Bound組成 class Range: def __init__(self ): self.lowBound = Bound() self.highBound = Bound() # Bound由值和類型組成 class Bound: def __init__(self): self.value = 'None' # inf 最大值 ； -inf 最小值; None 未設置； Not Exists 不存在 self.size = 'None' #邊界是 int or float
需要注意的是，在解決兩個函數(shù)之間的調用關系時，將被調用的函數(shù)**內聯(lián)進原函數(shù)**。我將被調用的函數(shù)的所有變量名都加入相應的后綴，比如`foo`調用`bar`函數(shù)，那么`bar`中的變量`i_1`將被更名保存為`i_1#bar$1`，其中#是變量原名和后綴分割符，$是函數(shù)名和一個隨機數(shù)的分割符，\$的作用是為了區(qū)分多次調用同一個函數(shù)的情況。
代碼：`\src\eSSAConstraintGraph.py`
這一步用于解決條件的添加。諸如`if (i_2 < j_3)`這樣的條件。在MyNode節(jié)點類型中，我設置了Conditions結構用于保存條件。Condition的數(shù)據結構如下：
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分別表示條件的兩個參數(shù)，op表示條件的比較運算符。在Future Resolution這一步會進行比較，進行范圍的約束。
以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
代碼：`\src\rangeAnalysis.py`
Widen 步驟用于將 變量范圍擴大。此步驟可以在O(n)階段內完成?；谠砣缦拢嚎梢孕蜗蟮睦斫鉃椋涸谶M行Φ操作時，如果發(fā)現(xiàn)變量范圍向上增加，就直接擴大到inf，如果發(fā)現(xiàn)變量范圍向下減小，就直接減小到-inf。
這樣下來后，每一個MyNode的范圍都會擴大到最大。
代碼：`\src\rangeAnalysis.py`
在Widen步驟中，只能解決每一個變量內部之間的賦值行為，在Future Resolution步驟，可以對變量之間的運算、以及條件進行處理。
我用了復雜的`ConditionHandle()`函數(shù)來解決條件變量的Constraint問題。我在每一個MyNode中添加了Conditions結構，用Condition約束來代替變量替換。這樣可以大大減少變量替換帶來的麻煩。
在`ConditionHandle()`中，我將條件拆分成`arg1` `arg2`和`op`三部分，將他們組合成條件為真的范圍，和條件為假的范圍。并把相應的范圍賦給相應的變量，以及檢查此路徑是否可以相通。
以`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
可以直接得到結果變量_7的范圍為：_7 int int | Range: 5 30
# 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]
到此，相信大家對“怎么用Python實現(xiàn)簡單的C++程序范圍”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續(xù)學習！
免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
