CN102360280A - Method for allocating registers for mixed length instruction set - Google Patents

Abstract

The invention discloses a method for allocating registers for a mixed length instruction set. By less revising the conventional graph coloring register allocation method, namely fully utilizing the characteristics of a mixed coding instruction set, codes with higher code density are generated. The method has the characteristics of simplicity, practicability and high in reliability.

Description

A Register Allocation Method for Mixed-Length Instruction Sets

technical field

The invention relates to a compiling technology, in particular to a register allocation method for mixed-length instruction sets.

Background technique

Embedded systems often adopt RISC architecture, and their instruction sets are generally fixed-length instruction sets, that is, instructions with only a single length. The instruction length is generally an integer number of bytes, for example, a 16-bit instruction and a 32-bit instruction. A longer instruction length can encode more operands, address more registers, or use a larger immediate value, etc., so it generally has better performance; while a shorter instruction length can make the compiled generated Executors are smaller. In order to have high code density of short instructions while having high performance of long instructions, modern RISC processors begin to use two or more instruction sets with mixed codes of different lengths. For example, ARM's thumb2 instruction set and Zhongtian Micro's cskyv2 instruction set are both 16-bit and 32-bit instruction mixed-coded instruction sets (hereinafter referred to as "mixed-coded instruction sets").

In the mixed instruction set, compared with long instructions, short instructions have fewer addressable operands, a smaller range of immediate values that can be encoded, or only part of registers can be used for a single address. For example, in the cskyv2 instruction set, long instructions can use all 32 general-purpose registers R0~R31, while most short instructions can only use 16 general-purpose registers R0~R15; long instructions generally have 3 operands, while short instructions There are at most only 2 operands. Short instructions are functionally a subset of long instructions. Usually, the compiler generates assembly instructions according to the function of long instructions, and when the assembler generates machine instructions, it will decide whether to generate long instructions or short instructions according to the type of the instruction and its operands.

Taking cskyv2 as an example, if a register operand of an instruction is assigned a register of R16~R31, then the instruction will generate a long instruction (except for individual instructions, which will be introduced below); but even if an instruction only uses R0~ The register of R15, it does not necessarily generate short instructions, because it may use immediate values beyond the encoding range of short instructions, or use 3 different operands, etc. Taking cskyv2 as an example, if a register operand of an instruction is assigned a register of R16~R31, then the instruction will generate a long instruction (except for individual instructions, which will be introduced below); but even if an instruction only uses R0~ The register of R15, it does not necessarily generate a short instruction, because it may use an immediate value beyond the encoding range of a short instruction, or use 3 different operands, and so on. If an instruction finally generates a machine instruction, whether it is a long instruction or a short instruction depends on the register it is assigned to (hereinafter referred to as a type A instruction); conversely, if it does not matter which register its register operand is assigned to, it must generate a long instruction, or A short instruction (hereinafter referred to as B type instruction) is bound to be generated. How to make the final machine instructions generated by all class A instructions into short instructions at a relatively low cost is a difficulty that technicians need to overcome.

Contents of the invention

In view of the above-mentioned technical difficulties, the present invention proposes a register allocation method for mixed-length instruction sets.

In order to solve the problems of the technologies described above, the technical solution of the present invention is as follows:

A register allocation method for a mixed-length instruction set, comprising the steps of:

1) Find all life cycles in the function, and judge whether the life cycle is a type A life cycle or a B type life cycle by setting whether the flag bit is set;

2) Execute the five processes of Renumber ₁ , build ₁ , coalesce ₁ , spill cost ₁ , and simplify ₁ of the graph coloring register allocation method, allocate lo-regs registers for all class A lifetimes, and obtain a conflict graph without any overflow operation G ₁ ;

3) Calculate the number m of free lo-regs registers, if the conflict graph G ₁ is not empty, then the number m of free lo-regs registers is 0, if the conflict graph G ₁ is empty, execute the graph coloring register allocation method select ₁ process, and calculate the number m of free lo-regs registers according to the generated register allocation scheme, and record the free register information;

4) Execute the Renumber ₂ , build ₂ , coalesce ₂ , simplify ₂ , spill code ₂ and select ₂ processes of the graph coloring register allocation method, allocate hi-regs registers and m free lo-regs registers for the lifetime of class B, and Calculate the number n of free hi-regs registers according to the generated allocation scheme, and record the free register information;

5) Execute the spill code ₁ and select ₁ process of the graph coloring register allocation method, if the select ₁ process is already in

Step 3) Execute, then the step ends, if not, repeat the process of spill code ₁ , Renumber ₁ , build ₁ , coalesce ₁ , spill cost ₁ , simplify ₁ until the conflict graph G ₁ is empty, and then execute the process of select ₁ as Class A lifetime generation register allocation scheme;

Renumber ₁ , build ₁ , coalesce ₁ , spill cost ₁ , simplify ₁ , spill code ₁ , select ₁ , Renumber _{2 ,} build ₂ , coalesce ₂ , spill cost 2 , simplify ₂ , spill code ₂ and select ₂ processes are graph coloring the steps of the register allocation method;

The graph coloring register allocation method includes the following steps:

11) Renumber: On the basis of data flow analysis, find all the lifetimes in the function and assign them unique numbers. One of the lifetimes begins with a fixed value of a variable and ends with the last use of the value ;

12) build: build a conflict graph G, the nodes in the conflict graph G are life periods, and the edges indicate that the two life periods connected through it have conflicts, and the same register cannot be allocated to them;

13) coalesce: determine whether to merge the life cycle, if necessary, delete unnecessary copy statements through the merge life cycle, return after the merge, and re-execute step 12), if no merge, execute step 14);

14) spill cost: calculate the overflow cost of each lifetime;

15) simplify: Simplify the conflict graph G, check the graph G repeatedly, delete nodes in G whose degree is less than the number of available registers k, and push the node into the stack s while deleting;

16) Spill code: When the degree of all nodes in the conflict graph G is greater than or equal to k, it is necessary to overflow the lifetime with the least overflow cost, that is, delete its node, push it into the stack s, and mark it as overflow , return to step 11 after overflowing a lifetime);

17) select: when the conflict graph G is empty, pop the lifetime in the stack s, allocate registers for it, and insert overflow code for the lifetime marked as overflow;

The lo-regs register is a register addressable by short instructions, and the rest is the hi-regs register. The standard for whether the flag is set is: set the lifetime referenced by a class A instruction to be set , set the lifetime referenced only by class B instructions to not set;

The class A instruction is a machine instruction finally generated by an instruction, whether it is a long instruction or a short instruction depends on the register to which it is allocated;

The type B instruction is that no matter which register its register operand is allocated to, it must generate a long instruction, or it must generate a short instruction.

Further, the flag is set in a structure that records lifetime information.

Further, the process of spill code ₁ in step 5) includes the following steps:

31) Save a backup conflict graph G ₁ -backup of the conflict graph G ₁ when constructing the conflict graph G ₁ ;

32) Every time simplify ₁ decides to overflow a certain lifetime l, first judge whether there are free hi-regs registers that can be used for overflow, if so, then insert a move instruction after each assignment of l and before use, and record the lifetime period l overflows to the information of the hi-regs register; and when each hi-regs register has an associated overflow lifetime, judge whether all overflow lifetimes associated with the register are judged according to the backup conflict graph G ₁ -backup Does not conflict with the current lifetime l to be spilled. If there is such a register, it can be used for the overflow of l. If there are no free hi-regs for overflow, then spill code ₁ uses the load/store instruction to overflow the lifetime to memory.

The beneficial effects of the present invention are: applicable to instruction sets having two or more instructions with different lengths, and wherein the set of registers accessible by shorter instructions is a subset of the set of registers accessible by longer instructions, the present invention can improve The instruction density of the generated code is simple and practical, and the reliability is strong. Finally, at a relatively small cost, all the machine instructions generated by the class A instructions are short instructions.

Description of drawings

Figure 1 is the basic flowchart of the graph coloring register allocation method;

Fig. 2 is the concrete implementation flowchart of the present invention;

Figure 3 is a flow chart of the marker lifetime type;

Figure 4 is a flowchart of spill code ₁ ;

Figure 5 is a partial diagram of the backup conflict graph.

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings and specific embodiments.

The present invention is an improved register allocation method based on the graph coloring register allocation method. Graph coloring is a traditional and most commonly used register allocation method. Its basic flow is shown in Figure 1. A brief description of each stage is as follows:

Rename (Renumber): Before this stage, the intermediate code can refer to an unlimited number of "virtual registers". In this stage, based on data flow analysis, find all lifetimes in the function and assign unique numbers to them. A lifetime begins with one setting of a variable and ends with the last use of that value.

Construct conflict graph (Build): At this stage, a "conflict graph G" is established. The nodes in G are life cycles, and the edges indicate that there is a conflict between the two life cycles connected through it, that is, they are active at a certain instruction at the same time, so They cannot be allocated the same register.

 Coalesce: In this phase, unnecessary replication statements are deleted by merging the lifespan. The merge lifetime changes the conflict graph, so the "Build" process needs to be rerun after the merge.

Spill cost analysis (Spill cost): This stage is used to calculate the spill cost of each lifetime.

Simplify the conflict graph (Simplify): In this stage, the conflict graph G is simplified, the graph G is checked repeatedly, and the node in G whose degree is less than the number of available registers k is deleted, and the node is pushed into the stack s while deleting.

Insert Spill code: When the degree of all nodes in graph G is greater than or equal to k, the "Simplify" process cannot continue. At this time, it is necessary to overflow the lifetime with the least overflow cost, that is, delete its node, push it into the stack s, and mark it as overflow. Execution of the graph coloring algorithm needs to be restarted from the "rename" phase after overflowing a lifetime.

Coloring (Select): The graph G will eventually be reduced to an empty graph. At this time, the lifetime in the stack s is popped, registers are allocated for it, and overflow code is inserted for the lifetime marked as overflow.

First classify the registers, most of the registers addressable by short instructions are called lo-regs, and the rest are called hi-regs. Then add a flag bit for each lifetime to mark whether it has been referenced by a class A instruction, and call the lifetime referenced by only the B class instruction "B class lifetime"; and the lifetime referenced by the A class instruction is called for "class A lifetimes" and sets that flag for each lifetime by scanning the entire function's instruction stream.

Then execute two graph coloring processes, allocate lo-regs for class A lifetime, and assign hi-regs for class B lifetime; if lo-regs and hi-regs are enough for class A lifetime and class B lifetime respectively, or The registers of the two graph coloring processes are insufficient, and both need to overflow the lifetime, so the two graph coloring processes are carried out independently. If lo-regs are enough for class A lifetime allocation and there is free time, but hi-regs are not enough for class B lifetime allocation, then the free registers in lo-regs and hi-regs registers are allocated to class B lifetime. Conversely, if hi-regs are free and lo-regs are insufficient, then when overflow code is generated during lo-regs allocation, the life cycle will be overflowed to free hi-regs first, and only when there are no hi-regs registers to overflow overflow to memory.

The specific implementation process of this method is shown in Figure 2, and the specific steps are as follows:

1. Life cycle mark. This phase finds all lifetimes in the function; and marks the type of each lifetime by scanning all instructions of the current function.

Two, Renumber ₁ , build ₁ , coalesce ₁ , spill cost ₁ , and simplify ₁ . This step executes the first five stages in the graph coloring algorithm flow, and allocates lo-regs registers for all class A lifetimes. After this step is executed, a conflict graph G ₁ without any overflow operation will be obtained.

3. Calculate the number of free lo-regs registers. This step calculates the number m of free lo-regs registers, if G ₁ is not empty, then m is 0; otherwise, if G ₁ is an empty graph, then we execute the select ₁ process, and calculate the free lo-regs according to the generated register allocation scheme -regs register number, and record free register information.

Four, Renumber ₂ , build ₂ , coalesce ₂ , spill cost ₂ , simplify ₂ , spill code ₂ and select ₂ . This step is a complete traditional graph coloring register allocation process. We use this procedure to allocate hi-regs and m free lo-regs for class B lifetimes. And calculate the number n of free hi-regs registers according to the generated allocation scheme, and record the free register information.

Five, spill code ₁ and select ₁ . If G ₁ is empty, then select ₁ has been executed in step 3, and the entire algorithm ends; otherwise, repeat the process of spill code ₁ , Renumber ₁ , build ₁ , coalesce ₁ , spill cost ₁ , and simplify ₁ until G ₁ is empty , and then select ₁ to generate a register allocation scheme for the lifetime of class A. The special feature of this step is that if n>0, then when executing spill code ₁ , we first overflow the lifetime to the free hi-regs register, and only when no hi-regs register is available, the lifetime overflow to memory. The advantage of this is that code generated using move instructions that spill lifetimes into free hi-regs generally executes faster than code generated using load/store execution that spills lifetimes into memory.

In addition, mixed instruction sets usually provide a special short instruction-move, which is a short instruction, but can address all registers. At this point, the code generated using move instructions to spill lifetimes into free hi-regs registers will be more efficient than spilling to memory (using short instructions for spilling, rather than the usual long instructions).

The method only needs a small amount of modification on the traditional graph coloring register allocation method, can make full use of the characteristics of the mixed instruction set, generate codes with higher code density, and has the characteristics of simplicity, practicability and strong reliability.

The following is a more detailed description combined with specific examples:

First, add a flag bit flag_short to the structure that records lifetime information. If the flag is set, it means that the lifetime is a type A lifetime, otherwise it is a type B lifetime. After the "life cycle identification" process ends, add a "mark life cycle type" process, as shown in Figure 3. This process sets the flag_short flag for each lifetime by sequentially scanning each instruction in the current function.

Then, two graph coloring processes need to be performed. Among them, select ₁ allocates lo-regs registers for all class A lifetimes; select ₂ allocates hi-regs registers and possible free lo-regs registers for all class B lifetimes. And select ₂ may be executed after the completion of select ₁ , or it may be executed after the first simplified conflict graph G ₁ process of select 1, as shown in Figure 2. It depends on whether the lo-regs are enough for class A lifetime allocation. If it is enough, then select ₁ is executed first, so that the remaining free lo-regs can be provided to select ₂ for allocation; otherwise, select ₁ is executed for the first time After the simplify ₁ process, execute the entire select ₂ process, so that if the select ₂ process has free hi-regs, they can be used for the insert spill code ₁ stage of select ₁ . In short, we used two graph coloring processes, select ₁ and select ₂ , in which select ₁ allocates lo-regs registers for all lifetimes where flag_short is true; select ₂ allocates hi-regs registers and possibly for all lifetimes where flag_short is false Free lo-regs registers. During these two graph coloring processes, the present invention only needs to add a judgment to the flag_short sign of the life cycle in the traditional graph coloring algorithm, so that select ₁ and select ₂ process the life cycle when flag_short is true and false respectively, and simply Just reorganize the execution process of select ₁ and select ₂ .

Finally, the present invention can also modify the overflow process of the traditional graph coloring algorithm to insert spill code ₁ , the flow of which is shown in FIG. 4 . First of all, when executing the process of constructing the conflict graph G ₁ , it is necessary to save a backup conflict graph G ₁ -backup; then each time the simplified conflict graph G ₁ decides to overflow a certain lifetime l, it is first judged whether there is a free hi- regs can be used for overflow, if there is, then insert move instructions after each assignment of l and before use, and record the information of lifetime l overflow to hi-regs. It should be noted that when each hi-regs has an associated overflow lifetime, it does not mean that no hi-regs can be used for overflow; at this time, it is necessary to judge whether there is a certain register according to G ₁ -backup, and its None of the associated overflow lifetimes conflict with the lifetime l currently being overflowed, and if there is such a register, then it can be used for the overflow of l. If there are no free hi-regs for overflow, then spill code ₁ performs the same process as the traditional graph coloring algorithm, that is, uses the load/store instruction to spill the lifetime to memory.

The following is an example of overflowing to registers. First, the G ₁ -backup that is backed up after the execution of the construction conflict graph G ₁ is completed, as shown in the figure below (to simplify the description, only 4 lifetimes are included in the schematic diagram, which can be considered as conflicts A small part of the figure):

Assume that there are two free hi-regs registers R1, R2 can be used for overflow, and now overflow lifetime 3 is required, and the usage of hi-regs by the previous overflow operation is as follows:

hi-regs register overflowed lifetime R1 1 R2 2

 hi-regs寄存器溢出情况记录 surface

hi-regs register overflow record

As shown in Flowchart 4, first obtain the first hi-regs register R1 that can be used for overflow, and according to the above table, lifetime 1 has overflowed to R1, and lifetime 3 is currently overflowing, according to the backup conflict graph G ₁ -backup, it can be seen that life periods 1 and 3 conflict, so R1 cannot be used to overflow life period 3. Next, get the second hi-regs register R2 that can be used for overflow. According to G ₁ -backup, there is no conflict between life periods 2 and 3, which means that life period 2 is no longer used during the active period of life period 3. Therefore, lifetime 3 can be overflowed to R2, and the information can be filled in Table 1, and a move instruction can be inserted where lifetime 2 is needed to copy its value from R2 to the corresponding lo-regs register, and move can be inserted after use The instruction copies its value from the corresponding lo-regs register to R2.

The above is only a preferred embodiment of the present invention, it should be pointed out that for those of ordinary skill in the art, without departing from the concept of the present invention, some improvements and modifications can also be made, and these improvements and modifications should also be considered Within the protection scope of the present invention.

Claims (3)

1. A register allocation method for a mixed-length instruction set, characterized in that, comprising the steps: 1) Find all the life cycles in the function, and determine whether the life cycle is a type A life cycle or a B type life cycle by setting whether the flag bit is set; 2) Execute the five processes of Renumber ₁ , build ₁ , coalesce ₁ , spill cost ₁ , and simplify ₁ of the graph coloring register allocation method, allocate lo-regs registers for all class A lifetimes, and obtain a conflict graph without any overflow operation G ₁ ; 3) Calculate the number m of free lo-regs registers, if the conflict graph G ₁ is not empty, then the number m of free lo-regs registers is 0, if the conflict graph G ₁ is an empty graph, execute the graph coloring register allocation method select ₁ process, and calculate the number m of free lo-regs registers according to the generated register allocation scheme, and record the free register information; 4) Execute the process of Renumber ₂ , build ₂ , coalesce ₂ , simplify ₂ , spill code ₂ and select ₂ of the graph coloring register allocation method, allocate hi-regs registers and m free lo-regs registers for the lifetime of class B, and Calculate the number n of free hi-regs registers according to the generated allocation scheme, and record the free register information; 5) Execute the process of spill code ₁ and select ₁ of the graph coloring register allocation method, if the process of select ₁ has been executed in step 3), then end all steps, if not, repeat the execution of spill code ₁ , Renumber ₁ , build ₁ , coalesce ₁ , spill cost ₁ , simplify ₁ process until the conflict graph G ₁ is empty, and then execute the select ₁ process to generate a register allocation scheme for the lifetime of class A; Renumber ₁ , build ₁ , coalesce ₁ , spill cost ₁ , simplify ₁ , spill code ₁ , select ₁ , Renumber ₂ , _{build 2} , coalesce ₂ , spill cost 2 , simplify ₂ , spill code ₂ and select ₂ processes are graph coloring the steps of the register allocation method; The graph coloring register allocation method includes the following steps: 11) Renumber: On the basis of data flow analysis, find all the lifetimes in the function and assign them unique numbers. One of the lifetimes begins with a fixed value of a variable and ends with the last use of the value ; 12) build: build a conflict graph G, the nodes in the conflict graph G are life periods, and the edges indicate that the two life periods connected through it have conflicts, and the same register cannot be allocated to them; 13) coalesce: determine whether to merge the life cycle, if necessary, delete unnecessary copy statements through the merge life cycle, return after the merge, and re-execute step 12), if no merge, execute step 14); 14) spill cost: calculate the overflow cost of each lifetime; 15) simplify: Simplify the conflict graph G, check the graph G repeatedly, delete nodes in G whose degree is less than the number of available registers k, and push the node into the stack s while deleting; 16) Spill code: When the degree of all nodes in the conflict graph G is greater than or equal to k, it is necessary to overflow the lifetime with the least overflow cost, that is, delete its node, push it into the stack s, and mark it as overflow , return to step 11 after overflowing a lifetime); 17) select: when the conflict graph G is empty, pop the lifetime in the stack s, allocate registers for it, and insert overflow code for the lifetime marked as overflow; The lo-regs register is a register addressable by short instructions, and the rest is the hi-regs register. The standard for whether the flag is set is: set the lifetime referenced by a class A instruction to be set , set the lifetime referenced only by class B instructions to not set; The type A instruction is a machine instruction finally generated by an instruction, whether it is a long instruction or a short instruction depends on the register to which it is allocated; The type B instruction is that no matter which register its register operand is allocated to, it must generate a long instruction, or it must generate a short instruction. 2. A register allocation method for mixed-length instruction sets according to claim 1, wherein the flag bit is set in a structure that records lifetime information. 3. A register allocation method for mixed-length instruction sets according to claim 1, characterized in that the process of spill code ₁ in step 5) includes the following steps: 31) Save a backup conflict graph G ₁ -backup of the conflict graph G ₁ when constructing the conflict graph G ₁ ; 32) Every time simplify ₁ decides to overflow a certain lifetime l, first judge whether there are free hi-regs registers that can be used for overflow, if so, then insert a move instruction after each assignment of l and before use, and record the lifetime period l overflows to the information of the hi-regs register; and when each hi-regs register has an associated overflow lifetime, judge whether all overflow lifetimes associated with the register are judged according to the backup conflict graph G ₁ -backup Does not conflict with the current lifetime l to be spilled. If there is such a register, it can be used for the overflow of l. If there are no free hi-regs for overflow, then spill code ₁ uses the load/store instruction to overflow the lifetime to memory.

Images