Assessing the Performance Effects of Adding New Synthesized Rewrite Rules to Halide

<p>Halide is a programming language that facilitates writing high-performance image processing pipelines. Its compiler internally uses a Term Rewriting System (TRS) in order to simplify complex expressions, which comprises over a thousand handwritten rewrite rules added by human compiler engineers. In order to strengthen the TRS by finding new rules that can rewrite input expressions that the TRS currently fails to simplify, a synthesizer was used to automatically generate 4127 verifiably sound rules. Experiments have shown that adding these rules lowers peak memory usage by up to 50%, while having relatively insignificant impact on runtime performance. However, adding every such rule increases compile-time and compiler code size. This project aims to address this problem by incrementally testing and assessing each rule and subsets of the rules, while adding them to the compiler only if they necessarily contribute to the peak memory reductions shown in the experiment or other improvements in performance.</p>