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

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

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

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

Цель [ править ]

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

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

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

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

 интервал   х   =   0  ;       /* A */ 
  x   =   x   +   y  ;       /* B */ 
  /* 1, некоторые варианты использования x */ 
  int   x2   =   35  ;     /* C */ 
  /* 2, некоторые варианты использования 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) Значения, используемые для вычисления делителя. 
  * @return Наибольший общий делитель a и b. 
  */ 
 int   НОД  (  int   a  ,   int   b  )   {  
     int   c   =   a  ; 
      интервал   d знак   равно   б  ;  
      если   (  c   ==   0  ) 
         вернуть   d  ; 
      while   (  d   !=   0  )   {  
         если   (  c   >   d  ) 
             c   знак равно   c   -   d  ; 
          иначе 
             d   =   d   -   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  ,   если  (  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  ,   вернуть   d1  ]  
  [  d1  ,   d1  =  b  ,   while  (  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  -  c  ,   c  =  c  -  d2  ]  
  [  d2  ,   d2  =  d2  -  c  ,   d2  =  d2  -  c  ]

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

/** 
 * @param(a, b) Значения, используемые для вычисления делителя. 
  * @return Наибольший общий делитель a и b. 
  **/ 
 int   НОД  (  int   a  ,   int   b  )   { 
     int   c   знак равно   а  ; 
      интервал   д  ;  
      если   (  c   ==   0  ) 
         вернуть   b  ; 
      если   (  б   !=   0  )   { 
         если   (  c   >   б  )   { 
             c   знак равно   c   -   б  ; 
              д   знак равно   б  ; 
          } 
         Еще 
             d   =   b   -   c  ; 
          while   (  d   !=   0  )   {  
             если   (  c   >   d  ) 
                 c   знак равно   c   -   d  ; 
              иначе 
                 d   =   d   -   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