Generalized instruction selection using SSA-graphs

Instruction selection is a well-studied compiler phase that trans-lates the compiler’s intermediate representation of programs to a sequence of target-dependent machine instructions optimizing for various compiler objectives (e.g. speed and space). Most existing instruction selection techniques are limited to the scope of a single statement or a basic block and cannot cope with irregular instruc-tion sets that are frequently found in embedded systems. We consider an optimal technique for instruction selection that uses Static Single Assignment (SSA) graphs as an intermediate representation of programs and employs the Partitioned Boolean Quadratic Problem (PBQP) for finding an optimal instruction se-lection. While existing approaches are limited to instruction pat-terns that can be expressed in a simple tree structure, we con-sider complex patterns producing multiple results at the same time including pre/post increment addressing modes, div-mod in-structions, and SIMD extensions frequently found in embedded systems. Although both instruction selection on SSA-graphs and PBQP are known to be NP-complete, the problem can be solved efficiently- even for very large instances. Our approach has been implemented in LLVM for an embedded ARMv5 architecture. Extensive experiments show speedups of up to 57 % on typical DSP kernels and up to 10 % on SPECINT 2000 and MiBench benchmarks. All of the test programs could be com-piled within less than half a minute using a heuristic PBQP solver that solves 99.83 % of all instances optimally