Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!husc6!spdcc!ima!compilers-sender From: johnson@p.cs.uiuc.edu (Ralph Johnson) Newsgroups: comp.compilers Subject: a practical UNCOL Message-ID: <3937@ima.ima.isc.com> Date: 18 May 89 14:57:08 GMT Sender: compilers-sender@ima.ima.isc.com Reply-To: Ralph Johnson Lines: 35 Approved: compilers@ima.UUCP Question from editor: [Isn't this the same model that GCC uses, fairly successfully? In any event, I wonder how well it addresses machines like the 360 and to some extent the PDP-10 where there are register asymmetries, e.g. the famous 360 BXLE instruction which does "r1 += r2, if r1 <= r3 goto x", but r2 and r3 have to be in an even-odd register pair. I know that IBM's PL.8 uses a similar scheme to generate 370 code, but believe that it has a lot of hints to help put things in the right registers. I know that such instructions are now considered old-fashioned, but there are a lot of old-fashioned machines. -John] It is quite similar to the model that GCC uses. GCC has also been influenced by the work of Robert Henry at U. of Washington. Either our compiler or PO will handle instructions that combine assignments with changes of control flow. I think that other table-driven code generators, like Henry's, will also handle those kind of instructions. The technique we use for register allocation will handle register asymmetries with no problem. I don't recall how PO did it. In our compiler, converting register transfers into machine instructions creates constraints on register allocation. For example, when the register transfer r3 = r1 + r2 gets converted to a 68020 ADD instruction, registers r1 and r3 are constrained to be the same, because ADD is a two-address instruction. If this constraint cannot be met (i.e. if r1 is used later) then the register allocator will have to introduce a new logical register. We use a graph-coloring based register allocation algorithm. In general, these kinds of algorithms are good at handling constraints. Ralph Johnson [From Ralph Johnson ] -- Send compilers articles to compilers@ima.isc.com or, perhaps, Levine@YALE.EDU Plausible paths are { decvax | harvard | yale | bbn}!ima Please send responses to the originator of the message -- I cannot forward mail accidentally sent back to compilers. Meta-mail to ima!compilers-request