Method for improving instruction selection efficiency in a DSP/RISC compiler

• US 20040025151A1
• Filed: 07/31/2002
• Published: 02/05/2004
• Est. Priority Date: 07/31/2002
• Status: Abandoned Application

• Current Assignee: Faraday Technology Corp.
• Original Assignee: Faraday Technology Corp.
• Inventors: Ku, Shan-Chyun
• Application Number:
  US10/207,829
• Publication Number:
  US 20040025151A1
• Time in Patent Office: Days
• US Class Current: 717/159
• CPC Class Codes: G06F 8/4441 Reducing the execution time required by the program code

Abstract

A method for improving instruction selection efficiency in a DSP/RISC compiler. Concurrently obtaining optimal performance and space, the method includes the following steps: determining a semantic tree for a basic block; finding all matching combinations for the semantic tree with reference to a set of patterns; determining cycle number and instruction length for all combinations; filtering the instruction length greater than a predetermined instruction length and extra ones having the same cycle number and instruction length according to the determined cycle number and instruction length; and choosing one combination with the smallest cycle number from the remaining combinations and outputting the one combination as the desired object code.

Claims

1. A method for improving instruction selection efficiency in a DSP/RISC compiler, comprising the steps of:

determining a semantic tree for a basic block;

finding all matching combinations for the semantic tree with reference to a set of patterns;

determining cycle number and instruction length for all combinations;

filtering the instruction length greater than a predetermined instruction length and extra ones having the same cycle number and instruction length according to the determined cycle number and instruction length; and

choosing one combination with the smallest cycle number from the remaining combinations and outputting the one combination to be the desired object code.

2. The method of claim 1, wherein the basic block is represented as one or more independent data dependency graph, each including one or more nodes.

3. The method of claim 2, wherein each node represents an instruction.

4. The method of claim 1, wherein each of the patterns comprises an entry node at the top and a node connecting to the entry node.

5. The method of claim 1, wherein each of the patterns comprises an entry node at the top and multiple nodes connecting to the entry node.

6. The method of claim 1, wherein the set of patterns are machine-dependent.

7. The method of claim 1, wherein the instruction length is machine-dependent.

8. The method of claim 1, wherein the predetermined instruction length is determined by the capacity of the DSP/RISC compiler.

9. The method of claim 1, wherein the desired object code is an assembly code.

10. The method of claim 1, wherein the desired object code is a binary code.

11. The method of claim 1, wherein the semantic tree matching is executed from bottom to a single root where the basic block implementation is completed.

12. The method of claim 1, further comprising using an optimizer to implement the method.

13. The method of claim 1, further comprising using a code generator to execute the method to output the desired object code.