Some (many?) architectures of the 1960s (earlier? later?) have the
feature that, when loading from an address, if a certain bit in the
word is set, the CPU uses that word as the address to access, and this
repeats until a word without this bit is found. At least that's how I
understand the descriptions of this feature.

The major question I have is why these architectures have this
feature.

The only use I can come up with for the arbitrarily repeated
indirection is the implementation of logic variables in Prolog.
However, Prolog was first implemented in 1970, and it did not become a
big thing until the 1980s (if then), so I doubt that this feature was
implemented for Prolog.

A use for a single indirection is the implementation of the memory
management in the original MacOS: Each dynamically allocated memory
block was referenced only from a single place (its handle), so that
the block could be easily relocated. Only the address of the handle
was freely passed around, and accessing the block then always required
double indirection. MacOS was implemented on the 68000, which did not
have the indirect bit; this demonstrates that the indirect bit is not
necessary for that. Nevertheless, such a usage pattern might be seen
as a reason to add the indirect bit. But is it enough?

Were there any other usage patterns? What happened to them when the
indirect bit went out of fashion?

One other question is how the indirect bit works with stores. How do
you change the first word in the chain, the last one, or any word in
between?

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

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>Some (many?) architectures of the 1960s (earlier? later?) have the
>feature that, when loading from an address, if a certain bit in the
>word is set, the CPU uses that word as the address to access, and this
>repeats until a word without this bit is found. At least that's how I
>understand the descriptions of this feature.

That's essentially accurate. The Burroughs medium systems
operands were described by an operand address that included
an 'address controller'. The address controller, a four-bit
field, specified two characteristics of the address; the
two-bit 'index' field contained the number of the index register
(there were three) to be used when calculating the final
address. The other two bits described how the data at the
final address should be treated by the processor
0b00 Unsigned Numeric Data [UN] (BCD)
0b01 Signed Numeric Data [SN] (BCD, first digit 0b1100 = "+", 0b1101 = '-').
0b10 Unsigned Alphanumeric Data [UA] (EBCDIC)
0b11 Indirect Address [IA]

Consider the operand 053251, this described an unsigned
numeric value starting at the address 53251 with no indexing.

The operand 753251 described an address indexed by IX1
and of the type 'indirect address' which points to another
operand word (potentially resulting in infinite recursion,
which was detected by an internal timer which would terminate
the process when triggered).

The actual operand data type was determined by the
address controller of the first operand that isn't
marked IA.

>
>The major question I have is why these architectures have this
>feature.

Primarily for flexibility in addressing without adding substantial
hardware support.

>
>The only use I can come up with for the arbitrarily repeated
>indirection is the implementation of logic variables in Prolog.

The aforementioned system ran mostly COBOL code (with some BPL;
assemblers weren't generally provided to customers).

>Were there any other usage patterns? What happened to them when the
>indirect bit went out of fashion?

Consider following a linked list to the final element as an
example usage.

The aforementioned system also had a SLL (Search Linked List)
that would test each element for one of several conditions
and terminate the indirection when the condition was true.

>
>One other question is how the indirect bit works with stores. How do
>you change the first word in the chain, the last one, or any word in
>between?

I guess I don't understand the question. It's just a pointer in
a linked list.

According to Anton Ertl <anton@mips.complang.tuwien.ac.at>:
>Some (many?) architectures of the 1960s (earlier? later?) have the
>feature that, when loading from an address, if a certain bit in the
>word is set, the CPU uses that word as the address to access, and this
>repeats until a word without this bit is found. At least that's how I
>understand the descriptions of this feature.

More or less. Indirect addressing was always controlled by a bit in
the instruction. It was more common to have only a single level of
indirect addressing, just controlled by that instruction bit.
Multi-level wasn't much more useful and you had to have a way to break
address loops.

>One other question is how the indirect bit works with stores. How do
>you change the first word in the chain, the last one, or any word in
>between?

The CPU follows the indirect address chain to get the operand address
and then does the operation. On the PDP-10, this stores into the
word that FOO points to, perhaps after multiple indirections:

MOVEM AC,@FOO

while this stores into FOO itself:

MOVEM AC,FOO

>The major question I have is why these architectures have this
>feature.

Let's say you want to add up a list of numbers and your machine
doesn't have any index registers. What else are you going to do?

Indirect addressing was a big improvement over patching the
instructions and index registers were too expensive for small
machines. The IBM 70x mainframes had index registers, the early DEC
PDP series didn't other than the mainframe-esque PDP-6 and -10. The
PDP-11 mini was a complete rethink a decade after the PDP-1 with eight
registers usable for indexing and no indirect addressing.

>Were there any other usage patterns? What happened to them when the
>indirect bit went out of fashion?

They were also useful for argument lists which were invariably in
memory on machines without a lot of registers which was all of them
before S/360 and the PDP-6. On many machines a Fortran subroutine call
would leave the return address in an index register and the addresses
of the arguments were in the words after the call. The routine would
use something like @3(X) to get the third argument. Nobody other than
maybe Lisp cared about reentrant or recursive code, and if the number
of arguments in the call didn't match the number the routine expected
and your program blew up, well, don't do that.

As you suggested, a lot of uses boiled down to providing a fixed
address for something that can move, so instructions could indirect
through that fixed address without having to load it into a register.

For most purposes, index registers do indirection better, and now that
everything has a lot of registers, you can use some of them for the
fixed->movable stuff like the GOT in Unix/linux shared libraries.

--
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

Anton Ertl wrote:

> Some (many?) architectures of the 1960s (earlier? later?) have the
> feature that, when loading from an address, if a certain bit in the
> word is set, the CPU uses that word as the address to access, and this
> repeats until a word without this bit is found. At least that's how I
> understand the descriptions of this feature.

> The major question I have is why these architectures have this
> feature.

Solves the memory access problem {arrays, nested arrays, linked lists,...}
The early machines had "insufficient" address generation means, and used
indirection as a trick to get around their inefficient memory address mode.

> The only use I can come up with for the arbitrarily repeated
> indirection is the implementation of logic variables in Prolog.
> However, Prolog was first implemented in 1970, and it did not become a
> big thing until the 1980s (if then), so I doubt that this feature was
> implemented for Prolog.

Some of the indirection machines had indirection-bit located in the
container at the address generated, others had the indirection in
the address calculation. In the case of the PDP-10 there was a time-
out counter and there were applications that worked fine up to a
particular size, and then simply failed when the indirection watch
dog counter kept "going off".

> A use for a single indirection is the implementation of the memory
> management in the original MacOS: Each dynamically allocated memory
> block was referenced only from a single place (its handle), so that
> the block could be easily relocated. Only the address of the handle
> was freely passed around, and accessing the block then always required
> double indirection. MacOS was implemented on the 68000, which did not
> have the indirect bit; this demonstrates that the indirect bit is not
> necessary for that. Nevertheless, such a usage pattern might be seen
> as a reason to add the indirect bit. But is it enough?

Two things: 1) the indirect bit is insufficient, 2) optimizing compilers
got to the point they were better at dereferencing linked lists than
the indirection machines were. {Reuse and all that rot.}

> Were there any other usage patterns? What happened to them when the
> indirect bit went out of fashion?

Arrays, matrixes, scatter, gather, lists, queues, stacks, arguments,....
We did all sorts of infinite-indirect stuff in asm on the PDP-10 {KI}
when programming at college.

They went out of fashion when compilers got to the point they could
hold the intermediate addresses in registers and short circuit the
amount of indirection needed--improving performance due to accessing
fewer memory locations.

The large register files of RISC spelled their doom.

> One other question is how the indirect bit works with stores. How do
> you change the first word in the chain, the last one, or any word in
> between?

In the machines where the indirection is at the instruction level, this
was simple, in the machines where the indirection was at the target, it
was more difficult.

> - anton

Summary::

First the architects thought registers were expensive.
{Many doubled down by OP-Mem ISAs.}
The architects endowed memory addressing with insufficient capabilities.
{Many to satisfy the OP-Mem and Mem-OP ISA they had imposed upon themselves}
Then they added indirection to make up for insufficient addressing.
And then everyone waited until RISC showed up (1980) before realizing their
error in register counts.
{Along about this time, Compilers started getting good.}

According to MitchAlsup <mitchalsup@aol.com>:
>Some of the indirection machines had indirection-bit located in the
>container at the address generated, others had the indirection in
>the address calculation. In the case of the PDP-10 there was a time-
>out counter and there were applications that worked fine up to a
>particular size, and then simply failed when the indirection watch
>dog counter kept "going off".

No, that's what the GE 635 did, a watchdog timer reset each time it
started a new instruction. The PDP-6 and -10 could take an interrupt
each time it calculated an address and would restart the instruction
when the interrupt returned. This worked because unlike on the 635 the
address calculation didn't change anything. (Well, except for the ILDB
and IDPB instructions that needed the first part done flag. But I
digress.)

You could tell how long the time between clock interrupts was by
making an ever longer indirect address chain and seeing where your
program stalled. It wouldn't crash, it just stalled as the very long
address chain kept being interrupted and restarted. I'm not being
hypothetical here.

>Two things: 1) the indirect bit is insufficient, 2) optimizing compilers
>got to the point they were better at dereferencing linked lists than
>the indirection machines were. {Reuse and all that rot.}

More importantly, index registers are a lot faster than indirect
addressing and at least since the IBM 801, we have good algorithms to
do register scheduling.

>> One other question is how the indirect bit works with stores. How do
>> you change the first word in the chain, the last one, or any word in
>> between?
>
>In the machines where the indirection is at the instruction level, this
>was simple, in the machines where the indirection was at the target, it
>was more difficult.

The indirection was always in the address word(s), not in the target.
It didn't matter if it was a load or a store.

--
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

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:

> Some (many?) architectures of the 1960s (earlier? later?) have the
> feature that, when loading from an address, if a certain bit in the
> word is set, the CPU uses that word as the address to access, and this
> repeats until a word without this bit is found. At least that's how I
> understand the descriptions of this feature.
>
> The major question I have is why these architectures have this
> feature.

I'll hazard a guess that once you've got the indirect bit out in memory,
it's easier to just use the same logic on all memory reads than to only
let it happen once.

According to Joe Pfeiffer <pfeiffer@cs.nmsu.edu>:
>I'll hazard a guess that once you've got the indirect bit out in memory,
>it's easier to just use the same logic on all memory reads than to only
>let it happen once.

That's not how indirect addressing worked.

There was always a bit in the instruction to say to do indirection.

Sometimes that was it, sometimes on machines where the word size was
bigger than the address size, it also looked at some other bit in the
indirect word to see whether to keep going. On the PDP-8, the words
were 12 bits and the addresses were 12 bits so there was no room, they
couldn't have done multilevel indirect if they wanted to.

As several of us noted, multilevel indirection needed something to
break loops, while single level didn't. In my experience, multiple
indirection wasn't very useful, I didn't miss it on the -8, and I
can't recall using it other than as a gimmick on the PDP-10.

--
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 Fri, 29 Dec 2023 17:20:43 +0000, Anton Ertl wrote:

> Some (many?) architectures of the 1960s (earlier? later?) have the
> feature that, when loading from an address, if a certain bit in the word
> is set, the CPU uses that word as the address to access, and this
> repeats until a word without this bit is found. At least that's how I
> understand the descriptions of this feature.
>
> The major question I have is why these architectures have this feature.

No doubt this answer has already been given.

The reason these architectures had that feature was because of a feature
they _didn't_ have: an index register.

So in order to access arrays and stuff like that, instead of doing surgery
on the short address inside an instruction, you can simply store a full
address in a word somewhere that points anywhere you would like.

> One other question is how the indirect bit works with stores. How do
> you change the first word in the chain, the last one, or any word in
> between?

Let's assume we do have an architecture that supports multi-level
indirection. So an instruction word looks like this:

(i)(x)(opcode)(p)(address)

and an address constant looks like this:

(i)(x)(address)

So in an address constant (some architectures that had index registers
kept indirection) you could specify indexing too, but now the address was
longer by the length of the opcode field.

If the address inside an instruction is too short to handle all of memory
(i.e. the word length is less than 24 bits) then you need a "page" bit in
the instruction: 0 means page zero, shared by the whole program, 1 means
the current page - the one the instruction is on.

Let's now say the instruction is a _store_ instruction. Then what? Well,
if the indirect bit is set, it acts like a *load* instruction, to fetch and
load the effective address. It only stores at the point where indirection
ends - where the address is now of the actual location to do the storing
in, rather than the location of the effective address, which must be read,
not written.

John Savard

Quadibloc wrote:

> On Fri, 29 Dec 2023 17:20:43 +0000, Anton Ertl wrote:

>> Some (many?) architectures of the 1960s (earlier? later?) have the
>> feature that, when loading from an address, if a certain bit in the word
>> is set, the CPU uses that word as the address to access, and this
>> repeats until a word without this bit is found. At least that's how I
>> understand the descriptions of this feature.
>>
>> The major question I have is why these architectures have this feature.

> No doubt this answer has already been given.

> The reason these architectures had that feature was because of a feature
> they _didn't_ have: an index register.

This is a better explanation than above. Instead of paying the high price
needed for index registers, they use main memory as their index registers.
{{A lot like building linked lists in FORTRAN 66}}.

> So in order to access arrays and stuff like that, instead of doing surgery
> on the short address inside an instruction, you can simply store a full
> address in a word somewhere that points anywhere you would like.

>> One other question is how the indirect bit works with stores. How do
>> you change the first word in the chain, the last one, or any word in
>> between?

> Let's assume we do have an architecture that supports multi-level
> indirection. So an instruction word looks like this:

> (i)(x)(opcode)(p)(address)

> and an address constant looks like this:

> (i)(x)(address)

> So in an address constant (some architectures that had index registers
> kept indirection) you could specify indexing too, but now the address was
> longer by the length of the opcode field.

> If the address inside an instruction is too short to handle all of memory
> (i.e. the word length is less than 24 bits) then you need a "page" bit in
> the instruction: 0 means page zero, shared by the whole program, 1 means
> the current page - the one the instruction is on.

Going all PDP-8 on us now ??

> Let's now say the instruction is a _store_ instruction. Then what? Well,
> if the indirect bit is set, it acts like a *load* instruction, to fetch and
> load the effective address. It only stores at the point where indirection
> ends - where the address is now of the actual location to do the storing
> in, rather than the location of the effective address, which must be read,
> not written.

> John Savard

On 30/12/2023 23:26, John Levine wrote:
> and I
> can't recall using it other than as a gimmick on the PDP-10.

It's a very long time ago, but I'm sure I do recall seeing it used on a
DECSystem10 for arrays of pointers for indirection.

The fact that 40 years later I can remember the @ being used in
assembler must mean something.

Modern machines don't like wasting space so much. On the '10 an address
pointed to was a 36 bit value with an 18 bit address in it. And the
indirection bit. There was space for things like this.

Andy

MitchAlsup <mitchalsup@aol.com> schrieb:
> Quadibloc wrote:
>
>> On Fri, 29 Dec 2023 17:20:43 +0000, Anton Ertl wrote:
>
>>> Some (many?) architectures of the 1960s (earlier? later?) have the
>>> feature that, when loading from an address, if a certain bit in the word
>>> is set, the CPU uses that word as the address to access, and this
>>> repeats until a word without this bit is found. At least that's how I
>>> understand the descriptions of this feature.
>>>
>>> The major question I have is why these architectures have this feature.
>
>> No doubt this answer has already been given.
>
>> The reason these architectures had that feature was because of a feature
>> they _didn't_ have: an index register.
>
> This is a better explanation than above. Instead of paying the high price
> needed for index registers, they use main memory as their index registers.
> {{A lot like building linked lists in FORTRAN 66}}.

The PDP-10 had both a recursive indirect bit and index registers (aka
memory locations 1 to 15), if I remember the manuals correctly
(I did a bit of reading, but I've never even come close to one of
these machines).

On 12/29/23 2:36 PM, John Levine wrote:
> According to Anton Ertl <anton@mips.complang.tuwien.ac.at>:
>> Some (many?) architectures of the 1960s (earlier? later?) have the
>> feature that, when loading from an address, if a certain bit in the
>> word is set, the CPU uses that word as the address to access, and this
>> repeats until a word without this bit is found.
[snip]
>> Were there any other usage patterns? What happened to them when the
>> indirect bit went out of fashion?
[snip]
> As you suggested, a lot of uses boiled down to providing a fixed
> address for something that can move, so instructions could indirect
> through that fixed address without having to load it into a register.

Paged virtual memory as commonly implemented introduces one level
of indirection at page (rather than word) granularity.
Virtualization systems using nested page tables introduce a second
direction.

Hierarchical/multi-level page tables have multiple layers of
indirection where instead of a page table base pointer pointing to
a complete page table it points to a typically-page-sized array of
address and metadata entries where each entry points to a similar
array eventually reaching the PTE.

Even with page table caching (and workloads that play well with
this kind of virtual memory), this is not free but it can be
"cheap enough". Using large pages for virtual-physical to physical
translation can help a lot. Presumably having an OS bias placement
of its translation table pages into large quasi-pages would help
caching for VPA-to-PA, i.e., many VPAs used by the OS for paging
would be in the same large page (e.g., 2MiB for x86).

(Andy Glew had suggested using larger pages for intermediate nodes
rather than limiting such to the last node in a hierarchical page
table. This has the same level-reducing effect of huge pages that
short-circuit the translation indirection at the end but allows
eviction and permission control at base-page size, with the
consequent larger number of PTEs active if there is spatial
locality at huge page granularity. Such merely assumes that
locality potentially exists at the intermediate nodes rather than
exclusively at the last node. Interestingly, with such a page
table design one might consider having rather small pages; e.g., a
perhaps insane 64-byte base page size (at least for the tables)
would only provide 3 bits per level but each level could be
flattened to provide 6, 9, 12, etc. bits. Such extreme flexibility
may well not make sense, but it seems interesting to me.)

> For most purposes, index registers do indirection better, and now that
> everything has a lot of registers, you can use some of them for the
> fixed->movable stuff like the GOT in Unix/linux shared libraries.

For x86-64 some of the segments can have non-zero bases, so these
provide an additional index register ("indirection").

John Levine <johnl@taugh.com> writes:
>According to Joe Pfeiffer <pfeiffer@cs.nmsu.edu>:
>>I'll hazard a guess that once you've got the indirect bit out in memory,
>>it's easier to just use the same logic on all memory reads than to only
>>let it happen once.
>
>That's not how indirect addressing worked.
>
>There was always a bit in the instruction to say to do indirection.

In our case (B3500 et alia), there was a bit per operand, so a three operand
instruction could have all three addresses indirect. The processor treated
the value at the indirect address as an operand address allowing infinite
recursion (subject to a processor timer in case of loops).

Quadibloc <quadibloc@servername.invalid> writes:
>On Fri, 29 Dec 2023 17:20:43 +0000, Anton Ertl wrote:
>
>> Some (many?) architectures of the 1960s (earlier? later?) have the
>> feature that, when loading from an address, if a certain bit in the word
>> is set, the CPU uses that word as the address to access, and this
>> repeats until a word without this bit is found. At least that's how I
>> understand the descriptions of this feature.
>>
>> The major question I have is why these architectures have this feature.
>
>No doubt this answer has already been given.
>
>The reason these architectures had that feature was because of a feature
>they _didn't_ have: an index register.

Not necessarily true. The B3500 had three index registers (special
locations in memory, not real registers). Later systems in the early
80's added an additional four register-based index registers, but
continued to support indirect addressing.

Paul A. Clayton wrote:

> On 12/29/23 2:36 PM, John Levine wrote:
>> According to Anton Ertl <anton@mips.complang.tuwien.ac.at>:
>>> Some (many?) architectures of the 1960s (earlier? later?) have the
>>> feature that, when loading from an address, if a certain bit in the
>>> word is set, the CPU uses that word as the address to access, and this
>>> repeats until a word without this bit is found.
> [snip]
>>> Were there any other usage patterns? What happened to them when the
>>> indirect bit went out of fashion?
> [snip]
>> As you suggested, a lot of uses boiled down to providing a fixed
>> address for something that can move, so instructions could indirect
>> through that fixed address without having to load it into a register.

> Paged virtual memory as commonly implemented introduces one level
> of indirection at page (rather than word) granularity.
> Virtualization systems using nested page tables introduce a second
> direction.

> Hierarchical/multi-level page tables have multiple layers of
> indirection where instead of a page table base pointer pointing to
> a complete page table it points to a typically-page-sized array of
> address and metadata entries where each entry points to a similar
> array eventually reaching the PTE.

> Even with page table caching (and workloads that play well with
> this kind of virtual memory), this is not free but it can be
> "cheap enough". Using large pages for virtual-physical to physical
> translation can help a lot. Presumably having an OS bias placement
> of its translation table pages into large quasi-pages would help
> caching for VPA-to-PA, i.e., many VPAs used by the OS for paging
> would be in the same large page (e.g., 2MiB for x86).

> (Andy Glew had suggested using larger pages for intermediate nodes
> rather than limiting such to the last node in a hierarchical page
> table.

I had been thinking that since my large-page translation tables have
a count of the number of pages, that when forking off a new GuestOS
that I would allocate the HyperVisor tables as a single 8GB large
page, and when it needs more then switch to a more treeified page
table. This leaves the second level of DRAM translation at 1 very
cacheable and TLB-able PTE--dramatically reducing the table walking
overhead.

A single 8GB page mapping can allow access to one 8192B page up to
1M 8192B pages. Guest OS page tables can map any of these 8192B pages
to any virtual address it desires with permissions it desires.

> This has the same level-reducing effect of huge pages that
> short-circuit the translation indirection at the end but allows
> eviction and permission control at base-page size, with the
> consequent larger number of PTEs active if there is spatial
> locality at huge page granularity. Such merely assumes that
> locality potentially exists at the intermediate nodes rather than
> exclusively at the last node. Interestingly, with such a page
> table design one might consider having rather small pages; e.g., a
> perhaps insane 64-byte base page size (at least for the tables)
> would only provide 3 bits per level but each level could be
> flattened to provide 6, 9, 12, etc. bits. Such extreme flexibility
> may well not make sense, but it seems interesting to me.)

>> For most purposes, index registers do indirection better, and now that
>> everything has a lot of registers, you can use some of them for the
>> fixed->movable stuff like the GOT in Unix/linux shared libraries.

> For x86-64 some of the segments can have non-zero bases, so these
> provide an additional index register ("indirection").

This has more to do with 16 registers being insufficient than indirection
(segmentation) being better.

Thomas Koenig wrote:

> MitchAlsup <mitchalsup@aol.com> schrieb:
>> Quadibloc wrote:
>>
>>> On Fri, 29 Dec 2023 17:20:43 +0000, Anton Ertl wrote:
>>
>>>> Some (many?) architectures of the 1960s (earlier? later?) have the
>>>> feature that, when loading from an address, if a certain bit in the word
>>>> is set, the CPU uses that word as the address to access, and this
>>>> repeats until a word without this bit is found. At least that's how I
>>>> understand the descriptions of this feature.
>>>>
>>>> The major question I have is why these architectures have this feature.
>>
>>> No doubt this answer has already been given.
>>
>>> The reason these architectures had that feature was because of a feature
>>> they _didn't_ have: an index register.
>>
>> This is a better explanation than above. Instead of paying the high price
>> needed for index registers, they use main memory as their index registers.
>> {{A lot like building linked lists in FORTRAN 66}}.

> The PDP-10 had both a recursive indirect bit and index registers (aka
> memory locations 1 to 15), if I remember the manuals correctly
> (I did a bit of reading, but I've never even come close to one of
> these machines).

All of the PDP-10s at CMU had the register upgrade. {2×Ki and 1×Kl}
I believe that most PDP-10 ever sold had the register upgrade.

According to Thomas Koenig <tkoenig@netcologne.de>:
>The PDP-10 had both a recursive indirect bit and index registers (aka
>memory locations 1 to 15), if I remember the manuals correctly
>(I did a bit of reading, but I've never even come close to one of
>these machines).

Yup. Each instruction had an 18 bit address, a four bit index register, and an indirect bit.
It took the address, and added the contents of the right half of the index register if non-zero.
If the indirect bit was off, that was the operand address. If the indirect bit was set, it
fetched the word at that location and did the whole thing over again, including the indexing.

You could in principle create extremely complicated address chanis but
it was so confusing that nobody did.

--
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

John Levine wrote:

> According to Thomas Koenig <tkoenig@netcologne.de>:
>>The PDP-10 had both a recursive indirect bit and index registers (aka
>>memory locations 1 to 15), if I remember the manuals correctly
>>(I did a bit of reading, but I've never even come close to one of
>>these machines).

> Yup. Each instruction had an 18 bit address, a four bit index register, and an indirect bit.
> It took the address, and added the contents of the right half of the index register if non-zero.
> If the indirect bit was off, that was the operand address. If the indirect bit was set, it
> fetched the word at that location and did the whole thing over again, including the indexing.

> You could in principle create extremely complicated address chanis but
> it was so confusing that nobody did.

At CMU is used this a lot for things like symbol table searches.
What I did not use was the index register stuff of the indirection (except
at the first level).

John Levine <johnl@taugh.com> wrote:

: More importantly, index registers are a lot faster than indirect
: addressing and at least since the IBM 801, we have good algorithms to
: do register scheduling.

Once upon a time saving an instruction was a big deal; the 801, and
RISC in general, was possible because memory got much cheaper.
Using index registers costs an extra instrucion for loading the index
register.

Index registers were a scarce resource too (except for the Atlas) so
keeping all your pointers in index registers wasn't a good option
either.

sarr`

sarr.blumson@alum.dartmouth.org wrote:

> John Levine <johnl@taugh.com> wrote:

> : More importantly, index registers are a lot faster than indirect
> : addressing and at least since the IBM 801, we have good algorithms to
> : do register scheduling.

> Once upon a time saving an instruction was a big deal; the 801, and
> RISC in general, was possible because memory got much cheaper.
> Using index registers costs an extra instrucion for loading the index
> register.

Mark Horowitz stated (~1983) MIPS executes 1.5× as many instructions
as VAX and at 6× the frequency for a 4× improvement in performance.

Now, imagine a RISC ISA that only needs 1.1× as many instructions as
VAX with no degradation WRT operating frequency.

> Index registers were a scarce resource too (except for the Atlas) so
> keeping all your pointers in index registers wasn't a good option
> either.

> sarr`

Anton Ertl wrote:
> Some (many?) architectures of the 1960s (earlier? later?) have the
> feature that, when loading from an address, if a certain bit in the
> word is set, the CPU uses that word as the address to access, and this
> repeats until a word without this bit is found. At least that's how I
> understand the descriptions of this feature.
>
> The major question I have is why these architectures have this
> feature.
>
> The only use I can come up with for the arbitrarily repeated
> indirection is the implementation of logic variables in Prolog.
> However, Prolog was first implemented in 1970, and it did not become a
> big thing until the 1980s (if then), so I doubt that this feature was
> implemented for Prolog.
>
> A use for a single indirection is the implementation of the memory
> management in the original MacOS: Each dynamically allocated memory
> block was referenced only from a single place (its handle), so that
> the block could be easily relocated. Only the address of the handle
> was freely passed around, and accessing the block then always required
> double indirection. MacOS was implemented on the 68000, which did not
> have the indirect bit; this demonstrates that the indirect bit is not
> necessary for that. Nevertheless, such a usage pattern might be seen
> as a reason to add the indirect bit. But is it enough?
>
> Were there any other usage patterns? What happened to them when the
> indirect bit went out of fashion?
>
> One other question is how the indirect bit works with stores. How do
> you change the first word in the chain, the last one, or any word in
> between?
>
> - anton

PDP-11 and VAX had multiple address modes with a single level of indirection.
The VAX usage stats from 1984 show about 3% use on SPEC.

DG Nova had infinite indirection - if the Indirect bits was set in the
instruction then in the address register if the msb of the address was zero
then it was the address of the 16-bit data, if the msb of the address was 1
then it was the address of another address, looping until msb = 0.
I don't know how DG used it but, just guessing, because Nova only had
4 registers might be to create a kind of virtual register set in memory.

The best use I have for single level indirection is compilers & linkers.
The compiler emits a variable reference without knowing if it is local
to the linkage unit or imported from a DLL. Linker discovers it is a
DLL export variable and changes the assigned variable to be a pointer
to the imported value that is patched by the loader,
and just flips the Indirect bit on the instruction.

Doing the same thing without address indirection requires inserting
extra LD instructions and having a spare register allocated to the
linker to work with.

According to EricP <ThatWouldBeTelling@thevillage.com>:
>PDP-11 and VAX had multiple address modes with a single level of indirection.
>The VAX usage stats from 1984 show about 3% use on SPEC.

The main place the PDP-11 used indirect addressing was in @(PC)+ which
was the idiom for absolute addressing. It fetched the next word in the
instruction stream as an immediate via (PC)+ and then used it as an
address via indirection. The assembler let you write @#123 to geerate
that address mode and put the 123 in line.

It was also useful for threaded code, where you had a register,
typically R4, pointing at a list of routine addresses and dispatched
with JMP @(R4)+

If you were feeling clever you could do this coroutine switch JSR PC,@(SP)+

That popped the top word off the stack, then pushed the current PC, then jumped
to the address it had popped.

>DG Nova had infinite indirection - if the Indirect bits was set in the
>instruction then in the address register if the msb of the address was zero
>then it was the address of the 16-bit data, if the msb of the address was 1
>then it was the address of another address, looping until msb = 0.
>I don't know how DG used it but, just guessing, because Nova only had
>4 registers might be to create a kind of virtual register set in memory.

My guess is that it was cheap to implement and let them say look, here
is a cool thing that we do and DEC doesn't. I would be surprised if
there were many long indirect chains.

--
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

John Levine wrote:

> According to EricP <ThatWouldBeTelling@thevillage.com>:
>>PDP-11 and VAX had multiple address modes with a single level of indirection.
>>The VAX usage stats from 1984 show about 3% use on SPEC.

> The main place the PDP-11 used indirect addressing was in @(PC)+ which
> was the idiom for absolute addressing. It fetched the next word in the
> instruction stream as an immediate via (PC)+ and then used it as an
> address via indirection. The assembler let you write @#123 to geerate
> that address mode and put the 123 in line.

> It was also useful for threaded code, where you had a register,
> typically R4, pointing at a list of routine addresses and dispatched
> with JMP @(R4)+

> If you were feeling clever you could do this coroutine switch JSR PC,@(SP)+

> That popped the top word off the stack, then pushed the current PC, then jumped
> to the address it had popped.

I used this in a real-timeOS I developed at CMU to deal with laser power control.

Processes (no MMU or protection) would receive control JSR PC,@(SP)+ and
return control with JSR PC,@(SP)+ at which time OS would find the next thing to
do and JSR PC,@(SP)+ all over again. Really light weight context switching.

>>DG Nova had infinite indirection - if the Indirect bits was set in the
>>instruction then in the address register if the msb of the address was zero
>>then it was the address of the 16-bit data, if the msb of the address was 1
>>then it was the address of another address, looping until msb = 0.
>>I don't know how DG used it but, just guessing, because Nova only had
>>4 registers might be to create a kind of virtual register set in memory.

> My guess is that it was cheap to implement and let them say look, here
> is a cool thing that we do and DEC doesn't. I would be surprised if
> there were many long indirect chains.

On Fri, 29 Dec 2023 19:04:56 GMT, Scott Lurndal wrote:

> The [Burroughs] system ran mostly COBOL code (with some BPL;
> assemblers weren't generally provided to customers).

For an interesting reason: privilege protection was enforced in software,
not hardware.

On Thu, 4 Jan 2024 01:36:35 +0000, MitchAlsup wrote:

> Mark Horowitz stated (~1983) MIPS executes 1.5× as many instructions as
> VAX and at 6× the frequency for a 4× improvement in performance.

Mmm, maybe you got the last two multipliers the wrong way round?