spamsink

Categories:

Вопрос теоретикам компьютерных наук

Про графы потока управления (в просторечии 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.

LJ Video