bytecodealliance / bytecodealliance/regalloc2

Replace scratch register with XOR swap

Open
#206 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
265
Forks
53
PR merge metrics
No merged PRs in 30d

Description

I'm getting up to snuff on compiler backend details for a personal project and the `regalloc2` overview and the [follow on article](https://cfallin.org/blog/2022/06/09/cranelift-regalloc2/) have been great.

I'm not going to pretend to completely understand the details here, but the `MachineEnv` requires a scratch register for what I gather is typically swaps, symbolically like this.
```rs
let x = 4;
let y = 5;

let swap = x;
x = y;
y = swap;
```
However there is a way to swap two values without introducing a third variable/register which is via an [XOR swap](https://en.wikipedia.org/wiki/XOR_swap_algorithm):
```rs
x = y ^ x;
y = x ^ y;
x = y ^ x;
```
You shouldn't do this in high level code but should be fine in machine code of course. If an ISA allows integer operations to be applied to float registers then this can be used for both classes.

I'm nearly certain you know of this already, but I wanted to get it out there for the off chance, and if nothing else get details on why it wouldn't work.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by reviewing the MachineEnv scratch-register requirement and the linked regalloc2 overview and follow-on article. Determine whether XOR swaps are valid for the relevant register classes and ISAs, and whether they preserve the allocator's required behavior. Done means reaching a concrete, documented decision about whether this should replace scratch-register swaps.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.