HyBF: A Hybrid Branch Fusion Strategy for Code Size Reduction

Binary code size is a first-class design consideration in many computing domains and a critical factor in many more, but compiler optimizations targeting code size are few and often limited in functionality. When size reduction opportunities are left unexploited, it results in higher downstream costs such as memory, storage, bandwidth, or programmer time. We present HyBF, a framework to manage code merging techniques that target conditional branches (i.e., if-then-else) with similar code regions on both paths. While such code can be easily and profitably merged with little control flow overhead, existing techniques generally fail to fully handle it. Our work is inspired by branch fusion, a technique for merging similar code in if-then-else statements, which is aimed at reducing thread divergence in GPUs. We introduce two new branch fusion techniques that can be applied to almost any if-then-else statement and can uncover many more code merging opportunities. The two approaches are mostly orthogonal and have different limitations and strengths. We integrate them into a single framework, HyBF, which can choose the optimal approach on a per branch basis to maximize the potential of reducing code size. Our results show that we can achieve significant code savings on top of already heavily optimized binaries using state-of-the-art code size optimizations. Over 61 benchmarks, we reduce the code size on 43 of them. That reduction typically ranges from a few hundred to a few thousand bytes, but for specific benchmarks, it can be substantial and as high as 4.2% or 67 KB.