TreeSeq: Register Pressure Aware Instruction Selection and Scheduling Based on Tree Pattern Matching

As the gap between CPU and memory speeds continues to widen, optimizing register usage in high performance processors becomes increasingly important. While many exact algorithms and heuristic techniques have been proposed to reduce register pressure via instruction scheduling, there are two critical challenges. Challenge-1: these approaches often struggle to balance the quality of generated code with compilation time. Challenge-2: their scheduling decisions may detrimentally affect instruction selection outcomes. In this paper, we propose a multi-phase integrated method of instruction selection and scheduling based on tree pattern matching called TreeSeq, which aims to reduce register pressure. TreeSeq first converts the intermediate representation into a set of as large expression trees as possible. It then reduces register pressure through two phases: Sethi-Ullman algorithm-based expression tree node ordering and heuristic expression tree scheduling. Finally, it applies tree pattern matching to these expression trees. TreeSeq ensures the quality of the generated code while reducing compilation time by splitting the classical instruction scheduling into two phases. It also generates more optimized code and further improves compilation time by integrating instruction scheduling into instruction selection. Our evaluation shows that TreeSeq achieves up to a 1.37x speedup on the SysY2022 benchmark. It reduces register pressure comparably to exact methods while saving an average of 57.19% in compilation time. Moreover, TreeSeq generates more optimized code than decoupled approaches of doing instruction selection and scheduling in two separate phases, with 34.32% average time savings.