Method of generating code for programmable processors, code generator and application thereof

• US 5,854,929 A
• Filed: 11/18/1996
• Issued: 12/29/1998
• Est. Priority Date: 03/08/1996
• Status: Expired due to Term

• Current Assignee: Synopsys Incorporated
• Original Assignee: Interuniversitair Micro-Electronica Centrum VZW (IMEC International)
• Inventors: Geurts, Werner Gustaaf Theresia, Van Praet, Johan Roland, Lanneer, Dirk, Goossens, Gert Lodewijk Huibrecht
• Primary Examiner(s): Trammell, James P.
• Assistant Examiner(s): Nguyen, Cuong H.
• Application Number:
  US08/751,337
• Time in Patent Office: 771 Days
• Field of Search: 395/701-709, 395/564-568, 395/800.01, 395/800.02, 395/800.07, 395/800.1, 395/800.11, 395/800.16, 395/800, 364/48-491, 364/578
• US Class Current: 717/156
• CPC Class Codes: G06F 30/30 Circuit design
• CPC Class Codes: G06F 8/41 Compilation

Abstract

The present invention concerns a method of generating code for a programmable processor and comprises several steps. The first step is representing the processor as a directed bipartite graph with first and second sets of vertices and with edges, the graph comprising essentially all information about an instruction set and hardware of the processor, the first set of vertices representing storage elements in the processor, and the second set of vertices representing operations in the processor. The second step includes linking the graph to tools and libraries required for generating code for the processor. The last step is executing the required code generation phases, whereby the required information about the processor is extracted from the graph. The present invention also concerns the application of this method.

Claims

1. A method of generating code for a programmable processor being implemented in hardware and having an instruction set, said method comprising the steps of;

representing said processor as a directed bipartite graph with first and second sets of vertices and with edges, said graph comprising essentially all information about the instruction set and the hardware of said processor, said first set of vertices representing storage elements in said processor, and said second set of vertices representing micro-operations in said processor,

linking said graph to tools and libraries required for generating code for said processor, and

executing the required code generation phases whereby the required information about said processor is extracted from said graph.

2. The method as defined in claim 1 wherein, said edges represent valid connections between said micro-operations and said storage elements, said connections modeling the data flow in said processor.

3. The method as defined in claim 1 wherein said code generator evaluates the optimization space of generating code for an application algorithm, further comprising the step of building a decision tree with vertices and branches wherein:

vertices of said decision tree represent primitive operations, whereby said application algorithm contains instances of said primitive operations;

said branches represent possible transformations of said primitive operations according to alternative mapping possibilities in said optimization space, and

wherein, the set of vertices of said decision tree comprises vertices representing patterns of other vertices of said set, said patterns being defined during said code generation phases, and the second set of vertices representing micro-operations of said processor.

4. The method as defined in claim 1, further comprising the steps of:

representing hardware conflicts in said processor as access conflicts on said vertices representing said storage elements; and

annotating each vertex of said second set of vertices representing micro-operations with an enabling condition, said enabling condition representing values of the instruction register of said processor that enable the execution of the micro-operation represented by said vertex.

5. The method as defined in claim 4 wherein, said method determines valid partial instructions, said method further comprising the steps of:

selecting a subset of said second set of vertices representing micro-operations;

verifying that the intersection of the enabling conditions of all micro-operations of said subset is not empty; and

verifying that said subset is free of access conflicts on said storage elements.

6. The method as defined in claim 1 wherein, said storage elements are static and transitory storage elements, said method further comprising the step of representing all hardware conflicts in said processor as access conflicts on said vertices representing said transitory storage elements.

7. The method as defined in claim 1 wherein, data-types supported by a storage element are specified, said method further comprising the steps of:

specifying different vertices representing one storage element;

annotating each of said different vertices with a data type supported by said one storage element, and

specifying an alias relationship between said different vertices representing said one storage element.

8. The method as defined in claim 1 adapted for representing record storage elements, said method further comprising the steps of:

specifying a vertex representing the concatenation of several storage elements;

annotating said vertex with a data type being a record of the data types of said storage elements;

specifying a structural relationship between said vertex and the vertices representing said storage elements.

9. The method as defined in claim 1, adapted for representing micro-operations of which the execution depends on a defined condition, said method further comprising the steps of:

specifying a subset of said second set of vertices representing micro-operations, characterized in that all vertices in said subset depend on said condition;

specifying in said subset a vertex;

specifying an edge of said edges, said edge connecting a vertex of said first set of vertices that represents the storage element where said condition is available with said vertex in said subset, and said edge indicating that said micro-operations represented in said subset can only be enabled when said condition has a specific value.

10. The method as defined in claim 4 wherein, execution times of micro-operations are modeled, said method further comprising the steps of:

annotating an enabling condition of said micro-operation with the relative time step of the corresponding instruction issue with respect to the start of said micro-operation;

annotating said operation with the time steps relative to the start of said micro-operation at which said operation accesses the input and output storage elements of said micro-operation.

11. The method as defined in claim 1 wherein, said method represents a functional unit in said processor, said method further comprising the steps of specifying a subset of said second set of vertices representing operations wherein, all vertices in said subset execute on said functional unit.

12. The method as defined in claim 1 wherein, said processor includes a controller unit, and micro-operations modeling said controller unit are represented as vertices of said second set of vertices representing micro-operations.

13. The method as defined in claim 1 wherein, said processor has an architecture and instruction set designed for a specific class of algorithms such as digital signal processing algorithms.

14. The method as defined in claim 13 wherein, said processor is integrated in an application-specific integrated circuit.

15. A retargetable code generator for generating code for programmable processors being embedded in an electronic system comprising:

an electronic system with an embedded programmable processor, first tools to build a directed bipartite graph with vertices and edges which internally represents said programmable processor, said graph comprising essentially all information about the instruction set and the hardware of said processor and having first and second sets of vertices, said first set of vertices representing storage elements in said processor, and said second set of vertices representing micro-operations in said processor, said edges represent valid connections between said micro-operations and said storage elements,

second tools and libraries required to generate code for said processor, and

means to link said graph to said second tools and said libraries, whereby the information about said processor required during code generation is extracted from said graph.

16. A retargetable code generator as defined in claim 15 wherein said first tools:

represent hardware conflicts in said processor as access conflicts on said vertices representing said storage elements; and

annotate each vertex of said second set of vertices representing micro-operations with their enabling condition, said enabling condition representing values of the instruction register of said processor that enable the execution of the operation represented by said vertex.

17. A retargetable code generator as defined in claim 16 wherein said second tools determine valid partial instructions by;

selecting a subset of said second set of vertices representing micro-operations;

verifying that the intersection of the enabling conditions of all micro-operations of said subset is not empty; and

verifying that said subset is free of access conflicts on said storage elements.

18. A method of simulating the execution of code on a programmable processor, being implemented in hardware and having an instruction set, said method comprising the steps of:

representing said processor as a directed bipartite graph with first and second sets of vertices and with edges, said graph comprising essentially all information about the instruction set and the hardware of said processor,

said first set of vertices representing storage elements in said processor,

said second set of vertices representing micro-operations in said processor;

said edges representing valid connections between micro-operations and said storage elements, and

said connections modeling the data flow in said processor,

linking said graph to tools and libraries requited for said simulation, and

executing said simulation whereby the required information about said processor is extracted from said graph.

19. The method as defined in claim 18 further comprising the step of representing hardware conflicts in said processor as access conflicts on said vertices representing storage elements.

20. The method as defined in claim 18 wherein, said storage elements are static and transitory storage elements and wherein all hardware conflicts in said processor are represented as access conflicts on said vertices representing said transitory storage elements.

21. The method as defined in claim 18 wherein, each vertex of said second set of vertices representing s is annotated wit an enabling condition, said enabling condition representing values of the instruction register of said processor that enable the execution of the micro-operation represented by said vertex.

22. The method as defined in claim 18 wherein data-types supported by a storage element are specified, said method further comprising the steps of:

specifying different vertices representing one storage element;

annotating each of said different vertices with a data type supported by said one storage element, and

specifying an alias relationship between said different vertices representing said one storage element.

23. The method as defined in claim 18 adapted for representing record storage elements, said method further comprising the steps of:

specifying a vertex representing the concatenation of several storage elements;

annotating said vertex with a data type being a record of the data types of said storage elements;

specifying a structural relationship between said vertex and the vertices representing said storage elements.

24. The method as defined in claim 18 adapted for representing micro-operations of which the execution depends on a defined condition, said method further comprising the steps of:

specifying a subset of said second set of vertices representing micro-operations, characterized in that all vertices in said subset depend on said condition;

specifying in said subset a vertex;

specifying an edge of said edges, said edge connecting a vertex of said first set of vertices that represents the storage element where said condition is available with said vertex in said subset, and said edge indicating that said micro-operations represented in said subset can only be enabled when said condition bas a specific value.

25. The method as defined in claim 18 wherein, the execution times of micro-operations are modeled, said method further comprising the steps of:

annotating an enabling condition of said micro-operation with the relative time step of the corresponding instruction issue with respect to the start of said operation;

annotating said micro-operation with the time steps relative to the start of said micro-operation at which said micro-operation accesses the input and output storage elements of said micro-operation.

26. The method as defined in claim 18 wherein, said method represents a functional unit in said processor, said method further comprising the step of specifying a subset of said second set of vertices representing micro-operations characterized in that all vertices in said subset execute on said functional unit.

27. The method as defined in claim 18 wherein said processor includes a controller unit, and said controller unit are represented as vertices of said second set of vertices representing micro-operations.

28. A retargetable simulator that performs the simulation of the execution of code on a programmable processor being embedded in an electronic system comprising:

an electronic system with an embedded programmable processor,

first tools to build a directed bipartite graph which internally represents said programmable processor with first and second sets of vertices and with edges, said graph comprising essentially all information about the instruction set and the hardware of said processor, said first set of vertices representing storage elements in said processor, and said second set of vertices representing operations in said processor;

second tools and libraries required for simulating said processor, and

means to link said graph to said second tools and libraries whereby the information about said processor required during simulation is extracted from said graph.

29. A method of synthesizing a programmable processor being implemented in hardware, comprising the steps of:

representing said processor as a directed bipartite graph with first and second sets of vertices and with edges, said graph comprising essentially all information about the instruction set and the hardware of said processor,

said first set of vertices representing storage elements in said processor;

said second set of vertices representing micro-operations in said processor;

said edges representing valid connections between said micro-operations and said storage elements, said connections modeling the data flow in said processor;

linking said graph to tools and libraries required for generating a netlist of hardware building blocks;

implementing said processor as a hardware device according to said netlist.

30. A method of modeling a programmable processor being implemented in hardware adapted for use in an automatic retargetable code generator and in an instruction set simulator, said method comprising the steps of:

identifying storage elements and micro-operations in said processor; and

representing said processor as a directed bipartite graph with first and second sets of vertices and with edges, said graph comprising essentially all information about the instruction set and the hardware of said processor, said first set of vertices representing storage elements in said processor, and said second set of vertices representing operations in said processor.

31. The method as defined in claim 30, wherein said edges represent valid connections between said micro-operations and said storage elements, said connections modeling the data flow in said processor.

32. The method as defined in claim 30, further comprising the step of constructing said graph, said constructing step including the further steps of:

parsing a textual specification of said processor described in a high-level language; and

transforming said parsed textual specification into said graph.

33. The method as defined in claim 32, wherein said high-level language is an nML processor description language.

34. The method as defined in claim 30, wherein each vertex of said second set of vertices representing -operations is annotated with an enabling condition, said enabling condition representing values of the instruction register of said processor that enable the execution of the micro-operation represented by said vertex.

35. The method as defined in claim 30, further comprising the step of representing hardware conflicts in said processor as access conflicts on said vertices representing storage elements.

36. The method as defined in claim 30, wherein said storage elements are static and transitory storage elements, said method further comprising the step of representing all hardware conflicts in said processor as access conflicts on said vertices representing said transitory storage elements.

37. The method as defined in claim 30, wherein data types supported by a storage element are specified, said method further comprising the steps of:

specifying different vertices representing one storage element;

annotating each of said different vertices with a data type supported by said one storage element; and

specifying an alias relationship between said different vertices representing said storage element.

38. The method as defined in claim 30, adapted for representing record storage elements, said method further comprising the steps of:

specifying a vertex representing the concatenation of several storage elements;

annotating said vertex with a data type being a record of the data types of said storage elements; and

specifying a structural relationship between said vertex and the vertices representing said storage elements.

39. The method as defined in claim 30, adapted for representing micro-operations of which the execution depends on a defined condition, said method further comprising the steps of:

specifying a subset of said second set of vertices representing micro-operations, characterized in that all vertices in said subset depend on said condition;

specifying in said subset a vertex;

specifying an edge of said edges, said edge connecting a vertex of said first set of vertices that represents the storage element where said condition is available with said vertex in said subset, and said edge indicating that said micro-operations represented in said subset can only be enabled when said condition has a specific value.

40. The method as defined in claim 30, wherein execution times of micro-operations are modeled, said method further comprising the steps of annotating an enabling condition of said micro-operation with the relative time step of the corresponding instruction issue with respect to the start of said micro-operation;

and

annotating said micro-operation with the time steps relative to the start of said micro-operation at which said micro-operation accesses the input and output storage elements of said micro-operation.

41. The method as defined in claim 30, wherein said method represents a functional unit in said processor, said method further comprising the steps of specifying a subset of said second set of vertices representing micro-operations, wherein all vertices in said subset execute on said functional unit.

42. The method as defined in claim 30, wherein said processor includes a controller unit, and micro -operations modeling said controller unit are represented as vertices of said second set of vertices representing micro-operations.

43. The method as defined in claim 30, wherein said processor has an architecture and instruction set designed for a specific class of algorithms such as digital signal processing algorithms.

44. The method as defined in claim 30, wherein said processor is integrated in an application-specific integrated circuit.