November 4, 2022
Moving identical computations to common successors or predecessors to reduce code size or improve performance is the basic design principle in classical compiler optimizations like Tail Merging and Code Sinking/Hoisting. These transformations only exploit instruction similarity at the basic block level and require identical instruction sequences to be present, making them less useful in real applications. However, real-world programs contain much more similar (non-identical) instruction sequences within control-flow regions. In this work, we propose Control-flow Melding (CFM), a more general version of tail merging that can merge control-flow at the region level. CFM ’s hierarchical region and instruction alignment approach ensures that it can exploit code similarity maximally to reduce code size and/or improve performance. We implement CFM as LLVM-IR transformation pass and evaluate its effectiveness in reducing control-flow divergence in GPU programs and reducing code size in CPU programs. Our evaluation shows that CFM is effective as a general compiler transformation pass and worthy of being integrated into a modern compiler pipeline.
About Charitha Saumya
Charitha Saumya is a PhD candidate in the Elmore School of Electrical and Computer Engineering at Purdue University. His current research is focused on developing targeted compiler transformations to improve performance and reliability of programs with irregular control-flow.