Jump Minimization in Linear Time

Abstract

Unlike other instructions, which compute or test values, unconditional branch instructions do no useful work.Rather, they are artifacts of the translation from a flow graph to the linear form of conventional machine language.Careful ordering of the basic blocks of a program can decrease the number of branches required by allowing a basic block to "fall through" to a successor.It is shown that although the general problem of minimizing the number of branches is NP-complete, an efficient algorithm is possible for "structured" programs--those written without goto statements.More specifically, an algorithm is presented that produces an optimal ordering of the basic blocks of any program that uses only the control structures if-then-else, loop, and exit.The running time of the algorithm is proportional to the length of the program, provided the number of loops exited by any exit statement can be bounded by a constant.