Path: utzoo!utgpu!utstat!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!rutgers!apple!voder!pyramid!prls!philabs!linus!spdcc!ima!compilers-sender From: johnson@p.cs.uiuc.edu (Ralph Johnson) Newsgroups: comp.compilers Subject: a practical UNCOL Message-ID: <3892@ima.ima.isc.com> Date: 11 May 89 02:59:05 GMT Sender: compilers-sender@ima.ima.isc.com Reply-To: Ralph Johnson Lines: 56 Approved: compilers@ima.UUCP The work of Davidson and Fraser points the way to a practical UNCOL. We have been using a register transfer langauge as an intermediate language in an optimizing compiler for Smalltalk. Davidson and Fraser designed a machine independent peephole optimizer that would translate a machine language program into register transfers, optimize the resulting program, and combine the transfers back into machine language. They claimed that register transfers can be a useful UNCOL. Early attempts at UNCOLs, they claimed, were essentially union languages that tried to include all the features that any machine might have. In contrast, register transfers contain only the intersection of features that any machine might have. They claimed that their combining algorithm would reconstruct more complicated instructions. Our use of register transfers as an intermediate language has been very successful. Our original system was quite similar to PO, which Davidson wrote. The main difference was that we generated register transfers directly. Also, we attempted more global optimizations and better register assignment, though this was not significantly better than what Davidson and Fraser did. Our version of the combining algorithm was much faster than theirs because we could use a lot of tricks in Smalltalk. However, we gradually changed our code generator until it is now quite different from PO. In particular, our intermediate data structure is similar to Static Single Assignment (SSA), invented by folks at IBM. We think that we now have a very elegant and reasonably efficient low-level representation for programs that is easy to retarget to different machines. The code generator has only been targeted to two different machines, so we don't yet have proof that it is really portable. One of the machines is the 68020 and the other is a local horizontally microcoded machine. However, our model stretches to fit both those machines, which is a pretty good sign. I don't think we will have any trouble with RISC machines. In summary, I think that a very simple-minded register transfer language is a good candidate for an UNCOL, using a combining algorithm similar to that of Davidson and Fraser for converting UNCOL programs into machine language for each kind of machine. Ralph Johnson [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] certain registers in [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