Практикум «Оптимизирующие компиляторы» (на примере GCC), страница 9

Количество«активных» интервалов определяет количество необходимых регистров вданной точке программы. В случае если их слишком много, рядпеременных временно сохраняется из регистров в память. В принципе,время работы такого распределителя линейно.Так как последний алгоритм весьма прямолинеен, используется рядулучшений, рассмотрим их.При анализе времени жизни полезно выделить места, где переменная неимеет полезного значения. Например, на рисунке 14 показан базовый блоки обозначено время жизни переменных с указанием дыр во времени жизни.Практикум «оптимизирующие компиляторы»В частности, если мы распределяем регистр r для переменной t, но в еёвремени жизни есть дыра, в которую умещается время жизни другойпеременной u, то мы можем распределить переменной u тот же регистр r.В частности, на рисунке переменная Т3 целиком помещается в дыру вовремени жизни Т1.Для подсчета времён жизни и «дыр» в них необходим реверсный проходпо программному коду.Таким образом, регистры представляются в виде ячеек, каждой из которыхв некоторый момент времени может соответствовать только однозначение.

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

Эта трактовка нескольконеоднозначна – фактически дыра во времени жизни обозначает, чтообразована новая переменная, но здесь понятие «дыры» вводится дляудобства представления.Таким образом, распределитель просматривает программу в прямомнаправлении, собирая информацию о времени жизни. При необходимостиназначения временной переменной t регистра выбирается либо один изсвободныхрегистров,либожевыбираетсярегистр,содержащийпеременную, у которой сейчас существует «дыра» и время жизни tцеликом умещается в «дыре». После сопоставления регистра всеобращения к t в программе заменяются обращениями к r.Если свободных регистров нет, необходимо подыскать «занятый» регистр,освобождение которого будет наименее болезненно. Должна быть выбранапеременная, которая будет позже остальных востребована, при этомнеобходимо учитывать глубину вложенности цикла, где она востребуется.Практикум «оптимизирующие компиляторы»Фактически, все переменные сохраняются в регистрах как можно дольше изаписываются в память только в том случае, если регистр нужен для«более приоритетной» переменной.

Ещё одна оптимизация заключается втом, что регистры, значение переменной в которых не отличается отзначения в памяти, не будут записываться обратно в память.При распределении регистров необходимо решить ещё одну проблему. Вслучае, если переменная вытесняется из памяти в одном или обоихбазовых блоках В2 и/или В3, к моменту перехода потока управления вблок В4 фактически две копии переменной могут находиться в разныхрегистрах, либо же в одном потоке переменная может находиться врегистре, а в другом – в памяти.

В этом случае производятся следующиедействия: 1) если копии переменной находятся в разных регистрах, то водин из потоков управления вставляется команда копирования из регистрав регистр. В случае, если переменная в одном потоке управления изменена,а в другом её нет в регистрах, делается сохранение переменной в памяти.Вообще, поведение распределителя в данном случае может зависеть отобстоятельств – если эта переменная будет использована практическисразу после слияния потоков управления, есть смысл загрузить её врегистр в той ветви, гдё её нет в регистре до слияния потоков.Более гибкое решение предполагает, что регистры у нас равноправны,следовательно, привязка регистров может быть нежёсткой, чтобы затемможно было подкорректировать номера при слиянии потоков, чтопозволит сэкономить несколько команд, но с другой стороны, усложниталгоритм.Ещё несколько улучшений алгоритма касаются поддержки современныхмикропроцессоров.

Для процессоров с длинным командным словомалгоритмы усложнены – так как у нас несколько времён жизнипеременных могут начинаться и завершаться одновременно, кроме того,Практикум «оптимизирующие компиляторы»команда загрузки/сохранения обычно может быть только одна нанесколько параллельно исполняющихся арифметических команд. В этомслучае переменные должны загружаться в память значительно раньшеместа их затребования, так как одна длинная команда может потребоватьболее трёх-четырёх переменных.Подытоживая, отметим, что в принципе алгоритмы распределениярегистров достаточно просты и понятны.

С другой стороны архитектурапроцессора оказывает определяющее влияние, и алгоритм обрастаетдостаточно сложными эвристиками.Генерация кодаГенерация кода может выполняться как минимум двумя общимиспособами: 1) полный перебор; 2) эвристические методы, основанные насписочных расписаниях. Полный перебор обеспечивает оптимальный код,но из-за его слишком долгого времени (функция экспоненциальна)исполнения, он не может быть использован даже на самых быстрыхПЭВМ.Эвристическиеметодыобеспечиваютгенерациюкодазаквазилинейное время, но могут давать погрешность от 5% до 15%.Для орграфа ББ Kb=(Vb,Eb) вводится фиктивная начальная вершина v0,fT(v0)="команда", и дуги e=(v0,vi) для всех vi, для которых fT(vi)="ресурс", ине существует такого v∈V, что fT(v)="команда", vi∈OUT(v).

Аналогичновводим конечную вершину vE, fT(vE)="команда", и дуги e=(vj,vE), для всехvj, для которых fT(vj)="ресурс", и не существует такого v∈V, чтоfT(v)="команда", vj∈IN(v). Для Kb вводятся следующие метрики:1)λv – длина пути из начальной вершины v0 в вершину v;2)γv – длина пути из вершины v в конечную вершину vE;3)lij – длина пути из вершины vi в вершину vj.Практикум «оптимизирующие компиляторы»Примем, что для ek=(vi,vj), где fT(vj)="команда", lij=0, а для em=(vi,vj), гдеfT(vj)="ресурс", lij определяется временем исполнения команды vj.Дополнительно вводим метрику – длину всего Kb Λb – длина пути извершины v0 в vE.Метрика Λb фактически является временем исполнения ББ на МП снеограниченными ресурсами.

В случае ограничения по ресурсам, реальноевремя исполнения вырастает обратно пропорционально к степениподдержки МП скалярного параллелизма.В процессе генерации кода ББ вводится время t, которое при генерациикода для начальной вершины ББ равняется 0, и увеличивается на единицу скаждой сгенерированной командой базового блока. Для команды vi(fT(vi)="команда"), исполнение которой началось в момент времени t0,результат будет получен в регистрах vj(fT(vj)="ресурс") в момент времениt0+dt, где dt – время исполнения vi (для системы команд RISC/CISC).Условием исполнения команды является доступность необходимый ейрегистровых операндов в регистрах и освобождение необходимыхинструкции конвейеров, что проверяется с помощью конечного автомата,представляющего конвейер.

В цикле генерации команды для KB=(VB,EB)просматриваются готовые к исполнению команды vi∈V, где для всехкомандоперандыприсутствуютвфизическихрегистрах.Ссопоставленных операциям ББ инструкций МП определяется множество V= { vi }, где vi – готовая к исполнению команда. Исходя из множества Vопределяется итоговая команда Ki, для которой функция оценкимаксимальная.

В качестве функции оценки используется сумма путей (дляодной команды – просто значение пути) атомарных команд-компонентсформированной команды cbest(V)=ΣγI, где γi – путь до конечной вершиныдля некоторой рассматриваемой команды. На формирование множества Vоказывает влияние информация о наличии свободных конвейеровПрактикум «оптимизирующие компиляторы»функциональных устройств, обновляющаяся после каждой генерациикомандывкаждыймоментвремениtсогласноописаниям,скомпилированным в конечный автомат. В случае конфликта из-зазанятости ресурса используется, например, алгоритм, описанный в [15],проиллюстрированный на следующем рисунке:λiλjliviγivjljγjРисунок 15.

Конфликт между командами по использованию функционального устройства.Как li и lj обозначены времена исполнения команд vi и vj. Для определенияочерёдности при исполнении команд вычисляется значение логическоговыражения λi+li+γj≥λj+lj+γi. При истинности выражения исполняется vj,иначе – vi, с целью минимального увеличения высоты Λb графа ББ.

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

Приведёмпример: процессоры с длинным командным словом могут исполнять затакт около 4-8 предварительно определённых компилятором команд. ЕслиПрактикум «оптимизирующие компиляторы»учесть,чтовпоследовательнойпрограмместепеньскалярногопараллелизма не превышает 2 (т.е. обычно не более 2-х команд могутвыполняться одновременно), возникает вопрос о том, как же задействоватьимеющиеся у нас в распоряжении вычислительные мощности, если всреднем степень параллелизма настолько мала? Ответ на этот вопроснетривиален – процессоры, которые могут выполнять за такт большоеколичество арифметико-логических операций, рассчитаны на исполнениециклов. При этом вид исполнения предполагается такой: посколькунаправление перехода в цикле обычно известно (всё время на начало),можно считать, что за телом цикла следует такое же тело (но представляетсобой следующую итерацию).

Таким образом поступают современныесуперскалярные процессоры: они могут просматривать не только первуюитерацию, но и вторую и третью и т.д., представляя их в виде линейногоучастка, при этом может быть начато исполнение готовых команд излюбой итерации. Таким образом, исполнение последовательных итерацийцикла на самом деле может перекрываться. В случае процессора сдлинным командным словом исполнение этой задачи берёт на себякомпилятор, в этом случае выполнение цикла с перекрытием итерацийбудет называться «программно конвейеризированным», а метод получениятакого расписания – программной конвейеризацией. При этом среднеевремя,проходящеемеждуначаломвыполненияпоследовательныхитераций называется интервалом инициации итераций (ИИИ).Существует достаточно много алгоритмов программной конвейеризации.Можно выделить версии «модульного планирования», где первоначальныйИИИ равен времени исполнения неконвейеризированного цикла, а затемпостепенно уменьшается на единицу.