Я не знаю об исследованиях и статистике, но да, есть определенная оптимизация, учитывающая это, что на самом деле делают компиляторы. И да, они очень важны (например, векторизация цикла tldr).
Помимо оптимизации компилятора, необходимо учитывать еще один аспект. С UB вы получаете целые числа со знаком C / C ++, которые ведут себя арифметически, как и следовало ожидать математически. Например, x + 10 > x
теперь верно (для действительного кода, конечно), но это не относится к поведению с циклическим изменением.
Я нашел отличную статью Как неопределенное переполнение со знаком позволяет оптимизировать GCC из блога Кристера Вальфридссона, в котором перечислены некоторые оптимизации, в которых учитывается UB со знаком переполнения. Следующие примеры взяты из него. Я добавляю в них c ++ и примеры сборки.
Если оптимизации выглядят слишком простыми, неинтересными или неэффективными, помните, что эти оптимизации - всего лишь шаги в гораздо большей цепочке оптимизаций. И эффект бабочки действительно происходит, так как казалось бы неважная оптимизация на более раннем этапе может вызвать гораздо более эффективную оптимизацию на более позднем этапе.
Если примеры выглядят бессмысленными (кто бы написал x * 10 > 0
), имейте в виду, что вы можете очень легко получить примеры такого рода в C и C ++ с помощью констант, макросов, шаблонов. Кроме того, компилятор может получить такие примеры при применении преобразований и оптимизаций в своем IR.
Упрощенное выражение со знаком со знаком
Устранить умножение по сравнению с 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), если c1 делится на 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
Второе преобразование действительно, только если c1 <= c2, как это было бы
в противном случае возникает переполнение, когда y имеет значение INT_MIN. </p>
bool foo(int x) { return x + 42 <= 11; }
foo(int):
cmp edi, -30
setl al
ret
Арифметика указателя и продвижение типа
Если операция не переполнена, то мы получим тот же результат, если
мы делаем операцию в более широком виде. Это часто полезно при выполнении
такие вещи, как индексирование массивов на 64-битных архитектурах - индекс
вычисления обычно выполняются с использованием 32-битного типа int, но указатели
64-битный, и компилятор может генерировать более эффективный код при подписании
переполнение не определено путем перевода 32-битных целых чисел в 64-битные
операции вместо генерации расширений типов.
Еще один аспект этого заключается в том, что неопределенное переполнение гарантирует, что [i]
и [i + 1] являются смежными. Это улучшает анализ доступа к памяти для
векторизация и т. д.
Это очень важная оптимизация, поскольку векторизация цикла является одним из наиболее эффективных и действенных алгоритмов оптимизации.
Демонстрировать хитрее. Но я помню, как на самом деле сталкивался с ситуацией, когда изменение индекса с unsigned
на signed
резко улучшало сгенерированную сборку. К сожалению, я не могу вспомнить или повторить это сейчас. Вернусь позже, если я это выясню.
Расчет диапазона значений
Компилятор отслеживает диапазон возможных значений переменных в
каждая точка в программе, то есть для такого кода, как
int x = foo();
if (x > 0) {
int y = x + 5;
int z = y / 4;
определяет, что x имеет диапазон [1, INT_MAX]
после
оператор if и, таким образом, может определить, что у имеет диапазон [6,
INT_MAX]
, поскольку переполнение не допускается. И следующая строка может быть
оппереведено на int z = y >> 2;
, так как компилятор знает, что у
неотрицательным.
auto foo(int x)
{
if (x <= 0)
__builtin_unreachable();
return (x + 5) / 4;
}
foo(int):
lea eax, [rdi+5]
sar eax, 2
ret
Неопределенное переполнение помогает оптимизировать, которые должны сравнивать два
значения (так как случай упаковки даст возможные значения в форме
[INT_MIN, (INT_MIN+4)]
или [6, INT_MAX]
, что мешает все полезное
сравнения с <
или >
), например
- Изменение сравнений
x<y
на true или false, если диапазоны для x
и y
не перекрываются
- Изменение
min(x,y)
или max(x,y)
на x
или y
, если диапазоны не перекрываются
- Изменение
abs(x)
на x
или -x
, если диапазон не пересекает 0
- Изменение
x/c
на x>>log2(c)
, если x>0
и константа c
является степенью 2
- Изменение
x%c
на x&(c-1)
, если x>0
и константа c
является степенью 2
Анализ и оптимизация контуров
Канонический пример того, почему неопределенное переполнение со знаком помогает циклу
оптимизация заключается в том, что циклы, как
for (int i = 0; i <= m; i++)
гарантированно завершится при неопределенном переполнении. Это помогает
архитектуры, которые имеют определенные инструкции цикла, как они делают в
вообще не обрабатывать бесконечные циклы.
Но неопределенное переполнение со знаком помогает во многих других оптимизациях цикла. Все
анализ, такой как определение числа итераций, преобразование
переменные индукции и отслеживания доступа к памяти используют
все в предыдущих разделах, чтобы сделать свою работу. В
в частности, набор циклов, которые могут быть векторизованы, строго
уменьшается, если разрешено переполнение со знаком .