Re: [PATCH/RFC] combine: Tweak the condition of last_set invalidation
Hi!
On Wed, Dec 16, 2020 at 04:49:49PM +0800, Kewen.Lin wrote:
> Currently we have the check:
>
> if (!insn
> || (value && rsp->last_set_table_tick >= label_tick_ebb_start))
> rsp->last_set_invalid = 1;
>
> which means if we want to record some value for some reg and
> this reg got refered before in a valid scope,
If we already know it is *set* in this same extended basic block.
Possibly by the same instruction btw.
> we invalidate the
> set of reg (last_set_invalid to 1). It avoids to find the wrong
> set for one reg reference, such as the case like:
>
>... op regX // this regX could find wrong last_set below
>regX = ... // if we think this set is valid
>... op regX
Yup, exactly.
> But because of retry's existence, the last_set_table_tick could
> be set by some later reference insns, but we see it's set due
> to retry on the set (for that reg) insn again, such as:
>
>insn 1
>insn 2
>
>regX = ... --> (a)
>... op regX--> (b)
>
>insn 3
>
>// assume all in the same BB.
>
> Assuming we combine 1, 2 -> 3 sucessfully and replace them as two
> (3 insns -> 2 insns),
This will delete insn 1 and write the combined result to insns 2 and 3.
> retrying from insn1 or insn2 again:
Always 2, but your point remains valid.
> it will scan insn (a) again, the below condition holds for regX:
>
> (value && rsp->last_set_table_tick >= label_tick_ebb_start)
>
> it will mark this set as invalid set. But actually the
> last_set_table_tick here is set by insn (b) before retrying, so it
> should be safe to be taken as valid set.
Yup.
> This proposal is to check whether the last_set_table safely happens
> after the current set, make the set still valid if so.
> Full SPEC2017 building shows this patch gets more sucessful combines
> from 1902208 to 1902243 (trivial though).
Do you have some example, or maybe even a testcase? :-)
> + /* Record the luid of the insn whose expression involving register n. */
> +
> + intlast_set_table_luid;
"Record the luid of the insn for which last_set_table_tick was set",
right?
> -static void update_table_tick (rtx);
> +static void update_table_tick (rtx, int);
Please remove this declaration instead, the function is not used until
after its actual definition :-)
> @@ -13243,7 +13247,21 @@ update_table_tick (rtx x)
>for (r = regno; r < endregno; r++)
> {
> reg_stat_type *rsp = _stat[r];
> - rsp->last_set_table_tick = label_tick;
> + if (rsp->last_set_table_tick >= label_tick_ebb_start)
> + {
> + /* Later references should not have lower ticks. */
> + gcc_assert (label_tick >= rsp->last_set_table_tick);
This should be obvious, but checking it won't hurt, okay.
> + /* Should pick up the lowest luid if the references
> + are in the same block. */
> + if (label_tick == rsp->last_set_table_tick
> + && rsp->last_set_table_luid > insn_luid)
> + rsp->last_set_table_luid = insn_luid;
Why? Is it conservative for the check you will do later? Please spell
this out, it is crucial!
> @@ -13359,7 +13378,10 @@ record_value_for_reg (rtx reg, rtx_insn *insn, rtx
> value)
>
>/* Mark registers that are being referenced in this value. */
>if (value)
> -update_table_tick (value);
> +{
> + gcc_assert (insn);
> + update_table_tick (value, DF_INSN_LUID (insn));
> +}
Don't add that assert please. If you really want one it should come
right at the start of the function, not 60 lines later :-)
Looks good if I understood this correctly :-)
Segher
Re: [PATCH/RFC] combine: Tweak the condition of last_set invalidation
Hi Segher, >> >> I think this should be postponed to stage 1 though? Or is there >> anything very urgent in it? >> > > Yeah, I agree that this belongs to stage1, and there isn't anything > urgent about it. Thanks for all further comments above! > Gentle ping this: https://gcc.gnu.org/pipermail/gcc-patches/2020-December/562015.html BR, Kewen
Re: [PATCH/RFC] combine: Tweak the condition of last_set invalidation
Hi Segher, on 2021/1/22 上午8:30, Segher Boessenkool wrote: > Hi Ke Wen, > > On Fri, Jan 15, 2021 at 04:06:17PM +0800, Kewen.Lin wrote: >> on 2021/1/15 上午8:22, Segher Boessenkool wrote: >>> On Wed, Dec 16, 2020 at 04:49:49PM +0800, Kewen.Lin wrote: ... op regX // this regX could find wrong last_set below regX = ... // if we think this set is valid ... op regX But because of retry's existence, the last_set_table_tick could >>> >>> It is not just because of retry: combine can change other insns than >>> just i2 and i3, too. And even changing i2 requires this! >> >> Ah, thanks for the information! Here retry is one example for that >> we can revisit one instruction but meanwhile the stored information >> for reg reference can be from that instruction after the current >> one but visited before. > > Yes; and we do not usually revisit just one insn, but everything after > it as well. We only need to revisit thos insns that are fed by what > has changed, but this is a good enough approximation (we never revisit > very far back). > >>> The whole reg_stat stuff is an ugly hack that does not work well. For >>> example, as in your example, some "known" value can be invalidated >>> before the combination that wants to know that value is tried. >>> >>> We need to have this outside of combine, in a dataflow(-like) thing >>> for example. This could take the place of REG_EQ* as well probably >>> (which is good, there are various problems with that as well). >> >> Good point, but IIUC we still need to keep updating(tracking) >> information like what we put into reg_stat stuff, it's not static >> since as you pointed out above, combine can change i2/i3 etc, >> we need to update the information for the changes. > > Yes, we should keep it correct all the time, and for any point in the > code. It also can be used by other passes, e.g. it can replace all > REG_EQ* notes, all nonzero_bits and num_sign_bit_copies, and no doubt > even more things. > >> Anyway, it's not what this patch tries to solve. :-P > > :-) > This proposal is to check whether the last_set_table safely happens after the current set, make the set still valid if so. >>> >>> I don't think this is safe to do like this, unfortunately. There are >>> more places that set last_set_invalid (well, one more), so at the very >>> minimum this needs a lot more justification. >> >> Let me try to explain it more. >> * Background * >> >> There are two places which set last_set_invalid to 1. >> >> CASE 1: > > > > Thanks for the in-depth explanation! > > I think this should be postponed to stage 1 though? Or is there > anything very urgent in it? > Yeah, I agree that this belongs to stage1, and there isn't anything urgent about it. Thanks for all further comments above! BR, Kewen
Re: [PATCH/RFC] combine: Tweak the condition of last_set invalidation
Hi Ke Wen, On Fri, Jan 15, 2021 at 04:06:17PM +0800, Kewen.Lin wrote: > on 2021/1/15 上午8:22, Segher Boessenkool wrote: > > On Wed, Dec 16, 2020 at 04:49:49PM +0800, Kewen.Lin wrote: > >>... op regX // this regX could find wrong last_set below > >>regX = ... // if we think this set is valid > >>... op regX > >> > >> But because of retry's existence, the last_set_table_tick could > > > > It is not just because of retry: combine can change other insns than > > just i2 and i3, too. And even changing i2 requires this! > > Ah, thanks for the information! Here retry is one example for that > we can revisit one instruction but meanwhile the stored information > for reg reference can be from that instruction after the current > one but visited before. Yes; and we do not usually revisit just one insn, but everything after it as well. We only need to revisit thos insns that are fed by what has changed, but this is a good enough approximation (we never revisit very far back). > > The whole reg_stat stuff is an ugly hack that does not work well. For > > example, as in your example, some "known" value can be invalidated > > before the combination that wants to know that value is tried. > > > > We need to have this outside of combine, in a dataflow(-like) thing > > for example. This could take the place of REG_EQ* as well probably > > (which is good, there are various problems with that as well). > > Good point, but IIUC we still need to keep updating(tracking) > information like what we put into reg_stat stuff, it's not static > since as you pointed out above, combine can change i2/i3 etc, > we need to update the information for the changes. Yes, we should keep it correct all the time, and for any point in the code. It also can be used by other passes, e.g. it can replace all REG_EQ* notes, all nonzero_bits and num_sign_bit_copies, and no doubt even more things. > Anyway, it's not what this patch tries to solve. :-P :-) > >> This proposal is to check whether the last_set_table safely happens > >> after the current set, make the set still valid if so. > > > > I don't think this is safe to do like this, unfortunately. There are > > more places that set last_set_invalid (well, one more), so at the very > > minimum this needs a lot more justification. > > Let me try to explain it more. > * Background * > > There are two places which set last_set_invalid to 1. > > CASE 1: Thanks for the in-depth explanation! I think this should be postponed to stage 1 though? Or is there anything very urgent in it? Segher
Re: [PATCH/RFC] combine: Tweak the condition of last_set invalidation
Hi Segher,
Thanks for the comments!
on 2021/1/15 上午8:22, Segher Boessenkool wrote:
> Hi!
>
> On Wed, Dec 16, 2020 at 04:49:49PM +0800, Kewen.Lin wrote:
>> When I was investigating unsigned int vec_init issue on Power,
>> I happened to find there seems something we can enhance in how
>> combine pass invalidate last_set (set last_set_invalid nonzero).
>>
>> Currently we have the check:
>>
>> if (!insn
>>|| (value && rsp->last_set_table_tick >= label_tick_ebb_start))
>> rsp->last_set_invalid = 1;
>>
>> which means if we want to record some value for some reg and
>> this reg got refered before in a valid scope, we invalidate the
>> set of reg (last_set_invalid to 1). It avoids to find the wrong
>> set for one reg reference, such as the case like:
>>
>>... op regX // this regX could find wrong last_set below
>>regX = ... // if we think this set is valid
>>... op regX
>>
>> But because of retry's existence, the last_set_table_tick could
>
> It is not just because of retry: combine can change other insns than
> just i2 and i3, too. And even changing i2 requires this!
>
Ah, thanks for the information! Here retry is one example for that
we can revisit one instruction but meanwhile the stored information
for reg reference can be from that instruction after the current
one but visited before.
> The whole reg_stat stuff is an ugly hack that does not work well. For
> example, as in your example, some "known" value can be invalidated
> before the combination that wants to know that value is tried.
>
> We need to have this outside of combine, in a dataflow(-like) thing
> for example. This could take the place of REG_EQ* as well probably
> (which is good, there are various problems with that as well).
>
Good point, but IIUC we still need to keep updating(tracking)
information like what we put into reg_stat stuff, it's not static
since as you pointed out above, combine can change i2/i3 etc,
we need to update the information for the changes. Anyway, it's not
what this patch tries to solve. :-P
>> This proposal is to check whether the last_set_table safely happens
>> after the current set, make the set still valid if so.
>
> I don't think this is safe to do like this, unfortunately. There are
> more places that set last_set_invalid (well, one more), so at the very
> minimum this needs a lot more justification.
>
Let me try to explain it more.
* Background *
There are two places which set last_set_invalid to 1.
CASE 1:
```
if (CALL_P (insn))
{
HARD_REG_SET callee_clobbers
= insn_callee_abi (insn).full_and_partial_reg_clobbers ();
hard_reg_set_iterator hrsi;
EXECUTE_IF_SET_IN_HARD_REG_SET (callee_clobbers, 0, i, hrsi)
{
reg_stat_type *rsp;
/* ??? We could try to preserve some information from the last
set of register I if the call doesn't actually clobber
(reg:last_set_mode I), which might be true for ABIs with
partial clobbers. However, it would be difficult to
update last_set_nonzero_bits and last_sign_bit_copies
to account for the part of I that actually was clobbered.
It wouldn't help much anyway, since we rarely see this
situation before RA. */
rsp = _stat[i];
rsp->last_set_invalid = 1;
```
The justification for this part is that if ABI defines some callee
clobberred registers, we need to invalidate their sets to avoid
later references to use the unexpected values.
CASE 2:
```
for (i = regno; i < endregno; i++)
{
rsp = _stat[i];
rsp->last_set_label = label_tick;
if (!insn
|| (value && rsp->last_set_table_tick >= label_tick_ebb_start))
rsp->last_set_invalid = 1;
else
rsp->last_set_invalid = 0;
}
```
The justification here is that: if the insn is NULL, it's simply to
invalidate this reg set, go for it; if the value is NULL, it's simply
to say the reg clobberred, invalidate it; if the reference of this
reg being set have been seen, let's invalidate it.
The last part follows the comments:
/* Now update the status of each register being set.
If someone is using this register in this block, set this register
to invalid since we will get confused between the two lives in this
basic block. This makes using this register always invalid. In cse, we
scan the table to invalidate all entries using this register, but this
is too much work for us. */
It's understandable to invalidate it to avoid the case:
... op regX// (a)
regX = ... // (b)
... op regX// (c)
When we are revisiting (a), it avoids to use the reg set in (b).
* Problem *
Firstly, the problem that this patch is trying to solve is mainly related
to case 2, so it doesn't touch CASE 1.
In the context of CASE 2, the current condition
(rsp->last_set_table_tick >= label_tick_ebb_start)
is completely safe but too
Re: [PATCH/RFC] combine: Tweak the condition of last_set invalidation
Hi! On Wed, Dec 16, 2020 at 04:49:49PM +0800, Kewen.Lin wrote: > When I was investigating unsigned int vec_init issue on Power, > I happened to find there seems something we can enhance in how > combine pass invalidate last_set (set last_set_invalid nonzero). > > Currently we have the check: > > if (!insn > || (value && rsp->last_set_table_tick >= label_tick_ebb_start)) > rsp->last_set_invalid = 1; > > which means if we want to record some value for some reg and > this reg got refered before in a valid scope, we invalidate the > set of reg (last_set_invalid to 1). It avoids to find the wrong > set for one reg reference, such as the case like: > >... op regX // this regX could find wrong last_set below >regX = ... // if we think this set is valid >... op regX > > But because of retry's existence, the last_set_table_tick could It is not just because of retry: combine can change other insns than just i2 and i3, too. And even changing i2 requires this! The whole reg_stat stuff is an ugly hack that does not work well. For example, as in your example, some "known" value can be invalidated before the combination that wants to know that value is tried. We need to have this outside of combine, in a dataflow(-like) thing for example. This could take the place of REG_EQ* as well probably (which is good, there are various problems with that as well). > This proposal is to check whether the last_set_table safely happens > after the current set, make the set still valid if so. I don't think this is safe to do like this, unfortunately. There are more places that set last_set_invalid (well, one more), so at the very minimum this needs a lot more justification. Segher
