TIP exercises

Exercise 1

1. Implement the missing part (i.e. the visit method) of the TypeAnalysis class in the TIP implementation. (Hint: use pattern matching on node and invoke unify for the associated constraints.) Then test it on some relevant TIP programs.
2. Explain what happens in UnionFindSolver and TypeAnalysis if analyzing a program with recursive types.

Exercise 2

Implement your solution to SPA Exercise 3.21 (about TIP with arrays).

Exercise 3

Implement a Scala method in the TIP project that can check whether an operation as defined in the absPlus, absMinus, etc. tables in SignLattice in SignLattice.scala is monotone. (Optional: add a test script to test that all the tables in SignLattice are monotone.)

Exercise 4

Implement the missing parts in the localTransfer method in the SimpleSignAnalysis class. (Expected: 2 lines of code.) Then test the analysis on some relevant TIP programs.

Exercise 5

Implement the class PowersetLattice in GenericLattices.scala. (A simple solution requires only 2 lines of code.) This code is needed for some of the exercises below.

Exercise 6

Implement the missing parts in LiveVarsAnalysis, and test the analysis on some relevant TIP programs.

Exercise 7

Implement the reaching definitions analysis (this can be done with around 50 lines of code), and test it on some relevant TIP programs.

Exercise 8

Implement the very busy expressions analysis, and test it on some relevant TIP programs.

Exercise 9

Implement and test the analysis from SPA Exercise 5.35.

Exercise 10

Finish the implementation of the widenInterval method in IntervalAnalysisWidening. (Expected: 1 line of code.) Them test the analysis on some relevant TIP programs.

Exercise 11

Implement the two missing parts in InterprocValueAnalysisFunctions.

Notice that this implementation of value analysis uses the lifted abstract state lattice, where the bottom element represents "unreachable". (Thereby the lattice can also be used for context sensitive analysis.) So don't forget that the entry of the main function is always reachable, and that function exits may be unreachable.

To be able to run the analysis, you need to insert your solution from Exercise 4 into ValueAnalysisMisc.localTransfer (for variable declarations and assignments). With this in place, you can run for example SignAnalysis.Interprocedural.WorklistSolverWithReachability (using -sign iwlr from the command line).

Exercise 12

ControlFlowAnalysis.scala contains a partial implementation of the control flow analysis for TIP, using CubicSolver. Implement the missing parts of ControlFlowAnalysis, and test it on some relevant TIP programs.

Exercise 13

Implement the missing parts in AndersenAnalysis and test it on some relevant TIP programs.

Exercise 14

Implement the missing parts in SteensgaardAnalysis and test it on some relevant TIP programs.