Midterm 2 key available

I've graded today's midterm and posted a key.

Overall you did well.  Maybe it was a bit too easy, but I'm satisfied that it showed you had a grasp of the material.  I don't think judging finer gradations of how deeply you understand one topic or another was something I could reasonably expect from a one-hour exam that covered so much material.

One more example question ...

I haven't thought of exactly how I would write this up ... but I can imagine asking you to create a data flow analysis for some particular problem, such as the "variables must be initialized on all paths before any possible use" check in Java.   I might give you one set of data flow equations as an example, and ask you to modify them (and describe what the gen and kill sets would be) for a different problem.

Sample final exam questions - part 2

These aren't from old final exams, but are sorts of things I could ask in the midterm Friday.

For these, assume a computer with a load/store architecture (that is, operands of any instruction other than load or store must be a register), and the following instructions  (rX are registers, mem are memory addresses, ";" introduces a comment till the end of the line
ADD  r0, r1, r2   ;; r0 := r1 + r2
SUB  r0, r1, r2   ;; r0 := r1 - r2
BZ   label    ;;  Branch if result of last operation was zero
BN  label     ;; Branch if result of last operation was negative
BNZ label   ;; Branch if result of last operation was not negative
LD  r0,mem  ;; r0 := Memory[mem]
ST  r0,mem  :: Memory[mem] := r

Assume an unlimited set of registers (i.e., assume that register allocation will be a separate step after generating code).

1a. Show an AST and then assembly code for  the following   (which might be Java or C or some similar language).

x = x + y;
y = y - x;

1b.  If your answer is not already in register SSA form (SSA except for memory references), show the assembly code in register SSA form.

2.  Show an AST and then assembly code for the following.

while (x < 0 || x < y) {
   x = x + y;
}

Sample final exam questions

We can discuss these in class on Wednesday, but you might want to try to work them out yourself in advance.

The first two are from a take-home exam.  Questions for take-home exams are written with the assumption that people can use search engines and compiler tools, and without quite the time constraint of an in-class exam.

---

1. Suppose class B extends (is a subclass of) class A, and we have a method M with the following Java signature:
B M(B o)
or, in Cool syntax
M(B o): B

The Java and Cool type systems do not allow passing an A object to M, but they do allow assigning the return value of M to a variable of type A. Why?

Be brief but clear and concrete. Don't tell me it is because it would be a violation of the type rules; I want to know why those type rules are in Java and Cool.

---

2. Storage for a Java variable of type int is allocated in the stack (activation record), as is storage for other primitive values like booleans. However, while references to objects are stored in the stack, storage for the objects themselves (including for example Int objects) is allocated in the heap. Why the difference? Be clear, precise, and brief.

---

The next question makes more sense if you are familiar with stack architectures and stack-oriented virtual machines (e.g., JVM), which we did not talk about this term. Nonetheless you may be able to figure it out.

---

3. Some of you generated code for the stack-oriented Java virtual machine, and some of you generated code for a physical processor with registers. If you generated Java byte code, you had to calculate the maximum number of stack slots required for expression evaluation. It is relatively simple to translate stack-oriented code into register-oriented code, provided you have as many available registers as the maximum required stack depth. Briefly describe how, and illustrate with an example of translation from postfix or stack-oriented code to register  oriented code for the expression

a + b − (c + d).

---

I'll try to make up a few new questions before Wednesday, since my stash of (suitable) old questions seems pretty small.  Ideally I would like to cover type checking, code generation, data flow analysis, and register allocation.  Realistically, in a 50-minute exam, I will not be able to cover everything, and it will difficult to craft questions that require some real understanding and yet can be answered quickly.  Probably there will be less of the "explain why" kind of question and more of the "generate code for this" kind of question, though there may be some of each.

Terminology: "Forward" and "Backward" analyses

I got to thinking about terminology after today's lecture, and I think I see how terminology for "forward" and "backward" analysis can be confusing.  When we "look forward" to see what will happen further ahead in execution, that's actually a "backward" flow analysis ... because the information flows backward (we are looking forward, but bringing the information back to here).  It also indicates the way an iterative data flow analysis algorithm orders the nodes it visits.  In a backward flow analysis, it is most efficient to iterate from last to first, again because that's the direction the information is moving.  In a work-list algorithm, if values at node N change, it is the predecessors of N that need to be added to the work list.

Bottom line: the term comes from which way the information is moving, which is reverse of the direction we are looking for it.  So if a flow equation takes in information from the successors of a node, it is a backward analysis, and if it takes in information from the predecessors of a node, it is a forward analysis.