GCC删除了&&的右操作数中的边界检查,但没有删除左操作数中的边界检查,为什么?

ki1q1bka  于 12个月前  发布在  其他
关注(0)|答案(5)|浏览(135)

下面是C/C++代码:

#define ARRAY_LENGTH 666

int g_sum = 0;
extern int *g_ptrArray[ ARRAY_LENGTH ];

void test()
{
    unsigned int idx = 0;

    // either enable or disable the check "idx < ARRAY_LENGTH" in the while loop
    while( g_ptrArray[ idx ] != nullptr /* && idx < ARRAY_LENGTH */ )
    {
        g_sum += *g_ptrArray[ idx ];
        ++idx;
    }

    return;
}

字符串
当我在12.2.0版中使用GCC编译器编译上述代码时,两种情况下都使用了-Os选项:

  1. while循环条件是g_ptrArray[ idx ] != nullptr
  2. while循环条件是g_ptrArray[ idx ] != nullptr && idx < ARRAY_LENGTH
    我得到了如下的集合:
test():
        ldr     r2, .L4
        ldr     r1, .L4+4
.L2:
        ldr     r3, [r2], #4
        cbnz    r3, .L3
        bx      lr
.L3:
        ldr     r3, [r3]
        ldr     r0, [r1]
        add     r3, r3, r0
        str     r3, [r1]
        b       .L2
.L4:
        .word   g_ptrArray
        .word   .LANCHOR0
g_sum:
        .space  4


正如你所看到的,程序集不对变量idx和值ARRAY_LENGTH进行任何检查。

我的问题

这怎么可能?编译器如何为两种情况生成完全相同的程序集,并忽略代码中存在的idx < ARRAY_LENGTH条件?请解释规则或过程,编译器如何得出结论,它可以完全删除条件。
在浏览器浏览器中显示的输出程序集(请参阅两个程序集是相同的):

注意:如果我将条件的顺序交换为idx < ARRAY_LENGTH && g_ptrArray[ idx ] != nullptr,则输出程序集包含idx的值检查,如您在此处看到的:https://godbolt.org/z/fvbsTfr9P

vq8itlhq

vq8itlhq1#

数组越界是一种未定义的行为,因此编译器可以假设它永远不会发生在&&表达式的LHS中。然后它会跳过一圈(优化),注意到由于ARRAY_LENGTH是数组的长度,RHS条件必须为真(否则UB将在LHS中发生)。因此您看到的结果。
正确的检查应该是idx < ARRAY_LENGTH && g_ptrArray[idx] != nullptr。这将避免RHS上任何未定义行为的可能性,因为必须首先评估LHS,除非LHS为真,否则RHS将 * 不 * 评估(在C和C++中,&&运算符保证以这种方式运行)。
即使是潜在的未定义行为也可以做这样的讨厌的事情!

oxosxuxt

oxosxuxt2#

C标准(C17 6.5.6 §8)规定,我们不能在数组之外进行指针运算,也不能在数组之外访问它-这样做是未定义的行为,任何事情都可能发生。
因此,严格地说,数组越界检查是多余的,因为你的循环条件是“在数组中发现空指针时停止”。如果g_ptrArray[ idx ]是越界访问,你调用了未定义的行为,所以理论上程序在这一点上会被烤熟。所以没有必要计算&&的右操作数。(您可能知道,&&有严格的从左到右求值。)编译器可以假设访问总是在已知大小的数组内。
我们可以通过添加一些东西来使编译器无法预测代码,从而使编译器恢复正常:

int** I_might_change_at_any_time = g_ptrArray;
void test2()
{
    unsigned int idx = 0;
     

    // check for idx value is NOT present in code
    while( I_might_change_at_any_time[ idx ] != nullptr && idx < ARRAY_LENGTH)
    {
        g_sum += *g_ptrArray[ idx ];
        ++idx;
    }
}

字符串
在这里,指针充当了“中间人”的角色。它是一个带有外部链接的文件作用域变量,因此它可以随时改变。编译器不再假设它总是指向g_ptrArray。现在&&的左操作数可以是一个定义良好的访问。因此gcc现在向汇编程序添加了越界检查:

cmp     QWORD PTR [rdx+rax*8], 0
        je      .L6
        cmp     eax, 666
        je      .L6

1mrurvl1

1mrurvl13#

解释:如Marco Bonelli所述,编译器假设编写第一个测试g_ptrArray[idx] != nullptr的程序员知道此代码已定义行为,因此它假设idx在正确的范围内,即:idx < ARRAY_LENGTH。因此,下一个测试&& idx < ARRAY_LENGTH是冗余的,因为idx已经知道是< ARRAY_LENGTH,因此代码可以省略。
目前还不清楚这种范围分析发生在何处,也不清楚编译器是否也可以警告程序员有关redundant test elided的情况,就像它在if (a = b) ...a = b << 1 + 2;中标记潜在的编程错误一样
是什么让这种 * 优化 * 反常IMHO是缺乏一个不明显的优化警告。
与编译器不同,程序员是人,也会犯错误。即使是10倍的程序员有时也会犯愚蠢的错误,编译器也不应该假设程序员总是对的,除非他们像if ((a = b)) ...那样明确地吹嘘这一点。
测试g_ptrArray[idx] != nullptridx < ARRAY_LENGTH的错误顺序在代码审查中应该是显而易见的。相反,如果假设g_ptrArray[idx] != nullptr是合法的,那么idx < ARRAY_LENGTH是冗余的,这一事实对代码的人类读者来说并不明显。编译器假设程序员知道g_ptrArray[idx] != nullptr可以执行,因此,假设idx在适当的范围内,并推断第二个测试是多余的。这是有悖常理的:如果程序员足够精明,正确地假设idx总是在正确的范围内,他们肯定不会编写冗余的测试。相反,如果他们犯了一个错误,以错误的顺序编写测试,这样标记冗余代码将有助于修复明显的bug。
当编译器变得足够聪明,能够检测到这种冗余时,这种级别的分析应该对程序员有益,并有助于检测编程错误,而不是使调试比现在更困难。

yjghlzjz

yjghlzjz4#

我想强调的是,因为其他答案没有,数组查找和边界测试的执行顺序并不重要。

bool in_bounds = idx < ARRAY_LENGTH;
    if ( g_ptrArray[ idx ] != nullptr && in_bounds ) { ... }

字符串
那么边界测试仍然可以被丢弃,即使它是在数组查找之前排序的。即使你让in_bounds成为volatile bool,GCC仍然可以丢弃测试并向其写入常量true
重要的是代码g_ptrArray[ idx ]是否执行。如果它总是执行,如上所述,那么即使在早期的使用中,idx也可以被假定为在边界内(当然,如果没有对它进行干预赋值的话)。( idx < ARRAY_LENGTH && g_ptrArray[ idx ] != nullptr )中没有删除边界检查,因为&&的短路行为意味着g_ptrArray[ idx ]并不总是运行。

r7knjye2

r7knjye25#

当C标准被编写时,C实现至少有三种不同的方式来处理类似的事情:

extern int a[5];
int x=a[i];

字符串
i在0..4范围之外的情况下:
1.一些实现使用一个抽象模型,将i添加到a的地址,以一种完全不知道结果地址是否在a内的方式,并从该地址执行加载,无论会发生什么后果。
1.某些实现会尝试在0..4范围之外的访问上捕获。
1.一些实现通常会像#1中一样,除了如果在同一个函数中访问b[0]之前和之后访问a[i],并且没有证据表明访问b[0]之间的任何内容都可能是对存储的访问,编译器可能会合并对b[0]的访问。
这些方法中的每一种都对某些任务有利,对另一些任务不利。标准没有试图暗示所有编译器都应该使用相同的方法,而是选择允许实现在其中选择,或者任何其他可能有用的方法,包括尚未发明的方法,但是他们认为合适,假设实现将选择对目标程序员最有用的方法。标准通过将#1和#3明显不同的情况归类为未定义行为来做到这一点。(脚注2)。
像gcc和clang这样的编译器是为这样的任务而设计的,这些任务可以通过识别和消除只在标准没有强加要求的情况下相关的代码来最好地服务,并且不会从其他处理中受益,例如说这样的数组读取可以在编译器空闲时通过阅读存储来处理,无论结果如何,或者以 * 无副作用 * 的方式产生一个任意值。这种处理就是你在这个例子中看到的。
脚注1:虽然C语言可能没有提供任何方法来强制任何特定的对象被分配存储在a之后,但其他语言确实提供了对布局的控制,如果a和其他对象extern int b[5];被强制连续存储,那么对a[5]的访问将是对b[0]的访问。
脚注2:一些方法(例如#3)将与行为分类为“实现定义的”不兼容。因为“as-if”规则要求程序行为的可观察方面不受优化影响 *,除非在分类为未定义行为 * 的场景中,并且因为使用方法#3的实现上的行为越界访问将受优化影响,标准有必要将这种访问归类为未定义行为。
这并不是说允许对象地址以方法#1有用的方式分配的实现不应该继续支持这种方法,也不是说以这种方式使用数组访问语法对于允许精确控制内存布局的实现来说不是一个好方法,以允许程序员利用这种控制。
尽管该标准在其“严格符合C程序”的定义中明确规定,此类程序不得执行任何被表征为调用未定义行为的行为,但其“符合C程序”的定义缺乏这样的要求,它明确指出,短语“X应该是Y”意味着当X不是Y时执行一个构造将调用未定义的行为[这意味着这种执行在 * 严格符合C程序 * 中是被禁止的,但在 * 符合C程序 * 中不是,有些人认为该标准不承认许多约束不适用的任何类别的符合性。

相关问题