Block translation optimizations for program code conversation

• US 20040255279A1
• Filed: 05/16/2003
• Published: 12/16/2004
• Est. Priority Date: 04/22/2003
• Status: Abandoned Application

• Current Assignee: Transitive Limited (International Business Machines Corporation)
• Original Assignee: Transitive Limited (International Business Machines Corporation)
• Inventors: Sandham, John, Brown, Alex, Souloglou, Jason, Owen, Daniel, Rawsthorne, Alasdair
• Application Number:
  US10/439,966
• Publication Number:
  US 20040255279A1
• Time in Patent Office: Days
• US Class Current: 717/136
• CPC Class Codes: G06F 9/30065 Loop control instructions; iterative instructions, e.g. LOOP, REPEAT
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory
• CPC Class Codes: G06F 9/45516 Runtime code conversion or optimisation

Abstract

Subject program code is translated to target code in basic block units at run-time in a process wherein translation of basic blocks is interleaved with execution of those translations. A combination of processes designed to enhance the speed and efficiency of run-time translation are applied based on characteristics of particular blocks and include translating a set of contiguous basic blocks prior to execution (“extended basic blocks”) and grouping and ordering of frequently executed basic blocks for translation (“group blocking”).

Claims

1. A method of translation of a plurality of basic blocks of program code comprising:

decoding a first basic block;

detecting whether the subject starting address of a successor block of said first basic block is statically determinable;

if said successor basic block is statically determinable, calculating the subject starting address of said successor block; and

resuming the decoding process at the subject starting address of said successor block.

2. The method of claim 1 wherein said first basic block includes an unconditional jump whose subject destination address is statically determinable and wherein said decoding process is resumed at said subject destination address.

3. The method of claim 1 wherein, if said successor block is statically determinable, an IR tree corresponding to the dynamic calculation of the starting subject address of said successor block is pruned.

4. The method of claim 1 wherein, if said successor block is not statically determinable, target code generated for said first basic block is executed prior to translation of said successor basic block.

5. The method of claim 4 further including the step of synchronizing a set of abstract registers at the end of execution of said basic block and prior to decoding of said successor block.

6. The method of claim 1 performed as part of a translation process including a control loop comprising the steps of:

executing translator code which translates a first block of subject code into translated code;

executing the translated code;

returning control to the translator code at the end of execution of the translated code; and

executing translator code which translates a second basic block into translated code.

24. The method of claim 1 wherein said steps are performed by program code stored on a tangible storage medium.

7. A method of translating a plurality of basic blocks of program code comprising:

applying a selection algorithm to identify a group of previously translated basic blocks for translation as a contiguous whole; and

generating an intermediate representation for each basic block of said group.

8. The method of claim 7 wherein the step of applying a selection algorithm comprises checking a profiling metric of previously executed basic block against at least one profiling threshold.

9. The method of claim 8 wherein said profiling metric comprises an execution count.

10. The method of claim 11 wherein said profiling threshold comprises a selected maximum count.

11. The method of claim 7 wherein the step of applying a selection algorithm comprises the steps of:

beginning group block formation wherein a trigger threshold is exceeded; and

selecting additional blocks for inclusion in the group based on an inclusion threshold.

12. The method of claim 11 wherein group block formation is terminated when the number of blocks selected for inclusion in the group block reaches a selected limit.

13. The method of claim 11 wherein additional blocks of the group are selected based on data identifying known successors of a preceding block.

14. The method of claim 13 wherein said data comprises references to basic block objects of known predecessor and successor blocks, said references comprising in the aggregate the control-flow graph of all previously executed basic blocks.

15. The method of claim 7 further including the step of performing an ordering traversal of said group of basic blocks to determine the order in which the blocks of said group will be translated.

16. The method of claim 15 wherein the ordering traversal is performed using an ordered depth-first search algorithm.

17. The method of claim 16 wherein said algorithm orders the blocks based on execution count.

18. The method of claim 15 further comprising the step of performing global dead code elimination on said group block.

19. The method of claim 18 further comprising the step of global register allocation.

21. The method of claim 7 performed as part of a translation process including a control loop comprising the steps of:

executing translator code which translates a first block of subject code into translated code;

executing the translated code;

returning control to the translator code at the end of execution of the translated code; and

executing translator code which translates a second basic block into translated code.

22. The method of claim 19 further including the steps of register allocation and register synchronization.

23. The method of claim 22 wherein the step of register synchronization comprises performing a 10-case register synchronization algorithm.

25. The method of claim 7 wherein said steps are performed by program code stored on a tangible storage medium.

26. The method of claim 10 wherein said steps are performed by program code stored on a tangible storage medium.

27. The method of claim 18 wherein said steps are performed by program code stored on a tangible storage medium.

20. A basic block data structure stored on a computer readable medium comprising:

a subject address;

a target code pointer;

a set of translation hints;

a set of entry conditions;

a set of exit conditions;

a profiling metric;

predecessor block data;

successor block data; and

an entry register map.