Question about the register plus immediate addressing mode

[s3a]

Question about the "register plus immediate" addressing mode

Homework Statement

The question:
"Why does adding addressing modes like register plus immediate to an instruction set architecture tend to improve performance?"

The answer:
"Adding additional addressing modes to an instruction set architecture tends to improve performance by reducing the number of instructions required to compute addresses. For example, if a data structure contains four data words, register plus immediate addressing can be used to access all of them with only one address computation required to change the pointer to point to the next data structure. If an architecture only provided the register addressing mode, an ADD instruction would be required to calculate the address of each element in the data structure."

Homework Equations

N/A

The Attempt at a Solution

I checked Wikipedia and found that:

1) Addressing modes are an aspect of the instruction set architecture in most central processing unit (CPU) designs.

2) The various addressing modes that are defined in a given instruction set architecture define how machine language instructions in that architecture identify the operand(or operands) of each instruction.

3) An addressing mode specifies how to calculate the effective memory address of an operand by using information held in registers and/or constants contained within a machine instruction or elsewhere.

Furthermore, I think I understand that having additional addressing modes just means that the processor can locate a memory address more efficiently and that, in this problem, the “register plus immediate” addressing mode allows the processor to locate memory addresses using fewer instructions.

What I'd like to know is:

1) Is an addressing mode nothing more than an additional functionality that the processor has in order to locate memory addresses? (If this sounds too similar compared to what I said above to be clear, I think I get that adding addressing modes allows the processor to locate memory addresses more efficiently but, I'm not too sure what an addressing mode actually is.)

2) Most importantly, could someone please briefly explain and then probably elaborate on how exactly the “register plus immediate” addressing mode functions?

If anything is unclear, tell me and, I will attempt to clarify the situation.

Any help in fully grasping this problem and its provided solution would be greatly appreciated!

 

[rcgldr]

Wiki article for addressing modes:

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

Register plus immediate is faster on most processors. Ancient trivia - on the early Intel processors, using load effective address with register plus immediate to add an immediate value to a register was faster than using an add instruction to add an immediate to a register and C compilers used this for optimiziation.

 

[s3a]

That's the Wikipedia article I looked at but, I cannot find the term "register plus immediate" nor any easily-digestible summary of it.

Sorry for the potentially stupid question but, what is an immediate (value)?

 

[s3a]

That's the Wikipedia article I looked at but, I cannot find the term "register plus immediate" nor any easily-digestible summary of it.

Sorry for the potentially stupid question but, what is an immediate (value)?

 

[rcgldr]

Register plus immediate is what the wiki article describes as base plus offset (base meaning a base register). An "immediate" value is one that is included as part of the instruction.

 

[s3a]

Thanks for your reply and sorry for my late one.

When I look at the relevant section of the Wikipedia article ( http://en.wikipedia.org/wiki/Addressing_modes#Base_plus_offset.2C_and_variations ), I see “load”, “reg”, “base” and “offset”.

Last post, you mentioned that “base” is short for “base register” but, I don't even know what that a “base register” is.

Furthermore, I also don't know what “load”, “reg” and “offset” are and, I strongly suspect that if I had their longer names, I would still not know what they are.

Could you please tell me what these are in the most basic, fundamental and easy-to-understand way? I would just like to understand the big picture of what is going on. I'm not currently interested in the specific details.

Basically, I just want to fully grasp the (very simple) problem I posted in my first/main post.

 

[rcgldr]

I see “load”, “reg”, “base” and “offset”.

load - load a value into a register

reg - register

base - base register, meaning it's not an "index" register. Base registers are never shifted before being used as part of an address.

index register - a register which may be optionally shifted and then optionally added to a base register as part of an address.

scaled - when an index register is shifted, it's called scaled. The syntax may be written as if it was multply, shift left 1 == *2, shift left 2 == *4, shift left 3 == *8.

offset - an immediate value (stored in the instruction, and usually signed so it can be negative or positive or zero) optionally added to a base or base + index register to form an address.

Also sometimes the registers are incremented or decremented before or after being used for addressing. In the case of a "push" instruction, on most processors, the stack pointer register is decemented before being used as an address. In the case of a "pop" instruction, the stack pointer register is incremented after being used as an address. The amount decremented or incremented would depend on the size of the operand being pushed or popped from the stack: for a 1 byte operand, the decrement or increment amount would be 1, for a 2 byte operand, the amount would be 2, for a 4 byte operand, 4, ... . Some processors also allow pre or post decrement or increment operation on any register used for addressing on most of their instructions that access memory.

 

[s3a]

Thanks for your answer. I think I get it or I am, at least, closer to getting it.

To see if I get it, could you please tell me wether or not the following stuff in my own words is 100% correct? (When I get a confirmation to something I write it in my own words, it greatly reduces the probability of me misunderstanding something.):

The register plus immediate addressing mode simply adds the offset to the base register's address and gets the effective address (which is the location of whatever datum is wanted). (The effective memory address can be an address to any kind of memory including registers, cache and RAM.) So, when dealing with an array of four elements, the base element's address summed with the offset will yield the address of the fourth element.

If no addressing mode were to be used, the CPU would have to add an offset of 1 to the address of the first element in order to get the address of the second element and would then have to add another offset of 1 to get the address of the third element and would then, again, have to add another offset of 1 to get the address of the fourth element which involves three additions instead of one as is the case with a CPU with the register plus immediate mode addressing mode.

If the above is not 100% correct, please tell me what's wrong and I will repost the corrected form until I get it 100% right.

P.S.
When a CPU is designed to have an offset for finding addresses with less computations, does that physically just mean it has more bits/registers included such that space/bits can be allocated to storing the offset?

 

[rcgldr]

The register plus immediate addressing mode simply adds the offset to the base register's address and gets the effective address (which is the location of whatever datum is wanted).

correct

The effective memory address can be an address to any kind of memory including registers, cache and RAM.

Very few processors map registers into the address space of RAM. Some processors map I/O ports into the address space of RAM. Cache is just a copy of portions of RAM, so a cache copy of a location in RAM would have the same address.

So, when dealing with an array of four elements, the base element's address summed with the offset will yield the address of the fourth element.

If the offset is 0 then the address is for the first element. If the offset is 3 * (size of an element) then the address is for the fourth element.

If no addressing mode were to be used

Accessing memory requires some form of addressing. There are instructions with no addressing modes, but they do not access memory, for example, instructions that disable or enable interrupts.

When a CPU is designed to have an offset for finding addresses with less computations, does that physically just mean it has more bits/registers included such that space/bits can be allocated to storing the offset?

This is more about the number of bits in the offset. On some processors, the offset is limited and can only access a portion of ram near the address stored in a base register. On other processors the offest can be large enough to access all of RAM.

PC based addressing with offset - on some processors, the PC (program counter) can be used as a base register. The insruction would also include an signed offset (positive, negative, or zero) to be added to the PC to generate an address. On an Intel processor, the PC can be used as a base register for branch or call instructions. On a Motorola 68000 series procesor, the PC can be used as a base register for most memory accessing (load or store) instructions.

 

[s3a]

Sorry again for my late reply. I have a hectic schedule and, I like to think deeply about these things when answering and not just give quick and sloppy replies.

correct

Thanks for confirming.

Very few processors map registers into the address space of RAM. Some processors map I/O ports into the address space of RAM. Cache is just a copy of portions of RAM, so a cache copy of a location in RAM would have the same address.

Thanks for telling me.

If the offset is 0 then the address is for the first element. If the offset is 3 * (size of an element) then the address is for the fourth element.

Thanks for telling me.

Accessing memory requires some form of addressing. There are instructions with no addressing modes, but they do not access memory, for example, instructions that disable or enable interrupts.

Thanks for telling me. Could you explain the steps taken by the register addressing mode? For example, the register plus immediate addressing mode has bits allocated to an offset which it sums with the base address to get the effective address which means it sums two values and makes the pointer point to that sum. What (extra) steps does the register addressing mode have to take (compared to the register plus immediate addressing mode)? Would it be almost the same exact thing except that, while the register plus immediate addressing mode can simply get the effective address in one sum, the register addressing mode would have to compute the effective address of each respective upcoming element until the desired (final) element/effective address is reached?

This is more about the number of bits in the offset. On some processors, the offset is limited and can only access a portion of ram near the address stored in a base register. On other processors the offest can be large enough to access all of RAM.

Is this the reason why 32 bit processors can only access 4GB of memory or is that attributed to something else?

PC based addressing with offset - on some processors, the PC (program counter) can be used as a base register. The insruction would also include an signed offset (positive, negative, or zero) to be added to the PC to generate an address. On an Intel processor, the PC can be used as a base register for branch or call instructions. On a Motorola 68000 series procesor, the PC can be used as a base register for most memory accessing (load or store) instructions.

Thanks for telling me.

 

[rcgldr]

Thanks for telling me. Could you explain the steps taken by the register addressing mode? For example, the register plus immediate addressing mode has bits allocated to an offset which it sums with the base address to get the effective address which means it sums two values and makes the pointer point to that sum. What (extra) steps does the register addressing mode have to take (compared to the register plus immediate addressing mode)?

Register plus offset requires adding the register and offset values. Register addressing does not add anything, it is the address.

compute the effective address of each respective upcoming element

This isn't done automatically. The addressing modes that do this are ones that increment or decrement a register by the size of an element either before or after being used as an address. On an Intel X86 cpu, only the push and pop type instructions do this, with the stack pointer register. On a ARM or Motorola type processor, most load and store instrutions allow pre or post decrement or increment with any base register.

Is this the reason why 32 bit processors can only access 4GB of memory or is that attributed to something else?

With 32 bits of addressing only 4GB of ram can be accessed. Intel Pentium Pro and later X86 "32 bit" processors have 36 bits of addressing for a maximum of 16GB ram, but require mapping registers and each virtual address space is limited to 4GB, although a system call could access memory outside of the current process virtual address space. I don't think any of the Windows 32 bit operating systems support this (perhaps some server versions of 32 bit Windows do this).

 

[s3a]

Register plus offset requires adding the register and offset values. Register addressing does not add anything, it is the address.

Going back to the solution of the problem I am focusing on (which is in my initial post), it was said that "if an architecture only provided the register addressing mode, an ADD instruction would be required to calculate the address of each element in the data structure.". Since you say register addressing does not add anything, what was meant by this part of the solution?

With 32 bits of addressing only 4GB of ram can be accessed. Intel Pentium Pro and later X86 "32 bit" processors have 36 bits of addressing for a maximum of 16GB ram, but require mapping registers and each virtual address space is limited to 4GB, although a system call could access memory outside of the current process virtual address space. I don't think any of the Windows 32 bit operating systems support this (perhaps some server versions of 32 bit Windows do this).

So, is this what the "32-bit" physical address extended Linux kernels are all about? Also, 2^34 = 16 GB != 2^36; what am I missing? (Pursuing this is not super important to me since what matters to me most is fully understanding how to answer the problem I posted initially but, I'm just curious since I care about this stuff.)

 

[rcgldr]

Intel Pentium Pro and later X86 "32 bit" processors have 36 bits of addressing for a maximum of 16GB ram.

Also, 2^34 = 16 GB != 2^36; what am I missing?

My mistake, 36 bits of addressing allows a maximum of 64GB of ram. I meant to state the 4 extra bits gives you 16 times the memory, and 16 x 4GB = 64GB, but an edit I made never went through and I forgot to recheck it. Intel calls this Physical Address Extension (PAE). As mentioned, desktop versions of 32 bit Windows don't support more than 4GB, but some server versions of 32 bit Windows do. Some other operating systems support PAE. Wiki article:

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

Going back to the solution of the problem I am focusing on (which is in my initial post), it was said that "if an architecture only provided the register addressing mode, an ADD instruction would be required to calculate the address of each element in the data structure.". Since you say register addressing does not add anything, what was meant by this part of the solution?

Once you have a register set to the address of the fist element of an array, it's common to simply add a value to that register in order to update that register to address the second value of an array and so on, especially there's a loop involved. If there is a register plus immediate addressing mode, then with the register set to the address of the first element of an array, the second element could be accessed using register plus immediate addressing mode, where the immediate value would be the size of an element in the array.

 

[s3a]

My mistake, 36 bits of addressing allows a maximum of 64GB of ram. I meant to state the 4 extra bits gives you 16 times the memory, and 16 x 4GB = 64GB, but an edit I made never went through and I forgot to recheck it.

Oh, I see. I'm relieved since I thought there would be something more complex going on. :P

Once you have a register set to the address of the fist element of an array, it's common to simply add a value to that register in order to update that register to address the second value of an array and so on, especially there's a loop involved. If there is a register plus immediate addressing mode, then with the register set to the address of the first element of an array, the second element could be accessed using register plus immediate addressing mode, where the immediate value would be the size of an element in the array.

So, in short, a processor using register addressing has to update the register with the address it wants whereas register plus immediate addressing (=register plus offset addressing) always has the same base address and uses a different offset to get the address wanted?

Furthermore, is the reason why the register addressing mode is slower than the register plus immediate adressing mode because it has to update the register n times where n is the number of elements from where the pointer is currently pointing to up to where it wants to point to (such as in an array)?

 

[rcgldr]

So, in short, a processor using register addressing has to update the register with the address it wants whereas register plus immediate addressing (=register plus offset addressing) always has the same base address and uses a different offset to get the address wanted?

Using offsets to index into an array is sometimes used when "unfolding" loops into sequential sequences of code to iterrate through an array.

Furthermore, is the reason why the register addressing mode is slower than the register plus immediate adressing mode?

The register addressing mode isn't slower, but the sequence of instructions, load, add, load, add, load, add, ... would be slower than load, load, load, ... using offsets instead of adding to index an array. On a processor with post increment on the addressing register, then the add insructions would not be needed, and the post increment operation may not affect the overall time of a sequence of code.

 

[s3a]

Using offsets to index into an array is sometimes used when "unfolding" loops into sequential sequences of code to iterrate through an array.

So, would that be a yes?

The register addressing mode isn't slower, but the sequence of instructions, load, add, load, add, load, add, ... would be slower than load, load, load, ... using offsets instead of adding to index an array. On a processor with post increment on the addressing register, then the add insructions would not be needed, and the post increment operation may not affect the overall time of a sequence of code.

That seems to be what I meant but, thank you for clarifying as it did slightly improve my view of the situation. One thing that I'm still wondering is, shouldn't changing the value of the offset slow things down too? Based on the solution to the problem I'm looking into, I'd say it doesn't slow things down as much as having to continously perform additions but, it is a slow-down and, there is more going on that just "load, load, load, ...", right?

 

[rcgldr]

One thing that I'm still wondering is, shouldn't changing the value of the offset slow things down too?

Here's an example of a loop and unfolded loop in 32 bit X86 assembly language that adds up 10 integers in an array:

loop example using register addressing and a loop that is run 9 times.

        mov     ecx,10-1        ;array has 10 values
        lea     ebx,array       ;ebx = address of array
        mov     eax,[ebx]
loop0:  add     ebx,4
        add     eax,[ebx]
        loop    loop0

unfolded loop using register + offset addressing mode

        lea     ebx,array       ;ebx = address of array
        mov     eax,[ebx]
        add     eax,[ebx+ 4]
        add     eax,[ebx+ 8]
        add     eax,[ebx+12]
        add     eax,[ebx+16]
        add     eax,[ebx+20]
        add     eax,[ebx+24]
        add     eax,[ebx+28]
        add     eax,[ebx+32]
        add     eax,[ebx+36]

 

[s3a]

Looking at the code samples, it seems that the first code sample will loop 10 times which means running mov and add 20 times and lea 10 times whereas the second code sample will run lea and mov 1 time and add 9 times. (Did I interpret that right? – I'm finding reading those code samples challenging since I haven't even covered mips assembly at all let alone x86.)

 

[rcgldr]

Looking at the code samples, it seems that the first code sample will loop 10 times

The first 3 insructions are only run once. The 3 instructions starting at loop0: are run 9 times each.

Example of unfolded loop using register addressing and adds:

        lea     ebx,array       ;ebx = address of array
        mov     eax,[ebx]
        add     ebx,4
        add     eax,[ebx]
        add     ebx,4
        add     eax,[ebx]
        add     ebx,4
        add     eax,[ebx]
        add     ebx,4
        add     eax,[ebx]
        add     ebx,4
        add     eax,[ebx]
        add     ebx,4
        add     eax,[ebx]
        add     ebx,4
        add     eax,[ebx]
        add     ebx,4
        add     eax,[ebx]
        add     ebx,4
        add     eax,[ebx]

 

[s3a]

Thanks for getting rid of the loop (and also for introducing it such that I've been exposed to it). Removing the loop helps get to the meat of the problem.

I think it's worth digging deeper into this so that when school is done I can learn x86 assembly on my own (since we will only look at mips in school) and also because it essentially is the code for what the words of the solution describe.

Could you elaborate on the unfolded code samples? What exactly are the instructions doing? Why is the incrementation on the unfolded loop using register + offset addressing mode an incrementation by 4?

Sorry for the numerous questions.

 

[rcgldr]

x86 assembly

Note that X86 instruction format ordeing of operatands is <destination>, <source>.

Why is the incrementation on the unfolded loop using register + offset addressing mode an incrementation by 4?

Since each integer in the array is 4 bytes (32 bits) long, the offset needs to increase by 4 for each integer.

Could you elaborate on the unfolded code samples?

        lea     ebx,array       ;ebx = address of array
        mov     eax,[ebx]       ;move contents of memory at ebx into eax
        add     ebx,4           ;add 4 to ebx (which is used to address array)
        add     eax,[ebx]       ;add contents of memory at ebx to eax
        ...

Motorola 68000 example with post increment. Note that A0 is incremented by 4 each time it's used with (a0)+ post increment addressing mode, since the data size is a long (4 bytes or 32 bits). Note operand order is <source>, <destination>

        lea     array,a0        ;a0 = address of array
        move.l  (a0)+,d0        ;d0 = first integer
        add.l   (a0)+,d0        ;d0 = 1st + 2nd integer
        add.l   (a0)+,d0        ;d0 = 1st + 2nd + 3rd integer
        add.l   (a0)+,d0        ; ...
        add.l   (a0)+,d0
        add.l   (a0)+,d0
        add.l   (a0)+,d0
        add.l   (a0)+,d0
        add.l   (a0)+,d0
        add.l   (a0)+,d0        ;d0 = sum of 10 integers

 

[s3a]

I'll keep the motorola code for future reference but, all I currently need is the x86 code samples. What's the a, b and c in e_x?

(I currently believe that by understanding the x86 code samples without loops from your two previous posts that I will better understand the solution to the problem.)

 

[rcgldr]

What's the a, b and c in e_x?

Those are the names of registers in an Intel X86 processor. The "e__" implies that they are 32 bit registers. In 32 bit mode, the registers are eax, ebx, ecx, edx, edi, esi, ebp, esp. Some instructions use specific registers, multiply and divide use edx:eax as a register pair to form a 64 bit number. The loop instructions use ecx. The string instructions use esi for source pointer, edi for destination pointer, and edi for scan (search for character). esp is the stack pointer. ebp is normally used to access variables on the stack. Wiki article:

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

 

[s3a]

Okay, I figured out enough so that I can answer the problem I began with in my first post.

Thanks. :)