DAG优化实践：基于局部块的代码改进

本篇文档主要讨论了基于DAG（有向无环图）的局部优化技术，这是编译原理中的一个重要概念，尤其是在代码优化过程中发挥关键作用。首先，我们回顾了编译原理中关于代码优化的基本分类，包括全球优化、局部优化和循环优化，这些优化旨在提高目标代码的效率，如减少空间占用和提升执行速度。 局部优化是编译优化的一个重要分支，它关注的是程序的单个部分，如基本块。基本块是一组连续执行的指令，没有数据流回溯。文档中提及的局部优化方法有： 1. 常值表达式节省（常数合并）：识别并合并那些在整个程序中具有相同值的表达式，如`a = 5+3; b = a+1`可以优化为`a = 8; b = 9`，避免不必要的计算。 2. 公共子表达式节省（删除多余运算）：如果某个计算结果在后续多个操作中重复使用，可以通过存储结果来避免重复计算，如`a = b + c; x = d - e; y = b; a = e - h/5`优化为`x = d - e; y = b; a = e - h/5`。 3. 删除无用赋值：检查是否有表达式的计算结果未被后续操作使用，如`a = b * d + 1; e = b * d - 2`中的`b * d`是一个公共子表达式，可以先计算并存储。 4. 不变表达式外提（循环优化的一种）：将循环内部的不变量（如累加器）提取到循环外部，以减少循环体内的计算量，如`i = 1; while(i < 100) { x = (k + a) / i; …; i++ }`可以优化为`i = 1; t = k + a; while(i < 100) { x = t / i; …; i++ }`。 5. 消减运算强度：在循环中，通过替换强度较大的运算为强度较小的运算来提高效率，例如将除法换为乘法。 这些局部优化技术利用DAG来分析程序的控制流和数据流，找出优化的机会。通过构建基本块的DAG图，可以更清晰地观察各个操作之间的依赖关系，从而实现更精细的优化策略。具体到题目中提到的示例，需要根据DAG来分析哪些操作可以合并、移出循环或删除，以达到减少指令执行次数和提高执行效率的目的。 总结来说，基于DAG的局部优化是通过分析程序的控制和数据流，识别并应用上述优化策略，以降低目标代码的复杂性，提升性能。对于给出的基本块，实际操作中需要构建DAG图，确定哪些操作是优化的重点，并按照这些方法调整四元式序列，以实现最终的优化目标。