Compile method, non-transitory computer-readable recording medium storing compile program, and information processing device

An information processing device includes: a memory that stores a program; and a processor that executes the program to perform operations, wherein the operations includes: specifying a first register which is allocated to scalar data and satisfies a condition that a survival interval of the scalar data includes a survival interval of first data to which any register is not allocated; and allocating an empty area of the first register to the first data.

CROSS-REFERENCE TO RELATED APPLICATION

This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2016-081847, filed on Apr. 15, 2016, the entire contents of which are incorporated herein by reference.

FIELD

The embodiments discussed herein are related to a compile technology.

BACKGROUND

In translating a source code into an object code, an optimization called a register allocation is performed. Since the register resources of a processor are limited in general, there is a case in which data (for example, data of variables) to which a register may not be allocated is generated in allocating the register. Such a phenomenon is called a register overflow. When the register overflow occurs, the data is temporarily retreated to a memory, and the like. The retreated data is restored to the register when the register is back to usable.

Related technologies are disclosed in, for example, Japanese Laid-Open Patent Publication Nos. 2008-009957 and 10-293691.

SUMMARY

According to one aspect of the embodiments, an information processing device includes: a memory that stores a program; and a processor that executes the program to perform operations, wherein the operations includes: specifying a first register which is allocated to scalar data and satisfies a condition that a survival interval of the scalar data includes a survival interval of first data to which any register is not allocated; and allocating an empty area of the first register to the first data.

DESCRIPTION OF EMBODIMENTS

Since a load command and a store command are issued in retreating and restoring, an execution performance of a source code is deteriorated. When the register resources of a processor increases, the occurrence of register overflow may be suppressed. For example, when the register resources increases, a command set architecture is significantly changed, and as a result, it may be difficult to increase the register resources.

FIG. 1is a hardware configuration diagram of an information processing device1according to an embodiment. The information processing device1includes a processor10, a memory11, a storage device12, and a bus13. The processor10, the memory11, and the storage device12are coupled to each other by the bus13. The processor10is, for example, a central processing unit (CPU). The memory11is, for example, a dynamic random access memory (DRAM). The storage device12is, for example, a hard disk drive (HDD).

The processor10includes cores101and102, Level (L) 1 caches103and104, and an Level (L) 2 cache105. The core101has a register including one or a plurality of universal registers1011and one or a plurality of SIMD registers1012. The core102has a register including one or a plurality of universal registers1021and one or a plurality of SIMD registers1022. Meanwhile, inFIG. 1, the number of cores of the processor10is 2, but is not limited thereto. Further, as the register other than the SIMD register, a register other than the universal register may be additionally included.

A program for executing processing of the embodiment is, for example, stored in the storage device12and executed by the processor10to realize a function of a compile processing unit15illustrated inFIG. 2.FIG. 2illustrates a functional block diagram of the information processing device1. The information processing device1includes the compile processing unit15, a source code storing unit16, a first data storing unit17, a second data storing unit18, and an object code storing unit19. The source code storing unit16, the first data storing unit17, the second data storing unit18, and the object code storing unit19are provided in, for example, the storage device12.

The compile processing unit15includes a source code interpreting unit151, an optimization unit152, a first register allocating unit153, an allocation interpreting unit154, a second register allocating unit155, and a generation unit156.

The source code interpreting unit151executes lexical analysis, syntax analysis and the like for a source code stored in the source code storing unit16to output an execution result to the optimization unit152. The lexical analysis and the syntax analysis may be known. The optimization unit152executes an optimization processing which does not depend on an architecture and a translation processing into an architecture command based on an execution result acquired from the source code interpreting unit151and outputs an execution result of the optimization unit152to the first register allocating unit153. The first register allocating unit153executes register allocation by a method such as a coloring method based on the execution result acquired from the optimization unit152to output a result of the register allocation to the allocation interpreting unit154. The method may be known. The allocation interpreting unit154generates information on register overflow and information on an empty area of an SIMD register from the result acquired from the first register allocating unit153to store the information on the register overflow in the first data storing unit17and store the information on the empty area of the SIMD register in the second data storing unit18. The second register allocating unit155executes processing by using data stored in the first data storing unit17and data stored in the second data storing unit18and updates the data stored in the first data storing unit17and the data stored in the second data storing unit18based on a processing result. The generation unit156generates an object code by using the data stored in the first data storing unit17and the data stored in the second data storing unit18based on an allocation result by the first register allocating unit153and stores the generated object code in the object code storing unit19.

For example, the processing by the source code interpreting unit151, the processing by the optimization unit152, the processing by the first register allocating unit153, and the processing by the generation unit156may be a well-known processing.

FIG. 3illustrates a function block diagram of the second register allocating unit155. The second register allocating unit155includes a first processing unit1551and a second processing unit1552.

The first processing unit1551executes a first optimization processing regarding the register allocation. The second processing unit1552executes a second optimization processing regarding the register allocation.

Hereinafter, the register allocation executed when the source code stored in the source code storing unit16is translated into the object code will be described. It is assumed that the information on the register overflow is stored in the first data storing unit17, and further, the information on the empty area of the SIMD register is stored in the second data storing unit18, as a result of the processing by the allocation analysis unit154.

FIG. 4Aillustrates an example of the information on the register overflow stored in the first data storing unit17. In the example ofFIG. 4A, the information on the register overflow includes a data type, information indicating a live range (also called a survival interval), identification information of an allocated register, and a turn. The data type indicates a type (SIMD or scalar in the embodiment) of data to which a register is not allocated by the processing by the first register allocating unit153. The live range is the live range of the data. The turn is a number allocated to each data block after dividing in the case of dividing data (hereinafter, called SIMD data. The SIMD data is used in an SIMD operation) in which the data type is the “SIMD.” For example, when the SIMD data is divided into two, the turn of the data block of the first half part is 1 and the turn of the data block of the second half part is 2. Meanwhile, in a step before the processing by the second register allocating unit155is executed, the identification information and the turn of the allocated register are not stored.

FIG. 4Billustrates an example of the information on the empty area of the SIMD register stored in the second data storing unit18. In the example ofFIG. 4B, the information on the empty area of the SIMD register includes the identification information of the register, information indicating a live range of scalar data (for examples, data used in a scalar operation) stored in the register, and a data type of additionally stored data. In the embodiment, each SIMD register has 4 areas, and one area is used by the scalar data. Accordingly, the register registered in the second data storing unit18has 3 empty areas in a step before data is additionally stored. Meanwhile, in the step before the processing by the second register allocating unit155is executed, a data type of the data to be additionally stored is not stored.

Hereinafter, the processing executed by the second register allocating unit155will be described by usingFIGS. 5 to 19B.

First, the second register allocating unit155reads the information on the register overflow from the first data storing unit17(FIG. 5: step S1).

The second register allocating unit155determines whether the register overflow occurs based on the information read from the first data storing unit17(step S3). When it is determined that the register overflow does not occur (step S3: No route), since the register allocation by the second register allocating unit155need not be performed, the processing ends.

Meanwhile, when it is determined that the register overflow occurs (step S3: Yes route), the second register allocating unit155specifies one unprocessed entry among entries included in the information read from the first data storing unit17(step S5).

The second register allocating unit155reads the information on the empty area of the SIMD register from the second data storing unit18(step S7).

The second register allocating unit155determines whether an empty space exists in an area of the SIMD register based on the information read from the second data storing unit18(step S9). As described above, the register registered in the second data storing unit18has 3 empty areas in the step before data is additionally stored. In the embodiment, the SIMD data is divided into two, and the data blocks after the division uses two areas, respectively, and the scalar data uses one area. Then, allocation is performed such that among the 3 empty areas, two areas are used for the data blocks originated from the SIMD data, and one area is used for the scalar data. Accordingly, the register registered in the second data storing unit18has the empty areas as long as both the data blocks originated from the SIMD data and the scalar data are not additionally stored.

When it is determined that no empty space exists in the area of the SIMD register (step S9: No route), the register may not be allocated, even by the processing by the second register allocating unit155, to data in which the register is not allocated by the processing by the first register allocating unit153. Accordingly, the processing ends.

Meanwhile, when it is determined that an empty space exists in the area of the SIMD register (step S9: Yes route), the second register allocating unit155determines whether the data type included in the entry specified in step S5is the “SIMD” (step S11).

When it is determined that the data type is the “SIMD” (step S11, Yes route), the second register allocating unit155calls the first processing unit1551to cause the first processing unit1551to execute the first optimization processing (step S13). The first optimization processing will be described by usingFIGS. 6 to 12B.

First, the first processing unit1551specifies a live range of the SIMD data (hereinafter, referred to as the “SIMD data to be processed”) of the entry specified in step S5from the information on the register overflow. Then, the first processing unit1551searches two SIMD registers satisfying a condition that the scalar data having a live range including the specific live range is to be stored, in the information on the empty area of the SIMD register (FIG. 6, step S21).

As illustrated inFIG. 7, in the embodiment, the SIMD data is divided into the data block of the first half part and the data block of the second half part. As a result, two SIMD registers to be allocated to the SIMD data are prepared.

The first processing unit1551determines whether two SIMD registers satisfying the condition exist (step S23). When it is determined that two SIMD registers satisfying the condition do not exist (step S23: No route), since the empty area may not be allocated with respect to the SIMD data to be processed, the process returns to the processing of a call source.

Meanwhile, when it is determined that two SIMD registers satisfying the condition exist (step S23: Yes route), the first processing unit1551stores the first half part of the SIMD data to be processed in the empty area of one SIMD register between the two SIMD registers satisfying the condition (step S25).

Herein, by referring toFIGS. 8A to 9B, a method for storing the first half part of the SIMD data to be processed in the empty area of the SIMD register will be described.

InFIG. 8A, in a % f2 register, a figure attached with hatching indicates the scalar data. First, as illustrated inFIG. 8A, the % f2 register is virtually coupled to the % f2 register, and a register having 8 areas illustrated inFIG. 8Bis virtually generated. InFIG. 8B, the scalar data of a first area from a left side and the scalar data of a fifth area from the left side are the same as each other. In addition, the data in the register illustrated inFIG. 8Bis shifted to a left-side direction by 2 areas. Then, since data of the fifth area from the left side inFIG. 8Bmoves to a third area at the left side, a % f2 register801illustrated inFIG. 8Cis generated.

The SIMD data to be processed is virtually coupled to the % f2 register801, and the register having 8 areas illustrated inFIG. 9Ais virtually generated. In addition, the data in the register illustrated inFIG. 9Ais shifted to the left-side direction by 2 areas. Then, inFIG. 9A, since data of a third area from the left side moves to a first area from the left side and further, fifth and sixth data from the left side moves to third and fourth areas from the left side respectively, a % f2 register901illustrated inFIG. 9Bis generated. By such a configuration, the first half part of the SIMD data to be processed is stored in the empty area of the SIMD register.

However, as the method for storing the data in the empty area of the SIMD register, a method other than the methods described by usingFIGS. 8A to 9Bmay be used.

Referring back toFIG. 6, the first processing unit1551stores the identification information of the register (the % f2 register in the examples ofFIGS. 8A to 9B) allocated to the first half part of the SIMD data to be processed in the first data storing unit17(step S27).

The first processing unit1551stores a turn (“1” in the embodiment) of the first half part of the SIMD data to be processed in the first data storing unit17(step S29).

The first processing unit1551stores the second half part of the SIMD data to be processed in the empty area of the other SIMD register between the two SIMD registers satisfying the condition (step S31). Since the second half part of the SIMD data to be processed is stored in the empty area of the SIMD register by the method such as the method described by usingFIGS. 8A to 9B, detailed description thereof will be omitted. Herein, as illustrated inFIG. 10, it is assumed that the second half part of the SIMD data to be processed is stored in the empty area of a % f4 register.

Accordingly, the SIMD register becomes a state illustrated inFIG. 11as a whole. InFIG. 11, a part other than the first half part and the second half part of the SIMD data to be processed among parts attached with the hatching corresponds to a part in which the allocation is performed by the register allocation by the first register allocating unit153. In the embodiment, an area just after the area in which the scalar data is stored just becomes the empty area so as to newly store the scalar data.

The first processing unit1551stores the identification information of the register (the % f4 register in the example ofFIG. 10) allocated to the second half part of the SIMD data to be processed in the first data storing unit17(step S33).

The first processing unit1551stores a turn (“2” in the embodiment) of the second half part of the SIMD data to be processed in the first data storing unit17(step S35). Then, the process returns to the processing of the call source.

By the above-described processing, for example, data illustrated inFIG. 12Ais stored in the first data storing unit17. InFIG. 12A, “% f2” and “% f4” are stored as the identification information of the register allocated to the SIMD data, and “1” and “2” are stored as the turn. Further, for example, data as illustrated inFIG. 12Bis stored in the second data storing unit18. InFIG. 12B, as the data type of the data which is additionally stored, “Simd” is stored in the entries of the % f2 register and the % f4 register.

Referring back to the description ofFIG. 5, when the first optimization processing ends, the process proceeds to a processing of step S19. Meanwhile, when the data type is not the “SIMD” (step S11: No route), the second register allocating unit155determines whether the data type is the “scalar” (step S15).

When it is determined that the data type is not the “scalar” (step S15: No route), the process proceeds to the processing of step S19. Meanwhile, when it is determined that the data type is the “scalar” (step S15, Yes route), the second register allocating unit155calls the second processing unit1552to cause the second processing unit1552to execute the second optimization processing (step S17). The second optimization processing will be described by usingFIGS. 13 to 15.

First, the second processing unit1552specifies the live range of the scalar data (hereinafter, called scalar data to be processed) of the entry specified in step S5from the information on the register overflow. Then, the second processing unit1552searches the SIMD register satisfying a condition that the scalar data having the live range including the specific live range is stored in the information on the empty area of the SIMD register (FIG. 13: step S41).

The second processing unit1552determines whether the SIMD register satisfying the condition exists (step S43). When it is determined that the SIMD register satisfying the condition does not exist (step S43: No route), since the empty area may not be allocated with respect to the scalar data to be processed, the process returns to the processing of the call source.

Meanwhile, when it is determined that the SIMD register satisfying the condition exists (step S43: Yes route), the second processing unit1552stores the scalar data to be processed in the empty area of the SIMD register satisfying the condition (step S45).

For example, as illustrated inFIG. 14A, considered is a case in which in the state where the scalar data has already been stored in a % f6 register, the scalar data is newly stored in the % f6 register. In this case, as illustrated inFIG. 14B, the scalar data is newly stored in the empty area just after the already stored scalar data. Accordingly, the first half part or the second half part of the SIMD data may be stored in the two remaining areas.

Accordingly, the SIMD register becomes the state illustrated inFIG. 15as a whole. InFIG. 15, a part other than the scalar data to be processed among the parts attached with the hatching corresponds to the part in which the allocation is performed by the register allocation by the first register allocating unit153. In the embodiment, a third area and a fourth area from the left side just become the empty area so as to newly store the SIMD data.

Referring back to the description ofFIG. 13, the second processing unit1552stores the identification information of the register (the % f6 register in the example ofFIG. 14) allocated to the scalar data to be processed in the first data storing unit17(step S47). Then, the process returns to the processing of the call source.

By the above-described processing, for example, data illustrated inFIG. 16Ais stored in the first data storing unit17. InFIG. 16A, “% f6” is stored as the identification information of the register allocated to the scalar data. Further, for example, data illustrated inFIG. 16Bis stored in the second data storing unit18. InFIG. 16B, as the data type of the data which is additionally stored, the “scalar” is stored in the entry of the % f6 register.

Referring back toFIG. 5, when the second optimization processing ends, the process proceeds to the processing of step S19. The second register allocating unit155determines whether an unprocessed entry exists (step S19). When it is determined that an unprocessed entry exists (step S19, Yes route), the process returns to the processing of step S5. Meanwhile, when it is determined that an unprocessed entry does not exist (step S19, No route), the processing ends.

When the above-described processing is executed, more data are allocated to the register, and as a result, an access from the processor10to the memory11may be reduced to increase the execution performance of the program.

By usingFIGS. 17A to 19B, a method for restoring the original SIMD data from the first half part and the second half part of the SIMD data will be described. Herein, as illustrated inFIG. 11, it is assumed that the % f2 register is allocated to the first half part, and the % f4 register is allocated to the second half part.

First, as illustrated inFIG. 17A, the % f4 register is virtually coupled to the % f2 register, and a register having 8 areas illustrated inFIG. 17Bis virtually generated. In addition, the data in the register illustrated inFIG. 17Bis shifted to the left-side direction by 2 areas. Then, a % f2 register1701illustrated inFIG. 17Cis generated.

Further, as illustrated inFIG. 18A, the % f2 register1701is virtually coupled to a definable SIMD register (herein, the SIMD register originally allocated to the SIMD data), and as a result, the register having 8 areas, which is illustrated inFIG. 18Bis virtually generated. In addition, the data in the register illustrated inFIG. 18Bis shifted to the left-side direction by 2 areas. Then, a definable SIMD register1801illustrated inFIG. 18Cis generated. Meanwhile, the processing described by usingFIGS. 17A to 17Cis executed even with respect to the second half part of the SIMD data to generate a % f4 register1802.

In addition, the % f4 register1802is virtually coupled to the definable SIMD register1801, and as a result, the register having 8 areas, which is illustrated inFIG. 19Ais virtually generated. In addition, the data in the register illustrated inFIG. 19Ais shifted to the left-side direction by 2 areas. Then, a definable SIMD register1901illustrated inFIG. 19Bis generated.

The embodiment of the present disclosure has been described above, but the present disclosure is not limited thereto. For example, the functional block configuration of the information processing device1described above may be different from an actual program module configuration.

Further, the configuration of each table described above is merely an example and may not be necessarily required. Further, in the processing flow, the processing turn may be changed as long as the processing result is not changed. Moreover, the processings may be executed in parallel.

Further, the SIMD register in the embodiment has 4 areas, but the number of the areas is not limited. Further, in the above-described example, the number of the data blocks obtained by dividing the SIMD data is 2, but is not limited.

The above-described embodiment of the present disclosure may be summarized as follows.

The information processing device according to a first aspect of the embodiment has (A) a specification unit that specifies a first single instruction multiple data (SIMD) register allocated to scalar data and further, satisfying a condition that a survival interval of the scalar data includes a survival interval of the first data to which any register is not allocated and (B) an allocation unit allocating to the first data the empty area of the first SIMD register specified by the specification unit.

As a result, the SIMD register allocated to the scalar data may be usefully used and occurrence of register overflow may be suppressed to enhance execution performance of the program. Further, the first SIMD register allocated to data in which the survival interval is common to at least a part of the survival interval of the first data may be suppressed from being allocated to the first data.

Further, the above-described allocation unit may (b1) divide the first data into a plurality of data blocks when the first data is SIMD data and (b2) allocate the empty areas of a plurality of respective first SIMD registers specified by the specification unit to any one of a plurality of data blocks. Since the first SIMD register is allocated to the scalar data, there may be a possibility that one first SIMD register will not be able to store the first data. Accordingly, the allocation of the SIMD data may be appropriately performed by performing as described above.

Further, the allocation unit (b3) may allocate to the first data the empty area just after the area in which the scalar data is stored in the first SIMD register when the first data is the scalar data. As a result, the scalar data may be allocated so as to prevent the allocation of the SIMD data from being interrupted.

A compile method according to a second aspect of the embodiment includes (C) specifying a first single instruction multiple data (SIMD) register allocated to scalar data and further, satisfying a condition that a survival interval of the scalar data includes the survival interval of the first data to which any register is not allocated and (D) allocating to the first data the empty area of the specified first SIMD register.

A program for allowing the processor to perform the processing by the above-described method may be prepared and the program is stored in computer readable storage media or storage devices including, for example, a flexible disk, a CD-ROM, a magneto-optic disk, a semiconductor memory, a hard disk, and the like. Further, an intermediate processing result is temporarily kept in memory devices including a main memory, and the like.