|Span-Dependent Instruction Bibliography email@example.com (John R. Levine) (1991-01-02)|
|Re: Span-Dependent Instruction Bibliography firstname.lastname@example.org (1991-01-03)|
|Re: Span-Dependent Instruction Bibliography email@example.com (Norman Adams) (1991-01-03)|
|Re: Span-Dependent Instruction Bibliography markz@ssc.UUCP (1991-01-04)|
|From:||firstname.lastname@example.org (Preston Briggs)|
|Keywords:||assembler, optimize, bibliography|
|Organization:||Rice University, Houston|
|Date:||Thu, 3 Jan 91 06:09:15 GMT|
John R. Levine <email@example.com> 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.
[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]
Return to the
Search the comp.compilers archives again.