Hi Jeff,
Thanks a lot for providing all this information and testcase! I have
been able to reproduce the issue with it.
I have investigated the cause of the issue and it's not what you
mention, the uses of all intermediate calculations are properly taken
into account.
In this case it would be fine to alter the runtime value of insn 58
because its uses are also memory accesses that can have a folded
offset. The real issue is that the offset for these two (insn 60/61)
is not updated.
I think this can be seen by using -fdump-rtl-fold_mem_offsets-all
which also shows root memory instructions and when instructions are
marked for propagation. Here's the relevant dump (a bit long but
should help with this):
Starting analysis from root: (insn 2 95 3 2 (set (reg/v/f:SI 3 %d3
[orig:44 pD.1867 ] [44])
(mem/f/c:SI (plus:SI (reg/f:SI 15 %sp)
(const_int 60 [0x3c])) [1 pD.1867+0 S4 A32]))
"/home/mtsamis/temp/fmo-bug-2/a.c":23:1 55 {*movsi_m68k2}
(expr_list:REG_EQUIV (mem/f/c:SI (plus:SI (reg/f:SI 15 %sp)
(const_int 60 [0x3c])) [1 pD.1867+0 S4 A32])
(nil)))
Starting analysis from root: (insn 3 2 4 2 (set (reg/v/f:SI 2 %d2
[orig:45 rD.1868 ] [45])
(mem/f/c:SI (plus:SI (reg/f:SI 15 %sp)
(const_int 64 [0x40])) [1 rD.1868+0 S4 A32]))
"/home/mtsamis/temp/fmo-bug-2/a.c":23:1 55 {*movsi_m68k2}
(expr_list:REG_EQUIV (mem/f/c:SI (plus:SI (reg/f:SI 15 %sp)
(const_int 64 [0x40])) [1 rD.1868+0 S4 A32])
(nil)))
Starting analysis from root: (insn 14 12 16 2 (set (mem/f:SI (reg/f:SI
15 %sp) [1 S4 A16])
(reg/v/f:SI 2 %d2 [orig:45 rD.1868 ] [45]))
"/home/mtsamis/temp/fmo-bug-2/a.c":25:21 discrim 1 54 {*movsi_m68k}
(expr_list:REG_ARGS_SIZE (const_int 4 [0x4])
(nil)))
Starting analysis from root: (insn 42 41 43 3 (set (mem:SI (reg:SI 8
%a0 [61]) [0 MEM <charD.2[1:5]> [(voidD.37 *)_15]+0 S4 A8])
(const_int 1633837924 [0x61626364]))
"/home/mtsamis/temp/fmo-bug-2/a.c":29:4 discrim 1 55 {*movsi_m68k2}
(nil))
Starting analysis from root: (insn 43 42 45 3 (set (mem:QI (plus:SI
(reg:SI 8 %a0 [61])
(const_int 4 [0x4])) [0 MEM <charD.2[1:5]> [(voidD.37
*)_15]+4 S1 A8])
(const_int 101 [0x65]))
"/home/mtsamis/temp/fmo-bug-2/a.c":29:4 discrim 1 62 {*m68k.md:1130}
(expr_list:REG_DEAD (reg:SI 8 %a0 [61])
(nil)))
Instruction marked for propagation: (insn 41 39 42 3 (set (reg:SI 8 %a0 [61])
(plus:SI (reg/f:SI 12 %a4 [52])
(reg:SI 13 %a5 [orig:36 _14 ] [36])))
"/home/mtsamis/temp/fmo-bug-2/a.c":29:4 discrim 1 150
{*addsi3_internal}
(nil))
Starting analysis from root: (insn 60 59 61 3 (set (mem:HI (reg:SI 8
%a0 [73]) [0 MEM <charD.2[1:3]> [(voidD.37 *)_19]+0 S2 A8])
(const_int 26215 [0x6667]))
"/home/mtsamis/temp/fmo-bug-2/a.c":31:4 discrim 1 58 {*m68k.md:1084}
(nil))
Starting analysis from root: (insn 61 60 63 3 (set (mem:QI (plus:SI
(reg:SI 8 %a0 [73])
(const_int 2 [0x2])) [0 MEM <charD.2[1:3]> [(voidD.37
*)_19]+2 S1 A8])
(const_int 0 [0])) "/home/mtsamis/temp/fmo-bug-2/a.c":31:4
discrim 1 62 {*m68k.md:1130}
(expr_list:REG_DEAD (reg:SI 8 %a0 [73])
(nil)))
Instruction marked for propagation: (insn 59 58 60 3 (set (reg:SI 8 %a0 [73])
(plus:SI (reg/f:SI 12 %a4 [52])
(reg:SI 8 %a0 [72])))
"/home/mtsamis/temp/fmo-bug-2/a.c":31:4 discrim 1 150
{*addsi3_internal}
(nil))
Instruction marked for propagation: (insn 58 57 59 3 (set (reg:SI 8 %a0 [72])
(plus:SI (plus:SI (reg:SI 13 %a5 [orig:36 _14 ] [36])
(reg:SI 11 %a3 [49]))
(const_int 5 [0x5])))
"/home/mtsamis/temp/fmo-bug-2/a.c":31:4 407 {*lea}
(expr_list:REG_DEAD (reg:SI 13 %a5 [orig:36 _14 ] [36])
(expr_list:REG_DEAD (reg:SI 11 %a3 [49])
(nil))))
Instruction marked for propagation: (insn 39 38 41 3 (set (reg:SI 13
%a5 [orig:36 _14 ] [36])
(plus:SI (reg:SI 10 %a2 [47])
(const_int 1 [0x1])))
"/home/mtsamis/temp/fmo-bug-2/a.c":29:4 150 {*addsi3_internal}
(nil))
Memory offset changed from 0 to 1 for instruction:
(insn 42 41 43 3 (set (mem:SI (reg:SI 8 %a0 [61]) [0 MEM
<charD.2[1:5]> [(voidD.37 *)_15]+0 S4 A8])
(const_int 1633837924 [0x61626364]))
"/home/mtsamis/temp/fmo-bug-2/a.c":29:4 discrim 1 55 {*movsi_m68k2}
(nil))
deferring rescan insn with uid = 42.
Memory offset changed from 4 to 5 for instruction:
(insn 43 42 45 3 (set (mem:QI (plus:SI (reg:SI 8 %a0 [61])
(const_int 4 [0x4])) [0 MEM <charD.2[1:5]> [(voidD.37
*)_15]+4 S1 A8])
(const_int 101 [0x65]))
"/home/mtsamis/temp/fmo-bug-2/a.c":29:4 discrim 1 62 {*m68k.md:1130}
(expr_list:REG_DEAD (reg:SI 8 %a0 [61])
(nil)))
deferring rescan insn with uid = 43.
Instruction folded:(insn 39 38 41 3 (set (reg:SI 13 %a5 [orig:36 _14 ] [36])
(plus:SI (reg:SI 10 %a2 [47])
(const_int 1 [0x1])))
"/home/mtsamis/temp/fmo-bug-2/a.c":29:4 150 {*addsi3_internal}
(nil))
Here you can see that insn 39 is the last to be marked for propagation
and only after insn 58 is also marked i.e. it can propagate a constant
offset to its uses.
After that the question was why the constants were not actually
propagated in insn 60/61 and I added additional debug code to check
why. The culprit was this instruction:
(insn 58 57 59 3 (set (reg:SI 8 %a0 [72])
(plus:SI (plus:SI (reg:SI 13 %a5 [orig:36 _14 ] [36])
(reg:SI 11 %a3 [49]))
(const_int 5 [0x5])))
Here the recursive call to fold_offsets for the first argument will
propagate the folded offset 1 from the change to register %a5.
But when it's time to handle the second argument (const_int 5 [0x5])
this code is used:
if (REG_P (arg2))
offset += fold_offsets (def, arg2, analyze, foldable_insns);
else if (REG_P (arg1) && CONST_INT_P (arg2) && !analyze)
{
offset += INTVAL (arg2);
/* This is a R1 = R2 + C instruction, candidate for folding. */
bitmap_set_bit (foldable_insns, INSN_UID (def));
}
else
return 0;
return offset;
This instruction doesn't match any of these since the if with the
CONST_INT only accepts arg1 being a single REG (that could be
extended, but that's not the point now) and as a result we do `return
0;`
But return 0 at this point loses the offset 1 calculated from arg1
previously and which is stored in `offset`. And that's our bug :)
Changing that return 0 to return offset (i.e. return what we have up
to now) fixes this testcase with the insn being folded and all offsets
updating properly. But it got me thinking that this is a more general
issue that I need to address differently.
There are more `return 0;` cases in the code which say "We know how to
handle this rtx code, but don't know how to propagate", but returning
0 is not enough.
It's also not correct to propagate an offset from just one argument
and punt on the other because the argument we punt might contain
references to the other argument.
So the general solution that solves all the issues is: If we don't
fully understand how to handle an instruction and its arguments in
fold_offsets then we need to mark it in one of the bitsets (either set
in cannot_fold or don't set in can_fold), whereas currently a insn
that has transitively all uses as foldable is foldable.
I will prepare a newer version that should handle all these cases (and
with the proper changes the testcase will still fold insn 39).
Please let me know If you have any other feedback on this.
Thanks!
Manolis
On Wed, Aug 9, 2023 at 7:22 PM Jeff Law <jeffreya...@gmail.com> wrote:
>
>
>
> On 8/7/23 08:33, Manolis Tsamis wrote:
> > This is a new RTL pass that tries to optimize memory offset calculations
> > by moving them from add immediate instructions to the memory loads/stores.
> > For example it can transform this:
> >
> > addi t4,sp,16
> > add t2,a6,t4
> > shl t3,t2,1
> > ld a2,0(t3)
> > addi a2,1
> > sd a2,8(t2)
> >
> > into the following (one instruction less):
> >
> > add t2,a6,sp
> > shl t3,t2,1
> > ld a2,32(t3)
> > addi a2,1
> > sd a2,24(t2)
> >
> > Although there are places where this is done already, this pass is more
> > powerful and can handle the more difficult cases that are currently not
> > optimized. Also, it runs late enough and can optimize away unnecessary
> > stack pointer calculations.
> >
> > gcc/ChangeLog:
> >
> > * Makefile.in: Add fold-mem-offsets.o.
> > * passes.def: Schedule a new pass.
> > * tree-pass.h (make_pass_fold_mem_offsets): Declare.
> > * common.opt: New options.
> > * doc/invoke.texi: Document new option.
> > * fold-mem-offsets.cc: New file.
> >
> > gcc/testsuite/ChangeLog:
> >
> > * gcc.target/riscv/fold-mem-offsets-1.c: New test.
> > * gcc.target/riscv/fold-mem-offsets-2.c: New test.
> > * gcc.target/riscv/fold-mem-offsets-3.c: New test.
> We still have the m68k issue to deal with.
>
> We've got these key insns going into fold-mem-offsets:
>
> > (insn 39 38 41 3 (set (reg:SI 13 %a5 [orig:36 _14 ] [36])
> > (plus:SI (reg:SI 10 %a2 [47])
> > (const_int 1 [0x1]))) "j.c":19:3 157 {*addsi3_internal}
> > (nil))
> > (insn 41 39 42 3 (set (reg:SI 8 %a0 [61])
> > (plus:SI (reg/f:SI 12 %a4 [52])
> > (reg:SI 13 %a5 [orig:36 _14 ] [36]))) "j.c":19:3 discrim 1 157
> > {*addsi3_internal}
> > (nil))
> > (insn 42 41 43 3 (set (mem:SI (reg:SI 8 %a0 [61]) [0 MEM <char[1:5]> [(void
> > *)_15]+0 S4 A8])
> > (const_int 1633837924 [0x61626364])) "j.c":19:3 discrim 1 55
> > {*movsi_m68k2}
> > (nil))
> > (insn 43 42 45 3 (set (mem:QI (plus:SI (reg:SI 8 %a0 [61])
> > (const_int 4 [0x4])) [0 MEM <char[1:5]> [(void *)_15]+4 S1
> > A8])
> > (const_int 101 [0x65])) "j.c":19:3 discrim 1 62 {*m68k.md:1130}
> > (expr_list:REG_DEAD (reg:SI 8 %a0 [61])
> > (nil)))
>
> [ ... ]
> > (insn 58 57 59 3 (set (reg:SI 8 %a0 [72])
> > (plus:SI (plus:SI (reg:SI 13 %a5 [orig:36 _14 ] [36])
> > (reg:SI 11 %a3 [49]))
> > (const_int 5 [0x5]))) "j.c":24:3 421 {*lea}
> > (expr_list:REG_DEAD (reg:SI 13 %a5 [orig:36 _14 ] [36])
> > (expr_list:REG_DEAD (reg:SI 11 %a3 [49])
> > (nil))))
>
>
> f-m-o will propagate the (const_int 1) from insn 39 into insns 42 & 43
> and modifies insn 39 into a simple copy. Note carefully that turning
> insn 39 into a simple copy changes the value in a5.
>
> As a result insn 58 computes the wrong value and the test (strlenopt-2)
> fails on the m68k.
>
> In fold_offsets we have this code:
>
> > /* We only fold through instructions that are transitively used as
> > memory addresses and do not have other uses. Use the same logic
> > from offset calculation to visit instructions that can propagate
> > offsets and keep track of them in CAN_FOLD_INSNS. */
> > bool success;
> > struct df_link *uses = get_uses (def, dest, &success), *ref_link;
> >
> > if (!success)
> > return 0;
> >
> > for (ref_link = uses; ref_link; ref_link = ref_link->next)
> > {
> > rtx_insn* use = DF_REF_INSN (ref_link->ref);
> >
> > if (DEBUG_INSN_P (use))
> > continue;
> >
> > /* Punt if the use is anything more complicated than a set
> > (clobber, use, etc). */
> > if (!NONJUMP_INSN_P (use) || GET_CODE (PATTERN (use)) != SET)
> > return 0;
> >
> > /* This use affects instructions outside of CAN_FOLD_INSNS. */
> > if (!bitmap_bit_p (&can_fold_insns, INSN_UID (use)))
> > return 0;
> >
> > rtx use_set = PATTERN (use);
> >
> > /* Special case: A foldable memory store is not foldable if it
> > mentions DEST outside of the address calculation. */
> > if (use_set && MEM_P (SET_DEST (use_set))
> > && reg_mentioned_p (dest, SET_SRC (use_set)))
> > return 0;
> > }
>
> AFAICT that code is supposed to detect if there are uses outside of the
> set of insns that can be optimized. In our case DEF is a0 (the base of
> the memory references) and its def is insn 41. The assignment of a0 in
> insn 41 only reaches insns 42 and 43 which are marked in can_fold_insns.
>
> That's find and good, but insufficient for correctness. ISTM we must
> look at the uses of any insn where we change the result of the
> computation, not just the def of the base register in the memory reference.
>
> In this particular case we're going to modify insn 39, so we need to
> look at the uses of a5 (the value defined by insn 39). If we did that
> we'd see the use of a5 at insn 38 and insn 38 and reject the optimization.
>
>
>
> Testcase below. You should be able to see the incorrect transformation
> with a m68k-linux-gnu cross compiler with -O2.
>
>
>
> typedef unsigned int size_t;
> extern void abort (void);
> void *calloc (size_t, size_t);
> void *malloc (size_t);
> void free (void *);
> char *strdup (const char *);
> size_t strlen (const char *);
> size_t strnlen (const char *, size_t);
> void *memcpy (void *__restrict, const void *__restrict, size_t);
> void *memmove (void *, const void *, size_t);
> char *strcpy (char *__restrict, const char *__restrict);
> char *strcat (char *__restrict, const char *__restrict);
> char *strchr (const char *, int);
> int strcmp (const char *, const char *);
> int strncmp (const char *, const char *, size_t);
> void *memset (void *, int, size_t);
> int memcmp (const void *, const void *, size_t);
> int strcmp (const char *, const char *);
> int sprintf (char * __restrict, const char *__restrict, ...);
> int snprintf (char * __restrict, size_t, const char *__restrict, ...);
> __attribute__((noinline, noclone)) char *
> foo (char *p, char *r)
> {
> char buf[26];
> if (strlen (p) + strlen (r) + 9 > 26)
> return ((void *) 0);
> strcpy (buf, p);
> strcat (buf, "/");
> strcat (buf, "abcde");
> strcat (buf, r);
> strcat (buf, "fg");
> return strdup (buf);
> }
> int
> main ()
> {
> char *volatile p = "string1";
> char *volatile r = "string2";
> char *q = foo (p, r);
> if (q != ((void *) 0))
> {
> if (strcmp (q, "string1/abcdestring2fg"))
> abort ();
> free (q);
> }
> return 0;
> }
> ~
>
>
>
