|Block reording. Edward.Rosten@gmail.com (2007-03-08)|
|Re: Block reordering to minimize length of jump instructions email@example.com (Bill Cox) (2007-03-10)|
|From:||Bill Cox <firstname.lastname@example.org>|
|Date:||10 Mar 2007 21:34:17 -0500|
|Keywords:||analysis, optimize, comment|
|Posted-Date:||10 Mar 2007 21:34:17 EST|
> 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]
Return to the
Search the comp.compilers archives again.