MCS-178 Homework Assignment 1

Remember: You are encouraged to turn in individual problems as soon as possible, rather than turning in the whole assignment on the due date. Please identify each problem with the exercise homework set number and exercise number below, as well as the number from the book. So the second problem below should be labeled, 1-2 (11.17a)

All procedures submitted on any homework or project assignment should be thoroughly tested on the computer so they work for all reasonable inputs. (For example, if a procedure is written to compute n factorial, it should work for non-negative integers.) If a procedure fails to work, you should state how it fails. You will be graded more severely for unreported bugs. Every procedure should be printed, not handwritten.

Do exercise 11.1 on page 344. Here is a postscript version of figure 11.5 which you can print and use. There is no need to allocate register names. Use SLIME to test your code.
Do exercise 11.17(a) on page 372. For part (a) two opcodes can be eliminated. For each of the two opcodes, show how to rewrite an instruction which uses that opcode so that it instead uses a non-eliminated opcode.
Do exercise 11.17(b) on page 372. For part (b) all but one opcode can be eliminated. To argue an individual opcode can be eliminated, give specific code fragments showing how an instruction using it can be rewritten in terms of any uneliminated opcodes. For example, assuming we have an otherwise unused register tmp at our disposal, we can start by eliminating sne, since
```
  sne s, a, b
```
b can be replaced by the sequence of instructions:
```
  seq s, a, b
  li tmp, 1
  sub s, tmp, s
```
or with the sequence of instructions:
```
  sub, s, a, b
  li tmp, done-label
  jeqz s, tmp
  li s, 1
done-label:
```
Remember, that the instruction you are replacing could appear anywhere in a larger program, so (for example) your proposed replacement should not halt. (It's always best if you can avoid using an an auxiliary register such as tmp.)
Do exercise 11.18 on page 373. You should test out your code in SLIME.
Do exercise 11.27 on pages 375-376.