Method and system of control flow graph construction

• US 7,624,382 B2
• Filed: 07/26/2005
• Issued: 11/24/2009
• Est. Priority Date: 07/27/2004
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Cabillic, Gilbert, Chauvel, Gerard, Lesot, Jean-Philippe, Peltier, Mikael
• Primary Examiner(s): Chan; Eddie P
• Assistant Examiner(s): VICARY, KEITH E
• Application Number:
  US11/189,367
• Publication Number:
  US 20060026571A1
• Time in Patent Office: 1,582 Days
• Field of Search: 712/209, 717/132
• US Class Current: 717/132
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/1081 for peripheral access to main memory, e.g. direct memory access [DMA]
• CPC Class Codes: G06F 2212/6012 of operating mode, e.g. cache mode or local memory mode
• CPC Class Codes: G06F 9/30174 for non-native instruction set, e.g. Javabyte, legacy code
• CPC Class Codes: G06F 9/45504 Abstract machines for programme code execution, e.g. Java virtual machine [JVM], interpreters, emulators
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A method and system to build a control flow graph by execution of micro-sequences using hardware. Some illustrative embodiments are a processor comprising fetch logic that retrieves an instruction from a memory, the instruction being part of a program, and decode logic coupled to the fetch logic which decodes the instruction, wherein the instruction decoded by the decode logic triggers execution of a micro-sequence to enter the instruction in a control flow graph.

Claims

1. A processor, comprising:

fetch logic configured to retrieve a plurality of instructions from a memory, wherein the plurality of instructions are from a first native instruction set of the processor; and

decode logic coupled to the fetch logic, wherein the decode logic is configured to decode the plurality of instructions,

wherein the processor is configurable to execute the plurality of instructions and to construct a control flow graph for the plurality of instructions,

wherein when the processor is configured to construct the control flow graph, each instruction in the first native instruction set of the processor is associated with a micro-sequence configured to generate a portion of the control flow graph corresponding to the instruction and the decode logic, responsive to decoding each instruction in the plurality of instructions, causes the micro-sequence associated with each instruction in the plurality of instructions to be executed, wherein the control flow graph is constructed, and

when the processor is configured to execute the plurality of instructions, each instruction in a subset of the first native instruction set is associated with a micro-sequence configured to perform a function of the instruction and the decode logic causes each instruction in the plurality of instructions to be executed, wherein when the micro-sequence is associated with the instruction, the micro-sequence is executed to perform the function of the instruction,

wherein a micro-sequence is one or more instructions from a second native instruction set of the processor.

2. The processor of claim 1, further comprising:

a vector table accessible by the decode logic, wherein the vector table comprises an entry for each instruction in the first native instruction set,

wherein when the processor is configured to construct the control flow graph, the vector table is used to associate each instruction in the first native instruction set with the micro-sequence configured to generate the portion of the control flow graph corresponding to the instruction, and

when the processor is configured to execute the plurality of instructions, the vector table is used to associate each instruction in the subset of instructions with the micro-sequence configured to perform the function of the instruction.

3. The processor of claim 2, wherein when a micro-sequence is associated with an instruction, the entry for the instruction references a location in the memory in which the micro-sequence is stored.

4. The processor of claim 1, wherein a compiler is configured to cause configuration of the processor to construct the control flow graph.

5. The processor of claim 1, wherein a micro-sequence configured to generate a portion of the control flow graph identifies whether an instruction is a leader instruction.

6. The processor of claim 1, wherein a micro-sequence configured to generate a portion of the control flow graph identifies whether an instruction is a non-leader instruction.

7. The processor of claim 1, wherein the control flow graph is constructed in a single pass.

8. The processor of claim 1, wherein the control flow graph is constructed in more than one pass.

9. A method for constructing a control flow graph for a plurality of instructions, comprising:

configuring a processor to construct the control flow graph instead of executing instructions in a first native instruction set of the processor, wherein configuring comprises associating each instruction in the first native instruction set of the processor with a micro-sequence configured to generate a portion of the control graph corresponding to the instruction;

responsive to fetching and decoding each instruction in the plurality of instructions, executing the micro-sequence associated with the instruction, wherein the control graph is constructed; and

reconfiguring the processor to execute instructions in the instruction set after the control graph is constructed, wherein reconfiguring comprises associating each instruction in a subset of the first native instruction set with a micro-sequence configured to perform a function of the instruction, wherein all other instructions in the first native instruction set are executed directly by the processor,

wherein a micro-sequence is one or more instructions from a second native instruction set of the processor.

10. The method of claim 9, wherein

associating each instruction in the first native instruction set further comprises placing a reference to the micro-sequence in an entry of a vector table, wherein the vector table comprises an entry for each instruction in the first native instruction set, and

fetching and decoding further comprises accessing the vector table to locate the micro-sequence.

11. The method of claim 9, wherein executing the micro-sequence further comprises:

adding the instruction to a current block of the control flow graph when the instruction is a non-leader instruction,

wherein the current block is one of one or more existing blocks in the control flow graph.

12. The method of claim 9, wherein executing the micro-sequence further comprises:

adding the instruction to a new block in the control flow graph when the instruction is a leader instruction; and

linking the new block to existing blocks in the control flow graph.

13. The method of claim 11, wherein executing the micro-sequence further comprises adding a target of an unconditional branch to a new block of the control flow graph.

14. The method of claim 11, wherein executing the micro-sequence further comprises adding a target of a conditional branch to a new block of the control flow graph.

15. The method of claim 11, wherein executing the micro-sequence further comprises adding a start of a catch block to a new block of the control flow graph.

16. The method of claim 9, wherein the control flow graph is constructed in a single pass.

17. The method of claim 9, wherein the control flow graph is constructed in more than one pass.

18. A system, comprising:

a memory;

a first processor; and

a second processor coupled to the first processor, the second processor comprising;

fetch logic configured to retrieve a plurality of instructions from the memory, wherein the plurality of instructions are from a first native instruction set of the second processor; and

decode logic coupled to the fetch logic, wherein the decode logic is configured to decode the plurality of instructions,

wherein the second processor is configurable to execute the plurality of instructions and to construct a control flow graph for the plurality of instructions,

wherein when the second processor is configured to construct the control flow graph, each instruction in the first native instruction set of the second processor is associated with a micro-sequence configured to generate a portion of the control flow graph corresponding to the instruction and the decode logic, responsive to decoding each instruction in the plurality of instructions, causes the micro-sequence associated with each instruction in the plurality of instructions to be executed, wherein the control flow graph is constructed, and

when the second processor is configured to execute the plurality of instructions, each instruction in a subset of the instruction set is associated with a micro-sequence configured to perform a function of the instruction and the decode logic causes each instruction in the plurality of instructions to be executed, wherein when a micro-sequence is associated with the instruction, the micro-sequence is executed to perform the function of the instruction,

wherein a micro-sequence is one or more instructions from a second native instruction set of the second processor.

19. The system of claim 18, wherein the second processor further comprises:

a vector table accessible by the decode logic, wherein the vector table comprises an entry for each instruction in the first native instruction set,

wherein when the second processor is configured to construct the control flow graph, the vector table is used to associate each instruction in the first native instruction set with the micro-sequence configured to generate the portion of the control flow graph corresponding to the instruction, and

when the second processor is configured to execute the plurality of instructions, the vector table is used to associate each instruction in the subset of instructions with the micro-sequence configured to perform the function of the instruction.

20. The system of claim 19, wherein when a micro-sequence is associated with an instruction, the entry for the instruction references a location in the memory in which the micro-sequence is stored.

21. The system of claim 18, wherein a micro-sequence configured to generate a portion of the control flow graph identifies whether an instruction is a leader instruction.

22. The system of claim 18, wherein a micro-sequence configured to generate a portion of the control flow graph identifies whether an instruction is a non-leader instruction.

23. The system of claim 18, wherein the control flow graph is constructed in a single pass.

24. The system of claim 18, wherein the control flow graph is constructed in more than one pass.