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

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

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

    Return (uint8_t)(x+1)>x
    и необходимая проверка возвращается в ассемблерный код.

    Вариант

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

    не прокатывает, что характерно.

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

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

    Комментарии 3

      +4
      у них ассемблер проще и понятнее, чем у ARM

      Ну как сказать…

      AVR
        mov r18,r24
        mov r19,r25
        subi r18,lo8(-(1))
        sbci r19,hi8(-(1))
        cp r24,r18
        cpc r25,r19
      


      ARM:
        adds r3, r0, #1
        cmp r3, r0
      


      Опять же, если взять нормальный компилятор, а не времён мезозоя, получим 3 инструкции вместо 5.

      alwaysTrue_unsigned(unsigned int):
        subs.w r0, r0, #-1
        it ne
        movne r0, #1
      
        0

        ))) тоже игрался арифмометром таким же образом

          0
          А вот если реально нашел баг например в clang, куда писать? На bugs.llvm.org без регистрации писать не дают, на письмо на адрес, куда предлагают писать для получения аккаунта, что-то не отвечают. В почтовый список рассылки написал lists.llvm.org/pipermail/llvm-dev/2020-October/146148.html и никакой реакции.

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое