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


 

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

28301. Система гражданского права 13.98 KB
  Система гражданского права Система гражданского права представляет собой внутренне согласованное единство и деление правовых норм составляющих данную отрасль права. Состоит из: подотраслей права норм регулирующих однородные отношения обязательственное право вещное право исключительные права личные неимуще права наследственное право жилищное транспортное Подотрасль состоит из правовых институтов. Все гражданскоправовые нормы составляющие систему гражданского права можно условно разделить на Общую и Особенную части. В Общую...
28302. Основные гражданско-правовые системы современности 17.03 KB
  Основные гражданскоправовые системы современности. Современный мир отличается многообразием гражданскоправовых систем. Каждое суверенное государство имеет свое национальное гражданское право. Вместе с тем в мире существуют своеобразные типы семьи правовых систем охватывающие группы права ряда государств.
28303. Источники гражданского права. Их классификация 14.7 KB
  Источники гражданского права. Нормы гражданского права содержатся и в так называемых подзаконных актах указах Президента РФ постановлениях Правительства РФ актах министерств и иных федеральных органов исполнительной власти. Наиболее важные законы группируются: в области корпаративного права зн об акционерных обществах зн об ООО зн об госуд.муницип и унитарных предприятиях зн о банкротстве ряд знов о некомерческих организациях в области обязательственного права зн о рынке ценных бумаг о финансовой аренделизинге о...
28304. Действие гражданского законодательства во времени, в пространстве и по кругу лиц 14.26 KB
  Действие гражданского законодательства во времени в пространстве и по кругу лиц. Под действием гражданского законодательства во времени понимается определение начального и конечного момента действия правового акта регулирующего гражданские отношения. По общему правилу акты гражданского законодательства не имеют обратной силы и применяются к отношениям возникшим после введения их в действие. Различают даты принятия акта гражданского законодательства опубликования и вступления в силу.
28305. Применение гражданского законодательства 14.21 KB
  В теории права различают 4 формы реализации права: 1 . Применение это такой способ реализации права кот связан с властными действиями юрисдикционных органов и должностных лиц. Применять норму права это значит применять власть а нередко принуждения санкции наказания. в случае пробелов в нем осуществляется путем применения аналогии закона и аналогии права.
28306. Гражданское правоотношение: понятие, элементы, содержание 15.11 KB
  Гражданское правоотношение: понятие элементы содержание. Гражданское правоотношение это урегулированные нормами гражданского права имущественные и личные неимущественные отношения. Элементы гражданского правоотношения как и любого правоотношения состоит из трех необходимых элементов: 1 субъектов; 2 объекта; 3 содержания. Виды правоотношй: 1.
28307. Субъекты и объекты гражданских правоотношений 14.49 KB
  Субъекты и объекты гражданских правоотношений Элементами гр. Субъекты гражданских правоотношений это те лица которые несут права и обязанности в правоотношении. В качестве субъектов гражданских правоотношений выступают граждане РФ иностранные граждане лица без гражданства юридические лица как российские так и иностранные. Особый субъект гражданских правоотношений государство и муниципальные образования.
28308. Основания возникновения, изменения и прекращения гражданских правоотношений 13.73 KB
  возникают из: сделок административных актов в резте создания произведений науки литературы и искусства и иных резтов интеллект деятети. вследствии причинения вреда другому лицу а также в следствии приобретения или сбережения имущества за счет средств другого лица без достаточных оснований в следствии иных действий граждан и организаций.
28309. Правосубъектность: понятие, состав, сравнительная характеристика по видам субъектов гражданских правоотношений 15.56 KB
  Так ребенок умершего зачатый при его жизни но родившийся после его смерти по закону приобретает право на наследство умершего. Факты рождения и смерти устанавливаются по медицинским показаниям. С определением момента смерти также связано много различных медицинских и правовых вопросов. Так в медицине различают состояние клинической смерти когда происходит остановка работы отдельных органов сердца почек головного мозга однако существует возможность восстановления жизнеспособности организма и биологической смерти когда начинаются...