What is the minimum number of addressing modes necessary for computation?

Question

In x86 Assembler, given that you have

• Immediate addressing mode for allocating numbers
• Register addressing mode for registers
• Direct addressing mode for memory addresses,

why do you need Indexed and Base Pointer addressing modes? Each could be replaced by a loop as far as I know.

Also Indirect mode doesn't seem to be overly useful either, since you can simply use Direct mode instead to reference the memory address. What is the purpose of first accessing a register which then contains a pointer to a memory address?

In short, which addressing modes are really necessary?

Answer 1

Although in theory 'addressing mode' can be used to refer to the operand type, it's a bit confusing since it doesn't involve an address. The Intel manual uses 'addressing mode' to refer to memory addressing, and I will use this definition.

In assembly, an operand can be :

• An immediate value
• A register
• A value in memory (the operand here is the address)

In the x86 architecture, the "addressing mode" is only for the last type of operands : memory operands (addresses), and refers to the methods available to calculate the addresses. The addressing modes can be summarized in a single configurable addressing mode :

address = REG_base + REG_index*n + offset

REG_base, REG_index, n and offset are all configurable, and can all be omitted (but you need at least one, obviously).

address = offset is called immediate, direct or absolute addressing.
address = REG_base is called register indirect addressing.
address = REG_base + REG_index is called base plus index addressing.
Similarly, you can add an offset (offset) and a scale (n).

Strictly speaking, you only need one mode to do everything : register indirect addressing (address = REG). With that, if you need to access memory, you can calculate any address you want in a register, and use it to do the access. It can also replace direct register operands by using memory instead, and immediate operands by constructing values with arithmetic. However, for a practical instruction set, you would still immediate operands to load addresses effectively, and register operands are needed if you don't want pointer-only registers.

All the other addressing modes beside register indirect are here for convenience, and they are indeed really convenient :

• Immediate addressing saves you a register if you just have to access a fixed variable in memory.
• Base + offset is really useful for accessing object members : you can keep the base address in a register and access individual members with a fixed offset. No need for intermediate calculations or register to hold the member address.
• Similarly, indexed addressing is used for accessing arrays : you can just change an index register to access any value in the array.
• With a scale you can access multi-bytes variable (ex: int) arrays with no additional registers or calculations.
• A combination of everything can be used to access an array member in an object, still preserving the base pointer for potential access to other members in the object.

These addressing modes don't need much calculations from the CPU : only additions and shifts. Considering x86 can do a multiplication every cycle, those operations are trivial but still very convenient.

Answer 2

x86 can't do much without registers, so I don't think you can get rid of the register "addressing mode". Some very different architectures might not use registers, and just have a stack or memory,memory instructions. IDK how they implement pointers; maybe such architectures can do memory[memory] (C array notation).

Immediate isn't needed for computation to be possible. You can construct any value, using multiple registers. Start with a zero (xor eax, eax), inc it to get a 1, left-shift it to whatever position you want, inc that to set the low bit, left-shift that, etc. So it takes at worst 2*popcount(N) instructions to get N into a register. Note that immediate shift counts won't be available, though, so the obvious method of repeated shifting by one (shl eax, yes there is a separate encoding for shift-by-one, or just use add eax, eax) will just depend on the position of the highest set bit. So log2(N) + popcount(N) for the obvious shift and inc.

Absolute (what you call direct) memory addressing is not the most useful addressing mode. We can emulate it by constructing addresses with a sequence of instructions (see above), and using [register]. If we're trying to cut down, we want to ditch it. As Jester pointed out, keeping absolute addressing as our only form would be terribly inconvenient (or maybe impossible?) to use.

Index is obviously available for performance, not necessity: you can shift and add with separate instructions.

Displacements are also just for performance, so we can get rid of them and force code to add any displacement manually. See the Immediate paragraph for how.

---

I believe x86 would still be arbitrarily programmable with just register and [register] addressing modes.

With register, [register], and immediate, performance should be not much worse than full x86.

---

If implicit access to memory doesn't count as an addressing mode, you can of course emulate [register] with lodsd and stosd, but you wouldn't be able to do atomic read-modify-write operations. That feels like a cheat, though.

There's also the stack (push/pop): I don't know if a stack+registers machine is Turing-complete, but it certainly isn't programmable in the usual sense. Of course, if you modify e/rsp, you can again emulate [register], but with less choice of operand-size than lodsb/w/d/q / stosb/w/d/q.

x86 has quite a lot of space to store things in registers if you include the 16 ymm registers. Although I can't think of a way to move data between integer registers and the high 128b of a ymm without using either memory or immediate operands (for vextractf128), so in practice you have more like sixteen 16B vector-register slots for stashing local state other than the stack. Still, it's limited size, which probably means that 8 GP registers in the 32bit 386 ISA vs. all the integer/mmx/ymm registers in the 64bit AVX2 ISA isn't relevant for whether the machine is turing-complete with only push/pop, registers, and no modification of the stack pointer other than by push/pop.