Rei Odaira 
contact information
5122869989 links
Professional Associations
Professional Associations: ACM | Information Processing Society of Japan (IPSJ)- Profile
- Publications
- Patents
- Code Patch to the STAMP Benchmarks for Hardware Transdactional Memory (HTM)
- IISWC 2014 Paper
- PPoPP 2014 Paper
- IISWC 2013 Paper
- Research Report: Eliminating GIL in Ruby through HTM
- ASPLOS 2012 Paper
- CGO 2010 Paper
- VEE 2010 Paper
- ISCA 2015 Paper
- Code Patch to Eliminate Global Interpreter Lock (GIL) in Ruby through Hardware Transactional Memory
- RubyのGVLにHTMを用いるパッチ
CGO 2010 Paper
Coloring-based Coalescing for Graph Coloring Register Allocation.
Rei Odaira, Takuya Nakaike, Tatsushi Inagaki, Hideaki Komatsu, and Toshio Nakatani.
In Proceedings of the 2010 International Symposium on Code Generation and Optimization (CGO), pp.160-169, 2010.
Full text [PDF]: CGO2010_ColoringBasedCoalescing.pdf
Slides [PDF]: CGO2010_ColoringBasedCoalescing_Slides.pdf
Abstract
Graph coloring register allocation tries to minimize the total cost of spilled live ranges of variables. Live-range splitting and coalescing are often performed before the coloring to further reduce the total cost. Coalescing of split live ranges, called sub-ranges, can decrease the total cost by lowering the interference degrees of their common interference neighbors. However, it can also increase the total cost because the coalesced sub-ranges can become uncolorable. In this paper, we propose coloring-based coalescing, which first performs trial coloring and next coalesces all copyrelated sub-ranges that were assigned the same color. The coalesced graph is then colored again with the graph coloring register allocation. The rationale is that coalescing of differently colored sub-ranges could result in spilling because there are some interference neighbors that prevent them from being assigned the same color. Experiments on Java programs show that the combination of live-range splitting and coloring-based coalescing reduces the static spill cost by more than 6% on average, comparing to the baseline coloring without splitting. In contrast, well-known iterated and optimistic coalescing algorithms, when combined with splitting, increase the cost by more than 20%. Coloring-based coalescing improves the execution time by up to 15% and 3% on average, while the existing algorithms improve by up to 12% and 1% on average.
Copyright
Copyright (C) 2010 by Association for Computing Machinery, Inc. Permission to make digital or hard copies of part of all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.