Rapid Type Analysis (RTA) is a whole-program interprocedural analysis for object-oriented languages, developed originally by Bacon & Sweeney and published in OOPSLA'96. (Get your own copy here and read it. The "algorithm" is sketched in a single paragraph in section 2.3!) It identifies those classes in a program that are possibly instantiated, and those methods that are possibly called. This information can be used to prune out any compilation work or imprecision due to uninstantiated classes and uncalled methods.
You will implement RTA in Whirlwind, and apply it to WIL files translated from Java programs. We have developed a skeleton for this algorithm that serves to isolate you from as many of the Whirlwind-specific details of program representation as possible, and we have implemented several simple hooks in other places in the compiler that use the results of the analysis to prune unreachable code. To get the latest version of the skeleton code, you should follow the directions for Code Updates.
The file vortex/Diesel/src/whirlwind/passes/compute-rta.diesel is the file you'll need to change; search for WRITE ME for the places that need your attention. The effect of your analysis should be to populate instantiable_classes_no_dep, callable_gfs_no_dep, and callable_funs_no_dep with as small a set of class_nodes, gf_nodes, and fun_nodes, respectively, as possible. Other files take these results and perform the unreachable-code-pruning operation (unlike the previous milestone, you don't have to implement any transformations, only the underlying analysis). The code in vortex/Diesel/src/whirlwind/internal-rep/globals/rta.diesel provides the interface to those clients. Search the Whirlwind implementation for calls of is_instantiable_class and is_callable_{fun,gf,method} for the current clients. (More are possible!)
In the initial system, RTA is disabled by default. It is controlled by the rta option. You can manually enable RTA every time you want to use it, or edit your own ~/.whirlwindrc file to turn rta on every time you run Whirlwind, or change its default to on by editing its definition in rta.diesel. You also should use the print_compute_rta_progress option to control debugging information output during the analysis. You also should set the pruning_unreachable_code_msgs option to 1 if you want to get a notice whenever a client pruning optimization has occurred.
You should exercise your RTA-enhanced compiler on the standard test.wil file and on the Towers of Hanoi Java benchmark, found in vortex/Java/src/example/wil/towers.wil. To compile this Java benchmark, do the following at the Whirlwind prompt (expanding $VORTEX_HOME to its real value in the commands below):
Whirlwind> append source_paths $VORTEX_HOME/Java/src/example/wil $VORTEX_HOME/Java/wil-stdlib $PROJECT/vortex/Java/wil-stdlib/native ... Whirlwind> makeo1 towers.wil ...
There are a number of other Java benchmarks also translated, in /projects/cecil/WIL-src/Java/<bench>/<bench>.wil; just add /projects/cecil/WIL-src/Java/<bench> to your source_paths option, and then you can do makeo1 <bench>.wil to compile it.
The main goal of RTA is to strip out unused code, which is particularly useful for small programs compiled against large libraries, e.g. most Java programs. When I use my sample solution to compile the towers.wil benchmark, with RTA on and off, on Linux, the sizes of the compiled programs (along with the empty WIL program, to identify the fixed size of the libraries linked with every WIL program), as reported by Unix size, are as follows:
text data bss dec hex filename 726832 11964 413508 1152304 119530 towers RTA ON 1010552 12316 421444 1444312 1609d8 towers RTA off 561744 5660 401316 968720 ec810 empty
Ignoring fixed overheads (i.e., the size of empty), towers with RTA is 183k, while towers without RTA is 475k; a 60% reduction!
A key claim to fame about RTA is that it is a linear-time algorithm: it can compute the set of reachable classes and methods in a single linear pass, and with an overall linear amount of work. A key component of this is maintaining clever data structures so that as a class or a method name (a generic function in WIL) becomes reachable, the previously scanned parts of the program that are now reachable can be identified quickly.
What is the computational complexity of your implementation? You may assume the usual complexity assumptions about standard data structures, e.g. that hash tables and hash sets have O(1) access time. You may also assume that each method predicate is bounded by a constant, i.e., that the size of method predicates does not grow with program size. I believe that, with these assumptions, my sample solution is indeed linear.