Re: Span-Dependent Instructions

dmr@research.att.com (Dennis Ritchie)
Wed, 9 Jan 91 23:54:25 EST

          From comp.compilers
Related articles
Re: Span-Dependent Instructions preston@libya.rice.edu (1991-01-03)
Re: Span-Dependent Instructions dmr@research.att.com (1991-01-09)
| List of all articles for this month |
Newsgroups: comp.compilers
From: dmr@research.att.com (Dennis Ritchie)
Keywords: assembler, optimize
Organization: Compilers Central
References: <1991Jan3.231845.21646@rice.edu> <9101022304.AA22609@iecc.cambridge.ma.us> <1991Jan3.060915.3641@rice.edu>
Date: Wed, 9 Jan 91 23:54:25 EST

The SDI discussion in comp.compilers seems to have died down, but
there remains a nugget or two. Leverett & Szymanski's PDP-11
assembler was faster than mine, because the SDI analysis was done
internally at the end of the first pass (or beginning of the second).
Even with the optimal analysis he won, because I had three passes
over the source (evaluate labels pessimistically, decide finally
which SDIs can certainly be shortened, generate code).


The NP-completeness result applies only to situations no sane
compiler (or user) would write; you need arithmetic expressions on
labels. If all references are to labels themselves, there's no
problem.


The L&S data structure was actually pretty clever too; they used a
dependency graph and searched it the right order. But presumably
Mike F. read their paper, and if he claims better behavior I would
believe it.


Dennis
--

Post a followup to this message

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