|Re: Span-Dependent Instructions firstname.lastname@example.org (1991-01-03)|
|Re: Span-Dependent Instructions email@example.com (1991-01-09)|
|From:||firstname.lastname@example.org (Dennis Ritchie)|
|References:||<1991Jan3.email@example.com> <9101022304.AA22609@iecc.cambridge.ma.us> <1991Jan3.firstname.lastname@example.org>|
|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
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
Return to the
Search the comp.compilers archives again.