Практикум «Оптимизирующие компиляторы» (на примере GCC), страница 8

выбор инструкций целевого МП – сопоставление некоторойоперациивыражениясоответствующейинструкции,передсопоставлением инструкций производится определение классарегистровдляимеющихсявпрограммепеременныхипромежуточных значений;2. распределение регистров – размещение переменных в регистрахсамым эффективным образом;3. составление расписания инструкций – формирование машинногокода базового блока из выбранных инструкций с наименьшимвременем исполнения.Первый этап генерации кода — сопоставления графа зависимостей поданным и управлению программы инструкциям целевого МП.

Длясопоставленияинструкцийбазовыйблокпредставляетсяввидеациклического сильно связанного двудольного орграфа потока данных(орграф ББ):Kb = (V, E),где V = {vi} – множество вершин двух типов:а) виртуальные (только с обозначением регистрового субфайла, а неномера, поскольку регистры в регионе функционально эквивалентны)регистры;б) команды;Практикум «оптимизирующие компиляторы»E – множество ориентированных рёбер, представляющих связи по данным,E = {ek}, ek = (vi, vj).На орграфе Kb вводится функция связности fc = V×V ∈ {0, 1}, и функцияразметки вершин fT(v) ∈ {"ресурс", "команда"}, v ∈ V.

Вводитсяобязательное условие: если fc(vi, vj) = 1, то fT(vi) ≠ fT(vj).Для каждой вершины v ∈ V определяется имя ресурса или команды, ивводятся атрибуты вершины. Для ∀v ∈ V, fT(v) = "команда", вводитсямножество операндов IN(v): vi ∈ IN(v), при fT(vi) = "ресурс", и существуетek= (vi, v); и множество результатов OUT(v): vj∈OUT(v), при fT(vj)="ресурс",и существует em=(v, vj). При таком представлении ББ автоматическивыделяется суперскалярный параллелизм. В орграфе ББ выделяетсямножество начальных вершин (либо вводится фиктивная начальнаявершина-команда)ипроводитсятопологическаясортировкадляподготовки этапа выбора инструкций.Выбор инструкцийВыбор инструкций для сопоставления с орграфом ББ происходит впроцессе полного покрытия орграфа ББ необходимым количеством копийграфов инструкций МП.

Процесс сопоставления является итеративным иможет происходить одновременно с окончательным распределениемрегистров и построением расписания инструкций (генерацией кода). Впроцессесопоставлениякаждойисходнойпеременнойvari∈VARопределяется её размещение в памяти и множество классов регистров дляразмещения копий переменной.После сопоставления каждой переменной множества классов регистровкаждой операции ББ сопоставляются одна (в улучшенных кодогенераторахвсе возможные) инструкции МП.

Например, при существовании разныхПрактикум «оптимизирующие компиляторы»инструкций сложения: сложения любых регистров (арифметических,индексных, и т.п.) и сложения регистров из некоторого субфайла, тоисходнойоперациисложениясопоставляютсялибонаиболее«приоритетная», либо первая встретившаяся в описании (GCC), либо всевозможные инструкции. Из сопоставленных инструкций при составлениирасписания команд выбирается только одна оптимальная.ДлянекоторогоББB=(VB,EB)∀v∈VB,дляfT(v)="команда",сопоставленными являются все InstrI, для которых в орграфе инструкцииМП KG=(VK,EK) существует команда v'∈VK, fT(v')="команда", такая, чтосовпадаютвиртуальные║OUT(v)║=║OUT(v')║,i=1,2,…,║IN(v)║,иимена(т.е.«+»,«-»),║IN(v)║=║IN(v')║,IN(v')i∈RT(TRT(Type(IN(v)i)))OUT(v')i∈RT(TRT(Type(OUT(v)i)))длядлякаждогокаждогоj=1,2,…,║OUT(v)║ – т.е.

инструкция МП может быть сопоставлена тольков случае, если типы операндов и результата исходной операции иинструкции совпадают. В случае комбинированных команд (исполняющихнесколько операций над данными за один такт) используется расширенноесопоставление.КомбинированнойкомандесорграфомKG=(VK,EK)инструкциями { v'1,…,v'n } | v'i∈VK, fT(v'i)="команда" сопоставляютсяv1,…,vn | vi∈VB, fT(v)="команда", с совпадающими виртуальными именами.Дляi=1,…,n:║IN(vi)║=║IN(vi')║,║OUT(vi)║=║OUT(v'i)║,дляj=1,2,…,║IN(v)║: IN(v')j∈RT(TRT((Type(IN(v)j))), и для k=1,2,…,║OUT(v)║:OUT(v')k∈RT(TRT(Type(OUT(v)k))).Дляпредставленияструктурыкомбинированной команды используются следующие ограничения: длянекоторых vi и vj, если IN(vi)≡IN(vj) или IN(vi)≡OUT(vj), необходимо, чтобыдля v'i и v'j, сопоставленных соответственно vi и vj, было справедливоOUT(v'i)≡IN(v'j) или IN(v'i)≡OUT(v'j).Сопоставления выполняется с вершин vi, имеющих IN(vi)=∅ (начальныевершины орграфа ББ) в направлении ориентации дуг орграфа.

В GCCПрактикум «оптимизирующие компиляторы»сопоставлениекомбинированныхкомандпроисходитвотдельномпроходе. В некоторых компиляторах приоритет при сопоставлении имеюткомбинированныекоманды.Специальныекоманды,состоящиеизнескольких операций (например, выборка из памяти с автоинкрементном)формируются либо в отдельном проходе, либо далее в процессесоставления расписания команд.Распределение регистров.Практически важнейшей проблемой при генерации коду являетсяраспределение регистров, основанное на определении времени жизнипеременных при выполнении кода функции. Большинство арифметикологических команд МП с RISC архитектурой не могут оперироватьнепосредственно со значениями в памяти, поэтому компилятор генерируетпоследовательность команд для загрузки необходимых в некоторыймомент времени значений переменных в регистры.

Для определениянеобходимых на текущий момент значений в регистровом файленеобходимо частично разрешить задачу определения времени жизнипеременных, копии которых находятся в регистровом файле (регистровыхпеременных).В современных моделях МП с длинным командным словом, улучшенныхRISC-МП,процессоровсархитектуройEPIC,нетрадиционныхпараллельных процессоров, ПЦОС ёмкость регистрового файла достигает64 – 256 регистров. Алгоритм распределения регистров долженэффективно задействовать такое количество регистров.В случае исполнения одной команды за такт (типичный RISC) особыхпроблем не возникает. Сначала строится расписание арифметикологических команд, затем между командами могут быть вставлены (принеобходимости) дополнительные команды загрузки или сохраненияПрактикум «оптимизирующие компиляторы»регистров в память.

При более сложной архитектуре процессора, установкадополнительныхкомандпроводиласьитеративнодоопределенияоптимального варианта, а затем все команды участвовали в составлениирасписания.При количестве одновременно исполняемых операций в длинной командеот 4 до 8 (или больше) проблема распределения регистров становитсягораздо более сложной. Обычно это связано с тем, что возможностиподачи данных из оперативной памяти в регистровый файл ограничены.Несколько легче эта проблема в случае, если мы обрабатываем регулярныебольшие куски данных – например, массивы, но, если доступ требуется кнескольким переменным, расположенным в памяти далеко друг от друга,проблемастановитсяочевидной–вычислительныевозможностипроцессора простаивают, так как скорость подачи данных относительноневелика.Решениеэтойпроблемыпутёмувеличенияколичестваинтерфейсов к оперативной памяти частично решает проблему подачиданных (гарвардская и супергарвардская архитектуры), но компиляциястановится ещё более сложной задачей.

Естественно, существуетнекотороеколичествонеочевидныхоптимизаций,связанныхсгруппированием данных и загрузкой векторов, но такие средства –редкость.Для старых моделей МП класса Intel 80486 проблема скорости подачиданных не поднималась в принципе, потому что ёмкость активной частирегистрового файла не превышала 6 регистров, кроме того, инструкцииМП обычно прямо оперировали значениями, расположенными в памяти.Однако, с появлением суперскалярных архитектур, проблема подачиданных компенсировалась в основном кэшем, и, в общем, анализпроводился с учётом того, что данные уже находятся в кэше 1-го уровня.Если рассмотреть процессор Itanium, то становится понятным, чтоПрактикум «оптимизирующие компиляторы»необходимы серьёзные меры для оптимального использования 128целочисленных регистров и 128 регистров для чисел с плавающей точкой.Среди алгоритмов распределения регистров рассмотрим два метода,широко использующихся на практике: распределение регистров спомощью раскраски графов и распределением регистров с помощьюлинейного сканирования потока данных.Оба метода используют т.н.

информацию о времени жизни переменныхдля нахождения распределения переменных-кандидатов на загрузку врегистры на машинные регистры.Для достижения цели метод, связанный с раскраской графов, представляетинформацию о времени жизни в виде графа зависимостей, в которомвершины представляют собой переменные-кандидаты и между двумявершинами существует дуга, если их времена жизни пересекаются – тоесть эти переменные не могут содержаться в одном регистре. Для целевогопроцессора, содержащего N регистров, нахождение раскраски этого графазависимостей времени жизни в N цветов эквивалентно распределениюпеременных-кандидатов по регистрам без конфликтов.

Первым описаниепроцесса раскраски графа зависимостей времени жизни встречается уЧайтина (Chaitin), этим вопросам посвящена диссертационная работаБриггса (Briggs) [27]. Алгоритм итеративно строит граф зависимостей ипытается его раскрасить. Если раскраска не удаётся, некоторые кандидатыперемещаются в память, убирается часть связей в графе, вставляется коддля выгрузки/загрузки переменных (spill code), и процесс повторяется. Напрактике основное время уходит на процесс построения графа, размеркоторого является O(n2) от количества переменных-кандидатов. Так какмодуль программы может иметь сотни переменных, и компилятор самможет генерировать достаточное количество временных переменных вПрактикум «оптимизирующие компиляторы»Рисунок 14случаеагрессивныхоптимизаций,раскраскаграфаможетзанятьдлительное время.Распределение регистров с помощью сканирования потока данныхоперирует с понятием «времени жизни», который начинается в моментприсвоения переменной этого значения и заканчивается в моментпоследнего использования этого значения в некоторой ветви программы.При сканировании просматривается в линейном порядке код программы, сцелью определения количества «активных» переменных.