Editing XOR swap algorithm (section)

== Application to register allocation ==

On architectures lacking a dedicated swap instruction, because it avoids the extra temporary register, the XOR swap algorithm is required for optimal [[register allocation]]. This is particularly important for [[compilers]] using [[static single assignment form]] for register allocation; these compilers occasionally produce programs that need to swap two registers when no registers are free. The XOR swap algorithm avoids the need to reserve an extra register or to spill any registers to main memory.<ref>{{cite book |last1=Pereira |first1=Fernando Magno Quintão |last2=Palsberg |first2=Jens |chapter=SSA Elimination after Register Allocation |title=Compiler Construction |series=Lecture Notes in Computer Science |date=2009 |volume=5501 |pages=158–173 |doi=10.1007/978-3-642-00722-4_12 |isbn=978-3-642-00721-7 |chapter-url=http://compilers.cs.ucla.edu/fernando/publications/papers/CC09.pdf |access-date=17 April 2022}}</ref> The addition/subtraction variant can also be used for the same purpose.<ref>{{cite book |last1=Hack |first1=Sebastian |last2=Grund |first2=Daniel |last3=Goos |first3=Gerhard |chapter=Register Allocation for Programs in SSA-Form |title=Compiler Construction |series=Lecture Notes in Computer Science |date=2006 |volume=3923 |pages=247–262 |doi=10.1007/11688839_20|isbn=978-3-540-33050-9 |doi-access=free }}</ref>

This method of register allocation is particularly relevant to [[GPU]] shader compilers. On modern GPU architectures, spilling variables is expensive due to limited memory bandwidth and high memory latency, while limiting register usage can improve performance due to dynamic partitioning of the [[register file]]. The XOR swap algorithm is therefore required by some GPU compilers.<ref>{{cite web |last1=Abbott |first1=Connor |last2=Schürmann |first2=Daniel |title=SSA-based Register Allocation for GPU Architectures |url=https://indico.freedesktop.org/event/1/contributions/7/attachments/8/11/SSA-based%20Allocation%20for%20GPU%20Architectures.pdf |access-date=17 April 2022}}</ref>