Метод нумерации значений и его использование в оптимизациях программ
| Вид материала | Документы |
- Практических: 0 Лабораторных:, 21.53kb.
- Задача прогнозирования значений временного ряда чаще всего предполагает использование, 148.11kb.
- Ствии с российской системой нумерации и планом нумерации сетей связи единой сети электросвязи, 496.86kb.
- Квалификационные программы для выполнения нового вида деятельности и/или подтверждения, 3326.09kb.
- Семинар Метод полной математической индукции. (напоминание), 14.86kb.
- Объяснение значений слов детям средней группы. Объяснение значений слов, 99.64kb.
- Вопросы по методике преподавания начального курса математики для переводного экзамена, 21.04kb.
- Уроках математики, 104.99kb.
- Форекс-стратегии Использование rsi, 95.81kb.
- Осадчей Ольги Валерьяновны, директора, 445.39kb.
МЕТОД НУМЕРАЦИИ ЗНАЧЕНИЙ
И ЕГО ИСПОЛЬЗОВАНИЕ В ОПТИМИЗАЦИЯХ ПРОГРАММ
Филиппов А.Н.
E-mail: filipov@mcst.ru
Скалярные оптимизации являются наиболее широко используемыми в современных оптимизирующих компиляторах. Широта их применения обусловлена полной независимостью от платформы, на которой код будет исполняться. Многие из этих оптимизаций представляются довольно очевидными, например удаление мертвого кода, распространение констант и сбор общих подвыражений. В последнем случае на этапе компиляции устанавливается тот факт, что ряд операций вырабатывает одинаковый результат, и часть из них удаляется как избыточные.
Для более эффективного сбора общих подвыражений можно предварительно провести анализ множества всех операций внутреннего представления, разбив его на классы эквивалентности (конгруэнтности). Тогда можно будет говорить, что операции вырабатывают один и тот же результат в том и только в том случае, если они принадлежат одному классу. Этот метод получил название метода нумерации значений (value numbering).
Процедура проведения нумерации значений предполагает наличие некоторых надстроек над промежуточным представлением программы, важнейшими из которых являются граф управления и форма статического единственного присваивания (SSA-форма). Граф управления представляет собой направленный связный граф, вершинам которого соответствуют линейные участки, а дугам – управляющие связи между ними, отображающие передачу управления. Что касается SSA-формы, то ключевым свойством программы, представленной в ней, является то, что любая переменная может быть определена только один раз. Для достижения этого требования в точках схождения потока данных размещаются Ф-узлы, которые представляют из себя псевдооперацию, выбирающую среди множества значений переменной нужное. Тогда разбиение множества операций на классы эквивалентности существенно упрощается: для установления факта эквивалентности двух операций достаточно доказать эквивалентность их аргументов.
Наличие у компилятора результатов анализа методом нумерации значений открывает широчайшие возможности для дальнейшей оптимизации программы, так как позволяет работать не с операциями промежуточного представления, а с классами эквивалентности. Одним из наиболее эффективных преобразований, использующих нумерацию значений, считается удаление частичных избыточностей (partial redundancy elimination), которое сочетает в себе сбор общих подвыражений, вынос инвариантного кода из циклов и перемещение вычислений из часто исполняемых участков программы в менее часто исполняемые.
Данный подход был реализован в составе оптимизирующего компилятора для платформы Эльбрус, что позволило получить ощутимый положительный эффект уменьшения времени исполнения кода.