Rapid Type Analysis (RTA) is a whole-program interprocedural analysis for OO 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 Whirlwind-specific details of program representation, 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 a copy of this system, one group member should execute the following command:
% /projects/instr/04wi/cse501/bin/cvs-import-latest <group_name>
This will have the effect of importing the latest version of Whirlwind into the group's shared copy of the compiler. (You may have conflicts between your group's pts-to.cecil file and the sample-solution pts-to.cecil file. You should probably take the sample solution, since there have been a couple of other changes to Whirlwind that would require you to make a couple of small changes to your sample solution to get it to work again. Just move your pts-to.cecil file to some other unused name before running the command above.)
Then each project member can do the usual cvs update -d to get the new stuff into their working copy.
The file vortex/Cecil/src/whirlwind/passes/rta-compute.cecil is the file you'll need to change; search for WRITE ME for the places that need your attention. The rest of that file is also important to understand, so that you know the role of the half-dozen methods that you need to implement. The effect of your analysis should be to populate instantiable_classes, callable_funs, and callable_gfs with as small a set of class_nodes, fun_nodes, and gf_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/Cecil/src/whirlwind/ir/rta/rta-computed.cecil provides the interface to those clients. Search for calls of is_instantiable_class and is_callable_{fun,gf,method} for the current set of 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 the default to on. You also should use the rta_msgs option to control debugging information output during the analysis. You also should set the skipping_unreachable_funs_msgs option to 1 if you want to get a notice whenever a client pruning optimization has occurred.
In addition to your own test files, you should exercise your system 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:
Whirlwind> append source_paths $PROJECT/vortex/Java/src/example/wil $PROJECT/vortex/Java/wil-stdlib $PROJECT/vortex/Java/wil-stdlib/native
where $PROJECT should be changed to be wherever your copy of the 501 project is. 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 make <bench>.wil to compile it.
When I run my RTA-enabled compiler on the towers.wil benchmark, the size of the compiled program is cut roughly in half!
One member from each group should send an email to Craig and Sorin by the beginning of class on Monday, March 8th with your modified rta-compute.cecil file as an attachment. You should also report the result of doing size towers on versions of the towers.wil benchmark compiled with optimization and with RTA either on or off.