Не совсем пример оптимизации, но одним полезным последствием неопределенного поведения является -ftrapv переключение командной строки GCC/clang. Он вставляет код, который приводит к сбою вашей программы при целочисленном переполнении.

Это не будет работать с целыми числами без знака, в соответствии с идеей, что переполнение без знака является преднамеренным.

Формулировка стандарта о переполнении целого числа со знаком гарантирует, что люди не будут намеренно писать переполняющий код, поэтому ftrapv является полезным инструментом для обнаружения непреднамеренного переполнения.

Ответ на самом деле в вашем вопросе:

Yet most CPUs implement signed arithmetics with defined semantics

Я не могу представить процессор, который вы можете купить сегодня, который не использует арифметику двойного комплимента для целых чисел со знаком, но так было не всегда.

Язык C был изобретен в 1972 году. Тогда еще существовали мейнфреймы IBM 7090. Не все компьютеры были двойками — комплимент.

Определить язык (и поведение переполнения) вокруг 2s-compliment было бы вредно для генерации кода на машинах, которых не было.

Кроме того, как уже было сказано, указание того, что подписанное переполнение должно быть UB, позволяет компилятору создавать более качественный код, поскольку он может сбрасывать со счетов пути кода, возникающие в результате подписанного переполнения, предполагая, что этого никогда не произойдет.

Если я правильно понимаю, что он предназначен для фиксации суммы a и b в 0....INT_MAX без зацикливания, я могу придумать два способа написать эту функцию совместимым образом.

Во-первых, неэффективный общий случай, который будет работать на всех процессорах:

int sum_max(int a, unsigned char b) {
    if (a > std::numeric_limits<int>::max() - b)
        return std::numeric_limits<int>::max();
    else
        return a + b;
}

Во-вторых, удивительно эффективный способ 2s-compliment:

int sum_max2(int a, unsigned char b) {
    unsigned int buffer;
    std::memcpy(&buffer, &a, sizeof(a));
    buffer += b;
    if (buffer > std::numeric_limits<int>::max())
        buffer = std::numeric_limits<int>::max();
    std::memcpy(&a, &buffer, sizeof(a));
    return a;
}

Получившийся ассемблер можно увидеть здесь: https://godbolt.org/z/F42IXV

Не знаю насчёт исследований и статистики, но да, с учётом этого точно есть оптимизации, которые на самом деле делают компиляторы. И да, они очень важны (например, векторизация цикла tldr).

Помимо оптимизации компилятора, необходимо учитывать еще один аспект. С UB вы получаете целые числа со знаком C/C++, которые ведут себя арифметически так, как вы ожидаете математически. Например, x + 10 > x остается верным сейчас (конечно, для действительного кода), но не при циклическом поведении.

Я нашел отличную статью Как неопределенное подписанное переполнение обеспечивает оптимизацию в GCC в блоге Кристера Вальфридссона, в которой перечислены некоторые оптимизации, учитывающие подписанное переполнение UB. Следующие примеры взяты оттуда. Я добавляю к ним примеры на С++ и ассемблере.

Если оптимизации кажутся слишком простыми, неинтересными или неэффективными, помните, что эти оптимизации — всего лишь шаги в гораздо большей цепочке оптимизаций. И эффект бабочки действительно имеет место, поскольку, казалось бы, неважная оптимизация на более раннем этапе может вызвать гораздо более эффективную оптимизацию на более позднем этапе.

Если примеры выглядят бессмысленно (кто бы написал x * 10 > 0), имейте в виду, что вы можете очень легко добраться до такого рода примеров на C и C++ с помощью констант, макросов, шаблонов. Кроме того, к такого рода примерам может попасть компилятор при применении преобразований и оптимизаций в своей ИР.

Упрощение целочисленного выражения со знаком

• Исключить умножение по сравнению с 0

  (x * c) cmp 0   ->   x cmp 0 
  

  bool foo(int x) { return x * 10 > 0 }
  

  foo(int):
          test    edi, edi
          setg    al
          ret
  

• Убрать деление после умножения

  (x * c1) / c2 -> x * (c1 / c2) if c1 is divisible by c2

  int foo(int x) { return (x * 20) / 10; }
  

  foo(int):
          lea     eax, [rdi+rdi]
          ret
  

• Устранить отрицание

  (-x) / (-y) -> x / y

  int foo(int x, int y) { return (-x) / (-y); }
  

  foo(int, int):
          mov     eax, edi
          cdq
          idiv    esi
          ret
  

• Упрощение сравнений, которые всегда истинны или ложны

  x + c < x       ->   false
  x + c <= x      ->   false
  x + c > x       ->   true
  x + c >= x      ->   true
  

  bool foo(int x) { return x + 10 >= x; }
  

  foo(int):
          mov     eax, 1
          ret
  

• Исключите отрицание в сравнениях

  (-x) cmp (-y)   ->   y cmp x
  

  bool foo(int x, int y) { return -x < -y; }
  

  foo(int, int):
          cmp     edi, esi
          setg    al
          ret
  

• Уменьшить величину констант

  x + c > y       ->   x + (c - 1) >= y
  x + c <= y      ->   x + (c - 1) < y
  

  bool foo(int x, int y) { return x + 10 <= y; }
  

  foo(int, int):
          add     edi, 9
          cmp     edi, esi
          setl    al
          ret
  

• Исключите константы в сравнениях

  (x + c1) cmp c2         ->   x cmp (c2 - c1)
  (x + c1) cmp (y + c2)   ->   x cmp (y + (c2 - c1)) if c1 <= c2
  

  The second transformation is only valid if c1 <= c2, as it would otherwise introduce an overflow when y has the value INT_MIN.

  bool foo(int x) { return x + 42 <= 11; }
  

  foo(int):
          cmp     edi, -30
          setl    al
          ret
  

Арифметика указателей и продвижение типов

If an operation does not overflow, then we will get the same result if we do the operation in a wider type. This is often useful when doing things like array indexing on 64-bit architectures — the index calculations are typically done using 32-bit int, but the pointers are 64-bit, and the compiler may generate more efficient code when signed overflow is undefined by promoting the 32-bit integers to 64-bit operations instead of generating type extensions.

One other aspect of this is that undefined overflow ensures that a[i] and a[i+1] are adjacent. This improves analysis of memory accesses for vectorization etc.

Это очень важная оптимизация, так как векторизация цикла является одним из наиболее эффективных алгоритмов оптимизации.

Это пример, когда изменение индекса с беззнакового на знаковый улучшает сгенерированную сборку:

Неподписанная версия

#include <cstddef>

auto foo(int* v, std::size_t start)
{
    int sum = 0;

    for (std::size_t i = start; i < start + 4; ++i)
        sum += v[i];

    return sum;
}

В случае unsigned необходимо учитывать случай, когда start + 4 переносится, и для этого случая создается ветка (ветки плохо влияют на производительность):

; gcc on x64 with -march=skylake

foo1(int*, unsigned long):
        cmp     rsi, -5
        ja      .L3
        vmovdqu xmm0, XMMWORD PTR [rdi+rsi*4]
        vpsrldq xmm1, xmm0, 8
        vpaddd  xmm0, xmm0, xmm1
        vpsrldq xmm1, xmm0, 4
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
        ret
.L3:
        xor     eax, eax
        ret

; clang on x64 with -march=skylake

foo1(int*, unsigned long):                             # @foo1(int*, unsigned long)
        xor     eax, eax
        cmp     rsi, -4
        jae     .LBB0_2
        vpbroadcastq    xmm0, qword ptr [rdi + 4*rsi + 8]
        vpaddd  xmm0, xmm0, xmmword ptr [rdi + 4*rsi]
        vpshufd xmm1, xmm0, 85                  # xmm1 = xmm0[1,1,1,1]
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
.LBB0_2:
        ret

В качестве примечания, использование более узкого типа приведет к еще худшей сборке, препятствующей использованию векторизованных инструкций SSE:

#include <cstddef>

auto foo(int* v, unsigned start)
{
    int sum = 0;

    for (unsigned i = start; i < start + 4; ++i)
        sum += v[i];

    return sum;
}

; gcc on x64 with -march=skylake

foo(int*, unsigned int):
        cmp     esi, -5
        ja      .L3
        mov     eax, esi
        mov     eax, DWORD PTR [rdi+rax*4]
        lea     edx, [rsi+1]
        add     eax, DWORD PTR [rdi+rdx*4]
        lea     edx, [rsi+2]
        add     eax, DWORD PTR [rdi+rdx*4]
        lea     edx, [rsi+3]
        add     eax, DWORD PTR [rdi+rdx*4]
        ret
.L3:
        xor     eax, eax
        ret

; clang on x64 with -march=skylake

foo(int*, unsigned int):                              # @foo(int*, unsigned int)
        xor     eax, eax
        cmp     esi, -5
        ja      .LBB0_3
        mov     ecx, esi
        add     esi, 4
        mov     eax, dword ptr [rdi + 4*rcx]
        lea     rdx, [rcx + 1]
        cmp     rdx, rsi
        jae     .LBB0_3
        add     eax, dword ptr [rdi + 4*rcx + 4]
        add     eax, dword ptr [rdi + 4*rcx + 8]
        add     eax, dword ptr [rdi + 4*rcx + 12]
.LBB0_3:
        ret

Подписанная версия

Однако использование подписанного индекса приводит к красивому векторизованному коду без ветвей:

#include <cstddef>

auto foo(int* v, std::ptrdiff_t start)
{
    int sum = 0;

    for (std::ptrdiff_t i = start; i < start + 4; ++i)
        sum += v[i];

    return sum;
}

; gcc on x64 with -march=skylake

foo(int*, long):
        vmovdqu xmm0, XMMWORD PTR [rdi+rsi*4]
        vpsrldq xmm1, xmm0, 8
        vpaddd  xmm0, xmm0, xmm1
        vpsrldq xmm1, xmm0, 4
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
        ret

; clang on x64 with -march=skylake

foo(int*, long):                              # @foo(int*, long)
        vpbroadcastq    xmm0, qword ptr [rdi + 4*rsi + 8]
        vpaddd  xmm0, xmm0, xmmword ptr [rdi + 4*rsi]
        vpshufd xmm1, xmm0, 85                  # xmm1 = xmm0[1,1,1,1]
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
        ret

Векторизованные инструкции по-прежнему используются при использовании более узкого знакового типа:

#include <cstddef>

auto foo(int* v, int start)
{
    int sum = 0;

    for (int i = start; i < start + 4; ++i)
        sum += v[i];

    return sum;
}

; gcc on x64 with -march=skylake

foo(int*, int):
        movsx   rsi, esi
        vmovdqu xmm0, XMMWORD PTR [rdi+rsi*4]
        vpsrldq xmm1, xmm0, 8
        vpaddd  xmm0, xmm0, xmm1
        vpsrldq xmm1, xmm0, 4
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
        ret

; clang on x64 with -march=skylake

foo(int*, int):                              # @foo(int*, int)
        movsxd  rax, esi
        vpbroadcastq    xmm0, qword ptr [rdi + 4*rax + 8]
        vpaddd  xmm0, xmm0, xmmword ptr [rdi + 4*rax]
        vpshufd xmm1, xmm0, 85                  # xmm1 = xmm0[1,1,1,1]
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
        ret

Расчет диапазона значений

The compiler keeps track of the variables' range of possible values at each point in the program, i.e. for code such as

int x = foo();
if (x > 0) {
  int y = x + 5;
  int z = y / 4;

it determines that x has the range [1, INT_MAX] after the if-statement, and can thus determine that y has the range [6, INT_MAX] as overflow is not allowed. And the next line can be optimized to int z = y >> 2; as the compiler knows that y is non-negative.

auto foo(int x)
{
    if (x <= 0)
        __builtin_unreachable();
    
    return (x + 5) / 4;
}

foo(int):
        lea     eax, [rdi+5]
        sar     eax, 2
        ret

The undefined overflow helps optimizations that need to compare two values (as the wrapping case would give possible values of the form [INT_MIN, (INT_MIN+4)] or [6, INT_MAX] that prevents all useful comparisons with < or >), such as

• Changing comparisons x<y to true or false if the ranges for x and y does not overlap
• Changing min(x,y) or max(x,y) to x or y if the ranges do not overlap
• Changing abs(x) to x or -x if the range does not cross 0
• Changing x/c to x>>log2(c) if x>0 and the constant c is a power of 2
• Changing x%c to x&(c-1) if x>0 and the constant c is a power of 2

Анализ цикла и оптимизация

The canonical example of why undefined signed overflow helps loop optimizations is that loops like

for (int i = 0; i <= m; i++)

are guaranteed to terminate for undefined overflow. This helps architectures that have specific loop instructions, as they do in general not handle infinite loops.

But undefined signed overflow helps many more loop optimizations. All analysis such as determining number of iteration, transforming induction variables, and keeping track of memory accesses are using everything in the previous sections in order to do its work. In particular, the set of loops that can be vectorized are severely reduced when signed overflow is allowed.

Вот реальный маленький эталон, пузырьковая сортировка. Я сравнил тайминги без/с -fwrapv (что означает переполнение UB/не UB). Вот результаты (секунды):

                   -O3     -O3 -fwrapv    -O1     -O1 -fwrapv
Machine1, clang    5.2     6.3            6.8     7.7
Machine2, clang-8  4.2     7.8            6.4     6.7
Machine2, gcc-8    6.6     7.4            6.5     6.5

Как видите, версия без UB (-fwrapv) почти всегда медленнее, самая большая разница довольно большая, 1,85x.

Вот код. Обратите внимание, что я намеренно выбрал реализацию, которая должна дать большую разницу в этом тесте.

#include <stdio.h>
#include <stdlib.h>

void bubbleSort(int *a, long n) {
        bool swapped;
        for (int i = 0; i < n-1; i++) {
                swapped = false;
                for (int j = 0; j < n-i-1; j++) {
                        if (a[j] > a[j+1]) {
                                int t = a[j];
                                a[j] = a[j+1];
                                a[j+1] = t;
                                swapped = true;
                        }
                }

                if (!swapped) break;
        }
}

int main() {
        int a[8192];

        for (int j=0; j<100; j++) {
                for (int i=0; i<8192; i++) {
                        a[i] = rand();
                }

                bubbleSort(a, 8192);
        }
}