Getting better understanding of constraints and reload

[Georg-Johann Lay <avr at gjlay dot de>]

Hi, I already submitted some patches for the avr backend and have still 
a bunch of ideas for implrovements.

However, I am still unsure about insn constraints and what they must 
look like to work in any situation, and I want to learn more about that 
subject before commnuity tars and feathers me because of some bugs in 
some corner cases...

I am aware that reload is one of the most complex parts of gcc. However, 
from the backend's perspective, it should be sufficient to understand 
reload in terms of the constraint-interface, so that there is no need to 
dive into reload's internals too deep, no matter what technique reload 
applies internally.

I read

http://gcc.gnu.org/onlinedocs/gccint/Multi_002dAlternative.html#Multi_002dAlternative

several times but not everything is clear to me. Because it's hard to 
tell what's unclear, let me start by describing my understanding of insn 
constraints and please correct me if I am wrong or fundamentally 
uncomplete.

As far as I understand, before reload an insn matches because all of its 
predicates match (and, of course, insn pattern and insn condition match).

If a predicate P is regarded as a set, all predicates span a cross 
product P1 x P2 x ... Pn of sets. Reloading then means to map this set 
into a smaller set that can be described as the union of the cross 
products of constraints.

To make it a little bit more explicit, let's consider an insn that has 
just three operands and two constraint alternatives, i.e. what reload 
has to map is

P = P1 x P2 x P3 -> (A1 x A2 x A3) + (B1 x B2 x B3) = K

Or in terms of sloppy rtl
 (match_operand "P1"  "A1,B1")
 (match_operand "P2"  "A2,B2")
 (match_operand "P3"  "A3,B3")

What is unclear to me is what conditions the constraints must satisfy to 
make reload do a (good) job. And of course not abort.

If the constraints were written as one alternative like in
 (match_operand "P1"  "A1 B1")
 (match_operand "P2"  "A2 B2")
 (match_operand "P3"  "A3 B3")
the problem would be much easier, because then we had

P = P1 x P2 x P3 -> (A1 + B1) x (A2 + B2) x (A3 + B3) = K'

If K' covers the hard reg part of P, everything is fine. Right?
Reload will map each pseudo/virtual in Pn to some hard reg in An+Bn or 
do just noting if the operand is an immediate.

But what happens when two alternatives are present? Obviously K is (in 
general) smaller than K' and reload must avoid the "holes" by generating 
new insns. These new insns can be movXX insns or insns that describe 
secondary reloads (or insns to spill a reg to get a needed reg_class free).

Is the condition "K' covers the hard reg part of P" also sufficient so 
that reload will never encounter problems like "insn does not satisfy 
its contraints" in the case of more than one alternative?

Do ?, ! and * have effects on running reload without problems? Or are 
they just present to improve the work of reload?

Internals say that reload scans constraints from left to right and 
choses the alternative with the most matches, skipping *-alternatives 
for reg_class preference. Then it tries to reload the pseudos that did 
not yet get a hard reg into an appropriate reg_class, i.e. some that 
matches the constraint, preferably one returned in 
PREFERRED_RELOAD_CLASS. If that macro return NO_REGS, reload reruns and 
also takes alternatives which are !-marked into account.

What is the situation if some regs are already hard regs? Is reload 
allowed to move a hard reg to some other hard reg (provided the 
destination is unused) to satisfy (more) constraints?

What happens when elimination takes place? For AVR eliminating the frame 
pointer aginst stack pointer is trivial because offset is 0. But what is 
about the fake argument pointer elimination whose offset is not 0?
Does eliminating the arg pointer suddenly turn (reg) into (plus reg x) 
and mov must reload a plus expression? Or does reload switch to addhi3 
and addhi3 suddenly faces the predicates/constraints of movhi and must 
handle a much more general case?

Thanks in advance,

Georg-Johann