Weekly Journal

Home | DMP | Project | Journal | Contact
Week 1 | Week 2 | Week 3 | Week 4 | Week 5 | Week 6 | Week 7 | Week 8 | Week 9 | Week 10

WEEK 1

This week has been interesting, exciting, and a bit frightening. And it's the easiest few days I'll have this summer! I started work on Tuesday, May 28, but the dorms here at UD don't open until Sunday. I've been staying with my boyfriend's family...one more week of home cooking before I must step out to face the cruel world of cafeteria food and restaurant hopping.
My first day of work was dominated by orientation. The other DMP student (and my roommate!), Emily Gibson, and I received our lab keys and UNIX accounts and met with our mentors for an introduction to our projects and lab policies. Professors Lori Pollock and Amie Souter also gave us a quick tour of the campus and downtown Newark and introduced us to the lab group.
My goal this week is to gain a basic familiarity with Java syntax and concepts. I've been reading Thinking in Java by Bruce Eckel and am impressed with the way in which the material is presented and the integration of examples with the text. The source code is even included on a CD-ROM so I can execute the programs myself. I really enjoy learning about Java, and my comfort zone is increasing daily. But when it comes to computing knowledge, I feel very overwhelmed and outclassed. I am learning a new windowing environment, which is quite frustrating, and am working with new compilers and commands that have a tendency to make my head spin. Everyone else seems like such an expert! I think that with time and hard work, though, I'll learn a great deal and achieve some degree of success in my research.

Emily and Me

WEEK 2
The FLEX compiler is the bane of my existence! Amie and I spent 3 days trying to download and install it from the FLEX site at MIT. Nothing worked, and we eventually had to give up on the source code and start a new process through CVS. I was very frustrated, especially when the FLEX website went down on Tuesday; we couldn't even look at the references. As of today (Friday), everything seems to be working. Most of my time this week has been spent figuring out how the FLEX system works and how to integrate its many classes into the call graph construction algorithm. I've been looking at a lot of documentation, and the PAMain testing program finally makes (almost) complete sense.
I am also looking into Java constructs in more detail and have discovered that I have learned something about my Sun workstation! I was able to fix a massive influx of errors by editing my classpath in .cshrc - with no help at all!! The most exciting part of the week was coding applets, some of which I may include on this site after further improvements.

WEEK 3
My focus this week was on modifying existing FLEX classes to create a basis for implementing the Delete_Call_Site algorithm. The program I have been working on creates the call graph and accessory data structures and shows different statistics, depending on the command line options entered by the user. I'll be doing testing early next week, but the goal is to be able to assert that a meta call graph (template call graph) has been created and is ready for reanalysis.
I also researched the existing Java classes and functions relating to call graphs and spent significant time with the algorithm itself. I plan to have the algorithm requirements matched to appropriate data structures and representations by the end of week 4. Some of my research has been posted:

Relevant Java Classes and Methods (always in progress)
Delete_Call_Site Algorithm
At the moment, I am sending some spec benchmarks through my main program. It is very similar to the PAMain.java included in the FLEX download but much more compact, with all pointer analysis eliminated and some changes in coding and naming conventions. After a frustrating morning of making small edits, I was able to run my DelCallSite program on a simple .java file! Of course, the hard part isn't the initialization; it's the actual algorithm implementation. I'll be rereading Amie's dissertation and research on incremental call graph reconstruction and analysis before diving in head first.

WEEK 4
I have been working with the MetaCallGraphImpl code this week - basically, the implementation of the template call graph. There have been many more difficulties than I expected, but that comes from adapting another programmer's code. I am eternally grateful to the FLEX people, as they have provided a basis for building and using call graphs. It is difficult, however, to interpret someone else's programming style when I'm not simply using the interface but making significant changes to gear it to a specific application. Names for the class fields were also used as parameters to functions and temporary variables, and objects were often passed through several levels of functions without explicit indication. I had to spend a great deal of time making the code readable as well as finding the places that needed to be modified.
The biggest obstacle is that the original code doesn't cover the reaching types, etc. for return values. Luckily, there is a Quad subclass, RETURN, that represents return statements, but it had to be worked into an implementation that dealt solely with call sites. Call sites are vital to the algorithm, but the sets del_types and add_types require the computation of reaching types upon returning from a template (meta-method)...
End of the week: After spending more time with the code and documentation, I believe that the RETURN additions and modifications may be unnecessary. Information on the templates (meta-methods) themselves and structures generated during the construction of a MetaCallGraph may provide the return types if I write some simple accessor functions. Luckily, I have kept a record of all the modifications I have made to the original classes (with the exception of coding convention changes). I plan to pursue this last line of thought to its conclusion and then worry about eliminating previous changes if necessary.

WEEK 5
Monday: I have completed a prototype implementation of the first two steps of the Delete_Call_Site algorithm. I hope to have the first outer for loop implemented completely, with propagate_update stubbed out, within the next two days. The question of the moment is how to retrieve or compute the set of possible return types for a given meta-method.
Wednesday: I am in a rut; I still haven't solved the CALL return value problem, although I've spent hours with the MetaCallGraphImpl code. On the other hands, I know much more about Quads and other FLEX classes than I did a few days ago. I am still searching for the answer to Monday's question, although I have been working on several minor tasks - editing the output produced upon call graph construction, adding new classes to my reference site, and researching referencing and aliasing in Java (an issue that came up in the MetaCallGraphImpl code).
Thursday: I feel rather silly right now, as I think I've found a solution to the delete_types_after problem. It's so simple that I can't believe I missed it before; I was trying too hard to find the most complicated process possible. Here's the proposal:
At a call site, an HMethod is specified. This HMethod can be specialized; it corresponds to potentially many MetaMethods. But MetaMethods are simply HMethods plus types for the parameters - types that are identical to or narrower than the types declared for the formal parameters of an HMethod. Thus, all we need to get the possible return types for the method called at a call site CS is the HMethod - not the individual MetaMethods. CS.method() returns the HMethod invoked by CS, and HMethod.getReturnType() returns the HClass representing the formal return type of the receiver. We can construct the set of possible return types by finding all subclasses of the formal return type (including the formal type itself) that can be instantiated by the analyzed program and implement the desired HMethod.
If we do not destroy the set of instantiated classes (cInstantiatedClasses in my MetaCallGraphImpl code) before exiting the call graph constructor, it is simple to call get_possible_classes (It must, of course, be made public.), which returns exactly the type set desired. Now I can move on to add_types_after!!
Friday: After our Friday meeting, my work on delete_types_after was approved, and I have some promising direction in terms of add_types_after. I'm very glad to be tackling something new, although I've learned to be more realistic regarding time goals. I'm working with completely new concepts and a new language, so it's going to take a while to sort everything out and bring the algorithm to virtual life. I'm looking into ways to calculate or retrieve the reaching types of a variable that is assigned the return value of a call. The two main options at this point are TypeInfo and ReachingDefs, although I'm already leaning toward ReachingDefs, as TypeInfo has specific intermediate representation requirements.
WEEK 6
Due to the 4th of July holiday, this week was shorter than most. I feel as if I accomplished something, though, especially on Wednesday. I removed all modifications to the original FLEX MetaCallGraph and MetaCallGraphAbstr classes, since the functionality I desire for my particular implementation is definitely not necessary for all implementations of the MetaCallGraph interface. I have either completed or am very close to completing the calculation of the add_types_after set and have begun to look at the second part of the algorithm, which propagates changes to callers. I added some auxiliary functions to my implementation and have begun piecing together this new phase of the code for the algorithm.
I decided on ReachingDefs for the add_types_after and, once again, after many headaches, found a simpler-than-expected possible solution. I modified the template call graph implementation to handle return variables as well as call site parameters. In an assignment like

x = q.m(param1, param2,...);
the original MetaCallGraphImpl computed the possible reaching types of x (the "retval Temp") very conservatively. Since I chose to calculate types generated by the call site by taking the set of instantiated subclasses of the formal return type of the HMethod invoked by the call, and the FLEX template call graph construction basically did the same thing for the "reaching types" of the retval Temp, the algorithm would not operate properly. The same types would be deleted and added (if get_possible_classes was also called on the GenType associated with the retval, as I would recommend); we would be back at square one, having wasted time and system resources. I modified the construction functions to perform strongly connected component and reaching definitions analysis on retvals (like x in the example) as well as on parameters (param1, etc.). A map from call sites to a set of GenTypes (for the call site's retval) is maintained, even after exiting the constructor. I'm still testing to see if this approach produces different type sets than those in the delete_types_after set.
While performing testing, I began to look at the second half of the Delete_Call_Site algorithm. I started looking at the MetaAllCallers class. The MetaAllCallers constructor takes a MetaCallGraph parameter and basically inverts the edges, providing a quick way to return the callers of a given meta-method. The penalty for construction of a MetaAllCallers object is insignificant, as most of the computation is performed during the MetaCallGraph computation. I also added functions to my implementation of the meta call graph - getCallSites(MetaMethod inMM1, MetaMethod inMM2), which returns the set of all call sites in the code of inMM1 that map to inMM2, and getCallSites(MetaMethod inMM, HMethod inHM), which returns all call sites in inMM that call some (meta-method) specialization of inHM.

WEEK 7
As frustrations continued to trickle down from previous weeks, I decided to spend much of this week doing additional research and equipping myself to tackle the more challenging aspects of type handling. Amie provided some helpful slides on type handling in general, which got me thinking. I had been confused about the connection between dependency detection and type inference in the FLEX code, and this resource made the murky waters much clearer. For a summary of the relevant information, see my page about type handling.
Amie also gave me a short paper by Ole Agesen, The Cartesian Product Algorithm: Simple and Precise Type Inference of Parametric Polymorphism. From this, I learned a great deal about typing systems, templates, and the Cartesian product algorithm - the basis of Delete_Call_Site's incremental reanalysis. I was able to draw parallels between Agesen's theory and the FLEX implementation for the meta call graph; it was as if a door to understanding was suddenly throw open. I continued my research by finding and studying Agesen's dissertation, Concrete Type Inference: Delivering Object-Oriented Applications.
After reading and studying relevant sections of the texts, I started to compile what I had learned and to apply it to the problem at hand. This information, which will hopefully be helpful to people studying the current project and other similar issues, can be found on this website under Project: Research.
I also fixed a simple semantic error. Tests showed that both the add_types_after and delete_types_after sets were faulty. I had been calling get_possible_classes on the formal return type of the method and the callee itself, but this returns the subclasses of the return type that implement the callee method. The set we actually need is obtained from get_instantiated_children, which returns the set of all subclasses of the input HClass - including that HClass itself (in Delete_Call_Site, the formal return type) - that could be instantiated by the target program. A few small changes remedied the problem; delete_types_after and add_types_after now consist of the possible return types, rather than the possible declaring classes. I felt rather silly because such a mistake had gone unnoticed for several weeks, but it was satisfying to eliminate the error and run successful tests.

WEEK 8
I spent most of this week working on my website and posting research. I added graphics and a no frames option and started experimenting with navigation bars. I also returned to the MetaCallGraphImpl code and did a quick reanalysis, keeping in mind the lessons learned during the past few weeks. I have many new ideas regarding the implementation of Delete_Call_Site! See my implementation page for details. (This part of the site is still very much in progress.)
add_types_after and delete_types_after had meaningful values as of the beginning of this week, but tests showed the two sets to be identical in all cases. Because of my research, I was able to determine a possible reason for this problem. Reaching definitions correspond to a particular variable read (or use). The reaching definitions for a given use are the definitions that may determine the value of the variable at that point in the program. The FLEX classes make an important - and consistent - distinction between variable definitions and uses. In the MCGExactTemp class, for example, each temporary variable is either a DEF or a USE. And Quads have separate methods to return all Temps used and all Temps defined within the receiver Quad. Until this week, I had been trying to modify the template call graph implementation to compute reaching definitions for definitions, which simply does not work. Assignments are destructive in Java; each assignment overwrites the last. And the occurrence of the variable to which the assignment is made is counted as a definition, not a use. Thus, the only reaching definition for x in x = variable.method() is the very definition supplied by variable.method(). Basically, you can't have a valid reaching definition for a definition, and that is what I was trying to do for add_types_after. I have a lot of work ahead of me, but, one the positive side, I have a new direction.

WEEK 9
Wednesday: I have spent the past few days immersed in implementation details. delete_call_site and propagate_update are no longer code fragments but viable skeletons. Of course, some aspects have not yet been implemented, but all of the necessary structures are in place. delete_call_site has moved to MetaCallGraphImpl5 (instead of being a static method in the main program that takes a call graph parameter). Right now, I'm working on getting a valid set of added reaching types by examining the call site's predecessors. The problem lies in somehow getting to types from a set of Temps. I am also unsure if Quad.prev() actually returns the statements I desire. Constant testing is in progress.
Friday: Tests for reaching definitions seem to be working; the reachingDefs method returns a valid list based on the body of the analyzed method, and MCGExactTemps have been found for the reaching definitions of each Temp used in a CALL quad (a call site). Of course, this isn't what we want for add_types_after, but it's an important step. If preexisting MCGExactTemps corresponding to the Temp storing the return value at a given call site can be found "within" the predecessors of this call site, we've accomplished a major goal. The reason these MCGExactTemps must already be in place is that their GenTypes were computed during dependency detection and type inference. We don't perform this analysis during delete_call_site and thus must depend on existing data structures.
I also worked on my website a bit and spent time reading past DMP participants' final reports to get ideas for my own, which I will have to finish next week. I wish I had more to show for my time and effort, but I have learned a great deal, and I'll be working on the implementation until the end of my mentorship.
While waiting for executions to run, I began to learn JavaScript from a WebMonkey tutorial. I didn't want to make my website too busy looking, so I settled for some image swaps that give the appearance of buttons being pressed and released.

WEEK 10
Although I was able to run several final tests and try some new ideas regarding the add types, the focus of this week was on tying up loose ends. I wrote my final report and worked on a readme specifying how to run my main program (/Harpoon/Code/Main/DelCallSite) from the command line, a status report for Amie, and a graphical representation of control flow in the MetaCallGraphImpl5 constructor. I uploaded the final report to my website and made some last minute changes to its appearance and content. Writing so much makes the days seem rather long! I'm excited to be going home, but I think I'm really going to miss the people, the lab, and the project. Amie and I plan to keep in touch, and if I have free time at school this coming semester, I'd like to try to make the implementation fully functional. I'm disappointed that I wasn't able to accomplish all of my goals, but I have lots of ideas for the future. This was a wonderful summer!

Home | DMP | Project | Journal | Contact
Week 1 | Week 2 | Week 3 | Week 4 | Week 5 | Week 6 | Week 7 | Week 8 | Week 9 | Week 10