10

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?

  • I don't know if it had a mnemonic name on the PDP-11, but the register for a similar kind of stack frame linkage is usually called base pointer (BP) or frame pointer (FP). Using an executable instruction during return is certainly predated by very early implementations of subroutines which modify a JMP (not on the stack, but e.g. directly before the subroutine) to do the return. Modification of instructions in memory was common long before CPUs with a specific stack. – dirkt Jul 19 '18 at 19:43
  • Are you sure you got the MARK semantics correct? I am pretty sure it was not used to not signal "there's stuff on the stack", but rather to put the parameters into the program space following the JSR and have RTS return to n words beyond. – tofro Jul 19 '18 at 19:47
  • @tofro Do you see any mistakes in my retyping of the linked PDP-11 instuction set manual? – Leo B. Jul 19 '18 at 20:03
  • No - but I have seen another explanation - will try and find it. – tofro Jul 19 '18 at 20:04
  • 1
    All I can say is that when I was taught PDP-11 MACRO, we were not taught this. Not for our code, nor for the exercises for when were wrote routines to be called by Fortran. – Will Hartung Jul 19 '18 at 22:53
6

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

  • 1
    Also note that the former allows r5 to be used as a general purpose register, leaving the program with 6 gp regs; whereas the mark version leaves the program with only 5 gp regs, which is a significant difference especially for early compilers whose register allocation wasn't that good, and that also shared the registers with the user program via the register keyword for special local variables in C. – Erik Eidt Jul 20 '18 at 15:53
  • My original thought was that as MARK and SOB weren't in the initial instruction set, programming practice using that initial instruction set had shown that these instructions would be beneficial. That proved to be correct for SOB but apparently wrong for MARK. Thus my question: how did that happen? Re x86, ENTER and LEAVE were at least used by production compilers for quite a while. – Leo B. Jul 20 '18 at 17:01
  • @ErikEidt Shouldn't it be "5 gp regs" and "4 gp regs" resp.? – Leo B. Jul 20 '18 at 19:31
  • 3
    ENTER was always slower than its equivalent instructions, so it was seldom used. LEAVE though was as fast or faster and always shorter so it was and continues to be used by compilers. – Ross Ridge Jul 20 '18 at 21:12
  • 1
    @LeoB. Don't know how PDP-11 compilers did it, but a frame pointer can be avoided (so as to rely solely on the sp) by evaluating & pushing function arguments onto the stack in reverse order, namely right to left rather than the more obvious (and possibly desired) left to right. C allows an implementation to do this since it doesn't prescribe the order of evaluation of operands (e.g. the parameters separated by the argument separator ","). (There are of course, still practical concerns of language interoperability on the given platform). – Erik Eidt Jul 20 '18 at 23:18
-1

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.

  • 1
    I don't see it used for function calls in UNIX V6 when I compile a sample Fortran program using fc. – Leo B. Jul 31 '18 at 2:33
  • Sorry - I meant the DEC Fortran compiler for PDP-11. Probably the F4P implementation. – dave Aug 1 '18 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.