Re: Span-Dependent Instruction Bibliography (Preston Briggs)
Thu, 3 Jan 91 06:09:15 GMT

          From comp.compilers

Related articles
Span-Dependent Instruction Bibliography (John R. Levine) (1991-01-02)
Re: Span-Dependent Instruction Bibliography (1991-01-03)
Re: Span-Dependent Instruction Bibliography (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 Briggs)
Keywords: assembler, optimize, bibliography
Organization: Rice University, Houston
References: <>
Date: Thu, 3 Jan 91 06:09:15 GMT

John R. Levine <> 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.