Категория:Потоковый анализ программ

Потоковый анализ является средством получения достоверной информации а поведении программы без ее реального исполнения. Извлекаемые из текста программы свойства — это глобальная информация о программе, которая не может быть получена ни пробными запусками программы, ни изучением ее отдельных фрагментов. Основной задачей потокового анализа является схематизация оптимизируемой программы — построение по программе моделирующей ее схемы, в которой важные для оптимизации свойства программы представлены о достаточной степенью точности. В процессе потокового анализа происходит извлечение определенных (схемных) семантических свойств программы; при этом используются семантика языка и текст анализируемой программы. Однако в отличие от «доказателей теорем» о программах потоковый анализ использует далеко не полную семантику языка и выводит существенно более простые свойства программы, чем свойство правильности или свойство пустоты. Техника потокового анализа — это «метод транзитивного замыкания», заметно уступающий по мощности таким общим методам доказательства теорем, как, например, «метод резолюций», но приводящий к существенно более эффективным алгоритмам.

Алгоритмы потокового анализа воспринимают программу (процедуру, модуль, программную систему и т.д.) в качестве входных данных, выявляют статическую информацию (вид которой зависит от конкретной решаемой проблемы) и возвращают полученную информацию в качестве результата. Такие алгоритмы используются при решении задач оптимизации, верификации, отладки, тестирования, распараллеливания, векторизации, параллельного программирования и во многих других приложениях. Они обеспечивают нахождение информации о программе или среде (окружении) без исполнения кода.

Традиционно потоковый анализ разделяют на анализ потока управления и анализ потока данных.

Основной задачей анализа потока управления является представление и структуризация множеств исполнений программы, а также нахождение свойств операторов и переходов в этих исполнениях и выбор порядка обработки операторов программы. Хотя все эти задачи и могут иметь самостоятельное значение, большинство из них возникает из нужд анализа потока данных, который, как правило, следует за анализом потока управления.

Анализ потока данных (как и потоковый анализ в целом) естественным образом разделяется на внутрипроцедурный и межпроцедурный анализы. Разные приложения связаны либо с низким (операторным) уровнем анализа, либо с более высоким уровнем, например, с анализом на уровне модулей или параллельных ветвей. Применяемая при разных видах анализа техника не различается существенно, но в них различны объекты, подвергающиеся анализу, а также они могут различаться по типу решаемых задач и/или охвату структурных свойств анализируемой программы. Внутрипроцедурный анализ имеет дело с операторами или линейными участками одной процедуры и с передачами управления между ними. Межпроцедурный анализ рассматривает процедуры программы и отношение обращения одной процедуры к другой.

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

Литература

• Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003.