REFIT: Improve Code Efficiency via Binary Level Loop Optimization

Efficient codes with high performance and compact size are the endless pursuit in computer systems, ranging from cloud servers to embedded devices. As the vastly predominated structure in programs, loops have been laboriously transformed by compilers at intermediate representation (IR) stage with heuristic-based unrolling. Nonetheless, IR level loop optimizations are typically sub-optimal considering that IR stage lacks machine details and heuristic strategies are generally approximation-based. As such, the loop unrolling can be continued or reverted in the subsequent binary stage. With the insight, this paper is motivated to have the design REFIT, which performs binary level transformations to refit the IR level loop revisions with the final machine. Overall, REFIT first analyzes the binary codes to locate and dissect loops in terms of iterations and unrolling factors, and then strives to further unroll with enlarged factors to accelerate execution. Whereas promising to raise performance, aggressive unrolling may greatly expand code size, which potentially constraints program executions. To strike a performance-size balance, REFIT is thus further enhanced to incorporate profiling statistics to have twofold unrolling/rolling optimizations based on the identified loop characteristics. For implementation, we build the prototype based on BOLT, the de facto binary optimizer, and evaluate on representative workloads of Polybench, MiBench and SPEC. Experimental results show that REFIT achieves an average of 1.4 % (up to 11.9 %) performance improvement, with moderate code size expansion.