Лекция 1

Понятие оптимизирующего

преобразования.

Виды оптимизаций.

Оптимизирующие компиляторы.

Задачи оптимизации

«хорошие» программы

• Хорошая программа должна работать как можно

быстрее и занимать как можно меньше памяти

Необходимое условие:

Задачи оптимизации

«хорошие» программы

• Хорошая программа должна работать как можно

быстрее и занимать как можно меньше памяти • И при этом работать правильно Необходимое условие:

Задачи оптимизации «хорошие» оптимизаторы • Хорошая программа должна работать как можно быстрее и занимать как можно меньше памяти • И при этом работать правильно оптимизатор P. P P1 (лучше) Таких оптимизаторов не бывает Замечание: никакие оптимизаторы не помогут программе, использующей неадекватные структуры данных и алгоритмы Задачи оптимизации «хорошие» оптимизаторы • Хорошая программа должна работать как можно быстрее и занимать как можно меньше памяти • И при этом работать правильно оптимизатор P1 (не хуже) P. P Таких оптимизаторов тоже не бывает.

Вопрос: почему компиляторы называют оптимизирующими, Необходимое условие:

а не пессимизирующими?

Задачи оптимизации «хорошие» оптимизаторы • Хорошая программа должна работать как можно быстрее и занимать как можно меньше памяти • И при этом работать правильно Зато бывают такие оптимизаторы:

оптимизатор P. P P1 (лучше) ! если таких программ немало, оптимизатор имеет Необходимое условие:

право на существование Задачи оптимизации «хорошие» оптимизаторы Примеры (нехороших оптимизаторов):

P2 (существенно медленнее P1) 1. P P2 (работает не так как P1) 2. P 3. человек-обфускатор исходного текста Необходимое условие:

Вопрос: в чем проблема оптимальности?

Задачи оптимизации критерии оптимальности Пусть PATHS (P) – множество путей (последовательностей исполняющихся операторов) программы P, начинающихся в первом и заканчивающихся в последнем операторе.

Path (P|d) PATHS (P) – путь при входных данных d Программы P1 и P2 эквивалентны (P1 P2 ), если при любых (допустимых) входных данных, они завершаются и вырабатывают одинаковый результат Задачи оптимизации критерии оптимальности Обозначим Time (p) - время исполнения p, p PATHS (P) Критерий оптимальности (производительность):

Q имеет лучшую производительность чем P (PQ), a.Time (Path(Q|a)) Time (Path (P|a) ) f.Time (Path (Q|f)) < Time (Path (P|f)) Замечание. Порядок может быть частичным и не содержать наибольшего элемента Задачи оптимизации алгоритмические проблемы Утверждение Следующие проблемы неразрешимы:

• эквивалентность двух программ • существование оптимальной программы, эквивалентной данной Следствие Оптимальная программа либо не существует, либо не существует алгоритма для ее нахождения.

Следствие Можно искать цепи P... P(n) P(n+1) Задачи оптимизации спекулятивные критерии оптимальности HOTPATHS(P) PATHS (P) – множество "горячих" путей (считаем, что они исполняются с высокой вероятностью) HOTDATA(P) =def {d | Path (P|d) HOTPATHS(P)} (данные, приводящие к исполнению горячих путей) Спекулятивный критерий оптимальности:

Q имеет спекулятивно лучшую производительность чем P (P Q), если P|HOTDATA (P) Q|HOTDATA (P) Задачи оптимизации спекулятивные критерии оптимальности Взяв программу P1, оптимизатор строит (конечную) последовательность {Pn} со свойствами k. Pk Pk+1 PkPk+ Пусть PQ. z – контрпример, если Time (Path(Q|z)) > Time (Path(P|z)) Выбирать спекулятивные оптимизации нужно аккуратно; желательно:

[ Time (Path(Q|z)) / Time (Path(P|z)) ] min В погоне за производительностью спекулятивными оптимизациями занимаются:

• компиляторы • среды исполнения (generational GCs) операционные системы (file prefetching, spin locks, thread/process scheduling) процессоры (pipelining, out-of-order execution, branch prediction, cache population) Разработчики компиляторов должны это учитывать Задачи оптимизации • Хорошая программа должна работать как можно быстрее и занимать как можно меньше памяти • И при этом работать правильно • И быть разработана за разумное время ! time to market Необходимое условие:

Задачи оптимизации • Хорошая программа должна работать как можно быстрее и занимать как можно меньше памяти • И при этом работать правильно • И быть разработана за разумное время ! time to market • И работать надежно Необходимое условие:

Задачи оптимизации • Хорошая программа должна работать как можно быстрее и занимать как можно меньше памяти • И при этом работать правильно • И быть разработана за разумное время ! time to market • И работать надежно • И быть легко читаемой, модифицируемой, и т.д.

(это неполный список, но для наших целей – достаточный) Необходимое условие:

Задачи оптимизации • Хорошая программа должна работать как можно быстрее и занимать как можно меньше памяти • И при этом работать правильно • И быть разработана за разумное время ! time to market • И работать надежно • И быть легко читаемой, модифицируемой, и т.д.

Необходимое условие Необходимое условие:

использование языка высокого уровня ! Нужен оптимизирующий компилятор Возможности оптимизации 1. абстракция управления (циклы, ветвления, процедуры) 2. абстракция данных (типы данных, локальные/глобальные переменные) 3. объектная-ориентированность (1 и 2 одновременно) 4. надежность (проверки времени исполнения, asserts) 5. читаемость кода (символические константы, кол-во переменных, …) Возможности оптимизации Компилятор совместно со средой исполнения способен улучшить (ускорить):

1. управление памятью (faster object allocation/reclaimation) 2. синхронизацию потоков or no thread synchronization, no atomic ops) 3. обработку исключений Возможности оптимизации 1. распределение регистров процессора (практически непосильная задача для человека) 2. выборка кода ("маленькие шедевры" компилятора) 3. перестановка команд (instruction scheduling, cache-concsious optimizations) 4. векторизация,...

Замечание: с развитием процессоров этот список будет расти Анализ – сбор информации о свойствах программы • большинство оптимизаций невозможны без анализа • зачастую, анализ - намного более сложная задача чем сама оптимизация (преобразование программы) Консервативность анализа – использование более грубых предположений при невозможности доказать некоторое свойство Виды анализа и оптимизаций Зависимость от исходного языка Языково-независимые вычисление константных выражений Языково-зависимые раскрытие виртуальных вызовов Виды анализа и оптимизаций Зависимость от целевой архитектуры Машинно-независимые вынос инвариантного кода из цикла Машинно-зависимые использование режимов адресации IA-32 при генерации кода учет особенностей CISC или RISC Виды анализа и оптимизаций Область применения Локальные оператор или лин. последовательность операторов (вычисление операции с конст. аргументами) Внутрипроцедурные операторы одной процедуры (удаление недостижимого кода) Виды анализа и оптимизаций Область применения Межпроцедурные операторы нескольких процедуры (открытая подстановка, вычисление свойств операции вызова другой процедуры) Внутримодульные операторы всех процедур одного модуля/класса (вычисление свойств приватных переменных, полей, и процедур) Виды анализа и оптимизаций Область применения Глобальные (обычно анализ) вся программа (вычисление свойств полей/глобальных переменных и формальных параметров процедур, построение иерархии наследования классов) Замечание: в реализациях некоторых языков "глобальное вИдение" возможно только в момент сборки исполняемого файла (Link-Time Optimization) Видов анализа и оптимизаций Источник информации Статические информацию предоставляет анализ (без исполнения) Адаптивные информация получена путем профилировки исполнения Гибридные (самые могучие) используется и статический анализ и динамические проверки/анализ Примеры оптимизаций int getX(){retun x;} int getX(){retun x;} int getY(){retun y;} int getY(){retun y;} a.getX()*a.getY(); getX(a)*getY(a);

/* virtual calls */ } Примеры оптимизаций Открытая подстановка (inlining) int getX(){return x;} int getX(){return x;} int getY(){return y;} int getY(){return y;} int square(){ int square(){ Примеры оптимизаций протяжка присваиваний (copy propagation)...

xz = 911;

a = b;

Примеры оптимизаций удаление "мертвого" кода (dead code elimination) xz = 911;

for (int i=1;...) /* nothing */ a[i] = b[i+1];

void foo() {goo();} void foo() {goo();} while (true){}; while (true){};

Примеры оптимизаций взрыв объектов (object explosion) int foo(int a){ int foo(int a){ Примеры оптимизаций удаление частичной избыточности (PRE) a = b*3;

Примеры оптимизаций удаление общих подвыражений (CSE) a[k+1] = b[i]; a[k] = temp_0;

Примеры оптимизаций Вынос инвариантного кода (invar. code motion) int a[];

int b[];

...