Class 11 Jump and Branch Instructions Jump instruction. Symbolic address. Conditional Branches. Textbook P&H: Chapter Instructions for making decisions. Central Connecticut State University, mips tutorial
Yüklə 0,59 Mb.
|
Class 11 Jump and Branch Instructions
Textbook P&H: Chapter 2.7.Instructions for making decisions. Central Connecticut State University, MIPS Tutorial. Chapters 17,18.The power of computers is their ability to repeat actions and their ability to alter their operation depending on data. Modern programming languages express these abilities using control structures. Repeated action (iteration) is done with a while structure. Altered operation (alteration) is done with an if-then-else structure. The machine instructions of the processor do not have these structures. Assembly language does not have these structures. When you program in assembly language you must build these structures out of basic assembly instructions. These basic instructions are the jump instructions and the conditional branch instructions. Review of the Machine Cycle
However, it takes an extra machine cycle before the change in the PC takes effect. Before the PC changes, the instruction after the jump instruction has been fetched and executed. The instruction that follows a jump instruction in memory is said to be in the branch delay slot. The reason for this delay is that MIPS is pipelined. Normally instructions are executed in sequence. In order to gain speed, the processor cleverly fetches several sequential instructions and starts working on them all. When the machine cycle calls for one of these instructions to be executed, most of the work has already been done. These instructions are in an instruction pipe. This means that the instruction after a jump instruction has mostly been completed when the jump is executed. Rather than waste this effort, the instruction is allowed to finish. Only then is the PC changed by the jump instruction. The instruction that follows a jump instruction in memory (in the branch delay slot) is always executed. After it executes the next instruction to execute is the one that was jumped to. Often the branch delay slot is filled with a no-op instruction. The SPIM simulator allows you to turn the pipeline feature off, but this is not an option with actual R2000 hardware. Altering the PC Here is a sequence of instructions. The "load" and "add" represent typical instructions. The "jump" instruction shows the address we wish to put into the PC. (The actual MIPS instruction for this involves details that we are skipping for the moment.) The last instruction, a no-op, fills the branch delay slot to give the PC time to change. Once started, the four instructions execute in an unending loop.
A loop structure is created with the jump instruction. The intent of the jump instruction is to put the address 0x00400000 into the PC. However, this effect is not seen until after the instruction in the branch delay slot has executed. The Jump Instruction In our schematic programs, the "jump" instruction gave a 32-bit address that goes into the PC. How does a 32-bit instruction specify a 32-bit address? Some of the instruction's bits must be used for the op-code. Here is the assembly language version of the jump instruction. j target # after a delay of one machine cycle, # PC <-- address of target Here is the machine language form of the instruction: 6 26 000010 00000000000000000000000000 -- fields of the instruction opcode target -- meaning of the fields
There is room in the instruction for a 26-bit address. The 26-bit target address field is transformed into a 32-bit address. Here is how this is done: Instructions always start on an address that is a multiple of four (they are word-aligned). So the low order two bits of a 32-bit instruction address are always "00". Shifting the 26-bit target left two places results in a 28-bit word-aligned address. Now the high-order four bits in the PC are concatenated to the high-order end of the 28-bit address to form a 32-bit address. 
Jump uses the Pseudodirect addressing mode, where the jump address is the 26 bits of the instruction concatenated with the upper bits of the PC 
Most Jumps (and Branches) are Local Most jumps and branches are to nearby addresses. The jump address and the address of the instruction following the jump instruction are likely to have the same high-order four bits. So the high-order four bits of the PC are likely to be the ones needed for the target address. Of course, an assembly language programmer must be careful to make sure that this is so. When a compiler translates a source program into machine language it also must pay attention to addresses. For tiny programs such as you will write for this course the high for bits of the PC will always be the high four bits of the address that you want. A jump instruction can't jump to any arbitrary location in the full 32-bit address space It must jump to an address within the following range: wxyz 0000 0000 0000 0000 0000 0000 0000 . . . wxyz 1111 1111 1111 1111 1111 1111 1100 Here, wxyz represents the high-order four bits of the PC. Almost always the jump instruction and the jump address are both within this range. All these details may look terrible to you at this point. Don't worry: (1) its not as bad as it looks, and (2) usually the assembler does all the work. (But for now, you get to do the work).
The left-most six bits of the j machine instruction are the opcode.
How do you know what the high-order four bits of the PC are? Well, since you have the address of the jump instruction, you know that its address is in the PC. So the high order four bits come from that address. Symbolic Address With some trickery, a 26-bit field can specify a 32-bit address. But it is a nuisance to figure out! If you were doing machine language programming, that is what you would have to do. But the assembler does the work for you. Here is a tiny program: ## jump.asm ##
.globl main
sll $0,$0,0 sll $0,$0,0 sll $0,$0,0 sll $0,$0,0 j main
addiu $8,$8,1 ## End of file It is similar to the previous example. The symbolic address main stands for the address of the first instruction. The instruction j main tells the assembler to assemble a machine instruction with the proper 26-bit field so that control is transferred to main. The branch delay slot is filled with an instruction that increments register $8. Assembled Program Here is a SPIM view of the program. When you run it, remember to set the value of the PC to 0x400000. To see the branch delay it should be enabled in the options menu. 
The assembler constructed the same machine language jump instruction as we did by hand. Using the assembler and a symbolic address is much easier You can build unending loops (infinite loops) with jump instruction. But additional instructions are needed for while loops and for if-then-else structures. 
Unconditionally jump to the instruction whose address is in register rs. ## jump to full 32 bit address by register ## .text .globl __start __start: sll $0,$0,0 here: sll $0,$0,0 sll $0,$0,0 lui $5,0x0040 ori $5,0x0004 jr $5 # Jump to 0x0040 0004 addiu $8,$8,1 ## End of file Do not use jumps in delay slots Mips states that placing branch instruction in to a branch delay slot leads to undefined results. If a branch or jump instruction is placed in the branch delay slot, the operation of both instructions is undefined. ## jump in delay slot is not allowed ## If a branch or jump instruction is placed in the branch delay slot, ## the operation of both instructions is undefined. ##
.globl __start __start: sll $0,$0,0 lbl1: sll $0,$0,0 sll $0,$0,0 lbl2: sll $0,$0,0 j __start # j lbl1 # j lbl2 # addiu $8,$8,1 ## End of file Conditional Branches What distinguishes a computer from a simple calculator is its ability to make decisions. Based on the input data and the values created during computation, different instructions execute. Decision making is commonly represented in programming languages using the if statement, sometimes combined with go to statements and labels. MIPS assembly language includes many decision-making instructions, similar to an if statement with a go to. Two of them are represented below. The first instruction is beq registerl, register2 ,L1 This instruction means go to the statement labeled L1 if the value in register1 equals the value in register2. The mnemonic beq stands for branch if equal. The second instruction is bne registerl, register2 ,L1 It means go to the statement labeled L1 if the value in register1 does not equal the value in register2. The mnemonic bne stands for branch if not equal. These two instructions are traditionally called conditional branches. A conditional branch instruction branches to a new address only if a certain condition is true. Usually the condition is about the values in registers. Here is the beq (branch on equal) instruction: The bit patterns in two registers are compared. If the bit patterns are the same, the PC is changed to the branch address. There is a branch delay following the instruction (just as for a jump instruction). beq u,v,addr # if register $u == register $v # PC <-- addr (after a delay of one machine cycle.) # else # no effect. Ifs and Whiles
Branch on Not Equal Here is the bne (branch on not equal) instruction: bne u,v,addr # if register $u =/= register $v # PC <-- addr (after a delay of one machine cycle.) # else # no effect. Two-way Decision A two-way decision (alternation) is written in assembly language using both a conditional branch and a jump instruction. Look at this example carefully! It shows how a basic control structure is built out of small assembly instructions.
Of course, any of the conditional branch instructions may be used in the place of beq. If you want the "true" branch to come first and the "false" branch to come second (as in an if-then-else of Java or C), pick a different branch instruction. Absolute Value
## absVal.asm ## ## Calculate the absolute value of A ## ## Registers: ## $8 --- A, two's comp. integer ## $9 --- sign bit of A ## $10 --- base register for .data section
.globl main main: # Get A
lui $10,0x1000 # Init base register lw $8,0($10) # Load A sll $0,$0,0 # no-op
srl $9,$8,31 # Shift sign bit to position 0 beq $0,$9,done # sign bit == zero, done sll $0,$0,0 # no-op # Store -A sub $8,$0,$8 # negate A sw $8,0($10) # save it
A: .word -1 ## End of File Branch Instructions Implementation Branch instructions use a signed 16-bit instruction offset field; hence, they can jump 215 - 1 instructions (not bytes) forward or 215 instructions backward. The jump instruction contains a 26-bit address field. In actual MIPS processors, branch instructions are delayed branches, which do not transfer control until the instruction following the branch (its “delay slot”) has executed. Delayed branches affect the offset calculation, since it must be computed relative to the address of the delay slot instruction (PC + 4), which is when the branch occurs. SPIM does not simulate this delay slot, unless the bare or delayed_branch flags are specified. In assembly code, offsets are not usually specified as numbers. Instead, an instructions branch to a label, and the assembler computes the distance between the branch and the target instructions. 
The target address that a branch instruction calculates is the following: Program counter = Program Counter+4 + Branch Offset*4 New PC = PC+4 + Off*4 Offset is a 16 bit 2’s complement. This form of branch addressing is called PC-relative addressing. As it is convenient for the hardware to increment the PC early to point to the next instruction, hence, the MIPS address is actually relative to the address of the following instruction (PC + 4) as opposed to the current instruction (PC). Since all MIPS instructions are 4 bytes long, MIPS stretches the distance of the branch by having PC-relative addressing refer to the number of words to the next instruction instead of the number of bytes. Thus, the 16-bit field can branch four times as far by interpreting the field as a relative word address rather than as a relative byte address. Similarly, the 26-bit field in jump instructions is also a word address, meaning that it represents a 28-bit byte address. This is a compiled version of program which calculates the Absolute Value. [0x00400000] 0x3c0a1000 lui $10, 4096 ; 15: lui $10,0x1000 # Init base register [0x00400004] 0x8d480000 lw $8, 0($10) ; 16: lw $8,0($10) # Load A [0x00400008] 0x00000000 nop ; 17: sll $0,$0,0 # no-op [0x0040000c] 0x00084fc2 srl $9, $8, 31 ; 20: srl $9,$8,31 # Shift sign bit to position 0 [0x00400010] 0x10090003 beq $0, $9, 12 [done-0x00400010]; 21: beq $0,$9,done # sign bit == zero, done [0x00400014] 0x00000000 nop ; 22: sll $0,$0,0 # no-op [0x00400018] 0x00084022 sub $8, $0, $8 ; 25: sub $8,$0,$8 # negate A [0x0040001c] 0xad480000 sw $8, 0($10) ; 26: sw $8,0($10) # save it [0x00400020] 0x00000000 nop ; 28: sll $0,$0,0 # target of the branch
It’s = 3. It’s calculated by compiler (translator) during the translation of the source code subtracting from ”done” address the PC (current+4)[done-0x00400010]=12, 12/4=3. Using this formula New PC = PC+4 + Off*4 The computer calculates the target address of branch. beq $0,$9,done beq $0 $9 0 0 0 3 opcode oprnd dest offset 000100 00000 01001 0000 0000 0000 0011 0001 0000 0000 1001 0000 0000 0000 0011 1 0 0 9 0 0 0 3 New PC = PC + Off*4 = 0x00400010+4 + 0x0003*4 = 0x00400014 + 0x0000000C = 0x00400020 [0x00400000] 0x3c0a1000 lui $10, 4096 [0x00400004] 0x8d480000 lw $8, 0($10) [0x00400008] 0x00000000 nop [0x0040000c] 0x00084fc2 srl $9, $8, 31 [0x00400010] 0x10090003 beq $0,$9,12 [done-0x00400010] [0x00400014] 0x00000000 nop [0x00400018] 0x00084022 sub $8, $0, $8 [0x0040001c] 0xad480000 sw $8, 0($10) done:[0x00400020] 0x00000000 nop = 0x00400020 BEQ and BNE use PC-relative addressing, where the branch address is the sum of the PC and a constant in the instruction. 
Yüklə 0,59 Mb. Dostları ilə paylaş:
|
