[Bug target/112445] New: [14 Regression] ICE: in lra_split_hard_reg_for, at lra-assigns.cc:1861 unable to find a register to spill: {*umulditi3_1} with -O -march=cascadelake -fwrapv

[Bug target/112445] New: [14 Regression] ICE: in lra_split_hard_reg_for, at lra-assigns.cc:1861 unable to find a register to spill: {*umulditi3_1} with -O -march=cascadelake -fwrapv

[zsojka at seznam dot cz]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112445

            Bug ID: 112445
           Summary: [14 Regression] ICE: in lra_split_hard_reg_for, at
                    lra-assigns.cc:1861 unable to find a register to
                    spill: {*umulditi3_1} with -O -march=cascadelake
                    -fwrapv
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Keywords: ice-on-valid-code
          Severity: normal
          Priority: P3
         Component: target
          Assignee: unassigned at gcc dot gnu.org
          Reporter: zsojka at seznam dot cz
  Target Milestone: ---
              Host: x86_64-pc-linux-gnu
            Target: x86_64-pc-linux-gnu

Created attachment 56536
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=56536&action=edit
reduced testcase

Compiler output:
$ x86_64-pc-linux-gnu-gcc -O -march=cascadelake -fwrapv testcase.c 
testcase.c: In function 'foo':
testcase.c:19:1: error: unable to find a register to spill
   19 | }
      | ^
testcase.c:19:1: error: this is the insn:
(insn 37 142 199 2 (parallel [
            (set (reg:TI 302 [orig:150 _73 ] [150])
                (mult:TI (zero_extend:TI (reg:DI 184 [ cu8_0 ]))
                    (zero_extend:TI (reg:DI 181 [ foo0_s64_0 ]))))
            (clobber (reg:CC 17 flags))
        ]) "testcase.c":10:9 510 {*umulditi3_1}
     (expr_list:REG_DEAD (reg:DI 184 [ cu8_0 ])
        (expr_list:REG_UNUSED (reg:CC 17 flags)
            (nil))))
during RTL pass: reload
testcase.c:19:1: internal compiler error: in lra_split_hard_reg_for, at
lra-assigns.cc:1861
0x7f3bef _fatal_insn(char const*, rtx_def const*, char const*, int, char
const*)
        /repo/gcc-trunk/gcc/rtl-error.cc:108
0x12b9d6d lra_split_hard_reg_for()
        /repo/gcc-trunk/gcc/lra-assigns.cc:1861
0x12b3268 lra(_IO_FILE*)
        /repo/gcc-trunk/gcc/lra.cc:2495
0x1261999 do_reload
        /repo/gcc-trunk/gcc/ira.cc:5973
0x1261999 execute
        /repo/gcc-trunk/gcc/ira.cc:6161
Please submit a full bug report, with preprocessed source (by using
-freport-bug).
Please include the complete backtrace with any bug report.
See <https://gcc.gnu.org/bugs/> for instructions.

$ x86_64-pc-linux-gnu-gcc -v
Using built-in specs.
COLLECT_GCC=/repo/gcc-trunk/binary-latest-amd64/bin/x86_64-pc-linux-gnu-gcc
COLLECT_LTO_WRAPPER=/repo/gcc-trunk/binary-trunk-r14-5250-20231108213319-g8cf7b936d44-checking-yes-rtl-df-extra-nobootstrap-amd64/bin/../libexec/gcc/x86_64-pc-linux-gnu/14.0.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: /repo/gcc-trunk//configure --enable-languages=c,c++
--enable-valgrind-annotations --disable-nls --enable-checking=yes,rtl,df,extra
--disable-bootstrap --with-cloog --with-ppl --with-isl
--build=x86_64-pc-linux-gnu --host=x86_64-pc-linux-gnu
--target=x86_64-pc-linux-gnu --with-ld=/usr/bin/x86_64-pc-linux-gnu-ld
--with-as=/usr/bin/x86_64-pc-linux-gnu-as --disable-libstdcxx-pch
--prefix=/repo/gcc-trunk//binary-trunk-r14-5250-20231108213319-g8cf7b936d44-checking-yes-rtl-df-extra-nobootstrap-amd64
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 14.0.0 20231108 (experimental) (GCC)

[Bug target/112445] [14 Regression] ICE: in lra_split_hard_reg_for, at lra-assigns.cc:1861 unable to find a register to spill: {*umulditi3_1} with -O -march=cascadelake -fwrapv

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112445

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |14.0

[Bug target/112445] [14 Regression] ICE: in lra_split_hard_reg_for, at lra-assigns.cc:1861 unable to find a register to spill: {*umulditi3_1} with -O -march=cascadelake -fwrapv

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112445

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-11-09
           Keywords|                            |needs-bisection

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed.

The code is very sensative to changes even.

[Bug target/112445] [14 Regression] ICE: in lra_split_hard_reg_for, at lra-assigns.cc:1861 unable to find a register to spill: {*umulditi3_1} with -O -march=cascadelake -fwrapv

[zsojka at seznam dot cz]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112445

--- Comment #2 from Zdenek Sojka <zsojka at seznam dot cz> ---
Created attachment 56545
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=56545&action=edit
testcase failing just at -O1

$ x86_64-pc-linux-gnu-gcc -O testcase2.c
testcase2.c: In function 'foo':
testcase2.c:19:1: error: unable to find a register to spill
   19 | }
      | ^
testcase2.c:19:1: error: this is the insn:
(insn 36 155 216 2 (parallel [
            (set (reg:TI 280 [orig:142 _66 ] [142])
                (mult:TI (zero_extend:TI (reg:DI 171 [ cu8_0 ]))
                    (zero_extend:TI (subreg:DI (reg:TI 104 [ _10 ]) 0))))
            (clobber (reg:CC 17 flags))
        ]) "testcase2.c":12:9 513 {*umulditi3_1}
     (expr_list:REG_DEAD (reg:DI 171 [ cu8_0 ])
        (expr_list:REG_UNUSED (reg:CC 17 flags)
            (nil))))
during RTL pass: reload
testcase2.c:19:1: internal compiler error: in lra_split_hard_reg_for, at
lra-assigns.cc:1861
0x7f4bef _fatal_insn(char const*, rtx_def const*, char const*, int, char
const*)
        /repo/gcc-trunk/gcc/rtl-error.cc:108
0x12bd93d lra_split_hard_reg_for()
        /repo/gcc-trunk/gcc/lra-assigns.cc:1861
0x12b6e38 lra(_IO_FILE*)
        /repo/gcc-trunk/gcc/lra.cc:2495
0x1265569 do_reload
        /repo/gcc-trunk/gcc/ira.cc:5973
0x1265569 execute
        /repo/gcc-trunk/gcc/ira.cc:6161
Please submit a full bug report, with preprocessed source (by using
-freport-bug).
Please include the complete backtrace with any bug report.
See <https://gcc.gnu.org/bugs/> for instructions.

[Bug target/112445] [14 Regression] ICE: in lra_split_hard_reg_for, at lra-assigns.cc:1861 unable to find a register to spill: {*umulditi3_1} with -O -march=cascadelake -fwrapv since r14-4968-g89e5d902fc55ad

[sjames at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112445

Sam James <sjames at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|needs-bisection             |
                 CC|                            |roger at nextmovesoftware dot com,
                   |                            |sjames at gcc dot gnu.org
            Summary|[14 Regression] ICE: in     |[14 Regression] ICE: in
                   |lra_split_hard_reg_for, at  |lra_split_hard_reg_for, at
                   |lra-assigns.cc:1861 unable  |lra-assigns.cc:1861 unable
                   |to find a register to       |to find a register to
                   |spill: {*umulditi3_1} with  |spill: {*umulditi3_1} with
                   |-O -march=cascadelake       |-O -march=cascadelake
                   |-fwrapv                     |-fwrapv since
                   |                            |r14-4968-g89e5d902fc55ad

--- Comment #3 from Sam James <sjames at gcc dot gnu.org> ---
Bisected to r14-4968-g89e5d902fc55ad.

[Bug target/112445] [14 Regression] ICE: in lra_split_hard_reg_for, at lra-assigns.cc:1861 unable to find a register to spill: {*umulditi3_1} with -O -march=cascadelake -fwrapv since r14-4968-g89e5d902fc55ad

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112445

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org,
                   |                            |segher at gcc dot gnu.org,
                   |                            |uros at gcc dot gnu.org,
                   |                            |vmakarov at gcc dot gnu.org

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I think this goes wrong during combine.
Before combine, we have:
(insn 8 7 10 2 (set (subreg:HI (reg:QI 152) 0)
        (zero_extract:HI (reg:HI 1 dx [ cu8_0 ])
            (const_int 8 [0x8])
            (const_int 8 [0x8]))) "pr112445.c":11:1 114 {*extzvhi}
     (expr_list:REG_DEAD (reg:HI 1 dx [ cu8_0 ])
        (nil)))
...
tons of insns including
(insn 36 34 37 2 (parallel [
            (set (reg:TI 142 [ _66 ])
                (mult:TI (zero_extend:TI (reg:DI 171 [ cu8_0 ]))
                    (zero_extend:TI (subreg:DI (reg:TI 104 [ _10 ]) 0))))
            (clobber (reg:CC 17 flags))
        ]) "pr112445.c":12:9 522 {*umulditi3_1}
     (expr_list:REG_DEAD (reg:DI 171 [ cu8_0 ])
        (expr_list:REG_UNUSED (reg:CC 17 flags)
            (nil))))
...
(insn 41 38 44 2 (set (reg:DI 177 [ cu8_0+1 ])
        (zero_extend:DI (reg:QI 152))) "pr112445.c":12:9 170 {zero_extendqidi2}
     (expr_list:REG_DEAD (reg:QI 152)
        (nil)))
and combine merges insn 41 with insn 8 across 20 other insns:
Trying 8 -> 41:
    8: r152:QI#0=zero_extract(dx:HI,0x8,0x8)
      REG_DEAD dx:HI
   41: r177:DI=zero_extend(r152:QI)
      REG_DEAD r152:QI
Successfully matched this instruction:
(set (reg:DI 177 [ cu8_0+1 ])
    (zero_extract:DI (reg:DI 1 dx [ cu8_0 ])
        (const_int 8 [0x8])
        (const_int 8 [0x8])))
into:
(insn 41 38 44 2 (set (reg:DI 177 [ cu8_0+1 ])
        (zero_extract:DI (reg:DI 1 dx [ cu8_0 ])
            (const_int 8 [0x8])
            (const_int 8 [0x8]))) "pr112445.c":12:9 116 {*extzvdi}
     (expr_list:REG_DEAD (reg:HI 1 dx [ cu8_0 ])
        (nil)))
and by that it significantly extends the live range of rdx register, which is a
single class register.  Now insn 36 has constraints =r,A on output and %d,a on
first input and rm,rm on second input, meaning that it either has %rdx:%rax
destination (second alternative), or %rdx as one of the inputs, so when %rdx is
live across it, it can't be reloaded.
On that insn, the commit changed
-           (match_operand:DWIH 1 "nonimmediate_operand" "%d,0"))
+           (match_operand:DWIH 1 "register_operand" "%d,a"))
on the constraints, is that something that LRA used to handle fine (how?)?
Actually, in the r14-4967 reload dump I see:
(insn 223 193 202 2 (set (mem/c:DI (plus:DI (reg/f:DI 7 sp)
                (const_int 40 [0x28])) [3 %sfp+-40 S8 A64])
        (reg:DI 1 dx)) "pr112445.c":12:9 90 {*movdi_internal}
     (nil))
(insn 202 223 36 2 (set (reg:DI 0 ax [orig:142 _66 ] [142])
        (mem/c:DI (reg/f:DI 7 sp) [3 %sfp+-80 S8 A128])) "pr112445.c":12:9 90
{*movdi_internal}
     (nil))
(insn 36 202 203 2 (parallel [
            (set (reg:TI 0 ax [orig:142 _66 ] [142])
                (mult:TI (zero_extend:TI (reg:DI 0 ax [orig:142 _66 ] [142]))
                    (zero_extend:TI (reg:DI 37 r9 [orig:104 _10 ] [104]))))
            (clobber (reg:CC 17 flags))
        ]) "pr112445.c":12:9 522 {*umulditi3_1}
     (nil))
(insn 203 36 224 2 (set (mem/c:TI (reg/f:DI 7 sp) [3 %sfp+-80 S16 A128])
        (reg:TI 0 ax [orig:142 _66 ] [142])) "pr112445.c":12:9 89
{*movti_internal}
     (nil))
(insn 224 203 158 2 (set (reg:DI 1 dx)
        (mem/c:DI (plus:DI (reg/f:DI 7 sp)
                (const_int 40 [0x28])) [3 %sfp+-40 S8 A64])) "pr112445.c":12:9
90 {*movdi_internal}
     (nil))
so presumably LRA managed in that case to save and restore %rdx around it.
Is the problem the 0->a change when operand 0 is A?

[Bug target/112445] [14 Regression] ICE: in lra_split_hard_reg_for, at lra-assigns.cc:1861 unable to find a register to spill: {*umulditi3_1} with -O -march=cascadelake -fwrapv since r14-4968-g89e5d902fc55ad

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112445

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Just changing
--- i386.md.xx  2023-11-22 09:47:22.746637132 +0100
+++ i386.md     2023-11-22 20:38:07.216218697 +0100
@@ -9984,7 +9984,7 @@
   [(set (match_operand:<DWI> 0 "register_operand" "=r,A")
        (mult:<DWI>
          (zero_extend:<DWI>
-           (match_operand:DWIH 1 "register_operand" "%d,a"))
+           (match_operand:DWIH 1 "register_operand" "%d,0"))
          (zero_extend:<DWI>
            (match_operand:DWIH 2 "nonimmediate_operand" "rm,rm"))))
    (clobber (reg:CC FLAGS_REG))]
makes the testcase pass.  A question is how RA treats 0 constraint when the two
operands have different modes, if it is basically the same as a in that case,
meaning that the first input operand will never be in %rdx even when the A
constraint contains %rax and %rdx registers (but the double-word mode implies
it must be low part in %rax high part in $rdx).

[Bug target/112445] [14 Regression] ICE: in lra_split_hard_reg_for, at lra-assigns.cc:1861 unable to find a register to spill: {*umulditi3_1} with -O -march=cascadelake -fwrapv since r14-4968-g89e5d902fc55ad

[ubizjak at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112445

--- Comment #6 from Uroš Bizjak <ubizjak at gmail dot com> ---
(In reply to Jakub Jelinek from comment #4)
> I think this goes wrong during combine.
Combine does not / should not combine moves from hard registers just because of
extending register live range. It looks that this should also include
zero-extracts and other "pseudo-move" instructions.

The relevant patch and discussion is at [1].

[1] https://gcc.gnu.org/legacy-ml/gcc-patches/2018-10/msg01356.html

[Bug target/112445] [14 Regression] ICE: in lra_split_hard_reg_for, at lra-assigns.cc:1861 unable to find a register to spill: {*umulditi3_1} with -O -march=cascadelake -fwrapv since r14-4968-g89e5d902fc55ad

[vmakarov at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112445

--- Comment #7 from Vladimir Makarov <vmakarov at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #5)
> Just changing
> --- i386.md.xx	2023-11-22 09:47:22.746637132 +0100
> +++ i386.md	2023-11-22 20:38:07.216218697 +0100
> @@ -9984,7 +9984,7 @@
>    [(set (match_operand:<DWI> 0 "register_operand" "=r,A")
>  	(mult:<DWI>
>  	  (zero_extend:<DWI>
> -	    (match_operand:DWIH 1 "register_operand" "%d,a"))
> +	    (match_operand:DWIH 1 "register_operand" "%d,0"))
>  	  (zero_extend:<DWI>
>  	    (match_operand:DWIH 2 "nonimmediate_operand" "rm,rm"))))
>     (clobber (reg:CC FLAGS_REG))]
> makes the testcase pass.  A question is how RA treats 0 constraint when the
> two operands have different modes, if it is basically the same as a in that

LRA treats the same way as reload pass.  It is the same hard reg for LE target.
 For BE they are different if they require different number of hard regs.


> case, meaning that the first input operand will never be in %rdx even when
> the A constraint contains %rax and %rdx registers (but the double-word mode
> implies it must be low part in %rax high part in $rdx).

I looked at the testcase.  It seems it can be fixed by different placement of
splitting insns.  So I believe the bug will stay and can be latent if we fix
the PR by some other way.

I'll start to work on this bug on Monday as I will be absent the next two days.

[Bug target/112445] [14 Regression] ICE: in lra_split_hard_reg_for, at lra-assigns.cc:1861 unable to find a register to spill: {*umulditi3_1} with -O -march=cascadelake -fwrapv since r14-4968-g89e5d902fc55ad

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112445

--- Comment #8 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Vladimir Makarov <vmakarov@gcc.gnu.org>:

https://gcc.gnu.org/g:1390bf52c17a71834a1766c0222e4f8a74efb162

commit r14-6060-g1390bf52c17a71834a1766c0222e4f8a74efb162
Author: Vladimir N. Makarov <vmakarov@redhat.com>
Date:   Fri Dec 1 11:46:37 2023 -0500

    [PR112445][LRA]: Fix "unable to find a register to spill" error

    PR112445 is a very complicated bug occurring from interaction of
    constraint subpass, inheritance, and hard reg live range splitting.
    It is hard to debug this PR only from LRA standard logs.  Therefore I
    added dumping all func insns at the end of complicated sub-passes
    (constraint, inheritance, undoing inheritance, hard reg live range
    splitting, and rematerialization).  As such output can be quite big,
    it is switched only one level 7 of -fira-verbose value.  The reason
    for the bug is a skip of live-range splitting of hard reg (dx) on the
    1st live range splitting subpass.  Splitting is done for reload
    pseudos around an original insn and its reload insns but the subpass
    did not recognize such insn pattern because previous inheritance and
    undoing inheritance subpasses extended a bit reload pseudo live range.
    Although we undid inheritance in question, the result code was a bit
    different from a code before the corresponding inheritance pass.  The
    following fixes the bug by restoring exact code before the
    inheritance.

    gcc/ChangeLog:

            PR target/112445
            * lra.h (lra): Add one more arg.
            * lra-int.h (lra_verbose, lra_dump_insns): New externals.
            (lra_dump_insns_if_possible): Ditto.
            * lra.cc (lra_dump_insns): Dump all insns.
            (lra_dump_insns_if_possible):  Dump all insns for lra_verbose >= 7.
            (lra_verbose): New global.
            (lra): Add new arg.  Setup lra_verbose from its value.
            * lra-assigns.cc (lra_split_hard_reg_for): Dump insns if rtl
            was changed.
            * lra-remat.cc (lra_remat): Dump insns if rtl was changed.
            * lra-constraints.cc (lra_inheritance): Dump insns.
            (lra_constraints, lra_undo_inheritance): Dump insns if rtl
            was changed.
            (remove_inheritance_pseudos): Use restore reg if it is set up.
            * ira.cc: (lra): Pass internal_flag_ira_verbose.

    gcc/testsuite/ChangeLog:

            PR target/112445
            * gcc.target/i386/pr112445.c: New test.

[Bug target/112445] [14 Regression] ICE: in lra_split_hard_reg_for, at lra-assigns.cc:1861 unable to find a register to spill: {*umulditi3_1} with -O -march=cascadelake -fwrapv since r14-4968-g89e5d902fc55ad

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112445

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Thanks for the fix.