Теормин (2015) (Теормин), страница 2

Поток данных – все возможные наборы значений переменных, вычисленныев различных точках программы.25. Живые переменные - переменные, используемые в базовых блоках, вкоторые попадает управление после выхода из исследуемого базового блока.25. Живые переменные - переменные, используемые в базовых блоках, вкоторые попадает управление после выхода из исследуемого базового блока.26-27. Существует несколько разновидностей бесполезного кода (инструкциикоторого не влияют на результат вычислений): мертвый код – инструкции,результат которых не используется в дальнейших вычислениях; недостижимыйкод – инструкции, которые не содержатся ни в одном реальном пути выполнения;избыточный код – инструкции, повторно вычисляющие уже вычисленныезначения (напр., доступные выражения или инвариантные вычисления в циклах).28.

Доминаторы. В ГПУ вершина d является доминатором вершины n (этотфакт записывается как d dom n или d = Dom(n)), если любой путь от вершиныEntry до вершины n проходит через вершину d. Каждая вершина n являетсядоминатором самой себя, так как путь от Entry до n проходит через n.Вершина i ГПУ является непосредственным доминатором вершины n(i idom n), если 1) i dom n, 2) не существует вершины m, m ≠ i, m ≠ n, такой чтоi dom m и m dom n.Вершина s ГПУ является строгим доминатором вершины n (s sdom n), еслиs dom n и s ≠ n.29. ДереводоминаторовB1B3B2B4B6Соединив дугамикаждый блок с егонепосредственнымдоминатором,получим дереводоминаторов (Entryэто блок B1).B1 ДереводоминаторовB2B5B3B4B5B7B6B7B8ГПУB10B8B7 ∈ DF(B3)B9B9B1030.

Граница доминирования n ( DF(n) ) - множество узлов m, удовлетворяющихусловиям: 1) n является доминатором предшественника m, т.е. p ∈ Pred(m) & n ∈Dom(p), 2) n не является строгим доминатором m, т.е. n ∉ (Dom (m) – {m}).Неформально: DF(n) содержит все первые узлы, которые достижимы из n, налюбом пути графа потока, проходящем через n, но над которыми n не доминирует.31. Постдоминатор: в ГПУ вершина p постдоминирует над вершиной n(p = Postdom (n) ), если каждый путь из вершины n в вершину exit проходит черезвершину p.

Выходной узел постдоминирует над всеми блоками графа.Постдоминаторы ГПУ – это доминаторы его обратного графа.32. Обратная граница доминирования (RDF(n)) вершины n ∈ G это обычнаяграница доминирования в обратном графе GR. Обратным графомориентированного графа G = 〈N, E〉 называется ориент. граф GR = 〈N, ER〉, уB1которого направления всех ребер противоположны.33. Выражение e доступно в точке p, если e вычисляется налюбом пути от Entry до p причем переменные, входящие в составe не переопределяются между последним такимk←вычислением и точкой p. //Пусть точка p – вход в блок B3. Нарисунке //присваивание не убивает выражение *, 4, i.//Поэтому t2 ← *, 4, i можно заменить на t2 ← t1t1← *,4,iB2+,i,7B3t2← *,4,i34-39.

ПолурешеткаПолурешетка – это абстрактная алгебраическая структура, над элементамикоторой определена абстрактная операция ∧ (мы будем называть ее «сбор»),обладающая свойствами операций ∪ и ∩.Опр. Полурешетка представляет собой множество L, на котором определенабинарная операция «сбор» ∧, такая, что для всех х, у и z ∈ L:x ∧ x = x (идемпотентность),x ∧ у = у ∧ x,x ∧ (y ∧ z) = (x ∧ y) ∧ z .Полурешетка имеет верхний (наибольший) элемент (или верх)что для всех x ∈ L выполняется Т ∧ x = x.Т ∈ L такой,Полурешеточное отношение частичного порядка: для всех пар x, у ∈ Lопределим отношение ≤: x ≤ у тогда и только тогда, когда x ∧ у = x(1) Рефлексивность ≤ следует из идемпотентности ∧: x ≤ x ⇔ x ∧ x = x(2) Антисимметричность ≤ следует из коммутативности ∧: пусть x ≤ у и у ≤ x;тогда x = x ∧ у = у ∧ x = у(3) Транзитивность ≤ следует из ассоциативности ∧: пусть x ≤ у и у ≤ z; тогда поопределению ≤x ∧ у = x и у ∧ z = у;(x ∧ z) = x ⇔ x ≤ z;(x ∧ z) = ((x ∧ у) ∧ z) = (x ∧ (у ∧ z)) – (x ∧ у) = x.Диаграмма полурешетки 〈L, ∧ 〉 представляет собой граф,узлами которого являются элементы L, а ребра направленыот х к у, если у ≤ х.Пример.

Диаграмма полурешетки 〈U, ∪〉, |U| = 8: элемент множестваU представляется битовым 3-вектором.40-42. Структурой потока данных называется четверка 〈D, F, L, ∧〉 , где D –направление анализа (Forward или Backward), F – семейство передаточныхфункций, L – поток данных, ∧ - операция сбора.Семейство передаточных функций F называется замкнутым, если:1) F содержиттождественную функцию I: ∀х∈ L: I(х) = х, 2) F замкнуто относительнокомпозиции: ∀ f, g ∈ F ⇒ h(x) = g(f(х))∈ F.Структура потока данных 〈D, F, L, ∧〉 называется монотонной, если∀х, у ∈ L, ∀f ∈ F f(x ∧ у) ≤ f(x) ∧ f(у).Структура потока данных 〈D, F, L, ∧〉 называется дистрибутивной, если∀х, у ∈ L, ∀f ∈ F: f(x ∧ у) = f(x) ∧ f(у).Утв.

Если структура потока данных 〈D, F, L, ∧〉 дистрибутивна, то она монотонна.43. Сворачивание констант заключается в вычислении констант в процессекомпиляции и замене константных выражений их значениями. Например,выражение 2 * 3.14 можно заменить значением 6.28.44. Пусть в оптимизируемой процедуре есть инструкция копирования x ← y.Распространение копий означает замену всех последующих вхожденийпеременной x на переменную y.

Каждая команда копирования описываетсячетверкой 〈x, y, b, p〉, b – блок, p – строка. Далее определяются и анализируютсямножество copy(b) команд копирования и множество kill(b) переопределений y …45. Форма статического единственного присваивания (SSA) позволяет вкаждой точке программы объединить 1) информацию об имени переменной2) с информацией о текущем значении этой переменной (или, что то же самое, синформацией о том, какое из определений данной переменной определяет еетекущее значение в данной точке).Хотелось бы, чтобы программа в SSA-форме удовлетворяла двум условиям: а) каждое определение переменной имеетиндивидуальное имя; б) каждое использование переменной достигало только одно определение.46. φ-функция - «функция» объединения значений.

φ -функция xопределяет SSA-имя для значения своего аргумента,x ← -,a,cсоответствующего ребру, по которому управлениевходит в блок. При входе в базовый блок все его φ -функциивыполняются одновременно и до любого другого оператора,определяя целевые SSA-имена.0← -,a,b147. Построенная SSA-форма называется максимальнойSSA-формой, так как она обычно содержит намного большеφ -функций, чем необходимо (в каждой точке сбора).48.

Частично усеченная SSA-форма содержит меньше φ функций, чем максимальная (но, к сожалению, она содержитне минимально возможное количество φ -функций).x2 ← +,a,bx3← φ(x0,x2)x4 ← *,a,cx5← φ(x4,x3)u ← *,x5,bx6← φ(x1,x5)v ← +,a,x6Чтобы не всегда вставлять φ -функции необходимо для каждой точки сбора уметьвыяснять, какие переменные нуждаются в φ -функциях ИЛИ для каждого определенияпеременной уметь находить множество всех точек сбора, которые нуждаются в φ функциях для значения, порожденного этим определением.1649. Натуральный (или естественный) цикл - цикл со следующими свойствами:1) цикл имеет единственный входной узел, называемый его заголовком,2) существует обратное ребро, ведущее в заголовок циклаНатуральный цикл обратного ребра 〈Bi, Bk〉 составляют узел Bk (заголовокцикла) и все узлы ГПУ, из которых можно достичь узла Bi, не проходя через узелBk.(эти узлы составляют тело цикла).50.

Инструкция инвариантна относительно цикла, если она удовлетворяетодному из следующих условий: 1) ее операнды – константы, 2) все определенияоперандов, достигающие инструкции, находятся вне цикла, 3) внутри циклаимеется в точности одно определение операнда, но оно само инвариантноотносительно цикла.51. Бесполезный код – см. 26-27.53. Машинно-независимая оптимизация: 1) простые оптимизации:сворачивание констант, алгебраические упрощения и перегруппировка,распространение копий; 2) оптимизация циклов; 3) исключение бесполезногокода; 4) оптимизация потока управления.Машинно-ориентированная оптимизация: генерация кода: 1) выбор команд,2)распределение регистров, 3) планирование кода.-Входной поток: промежуточное представление исходной программы(последовательность трехадресных инструкций) + таблица символов.-Выходной поток: объектный код (последовательность команд целевогопроцессора.1752.

Оптимизация потока управления: некоторые оптимизации могут иметьпобочный эффект, изменяющий форму ГПУ, добавляя в него бесполезные блоки идуги. Если компилятор содержит такие оптимизации, он должен также содержатьпроход, упрощающий ГПУ, исключая бесполезный поток управления. ФункцияClean() обрабатывает непосредственно ГПУ оптимизируемой процедуры,упрощая его:1) свернуть избыточную ветвь: если последние инструкции блока Bi реализуютветвление, и обе ветви выполняют условный переход на один и тот же блок Bi , товетвление заменяется безусловным переходом на блок Bi2) удалить пустой блок: если блок Bi содержит только инструкцию перехода, тоон поглощается своим последователем – блоком Bj.3) объединение блоков: если имеется блок Bi, который оканчивается переходомна Bj, у которого всего один предшественник, Bi, он может объединить эти блокикак показано на рисунке внизу, что позволяет исключить переход из Bi в Bj.4) подъём ветвлений: в ситуации, когда блок Bi, который оканчиваетсяпереходом в пустой блок Bj, а блок Bj оканчивается ветвлением, переход в концеблока заменяется на копию ветвления из блока Bj.

Такое преобразованиеподнимает ветвление из Bj в Bi.BiBj1) Bi⇒BjBiBiBj2)⇒BjBj3)⇒BiBj4)⇒BiBj54. Метод переписывания дерева.Целевой код генерируется в процессе свертки входного дерева в единый узелпутем последовательного применения правил преобразования дерева.