А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 128
Текст из файла (страница 128)
8.2, в которых единственным отличием между последовательностями а и б является оператор во второй инструкции. Кратчайшие последовательности ассемблерных кодов для а и б приведены на рис. 8.3. Ь=а+Ь Ь с б Ь = а+ т. = г * г. = т. / а) + с / б б) Рис. 8.2. Две последовательности трехадресных кодов а) Рис. 8.3. Оптимальные последовательности машинных кодов Аа означает г-й регистр; ЯВОА — сдвиг вправо (ЯЫй-Ы8)Н-)ЗоиЫе-Апштенс); команда ЯВЭА ВО, 32 сдвигает делимое в В1 н очищает ВО, делая все биты равными его знаковому биту. Команды Ь, БТ и А означают соответственно загрузку в регистр, сохранение регистра и суммирование.
Заметим, что оптимальный выбор регистра для загрузки а зависит от того, что в конечном счете произойдет с Ь. о Стратегии распределения регистров рассматриваются в разделе 8.8. В разделе 8.! О показано, что для некоторых классов машин можно построить последова- Ь В1, а А Н1, Ь М йО, с О ВО, с) БТ В1, А А ЯВОА 0 ЯТ ВО, а ВО, Ъ ВО, с йО, 32 ВО, с1 В1, б) 625 8.2. Целевой язык тельности кодов, которые будут выполнять вычисление выражения с использова- нием минимально возможного количества регистров. 8.1.5 Порядок вычислений Порядок, в котором выполняются вычисления, также может существенно влиять на эффективность целевого кода.
Как мы увидим, изменение порядка вычислений может привести к уменьшению количества регистров, необходимых для хранения промежуточных результатов. Однако в общем случае выбор оптимального порядка вычислений представляет собой сложную ХР-полную задачу. Вначале мы избежим этой задачи, генерируя целевой код для трехадресных инструкций в том порядке, в каком они были созданы генератором промежуточного кода. В главе 10 будет рассмотрено планирование кода для конвейерных машин, которые способны выполнять несколько операций за один такт. 8.2 Целевой язык Одним из непременных требований к построению хорошего генератора кода является близкое знакомство с целевой машиной и ее набором инструкций. К сожалению, при обсуждении общих вопросов генерации кода невозможно описать нюансы той или иной целевой машины достаточно подробно, чтобы иметь возможность генерировать для нее хороший код.
В этой главе в качестве целевого языка мы используем ассемблерный код для простого компьютера, являющегося типичным представителем множества регистровых машин. Однако рассматриваемые здесь методы генерации кода применимы и к множеству других классов машин. 8.2.1 Простая модель целевой машины Модель нашего целевого компьютера представляет собой трехадресную машину с операциями загрузки и сохранения регистров, вычислительными операциями, условными и безусловными переходами.
Компьютер представляет собой машину с байтовой адресацией памяти с и регистрами общего назначения ВО, Л1,..., Лц — 1. Полнофункциональный язык ассемблера должен иметь множество команд. Чтобы не потерять базовые концепции за мириадами несущественных деталей, мы будем использовать очень ограниченное множество команд и считать, что все операнды представляют собой целые числа. Большинство команд состоит из оператора, за которым следуют приемник и список исходных операндов.
Команде может предшествовать метка. Предполагается, что имеются команды следующих видов. Глава 8. Генерация кола 626 ° Операции загрузки. Команда ВВ Ызд а~И» загружает значение из ячейки памяти асИ» в ~Ы Эта команда описывает присваивание Ызг = а<И». Наиболее распространенной формой этой команды является ВВ т, х, которая загружает значение из ячейки памяти х в регистр т. Команда вида ВВ т,, тз представляет собой копирование, при котором содержимое регистра тз копируется в регистр тп ° Операция сохранения. Команда ЯТ х, т сохраняет значение из регистра т в ячейке памяти х.
Эта команда описывает присваивание х = т.. ° Вычисли»пвльные операции вида ОР дздз»сыз»сз, где ОР— оператор наподобие АВВ или Я0В, а аЫ, з»с1 и з»сз — местоположения данных, не обязательно различные. Результат выполнения команды состоит в применении операции ОР к значениям в местоположениях з»с1 и з»сз и помещении результата в сЫ Например„команда Я1)В ты тз, тз вычисляет »1 = тз — тз. Любое значение, ранее хранившееся в»ы теряется, но если т1 совпадает с тз или тз, то сперва считывается старое значение. Унарная операция, принимающая только один операнд, не имеет операнда втсз.
° Безусловные переходы. Команда ВВ Б приводит к передаче управления машинной команде с меткой Б (ВВ означает "Ьгапсй" — "переход"). ° Условные переходы вида Всопг)», Е, где т — регистр, Б — метка, а вопд означает одну из обычных проверок значения в регистре т. Например, В1ТЯ», Б приводит к переходу к метке Б, если значение в регистре т меньше нуля; в противном случае управление передается очередной машинной команде.
Наша целевая машина имеет несколько режимов адресации. ° В командах адрес может быть именем переменной х, что означает место в памяти, зарезервированное для х (т.е. для (-значения х). ° Адрес може~ быль индексированным адресом вида а(т), где и — переменная, а т — регистр. Адрес а(т) вычисляется путем прибавления к )- значению а значения из регистра т. Например, команда ВВ В1, а(В2) выполняет присваивание Л1 = сангели (а + сон~ел»в (В2)), где соп~епгв(х) означает содержимое регистра или ячейки памяти, представленной х. Этот режим адресации полезен для обращения к массивам, когда а представляет собой базовый адрес массива (т.е.
адрес его первого элемента), а в т хранится количество байтов после этого адреса, которые надо пропустить, чтобы обратиться к некоторому элементу массива а. 627 8.2. Целевой язык в Адрес может быть индексирован регистром. Например, команда ВР В1, 100 (82) выполняет присваивание В1 = сошепм (100+ сопиевы (В2)), те. в регистр В1 загружается значение из ячейки памяти, адрес которой получается путем прибавления 100 к содержимому регистра В2.
Эта адресация полезна при следовании по указателям, как будет видно в приведенном далее примере. ° Целевая машина допускает два режима косвенной адресации: *г означает ячейку памяти, находящуюся по адресу, представленному содержимым регистра г, а *100 (г) означает ячейку памяти, находящуюся по адресу, полученному путем прибавления 100 к содержимому г. Например, команда ВР В1, *100 (В2) выполняет присваивание Р1 = сопгепгз(сопРепгз(100+ + сопГепж(В2))), т.е. в регистр В1 загружается значение ячейки памяти, адрес которой хранится в ячейке памяти по адресу, равному 100 плюс содержимое регистра В2. ° Наконец, имеется режим адресации с использованием констант (для указания которых используется префикс ()).
Команда БВ В1, ()100 загружает в регистр 81 целое число 100, а ЛВР В1, В1, ()100 прибавляет 100 к регистру В1. Комментарии располагаются после команд и начинаются с символов //. Пример 8.2. Трехадресная инструкция х = у — г может быть реализована ма- шинными командами // В1 = у // В2 // В1 = В1 — В2 // х = В1 В1, у 10 В2, г ЯУВ 81, В1, 82 Вт х, К1 Однако, вероятно, код можно улучшить. Одна из целей хорошего алгоритма генерации кода — по возможности избежать использования как можно большего количества команд. Например, у и!или г могут быть вычислены в регистрах, и это позволит обойтись без команд загрузки ЬВ.
Точно так же можно обойтись без команды сохранения, если значение х используется в дальнейших вычислениях в регистре и больше в программе не потребуется. Предположим, что а — массив, элементы которого представляют собой 8- байтные значения, скажем, числа с плавающей точкой. Будем также считать, что элементы массива индексируются начиная с нулевого значения. Трехадресная команда Ь = а(11 может быть выполнена при помощи следующих машинных команд: 628 Глава 8.
Генерация кода На втором шаге вычисляется 8(, а на третьем в регистр Р2 загружается значение (-го элемента а, который находится на расстоянии 81 байт от базового адреса массива а. Аналогично присваивание элементу массива а, представленное трехадресной командой а ( З ) = с, реализуется такой последовательностью машинных команд: Для реализации простого косвенного обращения с использованием указателя, такого как трехадресная инструкция х = *р, можно использовать машинные команды Присваивание с использованием указателя *р = у реализуется аналогичными командами Наконец, рассмотрим трехадресную команду условного перехода наподобие 1Т х < у добро 1 Эквивалентный машинный код будет выглядеть примерно так: Здесь М вЂ” метка, представляющая первую машинную команду, сгенерированную трехадресной командой с меткой В.
Как и в случае любой трехадресной команды, мы надеемся, что сможем сэкономить несколько машинных команд за счет того, что необходимые операнды уже находятся в регистрах или что сохранение результатов не потребуется. и ВВ Р1, МШ Р,1, Р1, 8 1.0 Р2, а(Р1) ЯТ Ь, Р2 1.0 Р1, с 1.0 Р2, з МШ Р2, Р2, 8 ЯТ а(Р2), Р1 10 Р1, р ВВ Р2, 0(Р1) ЯТ х, Р2 10 Р1, р 1,() Рг, у ЯТ 0(Р1), Р2 10 Р1, х 1.0 Рг, у ЯУВ Р1, Р.1, Р2 В1ТЕ Р1, М // Р1 // Р1 = Р1 * 8 // Р2 = соптепсз(а+соптепсз(Р1)) // Ь = Р2 // Р1 = с // Р2 // Р2 = Р2 * 8 // сопСепсз(а+соптептз(Р2)) = Р1 // Р1 = р // Р2 = соптептз(0+соптеп~з(Р1)) // х = Р2 // Р1 = р // Рг = у // соптепТз(0+соптепсз(Р1)) = Р2 // Р1 = х //Р2=у // Р,1 = Р1 — Р2 // Если Р1 < О, переход к М 629 8.2.
Целевой язык 8.2.2 Стоимость программ и команд Мы часто связываем стоимость с компиляцией и выполнением программ. В зависимости от того, оптимизация какого именно аспекта программы нас интересует, наиболее распространенными мерами стоимости являются продолжительность компиляции, размер целевой программы и время ее работы. Определение фактической стоимости компиляции и работы программы представляет собой сложную задачу.
Поиск оптимальной целевой программы для данной исходной в общем случае — задача неразрешимая, а многие ее подзадачи МР- сложные. Как уже говорилось, при генерации кода приходится удовлетворяться эвристическими методами, которые дают хорошие, но не обязательно оптимальные целевые программы. В оставшейся части этой главы мы считаем, что каждая команда целевого языка имеет связанную с ней стоимость. Для простоты будем считать стоимость равной единице плюс стоимости, связанные с режимами адресации операндов. Такая стоимость соответствует длине команды в словах.
Режимы адресации с использованием регистров имеют нулевую стоимость, а режимы с использованием ячеек памяти или констант — дополнительную стоимость, равную единице, поскольку такие операнды хранятся в словах, следующих за командой. Вот некоторые примеры. ° Команда 1,0 ВО, В1 копирует содержимое регистра В1 в регистр ВО. Стоимость этой команды равна единице, поскольку для нее не требуются никакие дополнительные слова памяти. ° Команда ЪО ВО, М загружает содержимое ячейки памяти М в регистр ВО.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
