An optimization apparatus is capable of improving the execution efficiency of a loop that includes a loop carry dependency between consecutive iterations of the loop. For example, a value resulting from one iteration is used in an immediately following iteration. When the arithmetic expression “a[i+1]=a[i]*3+2;” is included in a loop body, and a value resulting from the arithmetic expression “a[i+1]=a[i]*3+2;” in one iteration is used in a following iteration, execution delays occur in pipeline processing of the loop. Here, the arithmetic expression “a[i+1]=a[i]*3+2;” is transformed into the arithmetic expression “a[i+4]=a[i]*81+80;” to expand the dependency distance. By doing so, the execution delays can be decreased.