Monash University > School of Computer Science and Software Engineering > CSE1303 > Part B > Tutorials > Tutorial B3

CSE1303 Computer Science
Semester 2, 2003
Part B
Tutorial B3

This tute covers material from lectures B07 to B09.

Attempt the questions marked (*) like this before the tutorial. If you have specific questions about unmarked questions, you can ask the tutor about them during the tutorial.

  1. Compilers and interpreters

    1. (*) Consider the differences between a compiled language and an interpreted one. How would these differences affect:
      • the speed of running programs?
      • the space efficiency of running programs?
      • the effect of liberal commenting on program speed?
      • the ease of stepping through running code and examining variables with a debugger?
      • the ability for a program to generate parts of itself dynamically?
      • how you can distribute your program to other people?
    2. Header files such as stdio.h contain prototypes for functions from the standard C library. Explain why it is necessary (from the compiler's perspective) to include a header file if your program uses a function that the header file declares. Describe what is likely to happen if you forget to include the header file in your program.

  2. MIPS Architecture

    1. Suggest a reason why the stack segment is designed, seemingly backwards, to extend into lower addresses as it grows.
    2. Suggest a reason why it is a good idea to keep the text segment and data segment separate, rather than all together in memory.
    3. MIPS provides 32 general-purpose registers for your programs to use, presumably because that's the number that its designers thought best to supply. What decisions and tradeoffs do you think they made in arriving at this number?
    4. What advantages are there to having all instructions the same length? What disadvantages are there?

  3. Pseudoinstructions

    For these questions, you will need to review the instruction set of the MIPS computer by reading sections 2.4 through 2.10 of the SPIM manual.

    1. (*) There is no real li (load immediate) instruction in the MIPS instruction set, because it can be completed using other, real, instructions. (In other words, li is a pseudoinstruction.) Show how it can be implemented using:
      1. addi
      2. ori

      Explain the difference, if any, between the implementations.

    2. Look up the meaning of the instruction lui (load upper immediate).

      Explain why such an instruction might be useful. (Hint: I-type instructions have an immediate field of 16 bits. How would you perform the following 32-bit immediate load using no pseudoinstructions? 

      li $t0, 0x12345678

      Note that you will need two instructions, one of them lui, to complete the operation.)

      How would you complete the same load without the lui instruction? (Hint: this time you will need at least three instructions.)

    3. (*) Look up the meaning of the instruction slt (set if less than) and the pseudoinstruction sgt (set if greater than).

      Explain how these two instructions: 

      slt $at, $t0, $t1
bne $at, $zero, foo

      are equivalent to this pseudoinstruction: 

      blt $t0, $t1, foo
    4. Using nothing more than slt, bne and beq, show the equivalents of the following pseudoinstructions:
      1. sgt $at, $t0, $t1 (one instruction)
      2. bgt $t0, $t1, foo (two instructions)
      3. ble $t0, $t1, foo (two instructions)
      4. bge $t0, $t1, foo (two instructions)
    5. (*) Look up the meaning of the instructions mult (the machine multiply instruction, note the trailing t), mflo (move from LO) and mfhi (move from HI). After a multiplication, HI and LO collectively contain a single 64-bit result, with the most significant 32 bits in HI and the least significant 32 bits in LO.

      Explain how multiplying two 32-bit registers can produce a 64-bit result. (Hint: multiply, in decimal if you prefer, two three-digit numbers and note the length of the result.)

      Explain how this pseudoinstruction: 

      mul $t2, $t0, $t1

      is expanded by the assembler into these two instructions: 

      mult $t0, $t1
mflo $t2

      Suggest why the HI register can usually be safely ignored.

    6. Look up the machine instruction version of div (divide), the one with only two operands (not the div pseudoinstruction with three operands). Suggest expansions for the pseudoinstructions div and rem.

  4. Assembling and disassembling

    1. An assembler converts assembly language instructions into machine language (which in MIPS is encoded in 32-bit binary).

      Using the tables and diagram at the end of this tutorial, show the encoding of the following instructions.

      1. (*) addi $t0, $zero, 1
      2. addiu $t0, $t1, -1
      3. (*) add $t2, $t0, $t1
      4. bne $a0, $zero, foo (assume that address of foo causes the instruction's immediate field to receive the value 42; this is covered later in the course)
      5. (*) jr $ra
    2. A disassembler converts the other way; that is, it takes binary machine language instructions and prints them in a human-readable format. Disassemblers are sometimes used by programmers to read programs when the original source code is not available.

      Using the same tables and diagram, determine the assembly language instructions that correspond to the following bit patterns.

      1. (*) 00100111101111011111111111110100
      2. (*) 00000010000100010001000000100101
      3. 00000000000001100100000101000000
      4. 00001100000000000000000010101010

MIPS Instruction formats

There are three main formats for MIPS instructions, depending on whether the operands are

These are illustrated in the following diagram.

Note that there are some exceptions: for instance, shift instructions sll, srl and sra are R-format instructions, with the first source register unused and the number of bits to shift stored in the "shift amount" field.

Opcode field encodings

This abridged table shows the bit patterns of instructions' opcodes (bits 31-26 of instruction word).
opcode field (binary)opcode field (decimal)opcodeinstruction format
0000000operation given in function field; see "Function" tableR-type
0000102jJ-type
0000113jalJ-type
0001004beqI-type
0001015bneI-type
0010008addiI-type
0010019addiuI-type
00101010sltiI-type
00101111sltiuI-type
00110012andiI-type
00110113oriI-type
00111014xoriI-type
00111115luiI-type
10000032lbI-type
10000133lhI-type
10001135lwI-type
10010036lbuI-type
10010137lhuI-type
10100040sbI-type
10100141shI-type
10101143swI-type

Function field encodings

This abridged table shows the bit patterns of the Function field (bits 5-0 of instruction word) for R-type instructions, where bits 31-26 are 0.
function field (binary)function field (decimal)opcode
0000000sll
0000102srl
0000113sra
0001004sllv
0001106srlv
0001117srav
0010008jr
0010019jalr
00110012syscall
01000016mfhi
01001018mflo
01100024mult
01100125multu
01101026div
01101127divu
10000032add
10000133addu
10001034sub
10001135subu
10010036and
10010137or
10011038xor
10011139nor
10101042slt
10101143sltu

Register encodings

This table lists general-purpose register numbers and their associated names.
Register field (binary)Register field (decimal)Register name
000000$zero
000011$at
000102$v0
000113$v1
001004$a0
001015$a1
001106$a2
001117$a3
010008$t0
010019$t1
0101010$t2
0101111$t3
0110012$t4
0110113$t5
0111014$t6
0111115$t7
1000016$s0
1000117$s1
1001018$s2
1001119$s3
1010020$s4
1010121$s5
1011022$s6
1011123$s7
1100024$t8
1100125$t9
1101026$k0
1101127$k1
1110028$gp
1110129$sp
1111030$fp
1111131$ra

[ Top | Home ]

Last modified 2002-07-03