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


 

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

11171. Сутність розкриття інформації в акціонерному товаристві 70.5 KB
  Сутність розкриття інформації в акціонерному товаристві. Сутність розкриття інформації акціонерними товариствами полягає у забезпеченні доступу зацікавлених осіб у тому числі акціонерів до повної достовірної інформації про виробничогосподарську діяльність підпр...
11172. Фінансові посередники в системі корпоративного управління 77.5 KB
  Тема 10. Фінансові посередники в системі корпоративного управління 10.1. Суть фінансового посередництва i його функції Світова практика свідчить про надзвичайно велику роль фінансових посередників у системі корпоративного управління Значну роль у корпоративному сект...
11173. Форми і функції державного регулювання 52.5 KB
  Форми і функції державного регулювання Одним з найважливіших елементів сфери корпоративного управління є його нормативноправове забезпечення. Загалом державне регулювання як один з напрямків корпоративного управління виходить за рамки безпосереднього управління...
11174. Виконання та захист графічних робіт. Виконання ескізу деталі з натури 27 KB
  Тема 6: Виконання та захист графічних робіт. Виконання ескізу деталі з натури. Мета: Навчальна: сформувати знання вміння та навички поданій темі. Виховна: виховувати в учнів культуру праці та акуратність. Розвиваюча: розвивати у школярів спеціальні здібності і техн
11175. Будова та класифікація різців. Режими різання 80.5 KB
  Тема. Будова та класифікація різців. Режими різання. Мета: ознайомити учнів з видами різців для виконання токарних робіт по металу; навчити вибирати різці для певного виду робіт; виховувати бережливе ставлення до обладнання та інструментів; розвивати логічне мислення
11176. Контрольно-вимірювальний інструмент 69.5 KB
  Тема 9: Контрольновимірювальний інструмент. Мета: виявити рівень теоретичних знань з розділу проектування виробів; ознайомити з контрольновимірювальними інструментами та навчити користуватися ними; первинний інструктаж з охорони праці під час виконання сл
11177. Технологічний процес виготовлення проектованого виробу. Розробка ескізу та технологічної послідовності виготовлення виробу 30.38 KB
  Тема. Технологічний процес виготовлення проектованого виробу. Розробка ескізу та технологічної послідовності виготовлення виробу . Мета: згідно теми проекту вибрати аналогпрототип та вдосконалити його характеристики; виховувати бережливе ставлення до обладнання
11178. Опоряджувальні роботи. Правила техніки безпеки. Лакування та фарбування, інкрустація та інтарсія 55.5 KB
  Тема: Опоряджувальні роботи. Правила техніки безпеки. Лакування та фарбування інкрустація та інтарсія. Мета. Ознайомити учнів з прийомами оздоблення деревяних виробів формувати в учнів поняття про техніку інтарсія та маркетрі; виховання позитивного ставлення до прац...
11179. Пошук необхідної інформації для проекту. Методи проектування (метод фокальних об’єктів).Практична робота: Складання ескізу проектного виробу 41 KB
  Тема уроку: Пошук необхідної інформації для проекту. Методи проектування метод фокальних об’єктів.Практична робота: Складання ескізу проектного виробу. Мета: згідно теми проекту вибрати аналогпрототип та вдосконалити його характеристики; виховувати бережливе ставл...