Всем привет. Такая проблема. Есть таблица, созданная парсингом/дизассемблированием процедуры. Это двусвязанный список, в котором определены все блоки кода без ветвлений, ветвления, блоки завершающие процедуры(iret, retf, etc). Все блоки в этом списке связаны в таблице, описатель ветвления содержит ссылку на предыдущий блок кода, следующий блок кода и блок на который выполняется ветвление. При сборке кода, который описывается таблицей необходимо вычислять размер ветвлений(длинный либо короткий джамп). Не знаю как полноценно решить эту задачу, есть решение но оно кривое и не полноценное(подсчёт числа ветвлений между текущим). Простейший случай: Код (Text): | .-->| | | | v | 1 O---. | | | | | | | | | | v | '---O 2 | | | | | |<--' | 1, 2 - это условные ветвления. Они могут быть короткими и длинными. Чтобы знать размер 1-го ветвления нужно знать размер второго. Если ветвлений множество, то необходим алгоритм пересчёта их размера, просто жисло длинных джампов посчитать это не подходит. В принципе можно перечислить последовательно все ветвления, считая изначально их короткими, делать текущий джамп длинным, сканировать всю таблицу на валидность ветвлений. Это требует очень много времени, поэтому данный алгоритм не применим. Есчо были идея решать системы уравнений, но это слишком сложно и тоже не оптимально наверно. Компиляторы ведь это исполняют както, хотя может и криво. Подскажите пожалусто суть алгоритма.
Clerk Эта структура называется control flow graph (по-русски граф потока управления, как мне подсказали) В зависимости от нужной точности результата и скорости вычисления есть несколько вариантов. 1) Просто ставить везде длинные прыжки. Оптимальная скорость, максимальный размер. 2) Записать код, считая все прыжки длинными. Потом еще раз пройтись по ним и пересчитать каждый прыжок. Скорость немного ниже (+ еще один проход по всем прыжкам), размер близок к оптимальному. Это решение реализовано у меня. 3) Записать код, считая все прыжки длинными. Построить граф зависимости прыжков и в заданной им последовательности (не вдаюсь в детали, вряд ли тебе это решение подойдет) пересчитать прыжки. Скорость низкая, размер оптимальный.
Clerk Проблема заключается в определении оптимальной последовательности, в которой нужно вычислять прыжки. Поэтому строится граф: узлы - прыжки, направленные ребра - зависимость. Т.е. ребро от узла а к узлу b существует тогда, когда длина прыжка a зависит от длины прыжка b. В твоем примере граф может (но не обязан, см. замечание ниже) быть таким: {1,2}, {1->2, 2->1}. Потом граф обходится вширь начиная с узлов без входящих ребер и в порядке обхода считается длина прыжков. Сильно связные компоненты без входящих ребер приравниваются при этом к одиночным узлам ("схлопываются"). Теперь что касается оптимальности. Понятно, что длина одного прыжка может зависеть от другого только если расстояние, на которое прыгаем, находится на грани между коротким и длинным. Иначе длина одного опкода никак не повлияет на результат. В обычном коде, если специально не конструировать, такие ситуации возникают раз в год Смысла нет под них оптимировать.
