CS 531
Compilers
Final
Spring, 1998

Notes

• Tear of this page.
• Turn the exam over and write your name next to the staple.

• There are 150 points possible on this test.

• Explicitly state any assumptions you make. Keep in mind that just because you make an assumption, it is not necessarily correct.

• In order to receive credit, make sure all your work is shown on each problem.

• If you have any questions during the test, feel free to ask me about them.

• Remember, you are graded not only on the correct answer for a question, but also on the best answer.

Page CS 531 Final

1.

(25 points) Consider the following interference graph and spill priorities (shown in parentheses). The greater the priority, the less likely the node will be spilled. Apply the graph coloring algorithm assuming there are three colors: red, blue, and green. Make sure you show all your work.

2.

(20 points) Suppose that f and g are functions with side effects (for example, each sets a global variable A), and consider the following conditional statement:

if (f(1) < 3) and (g(7) > 5) then write(A) else write(-A);

(a)

What can be said about the value written?

(b)

What would have to be done to guarantee an answer?

3.

(20 points) Consider the control flow graph shown below. Are there any common subexpressions? If so, eliminate them explaining the reason for each elimination. If there is a subexpression that cannot be eliminated, explain why it can't be eliminated. A common subexpression has to appear more than once in the control flow graph.

4.

(20 points) If all the inputs to an intermediate instruction are constants whose values are known, the result of the instruction can be computed at compile time and the instruction replaced by a ``load'' of the constant value. This transformation is called constant folding. Write an algorithm to perform constant folding. Assume the appropriate data flow analysis has been completed. Make sure your algorithm does all constant folding possible.

5.

(5 points) Every time you came to class, you climbed the stairs in the library to get to the fourth floor. How many stairs do you climb to get to the fourth floor of the library?

6.

(20 points) In Pascal, value and reference parameter modes are often confused. In particular, because value mode is the default, value parameters are sometimes used in a manner that suggests reference mode was intended. A sign of this confusion is an assignment to a value parameter before its value is used. Show how data flow analysis can be used to identify value parameters that are defined before they are used.

7.

(20 points) Compare the cost, in terms of number of instructions executed at run-time, of passing parameters by value and by reference. The analysis should include the cost of passing the parameters, assigning to the parameters, and referencing the parameters. When should each be used and why?

8.

(20 points) In phase three of the project, we passed parameters (both reference and value) to a procedure/function using the run time stack. This technique does not take advantage of the RISC architecture since the low registers are not used. Write an algorithm (high-level) that your compiler could use to pass parameters, whenever possible, via registers. Make sure your algorithm is general enough to take into account all situations that could arise.

About this document ...

This document was generated using the LaTeX2HTML translator Version 98.1 release (February 19th, 1998)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 final98.

The translation was initiated by Steve Allan on 1998-12-08