Использовать-определить цепочку

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

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

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

Цель

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

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

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

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

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

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

Настраивать

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

Операторы помечаются с использованием следующих соглашений: ⁠ ⁠ $s(i)$ , где i — целое число в ⁠ ⁠ $[1,n]$ ; а n — количество операторов в базовом блоке.
Переменные выделены курсивом (например, v , u и t ).
Предполагается, что каждая переменная имеет определение в контексте или области действия. (В статической форме одиночного присваивания цепочки use-define являются явными, поскольку каждая цепочка содержит один элемент.)

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

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

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

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

Если переменная v находится в правой части оператора ⁠ ⁠ $s(j)$ , то существует оператор ⁠ ⁠ $s(i)$ с i < j и ⁠ ⁠ $\min(j-i)$ , который является определением v и имеет применение в ⁠ ⁠ $s(j)$ (или, короче говоря, когда переменная v находится в правой части оператора ⁠ ⁠ $s(j)$ , то v имеет применение в операторе ⁠ ⁠ $s(j)$ ).

Исполнение

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

Определение в операторе ⁠ ⁠ $s(i)$ с i < j является активным в j , если оно используется в операторе ⁠ ⁠ $s(k)$ с k ≥ j . Набор активных определений в операторе i обозначается как ⁠ ⁠ $A(i)$ , а количество активных определений как . ( ⁠ ⁠ — простая, но мощная концепция: теоретические и практические результаты в теории сложности пространства , сложности доступа (сложности ввода-вывода), распределении регистров и эксплуатации локальности кэша основаны на ⁠ ⁠ .) $|A(i)|$ $A(i)$ $A(i)$
Определение в операторе ⁠ ⁠ $s(i)$ отменяет все предыдущие определения ( ⁠ ⁠ $s(k)$ с k < i ) для тех же переменных.

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

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

/*** @param(a, b) Значения, используемые для вычисления делителя.* @return Наибольший общий делитель a и b.*/int gcd ( int a , int b ) {       int c = a ;    целое число d = b ;     если ( с == 0 )    вернуть д ;  пока ( д != 0 ) {      если ( с > г )    с = с - d ;     еще д = д - с ;     }  вернуть c ;  }

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

Поиск первого определения переменной (доступ для записи).
В данном случае это " d=b" (л.7)
Поиск первого прочтения переменной.
В данном случае это " return d"
Запишите эту информацию в следующем стиле: [имя переменной, для которой вы создаете def-use-chain, конкретный доступ для записи, конкретный доступ для чтения]
В данном случае это:[d, d=b, return d]

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

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

 [ d , d = b , вернуть d ]     [ d , d = b , в то время как ( d != 0 )]    [ d , d = b , если ( c > d )]    [ д , д = б , с = с - д ]    [ д , д = б , д = д - в ]   [ d , d = d - c , пока ( d != 0 )]    [ d , d = d - c , если ( c > d )]    [ д , д = д - с , с = с - д ]    [ д , д = д - с , д = д - с ]

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

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

 [ d1 , d1 = b , вернуть d1 ]     [ d1 , d1 = b , в то время как ( d1 != 0 )]    [ d1 , d1 = b , если ( c > d1 )]    [ d1 , d1 = b , c = c - d1 ]    [ d1 , d1 = b , d1 = d1 - c ]   [ d2 , d2 = d2 - c , пока ( d2 != 0 )]    [ d2 , d2 = d2 - c , если ( c > d2 )]    [ d2 , d2 = d2 - с , с = с - d2 ]    [ d2 , d2 = d2 - с , d2 = d2 - с ]

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

/*** @param(a, b) Значения, используемые для вычисления делителя.* @return Наибольший общий делитель a и b.**/int gcd ( int a , int b ) {      int c = a ;    целочисленный d ;   если ( с == 0 )    вернуть б ;  если ( б != 0 ) {     если ( с > б ) {     с = с - б ;     г = б ;   } еще г = б - в ;     пока ( д != 0 ) {      если ( с > г )    с = с - d ;     еще д = д - с ;     } }  вернуть c ;  }

Метод построенияиспользование-определение(илиуд) цепь

Установите определения в операторе ⁠ ⁠ $s(0)$
Для каждого $i$ в ⁠ ⁠ $[1,n]$ найдите живые определения, которые используются в утверждении ⁠ ⁠ $s(i)$
Установите связь между определениями и вариантами использования.
Установите утверждение ⁠ ⁠ $s(i)$ как определение утверждения
Удалить предыдущие определения

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

На основе использования и определений переменных создается направленный ациклический граф ( DAG). DAG определяет зависимость данных между операторами присваивания, а также частичный порядок (следовательно, параллелизм между операторами).
Когда оператор ⁠ ⁠ $s(i)$ достигнут, есть список живых назначений переменных. Если, например, только одно назначение живое, может использоваться распространение констант .

Ссылки

^ Кеннеди, Кен (январь 1978). «Цепочки определений использования с приложениями». Computer Languages . 3 (3): 163–179. doi :10.1016/0096-0551(78)90009-7.
^ Сирл, Аарон; Гоф, Джон; Абрамсон, Дэвид (2003). «DUCT: интерактивный инструмент навигации по цепочке «Определение-Использование» для относительной отладки». arXiv : cs/0311037 .
↑ Лейсс, Эрнст Л. (26 сентября 2006 г.). Помощник программиста по анализу алгоритмов . ЦРК Пресс. ISBN 978-1-4200-1170-8.