Generalized instruction selection using SSA-graphs

Instruction selection is a well-studied compiler phase that translatesthe compiler's intermediate representation of programs to asequence of target-dependent machine instructions optimizing forvarious compiler objectives (e.g. speed and space). Most existinginstruction selection techniques are limited to the scope of a singlestatement or a basic block and cannot cope with irregular instructionsets that are frequently found in embedded systems.We consider an optimal technique for instruction selection thatuses Static Single Assignment (SSA) graphs as an intermediaterepresentation of programs and employs the Partitioned BooleanQuadratic Problem (PBQP) for finding an optimal instruction selection.While existing approaches are limited to instruction patternsthat can be expressed in a simple tree structure, we considercomplex patterns producing multiple results at the sametime including pre/post increment addressing modes, div-mod instructions,and SIMD extensions frequently found in embeddedsystems. Although both instruction selection on SSA-graphs andPBQP are known to be NP-complete, the problem can be solvedefficiently - even for very large instances.Our approach has been implemented in LLVM for an embeddedARMv5 architecture. Extensive experiments show speedups of upto 57% on typical DSP kernels and up to 10% on SPECINT 2000and MiBench benchmarks. All of the test programs could be compiledwithin less than half a minute using a heuristic PBQP solverthat solves 99.83% of all instances optimally.