* [PATCH] shrink-wrapping: Fix up prologue block discovery [PR103860]
@ 2021-12-30 9:43 Jakub Jelinek
2021-12-30 10:08 ` Segher Boessenkool
0 siblings, 1 reply; 6+ messages in thread
From: Jakub Jelinek @ 2021-12-30 9:43 UTC (permalink / raw)
To: Segher Boessenkool, Richard Biener, Jeff Law; +Cc: gcc-patches
Hi!
The following testcase is miscompiled, because a prologue which
contains subq $8, %rsp instruction is emitted at the start of
a basic block which contains conditional jump that depends on
flags register set in an earlier basic block, the prologue instruction
then clobbers those flags.
Normally this case is checked by can_get_prologue predicate, but this
is done only at the start of the loop. If we update pro later in the
loop (because some bb shouldn't be duplicated) and then don't push
anything further into vec and the vec is already empty (this can happen
when the new pro is already in bb_with bitmask and either has no successors
(that is the case in the testcase where that bb ends with a trap) or
all the successors are already in bb_with, then the loop doesn't iterate
further and can_get_prologue will not be checked.
The following simple patch makes sure we call can_get_prologue even after
the last former iteration when vec is already empty and only break from
the loop afterwards (and only if the updating of pro done because of
!can_get_prologue didn't push anything into vec again).
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
2021-12-30 Jakub Jelinek <jakub@redhat.com>
PR rtl-optimization/103860
* shrink-wrap.c (try_shrink_wrapping): Make sure can_get_prologue is
called on pro even if nothing further is pushed into vec.
* gcc.dg/pr103860.c: New test.
--- gcc/shrink-wrap.c.jj 2021-06-07 09:24:57.731689612 +0200
+++ gcc/shrink-wrap.c 2021-12-29 19:16:28.114148496 +0100
@@ -781,7 +781,7 @@ try_shrink_wrapping (edge *entry_edge, r
unsigned max_grow_size = get_uncond_jump_length ();
max_grow_size *= param_max_grow_copy_bb_insns;
- while (!vec.is_empty () && pro != entry)
+ while (pro != entry)
{
while (pro != entry && !can_get_prologue (pro, prologue_clobbered))
{
@@ -791,6 +791,9 @@ try_shrink_wrapping (edge *entry_edge, r
vec.quick_push (pro);
}
+ if (vec.is_empty ())
+ break;
+
basic_block bb = vec.pop ();
if (!can_dup_for_shrink_wrapping (bb, pro, max_grow_size))
while (!dominated_by_p (CDI_DOMINATORS, bb, pro))
--- gcc/testsuite/gcc.dg/pr103860.c.jj 2021-12-29 19:19:23.047696170 +0100
+++ gcc/testsuite/gcc.dg/pr103860.c 2021-12-29 19:19:08.360902059 +0100
@@ -0,0 +1,31 @@
+/* PR rtl-optimization/103860 */
+/* { dg-do run } */
+/* { dg-options "-O3" } */
+/* { dg-additional-options "-fPIC" { target fpic } } */
+
+static int d, *e;
+int f;
+
+__attribute__((noinline)) signed char
+foo (signed char b, signed char c)
+{
+ return b + c;
+}
+
+int
+main ()
+{
+ signed char l;
+ for (l = -1; l; l = foo (l, 1))
+ {
+ while (d < 0)
+ ;
+ if (d > 0)
+ {
+ f = 0;
+ *e = 0;
+ }
+ }
+ d = 0;
+ return 0;
+}
Jakub
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH] shrink-wrapping: Fix up prologue block discovery [PR103860]
2021-12-30 9:43 [PATCH] shrink-wrapping: Fix up prologue block discovery [PR103860] Jakub Jelinek
@ 2021-12-30 10:08 ` Segher Boessenkool
2021-12-30 12:52 ` Jeff Law
2022-01-03 11:00 ` [PATCH] shrink-wrapping: Don't call can_get_prologue unnecessarily [PR103860] Jakub Jelinek
0 siblings, 2 replies; 6+ messages in thread
From: Segher Boessenkool @ 2021-12-30 10:08 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Richard Biener, Jeff Law, gcc-patches
Hi!
On Thu, Dec 30, 2021 at 10:43:32AM +0100, Jakub Jelinek wrote:
> The following testcase is miscompiled, because a prologue which
> contains subq $8, %rsp instruction is emitted at the start of
> a basic block which contains conditional jump that depends on
> flags register set in an earlier basic block, the prologue instruction
> then clobbers those flags.
> Normally this case is checked by can_get_prologue predicate, but this
> is done only at the start of the loop. If we update pro later in the
> loop (because some bb shouldn't be duplicated) and then don't push
> anything further into vec and the vec is already empty (this can happen
> when the new pro is already in bb_with bitmask and either has no successors
> (that is the case in the testcase where that bb ends with a trap) or
> all the successors are already in bb_with, then the loop doesn't iterate
> further and can_get_prologue will not be checked.
>
> The following simple patch makes sure we call can_get_prologue even after
> the last former iteration when vec is already empty and only break from
> the loop afterwards (and only if the updating of pro done because of
> !can_get_prologue didn't push anything into vec again).
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
That looks good, and very simple, thanks!
git blame says I wrote 69.9% of shrink-wrap.c, but I am not maintainer
of it, so I cannot approve your patch -- but it is fine afaics.
Segher
> 2021-12-30 Jakub Jelinek <jakub@redhat.com>
>
> PR rtl-optimization/103860
> * shrink-wrap.c (try_shrink_wrapping): Make sure can_get_prologue is
> called on pro even if nothing further is pushed into vec.
>
> * gcc.dg/pr103860.c: New test.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] shrink-wrapping: Fix up prologue block discovery [PR103860]
2021-12-30 10:08 ` Segher Boessenkool
@ 2021-12-30 12:52 ` Jeff Law
2022-01-03 11:00 ` [PATCH] shrink-wrapping: Don't call can_get_prologue unnecessarily [PR103860] Jakub Jelinek
1 sibling, 0 replies; 6+ messages in thread
From: Jeff Law @ 2021-12-30 12:52 UTC (permalink / raw)
To: Segher Boessenkool, Jakub Jelinek; +Cc: Richard Biener, gcc-patches
On 12/30/2021 3:08 AM, Segher Boessenkool wrote:
> Hi!
>
> On Thu, Dec 30, 2021 at 10:43:32AM +0100, Jakub Jelinek wrote:
>> The following testcase is miscompiled, because a prologue which
>> contains subq $8, %rsp instruction is emitted at the start of
>> a basic block which contains conditional jump that depends on
>> flags register set in an earlier basic block, the prologue instruction
>> then clobbers those flags.
>> Normally this case is checked by can_get_prologue predicate, but this
>> is done only at the start of the loop. If we update pro later in the
>> loop (because some bb shouldn't be duplicated) and then don't push
>> anything further into vec and the vec is already empty (this can happen
>> when the new pro is already in bb_with bitmask and either has no successors
>> (that is the case in the testcase where that bb ends with a trap) or
>> all the successors are already in bb_with, then the loop doesn't iterate
>> further and can_get_prologue will not be checked.
>>
>> The following simple patch makes sure we call can_get_prologue even after
>> the last former iteration when vec is already empty and only break from
>> the loop afterwards (and only if the updating of pro done because of
>> !can_get_prologue didn't push anything into vec again).
>>
>> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
> That looks good, and very simple, thanks!
>
> git blame says I wrote 69.9% of shrink-wrap.c, but I am not maintainer
> of it, so I cannot approve your patch -- but it is fine afaics.
Well, we should probably fix the maintainer status of shrink-wrap.c.
In the mean time, based on Segher's review, this is fine for the trunk.
jeff
^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH] shrink-wrapping: Don't call can_get_prologue unnecessarily [PR103860]
2021-12-30 10:08 ` Segher Boessenkool
2021-12-30 12:52 ` Jeff Law
@ 2022-01-03 11:00 ` Jakub Jelinek
2022-01-03 13:12 ` Segher Boessenkool
1 sibling, 1 reply; 6+ messages in thread
From: Jakub Jelinek @ 2022-01-03 11:00 UTC (permalink / raw)
To: Segher Boessenkool, Jeff Law, Richard Biener; +Cc: gcc-patches
On Thu, Dec 30, 2021 at 04:08:25AM -0600, Segher Boessenkool wrote:
> > The following simple patch makes sure we call can_get_prologue even after
> > the last former iteration when vec is already empty and only break from
> > the loop afterwards (and only if the updating of pro done because of
> > !can_get_prologue didn't push anything into vec again).
During the development of the above patch I've noticed that in many cases
we call can_get_prologue often on the same pro again and again and again,
we can have many basic blocks pushed into vec and if most of those don't
require pro updates, i.e.
basic_block bb = vec.pop ();
if (!can_dup_for_shrink_wrapping (bb, pro, max_grow_size))
while (!dominated_by_p (CDI_DOMINATORS, bb, pro))
isn't true, then pro is can_get_prologue checked for each bb in the vec.
The following simple patch just remembers which bb we've verified already
and verifies again only when pro changes. Most of the patch is just
reindentation.
Ok for trunk if it passes bootstrap/regtest?
2022-01-03 Jakub Jelinek <jakub@redhat.com>
PR rtl-optimization/103860
* shrink-wrap.c (try_shrink_wrapping): Don't call can_get_prologue
uselessly for blocks for which it has been called already.
--- gcc/shrink-wrap.c.jj 2022-01-03 10:40:41.758156451 +0100
+++ gcc/shrink-wrap.c 2022-01-03 11:43:36.200744640 +0100
@@ -781,14 +781,20 @@ try_shrink_wrapping (edge *entry_edge, r
unsigned max_grow_size = get_uncond_jump_length ();
max_grow_size *= param_max_grow_copy_bb_insns;
+ basic_block checked_pro = NULL;
+
while (pro != entry)
{
- while (pro != entry && !can_get_prologue (pro, prologue_clobbered))
+ if (pro != checked_pro)
{
- pro = get_immediate_dominator (CDI_DOMINATORS, pro);
+ while (pro != entry && !can_get_prologue (pro, prologue_clobbered))
+ {
+ pro = get_immediate_dominator (CDI_DOMINATORS, pro);
- if (bitmap_set_bit (bb_with, pro->index))
- vec.quick_push (pro);
+ if (bitmap_set_bit (bb_with, pro->index))
+ vec.quick_push (pro);
+ }
+ checked_pro = pro;
}
if (vec.is_empty ())
Jakub
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH] shrink-wrapping: Don't call can_get_prologue unnecessarily [PR103860]
2022-01-03 11:00 ` [PATCH] shrink-wrapping: Don't call can_get_prologue unnecessarily [PR103860] Jakub Jelinek
@ 2022-01-03 13:12 ` Segher Boessenkool
2022-01-03 13:16 ` Richard Biener
0 siblings, 1 reply; 6+ messages in thread
From: Segher Boessenkool @ 2022-01-03 13:12 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Jeff Law, Richard Biener, gcc-patches
Hi!
On Mon, Jan 03, 2022 at 12:00:10PM +0100, Jakub Jelinek wrote:
> On Thu, Dec 30, 2021 at 04:08:25AM -0600, Segher Boessenkool wrote:
> > > The following simple patch makes sure we call can_get_prologue even after
> > > the last former iteration when vec is already empty and only break from
> > > the loop afterwards (and only if the updating of pro done because of
> > > !can_get_prologue didn't push anything into vec again).
>
> During the development of the above patch I've noticed that in many cases
> we call can_get_prologue often on the same pro again and again and again,
> we can have many basic blocks pushed into vec and if most of those don't
> require pro updates, i.e.
> basic_block bb = vec.pop ();
> if (!can_dup_for_shrink_wrapping (bb, pro, max_grow_size))
> while (!dominated_by_p (CDI_DOMINATORS, bb, pro))
> isn't true, then pro is can_get_prologue checked for each bb in the vec.
>
> The following simple patch just remembers which bb we've verified already
> and verifies again only when pro changes. Most of the patch is just
> reindentation.
I'd like it better if the code structure was changed so you do not need
this workaround. That will probably result in much clearer code.
But it does look correct :-)
This should make things O(n) again here. Thanks for fixing this!
Segher
> PR rtl-optimization/103860
> * shrink-wrap.c (try_shrink_wrapping): Don't call can_get_prologue
> uselessly for blocks for which it has been called already.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] shrink-wrapping: Don't call can_get_prologue unnecessarily [PR103860]
2022-01-03 13:12 ` Segher Boessenkool
@ 2022-01-03 13:16 ` Richard Biener
0 siblings, 0 replies; 6+ messages in thread
From: Richard Biener @ 2022-01-03 13:16 UTC (permalink / raw)
To: Segher Boessenkool; +Cc: Jakub Jelinek, Jeff Law, gcc-patches
On Mon, 3 Jan 2022, Segher Boessenkool wrote:
> Hi!
>
> On Mon, Jan 03, 2022 at 12:00:10PM +0100, Jakub Jelinek wrote:
> > On Thu, Dec 30, 2021 at 04:08:25AM -0600, Segher Boessenkool wrote:
> > > > The following simple patch makes sure we call can_get_prologue even after
> > > > the last former iteration when vec is already empty and only break from
> > > > the loop afterwards (and only if the updating of pro done because of
> > > > !can_get_prologue didn't push anything into vec again).
> >
> > During the development of the above patch I've noticed that in many cases
> > we call can_get_prologue often on the same pro again and again and again,
> > we can have many basic blocks pushed into vec and if most of those don't
> > require pro updates, i.e.
> > basic_block bb = vec.pop ();
> > if (!can_dup_for_shrink_wrapping (bb, pro, max_grow_size))
> > while (!dominated_by_p (CDI_DOMINATORS, bb, pro))
> > isn't true, then pro is can_get_prologue checked for each bb in the vec.
> >
> > The following simple patch just remembers which bb we've verified already
> > and verifies again only when pro changes. Most of the patch is just
> > reindentation.
>
> I'd like it better if the code structure was changed so you do not need
> this workaround. That will probably result in much clearer code.
>
> But it does look correct :-)
>
> This should make things O(n) again here. Thanks for fixing this!
Btw, you can take that as approval.
Richard.
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2022-01-03 13:16 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-12-30 9:43 [PATCH] shrink-wrapping: Fix up prologue block discovery [PR103860] Jakub Jelinek
2021-12-30 10:08 ` Segher Boessenkool
2021-12-30 12:52 ` Jeff Law
2022-01-03 11:00 ` [PATCH] shrink-wrapping: Don't call can_get_prologue unnecessarily [PR103860] Jakub Jelinek
2022-01-03 13:12 ` Segher Boessenkool
2022-01-03 13:16 ` 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).