相同C代码在不同GCC编译优化级别下表现异常的原因

我尝试实现归并排序算法，代码如下：

#include <stdio.h>

void printArray(int *array) {
    int i;
    for (i=0; i<20; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

void merge(int *array, int *temp, int left, int mid, int right) {
  int i=left, j=mid, k=left;
  while (i<mid && j<right) {
    if (array[i] > array[j]) {
      temp[k++]=array[j++];
    } else {
      temp[k++]=array[i++];
    }
  }
  while (i<mid) {
    temp[k++]=array[i++];
  }
  while (j<right) {
    temp[k++]=array[j++];
  }
  for (i=left; i<right; i++) {
    array[i]=temp[i];
  }
}

void mergeSort(int *array, int size) {
  int temp[size];
  int i,j;
  for (j=1; j<=size; j*=2) {
    printf("\n%d\n",j);
    for (i=0; i<size; i+=2*j) {
      if (i+2*j<size) {
        merge(array,temp, i, i+j, i+2*j);
      } else {
        merge(array,temp, i, i+j, size);
      }
    }
  }
}

int main() {
    int array[] = {83,86,77,15,93,35,86,92,49,21,62,27,90,59,63,26,40,26,72,36};
    printArray(array);
    mergeSort(array, 20);
    printArray(array);
}

问题现象 #

在mergeSort函数中，我期望j的循环会执行到j=16（因为size=20），但默认编译（无优化选项）时只执行到j=8，导致数组未完全排序，输出如下：

83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 

1

2

4

8
15 21 26 27 35 49 59 62 63 77 83 86 86 90 92 93 26 36 40 72

但将GCC的优化选项设置为O1、O2或O3编译后，得到了预期结果：

83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 

1

2

4

8

16
15 21 26 26 27 35 36 40 49 59 62 63 72 77 83 86 86 90 92 93

原因分析 #

问题的核心是数组越界引发的未定义行为，不同优化级别下编译器的处理方式不同，导致表现差异：

1. 越界场景：当j=8时，内层循环的i会取到16（i += 2*j = 16），此时i+j=16+8=24，而size=20，代码会调用merge(array,temp,16,24,20)——这里传入的mid=24大于right=20。
2. 未定义行为触发：在merge函数中，mid>right会导致while(i<mid)循环尝试访问array[20]到array[23]，但原数组只有20个元素（下标0-19），属于栈内存越界访问。
3. 优化级别的影响：
   • 默认编译（-O0）下，栈布局未优化，越界访问恰好覆盖了mergeSort函数中的变量j，导致j在执行j*=2后被修改为大于20的值，循环条件j<=size不成立，因此跳过了j=16的迭代。
   • 开启O1/O2/O3优化后，编译器会将变量j存储到寄存器中，或优化栈布局避免越界访问破坏变量值，因此循环能正常执行到j=16，完成最后一次合并操作。

修复方案 #

修改mergeSort的内层循环，确保传入merge的mid和right不会超过数组边界：

void mergeSort(int *array, int size) {
  int temp[size];
  int i,j;
  for (j=1; j<=size; j*=2) {
    printf("\n%d\n",j);
    for (i=0; i<size; i+=2*j) {
      int mid = i + j;
      int right = i + 2*j;
      // 确保mid和right不超过数组大小
      if (mid > size) mid = size;
      if (right > size) right = size;
      merge(array,temp, i, mid, right);
    }
  }
}

这样就能避免mid大于right的情况，防止数组越界，无论是否开启优化，都能正确完成排序。

内容的提问来源于stack exchange，提问作者giovanni106