Using a lookahead window in a compaction-based parallelizing compiler

Lookahead is a common technique for high performance uniprocessor design. In general, however, hardware lookahead window is too small to exploit instruction-level parallelism at run time, while compaction-based parallelizing compilers must suffer from worst-case exponential code explosion at compile time. In this paper, we propose a software lookahead method, which allows inter-basic block code motions within the prespecified number of operations, called software lookahead window, on any path emanating from the currently processed instruction at compile time. By software lookahead, instruction-level parallelism can be exploited in a much greater code area than the hardware approach, but the lookahead region is still limited to a constant depth with a user-specifiable window, and thus code explosion is restricted. The proposed scheme has been implemented in our prototype parallelizing compiler, which can generate code for uniprocessors with multiple functional units and multiway conditional branches, such as VLIW machines, and potentially for superscalars as well. To study 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, with software lookahead, code explosion problem is effectively alleviated, yet a substantial amount of inter-basic block parallelism is successfully extracted.