RFA: add lock_length attribute to break branch-shortening cycles

Quoting Richard Guenther <richard.guenther@gmail.com>:

> I miss a few things in this description:
> - what is the value of lock_length supposed to be?  From the "lock"
>   prefix it sounds like it is something unchanging, maybe even constant,
>   thus a maximum?
> - the length attribute still needs to be specified when lock_length is?
>   how do they relate?  Is lock_length always smaller / bigger than length?

I hope I have clarified this in the updated documentation:

  Usually, branch shortening is done assuming the worst case (i.e.
longest) lengths, and then iterating (if optimizing) to smaller lengths
till no further changed occur.  This does not work so well for
architectures that have very small minimum offsets and considerable
jumps in instruction lengths.

  If you define the `lock_length' attribute, branch shortening will work
the other way round: it starts out assuming minimum instruction lengths
and iterates from there.  `lock_length' specifies an instruction length
value that is calculated like `length' in every iteration, but if the
value at the last iteration was larger, that larger previous value will
be used instead.  The value computed for the `length' attribute will be
no smaller than that of the `lock_length' attribute, but you may still
specify a larger value, and in that case `length' can decrease in the
next iteration, but not below the value of `lock_length'.  The easiest
way to make sure branch shortening doesn't start looping indefinitely
is to define the `length' attribute to only a minimum instruction
length for varying length instructions and let the `lock_length'
attribute do all the heavy lifting of computing varying lengths.  On
the other hand, for some instruction sets you might get better
shortening outcomes if you use a more complex `length' attribute and
use `lock_length' only to the extent required to prevent indefinite
looping.  Note that `ADJUST_INSN_LENGTH' applies only to the `length'
attribute.

  Because defining `lock_length' makes branch shortening start with
optimistic assumptions, this means we have to see it through to the end
to eliminate all out-of-range branches, thus branch shortening might
take a bit longer at `-O0' than if you didn't define the `lock_length'
attribute.

  Using `lock_length' with varying delay slots and varying length delay
slot insns (all at once) is currently not supported.

> - what happens if you have patterns with lock_length and patterns without?
> - what patterns does lock_length apply to?

These questions don't really make literal sense; instruction attributes
are defined for all instructions.  Of course, you can define the default
value to 0, which means you see no effect of this attribute on a pattern
unless some non-default definition applies.

> In general optimistically attacking this kind of problem should be always
> better - did you try simply switching this for all targets?

No, I haven't.  The boundaries to be set for branch offsets can be different
when starting with optimistic assumptions than when starting with  
pessimistic assumptions.  Moreover, there could be 'interesting'  
interactions
with ADJUST_INSN_LENGTH.  And there is the problem with handling varying
delay slots.  I have modified the final.c patch to reduce the scope of this
issue so that lock_length should hopefully be useful for a wider range of
targets.

Also, ...

>  It shouldn't be
> slower and the only thing you need to guarantee is that during iteration
> you never make insn-lenghts smaller again.

At -O0 it is slower because we can't finish the loop early.

For all these reasons, I think it is better if each target maintainer  
evaluates
if the better branch shortening weighs out the longer -O0 compilation time,
and addresses any issues arising if/when converting.

Bootstrapped on i686-pc-linux-gnu

RFA: add lock_length attribute to break branch-shortening cycles

Commit Message

Patch