CREATION / INSTANTIATION

When an instance of MetaCallGraphImpl5 is created...

Normally, the call graph and the set of instantiated classes (cInstantiatedClasses) would be computed simultaneously, but the FLEX implementation uses the class hierarchy to generate the latter. Since for any class C such that a new T object might be created by the target program, at least one method of T must be executed, the set of actually instantiated classes can be approximated by reviewing the non-abstract declaring classes of all callable methods that are not static. Array classes are added as well.

For each HMethod (basically, a standard "method") in the set of program roots that was passed into the constructor, analyze(HMethod) is called. Taking a conservative view, the FLEX programmers treat each root method as polymorphic, as it could be called with arguments of any subtypes. analyze(HMethod) simply creates a new "polymorphic" meta-method - the types appearing in the method declaration are considered to be polymorphic - and passes it to analyze(MetaMethod).

analyze(MetaMethod) initializes a worklist (cWMM) and adds the meta-method argument to this worklist, which will be modified during analysis. Until the worklist is empty, a meta-method is removed, stored in cMMWork, and added to a growing set of analyzed meta-methods. analyze_meta_method() is called, with cMMWork being "passed" as a class field.

analyze_meta_method() is the heart of template call graph construction, calling the most important auxiliary functions and directing the generation of meta-methods and graph edges. The function first examines the HMethod of which the current meta-method (cMMWork) is a specialization; if it is a native method, there is no code to analyze, and we move on to the next meta-method in the worklist described above. Otherwise, get_method_data is called on the underlying HMethod.

get_method_data(HMethod inHM) looks for the method data of inHM in the Map cMh2md and returns this MethodData object. If no MethodData is found, it must be computed before get_method_data may return. The HMethod in question is converted to an HCode representation - corresponding roughly to a list of instructions. All call sites and method returns (CALL and RETURN Quads) are located and stored in the appropriate data structures. The set of call sites (and perhaps the set of returns) will be used during future analysis. get_method_data then initializes (or reinitializes) cEts2et, the Map from tuples to full MCGExactTemps and creates a ReachingDefs instance for the HCode version of the HMethod. get_initial_set traverses the set of call sites; for each parameter at each call site, if the type is not primitive, an MCGExactTemp for the parameter is added to the returned "initial set". Basically, get_initial_set returns the set of MCGExactTemps pertaining to the arguments of all the CALLs in the code of inHM.

This set is used in the computation of strongly connected components (SCC) as the first argument to the call compute_scc(myInitialSet, myRDef), where myRDef is the ReachingDefs object for the method code. compute_scc generates a topologically sorted list of strongly connected components containing the definitions of temporary variables pertaining to call site arguments. An edge from node A to node B represents the relationship "the type of MCGExactTemp A influences the type of MCGExactTemp B". The elements of the input initial set are added to a worklist, and the dependencies for each MCGExactTemp are determined through getDependencies. Any MCGExactTemps that influence the type of an element in the worklist are themselves added to the worklist and processed. Upon completion of the first stage of complete_scc, the next and prev fields of all the MCGExactTemps connected directly or indirectly (through dependencies) have been assigned meaningful values. next holds an MCGExactTemp[] of the MCGExactTemps whose types are influenced by the type of the receiver, and prev holds an array of those MCGExactTemps whose types influence the type of the receiver.

The work of compute_scc is far from over; the second step builds and sorts the SCC graph. A call to SCComponent.buildSCC constructs the graph containing all nodes reachable on paths that originate in nodes from the input set of all MCGExactTemps analyzed in part one. This call returns the sets of SCComponent roots - those nodes with no entering edge. Based on the root nodes, a topological sort is performed. All SCC reachable from one of the roots are sorted into a double linked list in decreasing topological order. Finally, compute_scc returns the first - one of the topologically biggest - SCC in the sorted graph. A control flow graph connecting related variables and types has been construted.

Control passes back to get_method_data, where a new MethodData is created based upon the SCC, the mapping from MCGExactTemps to their corresponding <Temp, Quad, DEF/USE> tuples, and the set of call sites in the method. A mapping to the appropriate HMethod is added, and the MethodData is returned. (Of course, if MethodData had already been in place for a given HMethod, there would be no need to call get_method_data in the first place, as mentioned above.

We have now returned to analyze_meta_method and can assert that a valid MethodData object is in place for the HMethod underlying the meta-method cMMWork. This HMethod is converted to HCode, and set_parameter_types is called with cMMWork and the HCode representation as arguments. This function sets the types of the parameters underlying cMMWork, using the appropriate type specializations. It first checks to ensure that the number of arguments in the call site matches the number of parameters of the callee and then adds the GenTypes computed for each formal parameter to the set of possible types (probably empty at this point) for the MCGExactTemp representing the corresponding argument in the call site.

compute_types is the next method called from analyze_meta_method. compute_types calls process_scc for each SCC retrieved from the MethodData, in top-down order; basically, types are added to the MCGExactTemp nodes. process_scc works with one SCC at a time. All nodes of the input SCC are added to a worklist, from which they are removed and analyzed. The type set of each MCGExactTemp is stored in a temporary variable before processing, and the MCGExactTemp's Quad is visited by a type inference Quad visitor that may add new types. For variable uses within call sites, for example, all reaching definitions (obtained by MCGExactTemp.prev) are merged. If the old and new type sets are not identical, all nodes in the SCC depending on the type of the current MCGExactTemp (the next field) are added to the worklist. The type changes must be propagated to these MCGExactTemps.

After control returns to analyze_meta_method from the type inference steps, analyze_calls() is called. Once again, information is "passed" through fields - the current meta-method through cMMWork and the set of call sites in that method through cCalls. analyze_calls simply calls analyze_one_call for each call site, in the context of the current meta-method cMMWork.

analyze_one_call(CALL inCS) is one of the most complicated parts of the template call graph implementation. The HMethod invoked by the call site and the number of arguments are stored in temporaries (myHM and myNbParams, respectively) before analysis begins. cParamTypes, which will store the possible types of each argument, is initialized or reinitialized to a new GenType[myNbParams]. There are many different cases to consider when analyzing a call site. The first, and simplest, case is that of a non-virtual or static callee. Static methods, constructors, and static initializers fall under this category. After a check for possible thread start sites (for native callees only), rec(myHM, inCS, 0, myNbParams) is called, after which analyze_one_call returns. (rec, an important method, will be discussed in detail after the structure of analyze_one_call is outlined.)

The next case is that of a non-static, native callee. Specialization of a native method is infeasible, as their bodies cannot be analyzed; there is no need to call rec. The first element in cParamTypes - the receiver - is assigned a polymorphic GenType with the callee's declaring class or interface as the root of the type cone. The other arguments are assigned GenTypes rooted in the formal types of their corresponding parameters in the callee's type signature. analyze_one_call then invokes specialize_the_call, which generates a new meta-method for the callee, with the types stored in cParamTypes, and records the caller-callee relationship between cMMWork and this new meta-method at the call site under analysis. If the new meta-method has not yet been analyzed, it is added to the list of templates to be analyzed (in analyze(MetaMethod)). Both specialize_the_call and analyze_one_call return, bringing this case to a close.

At this point in analyze_one_call, we know that the method invoked by the call site is non-static (has a receiver) and virtual. The first parameter, the method receiver, is handled in a special manner. An iterator enables the examination of each GenType in the type set of the receiver; depending on whether the GenType is monomorphic or polymorphic, treat_mono_base or treat_poly_base is called. Both functions handle the receiver type(s) and then move on to deal with the standard arguments by calling rec.

rec and specialize_the_call work together to generate all possible combinations of types for the parameters of the callee, create meta-methods, record the caller-callee relationships, and add new meta-methods to the worklist. rec serves as a framework for specialize_the_call, which was outlined above. It is a recursive function that, along with the iterator over the receiver types in analyze_one_call, enables the calculation of the Cartesian product of the type sets; each element of the product set becomes a new template (meta-method), as prescribed by the CPA. rec takes four arguments - an HMethod, a CALL, and two integers, the starting and maximum positions in the parameter array (inPos and inMaxPos, respectively) - and generates type combinations. For each possible type of the inPos^th parameter (The 0^th parameter is the receiver.), it sets cParamTypes[inPos] to that type and recurses on the remaining parameters. In this recursive call, the third and fourth arguments are inPos+1 and inMaxPos. When rec is called with inPos == inMaxPos, recursion halts, and specialize_the_call is invoked to build the newly determined meta-method and add it to the call graph. Thus, templates are generated only for the argument combinations that can actually occur in call sites of the target program, in keeping with the Cartesian product algorithm.

When all meta-methods in the worklist have been processed by analyze(MetaMethod), the set of meta-methods analyzed is added to the class field all_meta_methods. Upon return from the constructor, this field will hold all meta-methods that may be called during execution of the target program.

Finally, compact() is called; caller/callee relationships are stored in a more compact format for future retrieval by accessor functions. The constructor also sets many of the "class globals" to null, as they are no longer needed, and invokes the garbage collector.

CONSTRUCTOR CALL CHAINS

MetaCallGraphImpl Constructor(CachingCodeFactory, ClassHierarchy, Set)

1. void analyze(HMethod)
   1. void analyze(MetaMethod)
      1. void analyze_meta_method()
         1. MethodData get_method_data(HMethod)
            1. Set extract_the_calls(HCode)
            2. Set extract_the_returns(HCode)
            3. Set get_initial_set(Set)
               1. MCGExactTemp getExactTemp(Temp, Quad, int)
            4. SCComponent compute_scc(Set, ReachingDefs)
               1. MCGExactTemp[] getDependencies(MCGExactTemp, ReachingDefs)
         2. void set_parameter_types(MetaMethod, HCode)
            1. MCGExactTemp getExactTemp(Temp, Quad)
               1. MCGExactTemp getExactTemp(Temp, Quad, int)
         3. void compute_types(SCComponent)
            1. void process_scc(SCComponent)
         4. void analyze_calls()
            1. void analyze_one_call(CALL)
               1. void rec(HMethod, CALL, int, int)
                  1. void specialize_the_call(HMethod, CALL)
                  2. void rec(HMethod, CALL, int, int)
                  3. MCGExactTemp getExactTemp(Temp, Quad, int)
               2. boolean check_thread_start_site(CALL)
                  1. boolean thread_start_site(HMethod)
                  2. MCGExactTemp getExactTemp(Temp, Quad, int, int)
                  3. Set get_instantiated_children(HClass)
                  4. boolean has_a_run(CALL, HClass)
               3. void specialize_the_call(HMethod, CALL)
                  1. void record_call(MetaMethod, CALL, MetaMethod)
               4. MCGExactTemp getExactTemp(Temp, Quad, int)
               5. void treat_poly_base(HMethod, CALL, GenType)
                  1. Set get_possible_classes(HClasses, HMethod)
                     1. Set get_instantiated_children(HClass)
                  2. void rec(HMethod, CALL, int, int)
               6. void treat_mono_base(HMethod, CALL, GenType)
                  1. void rec(HMethod, CALL, int, int)
               7. void display_mm_data(MetaMethod)
                  1. MethodData get_method_data(HMethod)
2. void compact()