Re: Span-Dependent Instruction Bibliography

preston@libya.rice.edu (Preston Briggs)
Thu, 3 Jan 91 06:09:15 GMT

          From comp.compilers
Related articles
Span-Dependent Instruction Bibliography johnl@iecc.cambridge.ma.us (John R. Levine) (1991-01-02)
Re: Span-Dependent Instruction Bibliography preston@libya.rice.edu (1991-01-03)
Re: Span-Dependent Instruction Bibliography norman@parc.xerox.com (Norman Adams) (1991-01-03)
Re: Span-Dependent Instruction Bibliography markz@ssc.UUCP (1991-01-04)
| List of all articles for this month |
Newsgroups: comp.compilers
From: preston@libya.rice.edu (Preston Briggs)
Keywords: assembler, optimize, bibliography
Organization: Rice University, Houston
References: <9101022304.AA22609@iecc.cambridge.ma.us>
Date: Thu, 3 Jan 91 06:09:15 GMT

John R. Levine <johnl@iecc.cambridge.ma.us> writes:
>Here's a list of what I found on my 40-foot shelf. ...


Another related paper is


Jump minimization in linear-time
Ramanath and Solomon
TOPLAS 6(4), October 1984


It's more compiler-oriented (vs. assembler).
Arranges basic blocks to minimize the number of unconditional
jumps. Fast and optimimal for "structured" programs (reducible flow graphs?).
They also show the problem is NP-Complete for unstructured code
(though their algorithm still does a reasonable job).


Has anyone ever measured the efficacy of any of these algorithms?


An interesting study might examine the effectiveness of 2 or more of the
assembler-oriented improvers versus the above paper on machines like the
VAX or 680x0 and some currently interesting RISC machine. A nice test case
would be the SPEC benchmarks, either the C or Fortran programs.


Preston Briggs
[Szymanski's papers have some effectiveness results. His first paper reports
that in some pile of PDP-11 code, his algorithm shortened considerably more
branches than the one the assembler used. -John]
--

Post a followup to this message

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