本篇内容主要讲解“怎么用Python实现简单的C++程序范围”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“怎么用Python实现简单的C++程序范围”吧!

问题要求：针对静态单赋值（SSA）形式的函数中间代码输入，输出函数返回值的范围

实现思路： 基本根据 2013年在CGO会议上提出的“三步法”范围分析法加以实现[3]，求得各个变量的范围

算法优势：空间复杂度和时间复杂度都是 O(n)，效率高

算法瓶颈： “三步法”的功能存在较大局限，它只能分析各个变量的最大范围，对活跃变量只做了最简单的考虑，因此最终得到的范围比较不准确，往往只能得到范围的一个界

python main.py （ssa文件路径在main.py中设置）

不需要安装任何库。

简单概括：采用三步法（2013年在CGO会议上提出）

代码：\src\eSSAConstraintGraph.py; \src\structure.py

功能：解析SSA，构建CFG。

由于函数之间存在调用关系，因此首先把SSA划分成不同的函数的SSA，再分别构建CFG。CFG中保留了每一个函数的语句、Block之间的关系，为下一步构建Constraint Graph打基础。

CFG的结构如下：

#CFG类classCFG:def__init__(self):self.name=''self.Blocks=[]self.Edges=[]self.Arguments=[]3.2 构建Constraint Graph

代码：\src\eSSAConstraintGraph.py

三步法的前提是构建Constraint Graph。数据结构如下。在这一步中，我用自己定义的数据类型MyNode来表示一条Constraint。

#ConstraintGraph类classConstraintGraph:def__init__(self,cfg):self.MyNodes=[]#基本节点，每一个节点是一个Constraintself.MyConditions=[]#用于后面E-SSAConstraintGraph补充条件self.cfg=cfgself.Arguments=[]#输入参数self.returnName=''#输出参数#MyNode:ConstraintGraph的节点，也就是保存变量范围的地方classMyNode:def__init__(self,t="",name="",args=[],result=[],fromBlock=0,Statement=''):self.type=t#节点类型：leave叶节点存放范围和值#op运算符#var变量名self.name=name.strip()#节点名称：运算名称，或变量名称self.args=args#参数，一个节点是另一个节点的argument，意味着二者之间有边相连self.result=result#被用到哪，一个节点是另一个节点的result，意味着二者之间有边相连self.Conditions=[]#约束条件，在后面E-SSAConstraintGraph中补充条件self.fromBlock=fromBlock#在CFG的哪个Block中定义的self.Statement=Statement#在SSA中的哪条Statement中self.Range=Range()#节点范围self.size=''self.input=False#Range由两个Bound组成classRange:def__init__(self):self.lowBound=Bound()self.highBound=Bound()#Bound由值和类型组成classBound:def__init__(self):self.value='None'#inf最大值；-inf最小值;None未设置；NotExists不存在self.size='None'#边界是intorfloat

需要注意的是，在解决两个函数之间的调用关系时，将被调用的函数**内联进原函数**。我将被调用的函数的所有变量名都加入相应的后缀，比如`foo`调用`bar`函数，那么`bar`中的变量`i_1`将被更名保存为`i_1#bar$1`，其中#是变量原名和后缀分割符，$是函数名和一个随机数的分割符，\$的作用是为了区分多次调用同一个函数的情况。

代码：`\src\eSSAConstraintGraph.py`

这一步用于解决条件的添加。诸如`if (i_2 < j_3)`这样的条件。在MyNode节点类型中，我设置了Conditions结构用于保存条件。Condition的数据结构如下：

Class Description : Constraint Graph中的条件，附加在MyNode中

classMyCondition:def__init__(self,condition,index):self.condition=conditionself.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分别表示条件的两个参数，op表示条件的比较运算符。在Future Resolution这一步会进行比较，进行范围的约束。

以t7.ssa为例，得到的E-SSA Constraint Graph如下：

callbar$1in2:|Arguments:i_2,|Result:|Conditions:vari_2in2:|Arguments:|Result:bar$1,i#bar$1,i_2#bar$1,|Conditions:varj_4in2:|Arguments:_1#bar$1,|Result:bar$2,i#bar$2,i_2#bar$2,|Conditions:retbar$1in2:|Arguments:|Result:j_4,|Conditions:callbar$2in2:|Arguments:j_4,|Result:|Conditions:vark_6in2:|Arguments:_1#bar$2,|Result:_7,|Conditions:retbar$2in2:|Arguments:|Result:k_6,|Conditions:var_7in2:|Arguments:k_6,|Result:|Conditions:vari_2#bar$1in3:|Arguments:i_2,|Result:+,-,|Conditions:0#bar$10|leaf10in3:|Arguments:|Result:+,|Conditions:op+in3:|Arguments:i_2#bar$1,10,|Result:_3#bar$1,|Conditions:0#bar$10|var_3#bar$1in3:|Arguments:+,|Result:PHI,|Conditions:0#bar$10|leaf5in4:|Arguments:|Result:-,|Conditions:op-in4:|Arguments:5,i_2#bar$1,|Result:_4#bar$1,|Conditions:0#bar$11|var_4#bar$1in4:|Arguments:-,|Result:PHI,|Conditions:0#bar$11|opPHIin4:|Arguments:_3#bar$1,_4#bar$1,|Result:_1#bar$1,|Conditions:0#bar$11|var_1#bar$1in4:|Arguments:PHI,|Result:j_4,|Conditions:0#bar$11|leafi#bar$1in:|Arguments:i_2,|Result:|Conditions:vari_2#bar$2in3:|Arguments:j_4,|Result:+,-,|Conditions:0#bar$20|leaf10in3:|Arguments:|Result:+,|Conditions:op+in3:|Arguments:i_2#bar$2,10,|Result:_3#bar$2,|Conditions:0#bar$20|var_3#bar$2in3:|Arguments:+,|Result:PHI,|Conditions:0#bar$20|leaf5in4:|Arguments:|Result:-,|Conditions:op-in4:|Arguments:5,i_2#bar$2,|Result:_4#bar$2,|Conditions:0#bar$21|var_4#bar$2in4:|Arguments:-,|Result:PHI,|Conditions:0#bar$21|opPHIin4:|Arguments:_3#bar$2,_4#bar$2,|Result:_1#bar$2,|Conditions:0#bar$21|var_1#bar$2in4:|Arguments:PHI,|Result:k_6,|Conditions:0#bar$21|leafi#bar$2in:|Arguments:j_4,|Result:|Conditions:Conditions:i_2(D)>=0#bar$10#bar$1,i_2(D)>=0#bar$20#bar$2,```http://www.biyezuopin.vip3.4 三步法3.4.1 Widen

代码：`\src\rangeAnalysis.py`

Widen 步骤用于将 变量范围扩大。此步骤可以在O(n)阶段内完成。基于原理如下：可以形象的理解为：在进行Φ操作时，如果发现变量范围向上增加，就直接扩大到inf，如果发现变量范围向下减小，就直接减小到-inf。

这样下来后，每一个MyNode的范围都会扩大到最大。

代码：`\src\rangeAnalysis.py`

在Widen步骤中，只能解决每一个变量内部之间的赋值行为，在Future Resolution步骤，可以对变量之间的运算、以及条件进行处理。

我用了复杂的`ConditionHandle()`函数来解决条件变量的Constraint问题。我在每一个MyNode中添加了Conditions结构，用Condition约束来代替变量替换。这样可以大大减少变量替换带来的麻烦。

在`ConditionHandle()`中，我将条件拆分成`arg1` `arg2`和`op`三部分，将他们组合成条件为真的范围，和条件为假的范围。并把相应的范围赋给相应的变量，以及检查此路径是否可以相通。

以`t7.ssa`为例，三步法得到的所有变量的范围如下：

EnterRangeFori:-1010bar$1NoneNone|Range:NotExistsNotExistsi_2intint|Range:-1010j_4intint|Range:020bar$1NoneNone|Range:NotExistsNotExistsbar$2NoneNone|Range:NotExistsNotExistsk_6intint|Range:530bar$2NoneNone|Range:NotExistsNotExists_7intint|Range:530i_2#bar$1intint|Range:-101010NoneNone|Range:1010+intint|Range:020_3#bar$1intint|Range:0205NoneNone|Range:55-intint|Range:NotExistsNotExists_4#bar$1intint|Range:15-5PHIintint|Range:020_1#bar$1intint|Range:020i#bar$1NoneNone|Range:NotExistsNotExistsi_2#bar$2intint|Range:02010NoneNone|Range:1010+intint|Range:1030_3#bar$2intint|Range:10305NoneNone|Range:55-intint|Range:NotExistsNotExists_4#bar$2intint|Range:5-15PHIintint|Range:530_1#bar$2intint|Range:530i#bar$2NoneNone|Range:NotExistsNotExists

可以直接得到结果变量_7的范围为：_7 int int | Range: 5 30

#t1.SSAReferenceRange:[100,100]OutputRange:[100,+inf]#t2.SSAReferenceRange:[200,300]OutputRange:[200,+inf]#t3.SSAReferenceRange:[20,50]OutputRange:[20,+inf]#t4.SSAReferenceRange:[0,+inf]OutputRange:[0,+inf]#t5.SSAReferenceRange:[210,210]OutputRange:[0,+inf]#t6.SSAReferenceRange:[-9,10]OutputRange:[-9,10]#t7.SSAReferenceRange:[16,30]OutputRange:[5,30]#t8.SSAReferenceRange:[-3.2192308,5.94230769]OutputRange:[-0.41923075526423315,14.700000286102295]#t9.SSAReferenceRange:[9791,9791]OutputRange:[-10,+inf]#t10.SSAReferenceRange:[-10,40]OutputRange:[1,1]

到此，相信大家对“怎么用Python实现简单的C++程序范围”有了更深的了解，不妨来实际操作一番吧！这里是亿速云网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！