Instruction string optimization with estimation of basic block dependence relations where the first step is to remove self-dependent branching

An instruction string optimization apparatus comprising:

• code dividing means for dividing an instruction string comprising serially arranged instructions into sets of basic blocks each of the blocks being a string of sequential instructions having no branch in or branch out in the middle of the string;
• size dependence relation generation means for generating a size dependence relation representing the correspondence between a basic block having a constant to be resolved as an address difference and a depended basic block, the latter basic block being depended on by the former basic block and comprising an instruction string having a size on which the size of said constant depends;
• estimation order determining means for analyzing the size dependence relation and determining the order in which constants to be resolved as an address difference of a basic block are estimated, and for removing self-dependent branching;
• and
• size determining means for determining an unresolved size of said constant to be resolved in a basic block selected according to said estimation order or determining an unresolved size of an instruction which uses said constant to be resolved in a basic block selected according to said estimation order.