[PATCH] Add code-hoisting to GIMPLE

[Jeff Law]

On 07/08/2016 01:30 AM, Richard Biener wrote:
> On Mon, 4 Jul 2016, Steven Bosscher wrote:
>
>> On Mon, Jul 4, 2016 at 1:26 PM, Richard Biener wrote:
>>>
>>> The following patch is Stevens code-hoisting based on PRE forward-ported
>>> and fixed for bootstrap plus the case of hoisting code across loops
>>> which we generally do not want (expressions in the loop exit target block
>>> are antic-in throughout the whole loop unless they are killed and thus
>>> get inserted into the exit block and then PREd before the loop).
>>>
>>> Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
>>>
>>> I'm going to try making the bitmap_set ops in do_hoist_insert a bit
>>> faster - Steven, do you remember any issues with the approach from the
>>> time you worked on it?
>>
>> Hi Richi,
>>
>> It's been almost 8 years since I worked on this, so I really don't
>> recall much about this at all. Sorry :-)
>
> Fair enough ;)  Apart from the loop case I noticed that code-hoisting
> will cause
>
>   if (x1_6 > 6)
>     goto <bb 3>;
>   else
>     goto <bb 4>;
>
>   <bb 3>:
>   i_7 = i_2(D) + 2;
>
>   <bb 4>:
>   # i_1 = PHI <i_2(D)(2), i_7(3)>
>   i_8 = i_1 + 2;
>
> to be re-written to
>
>   _18 = i_2(D) + 2;
>   if (x1_6 > 6)
>     goto <bb 3>;
>   else
>     goto <bb 4>;
>
>   <bb 3>:
>   _19 = _18 + 2;
>
>   <bb 4>:
>   # i_8 = PHI <_18(2), _19(3)>
>
> which is because critical edge splitting splits 2->4 and thus makes
> i_2(D)+2 antic-in in the else block (IIRC it wouldn't be antic-in
> in bb 4 but antic-out in bb 2).  Not sure if it is worth trying to
> devise a "fix" for this, it's not really a pessimization.
>
> But it generally shows that hoisting is quite aggressive.
I don't see it as a pessimization either, though the gratutious code 
motion can make it awful hard to evaluate the real effects (I saw this 
when evaluating Click's GCM/GVN algorithm for GCC.

I thought we had a BZ where we wanted to do this kind of hoisting up 
through PHIs.  Oh, 64700, but it's in the other direction -- sink a 
common expression through a PHI.

Jeff

>
> Richard.
>