System and method for optimizing template object files6041180Abstract The present invention provides a system and method to reuse code, and thus save code space within a program. A compiler and a linker work together to decide which object code to reuse, for implementation of template classes, and other repetitive code segments. The compiler notes in the object file which functions are generated from template code, or other repetitive types of code. An intelligent linker then attempts to match code, and in the cases where the code matches, simply eliminates multiple versions of the same code by aliasing the function names. The compiler can reduce the amount of linker searching by storing a cyclic redundancy check (CRC) code with each method. By using the system and method of the present invention, code reuse is made possible without sacrificing program efficiency. Claims What is claimed is: Description FIELD OF THE INVENTION
______________________________________
#ifndef .sub.-- STACK.sub.-- TPL.sub.-- H
#define .sub.-- STACK.sub.-- TPL.sub.-- H
template<class T>
class stack
{
private:
T* v;
T* p;
int sz;
public:
stack(int);
.sup.- stack( );
void push(T);
T pop( );
int getSize( );
};
#endif
______________________________________
Note that the identifier T represents the template type. The class implementation for the above stack is as follows:
______________________________________
template<class T>stack<T>::stack(int s)
v = p = new T[sz=s];
}
template<class T>stack<T>::.sup.- stack( )
{
delete [] v;
}
template<class T> void stack<T>::push(T a)
{
*p++ = a ;
}
template<class T> T stack<T>::pop ( )
{
return *(--p);
}
template<class T> int stack<T>::getSize( )
{
return sz;
}
______________________________________
Different declarations (i.e. template classes) of this class template are defined as follows:
______________________________________
#include "stk.h"
typedef char *pCHAR;
typedef unsigned short
*pUSHORT;
typedef int *pINT;
typedef unsigned int *pUINT;
stack<unsigned int> dummy0(10);
stack<int> dummy1(10);
stack<unsigned short>
dummy2(10);
stack<pCHAR> dummy3(10);
stack<PUSHORT> dummy4(10);
stack<pINT> dummy5(10);
stack<pUINT> dummy6(10);
______________________________________
The stack class for integers can be used as follows:
______________________________________
#include <iostream.h>
#include "stk.h"
int main(void)
stack<int> s(10);
cout << "Pushing the sequence of numbers: 2 4 1 3.backslash.n";
s.push(2);
s.push(4);
s.push(1);
s.push(3);
cout << "Popping the numbers:expecting 3 1 4 2.backslash.n";
cout << "Sequence from Pop operations: ";
cout << s.pop( ) << ' ' ;
cout << s.pop( ) << ' ' ;
cout << s.pop( ) << ' ' ;
cout << s.pop( ) << '.backslash.n';
return 0;
}
______________________________________
When code is compiled, C++ compilers typically repeat the code for each method (e.g. push, pop, etc.) even if it is independent of the type (i.e. int, char, etc.) used for the template. In some cases, the code does need to be different because of differences in the type used in the template class declaration. However, in many cases the code will be identical, or nearly identical. For example, the generated assembly code for the pop() method for each of the different types is shown below:
______________________________________
unsigned int:
pop.sub.-- stackXTUi.sub.-- Fv proc
mov ecx,eax
mov eax,[ecx+04h]
lea edx,[eax-04h]
mov [ecx+04h],edx
mov eax,[eax-04h]
ret
pop.sub.-- stackXTUi.sub.-- Fv endp
int:
pop.sub.-- stackXTi.sub.-- Fv proc
mov ecx,eax
mov eax,[ecx+04h]
lea edx,[eax-04h]
mov [ecx+04h],edx
mov eax,[eax-04h]
ret
pop.sub.-- stackXTi.sub.-- Fv endp
unsigned short:
pop.sub.-- stackXTUs.sub.-- Fv proc
mov edx,eax
push ebx
mov ecx,[edx+04h]
xor eax,eax
lea ebx,[ecx-02h]
mov [edx+04h],ebx
pop ebx
mov ax,[ecx-02h]
ret
pop.sub.-- stackXTUs.sub.-- Fv endp
char:
pop.sub.-- stackXTc.sub.-- Fv proc
mov edx,eax
push ebx
mov cx,[edx+04h]
xor eax,eax
lea bx,[ecx-01h]
mov [edx+04h],ebx
pop ebx
mov a1,[ecx-01h]
ret
pop.sub.-- stackXTc.sub.-- Fv endp
______________________________________
Note that the generated code for unsigned int and int is exactly the same. This is not unexpected as the size of the type is the same (i.e. 4 bytes each). The code for unsigned short and char is different, as expected, because an unsigned int is only two bytes in size and a char is only one byte in size. As shown below, the generated code for all the pointer types are the same, as is the code for unsigned int and int:
______________________________________
pointer to unsigned int:
pop.sub.-- stackXTPUi.sub.-- Fv proc
mov ecx,eax
mov eax,[ecx+04h]
lea edx,[eax-04h]
mov [ecx+04h],edx
mov eax,[eax-04h]
ret
pop.sub.-- stackXTPUi.sub.-- Fv endp
pointer to int:
pop.sub.-- stackXTPi.sub.-- Fv proc
mov ecx,eax
mov eax,[ecx+04h]
lea edx,[eax-04h]
mov [ecx+04h],edx
mov eax,[eax-04h]
ret
pop.sub.-- stackXTPi.sub.-- Fv endp
pointer to unsigned short:
pop.sub.-- stackXTPUs.sub.-- Fv proc
mov ecx,eax
mov eax,[ecx+04h]
lea edx,[eax-04h]
mov [ecx+04h],edx
mov eax,[eax-04h]
ret
pop.sub.-- stackXTPUs.sub.-- Fv endp
pointer to char:
pop.sub.-- stackXTPc.sub.-- Fv proc
mov ecx,eax
mov eax,[ecx+04h]
lea edx,[eax-04h]
1. mov [ecx+04h],edx
mov eax,[eax-04h]
ret
pop.sub.-- stackXTPc.sub.-- Fv endp
______________________________________
The generated code for the getSize() method is also the same regardless of which template class is declared. In addition, the generated code for the constructor and destructor methods are the same regardless of which template class is declared. Two principles arise from these examples: 1. The generated code is the same if the template type is not used in the method. 2. The generated code is usually the same if the size of the template types is the same. Based on the above principles, the present invention provides a system and method which can be used by compilers and linkers to reuse object code, where possible, for implementation of template classes. The compiler notes in the object file which functions are generated from template code. The intelligent linker then attempts to match code, and in the cases where the code matches, simply eliminates multiple versions of the same code by aliasing the function names. The compiler can reduce the amount of linker searching by storing a cyclic redundancy check (CRC) with each method. Testing with various test cases will show whether the CRC is sufficient, or if the linker needs to perform a more exact match. The actual implementation will of course be compiler specific, however, an example is illustrated below with reference to FIG. 2. The present invention is especially beneficial when optimizing class templates in which the methods perform data manipulation not directly tied to the template type. A common example is collection classes in which most methods are concerned with walking the collection, and only a few methods deal with adding, deleting or finding elements in the collection. In addition, implementations of class libraries may be modified to derive the most benefit from the described optimization. For example, parameters that are template types can be converted to pointers before calling a relatively large implementation function. This results in only the wrapper function being different for each template type. Referring now to FIG. 2, a method of compiling and linking code according to the present invention will be described. During the compile phase 102, a source file 104 is processed through a preprocessor 106, a syntax checker and parser 108, and a code generator 110. The preprocessor 106, syntax checker and parser 108, and code generator 110 produce a symbol table 112. The generated code is then optimized 114 and an object file 116 is produced. During the linking phase 118, one or more object files 116 are linked together by being processed through a preprocessor 120 and an executable generator 122. Symbol table 124 is used for resolving linkages (i.e. collecting global names and resolving them). In addition, symbol table 124 is also used to collect and store all comment records found. The comment records are used to identify template object code, and are described more fully below. Finally, an executable code module 126 is created. For the purposes of this example, assume the stack template implementation is in a file referred to as STK.CPP, and the following code snippet is from a source file 104, referred to as TEST.CPP:
______________________________________
#include <iostream.h>
#include "stk.h"
stack<int> i(10);
stack<unsigned short *> s(10);
i.push(1);
i.push(2);
unsigned short j = 1;
s.push (&j);
j = 2;
s.push (&j);
cout << i.getSize( ) << "elements in integer stack.backslash.n";
cout << s.getSize ( ) <<
"elements in unsigned short pointer stack.backslash.n";
______________________________________
When TEST.CPP is compiled, three object files 116 are produced, one for TEST.CPP and one for each of the different invocations of the stack template class. Assume that the template file objects for each of the two separate invocations are named STK1.OBJ and STK2.OBJ. During the compiler phase 102, the compiler adds a comment record to each object file for each template function. The exact point at which the compiler adds the comment records will of course be compiler-dependent. The comment record contains the template filename, line number, function name and CRC (or checksum) for the object code. For example, STK1.OBJ contains:
______________________________________
filename line number CRC function
______________________________________
STK1.OBJ 1 8D23 .sub.-- C.sub.-- stack.sub.-- Fv
STK1.OBJ 6 CAA1 .sub.-- D.sub.-- stack.sub.-- Fv
STK1.OBJ 10 3A1F push.sub.-- stack.sub.-- Fi
STK1.OBJ 15 4A2C pop.sub.-- stack.sub.-- XTi.sub.-- Fv
STK1.OBJ 20 1CAD getSize.sub.-- stackXTi.sub.-- Fv
______________________________________
and STK2.OBJ contains:
______________________________________
filename
line number CRC function
______________________________________
STK2.OBJ
1 8D23 .sub.-- C.sub.-- stack.sub.-- Fv
STK2.OBJ
6 CAA1 .sub.-- D.sub.-- stack.sub.-- Fv
STK2.OBJ
10 3A1F push.sub.-- stack.sub.-- FPUs
STK2.OBJ
15 4A2C pop.sub.-- stackXTPUs.sub.-- Fv
STK2.OBJ
20 1CAD getSize.sub.-- stackXTPUs.sub.-- Fv
______________________________________
During the preprocessor step 120 of the linker phase 118, the linker stores these comment records in symbol table 124. During the executable generation step 122 of the linker phase 118, the comment records in the object files are searched for common template code. The exact point in step 122 where this searching takes place will be linker-specific. The speed of this search is improved by using the CRC. If two CRC codes are equal, it is very likely that the bytes of code used to generate the CRC codes are also the same. Thus, if the linker finds matching CRC codes, it will then compare the actual instructions to determine if the underlying code is the same. If a match is found, the linker creates a duplicate set of entry points in the executable code that aliases the found function and adjusts the addresses to the new function name. In the described example, the mapping would now be:
______________________________________
filename
line number CRC function
______________________________________
STK1.OBJ
1 8D23 .sub.-- C.sub.-- stack.sub.-- Fv
STK1.OBJ
6 CAA1 .sub.-- D.sub.-- stack.sub.-- Fv
STK1.OBJ
10 3A1F push.sub.-- stack.sub.-- Fi
STK1.OBJ
15 4A2C pop.sub.-- stack.sub.-- XTi.sub.-- Fv
STK1.OBJ
20 1CAD GetSize.sub.-- stackXTi.sub.-- Fv
STK2.OBJ
1 8D23 .sub.-- C.sub.-- stack.sub.-- Fv
STK2.OBJ
6 CAA1 .sub.-- D.sub.-- stack.sub.-- Fv
STK2.OBJ
10 3A1F push.sub.-- stack.sub.-- FPUs
STK2.OBJ
15 4A2C pop.sub.-- stackXTPUs.sub.-- Fv
STK2.OBJ
20 1CAD getSize.sub.-- stackXTUs.sub.-- Fv
______________________________________
The duplicate comment records for STK2.OBJ are also invalidated, as object STK1.OBJ has been used for resolving all symbol names and references.
______________________________________
filename line number CRC function
______________________________________
STK2.OBJ -- -- --
STK2.OBJ -- -- --
STK2.OBJ -- -- --
STK2.OBJ -- -- --
STK2.OBJ -- -- --
______________________________________
In the example shown, 50% of the code has been eliminated, thus saving significant code space. For each of the stack functions (i.e. constructor, destructor, push, pop, and getSize), there is only one entry point in the executable code. For example, a call to push an integer onto the integer stack (i.e. i.push(1) and i.push(2) in the original source code) will call the same executable code as will a call to push a pointer to an unsigned short onto the pointer to unsigned short stack (i.e. s.push(&j) in the original source code). For every function where the sets of instructions are the same, only one set of instructions is present in the executable module. Although the invention has been described with a certain degree of particularity, it should be recognized that elements thereof may be altered by persons skilled in the art without departing from the spirit and scope of the invention. One of the embodiments of the invention can be implemented as sets of instructions resident in the random access memory 16 of one or more computer systems configured generally as described in FIG. 1. Until required by the computer system, the set of instructions may be stored in another computer readable memory, for example in a hard disk drive, or in a removable memory such as an optical disk for eventual use in a CD-ROM drive or a floppy disk for eventual use in a floppy disk drive. Further, the set of instructions can be stored in the memory of another computer and transmitted over a local area network or a wide area network, such as the Internet, when desired by the user. One skilled in the art would appreciate that the physical storage of the sets of instructions physically changes the medium upon which it is stored electrically, magnetically, or chemically so that the medium carries computer readable information. The invention is limited only by the following claims and their equivalents.
|
Same subclass Same class Consider this |
||||||||||