Missed Optimization

AVR

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

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

RSS свернуть / развернуть
Забавненько.
Ну, оно работает хотя бы. И по сравнению с mP просто таки идеальный код)
А постоянно контролировать листинг… Ну, на мелких МК это еще реально…
0
  • avatar
  • Vga
  • 12 мая 2011, 19:20
Я имею ввиду, что нужно хотябы знать во что компилятор пережевывает типичные для вашего стиля разработки конструкции. Казалось-бы вполне нормально и эффективно маленькую структуру передавать и возвращать по значению. А вот и не всегда…
0
Да уж, тоже по этим граблям походил… При работе со структурами (особенно, содержащими массивы), листинг контролировать надо всегда. И если ГЦЦ начал выкобениваться надо шаманить с кодом =). Иногда бывает перепишешь тоже самое, но с другой стороны, и нагенерированное становится раза в полтора-два короче =)
0
Чего то я совсем забыл ассемблер.
Не подскажете, где там в тесте 4е компилятор «инициализировал кадр стека выделил место под две структуры.»?
0
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 у нас указатель на выделенное место.
0
Ок. А дальше он чего с ними делает?
Я так понял, он всю арифметику с прибавлением 10ти к элементу массива в стеке выполнил. Или нет?
0
Нет. В стек уже попадает изменённое значение, а потом копируется еще раз. Странное поведение.
Похожие баги:
gcc.gnu.org/bugzilla/show_bug.cgi?id=23782
gcc.gnu.org/bugzilla/show_bug.cgi?id=28831
Там где-то в комментариях есть предположения почему так происходит.
0
Круто.
При работе с GCC вообще сложилось впечатление, что он что-то чересчур много плясок при входе/выходе в функции делает. Правда, особо пристально не присматривался, да и не так уж много его юзал.

А на багтрекеры кто-нибудь это дело разослал? Просто есть почему-то такая традиция — красиво и подробно расписывать баги в статьях, а разработчикам о них не сообщать )
0
Этот баг уже под десятком имен и в разных проявлениях зарепорчен начиная 2006 года.
+1
Мда, с одной стороны, это очень хорошо. С другой, очень плохо ))
0
Ну, во первых баг не сильно критичный. Все ж работает. Во вторых, кто-то в комментах говорил, что баг на самом деле не столь прост и лучше передавать структуры более понятным для компилятора способом.
В результате баг периодически отпихивают на более поздний milestone)
+1
Для x86 и ARM он действительно не критичен. На x86 так и вовсе если параметры передаются в стеке, то всё хорошо, а если в регистрах (fastcall функция), то всего пара лишних инструкций. А вот для AVR разница между правильным кодом и тем, что есть примерно в 15 раз! Это уже серьёзно, и делает невозможным применение некоторых методик разработки.
Так и IAR туда-же. У него код конечно только в 5-6 раз распухший, но зато всегда. GCC начинает ченерировать правилльный код если структуру выровнять, а IAR вообще SRA для passthrow функций никогда не делает. Печаль…
0
Согласен, неприятно. И вообще подводные камни знать следует, так что плюсанул статью. Я только предполагаю, почему авторы GCC до сих пор баг игнорят. Тем паче, основная платформа для них, я полагаю, х86.
Ну и 15 раз — на наиболее примитивных функциях. Я думаю, если со структурой проводить более сложные операции — они нивелируют оверхед плясок со стеком.
А что значат сокращения? POD, SRA, passthrow функции?
0
POD — plain old data — обычная структура в Си/Си++ — просто данные, возможно с обычными функциями членами, но без конструкторов копирования, наследования и виртуальных функций и т.д.
SRA — scalar replacement of aggregates — в статье расшифровывается.
passthrow функци — принимает аргумент по значению модифицирует и ворвращает результат тоже по значению. Очень многие перегруженные операторы в Си++ именно такие. В статье Foo4 и есть такая функция.
0
Отличная статья, спасибо.

Только вот…

#pragma spellcheck=ON

помимо игрищь со стеком начинаются еще и пляски

игрищ_, OK? :-)
-1
Проверил тестовые примеры на avr-gcc 4.7.2 — похоже, что баг исчез.
Так, 4-й тест скомпилировался в те же две иструкции, что и при размере структуры, кратном слову. А WinAvr(gcc 4.3.3) выдал ту же
«портянку» ассемблерных инструкций, что в примере в статье. Ради
спортивного интереса проверил, что выдаст IAR. Так, IAR AVR 6.12 выдал то же, что и в статье. Баг avr-gcc пофиксен? Или я рано радуюсь?
Neiver'у — огромное спасибо за столь мощные статьи.
0
  • avatar
  • ulole
  • 10 февраля 2013, 23:27
Да для размера структуры 3 байта — всё как надо. Но если ее сделать 5 и более байт, то всё по прежнему, та-же портянка. Недочинили.
0
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.