8

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

采取以下代码。

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

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

output("xxxxx");

所以，换句话说，这个循环可以完全“编译”出来。这不是循环展开，而是我所说的“完全静态”，也就是说，没有输入会改变段的行为。我的想法是，任何完全静态的东西都可以解析为单个值，任何依赖输入或产生条件输出的东西当然不能进一步优化。那么，从机器的角度来看，我需要考虑什么？是什么让循环“完全静态”？

我想出了三种类型的循环，我需要弄清楚如何分类。每次运行后总是以相同的机器状态结束的循环，无论输入如何，循环永远不会完成，以及我无法找出一种或另一种方式的循环。如果我无法弄清楚（它会根据动态输入有条件地改变它将运行的次数），我并不担心优化。除非程序员特别禁止，否则无限循环将是编译错误/警告，并且每次都相同的循环应该直接跳过以使机器处于正确状态，而不循环。

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

4

1 回答 1

2

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

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

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

其中 E(i) 和 U(i) 是可以符号操作的表达式。有几个类相对容易：

U(i) = i + CONSTANT: n-th 周期的i值为S + n * CONSTANT

U(i) = i * CONSTANT: n-th 周期的i值为S * CONSTANT^n

U(i) = i / CONSTANT: n-th 周期的i值为S * CONSTANT^-n

U(i) = (i + CONSTANT) % M: n-th 周期的i值为(S + n * CONSTANT) % M

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

确定循环是否终止是搜索nwhere E(i(n))is false。对于很多情况，这可以通过一些符号操作来完成，但是在制作求解器时需要做很多工作。

例如

  • 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 时代，而且并不难。尽管所描述的（或变体）是最常见的类型实践，但还有许多更难和/或不可能解决的场景。

于 2012-05-02T17:23:37.283 回答