What is the history of the PDP-11 MARK instruction?

Question

The PDP-11 MARK instruction was intended to be used as part of the standard PDP-11 subroutine return convention. MARK facilitated the stack clean up procedures involved in subroutine exit.

To use it, the caller would put the MARK instruction on the stack:

MOV R5,-(SP)        ;place old R5 on stack
MOV P1,-(SP)        ;place N parameters
MOV P2,-(SP)        ;on the stack to be
                    ;used there by the
                    ;subroutine
MOV PN,-(SP)
MOV #MARKN,-(SP)    ;places the instruction
                    ;MARK N on the stack
MOV SP,R5           ;set up address at MARK N instruction
JSR PC,SUB          ;jump to subroutine

At this point the stack is as follows:

OLD R5
P1
...
PN
MARK N
OLD PC

The subroutine would execute normally and return using the RTS R5 instruction. This causes the contents of R5 to be placed in the PC which then results in the execution of the instruction MARK N. The contents of the old PC are placed in R5.

MARK N causes: (1) the stack pointer to be adjusted to point to the old R5 value; (2) the value now in R5 (the old PC) to be placed on the PC; and (3) contents of the old R5 to be popped into R5 thus completing the return from subroutine.

The MARK instruction seems unique in several aspects:

• It appears to be the only PDP-11 instruction which used the register R5 implicitly. Thus, similarly to the PC (R7) and SP(R6), R5 should have had a mnemonic name. Had it?
• It can only be used meaningfully when put on the stack (Now we know that an executable stack is a bad idea, but that was then).

From my recollection, the PDP-11 C/UNIX calling conventions did not use the MARK instruction; calling special subroutines CSAV/CRET instead.

In what PDP-11 OS or programming environment was it actually used?

Were there other instruction set architectures with instructions designed specifically for use on the stack? Is it known who came up with the idea?

Answer 1

Partial answer:

If you compare the PDP-11 calling convention using a stack as described e.g. here

   ! parameters passed on stack
       ...
       mov   parm1,-(sp)
       mov   parm2,-(sp)
       jsr   pc,subr2
       add   #4,sp       ! adjust stack to remove parameters
       ...

   ! subroutine called with parameters on stack
   subr2:
       mov   r1,-(sp)   ! save r1 contents on stack
       ...
       mov   (sp)+,r1   ! restore r1 contents from stack
       rts   pc         ! return to instruction following jsr

with the one from the manual which makes use of mark

   ! caller
       mov   r5,-(sp)
       mov   parm1,-(sp)
       mov   parm2,-(sp)
       mov   #mark2,-(sp)
       mov   sp,r5
       jsr   pc,subr

   ! callee
   subr:
       mov   r1,-(sp)
       ...
       mov   (sp)+,r1
       rts   r5

one can see that the use of mark is actually less efficient (three commands instead of just one) than just adjusting sp after the call. If you add to this that, as remarked in the report by Ritchie and Johnson, there are

special short instructions on the PDP-11 that are used to bump the sp by two or four bytes; these instructions [...] apply [...] to procedures of one and two arguments.

(and they also mention an improvement with a slightly different calling convention), then the conclusion is that mark was something the designers of the PDP-11 dreamed up before fully understanding stack-based calling conventions (other PDPs like the PDP-8 didn't use a stack, and stored the PC in front of the subroutine...), and mark probably was never used in practice.

Another indication for this is that there are PDP-11 models that don't implement this instruction, and neither does the VAX in PDP-11 compatibility mode.

As an aside: On the x86 there was a similar development, when the ENTER and LEAVE instructions fell out of favour and where replaced by manipulating SP directly (in various ways).

Answer 2

I've seen claims by many, that MARK instruction has been borrowed from, no pun intended, Burroughs large systems, to make porting of UCSD Pascal p-System easier and more straightforward. As the chronology goes:

•1974 Pascal is running on the Burroughs B6700 at UCSD
•1976 UCSD Pascal is running on a Terak microcomputer.

I tried to investigate into this subject a little, and found out that there's a lot of reference between PDP-11 MARK instruction and p-System. Those are - the terminology used in UCSD p-code machine implementation: MP(mark pointer), FP(stack frame pointer) etc... see here. As well as if you take a look at UCSD Pascal I.5 MACRO-11 source code, you'll find pieces like this:

; SHORT LOCAL LOADS...16 OF THEM
 SLDLS:  .IRP    N,<1,2,3,4,5,6,7,10,11,12,13,14,15,16,17,20>
         MOV     <N+N>+MSDLTA(MP),-(SP)
         BR      BACK
         .ENDR

where MSDLTA stands for, apparently, "Mark Stack ...something", and MP being assigned to R5:

 BK = %2
 BASE = %3
 IPC= %4
 MP = %5
 R0 = %0
 R1 = %1
 R2 = %2
 R3 = %3
 R4 = %4
 R5 = %5
 SP = %6
 PC = %7

I'm wondering if it's just a coincidence. Assumingly, the practice of using MARK had even been dropped at some earlier point, but the traces remained. It'd be interesting to see the sources of UCSD p-System I.4 and earlier versions for that matter. Unfortunately they're not opensourced as of yet, if I'm not mistaken.

Answer 3

I vaguely recall that MARK was added for Fortran, but I don't recall my source for this.

As a long-time Macro-11 programmer, both kernel and user modes, I never used MARK.