pardo@cs.washington.edu (David Keppel) (11/21/89)
>[All registers should be available at all points in the program > (Wish I'd said that -- Oh, I did !-)] A handy reminder: known methods for ``good'' register allocation are NP-complete. I think that they're exponential in the number of statements that are being looked at... ;-D on ( `NP': means `no problem', right? ) Pardo -- pardo@cs.washington.edu {rutgers,cornell,ucsd,ubc-cs,tektronix}!uw-beaver!june!pardo
mash@mips.COM (John Mashey) (11/22/89)
>>In article <2647@bushwood.oakhill.UUCP> oakhill!bushwood!phillip@cs.utexas.edu (Mike Phillip) writes: >>>In article <1989Nov16.212149.9770@paris.ics.uci.edu> Ron Guilmette <rfg@ics.uci.edu> writes: >> >>In defense of Mr. Phillip... > >I didn't realize that anybody was attacking him! > >>both HP PA and MIPS R3000s split the integer >>registers in approximately the same ratio as does the 88K... > >Like lemmings to the sea. Is everyone making the same mistake in the same >way? > >Inquiring minds want to know! Well, show that YOU have an inquiring mind by reading the reference that somebody already mentioned once: (I'll repeat it here, since it clearly hasn't gotten thru): (Fred Chow, Minimizing Register Usage Penalty at Procedure Calls, proc. ASPLOS III, SIGPLAN 23, 7 (July 1988) 85-94, which includes comments on caller-save and callee-save performance in the context of production compiler system that can do interprocedural register allocation, general inlining, etc, etc. Read some of the references pointed to by that paper; read Wall's paper in the same ASPLOS III. Read "Compilers for the new Generation of Hewlett-Packard Computers", Hewlett-Packard Journal, 37, 1(Jan 86) by Coutant, Hammond, and Kelley. SERIOUSLY consider reading some of these carefully-documented analyses before calling people who do it "lemmings..." Now, a few more pieces of data, in support of points that have mostly been made: a) Even when you have full-bore interprocedural register allocation generic inlining, there are still libraries, sometimes written in different languages than their calleres, and there are still assembly- language programs. b) About 50% of dynamic calls are to leaf routines. I've looked at lots of code: they almost NEVER save/restore any registers; guess what, it helps performance a bunch, given the dynamic frequency. c) On MIPS machines, the average number of registers saved per subroutine call is between 1.5 and 2, for realistic programs. d) The number is that low because there's enough registers for leaf routines (and others) to have plenty of caller-save registers to use without needing to save/restore anything. The high save/restore statistics found on older CISCs often derived from having to save registers just to have enough to do much of anything. e) Clever optimizers can be pretty smart about where they put things. For what it's worth, I've looked at lots of assembly code, and I've seldom seen many caller-save stores generated before a subroutine call. It turns out that there are plenty of dead registers lying around naturally. for example, consider the sequence: 1. (many references to X, X+1, X-Y, etc.) ... 2. function call 3. X = newvalue Now, X is naturally contained in register during part 1, and in fact, a good optimizer may well have decided to keep subexpressions involving X around, too. Now, all of those expressions are dead at 2 & 3., and a smart optimizer will have certainly tried to put them into caller-save registers. This is a simple case, but there are plenty of others where values that were worth keeping in registers become dead. Anyway, I don't know if the Motorola mix is optimal or not (and it can vary between machines and compilers), but I recall that when we looked at it, there was a reasonable range of mixtures on machines of this class that had fairly similar performance characteristics, i.e., it doesn't make a huge difference, although I'm sure the extremes would have less performance. -- -john mashey DISCLAIMER: <generic disclaimer, I speak for me only, etc> UUCP: {ames,decwrl,prls,pyramid}!mips!mash OR mash@mips.com DDD: 408-991-0253 or 408-720-1700, x253 USPS: MIPS Computer Systems, 930 E. Arques, Sunnyvale, CA 94086
rfg@ics.uci.edu (Ron Guilmette) (11/24/89)
In article <31899@winchester.mips.COM> mash@mips.COM (John Mashey) writes: > >Well, show that YOU have an inquiring mind by reading the reference >that somebody already mentioned once: (I'll repeat it here, since it >clearly hasn't gotten thru): You are right of course John, and will read that before commenting further. Also, I'd like to apologize if I offended anyone with my prior comments. I tend to shoot from the hip (before thinking). Of course that means that I often shoot myself in the foot. Given that I may have offended people, I should probably have shot myself in the mouth first. :-) // rfg