RE: PATCH: Support more than 2 relaxation passes

[James E Wilson <wilson at specifix dot com>]

On Wed, 2006-03-08 at 12:22, Dave Korn wrote:
>   I can't see any line of reasoning that suggests that the iterative process
> of relaxation would necessarily converge after no more than two passes, so why
> not?  Am I missing something that makes for a proof?

There is the general principle here that we should never change the code
without a good reason, and HJ provided none.  I am not even going to
bother to look at a patch that contains no justification.

Also, there is the issue of why we need this change now, when apparently
it has never been a problem before.

Linker relaxation works differently than gcc/gas relaxation.  In gas,
relaxing means converting a long instruction into a shorter one, which
may in turn allow additional relaxing opportunities.  In gas, yes,
convergence may take multiple passes.  Same for gcc.

However, in the linker, we normally don't change code size when
relaxing.  That would require redoing many relocations.  It would also
mean that gas can't resolve many relocations, since the linker would
need to redo them.  This would be a mess.  There is also the additional
complication on IA-64 that we have 3-instruction bundles, which means we
would have to reschedule and rebundle the code if we deleted an
instruction.  This would be a very complicated mess.

So lets look at what the IA-64 linker can do.  We can convert br
instructions into brl if they are out of range.  This involves adding a
trampoline outside the current code section.  There is no change to the
size of the current code section; we just have a new code section
appended at the end.  Hence there is no need for multiple passes.

So maybe you are wondering why we need two.  This is because we can also
do something else.  We can convert some two-instruction gp-relative load
sequences into single instruction sequences.  This requires knowing the
offset between the code and the got, which is affected by the above br
to brl conversion, so it must be done in a second separate pass.  There
is no code size or got size change here, so everything can be done in a
single pass.  The conversion involves changing a load/move into a
load/nop, since we can't actually delete any instructions at this point.

So there is no reason for more than 2 relaxation passes for the IA-64
linker, and all other linkers only need 1 relaxation pass.
-- 
Jim Wilson, GNU Tools Support, http://www.specifix.com