* Wrong cost computation / conclusion ins insn combine?
@ 2023-05-23 18:41 Georg-Johann Lay
2023-05-24 12:31 ` Richard Earnshaw (lists)
0 siblings, 1 reply; 3+ messages in thread
From: Georg-Johann Lay @ 2023-05-23 18:41 UTC (permalink / raw)
To: gcc
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
^ permalink raw reply [flat|nested] 3+ messages in thread* Re: Wrong cost computation / conclusion ins insn combine?
2023-05-23 18:41 Wrong cost computation / conclusion ins insn combine? Georg-Johann Lay
@ 2023-05-24 12:31 ` Richard Earnshaw (lists)
2023-05-25 14:31 ` Georg-Johann Lay
0 siblings, 1 reply; 3+ messages in thread
From: Richard Earnshaw (lists) @ 2023-05-24 12:31 UTC (permalink / raw)
To: Georg-Johann Lay, gcc
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.
^ permalink raw reply [flat|nested] 3+ messages in thread* Re: Wrong cost computation / conclusion ins insn combine?
2023-05-24 12:31 ` Richard Earnshaw (lists)
@ 2023-05-25 14:31 ` Georg-Johann Lay
0 siblings, 0 replies; 3+ messages in thread
From: Georg-Johann Lay @ 2023-05-25 14:31 UTC (permalink / raw)
To: Richard Earnshaw (lists), gcc
Am 24.05.23 um 14:31 schrieb Richard Earnshaw (lists):
> 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.
Are you proposing to temporarily patch some cost hook during combine?
Combine can't work out allocation costs because it won't look at
constraints. And when function need special classes, register alloc
has to kick out the hard regs again and re-alloc them...
And when constraints like "+r" or "0" are present, combine won't do
a great job in computing (spared) register allocation costs.
For some insns there is even predicates that disallow combine to
drop in hard-regs like combine_pseudo_register_operand, but that'
a bit too much for this case.
Johann
>>
>> 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.
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2023-05-25 14:32 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-05-23 18:41 Wrong cost computation / conclusion ins insn combine? Georg-Johann Lay
2023-05-24 12:31 ` Richard Earnshaw (lists)
2023-05-25 14:31 ` Georg-Johann Lay
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).