Шесть мыслей о генерации кода на C

Я занимаюсь разработкой компиляторов, то есть пишу программы, преобразующие программы в программы. Иногда требуется нацелиться на более высокоуровневый язык, чем, скажем, простой ассемблер, и зачастую именно в таком качестве удобно взять язык C. Генерировать C не так страшно, как писать от руки — в частности, потому, что генератор умеет не попадать в ловушки, связанные с неопределённым поведением. А когда пишешь на C вручную, именно неопределённого поведения следует особенно остерегаться. Здесь я опишу некоторые паттерны, которые обнаружил сам, и которые помогают мне результативно работать.

Считайте этот пост краткой подборкой тех вещей, которые мне действительно помогают. Рискуя, что меня могут обвинить в тщеславии, назову их «наилучшими практиками», хотя это действительно мои рабочие практики, поэтому, если они вам понравятся — смело берите их на вооружение.

Данные удобно абстрагировать при помощи статических встраиваемых функций

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

Но вот чего я долго не мог оценить по достоинству — так это факт, что функции, которые всегда остаются встроенными, исключают какие-либо потери производительности, связанные с абстрагированием данных. Например, в Wastrel можно описать ограниченный диапазон памяти WebAssembly при помощи структуры memory, а доступ к этой памяти реализовать в другой структуре:

struct memory { uintptr_t base; uint64_t size; };
struct access { uint32_t addr; uint32_t len; };

Затем, если мне нужен доступный для записи указатель на эту память, я могу сделать так:

#define static_inline \
  static inline __attribute__((always_inline))

static_inline void* write_ptr(struct memory m, struct access a) {
  BOUNDS_CHECK(m, a);
  char *base = __builtin_assume_aligned((char *) m.base_addr, 4096);
  return (void *) (base + a.addr);
}

(В Wastrel обычно пропускается какой-либо код для BOUNDS_CHECK, вместо этого просто отображают память на область PROT_NONE подходящего размера. Здесь мы пользуемся макросом, поскольку, если проверка границ не пройдёт и программа завершит процесс, то было бы хорошо иметь возможность  воспользоваться FILE и LINE).

Независимо от того, включены ли явные проверки границ, атрибут static_inline гарантирует полное устранение расходов на абстрагирование. В том случае, когда проверка границ пропускается, нам не требуется знать для доступа ни размера памяти size, ни длины len, поэтому они вообще не будут выделяться.

Если бы write_ptr не был static_inline, меня бы немного обеспокоило, что где-нибудь одно из этих значений struct передавалось бы через память. Это обычно актуально для функций, возвращающих структуры по значению. В свою очередь, например, в AArch64, при возврате struct memory использовались бы те же регистры, которые при вызове void (*)(struct memory) использовались бы для аргумента. Интерфейс ABI SYS-V x64 выделяет всего два регистра общего назначения, в которых будут записываться возвращаемые значения. Я предпочел бы не задумываться об узких местах такого рода, и именно такую задачу для меня решают статические встраиваемые функции.

Избегайте неявного преобразования целых чисел

В C по умолчанию применяется странный набор преобразований целых чисел. Например, uint8_t повышается до signed int, а также действуют странные граничные условия для целых чисел со знаком. При генерации кода на C, следовало бы, пожалуй, отступить от этих правил и действовать явно: определять статические встраиваемые функции преобразования u8_to_u32, s16_to_s32 и т.д., активировав при этом -Wconversion.

При использовании статических встраиваемых функций приведения также можно постулировать в генерируемом коде, что операнды относятся к конкретному типу.

Целенаправленно обёртывайте сырые указатели в целые числа

Whippet — это сборщик мусора, написанный на C. Сборщик мусора при работе пронизывает все абстракции данных: объекты могут трактоваться как абсолютные адреса, или как диапазоны в пространстве страниц памяти, или как смещения от начала области, выровненной по границе памяти и т.д. Если представить все эти сущности как size_t, или как uintptr_t, или как‑либо иначе — то вам не позавидуешь. Поэтому в Whippet есть struct gc_ref, struct gc_edge и т.п.: одночленные структуры, необходимые только для того, чтобы избежать путаницы при членении наборов применимых операций. Вызов gc_edge_address никогда не будет применяться с struct gc_ref, и т.д. для других типов и операций.

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

Например, при компиляции WebAssembly обратите внимание на операционную семантику struct.set: в текстовом представлении сказано: «Утверждени��: по причине валидации val — это некоторая ref.struct structaddr». Ведь было бы здорово, если бы удалось перевести это утверждение на C? Что ж, именно в данном случае это возможно: при образовании подтипов через одиночное наследование (как это делается в WebAssembly), можно реализовать лес подтипов указателей:

typedef struct anyref { uintptr_t value; } anyref;
typedef struct eqref { anyref p; } eqref;
typedef struct i31ref { eqref p; } i31ref;
typedef struct arrayref { eqref p; } arrayref;
typedef struct structref { eqref p; } structref;

Так, для (type $type_0 (struct (mut f64))) можно сгенерировать:

typedef struct type_0ref { structref p; } type_0ref;

Затем я генерирую сеттер поля $type_0 и заставляю его принять type_0ref:

static inline void
type_0_set_field_0(type_0ref obj, double val) {
  ...
}

Именно таким образом типы переносятся из исходного языка в целевой. Существует и похожий лес типов для фактических представлений объектов:

typedef struct wasm_any { uintptr_t type_tag; } wasm_any;
typedef struct wasm_struct { wasm_any p; } wasm_struct;
typedef struct type_0 { wasm_struct p; double field_0; } type_0;
...

Кроме того, мы генерируем маленькие приводящие процедуры, помогающие по мере необходимости перемещаться в обоих направлениях между type_0ref и type_0*. Никаких издержек не возникает, поскольку все процедуры — статические и встроенные, и поэтому мы бесплатно получаем возможность производить подтипы указателей. Таким образом, если инструкция struct.set $type_0 0 получает подтип $type_0, то компилятор может сгенерировать повышающее приведение с сопутствующей проверкой типа.

Не бойтесь memcpy

В WebAssembly обращения к линейной памяти не обязательно выравниваются, поэтому нельзя просто взять и привести адрес к (скажем) int32_t* и разыменовать. Вместо этого мы сделаем memcpy(&i32, addr, sizeof(int32_t)) и доверимся компилятору, чтобы он просто выдал невыровненную загрузку, если сможет (а он сможет). Добавить к этому нечего!

При работе с ABI и хвостовыми вызовами выделяйте регистры вручную

Итак, в GCC наконец-то появился attribute((musttail)) — и слава Богу. Правда, при компиляции WebAssembly может оказаться так, что вы будете компилировать функцию, скажем, с 30 аргументами или 30 возвращаемыми значениями. Я не питаю иллюзий, будто компилятор  C может надёжно переключаться между различными аргументами стека при хвостовых вызовах к такой функции или от неё. Он даже не может отказаться компилировать файл, если не в состоянии соответствовать записанным в нём обязательствам musttail; не лучшая характеристика для целевого языка.

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

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

Что нехорошо

Генерация C — это локальный оптимум. Вы приобретаете по-настоящему мощный механизм подбора инструкций и выделения регистров как в GCC или Clang, при этом вам не приходится реализовывать множество щелевых оптимизаций, при этом обеспечивая связывание с процедурами из среды выполнения, потенциально поддающимися встраиванию. Этот аспект проектирования сложно улучшить даже на самую малость.

Разумеется, есть у такого подхода и недостатки. Мой основной язык — Scheme, поэтому меня наиболее раздражало, что я не контролирую стек. То есть, не знаю, какая часть стека понадобится заданной функции, а также не могу расширить стек моей программы каким-либо разумным образом. Не могу перебрать стек, чтобы точно подсчитать встроенные указатели (но, пожалуй, так и неплохо). Я определённо не могу сегментировать стек так, чтобы захватить ограниченное продолжение.

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

Наконец, гнусно устроена отладка на уровне исходников. Конечно, хотелось бы иметь возможность встраивать DWARF-информацию, соответствующую тому коду, который вы оставляете в остатке; я не знаю, как это сделать при генерации C.

(А почему не на Rust? — спросите вы. Конечно, спросите. Как бы то ни было, я обнаружил, что работа с временами жизни — это проблема на фронтенде. Если код исходно написан на языке с явными временами жизни, то я попробовал бы сгенерировать Rust, поскольку тогда мог бы удостовериться машинными средствами, что для вывода предоставляются те же гарантии, что и для ввода. Как будто я пользуюсь стандартной библиотекой Rust. Но если вы компилируете код с языка, в котором нет затейливых времён жизни, то не знаю, чем Rust вам поможет: да, будет меньше неявных преобразований, но при этом в Rust не столь зрелая поддержка хвостовых вызовов, дольше идёт компиляция… в общем, ерунда, на мой взгляд).

Конечно, нет ничего идеального, и, погружаясь в изучение новой темы, лучше делать это с широко открытыми глазами. Если вы дочитали этот пост, то, надеюсь, мои заметки пригодятся вам при генерации кода. На мой взгляд, после того, как в сгенерированном C проверены типы — он работает. Дополнительной отладки почти не требуется. Не всегда всё идёт так гладко, но я предпочитаю решать проблемы по мере их поступления. Удачи в экспериментах!