从Bottom出发达到的一定是最小不动点从Top出发到达的一定是最大不动点对于Transfer Function的单调性，我们需要回到之前的章节以这个为例子，在课程中笔者认为该例子过于晦涩难懂，仅仅因为 genB固定 KillB固定就证明该函数是单调的。但实际上我们可以通过一个不严谨的思想来理解这个Transfer Function是单调的，我们考虑将该函数类比为 普通的一次函数y = const1 + x - const2其中 y = OUT[B] const1 = genbx = IN[B]const2 = killB通过如上的类似仿射变换的思想可以帮助我们理解Transfer Funcion的单调性。合理严格的证明如下这里的证明思路还是阐述一下方便理解。经过如上的证明我们能够将数据分析的问题转化到格上，且能够通过获取lfp和gfp 得到Best Fixed Point，也能够证明这些问题是一定有解的。现在我们需要讨论什么时候我们能够抵达不动点。为了解决这个问题我们需要引入格的高度这个概念。格的高度就是从 Top 到 Buttom最长的一条路径就是 格的高度最坏的迭代次数就是 格高度 * 节点个数 该次数是悲观上界 辅佐以下图理解，不过我们需要申明几个前提
我们可以考虑把一个PL的 抽象的Lattice 的 Product Lattice看成一个新的Lattice对于May 我们通常是从 Bottom 出发从一个unsafe result到 safe result的过程
结合这张图我们用 Reach Def 举例子在Reaching Definitions问题中，我们在Entry块给所有变量一个undefined定义。在格中：这里我们做一个类比理解想象你问："明天会下雨吗？"回答对应评价"不知道"（啥都没说）⊥ (Bottom)❌ 不靠谱（可能错过重要信息）"有30%概率下雨"不动点✅ 靠谱且有用"明天可能下雨，可能晴天，可能下雪，可能刮风，可能地震，可能外星人入侵..."⊤ (Top)✅ 靠谱（肯定不会错）❌ 但完全没用 Available Expressions分析是Must分析，目标是找出在某个程序点肯定被计算过且还有效的表达式（用于优化，如公共子表达式消除）。格的结构Top (⊤) = 所有表达式的全集Bottom (⊥) = ∅ (空集)我们给出该图进行回顾总结Definitions问题视角问题分析类型May"哪些定值可能到达？"May Reaching DefsMust"哪些定值一定到达？"Must Reaching DefsExpressions问题视角问题分析类型
回复或点赞可查看完整内容
---
来源: 看雪论坛
原文链接: https://bbs.kanxue.com/thread-288750.htm
[原创]静态程序分析之数据流分析(Foundations + LiveVar Analysis Code)续
190 浏览
13 回复
学习学习
最多的迭代次数为h*k是不是错了？格L高度为h，格积L^k高度则为h*k，则最多的总迭代次数的应该是h*k^2才对?
牛！！！
这是李樾和谭添的公开课程吧，对初学者非常友好。要想提高程序分析效率，得用静态单赋值（SSA）形式。
vasthao
最多的迭代次数为h*k是不是错了？格L高度为h，格积L^k高度则为h*k，则最多的总迭代次数的应该是h*k^2才对?
想象一个二维数组 外层 5个 内层数组最多3个 问这个大数组的个数最多为多少？是不是就是 5 * 3 =15 转换一下同理
最多的迭代次数为h*k是不是错了？格L高度为h，格积L^k高度则为h*k，则最多的总迭代次数的应该是h*k^2才对?
想象一个二维数组 外层 5个 内层数组最多3个 问这个大数组的个数最多为多少？是不是就是 5 * 3 =15 转换一下同理
舒默哦
这是李樾和谭添的公开课程吧，对初学者非常友好。要想提高程序分析效率，得用静态单赋值（SSA）形式。
是的是的:) 目前还在学习中。
这是李樾和谭添的公开课程吧，对初学者非常友好。要想提高程序分析效率，得用静态单赋值（SSA）形式。
是的是的:) 目前还在学习中。
TeddyBe4r
想象一个二维数组 外层 5个 内层数组最多3个 问这个大数组的个数最多为多少？是不是就是 5 * 3 =15 转换一下同理
真错了，论文Efficient chaotic iteration strategieswith widenings有这么一段：
想象一个二维数组 外层 5个 内层数组最多3个 问这个大数组的个数最多为多少？是不是就是 5 * 3 =15 转换一下同理
真错了，论文Efficient chaotic iteration strategieswith widenings有这么一段：
vasthao
真错了，论文Efficient chaotic iteration strategieswith widenings有这么一段：
具体可以看课程格相关部分有专门讲这里的
真错了，论文Efficient chaotic iteration strategieswith widenings有这么一段：
具体可以看课程格相关部分有专门讲这里的
vasthao
真错了，论文Efficient chaotic iteration strategieswith widenings有这么一段：
可以看这里
最后于 2026-1-28 11:08
被TeddyBe4r编辑
，原因：
真错了，论文Efficient chaotic iteration strategieswith widenings有这么一段：
可以看这里
最后于 2026-1-28 11:08
被TeddyBe4r编辑
，原因：
vasthao
真错了，论文Efficient chaotic iteration strategieswith widenings有这么一段：
这和格积的高度不是一回事。迭代次数的上界取决于分析的传播方式，而不是格积本身的维度。
真错了，论文Efficient chaotic iteration strategieswith widenings有这么一段：
这和格积的高度不是一回事。迭代次数的上界取决于分析的传播方式，而不是格积本身的维度。
vasthao
真错了，论文Efficient chaotic iteration strategieswith widenings有这么一段：
而且你这个是混沌迭代和常规的Kildall算法 的迭代计算方法不一样
真错了，论文Efficient chaotic iteration strategieswith widenings有这么一段：
而且你这个是混沌迭代和常规的Kildall算法 的迭代计算方法不一样
TeddyBe4r
而且你这个是混沌迭代和常规的Kildall算法 的迭代计算方法不一样
问题在于数据流分析该是应该用格还是用格积?课程老师认为是应该用格，个人怎么觉得该用格积呢?
论文Efficient chaotic iteration strategies with widenings的弱拓扑排序chaotic单调迭代算法是Abstract Interpretation计算不动点的通用算法，论文里的意思是chaotic迭代用格积?
而且你这个是混沌迭代和常规的Kildall算法 的迭代计算方法不一样
问题在于数据流分析该是应该用格还是用格积?课程老师认为是应该用格，个人怎么觉得该用格积呢?
论文Efficient chaotic iteration strategies with widenings的弱拓扑排序chaotic单调迭代算法是Abstract Interpretation计算不动点的通用算法，论文里的意思是chaotic迭代用格积?
课程笔记少了这张图： 以transfer function视角，则结点个数为 k，且格高度为 h，则迭代次数为h*k^2？以join/meet function视角，结点个数为 k，且格高度为 h，则迭代次数为h*k？抽象解释计算不动点可能是transfer function视角?传统的数据流分析计算不动点可能是join/meet function视角?