Missed Optimization

Missed Optimization
Часто бывает удобно упаковать несколько логически связанных атрибутов в одну POD структуру и работать с ними, как с единым целым. К томе-же, если структура не большая и целиком помещается в регистры, то это должно быть еще и эффективно. Должно, но…Примеров таких структур много, это может быть точка:
struct Point
{
int x;
int y;
};
Цвет пикселя:
struct Color
{
uint8_t r, g, b;
};
Или мы захотим сделать 3-х байтный указатель для AVR:
struct Ptr24
{
uint16_t low;
uint8_t high;
};
Давайте разберёмся как компиляторы работают с такими структурам. Разбираться будем на примерах для платформы AVR, так как она хорошо многим знакома и имеет относительно простой и понятный ассемблер, к тому-же выравнивание структур на этой платформе равно 1 и по идее не должно оказывать никакого влияния. Хотя всё описанное в равной степени относится и к другим платформам. Сравнивать будем традиционно компиляторы avr-gcc и IAR.
Структура, которую будем использовать для наших тестов:
enum{ Size = 3};
typedef struct
{
uint8_t bytes[Size];
} Bar;
Есть такой хитрый вид оптимизации SRA — scalar replacement of aggregates, при его использовании компилятор начинает рассматривать структуру не как просто кусок памяти определённого размера, а как сумму полей его составляющую. Это даёт компилятору возможность применить другие виды оптимизации, например, хранить структуру в регистрах, избавится от неиспользуемых полей, эффективно её копировать, и передавать как параметр в функции и т. д. Посмотрим как с этим обстоят дела у наших подопытных на практике.
Тест 1. Глобальная переменная:
Bar bar;
void Foo1()
{
PORTA = bar.bytes[0]++;
PORTB = bar.bytes[1]++;
PORTC = bar.bytes[2]++;
}
Ассемблерный листинг:
avr-gcc:
void Foo1()
{
PORTA = bar.bytes[0]++;
92: lds r24, 0x0064
96: out 0x1b, r24
98: subi r24, 0xFF
9a: sts 0x0064, r24
PORTB = bar.bytes[1]++;
9e: lds r24, 0x0065
a2: out 0x18, r24
a4: subi r24, 0xFF
a6: sts 0x0065, r24
PORTC = bar.bytes[2]++;
aa: lds r24, 0x0066
ae: out 0x15, r24
b0: subi r24, 0xFF
b2: sts 0x0066, r24
}
b6: 08 95 ret
IAR for AVR:
void Foo1()
{
PORTA = bar.bytes[0]++;
00000000 LDI R30, LOW(bar)
00000002 LDI R31, (bar) >> 8
00000004 LD R16, Z
00000006 OUT 0x1B, R16
00000008 LD R16, Z
0000000A INC R16
0000000C ST Z, R16
PORTB = bar.bytes[1]++;
0000000E LDD R16, Z+1
00000010 OUT 0x18, R16
00000012 LDD R16, Z+1
00000014 INC R16
00000016 STD Z+1, R16
PORTC = bar.bytes[2]++;
00000018 LDD R16, Z+2
0000001A OUT 0x15, R16
0000001C LDD R16, Z+2
0000001E INC R16
00000020 STD Z+2, R16
}
00000022 RET
Здесь всё впорядке, между компиляторями практически паритет — gcc проигрывает 2 байта памяти, но выигрывает 3 такта по скорости.
Тест 2. Локальная переменная.
void Foo2()
{
Bar bar = {{1, 2, 3}};
PORTA = bar.bytes[0];
PORTB = bar.bytes[1];
PORTC = bar.bytes[2];
}
avr-gcc:
void Foo2()
{
b8: ldi r24, 0x01
ba: out 0x1b, r24
PORTB = bar.bytes[1];
bc: ldi r24, 0x02
be: out 0x18, r24
PORTC = bar.bytes[2];
c0: ldi r24, 0x03
c2: out 0x15, r24
}
c4: ret
IAR:
void Foo2()
{
00000000 LDI R30, LOW(`?<Constant {{(uint8_t)'\\001', (uint8_t)'\\002',`)
00000002 LDI R31, (`?<Constant {{(uint8_t)'\\001', (uint8_t)'\\002',`) >> 8
00000004 LPM R16, Z+
00000006 LPM R17, Z+
00000008 LPM R18, Z
PORTA = bar.bytes[0];
PORTB = bar.bytes[1];
PORTC = bar.bytes[2];
00000000 OUT 0x1B, R16
00000002 OUT 0x18, R17
00000004 OUT 0x15, R18
00000006 RET
}
Оптимизатор GCC сработал как надо, а вот IAR перемудрил сам себя, сохранив инициализатор структуры в памяти программ, в данном случае это было не уместно.
Тест 3. Передача структуры как параметр функции по значению.
void Foo3(Bar i){
PORTA = i.bytes[0];
PORTB = i.bytes[1];
PORTC = i.bytes[2];
}
Структура в данном случае должна передоваться в регистрах, что в принципе и происходит.
Но вот тут у нас начинаются первые чудеса с avr-gcc:
void Foo3(Bar i)
{
c6: push r29
c8: push r28
ca: r28, 0x3d ; 61
cc: in r29, 0x3e ; 62
ce: subi r28, 0x03 ; 3
d0: out 0x3d, r28 ; 61
PORTA = i.bytes[0];
d2: out 0x1b, r22 ; 27
PORTB = i.bytes[1];
d4: out 0x18, r23 ; 24
PORTC = i.bytes[2];
d6: out 0x15, r24 ; 21
}
d8: adiw r28, 0x03 ; 3
da: out 0x3d, r28 ; 61
dc: pop r28
de: pop r29
e0: ret
Как видно он совершенно непонятно зачем создал кадр стека и выделил в нем место на 3 байта — как раз размер нашей структуры, но так им и не воспользовался.
IAR в дела обстоят гораздо лучше и он генерирует вполне годный код:
void Foo3(Bar i)
{
PORTA = i.bytes[0];
00000000 OUT 0x1B, R16
PORTB = i.bytes[1];
00000002 OUT 0x18, R17
PORTC = i.bytes[2];
00000004 OUT 0x15, R18
}
00000006 RET
Тест 4. Передача структуры как параметр функции по значению и ее возврат по значению.
Bar Foo4(Bar i)
{
i.bytes[2] += 10;
return i;
}
Чем дальше в лес, тем интереснее…
avr-gcc чудит еще больше, генерируя совсем непотребный (хотя рабочий) код:
Bar Foo4(Bar i)
{
e2: push r29
e4: push r28
e6: in r28, 0x3d ; 61
e8: in r29, 0x3e ; 62
ea: subi r28, 0x06 ; 6
ec: out 0x3d, r28 ; 61
ee: std Y+4, r22 ; 0x04
f0: std Y+5, r23 ; 0x05
i.bytes[2] += 10;
return i;
f2: subi r24, 0xF6 ; 246
f4: std Y+6, r24 ; 0x06
f6: movw r26, r28
f8: adiw r26, 0x01 ; 1
fa: movw r30, r28
fc: adiw r30, 0x04 ; 4
fe: ldi r24, 0x03 ; 3
100: ld r0, Z+
102: st X+, r0
104: subi r24, 0x01 ; 1
106: brne .-8 ; 0x100 <Foo4+0x1e>
108: ldd r22, Y+1 ; 0x01
10a: ldd r23, Y+2 ; 0x02
}
10c: ldd r24, Y+3 ; 0x03
10e: ldi r25, 0x00 ; 0
110: adiw r28, 0x06 ; 6
112: out 0x3d, r28 ; 61
114: pop r28
116: pop r29
118: ret
Здесь GCC инициализировал кадр стека выделил место под две структуры. Скопировал в первый буфер значения параметра из регистров, модифицировав один нужный байт, потом скопировал первый буфер во второй. После чего извлёк значение из стека опять в регистры, да, да, в те-же в которых оно и было, при вызове функции, вернул стек на место и вышел из функции. Жесть!
IAR тут повел себя лучше, но не на много. Он скопировал параметры в стек только один раз :) Ну и за счёт того, что в IAR отдельный стек данных и он уже заранее подготовлен, код получается покомпактней. Но всё равно, зачем копировать параметр в стек и тутже извлекать его обратно?!!!
Bar Foo4(Bar i)
{
00000000 SBIW R29:R28, 3
00000002 ST Y, R16
00000004 STD Y+1, R17
00000006 STD Y+2, R18
i.bytes[2] += 10;
00000008 LDD R16, Y+2
0000000A SUBI R16, 246
0000000C STD Y+2, R16
return i;
0000000E LD R16, Y
00000010 LDD R18, Y+2
00000012 ADIW R29:R28, 3
00000014 RET
}
Это явный баг в оптимизаторах обоих компиляторах, только у IAR он несколько нивелирован отдельным стеком данных. В GCC этот баг проявляется на всех платформах, начиная на x86 и заканчивая ARM и AVR и отмечен в баг-трекере более десяти раз под разными названиями. Присутствует начиная с GCC 4.2. и по сей день в GCC 4.6. Причем на платформах чувствительных к выравниванию данных, например на ARM, помимо игрищь со стеком начинаются еще и пляски с выравниванием данных.
И самое интересное, размер структуры в самом начале, я выбрал равным 3 байтам не случайно, если его сделать кратным слову, или двойному слову, например, 2, 4 или 8 байт, то все эти извращения волшебным образом исчезают и GCC начинает генерировать совершенно идеальный код, вида:
Bar Foo4(Bar i)
{
b8: subi r24, 0xF6 ; 246
ba: ret
}
В IAR-е размер структуры и выравнивание никак качественно не влияют на генерируемый код, и он упорно продолжает складывать структуру в стек.
Выводы:
1) Не доверяйте компиляторам, всегда проверяйте, что он там нагенерировал.2) Выравнивайте структуры по размеру слова или двойного слова, даже на архитектурах, теоретически не чувствительных к выравниванию.
- +11
- 12 мая 2011, 18:48
- neiver
Да уж, тоже по этим граблям походил… При работе со структурами (особенно, содержащими массивы), листинг контролировать надо всегда. И если ГЦЦ начал выкобениваться надо шаманить с кодом =). Иногда бывает перепишешь тоже самое, но с другой стороны, и нагенерированное становится раза в полтора-два короче =)
Чего то я совсем забыл ассемблер.
Не подскажете, где там в тесте 4е компилятор «инициализировал кадр стека выделил место под две структуры.»?
Не подскажете, где там в тесте 4е компилятор «инициализировал кадр стека выделил место под две структуры.»?
- MasterAlexei
- 12 мая 2011, 22:07
- ↓
e2: push r29
e4: push r28
e6: in r28, 0x3d ; 61
e8: in r29, 0x3e ; 62
ea: subi r28, 0x06 ; 6
ec: out 0x3d, r28 ; 61
вот этот фрагмент. Сохранили call-saved регистры, прочитали указатель стека, уменьшили на 6 — удвоенный размер структуры, и записали обратно. В r28-r29 у нас указатель на выделенное место.
Ок. А дальше он чего с ними делает?
Я так понял, он всю арифметику с прибавлением 10ти к элементу массива в стеке выполнил. Или нет?
Я так понял, он всю арифметику с прибавлением 10ти к элементу массива в стеке выполнил. Или нет?
- MasterAlexei
- 12 мая 2011, 22:29
- ↑
- ↓
Нет. В стек уже попадает изменённое значение, а потом копируется еще раз. Странное поведение.
Похожие баги:
gcc.gnu.org/bugzilla/show_bug.cgi?id=23782
gcc.gnu.org/bugzilla/show_bug.cgi?id=28831
Там где-то в комментариях есть предположения почему так происходит.
Похожие баги:
gcc.gnu.org/bugzilla/show_bug.cgi?id=23782
gcc.gnu.org/bugzilla/show_bug.cgi?id=28831
Там где-то в комментариях есть предположения почему так происходит.
Круто.
При работе с GCC вообще сложилось впечатление, что он что-то чересчур много плясок при входе/выходе в функции делает. Правда, особо пристально не присматривался, да и не так уж много его юзал.
А на багтрекеры кто-нибудь это дело разослал? Просто есть почему-то такая традиция — красиво и подробно расписывать баги в статьях, а разработчикам о них не сообщать )
При работе с GCC вообще сложилось впечатление, что он что-то чересчур много плясок при входе/выходе в функции делает. Правда, особо пристально не присматривался, да и не так уж много его юзал.
А на багтрекеры кто-нибудь это дело разослал? Просто есть почему-то такая традиция — красиво и подробно расписывать баги в статьях, а разработчикам о них не сообщать )
Ну, во первых баг не сильно критичный. Все ж работает. Во вторых, кто-то в комментах говорил, что баг на самом деле не столь прост и лучше передавать структуры более понятным для компилятора способом.
В результате баг периодически отпихивают на более поздний milestone)
В результате баг периодически отпихивают на более поздний milestone)
Для x86 и ARM он действительно не критичен. На x86 так и вовсе если параметры передаются в стеке, то всё хорошо, а если в регистрах (fastcall функция), то всего пара лишних инструкций. А вот для AVR разница между правильным кодом и тем, что есть примерно в 15 раз! Это уже серьёзно, и делает невозможным применение некоторых методик разработки.
Так и IAR туда-же. У него код конечно только в 5-6 раз распухший, но зато всегда. GCC начинает ченерировать правилльный код если структуру выровнять, а IAR вообще SRA для passthrow функций никогда не делает. Печаль…
Так и IAR туда-же. У него код конечно только в 5-6 раз распухший, но зато всегда. GCC начинает ченерировать правилльный код если структуру выровнять, а IAR вообще SRA для passthrow функций никогда не делает. Печаль…
Согласен, неприятно. И вообще подводные камни знать следует, так что плюсанул статью. Я только предполагаю, почему авторы GCC до сих пор баг игнорят. Тем паче, основная платформа для них, я полагаю, х86.
Ну и 15 раз — на наиболее примитивных функциях. Я думаю, если со структурой проводить более сложные операции — они нивелируют оверхед плясок со стеком.
А что значат сокращения? POD, SRA, passthrow функции?
Ну и 15 раз — на наиболее примитивных функциях. Я думаю, если со структурой проводить более сложные операции — они нивелируют оверхед плясок со стеком.
А что значат сокращения? POD, SRA, passthrow функции?
POD — plain old data — обычная структура в Си/Си++ — просто данные, возможно с обычными функциями членами, но без конструкторов копирования, наследования и виртуальных функций и т.д.
SRA — scalar replacement of aggregates — в статье расшифровывается.
passthrow функци — принимает аргумент по значению модифицирует и ворвращает результат тоже по значению. Очень многие перегруженные операторы в Си++ именно такие. В статье Foo4 и есть такая функция.
SRA — scalar replacement of aggregates — в статье расшифровывается.
passthrow функци — принимает аргумент по значению модифицирует и ворвращает результат тоже по значению. Очень многие перегруженные операторы в Си++ именно такие. В статье Foo4 и есть такая функция.
Проверил тестовые примеры на avr-gcc 4.7.2 — похоже, что баг исчез.
Так, 4-й тест скомпилировался в те же две иструкции, что и при размере структуры, кратном слову. А WinAvr(gcc 4.3.3) выдал ту же
«портянку» ассемблерных инструкций, что в примере в статье. Ради
спортивного интереса проверил, что выдаст IAR. Так, IAR AVR 6.12 выдал то же, что и в статье. Баг avr-gcc пофиксен? Или я рано радуюсь?
Neiver'у — огромное спасибо за столь мощные статьи.
Так, 4-й тест скомпилировался в те же две иструкции, что и при размере структуры, кратном слову. А WinAvr(gcc 4.3.3) выдал ту же
«портянку» ассемблерных инструкций, что в примере в статье. Ради
спортивного интереса проверил, что выдаст IAR. Так, IAR AVR 6.12 выдал то же, что и в статье. Баг avr-gcc пофиксен? Или я рано радуюсь?
Neiver'у — огромное спасибо за столь мощные статьи.
Комментарии (17)
RSS свернуть / развернуть