Кодогенерация кодогенераторов

[thedeemon]

Я тут когда-то писал о компиляторе своего языка и виртуальной машине к нему. Сейчас он у нас активно используется для обработки видео, т.к. оказался очень удобен в связке с AviSynth. Однако ВМ там - простой интерпретатор байткода, потому все работало не слишком быстро: Y-PSNR для кадра 1920х1080 вычислялся около секунды. Решил прикрутить туда JIT-компиляцию. Взял AsmJit, посмотрел примеры, собрал простой тест, с первого взгляда все работает и выглядит неплохо. Но стоило взяться за дело, как сразу столкнулся с проблемой. У меня ВМ трехадресная, и модификаторы команды определяют смысл операндов (R - register, P - pointer in a register, V - value). Например,
ADD|RRR 6 7 8 это reg6 = reg7 + reg8,
a ADD|PRV 6 7 8 это *reg6 = reg7 + 8,
где reg7 это на самом деле frame[fp + 7], локальная переменная номер семь.
В интерпретаторе ВМ это было реализовано очень просто: переменные
dest, source1 и source2 инициализировались в зависимости от модификаторов текущей команды, а потом она выполнялась:

  while(ip<codelen)
    const int cmd = code[ip];
    switch(cmd & 0xFF) {
      case ADD: LOAD_D; LOAD_A1; LOAD_A2; *dest = source1 + source2; ip += 4; break;
      case MUL: LOAD_D; LOAD_A1; LOAD_A2; *dest = source1 * source2; ip += 4; break;
      ...

где, например,

      
#define LOAD_A1 switch (cmd & (12<<MODSHIFT)) { \
    case AR: source1 = frame[fp + code[ip+2]]; break; \
    case AP: source1 = *(int*)frame[fp + code[ip+2]]; break; \
    case AV: source1 = code[ip+2]; break; \
   }

В AsmJite команды процессора представлены методами класса, а разные виды аргументов сделаны через перегрузку:

      
void  add (const Register &dst, const Register &src); 
void  add (const Register &dst, const Mem &src); 
void  add (const Register &dst, const Immediate &src); 
void  add (const Mem &dst, const Register &src); 
void  add (const Mem &dst, const Immediate &src); 

Поскольку выбор нужного метода делается, опираясь на тип аргументов, определить сперва аргументы, а потом один раз вызвать метод не получится. Выписывать же вручную разные случаи сложно, их более полутора сотен в простой версии ВМ. В итоге пришел к сабжу: тупой скрипт на Руби, генерирующий исходник на С++, который идет по байткоду и генерит машинный код x86.

Каждая операция транслируется независимо от соседей. На выходе получается нечто такое:

case ADD|RRV:
case ADD_RRV:
  if (code[ip+1]==code[ip+2]) {
    a.add(dword_ptr(edi, code[ip+1]*4), imm(code[ip+3]));
  } else {
    a.mov(eax, dword_ptr(edi, code[ip+2]*4));
    a.add(eax, imm(code[ip+3]));
    a.mov(dword_ptr(edi, code[ip+1]*4), eax);
  }
  ip += 4;
  break;
case ADD|RRS:
  if (code[ip+1]==code[ip+2]) {
    a.add(dword_ptr(edi, code[ip+1]*4), ecx);
  } else {
    a.mov(eax, dword_ptr(edi, code[ip+2]*4));
    a.add(eax, ecx);
    a.mov(dword_ptr(edi, code[ip+1]*4), eax);
  }
  ip += 4;
  break;     

Из примерно двухсот строк на Руби получилось 3200 строк на С++.
Первая версия, где результат каждой операции сохранялся в памяти, даже если это временное одноразовое значение, получилась где-то в Пи раз быстрее исходного интерпретатора. Потом добавил очевидную оптимизацию: если результат операции используется только в следующей, то он сохраняется в регистре и в память не пишется. В примере выше это модификатор S: видя его, мой JIT-компилятор знает, что второй операнд уже лежит в регистре ecx. Логика этой оптимизации у меня давно была реализована в компиляторе, но в интерпретаторе особого ускорения не дала. Здесь же ускорение получилось заметным и заJITенный код работает в 4.5 раза быстрее интерпретируемого.

А, да, команда mov_ptr в AsmJit, похоже, сломана, генерит совсем не то.

Comments

[diam-2003.livejournal.com]

Были лы попытки генерировать LLVM IR и скармливать результат LLVM-у?

[thedeemon.livejournal.com]

Нет еще. Может, потом попробую. Тут на весь JIT у меня полтора рабочих дня ушло, подозреваю, что с LLVM гораздо дольше бы разбираться пришлось. Но идея здравая, да.