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

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

 

Очевидно, цикл - это повторное выполнение инструкции. Следовательно, необходимо вести учет выполненных инструкций. Например завести битмап размером VirtualSize/8 и устанавливать в нем в 1 биты, соответствующие смещению и размеру инструкции в секции.

 

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

 

Зачем? Если мы видим в битмапе, что для очередной инструкции биты установлены в 1, значит она уже выполнялась и вот он - цикл.

 

rmn,

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

njeen,

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

 

С точки зрения control-flow это ни что иное, как цикл.

 

rmn,

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

 

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

 

А, ну да, третье не хранить если - тогда информация теряется впоследствии, но для задачи это и не важно.

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

 

главной сигнатурой цикла является возврат к младшим адресам. то бишь детектишь наибольший текущий адрес и смотришь прыгает ли назад.

 

UbIvItS,
Это не обязательно цикл. Может хитрое ветвление такое.

 

если прыгает хотя бы 2-3 раза, ужо как-то циклом начинает попахивать

 

UbIvItS,
Зачем дальше гадать? Я же выше дал замечательное определение цикла
Без учета выполненных инструкций определить цикл невозможно.

 

можно и без битмапа -- достаточно, что произошёл прыжок назад.

 

UbIvItS,
Прыжок назад может быть на инструкцию, которая еще не выполнялась (например, если перед этим был прыжок вперед через какой-то блок, на который потом вернулись). Это не цикл.

 

rmn,

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

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

UbIvItS,

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

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

njeen,

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

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

 

Нашёл решение для простых циклов https://exelab.ru/f/index.php?action=vthread&forum=6&topic=24744&page=-1#16

 

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

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

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

 

UbIvItS,

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

Code (Text):

1. L2:
2.     push @L1
3.     ret
4. L1:
5.     dec eax
6.     jnz L2
7.     jmp ebx

Обычно циклы находят графами, но тут совсем иное - обнаружение по потоку инструкций(повторное исполнение серии инструкций). Далее такой цикл выделяется в буфер, при этом фиксятся все ветвления за пределы цикла, это условные ветвления etc. Регистровые ветвления пропускаются, так как произойдёт утеря управления.

 

Indy_, и сколько наносек и озу нужно для распознавание хотя бы вот такого цикла?