Отчет о состоянии научной работы на конец 9го семестра.
Сделано за этот семестр:
1. Описаны все ограничения на регистры, существующие в архитектуре.
2. Изучен ряд методов распределения регистров, применяющихся к архитектурам для встроенных систем.
o Метод, основанный на раскраске графов, адаптированный с учетом регистровых пар: каждый регистр, соответствующий регистровой паре заменяется двумя регистрами, каждый из которых связан дугой со свой парой и со всеми регистрами, с которыми был связан исходный виртуальный регистр.
o Метод, основанный на раскраске обобщенного графа взаимодействия регистров – классический алгоритм, основанный на раскраске адаптируется для учета регистровых классов. Каждому узлу в графе взаимодействия регистров ставится в соответствие его регистровый класс и при вычислении критерия раскрашиваемости вершины учитывается возможное количество конфликтов с соседними узлами.
o Сведение задачи распределения регистров к задаче линейного программирование. В этом методе все конфликты, возникающие в архитектуре задаются в виде весовых функций (функции строятся для каждого виртуального регистра и для каждой пары взаимодействующих виртуальных регистров), после чего все функции переписываются в матричном виде и задача сводится задаче линейного программирования, которую можно решать различными эвристическими алгоритмами.
3. Предложены несколько подходов для адаптации этих алгоритмов к процессору NM6403.
Основная проблема адаптации алгоритмов к NM6403 – регистровые банки, остальные ограничения уже учтены так или иначе в алгоритмах.
o Для методов, основанных на раскраске графов, предлагается помечать подграфы, которые должны принадлежать одному регистровому банку. После этого преобразованиями графа сводить его к графу, в котором возможна раскраска с учетом ограничения на регистровые банки.
o Для метода, основанного на линейном программировании возможно указание конфликта между виртуальными регистрами, использующимися внутри отдельной инструкции процессора. Это усложняет процесс построения весовых функций, но позволяет описать необходимые ограничения.
Дальнейшие планы по научной работе
• Адаптация одного из существующих методов для архитектуры NM6403 (формулировка алгоритма).
• Реализация и отладка алгоритма в рамках системы LLVM.
• Тестирование полученного распределителя регистров (тестирование на корректность выдаваемого кода, сравнение со штатным компилятором для NM6403).
Литература:
1. А. Ахо, Р. Сети, Д. Ульман. Компиляторы: принципы, технологии и инструменты. М.: «Вильямс», 2003. – 768 с.
2. Chris Lattner. Introduction to the LLVM Compiler Infrastructure [PDF] (
http://llvm.org/pubs/2006-04-25-GelatoLLVMIntro.pdf)
3. Архитектура процессора Л1879ВМ1 (NM6403). [PDF] (
http://www.module.ru/files/nm6403arch-r.pdf)
4. Нейропроцессор NM6403. Введение в архитектуру. [PDF] (
http://www.module.ru/files/nm6403ao11b-r.pdf)
5. D. Koes, S. С. Goldstein. A Progressive Register Allocator for Irregular Architectures [PDF] (
http://www.cs.cmu.edu/~seth/papers/koes-cgo05.pdf)
6. J. Runeson, Sven-Olof Nystr¨om. Retargetable Graph-Coloring Register Allocation for Irregular Architectures [PDF] (
http://user.it.uu.se/~svenolof/wpo/AllocSCOPES2003.pdf)
7. A. Sudarsanam and S. Malik. Simultaneous Reference Allocation in Code Generation for Dual Data Memory [PDF] (
http://portal.acm.org/citation.cfm?id=335043.335047)
8. B. Scholz, E. Eckstein. Register Allocation for Irregular Architectures [PDF] (
http://portal.acm.org/citation.cfm?id=513829.513854)
9. T. Kong, K. D. Wilken. Precise Register Allocation for Irregular Architectures [PDF] (
http://www.princeton.edu/~echi/register ... rarchs.pdf)
10. J. C. Y. Paek, D. Whalley. Efficient Register and Memory Assignment for Non-orthogonal Architectures via Graph Coloring and MST Algorithms [PDF] (
http://portal.acm.org/citation.cfm?id=513829.513853)
11. P.Briggs Register Allocation via Graph Coloring [PDF] (
http://citeseer.ist.psu.edu/102127.html)
12. GJ Chaitin Register allocation & spilling via graph coloring[PDF] (
http://www.cs.ucsd.edu/~paturi/cse202/p ... haitin.pdf)