Да там обычно любые OS разрешают запустил процесс изолированно и наблюдать за состоянием. Если работает 2сек и сожрал Н-памяти - килить его к чертям.

Ну да, если там не МК какая-то.

именно для мк мне и интересно. т.е. чистое решение, только на основе кода

В очередной раз: теорема Райса (https://en.wikipedia.org/wiki/Rice%27s_theorem) Вам говорит, что для Тьюринг-полного языка (байт-кода, машинного кода — без разницы) без запуска программы Вы ничего гарантировать не сможете. Поэтому у Вас 2 варианта: запускать в песочнице, чего Вы на МК фиг сделаете, или ограничить входной/выходной язык так чтобы он не был Тьюринг-полным и гарантировал нужные свойства по построению.

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

меня устраивает ограничить язык

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

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

не используя таймер+прерывание

Читайте хотя бы Википедию. Не полные по Тьюрингу языки в последнее время очень популярны.

Это самое fuel, про которое Вы ничего не смогли найти, используется в Etheium, называется "газ" (gas).

язык гарантирующий отсутствие бесконечных циклов...
или рантайм [+hw] гарантирующий
- отсутствие блокировки процессора бесконечным циклом
- изоляцию адресного пространства каждого процесса
- менеджер процессов с ttl+wdt+ping для процесса
- move-семантика при передаче данных ссылкой в shared memory

первый вариант не дает интересный код писать

поэтому интересен второй

Ещё есть структурная рекурсия и well-founded рекурсия, они тоже гарантированно завершаются.

Некоторые разработки получают известность не в силу новаторских решений, а благодаря качественной инженерной работе и удобной сопроводительной документации. Пример - портативный компилятор lcc, ставший прообразом 8cc, chibicc, tcc и других свободно доступных небольших компиляторов.

Разработчики lcc задались целью сделать не просто полноценный компилятор языка Си, но еще и подробно документированный: проект написан в стиле "литературного программирования" Д.Кнута, когда код интегрирован в документацию (а не наоборот).

Более того, из такого "художественного" исходного кода можно собрать полноценную книгу, изданную под названием A Retargetable C Compiler: Design and Implementation. Вместе с книгой для разъяснения ключевых технических решений авторы опубликовали статьи, посвященные, например, распределению регистров и порождению кода.

lcc можно отнести к промежуточному варианту между простыми компиляторами, описываемыми в популярных книгах для программистов, и серьезными оптимизирующими компиляторами. Здесь есть внутреннее представление (лес ациклических графов внутри базовых блоков графа потока исполнения), используются отдельные популярные оптимизации.

Характерное для компилятора решение - распределение регистров. Оно локальное и восходящее, то есть проводится внутри базового блока проходом по списку инструкций. Регистры один за другим выделяются под значения до тех пор, пока не приходится искать значение для вытеснения в память. Вытесняются те значения, следующее использование которых в списке инструкций находится дальше всего.

В результате компилятор был портирован на множество платформ, стал основой для бесчисленных форков и даже использовался для скриптования популярного игрового движка id Tech 3 (см. Quake 3 Arena) компании idSoftware.

https://en.wikipedia.org/wiki/LCC_(compiler)

https://github.com/drh/lcc

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.2519&rep=rep1&type=pdf

https://en.wikipedia.org/wiki/Id_Tech_3

#lcc #history #registeralloc #quake3

"вытесняются те значения, следующее использование которых в списке инструкций  находится дальше всего". Имеется ввиду, что разница между позицией use и позицией Def максимальна?

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

Спасибо за разъяснение. Анализа программы нет, получается они на проходе распределения регистров реализуют эту эвристику

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

У них есть публикация (1992 года), где они доказывают, что без агрессивного inline функций проливаний все равно мало, поэтому такая неэффективность терпима.

А бежать "задом наперёд" по списку инструкций не получится? Чтобы два раза-то не бегать?

Думаю, там есть возможности для оптимизаций, но авторы старались все делать предельно просто.

Кажется с 92 года инлайнить стали существенно больше, но выглядит логично