Pull to refresh

Оптимизации в компиляторах. Часть 1

Reading time 7 min
Views 31K
Копаясь в дебрях LLVM, я неожиданно обнаружил для себя: насколько всё же интересная штука — оптимизация кода. Поэтому решил поделиться с вами своими наблюдениями в виде серии обзорных статей про оптимизации в компиляторах. В этих статьях я попытаюсь «разжевать» принципы работы оптимизаций и обязательно рассмотреть примеры.
Я попытаюсь выстроить оптимизации в порядке возрастания «сложности понимания», но это исключительно субъективно.
И ещё: некоторые названия и термины не являются устоявшимися и их используют «кто-как», поэтому я буду приводить несколько вариантов, но настоятельно рекомендую использовать именно англоязычные термины.


Вступление

(совсем немного теории о типах оптимизаций, которую можно пропустить)


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

Идём дальше: оптимизации бывают машинно-независимыми (высокоуровневыми) и машинно-зависимыми (низкоуровневыми). Смысл классификации понятен из названий, в машинно-зависимых оптимизациях используются особенности конретных архитектур, в высокоуровневых оптимизация происходит на уровне структуры кода.

Оптимизации также могут классифицироваться в зависимости от области их применения на локальные (оператор, последовательность операторов, базовый блок), внутрипроцедурные, межпроцедурные, внутримодульные и глобальные (оптимизация всей программы, «оптимизация при сборке», «Link-time optimization»).

Чую, что вы сейчас уснёте, давайте закончим на этом порцию теоиии и приступим уже к рассмотрению самих оптимизаций…


Constant folding

(Свёртывание/Свёртка констант)


Самая простейшая, самая известная и самая распространённая оптимизация в компиляторах. Процесс «свёртки констант» включает в себя поиск выражений (или подвыражений), включающих ТОЛЬКО константы. Такие выражения вычисляются на этапе компиляции и в результирующем коде «сворачиваются» в вычисленное значение.

Рассмотрим пример (придуманный на ходу из головы, абсолютно синтетический, тривиальный, абстрактный, ничего не значащий, далёкий от реальности, etc… и все примеры будут такими):
До оптимизации После оптимизации
#include <stdlib.h>

int main(int argc, char **argv)
{
    struct point
    {
        int x;
        int y;
    } p;
    int a = 32*32;
    int b = 32*32*4;
    long int c;
    //
    c = (a + b) * (4*4*sizeof(p) - 2 + 32);
    return 0;
}
#include <stdlib.h>

int main(int argc, char **argv)
{
    struct point
    {
        int x;
        int y;
    } p;
    int a = 1024; // Свёрнуто из 32 * 32
    int b = 4096; // Свёрнуто из 32 * 32 * 4
    long int c;
    // 16 = 4*4, 30 = -2 + 32
    c = (a + b) * (16*sizeof(p) + 30); 
    return 0;
}
Вроде бы получилось отлично и оптимизация выполнена, но на самом деле компиляторы поумнели и идут дальше. Дело в том, что в данном случае размер (sizeof) структуры "p" тоже является константой, и компиляторы об этом знают, поэтому получаем:
Разворачиваем sizeof Завершаем свертывание
... c = (a + b) * (16*8 + 30); ...
... c = (a + b) * 158; ...
Олично… Несколько тактов процессора эта оптимизация нам определённо экономит.
Всё довольно просто, если наш код представлен в виде Абстрактного Синтаксического Дерева (AST). Тогда для нахождения числовых выражений и подвыражений достаточно искать узлы дерева одного уровня (то есть имеющие общего предка), содержащие только числовые значения. Тогда значение в вышестоящем узле (родительском) можно будет свернуть. Для наглядности рассмотрим на простом примере дерева для одного из выражений, возьмём наше "int a = 32*32;":



То есть рекурсивным обходом нашего дерева AST мы можем свернуть все подобные константные выражения. Кстати пример с числами опять же упрощён, вместо операций с числами вполне могут быть операции со строками (конкатенация) или операции со строками и числами (аналог python'овского "'-' * 10") или константами любых других типов данных, поддерживаемых исходным языком программирования.


Constant propagation

(Распространение констант)


Эта оптимизация обычно всегда описывается в комплекте с «Constant folding» (ведь они взаимодополняют друг друга), но это всё же отдельная оптимизация. Процесс «распространения констант» включает в поиск выражений, которые будут постоянными при любом возможном пути выполнения (до использования данного выражения) и их замену на эти значения. На деле всё проще, чем звучит — возьмём всё тот же пример, который мы уже использовали, но с учётом, что мы уже прошлись по нему оптимизацией «Constant folding»:
До оптимизации После оптимизации
#include <stdlib.h>

int main(int argc, char **argv)
{
    struct point
    {
        int x;
        int y;
    } p;
    int a = 1024; 
    int b = 4096;
    long int c;
    //
    c = (a + b) * 94; 
    return 0;
}
#include <stdlib.h>

int main(int argc, char **argv)
{
    struct point
    {
        int x;
        int y;
    } p;
    int a = 1024; 
    int b = 4096;
    long int c;
    // c = (1024 + 4096) * 94
    c = 481280; 
    return 0;
}
То есть в нашей изначальной программе вобщем-то не надо было делать никаких вычислений. А что произошло? Всё просто… Так как значения переменных "a" и "b" никак не могут измениться между их объявлением и использованием в вычислении значения "c", то компилятор сам может подставить их значения в выражение и вычислить его.
То есть компилятору необходимо для каждого выражения проверять, всегда ли его значение будет постоянным (а точнее — может ли оно измениться). Попробуем изобразить схематично:



Допустим, что компилятор при очередном проходе оптимизации обнаруживает использование переменных "a" и "b". Как видно из схемы, после объявления переменной "a" в блоке A и переменной "b" в блоке B, ни одна, ни другая переменная не могут изменить значение в последующих блоках (A,B,C) перед их использованием. Этот случай тривиален, так как вся программа линейна и представляет из себя так называемый Базовый блок (BB). Но алгоритм определения «изменяемости» переменной в базовом блоке это ещё далеко не всё. Программа может включать условные конструкции, циклы, безусловные переходы и т.д. Тогда для определения «изменяемости» переменной необходимо построить направленный граф с базовыми блоками в вершинах, рёбра — передача управления между базовыми блоками. Такой граф называется Графом потока управления (CFG) и применяется для осуществления многих оптимизаций. В таком графе можно определить все базовые блоки, которые необходимо пройти от инициализации переменной до её использования и определить для каждого блока, может ли в нём измениться значение переменной. В случае невозможности его изменения, компилятор легко может заменить её значение константой.
«Constant propagation» и «Constant folding» обычно прогоняются несколько раз, пока не перестанут вносить какие-либо изменения в код программы.


Copy propagation

(Распространение копий)


А это ещё один спутник двух предыдущих оптимизаций, практически брат-близнец «Constant Folding», выполняющий очень похожую работу, но позволяет избавится от лишних (промежуточных) присваиваний переменных, подменяя в выражениях промежуточные переменные. Гораздо нагляднее это будет на простейшем примере:
До оптимизации После оптимизации
int calc(int x, int y)
{
  int a = x;
  int b = y;
  return a * a + b * b;
}
int calc(int x, int y)
{
  //
  //
  return x * x + y * y;
}


Dead Code Elimination (DCE)

(Устранение/Исключение недоступного кода)


Очень простая, но, к сожаленью, мало чего улучшающая в плане производительности оптмизация. Всё просто: код, который никак не может быть использован в программе, можно удалить. Давайте посмотрим пару примеров «мёртвого груза кода»:
До оптимизации После оптимизации
#include <stdlib.h>
#include <stdio.h>

int main(int argc, char **argv)
{
  while(true)
  {
    printf("Hi, I'm very hardy code =) !");
  }
  printf("Hi, I'm dead code =( !");
  return 0;
}
#include <stdlib.h>
#include <stdio.h>

int main(int argc, char **argv)
{
  while(true)
  {
    printf("Hi, I'm very hardy code =) !");
  }
  // Here there was a dead code
  return 0;
}
Как видите, строка "printf("Hi, I'm dead code =( !");" является недостижимой при любых обстоятельствах: либо программа выполняется бесконечно, либо завершается «насильно». Давайте ещё пару примеров:
До оптимизации После оптимизации
#include <stdlib.h>
#include <stdio.h>

int main(int argc, char **argv)
{
  int y = 0;
  int x;
  scanf("%d",  &x);
  if (x >= 10)
  {
    printf("x >= 10 \n");
    return 0;
  }
  else
  {
    printf("x < 10 \n");
    return 0;
  }
  printf("x = %d \n", &x);
}
#include <stdlib.h>
#include <stdio.h>

int main(int argc, char **argv)
{
  // Here there was a dead code
  int x;
  scanf("%d",  &x);
  if (x >= 10)
  {
    printf("x >= 10 \n");
    return 0;
  }
  else
  {
    printf("x < 10 \n");
    return 0;
  }
  // Here there was a dead code
}
Думаю здесь тоже всё ясно без комментариев: строка "printf("x = %d \n", &x);" также, как и в предыдущем примере, недостижима при любом пути исполнения программы, а объявленная в первой строки функции main переменная y никак не используется.
Ну и последний пример для этой оптимизации:
До оптимизации После оптимизации
#include <stdlib.h>

int sum(int x, int y)
{
  return x + y;
}
int sub(int x, int y)
{
  return x - y;
}

int main(int argc, char **argv)
{
  return sum(2, 2);
}
#include <stdlib.h>

int sum(int x, int y)
{
  return x + y;
}
//
//
//
//

int main(int argc, char **argv)
{
  return sum(2, 2);
}
И опять всё просто: функция sub не вызывается ни в одном месте программы, поэтому от неё можно избавиться.
С одной стороны «мёртвый код» в программе очень легко находится с помощью графа потока управления. Если в программе есть мертвый код, то граф будет либо несвязным и можно «выбросить» отдельные фрагменты графа. С другой стороны необходимо учитывать адресную арифметику и множество других ньюансов — не всегда можно однозначно определить, является ли код «мёртвым».


Common Sub-Expression Elimination (CSE)

(Устранение общих подвыражений)


Очень полезная и «красивая» оптимизация. Заключается в следующем: если вы используете расчёт какого либо выражения два или более раз, то его можно рассчитать один раз, а затем подставить во все использующие его выражения. Ну и куда мы без примера:
До оптимизации После оптимизации
int calc(int x, int y)
{
  int a = (x + y) * (x - y) - x * y;
  int b = x * (x + y) - y * (x - y);
  return (a * b + x - y) * (a * b + x + y);
}



int calc(int x, int y)
{
  int tmp1 = x + y;
  int tmp2 = x - y;
  int a = tmp1 * tmp2 - x * y;
  int b = x * tmp1 - y * tmp2;
  int tmp3 = a * b;
  return (tmp3 + tmp2) * (tmp3 + tmp1);
}
Да, этот оптимизированный код выглядит гораздо страшнее и более громоздко, но он избавлен от «лишних вычислений» (однократно сложение и вычитание x и y вместо трёхкратных, однократное перемножение a и b вместно двухкратного). А теперь представьте сколько эта оптимизация экономит процессорного времени в рамках большой вычислительной программы.



P.S. На самом деле я хотел приводить схемки для каждой из оптимизаций, но извиняйте, меня хватило на рисование всего двух.
P.P.S. Подскажите УДОБНЫЙ сервис для рисования схемок и графов.
P.P.P.S. To be continued?
Tags:
Hubs:
+106
Comments 36
Comments Comments 36

Articles