Минимизировать количество переходов при компиляции в сборку

Question

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

a(); 
if (bla) then c(); 
else b(); d(); 
e(); 

Теперь нам нужно «упаковать» эту последовательность в нашей линейной памяти и, таким образом, наш код должен расшириться (условно и нет). Например, одна из возможностей:

 CALL A 
     TEST bla 
     BRANCH else 
     CALL C 
     JMP esc 
else: CALL B 
     CALL D 
esc: CALL E 

Есть, конечно, несколько возможностей о том, как организовать эти блоки в линейной памяти, и все они различаются по количеству ветвей/прыжков. Наша цель - минимизировать их.
Вопросы:
a) Как называется эта проблема? Есть ли общее название? (Является ли это примером построения BDD?)
b) В чем сложность такой проблемы (найти расположение блоков таким образом, чтобы количество прыжков/ветвей было минимальным)?

Answer 1

У вас есть куча базовых блоков, которые передают управление от одного к другому в конце каждого базового блока.

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

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

Что вы хотите сделать, это выбрать набор последовательностей дуг (представьте, что вы окрашиваете эти синие), так что оставшиеся дуги (представьте их как красные) минимальны.

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

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

Максимальная секвенизация, вероятно, не то, что вы действительно хотите. Представьте себе, что мы привязываем вероятность каждой дуги, основываясь на данных профилирования, знаниях алгоритмов, предположениях, что исключения редки, поэтому низкая вероятность, или даже программист предоставил намеки. Теперь вам нужны длинные цепочки дуг с наибольшими вероятностями; такой путь называется «след» в литературе. Это гарантирует, что горячие пути в коде последовательны в памяти, максимизируя значение кэшей команд. Выстроенные таким образом ветви ветви являются низковероятными, например, холодными путями.

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

С цветными последовательностями дуги легко получить код в «правильном» порядке.

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