На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! Правила трёх "С"
Пожалуйста,
1. Соблюдайте правила Форума.
2. Слушайте советы Модераторов.
(например, http://forum.sources.ru/index.php?act=ST&f=7&t=80382 )
3. Сверяйтесь с учебником по Великому и Могучему
  
> Методики оптимизации в GCC. , Хм... "Теория", если кому понадобится...
    0. ПРЕДУПРЕЖДЕНИЯ.
    1. Собственно, не все, что здесь описано есть "оптимизация" в чистом виде.
    2. Ключи не указаны. В документации все довольно четко расписано. А переводить man... Ну, лишнее это, IMHO.
    Я рассматривал здесь общие принципы оптимизации, реализованные в gcc. Методики, стоящие за ключами
    оптимизации. IMHO, это важнее а для меня лично просто интереснее.
    3. Последствия опимизации могу быть фатальны для Вашего кода! Никогда не делайте предположений о том, как это
    работает. Гораздо проще опробовать это самому. См. п. 1.
    4. Не "затачивайте" оптимизацию строя предположения и о том, на каком процессоре это будет работать. Если Вы напишете
    код, который будет интересен не только Вам, но и начнет пользоваться популярностью, то он будет эксплуатироваться
    на различных платформах, а не только на той, для которой он писался. Более того! Сам по себе gcc это
    кросс-компилятор, генерирующий код под множество платформ и в связи с этим, несущий определенную избыточность.
    Учитывайте и это то же. Как, кстати, и ассемблер, применяемый для ассемблирования кода в проекте GNU --
    кросс-ассемблер...
    5. Останавливайтесь вовремя! "Слишком хорошо то же не хорошо" иначе, погружаясь в мелочи все глубже и глубже, в
    один не самый лучший день Вы поймете, что "шизофрения" для Вас это не диагноз, а способ Вашего мышления. А оно того
    не стоит. IMHO, стоит идти "срединным путем", сочетая разумную оптимальность кода с временными затратами на его
    получение.
    6. До проведения всех упражнений постарайтесь получить работоспособный и относительно безопасный код.
    Пропишите на бумаге хотя бы примерно свой агоритм. Чем тщательнее, тем лучше, т.к. писать все-таки лучше чем
    переписывать. Просто напишите то, что Вам нужно написать, получите рабочий код. Погоняйте его в SPLint'е. Уберите все, что
    Вам скажет lint. Вот теперь оптимизируйте до тех пор, пока Вы не удовлетворитесь или пока не выйдут сроки. Иначе я не
    удивлюсь, если Вас уволят за то, что Вы регулярно срываете все сроки отгрузки мегабайтов заказчику.
    7. Есть вещи, которые оптимизацией не правятся. Если Ваш алгоритм глюкав сам по себе, то хоть уоптимизируйтесь до
    посинения, результирующий код не станет ни шустрее, ни меньше. Подчас "перепланировка" алгоритма дает больше, чем
    самые свирепые извраты на почве "оптимизации".
    8. Я сознательно привожу английские термины, применяемые в теории компиляторов. Если Вы полны желания продолжить
    исследования, то они Вам как нельзя более к стати пригодятся. Я просто добавляю свои... "заметки на манжетах"...
    Более того! Я БМП когда какой шаг оптимизации когда исполняется, какая методика применяется при вызове того или иного
    ключа, хотя и догадываюсь... Когда-то "развлекался" с кодом как описано в п. #1. С тех пор, поняв тщетность
    попыток "выловить" десяток байт или пяток тактов, расслабился и получаю удовольствие от применения стандартных
    методик профилирования и оптимизации (включая вынесение "спорного" куска в отдельный модуль, получение его асмовского
    сырца и, опосля правки, компиляция этого куска как асм-кода).
    Лично мне довольно и того, что я знаю о том, что все это есть и это работает. Если кому интересно --
    полистайте сырцы на gcc... Ну а компиляторы я не разрабатываю. Неглубоко плаваю... Я даже не предендую на то, что
    указал абсолютно все методики оптимизации применяемые в gcc. Надеюсь, что кто-нибудь продолжит.

    1. Вариант проверки оптимизации.
    Берем один и тот же код. Получаем (-S -masm=att||intel -ключи оптимизации) ассемблерный сырец при
    различных ключах оптимизации и без них. Сравниваем. С ключами и без. Это мы делаем статический анализ кода.
    Динамический анализ. Начинаем "гонять" прогу в дебаггере. Смотрим на то, как она себя "ведет" при тех или иных
    условиях (ключах).

    За один день это не делается. За семестр в ВУЗе то же. Даже за год. Грамотная оптимизация это заклинания
    высшего порядка
    в "школе волшебников" gcc, т.к. на код должно выработаться "чутье". Интуиция, если угодно. Пока у Вас
    она не "прорежется", просто поэкономьте свои силы, иначе будете кидаться с дебаггером наперевес на все, что только
    исполняется (в особо запущеных случаях -- на все, что только движется). И лично мне знакомы люди, у которых она не
    прорежется никогда. Это уже клинические случаи, но и они бывают... :(

    2. Вздрогнули...
    Что делается при оптимизации. Всего-то ничего -- код перестраивается таким образом, чтобы в результате получить более
    простые инструкции процессора (выполняющиеся за меньшее число тактов), более полное использование регистров,
    минимизировать число обращений "память-память", "память-регистр", число ветвлений в коде, сам размер кода,
    минимизировать код пролога и эпилога функций и еще кое-чего, что указано ниже.

    Причем, попрошу заметить -- все это делается именно используя модель целевого процессора. Т.е. даже при том
    условии, что gcc это кросс-компилятор, все-равно при явном или неявном указании целевой платформы, gcc производит
    "наводку" результирующего кода именно на ту конкретную платформу, которую Вы "заказывали". Таким образом, даже
    при генерации кода на платформе i586 Вы имеете возможность получить вполне оптимальный код для SPARC или ARM...

    Собственно "оптимизация" включает в себя "подготовительные упражнения" и непосредственную оптимизацию кода. Давайте
    разделим мух и котлеты.

    2.1 "Подготовка".
    Это -- не оптимизация сама по себе. Это то, что делает gcc для подготовки соотв. шагов непосредственно оптимизации.

    Alias analysis.
    Здесь определяется можно ли достичь переменной одним или более путей. Если "да", то рассматриваем ее дальше. "Нет" -- см.
    ниже, т.к она нам не нужна.

    Live variable analysis.
    Просматривается область видимости каждой переменной в Вашем коде и, если она не нужна, то выдается предупреждение, но
    переменная не участвует в финальном коде.

    Value numbering.
    Используется на шаге оптимизации CSE.

    Constant folding.
    Вычисление значений констант, которые можно вычислить на момент компиляции. Учитывая то, что указатели, массивы,
    адреса должны быть определены в момент компиляции, то момент это важный.

    Caller-save optimizations.
    Размещение переменных в регистрах на момент вызова функции, при котором gcc делает попытку генерировать
    как можно меньше кода для записи переменных в регистры за счет ранее вычисленных значений.

    2.2 Оптимизация.
    Вот это то, что делает компил. для Вас и за Вас.

    Dead Code elimination.
    Если во время компиляции gcc определяет, что данный кусок кода не несет практической нагрузки, то gcc его просто
    выбросит. Причем код режется где угодно -- как в линейном теле программы, так и в циклах. Разновидность --
    "post reload flow analysis" см. ниже.

    Unreachable code elimination.
    На самом деле неиспользуемый код просто удаляется в результирующем коде. Генерируется предупреждение.

    Prologue/epilogue optimizations.
    Оптимизация именно "обертки" функций. Эта "обертка" генерируется gcc для каждой функции и включает в себя размещение
    аргументов вызова функции, сохранение/восстановление регистров. Здесь поддерживаются "delay slot scheduling" и
    "instruction scheduling", т.е. код пролога и эпилога рассматривается наряду с простым кодом и к нему применяются
    те же критерии оптимизации.

    Common Subexpression Elimination. CSE.
    Здесь gcc просматривает как локальный, так и глобальный код. Как в циклах, так и вне их. Суть в том, чтобы присвоить
    переменным их значения там, где это возможно, еще на этапе компиляции. Тогда, при исполнении код будет работать не
    над вычислением и присвоением этих значений, а над операциями с ними. Размер уменьшается, но есть опасность того,
    что при таком подходе gcc "не спросясь" присвоит какие-то значения каким-то переменным и все будет работать не так,
    как Вы заказывали. Используйте описание [i]volatile[/b] в определении тех переменных, относительно которых Вы не
    хотите чтобы gcc "фантазировал" по поводу их значений.

    Copy propagation и constant propagation.
    Определяются неиспользуемые присвоения значений переменным (в общем случае). Как локально, так и глобально. Если
    встречается неиспользуемые присвоения, то генерируется предупреждение и выбрасывается из кода. Дает экономию памяти
    и ускорение исполнения.

    Loop unrolling.
    Попытка развернуть цикл и перейти к более простой линейной организации программы. Ускорение за счет сокращения
    операций инкремента/декремента и сравнения.

    Local register allocation.
    Локальное размещение регистров призвано уменьшить оперций копирования регистр-регистр и оптимизировать использование
    регистров внутри одного локального блока (цикла, функции). Производится попытка использовать значение, содержащееся
    а регистре более одного раза в различных местах именно этого блока.

    Global register allocation.
    То же, что и выше, но попытка использовать уже сохраненное в регистре значение более чем в одном базовом блоке
    (функции или цикле).

    Loop inversion.
    Инверсия цикла при определенных условиях дает лучший результат. Дело в том, что gcc пытается перестроить
    цикл так, чтобы происходило не увеличение переменной и сравнение ее с некоторым значением, а уменьшение
    ее до нуля. В результате возможно уменьшение результирующего кода и ускорение программы.

    Constant equivalence handling for muliply-set pseudos.
    Вообщем-то идея аналогична работе с регистрами, но здесь работа идет с переменными и gcc пытается использовать где
    можно известные значения.

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

    If expression simplifications.
    Это целое семейство оптимизаций по числу вариантов применения оператора if (зависит от того что и с чем Вы сравниваете
    и что делаете после сравнения). Во-первых, gcc поддерживает все семейство, во-вторых, пытается упростить применение
    оператора за счет перевода кода к более простым формам и, как следствие, генерации в результате более оптимальных
    форм. Эта оптимизация так же применяется для поиска неиспользуемых фрагментов кода -- "dead code elimination".

    Post reload flow analysis.
    Оптимизация после оптимизации. Опосля всех переназначений регистров, перегрузки, gcc проверяет не появились ли
    где участки неиспользуемого кода и, если появились, то и их выбрасывает.

    Branch optimizations.
    GCC supports elimination of branches to branches, branches around branches, etc etc.

    Algebraic Simplifications & Reassociation.
    Это вид оптимизиции целочисленной математики. Т.е. gcc применяя алгебраические преобразования, пытается упростить
    арифметические выражения, перестроить их и сгенерировать более эффективный код. К примеру, i = i + 1; будет
    превращено в i++; или в ++i; (по усмотрению gcc). Последние варианты ассемблируются проще.

    Scalar Replacement of Aggregates.
    Здесь основное дело в том, что gcc пытается представить поля структур, объединений как уникальные переменные и
    применить к ним те же правила, которые применяются при оптимизации переменных. Включая так же то, что gcc пытается
    разместить их в регистрах, съэкономив тем самым на операциях копирования типа "память-регистр".

    Conditional move/predication.
    Компил. пытается перейти от сложных команд ассемблера, занимающих по нескольку машинных циклов при пересылке
    ряда значений, к более простым (в идеале, к mov), занимающим по одному циклу машинного времени для каждого
    значения. Здесь стоит учитывать разницу между RISC и CISC системами. Код подрастает в размере, но выполняется
    быстрее. Причем, gcc выполняет проверку самой по себе возможности и целесообразности такого перехода. Сравните
    размеры программ для RISC и CISC архитектур. В среднем, прога для RISC будет процентов на 10-20 "длиннее".

    More reload inheritance.
    Компил. пытается как-то по-эффективнее "пристроить" в памяти переменные, которым не нашлось место в регистрах
    целевого процессора на этапе компиляции. Я знаю что это есть, но как это работает... Воочию не наблюдал.
    Компилятором не работаю. Вполне возможно, что на другом процессоре, этип переменным нашлось бы место в регистрах.
    Если устроитесь на работу компиляторм, то всенепременно поговорите с процессорами...

    Local spilling in reload.
    Компил. пытается использовать регистры целевого процессора для хранения переменных настолько полно, насколько
    это вообще возможно. Это достигается тем, что компил. пытается сохранить в регистре значение как можно
    дольше без его (значения) перезаписи в регистре. В результате -- сокращение (в идеале) пересылок
    "память-регистр". Вообще, генерация кода для замены одного значения на другое в регистре, называется
    "register reloading". Этот код так же подвергается оптимизации наряду со всем остальным.

    Instruction scheduling.
    Планирование инструкций. Помогает на тех процах, которые используют механизм ковейеризации кода. На тех процах,
    которые этот механизм не используют, генерится просто более "гладкий" и "прямой" (с минимумом инструкций условного
    или безусловного перехода) код. Поддерживается оптимизация внутри одного блока, внутри модуля, внутри всей программы
    в целом. Строка поиска в Google -- "sheduling algorithms".

    Leaf routine optimizations.
    Опять-таки этот алгоритм оптимизации призван более оптимально распределить пространство регистров целевого проца
    и сгенерировать более эффективный код пролога/эпилога при вызовах функций.

    Code straightening.
    GCC supports code straightening by replacing conditional branch sequence with straight-line code, conditional
    moves, predicated instructions, etc.

    Loop Invariant Code Motion.
    Это часть оптимизации циклов. Делается попытка извлечь из тела цикла неиспользуемые в цикле выражения, переменные,
    присвоения, etc. Вытаскивается только то, что в цикле не несет смысловой нагрузки. По этой причине аккуратнее
    планируйте циклы, если можно.

    2.2.1 Специфичные моменты.
    Как я уже говорил и выше и не раз, gcc -- кросс-компилятор. По этой причине он учитывает ряд специфичных моментов,
    призванных оптимизировать код на различных платформах.

    PowerPC scheduling prologue & epilogue.
    Все то же, что и для "prologue/epilogue optimizations", но вот только для платформы PowerPC.

    Comparison optimizations.
    GCC пытается преобразовать несколько операций сравнения в более простые. Для PowerPC.

    "regmove" optimizations.
    Попытка уменьшить число используемых регистров при пересылке значений типа "память-регистр" для ia32, Hitachi SH,
    m68k, Hitachi H8 series... Релиз зависит от платформы.

    Delay slot scheduling.
    Для процессоров, поддерживающих технологию "branch/call delay slots". Определяется реализацией целевого "камня".

    Machine idioms & instruction combining.
    Если поддерживается архитектурой процессора и gcc "знает" об этом, то производится попытка объединить несколько
    инструкций в одну или несколько, но более простые.
      В общем, на первый взгляд, топик толковый. Кратко, и главное, "не мудрствуя лукаво". Что хотелось бы добавить для дзэнствующих на конкретном семействе процессоров.

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

      Конечно же, Вы вылизали сишный код до такого блеска, что он сияет, как тропическое солнце, проследовали всем "кроссплатформным" советом, но все же вас что-то будоражит.

      В этом случае, конечно, выход прост. Делается ассемблерная вставка, которая проверяется соответствующим #ifdef'ом на предмет "излюбленной" архитектуры. В результате ваше ухищрение будет работать на избранном вами процессоре, что никак не затронет остальные архитектуры.

      Конечно, не 100% кроссплатформенно, но дает возможность полной (в пределах видимости программиста) оптимизации под то, что знаешь лучше всего, и не создает ситуации под названием "vendor/platform lock-in".

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

      Это так, не чтоб опровергнуть, а штришок для полноты картины.
        Хэх! Для полноты картины сейчас вот готовлю тему по профилировке кода. Это, IMHO, одна из основных вещей при оптимизации...
        И, кстати, ASMProgrammer абсолютно прав! Но только не забудьте еще в доке на свою программу все вот такие вот "моменты", чтоб потом кто-то не ломал голову и не матерился... :D

        Кстати, здесь же попробую добавить -- Вы можете не только прописать инлайн через директивы, но и выделить такой критичный код в отдельный модуль (модули) и ассемблировать их потом в составе проекта именно как ассемблерные. Только один минус -- получится, что для работы с этим кодом понадобится генерировать прологи/эпилоги для функций или мудровать с naked-функциями. Зависит от того, что и как Вы хотите сделать. Хотя, просто, это дополнение и не более...

        Уффф... Еще и здесь же. Если ассемблер, применяемый в Вашем проекте тот же, что Вы можете применить на целевой платформе, то тогда просто в доке можете написать что асм нужен вот такой-то. Как пример. В QNX, M$ Windows, так и в Linux есть NASM. Можно использовать его, тогда голову меньше ломать.

        PS За мной еще доки по профилировке, отладке. Готовлю. Теперь, IMHO, понятна моя "задержка"? :D
          Верно. Для всяких нюансов с платформами позволю добавить:

          autoconf, automake, autogen - ваши друзья.
          0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
          0 пользователей:


          Рейтинг@Mail.ru
          [ Script execution time: 0,0193 ]   [ 15 queries used ]   [ Generated: 29.03.24, 10:52 GMT ]