  During compilation of a program, register allocation is the task of mapping
program variables to machine registers. During register allocation, the
compiler may introduce shuffle code, consisting of copy and swap operations,
that transfers data between the registers. Three common sources of shuffle code
are conflicting register mappings at joins in the control flow of the program,
e.g, due to if-statements or loops; the calling convention for procedures,
which often dictates that input arguments or results must be placed in certain
registers; and machine instructions that only allow a subset of registers to
occur as operands. Recently, Mohr et al. proposed to speed up shuffle code with
special hardware instructions that arbitrarily permute the contents of up to
five registers and gave a heuristic for computing such shuffle codes. In this
paper, we give an efficient algorithm for generating optimal shuffle code in
the setting of Mohr et al. An interesting special case occurs when no register
has to be transferred to more than one destination, i.e., it suffices to
permute the contents of the registers. This case is equivalent to factoring a
permutation into a minimal product of permutations, each of which permutes up
to five elements.
