Re: Block reordering to minimize length of jump instructions

Bill Cox <>
10 Mar 2007 21:34:17 -0500

          From comp.compilers

Related articles
Block reording. (2007-03-08)
Re: Block reordering to minimize length of jump instructions (Bill Cox) (2007-03-10)
| List of all articles for this month |

From: Bill Cox <>
Newsgroups: comp.compilers
Date: 10 Mar 2007 21:34:17 -0500
Organization: SBC
References: 07-03-034
Keywords: analysis, optimize, comment
Posted-Date: 10 Mar 2007 21:34:17 EST wrote:

> The code is simple to generate if I only use long distance jumps for
> je, since then every block is the same size and every jump is more or
> less equal in cost. However, a jump to an arbitrary point is 6 bytes
> of machine code, where as a jump to a nearby point can be sone in
> only 2 bytes. Naturally, I'd rather use as many short jumps as
> possible, but this requires some strategy to reorder the blocks and
> switching from a 6 byte jump to a 2 byte has the potential to affect
> the distances of a large number of the other jumps. And the shrinking
> of the code size may allow other short jumps to be used, etc...

You can get smaller jumps for the case where the reference is
backwards, and the PC-relative offset fits into the smaller jump
format. Would this help? It's a common optimization.

This method doesn't help with forward references or references outside
the current compilation unit, because you can't compute the necessary
offset in those cases.

Another technique that's implemented in the GNU assemblers and linker is
called "relaxation", in which the offset fields are shrunk where they
can be. The advantage in this case is that forward jumps can also be

For the latter topic, google for "gnu relaxation".

[Branch optimization comes up from time to time, most recently a couple
of weeks ago. The general problem is NP complete, but there are easy
ways to get close to optimal code. -John]

Post a followup to this message

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