Patent ID: 8645910
Filing Date: 2014-02-04
Classification: G06F

Abstract:
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.