УДК: 004.4'416

К вопросу об оптимальной линеаризации программ

Н. И. Вьюкова, ст. науч. сотр., e-mail: niva@niisi.msk.ru, B. А. Галатенко, д-р физ.-мат. наук, ст. науч. сотр., e-mail; galat@niisi.msk.ru, C.В. Самборский, ст. науч. сотр., НИИ системных исследований РАН, г. Москва

Представлены два метода оптимальной линеаризации программ с точки зрения минимизации числа переходов. Первый из них относится к простому случаю, когда принимаются во внимание только безусловные переходы. Эта задача может быть сформулирована как поиск оптимального покрытия путями вершин графа, являющегося подграфом графа потоков управления (Control Flow Graph — CFG). Рассматриваемый подграф (Fall Through Graph — FTG) включает только дуги, соответствующие безусловным переходам, и соединяемые ими вершины. Метод заключается в построении оптимального покрытия FTG путями и циклами с последующим размыканием циклов. Сложность алгоритма O(N), где N — число вершин FTG.

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

Ключевые слова: оптимизация переходов, линеаризация программы, покрытие путями

Стр. 3–8