А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 170
Текст из файла (страница 170)
Распространенные задачи потоков данных наподобие упомянутых выше, имеют общую математическую структуру. Значения потока данных являются элементами полурешетки, оператор сбора — оператором сбора полурешетки, а передаточная функция отображает элементы решетки на элементы решетки. Множество допустимых передаточных функций должно быть замкнуто относительно композиции и включать тождественную функцию. + Монотонные структуры. Полурешетка имеет отношение <, определяемое следующим образом: а < 6 тогда и только тогда, когда а Л Ь = а.
Монотонные структуры обладают тем свойством, что каждая передаточная функция сохраняет отношение <, т.е. из а < 6 следует ~(а) < Х(6) для любых элементов решетки а и 6 и передаточной функции г". + Дистрибутивные структуры. Эти структуры удовлетворяют условию з'(а Л Ь) = з'(а) Л У (6) для любых элементов решетки а и Ь и передаточной функции ~.
Можно показать, что условие дистрибутивности влечет за собой монотонность. + Итеративное решение абстрактной структуры. Все монотонные структуры потоков данных могут быть решены с использованием итеративного алгоритма, в котором соответствующим образом (в зависимости от структуры) инициализируются значения пч и опт для каждого блока, а новые значения этих переменных вычисляются путем многократного применения передаточных функций и операторов сбора. Это решение всегда безопасно (предлагаемая им оптимизация не изменяет результат работы программы), но является наилучшим из возможных только в случае дистрибутивности структуры. + Структура распространения констант. Наряду с дистрибутивными базовыми структурами, такими как достигающие определения, имеются интересные монотонные, но не дистрибутивные структуры.
Одним из примеров 836 Глава 9. Машинно-независимые оптимизации является распространение констант, использующее полурешетку, элементами которой являются отображения переменных программы на константы, а также два специальных значения, представляющих "нет информации" и "точно не константа". + Устранение частичной избыточности. Многие полезные оптимизации, такие как перемещение кода и устранение глобальных подвыражений, могут быть обобщены в единую задачу, которая называется устранением частичной избыточности.
Необходимые выражения, которые доступны только вдоль некоторых путей к точке, вычисляются толью вдоль тех путей, где они недоступны. Корректное применение этой идеи требует решения последовательности из четырех различных задач потоков данных, а также выполнения некоторых дополнительных операций. + Доминаторы. Узел в графе потока доминирует над другим узлом, если все пути к последнему проходят через первый. Истинным доминатором является доминатор, отличный от самого рассматриваемого узла. Каждый узел, кроме входного, имеет непосредственный доминатор — один из истинных доминаторов, над которым доминируют все остальные.
+ Упорядочение графов потоков в глубину. Если выполнить поиск графа потока в глубину, начиная с его входа, то мы получим глубинное остовное дерево. Упорядочение узлов в глубину представляет собой обращенный обратный порядок обхода. + Классификация ребер. При построении глубинного остовного дерева все ребра графа можно разбить на три группы: наступающие ребра (идущие от предка к истинному потомку), отступающие (идущие от потомка к предку) и поперечные (все остальные).
Важное свойство заключается в том, что все поперечные ребра идут в дереве справа налево. Другим важным свойством является то, что при использовании упорядочения в глубину среди этих ребер только у отступающих заголовок меньше хвоста. + Обратные ребра. Обратным называется ребро, заголовок которого доминирует над хвостом. Любое обратное ребро является отступающим, независимо от того, какое глубинное остовное дерево выбрано для его графа потока. + Приводимые графы потоков. Если все отступающие ребра являются обратными, независимо от выбранного глубинного остовного дерева, то граф потока называется приводимым. Подавляющее большинство графов потоков приводимо; точно приводимы графы потоков, инструкциями управления ВЗ7 9.9. Резюме к главе 9 потоком которых являются только обычные циклы и инструкции ветвле- ния.
+ Естественные циклы. Естественный цикл представляет собой множество узлов с заглавным узлом, который доминирует над всеми узлами множества, содержащее как минимум одно обратное ребро, входящее в этот узел. Для заданного обратного ребра можно построить его естественный цикл, беря заголовок ребра плюс все узлы, которые могут достичь хвоста ребра„ не проходя через заголовок. Два естественных цикла с разными заголовками либо не пересекаются, либо один из них полностью содержится в другом; этот факт позволяет нам говорить об иерархии вложенных циклов, если под "циклами" подразумеваются естественные циклы. + Упорндочение в глубину делает итеративный алгоритм более эффективным.
Итеративный алгоритм требует нескольких проходов, достаточных для распространения информации вдоль ациклических путей. Если посешать узлы в порядке в глубину, любая структура потока данных, распространяющая информацию в прямом направлении, например достигаюшие определения, будет сходиться не более чем за количество итераций, равное увеличенному на 2 наибольшему количеству отступающих ребер на любом ациклическом пути. То же самое справедливо и для структур с распространением информации в обратном направлении (например, для активных переменных), если посещать узлы в порядке, обратном порядку в глубину (в порядке обратного обхода).
+ Области. Области представляют собой множества узлов и ребер с заголовком 6, доминирующим над всеми узлами в области. Предшественники любого узла области, отличного от 6, также должны находиться в области. Все ребра области проходят между узлами области, за возможным исключением некоторых (или всех) ребер, входяших в заголовок.
+ Области и приводииые графы потоков. Приводимые графы потоков могут давать в результате разбора иерархию областей. Эти области являются либо областями циклов, которые включают ребра, ведущие в заголовок, либо области тел, которые не содержат ребер, ведуших в заголовок. + Анализ потока данных на основе областей. Альтернативой итеративному подходу к анализу потока данных является работа в восходящем и нисходящем направлениях с иерархией областей, при которой вычисляются передаточные функции от заголовка каждой области к каждому узлу этой области.
838 Глава 9. Машинно-независимые оптимизации + Обнаружение индуктивных переменных на основе областей. Важным применением анализа на основе областей является структура потока данных, которая пытается вычислить формулы для каждой переменной в области цикла, значения которой представляют собой аффннную функцию от количества выполненных итераций цикла. 9.10 Список литературы к главе 9 Два ранних компилятора, активно использовавших оптимизацию, — это А1рпа [16] и гогггап Н [16]. Фундаментальным исследованием по методам оптимизации циклов (например, перемещению кода) считается работа [Ц, хотя ранние версии некоторых из идей появились в [8].
Многие идеи по оптимизации кода можно найти в [4]. Первое описание итеративного алгоритма для анализа потока данных приводится в неопубликованном отче~с Высоцкого (Чукво1з)су) и Вегнера (утейпег) [20]. Научное изучение анализа потоков данных началось с пары статей Аллена (А11еп) [2] и Кука (Сос1се) [3]. Теоретическая абстракция решетки, описанная в нашей книге, основана на работе Килдалла (КИа1!) [13].
В его работе структуры считаются дистрибутивными, но имеется множество структур, не являюшихся таковыми. После того как было обнаружено достаточное количество структур, не являющихся дистрибутивными, в модель в работах [5 и 1Ц было введено условие монотонности. Впервые устранение частичной избыточности рассмотрено в [17]. Алгоритм отложенного перемещения кода, описанный в данной главе, основан на работе [14]. Доминаторы впервые использованы в компиляторе, описанном в [13].
Однако впервые идея появилась в [18]. Понятие приводимых графов потоков происходит из [2]. Структура этих графов потоков, представленная в данной главе, основана на [9 и 10]. В работах [12 и 15] впервые связаны приводимость графов потоков с распространенными вложенными структурами управления потоками, что поясняет широкую распространенность этого класса графов потоков. Определение приводимости с помощью приведения Т1 — Тз, используемое в анализе на основе областей, описано в [19].
Подход на основе областей впервые использован в компиляторе, описанном в [2Ц. Статическое промежуточное представление с единственным присваиванием содержит как поток данных, так и поток управления. Такое представление упрошает реализацию многих оптимизирующих представлений в распространенных структурах [6]. ГЛАВА 10 Параллелизм на уровне команд Все современные высокопроизводительные процессоры могут выполнять за один такт несколько операций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
