Будни компиляторостроителя

[thedeemon]

Делал недавно по просьбам общественности 64-битную версию своего нового плагина для VirtualDub. Собрать-то его для x64 проблем нет (разве что пару функций на асме с MMX пришлось выкинуть, на скорости это не отразилось), да только внутри у него неонка виртуальная машина, а в ней указатели и целые числа вперемешку хранятся и используются, так что пришлось ее перевести на int64. Добавил в компилятор новый режим - компиляция в 64 бита, там всех изменений - только работа с массивами, т.к. размер элементов другой. Плюс, добавил в Leo новый тип - int32, чтобы с RGB32 работать нормально (а обычный int сделался 64-битным). На простых тестах все заработало сразу, а "боевая" программа стала в 64-битном режиме падать. Там байткода на десятки тысяч команд, как узнать в чем ошибка? Стал добавлять в компилятор то, что обязано быть в каждом приличном компиляторе, но что обычно оставляют за кадром во всех книжках и примерах - протаскивание информации о координатах в исходнике через все фазы компиляции. Чтобы если ошибка происходит при IP=2345, знать, к какой строке исходной программы на Leo это относится.

Как я уже рассказывал, синтаксический разбор в Leo устроен на парсер-комбинаторах с мемоизацией, разбирающих последовательность лексем, созданную ocamllex'ом. В этом ocamllex'e есть структура, хранящая в процессе работы текущую позицию в разбираемом тексте, но автоматически там обновляется только один счетчик позиции, остальные счетчики (номер строки и пр.) нужно обновлять вручную. В общем, сделал, чтобы сгенеренный ocamllex'ом лексер возвращал поток пар лексема-координата, где координата описывается неким моим типом, непрозрачным для большей части кода.

Затем добавил координаты в свои парсер-комбинаторы:

type ('res, 'tok, 'src) parse_result = Parsed of ('res * 'src) * 'tok list | Failed;; 

При успешном разборе возвращается пара значение-координата. Базовые комбинаторы (вроде "ab" и "a+") были обновлены таким образом, что координатой сложной конструкции (из нескольких лексем) считалась координата ее начала.

Затем добавил координаты в типы данных AST. Типы для выражений и стейтментов заменил на пару из старого типа и координаты. Было

type code = statement list 
and statement 
  | Def of name * name list * expr 
  | Write of lvalue * expr 
  | Print of expr list 
  ...

а стало

type code = statement list 
and statement = raw_statement * source_loc 
and raw_statement = 
  | Def of name * name list * expr 
  | Write of lvalue * expr 
  | Print of expr list 
  ...

Т.к. конструкторы не поменялись, изменений в коде потребовалось сравнительно немного. Но все равно немало. Хотел бы я знать, как можно добавлять в алгебраические типы (мета-)информацию меньшими усилиями.
Аналогично координаты были добавлены в остальные слои компилятора - LeoC, Triasm, Asm. При компиляции информация о координатах просто аккуратно переносилась из каждого слоя в конструкции более низкоуровнего слоя.

Наконец, был изменен вывод ассемблерного текста: перед каждой последовательностью команд, относящихся к одной строке исходника, выводится исходный текст, а рядом с командой пишется ее смещение (значение регистра IP при исполнении ВМ). Например, для такой программы

a = new byte[100]
for i in a.range
 a[i] <- i + 1
end

Выводится такой текст:

/// a = new byte[100]
NEW|RVR, 1, 100, //IP: 0
MOV_RR, 2, 1, //IP: 3
/// for i in a.range
MOV_RV, 3, 0, //IP: 6
JMP, 26, //while_cond_7 //IP: 9
//11 - while_body_7: //IP: 11
///  a[i] <- i + 1
ADD_RRR, 4, 2, 3, //IP: 11
ADD_RRV, 5, 3, 1, //IP: 15
MOVB|PRR, 4, 5, //IP: 19
/// for i in a.range
INC, 3, 0, 0, //IP: 22
//26 - while_cond_7: //IP: 26
JMPLE|RRV, 11, 3, 100, //while_body_7 //IP: 26
//30 - endif_8: //IP: 30
//30 - endloop_7: //IP: 30

На все это ушло несколько дней неспешных ковыряний, и когда такой листинг был получен для исходной падающей программы, ради которой все затевалось, ошибка в ней стала совершенно очевидна: просто забыл поменять тип массива с картинкой с int[] на int32[]. Добавил эти два символа ("32") и все заработало. Вот она, цена элементарных ошибок. :)

Comments

[xeno-by.livejournal.com]

А как обычно протаскивается дебажная инфа в случае, когда внутри компилера еще находятся оптимизирующие преобразования? Понятно, что для этого нет общего решения - интересуют любые находки.

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

[thedeemon.livejournal.com]

Как обычно - не знаю.
У меня оптимизация сводится к упрощению выражений (в паре выражение-координата меняется одна часть, координата остается), copy propagation (координата копируемого приходит вместе с содержимым) и dead code elimination (тут и вопроса нет).
Мне кажется, в каждом конкретном случае несложно определить, что именно оптимизируется, и протащить ссылку на координаты.

[mr-aleph.livejournal.com]

в ручную по-мойму всегда это делается, с одного представления на другое таскается в какой-нибудь форме.

[gds.livejournal.com]

> Хотел бы я знать, как можно добавлять в алгебраические типы (мета-)информацию меньшими усилиями.

Конкретно в окамле -- по слухам, очень просто, но слегка по-читерски: weak hashtables. Функтор Weak.Make, однако есть ещё его модификации (в интернетах), и надо смотреть, что именно нужно. Не подскажу, так как сам не пользовал (а только намеревался).

[mr-aleph.livejournal.com]

изящное решение