Восстановление структуры условных переходов на Си

Тема в разделе "WASM.A&O", создана пользователем _Cyber_, 19 мар 2010.

  1. _Cyber_

    _Cyber_ New Member

    Публикаций:
    0
    Регистрация:
    12 июл 2006
    Сообщения:
    8
    Адрес:
    Уфа
    Задача:
    из текста типа:
    Код (Text):
    1. L_3:
    2. if(R1 != 1) goto L_1;
    3. R1 = R2;
    4. //....
    5. goto L_2;
    6. L_1:
    7. R1 = 1;
    8. //...
    9. L_2:
    10. //...
    11. if(R2 < 5) goto L_3;
    12. //...
    получить:
    Код (Text):
    1. do {
    2.    if(R1 == 1) {
    3.       R1 = R2;
    4.       //...
    5.    }
    6.    else {
    7.       R1 = 1;
    8.       //...
    9.    }
    10. } while(R2 < 5);
    11. //...
    в общем, нужно избавится от всех goto в тексте, если возможно, и преобразовать в красивые Сишные структуры с использованием if-else, while, do-while, for, switch, return.
    Может есть готовое описание или исходники такого алгоритма?
     
  2. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    _Cyber_
    Этому посвящен целый раздел теории графов (CFG - control flow graphs).
    Для затравочки:
    http://unicorn.cmc.msu.ru/op/lect/250902.doc
     
  3. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    http://unicorn.cmc.msu.ru/opt/lect/250902.doc
     
  4. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    _Cyber_
    Инструмент, который делает это для общего случая, представляет из себя часть декомпилятора. Алгоритм существует, но пока не опубликован - не знаю, когда у меня руки дойдут.
     
  5. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    KeSqueer
    Описанный там "Структурный анализ" на практике не имеет смысла, так как нестандартные выходы из statement'a (то есть break и continue) не распознаются никакими шаблонами. Но все равно неплохо, не думал, что в российских ВУЗ'ах вообще как-то касаются этой темы. А откуда лекция?
     
  6. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    Создание и перестройка графа, точнее оптимизация ветвлений(удаление холостых и пр.).
     
  7. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Stiver
    Распознаются, в этой лекции есть такие шаблоны.
    Наткнулся на нее, когда искал что такое "сводимые графы", решил сохранить ссылку.
     
  8. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    KeSqueer
    В том файле, который скачивается по ссылке, их нет (да и в принципе таких шаблонов не существует, насколько мне известно :)). Или у файла есть еще продолжение?

    Лучше все-таки обращаться к первоисточникам: M.S.Hecht, J.D.Ullman, Characterizations of Reducible Flow Graphs
    В сети этой работы по-моему нет в свободном доступе, но могу выслать.
     
  9. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Stiver
    Офис у меня сейчас не установлен, проверить не могу. Но все же был уверен, что такие шаблоны есть.
    Буду очень признателен, никак не мог найти стоящей литературы по этой теме.
     
  10. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    KeSqueer
    :) Шаблонов таких конечно же нет. Но есть алгоритмы, позволяющие заменить переходы в сводимых графах на циклы с выходами. Это именно алгоритмы, шаблонному распознаванию такие структуры не поддаются.

    Один и самых старых опубликовала Brenda Baker: "An Algorithm for Structuring Flowgraphs", 1977 год. Рекомендую, очень милая работа. Самое начало развития, тогда еще даже термин "доминатор" не использовался. В сети нет: An Algorithm for Structuring Flowgraphs

    Более поздний и более известный - алгоритм Ramshaw: http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-4.pdf Он был положен например в основу декомпилятора Krakatoa.

    У них у всех два недостатка: 1) дают совершенно нечитаемую структуру на выходе 2) что более важно, не умеют обходится со сложными statement'ами (обработчиками исключений например). Поэтому тот же Krakatoa авторы бросили на полпути. Хотя если _Cyber_ собирается работать с чистым С, то они ему вполне могут подойти.

    Мой собственный алгоритм дает простое и достаточно быстрое иерархическое разложение графа на statement'ы для Явы (то есть вместе с try{}catch{}finally), реализован в декомпиляторе Fernflower.

    Обещанная статья: Characterizations of Reducible Flow Graphs Кроме того советую почитать работы Cristina Cifuentes, из них главным образом произошел декомпилятор Boomerang.