KR100970758B1 - Apparatus and method of generating code optimized with compound instruction by eliminating nullified compound instruction - Google Patents

Abstract

The present invention relates to an apparatus for generating a code for a compound instruction and a method for generating the code, the method comprising: an instruction selecting unit for selecting an appropriate compound instruction candidate from a candidate interference graph composed of a compound instruction candidate extracted from an intermediate expression tree; A register allocator configured to generate a code to which a register is allocated by allocating and merging registers to be used for the composite command candidate selected by the command selector; A valueless compound instruction detector for detecting a valueless compound instruction including a valueless move instruction in a code allocated to the register; And a final code generator for discharging the code allocated to the register as a final code if the valueless compound instruction is not detected, wherein the valueless compound instruction removes the selected compound instruction candidate when the valueless compound instruction is detected. And a command generation unit for instructing the command selection unit to select a new compound command candidate and a method of generating the code.

Description

Apparatus and Method of Generating Code optimized with Compound Instruction by eliminating Nullified Compound Instruction}

The present invention relates to a code generation device for optimizing a code by removing a valueless compound instruction when selecting a compound instruction, and a method of generating the code. It relates to a code generating device that repeatedly performs a step and register allocation (including register merging) of the register allocation unit and a method of generating the code. [Task control number: 10030565, Task name: MPSoC design technology development]

In general, a processor executes a program by loading data stored in a memory into a register. In order to execute a program, program (symbol) variables must be assigned to a register embedded in the processor. This step is performed by a compiler that converts the source code into object code. Code generation by the compiler is divided into instruction selection and register allocation phases, and the compiler uses an algorithm called a graph coloring algorithm in the register allocation phase.

Most embedded processors, such as digital signal processors (DSPs), use a small number of registers dedicated to the function block to increase performance. In such architectures, the value stored in a register as a result of one function block is often moved to another register for use as input to another function block. In the code generation process using the compiler, many copy-related commands (copy or move) are used. Because these replication-related instructions cause code performance degradation, optimization techniques such as register coalescing using graph coloring algorithms can improve the code performance generated by the compiler.

On the other hand, compound instructions for encoding operations or memory operations on various arithmetic and logic units (ALUs) within instruction words have been considered the most effective way of improving performance. Cores embedded in SOC have suffered severe design constraints in performance, energy and storage. At the same time, they need to be programmed to ensure reuse for other applications. To meet these design challenges, they are often implemented in the form of an application-specific instruction-set processor (ASIP).

Instructions in ASIP are generally compound instructions, such as add-mult and shift-move, each of which encodes one or more ALUs or memory operations. The main advantage of an embedded processor core is to reduce code size by putting multiple tasks into a single instruction. In addition, they are usually designed to perform internal tasks in sequence or in parallel during one machine cycle.

It is more efficient to execute one compound instruction because the additional sequencing overhead required for instructions with multicycle execution time can be reduced. Thus, when the compound instruction is fully utilized, execution time is reduced.

However, the advantage of such compound instructions is that they complicate the compiler's code generation. Although register merge is a useful optimization algorithm, it can have unexpected side effects, such as generating worthless compound instructions when applied to code with compound instructions.

The problem to be solved by the present invention, by considering the register merge used in the register allocation step when selecting a complex instruction, to prevent the generation of a valueless compound instruction, which is a valueless compound instruction to improve the quality of the final object code, a compound instruction To provide a code generating apparatus and a code generating method for.

In order to solve the above problems, the present invention, the command selection unit for selecting an appropriate compound instruction candidate from the candidate interference graph consisting of the compound instruction candidate extracted from the intermediate expression tree; A register allocator for allocating and merging registers to be used for the composite instruction candidate selected by the command selector to generate a code to which a register is assigned; A valueless compound instruction detector for detecting a valueless compound instruction including a valueless move instruction in a code allocated to the register; And a final code generator for discharging the code allocated to the register as a final code when the valueless compound instruction is not detected. The valueless compound instruction detector may detect the selected compound instruction candidate when the valueless compound instruction is detected. And a method for generating a code for a composite command and instructing the command selection unit to remove and instruct the command selection unit to select a new composite command candidate.

According to the present invention, by considering the register merge used in the register allocation step when selecting a complex instruction, it is possible to prevent the generation of a valuable complex instruction and improve the quality of the final object code.

Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings. Like reference numerals in the drawings denote like elements.

1 is a diagram illustrating a code generation apparatus for optimizing a code by removing a valueless compound instruction when selecting a compound instruction according to an embodiment of the present invention.

The code generating apparatus 100 according to the embodiment of the present invention includes an instruction selector 110, a register allocator 120, a null valued compound instrucion detector 130, and a final code generation. The unit 140 is included.

The code generating apparatus 100 according to the present invention is a kind of compiler that finally receives a source code as an input and finally generates a target code that can be understood by a machine. Tree parsing Null compound compound instruction, a valueless compound instruction that uses register coalescing, which is used in the register allocation step during compound instruction selction. This can improve the quality of the end code by preventing the occurrence of.

The instruction selector 110 selects instructions of a target processor having the same semantics as the source code written by the user.

The register allocator 120 generates a code including a complex instruction by allocating and merging registers used by the instructions selected by the instruction selector 110. The generated code generates a valueless complex instruction detector 130 and a final code. It is delivered to the unit 140.

In the register allocation algorithm, an interference graph (IG) is used to represent the live range of each operand as a node or a temporary variable. The interference graph shows the interference edge of the survival range of two temporary nodes. For example, the possibility of a node being colored in an interference graph means that its corresponding node or temporary variable can be assigned to any register, and that it is independent of the register assignment of its neighboring node. If the number of neighboring nodes is greater than the number of available colors (registers), then the node is said to have a high degree of degree, vice versa, and has a low degree, and only nodes of low degree can be easily colored. have.

In graph coloring, register merging means merging two nodes, each representing a source operand and a destination operand, in a move instruction into one new node, where the merged new node and adjacent edges are replaced by the replaced nodes and adjacent edges. Combine. After that, the register is allocated to the new node and the associated move command must be removed. As such, register merging helps the compiler remove many duplicate move instructions in code. However, even though register merge is a useful optimization algorithm, it can have unexpected side effects such as generating valueless compound instructions which will be described later when applied to code having compound instructions.

The valueless compound instruction detector 130 detects whether a valueless compound instruction has occurred in the code generated by the register allocator 120, and if the valueless compound instruction is not detected, the final code generator 140 discharges the final code. If a valueless compound command is detected, the command selection unit 110 is informed to select the command again.

The code generating apparatus 100 according to the present invention performs a step of selecting a command in the command selecting unit 110 and a step of allocating registers (including register merging) of the register allocating unit 120 until the NCI disappears. Perform iteratively.

FIG. 2 is a diagram illustrating the command selection unit of FIG. 1 in detail.

Referring to FIG. 2, the command selector 110 includes a compound command selector 111, a labeling unit 1120, and a covering unit 113.

The compound instruction candidate selector 111 first checks a node cluster that is a compound instruction candidate (CIC) in the intermediate representation (IR) tree.

The labeling unit 112 labels each node with simple rules in the intermediate expression tree, and the covering unit 113 generates a code covering the intermediate expression tree.

3 is a diagram illustrating a code generation device according to another exemplary embodiment of the present invention.

The code generation apparatus 300 according to another embodiment of the present invention may further include a code generator generation unit 200 in the code generator 100. The code generator 100 has the same configuration and function as the code generation apparatus 100 of FIGS. 1 to 3, and redundant description thereof will be omitted.

The code generator generation unit 200 automatically generates a code generator 100 and divides rules having no tree shape for a compound instruction into sub-rules having a tree shape. .

The code generator generator 200 includes a split rule extractor 210 and a code generator-generator 220.

The code generator generator 220 automatically generates the code generator 100 from a target processor description written in a tree grammar.

Since the nontree-shaped rule for the compound instruction cannot be applied directly to the tree parser, the splitting rule extractor 210 tree all rules without the tree shape for the compound instruction. Split into subrules with Here, a sub rule is defined as a split rule, a rule having no tree shape for a compound instruction is defined as a complex rule, and has a tree shape for a basic instruction or a compound instruction. Let's define a rule as a simple rule. An example rule is shown below.

(example)

rules  : r _One ( add ,One), r ₂ ( mov ,One), r ₃ ( sll ,One), r ₄ ( sll - add 1.5), r ₅ ( sll - mov , 1), r ₆ ( add - move ,One)

split rules  : r ₄₁ ( sll ), r ₄₂ ( add ), r ₅₁ ( sll ), r ₅₂ ( mov ), r ₆₁ ( add ), r ₆₂ ( mov )

In the above example, the r _i rule carries a tuple, which is a set of values arranged in order. The first element of the tuple represents the task, and the second element represents the associated cost of the task. For example, r ₆ consists of two parallel operations, add and mov, with a cost of 1.

In the above example, r ₁ and r ₂ and r ₃ are simple rules, while r ₄ and r ₅ and r ₆ are complex rules. r ₄ and r ₅ and r ₆ are divided into (r ₄₁ , r ₄₂ ), (r ₅₁ , r ₅₂ ) and (r ₆₁ , r ₆₂ ) respectively, and in the split rule extraction (SRE) The cost is not yet determined.

The code generator generation unit 200 stores all the rules including the division rules as the command selector 110 of the newly generated code generator 100. At this time, information is correctly grouped so that the division rules form a complex rule.

4 illustrates an intermediate representation tree and a compound instruction candidate.

The intermediate representation tree and compound instruction candidate (CIC) of FIG. 4 are used as examples.

The compound instruction candidate selector 111 first identifies a node cluster that is a compound instruction candidate (CIC) in the intermediate expression tree. For example, in the intermediate expression tree of FIG. 4 (a), node cluster B including node 1 and node 4 may be a compound instruction candidate (CIC). This is because two member nodes of node cluster B match r ₄₁ and r ₄₁ , respectively, partitioned from complexity rule r ₄ .

Similarly, node clusters D, E, F, and G may also be compound instruction candidates (CICs). On the other hand, node clusters A, C, and h cannot be performed in parallel because of data dependencies, and thus are removed from the compound instruction candidate list.

Compound instruction candidates (CICs) are used to cover the intermediate expression tree in the covering unit 113 that performs the precover and covering operations, and then execute the parallel instructions in the final code generator 140. It is generated as a multi-output instruction (MOI) and emitted to the final code.

However, due to interference between compound instruction candidates, all compound instruction candidates (CICs) are selected in consideration of the covering operation. For example, even if five compound instruction candidates are calculated in FIG. 4B, node clusters B and D cannot be simultaneously selected. If B and D are selected at the same time, it is because tree node 1 is covered twice.

In order for the selected composite instruction candidates to be effectively covered without interfering with each other, the composite instruction candidates should be carefully selected. In the candidate set selection step of the compound instruction candidate selection unit 111, the interference relationship on the candidate interference graph (CIG) is classified into two types to be described later, and the interference relationship is appropriately selected according to each type. Should be dealt with.

In a candidate interference graph (CIG), node n represents a compound instruction candidate, an edge represents an interference relationship with an adjacent node, and only one node among several nodes is forced to be selected.

5 is a diagram illustrating candidate interference graphs, labeling, covering, codes of covering steps, and generated codes after register allocation. Figure 5 also uses the rules of the example.

FIG. 5A illustrates a candidate interference graph CIG, and an edge indicated by a solid line in FIG. 5A indicates a covering interference. As in the case of B and D of Fig. 5 (a), since the complex instruction selection candidates (CICs) connected to the edges indicated by solid lines share the same partitioning rule, the two complex instruction selection candidates collide in the covering step.

An edge indicated by a dotted line in FIG. 5 (a) means dependency interference. This dependence interference is a case where a new dependency between other nodes is obtained when one complex instruction candidate (CIC) is selected to cover an IR tree.

For example, assume that D is selected as a compound instruction candidate (CIC) to cover tree nodes 1 and 5 in FIG. 4 (a). If D is selected, a data dependency occurs between the 3 and 4 nodes of G that pass through the nodes of D. Since this dependency serializes the execution of internal nodes, G can no longer be selected to generate parallel execution instructions (multi-output instructions, MOI) in code.

In the candidate interference graph (CIG), each compound instruction candidate node m is weighted. The weight w _m for a compound instruction corresponding to node _m is defined as C ₀ , which is the opportunity cost of the complex rule r, as shown in Equation 1 below.

Where C _c is the cost of the composite instruction in size and latency.

When r _i is the i-th complex rule in r, r ' _i is a simple rule that represents the same instruction pattern as r _i . Then the two rules r _i and r ' _i are equivalent. C _s (r _i) to define a cost of r _'i, and define the total cost of all the simple rule corresponding to each ΣC _s (r _i) the splitting rule r. For example, the example rule shows that C _s (r ₄₁ ) = 1, which is the same cost as the sll command in r ₃ .

The costs of r ₄ , r ₅ and r ₆ are as follows.

C _o ( r ₄ ) = (1 + 1) -1.5 = 0.5, C ₀ ( r ₅ ) = (1 + 1) -1 = 1, C ₀ ( r ₆ ) = (1 + 1) -1 = 1

Therefore, the weights of the compound instruction candidates are calculated as follows.

w _B = 0.5 and w _D = w _E = w _F = w _G = 1

The main task of the compound set selection (CSS) step is to find the appropriate set of compound instruction candidates (CICs) with the greatest benefit (or maximum weighted sum). If two compound instruction candidates follow the interference constraint, they are appropriate compound instruction candidates.

In FIG. 5 (a), there are four suitable complex instruction candidate sets: {B, E}, {B, F}, {D, E} and {F, G}. The two sets {D, E} and {F, G} have the same maximum benefit (= 2). Assume that {F, G} is selected in the command candidate selection step.

In the next step, the compound instruction candidate set is used by a tree parser traversing the intermediate representation tree (IR tree), using dynamic programming to efficiently generate instructions for the final code. Although the compound instruction candidates with the maximum benefit do not guarantee the code with the best cost, they at least provide a good starting point for finding the optimal condition for the tree parser. However, the complex rules that match compound instruction candidates are treeless shapes, and thus rules as a whole cannot be recognized by the tree parser. The only rule for participating in parsing is through a split rule with a tree shape. For this reason, after the optimal compound instruction candidate set is calculated, the cost of all partitioning rules r _i must be calculated from the complex rules that match each compound instruction candidate in the set, as follows.

C (r _i ) = C (r ' _i ) -C _o (r) / n

Where r _i is the i-th division rule, r ' _i is equivalent to r _i, and n is the number of division rules r.

Since F and G of the selected set of compound instruction candidates match the simple rule r ₆ , the cost of the split rules of r ₆₁ and r ₆₂ can be calculated from r ₆ as follows.

C ( r ₆₁ ) = 1-1 / 2 = 0.5, C ( r ₆₂ ) = 1-1 / 2 = 0.5

rules  : r _One ( add ,One), r ₂ ( mov ,One), r ₃ ( sll ,One), r ₆₁ ( add , 0.5), r ₆₂ ( mov , 0.5)

As the segmentation rules increase in cost, the simple rules in the intermediate expression tree of the labeling step are labeled with each node.

In the following covering step, among the rules labeled together at each node, the tree parser extracts the optimal formula that covers the entire intermediate representation tree. For example, node 3 of FIG. 5 (b) is labeled with r ₂ , r ₆₂ two rules.

5 (c) consists of three rules covering all nodes in the tree: r ₃ <-(1), r ₆ <-(2,5), and r ₆ <-(3,4). In conclusion, you get three commands: sll, addmov, and addmov.

FIG. 5 (d) shows the code of the covering step of FIG. 5 (c), and FIG. 5 (e) illustrates the code generated after applying register merge and register allocation to the code of FIG. 5 (d). In this case, the move instruction can not be detached and removed by itself during the register allocation phase, so the compiler can no longer remove the valueless move instruction contained in the addmov instruction on the first line.

As shown in FIG. 1, the register allocator 120 has a path fed back to the instruction selector 110 to inform the instruction selector 110 of the existence of a valueless compound instruction NCI. The valueless compound instruction detector 130 performs this role, and the valueless compound instruction detector 130 detects the valueless compound instruction (NCI) and causes the command selector 110 to execute a candidate interference graph (CIG). Remove F and G, the candidates for the valueless compound instruction, and select the new compound instruction candidate. Prior to register allocation, the code of FIG. 5 (d) was an optimal code having a cost of 3, but the code of FIG. 5 (d) generates a valueless compound instruction (NCI) as in FIG. 5 (e) and should be discarded.

The instruction selector 110 removes a compound instruction candidate (CIC) that generated a valueless compound instruction (NCI) on a candidate interference graph (CIG) after NCI is detected, and then selects a next most suitable compound instruction candidate set (CIC set). Select again. However, this is too aggressive and naive to solve the problem of valueless compound instructions.

FIG. 6 illustrates a candidate interference graph, labeling, covering, code of covering steps, and generated code after register allocation, using example rules.

Even if a compound instruction candidate (CIC) called X has a valueless compound instruction on the first attempt, the compound instruction is not canceled again as long as X is selected with other compound instruction candidates on the next attempt to form a new set of compound instruction candidates. There is still a high probability. Different compound instruction candidates (CICs) produce different results not only in the covering phase but also in the register merging phase. Simply removing X from the candidate interference graph (CIG) just because it generates a valueless compound instruction deprives X of the opportunity to find the optimal code.

As shown in FIG. 6 (a), it is necessary to increase an additional interference edge in the candidate interference graph to better solve the valueless compound instruction problem.

In the code of FIG. 5 (e), once the first choice {F, G} fails because of the valueless compound instruction addmov, the instruction selector 110 has the next best compound instruction candidate having the maximum benefit. CIC) set.

In the same candidate interference graph CIG, {F, G} still belongs to the set with maximum benefit, so there is a chance to select {F, G} again. In order to prevent {F, G} from being reselected, a new edge is added to the candidate interference graph, and the new edge is indicated by a bold line as shown in FIG. 6 (a) to represent another type of interference.

Interference edges, denoted by bold lines, are mutual exclusion edges, which mean mutual exclusion edges of interconnected composite instruction candidate nodes.In any environment, nodes connected by mutual exclusion edges are worthless NCIs. They cannot be selected together to prevent their occurrence.

There are now four suitable complex instruction candidate (CIC) sets, {B, E}, {B, F}, {D, E}, and {G}, where {D, E} has a maximum cost of 2. It's the only set with that.

In a second attempt, after going through the labeling step of FIG. 6 (b) and the covering step of FIG. 6 (c), the code of FIG. 6 (d) is generated. However, the code of FIG. 6 (d) has a valueless compound instruction sllmov, as shown in FIG. 6 (e). Therefore, a new mutual exclusion edge must be added to the candidate interference graph CIG of FIG. 6 (a) again.

FIG. 7 is a diagram illustrating candidate interference graphs, labeling, covering, codes of covering steps, and generated codes after register allocation, with example rules being used.

As described above, referring to FIG. 7A, a new mutual exclusion edge is added between D and E in the candidate interference graph CIG. Recalculating the appropriate compound instruction candidate sets yields {B, E}, {B, F}, {D}, and {G}, wherein the first two sets have a maximum cost of 1.5.

In a third iteration, the labeling step of FIG. 7 (b) and the covering step of FIG. 7 (c) are passed. Since any one can be selected in the command selection step, when {B, E} is selected as in FIG. 7 (c), the code of FIG. 7 (d) is generated.

After three iterative attempts, there is no valueless compound instruction (NCI) as shown in FIG.

In order to obtain a code without NCI, the command selector 110 should produce the code of FIG.

Unfortunately, at the stage of selection set selection (CSS), the compiler chose {B, E} to be less important than the original choice of {F, G} as compound instruction candidate (CIC). This is not possible.

The policy for selecting the optimal set of compound instruction candidates (CICs) according to their profits at the instruction candidate selection (CIC) stage is to increase the chances of selection of compound instruction candidates that are successfully selected as compound instructions. However, this policy does not guarantee the creation of the final code which always has the minimum cost. This is because a valueless compound instruction (NCI) occurs as a result of register merging.

Each time the appropriate compound instruction candidates (CICs) are selected differently, the mix or order of instructions in the code is changed, and the survival range of the temporary variable is changed. This means that only after the CIC set is fixed, the colorability of each node on the interference graph can be known.

Thus, if all possible register merges are not prioritized for all compound instruction candidate (CIC) sets, then the candidate set selection (CSS) step determines which compound instruction candidates in the final code will result in a valueless compound instruction (NCI). Can't decide

In the above, the operation of the code generation device according to the present invention has been described in order. Since the operation (function) of the code generating apparatus according to the present invention is essentially the same as the procedure of the code generating method to be described below, redundant description will be omitted.

8 is a flowchart illustrating a code generation method according to an embodiment of the present invention.

First, the command selector 110 selects a compound command candidate CIC from G which is a candidate interference graph CIG (S11).

If the sets of appropriate compound instruction candidates calculated from the candidate interference graph G in the compound instruction candidate selection step are Ψ, the instruction selecting unit 110 selects ψ, which is a set of compound instruction candidates (CICs) satisfying the following. Where ψ∈Ψ and profit (ψ) ≥profit (φ) for every φ∈Ψ.

In addition, the instruction selector 110 evaluates the cost of all the division rules divided in the complex rule for ψ.

The command selector 110 performs the labeling step S12 and the covering step S13 by using the partitioning rules together with all the simple rules.

After the covering step is performed, the register allocator 120 generates a code after performing register allocation and register merging, and transfers the generated code to the valueless compound instruction detector 130 and the final code generator 140. (S14).

The valueless compound instruction detection unit 130 detects whether the code generated in the register allocation step has a valueless compound instruction (S15).

If the valueless compound instruction detection unit 130 does not detect any valueless compound instruction, the final code generator 14 notifies the fact so as to discharge the final final code (S17).

On the other hand, when the valueless compound instruction detector 130 detects a valueless compound instruction, the command selector 110 removes the compound instruction candidate that generated the valueless compound instruction from the candidate interference graph CIG and selects a new compound instruction candidate. (S16).

In this case, the command selector 110 determines X belonging to ψ as a compound command candidate corresponding to a valueless compound command. If X is the only compound instruction candidate of ψ, then remove the candidate interference graph X. Otherwise, the mutual exclusion edges X and Y, which are new interference edges, are inserted into the candidate interference graph G (S16). In this case, all Y belong to ψ (every Y∈ψ).

In the worst case, since the at least one interference edge is inserted into the G node or one compound instruction candidate is removed from the G node in step S16, the number of repetitions may be O (k ² ). Here, k is the number of composite instruction candidate nodes in the candidate interference graph. Normally, valueless compound instructions (NCIs) generally disappear in the initial iteration phase, so the number of iterations is reduced to O (k).

The most time consuming steps are step S11 and step S15. Therefore, since k is asymptotically proportional to n (the number of nodes in the intermediate expression tree), the total command selection time will be on average O (n ³ ).

In any case, as the experiments show, even if you manipulate the complex instructions further for code generation, you can maintain compile time within the boundary of O (n).

The method of the present invention can also be embodied as computer readable code on a computer readable recording medium. The computer-readable recording medium includes all kinds of recording devices in which data that can be read by a computer system is stored. Examples of the computer-readable recording medium include a ROM, a RAM, a CD-ROM, a magnetic tape, a floppy disk, an optical data storage device, and the like, and may be implemented in the form of a carrier wave (for example, transmission via the Internet) . The computer readable recording medium can also be distributed over network coupled computer systems so that the computer readable code is stored and executed in a distributed fashion.

While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it is to be understood that the invention is not limited to the disclosed embodiments, but, on the contrary, is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the invention. Therefore, the protection scope of the present invention should be interpreted by the claims to be described later, and all the technical ideas within the equivalent and equivalent ranges should be construed as being included in the protection scope of the present invention.

1 is a view showing a code generation device according to an embodiment of the present invention.

FIG. 2 is a diagram illustrating the command selection unit in detail in FIG. 1; FIG.

3 is a view showing a code generation device according to another embodiment of the present invention.

4 illustrates an intermediate representation tree and a compound instruction candidate.

5 illustrates candidate interference graphs, labeling, covering, codes of covering steps, and generated codes after register allocation.

6 illustrates candidate interference graphs, labeling, covering, codes of covering steps, and generation codes after register allocation.

7 illustrates candidate interference graphs, labeling, covering, codes of covering steps, and generated codes after register allocation.

8 is a flowchart illustrating a code generation method according to an embodiment of the present invention.

Claims (5)

An instruction selecting unit for selecting a set of composite instruction candidates having no interference relation and which may be performed in parallel, in a candidate interference graph including composite instruction candidates extracted from an intermediate expression tree; A register allocator for allocating and merging registers for use in the set of compound instruction candidates selected by the instruction selector to generate a code to which registers are assigned; A valueless compound instruction detector for detecting a valueless compound instruction including a valueless move instruction in a code allocated to the register; And If the valueless compound instruction is not detected, the register includes a final code generation unit for discharging the code assigned to the final code, The value-free compound instruction detection unit, when the valueless compound instruction is detected, instructs the command selection unit to remove the selected set of compound instruction candidates and select a new set of compound instruction candidates. Code generation device for optimizing code by eliminating compound instructions. The method of claim 1, wherein the valueless compound instruction detector When the valueless compound instruction is detected, nodes connected to the mutual exclusion edge are added to the candidate interference graph by adding mutual exclusion edges indicating mutual exclusion edges between nodes associated with the selected compound instruction candidate. And a code generation device for optimizing code by removing valueless compound instructions when selecting the compound instructions. The method of claim 1, wherein the command selection unit And selecting a set of compound instruction candidates to have a maximum weighted sum in the candidate interference graph. (a) selecting a set of composite instruction candidates that are non-interfering and can be performed in parallel in a candidate interference graph composed of composite instruction candidates extracted from the intermediate expression tree; (b) allocating and merging registers for use in the selected set of composite instruction candidates to generate a register-allocated code; (c) detecting a valueless compound instruction comprising a valueless move instruction in a code assigned to the register; And (d) if the valueless compound instruction is not detected, releasing the register-allocated code to the final code, If the valueless compound instruction is detected, returning to step (a) to remove the selected set of compound instruction candidates from the candidate interference graph and select a new set of compound instruction candidates. How to generate code to optimize your code by eliminating compound instructions. The method of claim 4, wherein the method is performed before step (b). (e) labeling and covering the intermediate expression tree, wherein the code generation method for optimizing code by removing a valueless compound instruction when selecting a compound instruction.

Images