Вчера, просматривая новый комментарий к своему старому посту о реализации сдвигов компилятора gcc для МК, обратил внимание на интересную ссылку godbolt.org/z/lW6rk8. На ней демонстрируется разница в коде, порождаемом компилятором для знаковых и без-знаковых кардинальных типов. Решил я немного поэкспериментировать с приведенным кодом и обнаружил интересные особенности компилятора, о которых и сообщаю сообществу.
Итак, мы видим две функции, которые сравнивают некую величину х и ее же, увеличенную на 1 и сообщают о том, какая из их больше. Подавляющее большинство читателей уже поняло, в чем дело, но для тех, кто забыл курс введения в программирование, напомню.
В обычной математике сама постановка задачи выглядит странно, если не вкладывать в понятие «больше» смысл, отличный от общепринятого. Естественно, что х+1>х, поскольку, если вычесть из обеих сторон неравенства х, получим тождество 1>0. При этом мы неявно постулируем, что для любого числа есть число, следующее за ним и количество возможных чисел бесконечно.
Примечание на полях (Пнп): где-то я читал, что кто-то из великих (вроде как Гаусс) считал, что существует наибольшее целое число, но даже если это и так, наверняка он имел в виду что-то другое.
Но в компьютерной математике не все так просто и проблема вытекает из ограниченности кардинальных типов, поскольку это означает конечное количество объектов, которые могут быть представлены конкретным типом при заданной кодировке. Среди них есть максимальное, в некотором смысле, число и попытка увеличить его приводит к парадоксу – требуется закодировать число, которое закодировать нельзя. Обычно такое явление называют переполнением разрядной сетки, или просто переполнением. Типичный пример: 255 для 8-битового числа.
Пнп: В детстве у меня одной из любимых игрушек был арифмометр «Феликс» и постоянным развлечением было прибавление к «999999999» числа «000000001». Я завороженно наблюдал, как одна за другой девятки превращались в нули и завершался этот процесс звонком. Еще более мистическим было вычитание из результата все той же единицы и девятки чудесным способом возникали снова. На другой моей игрушке – счетах (моя мама была бухгалтером) происходили такие же процессы, но там я сам перекидывал костяшки, а на арифмометре это было своего рода мистикой.
Так вот, для целых знаковых чисел парадокс разрешают простым способом – запрещают его возникновение, поэтому переполнение приводит к UB. И, поскольку относительно его результата справедливы любые предположения (в том числе и фантастические), компилятор вправе предположить, что х+1 всегда будет больше х и вернуть значение «истина», что он и делает в первой функции.
Пнп: Существует другой подход, применяемый в ЦОС – операции с насыщением, при этом х+1 может быть равен х, но это все-таки экзотика.
А вот для без-знаковых целых чисел результат прибавления 1 к максимальному числу определен и он равен нулю. Поэтому 0xFFFF+0x0001=0x0000 > 0xFFFF – неверно и компилятору приходится генерировать код для проверки данного случая, который мы и видим во второй функции.
Пока что я не написал ничего интересного для читателя «в теме», но вот оно начинается.
Для исследования ассемблерного кода я перешел к своим любимым AVR контроллерами (у них ассемблер проще и понятнее, чем у ARM).
Для начала обратим внимание на то, как gcc осуществляет заказанную нами проверку.
alwaysTrue_unsigned(unsigned int):
mov r18,r24
mov r19,r25
subi r18,lo8(-(1))
sbci r19,hi8(-(1))
ldi r20,lo8(1)
cp r24,r18
cpc r25,r19
brlo .L3
ldi r20,lo8(0)
.L3:
mov r24,r20
ret
Берем число х в буфер (строки 2,3), прибавляем к нему 1 (4,5), заготавливаем результат (6), сравниваем буфер с числом х (7,8), корректируем результат (9,10) и задача выполнена. Итого 9 команд и время выполнения 8+ тактов. Но это версия 5.4.0.
А вот выдача версии 9.2.0.:
alwaysTrue_unsigned(unsigned int):
mov r19,r25
mov r18,r24
ldi r24,lo8(1)
cpi r18,-1
sbci r19,-1
breq .L5
ret
.L5:
ldi r24,0
ret
и мы видим, что компилятор реализует совсем другую проверку.
Берем число х в буфер (2,3), заготавливаем результат (4), вычитаем из буфера 0xFFFF (5,6), корректируем результат. Итого 7 команд и время выполнения 6+ тактов. Если перевести этот код обратно на С, то мы получим что-то вроде
return (x!=0xFF)
И такое преобразование абсолютно валидно, но у меня нет ни малейших мыслей по поводу того, как такие преобразования компилятор делает, просто сказка какая-то. Обратите еще внимание на код проверки для выражения (x+4)>x и так далее.
Дальше я решил поиграть с типами и попробовал (u)int16_t – ничего не изменилось, (u)int32_t – появились загадочные пересылки, но смысл проверки остался прежний, использовал (u)int8_t и обалдел.
Совершенно неожиданно код для без-знакового аргумента редуцировался и функция стала выдавать жесткую единицу. Но ведь это откровенно неправильно и для случая x=0xFF условие (х+1)>х выполняться не будет. Ура, неужели я нашел ошибку в gcc (в части оптимизации) и смогу о ней сообщить и помочь развитию столь мощного продукта.
Пнп: Когда лет 15 назад мои мальчишки приходили с фразой «Папа, я нашел баг в компиляторе» (речь шла о TurboPascal) я их отсылал с предложением внимательнее посмотреть на свой код и баг компилятора рассасывался сам собой, но ведь тут совсем другое дело — я не могу допустить неточность в интерпретации предельно ясного случая.
Но счастье было недолгим. На самом деле надо внимательно читать стандарт языка С и покров тайны развеется (я не стал этого делать и просто догадался).
Return (uint8_t)(x+1)>x
и необходимая проверка возвращается в ассемблерный код.
Вариант
return (x+(unsigned char)1) > x;
не прокатывает, что характерно.
Наверняка есть прагма компилятора, которая сделает int по умолчанию 16-битным и позволит добиться возвращения проверки значения х, но это уже несколько замысловато.
Вот такая забавная пред-новогодняя история, которая лично мне дала в понимании приведения кардинальных типов в С больше (теперь я это никогда не забуду), чем возможное чтение стандартов (но это совершенно не означает, что их можно не читать).
Apple возобновила переговоры с OpenAI о возможности внедрения ИИ-технологий в iOS 18, на основе данной операционной системы будут работать новые…
Конкурсный управляющий российской «дочки» Google подготовил 23 иска к участникам рекламного рынка. Общая сумма исков составляет 16 млрд рублей –…
Google завершил обновление основного алгоритма March 2024 Core Update. Раскатка обновлений была завершена 19 апреля, но сообщил об этом поисковик…
У частных продавцов на Авито появилась возможность составлять текст объявлений с помощью нейросети. Новый функционал доступен в категории «Обувь, одежда,…
24 апреля 2024 года в Москве состоялась церемония вручения наград международного конкурса Workspace Digital Awards. В этом году участниками стали…
27 июня Яндекс проведет гик-фестиваль Young Con для студентов и молодых специалистов, которые интересуются технологиями и хотят работать в IT.…