Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1997-10-07
2001-06-26
Trammell, James P. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000
Reexamination Certificate
active
06253373
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This application relates in general to computer system compilers and in specific to tracking loops, and loop entry points and exit points in the compiler.
BACKGROUND OF THE INVENTION
Compilers convert a source program that is usually written in a high level language into low level object code, which typically comprises a sequence of machine instructions or assembly language. The constructs in the source program are also converted into a sequence of assembly language instructions in the executable program. To achieve the highest possible efficiency of operation, it is essential to understand exactly how the program executes. This would allow the program developer to concentrate on improving the parts of the program that are inefficient. Consequently information such as the length of time that the program takes to execute, and other statistics about the program execution, at the function level, at the loop level, and at the basic block level must be determined.
The compilers track loops so that the profilers can instrument these loops and collect information about the loops. In order for the compilers to track the loops, they need to perform some analysis on these loops. This analysis determines the location of the loop entry points and the loop exit points. Instrumentation code is then placed at the loop entry and the exit points identified by the analysis phase by the profiler. The instrumentation code allows the collection of information about the loops. An important requirement of instrumentation code is that it must not affect the code that is normally generated by the compiler. Thus, the instrumentation code must be placed after all of the optimizations have been completed. This process is complicated since loops can be nested inside of each other, and exit points can take the control flow out of a loop nest. Moreover, optimization phases may have taken place between the loop analysis and code generation phases that invalidates the information collected during the loop analysis phase. It may not be possible to update this information as loop control structures may have changed or disappeared after the analysis phase due to optimizations.
One prior art solution to this problem is to repeat the loop analysis several times throughout the compilation process. Since this loop analysis phase is carried out in a number of different places, the loops that are detected in each phase will be different from the previous phase because of the optimizations that happen between these phases. It becomes very difficult for the compiler to correlate the loops that are manifesting in the object code with the loops that are present in the source code. This will cause problems in trying to associate the information that is collected about the loops in the object code with the loops that are present in the source code.
One solution that the compilers use is to keep track of all the loop data structures for the whole compilation process. Whenever any optimization happens, the loop data structures are updated to reflect the loops that are present in the object code. This uses a great deal of memory, because the loop data structures must be maintained in memory for the whole compilation process. But for the need to track the loops, these loop data structures could have been eliminated once the loop optimizations have been performed in the compilers. Also, the compilation time increases because whenever an optimization takes places (even when it is not a loop optimization), a check must be performed to determine whether the loop data structures need to be updated, and then perform the updating if the need exists.
The other technique that prior art compilers use to overcome this problem is to perform the loop analysis and loop optimizations right before the code generation, so that any of the loops that have manifested in the object code can be correlated back to the source code. This is not the ideal place for the loop analysis and the loop optimizations to be performed, because it may not produce optimal code. The different phases of the compilation process have to be driven by the observations that the compiler developers make by examining the collected information on the source program that is being compiled. Because the different phases of the compilation process is limited by the information collection process, this lack of information has the effect of producing sub-optimal code for the program since all possible optimizations may not have been performed.
Another problem of the prior art compilers is their placement of the instrumentation code in loop entry and exits points. Some prior art compilers place the instrumentation code after the loop analysis phase, which guarantees accurate placement since the locations of the entry and exits points have not been changed. However, then the compilers perform optimization phases, and the subsequent optimization phases can optimize away the instrumentation code. Thus, this would render subsequent analysis of the code by the developers useless. Moreover, the resulting optimized code produced by the compiler in the presence of this instrumentation may be different than code produced if the instrumentation is not present.
Compilers comprise a number of different phases, and each of these phases transform the program to produce fast executing code through optimizations, and in the process the correlation between the source code loops and object code loops is lost. Thus, there is a need in the art to keep track of the information, so that the correlation is possible between the loops in the object code and the loops in the source code. This is important because the developer will only see the loops that are present in the source code, but only collect information about the loops that are in the object code. Thus, in order for the developer to adjust the source code for optimal performance by observing the behavior of the loops in the object code, the developer needs to be able to correlate the loops in the source code with the loops in the object code. As long as there are problems associated with the instrumentation code generation phase and the loop analysis phase, this will not be possible.
Therefore, there is a need in the art to separate the instrumentation code generation from the loop analysis phases in the compiler, so that each can be performed at their respective appropriate points in the complication process, depending on the requirements that would construct the most optimal code.
SUMMARY OF THE INVENTION
These and other objects, features and technical advantages are achieved by a system and method which separates the tracking of the loop entry and exit points and other loop information, from the production of the instrumentation code at the loop entry and exit points. In other words, the instrumentation code generation is separated from the loop analysis, and consequently, they need not be performed in the same phase in the compiler.
This invention allows the different phases in the compiler to proceed in an optimal manner with respect to producing the best optimized code, as opposed to trying to collect the information in an artificial manner imposed by the requirements of the compiler. The loop analysis phase and the optimization phase can occur anywhere in the compilation process, based solely on achieving optimal code, instead of correctly generating instrumentation code for the profiler.
This invention allows the correlation of the source code loops to the object code loops, even though different optimizations are being applied to loops. For example, if during an optimization process a loop is broken up into two different loops, enough information is maintained in the compiler to allow the developer to know that the two loops that are in the object code are from a single loop in the source code. Thus the developer, in viewing the timing information about the object code, knows that a change to the single source code loop will affect the performance of the two object code loops.
This invention does not de
Booker Kelvin
Hewlett--Packard Company
Trammell James P.
LandOfFree
Tracking loop entry and exit points in a compiler does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Tracking loop entry and exit points in a compiler, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tracking loop entry and exit points in a compiler will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2505434