Xref: utzoo comp.misc:2101 comp.arch:3931
Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!ll-xn!mit-eddie!bbn!rochester!PT.CS.CMU.EDU!sei!sei.cmu.edu!firth
From: firth@sei.cmu.edu (Robert Firth)
Newsgroups: comp.misc,comp.arch
Subject: Re: Instruction Scheduling
Message-ID: <4553@aw.sei.cmu.edu>
Date: 14 Mar 88 14:28:22 GMT
References: <12513@sgi.SGI.COM> <12560@sgi.SGI.COM> <12678@sgi.SGI.COM> <519@imagine.PAWL.RPI.EDU>
Sender: netnews@sei.cmu.edu
Reply-To: firth@bd.sei.cmu.edu.UUCP (Robert Firth)
Organization: Carnegie-Mellon University, SEI, Pgh, Pa
Lines: 56
Keywords: optimization   pipeline constraints  code re-organization

Thanks to Randell Jesup, Bron Nelson, and others for prompting
this.  The question they discuss is, how might one do some
really good code reorganising for a machine with pipeline
constraints, eg a RISC machine.

First point: when we looked at the MIPS M/500, we found some
less than good code reorganisation.  Details are in our report,
but one place where the reorganiser was VERY conservative was
in rearranging loads and stores.

The reason for this was that the reorganiser input was at
Assembler level, and the algorithms generally made worst-case
assumptions about aliasing.

Second point: To get really good code reorganisation, much the
best place to do it is in the compiler back end.  That is because
you there have some really vital information, for instance

. conceptual type
. conceptual address space

At the assembler level, variables X and Y may seem to be just 16-bit
integers, but if they are of conceptually different types, they can't
alias.  Similarly, X and Y may both be machine addresses, but if they
are reference variables of different types, they can't alias.  Nor
can, say, a by-reference parameter alias a pointer to an allocated
object.

Of course, this assumes you are working with a true high-level language,
such as Modula-2 or Ada.  If the programmer can perform arbitrary casts
and puns, all bets are off.

Third point: a good compiler must carry this information right through
to final code selection and ordering.  In principle, every fragment
that the compiler ever generates must be linked back to the attributed
parse tree, so that no attribute is ever lost or rendered inaccessible.

Hence, when you are debating whether to rearrange

	store r2, xxx(r12)
	load  r1, yyy(r11)

you can look back and see, for instance, that the load is of an INTEGER
and the store of a DURATION, or the load is from module MATHLIB (with
r11 bound as base pointer) and the store into an allocated object of
type DATE (designated by a pointer in r12). Or whatever.

Final point: not many compilers do this.  The reason is that this design
largely abandons the traditional "front end / back end" separation.  If
the back end has to interrogate the APT, then it probably has to know
which language the source program came from.  Unless, of course, you
first design a common APT across your set of languages - and then you
throw away your automatic parser generator (actually, not a bad idea,
given some of the ones I've seen!).

I've rambled on enough.  More later, maybe, since I did take this idea
down to a detailed design and it may yet become a Modula compiler.