170 похожих чатов

Народ, смотрю тут доклад про UB и там демонстрируется такой

пример
int table[4];
bool exists_in_table(int v){
for (int i = 0; i <= 4; i++)
if (table[i] == v) return true;
return false;
}
который компилятор оптимизирует в это
int table[4];
bool exists_in_table(int v){
return true;
}
Объяснение такое - мол компилятор думает что ub нет а значит этой последней итерации цикла не будет а значит будет выполнен return в предыдущей итерации цикла (мол значение найдено) а значит можно вообще избежать цикла и сразу вернуть true

В целом ход мыслей авторов компилятора понятен но вот непонятно почему авторы комплятора решили что они могут выстраивать различные преобразования и производить оптимизации используя как аксиому тот факт что ub и рантайм-ошибок в программе нет вместо того чтобы сначала попробовать доказать это (что UB и рантайм-ошибок нет) анализируя код и в случае невозможности это доказать выдать юзеру ошибку чтобы он поправил код (и только потом доказав отсутствие уб и рантайм-ошибок уже дальше делать всякие преобразования и оптимизации над кодом)

То есть я считаю что правильным должен быть такой алгоритм действий компилятора

1) компилятор видит небезопасную операцию которая приводит к ub (или просто выдает рантайм-ошибку) - например обращение к массиву - arr[i]

2) компилятор считает что в корректной программе не должно быть UB или рантайм-ошибок и пытается доказать что этого не произойдет - для этого компилятор анализиует data-flow по коду и смотрит какие значения может принимать переменная i (которая используется в небезопасной операции arr[i])

3) если компилятор не смог доказать что переменная i будет принимать значения не меньше 0 и не больше размера массива (например i является динамической переменной и приходит извне или над ней призводят нетривиальные преобразования а в компялторе не заложены формулы разнообразных математических преобразований) то тогда компилятор выдает ошибку и требует от программиста поменять код - например добавить условие перед выполнением этой небезопасной операции - if (i < std::size(arr)) arr[i]; - чтобы data-flow анализ смог легко увидеть что переменная индекса находится в пределах массива и компилятор (доказав отсутствие UB/рантайм-ошибки) смог перейти дальше к оптимизациям

И как результат в данном примере компилятор не сможет доказать что переменная i принимает значения от 0 до std::size(table) потому что по data-flow анализу увидит что i <= 4 и должен выдать ошибку юзеру

Кто-нибудь знает как можно настроить такое поведение (доказательство отсутствия вместо аксиомы что UB/ошибок нет) в Сlang/LLVM ? Или это невозможно и нужно будет писать свой компилятор?

35 ответов

27 просмотров

>> непонятно почему авторы комплятора решили что они могут выстраивать различные преобразования и производить оптимизации используя как аксиому тот факт что ub и рантайм-ошибок в программе нет вместо того чтобы сначала попробовать доказать это Потому что такие доказательства чаще всего невозможны без участия программиста. И поэтому компилятор принимает за аксиому утверждение, что программист благоразумен и не пишет на C++ то, что не является C++ В противном случае вы столкнётесь с ложноположительными срабатывания анализатора внутри компилятора. При том, у каждого компилятора будет уникальный набор эвристик и вам придётся доказывать корректность кода каждому из них >> Кто-нибудь знает как можно настроить такое поведение (доказательство отсутствия вместо аксиомы что UB/ошибок нет) в Сlang/LLVM? Можно в LLVM >> Или это невозможно и нужно будет писать свой компилятор? Уже написал, см. выше

>> непонятно почему авторы комплятора решили что они могут выстраивать различные преобразования и производить оптимизации используя как аксиому тот факт что ub и рантайм-ошибок в программе нет вместо того чтобы сначала попробовать доказать это потому что Стандарт >> Кто-нибудь знает как можно настроить такое поведение эта штука называется завтипы, в С++ их нет и не будет. выше упомянули Rust, там их тоже нет, и этот язык вообще про другое. Если хочешь попробовать, открой для себя Идрис или Эф стар. Ну и готовь баблишко для психотерапии.

оптимизации можно проводить только на основе уб и сопутствующего этому Описанный вами алгоритм 1. невозможен 2. если найдутся гении которые его напишут, то ошибки у всех компиляторов будут разные 3. int x = fooNOT42(); if(x == 42) returtn *nullptr; не получилось доказать, ошибка, потрясающее программирование будет

Богдан- Автор вопроса
Roman
>> непонятно почему авторы комплятора решили что о...

А почему сразу завтипы которых нет в плюсах? Я вот ни разу не функциональщик и мало представляю что такое завтипы но я вижу что это проблема не языка а реализации компилятора. Компилятор ведь может проанализировать код всей программы и построить data-flow и range-analysis? Может, я вот просматривал доклады про Clang Static Analyzer и там все это есть. Так почему же нельзя просто проверить эти переменные которые участвуют в небезопасных операциях и выдать ошибку если мы не смогли доказать что ошибки/ub не будет? Я не думаю что будет много ложноположительных срабатываний если не будем использовать раздельную компиляцию и компилятор будет анализировать data-flow/range-analysis всей программы

Богдан
А почему сразу завтипы которых нет в плюсах? Я вот...

потому что если ты не смог что-то доказать, это не значит что тут ошибка

Богдан
А почему сразу завтипы которых нет в плюсах? Я вот...

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

Богдан
А почему сразу завтипы которых нет в плюсах? Я вот...

>> но я вижу что это проблема не языка а реализации компилятора Нет, это проблема проблема несовершенства(?) этого мироустройства >> Компилятор ведь может проанализировать код всей программы и построить data-flow и range-analysis? Никого не устроит частное решение в качестве стандарта ввиду ложноположительных срабатываний, а полное решение, полагаю, невозможно ввиду проблемы останова и других смежных проблем

Богдан- Автор вопроса
Roman
потому что если бы так можно было сделать, то ты б...

Нет, проблемы останова здесь ни при чем. Можно было бы сказать про теорему Райса но у нас ведь нет цели полностью избавиться от ложноположительных срабатываний. Ничего страшного в том что в редких случаях компилятор попросит юзера вставить if-ы. Суть в том что если что-то доказать не получилось то зачастую эта переменная приходит извне или над ней производят нетривиальные математические преобразования про которые компилятор не в курсе (что встречается довольно редко в реальном коде) и тогда компилятор выдает ошибку а юзеру досточно будет просто добавить условие перед использованием небезопасной операции которое как бы валидирует значение переменной учавствующей в этой операции. Например если компилятор в редких случаях не смог доказать безопасность обращения к вектору то он выдает ошибку а юзер добавляет условие if (i < arr.size()) arr[i] перед считыванием ну и дальше компилятор видит по range-analysys что значение переменной i находится в пределах массива и успешно доказывает безопасность обращения к массиву

Богдан
Нет, проблемы останова здесь ни при чем. Можно был...

> редких случаях компилятор попросит юзера вставить if-ы не редких. Страшно.

Богдан
Нет, проблемы останова здесь ни при чем. Можно был...

>> нет цели полностью избавиться от ложноположительных срабатываний. Ничего страшного в том что в редких случаях компилятор попросит юзера вставить if-ы В редких случаях GCC, в редких Clang, иногда MSVC или ICC. И во что превратится ваш код? В портянки #ifdef? А что делать с другой веткой if-а? Сейчас у нас есть возможность и явно, и неявно сказать "она не может исполняться, оптимизируй". А что вы предлагаете взамен? Вы уверены, что настоящая цель бизнеса – это медленные в работе или разработке, но надёжные программы? Мне кажется, что обычно интересы там другие

Богдан- Автор вопроса
Ofee Oficsu
>> нет цели полностью избавиться от ложноположител...

Добавление условия вокруг небезопасной операции по сути будет валидировать разброс значений переменных которые участвуют в этой операции и это будет понимать любой компилятор умеющий в range-analysis так что достаточно будет написать один if а не для каждого компилятора свой #ifdef. Другая ветка условия не нужна так как это ложноположительная операция чисто для компилятора который не смог доказать что код в действительности является корректной и не вызывает ub/ошибку (вторая ветка условия не может выполниться по определению) Но кстати да, без развитого data-flow анализа этот подход не работает (либо if-ы придется писать на каждом шагу) но хорошая новость что подобный анализ уже наверное есть в большинстве компиляторов - в том же clang это clang static analyzer, касательно mvsv я тоже встречал доклад с демонстрацией path analysis ну а в gcc тоже скорее всего что-то пилят. Плюс типичный проект (допустим сервер/бэкенд или gui-приложение) в компании обычно собирается одним конкретным компилятором который меняется очень редко а баги обычно встречаются в коде проекта а не библиотек у которых в отличие от проекта есть требование работы под разными компиляторами и они хорошо протестированы). Соотвественно добавив эту возможность (принимать UB не как ошибку а как теорему которую надо доказать) даже в один компилятор Clang мы покроем значительную часть рынка и улучшим качество кода избавившись от UB и связанных с ними непредсказуемых оптимизаций

Богдан
Добавление условия вокруг небезопасной операции по...

не знаю какие у вас там развитые системы в компиляторах, у меня msvc не можт структуру внутри структуры объявить без ошибок

Богдан
Добавление условия вокруг небезопасной операции по...

>> Добавление условия вокруг небезопасной операции по сути будет валидировать разброс значений переменных А каким образом? Что делать, если вторая ветка невозможна с точки зрения семантики? Бросить исключение? Сделать std::terminate? >> Плюс типичный проект (допустим сервер/бэкенд или gui-приложение) в компании обычно собирается одним конкретным компилятором Это, конечно же, наинаглейшая ложь. Во-первых, нет, во вторых, в качестве зависимостей обычно используются фреймворки и библиотеки, которым нужно собираться любым компилятором >> а баги обычно встречаются в коде проекта а не библиотек Что, кончено же, ложь >> а с тем что UB это не достоинство а недостаток Наличие возможности оптимизации через UB – это свойство, которое не является ни положительным, ни отрицательным

Богдан- Автор вопроса
Ofee Oficsu
>> Добавление условия вокруг небезопасной операции...

А каким образом? Что делать, если вторая ветка невозможна с точки зрения семантики? Бросить исключение? Сделать std::terminate? Ок, пусть будет trap/std::terminate для второй ветки Это, конечно же, наинаглейшая ложь. Во-первых, нет, во вторых, в качестве зависимостей обычно используются фреймворки и библиотеки, которым нужно собираться любым компилятором так я и написал что требование работы под разными компиляторами есть у библиотек а у проектов как настроили сборку проекта каким-то компилятором так она может работы годами без смены комплятора Что, кончено же, ложь Какой процент багов в ежедневной разработкой связан с фреймворком/библиотекой а какой с кодом проекта? Модульный проекты части которых представлены библиотеками не считается я имею ввиду системные зависимости и библиотеки вроде qt Наличие возможности оптимизации через UB – это свойство, которое не является ни положительным, ни отрицательным К UB как к возможности relax-ить условия и лучше оптимизировать код у меня претензий нет. Моя претензия заключается в том что компилятор языка слепо доверяет коду беря за аксимоу что в коде нет UB из-за чего получаем примеры кода которые вызывают удивление (пример в первом сообщении или можно еще нагуглить never-called function) Получается какая-то каламбурная ситуация - с одной стороны в компиляторе развивают диагностики и анализ кода на ошибки - а с другой слепо доверяют коду и бросаются оптимизировать вместо того чтобы скачала доказать что UB нет и только потом проводить преобразования и оптимизации

Богдан
А каким образом? Что делать, если вторая ветка нев...

концепция предупреждений в компиляторе вам знакома?

Богдан
А каким образом? Что делать, если вторая ветка нев...

А если у меня std::terminate машину в kernel panic/BSOD роняет - юзер точно оценит? Или что-то крутится на МК и по некоторой причине вынужден отлаживаться исключительно логами?

Богдан
А каким образом? Что делать, если вторая ветка нев...

Процент багов малый, зато они всегда нескучные: только вчера Boost.Beast на коленке пришлось чинить

Богдан- Автор вопроса
Kelbon
концепция предупреждений в компиляторе вам знакома...

А в компиляторе можно настроить предупреждения чтобы они предупреждали что компилятор не смог доказать отсутствие UB и бросился оптимизировать код (считая что UB нет) ? Если так то я всеми руками за. Вопрос только в том как это настроить в том же кланге?

Богдан- Автор вопроса
Dmitriy [Отпуск]
А если у меня std::terminate машину в kernel panic...

Эта ветка ведь никогда не выполниться в корректно работающей программе. А если она выполнилась значит в коде содержится баг и тут уж лучше std::teminate чем UB который может обнаружиться очень далеко от места ошибки

Богдан
Эта ветка ведь никогда не выполниться в корректно ...

Но она как минимум существует (а как максимум - платим за лишний if, и разница между, скажем, at() и operator[] исчезает)

Богдан
А каким образом? Что делать, если вторая ветка нев...

>> Ок, пусть будет trap/std::terminate для второй ветки Прямо на hot path? >> Модульный проекты части которых представлены библиотеками не считается А почему, собственно? >> Какой процент багов в ежедневной разработкой связан с фреймворком/библиотекой а какой с кодом проекта? Я лично статистику не собирал, но прямо сейчас занят исправлением багов в нескольких зависимостях. Вы можете попробовать ещё провести анализ существующих CVE в таких библиотеках и фреймворках – они тоже пишутся на C++

Богдан
Нет, проблемы останова здесь ни при чем. Можно был...

осталось узнать, что бывает раздельная компиляция и динамическое связывание. Невозможно в принципе все доказать.

Boris Usievich
осталось узнать, что бывает раздельная компиляция ...

ТС предложил решение для недоказуемых случаев, но...

Dmitriy [Отпуск]
ТС предложил решение для недоказуемых случаев, но....

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

Богдан- Автор вопроса
Ofee Oficsu
>> Ок, пусть будет trap/std::terminate для второй ...

Прямо на hot path? Как получиться) Предполагается что после мощного data-flow/range/path/symbolic-execution анализа кейсы в которых нужно будет вставлять if чтобы помочь компилятору доказать корректность (отсутсвие ub/рантайм-ошибки) на какой-то небезопасной операции будут ничтожно малы в реальном коде и если исключить случаи динамических переменных (которые получают значение из инпута или где-то извне) для которых в подавляющем большинстве случаев и так нужна будет валидация (что является тем же if-ом который сужает значение и помогает компилятору доказать корректность) то остальные случаи относятся к сложным математическим преобразованиям которые сложно доказать без добавления в компилятор математических формул преобразования. Например есть формула квадратичного уравнения которая говорит что если для динамических переменных a, b, c, x1, x2 a * x1 * x1 + b * x1 + c == 0 && a * x2 * x2 + b * x2 + c == 0 и если a + b + c == 0 и если x1 * a == c то значение x2 будет равно 1 и операция arr[8 + x2] вполне себе безопасна для массива размером 10 но никто не захочет раздувать исходный код компилятора формулами для всевозможных математических преобразований соотвественно компилятор не сможет доказать что arr[8 + x2] можно безопасно считать и выдаст ошибку а юзер должен будет заврапить в условие if (8 + x2 > 0 && 8 + x2 < 10) value = arr[8 + x2] и дальше компилятор увидит по rage-analysis разброс значений для индек-выражения и докажет безопасность обращения к массиву. Соотвественно выполнение второй ветки будет говорить об ошибке в самом коде (например неправильно закодили выражение квадратного уравнения) и здесь получаем трейдофф - либо платим дополнительными инструкциями на if в рантайме чтобы сразу поймать ошибку через trap в другом бранче либо каким-то интристиком говорим компилятору что "зуб даю - чтение массива в этом месте безопасно" и компилятор верит на слово но тогда получаем UB которое сложно дебажить если мы сами ошиблись

Богдан
Прямо на hot path? Как получиться) Предполагается ...

Зачем сложные преобразования-то?) SomeOsApi(..., nullptr, ...) - UB или нет?

Богдан
Прямо на hot path? Как получиться) Предполагается ...

хотите гарантий доступа в массив - идите в java, там это гарантировано

Богдан
Прямо на hot path? Как получиться) Предполагается ...

глупо предполагать хоть в одном месте программы, что программист дурак и не даёт зуб за то что пишет

Богдан- Автор вопроса
Dmitriy [Отпуск]
Зачем сложные преобразования-то?) SomeOsApi(..., ...

Ну системный вызов принципиально не отличается от динамического инпута - любое взаимодействие с окружающей средой за пределами нашей статически-проверяемой песочницы либо нужно либо оборачивать рантайм-проверками (дополнительные if-ы которые сужают разброс значений и помогают доказывать корректность для дальнейших небезопасных операций) либо верить напрямую тем типам и поведению которое описываются в сигнатуре

Богдан
Ну системный вызов принципиально не отличается от ...

Идея вставлять в код ненужные if приведет к падению производительности. Кое где в разы, если убьет векторизацию внутреннего нагруженного цикла.

Что нужно проверить в моём примере?)

Богдан- Автор вопроса
Богдан
а где там может быть ub?

До непосредственного syscall вышеуказанный nullptr может быть разыменован в юзермодной части API Или знаменитый пример с виндой: часть API принимает размеры буферов в элементах, часть - в байтах

Похожие вопросы

Обсуждают сегодня

Господа, а что сейчас вообще с рынком труда на делфи происходит? Какова ситуация?
Rꙮman Yankꙮvsky
29
А вообще, что может смущать в самой Julia - бы сказал, что нет единого стандартного подхода по многим моментам, поэтому многое выглядит как "хаки" и произвол. Короче говоря, с...
Viktor G.
2
30500 за редактор? )
Владимир
47
а через ESC-код ?
Alexey Kulakov
29
Гайс, вопрос для разносторонее развитых: читаю стрим с юарта, нада выделять с него фреймы с определенной структурой, если ли чо готовое, или долбаться с ринг буффером? нада у...
Vitaly
9
Чёт не понял, я ж правильной функцией воспользовался чтобы вывести отладочную информацию? но что-то она не ловится
notme
18
У меня есть функция где происходит это: write_bit(buffer, 1); write_bit(buffer, 0); write_bit(buffer, 1); write_bit(buffer, 1); write_bit(buffer, 1); w...
~
14
Добрый день! Скажите пожалуйста, а какие программы вы бы рекомендовали написать для того, чтобы научиться управлять памятью? Можно написать динамический массив, можно связный ...
Филипп
7
Недавно Google Project Zero нашёл багу в SQLite с помощью LLM, о чём достаточно было шумно в определённых интернетах, которые сопровождались рассказами, что скоро всех "ибешни...
Alex Sherbakov
5
длина пакета фиксированная, или меняется?
Okhsunrog
7
Карта сайта