Browse Prior Art Database

Limiting Lifetimes of Register Sequences to Improve Register Allocation

IP.com Disclosure Number: IPCOM000116783D
Original Publication Date: 1995-Nov-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 4 page(s) / 136K

Publishing Venue

IBM

Related People

Aizikovitz, NE: AUTHOR [+7]

Abstract

Disclosed is a method in an optimizing compiler of limiting lifetimes of register sequences in order to minimize their impact on register allocation.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 41% of the total text.

Limiting Lifetimes of Register Sequences to Improve Register Allocation

      Disclosed is a method in an optimizing compiler of limiting
lifetimes of register sequences in order to minimize their impact on
register allocation.

      The main aim of register allocation within an optimizing
compiler is to maximize the utilization of the target machine's
register set.  This implies keeping information in registers as long
as possible and minimizing both spill code and register to register
copies in order to minimize run time.

      In the past, computer instruction sets have only included
instructions that manipulate a single register at a time; but today,
many architectures include instructions that can load and store pairs
or longer sequences of registers.  These register sequences may
represent character strings, long floating-point values, long
addresses, etc.  Often the architecture requires that these sequences
be aligned along an even- or quad-register boundary.  This increases
the complexity of the register allocator.

      Furthermore, these register sequences can unnecessarily waste
register resources, resulting in poor register utilization and
unnecessary generation of spill code.  For example, it often happens
that part of a loaded register sequence remains live for a long
period, while the remaining registers in the sequence do not.  If the
entire register sequence is treated as a unit, all of the registers
must be treated as being live, thus artificially increasing register
pressure.

      Treating register sequences as a unit can also increase the
amount of unnecessary spill code that is generated.  If register
pressure exceeds the number of physical registers at a program point
where a register sequence is live, the register allocator may have to
spill the sequence.  If the entire sequence is treated as a unit, the
whole sequence is spilled even if some registers in the sequence are
no longer live.  Indeed, if the register lifetimes were treated
individually, it might not have even been necessary to spill at all.

      The present invention recognizes that many tasks within the
register allocator are simplified if one knows that the lifetimes of
register sequences are guaranteed to be short.  Unfortunately,
instruction schedulers in compilers for modern Reduced Instruction
Set Computer/Cycles (RISC) architectures can easily greatly increase
the lifetimes of register sequences.

      To keep lifetimes of register sequences as small as possible,
our compiler does not generate instructions that load and store
register sequences until after register allocation has completed.
Instead, the intermediate representation of the program prior to
register allocation uses special indivisible "superinstructions"
that represent operations on register sequences.  To the register
allocator, it appears that the lifetime of each register sequence is
limited to a single superinstruction.  This makes re...