🚀 go-pugleaf

Johan Larson writes:

> Currently, single pass compilers are very popular, due to their speed.  This
> speed allows the development cycle to be shortened, sometimes by very
> significant amounts.  However, unless I'm very wrong, the speed of the
> single pass compiler is gained at the expense of code quality.  One 
> immediately obvious solution is a code optimizer, which could be used on a
> compiled program once the critical debuggion is done.  However, such a 
> code optimizer could also be put to another, and potentially more powerful
> use.
It depends on what you mean by a "single pass" compiler. If you mean a
single-pass compiler which yields assembly language, then you are sort of
cheating, because the two passes of the assembler represent the second and
third passes of your "one-pass" compiler.

If you mean a single-pass compiler which goes direct to object (or executable -
did I mention the two linking passes above, too?) then the big big problem with
single pass compilers is that they have to keep everything in memory. If your
program won't fit (and it has to be the WHOLE program, too - you can't break it
up unless you have a separate linker (which means two more passes)) then you
are SOL.

The biggest advantage of a multi-pass compiler is that the available memory at
compilation is almost unrelated to the size of the program being compiled (the
only thing which is related is the symbol table size).

If a single-pass compiler operates in memory, there is no fundamental reason
why it can't generate code just as efficient as a multi-pass compiler.

(By the way, I think you must be a Mac person. I don't know of any single pass
C-compilers for the Amiga, and very little development is done in any other
languages for it.)

> The Mac and Amiga worlds are currently in the process of changing from the
> 68000 processor to the similar, but more powerful 68020.  The 68030 has also
> been rumoured to be lurking somewhere on the horizon.  However, regardless of
> whether a '000 or a '020 is installed, the same code is used.  Thus, if a 
> system is using the more advanced '020, it is using code which was written for
> a more primitive, though similar, processor and thus the code does not take
> proper advantage of the more advanced features of the more modern processors.
> The same agrument applies for the math co-processors, the 68881 and its new
> sibling the 68882, which are rapidly becoming more popular on home computers.
Now, I may be wrong about this, but the big advantage of the 68020 isn't so
much new instructions (there are a few, but they aren't commonly used) but the
fact that it executes the old instructions much faster - because it uses a
32-bit internal data path and the 68000 uses a 16-bit path, so it takes twice
as many internal cycles on the 68000 for a given amount of wide data.

The execution speed of a program using the 68000 set, but run on the 68020,
will not be much worse typically than the same program compiled to use the full
68020 set - but both will beat the pants off of a 68000 running the same clock
rate.

The one big exception to this is that the 68000 cannot work with a math
co-processor and the 68020 (and the 68010 before it) can - so for math stuff if
you use the coprocessor instructions you can get orders of magnitude increases
in speed. There are ways of working around this so that the same code works on
both, but takes advantage of the math chip if it is there:

Way #1: All math operations are handled as calls to a run-time-loaded library
of math routines. On a 68000 or a 68020 without math chip, you load a software
floating point library. On the 68020 with math chip, you load one which calls
the chip. (This is what the Amiga does.)

Way #2: Everyone's code uses the math chip instructions, but on a 68000 or an
uninstalled 68020 they trap as illegal instructions - to a special routine
which emulates them in software and returns!

In the former case you pay a small performance hit on the 68020 with math
chip as compared to the latter.


> The code optimizer, if properly written, could remove the inefficiency of
> using primitive code on an advanced processor, simply by modifying the
> code to take advantage of the features of the more advanced processor.
> Since not everyone has a 68020, it would be left up to the user to decide
> whether or not (s)he wants the code of a program modified in such a way.
> The optimizer could also be written to rewrite the program code so as
> to take advantage of a coprocessor, it one is present.
An optimizer cannot run on compiled binary - the problem is indeterminate. The
reason is simple: The optimizer cannot differentiate between data and code.
(And if it optimizes the data, the program dies.) Worse than that, even if it
knew that it was in code, it cannot unambiguously identify the beginnings of
instructions.

In any case, in anything greater than a peephole optimizer, even the raw
assembly language isn't enough - the optimizer must be given information about
the original program.

An example is "common subtree" optimization in a complex
expression: To identify this is difficult and fraught with errors in the
assembly language. The right place to do it is in the parser when building the
expression tree.

Another example (probably closer to your heart) would be "Oh, I can use a 68881
instruction here". Unless your math library emulates the 68881 on a
one-call-per-one-instruction basis, you may not be able to figure out that a
68881 instruction will help - without reference to the original source.
(And if you are operating on binary, you may not know that this particular
subroutine call was a call to the math library, anyway!)

Peep-hole optimizers have their place, but the kind of optimization you are
asking for can't be done that way.

...and even if it could, I gather that you are thinking of this as a COMMERCIAL
thing - and what manufacturer will distribute the assembly language of their
program, complete with labels? (I gather that your idea was that someone buys a
commercial program intended for a 68000, passes it through the magic optimizer,
and all-of-a-sudden it is optimized for the 68020 with math chip.)


> Is there some fundamental problem with what is described above?  Is anyone
> working on such an optimizer?
> I welcome your comments and criticisms.
> 
> 	Johan Larson

It seems to me you've missed an easy answer to your problem: Use your
inefficient fast single-pass compiler while you develop, and when you are done
use the efficient slow multi-pass compiler for the production version.

Why do you need an optimizer at all? Use the one that's built into the
multi-pass compiler.
-- 
Steven C. Den Beste,   Bolt Beranek & Newman, Cambridge MA
denbeste@bbn.com(ARPA/CSNET/UUCP)    harvard!bbn.com!denbeste(UUCP)