Re: Shorten_branches and max_skip patch

[Jorn Wolfgang Rennecke <amylaar at cygnus dot com>]

In article <19990720200553.44643@atrey.karlin.mff.cuni.cz> you wrote:

: I've implemented align_fuzz in a way that it combines old guessing algorithm
: with new one that never guess larger padding than max_skip and always
: choose better result. The old one gives better result for many accumulated
: alignemnts while the new one gives better results otherwise.

Many accumulated alignments are the case where it matters to get good
estimates for the range of a branch.  If a branch spans only one or two
alignments, is is not likely to require more than the minimum offset field
anyways.

: Because of this I was also forced to relax uid_align and link all labels
: into one chain, because the max_skip alignments ought to be in all chains.
: Hope this will not cause any performance problems in align fuzz.

It will.  You changed an O(i(n)*n) algorithm into an O(i(n)*n*n) algorithm,
where i(n) is the number of iterations needed for a function with n
instructions, which is roughly logarithmic on average, and linear as a worst
case.

You also have to prove that your combined algorithm won't cause infinite
loops, i.e. that shorten_branches will only do a finite number of
iterations before it stops.

: The patch also add support for max_skips into address calculation code and
: improves choosing of maximal alignment (that don't means just picking one
: with maximal log anymore).

merge_alignments is unnecessarily complex (I won't bother to check if
it is correct).
Just say that every alignment has a max_skip, if none is specified, this
is (1 << align) - 1.
A max_skip larger than (1 << align) - 1 is meaningless, cap it to
(1 << align) - 1.
Then compare the max_skip of the two alignments; if they differ, choose the
alignment with the greater max_skip.  If not, choose the one with the
greater alignment.

: The second change is macro INSN_ALIGNMENT that can be used to define
: alignment per insn basis. This is very usefull for AMD processor familly
: that don't like instruction with two byte opcode to straddle over cache
: line boundary.

I guess this was actually the starting point, and you got worried because
this gives you a large alignment with a small max_skip?
For the purpose of branch shortening with the current algorithm, such
an alignment can be handled like the smallest alignment so that max_skip
is still in range.  I.e. if you have a p2align of 5 with a max_skip of 3,
you can handle it like a p2align of 2.
So the straightforward way to handle this would be to have a value triple
for each label: actual alignment, max_skip, and alignment for the purposes
of shorten_branches.