Re: [RFA] Handle target with no length attributes sanely in bb-reorder.c

[Richard Biener <richard.guenther@gmail.com>]

On Thu, Dec 1, 2016 at 6:28 PM, Jeff Law <law@redhat.com> wrote:
> On 12/01/2016 05:04 AM, Segher Boessenkool wrote:
>>
>> On Thu, Dec 01, 2016 at 10:19:42AM +0100, Richard Biener wrote:
>>>>>
>>>>> Thinking about this again maybe targets w/o insn-length should simply
>>>>> always use the 'simple' algorithm instead of the STV one?  At least
>>>>> that
>>>>> might be what your change effectively does in some way?
>>>>
>>>>
>>>> From reading the comments I don't think STC will collapse down into the
>>>> simple algorithm if block copying is disabled.  But Segher would know
>>>> for
>>>> sure.
>>>>
>>>> WRT the choice of simple vs STC, I doubt it matters much for the
>>>> processors
>>>> in question.
>>>
>>>
>>> I guess STC doesn't make much sense if we can't say anything about BB
>>> sizes.
>>
>>
>> STC tries to make as large as possible consecutive "traces", mainly to
>> help with instruction cache utilization and hit rate etc.  It cannot do
>> a very good job if it isn't allowed to copy blocks.
>>
>> "simple" tries to (dynamically) have as many fall-throughs as possible,
>> i.e. as few jumps as possible.

I hope it special-cases backedges, that is, not make those fallthru.

>>  It never copies code; if that means it
>> has to jump every second insn, so be it.  It provably is within a factor
>> three of optimal (optimal is NP-hard), under a really weak assumption
>> within a factor two, and it does better than that in practice.
>>
>> STC without block copying makes longer traces which is not a good idea
>> for most architectures, only for those that have a short jump that is
>> much shorter than longer jumps (and thus, cannot cover many jump
>> targets).
>>
>> I do not know how STC behaves when it does not know the insn lengths.
>
> mn103 &  m68k are definitely sensitive to jump distances, the former more so
> than the latter.  Some of the others probably are as well.
>
> I think we've probably discussed this more than is really necessary.  We
> just need to pick an alternative and go with it, I think either alternative
> is reasonable (avoid copying when STC has no length information or fall back
> to simple when there is no length information).

The description of both algorithms doesn't make it an obvious pick.  So lets
leave the decision of the algorithm to the target and make STC beave sane
with no length information (whether that means disallowing any copying or
substituting a "default" length is another question -- but obviously it's the
targets fault to not provide lenght information).

Richard.

>
>
> jeff