C ++中的签名溢出和未定义的行为(UB)

我想知道以下代码的使用

int result = 0;
int factor = 1;
for (...) {
    result = ...
    factor *= 10;
}
return result;

如果循环重复n次,则factor乘以10精确n次。但是,factor仅在与10相乘共n-1次之后才使用。如果我们假设factor除了在循环的最后一次迭代中不会溢出,而可能在循环的最后一次迭代中溢出,那么这样的代码是否可以接受?在这种情况下,factor的值可能在溢出发生后永远不会使用。

我正在就是否应接受此类代码进行辩论。可以将乘法放在if语句中,并且在可能溢出时,不对循环的最后一次迭代进行乘法。缺点是它会使代码混乱,并添加了一个不必要的分支,需要在所有先前的循环迭代中进行检查。我还可以减少循环迭代一次,并在循环后复制一次循环主体,这又使代码复杂化。

有问题的实际代码在一个紧密的内部循环中使用,该循环在实时图形应用程序中占用了CPU总时间的很大一部分。

foxconn_fy 回答:C ++中的签名溢出和未定义的行为(UB)

编译器确实假定有效的C ++程序不包含UB。考虑例如:

OfType<typeOf(AppsAvailable)>

如果if (x == nullptr) { *x = 3; } else { *x = 5; } ,则将其取消引用并分配值是UB。因此,在有效程序中结束的唯一方法是,当x == nullptr永远不会产生true且编译器可以在仿佛规则下假设时,上述等效于:

x == nullptr

现在输入您的代码

*x = 5;

int result = 0; int factor = 1; for (...) { // Loop until factor overflows but not more result = ... factor *= 10; } return result; 的最后一个乘法不能在有效程序中发生(带符号的溢出未定义)。因此,也不会发生对factor的分配。由于无法在最后一次迭代之前进行分支,因此先前的迭代也不会发生。最终,正确的代码部分(即,从未发生未定义的行为)是:

result
,

int溢出的行为是不确定的。

是否在循环体之外读取factor并不重要;如果它已经溢出了,那么代码在上,下以及在某种程度上之前的行为都是不确定的。

保留此代码可能会出现的一个问题是,在进行优化时,编译器变得越来越激进。特别是,他们正在养成一种习惯,即他们假设从未发生过未定义的行为。为此,他们可以完全删除for循环。

您不能为unsigned使用factor类型,尽管那样您会担心在包含两者的表达式中intunsigned的不必要转换吗? / p>

,

考虑现实世界中的优化器可能会很有见识。循环展开是已知的技术。 op循环展开的基本思想是

for (int i = 0; i != 3; ++i)
    foo()

最好在幕后实施

 foo()
 foo()
 foo()

这是简单的情况,具有固定界限。但是现代的编译器也可以做到这一点 对于变量范围:

for (int i = 0; i != N; ++i)
   foo();

成为

__RELATIVE_JUMP(3-N)
foo();
foo();
foo();

很明显,只有在编译器知道N 有符号的溢出不会发生,所以它知道循环在32位体系结构上最多可以执行9次。 10^10 > 2^32。因此,它可以进行9次迭代循环展开。 但是预期的最大值是10次迭代!

可能发生的情况是,您获得了相对跳转到N = 10的汇编指令(9-N),因此偏移为-1,这是跳转指令本身。哎呀。对于定义良好的C ++,这是完全有效的循环优化,但是给出的示例变成了紧密的无限循环。

,

任何有符号整数溢出都会导致不确定的行为,而不管是否已读取或可能会读取溢出的值。

也许在您的用例中,您可以将第一个迭代移出循环,将其变为

int result = 0;
int factor = 1;
for (int n = 0; n < 10; ++n) {
    result += n + factor;
    factor *= 10;
}
// factor "is" 10^10 > INT_MAX,UB

进入此

int factor = 1;
int result = 0 + factor; // first iteration
for (int n = 1; n < 10; ++n) {
    factor *= 10;
    result += n + factor;
}
// factor is 10^9 < INT_MAX

启用优化后,编译器可能会将上面的第二个循环展开为一个条件跳转。

,

这是UB;用ISO C ++术语来说,对于最终击中UB的执行,完全没有指定整个程序的整个行为。就C ++标准而言,最经典的例子是它可以使恶魔从你的鼻子里飞出来。 (我建议您不要使用可能存在鼻恶魔的实现方式)。有关其他详细信息,请参见其他答案。

编译器可以在编译时为执行路径“造成麻烦”,他们可以看到它们导致了编译时可见的UB,例如假设这些基本块从未达到。

另请参见What Every C Programmer Should Know About Undefined Behavior(LLVM博客)。如此处所述,带符号溢出的UB可使编译器证明for(... i <= n ...)循环不是无限循环,即使对于未知的n也是如此。它还允许他们将int循环计数器“提升”为指针宽度,而不是重做符号扩展。 (因此,在这种情况下,如果您期望将i签名包装到其值范围内,则UB的结果可能是访问数组的低64k或4G元素之外。)

在某些情况下,编译器将针对某个块发出x86 ud2之类的非法指令,如果执行该块,可证明会导致UB。 (请注意,可能永远不会调用一个函数,因此,编译器通常不会发疯并破坏其他函数,甚至不会通过不影响UB的函数的可能路径。即,机器代码它编译为必须仍可用于所有不会导致UB的输入。)


可能最有效的解决方案是手动剥离最后一次迭代,以便避免不必要的factor*=10

int result = 0;
int factor = 1;
for (... i < n-1) {   // stop 1 iteration early
    result = ...
    factor *= 10;
}
 result = ...      // another copy of the loop body,using the last factor
 //   factor *= 10;    // and optimize away this dead operation.
return result;

或者如果循环体很大,只需考虑为factor使用无符号类型。然后,可以让无符号乘法溢出,它将对某些对象进行明确定义的包装2的幂(无符号类型的值位数)。

这很好,即使您将其与 签名类型一起使用,尤其是在您的unsigned-> signed转换永远不会溢出的情况下。

无符号和2的补码符号之间的转换是免费的(所有值都使用相同的位模式);由C ++标准指定的int-> unsigned的模数包装简化为仅使用相同的位模式,而不像一个人的补码或符号/幅度。

与unsigned-> signed相似,尽管它是由实现定义的,用于大于INT_MAX的值,但它也微不足道。如果您没有使用最后一次迭代产生的巨大的无符号结果,则无需担心。但是,如果您是,请参见Is conversion from unsigned to signed undefined?。值不适合的情况是实现定义的,这意味着实现必须选择 some 行为。那些理智的人只需截断(如果需要)无符号的位模式并将其用作带符号的,因为这对于范围内的值以相同的方式起作用,而无需额外的工作。而且绝对不是UB。因此,大的无符号值可以成为负有符号整数。例如在int x = u; gcc and clang don't optimize away x>=0之后,即使没有-fwrapv也是如此,因为它们定义了行为。

,

如果您可以容忍循环中的一些其他汇编说明,而不是

int factor = 1;
for (int j = 0; j < n; ++j) {
    ...
    factor *= 10;
}

您可以写:

int factor = 0;
for (...) {
    factor = 10 * factor + !factor;
    ...
}

避免最后的乘法。 !factor将不会引入分支:

    xor     ebx,ebx
L1:                       
    xor     eax,eax              
    test    ebx,ebx              
    lea     edx,[rbx+rbx*4]      
    sete    al    
    add     ebp,1                
    lea     ebx,[rax+rdx*2]      
    mov     edi,ebx              
    call    consume(int)          
    cmp     r12d,ebp             
    jne     .L1                   

此代码

int factor = 0;
for (...) {
    factor = factor ? 10 * factor : 1;
    ...
}

优化后还会导致无分支装配:

    mov     ebx,1
    jmp     .L1                   
.L2:                               
    lea     ebx,[rbx+rbx*4]       
    add     ebx,ebx
.L1:
    mov     edi,ebx
    add     ebp,1
    call    consume(int)
    cmp     r12d,ebp
    jne     .L2

(与GCC 8.3.0 -O3一起编译)

,

您没有在for语句的括号中显示内容,但我将假定它是这样的:

for (int n = 0; n < 10; ++n) {
    result = ...
    factor *= 10;
}

您可以简单地将计数器增量和循环终止检查移到主体中:

for (int n = 0; ; ) {
    result = ...
    if (++n >= 10) break;
    factor *= 10;
}

循环中的汇编指令数量将保持不变。

受到安德烈·亚历山德列斯库(Andrei Alexandrescu)的演讲“在人心中发现速度”的启发。

,

考虑功能:

unsigned mul_mod_65536(unsigned short a,unsigned short b)
{
  return (a*b) & 0xFFFFu;
}

根据已发布的基本原理,该标准的作者希望,如果在(例如)一个参数为0xC000和0xC000的普通32位计算机上调用此函数,则将*的操作数提升为signed int将导致计算产生-0x10000000,当转换为unsigned时将产生0x90000000u -与他们已经将unsigned short提升为{{1 }}。但是,gcc有时会以某种方式优化该功能,如果发生溢出,这种方式会表现得毫无意义。 任何输入组合可能导致溢出的代码都必须使用unsigned选项进行处理,除非允许故意变形的输入的创建者执行他们选择的任意代码是可以接受的。

,

为什么不这样:

int result = 0;
int factor = 10;
for (...) {
    factor *= 10;
    result = ...
}
return result;
,

未定义行为的面孔很多,可接受的方式取决于用法。

  

紧密的内部循环,在实时图形应用程序中消耗了总CPU时间的很大一部分

就其本身而言,这是一件不寻常的事情,但是可能的是……如果确实如此,则UB最有可能在领域“允许的,可接受的” 。图形编程因黑客和丑陋的东西而臭名昭著。只要它“有效”并且制作帧的时间不超过16.6毫秒,通常没人会在意。但仍然要知道调用UB的含义。

首先,有标准。从这个角度来看,没有什么要讨论的,也没有任何理由可以证明,您的代码完全是无效的。没有ifs或whens,它不是有效的代码。从您的角度来看,您可能会说这是中指,而在95%到99%的情况下,无论如何您还是会很好。

下一步,在硬件方面。有一些不常见,怪异的体系结构会带来问题。我之所以说“不常见,很奇怪” ,是因为在一个体系结构中,它占所有计算机的80%(或两个在一起的 体系结构占所有计算机的95%)在硬件级别上是“是的,不管了,不在乎” 。您肯定会得到垃圾(尽管仍然可以预测)的结果,但是不会发生任何邪恶的事情。
在每种架构上都是不是情况,您很可能会陷入溢出陷阱(尽管看到您如何谈论图形应用程序,但采用这种奇特架构的机会却很小)。可移植性是个问题吗?如果是这样,您可能要弃权。

最后,在编译器/优化器方面。未定义溢出的原因之一是,将溢出保留在最简单的位置可以很容易地一次解决硬件问题。但是另一个原因是{strong>保证使x+1始终大于x,编译器/优化器可以利用此知识。现在,对于前面提到的情况,确实知道编译器可以通过这种方式起作用,并且只需剥离完整的块即可(几年前就有Linux漏洞利用,正是基于这一原因,编译器将一些验证代码完全删除了)。
对于您的情况,我将严重怀疑编译器会进行一些特殊的奇怪的优化。但是,您知道什么,我知道什么。如有疑问,请尝试。如果可行,那就很好了。

(最后,当然还有代码审核,如果不幸的话,您可能不得不浪费时间与审核员讨论。)

本文链接:https://www.f2er.com/3007265.html

大家都在问