Extremely CISC instructions

Gordon Henderson gordon+cctalk at drogon.net
Tue Aug 24 09:28:40 CDT 2021


On Tue, 24 Aug 2021, Tom Stepleton via cctalk wrote:

> Hello,
>
> For the sake of illustration to folks who are not necessarily used to
> thinking about what computers do at the machine code level, I'm interested
> in collecting examples of single instructions for any CPU architecture that
> are unusually prolific in one way or another. This request is highly
> underconstrained, so I have to rely on peoples' good taste to determine
> what counts as "interesting" here. Perhaps a whole lot of different kinds
> of work or lots of different resources accessed is what I'm after. I expect
> these kinds of "busy" instructions were more common in architectures that
> are now less common, so perhaps this list is a good place to ask.

Does a virtual machine count?

The BCPL compiler outputs code in few formats, one is called CINTCODE - 
Compact Intermediate Code. This is a bytecode designed to be interpreted 
by a suitable interpreter running on real hardware - in the way other 
bytecode systems work.

It has a switch instruction. Actually, it has 2 - one is a linear search 
and one a binary chop. This is the definition of the binary chop one 
(because linear is too easy)

   SWB filler n dlab K1 L1 . . . Kn Ln

   This instruction is used when the range of case constants is too large for
   SWL to be economical. It performs the jump using a binary chop strategy.
   The quantities n, dlab, K1 to Kn and L1 to Ln are 16 bit half words
   aligned on 16 bit boundaries by the option filler byte. This instruction
   successively tests A with the case constants in the balanced binary tree
   given in the instruction. The tree is structured in a way similar to that
   used in heapsort with the children of the node at position i at positions
   2i and 2i + 1. References to nodes beyond n are treated as null pointers.
   Within this tree, Ki is greater than all case constants in the tree rooted
   at position 2i, and less than those in the tree at 2i + 1. The search
   starts at position 1 and continues until a matching case constant is found
   or a null pointer is reached. If A is equal to some Ki then PC is set
   using the resolving half word Li , otherwise it uses the resolving half
   word dlab to jump to the default label. See Section 9.1.3 for details on
   how resolving half words are interpreted.

Obviously it needs the compiler to output the right stuff, but there it is 
and I won't embarass myself with my implementation of it in 65c816 
assembly code..

Gordon


More information about the cctalk mailing list