qwerty's Journal

Отведение регистров
На этот раз путем складывания паззлов. В один проход по предварительно подготовленной программе в варианте SSA. Годится для инструкций с операндами в фиксированных регистрах и ограниченного алиасинга регистров (например, x86 AH:AL/AX/EAX). Сначала жизненные интервалы как можно более мелко шинкуются, затем каждая операция преобразуется в паззл, для решения которого последовательно пробуются правила из фиксированной последовательности. Пока набор регистров можно представлять паззлами типов 0 и 1 (см. графическую нотацию по ссылке), первое подошедшее правило является и наилучшим (в силу некоей теоремы, доказательство которой еще не опубликовано). Если нашинкованной переменной назначен(ы) регистр(ы), соответствующие части фиксируются во всех паззлах с ее участием.

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

Забавно, что если бы в AMD64 можно было отдельно адресовать верхнюю часть 64-битовых регистров, то это уже не паззл типа 0 или 1, и, соответственно, правила было бы линейно не упорядочить, и алгоритм бы не работал.