Code duplication: An assist for global instruction scheduling

The recent appearance of supersca/ar machines (like IBM RISC System/6000, Intel i860, etc.) dictates that instruction scheduling must be done by the compiler well beyond the basic block boundaries. Moreover, when performing global instruction scheduling of the program, to further enhance the performance of the generated code, techniques which include speculative execution, duplication of code, software pipelining, etc. must be employed. Recently, a scheme for such global instruction scheduling was proposed in [BR91]. Here we describe an efficient technique for supporting duplication of code in the presence of a (general) acyclic control flow, as required by the global instruction scheduling framework. The algorithms have been implemented in the context of the IBM XL family of compilers, and we are in process of evaluating them on the IBM RISC System/6000 machines.