PDP-10 effective address calculation

Question

How does effective address calculation work on the PDP-10?

My understanding is that the instruction code contains an 18-bit address or offset, one bit for indirect, and a register code that's 4 bits. This probably means that the offset is added to the register, and the sum is the address (or the address of an address, depending on the indirect bit). And since you can't add an offset to R0, I guess that's somehow special cased to encode absolute addresses.

My confusion is about what happens next. It's gotta fetch that word from memory, right? Is that word actually the datum that's treated in whatever way by the instruction? Or is this word again treated in the same way as that 23-bit part of the instruction, adding the offset to a (possibly different) register, and maybe keep going like that?

score 5 · Accepted Answer · edited Jun 18 '20 at 08:29

5

TL;DR: Yes

A (calculated) address (from an instruction) is always used to fetch a word (36 Bit), which, if the I bit was set, is interpreted again the same way - thus allowing indefinite addressing chaining - otherwise used at face value for the operation.

The Long Read:

All instructions always an effective address, usually an operand in memory (*1)

As you already described, the effective address is calculated by using the three address fields of an instruction to calculate an 18 bit effective address (*2):

The indirect bit (I).
The 4 bit index field (X),
The basic 18 bit address field (Y)

If the X field is zero, the effective address is simply the contents of the address field (Y).

If the index field X is nonzero, then it names an accumulator to use as an index register. Any accumulator except 0 can be so used. The lower half of the contents of that register is added to the address field (Y) from the instruction.

A set I bit now specifies indirection. If set the first step is taken as before, but the resulting (18 bit, no overflow), is used to address a word (36 bit that is). Of this word the bits 13..35 (the lower 23 bits) are interpreted exactly as if taken from an instruction

*1 - For immediate instructions, it's not a memory address memory, but used directly, as a operand. Like ANDI, ADDI, MOVEI, etc.

*2 - The whole instruction format is

9 bit OP
4 bit Accumulator
1 bit Indirect
4 bit Index
18 bit Address

edited Jun 18 '20 at 08:29

Community

1

answered Nov 07 '18 at 12:55

Raffzahn

222,541
22
631
918

This means 1) you can not point to 36 bit data 2) linked list traversal might require that specific value(s) is kept in specific register(s) – Omar and Lorraine Nov 07 '18 at 13:01
@Wilson 1) Why not? 2) Why? (and which value?) – Raffzahn Nov 07 '18 at 13:05
because the upper 18 bits of the word overlay the Indirect and Index fields. 2) because with each level of indirection, it's possibly adding an offset to a different register. So it's possible to create a data structure which behaves completely differently depending on register contents.

Omar and Lorraine

Nov 07 '18 at 13:17

@Wilson 1) I fail to see an 'overlay'. That doesn't make sense. The I/X bits are only interpreted in an address word, not in the data word. 2) Well, yes, if you want to use it. Fine. But think about, it would be a extreme special use case. An index register is useful to select variations from a different base. Linked lists i memory are usually not variations, but linked lists - with simple memory addresses as links. Using the X field doesnt make any sense here, or does it. – Raffzahn Nov 07 '18 at 13:22

@Wilson I think I see where you went wrong. An address in an instruction is always an indirect one, as it's pointing to a word. Having the I bit set means that the word it points to is an address word, so it adds an(otehr) level of indirection - which then can have as well the I bit set to add a further layer of indirection and so on. If the I bit is cleared, this stops, and the word pointed to is a data word - without any further interpretation (addressing wise that is). – Raffzahn Nov 07 '18 at 13:38

Oh I see! So I and X are only present in the addresses; the first word to get fetched is always an address, the last word to get fetched is never an address. – Omar and Lorraine Nov 07 '18 at 13:41

@Wilson No, the instruction is always an address word, and every further word is only an address word if the previous had the I bit set. (Immediate instructions always excluded). How else should it ever work? But all of this is (more or less) a philosophical issue, as the technical part is described in the answer. – Raffzahn Nov 07 '18 at 13:43

Well, wikipedia quotes: "MOVEI A,3(C) adds 3 to the 18 lower bits of register C and puts the result in register A, without touching memory." So it doesn't seem to "be" an address (although it probably uses the address generation logic to do the addition). Possible the wiki's wrong, but I find it hard to understand that the instruction is an address so what do "immediate" instructions do with the indirect bit? – Omar and Lorraine Nov 07 '18 at 13:49

And, if there's a loop...? I remember, about forty-ish years ago, trying an experiment in the University computer center that began with the question, "what if it pointed back at itself?" and the instantaneous result was the sound of about fifty terminals printing "^G^G^G Decsystem-20 Not Running." followed by everybody in the room saying "Oh Shit!" in unison. But, I can no longer remember what the "it" was that I pointed back at itself. – Solomon Slow Nov 07 '18 at 15:49

1

@Wilson That's why I did the footnote about immediate - the address generated is the value. No indirection used. The I-bit gets ignored when immediate is used. What else. And regarding the instruction being an address, that's how every CPU with memory addressing works. On a 6502 the second byte of LDA $10 addresses the byte to be loaded, with LDA #$10 it uses the second byte as data (immideate), and LDA ($10) uses the pointer at $10 to load a byte. Looking close you'll find it in the 6502s encoding. The PDP-10 is just way more regular than the 6502 and allows a chain of pointers. – Raffzahn Nov 07 '18 at 21:15

1

@Wilson MOVEI A,3(C) is an immediate instruction. The number is treated as a data value, not an address. It falls under the answer's footnote 1. – JeremyP Nov 08 '18 at 11:08

I don't believe that the indirect bit is ignored for an immediate operand. Effective address computation is independent of opcode. Thus MOVEI A,@3(C) takes the content of accumulator C, adds 3, and uses that as an indirect address to fetch a further word, call it Y. Assuming that Y has the indirect bit clear, then its content is the "effective address". But MOVEI treats its effective address as immediate data, so Y is the value loaded into accumulator A. On the other hand, "indirect immediate" seems like a weird thing to write, and I don't think I ever did so. – dave Nov 13 '18 at 02:19

@dave You're awarem that the Manual states otherwise - with almost the same wording as in footnote 1 :)) – Raffzahn Nov 13 '18 at 03:32

Damn, I can't figure out how to lay out multiline code. But anyway: I checked the manual -and- I wrote code to verify it. Admittedly I ran the code on an simulator and not hardware. Additionally, my memory tells me I was correct. – dave Nov 13 '18 at 03:41

Extracts from 1.6, Effective Address Calculation, 1982 Processor Reference Manual. (1) The calculation outlined above is carried out for every instruction even if it need not address a memory location . (2) But when I is 1, the number determined from bits 14-35 is an indirect address no matter what type of information the instruction requires, and the word retrieved in any step of the calculation contains an indirect address so long as I remains 1. – dave Nov 13 '18 at 03:58

Link to the specific manual I quoted from: http://www.bitsavers.org/pdf/dec/pdp10/1982_ProcRefMan.pdf -- look for section 1.6 – dave Nov 13 '18 at 04:06

Example posted as answer. – dave Nov 13 '18 at 23:17

@dave Except, P.1-26 states clearly: "Many of the instructions that usually reference memory for an operand even have an “immediate” mode in which the result of the effective address calculation is itself used as a half word operand instead of a word taken from the memoiy location it addresses. " – Raffzahn Nov 13 '18 at 23:45

I think we're discussing the proposition that (quote). the I-bit gets ignored when immediate is used. It does not. Effective address computation is always the same, and always uses the I-bit. Ultimately we end up with a so-called effective address E. Now the actual instruction is considered. For memory-referencing instructions, E is used as an address. For other instructions, E is not an address. In the specific case of immediate instructions, E is the actual operand. But that is not a factor in how E is computed and whether the indirect bit is meaningful (it is always meaningful). – dave Nov 13 '18 at 23:56

So: effective address computation proceeds until we fetch a word in which the I-bit is not set. With this word we compute E = Y + content(X). In the non-immediate case, E is the address of the operand. In the immediate case, E I s the operand. At no point did we 'ignore' an indirect bit. – dave Nov 14 '18 at 00:04

@Raffzahn - ah, maybe your initial statement is in error: A (calculated) address (from an instruction) is always used to fetch a word (36 Bit), which, if the I bit was set, is interpreted again the same way. Not so. Consider the simple case, MOVEI 1,2. The effective address E = 2. It is never used to fetch a word, it is used as-is (Acc 1 is set to contain 2). i.e., the only word we read from memory is the instruction itself. The fruitful way to understand this is to consider separately the calculation of E and what the instruction then does with E. – dave Nov 14 '18 at 00:45

@dave Olease read it in whole. the cited sentence is the short version, focused on what has been asked, the special case if immediate instruction is described in footnote 1. Taking items out of context might be of lesser good. Also, as the i bit in your example is not set, no other word (than the already fetched) is fetched - isn't it? – Raffzahn Nov 14 '18 at 00:58

Let us continue this discussion in chat. – dave Nov 14 '18 at 02:21

Raffzahn, if you're going to have a TLDR answer, you might want to specify which question (of the many questions being asked) it applies to. You've actually done that very well in many of your other answers but it's a little unclear here. – Nov 16 '18 at 00:55

@paxdiablo I can only see one and that's the very first line. Isn't it - the others are details tehreof, captured in the long read. – Raffzahn Nov 16 '18 at 01:12

So your contention is that the answer to the question How does effective address calculation work on the PDP-10? is Yes? That seems somehow incongruent :-) – Nov 16 '18 at 02:18

@paxdiablo Oh, I would have assumed you're able to read the whole section, not just the title. But I guess there's always another level. – Raffzahn Nov 16 '18 at 04:14

I can read the whole thing. But the entire point of a TLDR answer is to state you didn't read the whole question, just the title or the first sentence for example. If so, then your answer as it stands doesn't make sense. You would be better off just deleting the TLDR "Yes" bit and just leaving your (excellent, by the way) remainder. However, all I can do is suggest, it's up to you how you want to handle it, if at all. – Nov 16 '18 at 04:24

@paxdiablo Sorry, but I can not see what you're talking about. The TLDR part - wich is the yes as he already describes the workings in the question, so a yes is sufficient for a short answer - PLUS the everything until the divider, which repeats the basic working. That's the whole sense of a TLDR part - to get an answer down to a sentence or not more than a paragraph. So unless you there's an error in the TLDR part which I don't see, your whole comment(s) is/are without substance. I can't help against willingful misinterpretation. – Raffzahn Nov 16 '18 at 04:47

dave · Answer 2 · 2018-11-14T00:13:03.870

Execution of all PDP-10 instructions first involves the computation of an "effective address" E. This computation is identical for all instructions, regardless of how they will use the result, and regardless of whether it's actually going to be used as an address, or used at all. The instruction format contains 3 relevant fields: Y (an 18-bit value), X (a 4-bit index field), and I, the indirect bit.

The term "modified address" is useful here. If the X field is zero, then the modified address is just the value in the Y field. If the X field is non-zero, then it names an accumulator (1 to 15) whose low-half content is added to Y to give the modified address (truncated to 18 bits).

If the I bit is zero, then the effective address E is equal to the modified address. If the I bit is one, then the word of memory (an "indirect word") addressed by the modified address is fetched. This indirect word has Y, X, and I fields that are then subject to the same effective address calculation. The iteration continues until a word with I bit zero is fetched, at which point we exit the computation with an effective address E computed from the Y and X values in this, the last-fetched indirect word.

For instructions that actually reference memory (e.g., MOVE from memory, MOVEM to memory) then E is the address of the operand.

For instructions that don't reference memory (e.g., MOVEI immediate), E may be the actual operand, a mask, a shift count, etc., depending on the instruction. In these cases "effective address" is a misnomer, though note that what the PDP-10 calls "move immediate" is called "load address" on other architectures.

Here is a trivial example I coded up and ran on a simh-emulated PDP-10 to demonstrate indirection. It's an intentionally preposterous example (not realistic).

a: z @b
b: z @c
c: z @d
d: 43 ; '#'

start: movei 1,@a
outchr 1
exit
end start

Note: 'z' is a pseudo-instruction that has opcode zero. It's useful for constructing address words such as this. '@' signifies setting the indirect bit.

The first instruction executed is "move immediate, indirect through location a, into accumulator 1". The I-bit is set in the instruction so we fetch the indirect word from 'a'. But that has a set I-bit so we fetch the indirect word from 'b'. But that has the I-bit set so we fetch the indirect word from 'c'. But that has the I-bit set so we fetch the indirect word from 'd'. That does not have the I-bit set so we're done, and the effective address E will be 43 octal.

Now, the instruction is move-immediate, so E is not really a memory address, it's the actual value. So accumulator 1, the target of the movei, is set to 43 octal.

From there we use a monitor call to output the content of acc 1 interpreted as an ASCII character: 43 octal is hash.

Here's the execution:

.exec foo
LINK: Loading
[LNKXCT FOO execution]
#
EXIT
.

If I had coded the move instruction as 'move 1,@a' (normal move, not move immediate) then the effective address 43 octal would have been used as the address of the operand; we'd have output the low 7 bits of location 43 (whatever might be there) as a character.

In real life I'd probably have written the simple form 'move 1,d' and not have used any indirection.

It is clearly possible to set up infinite loops in effective address calculation. The simplest is:

Z @.

"Dot" is the current location, so the infinitude should be obvious. As far as I recall, Z is not a valid opcode, but that does not matter; the CPU does not get as far as figuring that out. This burns CPU and memory cycles and executes no instructions. However, the sequence is interruptible. When I tried this long ago, the monitor (TOPS-10 6.03) would abort the program after some number of seconds of CPU had been squandered.

PDP-10 effective address calculation

2 Answers2

TL;DR: Yes

The Long Read:

Linked