是否允许 C 编译器用另一种算法替换算法？

Question

例如，你有一个带有气泡排序实现的函数sort（int*数字，size_t计数），C编译器识别这种模式。是否允许编译器将其更改为另一个示例？比如快速排序。

另一个例子是将从0到n的所有数字相加，编译器可以用（n*（n-1））/2替换for循环。

Answer 1

这里的“算法”这个词可能有点强，但是是的，现代编译器的默认设置通常提供与当前编译器技术允许的尽可能多的自由来更改代码，但与此同时，几乎每个编写的现代编译器都为应用程序程序员提供了一些关于编译器可以做什么和不能做什么的控制。

给定默认设置，现代编译器可以使用简单算法的替换构造，在某种程度上，甚至可以根据程序员可设置的偏好指导他们如何选择替换构造。编译器提供了许多不同的优化选项和级别，最常见的是与速度和/或内存使用有关。但更改的范围仅限于更简单的构造，根据构造的不同，这些构造可以变得更高效，也可以完全忽略。

在您的特定示例中，对于带有排序算法的函数，算法本身不会被替换，但是其中的一些组成部分可以根据它们的编码方式进行优化。

相反，您还可以将当前编译器设置为保留您编写的代码。例如，在较新版本的GCC（从v4.4开始）中，您可以使用这些Pragma环境完全禁用优化：

#pragma GCC push_options
#pragma GCC optimize ("O0")

normal C code

#pragma GCC pop_options

Answer 2

编译器定期对优化者认可的更简单的模式执行此操作。

在您的特定情况下，算法的改变可能会产生适得其反的副作用，因为气泡排序比快速排序对大多数排序的数组更有效。

还要注意，优化必须保持相同的语义:用不稳定的排序算法(如快速排序)替换稳定的排序算法，只有在可以断言不需要稳定性的情况下才是可接受的。对一个简单的< code>int数组进行排序似乎不受这个问题的影响，但是在具有负零和填充位的体系结构上，它会有所不同。如果数组是浮点型的，排序算法的稳定性肯定会影响最终的顺序。

Answer 3

如果被调用的函数在优化域内，即使函数是另一个文件，也有办法做到这一点，那么是的。与在同一文件中具有调用函数的方式相同。但这并不意味着编译器根据函数的名称假设被调用的代码到底是什么，你可以轻松地创建自己的 C 库并将其链接进来，并让命名函数（例如 qsort）做任何你想做的事情。所以这是不可取的，但工具做到了：

#include <stdio.h>
void fun ( void )
{
    printf("0");
}
Disassembly of section .text:

00000000 <fun>:
   0:   e3a00030    mov r0, #48 ; 0x30
   4:   eafffffe    b   0 <putchar>

编译器已将所需的函数调用替换为其他函数调用。

所以是的，如果优化器被编程为可以并且将会这样做。如果它具有可见性，它更有可能将两个部分作为一个整体进行优化：

unsigned int more_fun ( unsigned int a, unsigned int b )
{
    return(a+b);
}
unsigned int fun ( void )
{
    return(more_fun(1,2));
}

Disassembly of section .text:

00000000 <more_fun>:
   0:   e0800001    add r0, r0, r1
   4:   e12fff1e    bx  lr

00000008 <fun>:
   8:   e3a00003    mov r0, #3
   c:   e12fff1e    bx  lr

这不是像printf示例那样用另一个函数替换一个函数，而是用可能更优化的内联解决方案替换优化的函数。

当然，有些编译器会优化死循环：

unsigned int fun ( void )
{
    unsigned int ra;
    for(ra=0;ra<10;ra++)
    {
    }
    return(ra);
}

00000000 <fun>:
   0:   e3a0000a    mov r0, #10
   4:   e12fff1e    bx  lr

当然这是一个微不足道的问题，但我已经生成了伪随机数发生器，它们是像这样的死代码，取决于编译器/优化器和代码，如果它已经被编程，它会将循环/代码简化为更简单的东西。

或者也许这就是你要问的：

unsigned int more_fun ( unsigned int n )
{
    return((n*(n-1))/2);
}
unsigned int fun ( void )
{
    return(more_fun(10));
}

00000000 <more_fun>:
   0:   e2403001    sub r3, r0, #1
   4:   e0020093    mul r2, r3, r0
   8:   e1a000a2    lsr r0, r2, #1
   c:   e12fff1e    bx  lr

00000010 <fun>:
  10:   e3a0002d    mov r0, #45 ; 0x2d
  14:   e12fff1e    bx  lr

数学在可能的情况下被删除。

您不能假设特定的编译器会这样做，也不能期望两个编译器产生相同的代码/优化。但是，如果编译器被编程为并且能够看到它需要优化的所有代码，那么它可以并且将能够做到这一点。

就“允许的”而言，编译器的工作是用另一种语言从功能上替换一种语言，这也是为什么任何两个从一种语言转换为另一种（同一输入语言转换为同一输出目标）的编译器都可以并且将产生不同的输出代码的部分原因，这是一种功能上的替换——一个编译器的输出没有一个正确的答案，它可能会有所不同。因此，在可能的情况下，如上文所示，编译器根据语言生成功能等效的代码，这是它的工作，因此它可以完成这项工作。虽然我不认为putchar是printf的替代品，因为编译器没有查看我的printf代码，但同时我假设这个编译器（gcc）有一个命令行选项不允许这样做。同样，编译器替换同一类型的两个结构，比如一个结构赋值，这并不少见；使用memcpy，但同时有一个命令行选项，指示我不想让你用memcpy来替换我要求的代码，我希望它是独立完成的。

在 gcc 和 clang 之间，你会看到这些行为，所以就“允许”这个词而言，我想它是允许的。如图所示，您可以检查编译器输出，并查看您的用例，编译器做了什么。