如何利用Python实现简单C++程序范围分析

1. 实验说明

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

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

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

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

2. 项目使用

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

不需要安装任何库。

3. 算法原理

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

3.1 构建cfg

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

功能：解析ssa，构建cfg。

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

cfg的结构如下：

3.2 构建constraint graph

代码：\src\essaconstraintgraph.py

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

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

3.3 构建e-ssa constraint graph

代码：`\src\essaconstraintgraph.py`

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

 class description : constraint graph中的条件，附加在mynode中

其中，arg1和arg2分别表示条件的两个参数，op表示条件的比较运算符。在future resolution这一步会进行比较，进行范围的约束。

以t7.ssa为例，得到的e-ssa constraint graph如下：

3.4 三步法

3.4.1 widen

代码：`\src\rangeanalysis.py`

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

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

3.4.2 future resolution &  narrow

代码：`\src\rangeanalysis.py`

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

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

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

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

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

4. 实验结果

5. 总结

在本实验中，我采用python语言对ssa形式的c程序进行解析，并采用三步法针对特定输入进行了相应的范围分析。收货了写代码的乐趣，也为最后的效果遗憾。

最后的效果中，10个benchmark的结果中准确结果寥寥无几。尤其是上界，很多都直接到无穷了。这一方面是为了追求时间效率和空间效率，放弃了模拟执行采用三步法的缺陷，另一方面也是因为我没有想到合适的改进方法。

到此这篇关于如何利用python实现简单c++程序范围分析的文章就介绍到这了,更多相关python实现简单c++程序范围分析内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！