Re: Writing fast compilers...

In article 91-08-066 markh@csd4.csd.uwm.edu (Mark William Hopkins) writes:
>In article 91-08-051 davidsen@crdos1.crd.ge.com (bill davidsen) writes:
>> Note that true one pass compilers can not generate best possible code
>>for some machines, notably those which have a short branch instruction,
>>since forward jumps must be coded as long jumps.
>
>Evreything can always be done in one pass. The distinction is wholly
>artificial. Use logical variables or something equivalent, and Unification
>(or something equivalent). It's easy to think up an algorithm, based on
>Unification, doing a "least fixed point" calculation, for optimally
>resolving branches (once you know what Unification is).


It may be "one pass", but it won't be linear time.


The problem isn't resolving the branches, it is determining which "length"
of branch to use.


If we want "best possible" measured dynamically, then finding "best possible"
is equiv to solving the halting problem.


If we want "best possible" measured statically, then we have to deal with the
fact that the decision for one branch may well depend on the decision for
others. It isn't even necessarily true that you "merely" have to find the
right order to make the decisions, as circular dependencies are quite
possible. (That is, there may be a set of branches that can be made short
each if every one of them is made short, but it isn't necessarily true that
finding such sets is easy.) I'd be surprised if it could be done in
polynomial time.


-andy
--
UUCP: {arpa gateways, sun, decwrl, uunet, rutgers}!neon.stanford.edu!andy
ARPA: andy@neon.stanford.edu
[A lot of us would be surprised if it could be done in polynomial time, since
static branch optimization is NP complete. See Szymanski's article in the
April 1978 CACM and Robertson's article in the July 1979 TOPLAS for details.
There was quite a long discussion of branch optimization in January, in which
we discovered that a pretty decent approximation can be done on O(n log n).
-John]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.