Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-09-30
2001-09-11
Chaki, Kakali (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C717S152000, C717S152000, C717S152000, C717S152000
Reexamination Certificate
active
06289507
ABSTRACT:
This application is based on an application No. 9-265655 filed in Japan, the content of which is hereby incorporated by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an optimization apparatus equipped in a compiler apparatus, and to a computer-readable storage medium storing an optimization program.
2. Description of the Background Art
In recent years, electronics engineers have found it very difficult to develop embedded microcomputer systems that realize high-level and complex control. In general, an embedded microcomputer system refers to a computer system in which a mask ROM that stores all control programs from the firmware to application programs is integrated with a microprocessor. Such embedded microcomputer systems have increasingly been used in household electrical appliances, machine tools, information apparatuses, and communication apparatuses.
Nowadays it is common to develop programs embedded in such microcomputer systems using high-level programming language, such as C, since in view of recent rapid increases in scale of embedded-type application software, it is no longer possible to realize the high-level processing required for these embedded programs in the old software development environment based on assembly language. Also, to develop the embedded programs that realize high-level processing using assembly language puts a considerable burden on engineers.
However, when compared with application software developed using assembly language, machine-language software developed using high-level language has a problem of high redundancy. Accordingly, manufacturers who intend to suppress the cost of their products are reluctant to use high-level programming language to develop embedded programs.
For embedded processors, programs have to be stored in ROM, so that increases in program size can greatly affect manufacturing cost. Also, when specific performance (execution speed) is required for products, more expensive microprocessors have to be used or microprocessors have to operate at higher clock speeds, due to an increase in the execution time of embedded programs.
Thus, there are the notable disadvantages in using high-level programming language to develop embedded programs. To allow greater use of high-level programming language when developing embedded software, it is necessary to establish a high-level optimization algorithm that can eliminate redundancy of the resulting software.
While there are many definitions of program redundancy, in the present specification program redundancy indicates all factors, that are present in a program written in high-level language or intermediate language, which cause increases in code size and execution time of a machine language program after compiling.
Before explaining conventional optimization apparatuses, the construction of conventional compiler apparatuses is explained below, with reference to the following publications.
(1) A. V. Aho, R. Sethi, J. D. Ullman (1986): Compilers:
Principles, Techniques, and Tools
, Addison-Wesley Publishing Company Inc. (translated in Japanese by Kenichi Harada (1990):
Compilers I, II
, Science company Inc.)
(2) Hans Zima (1991):
Supercompilers for Parallel and Vector Computers
, Addison-Wesley Publishing Company Inc. (translated in Japanese by Yoichi Muraoka (1995):
Supercompilers
, Oum Company Inc.)
(3) Masataka Sasa (1989):
Programming Language Processing System
, Iwanami
FIG. 1
shows the construction of a conventional compiler apparatus. In the figure, the compiler apparatus includes a syntax analysis apparatus
41
, an optimization apparatus
42
, and a code generation apparatus
49
.
The syntax analysis apparatus
41
performs lexical analysis, syntax analysis, and semantic analysis on a source program which is stored as a file in a storage device (not illustrated) and converts the source program to an intermediate program to simplify the processing by the compiler apparatus. Here, each step (construct) in the intermediate program is called an intermediate instruction. Types of intermediate instructions include a quadruple, a triple, and an abstract syntax tree (reference (1): p.464). Such intermediate instructions are further converted to object code by the code generation apparatus
49
. In this specification, the syntax analysis apparatus
41
is not explained in detail, since it is not especially related to optimization processing which is the main focus of the present invention.
The optimization apparatus
42
optimizes the intermediate program to reduce the program size and the execution time of the resulting machine language program. The optimization apparatus
42
includes an optimization control unit
43
, a control flow information analysis unit
44
, a data flow information analysis unit
45
, an intermediate code optimization unit
46
, a control flow information storage unit
47
, and a data flow information storage unit
48
.
The control flow information analysis unit
44
divides the intermediate program into basic blocks where the control flow is unidirectional, and obtains control flow information that shows the control flow between basic blocks (reference (1): p.528). The basic blocks are explained in detail later.
The data flow information analysis unit
45
analyzes the intermediate code using the control flow information and obtains data flow information showing reaching definitions, available expressions, and live variables (for more details, see reference (1): pp.608-722). This data flow information is obtained by finding information that is to be used as data flow information, setting data flow equations for the entry and exit points of the basic blocks, and calculating the data flow equations according to an iterative algorithm.
The intermediate code optimization unit
46
uses the control flow information and the data flow information to optimize the intermediate code. Examples of such optimization processing are deletion of basic blocks that are beyond control using the control flow information, optimization of common subexpressions using the information on available expressions (reference (1): p.592), copy propagation using the information on reaching definitions (reference (1): p.594), and deletion of unnecessary code using the information on live variables (reference (3): p.482). The optimization processing is explained in greater detail later.
The control flow information storage unit
47
stores the control flow information generated by the control flow information analysis unit
44
.
The data flow information storage unit
48
stores the data flow information generated by the data flow information analysis unit
45
.
The code generation apparatus
49
allocates registers or memory to variables written in the intermediate program and converts each intermediate instruction to a machine language instruction. This code generation apparatus
49
is not the main focus of the present invention and so is not explained in detail here.
The following is a more detailed explanation of the optimization apparatus
42
, focusing on features related to the present invention, namely, the copy propagation using the information on reaching definitions and the optimization of common subexpressions using the information on available expressions.
First, the terms used in the explanation are introduced.
<Program Point>
Any point located between two adjacent intermediate instructions (reference (3):p.461).
<Basic Block> (reference (1): p.528)
When optimizing the program, there is a danger that the algorithm will be destroyed by rewriting instructions which include jump instructions or jump destinations. Accordingly, in the optimization processing, the execution order has to be unidirectional from the start to the end. Hence, in the intermediate program, each part (block) that includes neither a jump nor a jump destination is called a basic block, which is the minimum unit of the optimization processing. A point immediately before a first intermediate instruction in a basic block is called the entry poi
Odani Kensuke
Sayama Junko
Tanaka Akira
Tanaka Hirohisa
Chaki Kakali
Matsushita Electric - Industrial Co., Ltd.
Price and Gess
Vo Ted T.
LandOfFree
Optimization apparatus and computer-readable storage medium... 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 apparatus and computer-readable storage medium..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization apparatus and computer-readable storage medium... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2485781