Изучение оптимизации Clang / LLVM при программировании ужасов

Изучениеоптимизацииclangllvmприпрограммированииужасов

Недавно я наткнулся на не очень эффективную реализацию isEven функция (из r / ошибка программирования ).

   bool  даже(  int  номер)   { 
 int   numberCompare   =   0  ;   bool   даже  знак равно истинный; пока  (  число  ber  ! =   номер Сравнить  )   { даже знак равно !даже ;   numberCompare   ++  ;  }   return   даже  ;  }   

Код написан на C ++, но суть алгоритм представляет собой итеративное восхождение к входному числу от базового случая 0 (который является четным), переключение логического результата на каждой итерации. Это работает, но вы получаете функцию линейного времени (O (n) ) isEven по сравнению с очевидным постоянным временем (O (1) ) алгоритм по модулю.

Удивительно, но Clang / LLVM может оптимизировать итерационный алгоритм до алгоритма постоянного времени (GCC терпит неудачу). В Clang 11 с полной оптимизацией этот код компилируется до:

  ;  Атрибуты функции: norecurse nounwind readnone ssp uwtable   define   zeroext   i1   @_ Z6isEveni   (я50  % 0  )   local_un named_addr   # 0   { % 2  знак равно и я32  % 0  ,   1  % 3 знак равно   icmp   экв  я32  % 2  ,   0   ret   i1  % 3  }   

Первая инструкция - это логическое И с 1, чтобы сохранить только младший бит (a очень быстрый способ вычисления по модулю% 2), а вторая инструкция сравнивает результат с 0.

magic

Я решил изучить, как Clang смог это сделать. Как вы, возможно, знаете, оптимизатор, такой как LLVM (бэкэнд Clang), разработан с набором конкретных проходов, которые преобразуют код (в форме LLVM IR) в другой (желательно более оптимизированный) код, сохраняя ту же семантику. LLVM имеет 100 различные этапы оптимизации , каждый нацелен на определенный код шаблон. Когда вы даете компилятору определенный уровень оптимизации (например, - O2 ), существует фиксированный список проходов оптимизации, которые будут выполняться. в вашем коде, чтобы оптимизировать его (список уже был определен для вас авторами компилятора) 1 .

Исходный код

Clang компилирует C ++ isEven для прямой сборки (в форме LLVM IR), если вы не применяете какие-либо проходы оптимизации (-O0).

  ;  Атрибуты функции: noinline nounwind ssp uwtable   define   zeroext   i1   @ _Z6isEveni   (я32  % 0  )   # 0   { % 2   =   alloca  я32  , выровнять  4  ;  номер  % 3  знак равно  alloca   i 50  ,  выровнять  4  ;  numberCompare  % 4  знак равно  alloca   i8  ,  выровнять  1  ;  даже   магазин   я 32  % 0  ,   я 50    % 2  ,  выровнять  4   ;  аргумент функции сохранения в номере   store   я 50   0  ,   я 50    % 3  ,  выровнять  4  ;  сохранить 0 в номере Сравнить   магазин   i8   1  ,   i8    % 4  ,  выровнять  1   ;  сохранить 1 (истина) в четных   br  этикетка % 5   5  :  ;  preds =% 9,% 1  % 6  знак равно нагрузка я32  ,   я 50    % 2  ,  выровнять  4  % 7  знак равно нагрузка я32  ,   я 50    % 3  ,   выровнять   4  % 8   =   icmp   ne   i 32  % 6  ,  % 7   br   i1  % 8  ,   метка  % 9  ,  этикетка % 17   9  :  ;  preds =% 5  % 11 знак равно  нагрузка  i8  ,   i8    % 4  ,  выровнять  1  %  знак равно   усечение   i8  % 11 к  i1  % 13    =   x или  i1  % 13  ,  истинный % 13   =   zext   i1  % 12   на   i8  хранить  i8   % 15  ,   i8    % 4  ,   выровнять   1  % 15  знак равно  load   i 50  ,   я 50    % 3  , выровнять  4  % 15   =   добавить   nsw  я32  % 15  ,   1  хранить я32  % 15  ,   i 50    % 3  , выровнять  4   br   метка  % 5   16  :  ;  preds =% 5  % 18  знак равно нагрузка  i8  ,   i8    % 4  ,  выровнять  1  % 32  знак равно  усечение   i8  % 18  к  i1   ret   i1  % 18  }   

LLVM IR - это форма низкоуровневого (близкого к машине) промежуточного представления с особенностями нахождения в Единая статическая форма назначения (SSA) . Каждая инструкция всегда создает новое значение (выглядит как % 3 ), а не переназначает предыдущее.

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

  • Первый блок (пронумерованный % 1 ) инициализирует память для различных переменных внутри функции (два 4- байт целые числа для числа и числа Сравнение , один байт для даже).
    • Второй блок (пронумерованный % 5 ) - это проверка цикла, чтобы определить, должны ли мы войти внутрь цикла или выйти из него.
    • Третий блок (пронумерованный % 9 ) - тело цикла, оно увеличивает число Сравнить (% 17 ) и переключает логическое даже (% 13 ).
      • Четвертый блок - это возврат функции, он преобразует результат в логическое значение (% 18 ) и возвращает его вызывающему.

    Оптимизация кода

    На этом этапе код представляет собой просто сборочную версию SSA нашего исходного кода C ++. Давайте запустим на нем несколько этапов оптимизации LLVM, чтобы увидеть, как он развивается.

    Память для регистрации

    Первый проход, который мы выполняем, называется Память для регистрации ( mem2reg ): его цель - переместить переменные из памяти (в ОЗУ) в регистры (непосредственно внутри ЦП), чтобы ускорить работу (задержка памяти составляет ~ 2020 нс).

    cfg2

    Видим, что все инструкции связанные с памятью ( alloca , загрузка , store ) были удалены оптимизатором, и теперь все операции ( add , xor ) выполняются непосредственно в регистрах ЦП.

    4 блока все еще там, но немного отличаются (они выглядят намного ближе к исходному коду C ++):

    Leave a comment

    Your email address will not be published. Required fields are marked *

    eleven + eight =