Assignment 4, due Sept. 20

On all assignments, your name must be legible as it appears on your University ID card! Assignments are due at the start of class on the day indicated (usually Friday). Exceptions will be by advance arrangement unless there is what lawyers call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the teaching assistant's mailbox. Never push late work under someone's door!

1. Background: Consider a computer with the following characteristics (patterned on the MIPS architecture, but not identical to it):
   • A 32-bit instruction word, all instructions are word-aligned.
   • no direct memory addressing mode (all addressing is indexed).
   • PC relative addressing uses the program counter as an index register.
   • Immediate operands are composed of a 16-bit constant and a 5-bit rotate count.
   • Displacements for index registers are identical to immediate operands.
   • The add instruction allows an immediate operand.

   In detail, the constant field of an immediate operand is sign-extended and then rotated left from 0 to 31 places. A load-immediate followed by an add immediate or an or-immediate can load an arbitrary 32-bit constant.

   There are several ways a relocating loader could deal with this machine:

   1. It could insist that the only relocatable locations are full-word memory locations,
   2. it could allow relocation of halword constants in the immediate field of an instruction word, taking into account the rotate count in that instruction, or
   3. it could restrict relocation of halfword constants by requiring them to be in a fixed relationship, for example, the high half in the immediate field of the first instruction word and the low half in the immediate field of the next successive instruction word.

   a) Just to see if you understand this instruction format, About how many different ways are there to load the hexidecimal constant 01234567 into some particular index register using only immediate operands and no more than two instructions? (Suggested answers range from "it can't be done" to "on the order of 64") (0.2 points)

   b) If relocation applies only to aligned 32-bit words (alternative i), how would a programmer write code (or a compatible compiler generate code) to load an arbitrary relocatable constant (the address of a statically allocated variable) into a register. (0.4 points)

   c) Alternative iii) given above works but it is restrictive. Why is the following implementation of alternative ii) wrong? (Hint: It almost works, the failure is subtle. Consider what it does when loading an arbitrary 32 bit value using a load-immediate and an or-immediate 2-instruction sequence.) (0.4 points)

   // extract fields from word
   value = word.16bit_const_field
   shift = word.5bit_shift_field
   // relocate
   value = left_rotate( value, shift )
   value = value + relocation_base
   value = right_rotate( value, shift )
   // pack result back into word
   word.16bit_const_field = value
   

2. A Quick Question: In Unix (and Linux), the cc command runs the C compiler. This is how the command is usually introduced to new C programmers, but it is false. Give an example use of the command that does not invoke any compiler. (0.5 points)

3. Background: Consider this mess:
   • The program table.c reads data from standard input, and writes a set of C constant definitons to standard output.
   • The file data contains data in the form expected by table.c.
   • The program application.c has an #include directive for the file table.h that is supposed to define a number of constants derived by table.c from data.
   • The result of compiling applicaton.c should be in an executable file named applicaiton.

   A Not-so Quick Question: Write a makefile that binds all of the above so that you can make application to put it all together. (1.0 points)

4. Background: There are loaders, relocating loaders, and linking loaders, all are possible.

   A Problem: From what you know about the Unix/Linux execve command, which kind of loader does it incorporate? The answer can be inferred from what you already know. (0.5 points)