Цепочка использования-определения - Use-define chain

А Цепочка использования-определения (UD цепь) это структура данных который состоит из использования U Переменная и все определения D этой переменной, которые могут быть использованы без каких-либо других промежуточных определений. Цепь UD обычно означает назначение некоторого значения переменной.

Аналог UD цепь это Цепочка "определение-использование" (DU Chain), который состоит из определения D переменной и всех видов использования U, доступных из этого определения без каких-либо других промежуточных определений.

Цепочки UD и DU создаются с использованием формы статический анализ кода известный как анализ потока данных. Знание цепочек use-def и def-use для программы или подпрограммы является необходимым условием для многих оптимизация компилятора, включая постоянное распространение и исключение общего подвыражения.

Цель

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

Рассмотрим следующий фрагмент кода:

 int Икс = 0;    / * A * / Икс = Икс + у;    / * B * / / * 1, некоторые использования x * / Икс = 35;       / * C * / / * 2, еще несколько вариантов использования x * /

Заметь Икс присваивается значение в трех точках (отмеченных A, B и C). Однако в точке, отмеченной "1", цепочка use-def для Икс должен указывать, что его текущее значение должно быть получено из строки B (а его значение в строке B должно быть получено из строки A). Напротив, в точке, отмеченной цифрой "2", цепочка use-def для Икс указывает, что его текущее значение должно быть получено из строки C. Поскольку значение Икс в блоке 2 не зависит от каких-либо определений в блоке 1 или ранее, Икс с тем же успехом там может быть другая переменная; практически говоря, это является другая переменная - назовите это x2.

 int Икс = 0;    / * A * / Икс = Икс + у;    / * B * / / * 1, некоторые использования x * / int x2 = 35;  / * C * / / * 2, некоторые использования x2 * /

Процесс расщепления Икс на две отдельные переменные называется разделение живого диапазона. Смотрите также статическая форма единого назначения.

Настраивать

Список утверждений определяет строгий порядок среди утверждений.

• Заявления помечаются с использованием следующих соглашений: ${ Displaystyle s (я)}$, куда я целое число в ${ Displaystyle [1, п]}$; и п количество утверждений в базовый блок
• Переменные выделены курсивом (например, v,ты и т)
• Предполагается, что каждая переменная имеет определение в контексте или области действия. (В статическое одиночное присвоение форма, цепочки "использование-определение" являются явными, поскольку каждая цепочка содержит единственный элемент.)

Для переменной, например v, его объявление обозначено как V (курсивная заглавная буква), и для краткости его объявление обозначено как ${ displaystyle s (0)}$. Как правило, объявление переменной может находиться во внешней области (например, глобальная переменная ).

Определение переменной

Когда переменная, v, на LHS оператора присваивания, например ${ displaystyle s (j)}$, тогда ${ displaystyle s (j)}$ это определение v. Каждая переменная (v) имеет по крайней мере одно определение в своем объявлении (V) (или инициализация).

Использование переменной

Если переменная, v, находится справа от оператора ${ displaystyle s (j)}$, есть заявление, ${ Displaystyle s (я)}$ с я < j и ${ Displaystyle мин (J-I)}$, что это определение v и он используется в ${ displaystyle s (j)}$ (или, короче, когда переменная, v, находится справа от оператора ${ displaystyle s (j)}$, тогда v используется в заявлении ${ displaystyle s (j)}$).

Исполнение

Рассмотрим последовательное выполнение списка операторов, ${ Displaystyle s (я)}$, и то, что теперь можно наблюдать как вычисление в операторе, j:

• Определение в заявлении ${ Displaystyle s (я)}$ с я < j является живой в j, если он используется в заявлении ${ displaystyle s (k)}$ с k ≥ j. Множество живых определений в заявлении я обозначается как ${ Displaystyle А (я)}$ и количество живых определений как ${ Displaystyle | А (я) |}$. (${ Displaystyle А (я)}$ простая, но действенная концепция: теоретические и практические результаты в теория сложности пространства, сложность доступа (Сложность ввода / вывода), распределение регистров и местонахождение тайника эксплуатации основаны на ${ Displaystyle А (я)}$.)
• Определение в заявлении ${ Displaystyle s (я)}$ убивает все предыдущие определения (${ displaystyle s (k)}$ с k < я) для тех же переменных.

Пример выполнения def-use-chain

Этот пример основан на алгоритме Java для поиска gcd. (Не важно понимать, что делает эта функция.)

 1/** 2 * @param (a, b) Значения, используемые для вычисления делителя. 3 * @return Наибольший общий делитель a и b. 4 */ 5int gcd(int а, int б) {  6    int c = а; 7    int d = б;  8    если (c == 0) 9        возвращаться d;10    пока (d != 0) { 11        если (c > d)12            c = c - d;13        еще14            d = d - c;15    } 16    возвращаться c; 17}

Чтобы узнать все цепочки def-use для переменной d, выполните следующие действия:

1. Поиск при первом определении переменной (доступ для записи).

   В данном случае это "d = b"(l.7)

2. Выполните поиск при первом чтении переменной.

   В данном случае это "вернуться д"

3. Запишите эту информацию в следующем стиле: [имя переменной, для которой вы создаете цепочку def-use-chain, конкретный доступ для записи, конкретный доступ для чтения]

   В этом случае это: [d, d = b, return d]

Повторите эти шаги в следующем стиле: объедините каждый доступ для записи с каждым доступом для чтения (но НЕ наоборот).

Результат должен быть:

1 [d, d=б, возвращаться d] 2 [d, d=б, пока(d!=0)] 3 [d, d=б, если(c>d)] 4 [d, d=б, c=c-d] 5 [d, d=б, d=d-c]6 [d, d=d-c, пока(d!=0)] 7 [d, d=d-c, если(c>d)] 8 [d, d=d-c, c=c-d] 9 [d, d=d-c, d=d-c]

Вы должны позаботиться о том, чтобы переменная не изменилась со временем.

Например: от строки 7 до строки 13 в исходном коде, d не переопределяется / не изменяется. В строке 14, d может быть переопределен, поэтому вам нужно перекомбинировать этот доступ для записи на d со всеми возможными доступами для чтения, которые могут быть достигнуты. В этом случае актуален только код после строки 10. Например, линия 7 не может быть достигнута снова. Для вашего понимания вы можете представить 2 разные переменные d:

1 [d1, d1=б, возвращаться d1] 2 [d1, d1=б, пока(d1!=0)] 3 [d1, d1=б, если(c>d1)] 4 [d1, d1=б, c=c-d1] 5 [d1, d1=б, d1=d1-c]6 [d2, d2=d2-c, пока(d2!=0)] 7 [d2, d2=d2-c, если(c>d2)] 8 [d2, d2=d2-c, c=c-d2] 9 [d2, d2=d2-c, d2=d2-c]

В результате вы могли получить что-то вроде этого. Переменная d1 будет заменен на б

 1/** 2 * @param (a, b) Значения, используемые для вычисления делителя. 3 * @return Наибольший общий делитель a и b. 4 **/ 5int gcd(int а, int б) { 6    int c = а; 7    int d;  8    если (c == 0) 9        возвращаться б;10    если (б != 0) {11        если (c > б) {12            c = c - б;13            d = б;14        }15        еще16            d = б - c;17        пока (d != 0) { 18            если (c > d)19                c = c - d;20            еще21                d = d - c;22        }23    } 24    возвращаться c; 25}

Метод построения use-def (или же уд) цепь

Эта секция может быть сбивает с толку или неясно читателям. Пожалуйста, помоги нам прояснить раздел. Возможно обсуждение этого вопроса на страница обсуждения. (Январь 2007 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

1. Установить определения в заявлении ${ displaystyle s (0)}$
2. Для каждого я в ${ Displaystyle [1, п]}$, найдите живые определения, которые используются в инструкции ${ Displaystyle s (я)}$
3. Сделайте связь между определениями и использованием
4. Установите заявление ${ Displaystyle s (я)}$, как определение
5. Убить предыдущие определения

С помощью этого алгоритма достигаются две вещи:

1. А ориентированный ациклический граф (DAG) создается на основе использования и определений переменных. DAG определяет зависимость данных между операторами присваивания, а также частичный заказ (следовательно, параллелизм между утверждениями).
2. Когда заявление ${ Displaystyle s (я)}$ достигнут, есть список жить присвоения переменных. Если действует только одно задание, например, постоянное распространение может быть использован.