September 12, 2007 Machine Language and Pointers 1What does this C code do?int foo(char *s) {int L = 0;while (*s++) {++L;}return L;}September 12, 2007 Machine Language and Pointers 2Machine Language and Pointers Today we’ll discuss machine language, the binary representation forinstructions.— We’ll see how it is designed for the common case• Fixed-sized (32-bit) instructions• Only 3 instruction formats• Limited-sized immediate fields Array Indexing vs. Pointers— Pointer arithmetic, in particularSeptember 12, 2007 Machine Language and Pointers 3Assembly vs. machine language So far we’ve been using assembly language.— We assign names to operations (e.g., add) and operands (e.g., $t0).— Branches and jumps use labels instead of actual addresses.— Assemblers support many pseudo-instructions. Programs must eventually be translated into machine language, a binaryformat that can be stored in memory and decoded by the CPU. MIPS machine language is designed to be easy to decode.— Each MIPS instruction is the same length, 32 bits.— There are only three different instruction formats, which are verysimilar to each other. Studying MIPS machine language will also reveal some restrictions in theinstruction set architecture, and how they can be overcome.September 12, 2007 Machine Language and Pointers 4R-type format Register-to-register arithmetic instructions use the R-type format. This format includes six different fields.— op is an operation code or opcode that selects a specific operation.— rs and rt are the first and second source registers.— rd is the destination register.— shamt is only used for shift instructions.— func is used together with op to select an arithmetic instruction. The inside back cover of the textbook lists opcodes and function codes forall of the MIPS instructions.6 bits5 bits5 bits5 bits5 bits6 bitsfuncshamtrdrtrsopSeptember 12, 2007 Machine Language and Pointers 5About the registers We have to encode register names as 5-bit numbers from 00000 to 11111.— For example, $t8 is register $24, which is represented as 11000.— The complete mapping is given on page A-23 in the book. The number of registers available affects the instruction length.— Each R-type instruction references 3 registers, which requires a totalof 15 bits in the instruction word.— We can’t add more registers without either making instructions longerthan 32 bits, or shortening other fields like op and possibly reducingthe number of available operations.September 12, 2007 Machine Language and Pointers 6I-type format Load, store, branch and immediate instructions all use the I-type format. For uniformity, op, rs and rt are in the same positions as in the R-format. The meaning of the register fields depends on the exact instruction.— rs is a source register—an address for loads and stores, or an operandfor branch and immediate arithmetic instructions.— rt is a source register for branches and stores, but a destinationregister for the other I-type instructions. The address is a 16-bit signed two’s-complement value.— It can range from -32,768 to +32,767.— But that’s not always enough!16 bits5 bits5 bits6 bitsaddressrtrsopSeptember 12, 2007 Machine Language and Pointers 7 Larger constants can be loaded into a register 16 bits at a time.— The load upper immediate instruction lui loads the highest 16 bits of aregister with a constant, and clears the lowest 16 bits to 0s.— An immediate logical OR, ori, then sets the lower 16 bits. To load the 32-bit value 0000 0000 0011 1101 0000 1001 0000 0000:lui $s0, 0x003D # $s0 = 003D 0000 (in hex)ori $s0, $s0, 0x0900 # $s0 = 003D 0900 This illustrates the principle of making the common case fast.— Most of the time, 16-bit constants are enough.— It’s still possible to load 32-bit constants, but at the cost of twoinstructions and one temporary register. Pseudo-instructions may contain large constants. Assemblers includingSPIM will translate such instructions correctly.— Yay, SPIM!!Larger constantsSeptember 12, 2007 Machine Language and Pointers 8 The limited 16-bit constant can present problems for accesses to globaldata.— As we saw in our memory example, the assembler put our resultvariable at address 0x10010004.— 0x10010004 is bigger than 32,767 In these situations, the assembler breaks the immediate into two pieces.lui $at, 0x1001 # 0x1001 0000lw $t1, 0x0004($at) # Read from Mem[0x1001 0004]Loads and storesSeptember 12, 2007 Machine Language and Pointers 9 For branch instructions, the constant field is not an address, but an offsetfrom the current program counter (PC) to the target address.beq $at, $0, Ladd $v1, $v0, $0add $v1, $v1, $v1j SomewhereL: add $v1, $v0, $v0 Since the branch target L is three instructions past the beq, the addressfield would contain 3. The whole beq instruction would be stored as: SPIM’s encoding of branches offsets is off by one, so the code it produceswould contain an address of 4. (But it has a compensating error when itexecutes branches.)Branchesaddressrtrsop0000 0000 0000 00110000000001000100September 12, 2007 Machine Language and Pointers 10 Empirical studies of real programs show that most branches go to targetsless than 32,767 instructions away—branches are mostly used in loops andconditionals, and programmers are taught to make code bodies short. If you do need to branch further, you can use a jump with a branch. Forexample, if “Far” is very far away, then the effect of:beq $s0, $s1, Far...can be simulated with the following actual code.bne $s0, $s1, Nextj FarNext: ... Again, the MIPS designers have taken care of the common case first.Larger branch constantsSeptember 12, 2007 Machine Language and Pointers 11J-type format Finally, the jump instruction uses the J-type instruction format. The jump instruction contains a word address, not an offset— Remember that each MIPS instruction is one word long, and wordaddresses must be divisible by four.— So instead of saying “jump to address 4000,” it’s enough to just say“jump to instruction 1000.”— A 26-bit address field lets you jump to any address from 0 to 228.• your MP solutions had better be smaller than 256MB For even longer jumps, the jump register, or jr, instruction can be used.jr $ra # Jump to 32-bit address in register $ra26 bits6 bitsaddressopSeptember 12, 2007 Machine Language and Pointers
View Full Document
Unlocking...