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

В информатике цепочка определения использования (или цепочка 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, some uses of x */
 x = 35;       /* C */
 /* 2, some more uses of x */

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

 int x = 0;    /* A */
 x = x + y;    /* B */
 /* 1, some uses of x */
 int x2 = 35;  /* C */
 /* 2, some uses of x2 */

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

Настройка [ править ]

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

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

Для переменной, такой как 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 имеет использование оператора at $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 для поиска gcd . (Не важно понимать, что делает эта функция.)

/**
 * @param(a, b) The values used to calculate the divisor.
 * @return The greatest common divisor of a and b.
 */
int gcd(int a, int b) { 
    int c = a;
    int d = b; 
    if (c == 0)
        return d;
    while (d != 0) { 
        if (c > d)
            c = c - d;
        else
            d = d - c;
    } 
    return c; 
}

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

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

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

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

 [d, d=b, return d] 
 [d, d=b, while(d!=0)] 
 [d, d=b, if(c>d)] 
 [d, d=b, c=c-d] 
 [d, d=b, d=d-c]
 [d, d=d-c, while(d!=0)] 
 [d, d=d-c, if(c>d)] 
 [d, d=d-c, c=c-d] 
 [d, d=d-c, d=d-c]

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

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

 [d1, d1=b, return d1] 
 [d1, d1=b, while(d1!=0)] 
 [d1, d1=b, if(c>d1)] 
 [d1, d1=b, c=c-d1] 
 [d1, d1=b, d1=d1-c]
 [d2, d2=d2-c, while(d2!=0)] 
 [d2, d2=d2-c, if(c>d2)] 
 [d2, d2=d2-c, c=c-d2] 
 [d2, d2=d2-c, d2=d2-c]

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

/**
 * @param(a, b) The values used to calculate the divisor.
 * @return The greatest common divisor of a and b.
 **/
int gcd(int a, int b) {
    int c = a;
    int d; 
    if (c == 0)
        return b;
    if (b != 0) {
        if (c > b) {
            c = c - b;
            d = b;
        }
        else
            d = b - c;
        while (d != 0) { 
            if (c > d)
                c = c - d;
            else
                d = d - c;
        }
    } 
    return c; 
}

Метод построения цепочки use-def (или ud ) [ править ]

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

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

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

Ссылки [ править ]

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

[kennedy-1] Кеннеди, Кен (январь 1978 г.). «Цепочки определения использования с приложениями». Компьютерные языки . 3 (3): 163–179. дои : 10.1016/0096-0551(78)90009-7 .

[duct-2] Сирл, Аарон; Гоф, Джон; Абрамсон, Дэвид (2003). «DUCT: интерактивный инструмент цепной навигации по определению использования для относительной отладки». arXiv : cs/0311037 .

[leiss-3] Лейсс, Эрнст Л. (26 сентября 2006 г.). Помощник программиста в анализе алгоритмов . ЦРК Пресс. ISBN 978-1-4200-1170-8 .

[1]

[2]

[3]

v т и Оптимизация компилятора
Basic block	Peephole optimization Local value numbering
Loop	Automatic parallelization Automatic vectorization Induction variable Loop fusion Loop-invariant code motion Loop inversion Loop interchange Loop nest optimization Loop splitting Loop unrolling Loop unswitching Software pipelining Strength reduction
Data-flow analysis	Available expression Common subexpression elimination Constant folding Dead store elimination Induction variable recognition and elimination Live-variable analysis Use-define chain
SSA-based	Global value numbering Sparse conditional constant propagation
Code generation	Instruction scheduling Instruction selection Register allocation Rematerialization
Functional	Deforestation Tail-call elimination
Global	Interprocedural optimization
Other	Bounds-checking elimination Compile-time function execution Dead-code elimination Expression templates Inline expansion Jump threading Partial evaluation Profile-guided optimization
Static analysis	Alias analysis Array-access analysis Control-flow analysis Data-flow analysis Dependence analysis Escape analysis Pointer analysis Shape analysis Value range analysis