CSCI 5535: Homework 4

Due date: October 25th, 1999 at 5:00 p.m.
Please submit your solution on paper.
 

1. (30 points) This question deals with Steensgaard's paper.  For the purpose of this question, assume that you have simple programs without any procedures or calls (including to "allocate" or "op").  In other words, ignore the type rules in Figure 3 that have anything to do with "lam" and "allocate".  This should leave 4 rules for you to consider.
1. One of the weaknesses of this analysis is that it allows each storage shape graph node (type) to point to at most one storage shape graph node (type).   Give an example program that exposes this weakness.  Also walk through the steps that Steensgaard's algorithm would take to infer the types (and thus pointer information) for this example.
2. Give and explain an example that illustrates the added precision due to the <= (this is the triangle with the equal sign in the paper).  Also explain using the same example how doing cjoin, rather than join allows the algorithm to get the greater precision.  Also argue whether or not you feel that this added precision would actually translate into better results in practice.
3. Let's say you want want each storage shape graph node to point to up to two other nodes (rather than just to a single node as in Steensgaard's analysis).   In this case, the types may look as follows:

  alpha ::= beta x gamma
  beta ::= tau1 x tau2
  gamma ::= lambda1 x lambda2
Update the four type inference rules to reflect the new type system.
2. (20 points) Give an example where Lackwit would report a problem when the code is actually correct.
3. (20 points) Give an example where Steensgaard's pointer analysis would compute more precise results than Diwan et al's tbaa (assume SMFieldTypeDecl).  Give another example where SMFieldTypeDecl would yield better results than Steensgaard's analysis.