CSE647: Robust (Distributed) Software (Spring 2002)
                              Scott Stoller
			  Homework 6: Solution
Due: 29 April

This homework is about: John Whaley and Martin Rinard, Compositional
pointer and escape analysis for Java programs.  In Proceedings of the
14th Annual ACM SIGPLAN Conference on Object-Oriented Programming
Systems, Languages, and Applications (OOPSLA), 1999.

1.  Give a program such that, in the PTE graph for some analysis scope of
that program, some object may be represented by both an inside node and a
parameter node.  Or, argue briefly that this is impossible.  If it is
possible, show the PTE graph for the appropriate analysis scope, and
explain briefly why it satisfies the above requirement.  You do not need
to describe the execution of the analysis algorithm that produced the PTE
graph.  Make the program as small and simple as possible.  Your program
may contain 1 or more methods, as needed.  A program that has more than
about 6 statements total in all methods is unnecessarily complicated.
Express the program as a control flow graph whose nodes are labeled with
statements of the kind in section 4.1.  You do not need to give the
corresponding Java program.

Clarification: I meant that the object can be represented by both kinds
of nodes *at the same time*, i.e., in a single PTE graph computed for
some program point in some analysis scope.  I didn't take off points for
answers that didn't reflect this condition (since I forgot to state it),
although some such answers had other problems.  Without this condition,
the answer to question 1 becomes "yes, it's possible".

Comment: A few people made statements like "Therefore, n is both a load
node and an inside node."  Literally interpreted, this can't be true.
This statement does not distinguish sufficiently between the nodes (in
the PTE graph) and the objects (in the concrete heap) that they
represent.

Answer: This is impossible.  Parameter nodes can represent only objects
created before the start of execution of the method being analyzed.
Inside nodes can represent only objects created by the method being
analyzed.

2.  Same, except for inside node and load node.

Answer: This is possible.  Suppose m is analyzed first, i.e., before
analysis of m2.  In the PTE graph at the last program point in m,
inside node n1 and load node n2 represent the same object.

class C { 

  Object f;

  static m() {
    Object o = new Object;   // inside node n1
    r = m2(o);
    o1 = r.f;                // load node n2
  }

  static m2(Object p) {
    C c = new C;
    c.f = p
    return c;
  }
}

3.  Same, except for load node and return node.

Answer: This is possible.  Suppose m is analyzed first, i.e., before
analysis of m2.  In the PTE graph at the last program point in m,
return node n1 and load node n2 represent the same object.

class C { 

  C f;

  static m() {
    r = m2();               // return node n1
    c1 = r.f;               // load node n2
  }

  static m2(C p) {
    C c = new C;
    c.f = c
    return c;
  }
}