20622

Базовые блоки

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

Говорят что трехадресная инструкция вида определяет x и использует y и z. Выход: список базовых блоков такой что каждая трех адресная инструкция принадлежит только одному блоку. Правила: первая инструкция является лидером. любая инструкция являющаяся целевой инструкцией условного или безусловного переходов является лидером.

Русский

2013-07-31

111.5 KB

1 чел.

Лекция №9

Базовые блоки

Базовым блоком называется последовательность смежных инструкций, в которую поток управления входит в начале и выходит в конце без останова программы или возможности ветвления.

Говорят, что трехадресная инструкция вида  определяет x и использует y и z.

Имя в базовом блоке называется живым в данной точке, если его значение используется в программе после этой точки даже в другом базовом блоке.

Алгоритм разбиения потока на базовые блоки

Вход: последовательность трех адресных инструкций.

Выход: список базовых блоков такой, что каждая трех адресная инструкция принадлежит только одному блоку.

Правила:

  1.  первая инструкция является лидером.
  2.  любая инструкция, являющаяся целевой инструкцией условного или безусловного переходов является лидером.
  3.  любая инструкция, следующая за условным или безусловным переходом, является лидером.
  4.  базовый блок для каждого лидера состоит из него самого до следующего лидера, не включая его, или до конца программы.

Пример: скалярное произведение трех векторов.

begin

prod:=0;

i:=1;

repeat

prod:=prod+a[i]*b[i];

i:=i+1;

until(i>20);

end

Последовательность трехадресных инструкций:

Оптимизация внутри базовых блоков

  1.  Устранение общих подвыражений.

  1.  Устранение мертвого кода

мертвый код - инструкции являющейся элементом базового блока, но нигде не использующегося.

  1.  Переименование временных переменных

, t – временная переменная.

Если заменить имя одной временной переменной на имя другой временной переменной, при этом базовый блок не изменит своего смысла. Если такое преобразование возможно, такой базовый блок называется блоком нормального вида, тогда в дальнейшем это может позволить применить другие методы оптимизации.

  1.  Перестановка инструкций:

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

  1.  Арифметические преобразования.

Графы потоков управления

Узлами графа потоков являются базовые блоки. Графы потоков содержат информацию о потоке управления. Один из узлов графа определяется как стартовый. Направленная дуга графа потока от блока В1 к блоку В2 может быть построена, если блок В2 непосредственно следует за блоком В1 в потоке управления. Это реализуется в 2-х случаях:

  1.  имеется условный или безусловный переход от последней инструкции блока В1 к первой инструкции блока  В2 .
  2.  блок В2 следует за блоком В1, при этом В1 не должен заканчиваться инструкцией безусловного перехода.

В1 – называется предшественником В2

В2 – называется приемником В1.

Сбор информация о последующем использовании имен в базовых блоках

Алгоритм вычисления последующих использований

Пусть трехадресная инструкция с номером i присваивает значение переменной x. Если инструкция с номером j содержит x в качестве операнда и управление может перейти от i к j таким путем, на котором не меняется значение x, говорят, что j использует значение x, вычисленное в i. Сканирование на предмет последующих использований, происходит от конца базового блока к началу с запоминанием в таблице символов для каждого имени x, используется оно или нет.

Пример 1: Представить в виде последовательности трехадресных инструкций и оптимизировать.

x:=(a*(-b))+(c-(d+e))

t1:=d+e

t1:=c-t1

t2:=-b

t2:=t2*a

t1:=t1+t2

x:=t1

t1:=d+e

t1:=c-t1

t2:=-b

t2:=t2*a

x:=t1+t2


 

А также другие работы, которые могут Вас заинтересовать

36751. Изучение вращательного движения на маховике Обербека 107.5 KB
  Если на тело, закрепленное на неподвижной оси, действует сила, то тело приобретает угловое ускорение, направленное вдоль этой оси. Величина ускорения зависит не только от величины и направления силы, но и от точки ее приложения. Это отражено в понятии момента силы, который как и сила является векторной величиной. В случае вращения вокруг неподвижной оси угловое ускорение, направленное вдоль этой оси, определяется результирующей проекцией моментов всех сил на эту ось.
36753. Сведения о некоторых командах ОС UNIX 121.5 KB
  Команды поступающие от пользователей называют заданиями чтобы отличить их от системных процессов. Перевод процесса в фоновый режим Если вы запускаете какойто процесс путем запуска программы из командной строки то обычно процесс запускается как говорят на переднем плане . Это значит что процесс привязывается к терминалу с которого он запущен воспринимая ввод с этого терминала и осуществляя на него вывод.
36754. Форматирование таблиц 309 KB
  Вставка таблицы с помощью панели инструментов Рис. Окно Вставка таблицы Вы сами можете выбрать каким способом создавать таблицу: при помощи меню ТаблицаДобавить таблицу. указав в соответствующих полях ввода число строк и столбцов создаваемой таблицы или можно воспользоваться соответствующей кнопкой Добавить таблицу панели инструментов Нажав кнопку выделите не отпуская клавиши мыши нужное число ячеек в раскрывающемся поле рис. Первый способ создания таблицы удобно использовать если размеры таблицы превышают 5 столбцов...
36756. Определение главного фокусного расстояния тонких линз 212.5 KB
  Приборы и принадлежности: оптическая скамья с набором рейтеров осветитель с источником питания экран собирающая и рассеивающая линзы. Ее вершины и в этом случае можно считать совпадающими в точке называемой оптическим центром линзы. Причем ось проходящая через оптический центр линзы и центры кривизны ее преломляющих поверхностей называется главной оптической осью линзы. Если направить луч света параллельно главной оптической оси вблизи нее то преломившись он пройдет через точки или в зависимости от того слева или...
36757. Получение и исследование света с различными состояниями поляризации 230.5 KB
  Цель работы: изучить методы получения и анализа света с различными состояниями поляризации, сформулировать гипотезу исследования, установить связи между основными способами получения поляризованного излучения, выделить существующие различия между ними, определить этапы исследования.
36758. Определение постоянного Планка спектрометрическим методом 115.5 KB
  Цель работы: сформулировать гипотезу исследования по уровням сложности, проанализировать метод исследования спектра, исследовать спектр излучения атома водорода в видимой области спектра (серия Бальмера), определить постоянные Ридберга и Планка, объяснить методику их определения, выяснить, как соотносится сплошной и линейчатый спектры атома водорода.
36759. Система дистанционной поддержки в вузе (на примере центра дистанционной поддержки обучения РГПУ им. А. И. Герцена) 43.5 KB
  Сколько метакурсов предлагается в данном разделе Какие значки используются для обозначения метакурсов которые можно посетить: а без кодового слова б только по кодовому слову Откройте метакурс Демонстрация возможностей Moodle. Перечислите модули метакурса Демонстрация возможностей Moodle. Задание №3 Порядок выполнения: Выберите модуль Основные возможности метакурса Демонстрация возможностей Moodle.