Разработка компиляторов

       

Def-Use Chains


Следующей удобной формой представления программ для оптимизации является представление с использованием def-use chains .

Помимо алфавита операторов введем в рассмотрение алфавиты входов I и выходов O и определим для каждого оператора ? множество его входов input(?) и выходов output(?). При этом будем требовать, чтобы множества входов и выходов для разных операторов не пересекались.

Рассмотрим теперь отображение DU , которое каждому выходу сопоставляет некоторое подмножество множества входов. Тогда для каждого оператора определяются множества def(?) и use(?), которые есть соответственно множества его выходов и множество тех выходов других операторов, образы которых при отображении DU содержат хотя бы один вход оператора ?

Неформально говоря, данное представление позволяет отследить потоки данных в программе без учета того, как именно эти данные преобразуются. Множества входов и выходов соответствуют интуитивному представлению об аргументах и результатах операторов, а отображение DU просто описывает, как используются выработанные операторами результаты.



Содержание раздела