Задача глобального распределения регистров во время динамической двоичной трансляции

Распределение регистров оказывает существенное влияние на производительность генерируемого кода. В данной статье исследуется задача распределения регистров во время динамической двоичной трансляции. Так как существующие алгоритмы распределения регистров рассчитаны на использование в компиляторах, они плохо подходят для использования во время динамической двоичной трансляции. Был разработан новый алгоритм, который определяет, какие переменные должны располагаться на каких регистрах в начале и в конце базового блока (назовем эти ограничения пред- и постусловиями данного базового блока), а затем решает задачу локального распределения регистров в данных ограничениях. Для обеспечения корректности ограничений алгоритм должен работать так, чтобы бля любого базового блока b', предшествующего блоку b, постусловия блока b' совпадали с предусловиями блока b. Этого можно достичь, если выделить в графе потока управления группы дуг, на всех концах которых ограничения должны быть неизменны. Такие дуги называются точками синхронизации. Точки синхронизации являются связными компонентами в неориентированном графе, вершинами которого являются дуги графа потока управления, а ребрами соединены те дуги-вершины, которые либо входят, либо выходят из одного базового блока. Данное утверждение позволяет эффективно находить точки синхронизации. Для определения того, сколько переменных должно находиться на регистрах в точке синхронизации, количество доступных регистров оценивается с помощью регистрового давления. Затем выбираются конкретные переменные на их частоты использования в данном фрагменте кода. Алгоритм локального распределения регистров был модифицирован, чтобы использовать предусловия и обеспечивать постусловия. В статье приводится эффективный алгоритм для приведения существующего распределения в конце базового блока к требуемым постусловиям и доказывается оптимальность этого алгоритма. Применение описанного алгоритма распределения регистров привело к сокращению времени работы синтетического примера на 29.6%.

глобальное распределение регистров, динамическая двоичная трансляция, эмуляторы, QEMU

1. Батузов К. Задача локального распределения регистров во время динамической двоичной трансляции. Труды ИСП РАН, том 22, 2012 г., стр. 67-76. DOI: 10.15514/ISPRAS-2012-22-5

2. Chaitin G. J. Register allocation & spilling via graph coloring. Proceedings of the 1982 SIGPLAN symposium on Computer construction. SIGPLAN '82. New York, USA: ACM, 1982, pp. 98-105.

3. Poletto Massimiliano Sarkar Vivek. Linear san regsiter allocation. ACM Transaction on Programming Languages and Systems. 1999 Vol. 21, no 5, pp 895-913.

4. Bellard Fabrice. QEMU, a fast and portable dynamic translator. Proceedings of the annual conference on USENIX Annual Technical Conference. ATEC '05. Berkley, USA: USENIX Association, 2005, pp. 41-46.