A.2 Assemblers A-17 la $a0,int_str mov $al.$a0 ANSWER jal printf This example illustrates a drawback of macros.A programmer who uses this macro must be aware that printint uses register $a0 and so cannot correctly print the value in that register. Some assemblers also implement pseudoinstructions,which are instructions pro- Hardware vided by an assembler but not implemented in hardware.Chapter 2 contains many Software examples of how the MIPS assembler synthesizes pseudoinstructions and address- ing modes from the spartan MIPS hardware instruction set.For example, Interface Section 2.6 in Chapter 2 describes how the assembler synthesizes the blt instruc- tion from two other instructions:slt and bne.By extending the instruction set, the MIPS assembler makes assembly language programming easier without compli- cating the hardware.Many pseudoinstructions could also be simulated with macros, but the MIPS assembler can generate better code for these instructions because it can use a dedicated register($at)and is able to optimize the generated code. Elaboration:Assemblers conditionally assemble pieces of code,which permits a programmer to include or exclude groups of instructions when a program is assembled. This feature is particularly useful when several versions of a program differ by a small amount.Rather than keep these programs in separate files-which greatly complicates fixing bugs in the common code-programmers typically merge the versions into a sin- gle file.Code particular to one version is conditionally assembled,so it can be excluded when other versions of the program are assembled. If macros and conditional assembly are useful,why do assemblers for UNIX systems rarely,if ever,provide them?One reason is that most programmers on these systems write programs in higher-level languages like C.Most of the assembly code is produced by compilers,which find it more convenient to repeat code rather than define macros. Another reason is that other tools on UNIX-such as cpp,the C preprocessor,or m4,a general macro processor-can provide macros and conditional assembly for assembly language programs
A.2 Assemblers A-17 Elaboration: Assemblers conditionally assemble pieces of code, which permits a programmer to include or exclude groups of instructions when a program is assembled. This feature is particularly useful when several versions of a program differ by a small amount. Rather than keep these programs in separate files—which greatly complicates fixing bugs in the common code—programmers typically merge the versions into a single file. Code particular to one version is conditionally assembled, so it can be excluded when other versions of the program are assembled. If macros and conditional assembly are useful, why do assemblers for UNIX systems rarely, if ever, provide them? One reason is that most programmers on these systems write programs in higher-level languages like C. Most of the assembly code is produced by compilers, which find it more convenient to repeat code rather than define macros. Another reason is that other tools on UNIX—such as cpp, the C preprocessor, or m4, a general macro processor—can provide macros and conditional assembly for assembly language programs. la $a0, int_str mov $a1, $a0 jal printf This example illustrates a drawback of macros. A programmer who uses this macro must be aware that print_int uses register $a0 and so cannot correctly print the value in that register. ANSWER Some assemblers also implement pseudoinstructions, which are instructions provided by an assembler but not implemented in hardware. Chapter 2 contains many examples of how the MIPS assembler synthesizes pseudoinstructions and addressing modes from the spartan MIPS hardware instruction set. For example, Section 2.6 in Chapter 2 describes how the assembler synthesizes the blt instruction from two other instructions: slt and bne. By extending the instruction set, the MIPS assembler makes assembly language programming easier without complicating the hardware. Many pseudoinstructions could also be simulated with macros, but the MIPS assembler can generate better code for these instructions because it can use a dedicated register ($at) and is able to optimize the generated code. Hardware Software Interface
A-18 Appendix A Assemblers,Linkers,and the SPIM Simulator A.3 Linkers separate compilation Split- Separate compilation permits a program to be split into pieces that are stored in ting a program across many different files.Each file contains a logically related collection of subroutines and files,each of which can be com- piled without knowledge of data structures that form a module in a larger program.A file can be compiled and assembled independently of other files,so changes to one module do not require what is in the other files. recompiling the entire program.As we discussed above,separate compilation necessitates the additional step of linking to combine object files from separate modules and fix their unresolved references. The tool that merges these files is the linker(see Figure A.3.1).It performs three tasks: Searches the program libraries to find library routines used by the program Determines the memory locations that code from each module will occupy and relocates its instructions by adjusting absolute references Resolves references among files A linker's first task is to ensure that a program contains no undefined labels. The linker matches the external symbols and unresolved references from a pro- gram's files.An external symbol in one file resolves a reference from another file if both refer to a label with the same name.Unmatched references mean a symbol was used,but not defined anywhere in the program. Unresolved references at this stage in the linking process do not necessarily mean a programmer made a mistake.The program could have referenced a library routine whose code was not in the object files passed to the linker.After matching symbols in the program,the linker searches the system's program librar- ies to find predefined subroutines and data structures that the program references. The basic libraries contain routines that read and write data,allocate and deallo- cate memory,and perform numeric operations.Other libraries contain routines to access a database or manipulate terminal windows.A program that references an unresolved symbol that is not in any library is erroneous and cannot be linked. When the program uses a library routine,the linker extracts the routine's code from the library and incorporates it into the program text segment.This new rou- tine,in turn,may depend on other library routines,so the linker continues to fetch other library routines until no external references are unresolved or a rou- tine cannot be found. If all external references are resolved,the linker next determines the memory locations that each module will occupy.Since the files were assembled in isolation
A-18 Appendix A Assemblers, Linkers, and the SPIM Simulator Separate compilation permits a program to be split into pieces that are stored in different files. Each file contains a logically related collection of subroutines and data structures that form a module in a larger program. A file can be compiled and assembled independently of other files, so changes to one module do not require recompiling the entire program. As we discussed above, separate compilation necessitates the additional step of linking to combine object files from separate modules and fix their unresolved references. The tool that merges these files is the linker (see Figure A.3.1). It performs three tasks: ■ Searches the program libraries to find library routines used by the program ■ Determines the memory locations that code from each module will occupy and relocates its instructions by adjusting absolute references ■ Resolves references among files A linker’s first task is to ensure that a program contains no undefined labels. The linker matches the external symbols and unresolved references from a program’s files. An external symbol in one file resolves a reference from another file if both refer to a label with the same name. Unmatched references mean a symbol was used, but not defined anywhere in the program. Unresolved references at this stage in the linking process do not necessarily mean a programmer made a mistake. The program could have referenced a library routine whose code was not in the object files passed to the linker. After matching symbols in the program, the linker searches the system’s program libraries to find predefined subroutines and data structures that the program references. The basic libraries contain routines that read and write data, allocate and deallocate memory, and perform numeric operations. Other libraries contain routines to access a database or manipulate terminal windows. A program that references an unresolved symbol that is not in any library is erroneous and cannot be linked. When the program uses a library routine, the linker extracts the routine’s code from the library and incorporates it into the program text segment. This new routine, in turn, may depend on other library routines, so the linker continues to fetch other library routines until no external references are unresolved or a routine cannot be found. If all external references are resolved, the linker next determines the memory locations that each module will occupy. Since the files were assembled in isolation, A.3 Linkers A.3 separate compilation Splitting a program across many files, each of which can be compiled without knowledge of what is in the other files
A.4 Loading A-19 Object file sub: Object file Executable file Instructions main: main: ja1？?? jal printf ja1??? ial sub printf: call.sub Linker Relocation call.printf records sub: C library print: FIGURE A.3.1 The linker searches a collection of object files and program libraries to find nonlocal routines used in a program,combines them into a single executable file,and resolves references between routines in different files. the assembler could not know where a module's instructions or data will be placed relative to other modules.When the linker places a module in memory,all abso- lute references must be relocated to reflect its true location.Since the linker has relocation information that identifies all relocatable references,it can efficiently find and backpatch these references. The linker produces an executable file that can run on a computer.Typically, this file has the same format as an object file,except that it contains no unresolved references or relocation information. A.4 Loading A program that links without an error can be run.Before being run,the program resides in a file on secondary storage,such as a disk.On UNIX systems,the oper-
A.4 Loading A-19 the assembler could not know where a module’s instructions or data will be placed relative to other modules. When the linker places a module in memory, all absolute references must be relocated to reflect its true location. Since the linker has relocation information that identifies all relocatable references, it can efficiently find and backpatch these references. The linker produces an executable file that can run on a computer. Typically, this file has the same format as an object file, except that it contains no unresolved references or relocation information. A program that links without an error can be run. Before being run, the program resides in a file on secondary storage, such as a disk. On UNIX systems, the operFIGURE A.3.1 The linker searches a collection of object files and program libraries to find nonlocal routines used in a program, combines them into a single executable file, and resolves references between routines in different files. A.4 Loading A.4 Object file Instructions Relocation records main: jal ??? • • • jal ??? call, sub call, printf Executable file main: jal printf jal sub printf: sub: Object file sub: • • • C library print: • • • Linker • • • • • • • • •
A-20 Appendix A Assemblers,Linkers,and the SPIM Simulator ating system kernel brings a program into memory and starts it running.To start a program,the operating system performs the following steps: 1.Reads the executable file's header to determine the size of the text and data segments 2.Creates a new address space for the program.This address space is large enough to hold the text and data segments,along with a stack segment (see Section A.5). 3.Copies instructions and data from the executable file into the new address space. 4.Copies arguments passed to the program onto the stack. 5.Initializes the machine registers.In general,most registers are cleared,but the stack pointer must be assigned the address of the first free stack location (see Section A.5). 6.Jumps to a start-up routine that copies the program's arguments from the stack to registers and calls the program's main routine.If the ma in routine returns,the start-up routine terminates the program with the exit system call. A.5 Memory Usage The next few sections elaborate the description of the MIPS architecture pre- sented earlier in the book.Earlier chapters focused primarily on hardware and its relationship with low-level software.These sections focus primarily on how assembly language programmers use MIPS hardware.These sections describe a set of conventions followed on many MIPS systems.For the most part,the hard- ware does not impose these conventions.Instead,they represent an agreement among programmers to follow the same set of rules so that software written by different people can work together and make effective use of MIPS hardware. Systems based on MIPS processors typically divide memory into three parts (see Figure A.5.1).The first part,near the bottom of the address space(starting at address 400000),is the text segment,which holds the program's instructions. static data The portion of The second part,above the text segment,is the data segment,which is further memory that contains data divided into two parts.Static data (starting at address 10000000)contains whose size is known to the com- objects whose size is known to the compiler and whose lifetime-the interval dur- piler and whose lifetime is the ing which a program can access them-is the program's entire execution.For program's entire execution. example,in C,global variables are statically allocated since they can be referenced
A-20 Appendix A Assemblers, Linkers, and the SPIM Simulator ating system kernel brings a program into memory and starts it running. To start a program, the operating system performs the following steps: 1. Reads the executable file’s header to determine the size of the text and data segments. 2. Creates a new address space for the program. This address space is large enough to hold the text and data segments, along with a stack segment (see Section A.5). 3. Copies instructions and data from the executable file into the new address space. 4. Copies arguments passed to the program onto the stack. 5. Initializes the machine registers. In general, most registers are cleared, but the stack pointer must be assigned the address of the first free stack location (see Section A.5). 6. Jumps to a start-up routine that copies the program’s arguments from the stack to registers and calls the program’s main routine. If the main routine returns, the start-up routine terminates the program with the exit system call. The next few sections elaborate the description of the MIPS architecture presented earlier in the book. Earlier chapters focused primarily on hardware and its relationship with low-level software. These sections focus primarily on how assembly language programmers use MIPS hardware. These sections describe a set of conventions followed on many MIPS systems. For the most part, the hardware does not impose these conventions. Instead, they represent an agreement among programmers to follow the same set of rules so that software written by different people can work together and make effective use of MIPS hardware. Systems based on MIPS processors typically divide memory into three parts (see Figure A.5.1). The first part, near the bottom of the address space (starting at address 400000hex), is the text segment, which holds the program’s instructions. The second part, above the text segment, is the data segment, which is further divided into two parts. Static data (starting at address 10000000hex) contains objects whose size is known to the compiler and whose lifetime—the interval during which a program can access them—is the program’s entire execution. For example, in C, global variables are statically allocated since they can be referenced A.5 Memory Usage A.5 static data The portion of memory that contains data whose size is known to the compiler and whose lifetime is the program’s entire execution
A.5 Memory Usage A-21 7fff fffChex Stack segment Dynamic data Static data Data segment 10000000e Text segment 400000ex Reserved FIGURE A.5.1 Layout of memory. Because the data segment begins far above the program at address 10000000hex, Hardware load and store instructions cannot directly reference data objects with their Software 16-bit offset fields (see Section 2.4 in Chapter 2).For example,to load the word in the data segment at address 10010020pex into register $vo requires Interface two instructions: lui $s0.0x1001#0x1001 means 1001 base 16 1w$v0,0x0020($s0)#0x10010000+0x0020=0x10010020 (The 0x before a number means that it is a hexadecimal value.For example, 0x8000is8000aor32,768enm) To avoid repeating the lui instruction at every load and store,MIPS systems typically dedicate a register($gp)as a global pointer to the static data segment. This register contains address 10008000pex.so load and store instructions can use their signed 16-bit offset fields to access the first 64 KB of the static data segment. With this global pointer,we can rewrite the example as a single instruction: 1w$v0,0x8020($gp) Of course,a global pointer register makes addressing locations 10000000mex- 10010000faster than other heap locations.The MIPS compiler usually stores global variables in this area because these variables have fixed locations and fit bet- ter than other global data,such as arrays
A.5 Memory Usage A-21 FIGURE A.5.1 Layout of memory. Dynamic data Static data Reserved Stack segment Data segment Text segment 7fff fffchex 10000000hex 400000hex Because the data segment begins far above the program at address 10000000hex, load and store instructions cannot directly reference data objects with their 16-bit offset fields (see Section 2.4 in Chapter 2). For example, to load the word in the data segment at address 10010020hex into register $v0 requires two instructions: lui $s0, 0x1001 # 0x1001 means 1001 base 16 lw $v0, 0x0020($s0) # 0x10010000 + 0x0020 = 0x10010020 (The 0x before a number means that it is a hexadecimal value. For example, 0x8000 is 8000hex or 32,768ten.) To avoid repeating the lui instruction at every load and store, MIPS systems typically dedicate a register ($gp) as a global pointer to the static data segment. This register contains address 10008000hex, so load and store instructions can use their signed 16-bit offset fields to access the first 64 KB of the static data segment. With this global pointer, we can rewrite the example as a single instruction: lw $v0, 0x8020($gp) Of course, a global pointer register makes addressing locations 10000000hex– 10010000hex faster than other heap locations. The MIPS compiler usually stores global variables in this area because these variables have fixed locations and fit better than other global data, such as arrays. Hardware Software Interface