XOR swap algorithm - Revision history

Citation bot: Alter: title, template type. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Articles with example C code | #UCB_Category 35/199

2024-10-25T11:50:41Z

Alter: title, template type. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Articles with example C code | #UCB_Category 35/199

← Previous revision		Revision as of 11:50, 25 October 2024
Line 155:		Line 155:
	== Application to register allocation ==		== 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 ~~journal~~ \|last1=Pereira \|first1=Fernando Magno Quintão \|last2=Palsberg \|first2=Jens \|~~title~~=SSA Elimination after Register Allocation \|~~journal~~=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 \|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 ~~journal~~ \|last1=Hack \|first1=Sebastian \|last2=Grund \|first2=Daniel \|last3=Goos \|first3=Gerhard \|~~title~~=Register Allocation for Programs in SSA-Form \|~~journal~~=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>		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>		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>

Mengzhuo at 10:26, 14 October 2024

2024-10-14T10:26:31Z

← Previous revision		Revision as of 10:26, 14 October 2024
Line 19:		Line 19:
	{\| class="wikitable" style="width: 45em;"		{\| class="wikitable" style="width: 45em;"
	\|-		\|-
	! Pseudocode !! IBM [[System/370]] assembly !! x86 assembly		! Pseudocode !! IBM [[System/370]] assembly !! x86 assembly !! RISC-V assembly
	\|-		\|-
	\| {{code\|1=X := X XOR Y\|2=pascal}} \|\| {{code\|1=XR R1,R2\|2=asm}} \|\| {{code\|1=xor eax, ebx\|2=asm}}		\| {{code\|1=X := X XOR Y\|2=pascal}} \|\| {{code\|1=XR R1,R2\|2=asm}} \|\| {{code\|1=xor eax, ebx\|2=asm}} \|\| {{code\|1=xor x10, x11 \|2=asm}}
	\|-		\|-
	\| {{code\|1=Y := Y XOR X\|2=pascal}} \|\| {{code\|1=XR R2,R1\|2=asm}} \|\| {{code\|1=xor ebx, eax\|2=asm}}		\| {{code\|1=Y := Y XOR X\|2=pascal}} \|\| {{code\|1=XR R2,R1\|2=asm}} \|\| {{code\|1=xor ebx, eax\|2=asm}} \|\| {{code\|1=xor x11, x10 \|2=asm}}
	\|-		\|-
	\| {{code\|1=X := X XOR Y\|2=pascal}} \|\| {{code\|1=XR R1,R2\|2=asm}} \|\| {{code\|1=xor eax, ebx\|2=asm}}		\| {{code\|1=X := X XOR Y\|2=pascal}} \|\| {{code\|1=XR R1,R2\|2=asm}} \|\| {{code\|1=xor eax, ebx\|2=asm}} \|\| {{code\|1=xor x10, x11 \|2=asm}}
	\|}		\|}

	In the above System/370 assembly code sample, R1 and R2 are distinct [[processor register\|register]]s, and each {{code\|XR\|2=asm}} operation leaves its result in the register named in the first argument. Using x86 assembly, values X and Y are in registers eax and ebx (respectively), and {{code\|xor\|2=asm}} places the result of the operation in the first register.		In the above System/370 assembly code sample, R1 and R2 are distinct [[processor register\|register]]s, and each {{code\|XR\|2=asm}} operation leaves its result in the register named in the first argument. Using x86 assembly, values X and Y are in registers eax and ebx (respectively), and {{code\|xor\|2=asm}} places the result of the operation in the first register. In RISC-V assembly, value X and Y are in registers X10 and X11, and {{code\|xor\|2=asm}} places the result of the operation in the first register (same as X86)

	However, in the pseudocode or high-level language version or implementation, the algorithm fails if ''x'' and ''y'' use the same storage location, since the value stored in that location will be zeroed out by the first XOR instruction, and then remain zero; it will not be "swapped with itself". This is ''not'' the same as if ''x'' and ''y'' have the same values. The trouble only comes when ''x'' and ''y'' use the same storage location, in which case their values must already be equal. That is, if ''x'' and ''y'' use the same storage location, then the line:		However, in the pseudocode or high-level language version or implementation, the algorithm fails if ''x'' and ''y'' use the same storage location, since the value stored in that location will be zeroed out by the first XOR instruction, and then remain zero; it will not be "swapped with itself". This is ''not'' the same as if ''x'' and ''y'' have the same values. The trouble only comes when ''x'' and ''y'' use the same storage location, in which case their values must already be equal. That is, if ''x'' and ''y'' use the same storage location, then the line:

93.175.2.149 at 14:04, 22 March 2024

2024-03-22T14:04:35Z

← Previous revision		Revision as of 14:04, 22 March 2024
Line 131:		Line 131:
	void AddSwap( unsigned int* x, unsigned int* y )		void AddSwap( unsigned int* x, unsigned int* y )
	{		{
	if (x != y)
	{
	x = x + *y;		x = x + *y;
	y = x - *y;		y = x - *y;
	x = x - *y;		x = x - *y;
	}
	}		}
	</syntaxhighlight>		</syntaxhighlight>

87.227.12.223: Corrected which variables the results are assigned to.

2024-01-03T18:39:46Z

Corrected which variables the results are assigned to.

← Previous revision		Revision as of 18:39, 3 January 2024
Line 10:		Line 10:

	<syntaxhighlight lang="pascal">		<syntaxhighlight lang="pascal">
	X := Y XOR X; // XOR the values and store the result in Y		X := Y XOR X; // XOR the values and store the result in X
	Y := X XOR Y; // XOR the values and store the result in X		Y := X XOR Y; // XOR the values and store the result in Y
	X := Y XOR X; // XOR the values and store the result in Y		X := Y XOR X; // XOR the values and store the result in X
	</syntaxhighlight>		</syntaxhighlight>

76.116.204.3: /* The algorithm */

2023-12-23T04:37:12Z

The algorithm

← Previous revision		Revision as of 04:37, 23 December 2023
Line 10:		Line 10:

	<syntaxhighlight lang="pascal">		<syntaxhighlight lang="pascal">
	X := X XOR Y; // XOR the values and store the result in X		X := Y XOR X; // XOR the values and store the result in Y
	Y := Y XOR X; // XOR the values and store the result in Y		Y := X XOR Y; // XOR the values and store the result in X
	X := X XOR Y; // XOR the values and store the result in X		X := Y XOR X; // XOR the values and store the result in Y
	</syntaxhighlight>		</syntaxhighlight>

Uhai: Adding local short description: "Binary arithmetic algorithm", overriding Wikidata description "Simple algorithm to swap binary values"

2023-11-21T23:14:03Z

Adding local short description: "Binary arithmetic algorithm", overriding Wikidata description "Simple algorithm to swap binary values"

← Previous revision		Revision as of 23:14, 21 November 2023
Line 1:		Line 1:
			{{Short description\|Binary arithmetic algorithm}}
	[[Image:XOR Swap.svg\|thumb\|upright=2\|alt=With three XOR operations the binary values 1010 and 0011 are exchanged between variables.\|Using the XOR swap algorithm to exchange [[nibble]]s between variables without the use of temporary storage]]		[[Image:XOR Swap.svg\|thumb\|upright=2\|alt=With three XOR operations the binary values 1010 and 0011 are exchanged between variables.\|Using the XOR swap algorithm to exchange [[nibble]]s between variables without the use of temporary storage]]

OAbot: Open access bot: doi updated in citation with #oabot.

2023-08-24T05:58:12Z

Open access bot: doi updated in citation with #oabot.

← Previous revision		Revision as of 05:58, 24 August 2023
Line 157:		Line 157:
	== Application to register allocation ==		== 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 journal \|last1=Pereira \|first1=Fernando Magno Quintão \|last2=Palsberg \|first2=Jens \|title=SSA Elimination after Register Allocation \|journal=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 \|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 journal \|last1=Hack \|first1=Sebastian \|last2=Grund \|first2=Daniel \|last3=Goos \|first3=Gerhard \|title=Register Allocation for Programs in SSA-Form \|journal=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 }}</ref>		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 journal \|last1=Pereira \|first1=Fernando Magno Quintão \|last2=Palsberg \|first2=Jens \|title=SSA Elimination after Register Allocation \|journal=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 \|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 journal \|last1=Hack \|first1=Sebastian \|last2=Grund \|first2=Daniel \|last3=Goos \|first3=Gerhard \|title=Register Allocation for Programs in SSA-Form \|journal=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>		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>

Niokog: /* Code example */ simplified/flatted code with a guard clause

2023-08-23T11:02:28Z

Code example: simplified/flatted code with a guard clause

← Previous revision		Revision as of 11:02, 23 August 2023
Line 97:		Line 97:
	void XorSwap(int x, int y)		void XorSwap(int x, int y)
	{		{
	if (x != y)		if (x == y) return;
		⚫	x ^= y;
	{
	x ^= y;		y ^= x;
	y ^= x;		x ^= y;
⚫	x ^= y;
	}
	}		}
	</syntaxhighlight>		</syntaxhighlight>
	The code first checks if the addresses are distinct. ~~Otherwise~~, if they were equal, the algorithm would fold to a triple <code>x ^= x</code> resulting in zero.		The code first checks if the addresses are distinct and uses a [[Guard (computer science)#Flatter code with less nesting\|guard clause]] to exit the function early if they are equal. Without that check, if they were equal, the algorithm would fold to a triple <code>x ^= x</code> resulting in zero.

	The XOR swap algorithm can also be defined with a macro:		The XOR swap algorithm can also be defined with a macro:

Maggyero: /* Aliasing */

2023-04-16T21:38:11Z

Aliasing

← Previous revision		Revision as of 21:38, 16 April 2023
Line 124:		Line 124:
	The XOR swap is also complicated in practice by [[aliasing (computing)\|aliasing]]. If an attempt is made to XOR-swap the contents of some location with itself, the result is that the location is zeroed out and its value lost. Therefore, XOR swapping must not be used blindly in a high-level language if aliasing is possible. This issue does not apply if the technique is used in assembly to swap the contents of two registers.		The XOR swap is also complicated in practice by [[aliasing (computing)\|aliasing]]. If an attempt is made to XOR-swap the contents of some location with itself, the result is that the location is zeroed out and its value lost. Therefore, XOR swapping must not be used blindly in a high-level language if aliasing is possible. This issue does not apply if the technique is used in assembly to swap the contents of two registers.

	Similar problems occur with [[call by name]], as in [[Jensen's Device]], where swapping <code>i</code> and <code>A[i]</code> via a temporary variable yields incorrect results due to the arguments being related: swapping via <code>temp = i; i = A[i]; A[i] = temp</code> changes the value for <code>i</code> in the second statement, which then results in the incorrect i value for <code>A[i]</code> in the third statement.		Similar problems occur with [[call by name]], as in [[Jensen's Device]], where swapping <code>i</code> and <code>A[i]</code> via a temporary variable yields incorrect results due to the arguments being related: swapping via <code>temp = i; i = A[i]; A[i] = temp</code> changes the value for <code>i</code> in the second statement, which then results in the incorrect <code>i</code> value for <code>A[i]</code> in the third statement.

	==Variations==		==Variations==

Citation bot: Add: isbn, volume, series. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 1939/3000

2023-01-24T10:15:05Z

Add: isbn, volume, series. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 1939/3000

← Previous revision		Revision as of 10:15, 24 January 2023
Line 159:		Line 159:
	== Application to register allocation ==		== 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 journal \|last1=Pereira \|first1=Fernando Magno Quintão \|last2=Palsberg \|first2=Jens \|title=SSA Elimination after Register Allocation \|journal=Compiler Construction \|date=2009 \|pages=158–173 \|doi=10.1007/978-3-642-00722-4_12 \|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 journal \|last1=Hack \|first1=Sebastian \|last2=Grund \|first2=Daniel \|last3=Goos \|first3=Gerhard \|title=Register Allocation for Programs in SSA-Form \|journal=Compiler Construction \|date=2006 \|pages=247–262 \|doi=10.1007/11688839_20}}</ref>		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 journal \|last1=Pereira \|first1=Fernando Magno Quintão \|last2=Palsberg \|first2=Jens \|title=SSA Elimination after Register Allocation \|journal=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 \|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 journal \|last1=Hack \|first1=Sebastian \|last2=Grund \|first2=Daniel \|last3=Goos \|first3=Gerhard \|title=Register Allocation for Programs in SSA-Form \|journal=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 }}</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>		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>