## CS 375, Compilers: Example Question Answers for Final Exam

Consider the following declarations:
```     type complex = record  re, im: real  end;

item  = record name:      alfa;
age:       integer;
location:  complex;
displayed: boolean;
color:     array[(red,green,blue)] of integer;
cost:      real     end;

var items = array [ 8..12, (low, med, hi), 7..11] of item;
```
• If integer and boolean are 4 bytes and alfa, pointers, and real are 8 bytes, how much storage is used by the array items?

Answer: complex contains 2 reals, for a total of 16 bytes.

The item record has the following layout:

```Field       Offset     Size     Comment
name         0          8
age          8          4
location    16         16       pad to multiple of 16
displayed   32          4       boolean is a subrange of integer
color       36         12
link        48          8       pointers are size 8
cost        56          8

total       64
```
The total size of an item record is 64 bytes.

The array size should be calculated back-to-front to provide numbers that are used in the next step. 7..11 is 5 items, using the formula (high - low + 1), so we have:

```Record           64
7..11            *5   =  320
(low, med, hi)            *3 = 960
8..12                           *5 = 4800 bytes total
```
• Show the intermediate code for the expression:
```   items[10, hi, 8].link^.color[blue]
```
Show how it was derived and give the aref form.

Answer: We calculate the offset by adding the components, left-to-right:

```(10 - 8)  * 960  =  1920
hi (2 - 0) * 320 =   640
(8 - 7) * 64     =    64

total               2672

The first result is (aref items 2672).  Following the pointer ^ gives
(^ (aref items 2672)).  color[blue] is 36 + 8 = 44 offset from the pointer,
giving        (aref (^ (aref items 2672)) 44)
```

### Other Questions:

• A robot moves on a square grid. The robot can go forward (f), turn left (l), or turn right (r). Give a grammar to describe the language of all sequences of moves that leave the robot pointing in the same direction as when it started.

Answer: The robot can move in 4 directions on the square grid, so we use compass directions N, E, S, W and assume the robot starts out pointing S. It should finish pointing S, so we will include a terminating production S -> epsilon (empty). Moving forward (f) leaves the direction of the robot unchanged. Our productions are:

```S -> epsilon
S -> f S
S -> r W
S -> l E
W -> f W
W -> r N
W -> l S
N -> f N
N -> r E
N -> l W
E -> f E
E -> r S
E -> l N
```
• What kind of grammar is the above (in the Chomsky hierarchy)?

Answer: These productions all fit the pattern for a Regular grammar. The robot can be modeled by a finite automaton with 4 states, or by a simple program with a variable representing the direction.

• Describe a kind of local optimization.

Answer: Constant folding, e.g. 2 * 3 replaced by 6; Reduction in strength, e.g. i * 8 replaced by i << 3

• Describe what it means for a subexpression to be (a) available, (b) busy, (c) killed.

available: computed above and not yet killed (flows down)
busy: needed below if available (flows up)
killed: value is invalidated because some component has been redefined

• Describe sources of extra run-time overhead in (a) time and (b) space in an object-oriented language.

time: extra time for method call to determine the actual method to be used, depending on the class of the object whose method is called
space: extra space in an object to store what its class is. Java also stores hashCode.

• Draw boxes around the following code to show the basic blocks:
```   n := k*2;
if n < j then write('less')
else begin k := k - 1; write('more') end;
writeln(k);
```
The blocks would be:
1. n := k*2; n < j
2. write('less')
3. k := k - 1; write('more')
4. writeln(k)
Number the blocks and draw a flow graph; give the matrix form of the flow graph and its transitive closure.
```            1 2 3 4         1 2 3 4

1     1  0 1 1 0      1  0 1 1 1
/ \    2  0 0 0 1      2  0 0 0 1
2   3   3  0 0 0 1      3  0 0 0 1
\ /    4  0 0 0 0      4  0 0 0 0
4
```
• Give an advantage and a disadvantage for (a) call by reference (b) call by value.

Answer: Call by reference is fast for arrays (only the address is passed) but less safe (callee can change caller's variables). Call by value is safe (callee only gets a copy of caller's variables) but slow for arrays (must allocate more storage and copy the array).

• What are the most important things to optimize in a scientific program? Why?

Answer: Array references, because they have several kinds of leverage: Array references frequently occur in code; a large percentage saving in computation cost is possible; and they usually occur inside loops, thus are executed many times.

• Give three examples of computer architecture innovations that require compiler innovations to be effective.

1. cache prefetch: fetch memory to cache before it is needed, avoiding a processor stall.
2. branch prediction: tell the CPU which way a branch is likely to go (e.g. it is more likely to stay in a loop)
3. instruction reordering to take advantage of superscalar architecture (instructions on independent processor units such as integer, float, and branch can be performed simultaneously).

• Briefly and clearly define the following terms: ... 20 terms chosen from the vocabulary list on the study guide.