Общие принципы оптимизации кода

Большинство современных компиляторов выполняют еще один этап компиля­ции – оптимизацию результирующей программы (или просто “оптимизацию”), чтобы повысить ее эффективность насколько это возможно.

Оптимизация программы – это обработка, связанная с переупорядочиванием и изменением операций в компилируемой программе с целью получения более эф­фективной результирующей объектной программы. Оптимизация выполняется на этапах подготовки к генерации и непосредственно при генерации объектного кода.

В качестве показателей эффективности результирующей программы можно использовать два критерия: объем памяти, необходимый для выполнения результи­рующей программы (для хранения всех ее данных и кода), и скорость выполнения (быстродействие) программы. Далеко не всегда удается выполнить оптимизацию так, чтобы удовлетворить обоим этим критериям. Зачастую сокращение необхо­димого программе объема данных ведет к уменьшению ее быстродействия, и на­оборот. Поэтому для оптимизации обычно выбирается либо один из упомянутых критериев, либо некий комплексный критерий, основанный на них. Выбор кри­терия оптимизации обычно выполняет непосредственно пользователь в настрой­ках компилятора.

Но даже выбрав критерий оптимизации, в общем случае практически невозмож­но построить код результирующей программы, который бы являлся самым ко­ротким или самым быстрым кодом, соответствующим входной программе. Дело в том, что нет алгоритмического способа нахождения самой короткой или самой быстрой результирующей программы, эквивалентной заданной исходной про­грамме. Эта задача в принципе неразрешима. Все, что можно сделать на этапе оптимизации, – это выполнить над заданной программой по­следовательность преобразований в надежде сделать ее более эффективной.

Чтобы оценить эффективность результирующей программы, полученной с по­мощью того или иного компилятора, часто прибегают к сравнению ее с эквива­лентной программой (программой, реализующей тот же алгоритм), полученной из исходной программы, написанной на языке ассемблера. Лучшие оптимизи­рующие компиляторы могут получать результирующие объектные программы из сложных исходных программ, написанных на языках высокого уровня, почти не уступающие по качеству программам на языке ассемблера. Обычно соотноше­ние эффективности программ, построенных с помощью компиляторов с языков высокого уровня, к эффективности программ, построенных с помощью ассемб­лера, составляет 1,1—1,3, т.е. объектная программа, построенная с помощью компилятора с языка высокого уровня, обычно содержит на 10 – 30 % больше ко­манд, чем эквивалентная ей объектная программа, построенная с помощью ас­семблера, а также выполняется на 10 – 30 % медленнее.

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

Принципиально различаются два основных вида оптимизирующих преобразова­ний:

· преобразования исходной программы (в форме ее внутреннего представления в компиляторе), не зависящие от результирующего объектного языка;

· преобразования результирующей объектной программы.

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

Второй вид преобразований может зависеть не только от свойств объектного языка, но и от архитектуры вычислительной системы, на которой будет выполняться результирующая программа. Так, например, при оптимиза­ции может учитываться объем кэш-памяти и методы организации конвейерных операций центрального процессора. В большинстве случаев эти преобразования сильно зависят от реализации компилятора и являются “ноу-хау” производите­лей компилятора. Именно этот тип оптимизирующих преобразований позволяет существенно повысить эффективность результирующего кода.

Методы преобразования программы зависят от типов синтаксических конструк­ций исходного языка. Теоретически разработаны методы оптимизации для мно­гих типовых конструкций языков программирования. Оптимизация может выполняться для следующих типовых синтаксических кон­струкций:

· линейных участков программы;

· логических выражений;

· циклов;

· вызовов процедур и функций;

· других конструкций входного языка.