roy@phri.UUCP (Roy Smith) (07/20/87)
Imagine the following (rather silly) function:
struct foo {struct foo *next;};
f(s, p)
char *s;
struct foo *p
{
register char *rs;
register struct foo *rp;
for (rs = s; *rs != NULL; rs++);
for (rp = p; rp->next != NULL; rp = rp->next);
}
Are there any C compilers (or other languages, for that matter)
which are smart enough to realize that rs and rp could be put in the same
register? In Fortran you would write this as "EQUIVALENCE (RS, RP)" and
the compiler wouldn't have to be smart at all, but that's cheating.
Actually, I guess a really smart compiler might optimize the whole
function down to:
f() { return; }
--
Roy Smith, {allegra,cmcl2,philabs}!phri!roy
System Administrator, Public Health Research Institute
455 First Avenue, New York, NY 10016bright@dataio.Data-IO.COM (Walter Bright) (07/20/87)
In article <2803@phri.UUCP< roy@phri.UUCP (Roy Smith) writes:
< Imagine the following (rather silly) function:
<struct foo {struct foo *next;};
<f(s, p) char *s; struct foo *p
<{ register char *rs;
< register struct foo *rp;
<
< for (rs = s; *rs != NULL; rs++);
< for (rp = p; rp-<next != NULL; rp = rp-<next);
<}
< Are there any C compilers (or other languages, for that matter)
<which are smart enough to realize that rs and rp could be put in the same
<register?
The Datalight C compiler uses register allocation by coloring in order
to put rs and rp into the same register. I should know, I wrote it.henry@utzoo.UUCP (Henry Spencer) (07/20/87)
> Are there any C compilers (or other languages, for that matter) > which are smart enough to realize that rs and rp could be put in the same > register?... Any optimizing compiler worth its salt, for C or most anything else, will recognize that one. Good register allocation is a major area of concern for serious optimizers. -- Support sustained spaceflight: fight | Henry Spencer @ U of Toronto Zoology the soi-disant "Planetary Society"! | {allegra,ihnp4,decvax,utai}!utzoo!henry
devine@vianet.UUCP (Bob Devine) (07/20/87)
In article <2803@phri.UUCP>, roy@phri.UUCP (Roy Smith) writes: > Are there any C compilers (or other languages, for that matter) > which are smart enough to realize that rs and rp could be put in the same > register? In Fortran you would write this as "EQUIVALENCE (RS, RP)" and > the compiler wouldn't have to be smart at all, but that's cheating. You can increase the likelihood of register re-use if you break up the function into blocks that each declare their own "local" variables. I don't know which compilers will re-use (I believe that PCC descendants will) but this is strictly an implementators choice. Bob Devine [[ Here is the posted code rewritten into blocks. ]] { { register char *rs; for (rs = s; *rs != NULL; rs++); } { register struct foo *rp; for (rp = p; rp->next != NULL; rp = rp->next); } }
ron@topaz.rutgers.edu (Ron Natalie) (07/21/87)
> f(s, p) > char *s; > struct foo *p > { > register char *rs; > register struct foo *rp; > > for (rs = s; *rs != NULL; rs++); > for (rp = p; rp->next != NULL; rp = rp->next); > } Most C compilers are trully one pass jobs (note the frequent "jump to the end of the function to allocate the stack because by then we'll know how much to allocate hack" that many compilers use). They have no way of knowing that after the first "for" loop that "rs" will not be used again. Why not give it some help... f(s,p)...{ { register char *rs; for(rs = s; *rs != NULL; rs++); }{ register struct foo *rp; for( rp = p ... } } -Ron
ka@hropus.UUCP (Kenneth Almquist) (07/21/87)
> Imagine the following (rather silly) [code]: > register char *rs; > register struct foo *rp; > > for (rs = s; *rs != NULL; rs++); > for (rp = p; rp->next != NULL; rp = rp->next); > return; > Are there any C compilers (or other languages, for that matter) > which are smart enough to realize that rs and rp could be put in the same > register? There are certainly a lot of compilers for languages other than C which are that smart, IBM's PL/1 Optimizing Compiler being just one example. > In Fortran you would write this as "EQUIVALENCE (RS, RP)" and > the compiler wouldn't have to be smart at all, but that's cheating. In C, you should write: { register char *rs; for (rs = s; *rs != NULL; rs++); } { register struct foo *rp; for (rp = p; rp->next != NULL; rp = rp->next); } The standard joke is that in the C world, you don't have optimizing compilers, you have optimizing programmers. By the way, the FORTRAN equivalence statement may very well scare the optimizer out of putting either RS or RP in registers. Kenneth Almquist
grk@sfsup.UUCP (G.R.Kuntz) (07/22/87)
In article <1331@dataio.Data-IO.COM>, bright@dataio.UUCP writes: < In article <2803@phri.UUCP< roy@phri.UUCP (Roy Smith) writes: < < Imagine the following (rather silly) function: < <struct foo {struct foo *next;}; < <f(s, p) char *s; struct foo *p < <{ register char *rs; < < register struct foo *rp; < < < < for (rs = s; *rs != NULL; rs++); < < for (rp = p; rp-<next != NULL; rp = rp-<next); < <} < < Are there any C compilers (or other languages, for that matter) < <which are smart enough to realize that rs and rp could be put in the same < <register? < < The Datalight C compiler uses register allocation by coloring in order < to put rs and rp into the same register. I should know, I wrote it. On my master's thesis compiler I too did register allocation by graph coloring and so would put both rs and rp into the same register. -- G. Ralph Kuntz N2HBN UUCP: {ihnp4,allegra}!attunix!grk ARPA: rutgers.rutgers.edu!pisc2b!grk
stuart@bms-at.UUCP (Stuart D. Gathman) (07/22/87)
The GNU compiler reuses registers. It is free from the Free Software Foundation in source form. Machine descriptions for vax and 680?0 are included. -- Stuart D. Gathman <stuart@bms-at.uucp> <..!seismo!dgis!bms-at!stuart>
fnf@mcdsun.UUCP (Fred Fish) (07/23/87)
In article <2803@phri.UUCP> roy@phri.UUCP (Roy Smith) writes: > > Imagine the following (rather silly) function: > [...deleted...] > Are there any C compilers (or other languages, for that matter) >which are smart enough to realize that rs and rp could be put in the same >register? In Fortran you would write this as "EQUIVALENCE (RS, RP)" and The GNU C compiler emits: .globl _f .text .even _f: link a6,#0 movl a6@(12),d0 movl a6@(8),a0 tstb a0@ <--- use a0 for first pointer jeq L13 L2: addql #1,a0 tstb a0@ jne L2 L13: movl d0,a0 tstl a0@ <--- reuse a0 for second pointer jeq L12 L7: movl a0@,a0 tstl a0@ jne L7 L12: unlk a6 rts So the answer is yes, and it won't even cost you an arm and a leg... -Fred -- = Drug tests; just say *NO*! = Fred Fish Motorola Computer Division, 3013 S 52nd St, Tempe, Az 85282 USA = seismo!noao!mcdsun!fnf (602) 438-3614
john@rufus.molly.UUCP (John Franks) (07/24/87)
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? -- John Franks Dept of Math. Northwestern University UUCP john@molly.uucp Internet john%molly.uucp@eecs.nwu.edu
bright@dataio.Data-IO.COM (Walter Bright) (07/27/87)
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? For register AX, you color in the top part of the A... :-) But seriously, Imagine an x-y graph. The each point on the horizontal axis corresponds to one statement in the program. Each point on the vertical axis corresponds to a variable that could be allocated to a register. Now graph with a pencil each x-y point where the value of variable y is required at point x. (This is called the 'live range' of each variable.) Now aquire a crayon for each register you have, a different color for each crayon. Find a way of assigning a crayon to each variable such that when the graph is redrawn with the crayons, at no statement x do any two variables have the same color. In other words, you can never have two variables assigned to the same register at the same time, and two variable can occupy the same register if their usages do not overlap.
grk@sfsup.UUCP (08/07/87)
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