Path: utzoo!utgpu!water!watmath!clyde!rutgers!rochester!cornell!uw-beaver!fluke!oophost!bobc
From: bobc@oophost.UUCP (Bob Campbell)
Newsgroups: comp.sys.mac
Subject: Re: Code Optimization
Keywords: Single Pass Compilers Code Optimization
Message-ID: <312@oophost.UUCP>
Date: 27 Jan 88 18:55:32 GMT
References: <6252@cc5.bbn.COM>
Reply-To: bobc@oophost.UUCP (Bob Campbell)
Organization: Carl Nelson & Assocaites Inc.
Lines: 83

While I agree with Steven's conclusions about code optimization I find
that I must take exception to many of his comments about one-pass
compilers.
In article <6252@cc5.bbn.COM> denbeste@bbn.COM (Steven Den Beste) writes:
>...
>cheating, because the two passes of the assembler represent the second and
>third passes of your "one-pass" compiler.

Your analysis of what a "one-pass" compiler is is a little weak.  The
one pass compilers that I am aware of do not generate assembler
output.  Why? because using the assembler removes all of the speed
advantages that were gained by using "one-pass" compiler.  A true one
pass compiler takes one pass using back patching to generate code.  It
does require that the object code reside in memory.  This is the method
used by MacMETH, TML Modula-2, and most likely by the LightSpeed
products (put I can't say for sure about them).  (It should also be
noted that one-pass assemblers exist also.)

>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.

This is not true.  MacMETH is a good example of a one pass compiler
that that directly produces loadable code.  By the nature of Modula-2
it only needs to have at most one module in memory at a time.  Granted
this does not produce the smallest programs possible, but it is very
fast.  MacMETH and I assume LightSpeed C have dynamic loading, that
allows the compiled modules to be used together with out requiring a
linker.  In effect each object file becomes a "code" resource (not
exacly like a Mac "CODE" resource but simular), and the one pass
compiler generates a jump table that the dynamic loader uses when
the program is loaded.

>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).

This is only partly true.  A multi-pass compiler removes many of the
memory limits places on the compiler.  Which is important for a
optimizing compiler where extra tables of information are needed.
However many code optimizations require many passes over the code to
do their work.

>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.

Read the "Dragon Book" especially the chapters on code optimization,
you will find that even if you keep all of the code in memory, you
will need to take several passes over that code, and therefore you
will be a "multi-pass" compiler.

>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...

I listened to someone from Motorola speak on this subject, while all
of the 68000 instructions are faster on a 020, the 020 has a number of
instructions and addressing modes that if used can speed up the code
by a noticable amount.

>An optimizer cannot run on compiled binary - the problem is indeterminate. The
>reason is simple: The optimizer cannot differentiate between data and code.

From this point on things are basicly clear, it is not reasonable as
pointed out to optimize binaries, for the clear reason that it is not
possible to tell what is code and what is data.  In many cases an
optimizer could be constructed (if it knew all of the details on how
the compiler generated it's code)  but it would most likely be much
more efficent to build the optimizer into the compiler.

One idea that has been tossed around is the thought of having the
compilers produce assembly language output and then optimize that.
This would produce a language indepented optimizer (execpt that it
would depend on the assembly language), this would however require a
large effort....  In short the solution provided by Steven seems to be
the most correct, assuming that the multi-pass compiler has a good
optimizer (which many don't):

>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.

Bob Campbell