Minimização de Instruções para Acesso a Memória via Troca de Cores no Grafo de Interferência

  • Felipe Silva Universidade Estadual de Londrina
  • Marcelo Luna Universidade Estadual de Londrina
  • Wesley Attrot Universidade Estadual de Londrina

Resumo


Uma das estrat´egias mais eficientes de aloca¸c˜ao de registradores ´e baseada na colora¸c˜ao por grafos. Este trabalho descreve uma nova t´ecnica para trocar as cores em um grafo de interferˆencia que minimiza a inser¸c˜ao de c´odigo para acesso a mem´oria. Para isso, o alocador de George e Appel foi desenvolvido de duas maneiras: com a etapa de troca de cores ativada e desativada. Foram realizados experimentos com um conjunto de 27.921 grafos de programas reais. Os resultados mostraram que em alguns casos foi poss´ıvel reduzir a quantidade de vari´aveis enviadas `a mem´oria em mais de 12%.

Palavras-chave: Minimização de acesso à memória, Alocação de registradores, Coloração por grafos

Referências

A. W. Appel and L. George. Sample graph coloring problems, 1996. Access date: 18 Nov. 2014.

B. Heller, S. Seetharaman, P. Mahadevan, Y. Yiakoumis, P. Sharma, S. Banerjee, and N. McKeown. Elastictree: Saving energy in data center networks. In Proceedings of the 7th USENIX Conference on Networked Systems Design and Implementation, NSDI’10, pages 17–17, Berkeley, CA, USA, 2010. USENIX Association.

D. Bernstein, M. Golumbic, y. Mansour, R. Pinter, D. Goldin, H. Krawczyk, and I. Nahshon. Spill code minimization techniques for optimizing compliers. In Proceedings of the ACM SIGPLAN 1989 Conference on Programming Language Design and Implementation, PLDI ’89, pages 258–263, New York, NY, USA, 1989. ACM.

F. M. Q. a. Pereira. Register Allocation by Puzzle Solving by. PhD thesis, University of California, 2008.

G. J. Chaitin. Register allocation & spilling via graph coloring. In Proceedings of the 1982 SIGPLAN Symposium on Compiler Construction, SIGPLAN ’82, pages 98–105, New York, NY, USA, 1982. ACM.

K. D. Cooper and L. T. Simpson. Live range splitting in a graph coloring register allocator. In Compiler Construction, 7th International Conference, CC’98, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS’98, Lisbon, Portugal, March 28 - April 4, 1998, Proceedings, pages 174–187, 1998.

L. George and A. W. Appel. Iterated register coalescing. ACM Trans. Program. Lang. Syst., 18(3):300–324, May 1996.

M. P. Mills. The cloud begins with coal: the report, 2013. Access date: 21 Jan. 2015.

P. Bergner, P. Dahl, D. Engebretsen, and M. O’Keefe. Spill code minimization via interference region spilling. In Proceedings of the ACM SIGPLAN 1997 Conference on Programming Language Design and Implementation, PLDI ’97, pages 287–295, New York, NY, USA, 1997. ACM.

P. Briggs, K. D. Cooper, and L. Torczon. Rematerialization. In S. I. Feldman and R. L. Wexelblat, editors, PLDI, pages 311–321. ACM, 1992.

P. Briggs. Register Allocation via Graph Coloring. PhD thesis, 1992.

V. Tiwari, S. Malik, A. Wolfe, and M.-C. Lee. Instruction level power analysis and optimization of software. In Proceedings of 9th International Conference on VLSI Design, pages 326–328. IEEE Comput. Soc. Press, Jan. 1996.
Publicado
26/05/2015
Como Citar

Selecione um Formato
SILVA, Felipe; LUNA, Marcelo; ATTROT, Wesley. Minimização de Instruções para Acesso a Memória via Troca de Cores no Grafo de Interferência. In: SIMPÓSIO BRASILEIRO DE SISTEMAS DE INFORMAÇÃO (SBSI), 11. , 2015, Goiânia. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2015 . p. 483-486. DOI: https://doi.org/10.5753/sbsi.2015.5891.