Re: What ideas are better for assigning registers to terminals?

Torben Mogensen <torbenm@diku.dk>
20 Sep 1999 11:57:23 -0400

          From comp.compilers

Related articles
What ideas are better for assigning registers to terminals? bill@megahits.com (Bill A.) (1999-09-16)
Re: What ideas are better for assigning registers to terminals? torbenm@diku.dk (Torben Mogensen) (1999-09-20)
Re: What ideas are better for assigning registers to terminals? johnmce@world.std.com (1999-09-20)
| List of all articles for this month |

From: Torben Mogensen <torbenm@diku.dk>
Newsgroups: comp.compilers
Date: 20 Sep 1999 11:57:23 -0400
Organization: Compilers Central
References: 99-09-060
Keywords: registers, optimize

Bill Auerbach wrote:


>If an operator at a node must use a specific processor register to
>calculate the result, is it better to:
>
>1. Traverse the tree and pre-assign these registers, then globally
>allocate registers using these fixed ones as predetermined and
>unchangeable, or
>
>2. Globally allocate across the function and add register copies to
>satisfy the requirements of the operators needing specific registers
>(which implies possibly having to spill a globally allocated one to
>free it for use by the operator).




A third alternative is presented in Andrew Appel's "Tiger" compiler
books (Modern Compiler Implementation in ML/Java/C): Before register
allocation you insert copies from/to unnamed registers to/from the
specific registers you need. You then do register allocation with
coalescing.


Coalescing is a twist on register allocation that tries to eliminate
register-to-register moves by assigning source and destination to the
same register, if this can be done without causing spills in other
places. The method described by Appel keeps groups of MOVE-related
variables around and uses the following strategy:


  1) Simplify the interference graph by removing un-grouped variables
        that have less than N neighbours.


  2) If a group of variables has a total of less than N neighbours,
        then the variables in the group are coalesced into a single
        variable, and we go to step 1.


  3) If this can't be done, find a grouped variable that by itself has
        less than N neigbours and take it out of the group, and then go to
        step 1.


  4) If not done, do a normal spill and go to step 1.


Torben Mogensen (torbenm@diku.dk)


Post a followup to this message

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