Асимптотическая сложность компилятора

Question

Каково максимально допустимое асимптотическое время выполнения компилятора общего назначения?

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

Это сильно зависит от вашей точки зрения, так что это вики сообщества.

Посмотрите на это с точки зрения того, кто пишет компилятор. Будет ли когда-либо использоваться уровень оптимизации -O4 для более крупных программ, когда одна из его оптимизаций займет O (n ^ 6)?

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

• Когда супероптимизация (экспоненциальная сложность или даже неисчислимая) приемлема?

• Что приемлемо для JIT ? Должно ли оно быть линейным?

• В чем сложность установленных компиляторов? GCC? VC? Intel? Джава? C #? Турбо Паскаль? LCC? LLVM? (Reference?)

Если вы не знаете, что такое асимптотическая сложность : как долго вы готовы ждать, пока компилятор скомпилирует ваш проект? (исключены языки сценариев)

Answer 1

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