Тема 07(2016)Анализ на основе областей (1161802)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

7. Анализ потока данныхна основе областей17.1 Области графа потока управления7.1.1. Определение областиОпределение. Областью графа потока называется его подграфR = NR, ЕR такой, что1. существует узел h  NR, доминирующий над всеми узлами в R;этот узел называется заголовком области R;2. если из некоторого узла r2 графа потока управления можнодостичь узла r1  R, минуя заголовок h, то и r2  R;3. множество ЕR включает все ребра графа потока управлениямежду любыми узлами r1, r2  R, за исключением некоторыхребер, входящих в заголовок h;4. единственным входом в область является ее заголовок.27.1 Области графа потока управления7.1.1.

Определение областиПример 1.37.1 Области графа потока управления7.1.1. Определение областиПримеры.7. Рассмотрим граф на рисунке справа1) узлы В1 и В2 вместе с ребром В1  В2образуют область с заголовком В12) узлы В1, В2 и В3 и ребра В1  В2,В2  В3, В1  В3образуют область с заголовком В147.1 Области графа потока управления7.1.1. Определение областиПримеры.1.

Рассмотрим граф на верхнем рисунке3) подграф R = {В2, В3}, {В2  В3} область необразует, так как управление может попастьв него и через В2, и через В3:В2 не является доминатором В3,В3 не является доминатором В2и, следовательно, условие 1 определения 7.1.1(существует узел h  NR, доминирующийнад всеми узлами в R;)не выполняется (нижний рисунок)57.1 Области графа потока управления7.1.1.

Определение областиПример 2.Суперблок (рассматривался, когда изучался метод глобальнойнумерации значений) – пример области. В частности граф нарисунке – область с заголовком В1.Узел В1 доминирует над остальными узламиB1B2B3B4B567.1 Области графа потока управления7.1.1. Определение областиПример 3.Граф на рисунке – область с заголовком В3(естественный цикл).77.1 Структурный анализ графа потока управления7.1.2.

Классификация областей Определения:(1) Каждый базовый блок B может рассматриваться как областьR = {B}, . Такая область называется область-лист.(2) Пусть L – самый внутренний цикл гнезда циклов.Тело цикла L (все узлы и ребра, за исключением обратных реберк заголовку цикла) можно заменить узлом, представляющимобласть R. Такая область называется область-тело.(3) Если к области-телу R, соответствующей телу цикла Lприсоединить обратное ребро к заголовку цикла L, получитсяновая область Q. Такая область называется область-цикл.87.1 Структурный анализ графа потока управления7.1.2. Виды областей. ПримерR1R2R3R4R5R6R7Фрагмент процедурыБазовые блоки – области-листья97.1 Структурный анализ графа потока управления7.1.2.

Виды областей. ПримерR2R3R4R5R6Тело внутреннего цикла107.1 Структурный анализ графа потока управления7.1.2. Виды областей. ПримерR2R8R3R4R5можно заменить наобласть-тело R8R6Тело внутреннего цикла117.1 Структурный анализ графа потока управления7.1.2. Виды областей. ПримерR2R8R3R4R5R6можно заменить наобласть-тело R8добавив обратнуюдугу,R8получим областьцикл R9Тело внутреннего циклаR9127.1 Структурный анализ графа потока управления7.1.2. Виды областей.

ПримерГраф потокауправления примет видТело внешнего циклаR10R1R1R9R9R7Добавив обратнуюдугу, получимобласть-цикл R11R7R11R10Заменяетсяобластью-телом R10137.1 Структурный анализ графа потока управления7.1.2. Виды областей. ПримерДерево управленияR11R10R1R9R7R8R2R3R4R5R6147.1 Структурный анализ графа потока управления7.1.3.

Выделение областей Рассмотрим ГПУ, показанный на рисунке.B1B2B3B4B5ijaiaj..- m, 1nu1+ i, 1u2u3. .d1d2d3d4d5d6157.1 Структурный анализ графа потока управления7.1.3. Выделение областей1) Заменив базовые блокиEntry, B1, ..., B5, Exitобластями-листьямиRen, R1, …, R5, Rex ,получим граф167.1 Структурный анализ графа потока управления7.1.3. Выделение областей2) Области-листья R2, R3 и R4 и ребра R1R2, R2R3,R2 R4, R3 R4, R3 R5, R4 R5составляют область-тело R6 .R6 = {R2, R3, R4}, {R1R2, R2R3, R2R4, R3R4,R3R5, R4R5}R2R6R6R3R4177.1 Структурный анализ графа потока управления7.1.3.

Выделение областей3) Область-тело R6, и обратное ребро R4  R2составляют область-цикл R7 = {R6}, {R4 R2}.R7R7187.1 Структурный анализ графа потока управления7.1.4. Алгоритм построения иерархии областей Алгоритм.1.Найти все естественные циклы.2.Найденные естественные циклы упорядочить изнутригнезд наружу, т.е. начиная с наиболее внутренних циклов.3.Выбрать очередной естественный цикл (сначала – самыйпервый, потом – следующий по порядку).Если циклов больше нет, алгоритм заканчивается.4.Тело выбранного цикла L (все узлы и ребра, за исключениемобратных ребер к заголовку) заместить узлом R,представляющим область-тело.После замещения обратное ребро в заголовок L становитсяпетлей.5.Построить область-цикл Q, представляющую цикл L(в отличие от области R область Q не содержит петли).Перейти к шагу 3.197.1 Структурный анализ графа потока управления7.1.5. Построение иерархии областей Пример.

Применим алгоритм к следующему ГПУИсходный ГПУ207.1 Структурный анализ графа потока управления7.1.5. Построение иерархии областей Пример. Применим алгоритм к следующему ГПУИсходный ГПУБазовые блокизаменены областямилистьями217.1 Структурный анализ графа потока управления7.1.5. Построение иерархии областей Пример. Применим алгоритм к следующему ГПУИсходный ГПУБазовые блокизаменены областямилистьямиПосле шага 2227.1 Структурный анализ графа потока управления7.1.5. Построение иерархии областей Пример.После шага 4После шага 5Область R8 – весь ГПУ237.1 Структурный анализ графа потока управления7.1.5. Построение иерархии областей Пример.Исходный ГПУПоследовательность преобразований247.1 Структурный анализ графа потока управления7.1.5.

Построение иерархии областей Пример.Вся иерархияДерево управления257.1 Структурный анализ графа потока управления7.1.5. Построение иерархии областей Пример.Исходный ГПУДерево управления267.1 Структурный анализ графа потока управления7.1.6. Алгоритм построения восходящего порядка областей Вход: приводимый ГПУ G. Выход: список областей графа G, который может использоваться взадачах анализа потоков данных на основе областей. Метод: выполняем следующие действия.1)Составляем список областей-листьев, состоящих из отдельныхблоков в произвольном порядке.2)Выбираем очередной естественный цикл L, такой, что всеобласти, соответствующие естественным циклам, содержащимсяв L, уже внесены в список.

Сначала добавляем в список область-тело для L, а затем – область-цикл L.3)Если весь граф G является естественным циклом, добавляем вконец списка область, состоящую из всего графа потока целиком.277.1 Структурный анализ графа потока управления7.1.7. Скорость сходимости итерационных алгоритмовПостроение областей и дерева управления позволяет ускоритьобход графа потока управления во время выполнения различныхалгоритмов анализа потока данных.В алгоритмах анализа потока данных, в которых в качестве сбораиспользуется объединение, удается, заменив каждый цикл узломтипа область-цикл, оставить только ациклические пути дляраспространения атрибутов.Это позволяет сократить время выполнения соответствующегоанализа потока данных.287.2.

Анализ потока данных на основе областей7.2.1. Схема анализа потока данных на основе областейНа каждом уровне иерархии областей: Для каждой области R и для каждой подобласти R'  R вычисляется передаточная функцияf R , InR , суммирующая влияниевсех возможных путей в R, ведущих от входа в R ко входу в R'.Мы рассматриваем анализ в прямом направлении (сверху вниз).Анализ в обратном направлении рассматривается аналогично сочевидными изменениями.297.2. Анализ потока данных на основе областей7.2.1.

Схема анализа потока данных на основе областейНа каждом уровне иерархии областей: Для каждой области R и для каждой подобласти R'  R вычисля-fется передаточная функция R , In R  , суммирующая влияниевсех возможных путей в R, ведущих от входа в R ко входу в R‘. Например, для области R6и её подобластей R2, R3 и R4будут вычислены передаточные функцииf R6 , InR2 f R6 , InR3 f R6 , InR4 307.2.

Анализ потока данных на основе областей7.2.1. Схема анализа потока данных на основе областейНа каждом уровне иерархии областей: Область R  R называется выходной подобластью области R,если у R есть выходное ребро к некоторой области,не принадлежащей области R. Для каждой выходной области R  R вычисляется передаточнаяфункцияf R ,Out R, суммирующая влияние всех возможныхпутей в R, ведущих от выхода из R к выходу из R.317.2.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций