[ssa] [я столкнулся с проблемами]

[Spiridonov Alexander]

On Mon, Apr 16, 2018 at 12:50:01PM +0300, Vladislav Ivanishin wrote:
> Добрый день, Александр,
> 
> Spiridonov Alexander <spiridoncha at gmail.com> writes:
> 
> > Короче мне дико не нравится идея править qbe,
> > она предназначена чтоб создавать из IR исполняемые файлы,
> > а не работать на уровне source2source, мне кажется что мы просто
> > зароемся если захотим дополнить таким функционалом qbe.
> >
> > Если конкретнее(это только на первый взгляд):
> >   * Нужно выводить не только функцию, но и типы используемые в ней
> >     https://c9x.me/compile/doc/il.html#Aggregate-Types (я не
> >     нашёл ничего готового в qbe для этого)
> >   * Нужно выводить не только функцию, но и определяемые данные
> >     https://c9x.me/compile/doc/il.html#Data (я не
> >     нашёл ничего готового в qbe для этого)
> >   * Нужно переписать часть отвечающую за вывод call
> >     https://c9x.me/compile/doc/il.html#Call
> >   * Ну и по-мелочи ещё всякие retw и т.п.
> 
> Для задачи в ejudge вполне достаточно выводить только функцию. Задача
> ведь состоит в том, чтобы перевести её представление в SSA форму. Это
> преобразование никак не затрагивает типы, определённые в программе.
> 
> Конечно, программа без типов и данных становится непригодной для
> генирации по ней машинного кода, но это не должно понадобиться. В
> частности, ssa.cpp в репозитории сравнивает внутренние представления
> программ.
> 
> Или без типов возникает ошибка парсинга?
Да, выглядит это так:
  <original>:1: undefined type :mem
Пример для воспроизведения:
  export function :mem $test() {
  @ini
    %p =l alloc4 17
    ret %p # здесь было после printfn так - retc %p, :mem
  }
> 
> Изменения для вывода (вернее, для ввода -- разве нет? -- вывод ведь
> соответствует внутреннему представлению, реально хранимому qbe, нужно
> только научить его поглащать такую форму) call и retw выглядят простыми
> и полезными.
> 
> > В общем тут вся боль от того чтоб адаптировать инструмент для целей, для
> > которых он не предназначен.
> >
> > Предлагаю упростить задачу и
> > не работать в предположении что тот кто пишет задачу должен в качестве
> > вывода предоставить нам годный к парсингу IR.
> >
> > Предлагаю в качестве output задачи выдавать информацию в примерно таком
> > формате:
> >   @block_name_gl:
> >     phi:
> >       * имя переменной в блоке block_name_gl, которая до построения ssa
> >         была на месте, где после построения будет использование
> >         переменной определяемой phi(ёпрст, как это называется правильно??)
> >       * список вида: @block_name0, at block_name1
> >         блоков, откуда приходят определения переменной из первого пункта
> >         до построения ssa
> >
> > Например:
> >   input file:
> >     data $fmt = { b "%d", b 0 }
> >     export function w $main() {
> >     @start
> >       %p =l alloc4 4
> >       %t =w call $scanf(l $fmt, l %p)
> >       %x =w loadw %p
> >     @loop
> >       %x =w sub %x, 1
> >       jnz %x, @loop, @end
> >     @end
> >       ret %x
> >     }
> >
> >   output file:
> >     @loop:
> >       phi:
> >         %x
> >         @start, at loop
> >
> > В таком виде при решении задачи нужно будет по сути только определить
> > куда нужно вставлять фи-функции для преобразования в усечённую
> > ssa.
> >
> > Хотелось бы услышать кто что думает по этому поводу.
> 
> У меня нет больших возражений, но вывод полной программы для меня
> предпочтителен.
> 
> В принципе, такой содержит всю необходимую информацию -- в совокупностью
> со входными данными. В этом и состоит неудобство: для тестирования можно
> было бы выводить целую программу в виде графа (генерировать
> представление graphviz и запускать dot) и взглядом определять, корректра
> ли ssa-форма. В предложенном Вами подходе нужно будет выводить отдельно
> исходную программу и соотносить с полученным ответом.
Ну с новым форматом я полагал делать это так:
 * копипастим и припиливаем вывод под наш формат для построения ssa из qbe
 * считаем это эталонным решением
 * генерим с помощью него тесты
Ну а само тестирование просто проверяет что вывод пришедшего решения
совпадает с тем что мы нагенерили(ну, с поправкой на возможное
несовпадение порядка)

> 
> > P.S.
> >   Все задачи которые у нас были на ejudge, были именно такие; может кроме
> >   последнего, я подзабил на него, а условие уже посмотреть не дают :(
> >   Не вывести годный IR, а вывести инфу по базовым блокам.
> >   Возможно и нам стоит так поступить.
> 
> Я на прошлой неделе открыл контест на дорешивание. Упс -- теперь я вижу,
> что забыл при этом убрать дедлайны. Починил, теперь можно посмотреть и
> посдавать.
> 
> -- 
> Влад

-- 
С уважением,
Спиридонов Александр.