The Wheeler Jump.

Professor Brailsford, one of the original ARM processor architects, tells the history of how computers did subroutine calls before we had link registers or stacks and CALL, RTS, PUSH and POP instructions.

It was done with self-modifying code. Does that sound familiar?

Which he explains is "really bad". Little does he know...



«1

Comments

  • 49 Comments sorted by Date Added Votes
  • I saw that and immediately thought of PASM. The good news for the Propeller chip is that reentrant code isn't a big consideration with the limited amount of cog RAM.
  • Yup. Self-modifying code was not invented by the Propeller. It was just resurrected from the dead. Whether that is good or bad you can decide for yourself. One difference though is that PASM code *does* store the return address in a register. It's just that the register holds a JMP instruction since the Propeller executes its code from registers.
  • Heater.Heater. Posts: 20,220
    edited February 7 Vote Up0Vote Down
    David Betz,
    One difference though is that PASM code *does* store the return address in a register.
    Indeed it does.

    It puts the return address into the JMP at the end of the subroutine. In that respect it does what the Wheeler Jump does automatically. Rather than having to code it yourself.

    That's a bit different from the idea of a LINK register and very different from the modern day idea of automatically pushing return addresses to a stack.

    The Propeller confuses the discussion because it executes code from it's registers. I've never worked with any other processor that does that. Is there another example of such a thing out there ?

    But as Mel said "What use is a program that cannot modify its own code?"

    See "The Story of Mel". Discussed on this forum and all over the net.

  • Heater. wrote: »
    The Propeller confuses the discussion because it executes code from it's registers. I've never worked with any other processor that does that. Is there another example of such a thing out there ?
    The PDP-10 could do that but only for very short sections of code since it only had 16 registers.

  • Interesting. I have to check that out.

    The only other machine I know that could execute code from it's registers was the TI TMS9900.

    Basically because it did not have any registers internally. Ony a program counter, status register, and workspace pointer.

    The last of which pointed to a location in external RAM where it regarded 16 words as being it's general purpose registers.

    So basically you could execute code from, and/or modify, external RAM space, that was also considered to be registers.

    Chaos !


  • The Norsk Data ND-10 and ND-100 16--bit minis could execute single instructions from a register via an explicit "execute instruction" instruction. It was mostly used in CPU test programs, but was occasionally useful elsewhere also.
  • The Friden/Singer/ICL System Ten and the later ICL System 25 could be said to effectively run from register space, because there were no registers in the sense of what we think of in the propeller.
    There were three special locations in each cores own (partition) memory that could perform indexing within an instruction.

    Instructions were very much like the propeller - dual operand but reversed. It simulated multi-core by hardware time slicing, where each core had its' own memory (partition) and also shared (common) memory space. Code could run from both.

    My Prop boards: P8XBlade2, RamBlade, CpuBlade, TriBlade
    Prop OS (also see Sphinx, PropDos, PropCmd, Spinix)
    Website: www.clusos.com
    Prop Tools (Index) , Emulators (Index) , ZiCog (Z80)
  • Tor,

    Hmm... an "execute instruction" instruction. That is kind of meta. Weird.

    Could the "execute instruction" instruction execute the "execute instruction" instruction ?

  • Heater. wrote: »
    Tor,

    Hmm... an "execute instruction" instruction. That is kind of meta. Weird.

    Could the "execute instruction" instruction execute the "execute instruction" instruction ?
    The PDP-10 also had an EXEC instruction. I'm not sure what happened if an EXEC executed another EXEC. The PDP-10 could also do multiple levels of indirect in a single instruction. I'm not sure how that worked though and I don't think I have any of my PDP-10 manuals anymore.
  • Heater. wrote: »
    Could the "execute instruction" instruction execute the "execute instruction" instruction ?
    No, that was/is (I should test on my own hardware) forbidden: http://www.ndwiki.org/wiki/EXR
    (But I'm tempted to change my emulator to allow it.. just to see what's possible)

  • David BetzDavid Betz Posts: 11,699
    edited February 8 Vote Up0Vote Down
    Here is how the PDP-10 does it. I had forgotten that not only could you have multiple levels of indirect, you could also specify an index register at each level. I used this to look up values in a two-dimensional array with only a single instruction.
    Effective Address Calculation

    All instructions without exception calculate an "effective address". The effective address gets its name because it is usually used as the address of an operand in memory. Depending on the instruction, that operand might be read, written or both. For some instructions, called "immediate" instructions, the effective address is not used to address memory; it is used directly, as a number, in the operation. For example, the ADD instruction uses the effective address as the address of a location in memory, and uses the contents of that location in the addition. The ADDI instruction (Add Immediate) uses the effective address itself as the number to add.
    The effective address computation uses three fields of the instruction word: the 18-bit address field (Y), the index field (X), and the indirect bit (I). The result is an 18-bit effective address.

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

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

    The I bit specifies indirect addressing. If it is 1, then the result of the previous steps (Address field, or address field plus index quantity) is used as the address of an "indirect word". From the contents of this indirect word, a new address field Y, index field X and indirect bit I are obtained. Then the process starts from the beginning. If the I bit in the indirect word is 1, a second indirect word is eventually fetched. Indirection can happen any number of times, and only stops when an indirect word has 0 in its I bit.

    The result of the effective address calculation may be thought of as an instruction word where bits 0:12 are copied from the original instruction, bits 13:17 are zero, and 18:35 contain the effective address.

    The effective address computation is described by the following program. MA means memory address. PC means program counter. C(MA) means contents of the word addressed by MA.
    IFETCH: MA <- PC
            OP <- Bits  0:8  of C(MA);
            AC <- Bits  9:12 of C(MA);
    EACOMP: I  <- Bit  13    of C(MA);
            X  <- Bits 14:17 of C(MA);
            Y  <- Bits 18:35 of C(MA);
            E  <- Y;
            IF NOT(X=0) then E <- E+C(X);
            IF I=0 then go to done;
            MA <- E;
            GO TO EACOMP;
    DONE:
    
  • Heater. wrote: »
    Tor,

    Hmm... an "execute instruction" instruction. That is kind of meta. Weird.

    Could the "execute instruction" instruction execute the "execute instruction" instruction ?

    Heater,

    The System/360 (and 370, etc.) had an EX instruction):

    https://en.wikibooks.org/wiki/360_Assembly/360_Instructions/EX

    And trying to execute an Execute instruction caused an Execute instruction.

    BTW, the IBM 1130/1800 also used self-modifying code.

    Walter
    Tulsa, OK

    My OBEX objects:
    AGEL: Another Google Earth Logger
    DHT11 Sensor

    I didn't do it... and I promise not to do it again!
  • wmosscrop wrote: »
    [BTW, the IBM 1130/1800 also used self-modifying code.
    As did the PDP-8. It stored the return address of a subroutine at the beginning of the subroutine before the first instruction. A subroutine would end with a jump indirect to the subroutine label.
  • wmosscrop wrote:
    BTW, the IBM 1130/1800 also used self-modifying code.
    That's the machine I cut my programming teeth on. As in the PDP-8, a CALL pseudo-op would do a long BSI (branch-and-store-instruction-address) to the address stored in the word following the BSI. The address of two words past the BSI would be stored at the branch target and control would be passed to one word after that. An 1130 subroutine would look like this:
    SUBR    DC        *-*
            ...
            BR    I   SUBR
    

    "DC" stands for "define constant," and the "*-*" is just the location pointer minus the location pointer, IOW zero. It's just a visual indication that something will be written there, similar to (and the inspiration for) PASM's use of "0-0" . The "return" instruction is just an indirect branch through the address placed in SUBR.

    Another convention used by the 1130 was to place parameter addresses in DCs immediately following the CALL, viz:
            CALL        SUBR
            DC          PAR1_ADDR
            DC          PAR2_ADDR
    

    SUBR would access the parameters via the DC above its entry point and adjust the return address accordingly. This same technique could be employed in PASM!

    The 1130 also used a LIBF call to access frequently-called subroutines through a local transfer table. This enabled indexed BSIs that required only one word of storage, compared to the two required by a CALL.

    -Phil



    “Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery
  • wmosscrop wrote:
    BTW, the IBM 1130/1800 also used self-modifying code.
    That's the machine I cut my programming teeth on.

    As did I.

    In fact, the reason I started working with the Propeller was to create an 1130 emulator.

    It's easy (and already exists) to do it on a PC with gigs of ram and disk space.

    It's much more challenging to emulate a 16K (8K words) machine in 32K of ram.

    I thought it would take 6 months. It was more like 6 years before I really got it working as it should. The rule about rounding up to the next unit when estimating certainly applied here.

    Walter
    Tulsa, OK

    My OBEX objects:
    AGEL: Another Google Earth Logger
    DHT11 Sensor

    I didn't do it... and I promise not to do it again!
  • Scientific Data Systems 900 series and 9300 all had an EXUcute instruction as well as multi-level indirect addressing. They also stored the return address for subroutines in the instruction stream.
    Re-inventing the wheel is not a waste of time if, when you are done, you understand why it is round.
    Cool, CA, USA 95614
  • Little did I know when I posted this that there had been so many ways to create a GOTO and "GOBACK" subroutine call mechanism implemented.

    Thanks all.

    I'm kind of intrigued by Phils suggestion of IBM 1130 style parameter passing in PASM.

    Has anyone ever done such a thing in PASM? Is there an advantage to doing that in some cases?

    I have to think that though a bit...


  • An EXU that pointed to itself or an indirect address that pointed to itself broke the SDS 910 and got you laughed at. I have first hand knowledge.
    Re-inventing the wheel is not a waste of time if, when you are done, you understand why it is round.
    Cool, CA, USA 95614
  • Tor wrote: »
    Heater. wrote: »
    Could the "execute instruction" instruction execute the "execute instruction" instruction ?
    No, that was/is (I should test on my own hardware) forbidden: http://www.ndwiki.org/wiki/EXR
    (But I'm tempted to change my emulator to allow it.. just to see what's possible)
    This would be replaced by another instruction: "execute programmer".

    This reminds me of an old article in "Datamation" (IRC after 40 years) with a list of crazy CPU instructions like: execute invalid operation, execute ignorant operator
    --
    Reinhardt
  • Tor wrote: »
    Heater. wrote: »
    Could the "execute instruction" instruction execute the "execute instruction" instruction ?
    No, that was/is (I should test on my own hardware) forbidden: http://www.ndwiki.org/wiki/EXR
    (But I'm tempted to change my emulator to allow it.. just to see what's possible)
    Thinking about this for a second I realize it would be pretty useless to allow it. Bits 3-5 of the EXR instruction is used to identify the register with the instruction to execute. So, we could have:
    1) The register contains another EXR instruction, with bits 3-5 of that one also pointing to a register
    2) If that register is the same as for the original EXR instruction you would just have an infinite loop
    3) If that register is different from the one in the original, the original could just have pointed to the 'final' register in the first place. There's nothing at all to gain in doing this via a second (or third) EXR.
    So instead the architecture traps an attempt to execute an EXR via an an EXR, as it's pointless to do so anyway.

    This is very different from the infinite indirection addressing scheme of the PDP-10 that David described, which is actually useful for some stuff.

  • So bits 3-5 of the EXR instruction are a "program counter" where the "program" is in the registers rather than RAM. An EXR could jump to another EXR in different register, which can jump to another...

    Now if only they had added some other operations, ADD, SUB, etc that executed from registers then they would have had a Propeller architecture!

  • Have you heard about the BCF instruction?

    Branch and Catch Fire

    Cannot recall which computer this was attributed to... so long ago now
    My Prop boards: P8XBlade2, RamBlade, CpuBlade, TriBlade
    Prop OS (also see Sphinx, PropDos, PropCmd, Spinix)
    Website: www.clusos.com
    Prop Tools (Index) , Emulators (Index) , ZiCog (Z80)
  • Cluso99 wrote: »
    Have you heard about the BCF instruction?

    Branch and Catch Fire

    Cannot recall which computer this was attributed to... so long ago now

    Not sure which one it was either but I think it might also be the one that used special write-only memory.


    Tachyon Forth - compact, fast, forthwright and interactive
    useforthlogo-s.png
    Tachyon Forth News Blog
    TACHYON DEMONSTRATOR
    Brisbane, Australia
  • Cluso99 wrote: »
    Have you heard about the BCF instruction?

    Branch and Catch Fire

    Cannot recall which computer this was attributed to... so long ago now
    Almost..
    https://en.wikipedia.org/wiki/Halt_and_Catch_Fire

  • The Motorola 6809 had a SEX instruction.

    School boy snickers...

  • Not so uncommon, that..
    The aforementioned ND line of computers had one, 'Set EXtended address mode', and its partner was REX, 'Reset EXtended address mode'
  • Heater. wrote: »
    The Motorola 6809 had a SEX instruction.

    School boy snickers...
    it always gave us a laugh while learning the 6809 at college
    Tony
  • Tor,

    That is "SEX" as in "Sign Extend".
  • Yes, in the 6809. On the ND line it was 'set extended address mode'. I suspect there are other architectures out there with a similar mnemomic, possibly with other meanings than these two.
  • I did not mean to imply that Sign Extend was the only meaning of the SEX mnemonic in various assemblers over the years.

    There is nothing like modern day assembler instructions though. How about this from ARM?

    LDMIAEQ SP!, {R4-R7, PC}

    Or this from Intel?

    VZEROUPPERS

    Obvious ha?

Sign In or Register to comment.