数据流分析是一种比较经典的分析算法, 在大量的编译原理的书里都会提到(比如龙书)。
在PPA 中,为了方便讨论,使用了一种非常简单的命令式语言作为示例来进行讲解。
Syntax
算术符号比如+ - * /
布尔操作符比如and or xor
布尔关系操作符比如> < ==
这个语言主要包含赋值, if (可以带来数据流分支), while (可以有反向数据流)。如果使用racket实现的话这个还是比较容易的,直接基本上是把每一行直接翻译一下就可以了。在实现的时候使用的是S表达式的形式,然后sequence 结构直接用 list来实现了。
The program of interest
PPA 中使用 一些符号来表示了我们感兴趣的程序properties.如果我们使用的是flatten式的IR,并且使用逻辑式编程那么这些东西对应的应就是需要预处理得到的程序中的facts。 直接实现的话还是predicate加上函数可以搞定。
- S*: 表示顶层的statement. 也就是输入的程序
- Lab* : 在句法中我们不难看到, 这里我们的语言都是预先被打好了label l的, Lab* 表示所有的label, (labels(S))。我的实现中直接把这些带的理解成某种类型
- Var* : 所有的自由变量 (FV(S*))
- Blocks* : block这表示程序中所有带label的部分
- AExpr : 算术表达式。。。。。好吧,居然是Arithmetic 而不是Atomic,我第一次看到还confuse了好久。AExpr(...)就代表某东西里的所有非平凡算术表达式。
同时我们的示例语言中所有的label都必须保证是unique的
数据流
我们可以使用list of label pair来表示数据流路径, 即P(Lab x Lab) 。这里的P是幂集的意思。
先确定每条边起始位置:
然后是终止位置:
最后连接两点:
最后一步连接我是直接按书上的代码直接翻译之后按普通递归的方式去实现的。这里用普通的递归和尾递归没有太大的区别。
我的代码
https://github.com/StarGazerM/ppa-in-code/blob/master/dataflow/flow.rkt