[Bug rtl-optimization/106518] New: Exchange/swap aware register allocation (generate xchg in reload)

["roger at nextmovesoftware dot com" <gcc-bugzilla@gcc.gnu.org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106518

            Bug ID: 106518
           Summary: Exchange/swap aware register allocation (generate xchg
                    in reload)
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: roger at nextmovesoftware dot com
  Target Milestone: ---

This enhacement request is a proposal for improving/tweaking GCC's register
allocation, but assuming/making use of a register exchange/swap operation as a
useful abstraction.  Currently reload/lra is (solely) "move"-based, so when the
contents of regA need to be placed in regB and the original contents of regB
need to be placed in regA, they make use of a temporary register (or a spill)
and generate the classic sequence: tmp=regA; regA=regB; regB=tmp.

A small improvement is to tweak register allocation to assume, as a higher
level abstraction, the existence of an exchange/swap instruction, like x86's
xchg, much like is assummed/used during the reg-stack pass (with i387's fxch). 
[https://gcc.gnu.org/legacy-ml/gcc-patches/2004-12/msg00815.html]

During early register allocation, we introduce virtual exchange operations,
that on can be lowered as a later pass, either to real exchange operations on
targets that support them, or to the standard three-move shuffle sequence
above, if there's a spare suitable temporary register, or alternatively to the
sequence regA^=regB; regB^=regA; regA^=regB, which implements an exchange using
three fast instructions without requiring an additional register.  These three
alternatives guarantee that register allocation is no worse than current, but
has the flexibility to use fewer registers and perhaps fewer instructions.
On modern hardware, xchg is sometimes zero latency (using register renaming),
and on older architectures, a three xor sequence has the same latency as three
moves, but requires on less register, helpfully reducing register pressure.

An example application/benefit of this PR rtl-optimization/97756, which
demonstrates that the x86_64 ABI frequently places (TImode double word)
registers in locations that then neeed the high and low parts to be swapped
(or moved) to place them in the (reg X) and (reg X+1) locations required by
GCC's multi-word register allocation requirements.

Interestingly, GCC's middle-end doesn't have a standard named pattern for an
exchange/swap instruction, i.e. an optab, so currently it has no (easy) way of
deciding whether a target has an xchg-like instruction, which helps explain why
it doesn't currently use/generate them.