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) Выравнивайте структуры по размеру слова или двойного слова, даже на архитектурах, теоретически не чувствительных к выравниванию.