setmemsi, movmemsi and post_inc

setmemsi, movmemsi and post_inc

[Stefan Franke]

Hi there,

 

I consider implementing movmemsi/setmemsi for some arch using post_inc. Is
there a "best practice" for using auto increments in such early stages to
avoid hickups in cse, gcse, cprop etc.p.p.?

 

It looks like this:

 

(insn 8 7 9 2 (set (reg:SI 41)

        (reg/f:SI 40)) 

     (expr_list:REG_INC (reg:SI 41)

        (nil)))

(insn 9 8 10 2 (set (reg:SI 42)

        (reg/f:SI 39)) 

     (expr_list:REG_INC (reg:SI 42)

        (nil)))

(insn 10 9 11 2 (set (mem:QI (post_inc:SI (reg:SI 42)) [0  S1 A8])

        (mem:QI (post_inc:SI (reg:SI 41)) [0  S1 A8]))

     (expr_list:REG_INC (reg:SI 42)

        (expr_list:REG_INC (reg:SI 41)

            (nil))))

(insn 11 10 12 2 (set (mem:QI (post_inc:SI (reg:SI 42)) [0  S1 A8])

        (mem:QI (post_inc:SI (reg:SI 41)) [0  S1 A8])) 

     (expr_list:REG_INC (reg:SI 42)

        (expr_list:REG_INC (reg:SI 41)

            (nil))))

.

 

Regards

 

Stefan

 

Re: setmemsi, movmemsi and post_inc

[Jeff Law]

On 3/25/2021 8:21 AM, Stefan Franke wrote:
> Hi there,
>
>   
>
> I consider implementing movmemsi/setmemsi for some arch using post_inc. Is
> there a "best practice" for using auto increments in such early stages to
> avoid hickups in cse, gcse, cprop etc.p.p.?

IIRC best practice is not to expose auto-inc until the auto-inc pass as 
earlier passes don't know how to deal with them.  See "Incdec" in the 
developer manual.


I'm also not aware of a target where an autoinc happens in contexts 
other than in a MEM.  So you may run into problems with things that look 
like a simple reg->reg move -- insns 8 and 9 in your example.


jeff

AW: AW: setmemsi, movmemsi and post_inc

[Stefan Franke]

richt-----
> Von: Jeff Law <jeffreyalaw@gmail.com>
> Gesendet: Donnerstag, 25. März 2021 16:04
> On 3/25/2021 8:50 AM, Stefan Franke wrote:
> >> On 3/25/2021 8:21 AM, Stefan Franke wrote:
> >>> Hi there,
> >>>
> >>> I consider implementing movmemsi/setmemsi for some arch using
> >>> post_inc. Is there a "best practice" for using auto increments in
> >>> such early stages to avoid hickups in cse, gcse, cprop etc.p.p.?
> >> IIRC best practice is not to expose auto-inc until the auto-inc pass
> >> as earlier passes don't know how to deal with them.  See "Incdec" in
> >> the developer manual.
> >>
> >>
> >> I'm also not aware of a target where an autoinc happens in contexts
> >> other than in a MEM.  So you may run into problems with things that
> >> look like a simple reg->reg move -- insns 8 and 9 in your example.
> >>
> >>
> >> jeff
> > You looked closely! I added the reg note to the register move to enhance
> some passes to handle this correctly.
> > e.g. in cse.c
> >
> >    if (find_reg_note (insn, REG_INC, dest))
> >      continue;
> >
> >   But these modifications aren't the standard way, thus I asked 😊
> >
> > => The routines should emit mems with offset and pray that auto-inc will
> pick it up?
> 
> Yes.
> 
> 
> > (Btw: auto-inc-dec does not work well for unrolled loops, so I'm
> > tempted to force the auto-inc stuff...)
> 
> That's likely going to lead to a variety of problems.   The (documented)
> restriction around auto-inc not being used early in the pipeline has been
> around at least 30 years and passes have been written with that
> assumption.  Fixing all of them may be a substantial effort.
> 
> It's probably a better use of your time to get a deep understanding of why
> you're not getting the code you want in the presence of unrolling -- there
> may be things we can do in the unroller, auto-inc or passes in the middle to
> improve that.
> 
> Jeff

At least it seems possible to use auto_inc inside an emitted loop, since that yields a separate bb...

Loop unrolling and auto_inc (post_inc) does not play well since there are two issues. consider these mem refs, with mode size 4:
  a[0] = ...
  a[4] = ...
  a[8] = ...
  a[12] = ...

loop unrolling does something like
  b = a
  b[0] = ...
  b[4] = ...
  b[8] = ...
  b[12] = ...
  b = b + 16
  b[0] = ...
  ...

1. cse folds the memory refs from b to a, and but not the [4]
  b = a
  a[0] = ...
  b[4] = ...
  a[8] = ...
  a[12] = ...
...
And you end up with one post_inc in the beginning and the rest without.

My workaround here is to consider the DF_REG_USE_COUNT and DF_REG_DEF_COUNT to decide if b[4] should be folded too
     if (DF_REG_USE_COUNT(REGNO(folded_arg0)) <= 2 || DF_REG_DEF_COUNT(REGNO(folded_arg0)) > 1)
    break;

2. auto-inc-dec does not yet handle the form of mem refs with offset and a matching add after these.
Since the above pattern as insns looks like
  b = a + x
  *b = ...
  a = a + x + 4
and is detected as PRE_ADD, I convert it into
  a = a + x
  *a = ...
  a = a + 4
which is now a POST_INC, update the variables and auto-inc-dec generates post increments up to the top, where x gets zero.

=> there is room for improvements^^

Stefan

Re: AW: AW: setmemsi, movmemsi and post_inc

[Jeff Law]

On 3/25/2021 2:16 PM, Stefan Franke wrote:
>
> At least it seems possible to use auto_inc inside an emitted loop, since that yields a separate bb...

I wouldn't rely on that.


>
> Loop unrolling and auto_inc (post_inc) does not play well since there are two issues. consider these mem refs, with mode size 4:
>    a[0] = ...
>    a[4] = ...
>    a[8] = ...
>    a[12] = ...
>
> loop unrolling does something like
>    b = a
>    b[0] = ...
>    b[4] = ...
>    b[8] = ...
>    b[12] = ...
>    b = b + 16
>    b[0] = ...
>    ...
>
> 1. cse folds the memory refs from b to a, and but not the [4]
>    b = a
>    a[0] = ...
>    b[4] = ...
>    a[8] = ...
>    a[12] = ...
> ...
> And you end up with one post_inc in the beginning and the rest without.

So that argues that you want to fixup CSE and possibly your ports 
costing model.


>
> My workaround here is to consider the DF_REG_USE_COUNT and DF_REG_DEF_COUNT to decide if b[4] should be folded too
>       if (DF_REG_USE_COUNT(REGNO(folded_arg0)) <= 2 || DF_REG_DEF_COUNT(REGNO(folded_arg0)) > 1)
>      break;
>
> 2. auto-inc-dec does not yet handle the form of mem refs with offset and a matching add after these.
> Since the above pattern as insns looks like
>    b = a + x
>    *b = ...
>    a = a + x + 4
> and is detected as PRE_ADD, I convert it into
>    a = a + x
>    *a = ...
>    a = a + 4
> which is now a POST_INC, update the variables and auto-inc-dec generates post increments up to the top, where x gets zero.
>
> => there is room for improvements^^

Yup, and that's where I'd focus my efforts.  Emitting auto-increment 
addressing modes at a point where the compiler isn't expecting them is 
just asking for trouble.  It may work today, it may work for a decade, 
but experience shows that if you break the rules it will break one day.


jeff

AW: AW: AW: setmemsi, movmemsi and post_inc

[Stefan Franke]

> Von: Gcc-help <gcc-help-bounces@gcc.gnu.org> Im Auftrag von Jeff Law via
> On 3/25/2021 2:16 PM, Stefan Franke wrote:
> >
> > At least it seems possible to use auto_inc inside an emitted loop, since that
> yields a separate bb...
> 
> I wouldn't rely on that.
> 
What about using (parallel ) as envelope for the loop body?
Or even create a pseudo insn which yield the loop body as asm template?

STefan

Re: AW: AW: AW: setmemsi, movmemsi and post_inc

[Jeff Law]

On 3/26/2021 12:47 AM, Stefan Franke wrote:
>> Von: Gcc-help <gcc-help-bounces@gcc.gnu.org> Im Auftrag von Jeff Law via
>> On 3/25/2021 2:16 PM, Stefan Franke wrote:
>>> At least it seems possible to use auto_inc inside an emitted loop, since that
>> yields a separate bb...
>>
>> I wouldn't rely on that.
>>
> What about using (parallel ) as envelope for the loop body?

If you mean a parallel where you've got the memory reference as well as 
an update of the base register as distinct sets, yes that will work as 
the RTL pattern is fully describing the operation. This is documented in 
the manual:

An instruction that can be represented with an embedded side effect
could also be represented using @code{parallel} containing an additional
@code{set} to describe how the address register is altered.  This is not
done because machines that allow these operations at all typically
allow them wherever a memory address is called for.  Describing them as
additional parallel stores would require doubling the number of entries
in the machine description.

> Or even create a pseudo insn which yield the loop body as asm template?

I wouldn't recommend this.



Jeff

AW: AW: AW: AW: setmemsi, movmemsi and post_inc

[Stefan Franke]

> Von: Jeff Law <jeffreyalaw@gmail.com>
> Gesendet: Freitag, 26. März 2021 15:08
>
> On 3/26/2021 12:47 AM, Stefan Franke wrote:
> >> Von: Gcc-help <gcc-help-bounces@gcc.gnu.org> Im Auftrag von Jeff Law
> >> via On 3/25/2021 2:16 PM, Stefan Franke wrote:
> >>> At least it seems possible to use auto_inc inside an emitted loop,
> >>> since that
> >> yields a separate bb...
> >>
> >> I wouldn't rely on that.
> >>
> > What about using (parallel ) as envelope for the loop body?
> 
> If you mean a parallel where you've got the memory reference as well as an
> update of the base register as distinct sets, yes that will work as the RTL
> pattern is fully describing the operation. This is documented in the manual:
> 
> An instruction that can be represented with an embedded side effect could
> also be represented using @code{parallel} containing an additional
> @code{set} to describe how the address register is altered.  This is not done
> because machines that allow these operations at all typically allow them
> wherever a memory address is called for.  Describing them as additional
> parallel stores would require doubling the number of entries in the machine
> description.
> 
> > Or even create a pseudo insn which yield the loop body as asm template?
> 
> I wouldn't recommend this.
> 

Thank you for your insights.

Since using a base register with constant offsets seems to yield the best optimizations I added another conversion to auto-inc-dec which converts matching constant offsets into an post inc ladder:
from: 
    9: [r31:SI+0x4]=[r32:SI+0x4]
   10: [r31:SI+0x8]=[r32:SI+0x8]
   11: [r31:SI+0xc]=[r32:SI+0xc]
intermediate:
   19: r34:SI=r32:SI+0x4
    9: [r31:SI+0x4]=[r34:SI]
   10: [r31:SI+0x8]=[r34:SI+0x4]
   11: [r31:SI+0xc]=[r34:SI+0x8]
      REG_DEAD r34:SI
converted:
   19: r34:SI=r32:SI+0x4
    9: [r31:SI+0x4]=[r34:SI]
   20: r34:SI=r34:SI+0x4
   10: [r31:SI+0x8]=[r34:SI]
   21: r34:SI=r34:SI+0x4
   11: [r31:SI+0xc]=[r34:SI]
      REG_DEAD r34:SI

The is applied to the destination too => nice post increments.


Stefan

Re: setmemsi, movmemsi and post_inc

[Segher Boessenkool]

Hi!

On Thu, Mar 25, 2021 at 03:21:29PM +0100, Stefan Franke wrote:
> (insn 8 7 9 2 (set (reg:SI 41)
>         (reg/f:SI 40)) 
>      (expr_list:REG_INC (reg:SI 41)
>         (nil)))

REG_INC notes are only valid on insns containing a post_inc expression.
This usually is inside a mem, but it doesn't have to be.  So this would
be

  (set (reg:SI 41)
       (post_inc:SI (reg:SI 40)))


Segher

Re: setmemsi, movmemsi and post_inc

[Segher Boessenkool]

On Thu, Mar 25, 2021 at 08:44:07AM -0600, Jeff Law via Gcc-help wrote:
> I'm also not aware of a target where an autoinc happens in contexts 
> other than in a MEM.

See arm's "lazy_load_multiple_insn" for example.  Well it looks like
this is the only example in the current compiler :-)


Segher

Re: setmemsi, movmemsi and post_inc

[Segher Boessenkool]

On Fri, Mar 26, 2021 at 05:15:30PM -0500, Segher Boessenkool wrote:
> On Thu, Mar 25, 2021 at 08:44:07AM -0600, Jeff Law via Gcc-help wrote:
> > I'm also not aware of a target where an autoinc happens in contexts 
> > other than in a MEM.
> 
> See arm's "lazy_load_multiple_insn" for example.  Well it looks like
> this is the only example in the current compiler :-)

And I'm not sure how it is supposed to work even?  Without an enclosing
mem, it isn't clear to increment by how much?

In that arm example there is another parallel arm that *does* have a
mem with that same operand as address, but that looks to tricky to
work reliably.

rtl.def says

/* These unary operations are used to represent incrementation
   and decrementation as they occur in memory addresses.
   The amount of increment or decrement are not represented
   because they can be understood from the machine-mode of the
   containing MEM.  These operations exist in only two cases:
   1. pushes onto the stack.
   2. created automatically by the auto-inc-dec pass.  */
DEF_RTL_EXPR(PRE_DEC, "pre_dec", "e", RTX_AUTOINC)
DEF_RTL_EXPR(PRE_INC, "pre_inc", "e", RTX_AUTOINC)
DEF_RTL_EXPR(POST_DEC, "post_dec", "e", RTX_AUTOINC)
DEF_RTL_EXPR(POST_INC, "post_inc", "e", RTX_AUTOINC)


Segher

AW: setmemsi, movmemsi and post_inc

[Stefan Franke]

> Von: Segher Boessenkool <segher@kernel.crashing.org>
> Gesendet: Freitag, 26. März 2021 23:10
> 
> Hi!
> 
> On Thu, Mar 25, 2021 at 03:21:29PM +0100, Stefan Franke wrote:
> > (insn 8 7 9 2 (set (reg:SI 41)
> >         (reg/f:SI 40))
> >      (expr_list:REG_INC (reg:SI 41)
> >         (nil)))
> 
> REG_INC notes are only valid on insns containing a post_inc expression.
> This usually is inside a mem, but it doesn't have to be.  So this would be
> 
>   (set (reg:SI 41)
>        (post_inc:SI (reg:SI 40)))
> 

Well I'am (ab)using it as a marker: this register is used elsewhere in
post_inc insns. This avoids by simply testing the presence of this note the
folding/combing/etc.pp in cse, gcse and cprop.

Would it be better to add a new note flavour? REG_USED_IN_INC?

Stefan

AW: AW: setmemsi, movmemsi and post_inc

[Stefan Franke]

> Von: Jeff Law <jeffreyalaw@gmail.com>
> Gesendet: Donnerstag, 25. März 2021 16:04 On 3/25/2021 8:50 AM, Stefan
>
> That's likely going to lead to a variety of problems.   The (documented)
> restriction around auto-inc not being used early in the pipeline has
> been around at least 30 years and passes have been written with that
> assumption.  Fixing all of them may be a substantial effort.

My way to use auto-inc starting from expand seems to work. The torture tests are passed and also the compiled programs are still working. I'm waiting for feedback from the users of my special treated version... 

So I wan't to share my recipe - whilst I'm sure that you won't pick up that idea...

If an auto-inc insn gets emitted a temp register is mandatory, the REG_INC note must be set on the auto-insns and on the temp register. The REG-INC for the temp register is used as a marker to avoid aliasing or reuse since the value of the temp register changes. This is done via some patches, which do not affect the normal behavior.

  /* tmp reg for auto inc. */
  src = gen_reg_rtx (SImode);
  rtx_insn *sinsn = emit_move_insn (src, regsrc);
  add_reg_note (sinsn, REG_INC, src);

  /* create post_inc. */
  src = gen_rtx_MEM (SImode, gen_rtx_POST_INC(SImode, regsrc));

  /* emit an auto inc. */
  rtx_insn *insn = emit_move_insn (dst, src);
  add_reg_note (insn, REG_INC, regsrc);

To get it work you need changes in these sources:

alias.c: init_alias_analysis : 3463
		  if (set != 0
		      && REG_P (SET_DEST (set))
		      && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
		      /* SBF: ignore regs marked as REG_INC. */
		      && !find_reg_note(insn, REG_INC, SET_DEST (set)))

cprop.c: do_local_cprop : 1183
  if (REG_P (x)
      && (cprop_reg_p (x)
          || (GET_CODE (PATTERN (insn)) != USE
	      && asm_noperands (PATTERN (insn)) < 0))
      /* SBF: ignore regs marked as REG_INC. */
      && !find_reg_note (insn, REG_INC, x))

cse.c: cse_insn : 5513
	  /* SBF: ignore regs marked as REG_INC. */
	  if (!find_reg_note(insn, REG_INC, dest))
	    set_unique_reg_note (insn, REG_EQUAL, src_const);

		:5976
	if (REG_P (dest) || GET_CODE (dest) == SUBREG)
	  {
	    /* SBF: ignore regs marked as REG_INC. */
	    if (find_reg_note (insn, REG_INC, dest))
	      continue;
	    /* Registers must also be inserted into chains for quantities.  */
	    if (insert_regs (dest, sets[i].src_elt, 1))
	      {
		/* If `insert_regs' changes something, the hash code must be
		 recalculated.  */
		rehash_using_reg (dest);
		sets[i].dest_hash = HASH(dest, GET_MODE (dest));
	      }
	  }

gcse.c: pre_insert_copy_insn :2295
  /* SBF: move REG_INC note. */
  if (NEXT_INSN(insn) == new_insn && find_reg_note(insn, REG_INC, old_reg))
    {
      remove_note(insn, find_reg_note(insn, REG_INC, old_reg));
      add_reg_note (new_insn, REG_INC, old_reg);
    }

  gcse_create_count++;


web.c: replace_ref : 292
  rtx_insn * insn = DF_REF_INSN (ref);

  /* SBF: ignore regs marked as REG_INC. */
  if (oldreg == reg || find_reg_note(insn, REG_INC, oldreg))
    return;
  if (dump_file)
    fprintf (dump_file, "Updating insn %i (%i->%i)\n",
	     uid, REGNO (oldreg), REGNO (reg));
  *loc = reg;
  df_insn_rescan (insn);


> It's probably a better use of your time to get a deep understanding of
> why you're not getting the code you want in the presence of unrolling
> -- there may be things we can do in the unroller, auto-inc or passes
> in the middle to improve that.

Despite the REG_INC success: I added two functions to auto-inc-dev.c

1.
static bool
convert_to_post_inc (rtx_insn *last_insn, rtx *inc_reg, int size)

used in try_merge to convert an unsuccessful PRE_ADD into a POST_INC.

2.
static void
convert_mem_offset_to_add (rtx_insn *insn, basic_block bb, bool use_src)

This gets invoked early in the loop of merge_in_block to convert mems with offset and a trailing matching add to the address register into an POST_INC ladder.

Since it adds new registers (max_regno increases) some further changes were needed to adjust the structures.

If someone is interested...

Anyway - thank you for listening 😊


Stefan