Cтраница 2
Опять-таки, не входя в детали, рассмотрим возможные пути укрупнения операторов. Если рассматривать хорошо организованные и, так сказать, реальные программы, то в них всегда можно заметить такие участки, где вычисления идут подряд, не прерываясь передачами управления. Эти участки так и называют линейными участками программы. При абстрактном рассмотрении программ в виде графа переходов соответствующие цепочки вершин называются линейными компонентами графа. Более точно, линейной компонентой называется такая цепочка вершин графа, которая не содержится целиком ни в какой другой цепочке. Возьмем любую такую компоненту и разделим все относящиеся к ней полюсы на три категории. Мы назовем аргументами линейной компоненты I такие аргументы а, для которых существуют маршруты информационных пар вида ( г, а), содержащие хотя бы один оператор, не. [16]
В фрагменте исходной программы, написанной на языке Фортран, с помощью меток операторов, которым передается управление в операторах условного и безусловного переходов, можно достаточно легко определить отношения следования для его линейных участков. В то же время линейный участок 6 для фрагмента исходной программы, написанной на языке ПЛ / 1, не снабжен меткой. Задача определения отношений следования между линейными участками программ, составленных на языке ПЛ / 1, еще более усложняется, когда конструкции THEN и ELSE содержат группы DO или блоки BEGIN, которые, в свою очередь, могут содержать операторы цикла и условные операторы. [17]
Критические значения - предикаты, влияющие на маршруты, - во многих случаях не являются фиксированными, а формируются при сопоставлении нескольких переменных. При этом образование предикатов может происходить во всей области изменения каждой из переменных, например когда они оказываются равными или отличаются на некоторую величину. Формирование предикатов, определяющих выбор маршрутов исполнения программы, происходит в результате вычислений на линейных участках программы. Как уже отмечалось, эти участки в среднем невелики и содержат порядка 10 команд. [18]
Тривиальное решение задачи состоит в-изображении каждого оператора языка ( машинной команды, строки или любого фрагмента, признаваемого единицей языка) отдельной вершиной. При этом две вершины смежны, если между соответствующими операторами есть передача управления. Точнее, оператор, после исполнения которого производится передача управления, представляется началом дуги; оператор, на который передается управление - концом дуги, а каждая передача управления - дугой. При таком подходе размер графа сильно растет за счет появления длинных цепочек вершин, соответствующих линейным участкам программ. Они могут быть представлены одной вершиной. Более сложные подходы к построению управляющих графов состоят в выделении различного рода квазилинейных участков, как это было сделано, например, при разработке транслятора с языка альфа. Это возможно, если нет необходимости тщательно учитывать внутреннюю структуру отдельных частей программы. [19]