Методы реализации IR на основе регистров в форме статического одиночного назначения - PullRequest
Новая
       75

Методы реализации IR на основе регистров в форме статического одиночного назначения

1 голос
/ 28 декабря 2011

Я пишу компилятор для основанного на регистре байт-кода в IR с формой статического одиночного назначения (SSA) (в частности, из байт-кода Dalvik VM в IR LLVM, но я надеюсь, что вопрос можно взять для общеготопик) и я задаюсь вопросом, лучший или теоретически самый чистый способ сделать это.

Например, если у нас есть инструкции на основе регистра: 

add vA, vB, vC    (vA := vB + vC)
...
sub vA, vD, vE    (vA := vD - vE)

, то мы больше не можем использоватьстарое значение vA, поскольку оно было перезаписано и заменено на vD - vE.

В форме SSA у нас будет что-то более похожее на 

vA1 := vB + vC
...
vA2 := vD - vE

, поскольку каждая переменная назначается ровно один раз.

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

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

Я с нетерпением жду ваших идей.

1 Ответ

3 голосов
/ 28 декабря 2011

Ну, в общем, вам придется использовать что-то похожее на алгоритмы построения SSA.В вашем случае все может быть сложно из-за наличия ветвления (например, если у вас есть конструкция, похожая на if-else, и у вас есть один регистр, измененный только в предложении «if», но использованный впоследствии).

Говоря о LLVM IR- просто отправьте материал в форме, отличной от SSA (выделение регистров в стеке с помощью alloca и затем загрузите / сохраните значения), а затем просто передайте mem2reg, чтобы очистить все для вас.Вот как clang, llvm-gcc и многие другие интерфейсы испускают вещи:)

...