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


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

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