32bit_me (32bit_me) wrote,
32bit_me
32bit_me

Category:

Аллокация регистров

Важной частью компилятора является аллокатор регистров. Он выполняется после планировщика (scheduler), который генерирует уже практически финальный код в машинных инструкциях, но вместо физических регистров используются виртуальные регистры.
Работа аллокатора регистров заключается в том, чтобы назначить физические регистры вместо виртуальных. Количество физических регистров ограничено, виртуальных регистров потенциально неограниченное число, поэтому физических регистов может не хватить, тогда аллокатор должен сделать спиллинг (spill) виртуального регистра, то есть вставить команду, сохраняющую значение регистра в стеке, а перед использованием этого регистра извлечь значение из стека.
Также аллокатор регистров применяет множество техник оптимизации, таких, как рематериализация констант, изменение порядка выполнения инструкций, разделение виртуального регистра на несколько и т.п.
Хорошая новость состоит в том, что в LLVM есть готовый аллокатор (и не один), не требующий доработок со стороны разработчика бэкенда, то есть он работает просто на основании описания набора регистров.
Плохая новость состоит в том, что в ряде случаев, если у вас необычная архитектура, вообще нет регистров (2-х или 3-х адресная архитектура), стековая машина или что-то такое, он работать не будет.
Вторая хорошая новость состоит в том, что даже в таких тяжёлых случаях вы можете написать свой аллокатор, причём он будет даже проще стандартного. Намного проще, ведь не нужны будут сложные алгоритмы раскраски графа, реордеринга, сплиттинга и прочего. Можно просто назначать виртуальным регистрам смещения в стеке, например.

Ниже небольшой список литературы, в которой описывается аллокатор регистров:

1. Jakob Stoklund Olesen. Register Allocation in LLVM 3.0.
2. Jakob Stoklund Olesen. Greedy Register Allocation in LLVM 3.0.
3. How To Write An LLVM Register Allocator (https://github.com/nael8r/How-To-Write-An-LLVM-Register-Allocator)
4. The LLVM Target-Independent Code Generator (раздел Register Allocation)
Tags: llvm, программирование
Subscribe

  • Flang - новый компилятор Fortran

    Flang - новый компилятор Fortran на основе LLVM. Интересно, что Fortran жив до сих пор, а ведь он был впервые представлен в 1957 году. Последняя…

  • Книги

    Ретрокниги:

  • GitHub Desktop

    GitHub Desktop - очень прикольная штука. Ставите и забываете cli и git bash (если вы под виндой). Хотя и в cli нет ничего сложного, но GitHub Desktop…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 5 comments