PING^7 [PATCH v2] combine: Tweak the condition of last_set invalidation

[Kewen.Lin]

Hi,

Gentle ping this:

https://gcc.gnu.org/pipermail/gcc-patches/2021-June/572555.html

BR,
Kewen

>>>>>> on 2021/6/11 下午9:16, Kewen.Lin via Gcc-patches wrote:
>>>>>>> Hi Segher,
>>>>>>>
>>>>>>> Thanks for the review!
>>>>>>>
>>>>>>> on 2021/6/10 上午4:17, Segher Boessenkool wrote:
>>>>>>>> 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?  :-)
>>>>>>>>
>>>>>>>
>>>>>>> Sorry for the late reply, it took some time to get one reduced case.
>>>>>>>
>>>>>>> typedef struct SA *pa_t;
>>>>>>>
>>>>>>> struct SC {
>>>>>>>   int h;
>>>>>>>   pa_t elem[];
>>>>>>> };
>>>>>>>
>>>>>>> struct SD {
>>>>>>>   struct SC *e;
>>>>>>> };
>>>>>>>
>>>>>>> struct SA {
>>>>>>>   struct {
>>>>>>>     struct SD f[1];
>>>>>>>   } g;
>>>>>>> };
>>>>>>>
>>>>>>> void foo(pa_t *k, char **m) {
>>>>>>>   int l, i;
>>>>>>>   pa_t a;
>>>>>>>   l = (int)a->g.f[5].e;
>>>>>>>   i = 0;
>>>>>>>   for (; i < l; i++) {
>>>>>>>     k[i] = a->g.f[5].e->elem[i];
>>>>>>>     m[i] = "";
>>>>>>>   }
>>>>>>> }
>>>>>>>
>>>>>>> Baseline is r12-0 and the option is "-O3 -mcpu=power9 -fno-strict-aliasing",
>>>>>>> with this patch, the generated assembly can save two rlwinm s.
>>>>>>>
>>>>>>>>> +  /* Record the luid of the insn whose expression involving register n.  */
>>>>>>>>> +
>>>>>>>>> +  int				last_set_table_luid;
>>>>>>>>
>>>>>>>> "Record the luid of the insn for which last_set_table_tick was set",
>>>>>>>> right?
>>>>>>>>
>>>>>>>
>>>>>>> But it can be updated later to one smaller luid, how about the wording like:
>>>>>>>
>>>>>>>
>>>>>>> +  /* Record the luid of the insn which uses register n, the insn should
>>>>>>> +     be the first one using register n in that block of the insn which
>>>>>>> +     last_set_table_tick was set for.  */
>>>>>>>
>>>>>>>
>>>>>>>>> -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 :-)
>>>>>>>>
>>>>>>>
>>>>>>> Done.
>>>>>>>
>>>>>>>>> @@ -13243,7 +13247,21 @@ update_table_tick (rtx x)
>>>>>>>>>        for (r = regno; r < endregno; r++)
>>>>>>>>>  	{
>>>>>>>>>  	  reg_stat_type *rsp = &reg_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!
>>>>>>>>
>>>>>>>
>>>>>>> Since later the combinations involving this insn probably make the
>>>>>>> register be used in one insn sitting ahead (which has smaller luid than
>>>>>>> the one which was recorded before).  Yes, it's very conservative, this
>>>>>>> ensure that we always use the luid of the insn which is the first insn
>>>>>>> using this register in the block.  The last_set invalidation is going
>>>>>>> to catch the case like:
>>>>>>>
>>>>>>>    ... regX  // avoid the set used here ...
>>>>>>>    regX = ...
>>>>>>>    ...
>>>>>>>
>>>>>>> Once we have the smallest luid one of all insns which use register X,
>>>>>>> any unsafe regX sets should be caught.
>>>>>>>
>>>>>>> I updated the comments to:
>>>>>>>
>>>>>>> +              /* Since combination may generate some instructions
>>>>>>> +                 to replace some foregoing instructions with the
>>>>>>> +                 references to register r (using register r), we
>>>>>>> +                 need to make sure we record the first instruction
>>>>>>> +                 which is using register r, so always update with
>>>>>>> +                 the lowest luid here.  If the given set happens
>>>>>>> +                 before this recorded earliest reference, the set
>>>>>>> +                 value should be safe to be used.  */
>>>>>>>
>>>>>>>>> @@ -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 :-)
>>>>>>>>
>>>>>>>
>>>>>>> Exactly, fixed.
>>>>>>>
>>>>>>>> Looks good if I understood this correctly :-)
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>> Thanks again, I also updated the comments in func record_value_for_reg,
>>>>>>> the new version is attached.
>>>>>>>
>>>>>>> BR,
>>>>>>> Kewen
>>>>>>> -----
>>>>>>> gcc/ChangeLog:
>>>>>>>
>>>>>>> 	* combine.c (struct reg_stat_type): New member
>>>>>>> 	last_set_table_luid.
>>>>>>> 	(update_table_tick): Add one argument for insn luid and
>>>>>>> 	set last_set_table_luid with it, remove its declaration.
>>>>>>> 	(record_value_for_reg): Adjust the condition to set
>>>>>>> 	last_set_invalid nonzero.
>>>>>>>


BR,
Kewen