Дракон 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 байт данных значительно ускоряет код, хотя и требует дополнительных затрат либо на выравнивание, либо на анализ указателей и написание отдельных “веток” кода. Выравнивание указателей есть не единственный пример повышения производительности выравниванием. Смотри, например, Морской словарь Самойлова: 
"ВЫРАВНЯТЬ ВЕСЛА" — команда, подающаяся на гребных шлюпках, когда весла засушены. По этой команде гребцы равняют весла по загребному так, чтобы все они оказались в одной горизонтальной плоскости и параллельными между собой.

Лисичка и iPod

Расскажу тебе, дружок, о том, как лисичка-сестричка перестала кур таскать и заинтересовалась музыкальными устройствами. Однажды ранним утром я пошел в лес. Почти каждое летнее утро я хожу на наше с приятелем специальное место, чтобы размяться и подышать свежим лесным воздухом. Для того, чтобы не думать всякие неполезные мысли пока идешь, я слушаю сказки, романы и стихи. Для такой цели служит iPod, маленько устройство с надкусанным яблоком на обратной стороне. Наверное, ты видел его у своих родителей, а может оно у тебя есть. В этот раз я слушал “Маленькие трагедии” Александра Сергеевича Пушкина. Попробуй запомнить такие строчки из его произведения

Ныне церковь опустела;
Школа глухо заперта;
Нива праздно перезрела;
Роща темная пуста;
И селенье, как жилище
Погорелое, стоит, —
Тихо все.

Позднее, они помогут тебе узнать и полюбить великого русского поэта.
Придя на полянку, отгороженную молодыми кленами, я положил iPod на упавшее дерево. Раньше оно было могучей сосной. Около 10 лет назад страшная буря повалила деревья в лесу. Даже крепкие сосны не выдержали напора сильного ветра и рухнули, бессильно подняв свои переломанные корни. Теперь они покрываются мхом, трухлеют и постепенно исчезают, превращаясь в дерн.
Я тихо стоял, прислушиваясь к шорохам леса, как вдруг увидел, что рыжая лисичка бесшумно и уверенно семенит по тропинке в мою сторону. Мое неподвижное тело в одежде с зелеными разводами нисколько не встревожило ее. Она приближалась, обшаривая юрким носом следы на тропинке. Иногда поднимала острую мордочку и обнюхивала воздух. И тут она нашла устройство с нарисованным яблоком. Видимо, это было то, что она искала. Не раздумывая, лисичка схватила зубками провод и стала тянуть. iPod молча упал на землю. Кнопка “Играть” осталась не нажатой.
Я шевельнулся от восторга. Лисичка посмотрела на меня. Попробовала потянуть сильнее. Это было нелегко, потому что провод тянулся к коробочке через сучок. Рыжая умница поняла, что интерес к красивой игрушке затормозит ее бегство, отпустила провод и, не торопясь и оглядываясь, пошла по тропинке обратно.
Если ты, дружок, научишься замирать неподвижно, внимательно прислушиваться и наблюдать, то многое сможешь узнать о таинственном лесе и любопытных зверюшках, которые в нем живут.

Прикоснуться к Петру

Предлагается новый вид искусства скульптуры, предполагающий тактильное восприятие прекрасного. Разухабистые фигуры на арбатах такую роль сыграть не могут. В музее или выставочном зале скульптуры трогать запрещено. Думаю, это сильно ограничивает нас в восприятии, а некоторых лишает его совсем. Да и скульптор, очевидно, рассчитывает только на наше зрение. Конечно, есть изваяния, которые трогать не хочется, гипс шершав,  мрамор холоден. Фигуры должны быть из бронзы, меди или дерева, натуральных размеров, без высокого постамента. Я например, с удовольствием потрогал бы Петра работы Шемякина, суставы пальцев рук, череп, складки шарфа, полу сюртука, оказавшуюся отделенной от самого Петра. Ладонь должна накрывать несколько неровностей, морщин и складок. Ничего подобного невозможно достичь на Петре работы Церетели, вряд ли на того можно взобраться без снаряжения и лодки. Такие гиганты, кстати, могли бы стать отдельной разновидностью скульптуры, исследовать и рассматривать которые приходилось бы, взбираясь на нее. Тут Церетели стал бы непревзойденным.
Возвращаясь к воображаемому виду скульптуры, постигаемому через ощущение прикосновения, можно ожидать, что “зрительские” (скорее тактильные) симпатии можно будет легко обнаружить. Представим, например, стоят (или сидят) отполированный Путин и тусклый Медведев. Про женские фигуры особый разговор, их немедленно отнесли бы к эротике, потому что попадание руки на грудь может серьезно изменить состояние воспринимающего.