А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 137

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 137)

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

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

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

Поскольку программы тратят ббльшую часть времени на выполнение внутренних циклов, естественным подходом к глобальному назначению регистров будет попытка хранить часто используемое значение в фиксированном регистре в процессе выполнения всего цикла. Предположим, что нам известна циклическая структура графа потока и мы знаем, 67З 8.8.

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

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

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

Однако при использовании подхода из раздела 8.6 для генерации кода блока весьма вероятно, что вычисленное в блоке значение х останется в регистре, если используется далее в этом блоке. Таким образом, мы подсчитываем суммарную экономию от хранения ге в регистре, прибавляя единицу за каждое использование т в цикле Е, если такому использованию не предшествует присваивание гд в том же блоке. Кроме того, мы сэкономим две единицы, если избежим сохранения ш в конце блока. Таким образом, если ш хранится в регистре, мы добавляем к суммарной экономии по две единицы для каждого блока А, в котором к получает значение и остается живым при выходе из блока, Вместе с тем, если переменная ш является живой при входе в заголовок цикла, мы должны загрузить ее в регистр перед входом в цикл Ь.

Такая загрузка стоит две единицы. Кроме того, для каждого из выходных блоков В цикла Ь, в которых ьвбьявление переменных в качестве регистровых в языке программирования С является всего лишь пожеланием программиста, но никак не директивой компилятору, который при генерации кода может пренебречь этими объявлениями 1например, когда регистровыми объявлено больше переменных, чем имеется регистров у целевой машины). В современных компиляторах зти возможности оставлены в целях совместимою и, но их использование рассматривается как крайне нежелательное вмешательство в работу компилятора.

— Прим, ред. 674 Глава 8. Генерация кода х остается живым при входе в преемник блока В вне цикла Л, мы должны сохранить значение х, что также стоит две единицы. Однако в предположении, что цикл выполняется много раз, этой потерей экономии можно пренебречь (она однократна при входе в цикл). Таким образом, приближенная формула для выгоды от выделения регистра для хранения переменной х в цикле А выглядит следующим образом; (иве 1х, В) + 2* 1вве (х, В)) (8.1) Блоки В в Е Здесь иве 1х, В) — число использований х в В до любого определения х, а йие(х, В) равно 1, если переменная х остается живой при выходе из блока В, в котором ей присваивается значение, и 0 — в противном случае.

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

Переменные, живые при входе в блок и выходе из него, показаны на рисунке непосредственно над и под блоком. Здесь имеется несколько тонкое~ей, относящихся к живым переменным, о которых мы поговорим в следующей главе. Например, обратите внимание, что и е, и й живы при выходе из блока Вп но при входе в блок Вз жива только переменная е, а при входе в блок Вз — толь- живыв Ь,с,с,е, г живые Рис. 8.17. Граф потока внутреннего цикла 675 8.8. Распределение и назначение регистров ко й. В общем случае переменные, живые в конце блока, представляют собой объединение переменных, живых при входе в блоки-преемники.

При вычислении (8.1) для х = а заметим, что переменная а жива при выходе из Вз и получает в этом блоке свое значение, но не жива при выходе из блока Вз, Вз или Вл. Следовательно, 2; изе (о, В) = 2. Следовательно, значение (8.1) вас для х = а равно 4, а значит, выбирая а для хранения в одном из глобальных регистров, мы получаем экономию в 4 единицы. Значения (8.1) для Ь, с, г), е и й равны соответственно 5, 3, 6, 4 и 4, а потому для глобальных регистров КО, К1 и К2 мы можем выбрать переменные а, Ь и с1. Использование Р.О для хранения е или й вместо а дает тот же конечный результат.

На рис. 8.18 показан ассемблерный код, сгенерированный по рис. 8.17 с применением стратегии из раздела 8.6 для генерации кода каждого базового блока. Мы не приводим здесь код для опущенных условных и безусловных переходов в конце каждого блока, а также не показываем сгенерированный код в качестве единого непрерывного потока, как это осуществляется на практике. а Рвс. 8.18. Последовательность, использующая глобальное назначение регистров 676 Глава 8. Генерация кода 8.8.3 Назначение регистров для внешних циклов Назначив регистры и сгенерировав код для внутренних циклов, мы можем применить ту же идею и для больших циклов.

Если внешний цикл Л~ содержит внутренний цикл Лз, имена, хранящиеся в регистрах в Лз, не обязаны храниться в регистрах в Л1 — Лз. Если мы храним х в регистре в Ез, но не в 1,ы следует принять меры по загрузке к при входе в Ьз и сохранению при выходе из него.

Мы оставляем читателю в качестве упражнения вывод критерия для выбора имен, хранимых в регистрах во внешнем цикле А, по уже выбранным для хранения в регистрах именам во всех вложенных в Л циклах. 8.8.4 Распределение регистров путем раскраски графа Когда для вычисления требуется регистр, а все доступные регистры уже используются, содержимое одного из них должно быть сохранено (сброшсно— зр!!1ег!) в ячейке памяти для его освобождения. Раскраска графа — это простой систематичный метод распределения регистров и управления их сбросом.

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

Обычно их использование непосредственно транслируется в режим обращения к адресам, использованным в машинных командах. Если требуется более сложное обращение к адресу памяти, то оно разбивается на несколько машинных команд и, возможно, придется создать временный символический регистр !или ряд таких регистров). После выбора команд выполняется второй проход, в процессе которого и происходит назначение физических регистров символическим. Цель назначения состоит в минимизации стоимости сбросов.

11ри втором проходе для каждой процедуры строится граф взаимодействия регистров (гей)з1ег-1пгегГегепсе бган), узлы которого представляют собой символические регистры, а дуги соединяют два узла в том случае, если в момент определения одного из регистров второй оказывается жив. Например, граф взаимодействия регистров для представленного на рис. 8.17 кода будет иметь узлы лля имен а и с). Поскольку в блоке В1 в момент определения г! во второй инструкции а является живой переменной, эти узлы графа взаимодействия регистров будут соединены дугой. Далее предпринимается попытка раскрасить граф й цветами, где )с — количество доступных для назначения регистров.

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

Характеристики

Список файлов книги