Transcript Slide 1
MIPS coding SPIM • Some links can be found such as: http://www.cs.gmu.edu/~dnord/cs265/spim_intro.html A C Sort Example 3 A C Sort Example 4 A C Sort Example 5 A C Sort Example 6 A C Sort Example 7 Character and String Operations • Characters are encoded as 0’s and 1’s using ASCII most commonly – American Standard Code for Information Interchange – Each character is represented using 8 bits (or a byte) • MIPS provides instructions to move bytes – Load byte (lb) loads a byte to the rightmost 8 bits of a register – Store byte (sb) write the rightmost 8 bits of a register to memory 4/3/2016 week04-3.ppt 8 String Copy Procedure 4/3/2016 week04-3.ppt 9 String Copy Procedure • Do we have to use $s0? 4/3/2016 week04-3.ppt 10 Arrays vs. Pointers • Pointers sometime seem difficult to understand in C/C++ – Here by comparing arrays and pointers in MIPS assembly we can have a much better understanding of the differences 4/3/2016 CDA3100 11 C Programs Using Arrays and Pointers 4/3/2016 CDA3100 12 C Programs Using Arrays and Pointers 4/3/2016 CDA3100 13 MIPS Assembly Using Arrays • Register allocations: Two parameters are in $a0 (for array) and $a1 (for size), and local variable i is allocated to register $t0 4/3/2016 CDA3100 14 MIPS Assembly Using Pointers • Register allocations: Two parameters are in $a0 (for array) and $a1 (for size), and local variable p is allocated to register $t0 4/3/2016 CDA3100 15 Comparing Two Versions • Suppose the size of array is n, how many instructions for the array version? • How many instructions for the pointer version? 4/3/2016 CDA3100 16 Comparing Two Versions • Suppose the size of array is n, how many instructions for the array version? 1 6n • How many instructions for the pointer version? 4/3/2016 CDA3100 17 Comparing Two Versions • Suppose the size of array is n, how many instructions for the array version? 1 6n • How many instructions for the pointer version? 3 4n 4/3/2016 CDA3100 18 Tree Sort • This example shows to support data structures such as nodes in a binary tree • Binary search tree – One way to create a sorted list is to insert values sequentially into a binary tree, where the values in the left tree are no larger than the value in the node and the values in the right tree are no smaller than the value in the node 4/3/2016 CDA3100 19 Tree Node • In C, each tree node will be defined as a recursive data structure • How can we do that in MIPS? – In MIPS we do not have types explicitly – The types are defined implicitly based on the instructions we use 4/3/2016 CDA3100 20 Tree Node • In MIPS, we need three words 4/3/2016 CDA3100 21 Searching the Tree 4/3/2016 CDA3100 22 Treesort.s • It first creates an empty tree by creating a root node with empty left and right pointers • Loop – Read a new value – If it is the sentinel value, break out the loop – Otherwise, insert the value into the tree and repeat • Traverse the tree recursively • http://www.cs.fsu.edu/~zzhang/CDA3100_Spring_2008_files/tree_sort.asm 4/3/2016 CDA3100 23 Note • Note that a number can be written and saved in different ways – For example, number 1234 can be represented as “1234” (as a string) – number 1234 can be represented as a two’s complement integer 4/3/2016 week04-3.ppt 24 Number 1234 in Memory 4/3/2016 week04-3.ppt 25 Addressing Modes • An addressing mode is a form for specifying one or more operands • Typically one instruction set architecture will use multiple forms of addressing modes – In MIPS, we have five different addressing modes 4/3/2016 week04-3.ppt 26 MIPS Addressing Modes 1. Immediate addressing Operand is constant op rs rt Immediate 2. Register addressing Operand is in register op rs rt rd ... funct Registers Register 3. Base addressing op rs rt Memory Address lb $t0, 48($s0) + Register Byte Halfword Word 4. PC-relative addressing bne $4, $5, Label op (label will be assembled into a distance) j Label rs rt + PC Word 5. Pseudodirect addressing op Address Memory Word PC 4/3/2016 Memory Address week04-3.ppt 27 Translating a C Program 28 Generated Intel Assembly Example 29 Assembler • The primary task of an assembler is to translate assembly into machine code – It produces an object file, which consists of machine language instructions, data, and information needed to place instructions properly in memory • A UNIX object file consists of the object file header, text segment, static data segment, relocation information, symbol table, and debugging information • Which instructions may change depending on the absolute locations of instructions? 30 Linkers • Object files need to be combined together in order to produce an executable program – The tool is called the linker – Searches the libraries to find library routines used by the program – Determines the memory locations for each module and relocates its instructions by adjusting absolute references – Resolve any unresolved references among files (including libraries) 31 Linkers 32 Loaders • Note that an executable file is on the disk – To run a program, it needs to be loaded into memory 33 Dynamically Linked Libraries 34