24.01.2019 14:19
GarryC 35 4300 Источник

«Найди всему причину и ты многое поймешь»


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

Итак, мы начинаем.

Для начала небольшое введение в железо
в качестве целевой платформы мы будем рассматривать 8-битный МК без аккумулятора (это такая жалкая попытка спрятать скомпрометированное название AVR), который имеет следующие аппаратно реализованные команды:

lsl/lsr логический сдвиг влево/вправо, младший/старший бит очищается;
rol/ror циклический сдвиг влево/вправо через перенос (сдвигаем 9 битов);
asr арифметический сдвиг вправо, старший (знаковый) бит сохраняется (обратим внимание на то, что выполнить данный вид сдвига влево в общем случае невозможно в принципе).

Все эти команды выполняются над байтовым операндом и являются основой для реализации всех остальных возможных сдвигов. Например, сдвиг слова (2 байта rh,rl) со знаком вправо на 1 разряд, реализуется следующей последовательностью:

asr rh; ror rl;

Рассмотрим простенький пример кода и соответствующий ему ассемблерный код для МК с системой команд AVR, как всегда, полученный на сайте godbolt.org. (подразумевается, что оптимизация включена и переменная размещена в регистре r24)

int8_t byte;
byte = byte << 1;

clr r25
sbrc r24,7
com r25
lsl r24
rol r25

и видим, что операция занимает пять команд?

Примечание: Если кто в комментах подскажет, как оформить этот фрагмент (и последующие) в 2 колонки, буду признателен.

Из кода на ассемблере видно, что байтовая переменная расширяется до целого (16-битов) типа в первых трех командах, а в следующих двух осуществляется собственно сдвиг двухбайтового числа — как то странно, чтобы не сказать больше.

Со сдвигом вправо ничуть не лучше 

byte = byte >> 1;
clr r25
sbrc r24,7
com r25
asr r25
ror r24

— те же пять команд. Между тем очевидно, что на самом деле для выполнения последней операции нужна одна единственная команда 

аsr r24

а для первой операции не больше. Я неоднократно заявлял, что в настоящее время компилятор создает ассемблерный код ничуть не хуже программиста (правда, речь шла о ARM системе команд), особенно если ему немного помочь, и вдруг такой облом. Но попробуем помочь компилятору создать правильный код, может быть дело в смешении типов в операции сдвига и попробуем 

byte = byte >> (int8_t) 1;

— не помогло, от слова «совсем», но вариант 

 byte=(uint8_t) byte >> 1;

дает чуть лучший результат 

ldi r25,lo8(0)
asr r25
ror r24

— три команды, поскольку расширение до целого теперь занимает одну команду — уже лучше, хотя и не идеально, та же самая картина для 

byte=(uint8_t) byte << 1;

— три команды. Ладно, чтобы не писать лишние приведения, делаем саму переменную без-знаковой 

uint8_t byteu;

и БИНГО — ассемблерный код полностью соответствует нашим ожиданиям

byteu = byteu << 1;
lsr r24

Странно как то, казалось бы, какая разница, указать правильный тип переменной сразу, или привести ее непосредственно в операции — а оказывается, разница есть.

Дальнейшие исследования показали, что ассемблерный код учитывает тип переменной, которой присваивается результат, поскольку 

byteu = byte << 1;

работает отлично и производит минимальный код, а вариант 

byte = byteu << 1;

не может обойтись без трех команд.

Наверняка такое поведение описано в стандарте языка, прошу знающих в комментарии, я же в очередной раз с гордостью заявлю, что «чукча не читатель» и продолжу повествование.

Так вот, сдвигу вправо такой прием не помог — по прежнему 3 команды (хорошо. что не 5, как для знакового варианта) и улучшить результат мне никак не удалось никакими способами.
Но в любом случае мы видим, что операции сдвига с без-знаковым числом проводятся быстрее, нежели с его оппонентом. Поэтому, если мы не собираемся трактовать старший бит числа, как знак (а в случае с регистрами это так и есть, как правило) то нам безусловно надлежит добавлять атрибут unsigned, что мы и будем делать в дальнейшем.

Оказывается, со сдвигами вообще все на редкость интересно, начнем увеличивать количество позиций при сдвиге влево и смотреть на результаты: <<1 занимает 1 такт, <<2 — 2, <<3 — 3, 4 — 2 неожиданно, компилятор применил хитрую оптимизацию 

swap r24
andi r24,lo8(-16)

где команда swap меняет местами два ниббла в байте. Далее на основе последней оптимизации <<5 — 3, <<6 — 4, <<7 — 3 опять неожиданно, тут есть другая оптимизация 

ror r24
clr r24
ror r24

использован бит переноса, <<8 — 0 тактов, поскольку просто получается 0, дальше смотреть нет смысла.

Кстати, вот Вам интересная задача — за какое минимальное время можно выполнить операцию 

uint16_t byteu;
byteu = byteu << 4;

которая переводит 0х1234 в 0х2340. Очевидное решение — 4 раза выполнить пару команд 

lsl rl
rol rh

приводит к 4*2=8 тактам, я быстро придумал вариант 

swap rl  ; 1243
swap rh  ; 2143
andi rh,0xf0 ; 2043
mov tmp,rl 
andi tmp,0x0f 
or rh,tmp ; 2343
andi rl,0xf0 ; 2340

который требует 7 тактов и промежуточный регистр. Так вот, компилятор порождает код из 6 команд и никаких промежуточных регистров — круто, да.

Этот код я прячу под спойлер - попытайтесь найти решение сами.
Подсказка: в наборе команд МК есть команда ИСКЛЮЧАЮЩЕЕ ИЛИ или СУММА ПО МОДУЛЮ ДВА eor

Вот он, этот чудесный код
swap rl  ; 1243
swap rh  ; 2143
andi rh,0xf0  ; 2043
eor rh,rl  ; 6343
andi r2l,0xf0  ; 6340
eor rh,rl  ; 2340


Просто получаю эстетическое удовольствие от этого фрагмента.

Что характерно, для 16-битных чисел разница между кодом для знакового и без-знакового числа при сдвиге влево пропала, странно как то.

Вернемся к нашим байтам и начнем двигать вправо. Как мы помним, для знакового байта мы имеем 5 тактов, для без-знакового — 3 и уменьшить это время нельзя. Или все таки можно — да, можно, но уж больно странным способом (GCC с включенными оптимизациями — «это очень уж странное место»), а именно вот таким 

byteu = (byteu >> 1) & 0x7F;

который порождает ровно одну команду для обоих вариантов знака. Подходит и вариант 

 byteu = (byteu & 0xFE) >> 1;

но только для без-знакового числа, со знаковым все становится еще более уныло — 7 тактов, так что продолжаем исследовать только первый вариант.

Не могу сказать, что я понимаю происходящее, ведь очевидно, что логическое умножение (&) на такую константу после такого сдвига нет никакого смысла проводить (и его не проводят), но на код самого сдвига наличие операции & влияет. «Ты суслика видишь — нет — и я не вижу, а он есть».

Сдвиги на 2 и так далее показали, что важно погасить у результата знаковый бит, но ведь число исходно без-знаковое, в общем, фигня какая то получается, «но ведь работает же» — единственное, что можно сказать по этому поводу.

Тем не менее, можно с уверенностью заявить, что интерпретация содержимого регистров и памяти, как без-знаковых чисел, позволяет производить ряд операций (например, сдвиги или расширение значения) с ними проводить быстрее и порождает более компактный код, поэтому может быть настоятельно рекомендована при написании программ для МК, если иное (интерпретация как числа сщ знаком)не является обязательным условием.

Комментарии (35)


  1. AVKinc
    24.01.2019 20:08
    #19658316

    Вот жеж оно что. Познавательно. Спасибо. Учтем.


  1. Amomum
    24.01.2019 20:47
    #19658426

    Тем не менее, можно с уверенностью заявить, что интерпретация содержимого регистров и памяти, как без-знаковых чисел, позволяет производить ряд операций (например, сдвиги или расширение значения) с ними проводить быстрее и порождает более компактный код, поэтому может быть настоятельно рекомендована при написании программ для МК, если иное (интерпретация как числа сщ знаком)не является обязательным условием.

    Не могу сходу согласиться с таким радикальным предложением, поскольку нашли вы его эмпирически для одной конкретной ситуации.
    Взгляните, например, вот на такой пример — godbolt.org/z/lW6rk8 — (courtesy в сторону презентации самого товарища Godbolt'a «What has my compiler done for me lately»).

    Даже очень вдумчивое чтение стандартов С, по моему мнению, не заменяет проверки на практике. И зачастую просто смотреть на ассемблер и считать команды тоже недостаточно, особенно на архитектурах с большим конвейером, кэшом и всякими предсказателями переходов. Я понимаю, статья какбы про AVR, но в старших Cortex'ах это потихоньку появляется…


    1. GarryC Автор
      26.01.2019 11:36
      #19660482

      Ну это конечно, Вы совершенно правы, я только для AVR проверял и рекомендации однозначно распространяются на них, насчет остальных все непросто, как я указывал в посте про корень квадратный.


      1. Amomum
        26.01.2019 11:58
        #19660616
        +1

        А мой пример и на AVR будет работать точно так же :) godbolt.org/z/hKWNlb
        Тут как раз стандарт языка дает объяснение:

        Спойлер
        Переполнение знаковых целых — это неопределенное поведение! Т.е. с точки зрения компилятора это что-то такое, чего никогда не происходит. Ведь программист не допустит неопределенного поведения :)
        А раз это никогда не происходит, значит обычный int не переполняется и проверку на это можно не делать.

        А вот для беззнаковых переполнение точно определено, оно может произойти, поэтому компилятор вынужден вставлять проверку.


  1. boblenin
    25.01.2019 00:01
    #19659012
    +1

    Мне кажется, что если встает вопрос того, насколько эффективно что-то будет сделано компилятором, и встает этот вопрос обоснованно — то надо пользоваться ассемблерными вставками. Может быть я не прав — допускаю.


    1. sepulkary
      26.01.2019 08:03
      #19659546

      Так и есть. Например, в коде для сигнальных процессоров довольно часто мелькают ассемблерные вставки, когда человек «показывает пальцем», как именно надо сделать.


  1. sepulkary
    26.01.2019 08:15
    #19659564
    +1

    Есть мнение, что для того, чтобы указать компилятору на работу именно с 8-бит переменными, нужно использовать конструкцию вида (byte)((byte)a + b).

    В C# эта проблема даже удостоилась упоминания в «CLR via C#» Джеффри Рихтера.


    1. AngReload
      26.01.2019 09:03
      #19659674

      Я конечно же совсем не знаю С, но пост напоминает многие статьи по JS типа "Как не сложить число со строкой".


  1. mpa4b
    26.01.2019 08:55
    #19659648

    Я неоднократно заявлял, что в настоящее время компилятор создает ассемблерный код ничуть не хуже программиста (правда, речь шла о ARM системе команд)

    А вот не соглашусь. С того же годболта: godbolt.org/z/wBK0is. Зачем в 1ой функции cmp r3,#0? Зачем во 2ой функции внутри цикла постоянно(!) выполняются условный и безусловный переходы когда это очевидным способом сокращается до одного условного перехода в цикле, а вход в цикл идёт в его середину?


    1. DrGluck07
      26.01.2019 11:11
      #19660334

      Во второй функции volatile заставляет сохранять в «a» каждое значение. Поэтому всё время выполняется ldr и str. Если переписать так godbolt.org/z/bcPlpK то он уже не мучает переменную «a», но сразу сохраняет значение в «b».
      Вообще компилятор под AVR почти всегда в циклах сохраняет что-то в памяти и в следующей же инструкции достаёт это, хотя регистры очевидно не менялись. И редко использует обратный цикл (в данном случае он и не мог это сделать из-за волатайл).
      Во godbolt.org/z/65gS4V это его любимая фишка.


      1. mpa4b
        26.01.2019 16:46
        #19662500

        Ну так я специально написал volatile и у меня никаких претензий к тому что компилятор при этом постоянно перечитывает переменную нет.


    1. zloe_morkoffko
      26.01.2019 11:29
      #19660440

      Зачем в 1ой функции cmp r3,#0?

      В эту конструкцию транслировалось выражение (while a--).
      Зачем во 2ой функции[...]

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


      1. mpa4b
        26.01.2019 16:45
        #19662478

        В эту конструкцию транслировалось выражение (while a--).

        subs r3,r3,#1 уже выставил флаг нуля, нафиг его ещё раз генерировать при помощи cmp r3,#0? Претензия к этому.

        Поменяйте оптимизацию на O2.

        .L8:
        ldr r3, [sp, #4]
        cmp r3, r2
        bgt .L6
        ldr r3, [sp, #4]
        adds r3, r3, #1
        str r3, [sp, #4]
        b .L8

        Вот это сдвигом того что после bgt — в начало, а того что до — в конец, и заменой bgt на ble преобразуется в цикл без безусловного перехода. Сам безусловный переход отправляется делать вхождение в середину цикла (команды ldr/cmp, которые мы переставили в конец). Итого при ровно том же самом размере получаем выигрыш в быстродействии. Претензия именно к этому.


    1. GarryC Автор
      26.01.2019 11:44
      #19660524

      Конкретно здесь из за volatile, который ставят просто для того, чтобы код в режиме оптимизации просто не свернулся в 0, ведь реальной работы функция не делает.

      Но, вообще то, я имел в виде не то, что компилятор любой фрагмент (в том числе простой) сделает быстрее человека, а то, что в общем человеку крайне трудно учитывать все возможные фичи системы команд (типа сдвигов операндов, формирования констант и т.д.) и, в общем, человек проигрывает.


      1. mpa4b
        26.01.2019 16:50
        #19662530

        Ну честно говоря ваш пример с известной конструкцией xor-and-xor это не показатель, просто компилятор знал про этот трюк а вы нет :)


  1. DrGluck07
    26.01.2019 10:52
    #19660206
    +1

    Компилятор для AVR вообще любит чудачить с оптимизацией. Понятно, что на количество команд действует уровень оптимизации 0, 1, 2, s. Но иногда бывает так, что небольшое изменение в коде на С приводит к пропаданию десятка-другого инструкций.
    Ровно год назад я мучился, пытаясь впихнуть код бутлоадера в 8К. Тогда реально наблюдал ситуации, когда указание знаков/беззнаковых типов или какая-нибудь незначительная перестановка внезапно добавляет 100 байт кода и прошивка начинает занимать 8212 байт, например. Жаль сейчас уже примеры не вспомню. Но удивляло это знатно.


    1. Vitalley
      26.01.2019 11:24
      #19660420

      С AVR не знаком, но XC8 вполне нормально оптимизирует, пишешь на Си и понимаешь что будет на Асме


    1. u_235
      26.01.2019 18:38
      #19663196

      В таких случаях может помочь опция -flto.


      1. DrGluck07
        26.01.2019 19:02
        #19663286

        Я тогда много разных опций перепробовал. Самая беда была, что изначально бутлоадер со сторонней библиотекой весил 13К, потом с оптимизациями 11К. А потом пришлось взять напильник и вырезать часть библиотеки, тогда стало примерно 7600-7700.


  1. u_235
    26.01.2019 11:45
    #19660526

    Вариант

    byte=((uint8_t) byte) >> 1;

    не пробовали?


    1. GarryC Автор
      26.01.2019 12:01
      #19660628

      Кстати, забавно, Ваш вариант не помог — 3 такта но зато вариант
      byte = uint8_t (byte << 1);
      сделал минимальный код, короче, я не понимаю, как работает компилятор (ну это не новость).


      1. u_235
        26.01.2019 17:37
        #19662856

        Ещё забавнее, что вот это
        ubyte = ubyte / 2;
        даёт в итоге одну инструкцию.


      1. u_235
        26.01.2019 18:23
        #19663112

        silver bullet
        Опция компилятора для AVR -mint8, которая делает int однобайтным. Но, как говорится, есть нюансы — может возникнуть переполнение переменных в неожиданных местах.


  1. Mih-mih
    26.01.2019 11:57
    #19660604

    Простите, но тема, скорее, из области «почему для AVR лучше использовать проприетарный компилятор».
    IAR сразу дает однострочный результат LSL/LSR.


    1. GarryC Автор
      26.01.2019 12:06
      #19660662

      К сожалению, данный конкретный компилятор не поддерживает некоторые полезные фичи GCC, иначе я бы его точно рекомендовал.


      1. Mih-mih
        26.01.2019 12:33
        #19660812

        А какие именно, можно узнать?


        1. GarryC Автор
          26.01.2019 12:39
          #19660852

          Точно не дает использовать прагму обязательности использования возврата функции, это я недавно нарвался, а с год назад еще что то было, уже и не вспомню. Но эти фичи не входят в стандарт языка (наверное), они чисто GCC.


          1. Mih-mih
            26.01.2019 13:02
            #19661046

            Понятно. С другой стороны, у IAR есть свои плюшки, начисто отсутствующие в GCC. Ну и код на выходе существенно лучше.


  1. kaSKAdik
    26.01.2019 12:33
    #19660814

    uint16_t byteu;
byteu = byteu << 4;

    У меня образовался буйный восторг от кода компилятора! В одном проекте нужно было решить именно такую задачу. Там не было ограничения ни по ресурсам, ни по времени, а хотелось сделать оптимально из эстетических соображений. На тот момент лучше 7 команд, предложенных вами, я придумать не смог, но чувствовал, что можно!


    1. GarryC Автор
      26.01.2019 12:40
      #19660858

      Да, настоящее программирование в чем то подобно искусству, но только настоящее.
      Помимо восторга, у меня еще остается чувство «Черт, почему это придумал не я, ведь так все просто и очевидно»


      1. kaSKAdik
        26.01.2019 13:18
        #19661154

        Насчёт очевидности: для меня команда eor является понятной, но не интуитивно. И при первом взгляде на код, сразу начинаешь думать о каком-то подвохе: либо код вообще нерабочий, либо годен только для конкретной ситуации, ну или для некоторых входных данных, но не для всех. И только потом осознаёшь гениальность применения команды.
        Однако, не только eor является для меня «неочевидной» в AVR:
        до недавнего времени не использовал команды fmul, пока не потребовалось оптимизировать возведение в квадрат двухбайтного знакового числа;
        cpse использую редко, хотя порой она может сэкономить пару байт;
        ни разу не использовал команды ветвления на флагах N, V и H, но уверен, что есть куча случаев, где их применение оптимально;
        ldd и std порой экономят очередное указание адреса;
        и ещё для ijmp и icall я пока нашёл применение лишь в одном проекте.


        1. GarryC Автор
          26.01.2019 14:01
          #19661422

          Отмечу, что Вы (и я тоже) не являетесь «средним» пользователем МК в плане ассемблера, а достаточно много с ним работаете, и все равно всех тонкостей не используете, поэтому компилятор однозначно такого пользователя обгонит, да и нас тоже, скорее всего, особенно, если мы ему слегка поможем.
          Кстати, первой моей мыслью при виде этого кода была «Да тут ошибка, это не может работать, надо срочно сообщить разработчикам», но она погасла после внимательного взгляда.


  1. Polaris99
    26.01.2019 14:05
    #19661438

    Из серии «Я познаю мир» и «Чудеса на виражах с AVR GCC». CodeVision при всей своей примитивности и допотопности чудесно справляется со сдвигом одной операцией.


    1. u_235
      26.01.2019 14:34
      #19661616

      Это потому, что по умолчанию в настройках проекта CVAVR указано считать char как беззнаковое. Это не противоречит C, но все же необычное поведение.


  1. mpa4b
    26.01.2019 19:10
    #19663322

    gcc.gnu.org/bugzilla/show_bug.cgi?id=82658 не ваш ли случай кстати?