Simplify codegen for tuple swapping of collection elements
- Dominant language
- C#
- Stars
- 18.3k
- Forks
- 5.6k
- PR merge metrics
- PR metrics pending
Description
### Description
Analyser [IDE0180 - Use tuple to swap values](https://learn.microsoft.com/dotnet/fundamentals/code-analysis/style-rules/ide0180) provides an example where collection elements are swapped, but the JIT output could be potentially be improved.
[Godbolt](https://godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAMzwBtMA7AQwFtMQByARg9KtQYEAysib0QXACx8BBAKoBnTAAUAHpwAMvAFYTStJg1DIFCJsQAOpJfWQE8Ayo3QBhVLQCuLBiADMXUmcAGTwGTAA5LwAjTGIQSQAOUgtUBUIHBjdPbz8AlLT7ARCwyJYYuMTrTFtChiECcwIsrx9/KpqM%2BsbiiOjY%2BKSFBuIm9xbc62GCHtLygYBKa1QPYmR2Dg80owBqIQBPIcwWAFJfACFjjQBBS6vQgljmWm2hpntkbeQDBQVdgHcmBYFLdjgB2C7XbZQ7b3R5iF4Nd4wwTbIKoUS0AAqRwsQgBFgg81u0O2YIhVxJJKEFkMpxc91O2G2DD6xF%2BpwAIqSAKxnUGkbYANgF3OO3I5p3JlOhADdzNsHiwLKTfFyWWVYsDeRoxRLzsTpczWVqzjrxSq1caxWcuLrJQbperyibbebOQqcfbIYbiJgCCsGEaNWzrQAmO3671QsES64O5EPYhPBFvPAfe6o9FiTEeCz0PGAwnxsnxqk0hh0hm%2BJlOzUWnl8gXC7ai8VeimGgD0ne22AYvuAeEObNJocFtZDvNdsY70ogE5duoFC%2BtZo583r86t2qXQed1unRMjs8pvv9Sb3mrDEal0JjILjGgAnLCk/DXkiM2iMTm85gCxYACyhh7EWj5PiW4GXE%2B1K0r49KCIy2xMPW1r8kKIoCtI2y%2BAK4Ztse0HQd2vb9pgg7DuyY5MNa3JYQKuHbKGArTg%2BEHPhANG8q2HIClxZySLu/G%2BEJ17inxB6iTu4obu6nGrlJNqKfhvHIdaIniWpvKCZp/E8Ue5JEc%2BZ4BlpZwqe2RGgjO8avsmH5ptsMqoHg6DbMo5isNiSoARAsEVvBVY1saRJRqS4KlrK8qKsq7ortJeq3o626mrq9bxUpBFJZSGXTvWMXtiS96PiednvoijnOa57meSwv75viAD6XCNRofnlpWiHVpebKhSekEniSW7BoumkZWusmqtsw37gly4pYehV3tZD6lYIcLPA5HxVW5HnEF5uYNYCrXNe1cEIQQSELn1RURWFJIkWcywMOgvzIAgmDIAA1r8GgCgQH2Bra93QjNV5zT1o3rpuuW7uNuoGcWK0ldBZWbRV20ubttX1f%2B%2BLAQwoH%2BZ1l3dUwfVWYZz7QfJU6KWuEnaYpGmqXpimCgjm78aCik8Yz5ncnzZk6azB4M2Zi2EdTyM3DLHCLLQnDcrwPgcFopCoJwLjHKGvgvMsqyYKO/i8AQmjy4sX0gNyf2Kxwkgq%2BbGucLwCggH9Ztq/LpBwLASBoEqdCxOQlABxYQdxOgqAEGEBAEMQHgMF9JhmJYaC%2Bl8ZA0LQiZuxAURO1EoTmHsnA8KQRfMMQewAPJRNon2e%2BXAdsIINcMLQpde6QWBRB4wAuGItBu9wvBYCwhjAOI3f4Bn9gypgI/q5gqifR4Dxl7wsJ2%2BrtB4FE%2B3V24WBO/HeAsJvpAL8QUSpJgHJHJPe9GObixUAYwAKAAangmB/DXFhGCX34IIEQYh2BSBkIIRQKh1Dd10AEAwL8U7mCsHvKIbtICLFQBYWoI9eCoGvsQVyi94CLBsI3DITgXrNByL4ZiwRQi9GDBIXwwp8jpAELQ1ozEOG1BmKyVhwoKF2E6FMbhfhmIiNqF0EYAiWFcDYZMRoEj6HKLkUw2Y/RFGCnIQbNYEgFZK0dt3TWHBtgADpwjYExNNCeoQNxuF9C4IIAAlaauBCAkGNlweYptX6W2trbTgDtSCq3VmY127tSCey0PMIxHBQwmIiS7GJASr6aioZIIAA%3D)
#### Additional `lea` instructions
Compared to temp var swapping, an additional (tuple length - 1) `lea` instructions are generated; enregistering element addresses instead of using them directly.
```csharp
int LocalTempSwap()
{
Span numbers = [7, 6, 5];
var temp = numbers[0];
numbers[0] = numbers[1];
numbers[1] = temp;
return numbers[2];
}
int LocalTupleSwap()
{
Span numbers = [7, 6, 5];
// Enregisters &numbers[1]
(numbers[1], numbers[0]) = (numbers[0], numbers[1]);
return numbers[2];
}
```
```diff
; LocalTupleSwap
+ lea rax, bword ptr [rbp-0x0C]
mov ecx, dword ptr [rbp-0x10]
mov edx, dword ptr [rbp-0x0C]
mov dword ptr [rax], ecx
mov dword ptr [rbp-0x10], edx
```
LocalTupleSwapMany (ref Goldbolt)
```asm
; (a[5], a[4], a[3], a[2], a[1], a[0]) = (a[0], a[1], a[2], a[3], a[4], a[5]);
lea rax, bword ptr [rbp-0x14]
lea rcx, bword ptr [rbp-0x18]
lea rdx, bword ptr [rbp-0x1C]
lea rdi, bword ptr [rbp-0x20]
lea rsi, bword ptr [rbp-0x24]
```
These methods may also be candidates to be reduced to `return 5;` as there no side effects, escapees, etc.
#### User order bounds checking
When the length of the collection isn't known, the number of bounds checks generated depends on the order of elements defined in the swap.
```csharp
void ParamTupleSwap_1_0(Span numbers)
{
(numbers[1], numbers[0]) = (numbers[0], numbers[1]);
}
void ParamTupleSwap_0_1(Span numbers)
{
// Bounds checks 0, then 1
(numbers[0], numbers[1]) = (numbers[1], numbers[0]);
}
```
```diff
; ParamTupleSwap_0_1
+ test esi, esi
+ je SHORT G_M36679_IG04
cmp esi, 1
jbe SHORT G_M36679_IG04
```
When there are enough bounds checks to warrant a layout change a fast path is added, guarded by a check against the largest index.
ParamTupleSwapMany (ref Goldbolt)
```asm
; (a[1], a[0], a[4], a[3], a[5], a[6]) = (a[7], a[5], a[255], a[4], a[10], a[1]);
lea rbp, [rsp+0x20]
xor eax, eax
jl SHORT G_M25565_IG05
lea ecx, [rsi-0xFF]
cmp eax, ecx
jge SHORT G_M25565_IG05
; Continue without bounds checks
G_M25565_IG05:
; Throw after the first OoB index
cmp esi, 1
jbe SHORT G_M25565_IG06
lea rax, bword ptr [rdi+0x04]
cmp esi, 4
jbe SHORT G_M25565_IG06
lea rcx, bword ptr [rdi+0x10]
lea rdx, bword ptr [rdi+0x0C]
cmp esi, 5
jbe SHORT G_M25565_IG06
lea r8, bword ptr [rdi+0x14]
cmp esi, 6
jbe SHORT G_M25565_IG06
lea r9, bword ptr [rdi+0x18]
cmp esi, 7
jbe SHORT G_M25565_IG06
mov r10d, dword ptr [rdi+0x1C]
mov r11d, dword ptr [rdi+0x14]
cmp esi, 255
jbe SHORT G_M25565_IG06
mov ebx, dword ptr [rdi+0x03FC]
jmp SHORT G_M25565_IG03
; a[4, 10, 1] are accessed without checks at the start of IG03
```
Is maintaining the user defined left-to-right order and throwing on the first OoB index a necessary implementation detail or may it be simplified to only testing the largest index?
### Regression?
No, same codegen between .NET9 and 10-rc2. Current codegen is better than than 8 and earlier.
Contributor guide
Assessment
This issue has not been assessed yet.