Компиляция программ для современных архитектур



             

Базовый алгоритм селективного планирования - часть 2


Промежуточные множества доступных команд сохраняются в начале каждого базового блока.

На этапе перемещения выбранной команды регион обходится аналогичным образом сверху вниз в поиске команд, которые могли быть преобразованы в выбранную, при этом используются сохраненные множества доступных команд – если искомая команда не содержится в сохраненном множестве, то её нет смысла искать ниже текущего места региона. Если команда найдена, то она удаляется из региона, а на обратном пути вверх обновляются сохраненные множества доступных команд и в точках слияния потока управления на путях, не лежащих на текущем пути обхода, создаются компенсационные копии выбранной команды. После окончания перемещения выбранная команда в преобразованном виде добавляется в поток команд в точке планирования, а все промежуточные множества доступных команд оказываются верными, что значительно ускоряет этап сбора команд для следующей итерации планирования.

Важным достоинством селективного планировщика является возможность конвейеризации циклов, вытекающая из поддержки перемещений команд с созданием компенсационных копий и из того, что перемещение команд через барьер запрещено. При планировании внутреннего цикла из гнезда циклов текущим регионом считается ациклический регион, получающийся из цикла разрывом тех дуг, на которых в данный момент стоят барьеры. В начале планирования разрывается обратная дуга цикла. На этапе сбора команд разрешается собирать уже запланированные команды – при планировании обычного региона такая ситуация запрещена. При перемещении уже запланированной команды вдоль обратной дуги на входе в цикл наблюдается слияние потока управления, и поэтому на дуге перед циклом будет создана компенсационная копия, образующая пролог конвейеризованного цикла (см. рис. 4). При планировании внешнего цикла пролог внутреннего цикла добавляется к региону планирования, а тело внутреннего цикла обрабатывается как «черный ящик», при этом перемещения команд через него запрещены.




Содержание  Назад  Вперед