在 C 中遍历列表时，我是否看到了优化错误？

Question

我一直致力于将同事的软件库集成到我们更大的应用程序中。他一直在 gcc 4.9.3 -O0 下编写和测试他的库。这是用于报警系统的嵌入式软件。这个错误是在 -Os 优化下观察到的，我们正在使用直接 C（none 的 C++ 废话），也在 gcc 4.9.3 上。架构为ARM Cortex-M4F。

我在将该代码集成到更大的堆栈时遇到了问题。下面的代码最多应该遍历 GLOBAL_MAX_DEVICES，直到它在 table 中找到空闲的 space 以插入其条目：

RET_VALUES DEVICE_Add_To_New_Table( uint8_t *new_id, uint16_t unique_id )
{
    RET_VALUES ret_value = RET_OK;
    uint8_t pos = 0;

[...]
    else
    {
        debug_print( "A,", true, DEBUG_DEVELOP_MODE_PLAIN, DEBUG_TRACE );

        // See if the unique_id is already in the table (relearn)
        while(( unique_id != DEVICE_new_table.unique_id[pos] ) && ( pos < GLOBAL_MAX_DEVICES ))
        {
            debug_print( "B,", false, DEBUG_DEVELOP_MODE_PLAIN, DEBUG_TRACE );
            pos++;
        }
[...]

我们遇到的问题是循环迭代了 GLOBAL_MAX_DEVICES 次（当前为 13 次），而是迭代了 200 多次。序列 "B," 在 while(( unique_id != DEVICE_new_table.unique_id[pos] ) && ( pos < GLOBAL_MAX_DEVICES )) 循环中多次打印出来。

可以进行三项更改来解决此问题；

pos 可以设为易变的，这（我相信）会抑制对该值的一些优化。
while 块中的参数可以反转，强制首先计算 pos < GLOBAL_MAX_DEVICES 。
可以添加构建标志 -fno-aggressive-loop-optimizations 以关闭某些循环优化。

似乎只需要一个给定的修复程序即可解决该问题。

我最初认为问题可能归结为短路优化。但是，我可以确认 unique_id 参数不为零（在此示例中为 0x042b），并且 DEVICE_new_table 在结构的 unique_id 字段中初始化为全零。而且，在任何情况下，即使第一个参数为真，也应该评估后者；短路应该只适用于第一个为假的情况，这显然不是这种情况，至少最初不是，因为循环迭代了一段时间。

因此我很困惑为什么这个循环迭代了数百次（我假设最终会发生与内存地址的冲突，这会导致与 unique_id 的机会匹配，可能与堆栈中的值.) 在打印迭代器 pos 的循环中添加打印语句会导致循环运行超过 13,000 次。 13000比13大很多，我查了好几次

比较损坏示例（添加了额外的 printf 语句）和工作示例（也使用 printf）生成的机器代码表明，工作变体（布尔运算符中的参数颠倒）包括与迭代的比较13.

的最大值

损坏：

        debug_print( "A,", true, DEBUG_DEVELOP_MODE_PLAIN, DEBUG_TRACE );
    ea7a:   4822        ldr r0, [pc, #136]  ; (eb04 <DEVICE_Add_To_New_Table+0xb0>)
    ea7c:   f8df 80a4   ldr.w   r8, [pc, #164]  ; eb24 <DEVICE_Add_To_New_Table+0xd0>
    ea80:   2101        movs    r1, #1
    ea82:   2200        movs    r2, #0
    ea84:   2306        movs    r3, #6
    ea86:   f00b fef9   bl  1a87c <debug_print>

        // See if the unique_id is already in the table (relearn)
        while(( unique_id != DEVICE_new_table.unique_id[pos] ) && ( pos < GLOBAL_MAX_DEVICES ))
    ea8a:   2400        movs    r4, #0
    ea8c:   f838 3f02   ldrh.w  r3, [r8, #2]!
    ea90:   454b        cmp r3, r9
    ea92:   b2e7        uxtb    r7, r4
    ea94:   4626        mov r6, r4
    ea96:   f104 0401   add.w   r4, r4, #1
    ea9a:   d00c        beq.n   eab6 <DEVICE_Add_To_New_Table+0x62>
        {
            uart_printf(-1, "%d,", pos);
    ea9c:   4632        mov r2, r6
    ea9e:   491a        ldr r1, [pc, #104]  ; (eb08 <DEVICE_Add_To_New_Table+0xb4>)
    eaa0:   f04f 30ff   mov.w   r0, #4294967295
    eaa4:   f7f8 ff6c   bl  7980 <uart_printf>
            debug_print( "B,", false, DEBUG_DEVELOP_MODE_PLAIN, DEBUG_TRACE );
    eaa8:   2100        movs    r1, #0
    eaaa:   4818        ldr r0, [pc, #96]   ; (eb0c <DEVICE_Add_To_New_Table+0xb8>)
    eaac:   460a        mov r2, r1
    eaae:   2306        movs    r3, #6
    eab0:   f00b fee4   bl  1a87c <debug_print>
    eab4:   e7ea        b.n ea8c <DEVICE_Add_To_New_Table+0x38>
            pos++;
        }

工作（修剪不必要的部分），注意 eab2 处的 cmp r4, #13 语句，它在损坏的样本中不存在：

        debug_print( "A,", true, DEBUG_DEVELOP_MODE_PLAIN, DEBUG_TRACE );
    ea7a:   4845        ldr r0, [pc, #276]  ; (eb90 <DEVICE_Add_To_New_Table+0x13c>)
    ea7c:   f8df 8148   ldr.w   r8, [pc, #328]  ; ebc8 <DEVICE_Add_To_New_Table+0x174>
    ea80:   2101        movs    r1, #1
    ea82:   2200        movs    r2, #0
    ea84:   2306        movs    r3, #6
    ea86:   f00b ff4d   bl  1a924 <debug_print>
    ea8a:   4647        mov r7, r8
    ea8c:   2400        movs    r4, #0

        // See if the unique_id is already in the table (relearn)
        while(( pos < GLOBAL_MAX_DEVICES ) && ( unique_id != DEVICE_new_table.unique_id[pos] ))
    ea8e:   f837 3f02   ldrh.w  r3, [r7, #2]!
    ea92:   454b        cmp r3, r9
    ea94:   b2e5        uxtb    r5, r4
    ea96:   d00f        beq.n   eab8 <DEVICE_Add_To_New_Table+0x64>
        {
            uart_printf(-1, "%d,", pos);
    ea98:   4622        mov r2, r4
    ea9a:   493e        ldr r1, [pc, #248]  ; (eb94 <DEVICE_Add_To_New_Table+0x140>)
    ea9c:   f04f 30ff   mov.w   r0, #4294967295
    eaa0:   f7f8 ff6e   bl  7980 <uart_printf>
            debug_print( "B,", false, DEBUG_DEVELOP_MODE_PLAIN, DEBUG_TRACE );
    eaa4:   2100        movs    r1, #0
    eaa6:   483c        ldr r0, [pc, #240]  ; (eb98 <DEVICE_Add_To_New_Table+0x144>)
    eaa8:   460a        mov r2, r1
    eaaa:   2306        movs    r3, #6
    eaac:   3401        adds    r4, #1
    eaae:   f00b ff39   bl  1a924 <debug_print>

        // See if the unique_id is already in the table (relearn)
        while(( pos < GLOBAL_MAX_DEVICES ) && ( unique_id != DEVICE_new_table.unique_id[pos] ))
    eab2:   2c0d        cmp r4, #13
    eab4:   d1eb        bne.n   ea8e <DEVICE_Add_To_New_Table+0x3a>
    eab6:   4625        mov r5, r4
        {
            uart_printf(-1, "%d,", pos);
            debug_print( "B,", false, DEBUG_DEVELOP_MODE_PLAIN, DEBUG_TRACE );
            pos++;
        }

我觉得一个程序员责备他的工具就是承认失败，但我真的看不出这除了编译器错误之外还有什么。如果有人有任何想法，我将不胜感激。

Answer 1

如评论中所述，这是您程序中的错误，即数组的简单 out-of-bounds 访问。

给定 GLOBAL_MAX_DEVICES = 13，那么您最终会访问 DEVICE_new_table.unique_id[13] 甚至更多。在调试版本中，您可能在那里有一个零，它 "works" 偶然。然后在发布中你得到一些 non-zero 值并且循环变得混乱，short-circuiting 离开循环终止条件。

此外，如果您的代码包含未定义的行为，例如 out-of-bounds 访问，您可能会在优化器尝试循环展开等操作时生成非常奇怪的机器代码。例如，编译器可能会推理为："okay this first check is always true since all items in the array are zero, so we can remove the check after && entirely".

这可以通过以更简单的方式编写循环来解决。假设你想在循环（？）之后保留 pos 的值，那么这样做：

uint8_t pos = 0;
...
for(; pos<GLOBAL_MAX_DEVICES; pos++)
{
  if(unique_id != DEVICE_new_table.unique_id[pos])
    break;
  debug_print(...);
}

在 C 中遍历列表时，我是否看到了优化错误？

Am I seeing an optimisation bug when iterating through a list in C?

c

gcc

compiler-optimization

compiler-bug