Ответ на этот вопрос действительно зависит от компилятора и алгоритмов, выбранных для каждой фазы.В целом, лексирование / разбор будет очень дешевым, анализ и оптимизация будут дорогостоящими, а генерация кода будет где-то посередине.
Генерация кода обычно включает в себя выбор команд, планирование и распределение регистров.В зависимости от вашего компилятора могут быть другие этапы.
- Выбор инструкций - это процесс перевода вашего промежуточного представления в специфичные для архитектуры инструкции.Самый простой способ сделать это - просто иметь фиксированную последовательность для каждой инструкции IR;это даст плохой код, но очень быстро, так что вы можете увидеть это в JIT-компиляторе.В заранее скомпилированных языках, таких как C, у вас будет алгоритм «тайлинга», который покрывает ваш IR тайлами, представляющими машинные инструкции.Существуют различные алгоритмы, такие как maximal много, жадный алгоритм, используемый LLVM.Все известные мне алгоритмы O (n), но некоторые принимают несколько проходов.В общем, чем более оптимальным является мозаичное построение, тем дольше это занимает.
- Планирование инструкций позволяет упорядочить инструкции так, чтобы они выполнялись с минимальным количеством остановок на конкретном ЦП.Этот этап сильно зависит от процессора (а не только от архитектуры).Эта фаза является необязательной.
- Распределение регистров - это присвоение переменных регистрам или слотам стека.Опять же, есть несколько алгоритмов.Раскраска графа хороша, но она должна быть аппроксимирована, так как истинная раскраска графа является NP-полной.Линейное сканирование (используется LLVM) намного быстрее, но не так хорошо.Оба алгоритма O (n).