Making Compaction-Based Parallelization Affordable

Abstract

Compaction-based parallelization suffers from long compile time and large code size because of its inherent code explosion problem. If software pipelining is performed for loop parallelization along with compaction, as in our compiler, the code explosion problem becomes more serious. In this paper, we propose the software lookahead heuristic for use in software pipelining, which allows inter-basic-block movement of code within a prespecified number of operations, called the software lookahead window, on any path emanating from the currently processed instruction at compile time. Software lookahead enables instruction-level parallelism to be exploited in a much greater code area than a single basic block, but the lookahead region is still limited to a constant depth by means of a user-specifiable window, and thus code explosion is restricted. The proposed scheme has been implemented in our VLIW parallelizing compiler. To study the code explosion problem and instruction-level parallelism for branch-intensive code, we compiled five AIX utilities: sort, fgrep, sed, yacc, and compress. It is demonstrated that the software lookahead heuristic effectively alleviates the code explosion problem while successfully extracting a substantial amount of inter-basic-block parallelism. © 1993 IEEE