Лекция 08. Распределение и назначение регистров (Лекции (2015))

8. Распределениеи назначениерегистров8.1 Постановка задачи8.1.1 Модель памятиВ промежуточном представлении c каждой переменнойсвязывается ячейка памяти для хранения ее значений.Эта ячейка называются абстрактной, так как с нейсвязывается символический адрес, который может указыватьна регистры, стек, кучу, статическую память,причем каждому классу памяти соответствует бесконечно многосимволических адресовВ компиляторах часто используется модель памяти«регистр – регистр».В этой модели компилятор старается расположить все данныена символических регистрах (или псевдорегистрах).В отличие от физических регистров, число которых невелико,псевдорегистров бесконечно много.При распределении памяти часть псевдорегистров придетсяотобразить не на регистры, а в память.8.1 Постановка задачи8.1.2 Распределение и назначение регистровРаспределение регистровотображает неограниченное множество имен (псевдорегистров)на конечное множество физических регистров целевой машины,Это NP-полная задачаНазначение регистровотображает множество распределенных имен регистров нафизические регистры целевого процессора.

Для решения этойзадачи известно несколько алгоритмов полиномиальнойсложности.Во время назначения регистров предполагается, чтораспределение регистров уже было выполнено, так что пригенерации каждой команды требуется не более n регистров(n – число физических регистров).8.2 Локальное распределение регистров8.2.1Постановка задачиПрименения регистров:На регистры помещаются операнды и результатыопераций(при выполнении операции необходимо, чтобы ееоперанды находились на регистрах, результатполучается на регистре).Регистры – временные переменные(на регистры помещаются промежуточные результаты привычислении выраженийесли удается, на них размещаются все переменные,использующиеся в пределах только одного базовогоблока).Регистры используются для хранения глобальныхзначений.Регистры используются для помощи в управлениипамятью времени выполнения (например для управлениястеком времени выполнения, включая поддержкууказателя стека).8.2 Локальное распределение регистров8.2.1Постановка задачиРассмотрим алгоритм, распределяющий только те регистры,которые предназначены для операндов и временныхпеременных(остальные регистры зарезервированы).Предположения:Базовый блок уже оптимизирован (все «лишние»вычисления удалены).Для каждой операции OP существует команда видаOP reg, reg, reg(операнды и результат – на регистрах)В набор команд входят команды:LD reg, mem (загрузка из памяти на регистр)ST mem, reg (сохранение значения регистра)Необходимо, чтобы генератор кода минимизировал количествоопераций LD и ST в целевом коде8.2 Локальное распределение регистров8.2.2Дескрипторы регистров и переменныхДескриптор DR[r] регистра r указывает, значение какойпеременной содержится на регистре r (на каждом регистре могутхраниться значения одного или нескольких имен)Дескриптор DA[a] переменной a указывает адрес текущегозначения a.

Это может быть регистр, адрес памяти, указательстекаПусть определена функция getReg (I), имеющая доступ ко всемдескрипторам регистров и адресов, а также к другим атрибутамобъектов, хранящимся в таблице символов,которая назначает регистры для операндов и результатакоманды I.Функция getReg (I) позволяет назначать регистры во времявыбора команд8.2 Локальное распределение регистров8.2.3Выбор команд для базового блокаВыбор команд для вычислительной трехадресной инструкцииx  op, у, z1.2.3.4.С помощью функции getReg() выбираются регистрыRx, Ry и Rz для x, у и z.Если DR[Ry]  у (у не находится на Ry), генерируетсякомандаLD Ry, y',где у' = DA[y] (местоположение у в памяти).Если DR[Rz]  z, а DA[z] = z', генерируется командаLD Rz, z'.Генерируется команда OP Rx, Ry, Rz.8.2 Локальное распределение регистров8.2.3Выбор команд для базового блокаВыбор команды для инструкции копирования x = уФункция getReg() всегда выбирает для x и у одни и те жерегистры.Если DR[Ry]  у, генерируется команда LD Ry, y.Если DR[Ry] = у, ничего не генерируетсяВо всех случаях обновляется DR[Ry]: х становится одним иззначений, находящихся на Ry.Генерация команды запоминания значений переменных,остающихся живыми после выхода из блока.Если переменная х жива на выходе из блока,и если в конце блока оказывается, что DA[x] = R (а не х),требуется генерация команды ST x, R.8.2 Локальное распределение регистров8.2.3Выбор команд для базового блокаПравила обновления DR и DA после генерации командыДля команды LD R, х:изменяем DR[R]: в R хранится только x;изменяем DA[x], добавляя ссылку на RДля команды ST x, Rизменяем DA[x], добавляя ссылку на xДля команды: ADD Rx, Ry, Rz:изменяем DR[Rx]: в Rx хранится x;изменяем DA[x]: x – только на Rxудаляем Rx из DA всех переменных, кроме х.Для команды х = уесли DA[y]  Ry добавляем команду LD Rу, у;изменяем DA[x] так, чтобы он указывал толькона Ry8.2 Локальное распределение регистров8.2.4ПримерГенерация кода для базового блока:12345tuvad-,-,+,d+,a, ba, ct, uv, ut, u, v – временные переменные,локальные для блока,а, b, с, d – переменные, живыепри выходе из блока.Для инструкции 1: t = a – b необходимо сгенерировать три команды:загрузка регистра Raзагрузка регистра Rbвычитание (результат на регистре Rt)R1LDR1aR2R1,R2R3abcdabcdatuvuvgetReg() выдает R1 для RaR3abcda, R1bcdt8.2 Локальное распределение регистров8.2.4ПримерГенерация кода для базового блока:1 t  -, a, b2 u  -, a, c3 v  +, t, u4 a  d5 d  +, v, u– временные переменные,локальные для блока,а, b, с, d – переменные, живые привыходе из блока.t, u, vДля инструкции 1: t = a – b необходимо сгенерировать три команды:загрузка регистра Raзагрузка регистра Rbвычитание (результат на регистре Rt)R1R2R3aLDLDR1,R2,R1R2ababcdabcdabtuvuvgetReg() выдает R2 для RbR3aba, R1 b, R2cdcdt8.2 Локальное распределение регистров8.2.4ПримерГенерация кода для базового блока:1 t  -, a, b2 u  -, a, c3 v  +, t, u4 a  d5 d  +, v, u– временные переменные,локальные для блока,а, b, с, d – переменные, живые привыходе из блока.t, u, vДля инструкции 1: t = a – b необходимо сгенерировать три команды:загрузка регистра Raзагрузка регистра Rbвычитание (результат на регистре Rt)R1R2abLDLDSUBR1,R2,R2,R1R2atR3aba, R1 b, R2abR1,R3R2cdcdtuvuvgetReg() выдает R2 для RtabcdtabcdR28.2 Локальное распределение регистров8.2.4ПримерГенерация кода для базового блока:1 t  -, a, b2 u  -, a, c3 v  +, t, u4 a  d5 d  +, v, u– временные переменные,локальные для блока,а, b, с, d – переменные, живые привыходе из блока.t, u, vДля инструкции 2: u = a – c необходимо сгенерировать две команды:загрузка регистра Rcвычитание (результат на регистр Ru)R1R2R3abcdtuvatabcdR2LDSUBR3,R ,R1R2R3abcdtuutcabc, R3dR2R1cR1,getReg() выдаетR3 для Rc и R1 для RuR2vu помещается на R1, так как значение а, ранее располагавшееся на R1, большевнутри блока не используется8.2 Локальное распределение регистров8.2.4ПримерГенерация кода для базового блока:1 t  -, a, b2 u  -, a, c3 v  +, t, u4 a  d5 d  +, v, u– временные переменные,локальные для блока,а, b, с, d – переменные, живые привыходе из блока.t, u, vДля инструкции копирования 4: a = d необходимо сгенерировать однукоманду:загрузка регистра RdR1R2R3abcdtuvutvabcdR2R1R3LDR2,getReg() выдает R2 для RddR1R2R3abcdua, dvabcd, R2В регистре R2 теперь хранятся и d, и а.tuvR1R38.2 Локальное распределение регистров8.2.4ПримерГенерация кода для базового блока:1 t  -, a, b2 u  -, a, c3 v  +, t, u4 a  d5 d  +, v, u– временные переменные,локальные для блока,а, b, с, d – переменные, живые привыходе из блока.t, u, vДля инструкции 5: d = v + u необходимо сгенерировать одну команду:сложение, результат на регистр RdR1R2R3abcdua, dvabcd, R2ADDR1,R3,tuvR1R3getReg() выдает R1 для RdR1R1R2R3abcddavR2bcR1tПосле этой командыd хранится только на R1, но не в ячейке памяти для d.a хранится только на R2, но не в ячейке памяти для a.uvR38.2 Локальное распределение регистров8.2.4ПримерГенерация кода для базового блока:1 t  -, a, b2 u  -, a, c3 v  +, t, u4 a  d5 d  +, v, u– временные переменные,локальные для блока,а, b, с, d – переменные, живые привыходе из блока.t, u, vВ заключение необходимо сохранить живые переменные a и d, значениякоторых есть только на регистрахR1R2R3abcddavR2bcR1STSTa,d,R2R1R1R2R3abcddava, R2bcd, R1tuvR3tuvR38.2 Локальное распределение регистров8.2.4ПримерГенерация кода для базовогоблока:1 t  -, a, b2 u  -, a, c3 v  +, t, u4 a  d5 d  +, v, uСгенерированный код:LDR1, aLDR2, bSUBR2, R1,LDR3, cSUBR1, R1,ADDR3, R2,LDR2, dADDR1, R3,STa, R2STd, R1t, u и v – временные переменные,локальные для блока,а, b, с и d – переменные, живые привыходе из блока.Код содержит4 команды LD2 команды STR2R3R1R1Все эти команды связаны смножествами In(B) и Out(B)переменных живыхпри входе в блок B ипри выходе из него6 команд из 10 связаны собращениями к памяти8.2 Локальное распределение регистров8.2.5 Реализация функции getRegR1R2R3abcddava, R2bcd, R1iiiiooootuvR3fГенерация команды для инструкции Iх  op, y, zвыбор регистров для операндов y и zвыбор регистра для результата хВыбор регистра Ry для операнда y(регистр Rz для операнда z выбирается аналогично) .Если DA[y] ссылается на регистр R, то полагаем Rу = RЕсли DA[y] не содержит ссылок на регистры, ноимеется регистр R, для которого D[R] не содержитссылок ни на одну переменную, то полагаем Rу = R8.2 Локальное распределение регистров8.2.5 Реализация функции getRegВыбор регистра Ry для операнда yЕсли DA[y] не содержит ссылок на регистры и неимеется ни одного регистра R, для которого DR[R] несодержит ссылок ни на одну переменную, то R можноиспользовать в качестве Rу , если для каждой переменнойv, ссылка на которую содержится DR[R], выполняется одноиз следующих условий: DA[v] содержит ссылку не только на R, но и на адрес v, v представляет собой переменную х, вычисляемуюкомандой I, и х не является одновременно одним изоперандов команды I, переменная v после команды I больше не используется.Если ни одна из перечисленных выше ситуаций не имеетместа, то прежде чем использовать R в качестве Rу,необходимо выполнить сброс регистра, т.е.

командуST v, R8.2 Локальное распределение регистров8.2.5 Реализация функции getRegВыбор регистра Rx для результата xЕсли DR[R] ссылается только на х, то полагаем Rх = RЭто можно делать даже тогда, когда х является одним изу или z, так как в одной машинной команде допускаетсясовпадение двух регистров.Если y не используется после команды I и если DR[Ry]ссылается только на y, то Ry может использоватьсяв роли Rx.Если z не используется после команды I и если DR[Rz]ссылается только на z, то Rz может использоватьсяв роли Rx.Генерация команд для инструкции Iх  уСначала выбирается Ry, как и для операнда инструкциих  op, y, z, после чего полагается Rx = Ry.8.2 Локальное распределение регистров8.2.6 ОграниченияВ примере на рисунке независимое назначение регистров вбазовых блоках привело к тому, что для одной и той жепеременной x в каждом блоке используются разные регистрыЕсли бы getReg блока B3 знала, что в блоке B1 значение x былополучено на R7, то выделила бы для x регистр R7, чтопозволило бы исключить команду загрузки на регистр в блоке B3Наличие блоков B2 и B4 еще больше усложняет проблему, так каквозникают различные требования на разных путяхB1B2ST x, R7B3ST x, R3B4LD R2, xLD R4, x8.3 Глобальное распределение и назначение регистров8.3.1 Интервалы жизниИнтервалом жизни (ИЖ) значения w переменной v называетсямножество команд программы, начиная с команды, в которойпеременная v определяется со значением w, и кончая последнейкомандой, в которой переменная v используется с этимзначением.012345678910LDLDLDLDLDLDMULMULMULMULSTR0R1R2R3R4R5R1R1R1R1v…R0(0)2R0(@x)R0(@y)R0(@z)R1R2R1R3R1R4R1R5R0(0)|||||||||||R0R1R1R1R1R1R2R3R4R5[0,10][1,6][6,7][7,8][8,9][9,10][2,6][3,7][4,8][5,9]8.3 Глобальное распределение и назначение регистров8.3.2 Построение интервалов жизниПостроение множеств переменных, живых на выходе изкаждого блока.