Dibyendu Das is a member of the C/C++ compiler back-end team at Hewlett-Packard for PA-RISC. He can be contacted at dibyend@ india.hp.com.
Function devirtualization is a well-known compiler optimization technique for C++ code. This optimization replaces a call to a virtual method by a call to a particular method of a class, thus eliminating the overheads of accessing a virtual method via virtual table(s). In addition, the direct call may be inlined, leading to higher performance. Class Hierarchy Analysis (CHA) is one of the well-known techniques that are applied to find out whether a virtual call is devirtualizable. CHA is based on constructing the Class Hierarchy Graph (CHG) that encapsulates the base-class-derived class relationship among the classes that use virtual methods.
In this article, I present a new method of constructing the CHG that uses information generated by the C++ compiler for Run-Time Type Identification (RTTI). There are several advantages of this method over existing ones. For one thing, the C++ compiler front end need not emit any additional information for constructing the CHG in the optimizer. (Note that virtual methods in a class in one file may be overridden by a derived class in another file.) Information generated for RTTI is reused for this purpose. Because RTTI support is mandated by most C++ compilers, this method provides a universal mechanism for constructing the CHG. Also, the mechanism can be adopted by postlink-time optimizers or tools that inspect object code, enabling such tools or optimizers to carry out devirtualization at a very late phase.
What Is Function Call Devirtualization?
In Listing 1, the call to get_val() in foo() actually calls the function get_val() of class A. Normally, such virtual function calls are executed by using the virtual table pointers. These not only add overhead to the calling mechanism, but also block any form of inlining possible at the call point. The call to get_val() can be replaced by a direct call to get_val() of class A in the following manner:
return bp->A::get_val();
Automatic devirtualization in a compiler at static time requires knowledge of class hierarchy (knowing which subclasses have virtual functions that override those declared in their superclasses/base classes). For example, the call to get_val() can be rerouted to a call to A::get_val() by noting that class B does not override the virtual method named get_val() defined in class A (its base class). This analysis is termed the "Class Hierarchy Analysis" (CHA).
Building the Class Hierarchy Graph
The building block of CHA is the Class Hierarchy Graph (CHG). The CHG contains nodes, each of which represents a class; and edges, each of which represents a superclass-subclass relationship. For instance, if an edge points from node x to node y, then x is the superclass and y is the subclass. In addition, each node has a list of virtual functions defined in the class. Figure 1 is the CHG for Listing 1. Both A and B access the same get_val function—A::get_val. As defined in class A, get_val() is not overridden in class B.
Building the CHG is straightforward when all the class definitions are visible (in a single file, for instance). The situation is more complicated when the derived classes and the base classes are in different files, and the CHG needs to be constructed. In such cases, the compiler usually depends on a feature whereby all the compilation units are visible (for example, under the option -ipo for Intel and HP compilers or +O4 or +Owhole_program_mode for a host of others). Listing 2 illustrates this point. Class A is defined in file f1.H, while the derived class B is in f2.C. In addition, f1.C defines a function DoSomething() that takes a parameter that is a pointer to an object of type A.
Class B in file f2.C overrides the function get_val() defined in class A of f1.C. Hence, the CHG of Figure 1 would change to that in Figure 2. It would now be impossible (statically) to infer from the CHG that the call to pa->get_val() in DoSomething() can be replaced by pa->A::get_val(). Why? Because a call to DoSomething() in some file can pass either objects of type A or of type B to the function as actual parameters. If an object of type B is passed, replacing the virtual call by a call to A::get_val() results in incorrect code. Such virtual method invocations can still be devirtualized by a technique known as "dynamic devirtualization," but that is beyond the scope of this discussion.
Reusing RTTI Information
In general, a C++ front end does not generate any specific information to encode the class hierarchy. However, most C++ compilers support RTTI. To aid RTTI, a C++ front end generates the type structure of the classes that make use of virtual function calls. This information is encoded in the intermediate code generated by the C++ compiler. When the optimizer examines the intermediate code, it deciphers and constructs the CHG from the type structure emitted to aid RTTI.
Vtable pointers are the first fields of objects that use virtual functions. They point to static vtable structures created for each class (there may be multiple vtable static structures for multiple/virtual inheritance). For class A of the example, there is a static structure named, say, <Vtable_A> that is created. One of its fields is a pointer that points to the typeid structure. One of the fields of the vtable also points to the virtual function get_val().
By checking the vtable static variables (of the kind <Vtable_A>) that are created, the names of the classes and the virtual functions that are accessible from the virtual table can be inferred. Hence, the nodes as defined in Figure 1 and the lists of virtual functions that are accessible can be constructed. But the edges between the nodes cannot be inserted by inspecting the vtable static variables. This is because the superclass-subclass information is absent in the vtable directly. For this purpose, the typeid structures that are created for each class (and which the respective vtables point to) need to be inspected.
The typeid structure encapsulates the type information of the class and is used for C++ calls such as dynamic_cast, typeid, and the like. This can be exploited to extract the superclass-subclass hierarchy. The interesting part of the typeid structure is a field that points to the base-class table. The base-class table is an array of pointers pointing to the typeid structures of the superclasses (base classes) of the class in question. Figure 3 illustrates the vtable, typeid, and base-class structure for Listing 1.
From Figure 3, it is apparent that vtables (via typeid and BaseClassTables) encode the class hierarchy information. The base-class table of class B points to the typeid structure of class A, implying that A is the base class/superclass of B. The base-class table of A is empty, as it does not derive itself from any other class. The edge between node A and node B (in Figure 1) can now be constructed based on this information.
The algorithm (see Example 1) becomes slightly more complicated in the presence of multiple/virtual inheritance, as multiple vtables are created for the same class. For these cases, the algorithm needs to be modified to merge all the nodes created for the same class to a single node and maintain the edge relationships accordingly. Figure 4 illustrates the multiple-inheritance example in Listing 3.
There are two virtual tables—<Vtable_C_1> and <Vtable_C_2>—created for class C. Also, the typeid structure (<typeid_C>) is shared by both these vtables. This implies that if a node is created for each vtable following the BuildCHG() algorithm, then the CHG is represented as in Figure 5.
The representation in Figure 5 is wasteful because <Vtable_C_1> and <Vtable_C_2> carry similar information. Therefore, it is advisable to merge these nodes to create a single node for class C.
When RTTI Is Disabled
Some compilers (such as g++) support options (-fno-rtti, for instance) to disable RTTI information for code that is known not to use RTTI functionality. In such cases, compilers can still generate the RTTI information for the optimizer. However, the concluding passes of the optimizer can throw away the RTTI information after devirtualization has been put into effect. The final executable will not contain the RTTI information as expected from a -fno-rtti.
Conclusion
I've shown here how the CHG can be built from the information generated to aid RTTI by a C++ front end. The method presented can also be tailored to extract the CHG from the executable/object files easily without depending on any additional information. Also, the method is generic enough to be adopted by other compilers.
References
- Bacon, D.F. and P.F. Sweeney. "Fast Static Analysis of C++ Virtual Function Calls," OOPSLA 1996.
- Aigner, G. and U. Holzle. "Eliminating Virtual Function Calls in C++ Programs," ECOOP 1996.
- Dean, J., D. Grove, and C. Chambers. "Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis," Tech Report, Dept. of CSE, University of Washington, 1994.
- Porat, S., D. Bernstein, Y. Fedorov, J. Rodrigue, and E. Yahav. "Compiler Optimization of C++ Virtual Function Calls," Usenix 1996.
- Bacon, D.F. "Fast and Effective Optimization of Statically Typed Object-Oriented Languages," Ph.D. Thesis, UC Berkeley, 1997.
