К вопросу о сложении или как я нашел ошибку в gcc (на самом деле нет)

Многие вещи нам непонятны не потому, что наши понятия слабы; но потому, что сии вещи не входят в круг наших понятий.

Вчера, просматривая новый комментарий к своему старому посту о реализации сдвигов компилятора 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) я их отсылал с предложением внимательнее посмотреть на свой код и баг компилятора рассасывался сам собой, но ведь тут совсем другое дело — я не могу допустить неточность в интерпретации предельно ясного случая.

Но счастье было недолгим. На самом деле надо внимательно читать стандарт языка С и покров тайны развеется (я не стал этого делать и просто догадался).

Догадайтесь и Вы

Выражение (х+1) в операторе сравнения имеет тип int (в данном случае uint16_t), поэтому перед выполнением сложения тип uint8_t приводится к типу uint16_t приписыванием нулевого старшего байта, после чего переполнение становится невозможным и результат выполнения функции предрешен. Достаточно всего лишь явным образом обозначить свои намерения сравнивать именно байты следующим образом:

Return (uint8_t)(x+1)>x

и необходимая проверка возвращается в ассемблерный код.
Вариант

return (x+(unsigned char)1) > x;

не прокатывает, что характерно.
Наверняка есть прагма компилятора, которая сделает int по умолчанию 16-битным и позволит добиться возвращения проверки значения х, но это уже несколько замысловато.

Вот такая забавная пред-новогодняя история, которая лично мне дала в понимании приведения кардинальных типов в С больше (теперь я это никогда не забуду), чем возможное чтение стандартов (но это совершенно не означает, что их можно не читать).

Let’s block ads! (Why?)

Read More

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *