lindsay@k.gp.cs.cmu.edu (Donald Lindsay) (07/08/88)
In article <8444@pur-ee.UUCP> hankd@pur-ee.UUCP (Hank Dietz) writes: >... As for the number of registers, we've >recently found that a perfect (or just really good) global register >allocator should rarely want more than about 10 registers per processor... >We used the standard MIPS benchmarks, which are admittedly small programs... >We also constructed random intereference graphs and obtained very similar >results even for graph-coloring register allocation using very large graphs >which are very strongly connected (up to thousands of nodes, with each node >connected to as many as 90% of all other nodes) ... >Further note that we didn't put "variables" in registers; we put "live >values" in registers and that makes quite a difference. >Of course, your mileage may vary... but 16 registers seems to be plenty. Depending on language and architecture, registers may hold: - uplevel addressing link - exception handler pointer (for Ada) - frame pointer - program counter - stack pointer - actual parameters - return value(s) - constant pool pointer (thank you, IBM RT) - spare space for called routines to trash - registers reserved for link-time-generated code to use Plus, optimizing compilers transform graphs so that they have more data. (For example, common subexpression elimination, loop hoisting, and strength reduction.) Plus, code generation involves putting in all kinds of address calculation. Optimization of this code involves keeping lots of these addresses around. Plus, there has been interesting work recently in interprocedural optimization. The live sets are additive, since the lifetimes nest. Summary: there are profitable uses for more-than-16 registers. -- Don lindsay@k.gp.cs.cmu.edu CMU Computer Science "Imitation is not the sincerest form of flattery. Payments are." - a British artist who died penniless before copyright law.