过程内分析，顾名思义， 不考虑任何的过程/函数间调用的分析算法。 总的来说，这是最基础也是最简单的一类程序分析算法， 但是其实还是比较有用， 特别是在二进制分析的实际应用中这还算是比较常用的。 因为很多时候recover procedure 和indirect jump的存在， 其实过程间分析的精度可能会非常的糟糕。而且过程内其实往往已经能够帮我们解决非常多的问题了。 一般常见的有Available Expression, Reaching Definition, Live Variable , Very Busy Expression。这几个算法的实现其实非常的类似我以Available Expression为例子，上面的算法我都实现了一下。
Available Expressions Analysis
这个分析算法主要是为了找出在每一个程序位置， 什么表达式已经被计算过了并且不会被改变。 在编译优化过程中我们就不必重新计算某一个表达式了。
在PPA 的example language中这里的表达式指的其实就应该是非平凡的算术表达式了。 所以我们的算法最终需要给出一个从每一个程序label(也就是程序位置)到某些算术表达式的完全映射
根据每一个程序的输入和输出状态我们可以列出方程组(当然我们讨论的域是Available Expression)。然后求解最大解(largest solution)就可以得到结果。
我们可以定义如下的偏序关系
请脑补把里面的RD 换成AE
这样就可以比较解的大小了，并且能使解P(AExpr*)构成一个完全格。然后我们可以发现求最大解其实就是求解他的不动点。
什么是最大解呢， 首先我们不难发现如果令 那肯定是可以去解l'， 但是我们希望能得到信息量更多的结果，空没有意义。
但是其实这里在真正实现的时候是有一些问题的。Kill Gen 其实并没有什么问题，这两个函数也比较简单。问题在 的求解上。这是一个方程组。这种描述方式在逻辑式编程当中会非常好解，基本上算是直接照着写了。如果我们使用racket之类的函数式语言，显然就不能直接写一个递归的函数，肯定是直接死循环的，因为有back edge。
PPA 在第一章给出了一种算法来求解这个方程组，叫 混沌迭代(Chaotic Iteration)。 首先这个方程组一定能解，这一点会在后面的章节中给出证明。 其次， 最大意味着如果我们的迭代是单调增的那么，我们总能找到一个不动点，而这个不动点就是最大解(Top)。(其实这个证明不是很难)。所以在我们的代码中我们可以先无限迭代，如果我们发现我们的最终输出结果(AvailiableExpr的 return)不再变大了，我们就可以退出迭代了。
还有需要注意的是这个算法是个前向分析(Forward Analysis)要用正向的dataflow。
其他的几个算法关键区别在于是要求最大还是最小解是前向还是反向。
代码
https://github.com/StarGazerM/ppa-in-code/blob/master/dataflow/avaliable-expression.rkt
