Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-07-15
2001-06-05
Chaki, Kakali (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C717S152000
Reexamination Certificate
active
06243864
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an optimization apparatus for optimizing instruction sequences that have been converted into machine language or assembler language, and to a compiler for converting a source program in high-level language into an instruction sequence written in machine language or assembler language.
2. Description of the Prior Art
Optimization at an intermediate code level is performed after writing a source program and converting this into intermediate code. By performing optimization, the code size and/or execution time of the final program can be suitably improved. However, regardless of whether the program generated after optimization is composed of assembler instruction sequences (hereinafter simply called an “assembler program”) or machine language sequences (hereinafter simply called a “machine language program”), such programs often include redundant code or instruction sequences that cause execution delays.
When improvements to code size and/or execution time are strongly desired, optimization processes such as instruction scheduling, the deletion of redundant instructions, and copy propagation are performed on the assembler code or machine code generated by a compiler.
Optimization at assembler language level or machine language level is achieved by instruction scheduling or by deleting redundant transfer instructions using equivalence groups. Note that the following explanation focuses on the case where optimization is performed at assembler language level.
Instruction Scheduling
The following is a description of instruction scheduling as a first conventional example of optimization at assembler language level.
In recent years, pipeline architecture has been increasingly used in microprocessors to speed up processing. To achieve the full potential of pipeline architecture, the pipeline needs to be continuously filled with instructions.
Depending on the structure of the pipeline, different instruction sequences can produce gaps in the pipeline. As one example, for a 5-stage pipeline single scalar machine whose a pipeline is composed of an IF (instruction fetch), a DEC (instruction decode), EX (execute), MEM (memory operation), and WB (register write) stages, it is not possible for an instruction to refer to a value that has just been loaded from the memory (hereinafter referred to as “load-refer sequence”). When instructions are arranged in this order, a gap will appear in the pipeline, causing a delay. To avoid the generation of such delays, instruction scheduling needs to be performed for this machine to separate the load-refer sequence. In a compiler whose target is a pipeline-architecture machine, an optimization process called instruction scheduling is performed to separate the load-refer sequence and so allow the pipeline architecture to be used to its full potential.
Instruction scheduling is a process of reediting the arrangement of instructions to suit a pipeline architecture. The arrangement of instructions especially refers to the relations between a given instruction and its preceding and succeeding instructions, so that reediting involves the interchanging of certain pairs of instructions within a program.
Scheduling may be performed in two different ways, first by considering the pipeline structure of the target machine to avoid pipeline hazards, and secondly by efficiently supplying instructions to a parallel conversion unit. Since the degree to which the pipeline can be filled depends on the order in which instructions are supplied, the full potential of the pipeline may be realized by rearranging the order of the instructions.
It should be noted here that the interchanging of instructions needs to be performed very carefully. Should instructions be simply interchanged without regard for the consequences, there is a real risk of a breakdown in the algorithm of the program. To avoid this, instructions in the program need to be classified into those which cannot be interchanged (hereinafter “inviolable”) and those which can.
Inviolable instructions are a pair of instructions that cannot be interchanged. To establish which pairs of instructions are inviolable, instructions that cannot be interchanged are detected and directed links are established between them.
Definition-Reference links, reference-definition links, and definition-definition links are patterns of the directed links that are conventionally formed between inviolable instructions. These are described in more detail below.
Definition-reference Links
Definition-reference links are directed links which show that the order of an instruction defining a resource and a later instruction referring to the resource is inviolable. One example is the following pair of instructions.
(1) mov 100,D0
(2) add D0,D1
In the above instruction sequence, the data flow is dependent on the register D0. As a result, the interchanging of instructions will result in the breakdown of the data flow. Accordingly, when instruction scheduling is performed, directed links clearly show the inviolable relation between the instruction that defines the resource and the instruction that refers to it.
Reference-definition Links
Reference-definition links are directed links that show the inviolability of the relation between an instruction that refers to a resource and an instruction that redefines the resource. The following is an example instruction sequence that will be used to explain why reference-definition links also need to be examined when rearranging the instructions.
(1) mov 100,D0
(2) add D0,D1
(3) mov 200,D0
(4) add D0,D1
In the above instruction sequence, the data flow in instructions (1)-(2) is dependent on the register D0. The data flow in instructions (3)-(4) is similarly dependent on the register D0. Suppose here that the instruction sequence is rearranged into the order (1)-(3)-(2)-(4). In this order, the definition-reference order is maintained as described above, although if the machine language program is executed in this state, 200 will be added to the value in the register D1, changing the meaning of the machine language program. Accordingly, the dependence on the register D0 in instructions (2)-(3) is preserved as a reference-definition link, so that a clear indication of the inviolability of these instructions is given.
Definition-definition Links
Definition-definition links are directed links that show the inviolability of the order of an instruction that defines a given resource and another instruction that redefines the resource. The following is an example instruction sequence that will be used to explain why definition-definition links also need to be examined when rearranging the instructions.
(1) mov 100,D0
(2) mov 200,D0
(3) add D0,D2
In the above instruction sequence, the data flow in instructions (2)-(3) is dependent on the register D0. As a result, a definition-reference link is set between instructions (2) and (3). In this example, instruction (1) is also a definition of register D0. Supposing here that the instruction sequence is rearranged to become (2)-(1)-(3), the execution of the rearranged instruction sequence will result in 100 being added to register D2, which changes the meaning of the machine language program. To avoid such erroneous rearranging of the program, the dependence on the register D0 in instructions (1)-(2) is preserved as a definition-definition link in the dependence graph.
The following is an explanation of conventional instruction scheduling by way of an example program. The construction of a conventional compiler is shown in FIG.
5
. The following example deals with the case when processing the program shown in FIG.
1
A. The program is first inputted into the analyzing unit
81
, is analyzed, and is then converted into intermediate code. The intermediate code at this stage is shown in FIG.
1
B. Next, the resource assigning unit
82
assigns the variables in the intermediate code to registers or memory. In this example, the variable i is assigned to the register D0, while the variable k is ass
Odani Kensuke
Tanaka Akira
Tanaka Hirohisa
Chaki Kakali
Das Chameli C.
Matsushita Electric - Industrial Co., Ltd.
LandOfFree
Compiler for optimizing memory instruction sequences by... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compiler for optimizing memory instruction sequences by..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compiler for optimizing memory instruction sequences by... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2523070