Instruction scheduling for RISC processors

Abstract

Instruction scheduling is the process of reordering instructions (whether assembly code or code in some other form) so as to make fuller use of the resources provided by the processor. In the case of RISC processors, resources include pipelines, multiple functional units, a large register set, delayed loads etc. In this thesis, we have looked at two different instruction scheduling problems. The first problem deals with code generation with instruction chaining. Instruction chaining is a feature found in many vector machines and Intel's i860 and speeds up vector computations. We have considered the problem of generating code from directed acyclic graphs (DAGs) with instruction chaining. For this problem, optimal code generation is NP-complete. Hence we have designed a heuristic and have shown that it produces good code in practice by comparing it with the code produced by other methods. The second problem deals with generating optimal code from expression trees for delayed-load architectures with unit latency times. We have generalized an existing algorithm so as to handle register variables. We give proofs of optimality for the length of the code sequence as well as for register usage. Spilling is also handled optimally. This method is useful in optimizing the code for the integer units of the SPARC and MIPS processors. It serves as a good heuristic for longer latency times and for code generation from DAGs.