Wrong cost computation / conclusion ins insn combine?

[Georg-Johann Lay]

For some time now I am staring at the following test case and what
combine does with it:

typedef struct
{
    unsigned b0 : 1;
    unsigned b1 : 1;
    unsigned b2 : 1;
    unsigned b3 : 1;
    unsigned b4 : 1;
    unsigned b5 : 1;
    unsigned b6 : 1;
    unsigned b7 : 1;
} b_t;

Prior to combine, there is:

insn_cost 4 for    18: r52:QI = r24:QI
insn_cost 4 for     2: r47:QI = r52:QI
insn_cost 4 for     6: r48:QI = zero_extract(r47:QI,0x1,0)
insn_cost 4 for     7: r50:QI = 0x1
insn_cost 4 for     8: r49:QI = r48:QI ^ r50:QI
insn_cost 8 for     9: zero_extract(r47:QI,0x1,0) = r49:QI
insn_cost 4 for    15: r24:QI = r47:QI

So insn 6 extracts bit 0, insn 8 flips it, and insn 9 inserts
it as bit 0 again.

Combine then starts looking for combinations, and at some point
comes up with:


Trying 7 -> 9:
    7: r50:QI = ~r47:QI
    9: zero_extract(r47:QI,0x1,0) = r50:QI
Successfully matched this instruction:
(set (zero_extract:QI (reg/v:QI 47 [ a ])
                      (const_int 1 [0x1])
                      (const_int 0 [0]))
     (not:QI (reg/v:QI 47 [ a ])))
allowing combination of insns 7 and 9
original costs 4 + 8 = 12
replacement cost 12
deferring deletion of insn with uid = 7.
modifying insn i3     9: zero_extract(r47:QI,0x1,0)=~r47:QI
deferring rescan insn with uid = 9.

So the cost is 12 and this insn is accepted. But down the line,
combine cooks up this:

Trying 2, 9 -> 15:
    2: r47:QI = r52:QI
    9: zero_extract(r47:QI,0x1,0) = ~r47:QI
   15: r24:QI = r47:QI
...
Successfully matched this instruction:
(set (reg/i:QI 24 r24)
     (ior:QI (and:QI (reg:QI 52)
                     (const_int -2 [0xfffffffffffffffe]))
             (and:QI (reg/v:QI 47 [ a ])
                     (const_int 1 [0x1]))))
allowing combination of insns 2, 9 and 15
original costs 4 + 12 + 4 = 20
replacement costs 4 + 12 = 16
deferring deletion of insn with uid = 2.
modifying insn i2     9: r47:QI=~r52:QI
deferring rescan insn with uid = 9.
modifying insn i3    15: r24:QI=r52:QI&0xfffffffffffffffe|r47:QI&0x1
deferring rescan insn with uid = 15.

So this one has a cost of 16 which is more expensive than the first
combination. For example it still needs to flip the bit.

So why is combine choosing the expensive replacement over the cheap one?

Also it combines hard-registers in the 2nd case, but not in the
1st one.  So the costs get biased towards 2nd.

Can someone explain why combine takes the more expensive solution?

Target is avr, compiled with

$ avr-gcc-14 bits.c -dumpbase "" -S -Os -fdump-rtl-combine-details -dp

Johann