JPH04199428A - Register device and register allocating method - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION Field of Industrial Application The present invention relates to a register device having a plurality of general-purpose registers and applied to a data processing device such as a microprocessor;
The present invention relates to a register allocation method for allocating each variable in a program to a register when compiling a program to be executed by a data processing device to which this register device is applied.

BACKGROUND OF THE INVENTION Conventional register devices include, for example, Morishita Genshu, "Microcomputer Hardware J, pp. 44-4.
The one shown in No. 5 is known.

FIG. 4 is a block diagram showing the configuration of the main parts of a data processing device to which this type of register device is applied, in which 110 is a general-purpose register group (GR), 110a, 110b, . . . are registers, and 120 is an arithmetic logic Arithmetic unit (ALU), 12
1 to 123 are latch circuits, and 131 to 133 are buses.

The registers 110a... each have two output ports connected to the bus 131 or the bus 132,
Data can be simultaneously output from two of the registers 110a to the bus 131 and the bus 132.

In such a data processing device, for example, the register 110
When the arithmetic and logic unit 120 performs an operation on the data stored in the a/110b, the following operation is performed.

First, two pieces of data are simultaneously output from the registers 110a and 110b and held in the launch circuits 121 and 122 via buses 131 and 132, respectively. Latch circuit 1
The data held in 21 and 122 is the arithmetic and logic operation bag W1.
20 and stored in the launch circuit 123. The data stored in the latch circuit 123 is stored in any one of the registers 110a . . . via the bus 133.

That is, by outputting two pieces of data to the buses 131 and 132 at the same time, the calculation speed can be improved.

Problems to be Solved by the Invention However, in the conventional register device described above, although it is possible to improve the calculation speed, each register 110a
..., in more detail, all memory cells of each register 110a are connected to bus 131 or bus 132.
The problem is that the circuit configuration is complicated because it has two output ports.

In particular, this type of device is often implemented as an LSI, which requires a large chip area and increases manufacturing costs.

SUMMARY OF THE INVENTION In view of the above, an object of the present invention is to provide a register device and a register allocation method that have a simple circuit configuration and are capable of improving calculation speed.

Means for Solving the Problems In order to achieve the above object, the invention as set forth in claim 1:
When outputting data from multiple registers grouped into multiple register groups and multiple registers included in different register groups, output data from each register at the same time, while outputting data from multiple registers included in the same register group. In the case of outputting data from a plurality of registers, the present invention includes register control means for sequentially outputting data to each register, and switching means for outputting each data output from the register group to a predetermined bus, respectively. It is a feature.

Further, the invention according to claim 2 provides a register for allocating each variable and/or intermediate result of an operation in a program executed by a data processing device equipped with the register device according to claim 1 to each of the registers. The allocation method includes the step of allocating each variable and/or the intermediate result of the operation to a virtual register on the infinite side of a first virtual register group, and the step of allocating each of the virtual registers to a data Regarding the step of allocating the same number of virtual registers as the number of real registers of the processing device, and the plurality of correspondence relationships of allocating each virtual register of the second virtual register group to the real register, registers included in the same register group Calculate the frequency of sequentially outputting data from multiple registers, and based on this calculation result,
and allocating each virtual register of the second virtual register group to a real register.

According to the invention described in claim 1, when the register control means outputs data from a plurality of registers included in mutually different register groups, the register control means causes each register to output data at the same time, while outputting data from the same register group. When outputting data from a plurality of registers included in a register group, each register is outputted sequentially. The switching means outputs each data output from the register group to a predetermined bus.

According to the invention described in claim 2, each variable and/or intermediate result of an operation in a program is first allocated to an infinite number of virtual registers in a first virtual register group, and this virtual register is allocated to an infinite number of virtual registers in a first virtual register group. The number of virtual registers is the same as the number of real registers in the virtual register group.

Furthermore, for the virtual registers of the second virtual register group, the frequency of sequentially outputting data from multiple registers included in the same register group is calculated for multiple correspondence relationships assigned to real registers, and based on this calculation result. and allocated to real registers.

Embodiment FIG. 1 is a block diagram showing the configuration of the main parts of a data processing device to which a register device is applied.

In FIG. 1, 11 indicates eight registers lla and llb.
The first general-purpose register group (GRi
), 12 is a second general-purpose register group (GR2) comprising eight registers 12a, 12b, . . . , 20 is an arithmetic logic unit (ALU), 21 to 23 are latch circuits,
31 to 33 are buses, 40 is a register control means, 311.
321 is a selector.

Each register ll in the first general-purpose register group 11
a... each has one port connected to the selectors 311 and 312, and data is output from any one register to the selector 311 in response to a clock signal (not shown). There is.

Furthermore, each register 1 in the second general-purpose register group 12
Similarly, 2a... each has one port connected to the selector 312, and data is outputted from one of the registers to the selectors 311 and 312 in response to a clock signal. There is.

The selector 311 selectively outputs the data output from the general-purpose register groups 11 and 12 to the bus 31, while the selector 312 selectively outputs the data output from the general-purpose register groups 11 and 12 to the bus 32. It is designed to be output.

The register control means 40 selects one register from the general-purpose register group 11 and one register from the general-purpose register group 12 based on register designation signals 1 and 2 output from an arithmetic control device (not shown). When data is outputted, each register is outputted simultaneously, and selectors 311 and 312 are switched to output each data to bus 31 or bus 32.

The register control means 40 also controls the general-purpose register group 11.
When data is output from two registers included in one of the registers 12, the data is output from each register sequentially, and the selectors 311 and 312 are sequentially switched to send one data to the bus 31 and the other data to the bus 32. It is designed to output to .

The latch circuits 21 and 22 hold data sent via buses 31 and 32, respectively, and the arithmetic and logic unit 20 performs operations on the held data. In addition, the latch circuit 23 holds the calculation result and
It is designed to output to 3.

In the above configuration, for example, when calculating data stored in register Ila of general-purpose register group 11 and data stored in register lla of general-purpose register group 12, and register lla of the same general-purpose register group 11, - When calculating data stored in 11b, the following operations are performed.

First, the register control means 40 receives the register designation signal l.
When registers lla and 12a are specified by 2, it is detected that these registers lla and 12a are distributed in mutually different general-purpose register groups 11 and 12, and output instructions are given to each general-purpose register group 11 and 12. Output signals simultaneously.

It also outputs a selection signal that causes the selector 311 to select the general-purpose register group 11 and a selection signal that causes the selector 312 to select the general-purpose register group 12.

Therefore, the data stored in the registers lla and 12a are outputted from the general-purpose register groups 11 and 12 in the same one clock cycle, and sent to the latch circuits 21 and 22 via the selectors 311 and 312 and the buses 31 and 32. is maintained.

After the data held in the latch circuits 21 and 22 is operated on by the arithmetic and logic unit 20, it is held in the latch circuit 23, and then passed through the bus 33 to the registers 11a...12a...
・It is stored in one of the following.

On the other hand, when registers lla and llb of one general-purpose register group 11 are specified by register designation signals 1 and 2, the register control means 40 determines whether these registers lla and llb are included in the same general-purpose register group 11. It detects that the register lla is set and outputs an output instruction signal to the register lla to the general-purpose register group 11, and
A selection signal that causes the selector 311 to select the general-purpose register group 11 is output. Further, the register control means 40 outputs a conflict signal to the arithmetic control unit to request a temporary stop of the operation of the arithmetic and logic unit 20 and the like.

Therefore, the data stored in register lla is outputted from general-purpose register group 11 in the first clock cycle, and sent to latch circuit 21 via selector 311 and bus 31.
is maintained.

Next, the register control means 40 outputs an output instruction signal for register llb to the general-purpose register group 11, and also outputs a selection signal for causing the selector 312 to select the general-purpose register group 11. It also resets the conflict signal.

Therefore, the data stored in the register Ilb is output from the general-purpose register group 1 at the second clock cycle, and sent to the latch circuit 22 via the selector 312 and the bus 32.
is maintained. The data stored in the latch circuits 21 and 22 is then operated on by the arithmetic and logic unit 20, held in the latch circuit 23, and transferred to the register lla via the bus 33.
. . 12a . . .

A similar operation is also performed when the two registers specified by the register designation signals 1 and 2 are both included in the general-purpose register group 12.

In other words, when the registers to be operated on are distributed among the general-purpose register groups 11 and 12, the arithmetic processing is performed in one clock cycle, and the same general-purpose register group 11 and
12, it takes two clock cycles, but the arithmetic processing is performed properly.

Here, as described above, the less frequently each register that is the target of an operation is included in the same general-purpose register group 11, 12, the faster the operation process will be performed.

Therefore, for example, when compiling a program written in a high-level language into a target program to be executed on the data processing device mentioned above, the variables and intermediate results of operations in the program are assigned to each register as follows. It is possible to reliably speed up the processing.

FIG. 2 is a block diagram showing the configuration of the register allocation device.

In FIG. 2, 51 is a program input device, 52 is a processing device that allocates registers and generates a target program, and 53 is an output device that outputs the generated target program.

The processing device 52 may have the same configuration as the data processing device on which the generated target program is executed, or may have a different configuration.

Further, the output device 53 may be one that outputs the generated target program to a storage device or the like, or may be one that directly inputs the target program to a data processing device that executes the target program to start execution.

The register allocation processing operation performed by the processing device 52 will be explained below based on the flowchart shown in FIG.

Here, among the eight registers each in the general-purpose register groups 11 and 12 of the data processing device that executes the target program, one register is used as a so-called stack pointer or frame pointer, and the remaining seven registers are used as a so-called stack pointer or frame pointer. Assume that variables in the program are assigned to each register.

First, a program written in a high-level language is defined as a data processing device 0 purpose program format and an I! (Translate into intermediate code having the following format (Sl). At this time, the values of variables in the program and intermediate results of calculations are allocated to the first group of virtual registers, but to simplify the process, The first group of virtual registers is allocated on the assumption that an infinite number of them can be used.

Next, the first group of virtual registers in the intermediate code are allocated to the 14 second group of virtual registers, and the intermediate code is changed (S2).

The register allocation process performed in S2 above is, for example, rRegister by G. J. Chaitin et al.
A11ocation and Spilling v
ia Graph Coloring J (Pro
ceedings of the 5IGPLAN S
ymposium on ColIpilerCons
truction+ pp, 98-105. June
This can be done by applying the method shown in (1982). In other words, by applying graph theory to solve the problem of ``coloring all virtual registers in use with 14 or fewer colors so that registers that hold different data at the same time do not have the same color,'' be exposed.

Note that the details of this method are described in detail in the above-mentioned reference literature, so the explanation will be omitted here.

However, in the above method, the first group of virtual registers in the intermediate code is allocated to real registers, whereas
In S2, the second group of 14 virtual registers, which is the same number as the real registers, is allocated.

This means that in a register device where each register has multiple output ports and can output data from multiple registers simultaneously, as long as virtual registers holding different data at the same time are not allocated to the same real register, The arithmetic processing speed is the same no matter which real register is assigned, but when using a register device in which registers are grouped as described above, the assignment is made to the second group of virtual registers in S2, as shown below. In S3 and S4, processing is performed to allocate real registers so that registers to be simultaneously operated on do not belong to the same group as much as possible.

That is, in S3, if the number of virtual registers in the second group is 14 as described above and the number of real registers in general-purpose register groups 11 and 12 is 7 each, each virtual register is assigned to any general-purpose register group. Since there are 14C7''=3400 combinations of correspondence relationships that can be allocated to registers, the frequency with which registers that are simultaneously subject to operations during program execution belong to the same group is calculated for all of the combinations.

This calculation process is quite possible considering the processing power of recent data processing devices, but if there are many actual registers, for example, [using two colors and using the same command] It is also possible to reduce the amount of calculation by using the above-mentioned graph theory method to solve the problem J in which the registers used in J are painted with different colors.

If the intermediate code includes processing that forms a loop, calculating the frequency by multiplying the above frequency by a weighting factor will more reliably improve the calculation speed. You can improve your performance.

Next, in S4, the virtual registers of the second group are allocated to real registers according to the correspondence relationship that minimizes the calculated frequency, and a target program is generated.

As described above, even if the number of output ports for each register is reduced, if the referenced registers are distributed among each group,
Since the number of registers that can be referenced simultaneously does not actually decrease,
In addition to improving the calculation speed, it is possible to simplify the circuit configuration.

In particular, by performing register allocation processing such that the frequency of simultaneous reference to multiple registers in the same group is reduced, the above calculation speed can be reliably improved.

As described in detail, according to the invention described in claim 1,
By providing a plurality of registers grouped into a plurality of register groups and a register control means that causes each register to simultaneously output data when data is output from a plurality of registers included in mutually different register groups, Data can be output from multiple registers to multiple buses at the same time without providing multiple ports for each register, resulting in a simple circuit configuration and the ability to improve calculation speed. .

Further, according to the invention described in claim 2, data is sequentially output from a plurality of registers included in the same register group regarding a plurality of correspondence relationships in which each variable and/or an intermediate result of an operation is assigned to a register. Since the frequency is calculated and the registers are allocated based on the calculation result, it is possible to reliably improve the calculation speed.

[Brief explanation of the drawing]

Fig. 1 is a block diagram showing the configuration of the main parts of a data processing device to which a register device is applied, Fig. 2 is a block diagram showing the configuration of a register allocation device, and Fig. 3 is a register allocation processing operation performed in the processing device. A flowchart showing
FIG. 4 is a block diagram showing the configuration of main parts of a data processing device to which a conventional register device is applied. 11・12...General-purpose register group, lla, llb, 1
2a, 12b...Register, 40...Register control means, 52...Processing device, 311, 312...Selector agent Patent attorney Shiro Nakajima Figure 3 Figure 4 Figure 1.32

Claims (2)

[Claims] (1) When outputting data from multiple registers grouped into multiple register groups and multiple registers included in different register groups, output data from each register at the same time, while outputting data from the same register group. In the case of outputting data from a plurality of registers included in the register, the register control means includes register control means for outputting data sequentially to each register, and switching means for outputting each data output from the register group to a predetermined bus, respectively. A register device characterized by: (2) A register allocation method for allocating each variable and/or intermediate result of an operation in a program executed by a data processing device equipped with the register device according to claim 1 to each of the registers, the method comprising: and/or allocating intermediate results of the operation to an infinite number of virtual registers of the first virtual register group, each virtual register being equal to the number of real registers of the data processing device constituting the second virtual register group. The step of allocating the virtual registers to a number of virtual registers, and the plurality of correspondence relationships of allocating each virtual register of the second virtual register group to the real register, sequentially outputting data from a plurality of registers included in the same register group. A register allocation method comprising the steps of calculating the frequency and allocating each virtual register of the second virtual register group to a real register based on the calculation result.