优化"静态"循环

Question

我正在编写一个编译语言以获得乐趣,而且我最近因为使我的优化编译器非常健壮而受到了激励.我已经找到了几种方法来优化某些东西,例如,2 + 2总是4,所以我们可以在编译时进行数学运算,如果(false){...}可以完全删除等等,但现在我已经开始循环了.经过一些研究,我认为我正在尝试做的并不是完全循环展开,但它仍然是一种优化技术.让我解释.

请使用以下代码.

String s = "";
for(int i = 0; i < 5; i++){
    s += "x";
}
output(s);

作为一个人,我可以坐在这里告诉你,这是100%的时间相当于

output("xxxxx");

换句话说,这个循环可以完全"编译"出来.它不是循环展开,而是我称之为"完全静态",也就是说,没有输入可以改变段的行为.我的想法是,任何完全静态的东西都可以解析为单个值,任何依赖于输入或使条件输出的东西都无法进一步优化.因此,从机器的角度来看,我需要考虑什么？是什么让循环"完全静止？"

我想出了三种类型的循环,我需要弄清楚如何分类.每次运行后总是以相同的机器状态结束的循环,无论输入如何,循环都不会完成,以及我无法通过某种方式弄清楚的循环.在我无法弄清楚的情况下(它有条件地改变了基于动态输入运行的次数),我并不担心优化.无限的循环将是编译错误/警告,除非程序员特别禁止,并且每次循环都应该直接跳到将机器置于正确的状态,而不进行循环.

当然要优化的主要情况是静态循环迭代,当内部的所有函数调用也是静态的.确定循环是否具有动态组件是很容易的,如果它不是动态的,我想它必须是静态的.我无法弄清楚的是如何检测它是否会无限.有没有人对此有任何想法？我知道这是暂停问题的一个子集,但我觉得它是可以解决的; 暂停问题是一个问题,因为对于一些程序子集,你只是不能说它可能永远运行,它可能没有,但我不想考虑那些情况,我只是想考虑这些情况它会停止,或者它不会停止,但首先我必须区分这三种状态.

Answer 1

这看起来像是一种符号求解器，可以为多个类定义，但不是通用的。

让我们稍微限制一下要求：没有数字溢出，只有 for 循环（while 有时可以转换为完整的 for 循环，除非使用 continue 等），没有中断，没有修改 for 循环内的控制变量。

for (var i = S; E(i); i = U(i))...

其中 E(i) 和 U(i) 是可以进行符号操作的表达式。有几个类比较简单：

U(i) = i + CONSTANT：第-次循环的n值为iS + n * CONSTANT

U(i) = i * CONSTANT：第-次循环的n值为iS * CONSTANT^n

U(i) = i / CONSTANT：第-次循环的n值为iS * CONSTANT^-n

U(i) = (i + CONSTANT) % M：第-次循环的n值为i(S + n * CONSTANT) % M

以及其他一些非常简单的组合（以及一些非常困难的组合）

判断循环是否终止就是寻找n哪里E(i(n))为假。对于很多情况，这可以通过一些符号操作来完成，但是制作求解器涉及大量工作。

例如

• for(int i = 0; i < 5; i++),
• i(n) = 0 + n * 1 = n, E(i(n))=> not(n < 5)=>
• n >= 5=> 停止n = 5

• for(int i = 0; i < 5; i--),
• i(n) = 0 + n * -1 = -n, E(i(n))=> not(-n < 5)=> -n >= 5=>
• n < -5- 因为n是非负整数，所以这永远不会成立 - 永远不会停止

• for(int i = 0; i < 5; i = (i + 1) % 3),
• E(i(n))=> not(n % 3 < 5)=> n % 3 >= 5=> 这从来都不是真的 => 永远不会停止

• for(int i = 10; i + 10 < 500; i = i + 2 * i)=>
• for(int i = 10; i < 480; i = 3 * i),
• i(n) = 10 * 3^n,
• E(i(n))=> not(10 * 3^n < 480)=> 10 * 3^n >= 480= 3^n >= 48> = n >= log3(48)> => n >= 3.5...=>
• 因为 n 是整数 => 它将停止n = 4

对于其他情况，如果它们可以转化为您已经可以解决的情况，那就太好了......

许多符号操作的技巧来自 Lisp 时代，并且并不是太难。尽管所描述的（或变体）是最常见的实践类型，但还有许多更困难和/或不可能解决的场景。