Средства разработки приложений


Механизм контрольных точек - часть 2


Ячейка l является элементом DE(G?), если l «мертвая» во всех операторах сохранения контрольных точек в G?.

Ячейка памяти l является ячейкой только-для-чтения в операторе S, если l

use[S]. Поэтому l
RO(G?) тогда и только тогда, когда l
gen[S] для всех S в G?.

Эти определения консервативны, поскольку они ищут все возможные пути через граф потока управления, тогда как некоторые из них могут никогда не достигнуть выполнения в программе.

Анализ «живых» переменных обычно выражается в виде уравнений потока данных, по одному на каждое состояние в программе. Мы дадим уравнение потока данных, которое позволит нам определить DE(G?) и RO(G?) для каждого подграфа G? в программе. Каждое из этих уравнений может быть решено обычным итеративным методом.

Для достижения нашей цели уравнение потока данных характеризуем его функцией обновления. Такая функция ассоциируется с каждым состоянием S. Определим in[S] как множество мертвых переменных в точке непосредственно перед блоком S, а out[S] – такое же множество в точке, непосредственно следующей за блоком S.

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

out[S] = ?S? in[S?]

in[S] = FS,

где out[S] = ?S? DEAD[S?] – это пересечение множества мертвых переменных для всех состояний S?, которые являются преемниками S в G, а FS – это функция обновления, которая в нашем случае равна FS = out[S]

gen[S] – use[S] и свидетельствует о переменных, которые мертвы непосредственно перед S и тех переменных, которые стали мертвыми после S, плюс о тех, в которые производилась запись в состоянии S, минус любые ячейки, с которых происходило чтение в S.

При следующем запуске эти массивы и параметры загружаются, и по ним полностью восстанавливается контекст прерванной задачи.


Начало  Назад  Вперед