Compiler capable of partitioning program and program partitioning method

1. A compiler comprising:

Processor and memory;

a partitioning unit operative to partition an input program into cache blocks having a size within a predetermined size limit, wherein the partitioning unit comprises:

a subgraph detector operative to identify, in a path representing an order of processing instruction sequences forming the input program, a subgraph including a sequence of instructions that includes only one instruction at an entry and only one instruction at an exit;

and an extractor operative:

(i) to extract, from the subgraph, an instruction sequence of a maximum total size within the size limit as a new cache block, (ii) to substitute the extracted instruction sequence in the subgraph with an instruction for calling the source instruction sequence in the new cache block, (iii) to repeat the extraction and substitution until a size of the subgraph becomes smaller than or equal to the size limit, (iv) to extract the subgraph from the input program, (v) to substitute the extracted subgraph in the input program with an instruction for calling the extracted subgraph, (vi) to determine that each instruction sequence extracted from the subgraph as a respective cache block, (vii) to determine that the subgraph remaining after extracting the instruction sequence(s) is a further cache block, and (viii) to determine that the input program remaining after extracting the subgraph is a still further cash block;

(ix) to extract one or more of the nodes and generate a new control flow graph including the at least one basic block included in the one or more extracted nodes; and (x) to count a number of times that each basic block included in the program is extracted, and any of the nodes that include a basic block extracted a smaller number of times is given preference to other nodes for extraction that have been extracted a higher number of times;

a code generator operative to generate respective object code for each cache block determined by the extractor of the partitioning unit.

2. The compiler according to claim 1 , wherein the compiler further comprises a control flow graph generator operative to generate a control flow graph from the input program, the subgraph detector identifies a range in the subgraph, the range being defined by nodes each including at least one basic block forming the control flow graph.

3. The compiler according to claim 1 , wherein of the subgraphs included in the program, the subgraph detector identifies an atomic subgraph that does not include another subgraph.

4. The compiler according to claim 2 , wherein the extractor is operative to identify a range of linear node sequence included in the subgraph and extract a node set that is included in the range, continuous with a node selected from the nodes within the range, and of a maximum total size within the size limit.

5. The compiler according to claim 2 , further comprising:

a node substitution unit operative to substitute a single node for the subgraph identified by the subgraph detector and the range of linear node sequence identified by the extractor, wherein the subgraph detector is operative to further identify a subgraph in the control flow graph where substitution is performed by the node substitution unit.

6. A program partitioning method comprising:

reading a program stored in a memory, and identifying, in a path representing an order of processing instruction sequences forming the program, a subgraph including a sequence of instructions that includes only one instruction at an entry and only one instruction at an exit;

an extraction operation configured to:

(i) to extract, from the subgraph, an instruction sequence of a maximum total size within the size limit as a new cache block, (ii) to substitute the extracted instruction sequence in the subgraph with an instruction for calling the source instruction sequence in the new cache block, (iii) to repeat the extraction and substitution until a size of the subgraph becomes smaller than or equal to the size limit, (iv) to extract the subgraph from the input program, (v) to substitute the extracted subgraph in the input program with an instruction for calling the extracted subgraph, (vi) to determine that each instruction sequence extracted from the subgraph as a respective cache block, (vii) to determine that the subgraph remaining after extracting the instruction sequence(s) is a further cache block, and (viii) to determine that the input program remaining after extracting the subgraph is a still further cash block;

(ix) to extract one or more of the nodes and generate a new control flow graph including the at least one basic block included in the one or more extracted nodes; and

(x) to count a number of times that each basic block included in the program is extracted, and any of the nodes that include a basic block extracted a smaller number of times is given preference to other nodes for extraction that have been extracted a higher number of times;

storing as program blocks, the program blocks extracted from the subgraph, the subgraph remaining after extracting the instruction sequences, and the program remaining after extracting the subgraph in the memory.

7. A non-transitory, computer readable storage medium containing a computer program, comprising:

a module operative to read a program from a memory;

a module operative to identify, in a path representing an order of processing instruction sequences forming the program, a subgraph including a sequence of instructions that includes only one instruction at an entry and only one instruction at an exit;

an extraction module configured:

(i) to extract, from the subgraph, an instruction sequence of a maximum total size within the size limit as a new cache block, (ii) to substitute the extracted instruction sequence in the subgraph with an instruction for calling the source instruction sequence in the new cache block, (iii) to repeat the extraction and substitution until a size of the subgraph becomes smaller than or equal to the size limit, (iv) to extract the subgraph from the input program, (v) to substitute the extracted subgraph in the input program with an instruction for calling the extracted subgraph, (vi) to determine that each instruction sequence extracted from the subgraph as a respective cache block, (vii) to determine that the subgraph remaining after extracting the instruction sequence(s) is a further cache block, and (viii) to determine that the input program remaining after extracting the subgraph is a still further cash block;

(ix) to extract one or more of the nodes and generate a new control flow graph including the at least one basic block included in the one or more extracted nodes; and (x) to count a number of times that each basic block included in the program is extracted, and any of the nodes that include a basic block extracted a smaller number of times is given preference to other nodes for extraction that have been extracted a higher number of times;

a module operative to store, as program blocks, the program blocks extracted from the subgraph, the subgraph remaining after extracting the instruction sequences, and the program remaining after extracting the subgraph in the memory.