Конференции ИВТ СО РАН

Тезисы докладов

В настоящее время получил широкое распространение и практическое применение класс языков, поддерживающий обработку исключительных ситуаций. Это, бесспорно, весьма мощное средство, но вместе с тем общепризнано, что обработка исключительных ситуаций является одим из "наименее структурных" средств программирования. То есть она достаточно нетривиально выражается на языке классических структурных операторов, таких, как if-then-loop-while-break. Кроме того, обработка исключительных ситуаций обладает свойством нелокальности, что делает ее особенно полезной для задач реального программирования, но вместе с тем значительно усложняет реализацию на машинном языке. Еще одним отличительным свойством языков с обработкой исключительных ситуаций является обилие мест в программе, в которых возможно возникновение исключения. Это ведет к значительному усложнению семантики программы по сравнению с программой на обычном структурном языке, предназначенной для аналогичных целей.

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

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

В настоящее время наиболее широко используемыми являются представления, построенные на основе графа потока управления (control flow graph, CFG). Непосредственное применение принципов построения CFG к программам на языках, поддерживающих обработку исключений, приводит к занимающим большой объем памяти и сложным структурно внутренним представлениям. Прямое следствие этого - значительное увеличение требований к ресурсам и времени работы алгоритмов компилятора (многие из которых имеют сложность больше линейной).

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

Широко известным представителем класса компактных представлений является факторизованный граф потока управления (factored control flow graph, FCFG), описанный в работе [1]. Однако, это представление обладает рядом недостатков, главными из которых являются сложность структуры самого представления и алгоритмов его анализа, а также жесткая ориентированность на семантику конкретного языка (в данном случае языка Java).

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

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

[1] Jong-Deok Choi, David Grove, Michael Hind and Vivek Sarkar. Efficient and Precise Modeling of Exceptions for the Analysis of Java Programs. 1999 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'99).

Дополнительные материалы:

ZIP (428 kb)

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск