Wed, 21 Aug 1991 16:57:35 GMT

Related articles |
---|

[6 earlier articles] |

Re: Writing fast compilers... pcg@aber.ac.uk (1991-08-14) |

Re: Writing fast compilers... markh@csd4.csd.uwm.edu (1991-08-16) |

Re: Writing fast compilers... glew@pdx007.intel.com (1991-08-16) |

Re: Writing fast compilers... blenko-tom@CS.YALE.EDU (1991-08-16) |

Re: Writing fast compilers... brnstnd@kramden.acf.nyu.edu (1991-08-18) |

Re: Writing fast compilers... henry@zoo.toronto.edu (1991-08-20) |

Re: Writing fast compilers... andy@DEC-Lite.Stanford.EDU (1991-08-21) |

Newsgroups: | comp.compilers |

From: | andy@DEC-Lite.Stanford.EDU (Andy Freeman) |

Keywords: | performance, design |

Organization: | Computer Science Department, Stanford University |

References: | <PCG.91Aug11154854@aberdb.aber.ac.uk> 91-08-051 91-08-066 |

Date: | Wed, 21 Aug 1991 16:57:35 GMT |

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]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.