This paper is in the area of compiler optimizations for processors, such as very long instruction word (VLIW) and super scalar, processors which exploit instruction-level parallelism. A well-known technique is software pipelining of loops in the input programs. The paper presents a solution for the problem of software pipelining of loops with control flows in the loop bodies.

The first section of the paper introduces the problem. Section 2 contains the theoretical background. The program representation used is the extended sequential representation. After a description of the basic terminology, the dependence model, containing the definition of the “dependence chains” is described. Software pipelining is then formalized by presenting six constraints, in the third section. The theorems and proofs related to the conditions, and computations of the time optimality, are described in the fourth section.

Section 5 describes the “time optimal software pipelining algorithm.” This section also proves the time optimality of the algorithm. The major approach of the algorithm is to first unroll the sequential loop into an infinite control flow graph (CFG), and to then apply the percolation scheduling, leading the infinite CFG to a finite parallel graph. The sixth section describes the “practical software pipelining algorithm.” Here, a CFG is transformed into a nondeterministic CFG (NCFG). Section 7 presents the results of four related experiments. After the paper’s conclusion, in the eighth section, various algorithms are presented in appendices.

The paper establishes a theoretical foundation for the software pipelining of loops with control flows. It can be used for further related research by researchers working in the area. Some research students, especially those developing theories for practical problems, may find the style and organization of the paper demonstrative. Since the paper is specialized, it is not recommended for readers who are not interested in this subject area.