Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!mcsun!ukc!dcl-cs!aber-cs!athene!pcg From: pcg@cs.aber.ac.uk (Piercarlo Grandi) Newsgroups: comp.arch Subject: One obvious reference for coloring and registers Message-ID: Date: 28 Jan 91 11:40:47 GMT Sender: aro@aber-cs.UUCP Organization: Coleg Prifysgol Cymru Lines: 55 Nntp-Posting-Host: odin I was rereading the recent register count debate, and I realized that I had mentioned David Wall on the poverty of conventional static based register coloring, and then that probably me and Preston Briggs read more recent work in quite different ways; I have realized that one of such more recent papers I was unconsciously thinking of all the time, but I never mentioned explicitly. It is Chow&Hennessy on priority based register coloring. In my biased and malicious way of looking at things, I had gotten from it the impression that it said: 1) static register coloring is baaaad. 2) priorities based on expected frequency of dynamic use should be attached to values; *after* this is done coloring should be run to allocate the higher priority values to registers. 3) even pretty simple estimates of the dynamic use of values (assume all loops run for 10 times) seem to give good results, except for some cases. 4) on a MIPS R2000 the use of priorities before coloring means that, for a fairly wide spectrum on nonfloat applications, one gets comparable performance (but I think not the same code size) with just 8 (4+4) spare registers instead of the 21 (12+9) available (results for the intermediate cases are also given). It is interesting to compare these numbers with my own smaller scale experiments with the GNU cc register allocator on the same platform. The paper is in the October 1990 issues of TOPLAS; it was submitted January 1988. I have not been aware of it until recently therefore, but I have an interesting speculation about somebody else. John Mashey had explicitly denied (after I had specifically asked him on these screens) having any results available about varying the number of registers used by the MIPS code generator (he said some old experiments maybe had been done, but had been forgotten). Strange, because one of the authors of the paper works for MIPSco, John Mashey is personally thanked by both authors, and in the paper it is written that the results of the research described in the paper have been incorporated into MIPSco's commercial compiler suite. My speculation is: if it had been known earlier that MIPSco knew that there might be reason to think that about half their register set is redundant in scalar implementation of their architecture, their having long term plans to go superscalar would have been made very obvious much earlier than they wished. Rumour mongering again... :-) -- Piercarlo Grandi | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk