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

UbIvItS,

Размер цикла определяется размером кольцевого буфера, в который накапливается трасса. Для примера выше такой буфер будет содержать 4 указателя. Никакие тяжёлые операции по времени не используются.

 

Indy_, а что если твой код маленько поменять

Код (ASM):

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

тело функции не нарушает цикл, но весьма меняет картину с регистрами/флагами/стеком.

 

UbIvItS,

Сохранится трасса для функи, затем если она совпадёт на следующей итерации цикл обнаружен. Если же внутри функи сработает какое то условие, трасса изменится и цикл обнаружен не будет. Если цикл обнаружен, то в буфер выделится и код функи.

 

Indy_, и какой размер буфера?

 

UbIvItS,

Зависит от размера цикла. Если например 64 указателя помещается, то цикл может состоять макс из 64 инструкций. А почему вам именно память интересует ?

 

полиморфизм может делаться без доп. записи/перезаписи, а засчёт сдвигов. jmp label -одно тело вызывается, а jmp [label+n] - другое

 

то бишь опкоды меняются.

 

n=1,2

 

UbIvItS,

Регистровые ветвления: [R + n], косвенные [M] etc так не могут быть обработаны, только релатив, иначе после выделения цикла управление может быть передано вникуда.

 

отправка в хзк тожь вполне приемлема, ежель речь идёт о дидосах.

 

UbIvItS,

Вот семпл для примера. Детектор ровный, но выделение цикла в буфер нужно есчо допилить. Там буфер в 64 поинтера.
На кряклабе было вчера обсуждение, но я там тему закрыл что бы не гадили jit etc.

 

Indy_, Молодецправда, мне сейчас не до тестов с вынью.

 

Допилил немного.

 

Indy_
Оперировать здесь надо не инструкциями, а базовыми блоками. Как только доходите до ветвления -- финализируете блок, добавляете в качестве вершины CFG и сбрасываете очередь инструкций.

> Вначале нужно дать какое то чёткое определение - что такое цикл.

Весна 2017-го. Пора бы дать определение циклу. Полностью поддерживаю!
Например, в вашем случае -- это компонента сильной связности на графе потока управления.

> Можно в графе найти замыкания ветвей, но мы его построить
> не можем - это слишком долго, нужно всё сделать в динамике.

Список смежности с добавлением за O(1) и Тарьян для компонентов за O(V+E) -- это долго?
Если проапгрейдитесь до Intel 80286 -- будет с запасом, еще и хватит на замутить падающий снег по INT 8.

 

DelAlt,

Как вы себе это представляете ?

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

> финализируете блок, добавляете в качестве вершины CFG и сбрасываете очередь инструкций.

Вы уже все форумы загадили этим мат. дерьмом, не нужно тут.

 

DelAlt, Можешь накатать код и показать изложенное в действие, но у меня имеются подозрения, что Инди тута чертовски прав: щимить цикл в общем виде -- слишком напряжно для любой машины.

 

UbIvItS,

Могу запилить взятие всей процедуры конструктором, десяток строк занимает. Вот только смысл совсем не в этом.

 

а ежель цикл спрятан в условных ветвлениях и надо выщимить параметры, при коих он активируется?

 

UbIvItS,

Задача по оптимизации, в том и суть - выделить цикл и выполнить его напрямую. Любой анализ в данном случае как минимум потребует запуск конструктора.

Раз все твердят про графы, то давайте на реальном примере это рассмотрим. Во первых матчасть матчастью, она прямого отношения к профайлу не имеет. Собственно чем собирать тот самый граф ?
Пруфца может приведёте на моторы ?

Из всех существующих моторов только мой самый быстрый(kite). Но там тоже затыки по профайлу:
1. Дизасм длин. Была моя тема на клабе, тестились все существующие моторы на профайл. Лучшим оказался dizahex. Xed на порядок тормознее, хотя заявляется как табличный. Жаль что все быстрые моторы не поддерживают NPX инструкции(fpu etc).
2. Поиск описателей в графе. Используется обычный проход по связанным спискам. Можно использовать авл деревья.
3. Аллокатор. Добавление элемента в граф приводит к выделению памяти, реконструкции графа - оптимизации и связыванию структур. Глобальный аллокатор нэйтив, нельзя использовать стек. Но можно заранее выделить буфер достаточного размера, но всё равно это затыка по скорости.

Да и вообще я поднял тему для оптимизации визора, а он выполняется в реалтайме. Невозможен никакой анализ, иначе приложение повиснет.

 

int x=100, y=123, P=93;

while (x**y mod P > x){
-------
}
========================
цикл какбе есть, но может не срабатывать.

я про них даже не упоминал.