Лекция 07. Выбор команд (1157465), страница 3

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

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

отсутствуютобщие подвыражения)(2)количество доступных регистров r  2Выход: оптимальная последовательность машинных команддля вычисления значения корня дерева на регистре сиспользованием не более, чем r регистров(регистры R1, R2, ..., Rr)Метод: рекурсивный алгоритм генерации машинного кода497.6 Генерация оптимального кода для выражений7.6.4Вычисление выражений при недостаточном количестверегистровАлгоритм генерации кода для размеченного деревавыражения (с учетом конечного числа доступных регистров)Метод: рекурсивный алгоритм генерации машинного кодаПусть k – метка корня рассматриваемого дерева N.Если k  r, алгоритм совпадает с алгоритмом 7.6.2Если k > r, каждое поддерево обрабатывается отдельно,и результат большого поддерева (оно обрабатываетсяпервым) сохраняется в памяти.

Непосредственно передвычислением корня N этот результат загружается изпамяти на регистр Rr и используется вместе срезультатом маленького поддерева (полученного нарегистре Rr-1) для вычисления результата корня N (нарегистре Rr).507.6 Генерация оптимального кода для выражений7.6.4Вычисление выражений при недостаточном количестверегистровМетод(1)Выбор большого узла: Узел N имеет как минимум одиндочерний узел с меткой  r. Дочерний узел с большейметкой выбирается как «большой» , а узел с меньшейметкой – как «маленький».Если метки обоих узлов одинаковы, то в качестве«большого» берется правый дочерний узел.(2)Рекурсивная генерация кода для большого дочернегоузла с использованием регистров R1, R2, … , Rr.

Результатвычислений получается на регистре Rr.(3)Генерация команды ST tk Rr, где tk – временнаяпеременная, используемая для вычисления узлов сметкой k.517.6 Генерация оптимального кода для выражений7.6.4Вычисление выражений при недостаточном количестверегистровМетод(4)Рекурсивная генерация кода для маленького дочернегоузла с использованием регистров Rr-j, Rr-j+1, … , Rr,где j  r – метка маленького узла. Результат вычисленийполучается на регистре Rr.(5)Генерация команды LD Rr-1 tk.(6)Генерация команды OP Rr Rr Rr-1, если большой узелявляется правым дочерним узлом корня N,либо команды OP Rr Rr-1 Rr, если большой узелявляется левым дочерним узлом корня N.527.6 Генерация оптимального кода для выражений7.6.5ПримерПрименим алгоритм 7.6.4 к дереву на рисунке, в предположении,что количество доступных регистров равно 2 (r = 2), т.е.

дляхранения временных значений при вычислении выраженияможно использовать только два регистра – R1 и R2.Корень дерева имеет метку 3, большую, чем r = 2.Согласно п. (1) алгоритма 7.6.4 выбирается большой узел.Так как у обоих дочерних узлов метки одинаковы, выбираетсяправый узел.537.6 Генерация оптимального кода для выражений7.6.5ПримерРекурсивная генерация кода для поддерева с корнем t3выполняется алгоритмом 7.6.2, так как метка t3 равна 2, т.е.регистров для его вычисления достаточно.Результат похож на результат примера 7.6.3, но вместо регистровR2 и R3 используются регистры R1 и R2 :LDLDADDLDMULR2R1R2R1R2dcR1 R2eR1 R2547.6 Генерация оптимального кода для выражений7.6.5ПримерПоскольку длявычисления левогодочернего узла корнянужны оба регистра,генерируетсякомандаST t3 R2Для левого дочернего узла регистров хватает для вычислений,так что алгоритмом 7.6.2 генерируется кодLD R2 bLD R1 aSUB R2 R1 R2На регистре R1 восстанавливается значение правого поддеревакомандой LD R1 t3Выполняется операция в корне дерева командойADD R2 R2 R1557.6 Генерация оптимального кода для выражений7.6.5ПримерВ результате для дерева нарисунке генерируется код:LDLDADDLDMULSTLDLDSUBLDADDR2RlR2RlR2t3R2RlR2RlR2dсRleRlR2baRlt3R2R2R2R2RlКоторый вычисляет дерево,используя только два регистра567.7Генерация кода алгоритмомдинамического программирования7.7.1Постановка задачиАлгоритм 7.6.4 генерирует оптимальный код по деревувыражения за время, линейно зависящее от размера дерева.Этот алгоритм работает для машин, у которых все вычислениявыполняются в регистрах, а команды состоят из операторов,применяемых к двум регистрам или к регистру и ячейке памяти.Для расширения класса машин, для которых возможнопостроение оптимального кода на основе деревьев выраженийза линейно зависящее от размера дерева время, можновоспользоваться алгоритмом на основе динамическогопрограммирования.Алгоритм динамического программирования можетиспользоваться для генерации кода для любой машины с rвзаимозаменяемыми регистрами R0, R1, ..., R(r–1) и командамизагрузки, сохранения и операций.Для простоты сделано предположение, что все команды имеютодинаковую стоимость, равную единице, хотя алгоритм динамическогопрограммирования можно легко модифицировать для случая, когда57стоимости команд различны.7.77.7.1Генерация кода алгоритмомдинамического программированияПостановка задачиАлгоритм динамического программирования – это эвристика,которая состоит в разбиении сложной задачи на подзадачианалогичной структуры и поиске оптимального решения длякаждой подзадачи: предполагается, что каждая подзадача прощеосновной задачи, и ее оптимальное решение найти проще.Генерация оптимального кода для выражения сводится кгенерации оптимального кода для подвыражений этоговыражения и последующей генерации кода для выраженияв целом.Рассмотрим выражение Е вида Е1 ор Е2.Алгоритм динамическогопрограммирования составляетоптимальную программу для Е, выбираяоптимальный порядок выполнения программдля вычисления Е1 и Е2, и помещая вслед за ними код длявыполнения операции ор.Подзадачи генерации оптимального кода для вычисления58подвыражений Е1 и Е2 решаются аналогично.7.7Генерация кода алгоритмомдинамического программирования7.7.2Последовательные вычисленияПо определению программа Р вычисляет дерево Тпоследовательно, если она вначале вычисляет поддеревья Т1 иТ2 дерева Т (Т либо в порядке Т1, Т2 и затем корень, либо впорядке Т2, Т1 ) и запоминает их значения в памяти.

Затем Рвычисляет корень.При необходимости используются предварительновычисленные значения, хранящиеся в памяти.Утверждение. В случае регистровой машины для любойпрограммы P, вычисляющей дерево выражения Т, можно найтиэквивалентную программу P', такую, чтостоимость P' не больше стоимости Р;P' использует не больше регистров, чем Р;P' вычисляет дерево последовательно.Следствие. Каждое дерево выражения можно вычислитьоптимальным образом с помощью последовательнойпрограммы.597.7Генерация кода алгоритмомдинамического программирования7.7.2Последовательные вычисленияОптимальная программа, порожденная алгоритмомдинамического программирования, имеет важное свойство,заключающееся в том, что она вычисляет выражениеЕ = Е1 ор Е2 «последовательно».Синтаксическое дерево Т для выражения Е.Т1 и Т2 – синтаксические деревья для Е1 и Е2 соответственно.607.7Генерация кода алгоритмомдинамического программирования7.7.3Алгоритм динамического программированияАлгоритм динамического программирования состоит из трех фаз.(1)В восходящем порядке для каждого узла n деревавыражения Т вычисляется массив стоимости С, i-йэлемент которого С[i] представляет собой оптимальнуюстоимость вычисления поддерева S с корнем n с приусловии, что для вычисления имеется i (1  i  r)доступных регистров(r – число регистров целевой машины)(2)Обход дерева выражения Т с использованием векторовстоимости для определения, какие из поддеревьев Тдолжны быть вычислены в память.(3)Обход каждого дерева с использованием векторовстоимости и связанных с ними команд для генерацииконечного целевого кода.

Первым генерируется код дляподдеревьев, вычисляемых в память.Каждая из фаз может быть выполнена за время, линейно61пропорциональное размеру дерева выражения.7.7Генерация кода алгоритмомдинамического программирования7.7.3Алгоритм динамического программированияСтоимость вычисления узла n включает загрузки и сохранения,необходимые для вычисления S с данным количествомрегистров и стоимость выполнения операции в корне S.Нулевой компонент вектора стоимости – оптимальная стоимостьвычисления поддерева S с сохранением результата в памяти.Свойство последовательного вычисления гарантирует, чтооптимальная программа для вычисления поддерева S можетбыть сгенерирована путем рассмотрения комбинаций толькооптимальных программ для поддеревьев дерева с корнем S.Сформулированное ограничение сокращает количество случаев,которые необходимо рассмотреть.627.7Генерация кода алгоритмомдинамического программирования7.7.3Алгоритм динамического программированияДля вычисления стоимости С[i] в узле n будем рассматриватькоманды как правила преобразования дерева.Для каждого шаблона Е, соответствующего входному дереву вузле n:Изучая векторы стоимости соответствующих наследниковn, определить стоимости вычисления операндов влистьях Е.Для операндов Е, являющихся регистрами, рассмотретьвсе возможные порядки вычисления поддеревьев Т врегистры.Для каждого из рассматриваемых порядков вычисленияпервое поддерево, соответствующее регистровомуоперанду, можно вычислить с использованием iдоступных регистров, второе – с помощью i – 1 доступныхрегистров и т.д.Добавить стоимость команды, связанной с корнем Е.Значение С[i] представляет собой минимальную63стоимость среди всех возможных порядков вычисления.7.7Генерация кода алгоритмомдинамического программирования7.7.3Алгоритм динамического программированияВекторы стоимости для всего дерева Т могут быть вычислены ввосходящем порядке (снизу вверх) за линейное время.

Команды,соответствующие наилучшей стоимости С[i] для каждогозначения i, удобно хранить в узлах дерева; при этом наименьшаястоимость корневого узла Т соответствует минимальнойстоимости вычисления дерева Т.647.7Генерация кода алгоритмомдинамического программирования7.7.4ПримерПусть машина имеет два регистра R0 и R1 и следующие команды,стоимость каждой из которых равна единице:КомандаСемантика командыLD Ri, MjRi = Mjop Ri, Ri, RjRi = Ri op Rjop Ri, Ri, MjRi = Ri op MjLD Ri, RjRi = R jST Mi, RjMi = R jRi представляет собой либо R0, либо R1, a Mj – адрес в памяти.Значок ор соответствует знаку арифметической операции.657.7Генерация кода алгоритмомдинамического программирования7.7.4 Пример Применим алгоритм динамического программирования для генерацииоптимального кода для синтаксического дерева (см.

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

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