Unformatted text preview:

© 1996, Virgil BistriceanuControl Structures in MIPSObjectivesAfter completing this lab you will:• know how conditional and unconditional branches work in MIPS• better understand the advantages of having fixed size instructions• be able to use conditional and unconditional branches in your programsIntroductionExcept for some very simple programs all others use instructions that control the program flow. In a high levellanguage they may be called if (with its associated then and else), goto (which fans of structured programminghate), for, while, do. In assembly language they may be called branch, jump, call, return. They all have thefundamental property that they change the order in which instructions are executed. They allow the program-mer to specify different sequences of instructions to be executed based on the input and/or results calculatedearlier in the program.The pointer to the present instruction is the Program Counter (PC). PC is normally updated as to point to thenext sequential instruction to execute. Control instructions that may change the PC based on testing some con-dition are called conditional (or more often branches). Control instructions that always change the PC arecalled unconditional (or jumps).Any branch must indicate the condition which is tested as to decide whether the branch is taken (change thePC) or not (continue with the next sequential instruction). Any branch instruction must also indicate whereto start fetching instructions in case the branch is taken. In other words the instruction must also provide thetarget).Since branches are usually used to implement loops, and because loops tend to have a small number ofinstructions, the target is in most cases close to the current instruction. In other words, the difference betweenthe target address and the current PC is small in absolute value. There is no need to include the absolute valueof the target in the instruction1. What the instruction can specify instead, is the distance in bytes from the cur-rent instruction to the target. This distance (offset) can be positive (for forward branches) or negative(backward branch). If the branch is taken, then the offset is added to the current PC to obtain the address fromwhich the next instruction will be fetched. This is called PC-relative addressing.1. In particular this would not be possible in MIPS (nor in other RISC architectures) since all instructions have the samesize (32 bits) as an address.3© 1996, Virgil BistriceanuAside from the fact that PC-relative addressing allows for a better instruction encoding, it has also the prop-erty that it allows the code to run independent of where it is loaded in memory. This position-independencecan eliminate some work when the program is loaded in memory.Jumps, on the other hand, may reach instructions that are far away from the currently executing instruction.Since a jump is an unconditional change of PC, there is no need to specify anything else in the instruction butthe opcode and the address of the target (no, jumps are not PC-relative). Of course an instruction that is 32bit wide can not hold an address that is 32 bit itself. The field in the jump instruction that specifies the addressis 26 bit wide.The architecture also allows for the function call/return mechanism through a set of dedicated jumpinstructions.A brief summary of branches and jumps in the native MIPS instruction set is given below.In this table label and jlabel mean:• a symbolic name (i.e. a label in the program) in the user’s program• a 16 bit offset for a branch in the binary code. In this case PC ← label stands for PC-relativeaddressing• a 26 bit address for a jump in the binary code. In this case PC ← jlabel means that this 26 bitaddress replaces the PC during the execution of that jump instruction1.This laboratory is focused on branches and the regular jump (j). The other jumps (jr, jal, jalr) willbe studied in a different lab session.1. In reality the process is a little bit more complicated and will be described in detail in the Inlab section of Lab #3.Instruction Effectbeq Rs, Rt, label if (Rs == Rt) PC ← labelbne Rs, Rt, label if (Rs != Rt) PC ← labelbltz Rs, label if (Rs < 0) PC ← labelblez Rs, label if (Rs <= 0) PC ← labelbgtz Rs, label if (Rs > 0) PC ← labelbgez Rs, label if (Rs >= 0) PC ← labelj jlabel PC ← jlabeljr Rs PC ← Rsjal jlabel $ra ← PC+4, PC ← jlabeljalr Rs $ra ← PC+4, PC ← RsLaboratory 3: Prelab Control Structures in MIPS© 1996, Virgil BistriceanuLaboratory 3: PrelabDate SectionNameIntroductionLet’s have a closer look at the branch instructions and how they work. In particular we want to know in detailhow• branches are encoded• the target address is calculatedBranch encodingThe size of the offset field is 16 bits (the least significant bits in the instruction). Since instructions are of fixedsize (four bytes each), specifying the offset in bytes would be wasteful: the offset would always be a multipleof four number. Instead, the offset indicates the number of words (1 word = 4 bytes) to the target.The offset may be positive or negative. Negative numbers use 2’s complement representation.Caveat: to be efficient, any real implementation of MIPS is pipelined. This means a new instruction is fetchedevery clock cycle. Therefore the PC must point to a new instruction every clock cycle, a few clock cyclesbefore an instruction is complete. This means that PC is updated (PC ← PC+4) very early in an instructionto point to the next one. Hence, when it comes to branches, the offset is actually relative to the next instruction(PC+4) as opposed to the current one (PC). The SPIM simulator hides this complexity from the user. Whenyou inspect the memory you will see the offsets relative to the current instruction.Computing the targetThe following happen inside the CPU when the target of a branch is calculated:• the offset (16 bits) is left-shifted with two bits (which is equivalent to multiplying by 4) as to expressthe distance to the target in bytes.• the offset (18 bits now) is then sign-extended to 32 bits; if the offset is positive (the most significantbit of the offset is 0), then 0’s will be padded on the most significant positions up to 32 bits, otherwise,if the offset is negative (the most significant bit of the offset is 1), 1’s will be padded. Sign-extensiondoes not change the number.• add the offset (32 bits) to the PC (32 bits) and obtain the target address.The


View Full Document

IIT CS 402 - Control Structures in MIPS

Download Control Structures in MIPS
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Control Structures in MIPS and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Control Structures in MIPS 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?