Load/store with auto-increment/decrement can reduce the number of
instructions in many loops (especially those that mostly iterate over
arrays of data). It can also be used in function prologues and epilogues
(for push/pop functionality).

For a long time I had dismissed load/store with auto-increment for my
ISA (MRISC32). The reason is that a load operation with auto-increment
would have TWO results (the loaded value and the updated address base),
which would be a complication (all other instructions have at most one
result).

However, a couple of days ago I realized that store operations do not
have any result, so I could add instructions for store with auto-
increment, and still only have one result. I have a pretty good idea
of how to do it (instruction encoding etc), and it would fit fairly
well (the only oddity would be that the result register is not the
first register address in the instruction word, but the second register
address, which requires some more MUX:ing in the decoding stages).

The next question is: What flavors should I have?

- Post-increment (most common?)
- Post-decrement
- Pre-increment
- Pre-decrement (second most common?)

The "pre" variants would possibly add more logic to critical paths (e.g.
add more gate delay in the AGU before the address is ready for the
memory stage).

Any thoughts? Is it worth it?

/Marcus

According to Marcus <m.delete@this.bitsnbites.eu>:
>Load/store with auto-increment/decrement can reduce the number of
>instructions in many loops (especially those that mostly iterate over
>arrays of data). It can also be used in function prologues and epilogues
>(for push/pop functionality). ...

>Any thoughts? Is it worth it?

Autoincrement was quite popular in the 1960s and 70s. The DEC 12 and
18 bit minis and the DG Nova had a version of it where specific
addresses would autoinrement or decrement when used as indirect
addresses. I did a fair amount of PDP-8 programming and those
autoincrement locations were precious, which said as much about the
limits of the 8's instruction set as anything else.

The PDP-11 generalized this to useful modes -(R) and (R)+ to
predecrement or postincrement any register when used as an address,
which is how it handled stacks and the simple cases of stepping
through a string or array.

It also had indirect versions of both, @(R)+ which was useful for
stepping through an array of pointers (one instruction dispatch for
threaded code or coroutines) and @-(R) which turned out to be useless
and was dropped in the VAX.

Here it is 50 years later and they're all gone. I think the increase
in code density wasn't worth the contortions to ensure that your data
structures fit the few cases that the autoincrement modes handled. It
also made it harder to parallelize and pipeline stuff since address
modes had side effects that had to be scheduled around or potentially
unwound in a page fault.

--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

On 2023-05-06, John Levine wrote:
> Here it is 50 years later and they're all gone. I think the increase
> in code density wasn't worth the contortions to ensure that your data
> structures fit the few cases that the autoincrement modes handled. It
> also made it harder to parallelize and pipeline stuff since address
> modes had side effects that had to be scheduled around or potentially
> unwound in a page fault.

Actually, ARM has auto-increment (even AArch64). I think that if you
limit what you can do (not the crazy multi-memory accesses instructions
that was popular in CISC, e.g. 68k), you should not have any problems
with page fault handling etc. Unless...

Does the auto-increment instruction implicitly introduce a data-
dependency that's also dependent on the memory operation to complete?
Is there any real difference compared to doing the memory operation
and the address increment in two separate instructions (in an OoO
machine)?

/Marcus

On Saturday, May 6, 2023 at 9:59:03 AM UTC-5, Marcus wrote:
> Load/store with auto-increment/decrement can reduce the number of
> instructions in many loops (especially those that mostly iterate over
> arrays of data). It can also be used in function prologues and epilogues
> (for push/pop functionality).
<
Can it actually save instructions ??
<
p = <some address>;
q = <some other address>;
for( i = 0; i < max; i++ )
*p++ = *q++;
<
LDA Rp,[IP,,displacement1]
LDA Rq,[IP,,displacement2]
MOV Ri,#0
VEC Rt,{}
top_of_loop:
LDSW Rqm,[Rq+Ri<<2]
STW Rgm,[Rp+Ri<<2
LOOP LE,Ri,#1,Rmax
end_of_loop:
>
Which instruction can be saved in this loop??
<
> For a long time I had dismissed load/store with auto-increment for my
> ISA (MRISC32). The reason is that a load operation with auto-increment
> would have TWO results (the loaded value and the updated address base),
<
That is the first problem.
<
> which would be a complication (all other instructions have at most one
> result).
>
> However, a couple of days ago I realized that store operations do not
> have any result, so I could add instructions for store with auto-
> increment, and still only have one result. I have a pretty good idea
> of how to do it (instruction encoding etc), and it would fit fairly
> well (the only oddity would be that the result register is not the
> first register address in the instruction word, but the second register
> address, which requires some more MUX:ing in the decoding stages).
<
So, autoincrement on STs only ??
>
> The next question is: What flavors should I have?
>
> - Post-increment (most common?)
> - Post-decrement
> - Pre-increment
> - Pre-decrement (second most common?)
<
Not having these eliminates having to choose.
>
> The "pre" variants would possibly add more logic to critical paths (e.g.
> add more gate delay in the AGU before the address is ready for the
> memory stage).
>
> Any thoughts? Is it worth it?
<
In my option, needing autoincrements is a sign of a weak ISA and
possibly that of a less than stellar compiler.
>
> /Marcus

On Saturday, May 6, 2023 at 12:36:30 PM UTC-5, Marcus wrote:
> On 2023-05-06, John Levine wrote:
> > Here it is 50 years later and they're all gone. I think the increase
> > in code density wasn't worth the contortions to ensure that your data
> > structures fit the few cases that the autoincrement modes handled. It
> > also made it harder to parallelize and pipeline stuff since address
> > modes had side effects that had to be scheduled around or potentially
> > unwound in a page fault.
> Actually, ARM has auto-increment (even AArch64). I think that if you
> limit what you can do (not the crazy multi-memory accesses instructions
> that was popular in CISC, e.g. 68k), you should not have any problems
> with page fault handling etc. Unless...
>
> Does the auto-increment instruction implicitly introduce a data-
> dependency that's also dependent on the memory operation to complete?
<
Not necessarily, but it does create a base-register to base-register
dependency on uses of the addressing register. So, memory is not
compromised, but use of the register can be.
<
> Is there any real difference compared to doing the memory operation
> and the address increment in two separate instructions (in an OoO
> machine)?
>
> /Marcus

Marcus <m.delete@this.bitsnbites.eu> schrieb:
> Load/store with auto-increment/decrement can reduce the number of
> instructions in many loops (especially those that mostly iterate over
> arrays of data). It can also be used in function prologues and epilogues
> (for push/pop functionality).

One step further: You can have something like POWER's load and
store with update. For example,

ldux rt,ra,rb

will load a doubleword from the address ra + rb and set ra to
ra + rb, or

ldu rt,num(ra)

will load rt from num + ra and set ra = ra + num.

You can simulate autoincrement/autodecrement if you write

ldu rt,8(ra)

or

ldu rt,-8(ra)

respectively.

> For a long time I had dismissed load/store with auto-increment for my
> ISA (MRISC32). The reason is that a load operation with auto-increment
> would have TWO results (the loaded value and the updated address base),
> which would be a complication (all other instructions have at most one
> result).

Exactly.

> However, a couple of days ago I realized that store operations do not
> have any result, so I could add instructions for store with auto-
> increment, and still only have one result.

That would create a rather weird asymmetry between load and store.
It could also create problems for the compiler - I'm not sure that
gcc is set up to easily handle different addressing modes for load
and store.

> I have a pretty good idea
> of how to do it (instruction encoding etc), and it would fit fairly
> well (the only oddity would be that the result register is not the
> first register address in the instruction word, but the second register
> address, which requires some more MUX:ing in the decoding stages).
>
> The next question is: What flavors should I have?
>
> - Post-increment (most common?)
> - Post-decrement
> - Pre-increment
> - Pre-decrement (second most common?)

If you want to save instructions in a loop and have a "compare to zero"
instruction (which I seem to remember you do), then a negative index
could be something else to try.

Consider transforming

for (int i=0; i<n; i++)
a[i] = b[i] + 2;

into

*ap = a + n;
*bp = b + n;
for (int i=-n; i != 0; i++)
ap[i] = bp[i] + 2;

and expressing the body of the loop as

start:
ldd r1,rb,-ri
addi r1,r1,2
std r1,ra,-ri
add ri,ri,1
beq0 ri,start

Hmm... is there any ISA which allows for both negative and positive
indexing?

> The "pre" variants would possibly add more logic to critical paths (e.g.
> add more gate delay in the AGU before the address is ready for the
> memory stage).
>
> Any thoughts? Is it worth it?

Not sure it is - this kind of instruction will be split into two
micro-instructions on any OoO machine, and probably for in-order,
as well.

Consider a string of *p++
a = *p++;
b = *p++;
c = *p++;
<
Here we see the failure of the ++ or -- notation.
The LD of b is dependent on the ++ of a
The LD of c is dependent on the ++ of b
Whereas if the above was written::
<
a = p[0];
b = p[1];
c = p[2];
p +=3;
<
Now all three LDs are independent and can issue/execute/retire
simultaneously. Also, the add to p is independent, so we took
3 "instructions" that were serially dependent and make them into
4 instructions that are completely independent in all phases of
execution.

On 5/6/2023 1:15 PM, MitchAlsup wrote:
> On Saturday, May 6, 2023 at 9:59:03 AM UTC-5, Marcus wrote:
>> Load/store with auto-increment/decrement can reduce the number of
>> instructions in many loops (especially those that mostly iterate over
>> arrays of data). It can also be used in function prologues and epilogues
>> (for push/pop functionality).
> <
> Can it actually save instructions ??
> <
> p = <some address>;
> q = <some other address>;
> for( i = 0; i < max; i++ )
> *p++ = *q++;
> <
> LDA Rp,[IP,,displacement1]
> LDA Rq,[IP,,displacement2]
> MOV Ri,#0
> VEC Rt,{}
> top_of_loop:
> LDSW Rqm,[Rq+Ri<<2]
> STW Rgm,[Rp+Ri<<2
> LOOP LE,Ri,#1,Rmax
> end_of_loop:
>>
> Which instruction can be saved in this loop??
> <
>> For a long time I had dismissed load/store with auto-increment for my
>> ISA (MRISC32). The reason is that a load operation with auto-increment
>> would have TWO results (the loaded value and the updated address base),
> <
> That is the first problem.
> <
>> which would be a complication (all other instructions have at most one
>> result).
>>
>> However, a couple of days ago I realized that store operations do not
>> have any result, so I could add instructions for store with auto-
>> increment, and still only have one result. I have a pretty good idea
>> of how to do it (instruction encoding etc), and it would fit fairly
>> well (the only oddity would be that the result register is not the
>> first register address in the instruction word, but the second register
>> address, which requires some more MUX:ing in the decoding stages).
> <
> So, autoincrement on STs only ??
>>
>> The next question is: What flavors should I have?
>>
>> - Post-increment (most common?)
>> - Post-decrement
>> - Pre-increment
>> - Pre-decrement (second most common?)
> <
> Not having these eliminates having to choose.
>>
>> The "pre" variants would possibly add more logic to critical paths (e.g.
>> add more gate delay in the AGU before the address is ready for the
>> memory stage).
>>
>> Any thoughts? Is it worth it?
> <
> In my option, needing autoincrements is a sign of a weak ISA and
> possibly that of a less than stellar compiler.

I skipped auto-increment as it typically saves "hardly anything" (at
best) and adds an awkward case that needs to be decomposed into two
sub-operations (most other cases).

So, I didn't really feel it was "worth it".

It could almost make sense on a 1-wide machine, except that one needs to
add one of the main expensive parts of a 2-wide machine in order to
support it (and on a superscalar machine, the increment would likely end
up running in parallel with some other op anyways).

....

For register save/restore, maybe it makes sense:
But, one can use normal displacement loads/stores and a single big
adjustment instead;
Things like "*ptr++" could use it, but are still not common enough to
make it significant (combined with the thing of the "ptr++" part usually
just running in parallel with another op anyways).

>>
>> /Marcus

On Saturday, May 6, 2023 at 10:58:39 PM UTC-4, BGB wrote:
> On 5/6/2023 1:15 PM, MitchAlsup wrote:
> > On Saturday, May 6, 2023 at 9:59:03 AM UTC-5, Marcus wrote:
> >> Load/store with auto-increment/decrement can reduce the number of
> >> instructions in many loops (especially those that mostly iterate over
> >> arrays of data). It can also be used in function prologues and epilogues
> >> (for push/pop functionality).
> > <
> > Can it actually save instructions ??
> > <
> > p = <some address>;
> > q = <some other address>;
> > for( i = 0; i < max; i++ )
> > *p++ = *q++;
> > <
> > LDA Rp,[IP,,displacement1]
> > LDA Rq,[IP,,displacement2]
> > MOV Ri,#0
> > VEC Rt,{}
> > top_of_loop:
> > LDSW Rqm,[Rq+Ri<<2]
> > STW Rgm,[Rp+Ri<<2
> > LOOP LE,Ri,#1,Rmax
> > end_of_loop:
> >>
> > Which instruction can be saved in this loop??
> > <
> >> For a long time I had dismissed load/store with auto-increment for my
> >> ISA (MRISC32). The reason is that a load operation with auto-increment
> >> would have TWO results (the loaded value and the updated address base),
> > <
> > That is the first problem.
> > <
> >> which would be a complication (all other instructions have at most one
> >> result).
> >>
> >> However, a couple of days ago I realized that store operations do not
> >> have any result, so I could add instructions for store with auto-
> >> increment, and still only have one result. I have a pretty good idea
> >> of how to do it (instruction encoding etc), and it would fit fairly
> >> well (the only oddity would be that the result register is not the
> >> first register address in the instruction word, but the second register
> >> address, which requires some more MUX:ing in the decoding stages).
> > <
> > So, autoincrement on STs only ??
> >>
> >> The next question is: What flavors should I have?
> >>
> >> - Post-increment (most common?)
> >> - Post-decrement
> >> - Pre-increment
> >> - Pre-decrement (second most common?)
> > <
> > Not having these eliminates having to choose.
> >>
> >> The "pre" variants would possibly add more logic to critical paths (e.g.
> >> add more gate delay in the AGU before the address is ready for the
> >> memory stage).
> >>
> >> Any thoughts? Is it worth it?
> > <
> > In my option, needing autoincrements is a sign of a weak ISA and
> > possibly that of a less than stellar compiler.
> I skipped auto-increment as it typically saves "hardly anything" (at
> best) and adds an awkward case that needs to be decomposed into two
> sub-operations (most other cases).
>
> So, I didn't really feel it was "worth it".
>
> It could almost make sense on a 1-wide machine, except that one needs to
> add one of the main expensive parts of a 2-wide machine in order to
> support it (and on a superscalar machine, the increment would likely end
> up running in parallel with some other op anyways).
>
> ...
>
>
> For register save/restore, maybe it makes sense:
> But, one can use normal displacement loads/stores and a single big
> adjustment instead;
> Things like "*ptr++" could use it, but are still not common enough to
> make it significant (combined with the thing of the "ptr++" part usually
> just running in parallel with another op anyways).
>
>
> >>
> >> /Marcus

Auto inc/dec can be difficult for the compiler to make use of. Sometime
the p++ will end up as a separate add anyway. If there is scaled indexed
addressing often loop increment vars can be used, and the loop
increment is needed anyway.
p[n] = q[n];
n++;
I used extra bits available in load / store instruction to indicate the
cache-ability of data. Requires compiler support though.

Having a push instruction can be handy, and good for code density if it
can push multiple registers in a single instruction.

I have multi-register loads and stores in groups of eight registers for
Thor. Based on filling up the entire cache line with register data then
issuing a single load or store operation.

Marcus <m.delete@this.bitsnbites.eu> writes:
>Load/store with auto-increment/decrement can reduce the number of
>instructions in many loops (especially those that mostly iterate over
>arrays of data).

Yes.

If you do it only for stores, as suggested below, it could be used for
loops that read from one or more arrays and write to one array, all
with the same stride, as follows (in pseudo-C-code):

/* read from a and b, write to c */
da=a-c;
db=b-c;
for (...) {
*c = c[da] * c[db];
c+=stride;
}

the "c+=stride" could become the autoincrement of the store.

>It can also be used in function prologues and epilogues
>(for push/pop functionality).

Not so great, because it introduces data dependencies between the
stores that you then have to get rid of if you want to support more
than one store per cycle. As for the pops, those are loads, and here
the autoincrement would require an additional write port to the
register file, as you point out below; plus it would introduce data
dependencies that you don't want (many cores support more than one
load per cycle).

>The next question is: What flavors should I have?
>
>- Post-increment (most common?)
>- Post-decrement
>- Pre-increment
>- Pre-decrement (second most common?)
>
>The "pre" variants would possibly add more logic to critical paths (e.g.
>add more gate delay in the AGU before the address is ready for the
>memory stage).

You typically have memory-access instructions that include an addition
in the address computation; in that case pre obviously has no extra
cost. The cost of the addition can be reduced (eliminated) with a
technique called sum-addressed memory. OTOH, IA-64 supports only
memory accesses of an address given in a register, so here the
architects apparently thought that sum-addressed memory is still too
slow.

Increment vs. decrement: If your store supports reading two registers
for address computation (in addition to the data register), you can
put the stride in a register, making the whole question moot. Even if
you only support reading one register in addition to the data, you can
have a sign-extended constant stride, again giving you both increment
and decrement options. Note that having a store that does not support
the sum of two registers, but does support autoincrement, and a load
that supports the sum of two registers as address is means that both
loads and stores can read two registers and write one register, which
may be useful for certain microarchitectural approaches.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

John Levine <johnl@taugh.com> writes:
>Here it is 50 years later and they're all gone.

PowerPC and ARM A32 is still there. And there's even a new
architecture with auto-increment: ARM A64.

>I think the increase
>in code density wasn't worth the contortions to ensure that your data
>structures fit the few cases that the autoincrement modes handled.

Are you thinking of the DSPs that do not have displacement addressing,
but have auto-increment, leading to a number of papers on how the
compiler should arrange the variables to make best use of that?

With displacement addressing no such contortions are necessary.

>It
>also made it harder to parallelize and pipeline stuff since address
>modes had side effects that had to be scheduled around or potentially
>unwound in a page fault.

Pipelining was apparently no problem, as evidenced by several early
RISCs (ARM (A32), HPPA, PowerPC) having auto-increment. Just don't
write the address register before verifying the address. And
parallelizing is no problem, either: IA-64 was designed for Explicitly
Parallel Instruction Computing, and has auto-increment.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

MitchAlsup <MitchAlsup@aol.com> writes:
>Consider a string of *p++
> a = *p++;
> b = *p++;
> c = *p++;
><
>Here we see the failure of the ++ or -- notation.
>The LD of b is dependent on the ++ of a
>The LD of c is dependent on the ++ of b
>Whereas if the above was written::
><
> a = p[0];
> b = p[1];
> c = p[2];
> p +=3;
><
>Now all three LDs are independent and can issue/execute/retire
>simultaneously. Also, the add to p is independent, so we took
>3 "instructions" that were serially dependent and make them into
>4 instructions that are completely independent in all phases of
>execution.

Can the compiler not recogize the first pattern and convert
it into the second form under the as-if rule?

It appears that Anton Ertl <anton@mips.complang.tuwien.ac.at> said:
>PowerPC and ARM A32 is still there. And there's even a new
>architecture with auto-increment: ARM A64.

I need to take a look.

>>I think the increase
>>in code density wasn't worth the contortions to ensure that your data
>>structures fit the few cases that the autoincrement modes handled.
>
>Are you thinking of the DSPs that do not have displacement addressing,
>but have auto-increment, leading to a number of papers on how the
>compiler should arrange the variables to make best use of that?

Autoincrement only increments by the size of a single datum so it
works for strings and vectors, not for arrays of structures or 2-D
arrays. Compare it to the 360's BXLE loop closing instruction which
put the stride in a register so it could be whatever you wanted.
It also had base+index which the Vax did but the PDP-11 only sort
of did if you used absolute addresses instead of a base.

On the PDP-11 autoincrement allowed a two instruction string copy loop:

c: movb (r1)+,(r2)+
bnz c ; loop if the byte wasn't zero

but how useful is that now? I don't know.

>With displacement addressing no such contortions are necessary.

I don't see how that solves the stride problem. Or did you mean
something else?

>>It >also made it harder to parallelize and pipeline stuff since address
>>modes had side effects that had to be scheduled around or potentially
>>unwound in a page fault.
>
>Pipelining was apparently no problem, as evidenced by several early
>RISCs (ARM (A32), HPPA, PowerPC) having auto-increment. Just don't
>write the address register before verifying the address. ...

Do they have the kind of hazards that the -11 and Vax did, where you could
autoincrement the same register more than once in a single instruction, or
use the incremented register as an operand? That made things messy.
--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

On 07/05/2023 18:05, Scott Lurndal wrote:
> MitchAlsup <MitchAlsup@aol.com> writes:
>> Consider a string of *p++
>> a = *p++;
>> b = *p++;
>> c = *p++;
>> <
>> Here we see the failure of the ++ or -- notation.
>> The LD of b is dependent on the ++ of a
>> The LD of c is dependent on the ++ of b
>> Whereas if the above was written::
>> <
>> a = p[0];
>> b = p[1];
>> c = p[2];
>> p +=3;
>> <
>> Now all three LDs are independent and can issue/execute/retire
>> simultaneously. Also, the add to p is independent, so we took
>> 3 "instructions" that were serially dependent and make them into
>> 4 instructions that are completely independent in all phases of
>> execution.
>
> Can the compiler not recogize the first pattern and convert
> it into the second form under the as-if rule?

Yes, and compilers have done such conversions for decades. (Of course,
that assumes you are not dealing with external data, or expressions that
could alias each other.)

On 07/05/2023 18:55, John Levine wrote:
> It appears that Anton Ertl <anton@mips.complang.tuwien.ac.at> said:
>> PowerPC and ARM A32 is still there. And there's even a new
>> architecture with auto-increment: ARM A64.
>
> I need to take a look.
>
>>> I think the increase
>>> in code density wasn't worth the contortions to ensure that your data
>>> structures fit the few cases that the autoincrement modes handled.
>>
>> Are you thinking of the DSPs that do not have displacement addressing,
>> but have auto-increment, leading to a number of papers on how the
>> compiler should arrange the variables to make best use of that?
>
> Autoincrement only increments by the size of a single datum so it
> works for strings and vectors, not for arrays of structures or 2-D
> arrays. Compare it to the 360's BXLE loop closing instruction which
> put the stride in a register so it could be whatever you wanted.
> It also had base+index which the Vax did but the PDP-11 only sort
> of did if you used absolute addresses instead of a base.
>
> On the PDP-11 autoincrement allowed a two instruction string copy loop:
>
> c: movb (r1)+,(r2)+
> bnz c ; loop if the byte wasn't zero
>
> but how useful is that now? I don't know.
>

Similar instructions would be used for copying memory blocks, and that
is very useful!

Scott Lurndal <scott@slp53.sl.home> schrieb:
> MitchAlsup <MitchAlsup@aol.com> writes:
>>Consider a string of *p++
>> a = *p++;
>> b = *p++;
>> c = *p++;
>><
>>Here we see the failure of the ++ or -- notation.
>>The LD of b is dependent on the ++ of a
>>The LD of c is dependent on the ++ of b
>>Whereas if the above was written::
>><
>> a = p[0];
>> b = p[1];
>> c = p[2];
>> p +=3;
>><
>>Now all three LDs are independent and can issue/execute/retire
>>simultaneously. Also, the add to p is independent, so we took
>>3 "instructions" that were serially dependent and make them into
>>4 instructions that are completely independent in all phases of
>>execution.
>
> Can the compiler not recogize the first pattern and convert
> it into the second form under the as-if rule?

Of course:

void bar (int a, int b, int c);

void foo (int *p)
{ int a, b, c;
a = *p++;
b = *p++;
c = *p++;
bar (a, b, c);
}

results in

lw a2,8(a0)
lw a1,4(a0)
lw a0,0(a0)
tail bar

on RISC-V, for example (aarch64 plays games with load double,
so it's a bit harder to read).

But I believe Mitch was referring to the assembler equivalent, where
p be held in a register.

Autodecrement and increment is done on 386ff. How do they avoid
the register dependency of the stack register? Special handling?
Instruction fusing?

It appears that David Brown <david.brown@hesbynett.no> said:
>> On the PDP-11 autoincrement allowed a two instruction string copy loop:
>>
>> c: movb (r1)+,(r2)+
>> bnz c ; loop if the byte wasn't zero
>>
>> but how useful is that now? I don't know.
>
>Similar instructions would be used for copying memory blocks, and that
>is very useful!

Not really. On modern computers you want to copy in ways that make
best use of the multiple registers so you're more likely to do a
sequence of loads followed by a sequence of stores, mabybe with shift
and mask in between if they're not aligned, then move on to the next
block. You could use autoincrement but you'll probably get better
performance with instructions that clearly don't depend on each other
so they can run in parallel, e.g.

; r8 is source, r9 is dest
loop:
ld r1,0[r8]
ld r2,8[r8]
ld r3,16[r8]
ld r4,24[r8]
; shift and mask to align if needed
st r1,0[r9]
st r2,8[r9]
st r3,16[r9]
st r4,24[r9]

addi r8,#32
addi r9,#32
branch if not done to loop

--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

On Sunday, May 7, 2023 at 11:05:06 AM UTC-5, Scott Lurndal wrote:
> MitchAlsup <Mitch...@aol.com> writes:
> >Consider a string of *p++
> > a = *p++;
> > b = *p++;
> > c = *p++;
> ><
> >Here we see the failure of the ++ or -- notation.
> >The LD of b is dependent on the ++ of a
> >The LD of c is dependent on the ++ of b
> >Whereas if the above was written::
> ><
> > a = p[0];
> > b = p[1];
> > c = p[2];
> > p +=3;
> ><
> >Now all three LDs are independent and can issue/execute/retire
> >simultaneously. Also, the add to p is independent, so we took
> >3 "instructions" that were serially dependent and make them into
> >4 instructions that are completely independent in all phases of
> >execution.
> Can the compiler not recogize the first pattern and convert
> it into the second form under the as-if rule?
<
A) the compiler is so allowed
B) once the compiler is doing this, wanting auto{inc,dec} in your
ISA evaporates.

On Sunday, May 7, 2023 at 12:49:24 PM UTC-5, David Brown wrote:
> On 07/05/2023 18:55, John Levine wrote:
> > It appears that Anton Ertl <an...@mips.complang.tuwien.ac.at> said:
> >> PowerPC and ARM A32 is still there. And there's even a new
> >> architecture with auto-increment: ARM A64.
> >
> > I need to take a look.
> >
> >>> I think the increase
> >>> in code density wasn't worth the contortions to ensure that your data
> >>> structures fit the few cases that the autoincrement modes handled.
> >>
> >> Are you thinking of the DSPs that do not have displacement addressing,
> >> but have auto-increment, leading to a number of papers on how the
> >> compiler should arrange the variables to make best use of that?
> >
> > Autoincrement only increments by the size of a single datum so it
> > works for strings and vectors, not for arrays of structures or 2-D
> > arrays. Compare it to the 360's BXLE loop closing instruction which
> > put the stride in a register so it could be whatever you wanted.
> > It also had base+index which the Vax did but the PDP-11 only sort
> > of did if you used absolute addresses instead of a base.
> >
> > On the PDP-11 autoincrement allowed a two instruction string copy loop:
> >
> > c: movb (r1)+,(r2)+
> > bnz c ; loop if the byte wasn't zero
> >
> > but how useful is that now? I don't know.
> >
> Similar instructions would be used for copying memory blocks, and that
> is very useful!
<
Except you are moving blocks 1-byte at a time--which was fine for PDP-11 days
and for the era of 16-bits "was sufficient" addressing.

On Sunday, May 7, 2023 at 12:58:59 PM UTC-5, Thomas Koenig wrote:
> Scott Lurndal <sc...@slp53.sl.home> schrieb:
> > MitchAlsup <Mitch...@aol.com> writes:
> >>Consider a string of *p++
> >> a = *p++;
> >> b = *p++;
> >> c = *p++;
> >><
> >>Here we see the failure of the ++ or -- notation.
> >>The LD of b is dependent on the ++ of a
> >>The LD of c is dependent on the ++ of b
> >>Whereas if the above was written::
> >><
> >> a = p[0];
> >> b = p[1];
> >> c = p[2];
> >> p +=3;
> >><
> >>Now all three LDs are independent and can issue/execute/retire
> >>simultaneously. Also, the add to p is independent, so we took
> >>3 "instructions" that were serially dependent and make them into
> >>4 instructions that are completely independent in all phases of
> >>execution.
> >
> > Can the compiler not recogize the first pattern and convert
> > it into the second form under the as-if rule?
> Of course:
>
> void bar (int a, int b, int c);
>
> void foo (int *p)
> {
> int a, b, c;
> a = *p++;
> b = *p++;
> c = *p++;
> bar (a, b, c);
> }
>
> results in
>
> lw a2,8(a0)
> lw a1,4(a0)
> lw a0,0(a0)
> tail bar
>
> on RISC-V, for example (aarch64 plays games with load double,
> so it's a bit harder to read).
>
> But I believe Mitch was referring to the assembler equivalent, where
> p be held in a register.
>
> Autodecrement and increment is done on 386ff. How do they avoid
> the register dependency of the stack register? Special handling?
> Instruction fusing?
<
They did not--they just "ate" the latency and register conflicts.
But in general, the Great-Big execution window made all those
"go away".

On Sunday, May 7, 2023 at 1:12:10 PM UTC-5, John Levine wrote:
> It appears that David Brown <david...@hesbynett.no> said:
> >> On the PDP-11 autoincrement allowed a two instruction string copy loop:
> >>
> >> c: movb (r1)+,(r2)+
> >> bnz c ; loop if the byte wasn't zero
> >>
> >> but how useful is that now? I don't know.
> >
> >Similar instructions would be used for copying memory blocks, and that
> >is very useful!
> Not really. On modern computers you want to copy in ways that make
> best use of the multiple registers so you're more likely to do a
> sequence of loads followed by a sequence of stores, mabybe with shift
> and mask in between if they're not aligned, then move on to the next
> block. You could use autoincrement but you'll probably get better
> performance with instructions that clearly don't depend on each other
> so they can run in parallel, e.g.
<
Or you can (put into ISA and) use MM (memory to memory move)
<
MM Rcount,Rfrom,Rto
<
And rest assured that HW will simply do the optimal thing for that
implementation {up to 1 cache line per cycle.}
>
> ; r8 is source, r9 is dest
> loop:
> ld r1,0[r8]
> ld r2,8[r8]
> ld r3,16[r8]
> ld r4,24[r8]
> ; shift and mask to align if needed
> st r1,0[r9]
> st r2,8[r9]
> st r3,16[r9]
> st r4,24[r9]
>
> addi r8,#32
> addi r9,#32
> branch if not done to loop
> --
> Regards,
> John Levine, jo...@taugh.com, Primary Perpetrator of "The Internet for Dummies",
> Please consider the environment before reading this e-mail. https://jl.ly

On 5/7/2023 9:55 AM, John Levine wrote:

snip

> Autoincrement only increments by the size of a single datum so it
> works for strings and vectors, not for arrays of structures or 2-D
> arrays. Compare it to the 360's BXLE loop closing instruction which
> put the stride in a register so it could be whatever you wanted.

Or the 1108 which allowed you to specify, with an instruction bit, that
the high order half of an index register is added to the low order half
(which is all that was used for address calculation) after the memory
address is computed.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

Thomas Koenig <tkoenig@netcologne.de> schrieb:

> Autodecrement and increment is done on 386ff. How do they avoid
> the register dependency of the stack register? Special handling?
> Instruction fusing?

Seems like they have a dedicated stack engine for the
purpose. Agner Fog (who else) has a nice explanation at
https://agner.org/optimize/microarchitecture.pdf . Basically,
there is an extra stage in the pipeline for handling stack pointers
and for inserting stack synchronization micro-ops.

That is one level of complexity that address + offset addressing
relative to the stack pointer solves nicely.

On 5/7/2023 7:07 AM, Anton Ertl wrote:
> Marcus <m.delete@this.bitsnbites.eu> writes:
>> Load/store with auto-increment/decrement can reduce the number of
>> instructions in many loops (especially those that mostly iterate over
>> arrays of data).
>
> Yes.
>
> If you do it only for stores, as suggested below, it could be used for
> loops that read from one or more arrays and write to one array, all
> with the same stride, as follows (in pseudo-C-code):
>
> /* read from a and b, write to c */
> da=a-c;
> db=b-c;
> for (...) {
> *c = c[da] * c[db];
> c+=stride;
> }
>
> the "c+=stride" could become the autoincrement of the store.
>

Not all instructions are created equal.

Fewer instructions may not be a win if these instructions would result
in a higher latency.

>> It can also be used in function prologues and epilogues
>> (for push/pop functionality).
>
> Not so great, because it introduces data dependencies between the
> stores that you then have to get rid of if you want to support more
> than one store per cycle. As for the pops, those are loads, and here
> the autoincrement would require an additional write port to the
> register file, as you point out below; plus it would introduce data
> dependencies that you don't want (many cores support more than one
> load per cycle).
>

But, is kinda moot as, say:
MOV.Q R13, @-SP
MOV.Q R12, @-SP
MOV.Q R11, @-SP
MOV.Q R10, @-SP
MOV.Q R9, @-SP
MOV.Q R8, @-SP

Only saves 1 instruction vs, say:
ADD -48, SP
MOV.Q R13, (SP, 40)
MOV.Q R12, (SP, 32)
MOV.Q R11, (SP, 24)
MOV.Q R10, (SP, 16)
MOV.Q R9, (SP, 8)
MOV.Q R8, (SP, 0)

Depending on how it is implemented, the dependency issues on the shared
register could actually make the use of auto-increment slower than the
use of fixed displacement loads/stores (and, if one needs to wait the
whole latency of a load or store for the increment's write-back to
finish, using auto-increment in this way is likely "dead on arrival").

I can also note that an earlier form of BJX2 had PUSH/POP instructions,
but these were removed. Noting the above, it is probably not all that
hard to guess why...

>> The next question is: What flavors should I have?
>>
>> - Post-increment (most common?)
>> - Post-decrement
>> - Pre-increment
>> - Pre-decrement (second most common?)
>>
>> The "pre" variants would possibly add more logic to critical paths (e.g.
>> add more gate delay in the AGU before the address is ready for the
>> memory stage).
>
> You typically have memory-access instructions that include an addition
> in the address computation; in that case pre obviously has no extra
> cost. The cost of the addition can be reduced (eliminated) with a
> technique called sum-addressed memory. OTOH, IA-64 supports only
> memory accesses of an address given in a register, so here the
> architects apparently thought that sum-addressed memory is still too
> slow.
>
> Increment vs. decrement: If your store supports reading two registers
> for address computation (in addition to the data register), you can
> put the stride in a register, making the whole question moot. Even if
> you only support reading one register in addition to the data, you can
> have a sign-extended constant stride, again giving you both increment
> and decrement options. Note that having a store that does not support
> the sum of two registers, but does support autoincrement, and a load
> that supports the sum of two registers as address is means that both
> loads and stores can read two registers and write one register, which
> may be useful for certain microarchitectural approaches.
>

Nothing to add here.

> - anton

On Sunday, May 7, 2023 at 4:27:52 PM UTC-5, BGB wrote:
> On 5/7/2023 7:07 AM, Anton Ertl wrote:
> > Marcus <m.de...@this.bitsnbites.eu> writes:
> >> Load/store with auto-increment/decrement can reduce the number of
> >> instructions in many loops (especially those that mostly iterate over
> >> arrays of data).
> >
> > Yes.
> >
> > If you do it only for stores, as suggested below, it could be used for
> > loops that read from one or more arrays and write to one array, all
> > with the same stride, as follows (in pseudo-C-code):
> >
> > /* read from a and b, write to c */
> > da=a-c;
> > db=b-c;
> > for (...) {
> > *c = c[da] * c[db];
> > c+=stride;
> > }
> >
> > the "c+=stride" could become the autoincrement of the store.
> >
> Not all instructions are created equal.
>
> Fewer instructions may not be a win if these instructions would result
> in a higher latency.
<
But eliminating sequential dependencies is almost always a win
because it directly addresses latency.
<
> >> It can also be used in function prologues and epilogues
> >> (for push/pop functionality).
> >
> > Not so great, because it introduces data dependencies between the
> > stores that you then have to get rid of if you want to support more
> > than one store per cycle. As for the pops, those are loads, and here
> > the autoincrement would require an additional write port to the
> > register file, as you point out below; plus it would introduce data
> > dependencies that you don't want (many cores support more than one
> > load per cycle).
> >
> But, is kinda moot as, say:
> MOV.Q R13, @-SP
> MOV.Q R12, @-SP
> MOV.Q R11, @-SP
> MOV.Q R10, @-SP
> MOV.Q R9, @-SP
> MOV.Q R8, @-SP
>
> Only saves 1 instruction vs, say:
> ADD -48, SP
> MOV.Q R13, (SP, 40)
> MOV.Q R12, (SP, 32)
> MOV.Q R11, (SP, 24)
> MOV.Q R10, (SP, 16)
> MOV.Q R9, (SP, 8)
> MOV.Q R8, (SP, 0)
<
If you actually wanted to save instructions you would::
<
MOV.Q R13:R8,@-SP
<
So the argument of saving 1 instruction becomes moot--you can save 5
instructions.
>
> Depending on how it is implemented, the dependency issues on the shared
> register could actually make the use of auto-increment slower than the
> use of fixed displacement loads/stores (and, if one needs to wait the
> whole latency of a load or store for the increment's write-back to
> finish, using auto-increment in this way is likely "dead on arrival").
>
>
> I can also note that an earlier form of BJX2 had PUSH/POP instructions,
> but these were removed. Noting the above, it is probably not all that
> hard to guess why...
> >> The next question is: What flavors should I have?
> >>
> >> - Post-increment (most common?)
> >> - Post-decrement
> >> - Pre-increment
> >> - Pre-decrement (second most common?)
> >>
> >> The "pre" variants would possibly add more logic to critical paths (e.g.
> >> add more gate delay in the AGU before the address is ready for the
> >> memory stage).
> >
> > You typically have memory-access instructions that include an addition
> > in the address computation; in that case pre obviously has no extra
> > cost. The cost of the addition can be reduced (eliminated) with a
> > technique called sum-addressed memory. OTOH, IA-64 supports only
> > memory accesses of an address given in a register, so here the
> > architects apparently thought that sum-addressed memory is still too
> > slow.
> >
> > Increment vs. decrement: If your store supports reading two registers
> > for address computation (in addition to the data register), you can
> > put the stride in a register, making the whole question moot. Even if
> > you only support reading one register in addition to the data, you can
> > have a sign-extended constant stride, again giving you both increment
> > and decrement options. Note that having a store that does not support
> > the sum of two registers, but does support autoincrement, and a load
> > that supports the sum of two registers as address is means that both
> > loads and stores can read two registers and write one register, which
> > may be useful for certain microarchitectural approaches.
> >
> Nothing to add here.
>
> > - anton