Register Allocation for Register Pairs

Vince Del Vecchio <>
27 Jun 1999 00:13:34 -0400

          From comp.compilers

Related articles
Register Allocation for Register Pairs (Vince Del Vecchio) (1999-06-27)
Re: Register Allocation for Register Pairs (Vince Del Vecchio) (1999-07-20)
| List of all articles for this month |

From: Vince Del Vecchio <>
Newsgroups: comp.compilers
Date: 27 Jun 1999 00:13:34 -0400
Organization: Analog Devices CPD
Keywords: registers

I'm trying to allocate aligned register pairs within a Chaitin-Briggs
graph coloring allocator. I understand the basic idea used by Briggs
("Coloring Register Pairs", LOPLAS 1,1 (Mar 1992) p.3) of adding edges
so that whether each register is colorable corresponds to whether its
degree is less than K.

However, the target architecture encourages code which often switches
between using a pair as a whole and using one or both elements singly.
As a result, the halves of a pair might have different lifetimes. I
don't understand Briggs' method of dealing with such objects, and I
was hoping someone might enlighten me.

For example, consider:

X[0,1] = .... // start of lifetime of pair X[0,1]
      ... = X[1] // X[1] dies
          A = .... // start of lifetime of singleton A
      ... = A op X[0]

Clearly, A interferes with X[0] but not X[1], so the register
allocator should be able to allocate A to the same register as X[1].
I'd like to be able to handle cases like this.

Briggs says that when the components of a pair have different
lifetimes, as here, you copy the components into different registers,
and let coalesce/simplify/select handle it. This sounds reasonable,
but if coalesce does its job, aren't you just back to the picture

It seems like you need to model that A interferes with X[0] but not
X[1]. In fact, Briggs talks about an interference between a singleton
and half of a pair:

"For example, the real half of a complex pair might be copied to
another register. In this case, the target of the copy should
interfere only with the imaginary half of the complex pair. An
interference between the target register and the real half of the pair
would prevent coalesce from combining them and eliminating the copy."

This sounds like a single edge between the single register and part of
the pair. However, if the copy is not coalesced, the interference
must contribute _2_ to the degree of the pair (an unfortunate coloring
of K/2 such half-interfering nodes could prevent the pair from being
colored), but need only contribute 1 to the degree of the singleton.
I don't see a good way to model this asymmetry in an undirected graph.

There is no mention of any of this in the paper. Does the technique
simply rely on these half-interfering nodes being coalesced away?
That would prevent using conservative coalescing exclusively, or using
iterated coalescing, and would prevent using half interferences for my
original example, in which there is nothing to coalesce.

Any insight appreciated.

-Vince Del Vecchio

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.