Zero-cost range splitting
- 1 June 1994
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 29 (6), 257-265
- https://doi.org/10.1145/178243.178420
Abstract
This paper presents a new optimization technique that uses empty delay slots to improve code scheduling. We are able to split live ranges for free, by inserting spill code into empty delay slots. Splitting a live range can reduce interferences with other live ranges and can sometimes free registers. Live ranges no longer interfering with the split live range can sometimes make use of the extra register.Our algorithm, as a final pass over the code, exploits empty delay slots that would remain unused if spill code was not inserted. This paper proposes a variety of optimizations that use the extra registers generated from live range splitting, including coalescing live ranges and improving code scheduling. We present an algorithm for improving code scheduling and present implementation results.Keywords
This publication has 16 references indexed in Scilit:
- Register allocation with instruction schedulingPublished by Association for Computing Machinery (ACM) ,1993
- RematerializationPublished by Association for Computing Machinery (ACM) ,1992
- A retargetable compiler for ANSI CACM SIGPLAN Notices, 1991
- The priority-based coloring approach to register allocationACM Transactions on Programming Languages and Systems, 1990
- Register allocation across procedure and module boundariesPublished by Association for Computing Machinery (ACM) ,1990
- Improving register allocation for subscripted variablesPublished by Association for Computing Machinery (ACM) ,1990
- Register allocation in the SPUR Lisp compilerPublished by Association for Computing Machinery (ACM) ,1986
- Register allocation & spilling via graph coloringPublished by Association for Computing Machinery (ACM) ,1982
- Register allocation via coloringComputer Languages, 1981
- Complete Register Allocation ProblemsSIAM Journal on Computing, 1975