DOI: 10.15514/ISPRAS-2026-38(1)-5

И.А. Зинин, ORCID: 0009-0000-5287-1543 <zinin.ia@phystech.edu>
В.В. Черноног, ORCID: 0009-0007-8407-1082 <chernonog.vv@phystech.edu>

Московский физико-технический институт,
141701, Московская область, г. Долгопрудный, Институтский переулок, д. 9.

Аннотация. В работе рассмотрены принципы устройства оптимизации методом Распространения констант, играющей большую роль во многих современных оптимизирующих компиляторах. Исследована техника версионирования кода и предложен алгоритм, улучшающий метод Распространения констант. Реализация алгоритма была осуществлена в компиляторе GCC. Результатами, подтверждающими важность и актуальность данной работы, являются замеры работы вычислительно сложных приложений из пакета задач CPUBench.

Ключевые слова: оптимизации в компиляторе; распространение констант; межпроцедурное распространение констант; версионирование.

Для цитирования: Зинин И.А., Черноног В.В. Версионирование кода как развитие оптимизации методом Распространения констант. Труды ИСП РАН, том 38, вып. 1, 2026 г., стр. 61–70. DOI: 10.15514/ISPRAS-2026-38(1)-5.

1. Введение

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

2. Распространение констант

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

2.1 Виды распространения констант

Во многих современных оптимизирующих компиляторах, в том числе и в GCC [1], оптимизация распространением констант бывает двух видов: внутрипроцедурная и межпроцедурная. Внутрипроцедурное распространение констант [2], которое часто называют просто распространением констант, ограничивается графами потока данных и потока управления каждой процедуры, рассматриваемой как отдельной. Межпроцедурное распространение констант [3] рассматривает поток данных в рамках взаимодействия всех процедур, используемых в программе, опираясь на граф вызовов.

2.2 Внутрипроцедурное распространение констант

Рассмотрим краткое описание работы внутрипроцедурного распространения констант. Данная оптимизация активно работает с понятиями полурешеток и передаточных функций. В качестве оператора сбора вводится оператор слияния ⊔ (join), в качестве верхнего элемента ⊤ берется неопределенное значение (undef), а в качестве нижнего ⊥ берется переопределённое значение (overdef). Передаточной функцией базового блока берется функция, определяющая изолированное действие этого базового блока на вектор переменных.

Рис. 1. Пример исполнения алгоритма Распространения Констант.

Для графа потока управления, изображенного на рис. 1, передаточные функции базовых блоков выглядят соответствующим образом:

• F_BB0 (A, B, C, D) = (0, 1, 1, D)
• F_BB1 (A, B, C, D) = (A+1, B*A, C*C, D)
• F_BB2 (A, B, C, D) = (A, B, C, B+C)

Работа оптимизации начинается с выставления значения верхнего элемента (undef) всем переменным. Затем производится итеративное исполнение передаточных функций до момента схождения к неподвижной точке, то есть состояния, когда все F_BBi (X) = X для каждой из переменных. Переменные принявшие значение нижнего элемента (overdef) не могут быть заменены на константу, а те, что приняли какое-то одно константное значение, можно заменить на соответствующие константы. Например, на рис. 1 на последнем шаге алгоритм выявил, что для переменной C может быть распространено константное значение 1.

2.3 Межпроцедурное распространение констант

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

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

3. Проблемы существующих решений

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

1. Распространение констант как внутрипроцедурное, так и межпроцедурное, заменяет переменную на константу, если способно гарантировать единственность данного значения. Но зачастую переменная может принимать некоторый дискретный набор возможных константных значений.
2. Существующий анализ области значений переменной (Value Range Analysis) [4], реализованный в том числе и в GCC, способен отслеживать интервал значений переменной. Однако анализ не способен отслеживать дискретный набор значений, а только лишь непрерывные интервалы.
3. Межпроцедурное распространение констант не работает с графом потока управления в явном виде, потому может упускать некоторые особые случаи, подходящие для трансформации.

3.1 Проблема межпроцедурного распространения констант

Для того, чтобы разобрать проблему межпроцедурного распространения констант, необходимо обратиться к примеру, изображенному на рис. 2. В данном примере кода присутствует функция func_0, которая содержит внутри себя вызов другой функции func_1 при выполнении сложного (комплексного) условия. Условие состоит из двух простых условий проверки равенства значения переменной n какой-либо константе. Эта переменная является полем структуры tree, которая выступает аргументом вызова функции func_1.

Далее код программы из функции func_0 может привести исполнение к вычислительной функции compute_func, которая является “горячей”, то есть исполняется большое число раз. Внутри себя она содержит два вложенных цикла, числом итераций которых и является переменная n, переданная в качестве аргумента. Если во время компиляции можно было бы определить, что значение n является константным, тогда многие методы оптимизации, например, раскрутка циклов (Loop Unrolling) [5] или векторизация циклов (Loop Vectorization) [6], смогли бы получить больше возможностей для анализа и произвести необходимые трансформации.

Рис. 2. Пример кода, не обрабатываемый межпроцедурным Распространением Констант.

Так как значение n для вызова func_1 в func_0 не определено однозначно, существующий алгоритм межпроцедурного распространения констант не может распространить ни одно из возможных значений. Потому тело compute_func не может быть оптимизировано и его выполнение будет занимать большую часть времени и вычислительных ресурсов.

Согласно семантике языка C, если по ходу проверки простых условий, связанных логическим “ИЛИ” в комплексном условии, выполняется какое-то из них, то управление сразу передается к базовому блоку “then”. А это означает, если в исходном коде func_0 произвести версионирование, как показано на рис. 3, то поведение программы никак не изменится. Причем условия не обязательно должны быть взаимоисключающими, и сложное условие, соединяющее простые условия логическим “ИЛИ”, можно представить, как последовательность “if-elseif” простых условий.

Рис. 3. Пример возможного версионирования.

При данном варианте функции func_0 для каждого вызова func_1 будет однозначно определённое константное значение переменной n (4 или 20). Межпроцедурное распространение констант для каждого из значений способно создать клоны func_1, compute_func и других функций, лежащих в графе вызовов на пути от func_1 до compute_func. Таким образом, каждый из клонов compute_func будет содержать свое константное значение, которое обеспечит другим методам оптимизации больше свободы для осуществления трансформаций кода.

3.2 Проблема внутрипроцедурного распространения констант

Нередко такие вычислительные функции, как compute_func, являются “горячими”, но внутри себя содержат небольшой объем кода. В таких случаях большая часть вычислительных ресурсов во время исполнения программы тратится на осуществление вызова функции и возврата из неё. Эту проблему призвана решить оптимизация методом встраивания процедур (Inlining), которая в коде программы подставляет вместо вызовов функций непосредственно их код. Такая оптимизация имеет собственное ограничение: если объем кода увеличивается слишком сильно, то встраивание не осуществляется. Таким образом, если в пользовательской программе есть часто вызываемая функция и она небольшого размера, то её можно встроить в граф потока управления вызывающей функции.

В GCC есть два оптимизационных прохода встраивания процедур. Раннее встраивание процедур (Early Inlining) производится одним из первых среди оптимизационных проходов, работающих с графом потока управления в рамках одной единицы трансляции. Макроскопический вариант данной оптимизации, который включает в себя сложный межпроцедурный анализ, осуществляет свою работу в отложенном режиме LTO (Link Time Optimization) [7]. LTO объединяет несколько единиц трансляции в одну и с ней, как с единым целым, позволяет остальным оптимизациям производить трансформации.

Если в коде func_0 осуществится встраивание, как показано на рис. 4, тогда произвести версионирование будет невыгодно из-за значительного увеличения кода. Кроме того, в общем случае, версионирование лишь из-за возникновения подобного сложного условия чаще всего не будет улучшать производительность программы. Преимущество подхода, показанного на рис. 3, заключается в том, что оптимизации размера кода производятся вместе с более релевантными стадиями, такими как встраивание процедур или межпроцедурное распространение констант. В свою очередь, эти оптимизации, основываясь на своих эвристиках, будут осуществлять необходимое встраивание или клонирование. Соответственно, если осуществить версионирование, как на рис. 3, потом предоставить работу встраиванию процедур, а затем выполнить внутрипроцедурное распространение констант, то подобное версионирование способно качественно помочь в распространении соответствующих констант.

Рис. 4. Пример процедурного встраивания.

4. Реализация

Так как алгоритм, который будет представлен дальше, не зависит от конкретной платформы, он будет работать с высокоуровневым промежуточным представлением GIMPLE [8]. GIMPLE – это независимое от языка и целевой архитектуры трёхадресное промежуточное представление в компиляторе GCC, которое упрощает оптимизацию, представляя вычисления в виде последовательности базовых операций и превращая управляющие конструкции в условные переходы.

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

Ознакомиться с исходным кодом оптимизационного прохода можно в репозиторие openEuler/gcc [9].

4.1 Подходящие шаблоны кода

Ниже определены подходящие шаблоны кода, к которым алгоритм будет применять версионирование:

1. Алгоритм находит сложные условия, объединяющие простые условия логическим “ИЛИ”.
2. Одно из простых условий является проверкой на равенство значения переменной константе.
3. Эта переменная является аргументом вызова функции в базовом блоке “then”, причем явным, или полем какой-либо структуры, являющейся аргументом функции. В виду возможности неограниченной вложенности структур (nesting), алгоритм учитывает до двух таких уровней (причина выбора данного числа будет упомянута дальше).

4.2 Первый шаг оптимизации

В компиляторе GCC сложные условия могут быть представлены либо явной проверкой в одном базовом блоке, либо двумя базовыми блоками (рис. 5), образуя “if-elseif” конструкцию (рис. 6).

Рис. 5. Пример сложного условия в одном базовом блоке.

Представление проверки сложного условия в явном виде в одном базовом блоке является полезным для осуществления мелкозернистых арифметических операций над complex_cond. Так как после предыдущих компиляторных проходов могут встретиться оба варианта, необходимо реализовать первый шаг оптимизации, заключающийся в нахождении всех сложных условий, представленных одним базовым блоком и удовлетворяющих условиям подходящего шаблона, и трансформации их к виду двух базовых блоков, образующих цепочку “if-elseif”.

Рис. 6. Пример сложного условия в виде конструкции из двух базовых блоков.

Для этого алгоритм сначала находит все базовые блоки, содержащие сложное условие, удовлетворяющее Форме 1, среди них отбирает те, у которых одно из простых условий удовлетворяет Форме 2 (рис. 7). Затем он проверяет, что переменная, фигурирующая в проверке на равенство константе, либо является непосредственно аргументом в процедурном вызове в базовом блоке “then”, либо полем структуры, являющейся аргументом. Отметим, что алгоритм учитывает возможность вложенности переменной в структуру как по указателю (s → n), так и явно (s.n). С помощью компиляции тестовых приложений экспериментально было установлено, что анализ до двух уровней вложенности структур является оптимальным (outer_s → inner_s → n). Одного уровня вложенности было недостаточно, а анализ до трёх уровней не увеличивал множество обрабатываемых случаев.

Рис. 7. Шаблонные формы, необходимые для первого шага оптимизации.

Далее алгоритм выполняет трансформацию: в коде базового блока “if” остается лишь первое из простых условий, затем создаётся базовый блок “elseif”, в который помещается код второго простого условия. Стоит отметить, что алгоритмический подход первого шага способен обрабатывать цепочки “if-elseif” любой длины, так как в GCC не встречаются базовые блоки со сложными условиями, состоящими более чем из двух простых.

4.3 Второй шаг оптимизации

Второй шаг призван осуществить версионирование для подходящих шаблонов кода. Благодаря первому шагу все конструкции “if-elseif”, удовлетворяющие необходимым условиям, теперь представлены в виде двух отдельных базовых блоков.

Алгоритм второго шага в порядке RPO (Reverse Postorder) находит в графе потока управления базовые блоки с условиями проверки на равенство какой-либо переменной константе и дополнительно проверяет, что соответствующий базовый блок “then” содержит необходимый вызов так же, как это проверялось на первом шаге. Порядок RPO гарантирует, что в любой паре базовых блоков “if-elseif” блок “if” посетится первым, так как является предком блока “elseif”.

Трансформации, выполняемые на втором шаге (рис. 8):

1. Происходит расщепление (split) ребра, соединяющего блок “then” с его потомком. Вставляется специальный блок “merge”. Данный блок отвечает за точку схождения путей, проходящих через блоки “then” и “then_1” (описан в следующем пункте), позволяя компилятору осуществить восстановление SSA [10] формы с помощью добавления в блок “merge” необходимых 𝜑-функций.
2. Базовый блок “then”, содержащий необходимый вызов, копируется, создавая блок “then_1”. При создании блока “then_1” ребро, соединявшее блок “if” с блоком “then”, перенаправляется так, что теперь его потомком становится “then_1”.

Рис. 8. Пример работы алгоритма второго шага.

Поскольку первый шаг способен формировать цепочки “if-elseif” любой длины, тогда, соответственно, второй шаг способен осуществлять версионирование для любого числа подходящих проверок для каждого из вызовов, то есть могут быть обработаны примеры кода подобные изображенному на рис. 9.

Рис. 9. Пример версионирования для сложного случая.

5. Результаты работы оптимизации

В качестве результатов и демонстрации ценности проделанной работы приведена статистика работы реальных тестовых приложений из пакета CPUBench [11]. Замеры проводились на серверном процессоре с архитектурой ARM64, исходным набором опций был взят ‘-O3 -flto’. На диаграмме (рис. 10) показано отношение результатов запуска приложений с исходным набором опций, дополненным нашим проходом, к результатам запуска приложений с исходным набором. Методология CPUBench устанавливает, что в качестве результата каждой отдельного запуска выступает отношение времени выполнения данного запуска на эталонной машине к времени выполнения этого же запуска на тестируемой системе. Запуск каждого теста проводился 100 раз, при этом среднеквадратичное отклонения времени запуска не превышало 0,5%.

Рис. 10. Результаты по улучшению производительности тестовых приложений.

Максимальное ускорение в 19% было достигнуто на бенчмарке phyml. В этом бенчмарке встретилась конструкция, где “горячая” вычислительная функция содержала внутри себя два вложенных цикла с числом итераций, поступающим в функцию в качестве аргумента. Выше по графу вызовов располагалась функция, содержавшая в себе проверку соответствующей переменной на равенство 4 или 20. После изучения профиля программы оказалось, что значение этой переменной чаще всего было равно 4. Версионирование и последующее распространение значения 4 позволило циклической векторизации превратить вычисления в векторные, а раскрутке циклов трансформировать этот цикл в полностью линейный участок кода. Также имеют место ускорения на бенчмарке lightgbm примерно на 5% и на nektar примерно на 3%. Отметим, что на бенчмарке openfoam была обнаружена деградация производительности порядка 1%, которую не удалось сопоставить с каким-либо участком программы, исходя из анализа профиля. Предположительно, деградация возникла из-за изменения разложения кода в памяти и целевых адресов инструкций перехода.

Кроме того, было установлено, что при использовании представленного оптимизационного прохода, осуществляющего версионирование, общее число применений трансформации Распространения Констант в целом на пакете тестов увеличилось на 115 единиц.

6. Заключение

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

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

Список литературы

1. GCC official website. Available at: https://gcc.gnu.org/, accessed 01.11.2025. ↩
2. Wegman, Mark N., Zadeck F. K. Constant propagation with conditional branches. ACM Transactions on Programming Languages and Systems (TOPLAS), 1991, vol. 13, no. 2, pp. 181-210. ↩
3. Callahan D., Cooper K. D., Kennedy K., Torczon L. Interprocedural constant propagation. ACM SIGPLAN Notices, 1986, vol. 21, no. 7, pp. 152-161. ↩
4. Harrison W. H. Compiler analysis of the value ranges for variables. IEEE Transactions on software engineering, 1977, no. 3, pp. 243-250. ↩
5. Huang J. C., Leng T. Generalized loop-unrolling: a method for program speedup. Proceedings 1999 IEEE Symposium on Application-Specific Systems and Software Engineering and Technology. ASSET'99 (Cat. No. PR00122), IEEE, 1999, pp. 244-248. ↩
6. Liang X., Humos A. A., Pei T. Vectorization and parallelization of loops in C/C++ code, Proceedings of the International Conference on Frontiers in Education: Computer Science and Computer Engineering (FECS). The Steering Committee of The World Congress in Computer Science, Computer, 2017,
   pp. 203-206. ↩
7. Glek T., Hubicka J. Optimizing real world applications with GCC link time optimization. arXiv preprint. Available at: https://arxiv.org/abs/1010.2196, 2010, accessed 03.02.2026. ↩
8. Khedker U. GCC Translation Sequence and Gimple IR. GCC Resource Center, Department of Computer Science and Engineering. Indian Institute of Technology, Bombay, 2010. ↩
9. Исходный код в openEuler/gcc. Available at: https://gitee.com/openeuler/gcc/pulls/256/commits, accessed 03.02.2026. ↩
10. Cytron R., Ferrante J., Rosen B. K. et al. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems (TOPLAS), 1991, vol. 13, no. 4, pp. 451-490. ↩
11. Lu H., Ren X., Zhong W. et al. CPUBench: An open general computing CPU performance benchmark tool. Microelectronics & Computer, 2023, vol. 40, no. 5, pp. 75-83. ↩

Информация об авторах

Иван Александрович Зинин – студент МФТИ. Сфера научных интересов: компиляторные технологии, оптимизации, гетерогенные вычислительные системы.

Вячеслав Викторович Черноног – кандидат технических наук, ассистент кафедры перспективных вычислительных технологий МФТИ. Сфера научных интересов: компиляторные технологии, оптимизирующие компиляторы, анализ производительности высоконагруженных систем.