Re: [PATCH 1/4][RFC] middle-end/90348 - add explicit birth
Hello,
On Wed, 9 Feb 2022, Richard Biener wrote:
> > That breaks down when a birth is there (because it was otherwise
> > reachable) but not on the taken path:
> >
> > if (nevertrue)
> > goto start;
> > goto forw;
> > start:
> > {
> > int i;
> > printf("not really reachable, but unknowingly so\n");
> > forw:
> > i = 1;
> > }
>
> I think to cause breakage you need a use of 'i' on the side-entry
> path that is not reachable from the path with the birth. I guess sth like
>
>if (nevertrue)
> goto start;
>goto forw;
>start:
>{
> int i = 0;
> printf("not really reachable, but unknowingly so\n");
> goto common;
>forw:
> i = 1;
>common:
> foo ();
>}
>
> if we'd have a variable that's live only on the side-entry path
> then it could share the stack slot with 'i' this way, breaking
> things (now we don't move CLOBBERs so it isn't easy to construct
> such case). The present dataflow would, for the above, indeed
> compute 'i' not live in the forw: block.
Yes, now that we have established (in the subthread with Joseph) that the
value becomes indeterminate at decls we only need to care for not sharing
storage invalidly, so yeah, some changes in the conflict computation still
are needed.
> > Except for switches side-entries are really really seldom, so we might
> > usefully get away with that latter solution. And for switches it might be
> > okay to put the births at the block containing the switch (if it itself
> > doesn't have side entries, and the switch block doesn't have side
> > entries except the case labels).
> >
> > If the birth is moved to outward blocks it might be best if also the
> > dealloc/death clobbers are moved to it, otherwise there might be paths
> > containing a birth but no death.
> >
> > The less precise you get with those births the more non-sharing you'll
> > get, but that's the price.
>
> Yes, sure. I don't see a good way to place births during gimplification
> then.
Well, for each BIND you can compute if there are side entries at all,
then, when lowering a BIND you put the births into the containing
innermost BIND that doesn't have side-entries, instead of into the current
BIND.
> The end clobbers rely on our EH lowering machinery. For the entries we
> might be able to compute GIMPLE BIND transitions during BIND lowering if
> we associate labels with BINDs. There should be a single fallthru into
> the BIND at this point. We could put a flag on the goto destination
> labels whether they are reached from an outer BIND.
>
> goto inner;
> {
>{
> int i;
> {
>int j;
> inner:
>goto middle;
> }
> middle:
>}
> }
>
> Since an entry CLOBBER is also a clobber we have to insert birth
> clobbers for all decls of all the binds inbetwee the goto source
> and the destination. So for the above case on the edge to
> inner: have births for i and j and at the edge to middle we'd
> have none.
Correct, that's basically the most precise scheme, it's what I called
try-finally topside-down ("always-before"? :) ). (You have to care for
computed goto! i.e. BINDs containing address-taken labels, which make
things even uglier) I think the easier way to deal with the above is to
notice that the inner BIND has a side entry and conceptually move the
decls outwards to BINDs that don't have such (or bind-crossing gotos),
i.e. do as if it were:
int i; // moved
int j; // moved
goto inner;
{
{
{
inner:
goto middle;
}
middle:
}
}
> Requires some kind of back-mapping from label to goto sources
> that are possibly problematic. One issue is that GIMPLE
> lowering re-builds the BLOCK tree (for whatever reason...),
> so I'm not sure if we need to do it before that (for correctness).
>
> Does that make sense?
I honestly can't say for 100% :-) It sounds like it makes sense, yes.
Ciao,
Michael.
Re: [PATCH 1/4][RFC] middle-end/90348 - add explicit birth
On Tue, 8 Feb 2022, Michael Matz wrote:
> Hello,
>
> On Tue, 8 Feb 2022, Richard Biener wrote:
>
> > > int state = 2, *p, camefrom1 = 0;
> > > for (;;) switch (state) {
> > > case 1:
> > > case 2: ;
> > > int i;
> > > if (state != 1) { p = i = 0; }
> > > if (state == 1) { (*p)++; return *p; }
> > > state = 1;
> > > continue;
> > > }
> > >
> > > Note how i is initialized during state 2, and needs to be kept
> > > initialized
> > > during state 1, so there must not be a CLOBBER (birth or other) at the
> > > point of the declaration of 'i'. AFAICS in my simple tests a DECL_EXPR
> > > for 'i' is placed with the statement associated with 'case 2' label,
> > > putting a CLOBBER there would be the wrong thing. If the decl had an
> > > initializer it might be harmless, as it would be overwritten at that
> > > place, but even so, in this case there is no initializer. Hmm.
> >
> > You get after gimplification:
> >
> > state = 2;
> > camefrom1 = 0;
> > :
> > switch (state) , case 1: , case 2: >
> > {
> > int i;
> >
> > try
> > {
> > i = {CLOBBER(birth)}; /// ignore, should go away
> > :
> > :
> > i = {CLOBBER(birth)};
>
> I think this clobber here would be the problem, because ...
>
> > which I think is OK? That is, when the abstract machine
> > arrives at 'int i;' then the previous content in 'i' goes
> > away? Or would
> >
> > int foo()
> > {
> >goto ick;
> > use:
> >int i, *p;
> >return *p;
> > ick:
> >i = 1;
> >p =
> >goto use;
> >
> > }
> >
> > require us to return 1?
>
> ... I think this is exactly the logical consequence of lifetime of 'i'
> being the whole block. We need to return 1. (Joseph: correct me on that!
> :) ) That's what I was trying to get at with my switch example as well.
>
> > With the current patch 'i' is clobbered before the return.
> >
> > > Another complication arises from simple forward jumps:
> > >
> > > goto forw;
> > > {
> > > int i;
> > > printf("not reachable\n");
> > > forw:
> > > i = 1;
> > > }
> > >
> > > Despite the jump skiping the unreachable head of the BLOCK, 'i' needs to
> > > be considered birthed at the label. (In a way the placement of births
> > > exactly mirrors the placements of deaths (of course), every path from
> > > outside a BLOCK to inside needs to birth-clobber all variables (in C),
> > > like every path leaving needs to kill them. It's just that we have a
> > > convenient construct for the latter (try-finally), but not for the former)
> >
> > The situation with an unreachable birth is handled conservatively
> > since we consider a variable without a (visible at RTL expansion time)
> > birth to conflict with all other variables.
>
> That breaks down when a birth is there (because it was otherwise
> reachable) but not on the taken path:
>
> if (nevertrue)
> goto start;
> goto forw;
> start:
> {
> int i;
> printf("not really reachable, but unknowingly so\n");
> forw:
> i = 1;
> }
I think to cause breakage you need a use of 'i' on the side-entry
path that is not reachable from the path with the birth. I guess sth like
if (nevertrue)
goto start;
goto forw;
start:
{
int i = 0;
printf("not really reachable, but unknowingly so\n");
goto common;
forw:
i = 1;
common:
foo ();
}
if we'd have a variable that's live only on the side-entry path
then it could share the stack slot with 'i' this way, breaking
things (now we don't move CLOBBERs so it isn't easy to construct
such case). The present dataflow would, for the above, indeed
compute 'i' not live in the forw: block.
> > I don't see a good way to have a birth magically appear at 'forw'
> > without trying to argue that the following stmt is the first mentioning
> > the variable.
>
> That's what my 'Hmm' aluded to :) The only correct and precise way I see
> is to implement something similar like try-finally topside-down. An
> easier but less precise way is to place the births at the (start of)
> innermost block containing the decl _and all jumps into the block_. Even
> less presice, but perhaps even easier is to place the births for decls in
> blocks with side-entries into the function scope (and for blocks without
> side entries at their start).
>
> Except for switches side-entries are really really seldom, so we might
> usefully get away with that latter solution. And for switches it might be
> okay to put the births at the block containing the switch (if it itself
> doesn't have side entries, and the switch block doesn't have side
> entries except the case labels).
>
> If the birth is moved to outward blocks it might be best if also the
> dealloc/death clobbers are moved to it, otherwise there might be paths
> containing a birth but no death.
>
> The less precise you get with those births the more non-sharing you'll
> get, but that's the price.
Re: [PATCH 1/4][RFC] middle-end/90348 - add explicit birth
Hey, On Tue, 8 Feb 2022, Joseph Myers wrote: > On Tue, 8 Feb 2022, Richard Biener via Gcc-patches wrote: > > > which I think is OK? That is, when the abstract machine > > arrives at 'int i;' then the previous content in 'i' goes > > away? Or would > > Yes, that's correct. "If an initialization is specified for the object, > it is performed each time the declaration or compound literal is reached > in the execution of the block; otherwise, the value becomes indeterminate > each time the declaration is reached.". Okay, that makes things easier then. We can put the birth clobbers at their point of declaration, just the storage associated with a decl needs to survive for the whole block. We still need to make sure that side entries skipping declarations correctly "allocate" such storage (by introducing proper conflicts with other objects), but at least values don't need to survive decls. Ciao, Michael.
Re: [PATCH 1/4][RFC] middle-end/90348 - add explicit birth
On Tue, 8 Feb 2022, Richard Biener via Gcc-patches wrote: > which I think is OK? That is, when the abstract machine > arrives at 'int i;' then the previous content in 'i' goes > away? Or would Yes, that's correct. "If an initialization is specified for the object, it is performed each time the declaration or compound literal is reached in the execution of the block; otherwise, the value becomes indeterminate each time the declaration is reached.". -- Joseph S. Myers jos...@codesourcery.com
Re: [PATCH 1/4][RFC] middle-end/90348 - add explicit birth
Hello,
On Tue, 8 Feb 2022, Richard Biener wrote:
> > int state = 2, *p, camefrom1 = 0;
> > for (;;) switch (state) {
> > case 1:
> > case 2: ;
> > int i;
> > if (state != 1) { p = i = 0; }
> > if (state == 1) { (*p)++; return *p; }
> > state = 1;
> > continue;
> > }
> >
> > Note how i is initialized during state 2, and needs to be kept initialized
> > during state 1, so there must not be a CLOBBER (birth or other) at the
> > point of the declaration of 'i'. AFAICS in my simple tests a DECL_EXPR
> > for 'i' is placed with the statement associated with 'case 2' label,
> > putting a CLOBBER there would be the wrong thing. If the decl had an
> > initializer it might be harmless, as it would be overwritten at that
> > place, but even so, in this case there is no initializer. Hmm.
>
> You get after gimplification:
>
> state = 2;
> camefrom1 = 0;
> :
> switch (state) , case 1: , case 2: >
> {
> int i;
>
> try
> {
> i = {CLOBBER(birth)}; /// ignore, should go away
> :
> :
> i = {CLOBBER(birth)};
I think this clobber here would be the problem, because ...
> which I think is OK? That is, when the abstract machine
> arrives at 'int i;' then the previous content in 'i' goes
> away? Or would
>
> int foo()
> {
>goto ick;
> use:
>int i, *p;
>return *p;
> ick:
>i = 1;
>p =
>goto use;
>
> }
>
> require us to return 1?
... I think this is exactly the logical consequence of lifetime of 'i'
being the whole block. We need to return 1. (Joseph: correct me on that!
:) ) That's what I was trying to get at with my switch example as well.
> With the current patch 'i' is clobbered before the return.
>
> > Another complication arises from simple forward jumps:
> >
> > goto forw;
> > {
> > int i;
> > printf("not reachable\n");
> > forw:
> > i = 1;
> > }
> >
> > Despite the jump skiping the unreachable head of the BLOCK, 'i' needs to
> > be considered birthed at the label. (In a way the placement of births
> > exactly mirrors the placements of deaths (of course), every path from
> > outside a BLOCK to inside needs to birth-clobber all variables (in C),
> > like every path leaving needs to kill them. It's just that we have a
> > convenient construct for the latter (try-finally), but not for the former)
>
> The situation with an unreachable birth is handled conservatively
> since we consider a variable without a (visible at RTL expansion time)
> birth to conflict with all other variables.
That breaks down when a birth is there (because it was otherwise
reachable) but not on the taken path:
if (nevertrue)
goto start;
goto forw;
start:
{
int i;
printf("not really reachable, but unknowingly so\n");
forw:
i = 1;
}
> I don't see a good way to have a birth magically appear at 'forw'
> without trying to argue that the following stmt is the first mentioning
> the variable.
That's what my 'Hmm' aluded to :) The only correct and precise way I see
is to implement something similar like try-finally topside-down. An
easier but less precise way is to place the births at the (start of)
innermost block containing the decl _and all jumps into the block_. Even
less presice, but perhaps even easier is to place the births for decls in
blocks with side-entries into the function scope (and for blocks without
side entries at their start).
Except for switches side-entries are really really seldom, so we might
usefully get away with that latter solution. And for switches it might be
okay to put the births at the block containing the switch (if it itself
doesn't have side entries, and the switch block doesn't have side
entries except the case labels).
If the birth is moved to outward blocks it might be best if also the
dealloc/death clobbers are moved to it, otherwise there might be paths
containing a birth but no death.
The less precise you get with those births the more non-sharing you'll
get, but that's the price.
Ciao,
Michael.
Re: [PATCH 1/4][RFC] middle-end/90348 - add explicit birth
On Tue, 8 Feb 2022, Michael Matz wrote:
> Hello,
>
> On Tue, 8 Feb 2022, Richard Biener wrote:
>
> > int foo(int always_true_at_runtime)
> > {
> > {
> > int *p;
> > if (always_true_at_runtime)
> > goto after;
> > lab:
> > return *p;
> > after:
> > int i = 0;
> > p =
> > if (always_true_at_runtime)
> > goto lab;
> > }
> > return 0;
> > }
> >
> > For the implementation I considered starting lifetime at a DECL_EXPR
> > if it exists and otherwise at the start of the BIND_EXPR. Note the
> > complication is that control flow has to reach the lifetime-start
> > clobber before the first access. But that might also save us here,
> > since for the example above 'i' would be live via the backedge
> > from goto lab.
> >
> > That said, the existing complication is that when the gimplifier
> > visits the BIND_EXPR it has no way to know whether there will be
> > a following DECL_EXPR or not (and the gimplifier notes there are
> > cases a DECL_EXPR variable is not in a BIND_EXPR). My plan is to
> > compute this during one of the body walks the gimplifier performs
> > before gimplifying.
> >
> > Another complication is that at least the C frontend + gimplifier
> > combination for
> >
> > switch (i)
> > {
> > case 1:
> > int i;
> > break;
> > }
> >
> > will end up having the BIND_EXPR mentioning 'i' containing the
> > case label, so just placing the birth at the BIND will make it
> > unreachable as
> >
> > i = BIRTH;
> > case_label_for_1:
> > ...
>
> I think anything that needs to happen (conceptually) during the jump from
> switch to case-label needs to happen right before the jump, that might
> mean creating a new fake BLOCK that contains just the jump and the
> associated births.
>
> > conveniently at least the C frontend has a DECL_EXPR for 'i'
> > which avoids this and I did not find a way (yet) in the gimplifier
> > to rectify this when gimplifying switches.
>
> In C a 'case' label is nothing else than a normal label, it doesn't start
> it's own block or the like. So also for that one the births would need to
> be at the start of their containing blocks.
>
> > So there's still work to do but I think that starting the lifetime at a
> > DECL_EXPR if it exists is the way to go?
>
> Depends on where the DECL_EXPR is exactly placed, but probably it wouldn't
> be okay. You can't place the birth at the fall-through path, because this
> needs to work (basically your jump example above rewritten as switch):
>
> int state = 2, *p, camefrom1 = 0;
> for (;;) switch (state) {
> case 1:
> case 2: ;
> int i;
> if (state != 1) { p = i = 0; }
> if (state == 1) { (*p)++; return *p; }
> state = 1;
> continue;
> }
>
> Note how i is initialized during state 2, and needs to be kept initialized
> during state 1, so there must not be a CLOBBER (birth or other) at the
> point of the declaration of 'i'. AFAICS in my simple tests a DECL_EXPR
> for 'i' is placed with the statement associated with 'case 2' label,
> putting a CLOBBER there would be the wrong thing. If the decl had an
> initializer it might be harmless, as it would be overwritten at that
> place, but even so, in this case there is no initializer. Hmm.
You get after gimplification:
state = 2;
camefrom1 = 0;
:
switch (state) , case 1: , case 2: >
{
int i;
try
{
i = {CLOBBER(birth)}; /// ignore, should go away
:
:
i = {CLOBBER(birth)};
if (state != 1) goto ; else goto ;
:
p =
i = 0;
:
if (state == 1) goto ; else goto ;
:
_1 = *p;
_2 = _1 + 1;
*p = _2;
D.1995 = *p;
// predicted unlikely by early return (on trees) predictor.
return D.1995;
:
state = 1;
// predicted unlikely by continue predictor.
goto ;
}
finally
{
i = {CLOBBER(eol)};
}
}
which I think is OK? That is, when the abstract machine
arrives at 'int i;' then the previous content in 'i' goes
away? Or would
int foo()
{
goto ick;
use:
int i, *p;
return *p;
ick:
i = 1;
p =
goto use;
}
require us to return 1? With the current patch 'i' is clobbered
before the return.
> Another complication arises from simple forward jumps:
>
> goto forw;
> {
> int i;
> printf("not reachable\n");
> forw:
> i = 1;
> }
>
> Despite the jump skiping the unreachable head of the BLOCK, 'i' needs to
> be considered birthed at the label. (In a way the placement of births
> exactly mirrors the placements of deaths (of course), every path from
> outside a BLOCK to inside needs to birth-clobber all variables (in C),
> like every path leaving needs to kill them. It's just that we have a
> convenient construct for the latter (try-finally), but not for the former)
The situation with an unreachable birth is handled conservatively
since we consider a variable
Re: [PATCH 1/4][RFC] middle-end/90348 - add explicit birth
Hello,
On Tue, 8 Feb 2022, Richard Biener wrote:
> int foo(int always_true_at_runtime)
> {
> {
> int *p;
> if (always_true_at_runtime)
> goto after;
> lab:
> return *p;
> after:
> int i = 0;
> p =
> if (always_true_at_runtime)
> goto lab;
> }
> return 0;
> }
>
> For the implementation I considered starting lifetime at a DECL_EXPR
> if it exists and otherwise at the start of the BIND_EXPR. Note the
> complication is that control flow has to reach the lifetime-start
> clobber before the first access. But that might also save us here,
> since for the example above 'i' would be live via the backedge
> from goto lab.
>
> That said, the existing complication is that when the gimplifier
> visits the BIND_EXPR it has no way to know whether there will be
> a following DECL_EXPR or not (and the gimplifier notes there are
> cases a DECL_EXPR variable is not in a BIND_EXPR). My plan is to
> compute this during one of the body walks the gimplifier performs
> before gimplifying.
>
> Another complication is that at least the C frontend + gimplifier
> combination for
>
> switch (i)
> {
> case 1:
> int i;
> break;
> }
>
> will end up having the BIND_EXPR mentioning 'i' containing the
> case label, so just placing the birth at the BIND will make it
> unreachable as
>
> i = BIRTH;
> case_label_for_1:
> ...
I think anything that needs to happen (conceptually) during the jump from
switch to case-label needs to happen right before the jump, that might
mean creating a new fake BLOCK that contains just the jump and the
associated births.
> conveniently at least the C frontend has a DECL_EXPR for 'i'
> which avoids this and I did not find a way (yet) in the gimplifier
> to rectify this when gimplifying switches.
In C a 'case' label is nothing else than a normal label, it doesn't start
it's own block or the like. So also for that one the births would need to
be at the start of their containing blocks.
> So there's still work to do but I think that starting the lifetime at a
> DECL_EXPR if it exists is the way to go?
Depends on where the DECL_EXPR is exactly placed, but probably it wouldn't
be okay. You can't place the birth at the fall-through path, because this
needs to work (basically your jump example above rewritten as switch):
int state = 2, *p, camefrom1 = 0;
for (;;) switch (state) {
case 1:
case 2: ;
int i;
if (state != 1) { p = i = 0; }
if (state == 1) { (*p)++; return *p; }
state = 1;
continue;
}
Note how i is initialized during state 2, and needs to be kept initialized
during state 1, so there must not be a CLOBBER (birth or other) at the
point of the declaration of 'i'. AFAICS in my simple tests a DECL_EXPR
for 'i' is placed with the statement associated with 'case 2' label,
putting a CLOBBER there would be the wrong thing. If the decl had an
initializer it might be harmless, as it would be overwritten at that
place, but even so, in this case there is no initializer. Hmm.
Another complication arises from simple forward jumps:
goto forw;
{
int i;
printf("not reachable\n");
forw:
i = 1;
}
Despite the jump skiping the unreachable head of the BLOCK, 'i' needs to
be considered birthed at the label. (In a way the placement of births
exactly mirrors the placements of deaths (of course), every path from
outside a BLOCK to inside needs to birth-clobber all variables (in C),
like every path leaving needs to kill them. It's just that we have a
convenient construct for the latter (try-finally), but not for the former)
Ciao,
Michael.
Re: [PATCH 1/4][RFC] middle-end/90348 - add explicit birth
> I don't think an option to go to pre-12 behavior is useful. I'll > postpone the series to stage1. FWIW fine with me. -- Eric Botcazou
Re: [PATCH 1/4][RFC] middle-end/90348 - add explicit birth
On Mon, 7 Feb 2022, Joseph Myers wrote:
> On Fri, 4 Feb 2022, Richard Biener via Gcc-patches wrote:
>
> > This adds explicit variable birth CLOBBERs in an attempt to fix
> > PR90348 and duplicates. The birth / death CLOBBER pairs are
> > used to compute liveness and conflicts for stack variable
> > coalescing where the lack of an explicit birth but instead
> > use of first mention causes misrepresentation of variable life
> > ranges when optimization moves the first mention upwards the
> > original birth point at the variables bind expression start.
>
> I'm not clear on exactly where you consider a variable to be born, but
> note that non-VLA C variables have a lifetime that starts at the beginning
> of their block, not at their declaration: it's valid to jump backward from
> after the declaration to before it and then access the variable via a
> pointer, or jump forward again over the declaration and access it by name.
> (Most programs of course don't do that sort of thing.)
Oh, interesting. So the following is valid
int foo(int always_true_at_runtime)
{
{
int *p;
if (always_true_at_runtime)
goto after;
lab:
return *p;
after:
int i = 0;
p =
if (always_true_at_runtime)
goto lab;
}
return 0;
}
For the implementation I considered starting lifetime at a DECL_EXPR
if it exists and otherwise at the start of the BIND_EXPR. Note the
complication is that control flow has to reach the lifetime-start
clobber before the first access. But that might also save us here,
since for the example above 'i' would be live via the backedge
from goto lab.
That said, the existing complication is that when the gimplifier
visits the BIND_EXPR it has no way to know whether there will be
a following DECL_EXPR or not (and the gimplifier notes there are
cases a DECL_EXPR variable is not in a BIND_EXPR). My plan is to
compute this during one of the body walks the gimplifier performs
before gimplifying.
Another complication is that at least the C frontend + gimplifier
combination for
switch (i)
{
case 1:
int i;
break;
}
will end up having the BIND_EXPR mentioning 'i' containing the
case label, so just placing the birth at the BIND will make it
unreachable as
i = BIRTH;
case_label_for_1:
...
conveniently at least the C frontend has a DECL_EXPR for 'i'
which avoids this and I did not find a way (yet) in the gimplifier
to rectify this when gimplifying switches.
So there's still work to do but I think that starting the lifetime
at a DECL_EXPR if it exists is the way to go?
Richard.
Re: [PATCH 1/4][RFC] middle-end/90348 - add explicit birth
On Fri, 4 Feb 2022, Richard Biener via Gcc-patches wrote: > This adds explicit variable birth CLOBBERs in an attempt to fix > PR90348 and duplicates. The birth / death CLOBBER pairs are > used to compute liveness and conflicts for stack variable > coalescing where the lack of an explicit birth but instead > use of first mention causes misrepresentation of variable life > ranges when optimization moves the first mention upwards the > original birth point at the variables bind expression start. I'm not clear on exactly where you consider a variable to be born, but note that non-VLA C variables have a lifetime that starts at the beginning of their block, not at their declaration: it's valid to jump backward from after the declaration to before it and then access the variable via a pointer, or jump forward again over the declaration and access it by name. (Most programs of course don't do that sort of thing.) -- Joseph S. Myers jos...@codesourcery.com
Re: [PATCH 1/4][RFC] middle-end/90348 - add explicit birth
On Sat, 5 Feb 2022, Eric Botcazou wrote: > > In the past stack sharing has been quite important for the linux > > kernel. So perhaps one of the tests we should do if we wanted to go > > forward in this cycle would be to test kernel builds to see if any start > > tripping over the stack space diagnostics they've put in place over the > > years. > > Stack slot sharing is important generally speaking, not just for the kernel. > As demonstrated by the recent controversy about the 1/X optimization, last- > minute broad changes made during stage #4 are generally not a good idea, and > I'm not sure what the incentive for fixing PR middle-end/90348 now is (it's > labeled a 9/10/11/12 regression). At a minimum, I think that a switch to > revert to the pre-12 behavior would be in order if the patch goes in now. I don't think an option to go to pre-12 behavior is useful. I'll postpone the series to stage1. Richard.
Re: [PATCH 1/4][RFC] middle-end/90348 - add explicit birth
> In the past stack sharing has been quite important for the linux > kernel. So perhaps one of the tests we should do if we wanted to go > forward in this cycle would be to test kernel builds to see if any start > tripping over the stack space diagnostics they've put in place over the > years. Stack slot sharing is important generally speaking, not just for the kernel. As demonstrated by the recent controversy about the 1/X optimization, last- minute broad changes made during stage #4 are generally not a good idea, and I'm not sure what the incentive for fixing PR middle-end/90348 now is (it's labeled a 9/10/11/12 regression). At a minimum, I think that a switch to revert to the pre-12 behavior would be in order if the patch goes in now. -- Eric Botcazou
Re: [PATCH 1/4][RFC] middle-end/90348 - add explicit birth
On 2/4/2022 6:49 AM, Richard Biener via Gcc-patches wrote: This adds explicit variable birth CLOBBERs in an attempt to fix PR90348 and duplicates. The birth / death CLOBBER pairs are used to compute liveness and conflicts for stack variable coalescing where the lack of an explicit birth but instead use of first mention causes misrepresentation of variable life ranges when optimization moves the first mention upwards the original birth point at the variables bind expression start. Birth CLOBBERs are represented as traditional CLOBBERs with all the accompaning effect on optimization. While they do not serve as a barrier for address mentions they act as barrier for the actual accesses which is enough for determining conflicts in the context of stack slot sharing. The birth CLOBBERs are distinguished from death CLOBBERs by setting CLOBBER_MARKS_BIRTH using the private_flag on the CONSTRUCTOR node and amend the CLOBBER_MARK_EOL marked clobbers introduced earlier. The patch changes how we handle stack variables that are not marked with CLOBBERs. For those the first mention started live which then lasted upon function exit which means effectively all not marked variables conflicted with each other variable. This property is best represented by an extra flag rather than the full conflict bitmap which is what the patch introduces with conflicts_represented which is cleared at start and set to true once we visit the first birth CLOBBER. From that on we assume all variable accesses are properly fenced by birth/death CLOBBERs. Variables without explicit births will not take part in stack slot sharing after this change. Currently birth CLOBBERs are added when gimplification adds corresponding end-of-life CLOBBERs, during bind and target expression gimplification. Generally inserting births at DECL_EXPRs is more precise so we also do it there (also noting not all such variables are mentioned in BINDs). Avoiding redundant births is on the TOOD list and might also remove the need for the warn_switch_unreachable_r hunk. This is the meat of the PR90348 fix, the following 3 patches perform testcase adjustments and followup fixes to avoid regressions. Bootstrapped on x86_64-unknown-linux-gnu - re-testing in progress. Any comments? I have mixed feelings with proposing this for GCC 12 but like to hear from others as well. I didn't try to evaluate the quality of stack slot sharing before/after this change besides fixing the testsuite fallout (we have a few testcases checking for specific instances). Thanks, Richard. 2022-02-01 Richard Biener PR middle-end/90348 PR middle-end/103006 * tree-core.h (clobber_kind): Add CLOBBER_BIRTH. * gimplify.cc (gimplify_bind_expr): Also add birth CLOBBERs. (gimplify_target_expr): Likewise. (gimplify_decl_expr): Likewise. (warn_switch_unreachable_r): Do not treat birth CLOBBERs as real stmt - they get added at BIND starts but that's before the case labels. * tree-pretty-print.cc (dump_generic_node): Mark birth CLOBBERs. * cfgexpand.cc (stack_var::conflicts_represented): New. (add_stack_var): Initialize conflicts_represented. (add_stack_var_conflict): Assert the conflicts for the vars are represented. (stack_var_conflict_p): Honor conflicts_represented flag. (visit_op): Remove. (visit_conflict): Likewise. (add_scope_conflicts_1): Simplify by only considering birth and death CLOBBERs. (add_scope_conflicts): Adjust comment. (add_stack_protection_conflicts): Only add conflicts for variables that have them represented. * gcc.dg/torture/pr103006-1.c: New testcase. * gcc.dg/torture/pr103006-2.c: Likewise. * gcc.dg/torture/pr90348.c: Likewise. The lack of explicit birth/death points in gimple has been a long standing problem, so definitely happy to see this moving forward. As you note, it's not clear if we should go forward now or wait for the next stage1 cycle. In the past stack sharing has been quite important for the linux kernel. So perhaps one of the tests we should do if we wanted to go forward in this cycle would be to test kernel builds to see if any start tripping over the stack space diagnostics they've put in place over the years. Jeff
Re: [PATCH 1/4][RFC] middle-end/90348 - add explicit birth
On Fri, 4 Feb 2022, Jakub Jelinek wrote: > On Fri, Feb 04, 2022 at 02:49:13PM +0100, Richard Biener wrote: > > Any comments? I have mixed feelings with proposing this for GCC 12 > > but like to hear from others as well. I didn't try to evaluate > > the quality of stack slot sharing before/after this change besides > > fixing the testsuite fallout (we have a few testcases checking for > > specific instances). > > I have mixed feelings too, it is quite risky, on the other side we have > those numerous otherwise unsolvable PRs. Yep - it seems it's always stage3/4 when we get to those. That said, I'm happy to wait for stage1 and I'm also happy to revert if issues pop up. > I wonder if tree-ssa-live.cc (compute_live_vars_1) doesn't need similar > changes, after all, it is a variant of the cfgexpand algorithm. Oh, I wasn't aware of that. It seems it's only used by tail-recursion and inlining (there for inserting CLOBBERs). But yes, I think it might suffer from the same issue. > And I'll certainly need to incrementally mark most if not all current > build_clobbers in omp-low.cc as EOLs and emit birth clobbers (stuff that is > added post gimplification, so too late for gimplification's added birth/eol > handling there and so it must be done manually). Adding testcases for intended stack slot sharing in those cases would be nice. Richard.
Re: [PATCH 1/4][RFC] middle-end/90348 - add explicit birth
On Fri, Feb 04, 2022 at 02:49:13PM +0100, Richard Biener wrote: > Any comments? I have mixed feelings with proposing this for GCC 12 > but like to hear from others as well. I didn't try to evaluate > the quality of stack slot sharing before/after this change besides > fixing the testsuite fallout (we have a few testcases checking for > specific instances). I have mixed feelings too, it is quite risky, on the other side we have those numerous otherwise unsolvable PRs. I wonder if tree-ssa-live.cc (compute_live_vars_1) doesn't need similar changes, after all, it is a variant of the cfgexpand algorithm. And I'll certainly need to incrementally mark most if not all current build_clobbers in omp-low.cc as EOLs and emit birth clobbers (stuff that is added post gimplification, so too late for gimplification's added birth/eol handling there and so it must be done manually). Jakub
[PATCH 1/4][RFC] middle-end/90348 - add explicit birth
This adds explicit variable birth CLOBBERs in an attempt to fix PR90348 and duplicates. The birth / death CLOBBER pairs are used to compute liveness and conflicts for stack variable coalescing where the lack of an explicit birth but instead use of first mention causes misrepresentation of variable life ranges when optimization moves the first mention upwards the original birth point at the variables bind expression start. Birth CLOBBERs are represented as traditional CLOBBERs with all the accompaning effect on optimization. While they do not serve as a barrier for address mentions they act as barrier for the actual accesses which is enough for determining conflicts in the context of stack slot sharing. The birth CLOBBERs are distinguished from death CLOBBERs by setting CLOBBER_MARKS_BIRTH using the private_flag on the CONSTRUCTOR node and amend the CLOBBER_MARK_EOL marked clobbers introduced earlier. The patch changes how we handle stack variables that are not marked with CLOBBERs. For those the first mention started live which then lasted upon function exit which means effectively all not marked variables conflicted with each other variable. This property is best represented by an extra flag rather than the full conflict bitmap which is what the patch introduces with conflicts_represented which is cleared at start and set to true once we visit the first birth CLOBBER. From that on we assume all variable accesses are properly fenced by birth/death CLOBBERs. Variables without explicit births will not take part in stack slot sharing after this change. Currently birth CLOBBERs are added when gimplification adds corresponding end-of-life CLOBBERs, during bind and target expression gimplification. Generally inserting births at DECL_EXPRs is more precise so we also do it there (also noting not all such variables are mentioned in BINDs). Avoiding redundant births is on the TOOD list and might also remove the need for the warn_switch_unreachable_r hunk. This is the meat of the PR90348 fix, the following 3 patches perform testcase adjustments and followup fixes to avoid regressions. Bootstrapped on x86_64-unknown-linux-gnu - re-testing in progress. Any comments? I have mixed feelings with proposing this for GCC 12 but like to hear from others as well. I didn't try to evaluate the quality of stack slot sharing before/after this change besides fixing the testsuite fallout (we have a few testcases checking for specific instances). Thanks, Richard. 2022-02-01 Richard Biener PR middle-end/90348 PR middle-end/103006 * tree-core.h (clobber_kind): Add CLOBBER_BIRTH. * gimplify.cc (gimplify_bind_expr): Also add birth CLOBBERs. (gimplify_target_expr): Likewise. (gimplify_decl_expr): Likewise. (warn_switch_unreachable_r): Do not treat birth CLOBBERs as real stmt - they get added at BIND starts but that's before the case labels. * tree-pretty-print.cc (dump_generic_node): Mark birth CLOBBERs. * cfgexpand.cc (stack_var::conflicts_represented): New. (add_stack_var): Initialize conflicts_represented. (add_stack_var_conflict): Assert the conflicts for the vars are represented. (stack_var_conflict_p): Honor conflicts_represented flag. (visit_op): Remove. (visit_conflict): Likewise. (add_scope_conflicts_1): Simplify by only considering birth and death CLOBBERs. (add_scope_conflicts): Adjust comment. (add_stack_protection_conflicts): Only add conflicts for variables that have them represented. * gcc.dg/torture/pr103006-1.c: New testcase. * gcc.dg/torture/pr103006-2.c: Likewise. * gcc.dg/torture/pr90348.c: Likewise. --- gcc/cfgexpand.cc | 157 +- gcc/gimplify.cc | 83 +++- gcc/testsuite/gcc.dg/torture/pr103006-1.c | 27 gcc/testsuite/gcc.dg/torture/pr103006-2.c | 29 gcc/testsuite/gcc.dg/torture/pr90348.c| 40 ++ gcc/tree-core.h | 2 + gcc/tree-pretty-print.cc | 4 +- 7 files changed, 244 insertions(+), 98 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/torture/pr103006-1.c create mode 100644 gcc/testsuite/gcc.dg/torture/pr103006-2.c create mode 100644 gcc/testsuite/gcc.dg/torture/pr90348.c diff --git a/gcc/cfgexpand.cc b/gcc/cfgexpand.cc index d51af2e3084..02467874996 100644 --- a/gcc/cfgexpand.cc +++ b/gcc/cfgexpand.cc @@ -319,6 +319,10 @@ public: size, the alignment for this partition. */ unsigned int alignb; + /* Whether this variable has conflicts represented in the CONFLICTS + bitmap. If not, it conflicts with all other stack variables. */ + bool conflicts_represented; + /* The partition representative. */ size_t representative; @@ -479,7 +483,8 @@ add_stack_var (tree decl, bool really_expand) v->representative =
