231 Fall 2008 -- Exam 4 (with answers) Name: _______________________ Closed book. 50 minutes. Matching. Indicate the letter of the best description. (2 pts. each) 1. __c__ stub a. used to call a subroutine with no input b. used to call a subroutine with test input 2. __b__ test driver c. simple subroutine simulating the interface to the actual routine that will be used later 3. __f__ makefile d. used in inside-outside testing e. command in gdb 4. __g__ static linking f. script file of directions on how to assemble and link pieces of a program into an executable 5. __i__ dynamic linking g. linking performed while building an executable h. linking performed while building an object file 6. __j__ interpretation i. linking performed at run time j. translation and immediate execution of code 7. __k__ compilation k. translation of high-level source code into machine instructions that can be executed at later time by the computer l. expansion of macro definition 8. Draw the compile steps of the compilation model (that is, you may omit loading and running). Identify the five translators we have discussed, and also identify the type or name of the file that each produces. (30 pts.) language preprocessor compiler assembler linker .------. .--------. .--------. .------. .-------------. |source|------->|expanded|----->|assembly|------>|object|--->| executable | | code | | source | |language| | code | |(load module)| | (.c) | | code | | (.s) | | (.o) | | (a.out) | `------' `--------' | (.asm) | |(.obj)| | (.exe) | `--------' `------' `-------------' ^ .-------. / / |library|--- macro processor / |routine| / `-------' --------------- / |assembly source|------------ |w/ macros (.m) | `--------------- 9. Give at least two advantages of separate compilation/assembly. (6 pts.) any two of these: * separate source files provide a nice structure for dividing a project between several team members * separate source files allow separate testing (and thus better isolation and detection of bugs) * separate source files provide for easy reuse * separate source files minimize the work of reassembly and relinking needed whenever a change occurs in only one source file 10. Give at least two advantages for dynamic linking. (6 pts.) any two of these: * saves disk space when storing executable * saves memory space when loading memory image * get latest version of library routines Consider the following source file for questions 11-18. module A: .global main,zero,b,c main: save %sp,-96,%sp sethi %hi(a),%o0 or %o0,%lo(a),%o0 sethi %hi(d),%o1 or %o1,%lo(d),%o1 loop: call zero nop add %o0,4,%o0 cmp %o0,%o1 blt loop nop done: ret restore .section ".bss" a: .skip 4 b: .skip 4 c: .skip 4 d: .skip 4 11. Name the global text symbols that are exported (i.e., made public). (2 pts.) main 12. Name the global text symbols that are imported (i.e., are external). (2 pts.) zero 13. Name the local text symbols that are neither exported nor imported. (2 pts.) loop, done 14. Name the global data symbols that are exported (i.e., made public). (2 pts.) b, c 15. Name the global data symbols that are imported (i.e., are external). (2 pts.) 16. Name the local data symbols that are neither exported nor imported. (2 pts.) a, d 17. Identify which instructions have absolute address fields. (2 pts.) the sethi and or instructions 18. Identify which instructions have PC-relative displacement fields. (2 pts.) the call and blt instructions 19. On the right-hand-side of the page, give the symbol table built by the linker when combining the object files for these separate source modules. Assume the text section of A is placed first (at hex address 00) then the text section of B, then the bss section of A at the next doubleword boundary. (12 pts.) module A: .global main,zero,b,c linker symbol table 00: main: save %sp,-96,%sp --------------------- 04: sethi %hi(a),%o0 symbol hex address 08: or %o0,%lo(a),%o0 in executable 0c: sethi %hi(d),%o1 ------ ------------- 10: or %o1,%lo(d),%o1 14: loop: call zero _main_ __00__ 18: nop _zero_ __34__ 1c: add %o0,4,%o0 _b____ __44__ 20: cmp %o0,%o1 _c____ __48__ 24: blt loop 28: nop 2c: done: ret 30: restore .section ".bss" 00: a: .skip 4 04: b: .skip 4 08: c: .skip 4 0c: d: .skip 4 module B: .global zero 00: zero: st %g0,[%i0] 04: done: retl 08: nop 20. Is it legal for the symbol "done" to appear in both module A and module B in question 19 above? Explain your answer. (6 pts.) yes, each "done" is local to the source module and invisible to the linker Extra credit: **NOTE** There are regular credit questions on next page. XC-1. Identify the coding error in the assembly language given above for use in questions 11-19. (3 pts.) B00: zero: st %g0,[%i0] -- should use %o0 instead (since there is no save instruction) Consider the following program. c01 int fact( int value ){ c02 if( value <= 1 ) c03 return( 1 ); c04 else c05 return( value*fact(value-1) ); c06 } edited result of gcc -O2 -S a01: fact: save %sp, -112, %sp a02: add %i0, -1, %o0 a03: cmp %i0, 1 a04: mov 1, %g1 a05: ble .LL1 a06: nop a07: call fact a08: nop a09: mov %i0, %o1 a10: call .umul // unsigned multiply a11: nop a12: mov %o0, %g1 a13: .LL1: mov %g1, %i0 a14: ret a15: restore 21. To what line of the C program does assembly statement a02 correspond? (5 pts.) c05 -- specifically, it is the value-1 calculation for the parameter to pass for fact() 22. Why was %i0 moved to %o1 in line a09? (5 pts.) it is moved to the second parameter register for the call to .umul (the return value from fact() will already be in %o0) Extra credit: XC-2. Why was the compiler not able to do tail call elimination? (2 pts.) the recursive call was not the tail (last statement) of the function -- the function has to do the multiply after the recursive call returns XC-3. On the right-hand-side of the code given above question 11, give an equivalent C main() routine, which must include a loop. You can declare a, b, c, and d either as unsigned or as int. (5 pts.) int a, b, c, d; int main(){ /* zeros a, b, c */ int *ptr = &a; int *limit = &d; do{ zero( ptr++ ) } while( ptr < limit ); return; /* ret value undefined */ }