Оптимизация циклов.

Тема в разделе "WASM.A&O", создана пользователем Indy_, 20 май 2017.

Статус темы:
Закрыта.
  1. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    Здрасте.
    Задача следующая, решения пока я не вижу.
    Приложение взято под визор/трассировку - не суть важно, имеем каждую инструкцию его.
    Исполнение цикла имеет большой тайминг, посему цикл необходимо обнаружить и скипнуть.
    Как обнаружить цикл ?
    Вначале нужно дать какое то чёткое определение - что такое цикл.
    Серия вызовов функции(апи к примеру) очевидно это не цикл.
    Можно в графе найти замыкания ветвей, но мы его построить не можем - это слишком долго, нужно всё сделать в динамике.
     
  2. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.329
    Очевидно, цикл - это повторное выполнение инструкции. Следовательно, необходимо вести учет выполненных инструкций. Например завести битмап размером VirtualSize/8 и устанавливать в нем в 1 биты, соответствующие смещению и размеру инструкции в секции.
     
  3. njeen

    njeen Active Member

    Публикаций:
    0
    Регистрация:
    26 мар 2017
    Сообщения:
    138
    Адрес:
    Ташлинск
    цикл - связь между нодами более чем по одному пути. Достоверно определить наличие циклов можно только построением графа и раскраской вершин при посещении. Здесь же, т.к исполнение инструкций идет в сторону старших адресов, можно только предположить, что переходы назад (jxx, loop) будут признаком цикла. Но из этого возможны исключения.
    С битмапом (0,1) не обнаружить цикла. Нужно хотя бы 3 состояния
     
  4. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.329
    Зачем? Если мы видим в битмапе, что для очередной инструкции биты установлены в 1, значит она уже выполнялась и вот он - цикл.
     
  5. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    rmn,

    Второй вызов процедуры даст повторное исполнение инструкций. Но это не является циклом. Они вложенные - внутри одного цикла может быть другой.

    njeen,

    Граф создать невозможно за приемлемое время, в общем случае нужный для этого тайминг будет на порядки больше чем время прямого исполнения цикла. И это помимо ошибок - не обнаружения циклов.
     
  6. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.329
    С точки зрения control-flow это ни что иное, как цикл.
     
  7. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    rmn,

    Никакой это не цикл, повторное обращение к адресам. Он зависит от контекста.
     
  8. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.329
    ... называется циклом. Можешь вот прям нарисовать блок-схему того, что ты называешь циклом и рекурсивной функции и сравнить.
     
  9. njeen

    njeen Active Member

    Публикаций:
    0
    Регистрация:
    26 мар 2017
    Сообщения:
    138
    Адрес:
    Ташлинск
    А, ну да, третье не хранить если - тогда информация теряется впоследствии, но для задачи это и не важно.
    Можно и не создавать, а обойтись раскраской, как в варианте rmn. Тоже долго?
     
  10. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.077
    главной сигнатурой цикла является возврат к младшим адресам. то бишь детектишь наибольший текущий адрес и смотришь прыгает ли назад.
     
  11. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.329
    UbIvItS,
    Это не обязательно цикл. Может хитрое ветвление такое.
     
  12. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.077
    если прыгает хотя бы 2-3 раза, ужо как-то циклом начинает попахивать :)
     
  13. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.329
    UbIvItS,
    Зачем дальше гадать? Я же выше дал замечательное определение цикла :)
    Без учета выполненных инструкций определить цикл невозможно.
     
  14. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.077
    можно и без битмапа -- достаточно, что произошёл прыжок назад.
     
  15. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.329
    UbIvItS,
    Прыжок назад может быть на инструкцию, которая еще не выполнялась (например, если перед этим был прыжок вперед через какой-то блок, на который потом вернулись). Это не цикл.
     
  16. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    rmn,

    > ... называется циклом. Можешь вот прям нарисовать блок-схему

    Если например процедура вызывается два раза, циклом это будет только если вызывающий код повторно исполняется. Если к примеру до повторного вызова ранее выполненной процедуры выполнялся новый код, то это уже не цикл.
    А есчо процедура или вообще код выполняющийся в цикле может содержать вложенные циклы, выполнение которых может бать разным на разных итерациях, но это никак не влияет на основной цикл.

    UbIvItS,

    > главной сигнатурой цикла является возврат к младшим адресам.

    Это в самом простом случае и не обязательно это цикл. К примеру компиль умеет запутывать код разных процедур, одна процедура может располагаться в разных частях модуля. В таком случае ветвление назад никак не связано с циклами.

    njeen,

    > Можно и не создавать, а обойтись раскраской, как в варианте rmn.

    Допустим помечаем мы в битмапе выполненные инструкции. Обнаружим повторное исполнение инструкции - это не будет циклом, это будет повторным вызовом процедуры. Для обнаружения цикла наверно придётся отслеживать исполнение нового кода, который в битмапе не помечен. Если новый код обнаружен, то придётся сбросить всю битмапу. Как быть с вложенными циклами.. какой то не чёткий способ.
     
  17. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
  18. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.077
    если к некоему адресу возвращается 2-3 раза, то вполне себе цикл. Но главная проблема в несколько ином русле располагается: в цикле может находиться ветвление с jmp/ret к ХЗК (хз-куда) и вот отдетектить такой случай действительно сложно -- надо перебрать все ветки.

    ЗЫ. в общем и целом приемлемого решения тут нет.

    ЗЗЫ.. правда, наилучший вариант, пожалуй, определиться с размерами тела цикла, тогда слишком дальние броски отсеиваются без доп. сверок. да-да.. способ тожь не дюже надёжен, но сия Задача при решение в общем виде будет хавать проц. и/иль озу по экспоненте.
     
  19. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    UbIvItS,

    В данном случае цикл это совпадение трассы. Оно может каким угодно быть, например таким:

    Код (Text):
    1. L2:
    2.     push @L1
    3.     ret
    4. L1:
    5.     dec eax
    6.     jnz L2
    7.     jmp ebx
    Обычно циклы находят графами, но тут совсем иное - обнаружение по потоку инструкций(повторное исполнение серии инструкций). Далее такой цикл выделяется в буфер, при этом фиксятся все ветвления за пределы цикла, это условные ветвления etc. Регистровые ветвления пропускаются, так как произойдёт утеря управления.
     
  20. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.077
    Indy_, и сколько наносек и озу нужно для распознавание хотя бы вот такого цикла?
     
Статус темы:
Закрыта.