198:516 Homework 3 Spring 2006

1. Using the following pseudo-Java program, show the difference in the
call graphs obtained if you use RTA versus VTA.  Can you 
show a 1 statement change that would make the 2 call graphs the same?

      public class A{
        public void main(){ 
          if (..)  f(new B()) else f(new C());
        }
        public static void f(A a){
             A aa = new A();
             a.m();
             ...
        }
        public void m(){...}
      }
      public class B extends A{
        public void m(){...}
      }
      public class C extends A{
        public void m() {...}
      }


2. Using the program below:
a. Simulate Andersen's points-to analysis on this program using a 
worklist algorithm for the first 10 steps.  
b. What sorts of values are on the worklist and how would you organize it? 
c. What's the final points-to graph for this example?  
d. Would the graph be different if you performed a context-sensitive 
analysis?  Why or why not?

public class A{
    public void main(){
      A a;
      if (..) a = new A(new B()) else a = new A(new C());
      a.ds.f();
      a.ds.printme();
    }
    public A(D d){
      ds = d;
    }
    protected D ds;
}

public class E extends A{}

public class D{
    protected A aa;
    public void printme(){System.out.println("I am a D");
}

public class B extends D{
   public void f(){
      this.aa = new E();
   }
   public void printme(){System.out.println("I am a B");
}

public class C extends D{}
   public void f(){
     this.aa = new D();
   }
  public void printme(){System.out.println("I am a C");
}


3. Construct an example to use with Andersen's points-to analysis that
shows the difference between nofields, field-based and field-sensitive
analyses. (Recall that nofields does NOT distinguish between the
points-to sets of distinct reference fields of an object, field-based
uses one abstract object of each type with fields to represent ALL
instantiations of that type, and field-sensitive uses objects named
by creation sites with their individual fields points-to sets distinguished.

4. Think about the 4 types of reference assignments in Andersen's 
points-to analysis and their corresponding flow functions, if we consider using
an 'exploded' call graph as our program representation.  
a. Are these functions monotone? distributive?  k-bounded?  
b. What can we say about the solution lattice for this problem?