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

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

Текст из файла

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 Построение интервалов жизниПостроение множеств переменных, живых на выходе изкаждого блока.

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

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций