?

Log in

No account? Create an account

Вопрос теоретикам компьютерных наук - Общество дровосеков Бердичева по изучению Мишны

Jul. 17th, 2017

02:09 pm - Вопрос теоретикам компьютерных наук

Previous Entry Share Next Entry

Про графы потока управления (в просторечии CFG) - под катом,
чтобы не смущать генеральную популяцию.


Я ищу приладу, которая бы получала на вход упомянутый ГПУ в самом простом виде, скажем, последовательности строк одного из четырех видов:

    labelNNN:
    basic block NNN
    if (condNNN) goto labelNNN
    goto labelNNN

и порождала бы разумную структуризацию этого ГПУ с помощью условных операторов, циклов и операторов break/continue, минимизируя последние, и минимизируя оставшиеся "голые" операторы goto, если ГПУ оказался несводимым (irreducible, см. рис.).

Например, введя
        basic block 1
    label1:
        if (cond1) goto label2
        basic block 2
        if (cond2) goto label3
        basic block 3
    label3:
        basic block 4
        goto label1
    label2:


можно на выходе ожидать, скажем,
    for (basic block 1; !cond1; basic block 4) {
        basic block 2;
        if (cond2) continue;
        basic block 3;
    }
или
    basic block 1
    while (!cond1) {
        basic block 2;
        if (!cond2) basic block 3;
        basic block 4;
    }


Судя по ссылкам и поиску, имеющиеся прилады для работы с ГПУ заточены на преобразование из структурных операторов с целью компиляции и оптимизации, т.е. на обратную задачу.

Задача интересная, но не верится, что никто никогда не писал подобных прилад, например, в качестве дипломной работы или (если прилада оказалась очень умная) диссертации — не хочется изобретать велосипед.



This entry was originally posted at http://spamsink.dreamwidth.org/1056278.html. Please comment there using OpenID.

Comments:

[User Picture]
From:dtim
Date:July 17th, 2017 10:47 pm (UTC)
(Link)
Этим декомпиляторы занимаются обычно. Я специально не изучал алгоритмы, но есть вот такое, например:
* теория 1: https://www.internetsociety.org/doc/no-more-gotos-decompilation-using-pattern-independent-control-flow-structuring-and-semantics
* теория 2: https://net.cs.uni-bonn.de/fileadmin/ag/martini/Staff/yakdan/dream_oakland2016.pdf?platform=hootsuite (усовершенствованная версия, насколько я понимаю)
* практика: http://zneak.github.io/fcd/ (там другим человеком реализован алгоритм из первой статьи)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:July 18th, 2017 01:32 am (UTC)
(Link)
Конечно, так я именно что декомпилирую помаленьку.

Огромное спасибо! Алгоритм DREAM, похоже, придется находить в fcd (навскидку по именам файлов не вышло) и выкусывать оттуда вручную, но где наша не пропадала.
(Reply) (Parent) (Thread)
From:pigdeon
Date:July 18th, 2017 12:08 am (UTC)
(Link)
Описанная задача, "в мирное время" встречается редко, и обычно решается как часть процесса декомпиляции. Вот, наиболее продвинутый декомпилятор из известных мне: https://www.hex-rays.com/products/ida/index.shtml
Сам я им не пользовался, только изучал возможности.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:July 18th, 2017 01:34 am (UTC)
(Link)
Ну да (см. мой ответ на коммент выше), но IDA - это коммерческий продукт, который работает, начиная с бинарников, и никто ради меня его прикручивать к исторической архитектуре не будет.
(Reply) (Parent) (Thread)