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

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

Вчера, просматривая новый комментарий к своему старому посту о реализации сдвигов компилятора gcc для МК, обратил внимание на интересную ссылку godbolt.org/z/lW6rk8. На ней демонстрируется разница в коде, порождаемом компилятором для знаковых и без-знаковых кардинальных типов. Решил я немного поэкспериментировать с приведенным кодом и обнаружил интересные особенности компилятора, о которых и сообщаю сообществу.

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

В обычной математике сама постановка задачи выглядит странно, если не вкладывать в понятие «больше» смысл, отличный от общепринятого. Естественно, что х+1>х, поскольку, если вычесть из обеих сторон неравенства х, получим тождество 1>0. При этом мы неявно постулируем, что для любого числа есть число, следующее за ним и количество возможных чисел бесконечно.
Примечание на полях (Пнп): где-то я читал, что кто-то из великих (вроде как Гаусс) считал, что существует наибольшее целое число, но даже если это и так, наверняка он имел в виду что-то другое.

Но в компьютерной математике не все так просто и проблема вытекает из ограниченности кардинальных типов, поскольку это означает конечное количество объектов, которые могут быть представлены конкретным типом при заданной кодировке. Среди них есть максимальное, в некотором смысле, число и попытка увеличить его приводит к парадоксу – требуется закодировать число, которое закодировать нельзя. Обычно такое явление называют переполнением разрядной сетки, или просто переполнением. Типичный пример: 255 для 8-битового числа.
Пнп: В детстве у меня одной из любимых игрушек был арифмометр «Феликс» и постоянным развлечением было прибавление к «999999999» числа «000000001». Я завороженно наблюдал, как одна за другой девятки превращались в нули и завершался этот процесс звонком. Еще более мистическим было вычитание из результата все той же единицы и девятки чудесным способом возникали снова. На другой моей игрушке – счетах (моя мама была бухгалтером) происходили такие же процессы, но там я сам перекидывал костяшки, а на арифмометре это было своего рода мистикой.

Так вот, для целых знаковых чисел парадокс разрешают простым способом – запрещают его возникновение, поэтому переполнение приводит к UB. И, поскольку относительно его результата справедливы любые предположения (в том числе и фантастические), компилятор вправе предположить, что х+1 всегда будет больше х и вернуть значение «истина», что он и делает в первой функции.
Пнп: Существует другой подход, применяемый в ЦОС (импортозамещение для DSP)– операции с насыщением, при этом х+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) я их отсылал с предложением внимательнее посмотреть на свой код и баг компилятора рассасывался сам собой, но ведь тут совсем другое дело — я не могу допустить неточность в интерпретации предельно ясного случая.

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


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