Об одной ошибке оптимизации времени выполнения

:

Изначально пост планировалось посвятить ошибке 64х-битового компилятора xlc которую я безуспешно отлавливал многие часы и которая имеет место быть на серверах фирмы IBM архитектуры AIX. Но так уж получилось, что подобная ошибка затрагивает многие компиляторы, не стал исключением и Visual Studio 2010 с установленным пакетом обновления SP1. Что в итоге кажется забавным, так как наводит на мысли, что специалисты Microsoft сотрудничают с разработчиками из IBM в деле создания оптимизирующих компиляторов.

Немного предыстории. Есть один научный проект, который был написан на С++ достаточно давно и сейчас успешно переносится на многие платформы, среди которых можно отметить мейнфреймы HP-UX, IBM AIX, Oracle Solaris. Перенос по большому счету состоит в том, что исправляются ошибки времени компиляции, запускается группа тестов и если все тесты проходят, то делается вывод о работоспособности кода.

Так как скорость выполнения математических процедур очень даже важна, компиляция проходит с включенным ключом оптимизации по скорости -O2. Но на архитектуре IBM AIX компилятор xlc почему-то не может создать работоспособный код, удовлетворяющий набору тестов. В то же время без ключа -O2 все работает нормально.

Я бы, конечно, мог попробовать отловить эту ошибку непосредственно на мейнфрейме IBM AIX, будь у меня в запасе достаточно времени, но за отсутствием отладчика (в debug mode ошибка не проявлялась) ловить приходилось по-старинке, методом вставки printf в участки кода. Удаленный доступ к IBM AIX мне так и не дали, приходилось работать непосредственно в дата-центре и за те несколько часов, проведенных за терминалом, ничего внятного понять не удалось, кроме того, что ошибка имеет место быть и достаточно устойчивая. В итоге, ошибка так и сидела в коде на протяжении долгого времени.

Так продолжалось до тех пор, пока я не попробовал перенести код на Visual Studio 2010 SP1.

И о чудо! Ошибка проявила себя в том же первозданном виде, а именно в 32х-битовом режиме все работает нормально и при включении флага -O2 и без этого, а в x64 при включенном -O2 один из тестов «ругается» в точности так же, как это было на IBM AIX! Это победа, потому что теперь я мог, не ограничивая себя временными рамками, вдумчиво копать непаханное поле кода, экспериментируя и последовательно сравнивая результаты printf при правильном и неправильном прохождении тестов.

Результат не заставил себя долго ждать. Ниже будет приведена выжимка из полного кода, это наиболее сокращенный в размерах код. Данный код не работает и в 32х-битовом режиме тоже, так как параметр N равен 4. Если же установить #define N 8, то мы получим изначальный код, работающий на 32х битах, но неработающий на x64. Для простоты (не у всех есть x64, а многие, наверное, захотят попробовать) привожу исходный код, неработающий на любой архитектуре.

Итак, попробуем откомпилировать вот этот код с ключом -O2 и без него:

#include <stdio.h>
#define N 4
unsigned char a[N];
void f(unsigned int k) 
{
    int i;
    for(i=0;i<N;++i) {
        a[i]=k&0xf;
        k>>=4;
    }
}
int main(void) 
{
    int i;
    static unsigned int x=0x76543210;
    f(x);
    if (a[3]==2) {
        printf("Error!\n");
    }
    for(i=0;i<N;i++) {
        printf("%02x ", a[i]);
    }
    printf("\nsizeof(void*)=%d\n", sizeof(void*));
    return 0;
}

Код программы запишем в файл test32.c

Для компиляции воспользуемся Visual Studio 2010 SP1 и будем делать код для 32х разрядной операционной системы. Сборку и запуск проведем при помощи такого командного файла:

call "C:\Program Files\Microsoft Visual Studio 10.0\VC\vcvarsall.bat"
cl /nologo test32.c /Fano_opt >nul
echo Без оптимизации
test32
pause
echo Оптимизация включена
cl /nologo -O2 test32.c /Fawith_opt >nul
test32

После запуска получим результаты:
Setting environment fоr using Microsoft Visual Studio 2010 x86 tools.
Без оптимизации
00 01 02 03 
sizeof(void*)=4
Press any key to continue . . .
Оптимизация включена
Error!
00 01 02 02
sizeof(void*)=4

Видно, что после оптимизации получается 00 01 02 02 вместо 00 01 02 03.

Почему так происходит?

Рассмотрим ассемблерный файл with_opt.asm полученный при включенной оптимизации.

Ассемблерный файл no_opt.asm полученный при выключенной оптимизации нам не очень интересен, так как там все работает нормально. Желающие могут найти его у себя в рабочей директории.

Оптимизация включена:

_TEXT	SEGMENT
_main	PROC						; COMDAT
; Line 16
	mov	eax, DWORD PTR ?x@?1??main@@9@9
	mov	cl, al
	shr	eax, 4
	mov	dl, al
	shr	eax, 4
	and	al, 15					; 0000000fH
	and	cl, 15					; 0000000fH
	and	dl, 15					; 0000000fH
	mov	BYTE PTR _a, cl
	mov	BYTE PTR _a+1, dl
	mov	BYTE PTR _a+2, al
	mov	BYTE PTR _a+3, al
; Line 17
	cmp	al, 2
	jne	SHORT $LN4@main
; Line 18
	push	OFFSET ??_C@_07NPIJMNAB@Error?$CB?6?$AA@
	call	_printf
	add	esp, 4
$LN4@main:

Легко заметить, что вызов функции f() реально не происходит, компилятор сразу же рассчитывает значения переменной x и заполняет массив а. Причем при оптимизации заполнение происходит неправильно, элементы массива _a+2 и _a+3 заполняются одними и теми же значениями из регистра al.

Это же верно при компиляции 64х-разрядного исполняемого файла. Для работы с 64х-битным кодом заменим первую строку в командном файле:

call "C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\vcvarsall.bat" amd64

Получим такой же неправильный результат, но только при sizeof(void*)=8, что подтверждает 64х-битность полученного кода:
Setting environment fоr using Microsoft Visual Studio 2010 x64 tools.
Без оптимизации
00 01 02 03 
sizeof(void*)=8
Press any key to continue . . .
Оптимизация включена
Error!
00 01 02 02 
sizeof(void*)=8

Ассемблерный x64 код выглядит так:
main	PROC						; COMDAT
; Line 15
$LN21:
	push	rbx
	sub	rsp, 32					; 00000020H
; Line 16
	mov	ecx, DWORD PTR ?x@?1??main@@9@9
	movzx	eax, cl
	shr	ecx, 4
	and	al, 15
	mov	BYTE PTR a, al
	movzx	eax, cl
	shr	ecx, 4
	and	cl, 15
	and	al, 15
	mov	BYTE PTR a+1, al
	mov	BYTE PTR a+2, cl
	mov	BYTE PTR a+3, cl
; Line 17
	cmp	cl, 2
	jne	SHORT $LN4@main
; Line 18
	lea	rcx, OFFSET FLAT:??_C@_07NPIJMNAB@Error?$CB?6?$AA@
	call	printf
$LN4@main:

Легко увидеть, что здесь также не происходит вызов функции f(), а компилятор сразу рассчитывает значения переменной x и заполняет массив а. При этом элементы массива _a+2 и _a+3 заполняются одними и теми же значениями из регистра cl, что неправильно.

В итоге исходный код функции f() был исправлен таким образом:

void f(unsigned int k) 
{
    int i;
    for(i=0;i<N;++i) {
        a[i]=(k>>4*i)&0xf;
    }
}

И тут же все прекрасно заработало как на Visual Studio x86/x64 так и на xlc для IBM AIX.

Скорость выполнения тестов с ключом -O2 в итоге увеличилась примерно в 2,5 — 3 раза.

UPD: Для исключения недоразумений, поменял в коде знаковый тип int на unsigned int, ошибка осталась. Предыдущий вариант можно посмотреть здесь

UPD2: Получен официальный ответ из Microsoft:
Posted by Microsoft on 02.11.2011 at 11:17

Thanks for reporting this issue. I can confirm this problem with VS2010 SP1. It will be fixed in the next major release of Visual Studio.

ian Bearman
VC++ Code Generation and Optimization Team