Как именно вы спроектировали бы оптимизирующий компилятор? Точнее, как именно вы спроектировали и реализовали бы конкретные оптимизации? Попытка решить эту задачу за один присест — дело ошеломительно сложное и, пожалуй, даже невозможное, так как оптимизации компилятора во многом заключаются в следующем:

1. Выявить ситуацию, в которой мог бы быть применён конкретный трюк;

2. Выстроить анализ, который позволил бы найти такую ситуацию (или её расширенный вариант);

3. Применить этот трюк во всех подходящих точках, которые удастся найти в программе.

Составьте в ряд сотню таких «шагов оптимизации» (возможно, максимально переиспользуя шаг 2) — и вдруг ваш компилятор начинает вносить по-настоящему крупные и сложные изменения, которые сами собой складываются из более мелких!

Когда начинаешь изучать компиляторы, первым делом нужно разобраться со «щелевой оптимизацией» (peephole optimization), которая представляет собой простейший шаг, почти не требующий оптимизации. Кроме того, некоторые из таких оптимизаций, вероятно, выполнимы при помощи конкретных регулярных выражений. В качестве примера — пара простых щелевых оптимизаций:

• replace_muls_with_shifts: x * 2 эквивалентна x << 1 (второй вариант экономнее)

• merge_shifts: (x << 1) << 1 эквивалентна x << 2 (второй вариант экономнее)

Но, позвольте. А что, если у вас будет (x * 2) * 2? Этот вариант можно преобразовать в x << 2! Кстати, для этого нам даже не потребуется писать новую щель, так как для требуемого вычисления можно просто скомбинировать имеющиеся, верно? Просто сделаем так:

(x * 2) * 2
(x << 1) << 1
x << 2

А теперь попробуем на реальном компьютере:

Когда я закончил оптимизацию, готовая программа приобрела вид (x << 1) << 1

УФ. Хотите посмотреть, какой код я не написал?

fn do_optimizations() {
    merge_shifts();
    replace_muls_with_shifts();
}

Оказывается, чтобы это работало, требуется поменять порядок наших щелевых оптимизаций на «неправильный». Ладно, можно их просто переставить. Но, подождите, ведь если таких проходов будет слишком много, оптимального порядка, возможно, вообще не будет, и мы станем постоянно пропускать «очевидные» оптимизации. Требуется ли прогонять этот код в цикле? Если да — то откуда нам знать, когда остановиться?? Думаю, можно было бы проверять, могут ли после внесения изменений потенциально применяться какие-либо новые правила, после чего прогон повторяется??? Но, господи, а где гарантия, что этот цикл вообще остановится???? В самом деле, в какой момент издержки такого подхода перевесят его пользу, в общем, aaAAaaAAAaAAAAA!!!!!

Здесь невозможно† дать однозначных ответов, поэтому вы просто пробуете все варианты, пока не получите нормальных результатов. Затем вы просто стараетесь какое-то время не задумываться о порядке следования операций, пока в очередной раз не натыкаетесь на осиное гнездо – оказывается, уже очень долго две операции выполнялись в строго неверной последовательности. Ещё вероятнее, что при перестановке двух операций компилятор просто откажет, поскольку ранее такую перестановку никто не пробовал, а между этими операциями существует неочевидная зависимость..

Процитирую неизвестного коллегу, которому довелось промучиться в кишках компиляторов гораздо дольше, чем мне:

Проектирование оптимизаций — это наука, но упорядочивание операций — это искусство.

† Когда я это написал, у меня разразилась настоящая катастрофа с упоминаниями в Твиттере, так как я случайно задел половину ведущих мировых экспертов по компиляторам. Они стали забрасывать меня своими любимыми статьями по проектированию оптимизаций. Только и остаётся счесть, что можно собрать идеальный компилятор, а все предыдущие компиляторы – «трусы» и «дураки».

❯ Опасности

Щель merge_shifts, которую я описал в самом начале, слишком проста. Она не сможет обработать даже (x << 2) << 3! В самом деле, хотелось бы иметь возможность заменить все включения (x << y) << z на x << (y + z)!

Компилятор: привет! Да, я превратил x << 30 << 40 в x << 70

Уже гораздо лучше – но, всё-таки, а какой тип у x? Это 64-разрядное целое число? Подождите… тогда у нас проблема. То есть, если вы максимально буквально выразите это на x64, то код будет интерпретирован как x << 6, поскольку инструкция shl просто берёт по модулю (отсекает) переход, так, что он становится равен mod 64. Если хотя бы минимально чувствовать семантику, то совершенно понятно, что раньше программа работала совсем иначе!

То есть, следует несколько внимательнее относиться к нашим оптимизациям. Как правило, будут угрозы, из-за которых оптимизации окажутся недействительны. В описанном случае угроза заключается в том, что «сумма двух переходов окажется слишком большим числом».

Иногда такие опасности легко заметны, но, по мере того, как вы пытаетесь всё более и более генерализовать ваши оптимизации, вы всё чаще будете попадать в малоисследованные ситуации. Например, вы хотите допустить, чтобы один из переходов выражался переменной! Конечно, можно представить себе замену (x << 10) << z) на x << (10 + z), но… как теперь быть уверенным а корректности этого кода? Если переход будет слишком широким, он может превратиться в неопределённое поведение, при котором компилятор будет предполагать z < 64, но при этом ничего не скажет вам о 10 + z < 64!

Таким образом, генерализовать щелевой переход до такой степени просто неразумно, поскольку мы никогда не сможем быть уверены в корректности такого кода (не говоря уж о том, насколько он будет прибылен). Разве что… можно сделать наш анализ умнее! Если интересующий нас код обёрнут в if z < 20 {, то он валиден. Может быть, получится предусмотреть такие структуры данных и виды анализа, которые позволяют отслеживать поток данных и различные факты о коде, помогающие убедиться в отсутствии угроз!

Вдруг оказывается, что мы начинаем выстраивать Серьёзный Оптимизирующий Компилятор, а не просто прописываем какие-то щели!

❯ Упс, а это было важно?

Итак, в данный момент ваш компилятор уже довольно сложен. Вы выстраиваете множество изощрённых структур данных и настраиваете варианты анализа, всего лишь пытаясь доказать валидность определённых оптимизаций (давайте будем называть эту дополнительную информацию «метаданными»). Если с этим удастся справиться, то вы просто перепишете программу/промежуточное представление в новую форму, которая, остаётся надеяться, будет лучше прежней.

Это довольно сложно, поскольку при каждой оптимизации не только приходится выполнить собственный Странный Фокус, но и не забыть заново зафиксировать все метаданные, которые остались в старой версии кода. В частности, речь о debuginfo, которая пытается сопоставить актуальную программу с кодом исходной программы. Это нужно на случай, если пользователь запросит у вас “x”, чтобы вы в таком случае могли понять, в каком именно регистре этот «x» искать. При этом излишне говорить, что есть много таких багов, которые просто случаются, но это не тема данной статьи.

Меня по-настоящему интересует (и ради этого я вообще взялся писать эту статью), что на практике такие оптимизационные ходы обычно деструктивны. Преобразование x * 2 * 2 => x << 2 действует лишь потому, что мы полностью забываем, что исходно здесь производилось умножение — и живём дальше. Аналогично, при многих оптимизациях приходится полагаться на такие вещи как инлайнинг, свёртка констант, отсечение мёртвого кода, чтобы избавляться таким образом от лишних деталей и добиваться максимальной очевидности той Конкретной Ситуации, ради которой предпринимается оптимизация.

И в основном это хорошо! Если чем-то моя программа заниматься не должна я тоже не хочу этим заниматься!

Но вот в чём проблема: при таком множестве оптимизационных проходов, которые сопровождаются реально сложными проверками безопасности оказывается, что, совершенно безобидные на вид вещи оказываются очень многозначительными, и нужны они для того, чтобы при определённых оптимизациях не произошло ничего дурного.

Упс! Так значит, это было важно?

Меня целую вечность будет преследовать проблема, которая сразу отпугивает многих, кто впервые с ней сталкивается: пожалуй, при работе с llvm не следует допускать оптимизации, при которых выкидываются якобы бесполезные приведения указателей к целым числам. Ведь именно такие оптимизации могут приводить к реальным ошибкам компиляции в корректном коде. ДА УЖ.

В принципе, идея такова: компиляторы располагают подробной информацией о том, возможно ли совмещение двух указателей. Если они определённо не совмещаются, то все записи в один из них невозможно наблюдать через другой. Но, если привести два указателя к целым числам для сравнения их адресов, то компилятор входит во вкус и начинает заменять выражения с одним указателем на выражения с другим, где только их найдёт, пока во всём коде «запиши в x, прочитай из x» не превратится в «запиши в y+1, прочитай из x».

В таком случае мы опасно приближаемся к ситуации, в которой компилятор может счесть, что операции чтения и записи никак не связаны, и поэтому операции записи можно удалять. В данном случае остаётся одна надежда: компилятору должно быть известно, что приведение указателя к целому числу — это огромная опасность, выявляемая при анализе совмещений (alias analysis) и крепко об этом помнить… если только при другой оптимизации не выяснится, что приведения указателей к целым числам не нужны и, следовательно, могут быть удалены.

Представьте, как будто Гретель тщательно оставляет за собой дорожку из путеводных крошек, чтобы затем выбраться из леса, а Гензель видит на тропинке Бесплатные Лакомые Крошки — и подъедает их. Сейчас мы заблудились в лесу оптимизаций, и здесь нас вполне может съесть какой-нибудь дракон.

В некотором смысле проблема такова: компьютерные программы ужасно страдают от передачи сигналов внутри полосы. Поэтому даже у самой, казалось бы, безобидной операции, например, у приведения, есть двойное дно, на котором требуется проводить анализ совмещения. Но альтернатива… также довольно путаная. Имея тысячу оптимизаций и десятки вспомогательных структур данных, храня вне полосы всё больше важной информации о программе, на очередном шаге оптимизации становится всё сложнее упомнить о проверке всей важной информации или обеспечить её актуальность.

У меня нет на эти вопросы нормальных ответов. Просто «Вот чёрт!» и «Компиляторы сложны». Можете считать, что я хотел поплакаться. Может быть, rvsdg или какая-нибудь ещё волшебная палочка позволит это исправить, и простым смертным станет по силам судить о семантике компиляторов.

❯ Особенности аппаратных кэш-попаданий

И последнее. Недавно мне довелось узнать, что аппаратные модели памяти якобы гораздо более надёжны и строго определены, чем аналогичные модели, используемые компиляторами. Но почему? И, если так, почему в компиляторах просто не берутся на вооружение модели такого рода?

Насколько могу судить, это просто ещё одно следствие всего вышеизложенного. Мы ожидаем, что компилятор при оптимизациях будет действовать деструктивно, а железо – в большей или меньшей степени «делать то, что приказано». Многие любят подчёркивать, что железо вытворяет множество внутрисистемных фокусов, «компиляторных» по сути, но, в конце концов, железо вполне буквально интерпретирует многие инструкции. Кроме того, всегда есть полный исходный код, который работает прямо на железе.

Аналогично, в ЦП могут предусматриваться какие-то фокусы с кэшем, при помощи которых «на самом деле» операция загрузки или сохранения не выполняется. Тем не менее, процессору всё равно известно, что в данном случае предполагается логическое обращение к памяти, и что все внутриполосные сигналы, сопутствующие этому обращению, опираются на соблюдение определённых гарантий со стороны процессора.

С другой стороны, ожидается, что компилятор увидит операцию загрузки, чтобы можно было кэшировать загруженную информацию или, если потребуется, загрузить, или навсегда удалить – и напоминаний об этом не потребуется. Даже, если бы компилятор опирался на вспомогательную структуру данных, которая бы напоминала о существовании данной загруженной информации, надобность в этой структуре отпадает, как только мы соберём готовый двоичный файл. Она просто исчезает.

И вот почему, дорогие мои

барабанная дробь

На свете существует memory_order_consume, и это катастрофа! memory_order_consume как раз пытается охватить более тонкие гарантии упорядочивания, действующие на уровне железа.

Видите ли, любые инструменты с готовностью предоставляют вам серьёзные гарантии, касающиеся обращений к одним и тем же областям памяти (даже при работе с нестрогими атомарными операциями предусмотрен «общий порядок модификаций» (Total Modification Order)). Но ситуация становится гораздо более зыбкой, когда требуется обеспечить взаимную согласованность двух совершенно не связанных участков памяти. Как правило, решение этой проблемы подразумевает применение тех или иных «барьеров» в памяти, по достижении которых мы приказываем всем ядрам ЦП сделать паузу и «прийти к общему знаменателю», но такая операция очень тяжеловесная и дорогая.

Все аппаратные модели памяти согласуются в следующем: если загружать указатель B из указателя A, то все обращения к B на самом деле относятся к A! Да, тут есть в чём запутаться, давайте рассмотрим на простом примере:

static mut LATEST_DATA: AtomicPtr<u64> = ptr::null_mut();
static mut MY_DATA: u64 = 0;

unsafe fn thread1() {
    MY_DATA = 5;                                // инициализируем наши данные
    LATEST_DATA.store(&mut MY_DATA, Release);   // делимся ими
}

unsafe fn thread2() {
    let latest_ptr = LATEST_DATA.load(Consume); // Получаем новейшие
    let data = *latest_ptr;                     // Считываем данные
    println!("{data}");
}

Один поток записывает некоторые данные в MY_DATA, а потом сообщает всем остальным потокам, чтобы те пошли с ними ознакомились. Для этого он сохраняет указатель на эти данные в LATEST_DATA (с учётом семантики высвобождения (Release), так, чтобы запись в MY_DATA определённо прошла раньше всех считываний). Затем другой поток загружает этот указатель (семантика потребления (Consume), барьер не требуется) из LATEST_DATA и через этот указатель считывает содержимое MY_DATA. Поскольку та операция считывания, с которой связана LATEST_DATA, очевидно требует сначала прочитать указатель LATEST_DATA, здесь складывается очевидная причинно-следственная связь, и никакой дополнительной синхронизации не требуется!

«Сделать какую-нибудь гадость, а потом забросить указатель на эту гадость в структуру данных» — хлеб и масло у всех, кто привык работать с неблокирующими структурами данных. Поэтому мы определённо будем в большом выигрыше, если сможем организовать эту операцию более эффективно (и интуитивно правильно!).

К сожалению, эта удивительно элегантная система полностью разрушается под действием оптимизирующих компиляторов, поскольку мы сами приказываем им прочёсывать код и устранять все операции загрузки и сохранения, какие только возможно. Ваша тщательно проработанная цепочка причинно-следственных связей может обратиться в прах, стоит компилятору счесть, что какая-то операция загрузки избыточна — и удалить её. Более тонкая ситуация возникает, если компилятор заметит, что два указателя гарантированно равны, и перенаправит через один из них все обращения, которые шли через другой!

Упс, это было важно!

В результате все компиляторы трактуют consume просто как немного более затратный аналог acquire, поскольку просто не могут как следует поддерживать его одновременно с поддержкой всех прочих оптимизаций, которые мы от них ожидаем.

Естественно, такая ситуация демотивирует людей, плотно работающих с железом. Вот почему они зачастую просят о каких-то «бессмысленных» вещах, например, о «высвобождении загруженного» . В таком случае вас просят просто соблюсти гарантии, уже действующие на уровне железа: «посмотрите, они же уже здесь». Но, увы, модель памяти, применяемая при работе с памятью, просто не приспособлена к таким гарантиям.

Да уж, компиляторы чертовски сложны.

Читайте также:

• ➤ Можно ли доверить компилятору оптимизацию вашего кода?;

• ➤ STM32. Процесс компиляции и сборки прошивки;

• ➤ Реверс-инжиниринг нативно скомпилированных .NET-приложений;

• ➤ TypeScript: разрабатываем WebAssembly-компилятор;

• ➤ Пишем программы на C# для одноплатников: что, как и где на примере Orange Pi One.

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud - в нашем Telegram-канале ↩