📚 Статья Rocha, Rodrigo CO, et al. "Hybf: A hybrid branch fusion strategy for code size reduction." Proceedings of the 32nd ACM SIGPLAN International Conference on Compiler Construction. 2023. Авторы реализовали для LLVM IR два новых алгоритма слияния ветвей. 70% бенчмарков показали уменьшение размера кода до 4% поверх уже внедренных оптимизаций с пренебрежимо малым эффектом на производительность кода. Распространенные алгоритмы слияния ветвей ограничены в применении: - Первоначальная версия алгоритма слияния ветвей [1] работает только для похожих ветвей, содержащих по одному базовому блоку, т.е. для ромбов в графе потока управления. - Другой алгоритм — Control Flow Melding (Divergence Aware Region Melder, DARM), поддерживает только структурно простые ветви: вложенные if-then, if-then-else или natural loops. Авторы предлагают два новых алгоритма для слияния ветвей и алгоритм HyBF, выбирающий лучшую из двух трансформаций для конкретного подграфа потока управления. Они работают с т.н. регионами графа потока управления – это подграфы с одной точкой входа. Первый алгоритм, предложенный авторами — Control Flow Melding (CFM-CS), это улучшенная версия алгоритма DARM. CFM-CS работает только с SESE-регионами (single-entry-single-exit, регионы с одной точкой выхода). Первоначально, DARM предназначен для борьбы с control flow divergence. Это ситуация в моделях вычислений Single Instruction Multiple Threads, когда несколько потоков выполняют один и тот же код, но выбирают разные пути из-за условного ветвления [2]. Если ветви выполняются неодинаковое время, потоки, уже выполнившие более короткую ветвь, ожидают еще не завершившиеся потоки, занятые длинными ветвями, как при барьерной синхронизации. DARM обычно ведёт к уменьшению размера кода, но не нацелен на это, и не способен работать со сложно структурированными подграфами потока управления. Улучшенная версия DARM — CFM-CS — работает следующим образом: 1. Определить SESE-регион, где возможно слияние (блок с двумя исходящими ветвями, сходящимися в одном блоке). 2. Собрать подрегионы каждой ветви в дерево (авторы используют структуру данных region tree в LLVM). 3. Изо всех возможных пар подрегионов, принадлежащих двум ветвям, нужно выбрать пару изоморфных подрегионов, причем с наиболее "похожими" инструкциями внутри. Для этого регионы должны быть выровнены, как в проблеме "выравнивания последовательностей"[3]. Авторы используют специальную эвристику в качестве меры сходства, позволяющей выбрать пары подрегионов наиболее выгодные для слияния. 4. Чтобы объединить изоморфные подрегионы из двух ветвей необходимо выровнять уже инструкции внутри соответствующих блоков. Это разделит инструкции блоков на: - не имеющие соответствия в блоке изоморфного подрегиона. Эти инструкции перемещаются в новые, условно выполняемые базовые блоки. - совпадающие с инструкциями в блоке изоморфного подрегиона. Это одинаковые инструкции с разными операндами: они будут помещены в объединенный базовый блок, но их операнды будут вычисляться с использованием псевдоинструкций SELECT. Условием таких SELECT'ов будет, разумеется, условие из входного блока большого SESE-региона. Исходный код алгоритма CFM-CS для LLVM IR. Алгоритм CFM-CS эффективен, когда ветви имеют похожую структуру, но если одна из ветвей содержит всего один блок, такой блок можно обернуть в код, имитирующий структуру другой ветви, а затем запустить на полученном регионе CFM-CS. Эта техника называется Region Replication, и авторы также предлагают улучшение существующего алгоритма Region Replication используемого в DARM. Второй предложенный алгоритм SEME-fusion обобщает алгоритм слияния функций HyFM, предложенный авторами в предыдущей статье [4], на любой SEME-регион (Single-Entry-Multiple-Exit). Он сравнивает блоки двух областей SEME на основе расстояний между их fingerprint'ами, вычисляя linear pairwise alignment [4]. После выравнивания и слияния блоков происходит технический процесс корректировки ϕ-функций в выходных блоках. Исходный код алгоритма SEME-fusion для LLVM IR.