CS 412/413
Introduction to Compilers and Translators
Spring 2000
Cornell University

Homework 4: Code Generation,
Objects, and Optimization

due: Monday, April 10, in class.

1. The Return of Tuples
   In Homework 3, we developed the static semantics for immutable tuples. A type expression of the form (T₁,...T_n) is the type of a tuple containing n elements of the types T₁ through T_n respectively. An expression of the form e[i], where e has tuple type and i is a constant integer, accesses the i^th element of the tuple. And we also need a new kind of expression (e₁,...e_n) that produces a tuple value. Only a couple of things are missing...
1. Give the most permissive safe rule that defines subtyping on tuple types. Does it matter whether tuples are stack allocated?
2. Show how to generate code for the tuple element access expression: define the value of E  [[ e[i] ]]
   
2. Subclassing and subtyping
   The language Ada 95 takes the position that when the code of a class C is inherited by some subclass D, all of the places where the type C occurs in its own method signatures is replaced by the type D. In addition, the type D is considered to be a subtype of  the type C when the class D inherits from the class C. Consider a class C with a single method:
   

class C { boolean equals(C); }

and a corresponding subclass D:

class D extends C { boolean equals(D); }

Despite its different signature, the method equals is considered to be the same method as in C, because of the substitution of D for C in the signature. In fact, the method equals will have this signature in class D whether or not its code is inherited from the class C. Is the Ada 95 rule safe? That is, does this rule allow a well-typed program to produce a run-time type error? Explain. What if the language allows this kind of inheritance, but the type D is not considered to be a subtype of C? Hint: consider all legal combinations of static and dynamic types that can occur at a method invocation.

3. Implementing Objects
   The bidirectional object layout uses negatively indexed dispatch vectors to allow limited forms of multiple inheritance with only a single word of dispatch overhead per object. Suppose that Iota⁺ were extended so that a class could extend both a class and an interface, but interfaces could still only extend a single interface. Methods declared in interfaces are indexed in the normal way, starting from 0. Methods declared only in a class are indexed starting at -1, with successively larger negative indices as we walk down the class hierarchy. In general, the first word in the object points into the middle of the object's dispatch vector. Draw the layout of objects of the class Triangle in both the standard C++ object layout and the bidirectional object layout:

   interface Shape {
     height(): int
     width(): int
   }
   interface ColoredShape extends Shape {
     color(): Color
   }
   class BaseShape extends Shape {
     lowerLeft, upperRight: Point 
     height():int = upperRight.y() - lowerleft.x()
     width():int = upperRight.x() - lowerleft.x()
     init() = ( lowerLeft = upperRight = new Point )
   } 
   class ColoredTriangle extends BaseShape, ColoredShape {
     topx: int 
     c: Color
     color(): Color = c
   }

4. Lattices
   1. Draw the Hasse diagram for the lattice consisting of the subsets of {a,b,c}, with the ordering relation ³.
   2. Consider a set consisting of all points (x,y) with non-negative integer coordinates. One point (x,y) is considered less than or equal to another point (u,v) iff x ´ u and y ´ v. Show that this set is a lattice and define the meet and join operators. Does the set have a bottom element? A top element?
      
5. Data-flow analysis
   In this problem we will identify code that may not terminate using data-flow analysis, by computing a lower bound on the execution time of the code. Assume that we have as input a control-flow graph in which the nodes are quadruples. We will pretend that all quadruples take 1 unit of time to execute -- even function calls. The output of the analysis will be, for every node in the graph, the earliest time at which this node could have been reached, assuming that the start node is reached at time 0. Nodes that are never reached are assigned the special value Infinity. If all final nodes of the graph has the value Infinity, the code will never terminate. In addition, nodes assigned this value correspond to unreachable nodes that may be removed from the control flow graph.
   1. One of the data-flow equations clearly will take the form out[n] = in[n] + 1. What is the equation for defining in in terms of out? What are the initial assignments to the nodes in the graph? Do any nodes need to be initialized with a value different from the others? Is this a forward or backward data-flow analysis?
   2. Draw the control flow graph for the following code, and show the operation of the worklist algorithm using the equations of part a.

      start
a = b + c
d = a < 10
L0: if d goto L1 else L2
b = a - 1
L1: a = f(d,e)
if a goto L0 else L2
L2: a = b
end

   3. Name two other standard code optimizations that, if performed before the dataflow analysis, can result in increased precision for this analysis of execution time.
      
6. Optimization
   The transformation known as loop peeling removes one iteration from the beginning of a loop by inserting a copy of the entire loop body before the beginning of the loop. Performing loop peeling followed by constant propagation and constant folding easily can result in code to which more optimizations, including more loop peeling, can be applied. Apply loop peeling and other optimizations to convert the following code to constant assignments:

   m = 1
i = 1
L1: m = m * i
i = i + 1
c = i < 5
if c goto L1