24

I am studying Assembly programming in general, so I've decided to try and implement a "virtual microprocessor" in software, which has registers, flags and RAM to work with, implemented with variables and arrays. But since I want to simulate only the most basic behavior of any microprocessor, I want to create an assembly language that has only the essential instructions, only those instructions without which it couldn't be useful. I mean, there are assembly languages that can do multiplication and swapping register values, etc, but these operations are not basic because you can implement them using simpler instructions. I don't want to implement instructions like those.

I can imagine a couple of instructions which (I believe) must always be present in any assembly language, such as MOV to move bytes around and JP to send the instruction pointer to another address.

Could you suggest a set of the most basic and essential assembly instructions? Thanks!

Seki
  • 11,135
  • 7
  • 46
  • 70
Fernando Aires Castello
  • 1,203
  • 3
  • 17
  • 23
  • 2
    see http://stackoverflow.com/q/3711443/309483 – Janus Troelsen Oct 31 '12 at 17:37
  • 1
    @CiroSantilli: related but not a duplicate. One-instruction-set computers might be easy to build, but not so much easier that the horrible performance would be worth doing in practice. If you rule out definitions of "useful" like "useful as an example of Turing completeness", and only consider "useful for some real-world purpose with a hardware or VM implementation", then the minimum standard for being *useful* is much higher than "Turing complete" when it comes to assembly language. If your problem is so domain-specific you don't need Turing-completeness, you don't need asm. – Peter Cordes Feb 16 '18 at 02:02
  • @PeterCordes it is true, you are right. I've updated my answer to account for that. – Ciro Santilli OurBigBook.com Feb 16 '18 at 06:55
  • [What is the absolute minimum set of instructions required to build a Turing complete processor](https://softwareengineering.stackexchange.com/q/230538/98103) – phuclv Jun 30 '18 at 13:29

8 Answers8

11

Control structures comprise the basic feature without which there is no language. This means that your language must provide arithmetic operations on two variables; and then allow a program to change the program counter -- that is, to branch -- based on the result of an operation. Very often, the crucial operation is SUB, for subtract one operand from another. And the conditions on which you would allow a branch are:

  1. result is zero;
  2. result is greater than zero;
  3. result is less than zero.
  4. no condition, i.e., branch unconditional

You also need instructions to move data around: LOAD and STORE, say.

These three conditions and their corresponding branches (or skips, which is another way to do it) are necessary for any program. Not only that, but just these three simple operations plus data-moving instructions, are sufficient to do anything in a program except I/O. If you wanted to, and given a cooperating memory organization, you could rewrite Linux using just LOAD, STORE, ADD, SUB, and the three conditional branches.

The PDP-8 was a much more powerful machine than this: it had a rich set of eight instructions, including I/O.

HTH

Pete Wilson
  • 8,610
  • 6
  • 39
  • 51
9

Surprisingly, there is such a thing as a one instruction set computer.

Archagon
  • 2,470
  • 2
  • 25
  • 38
  • 3
    The "processor" in the Apple II floppy drive controller has one 8-bit "instruction" (from a 256-byte memory): Output a specified 4-bit value on 4 control outputs, and use four control inputs along with 4 bits of the instruction to find the 8-bit address of the next instruction. Rather a specialized application, but certainly useful for anyone who ever had to read or write an Apple II floppy. – supercat Nov 14 '12 at 21:48
  • 1
    I'd argue that OIC is not *useful* in practice, even though it's Turing complete. Compiling for that instruction set produces large slow programs. The ease-of-hardware-implementation benefit is too small to make up for how much it sucks. – Peter Cordes Feb 16 '18 at 02:04
  • @PeterCordes the utility of SICs is the pure simplicity of the abstract model itself, not the ease of hardware implementation. You can gradually substitute in more and more layers of software abstraction as you like, creating automatic translation from the abstract to the concrete at each layer. Then, you make the hardware more "abstract" (i.e., introduce instructions that encompass *the equivalent of* multiple SIS instructions in one cycle, for more computation per Hz). So now, you can abandon SIS but have a high-level language that retains the ability to translate to the *lowest* low-level. – iono Jul 27 '22 at 09:41
  • This way, you now have a baseline guarantee that any software you write *will* be compiled and will run identically on any hardware that implements a node on this "tree" of abstractions (where the SIS is the concrete root node, and the leaves are the most abstract / high-level languages). Each branch of the tree represents pre-existing compilation/"down-translation" software that is fully valid for any higher program, and any hardware *or* software that can run that lower language. – iono Jul 27 '22 at 09:48
  • *"that implements a node" -> "that implements an ancestor node" – iono Jul 27 '22 at 10:57
  • @iono: Yes, obviously you can abstract away the low-level details in any *Turing complete* system. But the question is whether the *assembly language* itself is "useful". I'd argue that it's not really useful for writing programs in, only as a theoretical minimum of instruction-set while still providing Turing completeness. Except apparently in special cases like the Apple II floppy controller that supercat mentioned. phuclv's answer also covers the OIC idea but says something useful about it, and about a definition of "useful". I upvoted that one. – Peter Cordes Jul 27 '22 at 15:14
  • @PeterCordes Focusing on the speed achievable in the present using *any* given instruction set or *any* given hardware is missing the point entirely. No-one should ever write any programs for a SIC in SIS language. The very first step should be to climb your way up to the abstract. The benefit of SICs is a practical human benefit, and that is the educational / rhetorical power of being able to show the lowest, simplest (serial) computer possible. x86, even a toy IL are worlds away from SICs. The abstraction has been moved into the hardware itself. That's an important idea SICs communicate – iono Jul 27 '22 at 17:24
  • @iono: Feel free to post an answer explaining the usefulness of SIC in theoretical computer science, or in teaching. This answer doesn't do that, it just says they exist. Creating an SIC simplifies that part, but complicates the higher levels of actually using it, as you say. A good answer would go into such details and tradeoffs, pointing out that it would be too painful to program by hand for more than the simplest things, and probably harder to debug compiler bugs when the sequence of asm instructions for a program is so complex. – Peter Cordes Jul 27 '22 at 17:33
  • @PeterCordes I guess what I'm trying to say is that "it would be too painful to program by hand for more than the simplest things" and "probably harder to debug compiler bugs when the sequence of asm instructions for a program is so complex" applies continuously/recursively to an increasingly abstract infinite series of "assembly"/"machine" languages, which can, themselves, be thought of as human languages. My point is that where we draw the line at "hardware" and "software" is arbitrary. – iono Jul 27 '22 at 17:39
  • @iono: Ok, fair enough, interesting tangent. You could implement a "useful assembly language" like the question is asking for by compiling to a SIC, or perhaps running on hardware with microcode that implements each machine instruction as a sequence of SIC instructions. But the "useful assembly language" (for humans or a simple compiler target) is not the SIC instructions, it's the higher level one humans can make sense of (regardless of how it's implemented). So I still say this answer isn't a good answer to the question asked, regardless of the possibility of a SIC at the bottom layer. – Peter Cordes Jul 27 '22 at 17:51
8

Well, this is a very broad subject. I suppose you need to get familiar with Random Access Machine. I'm not an expert, but it's difficult to tell which instructions should be supported by this very basic microprocessor. For example: Subtraction and multiplication may be simulated by Addition operation. Multiplication is possible if microprocessor supports jumps and conditional instructions and subtraction is possible by adding negative number.

Lukasz
  • 7,572
  • 4
  • 41
  • 50
  • I see. I thought there was a minimum instruction set which any and every assembly language should implement. I'll take a look at the article you suggested. Thanks. – Fernando Aires Castello Feb 24 '12 at 22:43
7

The least instruction set requires no instruction or maybe zero instruction. I don't know if they had come into real devices or not, but the one instruction set computer (OISC) has been implemented and run successfully in carbon nanotubes computers and MAXQ.

In fact x86 can also be used as an OISC architecture because it's possible to do anything with just a single mov because it has been proved to be Turing-complete. There's even a compiler named movfuscator to compile valid C code into a program with only MOVs (or only either of XOR, SUB, ADD, XADD, ADC, SBB, AND/OR, PUSH/POP, 1-bit shifts, or CMPXCHG/XCHG). See Why is mov turing complete?

However IMO an architecture should be "fast" enough (or do not require too many instructions like OISC for a task compared to other architectures) to be considered useful.

The most basic instruction types for a computer are data movements, logic/arithmetic operations and branching. For arithmetic operations, just an add/subtract is enough. For logic, we can calculate any functions with only a NOR or NAND, so only one is needed. For jumping, we'll need one jump on "<=" or jump on "<" instruction. Data movements can be emulated by add/sub. Like that, we can use 2 bits to encode 3 opcodes (add, nand, jump on "<=") and leave one for future expansion. But since this has no separate load/store instructions, it must operate directly on large register file instead of memory, or the instructions must have the ability to use memory as operands.

If more speed is needed then some more logic, branching instructions and possibly load/store can be added, increasing the opcode space to 3 bits. The instruction set may be:

  1. load
  2. store
  3. add
  4. and
  5. nor
  6. jump on less than
  7. jump on equal

Left shift can be done with add but right shift is trickier, so you may also want to add a right shift to ease up some common operations

phuclv
  • 37,963
  • 15
  • 156
  • 475
  • 1
    https://en.wikipedia.org/wiki/Little_man_computer is an example of a *very* minimal instruction set (used as a teaching architecture). With add/sub but *not* AND or any other booleans or a right shift, it's very inconvenient to do many things (there are some SO questions where the answer is really horrible compared to what MIPS could do, even without a DIV or MUL instruction). [LC-3](https://en.wikipedia.org/wiki/LC-3#Instruction_set) is a little less crippled, and has booleans as well. – Peter Cordes Feb 16 '18 at 02:28
4

You can survive perfectly well with a minimal instruction set consisting only of SOB: subtract one and branch. Entire programs can and have been written with this.

user207421
  • 305,947
  • 44
  • 307
  • 483
3

Look at commercial implementations

The best answer is likely to look at existing commercial implementations.

Anything that is not commercially sold, is likely to not be useful.

What is the definition of an instruction?

For example, I could make one instruction that implements the unzip algorithm, based on a hardware implementation of unzip, and this would of course be the most efficient machine possible for unzipping.

Would it be commercially appealing however? Unlikely, since that hardware would probably be too specialized to justify the development cost.

But there are much more nuanced cases than this extreme one, and the answer will likely vary with existing competitor technologies and market demand in time to make things even worse.

In the end, "efficient hardware" means:

  • take a set of benchmarks, assign one importance weight for each
  • write optimal software that solves those benchmarks

Possible reasons why very small Turing complete ISAs may be inefficient

  • the few instructions that they do have are very complex, and incur large costs every time they are called, e.g. you cannot do certain pipelining optimizaitons
  • the code density is very small which implies:
    • performance may be bound by instruction fetching
    • not good for embedded devices with small ROM memory

Notable OISC implementations

It would be interesting to analyze those to have a more concrete answer.

movfuscator

https://github.com/xoreaxeaxeax/movfuscator

Toy C compiler for x86 that uses just the mov x86 instructions, showing in a very concrete way that a single instruction suffices.

The Turing completeness seems to have been proven in a paper: https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

subleq

Educational OSIC, previously mentioned at https://stackoverflow.com/a/9439153/895245 but without the name:

See also: https://esolangs.org/wiki/Subleq

See also

https://softwareengineering.stackexchange.com/questions/230538/what-is-the-absolute-minimum-set-of-instructions-required-to-build-a-turing-comp/325501

Ciro Santilli OurBigBook.com
  • 347,512
  • 102
  • 1,199
  • 985
  • There are a whole lot of different instructions hidden behind the "mov" opcode, though. You may as well have a "x86" instruction that means "interpret what follows as an x86 instruction" and then call it a one-instruction computer because it only has the "x86" instruction. – user253751 Feb 15 '18 at 21:32
  • @immibis yes, subleq is theoretically more appealing. The appeal of mov is that you can actually run it. Then comes the discussion of what is the definition of an instruction, which would likely end in Kolmogorov complexity arguments :-) – Ciro Santilli OurBigBook.com Feb 15 '18 at 22:44
  • 1
    It's potentially interesting to consider what could have been useful in the past (when transistor budgets were more limited), or what could be useful for building CPUs out of something other than silicon, or with totally different memory technology. Looking at modern commercial implementations definitely tells us that register machines are king (or at least accumulator machines + some kind of pointer register), although memory-memory architectures existed in the past I think. – Peter Cordes Feb 16 '18 at 07:21
  • @PeterCordes exactly. I like https://stackoverflow.com/a/9439153/895245 mentions PDP. Ping me if you find any others. – Ciro Santilli OurBigBook.com Feb 16 '18 at 09:05
  • 1
    [Lưu Vĩnh Phúc's answer](https://stackoverflow.com/questions/9439001/what-is-the-minimum-instruction-set-required-for-any-assembly-language-to-be-con/19677755#19677755) is nice, too; OISC was actually implemented on carbon nanotubes as a proof of concept. And the rest of the answer is a nice summary of what you typically find in a stripped-down but still *efficiently*-usable instruction-set. – Peter Cordes Feb 16 '18 at 09:11
2

Theoretically, a single instruction computer is possible. However on real hardware, you would need a minimum of 4. Assuming a memory only architecture (no user accessible registers).

MOV mem1 mem2 - copy the contents of memory location mem1 to memory location mem2 leaving mem1 unchanged

NAND mem1 mem2 to mem3- perform a bitwise logical NAND between the data at mem1 and mem2 and write the result to mem3

BITSHIFTR mem1 mem2 mem3- bitshift right the data at mem1 mem2 places and write the output to mem3

JMPcond mem1 mem2 - test the least significant bit at mem1 and if it is true(1) jump to mem2

Now it won't be super fast and it will eat memory bandwidth like crazy, but it can be used to implement a virtual machine with any arbitrary instruction set. Additionally there are certain programming constraints, like the need to program in all starting data, or the very least a memory location with only the LSB set to 1. hardware peripherals will have to use DMA for I/O access, and if implemented on a harvard architecture the program will not have direct access to things like pointers.

K.Nicholas
  • 10,956
  • 4
  • 46
  • 66
Anthony Bachler
  • 224
  • 2
  • 4
1

You may also want to look up Turing Completeness.

http://en.wikipedia.org/wiki/Turing_completeness

http://c2.com/cgi/wiki?TuringComplete

What is Turing Complete?

It means that a language is sufficient to compute anything that can be computed.

Community
  • 1
  • 1
solak
  • 19
  • 2