OPTIMAL CODE GENERATION FOR EXPRESSIONS ON SUPER SCALAR MACHINES.

Abstract

The problem of generating optimal code to evaluate expression trees under varied assumptions of the underlying execution model is considered. A RISC-style load/store instruction set architecture is assumed throughout. Initially, a simple nonpipelined, serial execution model with N registers is considered. The machine model is then modified to allow pipelined execution of a single instruction stream. Finally, a decoupled access/execute model is considered, in which each (decoupled) unit is pipelined. Concepts of optimum register allocation and code scheduling are combined into a single, efficient, tree-walk algorithm.