Object-code compatible representation of very long instruction word programs

• US 5,951,674 A
• Filed: 02/14/1996
• Issued: 09/14/1999
• Est. Priority Date: 03/23/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Moreno, Jaime Humberto
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): Najjar, Saleh
• Application Number:
  US08/601,640
• Time in Patent Office: 1,308 Days
• Field of Search: 395/376, 395/380, 395/386, 712/210, 712/200
• US Class Current: 712/210
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836
• CPC Class Codes: G06F 9/30061 Multi-way branch instructions, e.g. CASE
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3853 of compound instructions
• CPC Class Codes: G06F 9/3856 Reordering of instructions, e.g. using queues or age tags
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units

Abstract

Object-code compatibility is provided among VLIW processors with different organizations. The object-code can also be executed by sequential processors, thus providing compatibility with scalar and superscalar processors, A mechanism is provided which allows representing VLIW programs in an implementation-independent manner. This mechanism relies on instruction cache (I-cache) reload/access logic which incorporates implementation-dependent features into a VLIW program. In this way, programs are represented in main memory in an implementation-independent manner, the implementation-specific aspects are introduced as part of the instruction cache reload/fetch processes, and the simplicity in instruction dispatch logic that is characteristic of VLIW processors is preserved. The foregoing allows for object-code compatibility among VLIW processors with different organizations. Also provided is a mechanism and an apparatus for the interpretation of tree-instructions by a computer system based on a VLIW processor.

Claims

1. A method of executing a program, said method comprising the steps of:

constructing a program as a set of variable length tree-instructions, each given tree-instruction comprising a sequence of primitive instructions including at least one execution path which are subject to sequential semantics, wherein each execution path starting at a first primitive instruction of said sequence of primitive instructions for said given tree-instruction and terminating at an unconditional branch instruction to a target instruction outside of said tree-instruction;

storing said program in memory, wherein, for each given tree-instruction, said sequence of primitive instructions for said given tree-instruction are stored in consecutive memory locations;

accessing said memory to fetch a memory block;

decomposing portions of at least one tree-instruction stored in said memory block into a plurality of variable length intermediate instructions according to resources of a processor;

executing said variable-length intermediate instructions in said processor.

2. The method recited in claim 1, further comprising the step of:

storing said variable length intermediate instructions in a high-speed buffer or cache for execution by said processor.

3. The method recited in claim 2, wherein said high speed buffer comprises a multi-level cache system.

4. The method recited in claim 1, wherein said processor is a very long instruction word (VLIW) processor including a VLIW register having a fixed-length, said method further comprising the steps of:

fetching a variable-length intermediate instruction; and

expanding and aligning said variable-length intermediate instruction to fit the fixed-length of the VLIW register.

5. The method of claim 1, wherein said memory block contains at least one complete tree-instruction, and said decomposing step decomposes said at least one complete tree-instruction.

6. The method of claim 1, wherein said memory block contains at least one incomplete tree-instruction, and said decomposing step inserts an implicit unconditional branch to the next sequential address that is to occur after the last primitive instruction for said incomplete tree-instruction.

7. The method of claim 1, wherein said sequence of primitive instructions for a given tree-instruction include multiple execution paths, whereby primitive conditional skip instructions that branch to primitive instructions within said tree-instruction spawn said execution paths, and whereby a sequential representation of said tree-instruction may be generated by traversing said execution paths in a depth first manner.

8. The method of claim 7, wherein said memory block contains at least one incomplete tree-instruction, and said decomposing step inserts into an implicit unconditional branch instruction to the next sequential address that is to occur after the last primitive instruction for said incomplete tree-instruction, and replaces any primitive conditional skip instruction to a location outside said memory block with a conditional branch instruction to said location outside said memory block.

9. A method of providing object-code compatibility among very long instruction word (VLIW) processors with different organizations, and compatibility with scalar and superscalar processors, by representing programs in an implementation-independent manner, said method comprising the steps of:

storing in computer memory a program as a set of variable length tree-instructions, each given tree-instruction comprising a sequence of primitive instructions including at least one execution path which are subject to sequential semantics, wherein each execution path starting at a first primitive instruction of said sequence of primitive instructions for said given tree-instruction and terminating at an unconditional branch instruction to a target instruction outside of said tree-instruction; and

introducing implementation-specific aspects of a computer processor into the program stored in computer memory as part of the instruction cache (I-cache) access, said logic performing a first set of tasks at I-cache reload time and a second-set of tasks at I-cache fetch time.

10. The method recited in claim 9 wherein the step of introducing implementation-specific aspects of the processor into the program comprises the steps of:

accessing said computer memory to fetch a memory block containing one or more tree-instructions, said tree-instructions are not allowed to straddle beyond the end of said memory block, and the tree-instruction straddling said memory block is regarded as terminated at the end of said memory block, and skip instructions whose target is outside said memory block are regarded as conditional branch instructions that terminate the corresponding execution paths; and

decomposing each fetched tree-instruction into a plurality of intermediate instructions of variable length, according to the resources of a processor on which the program is to be executed.

11. The method recited in claim 10 wherein the process is a VLIW processor having a fixed-length VLIW register, further comprising the steps of:

writing the variable-length intermediate instructions in an instruction cache (I-cache) for fetching by said processor;

fetching a variable-length intermediate instruction from said I-cache; and

expanding and aligning the fetched variable length intermediate instruction to fit the fixed-length VLIW register.

12. The method recited in claim 11 wherein each tree-instruction fetched by said processor is decomposed into a plurality of variable-length intermediate instructions utilizing the following steps:

determining the number of tree-paths in a corresponding multiway branch from skip instructions in the tree-instruction, each skip operation originating an additional path, and each path ending in an unconditional branch instruction or at the end of the memory block;

determining if the number of paths exceeds the resources of the processor; and

if the number of paths exceeds the resources of the processor, replacing skip instructions whose target is farthest away by conditional branch instructions with the same target, leaving only as many paths as the implementation allows.

13. The method recited in claim 12 further comprising the steps of:

determining if the number of primitive operations in the fetched tree-instruction exceeds the number of functional units in the processor;

if the number of primitive operations in the fetched tree-instruction exceeds the number of functional units, replacing skip instructions whose target is beyond a primitive instruction where the number of resources is exceeded by conditional branch instructions with the same target; and

breaking the path containing the operation where the number of resources is exceeded into different intermediate instructions by inserting an implicit unconditional branch to the next sequential address.

14. In a data processing system including a memory for storing a sequence of variable length tree-instructions, a method for executing said variable length tree-instructions comprising the steps of;

fetching from said memory a block containing at least one variable length tree-instruction, each given tree-instruction comprising a sequence of primitive instructions including at least one execution path which are subject to sequential semantics, wherein each execution path starting at a first primitive instruction of said sequence of primitive instructions for said given tree-instruction and terminating at an unconditional branch instruction to a target instruction outside of said tree-instruction;

decomposing portions of said at least one variable length tree-instruction fetched from said memory into a plurality of intermediate instructions according to resources of a processing engine;

storing said plurality of intermediate instructions in a high speed buffer; and

executing said plurality of intermediate instructions stored in said high speed buffer in said processing engine.

15. The method of claim 14, wherein said high speed buffer is a multi-level cache system.

16. The method of claim 14, wherein said processing engine is a VLIW processor and each of said intermediate instructions is of variable length.

17. The method of claim 16, wherein said VLIW processor includes a fixed-length VLIW register, said method further comprising the steps:

fetching a variable-length intermediate instruction from said high-speed buffer; and

expanding and aligning said variable-length intermediate instruction fetched from said high-speed buffer to fit said fixed-length of said VLIW register.

18. The method of claim 14, wherein end of the particular tree-instruction is delimited by a primitive operation that follows an unconditional branch instruction and that is not reachable by any skip primitive within the particular tree-instruction, or when the end of the memory block is reached.

19. The method of claim 18, wherein the decomposing step includes the following step:

pruning said at least one tree-instruction according to said resources of said processing engine to generate a plurality of intermediate instructions.

20. The method of claim 19, wherein the pruning step replaces a skip primitive within said at least one tree instruction with a conditional branch primitive.

21. The method of claim 18, wherein said intermediate instructions each comprise a plurality of chunks.

22. The method of claim 21, wherein the step of executing said plurality of intermediate instructions stored in said high speed buffer in said processing engine includes the steps of:

for each path within said plurality of intermediate instructions, generating TEM data that identifies chunks within said plurality of intermediate instructions that are to be completed in the given path and that identifies chunks within said plurality of intermediate instructions that are not to be completed in the given path;

determining a selected path;

selecting TEM data corresponding to said selected path;

controlling functional units of said processing engine to complete operations contained in said chunks within said plurality of intermediate instructions according to said selected TEM data.

23. The method of claim 22, wherein said functional units of said processing engine complete operations contained in chunks identified by said selected TEM data as chunks that are to be completed.

24. The method of claim 22, wherein said functional units of said processing engine do not complete operations contained in chunks identified by said selected TEM data as chunks that are not to be completed.

25. The method of claim 21, wherein the decomposing step includes the following step:

pruning said at least one tree-instruction according to said resources of said processing engine to generate a plurality of intermediate instructions.

26. The method of claim 25, wherein said pruning step includes the following steps:

if resources required to execute said at least one tree instruction exceed resources of said processing engine,

generating first data associated with a given chunk that identifies one or more skip instructions within said given chunk as a pruning point,

identifying at least one chunk within said at least one tree instruction that is to be pruned; and

if final operation of the chunk preceding said at least one chunk is not an unconditional branch instruction,

generating second data that identifies an implicit branch operation at end of said chuck preceding said at least one chunk.

27. The method of claim 26, wherein said skip instructions identified by said first data as pruning points are interpreted as conditional branch instructions to a separate tree instruction.

28. The method of claim 26, wherein the step of executing said plurality of intermediate instructions stored in said high speed buffer in said processing engine includes the steps of:

for each path within said plurality of intermediate instructions, generating TEM data that identifies chunks within said plurality of intermediate instructions that are to be completed in the given path and that identifies chunks within said plurality of intermediate instructions that are not to be completed in the given path, wherein, if said first data associated with a particular chunk identifies a skip instruction within the particular chunk as a pruning point, said TEM data corresponding to the particular chunk is set to indicate that the particular chunk is not to be completed in the given path;

determining a selected path;

selecting TEM data corresponding to said selected path;

controlling functional units of said processing engine to complete operations contained in said chunks within said plurality of intermediate instructions according to said selected TEM data.

29. The method of claim 28, wherein said functional units of said processing engine complete operations contained in chunks identified by said selected TEM data as chunks that are to be completed.

30. The method of claim 28, wherein said functional units of said processing engine do not complete operations contained in chunks identified by said selected TEM data as chunks that are not to be completed.

31. A data processing system comprising:

a memory storing a sequence of variable length tree-instructions, each given tree-instruction comprising a sequence of primitive instructions including at least one execution path which are subject to sequential semantics, wherein each execution path starting at a first primitive instruction of said sequence of primitive instructions for said given tree-instruction and terminating at an unconditional branch instruction to a target instruction outside of said tree-instruction;

instruction fetch means for fetching from said memory a block of data containing at least one variable length tree-instruction;

a pruning unit, coupled to said instruction fetch means, decomposing portions of said at least one variable length tree-instruction fetched from said memory into a plurality of intermediate instructions according to resources of a processing engine;

a high speed buffer, coupled to said pruning unit, storing said plurality of intermediate instructions;

wherein said processing engine executes said plurality of intermediate instructions stored in said high speed buffer.

32. The data processing system of claim 31, wherein said high speed buffer is a multi-level cache system.

33. The data processing system of claim 31, wherein said processing engine is a VLIW processor and each of said intermediate instructions is a variable-length VLIW.

34. The data processing system of claim 33, wherein said VLIW processor comprises:

a VLIW register having a fixed-length;

means for fetching one or more intermediate instructions from said high-speed buffer;

aligning means for aligning said one or more intermediate instructions fetched from said high-speed buffer such that said one or more intermediate instructions fit said fixed-length of said VLIW register; and

means for loading said one or more intermediate instructions generated by said aligning means into said fixed-length VLIW register.

35. The data processing system of claim 31, wherein each particular tree instruction includes at least one unconditional branch instruction which comprises a flow control operation to a target outside the particular tree instruction.

36. The data processing system of claim 31, wherein end of a particular variable length tree-instruction is delimited by a primitive operation that follows an unconditional branch instruction and that is not reachable by any skip primitive within the particular variable length tree-instruction.

37. The data processing system of claim 36, wherein said processing unit prunes said at least one variable length tree-instruction according to said resources of said processing engine to generate a plurality of intermediate instructions.

38. The data processing system of claim 37, wherein said pruning unit replaces a skip primitive within said at least one variable length tree-instruction with a conditional branch primitive in pruning said at least one variable length tree-instruction.

39. The data processing system of claim 31, wherein said variable length tree-instructions and said intermediate instructions each comprise a plurality of chunks.

40. The data processing system of claim 39, wherein said processing engine comprises:

a branch evaluation unit determining a selected path within each said intermediate instruction;

a TEM generator, coupled to said branch evaluation unit, that, for each path within each said intermediate instruction, generates TEM data that identifies chunks within each said intermediate instruction that are to be completed in the given path and that identifies chunks within each said intermediate instruction that are not to be completed in the given path, and that selects TEM data corresponding to said selected path; and

functional units that complete operations contained in said chunks within each said intermediate instruction according to said selected TEM data.

41. The data processing system of claim 40, wherein said functional units complete operations contained in chunks identified by said selected TEM data as chunks that are to be completed.

42. The data processing system of claim 40, wherein said functional units do not complete operations contained in chunks identified by said selected TEM data as chunks that are not to be completed.

43. The data processing system of claim 39, wherein said pruning unit prunes said at least one variable length tree-instruction according to said resources of said processing engine to generate a plurality of intermediate instructions.

44. The data processing system of claim 43, wherein, if resources required to execute said at least one variable length tree-instruction exceed resources of said processing engine, said pruning unit

generates first data associated with a given chunk that identifies one or more skip instructions within said given chunk as a pruning point;

identifies at least one chunk within said at least one variable length tree-instruction that is to be pruned; and

if final operation of the chunk preceding said at least one chunk is not an unconditional branch instruction, generates second data that identifies an implicit branch operation at end of said chunk preceding said at least one chunk.

45. The data processing system of claim 44, wherein said skip instructions identified by said first data as pruning points are interpreted as conditional branch instructions to a separate variable length tree-instructions.

46. The data processing system of claim 43, wherein said processing engine comprises:

a branch evaluation unit for determining a selected path within each said intermediate instruction;

a TEM generator, coupled to said branch evaluation unit, that, for each path within each said intermediate instruction, generates TEM data that identifies chunks within each said intermediate instruction that are to be completed in the given path and that identifies chunks within each said intermediate instruction that are not to be completed in the given path, wherein, if said first data associated with a particular chunk identifies a skip instruction within said particular chunk as a pruning point, said TEM data corresponding to the particular chunk targeted by said skip instruction is set to indicate that the particular chunk is not to be completed in the given path; and

functional units that complete operations contained in said chunks within each said intermediate instruction according to said selected TEM data.

47. The data processing system of claim 46, wherein said functional units complete operations contained in chunks identified by said selected TEM data as chunks that are to be completed.

48. The data processing system of claim 46, wherein said functional units do not complete operations contained in chunks identified by said selected TEM data as chunks that are not to be completed.

49. The data processing system of claim 31, wherein said block of data contains at least one complete tree-instruction, and said pruning unit decomposes said at least one complete tree-instruction.

50. The data processing system of claim 31, wherein said block of data contains at least one incomplete tree-instruction, and said pruning unit inserts an implicit unconditional branch to the next sequential address that is to occur after the last primitive instruction for said incomplete tree-instruction.

51. The data processing system of claim 31, wherein said sequence of primitive instructions for a given tree-instruction include multiple execution paths, whereby primitive conditional skip instructions that branch to primitive instructions within said tree-instruction spawn said execution paths, and whereby a sequential representation of said tree-instruction may be generated by traversing said execution paths in a depth first manner.

52. The data processing system of claim 51, wherein said block of data contains at least one incomplete tree-instruction, and said pruning unit inserts into an implicit unconditional branch instruction to the next sequential address that is to occur after the last primitive instruction for said incomplete tree-instruction, and replaces any primitive conditional skip instruction to a location outside said block of data with a conditional branch instruction to said location outside said block of data.

53. A method of executing a program stored in memory, said program characterized as being a set of variable length tree-instructions, each given tree-instruction comprising a sequence of primitive instructions including at least one execution path which are subject to sequential semantics, wherein each execution path starting at a first primitive instruction of said sequence of primitive instructions for said given tree-instruction and terminating at an unconditional branch instruction to a target instruction outside of said tree-instruction, the method comprising the steps of:

accessing said memory to fetch a memory block;

decomposing portions of said at least one variable tree-instruction stored in said memory block into a plurality of variable length intermediate instructions according to resources of a processor; and

executing said variable length intermediate instructions in said processor.