Autoincrement addressing modes

Autoincrement addressing modes

[Michael P. Hayes]

I have been working on generalised support for autoincrement
addressing modes, where the increment may be a constant (not just the
width of the data type), an index register, or even potentially a
scaled index register, circularly modified base register, or
bit-reversed base register.

The format I've used is:

(post_modify (reg base) (expr))
(pre_modify (reg base) (expr))

where in the first case (reg base) is used as the address and then
this gets set to (expr) and in the second case (reg base) gets set
to (expr) and then used as the address.

Currently, I've patched flow.c and reload.c to handle the common
forms:

({post,pre}_modify (reg base) (plus (reg base) (reg index)))  
({post,pre}_modify (reg base) (plus (reg base) (const_int)))
({post,pre}_modify (reg base) (minus (reg base) (reg index)))

supporting addressing modes such as:

*(base += index)
*(base += const)
*(base -= index)

At this stage I'm interested in what other common forms should be
supported.

I'm also wondering if it is worthwhile to describe the addressing
modes of a machine, using something like:

(define_address
 [(mem:SF (match_operand:SI 0 "base_register" "a"))]
 ""
 "*%0")

or

(define_address
 [(mem:SI (plus:SI (match_operand:SI 0 "base_register" "a")
                   (match_operand:SI 1 "index_register" "x")))]
 ""
 "*%0(%1)")

or

(define_address
 [(mem:SI (post_modify:SI (match_operand:SI 0 "base_register" "a")
                          (plus:SI (match_dup 0)
                                  (match_operand:SI 1 "index_register" "x"))))]
 ""
 "*%0++(%1)")

Re: Autoincrement addressing modes

[Joern Rennecke]

> At this stage I'm interested in what other common forms should be
> supported.

The SH doesn't have any exotic update forms, but it has another
quirk in autoincrement that gcc doesn't handle efficiently:
POST_INC is only available for reading, while PRE_DEC is only
available for writing.

There are some places in the compiler that just test POST_INC / PRE_DEC
(or more generally HAVE_AUTO_INC) to check if an autoincrement might
be generated in a later stage.  It would be nice if these would
be updated not only to handle the new address updates properly, but also
only speculate the appropriatenes of an address update depending on
the direction of the memory access.

Re: Autoincrement addressing modes

[Jeffrey A Law]

  In message < 199802112304.XAA11969@phal.cygnus.co.uk >you write:
  > > At this stage I'm interested in what other common forms should be
  > > supported.
  > 
  > The SH doesn't have any exotic update forms, but it has another
  > quirk in autoincrement that gcc doesn't handle efficiently:
  > POST_INC is only available for reading, while PRE_DEC is only
  > available for writing.
The PA has similar constraints.

jeff

Re: Autoincrement addressing modes

[Michael P. Hayes]

Jeffrey A Law writes:
 > 
 >   In message < 199802112304.XAA11969@phal.cygnus.co.uk >you write:
 >   > > At this stage I'm interested in what other common forms should be
 >   > > supported.
 >   > 
 >   > The SH doesn't have any exotic update forms, but it has another
 >   > quirk in autoincrement that gcc doesn't handle efficiently:
 >   > POST_INC is only available for reading, while PRE_DEC is only
 >   > available for writing.
 > The PA has similar constraints.

Does this asymmetry only apply to these update forms of addressing
modes?

Any ideas how to describe this to GCC?  I suppose if there was a flag
to differentiate memory reads from writes, then
GO_IF_LEGITIMATE_ADDRESS could reject the invalid forms.

Re: Autoincrement addressing modes

[Joern Rennecke]

> Does this asymmetry only apply to these update forms of addressing
> modes?

The SH only has POST_INC and PRE_DEC.

I don't know what asymmetries appear in other processors, though.

Re: Autoincrement addressing modes

[Joern Rennecke]

> Does this asymmetry only apply to these update forms of addressing
> modes?
> 
> Any ideas how to describe this to GCC?  I suppose if there was a flag

One way would be to have

HAVE_PRE_DECREMENT_READ and HAVE_PRE_DECREMENT_WRITE to control the
two possible uses of PRE_DEC;
when HAVE_PRE_DECREMENT is defined, it can mean both of the above,
to maintain backward compatibility and make it easy for ports that
don't need to distinguish them.
Similarily for POST_DEC, PRE_INC, POST_INC.

> to differentiate memory reads from writes, then
> GO_IF_LEGITIMATE_ADDRESS could reject the invalid forms.

That would be goof too, but it doesn't help the code that doesn't
actually try to use the auto-increment, e.g. like move_by_pieces
in expr.c

Re: Autoincrement addressing modes

[Jeffrey A Law]

  In message < 199802120014.NAA29645@ongaonga.chch.cri.nz >you write:
  >  > The PA has similar constraints.
  > 
  > Does this asymmetry only apply to these update forms of addressing
  > modes?
Well, there's some weird asymmetry problems with nearly all of the addressing
modes, except for (reg) on the PA.  Many we are able to ignore, others we
deal with by not considering such addresses valid according to
GO_IF_LEGITIMATE_ADDRESS -- we do allow them in some predicates when we
can check for the weird problems.

  > Any ideas how to describe this to GCC?  I suppose if there was a flag
  > to differentiate memory reads from writes, then
  > GO_IF_LEGITIMATE_ADDRESS could reject the invalid forms.
So far we haven't tried.

Being able to distinguish between loads & stores in GO_IF_LEG... would be
a big step forward, but a lot of work.

My recommendation would be to not try and handle *all* the cases in the
first submission.  Just get something that can be extended, particularly
if we do fix GO_IF_LEG... later.
jeff

Re: Autoincrement addressing modes

[Richard Henderson]

On Thu, Feb 12, 1998 at 11:06:26AM +1300, Michael P. Hayes wrote:
> I'm also wondering if it is worthwhile to describe the addressing
> modes of a machine, using something like:
> 
> (define_address
>  [(mem:SF (match_operand:SI 0 "base_register" "a"))]
>  ""
>  "*%0")

I think this is a swell idea.  I can see it as being particularly
useful to use this kind of description to help auto-generate
GO_IF_LEGITIMATE_ADDRESS and LEGITIMIZE_ADDRESS.  As it is not a
few ports lie to gcc about how addresses really work with -fpic,
perhaps if it were easier to describe, ports would quite lying.

Though I would get rid of the mem and add a name,

(define_address "base_disp"
  [(plus:DI (match_operand:DI 0 "register_operand" "r")
	    (match_operand:DI 1 "const16_operand" "I"))]
  ""
  "%1(%0)")

(define_address "unaligned_base_disp"
  [(and:DI (plus:DI (match_operand:DI 0 "register_operand" "r")
	            (match_operand:DI 1 "const16_operand" "I"))
	   (const_int -8))]
  ""
  "%1(%0)")

(define_address "symbolic"
  [(match_operand:SI 0 "symbolic_operand" "s")]
  "! flag_pic"
  "%0")

(define_address "symbolic"
  [(plus:SI (reg:SI "ebx")
     (match_operand:SI 0 "symbolic_operand" "s"))]
  "flag_pic"
  "%0(%%ebx)")

and create a mechanism whereby related address modes could be
collected and named ("input_address"). 

You might also allow addressing modes to be given attributes,
like "cost" or "length".  The former might be useful in creating
ADDRESS_COST, the later in adjusting the length of the insn that
contains the address.

It would be interesting to see what would happen if the mov insns
were restructured to name the precise address modes that could be
used (via a match_address).  This would increase the number of
insn patterns, possibly greatly, but it would also allow all the
HAVE_PRE_DEC_INPUT or whatever uglyness to be detected by genconfig.


Just rambling at this point...


r~

Re: Autoincrement addressing modes

[Michael P. Hayes]

Richard Henderson writes:
 > On Thu, Feb 12, 1998 at 11:06:26AM +1300, Michael P. Hayes wrote:
 > > I'm also wondering if it is worthwhile to describe the addressing
 > > modes of a machine, using something like:
 > > 
 > > (define_address
 > >  [(mem:SF (match_operand:SI 0 "base_register" "a"))]
 > >  ""
 > >  "*%0")
 > 
 > I think this is a swell idea.  I can see it as being particularly
 > useful to use this kind of description to help auto-generate
 > GO_IF_LEGITIMATE_ADDRESS and LEGITIMIZE_ADDRESS.  As it is not a
 > few ports lie to gcc about how addresses really work with -fpic,
 > perhaps if it were easier to describe, ports would quite lying.
 > 
 > Though I would get rid of the mem and add a name,

Yes, I agree.  Initially I thought that it was necessary to specify
the mode that could be addressed (say to validate an offsettable
displacement), but this should be handled by the condition.

This condition could also test a global variable, memory_read, or some
such thing, to handle the assymetry of some machines where
autoincrements are OK for memory reads but not for memory writes.

Re: Autoincrement addressing modes

[Joern Rennecke]

> > (define_address
> >  [(mem:SF (match_operand:SI 0 "base_register" "a"))]
> >  ""
> >  "*%0")
> 
> I think this is a swell idea.  I can see it as being particularly
> useful to use this kind of description to help auto-generate
> GO_IF_LEGITIMATE_ADDRESS and LEGITIMIZE_ADDRESS.  As it is not a
> few ports lie to gcc about how addresses really work with -fpic,
> perhaps if it were easier to describe, ports would quite lying.
> 
> Though I would get rid of the mem and add a name,
> 
> (define_address "base_disp"
>   [(plus:DI (match_operand:DI 0 "register_operand" "r")
> 	    (match_operand:DI 1 "const16_operand" "I"))]
>   ""
>   "%1(%0)")

Adding a name is fine, but I wouldn't want to drop the mem.  Note that the
mem has a mode, which is useful for a number of ports.
If it is not useful, you can still leave out the mode (i.e., it will be
VoidMODE).

moreover, we need some way to link the address forms to the places where
they are possible - e.g. it is common that the set of allowed addresses
for loads is different from the ones allowed for stores.

Should that be a list of constraints - e.g. "g" could be only for reading
general operands, "=g" only for writing general operands, "=g,g" for 
either of these, "+g" only for read-write general operands, "=" for and
kind of write-only operand...

Or should we put lists of addressing modes in some other kind of
declaration in the machine description?
E.g.:
(define_load ["base", "base_disp", "auto_inc"])
(define_store ["base", "base_disp", "auto_dec"])
(define_mem_arith ["base", "base_disp"])

Re: Autoincrement addressing modes

[Richard Henderson]

On Mon, Mar 16, 1998 at 10:51:27PM +0000, Joern Rennecke wrote:
> Adding a name is fine, but I wouldn't want to drop the mem.  Note that the
> mem has a mode, which is useful for a number of ports.
> If it is not useful, you can still leave out the mode (i.e., it will be
> VoidMODE).
> 
> moreover, we need some way to link the address forms to the places where
> they are possible - e.g. it is common that the set of allowed addresses
> for loads is different from the ones allowed for stores.

I thought I'd had a pseudo example of what I'd had in mind for handling
both of these in a stroke: referencing it in an insn.

  (define_insn "*movsi_load"
    [(set (match_operand:SI 0 "register_operand" "r")
	  (mem:SI (match_address:PI 1 "base,base_disp,auto_inc")))]
    "ldl %0,%1")

  (define_insn "*movsi_store"
    [(set (mem:SI (match_address:PI 1 "base,base_disp,auto_dec"))
	  (match_operand:SI 0 "register_operand" "r"))]
    "stl %0,%1")

(While we're at changes, recognize PI as an alias for SI or DI as 
appropriate to the current pointer size.)

I like this method since it allows to use the same address forms
in lea-type instructions.  

We'll also probably find it convenient to do something similar to

  (define_address "load" ["base", "base_disp", "auto_inc"])

simply to define aliases that are combinations of address types,
since otherwise cisc-y boxes like i386 and m68k will get unwieldy.


r~

Re: Autoincrement addressing modes

[Michael P. Hayes]

Richard Henderson writes:
 > On Mon, Mar 16, 1998 at 10:51:27PM +0000, Joern Rennecke wrote:
 > I thought I'd had a pseudo example of what I'd had in mind for handling
 > both of these in a stroke: referencing it in an insn.
 > 
 >   (define_insn "*movsi_load"
 >     [(set (match_operand:SI 0 "register_operand" "r")
 > 	  (mem:SI (match_address:PI 1 "base,base_disp,auto_inc")))]
 >     "ldl %0,%1")
 > 
 >   (define_insn "*movsi_store"
 >     [(set (mem:SI (match_address:PI 1 "base,base_disp,auto_dec"))
 > 	  (match_operand:SI 0 "register_operand" "r"))]
 >     "stl %0,%1")
 > 

I'm unsure about this since it would require wholesale changes to the
machine description.  For example, how would you handle an add insn
that could have memory or register operands in various combinations?

 > (While we're at changes, recognize PI as an alias for SI or DI as 
 > appropriate to the current pointer size.)

I agree that Pmode should be used for addresses in the machine
description.

Re: Autoincrement addressing modes

[Joern Rennecke]

>  > I thought I'd had a pseudo example of what I'd had in mind for handling
>  > both of these in a stroke: referencing it in an insn.
>  > 
>  >   (define_insn "*movsi_load"
>  >     [(set (match_operand:SI 0 "register_operand" "r")
>  > 	  (mem:SI (match_address:PI 1 "base,base_disp,auto_inc")))]
>  >     "ldl %0,%1")
>  > 
>  >   (define_insn "*movsi_store"
>  >     [(set (mem:SI (match_address:PI 1 "base,base_disp,auto_dec"))
>  > 	  (match_operand:SI 0 "register_operand" "r"))]
>  >     "stl %0,%1")
>  > 
> 
> I'm unsure about this since it would require wholesale changes to the
> machine description.  For example, how would you handle an add insn
> that could have memory or register operands in various combinations?

Seconded.  This even applies to some RISC pattern, e.g. sign/zero extension
can be a register-register operation or a memory-register operation.
The way gcc is designde we have to use a single pattern for this so that
reload can do The Right Thing (tm).

Re: Autoincrement addressing modes

[Richard Henderson]

> Seconded.  This even applies to some RISC pattern, e.g. sign/zero extension
> can be a register-register operation or a memory-register operation.
> The way gcc is designde we have to use a single pattern for this so that
> reload can do The Right Thing (tm).

Good point.  Perhaps the thing to do then is to tie addresses
to instruction types, a-la 

  (define_attr "type" "ld,st,lea")

  (define_address "base"
    (mem (match_operand:PI 0 "register_operand" "r"))
    (eq_attr "type" "ld,st,lea")
    "0(%0)")

  (define_address "auto_inc"
    (mem (post_inc (match_operand:PI 0 "register_operand" "r")))
    (eq_attr "type" "ld")
    "(%0)+")

This would then let us have arbitrarily complex conditions that
the insn must satisfy before the address strictly matches. 

Not sure exactly how we'd notice that insn type "ist" is a store,
for early (pre-reload) optimizations for things like auto_inc.
Perhaps with magic attributes on the addresses themselves, though
it would be nicer to discover these kinds of things rather than
having to be told.


r~

Re: Autoincrement addressing modes

[Joern Rennecke]

> Good point.  Perhaps the thing to do then is to tie addresses
> to instruction types, a-la 
> 
>   (define_attr "type" "ld,st,lea")
> 
>   (define_address "base"
>     (mem (match_operand:PI 0 "register_operand" "r"))
>     (eq_attr "type" "ld,st,lea")
>     "0(%0)")
> 
>   (define_address "auto_inc"
>     (mem (post_inc (match_operand:PI 0 "register_operand" "r")))
>     (eq_attr "type" "ld")
>     "(%0)+")
> 
> This would then let us have arbitrarily complex conditions that
> the insn must satisfy before the address strictly matches. 

We already have this possibility when recognizing an insn - since every
insn can have an arbitrary condition.
Thus, if we actually need to have the exact insn in order to verify it,
we win nothing compared to the current scheme.

One possible improvement could be if we don't need to have the exact insn,
but only one that matches the right pattern, and then be able to
look at the different alternatives 'by hand' .  If we make the "type"
attribute 'magic', we could probably do some tests for possible addressing
modes without actually modifying the insn - provided that the "type"
attribute of the insn only depends on the alternative, and that
the conditions of the addressing modes are NOT arbitrarily complex,
but only list a list of possible insn types.

> Not sure exactly how we'd notice that insn type "ist" is a store,
> for early (pre-reload) optimizations for things like auto_inc.
> Perhaps with magic attributes on the addresses themselves, though
> it would be nicer to discover these kinds of things rather than
> having to be told.

That is not that hard in flow / regmove when we are dealing with
actual insns, but it seems near impossible for pre-rtl-generation tests
like in expr.c:move_by_pieces .

We probably have to use some sort of approximation, i.e. if the
mode & direction is available for any insn & alternative under some
condition, we presume that it is available.

But if using predicates that the gen* files don't understand will lead to
poor code, maybe we should not use a model that encourages to use them.

To pick up the example from above, we could say:

  (define_address "base"
    (mem (match_operand:PI 0 "register_operand" "r"))
    "ld,st,lea"
    "0(%0)")

and it is implied that "ld,st,lea" is a list of values for the attribute
"type" .

If addressing modes of different operands interfere with each other, it
should in general be possible to express this with sufficiently detailed
instruction alternatives.  If you need anything more complicated, it
should propably go into the insn predicate.

Re: Autoincrement addressing modes

[Michael P. Hayes]

Joern Rennecke writes:
 > Adding a name is fine, but I wouldn't want to drop the mem.  Note that the
 > mem has a mode, which is useful for a number of ports.
 > If it is not useful, you can still leave out the mode (i.e., it will be
 > VoidMODE).

I think I like having the mem since it does indicate which modes are
valid for the address (although it could be handled by an extra
condition).  If the mem was kept, this define_address construct could
be generalised to something like define_operand which could detail all
the valid operand forms for the target machine.

I would also like to see a more generalised cost mechanism for
operands that takes into account other operands used in an insn.  For
example, a small immediate integer may have a low cost in an insn if
the other operand is a register, but a high cost if the other operand
is a memory address.

 > moreover, we need some way to link the address forms to the places where
 > they are possible - e.g. it is common that the set of allowed addresses
 > for loads is different from the ones allowed for stores.

The problem here is dealing with insns that may allow two addresses
with small displacements but only one address with a large
displacement.

I suppose the only way to be sure that an address is valid for an insn
is to try recognising the insn with that address.

I've had similar problems (notably with instantiate_virtual_regs_1)
where a small constant is added to an address.  While the new address
is deemed valid by memory_address_p, it is no longer valid for
the insn it is used with.