An efficient hybrid scheme has been developed for optimizing register allocation applicable to CISC and RISC processors, which is crucial for maximizing their execution speed. Graph-coloring at the function level is combined with a powerful local register assigner. This assigner uses accurate program flows and access patterns of variables, and optimizes a wider local range, called an extended basic-block (EBB), than other optimizing compilers. The EBB is a set of basic-blocks that constitute a tree-shaped control flow, which is suitable for the large nested branches that frequently appear in embedded system-control programs, such as those for telephone call processing. The coloring at the function level involves only the live-ranges of program variables that span EBBs. The interference graph is therefore very small even for large functions, so it can be constructed quickly. Instead of iterative live-range splitting or spilling, the unallocated live-ranges are optimized by the EBB-based register assigner, so neither load/store insertion nor code motion is needed. This facilitates generating reliable code and debug symbols. The information provided for the EBB-based assigner facilitates the priority-based heuristics, fine-grained interference checking, and deferred coloring, all of which increase the colorability. Using a thread-support package for CHILL as a sample program, performance measurement showed that local variables are successfully located in registers, and the reduction of static cycles is about 20-30%. Further improvements include using double registers and improving debuggability.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Norio SATO, "Efficient Hybrid Allocation of Processor Registers for Compiling Telephone Call Control Programs" in IEICE TRANSACTIONS on Communications,
vol. E81-B, no. 10, pp. 1868-1880, October 1998, doi: .
Abstract: An efficient hybrid scheme has been developed for optimizing register allocation applicable to CISC and RISC processors, which is crucial for maximizing their execution speed. Graph-coloring at the function level is combined with a powerful local register assigner. This assigner uses accurate program flows and access patterns of variables, and optimizes a wider local range, called an extended basic-block (EBB), than other optimizing compilers. The EBB is a set of basic-blocks that constitute a tree-shaped control flow, which is suitable for the large nested branches that frequently appear in embedded system-control programs, such as those for telephone call processing. The coloring at the function level involves only the live-ranges of program variables that span EBBs. The interference graph is therefore very small even for large functions, so it can be constructed quickly. Instead of iterative live-range splitting or spilling, the unallocated live-ranges are optimized by the EBB-based register assigner, so neither load/store insertion nor code motion is needed. This facilitates generating reliable code and debug symbols. The information provided for the EBB-based assigner facilitates the priority-based heuristics, fine-grained interference checking, and deferred coloring, all of which increase the colorability. Using a thread-support package for CHILL as a sample program, performance measurement showed that local variables are successfully located in registers, and the reduction of static cycles is about 20-30%. Further improvements include using double registers and improving debuggability.
URL: https://global.ieice.org/en_transactions/communications/10.1587/e81-b_10_1868/_p
Copy
@ARTICLE{e81-b_10_1868,
author={Norio SATO, },
journal={IEICE TRANSACTIONS on Communications},
title={Efficient Hybrid Allocation of Processor Registers for Compiling Telephone Call Control Programs},
year={1998},
volume={E81-B},
number={10},
pages={1868-1880},
abstract={An efficient hybrid scheme has been developed for optimizing register allocation applicable to CISC and RISC processors, which is crucial for maximizing their execution speed. Graph-coloring at the function level is combined with a powerful local register assigner. This assigner uses accurate program flows and access patterns of variables, and optimizes a wider local range, called an extended basic-block (EBB), than other optimizing compilers. The EBB is a set of basic-blocks that constitute a tree-shaped control flow, which is suitable for the large nested branches that frequently appear in embedded system-control programs, such as those for telephone call processing. The coloring at the function level involves only the live-ranges of program variables that span EBBs. The interference graph is therefore very small even for large functions, so it can be constructed quickly. Instead of iterative live-range splitting or spilling, the unallocated live-ranges are optimized by the EBB-based register assigner, so neither load/store insertion nor code motion is needed. This facilitates generating reliable code and debug symbols. The information provided for the EBB-based assigner facilitates the priority-based heuristics, fine-grained interference checking, and deferred coloring, all of which increase the colorability. Using a thread-support package for CHILL as a sample program, performance measurement showed that local variables are successfully located in registers, and the reduction of static cycles is about 20-30%. Further improvements include using double registers and improving debuggability.},
keywords={},
doi={},
ISSN={},
month={October},}
Copy
TY - JOUR
TI - Efficient Hybrid Allocation of Processor Registers for Compiling Telephone Call Control Programs
T2 - IEICE TRANSACTIONS on Communications
SP - 1868
EP - 1880
AU - Norio SATO
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E81-B
IS - 10
JA - IEICE TRANSACTIONS on Communications
Y1 - October 1998
AB - An efficient hybrid scheme has been developed for optimizing register allocation applicable to CISC and RISC processors, which is crucial for maximizing their execution speed. Graph-coloring at the function level is combined with a powerful local register assigner. This assigner uses accurate program flows and access patterns of variables, and optimizes a wider local range, called an extended basic-block (EBB), than other optimizing compilers. The EBB is a set of basic-blocks that constitute a tree-shaped control flow, which is suitable for the large nested branches that frequently appear in embedded system-control programs, such as those for telephone call processing. The coloring at the function level involves only the live-ranges of program variables that span EBBs. The interference graph is therefore very small even for large functions, so it can be constructed quickly. Instead of iterative live-range splitting or spilling, the unallocated live-ranges are optimized by the EBB-based register assigner, so neither load/store insertion nor code motion is needed. This facilitates generating reliable code and debug symbols. The information provided for the EBB-based assigner facilitates the priority-based heuristics, fine-grained interference checking, and deferred coloring, all of which increase the colorability. Using a thread-support package for CHILL as a sample program, performance measurement showed that local variables are successfully located in registers, and the reduction of static cycles is about 20-30%. Further improvements include using double registers and improving debuggability.
ER -