看懂编译原理：活跃度分析

专业术语概念解释

1. 基本块（本地优化就是做基本快的优化）基本快是指程序中顺序执行的代码块（只能从入口进入出口退出且必须是顺序执行也就意味着如果碰到跳转指令那么之前的指令就可以构成一个基本快，跳转指令之后的是一个新的基本块）
2. 控制流图cfg（涉及不可达代码删除优化，寄存器优化）：由一个函数内的多个基本快组成，这些基本快相互关联，形成的就是控制流图（多个基本快的联系）

如果一个基本快中的指令跳转到另外一个基本快之中（那么这两个基本快就形成了一条边）就形成了控制流图。

注：一个函数里面如果包含多个基本快就可以表示成一个cfg（多个基本快意味着有很多跳转代码）

1. *数据流图（ *涉及公共子表达式替换，删除无用表达式优化）：从上到下遍历指令分析数据流转的方向。比如c＝a+b之后的指令是d＝c，那么c就是数据流转可以将d直接等于a+b。

用于可用表达式分析优化：程序中的指令都会被添加到一个集合中，新添加进来的指令会和之前的指令比对是否优化。

1. 活跃性分析（涉及无用变量和无用表达式删除优化）：遍历顺序和数据流方向相反，如果一个变量从末尾遍历到开头都没有人引用它，那么这个变量就是死变量，可以删除掉及它对应的表达式。

比如还是上面数据流的例子，假设最终d是被返回或者被后面变量引用的。那么d＝c会把c也加入活跃集合；dcab都是活跃变量。如果之前是e＝c但是e没有被用到那么e就是死的需要删除。

活跃性分析练习

基本快2的活跃性变量集合输出是什么，基本快3的活跃性变量集合输出是什么？

首先基本快5的输出是x，基本快四的输出就是x等于a+b的a，b变量集合。根据基本快四的分支情况推到出基本快二三的输出。

基本快三很简单都用的是ab已经在集合中了因此输出还是ab。

基本快2的输出由于4中y可以确定一定是没用的（声明后没人用它），而d是在y声明之前只用过一次，因此也可以确定d这个变量也是死的。但是在2中不能够因为d变量是死的就认定c也是死的，判断条件不足，因此c是作为可能是活的存放在集合中的。c可能是在前面用到了而且会影响结果。

优化分析方案总结

活跃度分析和可用表达式分析都是基于集合存储的

• 活跃度分析刚开始（程序末尾）是一些活变量，随着倒序遍历会被添加进新的活跃变量和删除
• 可用表达式分析优化刚开始是空的集合，随着指令顺序往下遍历会添加进来同时会进行无用表达式删除和公共子表达式替换和不可达基本快删除优化

我正在参与2023腾讯技术创作特训营第四期有奖征文，快来和我瓜分大奖！