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


 

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

41513. Психологія особистості керівника 311 KB
  Феномен керівника в історії розвитку суспільства Мотиваційна сфера особистості керівника Труднощі вимоги та обмеження у роботі керівників Якості і риси керівника Проблема статі в управлінні Ортобіоз особистості керівника Регресивний розвиток керівника та управлінська деформація 1.Феномен керівника в історії розвитку суспільства Давні історичні політичні та соціальні вчення Єгипту Китаю Греції Риму та інших країн відображали не лише основні риси ранніх типів суспільства а й певні характерологічні особливості правителів...
41514. ПСИХОЛОГІЧНІ ЧИННИКИ ОЦІНЮВАННЯ УПРАВЛІНСЬКИХ КАДРІВ 110.5 KB
  Роль оцінювання працівників у процесі управління Соціальнопсихологічні завдання оцінювання Оцінювання за головними параметрами діяльності класифікація характеристика елементів класифікації Установки і форми поведінки керівників під час оцінювання підлеглих Характеристика сучасного менеджера управлінця 1. Роль оцінювання працівників у процесі управління Оцінювання працівників є складовою процесу управління. Головна мета оцінювання: 1.
41515. УПРАВЛІНСЬКЕ КОНСУЛЬТУВАННЯ І БІЗНЕС 79 KB
  Специфіка найму і роботи штатних та зовнішніх управлінських консультантів Головні стилі роботи консультанта. Особливості діяльності консультантів. Специфіка найму і роботи штатних та швшнініх управлінських консультантів У розвинених країнах широко використовується особливий вид діяльності управлінське консультування. Зауважимо що жодна значна перебудова у фірмах Заходу не обходилась без запрошення консультантів.
41516. Соціальні та психологічні аспекти керівництва 147 KB
  Соціальні та психологічні аспекти керівництва Кадри управління. Кадри управління. Кадри управління є складовою частиною управління ця частина системи має: відповідну кваліфікацію. Зокрема керівників залежно від профілю колективів котрі вони очолюють прийнято поділяти на лінійних та функціональних а від рівня і місця в загальній системі управління господарством на керівників відповідних ланок управління вищої середньої низової ланок.
41517. Колегіальний підхід в прийнятті управлінських рішень 177.5 KB
  Функція планування передбачає рішення про те якими повинні бути цілі організації і що повинні робити члени організації щоб досягнути цих цілей. Стратегічне планування сприяє зниженню ризику під час прийняття рішення. Вторинна інформація це дані зібрані раніше для цілей що відмінні від цілей пов'язаних з вирішенням досліджуваної проблеми. Інтерес науковців до цієї проблеми зумовлений тим що в рішеннях фіксується вся сукупність відносин котрі виникають у процесі трудової діяльності і управління організацією.
41518. Основи групової самоорганізації 124.5 KB
  Думка щодо органічності суспільства і людини виражена шведським вченим Еммануїлом Сведенборгом 1688 1772: Існує чітка функціональна подібність між людством народом і окремим індивідом. А теоцентричний представник філософського езотеризму Володимир Олексійович Шмаков 1929 доводив виказану позицію раціональними методами: Вірно виявлена загальна ідея організму однаково застосовна до людини і суспільства але в останньому вона виявляється з більшою силою і багатоманіттям.тому і заперечення того що суспільство є організмом і повне...
41519. КОНФЛІКТИ В СИСТЕМІ УПРАВЛІННЯ ПСИХОЛОГІЧНА ПІДГОТОВКА ДО НОВОВВЕДЕНЬ 180 KB
  Поняття конфлікту. Поняття інновація та нововведення Головні передумови позитивного ставлення до нововведень 1 Поняття конфлікту. Позитивний ефект конструктивного конфлікту для окремої людини може виявлятися і в тощ' що при його вирішенні відбувається усунення внутрішнього психічного напруження і як наслідок буде знайдено вихід зі стану фрустрації. Під час аналізу конфлікту дуже важливо з'ясувати справжні причини його виникнення.
41520. ТЕОРЕТИЧНІ ОСНОВИ ПСИХОЛОГІЇ УПРАВЛІННЯ 112 KB
  Психологія управління на Заході Поняття про науку управління Поняття управління використовують у різних науках. Відповідно до трьох головних сфер розвитку об'єктивного світу нежива природа жива природа суспільство можна виокремити головні види управління: управління в неживій природі; управління в живій природі; управління у суспільстві.
41521. Особистість в системі управління 205 KB
  Теорії особистості та їх використання в управлінській практиці Активність особистості як форма вияву її індивідуальності творчості та професіоналізму Соціальна позиція та роль особистості в організації Рівень домагань особистості та їх значення в управлінських відносинах Соціальні норми як регулятори поведінки особистості 2. Теорії особистості та їх використання в управлінській практиці У процесі осмислення психологічною наукою сутності особистості особливостей її розвитку самореалізації взаємодії із зовнішнім середовищем...