calculating offset

Question

I have a question from homework.

I have a BNE instruction at 0x88888888, and I need to tell what is the legal jump range.

My theory is that the offset tells me I can go:

• From 0x8888888 - 4 * 2¹⁵
• To 0x88888888 + 4 * (2¹⁵-1)

I really don't understand why and how this works, can someone please explain it?

Answer 1

Find an instruction reference that shows the instruction encoding such as http://en.wikipedia.org/wiki/MIPS_architecture

000100ss sssttttt CCCCCCCC CCCCCCCC

s and t hold the registers being compared, 5 bits, gives register 0 - 31 each. the lower 16 bits are the offset in units of instructions.

(for mips) from a programmers perspective assume the program counter is 1 instruction ahead, 4 bytes. So for address 0x88888888 do your calculations with the address 0x88888888+4 = 0x8888888C.

The instruction encoding uses twos complement so your maximum forward branch is 0x7FFF instructions which is 0x7FFF<<2 = 0x1FFFC bytes. The maximum backward branch is 0x8000 when sign extended is 0xFFFF8000 instructions, in bytes that is 0xFFFF8000<<2 = 0xFFFE000

0x8888888C + 0x0001FFC = 0x888A8888
0x8888888C + 0xFFFE000 = 0x88868888

The program counter adjustment is pretty simple to figure out from a disassembly of working code generated by a working assembler. (plus the instruction reference at least enough to see the number of bits you have to use).

00002030 <back>:
    2034:
    2038:   1443fffd    bne v0,v1,2030 <back>
    203c:   00000000    nop
    2040:   1443fffb    bne v0,v1,2030 <back>
    2044:   00000000    nop
    2048:   1443fff9    bne v0,v1,2030 <back>
    204c:   00000000    nop
    2050:   14430003    bne v0,v1,2060 <fore>
    2054:   00000000    nop
    2058:   14430001    bne v0,v1,2060 <fore>
    205c:   00000000    nop

00002060 <fore>:

0x1443FFFD and 0x1443FFFB are 8 bytes apart, and two instructions apart. The difference between the offsets in the instruction is a count of 2 so that implies the encoding is in units of instructions/words not bytes nor halfwords. The forward reference is easier to do first 0x2060 - 0x2050 is 0x10 bytes, which is 4 instructions. the offset is 3 instructions, 0x2060 minus 3 instructions is 0x2054 the next instruction after the one doing the bne (makes a lot of sense, pipelined or not the pc is usually at least on the next instruction by the time you get to execute, and when you execute math with the pc the pc has already done that move forward). This can be verified with the other three branches. 0x2058 says branch one instruction head if not equal, which implies the pc is 0x205C, one ahead. 0xFFFD, invert and add 1 = 2+1 = 3 so to go backward three and get to 0x2030 you need to be at 0x203C, one ahead of the encoded instruction. 0xFFFB 4+1 = 5, 5 instructions back, which means you start at 0x2044, the instruction after the branch encoded with a 0xFFFB.

Other instruction sets it is not as simple. Arm is fairly simple, both arm and thumb mode you assume two instructions ahead from the address containing the beginning of the instruction, so in thumb mode 4 bytes, arm mode 8 bytes. Even thumb2 which is primarily 32 bit instructions, the program counter from a programmers perspective is 2 instructions ahead.

Variable word length instruction sets, which are not as regular as arm, mips, etc. Either the hardware uses a fixed rule as it does with thumb2 despite the actual address being prefetched. Or you have to know from the size of the instruction where the program counter will be and use that reference. Note that maybe the first cut at these processors the program counter was right at one or two instructions ahead when you executed, but the pipelining buried in many of them (arm, mips) the prefetch address might be regular but much farther ahead, or when you go superscalar with branch prediction, the fetches can be anywhere, even touching registers in hardware (good hardware designs do not modify anything on a simple read, only writes, you do not read a value and autoincrement a hardware pointer for example, at least for pci(e) hardware that can be used on many processors).

Answer 2

This SPIM reference says:

Branch instructions use a signed 16-bit offset field; hence they can jump 2¹⁵-1 instructions (not bytes) forward or 2¹⁵ instructions backwards.

Since instructions seem to be always 4 bytes wide, your reasoning appears right, but you've swapped the signs.

The maximum backward branch (towards a lower address) is by 2¹⁵-1 instructions, i.e. 32767 instructions or 131068 bytes, so you could reach 0x88888888 - 131068 = 8886888c.

Likewise, the maximum forward branch takes you to 0x88888888 + 131072 = 0x888a8888.