Compiling apparatus and method for promoting an optimization effect of a program

Abstract

A compiling apparatus and method in which instructions are scheduled for an efficient parallel process with a register allotting process and an instruction scheduling process performed independently of each other. An instruction scheduling unit collects information indicating the range of available registers, and renames registers by replacing the register numbers used by the instructions with other register numbers according to the collected register information and the analysis of definition/reference instruction dependency. The instructions are scheduled after the registers have been renamed.

Claims

What is claimed is:

1. A compiling apparatus for scheduling instructions by rearranging the instructions after allotting registers to object data for each of the instructions in a program, comprising:

register information collecting means for collecting availability register information of the registers after once allotting the availability register information in a scheduling range in which the instructions are rearranged;

instruction dependency analyzing means for analyzing dependency relating to definition of and reference to the registers among the object data for the instructions in the program;

register renaming means for replacing at least one of the registers after once being allotted to the object data in the instructions based on intermediate text with at least one of the other registers according to an output of said register information collecting means and an output of said instruction dependency analyzing means; and

an instruction schedule process unit for scheduling said instructions based on the at least one of the other registers generated by said register renaming means.

2. The compiling apparatus according to claim 1, further comprising:

register information storage means for storing the register information collected by said register information collecting means;

wherein said register information storage means stores, for each of a plurality of scheduling ranges in the program, information about a register not required in the scheduling range, a register used in the scheduling range, a register entered as an alive register in the scheduling range, and a register exiting as the alive register from the scheduling range.

3. The compiling apparatus according to claim 1, further comprising:

register information storage means for storing the register information generated by said register renaming means; and

debug information output means for outputting the register information which is collected by said register information collecting means and stored in said register information storage means, in the form of characters as debug information.

4. The compiling apparatus according to claim 1, wherein:

said register renaming means renames the registers for improving parallelism of processes by replacing the registers allotted to the object data with other registers; and

said register renaming means renames the registers for reducing a number of the registers by using, in a single instruction; a source register which stores reference data also as a destination register which stores data obtained as a result of execution of the instruction.

5. The compiling apparatus according to claim 4, wherein said register renaming means sequentially retrieves the instructions in the scheduling range one by one in an execution order, determines whether the source register can also be used as the destination register in a retrieved instruction, and if the source register can also be used as the destination register in the retrieved instruction, assigns a same number as the destination register to the source register, and if the source register cannot also be used as the destination register in the retrieved function, sequentially determines whether a register renaming process which improves the parallelism of the processes is valid, and if the register renaming process is valid, replaces the register allotted to the object data with the other register.

6. The compiling apparatus according to claim 5, wherein said register renaming means determines whether the register renaming process is valid for a first retrieved instruction, and retrieves a next instruction in the execution order without renaming the registers for the first retrieved instruction if the register renaming process is invalid.

7. The compiling apparatus according to claim 5, wherein said register renaming means determines that the source register can also be used as the destination register based upon a first condition, a second condition, and a third condition existing, said first condition requiring that contents of the destination register defined in the instruction to be determined are referred to at least once in subsequent instructions within the scheduling range to which the instruction belongs, said second condition requiring that contents of the source register in the instruction to be determined are not referred to in the subsequent instructions, and said third condition requiring that contents of the destination register in the instruction to be determined are not referred to in any program after the scheduling range to which the instruction belongs.

8. The compiling apparatus according to claim 5, wherein said register renaming means stores a last reference position of the register in the instruction replaced in the register renaming process, and allows the register to be reused as an available register candidate if the instruction to be processed in the register renaming process after the instruction in which the register was replaced appears after the last reference position.

9. The compiling apparatus according to claim 4, wherein said register renaming means determines whether the source register is also usable as the destination register in each of entire instructions in one scheduling range, performs the register renaming process according to a determination result such that the source register is also usable as the destination register, and then performs the register renaming process in which the registers allotted to the object data are replaced with other registers for the entire instructions in the scheduling range.

10. The compiling apparatus according to claim 9, wherein said register renaming means determines that the source register can also be used as the destination register based upon a first condition, a second condition, and a third condition existing, said first condition requiring that contents of the destination register defined in the instruction to be determined are referred to at least once in subsequent instructions within the scheduling range to which the instruction belongs, said second condition requiring that contents of the source register in the instruction to be determined are not referred to in the subsequent instructions, said third condition requiring that contents of the destination register in the instruction to be determined are not referred to in any program after the scheduling range to which the instruction belongs.

11. The compiling apparatus according to claim 9, further comprising:

architecture information storage means for storing architecture information of a computer in which the program to be compiled operates;

wherein said register renaming means alters register renaming priority levels among a plurality of instructions for transferring one of the registers to one of the other registers based upon the intermediate text depending on the architecture information of the computer.

12. A compiling apparatus which schedules instructions after allotting registers to generate codes for an efficient parallel process of the instructions, said apparatus having a front-end unit for receiving and analyzing a source program, an optimization unit for optimizing an analysis result, a register allotting unit for allotting the registers to data to be processed as the analysis result, an instruction scheduling unit for rearranging the instructions, and a code output unit for outputting an object program, the instruction scheduling unit comprising:

a register information collecting unit for collecting register information indicating a range of available registers;

instruction dependency analyzing means for analyzing dependency of the instructions in definition and reference;

register renaming means for renaming the registers by replacing register numbers used for the instructions with other register numbers according to the collected register information and the instruction dependency analysis result; and

instruction schedule process means for rearranging the instructions according to the renaming of the registers.

13. A compiling method for scheduling instructions by rearranging the instructions after allotting registers to object data for each of the instructions in a program, comprising the steps of:

collecting availability information of the registers in a scheduling range in which the instructions are rearranged;

analyzing dependency relating to definition of and reference to the registers among the instructions in the program;

replacing at least one of the registers allotted to the object data in the instructions with at least one of the other registers according to an output of said register information collecting step and an output of said instruction dependency analyzing step; and

scheduling said instructions based on a result generated by said register renaming step.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a compiling apparatus and method for promoting an optimization effect of a program operated by computers such as super scalar and VLIW architecture.

With an increasing demand for high-speed computer systems, a number of processors for simultaneously executing a plurality of instructions in a single cycle and machines which can perform vector operations have been developed. Requested also is optimum instruction scheduling for a compiler.

The instruction scheduling is one of the optimization methods. By rearranging the instructions, a pipeline process which can save time or resources (registers, operators, etc.) can be effectively utilized. It is a very effective method for a compiler having the function of performing parallel processes.

2. Description of the Prior Art

A compiler, which compiles a source program written in a high-level language into an object program or an assembler program composed of instruction strings written in machine language, first analyzes a sentence and meanings in its front-end unit, optimizes the program by deleting redundant instructions in its optimizing unit, allocates registers based on the analysis and optimization results, and outputs codes of instructions written in machine language. Particularly, a compiler of a processor having the function of performing a parallel processing is designed to schedule instructions for efficient parallel processing by rearranging the instructions before outputting the codes.

Instruction scheduling and register allotting are important factors of optimization. There are the following problems in determining the execution order between instruction scheduling and register allotting.

1. If instructions are scheduled before registers are allotted, the range of variable/temporary registers is enlarged and available registers are short. Thus, a spill instruction or register transfer instruction may be generated. Since a spill instruction requires a longer execution time using memory than other operations, it may result in deteriorated system performance. A spill instruction refers to a code generated when there are no registers to be allotted to data. Normally, a spill instruction comprises two instructions, that is, a store instruction to save in memory the data stored in a register to reserve the register and a load instruction to fetch the saved data to the register.

2. When instructions are scheduled after registers are allotted, allotting the registers may reserve the same register for different pieces of data to be processed normally in parallel, thereby disturbing the parallel process of the data.

That is, when the instruction schedule is performed first, available registers may be short. On the other hand, if registers are allotted first, then the registers may be allotted in the register allotting process such that the smallest possible number of registers can be allotted, thereby preventing the parallel process from being performed successfully.

The above described problems exist conventionally. Since a register allotting process and instruction scheduling are indispensable processes for an optimization compiler, the above described problems have been solved by the following methods in the conventional technology.

1. If instructions have been scheduled before registers are allotted, the instructions are rescheduled after the registers are allotted, and generated spill codes are properly scheduled.

2. If instructions are scheduled after registers have been allotted, then cyclically allotting the registers prevents to some extent the parallel process from being disturbed.

However, the following problems remain in the conventional technology.

1. If instructions are scheduled before registers are allotted;

(1) Two scheduling phases should be followed to schedule a (spill instruction. The effect of scheduling through compilation is not as distinct as the user can expect.

(2) A spill instruction generated by the register allotting process cannot be deleted.

2. If instructions are scheduled after registers have been allotted;

(1) Cyclically allotting the registers recognizes only the parallel arrangement of data, but not intrinsic parallelism of the data including machine-dependency such as the parallelism of operating units.

(2) Some cyclical register allotting methods clearly separate source (reference) registers from destination (definition) registers. In these methods, registers may become short during the operations.

SUMMARY OF THE INVENTION

First, the present invention aims at solving the problem of the process order between allotting registers and scheduling instructions by renaming the registers during the instruction scheduling process so that various optimization requests for compilers can be fully satisfied.

Second, the present invention aims at determining the priority level of each piece of renamed data according to architecture information.

According to a third object of the present invention, if register allotting clearly separates source (reference) registers from destination (definition) registers and therefore available registers become short, then the source and destination registers are renamed to be equivalent to one another such that the parallelism of data is retained and the optimal registers can be used.

Fourth, the present invention aims at separately performing an instruction scheduling process and a register allotting process by removing the necessity of recognizing the instruction schedule and parallelism of hardware in the register allotting process.

A feature of the present invention resides in a compiling apparatus which schedules instructions after allotting registers to generate codes for an efficient parallel process of the instructions, said apparatus having a front-end unit for receiving and analyzing a source program, an optimization unit for optimizing an analysis result, a register allotting unit for allotting the registers to data to be processed as the analysis result, an instruction scheduling unit for rearranging the instructions, and a code output unit for outputting an object program, comprising in the instruction scheduling unit, a register information collecting unit for collecting information indicating a range of available registers, an instruction dependency analyzing unit for analyzing dependency of the instructions in definition and reference, a register renaming unit for renaming the registers by replacing register numbers used for the instructions with other register numbers according to collected register information and an instruction dependency analysis result, and an instruction schedule process unit for rearranging the instructions according to a result of renaming the registers.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 shows an example of the configuration according to the present invention;

FIGS. 2(A)-2(D) show the renaming process according to the present invention:

FIG. 3 shows an example of the architecture information table;

FIG. 4 shows the configuration of the register information management table;

FIG. 5 shows the processes performed by the instruction scheduling unit according to a first embodiment of the present invention;

FIG. 6 is a detailed flowchart showing the register information collecting process;

FIG. 7 is a flowchart of the processes performed by the instruction dependency analyzing unit;

FIG. 8 is a flowchart of the processes performed by the register renaming unit;

FIG. 9 is a detailed flowchart showing the process of determining whether or not the source and destination registers can share the same number;

FIG. 10 is a flowchart showing the process of determining the effectiveness of renaming the registers when the source and destination registers cannot share the same number;

FIG. 11 is a general flowchart showing the processes according to the first embodiment;

FIG. 12 is a general flowchart (continued) showing the processes according to the first embodiment;

FIG. 13 shows the dependency among the instructions in the scheduling range L1;

FIG. 14 shows the result of the register renaming process for the scheduling range L1;

FIG. 15 shows the processes performed by the instruction scheduling unit according to a second embodiment of the present invention;

FIG. 16 is a flowchart of the processes performed by the register renaming unit according to the second embodiment shown in FIG. 15;

FIG. 17 is a general flowchart showing the process according to the second embodiment;

FIG. 18 is a general flowchart (continued) showing the process according to the second embodiment;

FIGS. 19(A)-19(C) show the register renaming process depending on the architecture;

FIG. 20 shows a practical example (1) of the register renaming process performed depending on the architecture;

FIG. 21 shows a practical example (2) of the register renaming process performed depending on the architecture; and

FIG. 22 shows an output example of the debug information according to the present invention.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

FIG. 1 shows an example of the configuration of the present invention.

In FIG. 1, 10 is a source program to be compiled; a processor 11 comprises a CPU, memory, etc.; 12 is a compiler; a front-end unit 13 generates an intermediate text from the source program 10 through sentence and meaning analysis; an optimization unit 14 deletes redundant portions of the intermediate text; a register allotting unit 15 allots registers according to optimization results; an instruction scheduling unit 16 rearranges instructions so that a parallel process can be efficiently performed; a register information collecting unit 17 collects register use information; an instruction dependency analyzing unit 18 analyzes the independency in defining and referring to instructions; a register renaming unit 19 replaces a register number in an instruction with another register number; an instruction schedule process unit 20 schedules instructions according to register renaming results; an architecture information table 21 stores architecture information about a computer in which a program to be compiled is executed; a code output unit 22 outputs codes of, for example, instruction strings written in machine language; a debug information output unit 23 outputs debug information; an object program 24 is obtained by compiling a program; debug information 25 are output by the debug information output unit 23; and a register information management table 30 stores information indicating the use state of registers.

The present invention closely relates to the instruction scheduling unit 16 of the compiler 12. Other units are similar to those of the prior art technology. The instruction scheduling unit 16 comprises the register information collecting unit 17 before the instruction dependency analyzing unit 18, and replaces a register number through the register renaming unit to remove the anti-dependency and output dependency and realize instruction scheduling with improved parallel processes for instructions. The register renaming unit 19 uses the architecture information table 21 to change the renaming priority depending on computer architecture.

According to the present invention, the register information collecting unit 17 calculates the use range of registers according to instruction strings assigned registers. When the instruction dependency analyzing unit 18 analyzes an instruction, the register renaming unit 19 renames registers.

FIGS. 2A through 2D shows the register renaming process.

Assumed are, for example, instruction strings 1 through 4 as shown in FIG. 2A. In instructions 1 through 4, add indicates an add instruction, and sub indicates a subtraction instruction. gr1 through gr10 indicate general purpose registers 1 through 10. For example, instruction 1 is to add values of gr1 and gr2 and assign the sum to gr3. Instruction 3 is to subtract a value of gr7 from that of gr6 and assign the difference to gr3.

According to the dependency of the instruction strings shown in FIG. 2A, instruction 1 defines gr3; instruction 2 refers to gr3; instruction 3 defines gr3, and instruction 4 refers to gr3. Thus, the dependency of the instructions are as shown in FIG. 2B, and the instruction is not allowed to be rearranged in an execution order.

If gr3 in instructions 3 and 4 is renamed into gr10 indicating another general-purpose register as shown in FIG. 2C, then the dependency between instructions 1 and 2 and instructions 3 and 4 is cleared as shown in FIG. 2D. This indicates that instructions 1 and 2 can be executed in parallel with the subsequent instructions 3 and 4.

According to the present invention, the above described register renaming processes improve the efficiency in parallel processes and the performance of the generated object program 24.

FIG. 3 shows an example of the architecture information table used in the embodiment of the present invention.

According to the present embodiment, the architecture information table 21 shown in FIG. 3 is used so that the compiler 12 shown in FIG. 2 properly corresponds to various types of architecture.

Entered in the architecture information table 21 is architecture information such as the number of available registers, instruction sets, instruction latency indicating the instruction delay, etc., for the computer in which a program to be compiled is executed. In the example shown in FIG. 3, the number of registers is 32 for both general-purpose registers and floating point registers. Set in the instruction set column is information for use in converting instructions into standardized internal instructions, for example, an add instruction into an internal operation code INST.sub.13 ADD, an addl instruction into an internal operation code INST.sub.13 ADD.sub.-- L, etc. Entered in the instruction latency column is instruction delay in the four cases where two instructions are not dependent on each other; two instructions are definition-reference related; two instructions are reference-definition related; and two instructions are definition-definition related. In this example, the delay of an add instruction and an addl instruction is represented by 1, and the delay of a dependent fadd instruction (floating point add instruction) is represented by 4. Other information about the number and types of operating units, etc. is entered in the architecture information table 21.

Particularly, register renaming can be effectively realized depending on computer architecture by referring to the architecture information table 21 through the register renaming unit 19 shown in FIG. 1.

Described before explaining the practical operations performed according to the present embodiments is; the configuration of the register information management table 30 generated by the register information collecting unit 17. FIG. 4 shows the configuration of the register information management table 30.

The register information management table 30 stores the results of the analysis for the available range of the registers in basic block units. A basic block refers to a unit comprising serial intermediate text strings (or instruction strings) without branches, stops or interruptions after control is passed to the leading intermediate text (or instruction).

The fields from Kill to Use on the register information management table 30 point to bit vectors of the number of respective registers. Since the number of vectors is a total of 64 in the present embodiments, each bit vector is formed of 64 bits. The bit value 1 or 0 indicates the setting of each register for the field.

Kill indicates which register is not required in the basic block. Live in indicates a register received alive in a basic block. Live out indicates a register exiting alive from a basic block. Use indicates which register is used in the basic block. The Reg Usage field points to the array of the number of registers, and the components of each array are data stored in respective registers. The data is, for example, position information on intermediate text represented by a value set in a register, information indicating whether the value is a variable or constant, etc.

FIG. 5 shows the configuration of the process performed by the instruction scheduling unit 16 according to a first embodiment of the present invention.

According to the first embodiment shown in FIG. 5, the register information collecting unit 17 collects register information and the register information management table 30 is generated for the entire range of scheduling. Then, all intermediate text in the range of scheduling is processed by the instruction dependency analyzing unit 18 and the register renaming unit 19, and the result is processed by the instruction schedule process unit 20.

Described in detail below is the process performed by each unit.

›Process of Register Information Collecting Unit 17!

The register information collecting unit 17 analyzes the range of available registers used for functions to be compiled. According to the first embodiment, the range of scheduling is a basic unit, but is not necessarily a basic unit. The algorithm of analyzing the range of available registers can be based on a well-known data flow analyzing technology (refer to A.V. Aho et al. Compiler--Principle, Technology, and Tools, Chapter 10, published by Science).

The register information collecting unit 17 informs the user of alive/dead register numbers. The information can be stored in the data structure as shown in FIG. 4, and passed to the subsequent phases. A compiler switch can also be designed to output the information to the debug information of the assembler and the compiler.

Alive/dead registers are defined as follows. If data is effective at a given time (for example, at the end of the basic block, at the end of the range of scheduling, and as an intermediate text) and afterwards, then the data is referred to as being alive. Alive data can be referred to. On the other hand, if data is not effective, that is, cannot be referred to, at and after a given time, then the data is dead.

Among the processes of the instruction scheduling unit 16 shown in FIG. 5, the operation of the process performed by the register information collecting unit 17 is described by referring to FIG. 6. FIG. 6 is a flowchart showing in detail the process performed by the register information collecting unit 17 by referring to FIG. 1. In FIG. 6, the register information collecting unit 17 performs its operation in response to the input of the source program 10 after the process 13 performed by the front-end unit, the process 14 performed by the optimization unit, and the process 15 performed by the register allotting unit as in FIG. 1.

FIG. 6 shows in detail the process of the register information collecting with step numbers assigned. First, in step S1, it is determined whether or not the processes in steps S2 through S5 have been completed for all scheduling ranges. If it is determined that the processes have not been completed, then one scheduling range is retrieved in step S2, a register being used in the scheduling range is checked in step S3, and the register being used in the scheduling range is stored as corresponding to USE explained by :referring to FIG. 4.

The register defined in the scheduling range and then referred to is checked in step S4, and it is stored as a register for KILL shown in FIG. 4. In step S5, a set OUT›S! is an empty set and the set IN›S! of registers alive in the scheduling range is calculated by the following equation.

IN›S!=OUT›S!+USE›S!-KILL›S!

If the process for one scheduling range S has been completed, then control returns to step S1 again, and the processes in steps S2 through S5 continue for all scheduling ranges. Thus, the set IN›S! is initialized for all scheduling ranges.

If it is determined that the processes in steps S2 through S5 have been completed for all scheduling ranges in step 1, then it is determined whether or not the processes in steps S8 through S12 have been completed for all scheduling ranges in step S7 after a check flag (CHECKF) is set to 0 in step S6. If not, the set OUT›S! of registers alive when the scheduling range is quit is obtained as all successors, that is, a sum of the set IN for the next jump to scheduling range from the present scheduling range in step S8.

Then, in step S9, the present set IN›S! is defined as a set OLD IN and then the set IN›S! is calculated again in step 10 using the similar equation indicated in step S5.

In step S11, it is determined whether or not the two sets obtained in steps S9 and S10 match each other. If not, the value of the check flag is set to 1 in step S12. If yes, no process is performed. Then, control returns to step S7, and the processes are performed for the next scheduling range.

If it is determined in step S7 that the processes in steps S8 through S12 have been completed for all scheduling ranges, then it is determined whether or not the value of the check flag is 1 in step S13. If yes, control returns to step S6 and the value of the check flag is set to 0. Then, the processes in and after step S7 are repeated. If it is determined that the check flag does not indicate 1 in step S13, then control is passed to the process 18 to be performed by the instruction dependency analyzing unit as shown in FIG. 1.

Described further is the process of collecting register information shown in FIG. 6. As described above, the processes in steps S2 through S5 initialize the two sets IN›S! and OUT›S!. The value of IN›S! is individually calculated for each scheduling range, and OUT›S! is defined as an empty set.

After the value of the check flag is set to 0 in step S6, re-calculations are made for the two sets in the processes in steps S7 through S12 for each scheduling range. Therefore, the values of IN›S! and OUT›S! are variable. If the value of IN›S! varies, the value of the check flag is set to 1.

That is, the value of OUT›S! is calculated for each scheduling range in step S8. The set can be considered a sum of the set IN of the successors of the scheduling range S. The sum of the set IN of all successors is calculated as the value of OUT. OUT›S! is a subset of the sum of the set IN of the successors of the scheduling range S. The sum of the set IN for the successors is calculated for the purpose of shortening the compiling time and obtaining a correct result.

Since the value of the set OUT›S! can be variable in step S8, the value of IN›S! is calculated again in step S10 and is compared with the old value of IN, that is, OLD IN. If they are different from each other, then the value of the set OUT›S! needs a further re-calculation. Therefore, the value of the check flag is set to 1 in step S12, it is determined that control should return to step S6 in step S13, and the processes in steps S8 through S12 are performed again for all scheduling ranges.

These processes are repeated until the processes in steps S8 through S11 have been completed for all scheduling ranges with the value of the check flag set to 0, that is, until a predetermined state is entered. The value of KILL›S! is fixed in the equation of IN in step S10. IN and OUT are calculated to increment the elements of the sets. The increment of the set elements of these sets can be reduced by the original data. Since the original data remains unchanged, a predetermined state can be entered sometime, it is determined that the value of the check flag is 0 in step S13, and control is passed to the process performed by the instruction dependency analyzing unit 18.

Described below in detail is a practical example of collecting register information. The following program is used in the example of collecting the register information.

    ______________________________________
           << program >>
    REAL *8 A(100),B(100), S,FUNF
    S-FUNF (1.000)       L0
    DO 1 I=1, 100
    A(I) = A(I) + S*B(I)
    A(I+1) = A(I+1) + S*B(I+1)
                         L1
    CONTINUE
    CALL SUB(A)
    END                  L2
    ______________________________________

    ______________________________________
    << structure of intermediate text >>
    struct GEN type {
    struct GEN.sub.-- type
                 *next.sub.-- tn
                              ;/* next GEN
    short int    gentype.sub.-- code
                              ;/* type of operation
    short int    genkind.sub.-- code
                              ;/* GEN code
    struct GEN.sub.-- type
                 *back.sub.-- tn;
                               /* back chain
    void         *operand›6!
    int          reg.sub.-- no›6!
    };
    << structure to be used selectively >>
              struct select.sub.-- 1{
              struct select.sub.-- 1 *next
              int     *reg.sub.-- no
              struct GEN.sub.-- type *first
              struct GEN.sub.-- type *last
    ______________________________________

    ______________________________________
    LO:
    33:  entry{none} gp1{sp, ret, fp}
    34:  movehi{u4}  prg28{u4} cnt{2147483648}
                     ›g8!
    35:  call{none}  none lbd.sub.-- "jwe.sub.-- xcop" aad{gp1{prg28{u4}}}
                               ›g8!
    21:  movehi{u4}  std21{u4} ADC›.S0000000!
                     ›g2!
    22:  or{u4}      prg23{u4} std21{u4} ADC›.S0000000!
                     ›g2!  ›g2!
    24:  call{r8}    std24{r8} erd.sub.-- "FUNF" aad(gp1{prg23{u4}}}
                     ›f0!           ›g2!
    25:  move{r8}    prg11{r8} std24{r8}
                     ›f2!   ›f0!
    26:  move{i4}    prg8{14} cnt(100)
                     ›g2!
    27:  move{i4}    prg9{14} cnt(8)
                     ›g3!
    28:  movehi{u4}  std25{u4} ADC›.B0000000+4096!
                     ›g4!
    29:  or{u4}      std26{u4} std25{u4} ADC›.B0000000+4096!
                     ›g4!   ›g4!
    30:  add{u4}     prg27{u4} std26{u4} cnt(-3296)
                     ›g5!   ›g4!
    31:  add{u4}     prg3{u4} std26{u4} cnt{-4096}
                     ›g6!   ›g4!
    32:  add{u4}     prg10{u4} prg27{u4} cnt{8}
    IN = { }
    OUT = { }
    KILL={g2, g3, g4, g5, g6, g7, g8, f0, f2 }
    USE ={g2, g3, g4, g5, g6, g7, g8, f0, f2, sp, fp, ret}
    L1:
     7:  load{r8}    std12{r8} BXD›prg10{u4} +-8!
                     ›f0!     ›g7!
     8:  mult{r8}    std13{r8} std12{r8} prg11{r8}
                     ›f0!    ›f0!    ›f2!
     9:  load{r8}    std14{r8} BXD›prg10{u4} +-808!
                     ›f4!     ›g7!
    10:  add{r8}     std15{r8} std14{r8} std13{r8}
                     ›f0!    ›f4!    ›f0!
    11:  store{r8}   BXD›prg10{u4} +-808! std15{r8}
                       ›g7!       ›f0!
    12:  load{r8}    std16{r8} BXD›prg10{u4} +0!
                     ›f0!     ›g7!
    13:  mult{r8}    std17{r8} std16{r8} prg11{r8}
                     ›f0!    ›f0!   ›f2!
    14:  load{r8}    std18{r8} BXD ›prg3{u4} +prg9 {14}!
                     ›f4!     ›g6!  ›g3!
    15:  add{r8}     std19{r8} std18{r8} std17{r8}
                     ›f0!    ›f4!   ›f0!
    16:  store{r8}   BXD›prg3{u4} +prg9 {14}! std19{r8}
                       ›g6!  ›g3!    ›f0!
    17:  add{i4}     prg9{i4} prg9{i4} cnt {8}
                     ›g3!   ›g3!
    18:  add{u4}     prg10{u4} prg10{u4} cnt {8}
                      ›g7!   ›g7!
    19:  sub{i4}     ctd(prg8{i4}, prg20{cc}) prg8{i4} cnt{1}
                       ›g2!     ›g2!
    20:  bne{cc} {90.0}
                     oud#1 prg20 {cc}
    IN ={ }
    OUT ={ }
    KILL = {f0, f4}
    USE = {g2, g3, g6, g7, f0, f2, f4}
    L2:
    0:   move{u4}    prg4{u4} prg3{u4}
                     ›g8!  ›g2!
    1:   call{none}  none erd.sub.-- "SUB" aad {gp1 {prg4{u4}}}
                              ›g8!
    2:   movehi{u4}  std5{u4} ADC ›.S0000000+24!
                     ›g8!
    3:   or{u4}      prg7{u4} std5{u4} ADC›.S0000000+24!
                     ›g8!   ›g8!
    5:   call{none}  none lbd.sub.-- "jwe.sub.-- xstp" aad {gp1 {prg7{u4}}}
                                ›g8!
    6:   return{i4}  none gpl {sp, ret, fp}
    IN ={ }
    OUT ={ }
    KILL={g8}
    USE ={g2, g8, sp, ret, fp}
    ______________________________________

    ______________________________________
    IN›L0!   = OUT›L0!+USE›L0!-KILL›L0!
             = { } + {g2, g3, g4, g5, g6, g7, g8, f0, f2, sp, fp, ret} -
              {g2, g3, g4, g5, g6, g7, g8, f0, f2}
             = {sp, fp, ret}
    IN›L1!   = OUT›L1!+USE›L1!-KILL›L1!
             = { } +{g2, g3, g6, g7, f0, f2, f4} - {f0, f4}
             = {g3 g3 g6 g7 f2}
    IN›L2!   = OUD›L2!+USE›L2! - KILL›L2!
             = { } + {g2, g6, sp, ret, fp} - {g8}
             = {g2, sp, ret, fp}
    ______________________________________

    ______________________________________
    checkf       = 0
    OUT›L0!      = IN›L0! + IN›L1!
                 = {sp,fp,ret,g2,g3,g6,g7,f2}
    oldin        = IN›L0! ={sp,fp,ret}
    IN›L0!       = OUT›L0! +USE›L0!-KILL›L0!
                 = {sp,fp,ret,g2,g3,g6,g7,f2} +
                  {g2,g3,g4,g5,g6,g7,g8,f0,f2,sp,fp,re -
                  {g2,g3,g4,g5,g6,g7,g8,f0,f2}
                 = {sp,fp,ret}
    if (oldin l = IN›L0!) checkf = 1
    OUT›L1!      = IN›L1! + IN›L2! + IN›L1!
                 = {g2,g3,g6,g7,f2} + {g2,sp,ret,fp}
                 = {g2,g3,g6,g7,f2,sp,ret,fp}
    oldin        = IN›L1! = {g2,g3,g6,g7,f2}
    IN›L1!       = OUD›L1! + USE›L1!-KILL›L1!
                 = {g2,g3,g6,g7,f2,sp,ret,fp} +
                  {g2,g3,g6,g7,f0,f2,f4} - {f0,f4}
                 = {g2,g3,g6,g7,f2,sp,ret,fp}
    if (oldin l = IN›L1!) checkf = 1 <<-
    OUT›L2!      = IN›L2!
                 = {g2,sp,fp,ret}
    oldin        = IN›L2! = {g2,sp,fp,ret}
    IN›L2!       = OUD›L2!+USE›L2! - KILL›L2!
                 = {g2,sp,ret,fp}+
                  {g2,g8,sp,ret,fp} - {g8}
                 = {g2,sp,fp,ret}
    if (oldin 1= IN›L1!) checkf = 1
    if (checkf == 1 ) goto LOOP <<-
    else EXIT LOOP
    ______________________________________

    ______________________________________
    OUT›L1!     = IN›L1! + IN›L2! + IN›L1!
                = {g2,g3,g6,g7,f2,sp,ret,fp} + {g2,sp,ret,fp}
                = {g2,g3,g6,g7,f2,sp,ret,fp}
    oldin       = IN›L1! = {g2,g3,g6,g7,f2,sp,ret,fp}
    IN›L1!      = OUD›L1! + USE›L1!-KILL›L1!
                = {g2,g3,g6,g7,f2,sp,ret,fp} +
                  {g2,g3,g6,g7,f0,f2,f4} -{f0,f4}
                = {g2,g3,g6,g7,f2,sp,ret,fp}
    if (oldin l = IN›L1!) checkf = 1
    OUT›L2!     = IN›L2!
                = {g2,sp,fp,ret}
    oldin       = IN›L2! = {g2,sp,fp,ret}
    IN›L2!      = OUD›L2!+USE›L2! - KILL›L2!
                = {g2,sp,ret,fp}+{g2,g8,sp,ret,fp} - {g8}
                = {g2,sp,fp,ret}
    if (oldin l = IN›L1!) checkf = 1
    if (checkf == 1 ) goto LOOP
    else EXIT LOOP
    ______________________________________

    ______________________________________
    L0:
    IN          = {sp,fp,ret}
    USE         = {g2,g3,g4,g5,g6,g7,g8,f0,f2,sp,fp,ret}
    OUT         = {sp,fp,ret,g2,g3,g6,g7,f2}
    L1:
    IN          = {g2,g3,g6,g7,f2,sp,fp,ret}
    USE         = {g2,g3,g6,g7,f0,f2,f4}
    OUT         = {sp,fp,ret,g2,g3,g6,g7,f2}
    L2:
    IN          = {g2,sp,fp,ret}
    USE         = {g2,g8,sp,fp,ret}
    OUT         = {g2,sp,fp,ret}
    ______________________________________

    ______________________________________
    L1:
              load        (gr7-8), f0   (7)
              subcc       g2,1,g2      (19)
              load        (gr7-808), f4
                                        (9)
              fauld       f0,f2,f0      (8)
              nop
              nop
              nop
              faddd       f0,f4,f0     (10)
              nop
              nop
              nop
              store       f0, (g7-808) (11)
              load        (g7+0), f0   (12)
              add         g7,9,g7      (14)
              load        (g4+g3), f4  (14)
              fauld       f0,f2,f0     (13)
              nop
              nop
              nop
              faddd       f0,f4,f0     (15)
              nop
              nop
              nop
              store       f0, (g6+g1)
              add         g3,8,g3      (17)
              bne LOOP
    ______________________________________

    ______________________________________
    7:     load{r8}  std12{r8} BXD ›prg10{u4} +-6!
                     ›f0!    ›g7!
    8:     mult{r8}  std13{r8} std12{r8} prg11{r8}
                     ›f0!   ›f0!   ›f1!
    9:     load{r8}  std14{r8} BXD ›prg10{u4} +-808!
                     ›f4!      ›g7!
    10:    add{r8}   std15{r8} std14{r8} std13{r8}
                     ›f0!   ›f4!   ›f0!
    11:    store{r8} BXD {prg10{u4}+-208} std15{r8}
                       ›g7!    ›f0!
    12:    load{r8}  std15{r8} BXD ›prg10{u4} +0!
                     ›f6!   ›g7!
    13:    mult{r8}  std17{r8} std16{r8} prg11{r8}
                     ›f0!   ›f6!   ›f2!
    14:    load{r8}  std18{r8} BXD ›prg3{u4}+prg3 {14}!
                     ›f4!    ›g6!  ›g3!
    15:    add{r8}   std19{r8} std18{r8} std17{r8}
                     ›f0!   ›f4!   ›f0!
    16:    store{r8} BXD ›prg3{u4} +prg9 {14}! std19{r8}
                       ›f6!  ›g3!  ›f0!
    17:    add{f4}   prg9 {14} prg9 {14} cnt{r8}
                     ›g3!  ›g3!
    18:    add{u4}   prg10{u4} prg10{u4} cnt {8}
                      ›g7!  ›g7!
    19:    sub{i4}   ctd (prg6 {14}, prg20 {cc}) prg8 {14} cnt {1}
                       ›g2!      ›g2!
    20:    bne {cc}  oud#1 prg20 {cc}
           {90.0}
    ______________________________________

    ______________________________________
    7:     load{r8}  std12{r8} BXD ›prg10{u4}+-8!
                     ›f0!   ›g7!
    8:     mult{r8}  std13{r8} std12{r8} prg11{r8}
                     ›f0!   ›f0!   ›f2!
    9:     load{r8}  std14{r8} BXD(prg10{u4}+-808)
                     ›f4!   ›g7!
    10:    add{r8}   std15{r8} std14{r8} std13{r8}
                     ›f0!   ›f4!   ›f0!
    11:    store{r8} BXD(prg10{u4}+-808) std15{r8}
                       ›g7!   ›f0!
    12:    load{r8}  std14{r8} BXD ›prg10{u4}+9!
                     ›f8!   ›g7!
    13:    mult{r8}  std17{r8} std16{r8} prg11{r8}
                     ›f8!   ›f8!   ›f2!
    14:    load{r8}  std18{r8} BXD ›prg3{u4}+prg9 {14}!
                     ›f4!    ›g6!  ›g3!
    15:    add{r8}   std19{r8} std18{r8} std17{r8}
                     ›f0!   ›f4!   ›f6!
    16:    store{r8} BXD›prg3{u4}+prg5 {14}! std19 {r6}
                       ›g8!  ›g5!  ›f0!
    17:    add{i4}   prg3 {14} prg9 {14} cnt {8}
                     ›g3!  ›g3!
    18:    add{u4}   prg10{u4} prg10{u4} cnt {8}
                     ›g7!  ›g7!
    19:    sub{i4}   ctd (prg8 {14}, prg20 {cc}) prg8 {14} cnt {1}
                       ›g2!    ›g2!
    20:    bne {cc}  oud#1 prg20 {cc}
           {90.0}
    ______________________________________

    ______________________________________
    7:     load{r8}  std12{r8} BXD›prg10{u4}+-8!
                     ›f0!     ›g7!
    8:     mult{r8}  std13{r8} std12{r8} prg11{r8}
                     ›f0!   ›f0!   ›f2!
    9:     load{r8}  std14{r8} BXD ›pgr10{u4}+-808!
                     ›f4!   ›g7!
    10:    add{r8}   std15{r8  std14{r8} std13 {r4!
                     ›f0!   ›f4!   ›f0!
    11:    store{r8} BXD›prg10{u4}+-808! std15{r8}
                        ›g7!   ›f0!
    12:    load{r8}  std16{r8} BXD ›prg10{u4}+-0!
                     ›f6!   ›g7!
    13:    mult{r8}  std17{r8} std16{r8} prg11{r8}
                     ›f6!   ›f6!   ›f2!
    14:    load{r8}  std18{r8} BXD ›prg3{u4}+prg9 {14}!
                     ›f8!    ›g6!  ›g3!
    15:    add{r8}   std19{r8} sd18{r8} std17{r8}
                     ›f0!   ›f8!   ›f6!
    16:    store{r8} BXD›prg3{u4}+prg9 {14}! std13{r8}
                       ›g6!  ›g3!  ›f0!
    17:    add{i4}   prg3 {14} prg3 {14} cnt {8}
                     ›g3!  ›g3!
    18:    add{u4}   prg10{u4} prg10{u4} cnt {8}
                     ›g7!  ›g7!
    19:    sub{i4}   ctd(prg8 {f4}, prg20 {cc}) prg6 {14} cnt {1}
                       ›g2!    ›g2!
    20:    bne{cc}   oud#1 prg20 {cc}
           {90.0}
    ______________________________________

    ______________________________________
    7:     load{r8}  std12{r8} BXD ›prg10{u4}+-8!
                     ›f0!    ›g7!
    8:     mult{r8}  std13{r8} std12{r8} prg11{r8}
                     ›f0!   ›f0!   ›f2!
    9:     load{r8}  std14{r8} BXD›prg10{u4+-808!
                     ›f4!   ›g7!
    10:    add{r8}   std13{r8} std14{r8} std13{r8}
                     ›f0!   ›f4!   ›f0!
    11:    store{r8} BXD(prg10{u4}+-808} std15{r8)
                       ›g7!  ›f0!
    12:    load{r8}  std16{r8} BXD›prg10{u4}+0!
                     ›f6!   ›g7!
    13:    mult{r8}  std17{r8} std16{r8} prg11{r8}
                     ›f6!   ›f6!  ›f2!
    14:    load{r8}  std18{r8} BXD(prg3{u4}+prg9 {14}!
                     ›f8!    ›g6!  ›g3!
    15:    add{r8}   std19{r8} std18{r8} std17{r8}
                     ›f8!   ›f8!   ›f6!
    16:    store{r8} BXD›prg3{u4+pr9 {14}! std19{r8}
                       ›g6!  ›g3!  ›f6!
    17:    add{i4}   prg9 {14} prg9 {14} cnt {8}
                     ›g3!   ›g3!
    18:    add{u4}   prg10{u4} prg10{u4} cnt {8}
                     ›g7!   ›g7!
    19:    sub {i4}  ctd(prg8 {14}, prg20 {cc}) prg8{14} cnt {1}
                       ›g2!    ›g2!
    20:    bne {cc}  oud#1 prg20 {cc}
           {90.0}
    ______________________________________

    ______________________________________
              load        ›gr7-8!, f0
                                     (7)
              subcc       g2, 1, g2 (19)
              load        ›g7+0!, f6
                                    (12)
              load        ›gr7-808!f4
                                     (9)
              fmuld       f0, f2, f0
                                     (8)
              load        ›g6+g3!, f8
                                    (14)
              add         g7, 8, g7 (14)
              fmuld       f6, f2, f6
                                    (13)
              nop
              nop
              faddd       f0, f4, f0
                                    (10)
              faddd       f6, f8, f6
                                    (15)
              nop
              nop
              store       f0, ›g7-808!
                                    (11)
              store       f6, ›g6+g3!
              add         g3, 8, g3 (17)
              bne LOOP
    ______________________________________

    ______________________________________
    (1)           LOAD         A, f0
    (2)           FMULT        f0, f2, f0
    (3)           LOAD         B, f4
    (4)           FADD         f0, f4, f0
    (5)           STORE        f0, C
    (6)           LOAD         D, f4
    (7)           LOAD         E, f0
    (8)           FMULT        f0, f2, f0
    (9)           FADD         f0, f4, f0
    (10)          STORE        f0, F
    ______________________________________

    ______________________________________
                  LOAD         A, f0
                  LOAD         F, f4
                  FMULT        f0, f2, f0
                  nop
                  nop
                  nop
                  FADD         f0, f4, f0
                  nop
                  nop
                  nop
                  STORE        f0, C
                  LOAD         D, f4
                  LOAD         E, f0
                  nop
                  FMULT        f0, f2, f0
                  nop
                  nop
                  nop
                  FADD         f0, f4, f0
                  nop
                  nop
                  nop
                  STORE        f0, 7
    ______________________________________

    ______________________________________
    (1)           LOAD         A, f0
    (2)           FMULT        f0, f2, f0
    (3)           LOAD         B, f4
    (4)           FADO         f0, f4, f0
    (5)           STORE        f0, C
    (6)           LOAD         D, f6
    (7)           LOAD         E, f0
    (8)           FMULT        f0, f2, f0
    (9)           FADO         f0, f6, f0
    (10)          STORE        f0, F
                        LOAD A, f0
                        LOAD B, f4
                        FMULT f0, f2, f0
                        LOAD D, f6
                        nop
                        nop
                        nop
                        FADO f0, f4, f0
                        nop
                        nop
                        nop
                        STORE f0, C
                        LOAD E, f0
                        nop
                        FMULT f0, f2, f0
                        nop
                        nop
                        nop
                        FADO f0, f4, f0
                        nop
                        nop
                        nop
                        STORE f0, F
    ______________________________________

    ______________________________________
    (1)           LOAD         A, f0
    (2)           FMULT        f0, f2, f0
    (3)           LOAD         B, f4
    (4)           FADO         f0, f4, f0
    (5)           STORE        f0, C
    (6)           LOAD         D, f4
    (7)           LOAD         E, f6
    (8)           FMULT        f6, f2, f6
    (9)           FADO         f6, f4, f6
    (10)          STORE        f0, F
                        LOAD A, f0
                        LOAD B, f4
                        LOAD E, f4
                        FMULT f0, f2, f0
                        nop
                        FMULT f6, f2, f6
                        nop
                        FADO f0, f4, f0
                        nop
                        nop
                        nop
                        STORE f0, C
                        LOAD D, f4
                        nop
                        FADO f6, f4, f6
                        nop
                        nop
                        nop
                        STORE f0, F
    ______________________________________

    ______________________________________
    (1)           LOAD         A, f0
    (2)           FMULT        f0, f2, f0
    (3)           LOAD         B, f4
    (4)           FADO         f0, f4, f0
    (5)           STORE        f0, C
    (6)           LOAD         D, f4
    (7)           FADO         f2, f2, f0
    (8)           FMULT        f0, f4, f0
    (9)           STORE        f0, E
    ______________________________________

    ______________________________________
                        LOAD A, f0
                        LOAD B, f4
                        FMULT f0, f2, f0
                        nop
                        nop
                        nop
                        FADO f0, f4, f0
                        nop
                        nop
                        STORE f0, C
                        LOAD D, f4
                        FADO f2, f2, f0
                        nop
                        nop
                        nop
                        FMULT f0, f4, f0
                        nop
                        nop
                        nop
                        STORE f0, E
    ______________________________________

    ______________________________________
    (1)           LOAD         A, f0
    (2)           FMULT        f0, f2, f0
    (3)           LOAD         B, f4
    (4)           FADO         f0, f4, f0
    (5)           STORE        f0, C
    (6)           LOAD         D, f0
    (7)           FADO         f2, f2, f6
    (8)           FMULT        f6, f4, f6
    (9)           STORE        f6, E
                        LOAD A, f0
                        FADO f2, f2, f6
                        LOAD B, f4
                        FMULT f0, f2, f0
                        nop
                        nop
                        nop
                        FADO f0, f4, f0
                        nop
                        nop
                        nop
                        LOAD D, f4
                        nop
                        FMULT f0, f4, f0
                        nop
                        nop
                        nop
                        STORE f0, E
    ______________________________________

• Inventors
  Hayashi, Masakazu;
• Assignee
  Fujitsu Limited (Kawasaki, JP)
• Published
  Oct-27-1998
• Current US Classes:
  717/146
  717/154
  717/159
• Application #
  393561
• International Classes
  G06F 009/45
• Field of Search
  395/700 395/705 395/707 395/709
• Examiner
  Voeltz; Emanuel Todd
• Agent
  Staas & Halsey
• US Patent References:
  4931928
  5021945
  5261062
  5404551
  5428793
  5497499
  5557793