Часть 1
Часть 2
Часть 3
Люди иногда спрашивают, почему код, скомпиливанный в LLVM иногда генерирует сигналы SIGTRAP, когда оптимизация была включена. Покопавшись, они обнаруживают, что Clang сгенерировал инструкцию «ud2» (подразумевается код X86) — то же, что генерируется __builtin_trap(). В этой статье рассматривается несколько вопросов, касающихся неопределённого поведения кода на C и того, как LLVM его обрабатывает.
В этой статье (первой из трёх) мы попытаемся объяснить некоторые из этих вопросов, чтобы вы могли лучше понять связанные с ними компромиссы и сложности, и возможно, изучить немного больше тёмные стороны С. Мы выясним, что C не является «высокоуровневым ассемблером», как многие опытные программисты на C (особенно те, кто сфокусирован на низком уровне) предпочитают думать, и что C++ и Objective-C напрямую унаследовали множество таких проблем.
В языках программирования LLVM IR и C есть концепция «неопределённого поведения». Неопределённое поведение, это широкая тема с множеством нюансов. Лучшее введение в тему, которое я нашёл, это пост в блоге Джона Реджера. Краткая суть этой прекрасной статьи состоит в том, что многие вещи, кажущиеся осмысленными в C, на самом деле имеют неопределённое поведение, и это является источником множества багов в программах. Более того, каждая конструкция с неопределённым поведением в С имеет лицензию на реализацию (компиляцию и выполнение) кода, который может отформатировать ваш жёсткий диск, и делать ещё более плохие вещи совершенно неожиданно. И снова, я настоятельно рекомендую прочесть статью Джона.
Неопределённое поведение существует в С-подобных языках по той причине, что разработчики С хотели, чтобы он был предельно эффективным низкоуровневым языком программирования. Как противоположность, языки типа Java (и многие другие «безопасные» языки программирования) избегают неопределённого поведения, потому что они хотят безопасного и воспроизводимого поведения, не зависящего от реализации, и готовы пожертвовать производительностью, чтобы достичь этой цели. Хотя ничто из этого не является вашей целью, если вы программируете на С, вы на самом деле должны понимать, что такое неопределённое поведение.
Перед тем, как погрузиться в детали, стоит напомнить, что позволяет компилятору достичь высокого быстродействия на большом диапазоне C-приложений, при том, что нет никакой волшебной пули. На самом высоком уровне, компилятор генерирует быстрый код за счёт того, что он: а) реализует основные алгоритмы компиляции, такие, как аллокация регистров, планирование (scheduling) и т.п.; б) использует множество ухищрений (таких, как peephole-оптимизации, преобразования циклов и т.п.), и применяет их, когда это выгодно; в) удаляет избыточные абстракции (появляющиеся в результате использования макросов и т.п.), делает инлайн функций, удаляет временные объекты в С++ и т.п.; г) и ничего не портит при этом. Хотя любые из оптимизаций могут выглядеть тривиально, экономия всего одной итерации в критическом цикле может ускорить работу, например, кодека, на 10% и сэкономить 10% потребляемой мощности.
Перед тем, как погрузиться в тёмную сторону неопределённого поведения и поведения и политики LLVM, когда он используется в качестве компилятора C, я думаю, будет полезным рассмотреть несколько специфических случаев неопределённого поведения, и поговорить о том, как в каждом из этих случаев достигается производительность, лучшая, чем в безопасных языках, таких, как Java. Вы можете смотреть на это как на оптимизацию, которую позволяет сделать класс неопределённого поведения, либо как избавление от избыточности, которая потребовалась бы, имей этот класс случаев определённое поведение. Хотя компилятор может устранять некоторые из этих избыточностей в некоторых случаях, для того, чтобы сделать это в общем виде (для каждого случая), может потребоваться решение «проблемы останова» и многих других интересных задач.
Также нужно отметить, что и Clang, и GCC определяют некоторые случаи поведения, которые стандарт С оставляет неопределёнными. Те случаи, которые я буду описывать, являются неопределёнными как в соответствии со стандартом, так и рассматриваются как неопределённые обоими компиляторами в настройках по умолчанию.
Использование неинициализированной переменной: широко известный источник проблем в программах на С, и существует множество инструментов для отлавливания таких ошибок: от предупреждений компилятора до статических и динамических анализаторов. Это увеличивает быстродействие, так как не требует инициализации нулём всех переменных, которые попадают в область видимости (как это делает Java). Для большинства скалярных переменных, это очень небольшая избыточность, но инициализация массивов на стеке и памяти, выделенной в куче, может быть довольно дорогостоящей, особенно, если дальше эта память полностью перезаписывается.
Переполнение знакового целого: если переполняется тип 'int' (например), результат не определён. Например, «INT_MAX+1» не гарантированно будет равен INT_MIN. Такое поведение делает возможным целый класс оптимизаций, важных в ряде случаев. Например, знание того, что INT_MAX+1 не определено, позволяет заменить «X+1 > X» на «true». Знание того, что умножение «не может» приводить к переполнению (потому что это приводило бы к неопределённому поведению) позволяет заменить «X*2/2» на «X». Хотя эти примеры кажутся тривиальными, они часто встречаются после инлайна функций или разворачивания макросов. Более важная оптимизация происходит для "<=" в таком цикле:
В этом цикле компилятор может предполагать, что количество итераций цикла будет в точности N+1, если «i» не определено при переполнении, что позволяет предпринимать широкий спектр оптимизаций. С другой стороны, если переменная определённо должна «заворачиваться» при переполнении, то компилятор должен предполагать, что такой цикл может быть бесконечным (что произойдёт, если N равен INT_MAX) — что не позволит сделать множество оптимизаций цикла. Это особенно касается 64-битных платформ, в которых «int» часто используется для переменных цикла.
Для беззнаковых переменных ничего не стоит гарантировать переполнение по модулю 2 (заворачивание), и вы можете всегда использовать это. Сделать определённым переполнение знаковых чисел будет стоить потери таких оптимизаций (например, общий симптом проблемы, тонны знаковых расширений внутри циклов в 64-битных таргетах). И Clang, и GCC допускают флаг "-fwrapv", который заставляет компилятор рассматривать переполнение знаковых как определённое (кроме деления INT_MIN на -1).
Сдвиг на величину, большую, чем разрядность переменной: Сдвиг uint32_t на 32 или большее количество бит не определён. По моим догадкам, это произошло из-за того, что операция сдвига на различных CPU производится по-разному: например, X86 обрезает 32-битную величину сдвига до 5 бит (то есть сдвиг на 32 бита — то же самое, что на 0 бит), но PowerPC обрезает 32-битную величину сдвига до 6 бит (и результат сдвига на 32 бита равен нулю). Из-за этих аппаратных различий, поведение полностью не определено в языке C (то есть сдвиг на 32 бита на PowerPC может отформатировать ваш жёсткий диск, он не гарантированно выдаст в результате ноль). Стоимость устранения такого неопределённого поведения состоит в том, что компилятор должен генерировать дополнительные операции (такие, как 'and') для переменной сдвига, что сделало бы эту операцию в два раза более дорогой на распространённых CPU.
Разыменование «диких» указателей и доступ за пределы массива: Разыменование произвольного указателя (такого, как NULL, указателя на нераспределённую память, и т.п.) и случай доступа к массиву с выходом за его границы является распространённым багом в приложениях на C, и нуждается в разъяснениях. Чтобы устранить этот источник неопределённого поведения, при доступе к массиву должна производиться проверка диапазона, и ABI должен быть изменён так, чтобы информация о диапазоне сопровождала каждый указатель, который может быть использован в адресной арифметике. Это имело бы чрезвычайно высокую стоимость для многих числовых и других приложений, и сломало бы бинарную совместимость со всеми существующими библиотеками С.
Разыменование NULL-указателя: в противоположность популярному мнению, разыменование нулевого указателя в C не определено. Оно не определено как вызов команды «trap», и если вы сделаете mmap страницы по адресу 0, это не приведет к доступу к этой странице. Это нарушение правила, которое запрещает разыменовывать «дикие» указатели и использовать NULL как «сторожевое» значение. Разыменование указателя NULL является неопределённым и позволяет делать широкий диапазон оптимизаций: в противоположность, Java запрещает компилятору перемещать операции с побочными эффектами между объектами, которые не могут рассматриваться оптимизатором как гарантированно ненулевые. Это существенно ухудшает планирование и другие оптимизации. В C-подобных языках, неопределённость разыменования NULL делает возможными большое количество скалярных оптимизаций, и улучшить результат развёртывания макросов и инлайна функций.
Если вы используете компилятор на основе LLVM, вы можете разыменовывать «volatile» указатель на null и получить аварийный останов, если это то, чего вы хотите, так как операции чтения и записи volatile-объектов в общем случае не оптимизируются. В настоящее время не существует флага, позволяющего произвольной операции чтения из указателя на NULL рассматриваться как валидная операция или разрешить произвольные операции чтения из указателя, про который известно, что он может быть нулевым.
Правила нарушения типа: Случаем неопределённого поведения является преобразование int* в float* с последующим разыменованием (доступом к «int» как если бы это был «float»). Язык C требует, чтобы такой тип преобразования происходил через memcpy: использование преобразования указателей некорректно и результаты не определены. В этих правилах довольно много нюансов, и я не хочу погружаться здесь в детали (есть исключения для char*, вектора имеют особые свойства, объединения работают по-другому, и т.д.). Такое поведение делает возможным «Type-Based Alias Analysis» (TBAA), использующийся в широком диапазоне оптимизаций доступа к памяти в компиляторе, и может существенно улучшить производительность сгенерированного кода. Например, это правило позволяет clang-у оптимизировать такую функцию:
в «memset(P, 0, 40000)». Такая оптимизация также позволяет вынести за цикл множество операций чтения, оптимизировать общие подвыражения и т.п. Этот класс неопределённого поведения может быть запрещён флагом -fno-strict-aliasing, который отключает анализ. Когда флаг установлен, Clang скомпилирует этот цикл в 10000 4-байтовых операций записи (что во много раз медленнее), потому что должен считать, что каждая из этих операций записи изменяет значение P, как в следующем примере:
Такое нарушение типизации достаточно необычно, поэтому комитет по стандартизации решил, что существенный выигрыш в производительности стоит неожиданных результатов при «резонных» преобразованиях типов. Стоит заметить, что Java извлекает преимущества из оптимизаций преобразований типов без таких недостатков, потому что в ней нет небезопасного приведения указателей как такового.
В любом случае, я надеюсь, что это дало вам понимание того, как целые классы оптимизаций становятся возможными благодаря неопределённому поведению в C. Конечно, существует много других случаев, включая нарушения точек следования, как, например, «foo(i, ++i)», состязания в многопоточных программах, нарушения доступа, деление на ноль, и т.п.
В следующем посте, мы обсудим, почему неопределённое поведение в C является довольно пугающей вещью, если производительность не является вашей единственной целью. В последнем посте цикла мы поговорим о том, как LLVM и Clang обрабатывают неопределённое поведение.
Часть 2
Часть 3
Люди иногда спрашивают, почему код, скомпиливанный в LLVM иногда генерирует сигналы SIGTRAP, когда оптимизация была включена. Покопавшись, они обнаруживают, что Clang сгенерировал инструкцию «ud2» (подразумевается код X86) — то же, что генерируется __builtin_trap(). В этой статье рассматривается несколько вопросов, касающихся неопределённого поведения кода на C и того, как LLVM его обрабатывает.
В этой статье (первой из трёх) мы попытаемся объяснить некоторые из этих вопросов, чтобы вы могли лучше понять связанные с ними компромиссы и сложности, и возможно, изучить немного больше тёмные стороны С. Мы выясним, что C не является «высокоуровневым ассемблером», как многие опытные программисты на C (особенно те, кто сфокусирован на низком уровне) предпочитают думать, и что C++ и Objective-C напрямую унаследовали множество таких проблем.
Введение в Неопределённое Поведение
В языках программирования LLVM IR и C есть концепция «неопределённого поведения». Неопределённое поведение, это широкая тема с множеством нюансов. Лучшее введение в тему, которое я нашёл, это пост в блоге Джона Реджера. Краткая суть этой прекрасной статьи состоит в том, что многие вещи, кажущиеся осмысленными в C, на самом деле имеют неопределённое поведение, и это является источником множества багов в программах. Более того, каждая конструкция с неопределённым поведением в С имеет лицензию на реализацию (компиляцию и выполнение) кода, который может отформатировать ваш жёсткий диск, и делать ещё более плохие вещи совершенно неожиданно. И снова, я настоятельно рекомендую прочесть статью Джона.
Неопределённое поведение существует в С-подобных языках по той причине, что разработчики С хотели, чтобы он был предельно эффективным низкоуровневым языком программирования. Как противоположность, языки типа Java (и многие другие «безопасные» языки программирования) избегают неопределённого поведения, потому что они хотят безопасного и воспроизводимого поведения, не зависящего от реализации, и готовы пожертвовать производительностью, чтобы достичь этой цели. Хотя ничто из этого не является вашей целью, если вы программируете на С, вы на самом деле должны понимать, что такое неопределённое поведение.
Перед тем, как погрузиться в детали, стоит напомнить, что позволяет компилятору достичь высокого быстродействия на большом диапазоне C-приложений, при том, что нет никакой волшебной пули. На самом высоком уровне, компилятор генерирует быстрый код за счёт того, что он: а) реализует основные алгоритмы компиляции, такие, как аллокация регистров, планирование (scheduling) и т.п.; б) использует множество ухищрений (таких, как peephole-оптимизации, преобразования циклов и т.п.), и применяет их, когда это выгодно; в) удаляет избыточные абстракции (появляющиеся в результате использования макросов и т.п.), делает инлайн функций, удаляет временные объекты в С++ и т.п.; г) и ничего не портит при этом. Хотя любые из оптимизаций могут выглядеть тривиально, экономия всего одной итерации в критическом цикле может ускорить работу, например, кодека, на 10% и сэкономить 10% потребляемой мощности.
Преимущества неопределённого поведения в С, примеры
Перед тем, как погрузиться в тёмную сторону неопределённого поведения и поведения и политики LLVM, когда он используется в качестве компилятора C, я думаю, будет полезным рассмотреть несколько специфических случаев неопределённого поведения, и поговорить о том, как в каждом из этих случаев достигается производительность, лучшая, чем в безопасных языках, таких, как Java. Вы можете смотреть на это как на оптимизацию, которую позволяет сделать класс неопределённого поведения, либо как избавление от избыточности, которая потребовалась бы, имей этот класс случаев определённое поведение. Хотя компилятор может устранять некоторые из этих избыточностей в некоторых случаях, для того, чтобы сделать это в общем виде (для каждого случая), может потребоваться решение «проблемы останова» и многих других интересных задач.
Также нужно отметить, что и Clang, и GCC определяют некоторые случаи поведения, которые стандарт С оставляет неопределёнными. Те случаи, которые я буду описывать, являются неопределёнными как в соответствии со стандартом, так и рассматриваются как неопределённые обоими компиляторами в настройках по умолчанию.
Использование неинициализированной переменной: широко известный источник проблем в программах на С, и существует множество инструментов для отлавливания таких ошибок: от предупреждений компилятора до статических и динамических анализаторов. Это увеличивает быстродействие, так как не требует инициализации нулём всех переменных, которые попадают в область видимости (как это делает Java). Для большинства скалярных переменных, это очень небольшая избыточность, но инициализация массивов на стеке и памяти, выделенной в куче, может быть довольно дорогостоящей, особенно, если дальше эта память полностью перезаписывается.
Переполнение знакового целого: если переполняется тип 'int' (например), результат не определён. Например, «INT_MAX+1» не гарантированно будет равен INT_MIN. Такое поведение делает возможным целый класс оптимизаций, важных в ряде случаев. Например, знание того, что INT_MAX+1 не определено, позволяет заменить «X+1 > X» на «true». Знание того, что умножение «не может» приводить к переполнению (потому что это приводило бы к неопределённому поведению) позволяет заменить «X*2/2» на «X». Хотя эти примеры кажутся тривиальными, они часто встречаются после инлайна функций или разворачивания макросов. Более важная оптимизация происходит для "<=" в таком цикле:
for (i = 0; i <= N; ++i) { ... }В этом цикле компилятор может предполагать, что количество итераций цикла будет в точности N+1, если «i» не определено при переполнении, что позволяет предпринимать широкий спектр оптимизаций. С другой стороны, если переменная определённо должна «заворачиваться» при переполнении, то компилятор должен предполагать, что такой цикл может быть бесконечным (что произойдёт, если N равен INT_MAX) — что не позволит сделать множество оптимизаций цикла. Это особенно касается 64-битных платформ, в которых «int» часто используется для переменных цикла.
Для беззнаковых переменных ничего не стоит гарантировать переполнение по модулю 2 (заворачивание), и вы можете всегда использовать это. Сделать определённым переполнение знаковых чисел будет стоить потери таких оптимизаций (например, общий симптом проблемы, тонны знаковых расширений внутри циклов в 64-битных таргетах). И Clang, и GCC допускают флаг "-fwrapv", который заставляет компилятор рассматривать переполнение знаковых как определённое (кроме деления INT_MIN на -1).
Сдвиг на величину, большую, чем разрядность переменной: Сдвиг uint32_t на 32 или большее количество бит не определён. По моим догадкам, это произошло из-за того, что операция сдвига на различных CPU производится по-разному: например, X86 обрезает 32-битную величину сдвига до 5 бит (то есть сдвиг на 32 бита — то же самое, что на 0 бит), но PowerPC обрезает 32-битную величину сдвига до 6 бит (и результат сдвига на 32 бита равен нулю). Из-за этих аппаратных различий, поведение полностью не определено в языке C (то есть сдвиг на 32 бита на PowerPC может отформатировать ваш жёсткий диск, он не гарантированно выдаст в результате ноль). Стоимость устранения такого неопределённого поведения состоит в том, что компилятор должен генерировать дополнительные операции (такие, как 'and') для переменной сдвига, что сделало бы эту операцию в два раза более дорогой на распространённых CPU.
Разыменование «диких» указателей и доступ за пределы массива: Разыменование произвольного указателя (такого, как NULL, указателя на нераспределённую память, и т.п.) и случай доступа к массиву с выходом за его границы является распространённым багом в приложениях на C, и нуждается в разъяснениях. Чтобы устранить этот источник неопределённого поведения, при доступе к массиву должна производиться проверка диапазона, и ABI должен быть изменён так, чтобы информация о диапазоне сопровождала каждый указатель, который может быть использован в адресной арифметике. Это имело бы чрезвычайно высокую стоимость для многих числовых и других приложений, и сломало бы бинарную совместимость со всеми существующими библиотеками С.
Разыменование NULL-указателя: в противоположность популярному мнению, разыменование нулевого указателя в C не определено. Оно не определено как вызов команды «trap», и если вы сделаете mmap страницы по адресу 0, это не приведет к доступу к этой странице. Это нарушение правила, которое запрещает разыменовывать «дикие» указатели и использовать NULL как «сторожевое» значение. Разыменование указателя NULL является неопределённым и позволяет делать широкий диапазон оптимизаций: в противоположность, Java запрещает компилятору перемещать операции с побочными эффектами между объектами, которые не могут рассматриваться оптимизатором как гарантированно ненулевые. Это существенно ухудшает планирование и другие оптимизации. В C-подобных языках, неопределённость разыменования NULL делает возможными большое количество скалярных оптимизаций, и улучшить результат развёртывания макросов и инлайна функций.
Если вы используете компилятор на основе LLVM, вы можете разыменовывать «volatile» указатель на null и получить аварийный останов, если это то, чего вы хотите, так как операции чтения и записи volatile-объектов в общем случае не оптимизируются. В настоящее время не существует флага, позволяющего произвольной операции чтения из указателя на NULL рассматриваться как валидная операция или разрешить произвольные операции чтения из указателя, про который известно, что он может быть нулевым.
Правила нарушения типа: Случаем неопределённого поведения является преобразование int* в float* с последующим разыменованием (доступом к «int» как если бы это был «float»). Язык C требует, чтобы такой тип преобразования происходил через memcpy: использование преобразования указателей некорректно и результаты не определены. В этих правилах довольно много нюансов, и я не хочу погружаться здесь в детали (есть исключения для char*, вектора имеют особые свойства, объединения работают по-другому, и т.д.). Такое поведение делает возможным «Type-Based Alias Analysis» (TBAA), использующийся в широком диапазоне оптимизаций доступа к памяти в компиляторе, и может существенно улучшить производительность сгенерированного кода. Например, это правило позволяет clang-у оптимизировать такую функцию:
float *P;
void zero_array() {
int i;
for (i = 0; i < 10000; ++i)
P[i] = 0.0f;
}в «memset(P, 0, 40000)». Такая оптимизация также позволяет вынести за цикл множество операций чтения, оптимизировать общие подвыражения и т.п. Этот класс неопределённого поведения может быть запрещён флагом -fno-strict-aliasing, который отключает анализ. Когда флаг установлен, Clang скомпилирует этот цикл в 10000 4-байтовых операций записи (что во много раз медленнее), потому что должен считать, что каждая из этих операций записи изменяет значение P, как в следующем примере:
int main() {
P = (float*)&P; // cast causes TBAA violation in zero_array.
zero_array();
}Такое нарушение типизации достаточно необычно, поэтому комитет по стандартизации решил, что существенный выигрыш в производительности стоит неожиданных результатов при «резонных» преобразованиях типов. Стоит заметить, что Java извлекает преимущества из оптимизаций преобразований типов без таких недостатков, потому что в ней нет небезопасного приведения указателей как такового.
В любом случае, я надеюсь, что это дало вам понимание того, как целые классы оптимизаций становятся возможными благодаря неопределённому поведению в C. Конечно, существует много других случаев, включая нарушения точек следования, как, например, «foo(i, ++i)», состязания в многопоточных программах, нарушения доступа, деление на ноль, и т.п.
В следующем посте, мы обсудим, почему неопределённое поведение в C является довольно пугающей вещью, если производительность не является вашей единственной целью. В последнем посте цикла мы поговорим о том, как LLVM и Clang обрабатывают неопределённое поведение.
