Распределение В/Т регистров
При распределении В/Т регистров учитывается то, что их достаточно много по сравнению с числом переменных и других объектов в «средней» фортрановской программе. Однако, с учетом возможностей совместной компиляции задача их распределения тем не менее возникает.
Для ее решения строится дерево циклов в исходной программе. Распределение регистров происходит по циклам, начиная с самых вложенных в гнезде циклов.
Все объекты, которые должны быть в результате распределения на регистрах, загружаются перед входом в цикл. Множество объектов, занимающих регистры на определенном интервале программы, называется далее контекстом. При выходе из цикла восстанавливается объемлющий контекст.
Цикл представляет собой некоторый частный случай критического интервала. Выбор контекста на критическом интервале осуществляется по представлению программы, полученной на предыдущей фазе, и является начальным этапом алгоритма, более точно, речь идет о выборе начального контекста, включающего кандидатов в контекст.
Каждому объекту программы по полученному представлению приписывается определенный коэффициент использования. В простейшем случае он формируется на основе информации об общем количестве использований объекта по считыванию и записи со своими коэффициентами. Более точно этот коэффициент может быть определен на основе той же весовой функции, которая использовалась при построении сбалансированного дерева. Это можно продемонстрировать на следующем примере (3) выражения
a+a+b^b
2 объекта a и b использованы по считыванию два раза. Однако, весовая функция в узле К2(*) больше, чем в узле К\ (+).
При наличии одного регистра Т предпочтительнее отдать регистр для В, так как это в меньшей степени задержит вычисления по дереву в целом.
Поэтому коэффициент использования объекта в общем случае определяется как сумма весовых функций по узлам деревьев, которые входят в путь от вершины к данному объекту.
Объекты с наибольшими коэффициентами использования образуют начальный контекст на критическом интервале. Выбор контекста в объемлющем критическом интервале (объемлющем цикле в нашем случае) производится с учетом следующих факторов.
Во-первых, если остаются свободные регистры, то они отдаются объемлющему контексту.
Во-вторых, если имеются несколько интервалов на одном уровне, вложенных в один объемлющий, то распределение регистров в каждом интервале ведется таким образом, чтобы минимизировать накладные расходы на вход/выход в интервалы. Если имеются объекты объемлющего интервала, коэффициент использования которого превосходит общий накладной расход по какому-либо регистру, связанный со входом/выходом в интервалы, то такой объект также может быть включен в объемлющий контекст.
Результаты вычислений общих подвыражений входят в общее множество анализируемых объектов. Для обеспечения промежуточных результатов вычислений, которые могут возникать в процессе генерации кода, и обеспечения команд перезагрузки, которые могут возникнуть при распределении A/S регистров, резервируется некоторое количество В/Т регистров, возможно на основе анализа полученных деревьев.
В общем случае на входе в фазу планирования по балансу и распределения В/Т регистров может поступать программа в виде ациклического направленного графа, а не в виде списка деревьев в чистом виде.
Это обуславливается работой на предыдущих фазах по поиску общих подвыражений. Узел на таком графе (К), означающий результат общего подвыражения, может быть легко выделен поскольку в этот узел входит не одна ветвь, а несколько. Именно такие узлы соответствуют общим подвыражениям. Они рассматриваются как и другие объекты (переменные, константы и т. п.) при распределении В/Т регистров и образуют специфичный вид объектов.
Таким образом, для результатов вычисления общих подвыражений могут быть назначены (выделены) В/Т регистры на основе общего алгоритма их распределения.
Коэффициент использования для объектов подобного вида требует более сложного определения. В частности, он должен включать значения коэффициентов по всем деревьям, куда входит общее подвыражение.
Аналогичным образом и при построении сбалансированного дерева весовые функции в подобных узлах считаются по специальным правилам.
Промежуточные результаты вычислений, которые могут появляться в ходе генерации по этому представлению, возможно, связать с оставшимися узлами деревьев, соответствующими операциям ЭВМ. Это позволяет оценить их возможное число.
Более подробный анализ подобных специфических ситуаций трудно вместить в рамки данной статьи.
Следует также отметить, что не предполагается выполнять глобальные виды оптимизаций, как по данным, так и по управлению. В связи с этим поиск общих подвыражений предварительно предполагается выполнять в рамках линейных блоков. Это необходимо подчеркнуть в связи с общей схемой оптимизационных преобразований.
Метки: регистр, распределение регистров