Method and a device for abstracting instruction sequences with tail merging

Abstract

A method and a device for abstracting instruction sequences in a computer program. First, a control flow graph of the program is generated and analysed in order to detect multiple occurrences of a same instruction sequence ( 504, 506 ). Then, a function including the longest sequence common to at least two instruction sequences from a plurality of sequences having a common instruction sequence of equal or shorter length compared to the longest sequence is created ( 512 ). Finally, the original occurrences of the instruction sequences in the plurality of sequences with a reference to a proper position in the newly created function are deleted and a reference to a proper position in the created function inserted instead ( 514 ).

1. A method comprising:
 creating a control flow graph of a computer program having instruction sequences, said control flow graph including basic blocks of instructions, each basic block having a last instruction, 
 traversing through the basic blocks in order to detect multiple occurrences of a same instruction sequence which includes said last instruction for each of at least two basic blocks, 
 creating a function including a longest sequence of last instruction sequences common to said at least two basic blocks and which includes said last instruction for each of said at least two basic blocks, said longest sequence from a plurality of sequences of last instruction sequences common to said at least two basic blocks and having a common instruction sequence of equal or shorter length compared to said longest sequence, said longest sequence including the equal or shorter length sequences of said plurality of sequences, and 
 replacing the original occurrences of said instruction sequences in said plurality of sequences with a reference to a proper position in said created function. 
 
     
     
       2. A method of  claim 1 , wherein the blocks are traversed in a direction opposite to execution of said blocks. 
     
     
       3. A method of  claim 1 , wherein said proper position is the position from which onward the sequence in the function matches with the original occurrence of the replaced instruction sequence. 
     
     
       4. A method of  claim 1 , wherein said reference is substantially a function call or a branch instruction. 
     
     
       5. A method of  claim 1 , wherein said created function contains substantially the at least two basic blocks whereto said longest sequence belongs. 
     
     
       6. A method of  claim 1 , wherein after creating the flow graph said basic blocks are divided into a plurality of block sets, said blocks in different sets comprising no common instruction sequences. 
     
     
       7. A storage medium carrying a computer executable program for carrying out the method of  claim 1 . 
     
     
       8. A computer program product comprising code stored on a readable storage medium for execution by a processing unit so as to carry out:
 creating a control flow graph of a computer program having instruction sequences, said control flow graph including basic blocks of instructions, each basic block having a last instruction, 
 traversing through the basic blocks in order to detect multiple occurrences of a same instruction sequence which includes said last instruction for each of at least two basic blocks, 
 creating a function including a longest sequence of last instruction sequences common to said at least two basic blocks and which includes said last instruction for each of said at least two basic blocks, said longest sequence from a plurality of sequences of last instruction sequences common to said at least two basic blocks and having a common instruction sequence of equal or shorter length compared to said longest sequence, said longest sequence including the equal or shorter length sequences of said plurality of sequences, and 
 replacing the original occurrences of said instruction sequences in said plurality of sequences with a reference to a proper position in said created function. 
 
     
     
       9. An electronic device comprising:
 a processing unit, 
 a memory for storing instructions and data, and 
 a data transfer module for accessing data, 
 said device arranged to create a control flow graph of a computer program having instruction sequences, said control flow graph including basic blocks of instructions, each basic block having a last instruction, said device further arranged to traverse through the basic blocks in order to detect multiple occurrences of a same instruction sequence which includes said last instruction for each of at least two basic blocks, to create a function including a longest sequence of last instruction sequences common to said at least two basic blocks and which includes said last instruction for each of said at least two basic blocks, said longest sequence from a plurality of sequences having a common instruction sequence of equal or shorter length compared to said longest sequence, said longest sequence including the equal or shorter length sequences of said plurality of sequences and to replace the original occurrences of said instruction sequences in said plurality of sequences with a reference to a proper position in said created function. 
 
     
     
       10. The electronic device of  claim 9  further arranged so that the blocks are traversed in a direction opposite to execution of said blocks. 
     
     
       11. The electronic device of  claim 9 , arranged so that said proper position is the position from which onward the sequence in the function matches the original occurrence of the replaced instruction sequence. 
     
     
       12. The electronic device of  claim 9 , arranged so that said reference is substantially a function call or a branch instruction. 
     
     
       13. The electronic device of  claim 9 , arranged so that said created function contains substantially the at least two basic blocks whereto said longest sequence belongs. 
     
     
       14. The electronic device of  claim 9 , arranged so that after creating the flow graphs said basic blocks are divided into a plurality of block sets, said blocks in different sets comprising no common instruction sequences. 
     
     
       15. An electronic device comprising:
 means for processing, 
 means for storing instructions and data, and 
 means for accessing data, 
 said device arranged to create a control flow graph of a computer program having instruction sequences, said control flow graph including basic blocks of instructions, each basic block having a last instruction, said device further arranged to traverse through the basic blocks in order to detect multiple occurrences of a same instruction sequence which includes said last instruction for each of at least two basic blocks, to create a function including a longest sequence of last instruction sequences common to said at least two basic blocks and which includes said last instruction for each of said at least two basic blocks, said longest sequence from a plurality of sequences having a common instruction sequence of equal or shorter length compared to said longest sequence, said longest sequence including the equal or shorter length sequences of said plurality of sequences and to replace the original occurrences of said instruction sequences in said plurality of sequences with a reference to a proper position in said created function. 
 
     
     
       16. The electronic device of  claim 15 , wherein the blocks are traversed in a direction opposite to execution of said blocks.