DU-цепь ( англ. DU chain, def-use chain, definition-use chain — цепь «определение — использование» ) — структура данных , используемая в (англ.) ( для нахождения мест использования определяемой переменной или нахождения всех мест определений значений переменных, входящих в выражение . Эта структура ставит в соответствие каждому определению переменной список операторов, достижимых из определения и содержащих переменную. Аналогично, UD-цепь ( англ. UD chain, use-def chain, use-definition chain ) содержит для каждого случая использования переменной места её определения, из которых место использования достижимо .

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

Одним из улучшений идеи UD/DU-цепочек является форма статического одиночного присваивания ( англ. Static Single Assignment, SSA ). SSA-форма является промежуточным представлением, при котором каждая переменная имеет только одно определение в программе. Следует заметить, что (статическое) определение может находиться в цикле, выполняемом много раз, поэтому SSA не следует путать с .

Примечания

Литература

• Khedker, U. and Sanyal, A. and Sathe, B. Data Flow Analysis: Theory and Practice. — CRC Press, 2009. — P. 185-. — ISBN 9780849332517 .
• Appel, A.W. and Ginsburg, M. . — Cambridge University Press, 2004. — P. . — ISBN 9780521607650 .
• Appel, A.W. Modern Compiler Implementation in ML. — Cambridge University Press, 2004. — P. 427-. — ISBN 9781107268548 .