Abstract
We describe a new algorithm for parallelization of sequential code that eliminates anti and output dependence8 by renaming registers on an as-needed basis during scheduling. A dataflow attribute at the beginning of each basic block indicates what operations are available for moving up through this basic block. Scheduling consists of choosing the best operation from the set of operations that can move to a point, moving the instances of the operation to the point, making bookkeeping copies for edges that join the moving path but are not on it, and updating the dataflow attributes of basic blocks only on the paths that were traversed by the instances of the moved operations. The code motions are done globally without going through atomic transformations of percolation scheduling, for better eficiency. For performing the code motions, we use an intermediate representation that is directly executable as sequential RISC code, rather than VLIW code. As a result, the new algorithm can be used to generate parallelized code for multiple ALU superscalar processors as well. The enhanced pipeline scheduling algorithm for software pipelining of arbitrary code is reformulated within the framework of the new sequential RISC representation. The new algorithm has been implemented, and preliminary results on AIX utilities indicate that it requires significantly less compilation time than the percolation scheduling approach.