RFC: Strategy for cc0 -> CCmode conversion for the AVR target.

[Björn Haase <bjoern dot m dot haase at web dot de>]

Hi,

During the last weeks I have experimented a bit with the AVR back-end. IMO 
there presently are two areas where it is worth to concentrating efforts on:
1.) cc0 -> CCmode transition
2.) splitting of HI- and SI-mode operations so that the RTL finally gets some 
similarity with the actually existing AVR instructions.

I'd like to discuss with you on how to address these issues best because I 
think it's better to have a good plan of what to do before starting 
programing.

Concerning 1.) Ian Lance Taylor has made a couple of suggestions on how to 
make the transition easier for the back-end maintainers. So it seems that 
there is already some activity around. For issue 2.) Richard Henderson has 
recently posted a patch that implements a "subreg-lowering" pass run directly 
after expand that gives the register allocator the freedom to handle and 
allocate the individual subreg expressions individually (could give some 
tremendous improvements for AVR, e.g. when dealing with expressions combining 
expressions with different modes).

IMO the two issues 1.) and 2.) are somewhat linked since, IMO it would be a 
good idea to implement a cc0->CCmode transition method that does not make it 
difficult to use Richard Henderson's patch later-on.


1.) Concerning the cc0 -> CCmode transition, IIUC, there are two main 
problems:

A) We must make sure the reload does not insert condition-code (CC) clobbering 
instructions in between a CC setter and a CC user (i.e. conditional 
branches).
B) We must find a way to teach GCC to re-use as frequently as possible the 
condition codes that are set by arithmetic and logic operations.

IMO, the easiest and most straight-forward solution of A) for the avr target 
would be to follow Ian's suggestion:
> Ian Lance Taylor wrote:
>
>> Is there a way that makes it possible that only reload uses the patterns 
>> that save and restore the condition code while everywhere else the usual 
>> patterns are generated? 
>> In case of the AVR target, most of the time reload will be  
>> able to use processor instructions that do not require the save/restore 
>> operations (it could freely access addresses up to a constant offset of 64 
>> from the stack pointer) and the costly operations would not show up very 
>> frequently (only for large offsets).  
>
>You could do it by writing your insn patterns as expanders which check
>reload_in_progress || reload_completed and under those circumstances
>emit insns which do not clobber the condition codes.
>
>Ian

I would expect that in the rare case that reload needs to access data beyond 
the 64-Byte boundary it could be tolerated to expand the memory access to a 
sequence of type 
"(set (temp_register) (SR))
 (memory_move_instruction_instruction_inserted_by_reload)
 (set (SR) (temp_register))"

One would have to confirm that, but I assume that the remaining passes after 
reload would be sufficiently smart to optimize away the two copy operations 
for saving and restoring the status register in case that they are not 
necessary.? E.g. I think that it is justified to assume that if above 
reload-generated memory access is followed by an instruction that clobbers 
the condition code, both of the status register operations that are embracing 
the memory move would be deleted. Possibly these two instructions would also 
be deleted, if the memory move instruction does not clobber the condition 
code.

Doing this, I think that one could resolve the most difficult issue A) of 
cc0->CCmode conversion without having to face what has been called "the 
combinatorical pattern explosion" in the mailing list archives.


Concerning issue B) Ian Lance Taylor suggests, IIUC, to implement a new pass 
after reload: After reload, it is known which alternative of the different 
instructions that possibly set CC has been chosen and one could find out 
whether some of the compare instructions could be deleted.
IMO, if this new pass is available by the time the cc0->CCmode transition is 
implemented for AVR, one should probably try to use it. 

Meanwhile I'd like to suggest an approach that tries to remove the unnecessary 
compare instructions already before reload. I.e. what I am thinking about is 
to try to use the (G)CSE passes to identify situations where arithmetic 
instructions calculate the same condition code that is again calculated 
later-on by compare or test instructions. Disadvantage would be that at this 
time one would not be able to know which alternative of an instruction will 
be chosen by reload. In my present opinion, however, this is an issue that is 
not a very big problem for AVR.

Also, IMO, one should probably try hard to identify the 
"single-bit-test-and-branch" patterns before reload.

The condition-code re-use issue is the point, where, IMO, the link to the 
subreg-lowering 2.) shows up. After, e.g., breaking down a HI mode "sub" 
operation into two QI mode "sub" and "sub-with-carry"s at expand, I consider 
it to be extremely difficult to make the mid-end smart enough to identify 
that a the end of the QI "sub-with-carry" the condition code is set according 
to the corresponding HImode substract operation. For DImode operations the 
mid-end would already need to take 8 (!) Instructions into account for 
finding out what the calculated condition code actually represents. This, 
also, will be a major difficulty when considering Ian's suggested optimizer 
pass after reload. 

IMO condition code re-use will also be an issue for the bigger targets (e.g. 
x86) when dealing with DI mode operations. My suggestion to address this 
issue is: Let's not try to make the mid-end hyper smart, but let's give the 
back-end designer a possibility to guide the mid-end by inserting helpful 
information in the RTL. In order to illustrate what I am thinking about, 
let's take above example with the minus:HI. I'd suggest to expand a subhi3 
operation with 3 register operands into a sequence like

; copying the input operands in individual QImode variables
(set (reg:QI 1) (subreg:QI (operands[1]) 0))
(set (reg:QI 2) (subreg:QI (operands[1]) 1))
(set (reg:QI 3) (subreg:QI (operands[2]) 0))
(set (reg:QI 4) (subreg:QI (operands[2]) 1))

; first add
(parallel [
 (set (reg:QI 5)(minus:QI (reg:QI 1) (reg:QI 3))
 (set (reg:CC_carry SR) (unspec:CC_carry [(reg:QI 1) (reg:QI 3)] 
carry_from_sub_code))])

; second add (with carry)
(parallel [
 (set (reg:QI 6) (minus:QI (minus:QI (reg:QI 2) (reg:QI 4)) (reg:CC_carry SR))
 (set (reg:CC_cc SR) (unspec:CC_cary [(reg:QI 1) (reg:QI 3) (reg:CC_carry SR)] 
carry_from_sub_with_carry_code))])

; write back the result into the output operands
(set (subreg:QI (operands[0]) 0) (reg:QI 5))
(set (subreg:QI (operands[0]) 1) (reg:QI 6))

; Additional "Marker" instructions to be used by GCSE
(parallel [
 (use (reg:CC_cc SR))
 (set (reg:CC_cc SR) (compare:HI (operands[1]) (operands[2]))
 (note "please delete the entire embracing parallel instruction before 
register life-time analysis by a new pass: It pretends to use operands 1 and 
2 while in fact this instruction does nothing except from giving hints to 
GCSE.")
])
(parallel [
 (use (reg:CC_cc SR))
 (set (reg:CC_cc SR) (compare:HI (operands[0]) (const_0))
 (note "please delete the entire embracing parallel instruction before 
register life-time analysis by a new pass: It pretends to use operand[0] 
while in fact this instruction does nothing except from giving hints to 
GCSE.")
])
(parallel [
 (use (operands[0]))
 (set (operands[0]) (minus:HI (operands[1]) (operands[2]))
 (note "please delete the entire embracing parallel instruction before 
register life-time analysis by a new pass: It pretends to use operands 1 and 
2 while in fact this instruction does nothing except from giving hints to 
GCSE.")
])

IIUC, (g)cse would be well adapted to deal with the probably unnecessary move 
instructions without any serious problems. It also will be able to identify 
if a later compare instruction calculates the same condition code as the 
minus operation had calculated. When having to choose between (a) teaching 
the mid-end to understand what add/substract-with-carry instructions actually 
do and (b) using a method like above to give hints to the present mid-end, 
(b) is my favorite approach. The simplified pass sequence before reload would 
then look similar to

- expand
- Richard's subreg lowering pass
- gcse and friends
- ( possible place 1 for marker instruction removal )
- combine
- ( possible place 2 for marker instruction removal )
- register allocation and reload

I know that the RTL generated by the back-end will get much more complex in 
comparison to the present case. But IMO this would be part of the price one 
always will have to pay when exposing the complexity of the subreg-lowering 
to the RTL optimizers.

In order to be able to identify the case of single-bit tests, it might be 
possible to implement a second to the optimizing procedure: By using a 
special optimizer switch it would be nice if one could change the pass flow 
before reload by 

- expand
- gcse and friends
- combine

- ( marker instruction removal )
- Richard's subreg lowering pass
- gcse and friends -re run
- combine -re-run

- register allocation and reload

This way, it would be possibly easier for the combine pass to find out whether 
a conditional branch in fact is a "branch on a single bit condition" since it 
would still find the information in the RTL which kind of original 
aggregate-mode expressions (i.e. HImode and larger) correspond to the zoo of 
atomic (i.e. QImode) instructions expand had generated.

I think that in case that above ideas work, it will be the AVR-back-end that 
would benefit most. But I also think that a similar approach could be very 
for all of the other targets that have only 16 bit instructions, e.g. like 
MSP430 and HC12. Possibly a similar procedure might also be helpful for the 
bigger targets when dealing with DI mode expressions!

So I am having hope that addressing this issue justifies changes in gcc's mid 
end.

Hoping to receive many comments and additional ideas from more competent 
people ... best regards

Björn