CS 412/413
Introduction to Compilers
Spring 2001

Homework 4: Objects and Optimization

due: Friday, April 13, in class

1. Subtyping and implementation

   Suppose we want to add a new kind of type to Iota, similar to C++ anonymous union types to Iota. Let the type expression

   union {
       a:T1
       b:T2
   }
       

   denote a type whose values may be either a value of type T1 or a value of type T2, tagged with some information about which of the two is present. This kind of type is sometimes known as a variant record. Unlike C++ unions, our unions are type-safe: they keep track of which one of the fields currently contains a value. If an attempt is made to read one of the other union fields, the result is null. Assigning into a union field sets that field as the current field. Here is an example of the use of unions:

       x: union {
          color: Color
          shape: Shape
       }
       red: Color
       square: Shape
       ...
       x.color = red; // x now contains the color red
       if (x.shape) print("It can't happen here");
       x.shape = square; // now x contains the shape square,
                         //and not the color red
       if (x.color) print("Can't happen here either"); 

   1. In Iota⁺ or Java, what restriction must we place on the field types T_i in order that all the operations on a value of type union{x₁:T₁, ..., x_n:T_n} make sense?
   2. Assuming that there are no more than 2³² fields per union type, propose an efficient implementation for unions.
   3. Write an inference rule that defines how to type the union field access expression e.f (where f is the name of a field) in accordance with the description above. Also write an inference rule for typing the union field assignment expression e.f = e' 
   4. The following proposed subtyping rule for unions is not safe. Give an example of code that would type-check but result in a run-time type error if this rule were allowed (for example, accessing a field of an object that doesn't have that field).
      
      

      n´m                  Ti <: T'i    i21..n

      union{f1: T1, ..., fn: Tn} <: union{f1: T'1, ..., fn: T'n, ..., fm: T'm}

   
   
   5. Propose a more restrictive, sound rule for subtyping on union types that does permit useful subtype relationships between unequal union types.
   
   
2. Dataflow Analysis and Optimization
1. We have informally described the copy propagation optimization in class. In this problem we will work out an analysis designed just for this optimization. When doing copy propagation on an assignment x=y, we replace subsequent uses of x with uses of y if there are no intervening instructions that change either x or y. For example, the code

   c = a + b
   d = a
   e = d + b
   d = d * 2
   f = d + b

   becomes, after propagation of the copied value in a to the appropriate uses of d,

   c = a + b
   d = a
   e = a + b
   d = a * 2
   f = d + b
       

   Copy propagation is useful because it can create dead code, such as the first assignment to d, and new opportunities for optimization, such as common subexpression elimination on a + b. It is easy to do copy propagation within a basic block, but for the more general case of a control flow graph, we perform a dataflow analysis to determine which copy assignments reach uses of their left-hand variables without having either variable redefined. An element of the lattice on which the dataflow analysis operates is a set of copy assignments, which are pairs (x,y). Each such copy assignment indicates that the variable x contains a copy of the variable y.

   1. Is this properly a forward or backward data-flow analysis?

   2. What combining operator u should be used?

   3. What are the top and bottom elements of the lattice?

   4. Let GEN(n) be the set of copies generated by node n. Let KILL(n) be the set of copies killed by n. Define GEN and KILL for each of the following node types.

      • x = y
      • x = a1 OP a2
      • if x goto L1 else L2
      • goto L1
      • x = f(a1, a2, ..., an)

   5. Define the flow function F_n(x) for a node n in terms of GEN(n) and KILL(n)

   6. Draw a control flow graph for the following code:

      y = b
      a = y
      L1: x = a
      z = y*2
      y = f(x)
      y = y + z
      c = x < b;
      if (c) goto L1 else L2
      L2: y = a + 1
      

   7. Show the result of performing your dataflow analysis on this code, using the work-list algorithm.