Shop OBEX P1 Docs P2 Docs Learn Events
The Wheeler Jump. — Parallax Forums

The Wheeler Jump.

Heater.Heater. Posts: 21,230
in Propeller 1
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

  • Martin_HMartin_H Posts: 4,051
    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.
  • David BetzDavid Betz Posts: 14,516
    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: 21,230
    edited 2018-02-07 20:41
    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.

  • David BetzDavid Betz Posts: 14,516
    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.

  • Heater.Heater. Posts: 21,230
    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 !


  • TorTor Posts: 2,010
    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.
  • Cluso99Cluso99 Posts: 18,069
    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.

  • Heater.Heater. Posts: 21,230
    Tor,

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

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

  • David BetzDavid Betz Posts: 14,516
    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.
  • TorTor Posts: 2,010
    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: 14,516
    edited 2018-02-08 13:56
    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:
  • wmosscropwmosscrop Posts: 409
    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
  • David BetzDavid Betz Posts: 14,516
    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.
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 23,514
    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



  • wmosscropwmosscrop Posts: 409
    Phil Pilgrim (PhiPi) wrote: »
    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
  • tomcrawfordtomcrawford Posts: 1,129
    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.
  • Heater.Heater. Posts: 21,230
    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...


  • tomcrawfordtomcrawford Posts: 1,129
    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.
  • rbehmrbehm Posts: 102
    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
  • TorTor Posts: 2,010
    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.

  • Heater.Heater. Posts: 21,230
    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!

  • Cluso99Cluso99 Posts: 18,069
    Have you heard about the BCF instruction?

    Branch and Catch Fire

    Cannot recall which computer this was attributed to... so long ago now
  • Peter JakackiPeter Jakacki Posts: 10,193
    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.


    pdf
    pdf
    25120-bw.pdf
    80K
  • TorTor Posts: 2,010
    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

  • Heater.Heater. Posts: 21,230
    The Motorola 6809 had a SEX instruction.

    School boy snickers...

  • TorTor Posts: 2,010
    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'
  • TonyDTonyD Posts: 210
    Heater. wrote: »
    The Motorola 6809 had a SEX instruction.

    School boy snickers...
    it always gave us a laugh while learning the 6809 at college
  • Heater.Heater. Posts: 21,230
    Tor,

    That is "SEX" as in "Sign Extend".
  • TorTor Posts: 2,010
    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.
  • Heater.Heater. Posts: 21,230
    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.