Exercises for PAG/WWW

Thanks to Hanne Riis Nielson there is a list of suggested exercises for PAG/WWW:

• Modify the live variables analysis to perform faint variables analysis: A variable is a faint variable if it is dead or if it is only used to calculate new values for faint variables; otherwise it is strongly live. As an example, consider the program fragment
  x := 1; x := x-1; x := 2
  with the assumption that x is dead afterwards. Then x will be faint after each of the three assignments (whereas it is dead after the second and third assignment, but live after the first assignment due to the usage in the second assignment).
  
  
• A detection of signs analysis will model all the negative numbers by the number -1, zero by 0, and the positive numbers by 1. So the set {-2,-1,1} will be modeled by the set {-1,1}, that is an element of P({-1,0,1}). Modify the constant propagation analysis to perform a detection of signs analysis.
  
  
• A parity analysis models all the even numbers by the number 0 and all the odd numbers by 1. So the set {0,2} will be modeled by {0} whereas {0,1} and {0,1,2,3} are modeled by {0,1}. Modify the constant propagation analysis to perform a parity analysis.
  
  
• Modify the constant propagation analysis to take the values of conditions into account by having two transfer functions associated with boolean expressions, one to be used in the case the true branch is followed and one to be used in the case the false branch is followed.
  
  
• The upwards exposed uses analysis is the dual of the reaching definitions analysis: it determines for each definition of a variable which uses it might have.
  
  
• The copy-propagation analysis determines for each program point if there is a path to it from a copy assignment, say x := y, where there are no assignments to y.
  
  
• The dominator analysis determines for each assignment which other assignments it is dominated by. An assignment is dominated by another if every possible execution of the latter will be preceded by an execution of the former.

Search