Table of Contents

Введение: почему важно зарегистрировать распределение

В основе каждой скомпилированной программы лежит скрытая битва за самый ценный аппаратный ресурс в процессоре: его регистры. Современные процессоры содержат небольшой набор сверхбыстрых мест хранения, называемых регистрами, обычно варьирующихся от 16 до 32 регистров общего назначения в таких архитектурах, как x86-64 или ARM64. Эти регистры работают со скоростью процессорных часов, в то время как основные доступы к памяти (DRAM) на порядок медленнее, часто накладывая сотни циклов задержки. Способность компилятора назначать переменные регистрам вместо памяти напрямую определяет скорость выполнения, энергоэффективность и размер кода.

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

В этой статье исследуется глубокая связь между окраской графов и распределением регистров. Мы рассмотрим фундаментальные концепции, классический алгоритм (алгоритм Чайтина), передовые методы, такие как объединение и разлив, практические проблемы и роль окрашивания графов в современных компиляторах, таких как GCC, LLVM и другие. К концу вы поймете, почему окрашивание графов остается краеугольным камнем оптимизации компилятора и как оно продолжает развиваться, чтобы удовлетворить требования современного оборудования.

Проблема распределения реестра: более глубокий взгляд

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

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

Почему графический дизайн является естественным

Графическая окраска является одной из классических NP-полных проблем. Тем не менее, распределение регистров становится NP-полным только тогда, когда нам требуется оптимальная окраска. На практике компиляторы используют эвристические алгоритмы, которые производят хорошие окраски в полиномиальное время. Картирование от распределения регистров до окраски графов было впервые описано Грегори Чайтином в 1981 году в основополагающей статье, которая установила окраску графов в качестве доминирующего подхода. С тех пор практически каждый оптимизирующий компилятор принял некоторый вариант распределения регистров окраски графов.

Создание графа помех

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

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

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

Алгоритм Чайтина: классический подход

Алгоритм Чайтина, названный в честь Грегори Чайтина, является основой распределения регистров с графическим окрашиванием. Он работает в серии этапов:

  1. Строить: Построить интерференционный граф с помощью анализа диапазона прямой трансляции.
  2. Упростите: Неоднократно удаляйте из графа узлы, имеющие меньше K-соседей (где K — число физических регистров), выталкивая их на стек. Эти узлы гарантированно являются цветными, поскольку у них есть максимум K-1-соседи и, таким образом, по крайней мере один свободный цвет.
  3. Таблетка: Если узел со степенью <K не существует, выберите узел, который будет пролит (т.е. удален из графика и сохранен в памяти). Эвристический выбор имеет значение: обычно выбираются узлы с высокой стоимостью разлива и/или высокой степенью. После удаления кандидата на разлив продолжается петля упрощения.
  4. Выберите: Поп-узлы из стека в обратном порядке и назначьте им цвет (физический регистр), не используемый ни одним уже окрашенным соседом.Если узел не может быть назначен (все цвета K, взятые соседями), он помечается для разлива и алгоритм должен перезапуститься с разливом.
  5. Вставка кода таблетки: Для каждого пролитого узла вставьте инструкции по хранению/загрузке в соответствующие точки для передачи значений между памятью и регистрами. Это изменяет диапазоны действия, поэтому процесс должен повторяться (часто итеративно) до тех пор, пока не потребуется пролить.

Сила алгоритма Чайтина заключается в его консервативной ширине регистра: фаза упрощения гарантирует, что узлы со степенью <K всегда окрашены, в то время как эвристика разлива пытается минимизировать накладные расходы на время выполнения. Однако NP-полнота означает, что алгоритм не может гарантировать оптимальную окраску без обратного отсчета. На практике эвристика хорошо работает.

Улучшения: Оптимистическая окраска

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

Уголь и разделение на живую грань

Распределители графического цвета также должны обрабатывать регистрационные копии (перемещаются). Когда инструкция по переезду копирует значение из одного виртуального регистра в другой, два регистра имеют идентичные значения в этой точке. Если они не мешают в другом месте, они могут быть коалесцированы в один виртуальный регистр, устраняя перемещение. Однако коалесцирование удаляет край помех между ними и уменьшает количество узлов, способствуя окраске. Агрессивное коалесцирование может иметь обратный эффект: оно может увеличить степень объединенного узла и вызвать разлив. Следовательно, , размещённые коалесцирующие методы (например, алгоритм Джорджа и Аппеля) упрощают межклапанное соединение и коалесцируют фазы для достижения баланса.

Расщепление на расстоянии в реальном времени — ещё один метод, который разбивает длинный диапазон на более мелкие кусочки, уменьшая помехи и часто улучшая цветовосприимчивость. Особенно он полезен для глобального распределения (по основным блокам). Современные распределители могут расщепляться на границах петли или на участках вызова, где погибают регистры, спасённые абонентами.

Разлив: искусство выбора, что выселить

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

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

Альтернативные подходы к распределению регистра

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

  • Распределение сканирования по строкам: Этот более простой и быстрый алгоритм выделяет регистры, сканируя линеаризованный порядок инструкций (например, в базовом блоке). Он имеет более низкие накладные расходы на компиляцию и хорошо работает для компиляторов точно в срок (JIT), где важна скорость. Сканирование по строкам было популяризировано Jikes RVM и используется во многих JIT (например, V8, компилятор C1 HotSpot).
  • Разделенное булевое квадратичное программирование (PBQP): Более новый метод, который формулирует распределение как квадратичную программу, позволяя лучше обрабатывать ограничения, такие как псевдоним регистра и параллелизм уровня инструкций. PBQP используется в LLVM распределитель регистра (в качестве альтернативы жадному распределителю по умолчанию).
  • Жадное распределение: Большинство современных компиляторов (например, GCC, LLVM) используют гибридные подходы. Аллокатор по умолчанию LLVM представляет собой жадный распределитель, который сочетает в себе аспекты окраски графов и линейного сканирования. Он создает живые диапазоны, жадно присваивает виртуальные регистры и использует расщепление и подсказки (например, предпочтения на основе инструкций по движению) для улучшения качества.

Графическое окрашивание против жадности: практические компромиссы

Чистая раскраска графов (в стиле Чайтина) обеспечивает чистую теоретическую модель, но может быть медленной для больших функций из-за построения графов и повторяющихся циклов разливов. Современные распределители часто торгуют оптимальностью скорости. Например, распределитель по умолчанию LLVM не основан на строгом раскраске графов; он использует алгоритм расщепления диапазона жизни [FLT: 0], который ближе к линейному сканированию с обратным отслеживанием. Тем не менее, фундаментальное понимание интерференционных графов и эвристики окраски остается центральным. Многие компиляторы исследований и статические рамки оптимизации по-прежнему полагаются на окраску графов для ее предсказуемости и качества.

Графическая окраска в компиляторах реального мира

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

  • GCC: Компилятор GCC исторически использовал графораспределитель (фаза «перезагрузки» была старым распределителем). Начиная с GCC 4.x, он переходил на региональный регистровый распределитель, который основывается на принципах графораскраски, но использует передовую эвристику и частоты.
  • LLVM: Семейство LLVM-распределителей регистров включает в себя вариант раскраски графа (основной) и более продвинутый «жадный» распределитель. Жадный распределитель внутренне конструирует интерференционный граф, но использует схему, основанную на приоритете, для назначения регистров, что делает его ближе к раскраске графа по духу.
  • Java HotSpot Compiler (C2): Серверный компилятор использует глобальный аллокатор регистров с графическим окрашиванием, который обрабатывает как регистры, так и слоты стека. Он выполняет разделение и коалесцирование в реальном масштабе времени, и он известен тем, что создает высоко оптимизированный код.
  • Граальский компилятор OpenJDK: Граал использует в качестве одного из своих вариантов вычислитель регистра с графическим окрашиванием, наряду с линейным сканированием для быстрых компиляций.

Все эти компиляторы демонстрируют, что раскраска графов не является академическим упражнением, а напрямую влияет на производительность программного обеспечения, которое мы используем ежедневно.

Проблемы и ограничения графического окрашивания

Несмотря на свою эффективность, распределение регистров с графическим цветом сталкивается с фундаментальными препятствиями:

  • NP-Тяжесть: Оптимальная окраска NP-полная. Эвристика может производить субоптимальные окраски, приводящие к ненужному разливу. Для функций со многими живыми диапазонами алгоритм может бороться.
  • Крупные графы: Современные программы с наложением (например, шаблоны C++) могут создавать огромные функции с десятками тысяч виртуальных регистров. Построение и окрашивание полного графа помех может стать непомерно медленным. Компиляторы часто используют двухфазное распределение: локальное распределение для небольших базовых блоков и глобальное распределение для горячих путей.
  • Комплексные аппаратные ограничения: Современные процессоры имеют псевдонимы регистров (например, полурегистр x86), регистровые пары, регистры специального назначения (указатель стека, регистры флага) и соглашения вызовов.
  • Точность принятия решений по схеме: Эвристика затрат на разброс зависит от статических оценок (например, глубины вложенности в цикл). Оптимизация под руководством профиля может улучшить это, но не все компиляторы используют профилирование.

Стратегии смягчения

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

Преимущества графического окрашивания: почему оно сохраняется

Учитывая сложность, почему окраска графов остается краеугольным камнем? Причины убедительны:

  • Почти оптимальное качество: Для большинства программ раскраска графов с консервативной эвристикой производит задания регистров, которые по крайней мере так же хороши, как и другие методы, и часто лучше, чем линейное сканирование.
  • Чистая теоретическая основа: Модель раскраски графов элегантна и проста в рассуждении.Доказательства правильности (например, консервативное свойство раскраски) придают инженерам-компилятора уверенность.
  • Масштабируемость с эвристикой: В то время как поведение в худшем случае плохое, программы реального мира редко демонстрируют графики помех в худшем случае. При правильной эвристике алгоритм масштабируется до миллионов инструкций.
  • Расширяемость: Новые аппаратные средства (например, многорегистрационные инструкции, ограничения для машин) могут быть включены путем добавления новых краев или цветов.

Графическая окраска также служит исходным пунктом для оценки других распределителей.Многие исследовательские работы сравнивают свой новый подход с графовой окраской в стиле Чайтина, демонстрируя ее непреходящую важность.

Будущие направления: графическое окрашивание в эпоху искусственного интеллекта и пользовательского оборудования

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

Более того, настраиваемое оборудование, такое как FPGA и грубозерные реконфигурируемые массивы (CGRA), имеет свои собственные регистроподобные ограничения. Модели графической окраски могут быть адаптированы для выделения вычислительных блоков или буферов. Это демонстрирует универсальность фундаментальной идеи: любая проблема планирования ресурсов с парными ограничениями может быть сведена к графовой окраске.

Заключение

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

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