Как использовать LLVM для преобразования байт-кода виртуальной машины в стеке в форму SSA - PullRequest
Новая
       59

Как использовать LLVM для преобразования байт-кода виртуальной машины в стеке в форму SSA

1 голос
/ 02 мая 2019

Есть несколько вопросов о том, как преобразовать представление SSA в стековые машины, но меня интересует обратное.

Вопрос

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

Существуют ли инструменты / подходы в структуре LLVM для восстановления формы SSA из вывода байт-кода.По сути, это была бы форма разборки.

1 Ответ

1 голос
/ 02 мая 2019

В самом LLVM нет инструментов, но это просто s SMoP .Я сделал это.Частично это было сложно, но так же, как и все.Я отвечу вместо комментария, чтобы немного рассказать о самой сложной части.

Стеки обычно не имеют типов;значение, которое находится на вершине стека, имеет тип, а «верх стека» - нет.Тип LLVM Value всегда имеет тип, и эти две системы сталкиваются, когда код содержит циклы.Рассмотрим этот код: 

int a = b();
while(a<10)
    a++;

a имеет тип, и все значения будут иметь тип int (возможно, i32 в LLVM IR).Когда первая строка помещает возвращаемое значение из b() в стек, вершина стека получает тип int.Вы, вероятно, можете представить, как эти строки выглядят на вашем стековом компьютере.Он должен быть переведен в IR скорее так: 

entry:
  %a1 = call @b();
  br label %b1
b1:
  %stack.0.b1 = phi i32 [%entry, %a1], [%b1, %a2]
  %a2 = add i32 1, %stack.0.b1
  %done = icmp ult i32 %stack.0.b1, 10
  br i1 %done, label %b1, label %b2
b2:

(Извините за синтаксические ошибки, я не написал много IR вручную.)

Вы, вероятно, видите, что каждая инструкциякроме того, что phi может быть сгенерировано из одной инструкции на вашем языке стека.Возможно, инструкция на вашем языке стека приводит к более чем одной IR-инструкции или не приводит к IR-командам, например dup или push-constant-zero, которые просто изменяют стек.

phi отличается,он представляет стек в этой точке.

Стек при входе в блок b1 вычисляется из стека в конце каждого из entry и b1.Вы можете сгенерировать фи-узел для каждого значения в стеке в начале каждого базового блока;Проблема в том, что тип каждого фи-узла зависит от типов в стеке в конце предыдущих блоков.В этом случае стек в конце entry имеет одну запись a1, а в конце b1 - одну запись a2.Поэтому тип stack.0.b1 зависит от типа a2, который, в свою очередь, зависит от stack.0.b1.Вам нужно подумать об этом, особенно если ваш язык включает в себя неявное продвижение типов или приведение типов (i32 к i64, строки к объекту и т. Д.).

(я мог бы начать с системы типов, подобной ruby)и код вместо c-like; я думаю, что последняя проблема будет такой же, только ваше решение будет другим.)

...