Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2000-09-18
2004-04-13
Ingberg, Todd (Department: 2124)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06721945
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the programing languages that use pointers for passing reference parameters, and particularly the calling conventions of that language.
In this specification a reference to the “C programing language” or simply “C” is to be understood as a general reference to all C programing language versions, including ANSI C, C+ and C++. C is one such programing language that uses pointers for passing reference parameters.
It is further to be appreciated that the invention can be embodied at any desired programing level including source code, an intermediate language level, object code, or assembly-level code.
BACKGROUND OF THE INVENTION
A problem common to many high-level programing languages is the constraints placed upon programing semantics, which can hinder the generation of optimum source code. This is true of the calling conventions of the C programing language. A fundamental reference to the C programing language is the text “The C Programing Language”, by Brian W. Kernighan and Dennis M. Ritchie, published by Prentice-Hall, second edition, 1998 (ISBN 0-13-110362-8). In C, there is a requirement that if any procedure makes changes to a formal parameter it should be passed as a reference parameter for this change to be visible outside the procedure.
This requires that the procedure takes-in pointer values as parameters, and at the call-site, the actual argument is the address-taken value of the variable that is needed to be modified. This introduces several unnecessary memory load and store operations.
FIG. 1
is a schematic block diagram of the generalised compilation process. In the first module
10
, an input source code program undergoes lexical analysis, such that the program is broken up into a stream of lexical tokens that are recognised by the programing language. The passing module
12
then takes these tokens and performs a syntax analysis of the program, catches any syntax errors, and translates the program to an intermediate language. The semantic analysis module
14
principally performs a type-checking analysis. In the next module
16
, various compiler optimizations are performed. The subsequent processing modules
18
-
22
perform register allocation and code generation (i.e. translation to assembly-level language), and production of the object code.
FIG. 2
is a schematic flow diagram demonstrating how parameters are passed in such conventional compilers. The call site is that passing the reference parameter, while the procedure body is that element using or defining the reference parameter. At the call-site, in step
30
, the actual argument value is placed into memory. In step
32
, the address of this location is placed in the parameter register. On the procedure body side, the memory address value for the argument value is fetched from the parameter register, in block
34
. Finally, in step
36
, the argument value is read from/assigned to the memory location.
Consider now the specific example of swapping two variables, A and B, represented by the following source code:
void swap(int* x, int* y)
{
int temp = *x;
*x = *y;
*y = temp;
}
The call-site that wants to swap the two variables A and B would call the foregoing procedure as:
swap(&a, &b);
A sample of the assembly-level code generated by the procedure is follows:
1
r
0
,
0
(r
4
)
1
r
5
,
0
(r
3
)
st r
0
,
0
(r
3
)
st r
5
,
0
(r
4
)
. . .
Here, the registers r
3
and r
4
store the addresses of the locations containing the values to be swapped. These memory locations are dereferenced, and the values stored in registers r
5
and r
0
respectively, then these values are written back into the swapped locations. The sequence of the code at the call-site contains instructions for storing the values of a and b to memory and storing the values of the corresponding memory locations into registers r
3
and r
4
. Since the addresses of these variables have been taken, they should be located in proper memory locations. However in this particular case, the call-site takes the address of these variables, not because this address-value is to be used, but because this is the only mechanism to allow the procedure swap to interchange two values and have them visible outside the procedure.
If the registers r
3
and r
4
are permitted to hold the actual values to be swapped, dereference of the address contained in these registers would not be required; moreover, storing of the values of the variables a and b into memory locations and then storing those locations into registers would not be required. Rather, it would simply be a matter of loading the values a and b into registers r
3
and r
4
, calling the function swap, and picking up the swapped values from registers r
4
and r
3
respectively.
The present invention is directed to achieving this result.
SUMMARY OF THE INVENTION
The gist of the invention is the replacement of reference parameters by scalar variables that are visible to the calling procedure, such as being global in scope.
The invention discloses a method for executing procedure calls, the method comprising the steps of:
replacing reference parameters for a calling procedure by variables visible to the calling procedure; and
directly accessing the argument value by the calling procedure body.
The invention further discloses a method for executing procedure calls, the method comprising the steps of:
identifying reference parameters for a calling procedure;
replacing said reference parameters with respective scalar variables;
propagating said scalar variables at a call site; and
directly accessing the scalar variables by the calling procedure body.
In a preferred form, the step of identifying reference parameters includes those parameters which are dereferences in a procedure body until the first calling definition. The propagating step can include backwards copying said scalar variables. The propagating step can further include forwards copying said scalar values. It is particularly preferred that the procedure calls relate to the C programing language.
The invention yet further discloses a method for optimizing a compiler for the C programing language, comprising the steps of:
translating a C language code body to an intermediate language code body;
for procedure calls, replacing reference parameters thereof by variables visible to a call procedure; and
translating said intermediate language code body, with said replacement variables, to an assembly language code body.
The invention yet further discloses a computer program product having a computer readable medium with a computer product recorded thereon for executing procedure calls. The computer program includes respective computer program code means for performing the steps defined above.
The replacing step can include identifying reference parameters for a calling procedure, replacing said reference parameters with respective scalar variables, and propagating said scalar variables at a call site. Not all reference parameters are replaced with respective scalar variables; non-replace parameters being propagated at a call-site.
REFERENCES:
patent: 5220669 (1993-06-01), Baum et al.
patent: 5522072 (1996-05-01), De Bruler
patent: 5530870 (1996-06-01), De Bruler
patent: 6141697 (2000-10-01), Hale et al.
patent: 6446137 (2002-09-01), Vasudevan et al.
patent: 6481007 (2002-11-01), Iyer et al.
patent: 6546433 (2003-04-01), Matheson
“Putting Pointer Analysis to Work”, R. Ghiya et al, ACM, published 1998, pp. 121-133.*
“Using Registers to Optimize Cross-Domain Call Performance”, Paul A. Karger, ACM published 1989, pp. 194-204.*
“Eliminating Redundancies in Sum-of-Product Array Computations”, S. Deitz et al, ACM, 2001, pp. 65-77.*
“An Improved Storage Management Scheme for Block Structure Language”, T.P. Murtaugh, ACM, 1991, pp. 372-398.*
Minimizing Register Usage Penalty at Procedure Calls, Fred C. Chow, ACM, 1988, pp. 85-94.*
“Advanced Compiler Design & Implementation”, Steven S. Muchnick, published 1997, pp. 116-126,325-333.*
“Replacing Function Parameters By
Coca T. Rao
England Anthony V. S.
Ingberg Todd
Schecter Manny W.
LandOfFree
Optimization of calls in programming languages using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimization of calls in programming languages using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization of calls in programming languages using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3221345