如果C编译器不能证明缺少UB,为什么禁止优化?

8ehkhllq  于 2023-10-16  发布在  其他
关注(0)|答案(3)|浏览(131)

如果一个C程序有未定义的行为,任何事情都可能发生。因此,编译器可以假定任何给定的程序都不包含UB。假设我们的程序包含以下内容:

x += 5;
/* Do something else without x in the meantime. */ 
x += 7;

当然,这可以被优化以

/* Do something without x. */
x += 12;

或者类似地以另一种方式。
如果x的类型是unsigned int,那么在上面的程序中就不可能有UB。另一方面,如果x的类型为signed int,则存在溢出的可能性,因此存在UB。由于编译器可能会假设我们的程序不包含UB,因此我们可以进行上述相同的优化。事实上,在这种情况下,编译器甚至可以假设x - 12 <= MAX_INT
然而,这似乎与Jens Gustedt著名的"Modern C"(第42页)相矛盾:
但是这样的优化也可能被禁止,因为编译器不能证明某个操作不会强制程序终止。在我们的例子中,很大程度上取决于x的类型。如果x的当前值可能接近类型的上限,看似无害的操作x += 7可能会产生溢出。根据类型的不同,对此类溢出的处理也有所不同。正如我们所看到的,无符号类型的溢出不是问题,压缩操作的结果将始终与两个单独的操作一致。对于其他类型,如有符号整数类型(signed)和浮点类型(double),溢出可能引发异常并终止程序。无法进行优化。
(重点是我的)。如果编译器可以(并且确实)假设我们的程序没有UB,为什么不能执行这种优化?
[1]:Jens Gustedt. Modern C. Manning, 2019, 9781617295812. hal-02383654

icnyk63a

icnyk63a1#

TL:DR:你是对的,这种优化并不禁止signed int,只禁止float/double,而不仅仅是因为这种情况下的例外。
UB的一个原因是一些不知名的机器可能会引发异常。但是,命中UB并不能保证在所有机器上引发异常(除非你使用gcc -fsanitize=undefined编译,对于UB类型,它或clang可以可靠地检测到,或者gcc -ftrapv将有符号int溢出的行为定义为陷阱)。当编译器通过假设某些事情不会发生来将UB视为优化机会时,情况就大不相同了:UB不是“故障”或“陷阱”的同义词。

有些操作可能会在普通CPU上陷入陷阱,例如未知指针的deref,以及某些ISA上的整数除法(例如x86但不是ARM)。如果你正在寻找一个编译器可能需要小心的操作,以避免在需要发生的副作用之前引入异常,或者在可能导致抽象机器根本无法到达未定义操作的分支之前引入异常,那么这些操作可以作为示例。

有符号整数溢出是UB,所以在程序执行的任何时候都可能发生这种情况(在C中,根据C标准的一些解释),即使在编译非陷阱add指令的机器时(像所有现代ISA一样)。
某些实现可能将该行为定义为引发异常。如果他们定义了异常被引发的地方,那么它将阻止优化;每个加法都需要按照写好的那样发生,这样如果抽象机器中的操作溢出,它就可以在那里陷入困境。但这将定义行为,与UB的意思正好相反,UB的意思是absolutely zero guarantees,关于你的程序实际上做了什么。
在C语言中,如果n3128被接受,那么在抽象机器遇到UB之前,任何可见的副作用都必须发生。但是在遇到UB之后,实际上任何事情都是允许的,包括进行I/O。UB不必出错并停止执行。如果编译器使用MIPS签名溢出捕获add指令而不是通常的addu来编译+=操作,那么在 * 插入代码之后 * 优化为x+=12是法律的,即使它包含I/O操作或其他可见的副作用(如volatile读取或写入)。即使x+=5在抽象机器中导致了有符号的溢出UB,如果实际行为是稍后捕获(例如,当抽象机器完成x+=7部分时),也是可以的。只要它是在抽象机器命中UB时或之后,任何东西都是允许的。(在C
中,即使在 * a printf或其他东西之前执行可能的捕获addi $s0, $s0, 12也是法律的,因为即使在第一个未定义的操作之前也没有明确的行为要求,对于确实遇到UB的执行。但是只有当编译器可以证明printf肯定返回时,所以在实践中,这种优化通常只会发生在volatile访问中。但即使没有追溯效应,我们也可以在之前执行x+=5,在之后执行x+=7,或者在之后执行x+=12。不出错是有符号溢出的有效行为,但是抽象机已经完成了一个未定义的操作,所以后面发生的任何事情都是允许的,比如打印然后陷印,或者只是进行加法 Package 。

编译器只需要避免在不应该有任何的执行路径上引入异常。(这对于主流ISA上的整数加法来说不是问题;大多数甚至没有陷印signed-add指令,针对MIPS的编译器甚至使用addu进行有符号的数学运算,这样他们就可以自由地优化,因为历史上程序员不希望陷印int数学运算。

脚注1:C与C++,以及C UB应该是“具体的”还是“抽象的”

参见 * Does undefined behaviour retroactively mean that earlier visible side-effects aren't guaranteed? * 和 * n3128: Taming the Demons -- Undefined Behavior and Partial Program Correctness *,一个让ISO C明确规定在抽象机器到达未定义操作之前可见的副作用(如I/O)仍然必须发生的建议。(当前ISO C标准的常见解释对待UB就像在C中一样,C标准明确允许“破坏”东西沿着一条不可避免的路径到达UB。

编译器实现此功能的实际示例

intunsigned都可以进行这种优化,只有FP类型不能,但这(也)是因为四舍五入,即使您使用gcc -fno-trapping-math(FP数学选项)编译。使用GCC 13和Clang 16在Godbolt上看到它的行动

int sink;    // volatile int sink doesn't make a difference
int foo_signed(int x) {
    x += 5;
    sink = 1;
    x += 7;
    return x;
}
// also unsigned and float versions
# GCC -O3 -fno-trapping-math
foo_signed:                               # input in EDI, retval in EAX
        mov     DWORD PTR sink[rip], 1
        lea     eax, [rdi+12]             # x86 can use LEA as a copy-and-add
        ret
foo_unsigned:
        mov     DWORD PTR sink[rip], 1
        lea     eax, [rdi+12]
        ret
foo_float:                    # first arg and retval in XMM0
        addss   xmm0, DWORD PTR .LC0[rip]     # add Scalar Single-precision
        mov     DWORD PTR sink[rip], 1
        addss   xmm0, DWORD PTR .LC1[rip]     # two separate 5.0f and 7.0f adds
        ret
早期版本的答案,对同一结论提出不同观点

你说得对假设x是一个局部变量,所以实际上没有任何东西可能使用x += 5结果,对于signedunsigned整数类型,将x+=5; ... ; x+=7优化为x+=12是安全的。
无符号整数数学当然是好的。

有符号整数数学必须在抽象机器 * 不 * 遇到UB的任何情况下产生正确的结果。x+=12就是这样。不能保证有符号溢出会在程序中的任何特定点引发异常,这是现代C语言基于未定义行为不会发生的假设进行优化的全部要点。对于将遇到UB的执行,字面上任何事情都可以在该点之前或之后的任何地方发生(但请参见上面的脚注1,re:“打破”的东西沿着一条不可避免的道路UB)。
这种优化甚至对于将x-=5; x+=7转换为x+=2也是安全的,在这种情况下,抽象机可以 Package 两次(遇到UB),但asm不会 Package ,因为“碰巧工作”是允许的行为,并且在实践中很常见。(例如,即使使用MIPS捕获add指令。
如果你使用像gcc -fwrapv这样的编译器选项,它将有符号整数数学的行为定义为2的补码 Package ,删除UB并使情况与无符号相同。
GCC有时会错过带符号整数数学的优化,因为GCC内部不愿意在asm中的临时变量中创建带符号溢出,而在抽象机器中不存在这种溢出。这是一个错过的优化时,编译的机器,允许非陷阱整数数学(即。例如,GCC会将a+b+c+d+e+f优化为(a+b)+(c+d)+(e+f),但不会将-fwrapv优化为signed int。Clang支持AArch 64和RISC-V,但不支持x86。(Godbolt).同样,这是一个错过的优化,由于海湾合作委员会过于谨慎的一些未知的原因;完全有效2的补码有符号数学与无符号二进制数学相同,因此是结合的;例如,在优化的计算来回缠绕而抽象机器没有的情况下,最终结果将是正确的。
带符号的溢出UB只是抽象机中的一个东西,而不是asm;大多数主流ISA甚至没有在溢出时捕获的整数加法指令。(MIPS有,但编译器不使用它们进行int数学运算,所以它们可以进行优化,生成抽象机器中不存在的值。
半相关:Why doesn't GCC optimize aaaaaa to (aaa)(aaa)?(答案表明编译器确实优化了整数数学的三次乘法,即使是有符号的int

FP异常不是float/double唯一的问题

**浮点数学无法进行此优化,因为在非溢出情况下,由于不同的舍入,它可能会给予不同的结果。一个更大的数字超过了阈值。

例如,对于一个足够大的数,使得最近的可表示的double值是彼此分开的168将得到一半,并舍入到最近偶数(假设默认舍入模式)。但任何更小的,如75,将始终向下舍入; x + 7 == x,所以57都将丢失,但是x+12将一次性地越过驼峰到达下一个可表示的float或double,产生x+16
(The(尾数的)最后一个单位的大小取决于float/double的指数。对于足够大的FP值,它是1.0。对于更大的值,例如double从253到254只有偶数是可表示的,以此类推。
如果使用GCC的错误默认值-ftrapping-math进行编译,它将尝试遵守FP异常语义。如果溢出发生两次,它不会可靠地生成2个FP异常,所以它可能不关心这个。
但是,是的,对于#pragma STDC FENV_ACCESS ON,每个单独的FP操作都应该有一个可观察的效果。(https://en.cppreference.com/w/c/numeric/fenv)。但是如果你不调用fegetexcept来实际观察两个操作之间的FP异常标志,理论上它们仍然可以被优化 * 如果 * 我们可以证明舍入是相同的,因为我认为即使是ISO C的FENV_ACCESS ON也不应该支持为每个捕获操作实际运行异常/信号处理程序。
例如,像x *= 1.0;这样的两个标识操作可以被折叠为一个,这将在NaN上引发异常。或者x *= 2; x *= 2;可以优化为x *= 4;,因为乘以2的精确幂不会改变尾数,因此不会导致舍入。不管第一次还是第二次乘法是否溢出到+-Inf,这仍然是最终结果。(除非Inf * 2引发了溢出乘法不会引发的异常标志?我不这么认为。)
它们都在同一个方向上改变指数,不像x *= 4; x *= 0.5;,它可能会溢出到+Inf的大数字,所以不等同于x *= 2。此外,如果x *= 0.5; x *= 0.5;产生低于正常的结果,它实际上 * 可以 * 四舍五入两次时,右移尾数; IEEE FP具有逐渐下溢(具有特殊指数编码的次法线),但非逐渐上溢到+Inf。

弄清楚将x * 0.5 * 0.5优化为x *= 0.25是否安全超出了这个答案的范围。GCC和clang即使使用-fno-trapping-math也没有将x *= 2.0f; x *= 2.0f;优化为x *= 4.0f;,但我认为这是一个遗漏的优化。

doinxwow

doinxwow2#

IMO,你是对的。UB就是UB,没有义务提出异常并终止程序,因此应该允许优化。
无论如何,如果编译器被设置为在有符号溢出时导致陷阱,则陷阱必须在它发生的地方被接受,并且添加的合并是不可能的。
请注意,这不是C的要求(UB可以是任何东西),而是编译器的要求(如果UB被设置为陷阱-这将强制使用“DB”)。

qmb5sa22

qmb5sa223#

允许编译器执行不会明显影响任何已定义程序执行行为的优化。一个不幸的推论是,允许可能会显著影响某些程序执行行为的有用优化的唯一方法是将任何执行归类为调用未定义行为。标准编写者对未定义行为的疯狂迷恋源于标准编写者不愿意指定 * 具体 * 方式,在这种情况下,程序执行将在这种偏差允许的范围内定义,编译器可能会以与顺序处理程序的各个步骤不一致的方式进行行为。
如果编译器针对的是一种语言或平台,该语言或平台指定了它在比标准规定的更多情况下的行为方式,则编译器可能会执行在缺乏此类保证的情况下无效的优化。例如,如果编译器给出一个像这样的构造:

extern int x[],y[];
int i,*p;
...
if (p+i==x+4)
  p[i] = 1;

并且它的输出语言保证解引用指针的操作将以一种与它们是如何计算无关的方式进行处理,它可以将结构p[i]转换为x[4],即使在标准可能定义前者而不是后者的行为的情况下。
如果下游处理没有以上游优化所依赖的方式处理所有预期情况,则这样的优化可能不再有效。例如,在上面的结构中,如果下游代码假设由于x[4]的地址是通过将整数位移添加到x的基址来计算的,那么解引用它不可能访问y[0]处的存储,即使标准将程序行为指定为如果x有四个元素,在内存中,y紧跟在x之后,而p是通过取y的地址形成的。
请注意,上述任何一种优化都是独立合法的,尽管组合并不合法。如果上游通道知道下游通道不会执行某些转换,那么它可以合法地执行优化,而如果没有这样的知识,优化将是不合理的。该标准依赖于实现来识别哪些组合是无效的,并设计出最方便的方法来避免它们。

相关问题