Дракон LLVM

Интерес к LLVM
Пока зал ремонтируют, а в лес не зайти, проверил C-компилятор LLVM. Проверял только производительность генерируемого кода, хотя возможности среды разработки LLVM значительно шире, например, генерация и выполнение бит-кода, и создание компилятора по вкусу. Скачал исходники и построил в Win32, точнее в cygwin, и Darwin9. Сообщу на всякий случай, что при сборке в Win32 встретил только одно затруднение - с ocaml. Проблема разрешилась установкой правильной переменной окружения OCAMLLIB, которая должна указывать на cygwin версию ocaml. LLVM действительно оказался сильным средством. Не зря его использует Apple. LLVM используется в ocamlopt среды программирования OCaml, его встроили в Haskell, и его используют с Питоном в Google. Разрабатывается реконфигурируемый MPEG видео-декодер LLVM-based scalable MPEG-RVC decoder. Это только крупные видимые проекты. 
Таймирование 
В качестве тестовой задачи написал на С несколько вариантов умножения матриц MMM, так называемые Schoolbook версии со сложностью O(n^3). До блокирования матриц дело не довел, может позднее получится сгенерировать код автоматически. Замечу, что сравнение с MKL имеет смысл только для кода с блокированием. Тест построил следующими компиляторами gcc, Microsoft, LLVM и Intel. Интерес, в основном, был к gcc и llvm, так как они доступны везде и бесплатно. Но затем, когда стало понятно, что llvm хорош, для полноты картины добавил MS и Intel компиляторы. Опции и версии компиляторов:
CL 16.0: -O2 -arch:SSE2 -fp:fast
clang 2.8: -O3 -msse2 -march=core2
ICL 10.0: -O3 /QxP /arch:SSE2
g++ 4.3.4: -O3 -msse2 -march=core2 -funroll-loops.
Тестовая машина: Win32, T2500 1994MHz L2=2048K.
Матрицы: 400x40 * 40x800 = 400x800
Задача - сравнение компиляторов, а не тестирование машины, и не оценка реализации функции умножения матриц. Поэтому ни Штрассен, ни блокирование не обязательны.
Результаты таймирования
Сначала посмотрим на результаты тестов производительности, а затем кратко обсудим LLVM. Результаты даны в MFlops

Супер-производительность кодов компилятора Intel не должна отвлечь нас от рассмотрения других результатов.
В любой задаче, даже сверх-вычислительной, имеет значение, как читается память: последовательно, значит из кэша, или фрагментами за пределами кэша. В наивной версии МММ, так называемой ijk (смотри Golub “Matrix computations”), только для одной матрицы читаем память последовательно без скачков. Для второй, мы читаем данные по столбцу, перемещаясь по памяти через строку, не используя данные в кэше и теряя производительность. В перспективной версии ikj, тоже наивной, данные двух матриц читаются последовательно по строкам. Плата за такое преимущество - дополнительная операция - обнуление матрицы результата перед вычислениями (или заполнение первыми результатами). В обнулении ICL тоже преуспел со своим intel_fast_memset.
MS без опции fp:fast в 2 раза медленнее из-за постоянных преобразований float-double.
GCC хорош, особенно на reference коде. Опция unroll значительно улучшила результаты. Однако, GCC использует только скалярные SSE инструкции и поэтому не может достичь высокой производительности.
ICL очень хорош на MMM реализации ikj с последовательным чтением данных, но тормозит, если программист сам пытается развернуть циклы.
Грубо говоря, имеем 2 кластера производительности на тестовой машине: 1000 MFlops и 2000 MFlops. Во второй можно попасть только с векторизацией и инструкциями для выравненных данных. В этом равных ICL нет.
LLVM
Результаты показывают, что LLVM имеет не плохой компилятор, хотя он значительно моложе gcc. Результаты были бы еще лучше, сумей я заставить его развернуть цикл. Не получилось ни в Win32 с clang, ни в Darwin c llvm-gcc. Даже демо версия компилятора, доступная на сайте online, не разворачивает скалярное произведение векторов. С разверткой он, думаю, уступил бы только ICL. Возможно, что в Linux, LLVM успешно разворачивает и векторизует. Не знаю, пока не было возможности попробовать.
LLVM использует, и дает такую возможность нам пользователям, промежуточное представление кода IR. IR является основой генерации и выполнения байт-кода, и вы можете программировать на его языке, близком к ассемблеру. Насколько близком? Например, для того, чтобы векторизовать основной цикл умножения матриц мне пришлось написать на LLVM ассемблере следующее (фрагмент, внутренний цикл, вычисляющий c+=a*b)

Код дан рисунком, потому что иначе blogger не может сохранить сообщение. Что интересного можно заметить в коде? Видим так называемую phi переменную, которая позволяет присваивание значений в ходе исполнения кода в зависимости от того, откуда инструкции пришло управление. Например, indvar будет присвоено значение indvar.next, если управление передано из текущего блока bb.nph; или 0, если управление пришло извне, в частности, из блока bb.nph14. Случай многократного присваивания значений переменной является специальным, так как в IR действует закон одного присваивания SSA. Видим строгую проверку типов - все операции сопровождаются указаниями типов операндов. Один из типов, а именно <4 x float>, обеспечивает использование SIMD. С параметром “align 4” генерируются инструкции movups, если заменить его на “align 16”, генерируются muvaps. Выгодно то, что код близок к уровню ассемблера и с ним можно идти на любую платформу, чего не скажешь о коде на masm или gas. 
Фрагмент представляет собой самостоятельный блок программы, который можно перемещать. Таким же образом, то есть перемещаемыми, оформляются эпилоги и прологи циклов, что обеспечивает оптимизирующие преобразования циклов - изменение порядка вложенности и слияние циклов. LLVM поддерживает большое количество преобразований кода, в том числе и развертку циклов, которой я безуспешно добивался. Оптимизирующими преобразованиями занимается модуль opt. Он анализирует и преобразует байт-код в оптимизированный байт-код. Чрезвычайно полезен, если код генерируется автоматически. Пользователь может встраивать свои собственные преобразования, которые будут включены в список проходов оптимизатора. 
Генерацией кода на конкретную платформу занимается компилятор llc. Так как полный список поддерживаемых процессоров в документации явно не дан, приведу его здесь: amdfam10, athlon, athlon-4, athlon-fx, athlon-mp, athlon-tbird, athlon-xp, athlon64, athlon64-sse3, atom, barcelona, c3, c3-2, core2, corei7, generic, i386, i486, i586, i686, istanbul, k6, k6-2, k6-3, k8, k8-sse3, nehalem, nocona, opteron, opteron-sse3, penryn, pentium, pentium-m, pentium-mmx, pentium2, pentium3, pentium4, pentiumpro, prescott, sandybridge, shanghai, westmere, winchip-c6, winchip2, x86-64, yonah. 
Последний шаг
Завершил я это короткое изучение написанием кода умножения матриц, версия ikj, на ассемблере c векторизацией на SSE2 инструкции, анализом выравненности указателей и специальным кодом для невыравненных. 

Производительность ассемблерного кода чуть лучше кода, генерируемого ICL и значительно лучше кода LLVM, как С, так и ассемблерного.
Заключение
Если вы решили написать компилятор, создать новый DSL, или решили, что писать на masm и на gas для пары процессоров один и тот же код слишком накладно или слишком “низко”, то LLVM является хорошим кандидатом для того, чтобы стать вашим основным инструментом. 
Если нет, продолжайте использовать MS CL и GCC. С требованием высокой производительности кода следует обратиться к Intel ICL.
Если выравнивание утесняет вашу самобытность
Использование SIMD инструкций для выравненных на 16 байт данных значительно ускоряет код, хотя и требует дополнительных затрат либо на выравнивание, либо на анализ указателей и написание отдельных “веток” кода. Выравнивание указателей есть не единственный пример повышения производительности выравниванием. Смотри, например, Морской словарь Самойлова: 
"ВЫРАВНЯТЬ ВЕСЛА" — команда, подающаяся на гребных шлюпках, когда весла засушены. По этой команде гребцы равняют весла по загребному так, чтобы все они оказались в одной горизонтальной плоскости и параллельными между собой.