Достигающие определения
Достигающие определения (англ. Reaching definition) — одна из наиболее распространенных и полезных схем потока данных. Зная, где именно в программе может быть определена каждая переменная x при достижении потоком управления каждой точки p, можно получить много информации об этой переменной. В частности, компилятор может выяснить, является ли x константой в точке p, а отладчик может сообщить о возможном использовании в точке p не инициализированной переменной x[1].
Значение термина
Мы говорим, что определение d достигает точки p, если существует путь от точки, непосредственно следующей за d, к точке p, такой, что d не уничтожается вдоль этого пути. Мы уничтожаем определение переменной x, если существует иное определение x где-то вдоль пути. Интуитивно понятно, что, если определение d некоторой переменной x достигает точки p, то d может быть местом, где последний раз определяется значение x, используемое в p.
Определением переменной x является инструкция, которая присваивает или может присваивать значение переменной x. Анализ программы должен быть консервативным: если мы не знаем, присваивает ли инструкция s значение переменной x, то мы должны считать, что она может сделать это, т.е. что переменная x после инструкции s может иметь либо исходное значение, бывшее у неё до инструкции s, либо новое значение, созданное s[1].
Пример
Для примера рассмотрим следующий код:
d1 : y := 3 d2 : x := y
где определение d1 достигает определение d2. Однако, в следующем примере:
d1 : y := 3 d2 : y := 4 d3 : x := y
определение d1 не достигает определения d3, потому что определение d2 уничтожает определение переменной y в d1.
Примечания
Литература
- Альфред Ахо, Моника Лам, Рави Сети, Джеффри Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е издание. — М.: «Вильямс», 2008. — 1184 с. — 1500 экз. — ISBN 978-5-8459-1349-4.