On 23/05/2023 19:41, Georg-Johann Lay wrote:
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?
Because it thinks it is cheaper. As your log shows, the calculation is:
original costs 4 + 12 + 4 = 20
replacement costs 4 + 12 = 16
But the real problem is that two of the instructions in this example are
simple register-register move operations which will likely be eliminated
during register allocation anyway (due to coalescing) and this throws
off the cost calculations.
I've seen this sort of thing before; perhaps the best solution would be
to override the cost of a simple (register to register) set and give it
a cost of zero. Then we'd see that this new sequence is worse than the
original.
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
R.
