4 ms·

Subroutines in MIX are called using self-modifying code

20 points by deanmen 12y ago

falava 12y ago
Quoting Donald Knuth from MMIX 2009 [1] (the revision of the MIX architecture): "And ouch, the standard subroutine calling convention of MIX is irrevocably based on self-modifying instructions! Decimal arithmetic and self-modifying code were popular in 1962, but they sure have disappeared quickly as machines have gotten bigger and faster." [1] http://www-cs-faculty.stanford.edu/~uno/mmix.html http://www-cs-faculty.stanford.edu/~uno/mmix.html
mmagin 12y ago
Ironically, I was just learning this morning how it's done on the PDP-8, which has a disturbingly similar flavor. http://en.wikipedia.org/wiki/PDP-8#Subroutines http://en.wikipedia.org/wiki/PDP-8#Subroutines
userbinator 12y ago
It's worth noting that JIT compilation techniques are also an extremely advanced form of self-modifying code.
- Dylan16807 12y ago
  In a sense, yes, but the basic flow of a JIT is write-once, and it's logically an external process from the code being modified.
kps 12y ago
Many early machines did this, often using a special form of store instruction that only modified the target address part of an instruction word. EDSAC, on which David Wheeler invented the subroutine call, had no such instruction, and did it like this (using a modern pseudo-assembler syntax, not the original): address instruction comment ------- ----------------- --------- m - 1. clear accumulator m. add from m # Load the 'add from m' instruction itself # (which contains its own address) into # the accumulator. m + 1. jump to s # Jump to the subroutine. m + 2. … # Control will return here. ⋮ s. add from 3 # Add a magic constant (kept in location 3) # to the accumulator (which contains the # 'add from m' instruction from m) resulting # in a 'jump to m+2' instruction. s+1. store to r # Store the 'jump to m+2' instruction at the # end of the subroutine. ⋮ # Subroutine body. r. (anything) # ‘Return’ jump stored here.
pcwalton 12y ago
This approach doesn't work with recursive functions, of course. The chapter notes this: "Reentrant routines are useful in relatively rare circumstances." Oh, how times have changed…
abecedarius 12y ago
Ken Thompson's regular-expression matcher also worked this way. It used two arrays of jump instructions: one jump for each current NFA state, jumping into the machine code that had been compiled for the regex. These jumps were actually calls using self-modifying code as in the OP (but for IBM 709 instead of MIX). But the new wrinkle was, it also wrote more jump instructions into the other array, for the next-state set of the NFA matcher. Unlike the MIX, the IBM 709 had a jump-through-register instruction, so self-modifying code wasn't necessary. I found that Thompson's code could've been more compact and about as fast (sometimes faster, sometimes slower) using such indirect jumps only, at the cost of needing to use all of the registers.
- abecedarius 12y ago
  (The compiled code for an NFA state could append jump instructions to the current state set as well as the next-state set, to implement the | operator. Just noting this for completeness.)

20 points by deanmen 12y ago

Quoting Donald Knuth from MMIX 2009 [1] (the revision of the MIX architecture): "And ouch, the standard subroutine calling convention of MIX is irrevocably based on self-modifying instructions! Decimal arithmetic and self-modifying code were popular in 1962, but they sure have disappeared quickly as machines have gotten bigger and faster." [1] http://www-cs-faculty.stanford.edu/~uno/mmix.html http://www-cs-faculty.stanford.edu/~uno/mmix.html

mmagin 12y ago

Ironically, I was just learning this morning how it's done on the PDP-8, which has a disturbingly similar flavor. http://en.wikipedia.org/wiki/PDP-8#Subroutines http://en.wikipedia.org/wiki/PDP-8#Subroutines

userbinator 12y ago

It's worth noting that JIT compilation techniques are also an extremely advanced form of self-modifying code.

Dylan16807 12y ago
In a sense, yes, but the basic flow of a JIT is write-once, and it's logically an external process from the code being modified.

kps 12y ago

Many early machines did this, often using a special form of store instruction that only modified the target address part of an instruction word. EDSAC, on which David Wheeler invented the subroutine call, had no such instruction, and did it like this (using a modern pseudo-assembler syntax, not the original): address instruction comment ------- ----------------- --------- m - 1. clear accumulator m. add from m # Load the 'add from m' instruction itself # (which contains its own address) into # the accumulator. m + 1. jump to s # Jump to the subroutine. m + 2. … # Control will return here. ⋮ s. add from 3 # Add a magic constant (kept in location 3) # to the accumulator (which contains the # 'add from m' instruction from m) resulting # in a 'jump to m+2' instruction. s+1. store to r # Store the 'jump to m+2' instruction at the # end of the subroutine. ⋮ # Subroutine body. r. (anything) # ‘Return’ jump stored here.

pcwalton 12y ago

This approach doesn't work with recursive functions, of course. The chapter notes this: "Reentrant routines are useful in relatively rare circumstances." Oh, how times have changed…

abecedarius 12y ago

Ken Thompson's regular-expression matcher also worked this way. It used two arrays of jump instructions: one jump for each current NFA state, jumping into the machine code that had been compiled for the regex. These jumps were actually calls using self-modifying code as in the OP (but for IBM 709 instead of MIX). But the new wrinkle was, it also wrote more jump instructions into the other array, for the next-state set of the NFA matcher. Unlike the MIX, the IBM 709 had a jump-through-register instruction, so self-modifying code wasn't necessary. I found that Thompson's code could've been more compact and about as fast (sometimes faster, sometimes slower) using such indirect jumps only, at the cost of needing to use all of the registers.

abecedarius 12y ago
(The compiled code for an NFA state could append jump instructions to the current state set as well as the next-state set, to implement the | operator. Just noting this for completeness.)