Тема 13 2018Распределение_и_назначение. 13. Распределение и назначение регистров 13. 1
 Скачать 0.73 Mb.
|
|
13. Распределение и назначение регистров 13.1 Постановка задачи В промежуточном представлении c каждой переменной связывается ячейка памяти для хранения ее значений Эта ячейка называются абстрактной , так как с ней связывается символический адрес , который может указывать на регистры, стек, кучу, статическую память, причем каждому классу памяти соответствует бесконечно много символических адресов В компиляторах часто используется модель памяти « регистр – регистр ». В этой модели компилятор старается расположить все данные на символических регистрах (или псевдорегистрах ). В отличие от физических регистров, число которых невелико, псевдорегистров бесконечно много. При распределении памяти часть псевдорегистров придется отобразить не на регистры, а в память. 13.1.1 Модель памяти 13.1 Постановка задачи 13.1.2 Распределение и назначение регистров Распределение регистров отображает неограниченное множество имен (псевдорегистров) на конечное множество физических регистров целевой машины , Это NP- полная задача Назначение регистров отображает множество распределенных имен регистров на физические регистры целевого процессора. Для решения этой задачи известно несколько алгоритмов полиномиальной сложности. Во время назначения регистров предполагается, что распределение регистров уже было выполнено, так что при генерации каждой команды требуется не более n регистров ( n – число физических регистров ). 13.2 Локальное распределение регистров 13.2.1 Постановка задачи Применения регистров: На регистры помещаются операнды и результаты операций ( при выполнении операции необходимо, чтобы ее операнды находились на регистрах, результат получается на регистре ). Регистры – временные переменные ( на регистры помещаются промежуточные результаты при вычислении выражений если удается, на них размещаются все переменные, использующиеся в пределах только одного базового блока ). Регистры используются для хранения глобальных значений Регистры используются для помощи в управлении памятью времени выполнения (например для управления стеком времени выполнения, включая поддержку указателя стека). 13.2 Локальное распределение регистров 13.2.1 Постановка задачи Рассмотрим алгоритм, распределяющий только те регистры, которые предназначены для операндов и временных переменных ( остальные регистры зарезервированы). Предположения: Базовый блок уже оптимизирован ( все «лишние» вычисления удалены ). Для каждой операции OP существует команда вида OP reg, reg, reg (операнды и результат – на регистрах) В набор команд входят команды: LD reg, mem (загрузка из памяти на регистр) ST mem, reg (сохранение значения регистра) Необходимо, чтобы генератор кода минимизировал количество операций LD и ST в целевом коде Дескриптор DR[r] регистра r указывает, значение какой переменной содержится на регистре r (на каждом регистре могут храниться значения одного или нескольких имен) Дескриптор DA[a] переменной a указывает адрес текущего значения a . Это может быть регистр, адрес памяти, указатель стека Пусть определена функция getReg (I) , имеющая доступ ко всем дескрипторам регистров и адресов, а также к другим атрибутам объектов, хранящимся в таблице символов, которая назначает регистры для операндов и результата команды I . Функция getReg (I) позволяет назначать регистры во время выбора команд 13.2 Локальное распределение регистров 13.2.2 Дескрипторы регистров и переменных 13.2 Локальное распределение регистров 13.2.3 Выбор команд для базового блока Выбор команд для вычислительной трехадресной инструкции x op, у, z 1. С помощью функции getReg() выбираются регистры R x , R y и R z для x , у и z 2. Если DR[R y ] у ( у не находится на R y ), генерируется команда LD R y , y' , где у' = DA[y] ( местоположение у в памяти ). 3. Если DR[R z ] z , а DA[z] = z' , генерируется команда LD R z , z' 4. Генерируется команда OP R x , R y , R z . 13.2 Локальное распределение регистров 13.2.3 Выбор команд для базового блока Выбор команды для инструкции копирования x = у Функция getReg() всегда выбирает для x и у одни и те же регистры Если DR[R y ] у , генерируется команда LD R y , y . Если DR[R y ] = у , ничего не генерируется Во всех случаях обновляется DR[R y ] : х становится одним из значений , находящихся на R y Генерация команды запоминания значений переменных, остающихся живыми после выхода из блока. Если переменная х жива на выходе из блока, и если в конце блока оказывается, что DA[x] = R (а не х), требуется генерация команды ST x, R 13.2 Локальное распределение регистров 13.2.3 Выбор команд для базового блока Правила обновления DR и DA после генерации команды Для команды LD R, х : изменяем DR[R] : в R хранится только x ; изменяем DA[x] , добавляя ссылку на R Для команды ST x, R изменяем DA[x] , добавляя ссылку на x Для команды: ADD R x , R y , R z : изменяем DR[R x ] : в R x хранится x ; изменяем DA[x]: x – только на R x удаляем R x из DA всех переменных, кроме х . Для команды х = у если DA[y] R y добавляем команду LD R у , у ; изменяем DA[x] так, чтобы он указывал только на R y 13.2 Локальное распределение регистров 13.2.4 Пример t , u , v – временные переменные, локальные для блока, а , b , с , d – переменные, живые при выходе из блока. Для инструкции 1 : t = a – b необходимо сгенерировать три команды : загрузка регистра R a загрузка регистра R b вычитание (результат на регистре R t ) R 1 R 2 R 3 a b c d t u v a b c d R 1 R 2 R 3 a a b c d t u v a, R 1 b c d LD R1, a getReg() выдает R 1 для R a Генерация кода для базового блока: 1 t -, a, b 2 u -, a, c 3 v +, t, u 4 a d 5 d +, v, u 13.2 Локальное распределение регистров 13.2.4 Пример t , u , v – временные переменные, локальные для блока, а , b , с , d – переменные, живые при выходе из блока. Для инструкции 1 : t = a – b необходимо сгенерировать три команды : загрузка регистра R a загрузка регистра R b вычитание (результат на регистре R t ) R 1 R 2 R 3 a R 1 R 2 R 3 a b a b c d t u v a, R 1 b, R 2 c d a b c d t u v a b c d LD R1, a LD R2, b getReg() выдает R 2 для R b Генерация кода для базового блока: 1 t -, a, b 2 u -, a, c 3 v +, t, u 4 a d 5 d +, v, u 13.2 Локальное распределение регистров 13.2.4 Пример t , u , v – временные переменные, локальные для блока, а , b , с , d – переменные, живые при выходе из блока. Для инструкции 1 : t = a – b необходимо сгенерировать три команды : загрузка регистра R a загрузка регистра R b вычитание (результат на регистре R t ) R 1 R 2 R 3 a b a b c d t u v a, R 1 b, R 2 c d LD R1, a LD R2, b SUB R2, R1, R2 R 1 R 2 R 3 a t a b c d t u v a b c d R 2 getReg() выдает R 2 для R t Генерация кода для базового блока: 1 t -, a, b 2 u -, a, c 3 v +, t, u 4 a d 5 d +, v, u 13.2 Локальное распределение регистров 13.2.4 Пример t , u , v – временные переменные, локальные для блока, а , b , с , d – переменные, живые при выходе из блока. Для инструкции 2 : u = a – c необходимо сгенерировать две команды : загрузка регистра R c вычитание (результат на регистр R u ) R 1 R 2 R 3 u t c a b c d t u v a b c, R 3 d R 2 R 1 LD R3, c SUB R , R1, R2 R 1 R 2 R 3 a t a b c d t u v a b c d R 2 getReg() выдает R 3 для R c и R 1 для R u u помещается на R 1 , так какзначение а , ранее располагавшееся на R 1 , больше внутри блока не используется Генерация кода для базового блока: 1 t -, a, b 2 u -, a, c 3 v +, t, u 4 a d 5 d +, v, u 13.2 Локальное распределение регистров 13.2.4 Пример t , u , v – временные переменные, локальные для блока, а , b , с , d – переменные, живые при выходе из блока. R 1 R 2 R 3 u a, d v a b c d t u v a b c d, R 2 R 1 R 3 LD R2, d R 1 R 2 R 3 u t v a b c d t u v a b c d R 2 R 1 R 3 getReg() выдает R 2 для R d Для инструкции копирования 4: a = d необходимо сгенерировать одну команду: загрузка регистра R d В регистре R 2 теперь хранятся и d , и а Генерация кода для базового блока: 1 t -, a, b 2 u -, a, c 3 v +, t, u 4 a d 5 d +, v, u 13.2 Локальное распределение регистров 13.2.4 Пример t , u , v – временные переменные, локальные для блока, а , b , с , d – переменные, живые при выходе из блока. R 1 R 2 R 3 u a, d v a b c d t u v a b c d, R 2 R 1 R 3 ADD R1, R3, R1 R 1 R 2 R 3 d a v a b c d t u v R 2 b c R 1 R 3 getReg() выдает R 1 для R d Для инструкции 5: d = v + u необходимо сгенерировать одну команду: сложение, результат на регистр R d После этой команды d хранится только на R 1 , но не в ячейке памяти для d a хранится только на R 2 , но не в ячейке памяти для a Генерация кода для базового блока: 1 t -, a, b 2 u -, a, c 3 v +, t, u 4 a d 5 d +, v, u 13.2 Локальное распределение регистров 13.2.4 Пример t , u , v – временные переменные, локальные для блока, а , b , с , d – переменные, живые при выходе из блока. R 1 R 2 R 3 d a v a b c d t u v a, R 2 b c d, R 1 R 3 ST a, R2 ST d, R1 R 1 R 2 R 3 d a v a b c d t u v R 2 b c R 1 R 3 В заключение необходимо сохранить живые переменные a и d , значения которых есть только на регистрах Генерация кода для базового блока: 1 t -, a, b 2 u -, a, c 3 v +, t, u 4 a d 5 d +, v, u 13.2 Локальное распределение регистров |