Кратко

  • Frances E. Allen превратила оптимизацию из набора приёмов ускорения в дисциплину анализа путей управления, определений и использований.
  • Интервалы, достигающие определения и живость дают условные статические факты; это не трасса выполнения и не гарантия отсутствия неопределённого поведения, гонок или численной неустойчивости.
  • Работу Allen следует описывать рядом с вкладом John Cocke, Reese T. Prosser, E. S. Lowry, C. W. Medlock, Kenneth Kennedy и коллективов Stretch, Harvest и ACS.

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

Frances E. Allen помогла заменить догадку «похоже, безопасно» вычислимым утверждением. История IBM сообщает, что в 1957 году она пришла в компанию преподавать FORTRAN новым научным сотрудникам. Затем участвовала в Stretch–Harvest и экспериментальном проекте Advanced Computing Systems. В 2006 году ACM присудила ей премию Тьюринга за основополагающий вклад в теорию и практику оптимизирующих компиляторов. Она стала первой женщиной-лауреатом.

Фраза «Allen изобрела оптимизацию» слишком широка. Более важный результат её работ — язык для точного ответа: что компилятор установил, при каких предпосылках и насколько далеко распространяется вывод.

Граф возможных путей

В статье 1970 года Control Flow Analysis базовые блоки представлены узлами, а возможные переходы управления — ориентированными рёбрами. Базовый блок в модели представляет линейную последовательность с одним входом и выходом.

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

Allen организует граф с помощью интервалов. Интервал с заголовком h — максимальный подграф с единственным входом, где каждый замкнутый путь содержит h. Узел добавляется, когда все его непосредственные предшественники уже вошли в интервал; затем процесс повторяется над сокращённым графом. Такая иерархия позволяет анализировать циклы без перебора всех путей.

Статья аккуратно распределяет авторство. Ранние матрицы связности и введение доминирования отнесены к Reese T. Prosser, развитие доминирования — к E. S. Lowry и C. W. Medlock, конструкция интервала — к John Cocke. Достижение Allen заключалось не в стирании этих оснований, а в их превращении в цельный инженерный метод.

«Может достигнуть» не значит «произошло»

В 1976 году Allen и Cocke опубликовали A Program Data Flow Analysis Procedure. Процедура вычисляет определения, которые могут достичь каждого узла, и определения, живые на каждом ребре.

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

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

Метод использует упорядоченные интервалами рёбра и битовые векторы, обрабатывая приводимые и неприводимые графы в одной схеме. Kenneth Kennedy указан как автор алгоритма живости, Richard Stasko — идей структуры данных; отмечены также Ullman, Hecht, Kildall, Schaefer, Schwartz и другие исследователи.

Каталог не обещал глобальный оптимум

В A Catalogue of Optimizing Transformations Allen и Cocke систематизировали устранение общих подвыражений, перемещение кода, понижение стоимости операций и удаление избыточных вычислений. Авторы называют каталог неполным и отмечают, что слово «оптимизация» неточно, когда общий оптимум не определён. Основное внимание уделено времени выполнения, затем памяти.

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

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

Сохранение семантики не доказывает правильность целого

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

Такое ограничение — достоинство. Полезный анализ формулирует проверяемый вывод: при данном графе, определениях, использованиях и семантических условиях отношение выполняется. Риск появляется, когда организация сокращает эту фразу до зелёного значка «правильно».

История Allen требует той же точности. IBM называет её проектировщиком и языковым связующим звеном Stretch–Harvest и ключевой фигурой компилятора ACS. Профиль IEEE Computer Society связывает отчёт Program Optimization 1966 года, интервалы и каталог. Профиль John Cocke в ACM сохраняет его самостоятельный вклад. Команды аппаратуры, языков и компиляторов превратили абстракции в работающие системы.

Наследие Allen — не всезнающий компилятор, а компилятор, способный строго сообщить, что именно он доказал.

Источники