Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!seismo!rutgers!bellcore!faline!scherzo!allegra!ulysses!sfmag!sfsup!grk
From: grk@sfsup.UUCP
Newsgroups: comp.lang.c
Subject: Re: re-using registers
Message-ID: <1789@sfsup.UUCP>
Date: Fri, 7-Aug-87 10:27:31 EDT
Article-I.D.: sfsup.1789
Posted: Fri Aug  7 10:27:31 1987
Date-Received: Sun, 9-Aug-87 11:36:35 EDT
References: <2803@phri.UUCP> <1331@dataio.Data-IO.COM> <1668@sfsup.UUCP> <1334@dataio.Data-IO.COM>
Organization: AT&T-IS, Summit N.J. USA
Lines: 217
Summary: more off-color graphs :-)

WARNING! LONG! SKIP IF YOU SUFFER FROM EXTREME BOREDOM!

In article <1334@dataio.Data-IO.COM>, bright@dataio.Data-IO.COM (Walter Bright) writes:
> In article <358@rufus.molly.UUCP> john@rufus.molly.UUCP (John Franks) writes:
> >In article <1668@sfsup.UUCP>, grk@sfsup.UUCP (G.R.Kuntz) writes:
> >> On my master's thesis compiler I too did register allocation by graph coloring
> >Anybody want to explain what is register allocation by coloring?

While doing code generation we imagine that we have an ideal machine with an
unlimited number of registers.  For example, lets say we want to evaluate the
following expression:

		auto short a[4], i, b;

		a[i + 1] = a[i + 1] * i + b;

with the following frame layout:

		a[0]:	0(fp)
		a[1]:	2(fp)
		a[2]:	4(fp)
		a[3]:	6(fp)
		i:	8(fp)
		b:	10(fp)

The sample expression might generate the following pseudo-assembly:

	1:	t0 <- *8(fp)		/* contents of i */
	2:	t1 <- 1			/* guess :-) */
	3:	t2 <- t0 + t1		/* i + 1 */
	4:	t3 <- t2 * 2		/* offset by size of one element */
	5:	t4 <- adr[0(fp)]	/* address of a[0] */
	6:	t5 <- t3 + t4		/* address of a[i + 1] */
	7:	t6 <- *t5		/* fetch a[i + 1] */
	8:	t7 <- t6 * t0		/* a[i + 1] * i */
	9:	t8 <- *10(fp)		/* contents of b */
	10:	t9 <- t7 + t8		/* a[i + 1] * i + b */
	11:	*t5 <- t9		/* a[i + 1] = a[i + 1] * i + b */

Now we've got to assign all of the various t? to real registers.  We first
decide the live-ness of each pRegister (pseudo-register) as follows:

		first used		last used
		----------		---------
	t0	    1			    8
	t1	    2			    3
	t2	    3			    4
	t3	    4			    6
	t4	    5			    6
	t5	    6			    11
	t6	    7			    8
	t7	    8			    10
	t8	    9			    10
	t9	    10			    11

We now draw a graph in which the nodes are the pRegisters and an edge between
two nodes indicates that both of those pRegisters are in use at the same time:

			  ______ 1
			 /
		6 _____ 0 ______ 2
		|      /|\
	  7 ___ 5 ____/ | \_____ 3
	  |    /|       \        |
	  8 __/ 9        \______ 4

Assume our real machine has 3 registers.  We begin removing nodes from the
graph that contain 3 or less edges, and remember the order that we remove
them:

	remove 8:

			  ______ 1
			 /
		6 _____ 0 ______ 2
		|      /|\
	  7 ___ 5 ____/ | \_____ 3
	        |       \        |
	        9        \______ 4

	remove 6:
			  ______ 1
			 /
		        0 ______ 2
		       /|\
	  7 ___ 5 ____/ | \_____ 3
	        |       \        |
	        9        \______ 4

	remove 5:
			  ______ 1
			 /
		        0 ______ 2
		        |\
	  7             | \_____ 3
	                \        |
	        9        \______ 4

	remove 3:
			  ______ 1
			 /
		        0 ______ 2
		        |
	  7             |
	                \
	        9        \______ 4

	remove 0:
			         1
			 
		                 2

	  7

	        9                4

	remove the rest in arbitrary order 1, 2, 4, 7, 9

Let's assign "colors" to our real registers as follows:

	r0:	red (R)
	r1:	green (G)
	r2:	blue (B)

We removed the nodes from the graph in the following order:

	8, 6, 5, 3, 0, 1, 2, 4, 7, 9

Reverse them:

	9, 7, 4, 2, 1, 0, 3, 5, 6, 8

and we assign the colors by referring to the original graph and making
sure that there is no overlap:

	9, 7, 4, 2, 1 can all get red since they do not touch:

			  ______ R
			 /
		6 _____ 0 ______ R
		|      /|\
	  R ___ 5 ____/ | \_____ 3
	  |    /|       \        |
	  8 __/ R        \______ R

	0 gets an unused color, say green:

			  ______ R
			 /
		6 _____ G ______ R
		|      /|\
	  R ___ 5 ____/ | \_____ 3
	  |    /|       \        |
	  8 __/ R        \______ R

	3 and 5 get blue:

			  ______ R
			 /
		6 _____ G ______ R
		|      /|\
	  R ___ B ____/ | \_____ B
	  |    /|       \        |
	  8 __/ R        \______ R

	6 becomes red:

			  ______ R
			 /
		R _____ G ______ R
		|      /|\
	  R ___ B ____/ | \_____ B
	  |    /|       \        |
	  8 __/ R        \______ R

	finally, 8 becomes green:

			  ______ R
			 /
		R _____ G ______ R
		|      /|\
	  R ___ B ____/ | \_____ B
	  |    /|       \        |
	  G __/ R        \______ R

Now our original code looks like the following:

	1:	r1 <- *8(fp)		/* contents of i */
	2:	r0 <- 1			/* guess :-) */
	3:	r0 <- r1 + r0		/* i + 1 */
	4:	r2 <- r0 * 2		/* offset by size of one element */
	5:	r0 <- adr[0(fp)]	/* address of a[0] */
	6:	r2 <- r2 + r0		/* address of a[i + 1] */
	7:	r0 <- *r2		/* fetch a[i + 1] */
	8:	r0 <- r0 * r1		/* a[i + 1] * i */
	9:	r1 <- *10(fp)		/* contents of b */
	10:	r0 <- r0 + r1		/* a[i + 1] * i + b */
	11:	*r2 <- r0		/* a[i + 1] = a[i + 1] * i + b */

and in real code:

	move	8(fp),r1
	move	1,r0		/* could have been better */
	add2	r1,r0
	mul3	r0,2,r2		/* peephole changes to shift left 1 */
	movadr	0(fp),r0
	add2	r0,r2
	move	*r2,r0
	mul2	r1,r0
	move	10(fp),r1
	add2	r1,r0
	move	r0,*r1

Hope this long-winded discussion helps.
-- 
	G. Ralph Kuntz N2HBN	UUCP: {ihnp4,allegra}!attunix!grk
				ARPA: rutgers.rutgers.edu!pisc2b!grk