algorithm - 程序员如何确保编译器创建正确的代码？

Question

在 SO 上阅读这个引人入胜的(也是投票最高的问题)，Why is it faster to process a sorted array than an unsorted array?让我怀疑编译器代码的正确性。

例如，答案指出:

Intel Compiler 11 does something miraculous. It interchanges the two loops...

编译器程序员如何知道何时可以交换循环？

而且，一般来说，他们是否使用数学证明来证明结论？

编译器程序员如何知道他们的编译器将生成正确的代码？他们如何检验他们的结论？他们是否必须编写一个运行编译器的测试套件，并检查生成的代码是否正确？

Answer 1

How does a compiler programmer know when it's OK to interchange loops?

编译器对代码运行一系列检查以确定交换循环是否安全。例如，如果代码没有完全内联，它可能无法交换循环。如果代码修改了一个 volatile 变量，它不会交换循环。如果代码存储在先前循环迭代中计算的值，则编译器不会交换循环。如果他们可以确定它是安全的，因为没有触发这些条件，则编译可以交换循环。

And, in general, do they use mathematical proofs to demonstrate conclusions?

没有。他们只是制定出一个优化和一组保守的测试来确保优化是安全的。随着时间的推移，他们开发了更多的优化和更复杂的算法来检测优化何时是安全的，即使在不太明显的情况下也是如此。

How does a compiler programmer know that their compiler will generate correct code?

他们尽力而为。他们偶尔会犯错误。人们提交错误报告，然后他们修复它。

How do they test their conclusion? Do they have to write a test suite that runs the compiler, and checks that the generated code is correct?

他们确实使用测试套件。当在 GCC 中检测到错误时，会专门将测试添加到测试套件中，以确保错误已修复且不会重新引入。