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


 

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

57925. Води суходолу Північної Америки. Основні річкові системи. Великі озера, їх походження 69 KB
  Мета: сформувати в учнів систему знань про внутрішні води Північної Америки розкрити загальні особливості вод суходолу показати їх залежність від рельєфу та клімату нерівномірність розподілу на території материка...
57926. Основы объектно-ориентированного программирования. Создание формы 573.5 KB
  Цель: Сформировать у учащихся представление о среде программирования Visul Studio; освоить основные приемы создания форм получить практические навыки создания формы в среде программирования; формировать у учащихся информационную компетентность.
57927. Клітинний цикл. Мітоз 62.5 KB
  Німецький вчений Рудольф Вірхов стверджував що клітина може виникнути тільки з попередньої клітини в результаті її поділу. Відома його знаменита фраза усяка клітина з клітини З таким поняттям як поділ клітини ви вже неодноразово зустрічались на уроках біології.
57928. Створення програм з використанням оператора циклу з параметром 140 KB
  Після цього уроку ви зможете: використовувати оператор циклу з параметром для створення програм обчислення суми та добутку скінченої кількості чисел знаходження кількості елементів з певними властивостями; наводити особливості накопичення суми та...
57929. Снежная книга Зимы 214.5 KB
  Цель: обобщить представления детей о зиме, познакомить с новыми рассказами и стихотворениями о зиме; продолжить работу над техникой чтения. Воспитывать любовь к родному слову, бережное отношение к природе.
57930. Цитологія – наука про будову і функції клітини. Історія вивчення клітини. Методи цитологічних досліджень 356 KB
  Мета: сформувати основні положення клітинної теоріїрозширити уявлення про історію вивчення клітини розкрити основні методи цитологічних досліджень; розвивати критичне і логічне мислення удосконалювати творчі здібності вміння...
57931. Зорі. Еволюція зір 340 KB
  І почнемо ми з вами саме з визначення найголовнішого небесного світила зорі. учні дають визначення зорі Вчені прийшли до висновку що зорі включаючи і наше Сонце мають життєві цикли. Ці стадії різні оскільки зорі складаються з різних елементів і відрізняються розмірами.
57932. Зажурилась зимонька не дарма, молодої силоньки вже нема 62.5 KB
  Мета: познайомити з традиціями святкування Стрітення, прикметами, які з ним пов’язані; формувати навички виразного читання віршів; підтримувати у дітей інтерес до занять фізкультурою, привчати дітей грати в командних іграх-естафетах...
57933. За О. Цегельською. Пригода на ковзанці. Безпечний відпочинок взимку 75.5 KB
  Мета: познайомити з оповіданням О. Цегельської; формувати вміння читати, зв’язно розповідати; розширювати знання учнів про зимові розваги; закріпити знання правил про поведінку на льоду, показати, яку небезпеку може приховувати вода; розвивати пам’ять, увагу, мислення, пізнавальний інтерес...