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


 

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

46646. Методика изучения темы «ПЗ, ПС химических элементов Д.И. Менделеева» 24.04 KB
  элтов это не только один из важнейших законов природы это и методическая основа изучения химии. средство изучения химии.время любой систематический курс химии имеет в своей основе ПЗ. В программе по химии приводятся требования к знаниям относящиеся к образовательной стороне обучения.
46647. Исламская республика 24.33 KB
  Политические партии. Это партии входившие в Национальный фронт партии марксистского типа а также партии использовавшие исламские лозунги. Активное участие в свержении шахского режима приняли такие левые партии как Организация моджахедов иранского народа Моджахедине Хальк Организация партизанфедаев Федаяне хальк иранского народа Народная партия Ирана Туде. Поддержали революцию некоторые буржуазнодемократические партии Национального фронта члены которых вошли в состав Временного революционного правительства партия Движение за...
46648. Сжимаемость, температурное расширение, испаряемость 24.34 KB
  Сжимаемость свойство вещества изменять свой объём при изменении внешнего давления или другими словами при изменении напряжений в веществе. Если давление в гидросистеме не превышает давления на которое настроен вспомогательный клапан последний закрыт давления в торцовых полостях переливного золотника 5 одинаковы и золотник прижат пружиной 9 к своему конусному седлу вследствие этого напорная и сливная линии разъединены. Изза потери давления в малом отверстии 7 давление в полости 10 уменьшится и золотник 5 переместится вверх сжимая...
46649. Методы и средства обеспечения безопасности установок и систем повышенной опасности 24.43 KB
  Методы и средства обеспечения безопасности установок и систем повышенной опасности. Основные методы обеспечения безопасности установок. Госгортехнадзор РФ утверждает обязательные для предприятий организаций и АО далее предприятий всех форм собственности межотраслевые правила по устройству и безопасной эксплуатации этих установок [19. В них содержатся требования безопасности которые должны быть выполнены как при проектировании и изготовлении так и при монтаже эксплуатации и ремонте данных установок.
46650. Дополнительное профессиональное образование 24.45 KB
  Представляет собой систему средств обеспечивающих прогностическую оценку взаимосоответствия человека и профессии в тех видах деятельности которые осуществляются в нормативно заданных опасных условиях гигиенических микроклиматических технических социальнопсихологических требующих от человека повышенной ответственности здоровья высокой работоспособности и точности исполнения задания устойчивой эмоциональноволевой регуляции. Вот почему на каждом уроке как правило учителя дают учащимся домашние задания. Обычно эти задания включают в...
46651. Статус української мови як державної 24.5 KB
  Українська мова в Україні має статус державної. Це закріплено у десятій статті Конституції України. Державна мова - мова, яка користується у конкретній державі законодавчим статусом обов'язкової для вживання в офіційних сферах життя. Державна мова обслуговує державні і суспільні органи, організації, заклади культури і освіти. Вона повинна побутувати у всіх сферах життя