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


 

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

80003. Задачи IV соросовской олимпиады по математике для 6 - 11 классов 1.94 MB
  В последнее десятилетие широкую известность получили так называемые соросовские олимпиады, проводимые под эгидой фонда Сороса. Уровень этих олимпиад весьма высок и успех на них возможен только при наличии незаурядных математических способностей.
80004. ВЛИЯНИЕ НЕСТАЦИОНАРНЫХ ЭФФЕКТОВ НА ДИНАМИКУ ВСПЛЫТИЯ ПУЗЫРЬКА 2.21 MB
  Данная работа состоит из трех разделов. В первом рассмотрена динамика всплытия пузырька в стационарном режиме. Приведены теоретические расчеты скорости пузырьков в различных растворах. При движении пузырьков в режиме ускорения на них действуют дополнительные силы: сила, приведенной массы, связанная с присоединенной массой и сила Бассэ.
80005. Сравнительный анализ «опыта потока» в игровой и продуктивной деятельности 1.15 MB
  Человек, переживающий поток, оказывается сверхвовлеченным и сверхсконцентрированным в своей деятельности, причем она доставляет ему огромное удовольствие. Поток принадлежит к кругу явлений внутренней мотивации: деятельностью, в которой возникает поток, люди продолжают заниматься ради самого процесса, конечный результат не столь важен для них.
80006. ОПТИМИЗАЦИЯ ПЛАНА РЕГЛАМЕНТНЫХ РАБОТ ПО КРИТЕРИЮ МАКСИМУМА СРЕДНЕГО ПОТОКА В СЕТИ ПРИМЕНИТЕЛЬНО К ЗАДАЧЕ ТРАНСПОРТИРОВКИ НЕФТИ ПО МАГИСТРАЛЬНОМУ НЕФТЕПРОВОДУ 960 KB
  проведена программная реализация алгоритма Форда – Фалкерсона нахождения максимального потока в сети, построен и программно реализован алгоритм субоптимального планирования регламентных работ на участках нефтепровода по критерию максимума потока в сети. Тем самым разработан и реализован метод решения задачи максимизации потока в нестационарной сети на основе алгоритма Форда – Фалкерсона.
80007. Анализ и моделирование расщепления ДНК ультразвуком 4.97 MB
  Количественный анализ экспериментальных данных по расщеплению молекул ДНК ультразвуком и развитие подходов к моделированию реакции ДНК на внешние воздействия. Такие подходы используются для решения задачи о физической интерпретации специфичности расщепления молекул ДНК ультразвуком.
80009. ОСОБЕННОСТИ КОНЦЕПТОСФЕРЫ ПРОИЗВЕДЕНИЙ ЭДИТ ВАРТОН 271 KB
  Сделать обзор работ, касающихся понятия «концепт»; определить понятие концептосферы литературного произведения; выявить основные способы репрезентации ключевых концептов исследуемых произведений; выявить особенности концептуальной модели произведений
80010. Исследование модели фрактального броуновского движения 1.14 MB
  В данной работе рассматривается теоретические основы фрактального броуновского движения (ФБД), вопросы статистического моделирования ФБД на компьютере, а также применение теории ФБД при статистическом моделировании процессов стохастической системы, описываемых линейным дифференциальным уравнением с возмущениями в виде ФБД.
80011. СИСТЕМА УПРАЖНЕНИЙ В ОБУЧЕНИИ ПИСЬМЕННОЙ РЕЧИ УЧАЩИХСЯ 6 КЛАССА НА УРОКАХ АНГЛИЙСКОГО ЯЗЫКА 100.02 KB
  Письмо и письменная речь репродуктивная и продуктивная письменная речь формы коммуникативной письменной речи. Письмо как цель обучения цели и задачи письменной речи. Три компонента содержания обучения письменной речи навыки и умения обучения письменной речи...