231 Fall 2007 -- Exam 4 Name: _______________________ Closed book. 50 minutes. 110 total points, but will be graded out of 100. Matching. Indicate the letter of the best description. (2 pts. each) 1. _____ stub a. a subroutine for testing that typically returns without doing anything significant 2. _____ test driver b. used to call a subroutine with test input c. used in inside testing 3. _____ makefile d. used in outside testing e. expansion of macro definition 4. _____ compilation f. script file of directions on how to compile or assemble and link separate source routines 5. _____ interpretation g. translation of high-level source code into machine instructions that can be executed 6. _____ static linking at later time by the computer h. translation and immediate execution of code 7. _____ dynamic linking i. linking performed while building an object file j. linking performed while building an executable 8. _____ callee-save k. linking performed at run time l. register values are saved by the caller before 9. _____ caller-save call, and later restored by caller after return m. register values are saved by the called 10. _____ ABI subroutine at entry, and later restored by the subroutine just prior to return n. automatic broker interface for middleware o. application binary interface p. application programming interface 11. Draw the compilation model and identify the six translators we have discussed and also give the types/names of files/memory contents that each produces. (24 pts.) [Use static linking in your diagram.] 12. Give at least two advantages of separate compilation/assembly. (6 pts.) 13. Give at least two advantages for dynamic linking. (6 pts.) For 14-21, consider the generated assembly on the handout for the main() routine. (That is, the assembly code with the aa__ line numbers.) 14. Name the global text symbols, if any, that are exported. (2 pts.) 15. Name the global text symbols, if any, that are imported. (2 pts.) 16. Name the local text symbols, if any, that are neither exported nor imported. (2 pts.) 17. Name the global data symbols, if any (and no matter whether read/ write or read-only), that are exported. (2 pts.) 18. Name the global data symbols, if any (and no matter whether read/ write or read-only), that are imported (i.e., are external). (2 pts.) 19. Name the local data symbols, if any (and no matter whether read/ write or read-only), that are neither exported nor imported. (2 pts.) 20. Identify the line numbers of instructions, if any, that have absolute address fields. (3 pts.) 21. Identify the line numbers of instructions, if any, that have PC-relative displacement fields. (3 pts.) bc01: int my_str_len( char * s ){ bc02: return recursive_str_len( s, 0 ); bc03: } cc01: int recursive_str_len( char *s, int n ){ cc02: if( *s == 0 ) return n; cc03: else return recursive_str_len( s+1, n+1 ); cc04: } For 22-26, consider the generated assembly on the handout for the unoptimized my_str_len() routine. (That is, the ba__ line numbers.) 22. ____ The 68 in the store instruction on line ba06 is: (choose one) (4 pts.) a. an absolute address b. a PC-relative displcement c. a relative offset to the frame pointer d. none of the above 23. Consider the following address assignments. Fill in the empty field needed by the call instruction. (4 pts.) 0x100: my_str_len: 0x104: 0x108: 0x10c: 0x110: ________ 0x114: 0x118: 0x11c: end: 0x120: 0x124: recursive_str_len: 0x128: ... rest of recursive_str_len() ... 24. ____ If the three C routines are separately compiled, the needed value for the call field in my_str_len() would be determined by the: (choose one) (4 pts.) a. the assembler b. the linker c. the loader d. none of the above 25. If the three unoptimized assembly routines are separately assembled, is it acceptable to have the same label "end" appear at aa19 and ba12? (2 pts.) 26. If the three unoptimized assembly routines are edited into a single source file and then assembled, is it acceptable to have the same label "end" twice in the same assembly source file (2 pts.) For 27, consider the generated assembly on the handout for the optimized my_str_len() routine. (That is, the bopt__ line numbers.) 27. Why is there no ret or retl instruction? (5 pts.) Hint: the order of execution for the instructions would be: bopt05 - mov bopt06 - or bopt07 - call bopt08 - or first instruction of recursive_str_len() ... if there is no save instruction, recursive_str_len() will end in retl (which is jmp %o7+8) For 28-30, consider the generated assembly on the handout for the unoptimized recursive_str_len() routine (that is, the ca__ line numbers) along with the generated assembly for the optimized recursive_str_len() routine (that is, the copt__ line numbers). 28. Explain how the two generated routines can be equivalent if the unoptimized version uses a ldub at ca08 while the optimized version uses a ldsb at copt09. (5 pts.) 29. What aspect of the C source code leads to a compiler choosing to zero-fill or sign-extend the value of a byte loaded into a word-length register? (5 pts.) 30. Why is the optimized version not recursive? Identify and explain the compiler optimization used. (5 pts.) Consider the following C main program and the (edited) generated assembly. ac01: #include ac02: char t[] = "this is a test"; ac03: int main(){ ac04: printf("%d\n",my_str_len( t )); ac05: } aa01: .global t aa02: .section ".data" aa03: t: .asciz "this is a test" aa04: .section ".rodata" aa05: .LLC0:.asciz "%d\n" aa06: .section ".text" aa07: .global main aa08: .global my_str_len aa09: main:save %sp, -112, %sp aa10: sethi %hi(t), %g1 aa11: or %g1, %lo(t), %o0 aa12: call my_str_len aa13: nop aa14: mov %o0, %o1 aa15: sethi %hi(.LLC0), %g1 aa16: or %g1, %lo(.LLC0), %o0 aa17: call printf aa18: nop aa19: end: ret /* label added */ aa20: restore A wrapper subroutine in C and the (edited) generated assembly. bc01: int my_str_len( char * s ){ bc02: return recursive_str_len( s, 0 ); bc03: } ba01: .section ".text" ba02: .global my_str_len ba03: .global recursive_str_len ba04: my_str_len: ba05: save %sp, -112, %sp ba06: st %i0, [%fp+68] ba07: ld [%fp+68], %o0 ba08: mov 0, %o1 ba09: call recursive_str_len ba10: nop ba11: mov %o0, %i0 ba12: end: ret /* label added */ ba13: restore Compare the (edited) optimized generated assembly code for my_str_len(). bopt01: .section ".text" bopt02: .global my_str_len bopt03: .global recursive_str_len bopt04: my_str_len: bopt05: mov 0, %o1 bopt06: or %o7, %g0, %g1 bopt07: call recursive_str_len bopt08: or %g1, %g0, %o7 bopt09: nop A recursive string length subroutine in C and the (edited) generated assembly. cc01: int recursive_str_len( char *s, int n ){ cc02: if( *s == 0 ) return n; cc03: else return recursive_str_len( s+1, n+1 ); cc04: } ca01: .section ".text" ca02: .global recursive_str_len ca03: recursive_str_len: ca04: save %sp, -120, %sp ca05: st %i0, [%fp+68] ca06: st %i1, [%fp+72] ca07: ld [%fp+68], %g1 ca08: ldub [%g1], %g1 ca09: sll %g1, 24, %g1 ca10: sra %g1, 24, %g1 ca11: cmp %g1, 0 ca12: bne .LL2 ca13: nop ca14: ld [%fp+72], %g1 ca15: st %g1, [%fp-20] ca16: b .LL4 ca17: nop ca18: .LL2:ld [%fp+68], %g1 ca19: add %g1, 1, %g2 ca20: ld [%fp+72], %g1 ca21: add %g1, 1, %g1 ca22: mov %g2, %o0 ca23: mov %g1, %o1 ca24: call recursive_str_len ca25: nop ca26: mov %o0, %g1 ca27: st %g1, [%fp-20] ca28: .LL4:ld [%fp-20], %g1 ca29: mov %g1, %i0 ca30: ret ca31: restore Compare the (heavily-edited) optimized generated assembly code for recursive_str_len(). (E.g., annulling branches and delay slots have been restructured for ease of understanding the code.) copt01: .section ".text" copt02: .global recursive_str_len copt03: recursive_str_len: copt04: ldsb [%o0], %g1 copt05: b .LL10 copt06: nop copt07: .LL6: add %o0, 1, %o0 copt08: add %o1, 1, %o1 copt09: ldsb [%o0], %g1 copt10: .LL10: cmp %g1, 0 copt11: bne .LL6 copt12: nop copt13: mov %o1, %o0 copt14: retl copt15: nop