Как стать автором
Обновить

Комментарии 16

Frame pointer — лишняя сущность. Всё можно адресовать относительно вершины стека. И всегда известно сколько из него вычесть при возврате.

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

При компиляции любого выражения, компилятор знает, сколько временных объектов было помещено в стек. Это число — глубина самой вложенной локальной переменной относительно вершины стека. Остальные локалы находятся в соседних более глубоких элементах стека. Также копилятор знает количество локалов в данной точке. Сложив эти два числа компилятор получит смещение в стеке до элемента, хранящего адрес возврата. Сразу за адресом возврата в стеке лежат параметры, количество которых тоже известно компилятору.
То есть алгоритм такой:
Заводим в компиляторе три переменные:


  • params_count — количество параметров текущей функции (если язык разрешает переменное количество параметров — эта переменная хранит количество именованных парметров, а остальные пакуются в iterable контейнер, который становится еще одним параметром)
  • locals_count — количество живых локалов — от начала функции до текущег компилируемого выражения.
  • temps_count — глубина стека в текущем компилируемом выражении.

Добавляем в виртуальную машину две инструкции push_local / pop_local c одним числовым параметром — offset. Первая инструкция помещает на стек элемент стека, находящийся на глубине offset от вершины. Вторая наоборот снимает со стека вершину и присваивает ее элементу на глубине offset от вершины. Эти две инструкции используются для доступа к локалам, параметрам, записи результата, и всяких манипуляций нужных для операций вида: a.field[index] += value.


Порядок действий (при компиляции):


  • при компиляции новой локальной переменной — компилируем ее инициализатор и просто оставляем его результат на стеке, и делаем this_local->offset = ++locals_count
  • при уходе локальной переменной из зоны видимости вставялем команду drop и делаем locals_count--
  • при push -> temps_count++, при pop -> temps_count--, при других инструкциях влияющих на стек — тоже изменяем temps_count, например add снимает со стека два элемента и кладет один, значит temps_count--.
  • при чтении/изменении локала компилируем инструкцию push_local / pop_local с параметром temps_count + locals_count - this_local->offset
  • при обращении к параметру компилируем push_local / pop_local temps_count + locals_count + 1 /*там адрес возврата лежит*/ + parameter->offset.
  • при return <expression> — компилируем expression; pop_local temps_count + locals_count + 1 /*адрес возврата*/ + parameters_count; компилируем drop temps_count + locals_count; ret. А коллер после инструкции call может добавить drop function->params_count.

При этом возможны вариации и оптимизации, например, можно класть результат прямо в место для первого параметра, или ввести специальную инструкцию ret_val, в которой закодировано два числа — количество снимаемых темпов+локалов (смещение до адреса возврата) и количество снимаемых параметров, которое одновременно задает глубину элемента стека для результата. Такая инструкция позволяет очищать стек из вызывамой функции и экономит две инструкции drop и одну pop_local.


В общем, если сделать компилятор чуть более умным, можно сделать виртуальную машину существенно более постой и эффективной.


Кстати, имея locals_count и temps_count, компилятор может вычислить max_frame_size и положить его в начало функции, и тогда vm может делать проверку в момент вызова функции и защищаться от переполнения стека.

Это имеет смысл, если делаем jit (компилируем в маш. код), тогда можно освободить регистр rbp под другие нужды. Но если у нас интерпретатор, не факт что после такой «оптимизации» код будет проще (а значит, быстрее), чем явное хранение frame pointer в переменной.

В обоих случаях для доступа к локалу и параметру нужно будет делать доступ в память по указателю (sp или frame pointer) + смещение из инструкции. Так что эта конкретная инструкция будет одинакова. Вообще-то в случае frame pointer смещение должно быть знаковым, и его получение из байткода будет дороже.


Экономия в моем подходе возникает:


  • из-за отсутствии манипуляций с frame pointer при каждом входе-выходе из функции,
  • в отсуствии лишней локальной переменной в цикле интерпретатора, из-за чего что-то нужной может поместиться в регистр или будет меньше тарфика с памятью при нативных вызовах,
  • и в сокращенном наборе байткодов (одна инструкция выполняет доступ к локалу, параметру, возврат результата и манипуляции над вершиной стека), из-за чего главный цикл интерпретатора лучше влезет в кеш инструкций.
Без FP трудно будет сделать трассировку стека для отладки и реализовать отмотку стека для try/catch/finally. Стоит ли оно того?

Try-catch-finally распадается на три несвязанные проблемы:

  • диспетчеризация - узнать насколько отмотать стек и к какому байткоду перейти (это делается или картами байткода или добавлением в стек capture-фреймов или прямыми проверками в каждом call и источнике исключений и переходу на landing pad) - эта проблема ортогональна frame-pointer-ам

  • размотка - разрушение локалов и темпов, делается или через GC или теггированием стековых элементов или разнесением стека значении и стека ссылок или в landing pad-ах. Эта часть тоже не зависит от того, используются frame-pointer-ы или нет.

  • восстановление контекста - присваивание правильных значений sp, pc, frame-pointer, exception handler и еще некоторым tls переменным, восстановление регистров. Для этой задачи frame-pointer создает лишнюю проблему.

Для отладки - vm должен иметь интерфейс отладчика с on_function_entry on_function_return методами. Отладчик ведет свой список кадров активации. Положение всех локалов и параметров отсчитывается от соответствующего кадра. Информация отладчика хранится в отладчике (single responsibility).

Интересное продолжение, что собираетесь рассмотреть в следующей части?

Наверное, пора писать парсер для построения полноценного Abstract Syntax Tree и генерацию кода из C подобного языка. Уже хочу закрыть гештальт на тему "могу ли написать полноценную виртуальную машину и компилятор" на C++ )))

Увлекательная тема. Развлекался в свое время реализацией Smalltalk-VM c jit-компиляцией. Если бы еще увлекался бы этим, то придумывал бы не свою VM, а попробовал бы реализовать VM для WASM. Тема интересная, и она может в будущем оказаться полезной.

Вы правы, делать свою VM - это не практично, о чем говорил в первой части. Причина по которой пишу VM и компилятор - это желание самому детально понять как всё работает с нуля. По той же причине не использую парсеры (типа bison). Хочу во всём разобраться и понять. Дай бог закончу, можно будет заменить VM на нативную компиляцию (x86/64) или в WASM, или Java Bytecode.

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

Прикольно! Не думал о реализации WASM виртуальной машины. В будущем можно попробовать. Спасибо.

Можно пояснение: на шаге 32 в стек загоняется константа, на шагах 34-38 в стек загоняются аргументы функции, производится сложение, результат записывается на стек. Теперь там должен быть результат сложения и 10. А на шаге 39 производится загрузка на стек переменной c и потом вычитание. Но как 10 попало в с? Или на шаге 32 параметр не в стек загружен?

Если я правильно понял вопрос, то локальная переменная 'c' в функции SUM создана по адресу [32] командой ICONST 10 (аллокация на стеке места под переменную и её инициализация константой 10), по адресу [39] её значение добавляется на вершину стека командой ILOAD #0 для вычислений, без изменения переменной.

Константа которая была передана как второй аргумент изначально создана по адресу [9].

Аргументы функции идут по адресам FP+0 (A=I), FP+1 (B=10) - доступ к ним по команде ARG #index. Локальные переменные по адресам LP+0 (C=10), доступ к ним iload #index.

омандой ICONST 10 (аллокация на стеке места под переменную и её инициализация константой 10)

Ах, тогда ясно. Я не предполагал, что переменные тоже на стеке.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.