Learning to Combine Instructions in LLVM Compiler

Instruction combiner (IC) is a critical compiler optimization pass, which replaces a sequence of instructions with an equivalent and optimized instruction sequence at basic block level. There can be thousands of instruction-combining patterns which need to be frequently updated as new coding styles/idioms/applications and novel hardware evolve over time. This makes the IC optimization pass error prone, incurring high maintenance cost. Prior work has shown that IC pass is the buggiest pass in the LLVM (Low Level Virtual Machine) compiler and the third most buggy pass in GCC (GNU Compiler Collection). To mitigate these challenges associated with the traditional IC, we design and implement a Neural Instruction Combiner {NIC}) and demonstrate its feasibility by integrating it into the standard LLVM compiler optimization pipeline. NIC leverages neural Seq2Seq model techniques for generating optimized encoded IR sequence from the unoptimized encoded IR sequence. We show that NIC achieves exact match results percentage of 72% for optimized sequences as compared to traditional IC, demonstrating its feasibility in a production compiler pipeline.