RFC: Patch for switch elimination (PR 54742)

[Richard Biener]

On Tue, Aug 12, 2014 at 10:40 PM, Jeff Law <law@redhat.com> wrote:
> On 08/12/14 14:23, Richard Biener wrote:
>>
>> On August 12, 2014 8:31:16 PM CEST, Jeff Law <law@redhat.com> wrote:
>>>
>>> On 08/12/14 11:46, Steve Ellcey wrote:
>>>>
>>>> After talking to Jeff Law at the GCC Cauldron I have updated my
>>>
>>> switch
>>>>
>>>> shortcut plugin pass to try and address this optimization in the
>>>
>>> hopes of
>>>>
>>>> getting it added to GCC as a static pass.  I fixed the code to build
>>>
>>> with
>>>>
>>>> the various C++ changes that have been happening in GCC but the
>>>
>>> current
>>>>
>>>> version I have included in this email is not working yet.  When I run
>>>
>>> it
>>>>
>>>> on coremark I get errors like:
>>>>
>>>> core_state.c: In function 'core_bench_state':
>>>> core_state.c:43:8: error: size of loop 16 should be 13, not 5
>>>>    ee_u16 core_bench_state(ee_u32 blksize, ee_u8 *memblock,
>>>>           ^
>>>> core_state.c:43:8: error: bb 15 does not belong to loop 16
>>>> core_state.c:43:8: error: bb 113 does not belong to loop 16
>>>> core_state.c:43:8: error: bb 118 does not belong to loop 16
>>>> core_state.c:43:8: error: bb 117 does not belong to loop 16
>>>> (etc)
>>>>
>>>> Apparently there have been some changes to the loop information that
>>>> is built since GCC 4.9.  I had hoped that adding a call to
>>>
>>> fix_loop_structure
>>>>
>>>> after recalculating the dominance information would fix this but it
>>>
>>> didn't.
>>>>
>>>>
>>>> Does anyone have any ideas on how to fix up the loop information that
>>>
>>> my
>>>>
>>>> optimization has messed as it duplicates blocks?  I tried adding a
>>>
>>> call
>>>>
>>>> 'loop_optimizer_init (LOOPS_NORMAL)' before the fix_loop_structure
>>>
>>> but that
>>>>
>>>> did not seem to have any affect.
>>>
>>> Try setting the header & latch fields for the loop structure to NULL,
>>> then call loops_set_state (LOOPS_NEED_FIXUP).
>>
>>
>> But that is _not_ the appropriate way of keeping loops preserved!
>
> I think that's done when we've scrogged the loop beyond repair and want the
> structures rebuilt.  IIRC, that's what you recommended we do.

I don't see that this pass should "scrog" a loop beyond repair.  Btw,
the "proper" way of just fixing loops up (assuming that all loop
headers are still at their appropriate place) is to _just_ do
loops_set_state (LOOPS_NEED_FIXUP).

The next pass doing a loop_optimizer_init () then will fixup loops.

So the case you mention is when you totally screw the loop by
creating new entry edges that not go to its header for example.
But still this is in theory very bad as you cause important annotations
to be lost.  If the loop is truly gone, ok, but if it just re-materializes
then you've done a bad job here.  Consider the case where a
loop becomes a loop nest - you'd want to preserve the loop header
as the header of the outer loop (which you'd have to identify its
header in some way - dominator checks to the rescue!) and let
fixup discover the new inner loop.

Yes, we may have little utility for dealing with the more complex
cases and I've been hesitant to enforce not dropping loops on the
floor an ICE (well, mainly because we can't even bootstrap with
such check ...), but in the end we should arrive there.

Richard.

> jeff