* fwprop fix for PR79405
@ 2017-02-16 19:44 Bernd Schmidt
2017-02-17 9:11 ` Richard Biener
2017-02-22 17:54 ` Jeff Law
0 siblings, 2 replies; 9+ messages in thread
From: Bernd Schmidt @ 2017-02-16 19:44 UTC (permalink / raw)
To: GCC Patches
[-- Attachment #1: Type: text/plain, Size: 604 bytes --]
We have two registers being assigned to each other:
(set (reg 213) (reg 209))
(set (reg 209) (reg 213))
These being the only definitions, we are happy to forward propagate reg
209 for reg 213 into a third insn, making a new use for reg 209. We are
then happy to forward propagate reg 213 for it in the same insn...
ending up in an infinite loop.
I don't really see an elegant way to prevent this, so the following just
tries to detect the situation (and more general ones) by brute force.
Bootstrapped and tested on x86_64-linux, verified that the test passes
with a ppc cross, ok?
Bernd
[-- Attachment #2: 79405.diff --]
[-- Type: text/x-patch, Size: 2785 bytes --]
PR rtl-optimization/79405
* fwprop.c (forward_propagate_into): Detect potentially cyclic
replacements and bail out for them.
PR rtl-optimization/79405
* gcc.dg/torture/pr79405.c: New test.
Index: gcc/fwprop.c
===================================================================
--- gcc/fwprop.c (revision 244815)
+++ gcc/fwprop.c (working copy)
@@ -1374,13 +1374,42 @@ forward_propagate_into (df_ref use)
/* Only consider uses that have a single definition. */
def = get_def_for_use (use);
- if (!def)
+ if (!def || DF_REF_INSN_INFO (def) == NULL)
return false;
if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
return false;
if (DF_REF_IS_ARTIFICIAL (def))
return false;
+ df_ref tmp_def = def;
+ /* There is a problematic case where a chain of assignments
+ rA = rB; rB = rC; .... ; rM = rN; rN = rA.
+ can cause us to replace these registers in an infinite cycle.
+ Walk backwards until we can guarantee that this situation is
+ not present. */
+ for (;;)
+ {
+ rtx_insn *insn = DF_REF_INSN (tmp_def);
+ rtx set = single_set (insn);
+ if (set == NULL_RTX)
+ break;
+ rtx src = SET_SRC (set);
+ rtx dst = SET_DEST (set);
+ if (GET_CODE (src) != REG || GET_CODE (dst) != REG)
+ break;
+ if (rtx_equal_p (src, DF_REF_REG (use)))
+ return false;
+ df_ref tmp_use = df_single_use (DF_REF_INSN_INFO (tmp_def));
+ if (!tmp_use)
+ break;
+ tmp_def = get_def_for_use (tmp_use);
+ if (!tmp_def || DF_REF_INSN_INFO (tmp_def) == NULL)
+ break;
+ if (DF_REF_FLAGS (tmp_def) & DF_REF_READ_WRITE)
+ break;
+ if (DF_REF_IS_ARTIFICIAL (tmp_def))
+ break;
+ }
/* Do not propagate loop invariant definitions inside the loop. */
if (DF_REF_BB (def)->loop_father != DF_REF_BB (use)->loop_father)
return false;
Index: gcc/testsuite/gcc.dg/torture/pr79405.c
===================================================================
--- gcc/testsuite/gcc.dg/torture/pr79405.c (nonexistent)
+++ gcc/testsuite/gcc.dg/torture/pr79405.c (working copy)
@@ -0,0 +1,42 @@
+/* { dg-do compile } */
+char cz;
+long long int xx, u2;
+
+void
+qv (int js, int wl)
+{
+ if (js != 0)
+ {
+ short int sc;
+ int *at = (int *)≻
+ long long int gx = 0;
+
+ for (;;)
+ {
+ *at = 0;
+ js /= sc;
+
+ for (wl = 0; wl < 2; ++wl)
+ {
+ xx = gx;
+ u2 %= xx > 0;
+ cz /= u2;
+
+ fa:
+ if (cz != u2)
+ {
+ gx |= js;
+ cz = gx / js;
+ }
+ }
+ }
+
+ yq:
+ wl /= 0x80000000;
+ u2 = wl;
+ u2 |= (wl != 0) | (wl != 0 && gx != 0);
+ js = u2;
+ goto fa;
+ }
+ goto yq;
+}
^ permalink raw reply [flat|nested] 9+ messages in thread* Re: fwprop fix for PR79405
2017-02-16 19:44 fwprop fix for PR79405 Bernd Schmidt
@ 2017-02-17 9:11 ` Richard Biener
2017-02-17 9:21 ` Richard Biener
2017-02-22 17:54 ` Jeff Law
1 sibling, 1 reply; 9+ messages in thread
From: Richard Biener @ 2017-02-17 9:11 UTC (permalink / raw)
To: Bernd Schmidt; +Cc: GCC Patches
On Thu, Feb 16, 2017 at 8:41 PM, Bernd Schmidt <bschmidt@redhat.com> wrote:
> We have two registers being assigned to each other:
>
> (set (reg 213) (reg 209))
> (set (reg 209) (reg 213))
>
> These being the only definitions, we are happy to forward propagate reg 209
> for reg 213 into a third insn, making a new use for reg 209. We are then
> happy to forward propagate reg 213 for it in the same insn... ending up in
> an infinite loop.
>
> I don't really see an elegant way to prevent this, so the following just
> tries to detect the situation (and more general ones) by brute force.
> Bootstrapped and tested on x86_64-linux, verified that the test passes with
> a ppc cross, ok?
But isn't the issue that we are walking "all uses" (in random order) rather than
only processing each stmt once? That is,
/* Go through all the uses. df_uses_create will create new ones at the
end, and we'll go through them as well.
Do not forward propagate addresses into loops until after unrolling.
CSE did so because it was able to fix its own mess, but we are not. */
for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
{
df_ref use = DF_USES_GET (i);
if (use)
if (DF_REF_TYPE (use) == DF_REF_REG_USE
|| DF_REF_BB (use)->loop_father == NULL
/* The outer most loop is not really a loop. */
|| loop_outer (DF_REF_BB (use)->loop_father) == NULL)
forward_propagate_into (use);
}
if that were simply walking all instructions, doing forward_propagat_into on
each use on an instruction we'd avoid the cycle (because we stop propagating).
Because when propagating DF_USES_TABLE changes.
Richard.
>
>
> Bernd
>
^ permalink raw reply [flat|nested] 9+ messages in thread* Re: fwprop fix for PR79405
2017-02-17 9:11 ` Richard Biener
@ 2017-02-17 9:21 ` Richard Biener
2017-02-20 14:02 ` Bernd Schmidt
0 siblings, 1 reply; 9+ messages in thread
From: Richard Biener @ 2017-02-17 9:21 UTC (permalink / raw)
To: Bernd Schmidt; +Cc: GCC Patches
On Fri, Feb 17, 2017 at 10:07 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Thu, Feb 16, 2017 at 8:41 PM, Bernd Schmidt <bschmidt@redhat.com> wrote:
>> We have two registers being assigned to each other:
>>
>> (set (reg 213) (reg 209))
>> (set (reg 209) (reg 213))
>>
>> These being the only definitions, we are happy to forward propagate reg 209
>> for reg 213 into a third insn, making a new use for reg 209. We are then
>> happy to forward propagate reg 213 for it in the same insn... ending up in
>> an infinite loop.
>>
>> I don't really see an elegant way to prevent this, so the following just
>> tries to detect the situation (and more general ones) by brute force.
>> Bootstrapped and tested on x86_64-linux, verified that the test passes with
>> a ppc cross, ok?
>
> But isn't the issue that we are walking "all uses" (in random order) rather than
> only processing each stmt once? That is,
>
> /* Go through all the uses. df_uses_create will create new ones at the
> end, and we'll go through them as well.
>
> Do not forward propagate addresses into loops until after unrolling.
> CSE did so because it was able to fix its own mess, but we are not. */
>
> for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
> {
> df_ref use = DF_USES_GET (i);
> if (use)
> if (DF_REF_TYPE (use) == DF_REF_REG_USE
> || DF_REF_BB (use)->loop_father == NULL
> /* The outer most loop is not really a loop. */
> || loop_outer (DF_REF_BB (use)->loop_father) == NULL)
> forward_propagate_into (use);
> }
>
> if that were simply walking all instructions, doing forward_propagat_into on
> each use on an instruction we'd avoid the cycle (because we stop propagating).
>
> Because when propagating DF_USES_TABLE changes.
Which either means we might even miss visiting some uses or a fix as simple as
Index: gcc/fwprop.c
===================================================================
--- gcc/fwprop.c (revision 245501)
+++ gcc/fwprop.c (working copy)
@@ -1478,7 +1478,8 @@ fwprop (void)
Do not forward propagate addresses into loops until after unrolling.
CSE did so because it was able to fix its own mess, but we are not. */
- for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
+ unsigned sz = DF_USES_TABLE_SIZE ();
+ for (i = 0; i < sz; i++)
{
df_ref use = DF_USES_GET (i);
if (use)
might work? (not knowing too much about this detail of the DF data
structures - can
the table shrink?)
Richard.
> Richard.
>
>
>>
>>
>> Bernd
>>
^ permalink raw reply [flat|nested] 9+ messages in thread* Re: fwprop fix for PR79405
2017-02-17 9:21 ` Richard Biener
@ 2017-02-20 14:02 ` Bernd Schmidt
2017-02-20 17:15 ` Richard Biener
0 siblings, 1 reply; 9+ messages in thread
From: Bernd Schmidt @ 2017-02-20 14:02 UTC (permalink / raw)
To: Richard Biener; +Cc: GCC Patches
On 02/17/2017 10:11 AM, Richard Biener wrote:
> Index: gcc/fwprop.c
> ===================================================================
> --- gcc/fwprop.c (revision 245501)
> +++ gcc/fwprop.c (working copy)
> @@ -1478,7 +1478,8 @@ fwprop (void)
> Do not forward propagate addresses into loops until after unrolling.
> CSE did so because it was able to fix its own mess, but we are not. */
>
> - for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
> + unsigned sz = DF_USES_TABLE_SIZE ();
> + for (i = 0; i < sz; i++)
> {
> df_ref use = DF_USES_GET (i);
> if (use)
>
> might work? (not knowing too much about this detail of the DF data
> structures - can the table shrink?)
This would probably work to fix the bug, but this behaviour is
explicitly documented as intentional (in the comment the second half of
which you've quoted). I assume it enables additional substitutions.
Bernd
^ permalink raw reply [flat|nested] 9+ messages in thread* Re: fwprop fix for PR79405
2017-02-20 14:02 ` Bernd Schmidt
@ 2017-02-20 17:15 ` Richard Biener
0 siblings, 0 replies; 9+ messages in thread
From: Richard Biener @ 2017-02-20 17:15 UTC (permalink / raw)
To: Bernd Schmidt; +Cc: GCC Patches
On February 20, 2017 2:58:54 PM GMT+01:00, Bernd Schmidt <bschmidt@redhat.com> wrote:
>On 02/17/2017 10:11 AM, Richard Biener wrote:
>> Index: gcc/fwprop.c
>> ===================================================================
>> --- gcc/fwprop.c (revision 245501)
>> +++ gcc/fwprop.c (working copy)
>> @@ -1478,7 +1478,8 @@ fwprop (void)
>> Do not forward propagate addresses into loops until after
>unrolling.
>> CSE did so because it was able to fix its own mess, but we are
>not. */
>>
>> - for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
>> + unsigned sz = DF_USES_TABLE_SIZE ();
>> + for (i = 0; i < sz; i++)
>> {
>> df_ref use = DF_USES_GET (i);
>> if (use)
>>
>> might work? (not knowing too much about this detail of the DF data
>> structures - can the table shrink?)
>
>This would probably work to fix the bug, but this behaviour is
>explicitly documented as intentional (in the comment the second half of
>
>which you've quoted). I assume it enables additional substitutions.
Hmm, this means the walking-stmts solution sounds more correct and also gets these second-level opportunities.
Richard.
>
>Bernd
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: fwprop fix for PR79405
2017-02-16 19:44 fwprop fix for PR79405 Bernd Schmidt
2017-02-17 9:11 ` Richard Biener
@ 2017-02-22 17:54 ` Jeff Law
2017-02-23 9:02 ` Richard Biener
1 sibling, 1 reply; 9+ messages in thread
From: Jeff Law @ 2017-02-22 17:54 UTC (permalink / raw)
To: Bernd Schmidt, GCC Patches
On 02/16/2017 12:41 PM, Bernd Schmidt wrote:
> We have two registers being assigned to each other:
>
> (set (reg 213) (reg 209))
> (set (reg 209) (reg 213))
>
> These being the only definitions, we are happy to forward propagate reg
> 209 for reg 213 into a third insn, making a new use for reg 209. We are
> then happy to forward propagate reg 213 for it in the same insn...
> ending up in an infinite loop.
>
> I don't really see an elegant way to prevent this, so the following just
> tries to detect the situation (and more general ones) by brute force.
> Bootstrapped and tested on x86_64-linux, verified that the test passes
> with a ppc cross, ok?
>
>
> Bernd
>
>
> 79405.diff
>
>
> PR rtl-optimization/79405
> * fwprop.c (forward_propagate_into): Detect potentially cyclic
> replacements and bail out for them.
>
> PR rtl-optimization/79405
> * gcc.dg/torture/pr79405.c: New test.
OK.
jeff
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: fwprop fix for PR79405
2017-02-22 17:54 ` Jeff Law
@ 2017-02-23 9:02 ` Richard Biener
2017-02-23 22:21 ` Jeff Law
0 siblings, 1 reply; 9+ messages in thread
From: Richard Biener @ 2017-02-23 9:02 UTC (permalink / raw)
To: Jeff Law; +Cc: Bernd Schmidt, GCC Patches
On Wed, Feb 22, 2017 at 6:19 PM, Jeff Law <law@redhat.com> wrote:
> On 02/16/2017 12:41 PM, Bernd Schmidt wrote:
>>
>> We have two registers being assigned to each other:
>>
>> (set (reg 213) (reg 209))
>> (set (reg 209) (reg 213))
>>
>> These being the only definitions, we are happy to forward propagate reg
>> 209 for reg 213 into a third insn, making a new use for reg 209. We are
>> then happy to forward propagate reg 213 for it in the same insn...
>> ending up in an infinite loop.
>>
>> I don't really see an elegant way to prevent this, so the following just
>> tries to detect the situation (and more general ones) by brute force.
>> Bootstrapped and tested on x86_64-linux, verified that the test passes
>> with a ppc cross, ok?
>>
>>
>> Bernd
>>
>>
>> 79405.diff
>>
>>
>> PR rtl-optimization/79405
>> * fwprop.c (forward_propagate_into): Detect potentially cyclic
>> replacements and bail out for them.
>>
>> PR rtl-optimization/79405
>> * gcc.dg/torture/pr79405.c: New test.
>
> OK.
Err - this looks quite costly done for each fwprop. And placing it before
less costly bailouts even...
See my discussion with Bernd anyway.
Richard.
> jeff
>
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: fwprop fix for PR79405
2017-02-23 9:02 ` Richard Biener
@ 2017-02-23 22:21 ` Jeff Law
2017-02-24 10:08 ` Richard Biener
0 siblings, 1 reply; 9+ messages in thread
From: Jeff Law @ 2017-02-23 22:21 UTC (permalink / raw)
To: Richard Biener; +Cc: Bernd Schmidt, GCC Patches
On 02/23/2017 01:57 AM, Richard Biener wrote:
> On Wed, Feb 22, 2017 at 6:19 PM, Jeff Law <law@redhat.com> wrote:
>> On 02/16/2017 12:41 PM, Bernd Schmidt wrote:
>>>
>>> We have two registers being assigned to each other:
>>>
>>> (set (reg 213) (reg 209))
>>> (set (reg 209) (reg 213))
>>>
>>> These being the only definitions, we are happy to forward propagate reg
>>> 209 for reg 213 into a third insn, making a new use for reg 209. We are
>>> then happy to forward propagate reg 213 for it in the same insn...
>>> ending up in an infinite loop.
>>>
>>> I don't really see an elegant way to prevent this, so the following just
>>> tries to detect the situation (and more general ones) by brute force.
>>> Bootstrapped and tested on x86_64-linux, verified that the test passes
>>> with a ppc cross, ok?
>>>
>>>
>>> Bernd
>>>
>>>
>>> 79405.diff
>>>
>>>
>>> PR rtl-optimization/79405
>>> * fwprop.c (forward_propagate_into): Detect potentially cyclic
>>> replacements and bail out for them.
>>>
>>> PR rtl-optimization/79405
>>> * gcc.dg/torture/pr79405.c: New test.
>>
>> OK.
>
> Err - this looks quite costly done for each fwprop. And placing it before
> less costly bailouts even...
>
> See my discussion with Bernd anyway.
I read your last message as being OK with Bernd's approach? Did I
mis-understand?
jeff
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: fwprop fix for PR79405
2017-02-23 22:21 ` Jeff Law
@ 2017-02-24 10:08 ` Richard Biener
0 siblings, 0 replies; 9+ messages in thread
From: Richard Biener @ 2017-02-24 10:08 UTC (permalink / raw)
To: Jeff Law; +Cc: Bernd Schmidt, GCC Patches
On Thu, Feb 23, 2017 at 11:17 PM, Jeff Law <law@redhat.com> wrote:
> On 02/23/2017 01:57 AM, Richard Biener wrote:
>>
>> On Wed, Feb 22, 2017 at 6:19 PM, Jeff Law <law@redhat.com> wrote:
>>>
>>> On 02/16/2017 12:41 PM, Bernd Schmidt wrote:
>>>>
>>>>
>>>> We have two registers being assigned to each other:
>>>>
>>>> (set (reg 213) (reg 209))
>>>> (set (reg 209) (reg 213))
>>>>
>>>> These being the only definitions, we are happy to forward propagate reg
>>>> 209 for reg 213 into a third insn, making a new use for reg 209. We are
>>>> then happy to forward propagate reg 213 for it in the same insn...
>>>> ending up in an infinite loop.
>>>>
>>>> I don't really see an elegant way to prevent this, so the following just
>>>> tries to detect the situation (and more general ones) by brute force.
>>>> Bootstrapped and tested on x86_64-linux, verified that the test passes
>>>> with a ppc cross, ok?
>>>>
>>>>
>>>> Bernd
>>>>
>>>>
>>>> 79405.diff
>>>>
>>>>
>>>> PR rtl-optimization/79405
>>>> * fwprop.c (forward_propagate_into): Detect potentially cyclic
>>>> replacements and bail out for them.
>>>>
>>>> PR rtl-optimization/79405
>>>> * gcc.dg/torture/pr79405.c: New test.
>>>
>>>
>>> OK.
>>
>>
>> Err - this looks quite costly done for each fwprop. And placing it before
>> less costly bailouts even...
>>
>> See my discussion with Bernd anyway.
>
> I read your last message as being OK with Bernd's approach? Did I
> mis-understand?
No, I was refering to the following with "walking stmts"
---
But isn't the issue that we are walking "all uses" (in random order) rather than
only processing each stmt once? That is,
/* Go through all the uses. df_uses_create will create new ones at the
end, and we'll go through them as well.
Do not forward propagate addresses into loops until after unrolling.
CSE did so because it was able to fix its own mess, but we are not. */
for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
{
df_ref use = DF_USES_GET (i);
if (use)
if (DF_REF_TYPE (use) == DF_REF_REG_USE
|| DF_REF_BB (use)->loop_father == NULL
/* The outer most loop is not really a loop. */
|| loop_outer (DF_REF_BB (use)->loop_father) == NULL)
forward_propagate_into (use);
}
if that were simply walking all instructions, doing forward_propagat_into on
each use on an instruction we'd avoid the cycle (because we stop propagating).
Because when propagating DF_USES_TABLE changes.
---
Richard.
> jeff
>
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2017-02-24 10:05 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-02-16 19:44 fwprop fix for PR79405 Bernd Schmidt
2017-02-17 9:11 ` Richard Biener
2017-02-17 9:21 ` Richard Biener
2017-02-20 14:02 ` Bernd Schmidt
2017-02-20 17:15 ` Richard Biener
2017-02-22 17:54 ` Jeff Law
2017-02-23 9:02 ` Richard Biener
2017-02-23 22:21 ` Jeff Law
2017-02-24 10:08 ` Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).