Тут по сети гуляет мем, что LLVM смог доказать Collatz Conjecture. Это такая теорема о том, что при двух операциях (x/2, когда x чётное, иначе 3*x+1) всё сходится в единицу.
Ну, во-первых, Сollatz верен до каких-то больших значений, уж для 32 битных чисел оно точно верно. Поэтому LLVM в любом случае прав.
Если побисектить оптимизации LLVM, то можно найти
Пользуются ли компиляторы идеей для комбинирования циклов в 2к21? Нет. Эту логику даже пытались удалить из C++, но как-то не вышло.
Что будет, если отключить оптимизацию удаления циклов в LLVM? Ну, я решил собрать ClickHouse и посмотреть:
Но и удалилось несколько тысяч циклов (в LLVM можно передать опцию
Поэтому в целом бесполезно с точки зрения бесконечных циклов, но полезно с точки зрения чистоты кода, много циклов можно просто удалить из-за мелких доказуемых контейнеров.
[1] Бисекция оптимизаций в LLVM
[2] N1509 — попытка удалить логику бесконечных циклов
[3] N1528 — официальный ответ на попытку удалить эту логику
[4] LLVM не может применить оптимизацию из 2010 года, в которую верили в N1528
[5] Проблемы в безопасности Rust из-за удаления бесконечных циклов
[6] Пример неопределённого поведения по опровержению теоремы Ферма на cppreference
[7] Loop Deletion Pass в LLVM
[8] Количество удалённых циклов по строчкам кода в ClickHouse
Ну, во-первых, Сollatz верен до каких-то больших значений, уж для 32 битных чисел оно точно верно. Поэтому LLVM в любом случае прав.
Если побисектить оптимизации LLVM, то можно найти
BISECT: running pass (49) LoopDeletionPass on Parallel Loop at depth 1 containing: %if.end<header><latch><exiting>И это на самом деле достаточно дурацкая история C++, когда думали, что можно несколько циклов склеивать в один и получать ускорения. И если один из них бесконечный, то такое бы не оптимизировалось:
example.cpp:2:5: remark: Loop deleted because it is invariant [-Rpass=loop-delete]
while (true) {
^
// count, count2 are global/unknownКакое общее правило за этим стоит? Если у цикла нет сайд эффектов (не пишет никуда, не читает, никаких сисколлов не зовёт, никакой atomic памяти не разыменовывает), то бесконечный цикл является неопределённым поведением. Действительно, если вы проверяйте, работает ли бесконечно цикл, то вы делаете что-то не то.
// What if list is infinite/circular?
for (p = q; p != 0; p = p->next) {
++count;
}
for (p = q; p != 0; p = p->next) {
++count2;
}
->
for (p = q; p != 0; p = p->next) {
++count;
++count2;
}
Пользуются ли компиляторы идеей для комбинирования циклов в 2к21? Нет. Эту логику даже пытались удалить из C++, но как-то не вышло.
Что будет, если отключить оптимизацию удаления циклов в LLVM? Ну, я решил собрать ClickHouse и посмотреть:
Было:Прирост в 6КБ кода из 400МБ, не так много, но неприятно. А компиляция 8500 таргетов ускорилась на 10 секунд из 10 минут.
419035760 clickhouse
Стало:
419041928 clickhouse
Но и удалилось несколько тысяч циклов (в LLVM можно передать опцию
-Rpass=$PASS_NAME и он покажет все решения за оптимизациями), больше всего в стандартных контейнерах, скорее всего компилятор смог понять, что кое-где контейнеры пустые или маленькие, и циклы не нужны.Поэтому в целом бесполезно с точки зрения бесконечных циклов, но полезно с точки зрения чистоты кода, много циклов можно просто удалить из-за мелких доказуемых контейнеров.
[1] Бисекция оптимизаций в LLVM
[2] N1509 — попытка удалить логику бесконечных циклов
[3] N1528 — официальный ответ на попытку удалить эту логику
[4] LLVM не может применить оптимизацию из 2010 года, в которую верили в N1528
[5] Проблемы в безопасности Rust из-за удаления бесконечных циклов
[6] Пример неопределённого поведения по опровержению теоремы Ферма на cppreference
[7] Loop Deletion Pass в LLVM
[8] Количество удалённых циклов по строчкам кода в ClickHouse