Re: [PATCH 4/5] shrink-wrap: Shrink-wrapping for separate components

[Jeff Law <law@redhat.com>]

On 09/28/2016 03:04 AM, Segher Boessenkool wrote:
>
>>> +static void
>>> +place_prologue_for_one_component (unsigned int which, basic_block head)
>>> +{
>>> +  /* The block we are currently dealing with.  */
>>> +  basic_block bb = head;
>>> +  /* Is this the first time we visit this block, i.e. have we just gone
>>> +     down the tree.  */
>>> +  bool first_visit = true;
>>> +
>>> +  /* Walk the dominator tree, visit one block per iteration of this loop.
>>> +     Each basic block is visited twice: once before visiting any children
>>> +     of the block, and once after visiting all of them (leaf nodes are
>>> +     visited only once).  As an optimization, we do not visit subtrees
>>> +     that can no longer influence the prologue placement.  */
>>> +  for (;;)
>> Is there some reason you wrote this as a loop rather than recursion?
>> IMHO it makes this function (and spread_components) more difficult to
>> reason about than it needs to be.
>
> It would recurse a few thousand frames deep on not terribly big testcases
> (i.e. I've seen it happen).  This uses a lot of stack space on some ABIs,
> and is very slow as well (this is the slowest function here by far).
> Unlimited recursion is bad.
I'm surprised the recursion was that deep.  Such is life.   Thanks for 
clarifying.  I won't object to the iterative version. :-)

>>> +/* Place code for prologues and epilogues for COMPONENTS where we can put
>>> +   that code at the end of basic blocks.  */
>>> +static void
>>> +emit_common_tails_for_components (sbitmap components)
>> [ Snip. ]
>>> +
>>> +      /* Put the code at the end of the BB, but before any final jump.  */
>>> +      if (!bitmap_empty_p (epi))
>> So what if the final jump uses hard registers in one way or another?   I
>> don't immediately see anything that verifies it is safe to transpose the
>> epilogue and the final jump.
>
> Whoops.  Thanks for catching this.
I missed it the first time though the code too.

>
>> Conceptually want the epilogue to occur on the outgoing edge(s).  But
>> you want to actually transpose the epilogue and the control flow insn so
>> that you can insert the epilogue in one place.
>
> The same problem happens with prologues, too.
Yea.  I guess if a had a jump with an embedded side effect (such as movb 
or addb on the PA), then transposing the control flow insn with the 
prologue would be problematical as well.

>
> A cc0 target can not use separate shrink-wrapping *anyway* if any of the
> components would clobber cc0, so that is no problem here.
True, but I'd be more comfortable if we filtered out cc0 targets explicitly.

>
>>   I think you need to handle the former more cleanly.  The latter I'd
>> be comfortable filtering out in try_shrink_wrapping_separate.
>
> I'm thinking to not do the common tail optimisation if BB_END is a
> JUMP_INSN but not simplejump_p (or a return or a sibling call).  Do
> you see any problem with that?
Seems reasonable.


Jeff