A generalized algorithm for graph-coloring register allocation Export

@inproceedings{smith04regalloc, abstract = {Graph-coloring register allocation is an elegant and extremely popular optimization for modern machines. But as currently formulated, it does not handle two characteristics commonly found in commercial architectures. First, a single register name may appear in multiple register classes, where a class is a set of register names that are interchangeable in a particular role. Second, multiple register names may be aliases for a single hardware register. We present a generalization of graph-coloring register allocation that handles these problematic characteristics while preserving the elegance and practicality of traditional graph coloring. Our generalization adapts easily to a new target machine, requiring only the sets of names in the register classes and a map of the register aliases. It also drops easily into a well-known graph-coloring allocator, is efficient at compile time, and produces high-quality code.}, address = {New York, NY, USA}, author = {Smith, Michael D. and Ramsey, Norman and Holloway, Glenn}, booktitle = {PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation}, citeulike-article-id = {240596}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=996875}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/996841.996875}, doi = {10.1145/996841.996875}, isbn = {1-58113-807-5}, keywords = {compilers, pldi, register\_allocation}, location = {Washington DC, USA}, month = {May}, number = {6}, pages = {277--288}, posted-at = {2009-10-22 14:48:04}, priority = {0}, publisher = {ACM}, title = {A generalized algorithm for graph-coloring register allocation}, url = {http://dx.doi.org/10.1145/996841.996875}, volume = {39}, year = {2004} }

TY - CONF ID - smith04regalloc L3 - citeulike-article-id:240596 N2 - Graph-coloring register allocation is an elegant and extremely popular optimization for modern machines. But as currently formulated, it does not handle two characteristics commonly found in commercial architectures. First, a single register name may appear in multiple register classes, where a class is a set of register names that are interchangeable in a particular role. Second, multiple register names may be aliases for a single hardware register. We present a generalization of graph-coloring register allocation that handles these problematic characteristics while preserving the elegance and practicality of traditional graph coloring. Our generalization adapts easily to a new target machine, requiring only the sets of names in the register classes and a map of the register aliases. It also drops easily into a well-known graph-coloring allocator, is efficient at compile time, and produces high-quality code. CY - Washington DC, USA IS - 6 SN - 1-58113-807-5 AD - New York, NY, USA EP - 288 TI - A generalized algorithm for graph-coloring register allocation PB - ACM VL - 39 T2 - PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation SP - 277 KW - compilers KW - pldi KW - register_allocation AU - Smith, Michael AU - Ramsey, Norman AU - Holloway, Glenn PY - 2004/05// UR - http://dx.doi.org/10.1145/996841.996875 ER -