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

    Копаясь в дебрях 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?
    Поделиться публикацией
    Комментарии 36
      +6
      позновательно, буду ждать второй части
        +2
        да, я тоже узнол много нового :)
        +1
        Устранение общих подвыражений порадовало. Только в сложных программах, наверное, сложно делать подобные оптимизации.

        А как обстоят дела по отношению к циклам? Например, будет ли цикл for(i=0; i<2; i++) развёрнут в линейную структуру? При генерации Schematic из VHDL такое точно может происходить
          +3
          По оптимизациям циклов будет отдельная часть )
            +1
            В gcc, если мне не изменяет память, есть опция -funroll-loops, которая может разворачивать циклы. Более хитрая оптимизация — swing modulo scheduling, которая умеет выносить из цикла пролог и эпилог с целью уменьшить зависимость по данным внутри одной итерации цикла. А вообще, с циклами много всего есть, поэтому это действительно тема для отдельной части.
            +4
            > Устранение/Исключение недоступного кода

            Недоступный код — unreachable code. Понятие dead code шире — это любой код, который можно удалить не повлияв на результат выполнения програмы. Например, вычисление значения, которое потом не используется нигде. Некоторые бенчмарки грешат тем, что их вычислительная часть по сути dead code.

            > А теперь представьте сколько эта оптимизация экономит процессорного времени в рамках большой вычислительной программы.
            Устранение общих подвыражений уменьшает количество вычислений, но увеличивает количество живых переменных и тем самым давление на регистры. Поэтому если регистров мало, а выражние простое (стоит меньше чем скажем чтение из памяти), то получается CSE может легко повредить и может надо наоборот делать rematerialization в местах использования.
              +1
              Да, вы правы, пожалуй я смешал unreachable code elimination и dead code elimination

              Устранение общих подвыражений уменьшает количество вычислений, но увеличивает количество живых переменных и тем самым давление на регистры. Поэтому если регистров мало, а выражние простое (стоит меньше чем скажем чтение из памяти), то получается CSE может легко повредить и может надо наоборот делать rematerialization в местах использования.
              разве? это для простоты в коде представлено так, как у меня, но на деле, во внутреннем представлении (например, SSA) CSE значительно уменьшит использование регистров, а не увеличит
                +2
                Скажем так, в моем комментарии было пропущено слово «может», может увеличить, может уменьшить. Представьте допустим, что у нас код:

                for (int i = 0; i < N; i++) s += calc(i, j);
                


                мы выполняем открытую подстановку, а потом CSE. после чего оказывается, что в точке где к s прибавляется результат calc у нас живы: i, j, s, tmp1, tmp2, tmp3 (можно считать на x86 регистры почти кончились), а в оригинальном коде живы i, j, s, a, b.

                Может так оказаться, что только a * b элиминировать (живы i, j, s, tmp3) выгоднее.

                Важно тут не количество переменных (в IR действительно a * b уже само по себе сидит во временной переменной), важно количество живых переменных в каждой отдельно взятой точке программы и удлиннение промежутков жизни для временных переменных.
                • НЛО прилетело и опубликовало эту надпись здесь
                +4
                Статья очень интересная, но примеры слишком очевидные и простые. Поэтому ждем второй части, с оптимизациями посложнее.
                  +2
                  Спасибо за статью, очень интересно. Будет так же интересно почитать что-нибудь на тему ран-тайм оптимизаций в динамических языках, если это конечно возможно :)
                    +1
                    >> Устранение общих подвыражений
                    эта оптимизация(как и туча других) была бы гораздо полезнее, если бы в выражениях могли бы участвовать не только локальные переменные, но и вызовы функций. А для этого нужно уметь определять является ли функции чистыми. Либо дать возможность программисту давать хинт компилятору по этому поводу… ИМХО такая фича весьма и весьма помогла бы и в деле ускорения программ, и вообще в понятности кода.
                      +1
                      В некоторых компиляторах есть такие хинты. Например __pure в Keil CC.
                        +1
                        __attribute__((pure)) в gcc, начиная с gcc3.
                        +5
                        Вспомнилась замечательная история про оптимизацию xD: ithappens.ru/story/2959
                          +3
                          Кстати, очень часто компиляторы не только удаляют unreachable code, но и ещё и ругаются на него ворнингами. А в специфичных случаях — ошибками.
                          Ибо наличие такого кода обычно сигнализирует о том, что программист где-то ошибся.
                            0
                            А если просто подключена библиотека с функциями? Не все же используются.
                              0
                              А в таких случаях выкидываются сразу функции целиком, и этим занимается обычно линковщик, а не компилятор.
                              Кроме случае whole program optimization, как я понимаю. Но это отдельная непростая тема :)
                                0
                                Кстати да — какой вообще статус у whole program optimization. По мне так это именно то что должно координально уменьшить размер программы а также ускорить ее. Но насколько я понял в GCC это все еще в зачаточном состоянии. Это так?
                            +1
                            Было бы интересно узнать, насколько успешно разные компиляторы справляются с этими и другими оптимизациями.
                              +1
                              Конкретно с этими очень успешно.
                                +1
                                Это ж основы основ, классика :)
                              • НЛО прилетело и опубликовало эту надпись здесь
                                  +1
                                  ну это может быть 16-битная архитектура, а может быть ошибка автора :)
                                    +1
                                    да, спасибо, действительно, я ошибся… сначала «p» был просто int'ом. Код изменил, а размер поправить забыл.
                                    +1
                                    > Тогда для нахождения числовых выражений и подвыражений достаточно искать соседние узлы дерева, содержащие числовые значения, причём ТОЛЬКО числовые значения.
                                    Это не совсем так, эта оптимизация обычно еще учитывает ассоциативность и коммутативность операций.
                                    Например, 16 + a + 2, может в дереве выглядеть как plus(16, plus(a, 2)).
                                      0
                                      спасибо, очень меткое замечание, я немного исправил формулировку.
                                      0
                                      Вопрос к аудитории — есть ли интерес к более подробному описанию классических и не очень оптимизаций? Если да, то почему — для общего развития, применимо к работе или что-то ещё?

                                      Иногда просыпается желание написать что-то подобное, но не совсем понятно кому это может быть интересно и на чём делать акценты, насколько углубляться в ньюансы и т.д.
                                        0
                                        Есть, для общего развития :) Можно начать с чего-то общего. Если людям будет интересно, наверняка в комментариях будут просьбы описать что-то конкретное.
                                          0
                                          Если это будет не пересказ соответствующих глав Dragon Book своими словами, а что-то там не затронутое, то интересно.
                                          +1
                                          В DCE было бы интересней последней строкой печатать y, а не x — можно продемонстрировать многопроходность оптимизации.

                                          Кстати попробуйте для рисования графов yEd — многие хвалят.
                                            +1
                                            Спасибо за статью. Интересный материал и хорошая компоновка текста в статье — одно удовольствие читать. Некоторым авторам этого не достает!
                                              0
                                              «как бы не улучшала оптимизация характеристики программы, она обязательно должна сохранять изначальный смысл программы при любых условиях. Именно поэтому, например, в GCC существуют различные уровни оптимизации»

                                              По моему уровни оптимизации существуют не поэтому — в идеале любая оптимизация должна сохранять смысл программы (в gcc это к сожалению не так, и встречаются опции, которые меняют результат, в основном правда при вычислениях с плавающей запятой).
                                              Есть отличная статья про уровни оптимизации.
                                                +1
                                                Супер, очень интересна эта тема, особенно проект LLVM. Спасибо за статью. Очень хотел бы увидеть продолжение.
                                                  0
                                                  <зануда>
                                                  В самой первой оптимизации (Constant folding) самое первое AST кажется неприавльно нарисовано. Разве не должно быть так:
                                                  - Объявление переменной: int a
                                                  - Присваивание =
                                                          - a
                                                          - Умножение *
                                                                  - 32
                                                                  - 32
                                                  

                                                  Ну то есть присванивание тоже оператор и у него два операнда, которые должны быть его сыновьями в дереве.
                                                  </зануда>
                                                    0
                                                    Кстати, во всех AST так. Простите за занудство.

                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                  Самое читаемое