Repository: mmcloughlin/avo
Pull request #121 (2020-01-19 08:31:30)

reg,pass: refactor allocation of aliased registers
Issue #100 demonstrated that register allocation for aliased registers is
fundamentally broken. The root of the issue is that currently accesses to the
same virtual register with different masks are treated as different registers.
This PR takes a different approach:

* Liveness analysis is masked: we now properly consider which parts of a register are live
* Register allocation produces a mapping from virtual to physical ID, and aliasing is applied later

klauspost: This is super awesome. All my code "compiles" now and the power feels... overwhelming.

Still have no idea if my code works, but at least now I can generate it and start debugging 👍 
codecov-io: # [Codecov](https://codecov.io/gh/mmcloughlin/avo/pull/121?src=pr&el=h1) Report
> Merging [#121](https://codecov.io/gh/mmcloughlin/avo/pull/121?src=pr&el=desc) into [master](https://codecov.io/gh/mmcloughlin/avo/commit/b0ac74488c88a329ab76bdc649d3118b5ce2fcd3?src=pr&el=desc) will **increase** coverage by `0.01%`.
> The diff coverage is `89.94%`.

[![Impacted file tree graph](https://codecov.io/gh/mmcloughlin/avo/pull/121/graphs/tree.svg?width=650&token=DaOLKxzdQS&height=150&src=pr)](https://codecov.io/gh/mmcloughlin/avo/pull/121?src=pr&el=tree)

```diff
@@            Coverage Diff            @@
##           master    #121      +/-   ##
=========================================
+ Coverage   76.19%   76.2%   +0.01%     
=========================================
  Files          53      53              
  Lines       31343   31373      +30     
=========================================
+ Hits        23883   23909      +26     
  Misses       7355    7355              
- Partials      105     109       +4
```

| Flag | Coverage Δ | |
|---|---|---|
| #integration | `6.53% <87.7%> (+0.15%)` | :arrow_up: |
| #unittests | `74.01% <32.4%> (-0.17%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/mmcloughlin/avo/pull/121?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [ir/ir.go](https://codecov.io/gh/mmcloughlin/avo/pull/121/diff?src=pr&el=tree#diff-aXIvaXIuZ28=) | `90.47% <ø> (ø)` | :arrow_up: |
| [operand/types.go](https://codecov.io/gh/mmcloughlin/avo/pull/121/diff?src=pr&el=tree#diff-b3BlcmFuZC90eXBlcy5nbw==) | `95.77% <100%> (ø)` | :arrow_up: |
| [build/global.go](https://codecov.io/gh/mmcloughlin/avo/pull/121/diff?src=pr&el=tree#diff-YnVpbGQvZ2xvYmFsLmdv) | `80.43% <100%> (+0.88%)` | :arrow_up: |
| [reg/x86.go](https://codecov.io/gh/mmcloughlin/avo/pull/121/diff?src=pr&el=tree#diff-cmVnL3g4Ni5nbw==) | `100% <100%> (ø)` | :arrow_up: |
| [pass/reg.go](https://codecov.io/gh/mmcloughlin/avo/pull/121/diff?src=pr&el=tree#diff-cGFzcy9yZWcuZ28=) | `85.45% <100%> (-2.05%)` | :arrow_down: |
| [reg/types.go](https://codecov.io/gh/mmcloughlin/avo/pull/121/diff?src=pr&el=tree#diff-cmVnL3R5cGVzLmdv) | `83.96% <80.64%> (-6.63%)` | :arrow_down: |
| [reg/set.go](https://codecov.io/gh/mmcloughlin/avo/pull/121/diff?src=pr&el=tree#diff-cmVnL3NldC5nbw==) | `87.27% <93.18%> (+5.22%)` | :arrow_up: |
| [reg/collection.go](https://codecov.io/gh/mmcloughlin/avo/pull/121/diff?src=pr&el=tree#diff-cmVnL2NvbGxlY3Rpb24uZ28=) | `94.44% <93.75%> (+0.69%)` | :arrow_up: |
| [pass/alloc.go](https://codecov.io/gh/mmcloughlin/avo/pull/121/diff?src=pr&el=tree#diff-cGFzcy9hbGxvYy5nbw==) | `89.79% <95.34%> (-0.21%)` | :arrow_down: |
| [build/zinstructions.go](https://codecov.io/gh/mmcloughlin/avo/pull/121/diff?src=pr&el=tree#diff-YnVpbGQvemluc3RydWN0aW9ucy5nbw==) | `3.23% <0%> (+0.08%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/mmcloughlin/avo/pull/121?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/mmcloughlin/avo/pull/121?src=pr&el=footer). Last update [b0ac744...90fd6b9](https://codecov.io/gh/mmcloughlin/avo/pull/121?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

klauspost: It seems like something is still a bit weird. I have two pieces of code that after some changes that shouldn't cause allocation changes are now causing issues.

[Case 1](https://github.com/klauspost/compress/pull/186/files#diff-60d6e6209d2fc7873851f07b946a5dc7R292)

This is probably the easiest to understand. In this case it simply skips over the piece of code that are inlined below. Adding the branch should not make any difference on allocation, but it seems to do so.


[Case 2](https://github.com/klauspost/compress/pull/186/files#diff-60d6e6209d2fc7873851f07b946a5dc7R216)

This skips a whole bunch of code if taken, but none of the registers allocated in that piece of code (rep, left, right) is referenced in where it is jumping to. The registers at the destination should already be carried over because the rest of the code can end up there anyway.

It can easily be a problem in my code, which is why it would be great to have more info than "failed to allocate registers".
klauspost: FWIW, [this commit](https://github.com/klauspost/compress/pull/186/commits/00a95d63993ceeed5809fb66767781e69e598c43) is where it 'broke'. No other changes than size-related AFAICT.

I am looking at changing parts of it so I can see where it breaks.
mmcloughlin: @klauspost Sorry there's another problem, and thanks for your effort debugging this!

There's something I've been aware of but didn't think was going to be an immediate problem, specifically the behavior of 32-bit operands in 64-bit mode. From the Intel Manual:

> When in 64-bit mode, operand size determines the number of valid bits in the destination general-purpose register:
> * 64-bit operands generate a 64-bit result in the destination general-purpose register.
> * 32-bit operands generate a 32-bit result, zero-extended to a 64-bit result in the destination general-purpose register.
> * 8-bit and 16-bit operands generate an 8-bit or 16-bit result. The upper 56 bits or 48 bits (respectively) of the destination general-purpose register are not modified by the operation. If the result of an 8-bit or 16-bit operation is intended for 64-bit address calculation, explicitly sign-extend the register to the full 64-bits.

This means that 32-bit instructions will actually cause a write to the full 64-bit register. However the current implementation in `avo` does not handle this correctly: it sees a write to a 32-bit register and doesn't account for the zero-extension. So if a 32-bit write is followed by a 64-bit read of the same register, liveness analysis would consider there to be a dependency on the high 32-bits of the register, when in fact there is no such dependency.

The fact that your problem manifests when you change sizes from 64-bit to 32-bit makes me think the above issue might be to blame. However this is just a guess at this point, I'll have to dig into the details (I'll have time later today).
klauspost: Not completely sure I understand what it does. Kinda just assumed a `GP64()` lived as long as it was referenced (or an AsXX(), referring to the same register). 

Anyway, if you don't crack it, a workaround would be great. I can at least run parts of the code now, and I got a reasonable setup with delve, so I can actually debug it somewhat, so making progress.
mmcloughlin: Okay, using my experimental debug printer (https://github.com/mmcloughlin/avo/compare/regalloc-debug) we see

```
function {
	name       = "encodeBlockAsm"
	attributes = 0x0000 0
	doc        = []string{"encodeBlockAsm encodes a non-empty src to a guaranteed-large-enough dst.", "It assumes that the varint-encoded length of the decompressed bytes has already been written.", ""}
	signature  = (dst []byte, src []byte) int
	local size = 65568
	nodes {
		instruction {
			addr        = 0x0xc00010a000
			opcode      = "MOVQ"
			terminal    = false
			branch      = false
			conditional = false
			operands {
				0: $0x00000200
				1: AX
			}
			inputs {
			}
			outputs {
				0: <virtual:0:1:8>
			}
			pred {
			}
			succ {
				0x0xc00010a0c0
			}
			livein {
				000b0101: 08
				00220101: 08
				001a0101: 08
				00250101: 08
				005e0101: 08
			}
			liveout {
				00000101: 0f
				000b0101: 08
				00220101: 08
				001a0101: 08
				00250101: 08
				005e0101: 08
			}
		}
		...
```

Note the `livein` and `liveout` sections show a map from register ID to live mask. The `0x08` masks here indicate that `avo` thinks the high 32 bits of those registers are live, lending some credence to the theory in my last comment.
klauspost: ok, I managed to work around it by not converting registers as much.
mmcloughlin: > ok, I managed to work around it by not converting registers as much.

Good to hear. I'm going to try to work on a proper fix for this.

> Not completely sure I understand what it does. Kinda just assumed a `GP64()` lived as long as it was referenced (or an AsXX(), referring to the same register).

Just to clarify what the problem is, consider the following:

```go
...
x := GP64()
MOVW(U16(42), x.As16())
ADDQ(x, ...)
...
```

The move instruction only writes the low 16 bits, and the add consume the full 64 bits. Therefore `avo` liveness analysis would consider the high 48 bits to be live prior to the move instruction (all the way to the beginning of the function if there's no other write to `x`). This is actually correct, since a 16-bit operation will only write to the low 16 bits of the register. But what about the same thing in 32 bit?

```go
...
x := GP64()
MOVL(U32(42), x.As32())
ADDQ(x, ...)
...
```

This _should not_ exhibit the same problem as the 16 bit version, because in x86-64 the 32-bit write caused by `MOVL` will be zero extended to a 64-bit write. Hence it's just a 64-bit write followed by a 64-bit read, perfectly fine. The problem is that `avo` at the moment does not account for the zero-extension, and it sees a 32-bit write followed by a 64-bit read, and thinks that the upper 32 bits of x is live prior to the move instruction.

Ultimately this means `avo` thinks there are more live registers than there actually are, and in your case this is bad enough it prevented register allocation. If I have `avo` account for the zero-extension, the problem should be resolved. I hope :sweat_smile:

mmcloughlin: @klauspost I have added an additional pass that handles the 32-bit zero extension issue I described. With this change the code you referenced in https://github.com/mmcloughlin/avo/pull/121#issuecomment-576368875 doesn't fail allocation.

Please let me know how you get on with this new version. I actually think your change in https://github.com/klauspost/compress/pull/186/commits/214d2e2bcfe649cd720ef6b9bf8b87d85efc7204 is probably preferable anyway, not just as a workaround for this problem.

Once again, thanks for working through this with me 😄 

Patch:
diff --git a/build/global.go b/build/global.go
index 044d168..4095f81 100644
--- a/build/global.go
+++ b/build/global.go
@@ -70,7 +70,13 @@ func Constraint(t buildtags.ConstraintConvertable) { ctx.Constraint(t) }
 // constraint comments.
 func ConstraintExpr(expr string) { ctx.ConstraintExpr(expr) }
 
-// GP8 allocates and returns a general-purpose 8-bit register.
+// GP8L allocates and returns a general-purpose 8-bit register (low byte).
+func GP8L() reg.GPVirtual { return ctx.GP8L() }
+
+// GP8H allocates and returns a general-purpose 8-bit register (high byte).
+func GP8H() reg.GPVirtual { return ctx.GP8H() }
+
+// GP8 allocates and returns a general-purpose 8-bit register (low byte).
 func GP8() reg.GPVirtual { return ctx.GP8() }
 
 // GP16 allocates and returns a general-purpose 16-bit register.
diff --git a/ir/ir.go b/ir/ir.go
index 5431eaa..c5b52a1 100644
--- a/ir/ir.go
+++ b/ir/ir.go
@@ -55,8 +55,8 @@ type Instruction struct {
 	Succ []*Instruction
 
 	// LiveIn/LiveOut are sets of live register IDs pre/post execution.
-	LiveIn  reg.Set
-	LiveOut reg.Set
+	LiveIn  reg.MaskSet
+	LiveOut reg.MaskSet
 }
 
 func (i *Instruction) node() {}
diff --git a/operand/types.go b/operand/types.go
index 3ca07e4..878425e 100644
--- a/operand/types.go
+++ b/operand/types.go
@@ -141,10 +141,10 @@ func Registers(op Op) []reg.Register {
 func ApplyAllocation(op Op, a reg.Allocation) Op {
 	switch op := op.(type) {
 	case reg.Register:
-		return a.LookupDefault(op)
+		return a.LookupRegisterDefault(op)
 	case Mem:
-		op.Base = a.LookupDefault(op.Base)
-		op.Index = a.LookupDefault(op.Index)
+		op.Base = a.LookupRegisterDefault(op.Base)
+		op.Index = a.LookupRegisterDefault(op.Index)
 		return op
 	}
 	return op
diff --git a/pass/alloc.go b/pass/alloc.go
index c67a211..fc7773a 100644
--- a/pass/alloc.go
+++ b/pass/alloc.go
@@ -3,6 +3,7 @@ package pass
 import (
 	"errors"
 	"math"
+	"sort"
 
 	"github.com/mmcloughlin/avo/reg"
 )
@@ -10,28 +11,43 @@ import (
 // edge is an edge of the interference graph, indicating that registers X and Y
 // must be in non-conflicting registers.
 type edge struct {
-	X, Y reg.Register
+	X, Y reg.ID
 }
 
 // Allocator is a graph-coloring register allocator.
 type Allocator struct {
-	registers  []reg.Physical
+	registers  []reg.ID
 	allocation reg.Allocation
 	edges      []*edge
-	possible   map[reg.Virtual][]reg.Physical
-	vidtopid   map[reg.VID]reg.PID
+	possible   map[reg.ID][]reg.ID
 }
 
 // NewAllocator builds an allocator for the given physical registers.
 func NewAllocator(rs []reg.Physical) (*Allocator, error) {
-	if len(rs) == 0 {
-		return nil, errors.New("no registers")
+	// Set of IDs, excluding restricted registers.
+	idset := map[reg.ID]bool{}
+	for _, r := range rs {
+		if (r.Info() & reg.Restricted) != 0 {
+			continue
+		}
+		idset[r.ID()] = true
+	}
+
+	if len(idset) == 0 {
+		return nil, errors.New("no allocatable registers")
 	}
+
+	// Produce slice of unique register IDs.
+	var ids []reg.ID
+	for id := range idset {
+		ids = append(ids, id)
+	}
+	sort.Slice(ids, func(i, j int) bool { return ids[i] < ids[j] })
+
 	return &Allocator{
-		registers:  rs,
+		registers:  ids,
 		allocation: reg.NewEmptyAllocation(),
-		possible:   map[reg.Virtual][]reg.Physical{},
-		vidtopid:   map[reg.VID]reg.PID{},
+		possible:   map[reg.ID][]reg.ID{},
 	}, nil
 }
 
@@ -45,23 +61,24 @@ func NewAllocatorForKind(k reg.Kind) (*Allocator, error) {
 }
 
 // AddInterferenceSet records that r interferes with every register in s. Convenience wrapper around AddInterference.
-func (a *Allocator) AddInterferenceSet(r reg.Register, s reg.Set) {
-	for y := range s {
-		a.AddInterference(r, y)
+func (a *Allocator) AddInterferenceSet(r reg.Register, s reg.MaskSet) {
+	for id, mask := range s {
+		if (r.Mask() & mask) != 0 {
+			a.AddInterference(r.ID(), id)
+		}
 	}
 }
 
 // AddInterference records that x and y must be assigned to non-conflicting physical registers.
-func (a *Allocator) AddInterference(x, y reg.Register) {
+func (a *Allocator) AddInterference(x, y reg.ID) {
 	a.Add(x)
 	a.Add(y)
 	a.edges = append(a.edges, &edge{X: x, Y: y})
 }
 
 // Add adds a register to be allocated. Does nothing if the register has already been added.
-func (a *Allocator) Add(r reg.Register) {
-	v, ok := r.(reg.Virtual)
-	if !ok {
+func (a *Allocator) Add(v reg.ID) {
+	if !v.IsVirtual() {
 		return
 	}
 	if _, found := a.possible[v]; found {
@@ -91,35 +108,22 @@ func (a *Allocator) Allocate() (reg.Allocation, error) {
 
 // update possible allocations based on edges.
 func (a *Allocator) update() error {
-	for v := range a.possible {
-		pid, found := a.vidtopid[v.VirtualID()]
-		if !found {
-			continue
-		}
-		a.possible[v] = filterregisters(a.possible[v], func(r reg.Physical) bool {
-			return r.PhysicalID() == pid
-		})
-	}
-
 	var rem []*edge
 	for _, e := range a.edges {
-		e.X, e.Y = a.allocation.LookupDefault(e.X), a.allocation.LookupDefault(e.Y)
-
-		px, py := reg.ToPhysical(e.X), reg.ToPhysical(e.Y)
-		vx, vy := reg.ToVirtual(e.X), reg.ToVirtual(e.Y)
-
+		x := a.allocation.LookupDefault(e.X)
+		y := a.allocation.LookupDefault(e.Y)
 		switch {
-		case vx != nil && vy != nil:
+		case x.IsVirtual() && y.IsVirtual():
 			rem = append(rem, e)
 			continue
-		case px != nil && py != nil:
-			if reg.AreConflicting(px, py) {
+		case x.IsPhysical() && y.IsPhysical():
+			if x == y {
 				return errors.New("impossible register allocation")
 			}
-		case px != nil && vy != nil:
-			a.discardconflicting(vy, px)
-		case vx != nil && py != nil:
-			a.discardconflicting(vx, py)
+		case x.IsPhysical() && y.IsVirtual():
+			a.discardconflicting(y, x)
+		case x.IsVirtual() && y.IsPhysical():
+			a.discardconflicting(x, y)
 		default:
 			panic("unreachable")
 		}
@@ -130,30 +134,29 @@ func (a *Allocator) update() error {
 }
 
 // mostrestricted returns the virtual register with the least possibilities.
-func (a *Allocator) mostrestricted() reg.Virtual {
+func (a *Allocator) mostrestricted() reg.ID {
 	n := int(math.MaxInt32)
-	var v reg.Virtual
-	for r, p := range a.possible {
-		if len(p) < n || (len(p) == n && v != nil && r.VirtualID() < v.VirtualID()) {
+	var v reg.ID
+	for w, p := range a.possible {
+		// On a tie, choose the smallest ID in numeric order. This avoids
+		// non-deterministic allocations due to map iteration order.
+		if len(p) < n || (len(p) == n && w < v) {
 			n = len(p)
-			v = r
+			v = w
 		}
 	}
 	return v
 }
 
 // discardconflicting removes registers from vs possible list that conflict with p.
-func (a *Allocator) discardconflicting(v reg.Virtual, p reg.Physical) {
-	a.possible[v] = filterregisters(a.possible[v], func(r reg.Physical) bool {
-		if pid, found := a.vidtopid[v.VirtualID()]; found && pid == p.PhysicalID() {
-			return true
-		}
-		return !reg.AreConflicting(r, p)
+func (a *Allocator) discardconflicting(v, p reg.ID) {
+	a.possible[v] = filterregisters(a.possible[v], func(r reg.ID) bool {
+		return r != p
 	})
 }
 
 // alloc attempts to allocate a register to v.
-func (a *Allocator) alloc(v reg.Virtual) error {
+func (a *Allocator) alloc(v reg.ID) error {
 	ps := a.possible[v]
 	if len(ps) == 0 {
 		return errors.New("failed to allocate registers")
@@ -161,7 +164,6 @@ func (a *Allocator) alloc(v reg.Virtual) error {
 	p := ps[0]
 	a.allocation[v] = p
 	delete(a.possible, v)
-	a.vidtopid[v.VirtualID()] = p.PhysicalID()
 	return nil
 }
 
@@ -171,14 +173,14 @@ func (a *Allocator) remaining() int {
 }
 
 // possibleregisters returns all allocate-able registers for the given virtual.
-func (a *Allocator) possibleregisters(v reg.Virtual) []reg.Physical {
-	return filterregisters(a.registers, func(r reg.Physical) bool {
-		return v.SatisfiedBy(r) && (r.Info()&reg.Restricted) == 0
+func (a *Allocator) possibleregisters(v reg.ID) []reg.ID {
+	return filterregisters(a.registers, func(r reg.ID) bool {
+		return v.Kind() == r.Kind()
 	})
 }
 
-func filterregisters(in []reg.Physical, predicate func(reg.Physical) bool) []reg.Physical {
-	var rs []reg.Physical
+func filterregisters(in []reg.ID, predicate func(reg.ID) bool) []reg.ID {
+	var rs []reg.ID
 	for _, r := range in {
 		if predicate(r) {
 			rs = append(rs, r)
diff --git a/pass/pass.go b/pass/pass.go
index 3fd5452..62f37b1 100644
--- a/pass/pass.go
+++ b/pass/pass.go
@@ -16,6 +16,7 @@ var Compile = Concat(
 	FunctionPass(PruneDanglingLabels),
 	FunctionPass(LabelTarget),
 	FunctionPass(CFG),
+	InstructionPass(ZeroExtend32BitOutputs),
 	FunctionPass(Liveness),
 	FunctionPass(AllocateRegisters),
 	FunctionPass(BindRegisters),
diff --git a/pass/reg.go b/pass/reg.go
index 6d6e215..79147b0 100644
--- a/pass/reg.go
+++ b/pass/reg.go
@@ -8,6 +8,24 @@ import (
 	"github.com/mmcloughlin/avo/reg"
 )
 
+// ZeroExtend32BitOutputs applies the rule that "32-bit operands generate a
+// 32-bit result, zero-extended to a 64-bit result in the destination
+// general-purpose register" (Intel Software Developer’s Manual, Volume 1,
+// 3.4.1.1).
+func ZeroExtend32BitOutputs(i *ir.Instruction) error {
+	for j, op := range i.Outputs {
+		if !operand.IsR32(op) {
+			continue
+		}
+		r, ok := op.(reg.GP)
+		if !ok {
+			panic("r32 operand should satisfy reg.GP")
+		}
+		i.Outputs[j] = r.As64()
+	}
+	return nil
+}
+
 // Liveness computes register liveness.
 func Liveness(fn *ir.Function) error {
 	// Note this implementation is initially naive so as to be "obviously correct".
@@ -23,8 +41,8 @@ func Liveness(fn *ir.Function) error {
 
 	// Initialize.
 	for _, i := range is {
-		i.LiveIn = reg.NewSetFromSlice(i.InputRegisters())
-		i.LiveOut = reg.NewEmptySet()
+		i.LiveIn = reg.NewMaskSetFromRegisters(i.InputRegisters())
+		i.LiveOut = reg.NewEmptyMaskSet()
 	}
 
 	// Iterative dataflow analysis.
@@ -33,29 +51,16 @@ func Liveness(fn *ir.Function) error {
 
 		for _, i := range is {
 			// out[n] = UNION[s IN succ[n]] in[s]
-			nout := len(i.LiveOut)
 			for _, s := range i.Succ {
 				if s == nil {
 					continue
 				}
-				i.LiveOut.Update(s.LiveIn)
-			}
-			if len(i.LiveOut) != nout {
-				changes = true
+				changes = i.LiveOut.Update(s.LiveIn) || changes
 			}
 
 			// in[n] = use[n] UNION (out[n] - def[n])
-			nin := len(i.LiveIn)
-			def := reg.NewSetFromSlice(i.OutputRegisters())
-			i.LiveIn.Update(i.LiveOut.Difference(def))
-			for r := range i.LiveOut {
-				if _, found := def[r]; !found {
-					i.LiveIn.Add(r)
-				}
-			}
-			if len(i.LiveIn) != nin {
-				changes = true
-			}
+			def := reg.NewMaskSetFromRegisters(i.OutputRegisters())
+			changes = i.LiveIn.Update(i.LiveOut.Difference(def)) || changes
 		}
 
 		if !changes {
@@ -80,7 +85,7 @@ func AllocateRegisters(fn *ir.Function) error {
 				}
 				as[k] = a
 			}
-			as[k].Add(r)
+			as[k].Add(r.ID())
 		}
 	}
 
@@ -89,7 +94,7 @@ func AllocateRegisters(fn *ir.Function) error {
 		for _, d := range i.OutputRegisters() {
 			k := d.Kind()
 			out := i.LiveOut.OfKind(k)
-			out.Discard(d)
+			out.DiscardRegister(d)
 			as[k].AddInterferenceSet(d, out)
 		}
 	}
diff --git a/reg/collection.go b/reg/collection.go
index 5c85104..d35c3a0 100644
--- a/reg/collection.go
+++ b/reg/collection.go
@@ -3,46 +3,52 @@ package reg
 // Collection represents a collection of virtual registers. This is primarily
 // useful for allocating virtual registers with distinct IDs.
 type Collection struct {
-	vid map[Kind]VID
+	idx map[Kind]Index
 }
 
 // NewCollection builds an empty register collection.
 func NewCollection() *Collection {
 	return &Collection{
-		vid: map[Kind]VID{},
+		idx: map[Kind]Index{},
 	}
 }
 
 // VirtualRegister allocates and returns a new virtual register of the given kind and width.
-func (c *Collection) VirtualRegister(k Kind, w Width) Virtual {
-	vid := c.vid[k]
-	c.vid[k]++
-	return NewVirtual(vid, k, w)
+func (c *Collection) VirtualRegister(k Kind, s Spec) Virtual {
+	idx := c.idx[k]
+	c.idx[k]++
+	return NewVirtual(idx, k, s)
 }
 
-// GP8 allocates and returns a general-purpose 8-bit register.
-func (c *Collection) GP8() GPVirtual { return c.GP(B8) }
+// GP8L allocates and returns a general-purpose 8-bit register (low byte).
+func (c *Collection) GP8L() GPVirtual { return c.GP(S8L) }
+
+// GP8H allocates and returns a general-purpose 8-bit register (high byte).
+func (c *Collection) GP8H() GPVirtual { return c.GP(S8H) }
+
+// GP8 allocates and returns a general-purpose 8-bit register (low byte).
+func (c *Collection) GP8() GPVirtual { return c.GP8L() }
 
 // GP16 allocates and returns a general-purpose 16-bit register.
-func (c *Collection) GP16() GPVirtual { return c.GP(B16) }
+func (c *Collection) GP16() GPVirtual { return c.GP(S16) }
 
 // GP32 allocates and returns a general-purpose 32-bit register.
-func (c *Collection) GP32() GPVirtual { return c.GP(B32) }
+func (c *Collection) GP32() GPVirtual { return c.GP(S32) }
 
 // GP64 allocates and returns a general-purpose 64-bit register.
-func (c *Collection) GP64() GPVirtual { return c.GP(B64) }
+func (c *Collection) GP64() GPVirtual { return c.GP(S64) }
 
 // GP allocates and returns a general-purpose register of the given width.
-func (c *Collection) GP(w Width) GPVirtual { return newgpv(c.VirtualRegister(KindGP, w)) }
+func (c *Collection) GP(s Spec) GPVirtual { return newgpv(c.VirtualRegister(KindGP, s)) }
 
 // XMM allocates and returns a 128-bit vector register.
-func (c *Collection) XMM() VecVirtual { return c.Vec(B128) }
+func (c *Collection) XMM() VecVirtual { return c.Vec(S128) }
 
 // YMM allocates and returns a 256-bit vector register.
-func (c *Collection) YMM() VecVirtual { return c.Vec(B256) }
+func (c *Collection) YMM() VecVirtual { return c.Vec(S256) }
 
 // ZMM allocates and returns a 512-bit vector register.
-func (c *Collection) ZMM() VecVirtual { return c.Vec(B512) }
+func (c *Collection) ZMM() VecVirtual { return c.Vec(S512) }
 
 // Vec allocates and returns a vector register of the given width.
-func (c *Collection) Vec(w Width) VecVirtual { return newvecv(c.VirtualRegister(KindVector, w)) }
+func (c *Collection) Vec(s Spec) VecVirtual { return newvecv(c.VirtualRegister(KindVector, s)) }
diff --git a/reg/set.go b/reg/set.go
index fd1ddf3..2cf8814 100644
--- a/reg/set.go
+++ b/reg/set.go
@@ -1,69 +1,99 @@
 package reg
 
-// Set is a set of registers.
-type Set map[Register]bool
+// MaskSet maps register IDs to masks.
+type MaskSet map[ID]uint16
 
-// NewEmptySet builds an empty register set.
-func NewEmptySet() Set {
-	return Set{}
+// NewEmptyMaskSet builds an empty register mask set.
+func NewEmptyMaskSet() MaskSet {
+	return MaskSet{}
 }
 
-// NewSetFromSlice forms a set from the given register list.
-func NewSetFromSlice(rs []Register) Set {
-	s := NewEmptySet()
+// NewMaskSetFromRegisters forms a mask set from the given register list.
+func NewMaskSetFromRegisters(rs []Register) MaskSet {
+	s := NewEmptyMaskSet()
 	for _, r := range rs {
-		s.Add(r)
+		s.AddRegister(r)
 	}
 	return s
 }
 
 // Clone returns a copy of s.
-func (s Set) Clone() Set {
-	c := NewEmptySet()
-	for r := range s {
-		c.Add(r)
+func (s MaskSet) Clone() MaskSet {
+	c := NewEmptyMaskSet()
+	for id, mask := range s {
+		c.Add(id, mask)
 	}
 	return c
 }
 
-// Add r to s.
-func (s Set) Add(r Register) {
-	s[r] = true
+// Add mask to the given register ID.
+// Reports whether this made any change to the set.
+func (s MaskSet) Add(id ID, mask uint16) bool {
+	if (s[id] & mask) == mask {
+		return false
+	}
+	s[id] |= mask
+	return true
+}
+
+// AddRegister is a convenience for adding the register's (ID, mask) to the set.
+// Reports whether this made any change to the set.
+func (s MaskSet) AddRegister(r Register) bool {
+	return s.Add(r.ID(), r.Mask())
+}
+
+// Discard clears masked bits from register ID.
+// Reports whether this made any change to the set.
+func (s MaskSet) Discard(id ID, mask uint16) bool {
+	if curr, found := s[id]; !found || (curr&mask) == 0 {
+		return false
+	}
+	s[id] &^= mask
+	if s[id] == 0 {
+		delete(s, id)
+	}
+	return true
 }
 
-// Discard removes r from s, if present.
-func (s Set) Discard(r Register) {
-	delete(s, r)
+// DiscardRegister is a convenience for discarding the register's (ID, mask) from the set.
+// Reports whether this made any change to the set.
+func (s MaskSet) DiscardRegister(r Register) bool {
+	return s.Discard(r.ID(), r.Mask())
 }
 
-// Update adds every register in t to s.
-func (s Set) Update(t Set) {
-	for r := range t {
-		s.Add(r)
+// Update adds masks in t to s.
+// Reports whether this made any change to the set.
+func (s MaskSet) Update(t MaskSet) bool {
+	change := false
+	for id, mask := range t {
+		change = s.Add(id, mask) || change
 	}
+	return change
 }
 
 // Difference returns the set of registers in s but not t.
-func (s Set) Difference(t Set) Set {
+func (s MaskSet) Difference(t MaskSet) MaskSet {
 	d := s.Clone()
 	d.DifferenceUpdate(t)
 	return d
 }
 
 // DifferenceUpdate removes every element of t from s.
-func (s Set) DifferenceUpdate(t Set) {
-	for r := range t {
-		s.Discard(r)
+func (s MaskSet) DifferenceUpdate(t MaskSet) bool {
+	change := false
+	for id, mask := range t {
+		change = s.Discard(id, mask) || change
 	}
+	return change
 }
 
-// Equals returns true if s and t contain the same registers.
-func (s Set) Equals(t Set) bool {
+// Equals returns true if s and t contain the same masks.
+func (s MaskSet) Equals(t MaskSet) bool {
 	if len(s) != len(t) {
 		return false
 	}
-	for r := range s {
-		if _, found := t[r]; !found {
+	for id, mask := range s {
+		if _, found := t[id]; !found || mask != t[id] {
 			return false
 		}
 	}
@@ -71,11 +101,11 @@ func (s Set) Equals(t Set) bool {
 }
 
 // OfKind returns the set of elements of s with kind k.
-func (s Set) OfKind(k Kind) Set {
-	t := NewEmptySet()
-	for r := range s {
-		if r.Kind() == k {
-			t.Add(r)
+func (s MaskSet) OfKind(k Kind) MaskSet {
+	t := NewEmptyMaskSet()
+	for id, mask := range s {
+		if id.Kind() == k {
+			t.Add(id, mask)
 		}
 	}
 	return t
diff --git a/reg/types.go b/reg/types.go
index cd9f32a..9f69e91 100644
--- a/reg/types.go
+++ b/reg/types.go
@@ -5,26 +5,12 @@ import (
 	"fmt"
 )
 
-// Width is a register width.
-type Width uint
-
-// Typical register width values.
-const (
-	B8 Width = 1 << iota
-	B16
-	B32
-	B64
-	B128
-	B256
-	B512
-)
-
-// Size returns the register width in bytes.
-func (w Width) Size() uint { return uint(w) }
-
 // Kind is a class of registers.
 type Kind uint8
 
+// Index of a register within a kind.
+type Index uint16
+
 // Family is a collection of Physical registers of a common kind.
 type Family struct {
 	Kind      Kind
@@ -32,8 +18,8 @@ type Family struct {
 }
 
 // define builds a register and adds it to the Family.
-func (f *Family) define(s Spec, id PID, name string, flags ...Info) Physical {
-	r := newregister(f, s, id, name, flags...)
+func (f *Family) define(s Spec, idx Index, name string, flags ...Info) Physical {
+	r := newregister(f, s, idx, name, flags...)
 	f.add(r)
 	return r
 }
@@ -47,8 +33,8 @@ func (f *Family) add(r Physical) {
 }
 
 // Virtual returns a virtual register from this family's kind.
-func (f *Family) Virtual(id VID, w Width) Virtual {
-	return NewVirtual(id, f.Kind, w)
+func (f *Family) Virtual(idx Index, s Spec) Virtual {
+	return NewVirtual(idx, f.Kind, s)
 }
 
 // Registers returns the registers in this family.
@@ -56,41 +42,56 @@ func (f *Family) Registers() []Physical {
 	return append([]Physical(nil), f.registers...)
 }
 
-// Set returns the set of registers in the family.
-func (f *Family) Set() Set {
-	s := NewEmptySet()
-	for _, r := range f.registers {
-		s.Add(r)
-	}
-	return s
-}
-
-// Lookup returns the register with given physical ID and spec. Returns nil if no such register exists.
-func (f *Family) Lookup(id PID, s Spec) Physical {
+// Lookup returns the register with given physical index and spec. Returns nil if no such register exists.
+func (f *Family) Lookup(idx Index, s Spec) Physical {
 	for _, r := range f.registers {
-		if r.PhysicalID() == id && r.Mask() == s.Mask() {
+		if r.PhysicalIndex() == idx && r.Mask() == s.Mask() {
 			return r
 		}
 	}
 	return nil
 }
 
+// ID is a register identifier.
+type ID uint32
+
+// newid builds a new register ID from the virtual flag v, kind and index.
+func newid(v uint8, kind Kind, idx Index) ID {
+	return ID(v) | (ID(kind) << 8) | (ID(idx) << 16)
+}
+
+// IsVirtual reports whether this is an ID for a virtual register.
+func (id ID) IsVirtual() bool { return (id & 1) == 1 }
+
+// IsPhysical reports whether this is an ID for a physical register.
+func (id ID) IsPhysical() bool { return !id.IsVirtual() }
+
+// Kind extracts the kind from the register ID.
+func (id ID) Kind() Kind { return Kind(id >> 8) }
+
+// Index extracts the index from the register ID.
+func (id ID) Index() Index { return Index(id >> 16) }
+
 // Register represents a virtual or physical register.
 type Register interface {
+	ID() ID
 	Kind() Kind
 	Size() uint
+	Mask() uint16
 	Asm() string
 	as(Spec) Register
+	spec() Spec
 	register()
 }
 
-// VID is a virtual register ID.
-type VID uint16
+// Equal reports whether a and b are equal registers.
+func Equal(a, b Register) bool {
+	return (a.ID() == b.ID()) && (a.Mask() == b.Mask())
+}
 
 // Virtual is a register of a given type and size, not yet allocated to a physical register.
 type Virtual interface {
-	VirtualID() VID
-	SatisfiedBy(Physical) bool
+	VirtualIndex() Index
 	Register
 }
 
@@ -103,43 +104,39 @@ func ToVirtual(r Register) Virtual {
 }
 
 type virtual struct {
-	id   VID
+	idx  Index
 	kind Kind
-	Width
-	mask uint16
+	Spec
 }
 
 // NewVirtual builds a Virtual register.
-func NewVirtual(id VID, k Kind, w Width) Virtual {
+func NewVirtual(idx Index, k Kind, s Spec) Virtual {
 	return virtual{
-		id:    id,
-		kind:  k,
-		Width: w,
+		idx:  idx,
+		kind: k,
+		Spec: s,
 	}
 }
 
-func (v virtual) VirtualID() VID { return v.id }
-func (v virtual) Kind() Kind     { return v.kind }
+func (v virtual) ID() ID              { return newid(1, v.kind, v.idx) }
+func (v virtual) VirtualIndex() Index { return v.idx }
+func (v virtual) Kind() Kind          { return v.kind }
 
 func (v virtual) Asm() string {
 	// TODO(mbm): decide on virtual register syntax
-	return fmt.Sprintf("<virtual:%v:%v:%v>", v.id, v.Kind(), v.Size())
-}
-
-func (v virtual) SatisfiedBy(p Physical) bool {
-	return v.Kind() == p.Kind() && v.Size() == p.Size() && (v.mask == 0 || v.mask == p.Mask())
+	return fmt.Sprintf("<virtual:%v:%v:%v>", v.idx, v.Kind(), v.Size())
 }
 
 func (v virtual) as(s Spec) Register {
 	return virtual{
-		id:    v.id,
-		kind:  v.kind,
-		Width: Width(s.Size()),
-		mask:  s.Mask(),
+		idx:  v.idx,
+		kind: v.kind,
+		Spec: s,
 	}
 }
 
-func (v virtual) register() {}
+func (v virtual) spec() Spec { return v.Spec }
+func (v virtual) register()  {}
 
 // Info is a bitmask of register properties.
 type Info uint8
@@ -150,13 +147,9 @@ const (
 	Restricted Info = 1 << iota
 )
 
-// PID is a physical register ID.
-type PID uint16
-
 // Physical is a concrete register.
 type Physical interface {
-	PhysicalID() PID
-	Mask() uint16
+	PhysicalIndex() Index
 	Info() Info
 	Register
 }
@@ -172,16 +165,16 @@ func ToPhysical(r Register) Physical {
 // register implements Physical.
 type register struct {
 	family *Family
-	id     PID
+	idx    Index
 	name   string
 	info   Info
 	Spec
 }
 
-func newregister(f *Family, s Spec, id PID, name string, flags ...Info) register {
+func newregister(f *Family, s Spec, idx Index, name string, flags ...Info) register {
 	r := register{
 		family: f,
-		id:     id,
+		idx:    idx,
 		name:   name,
 		info:   None,
 		Spec:   s,
@@ -192,16 +185,18 @@ func newregister(f *Family, s Spec, id PID, name string, flags ...Info) register
 	return r
 }
 
-func (r register) PhysicalID() PID { return r.id }
-func (r register) Kind() Kind      { return r.family.Kind }
-func (r register) Asm() string     { return r.name }
-func (r register) Info() Info      { return r.info }
+func (r register) ID() ID               { return newid(0, r.Kind(), r.idx) }
+func (r register) PhysicalIndex() Index { return r.idx }
+func (r register) Kind() Kind           { return r.family.Kind }
+func (r register) Asm() string          { return r.name }
+func (r register) Info() Info           { return r.info }
 
 func (r register) as(s Spec) Register {
-	return r.family.Lookup(r.PhysicalID(), s)
+	return r.family.Lookup(r.PhysicalIndex(), s)
 }
 
-func (r register) register() {}
+func (r register) spec() Spec { return r.Spec }
+func (r register) register()  {}
 
 // Spec defines the size of a register as well as the bit ranges it occupies in
 // an underlying physical register.
@@ -235,13 +230,25 @@ func (s Spec) Size() uint {
 	return (x >> 1) + (x & 1)
 }
 
-// AreConflicting returns whether registers conflict with each other.
-func AreConflicting(x, y Physical) bool {
-	return x.Kind() == y.Kind() && x.PhysicalID() == y.PhysicalID() && (x.Mask()&y.Mask()) != 0
+// LookupPhysical returns the physical register with the given parameters, or nil if not found.
+func LookupPhysical(k Kind, idx Index, s Spec) Physical {
+	f := FamilyOfKind(k)
+	if f == nil {
+		return nil
+	}
+	return f.Lookup(idx, s)
+}
+
+// LookupID returns the physical register with the given id and spec, or nil if not found.
+func LookupID(id ID, s Spec) Physical {
+	if id.IsVirtual() {
+		return nil
+	}
+	return LookupPhysical(id.Kind(), id.Index(), s)
 }
 
 // Allocation records a register allocation.
-type Allocation map[Register]Physical
+type Allocation map[ID]ID
 
 // NewEmptyAllocation builds an empty register allocation.
 func NewEmptyAllocation() Allocation {
@@ -251,18 +258,46 @@ func NewEmptyAllocation() Allocation {
 // Merge allocations from b into a. Errors if there is disagreement on a common
 // register.
 func (a Allocation) Merge(b Allocation) error {
-	for r, p := range b {
-		if alt, found := a[r]; found && alt != p {
+	for id, p := range b {
+		if alt, found := a[id]; found && alt != p {
 			return errors.New("disagreement on overlapping register")
 		}
-		a[r] = p
+		a[id] = p
 	}
 	return nil
 }
 
-// LookupDefault returns the register assigned to r, or r itself if there is none.
-func (a Allocation) LookupDefault(r Register) Register {
-	if p, found := a[r]; found {
+// LookupDefault returns the register ID assigned by this allocation, returning
+// id if none is found.
+func (a Allocation) LookupDefault(id ID) ID {
+	if _, found := a[id]; found {
+		return a[id]
+	}
+	return id
+}
+
+// LookupRegister the allocation for register r, or return nil if there is none.
+func (a Allocation) LookupRegister(r Register) Physical {
+	// Return immediately if it is already a physical register.
+	if p := ToPhysical(r); p != nil {
+		return p
+	}
+
+	// Lookup an allocation for this virtual ID.
+	id, found := a[r.ID()]
+	if !found {
+		return nil
+	}
+
+	return LookupID(id, r.spec())
+}
+
+// LookupRegisterDefault returns the register assigned to r, or r itself if there is none.
+func (a Allocation) LookupRegisterDefault(r Register) Register {
+	if r == nil {
+		return nil
+	}
+	if p := a.LookupRegister(r); p != nil {
 		return p
 	}
 	return r
diff --git a/reg/x86.go b/reg/x86.go
index 96316bd..a1ec94c 100644
--- a/reg/x86.go
+++ b/reg/x86.go
@@ -28,7 +28,7 @@ func init() {
 	}
 }
 
-// FamilyOfKind returns the Family of registers of the given kind.
+// FamilyOfKind returns the Family of registers of the given kind, or nil if not found.
 func FamilyOfKind(k Kind) *Family {
 	return familiesByKind[k]
 }
@@ -51,17 +51,6 @@ type GP interface {
 	As64() Register
 }
 
-type gpcasts struct {
-	Register
-}
-
-func (c gpcasts) As8() Register  { return c.as(S8) }
-func (c gpcasts) As8L() Register { return c.as(S8L) }
-func (c gpcasts) As8H() Register { return c.as(S8H) }
-func (c gpcasts) As16() Register { return c.as(S16) }
-func (c gpcasts) As32() Register { return c.as(S32) }
-func (c gpcasts) As64() Register { return c.as(S64) }
-
 // GPPhysical is a general-purpose physical register.
 type GPPhysical interface {
 	Physical
@@ -70,10 +59,16 @@ type GPPhysical interface {
 
 type gpp struct {
 	Physical
-	GP
 }
 
-func newgpp(r Physical) GPPhysical { return gpp{Physical: r, GP: gpcasts{r}} }
+func newgpp(r Physical) GPPhysical { return gpp{Physical: r} }
+
+func (p gpp) As8() Register  { return newgpp(p.as(S8).(Physical)) }
+func (p gpp) As8L() Register { return newgpp(p.as(S8L).(Physical)) }
+func (p gpp) As8H() Register { return newgpp(p.as(S8H).(Physical)) }
+func (p gpp) As16() Register { return newgpp(p.as(S16).(Physical)) }
+func (p gpp) As32() Register { return newgpp(p.as(S32).(Physical)) }
+func (p gpp) As64() Register { return newgpp(p.as(S64).(Physical)) }
 
 // GPVirtual is a general-purpose virtual register.
 type GPVirtual interface {
@@ -83,12 +78,18 @@ type GPVirtual interface {
 
 type gpv struct {
 	Virtual
-	GP
 }
 
-func newgpv(v Virtual) GPVirtual { return gpv{Virtual: v, GP: gpcasts{v}} }
+func newgpv(v Virtual) GPVirtual { return gpv{Virtual: v} }
 
-func gp(s Spec, id PID, name string, flags ...Info) GPPhysical {
+func (v gpv) As8() Register  { return newgpv(v.as(S8).(Virtual)) }
+func (v gpv) As8L() Register { return newgpv(v.as(S8L).(Virtual)) }
+func (v gpv) As8H() Register { return newgpv(v.as(S8H).(Virtual)) }
+func (v gpv) As16() Register { return newgpv(v.as(S16).(Virtual)) }
+func (v gpv) As32() Register { return newgpv(v.as(S32).(Virtual)) }
+func (v gpv) As64() Register { return newgpv(v.as(S64).(Virtual)) }
+
+func gp(s Spec, id Index, name string, flags ...Info) GPPhysical {
 	r := newgpp(newregister(GeneralPurpose, s, id, name, flags...))
 	GeneralPurpose.add(r)
 	return r
@@ -184,14 +185,6 @@ type Vec interface {
 	AsZ() Register
 }
 
-type veccasts struct {
-	Register
-}
-
-func (c veccasts) AsX() Register { return c.as(S128) }
-func (c veccasts) AsY() Register { return c.as(S256) }
-func (c veccasts) AsZ() Register { return c.as(S512) }
-
 // VecPhysical is a physical vector register.
 type VecPhysical interface {
 	Physical
@@ -203,7 +196,11 @@ type vecp struct {
 	Vec
 }
 
-func newvecp(r Physical) VecPhysical { return vecp{Physical: r, Vec: veccasts{r}} }
+func newvecp(r Physical) VecPhysical { return vecp{Physical: r} }
+
+func (p vecp) AsX() Register { return newvecp(p.as(S128).(Physical)) }
+func (p vecp) AsY() Register { return newvecp(p.as(S256).(Physical)) }
+func (p vecp) AsZ() Register { return newvecp(p.as(S512).(Physical)) }
 
 // VecVirtual is a virtual vector register.
 type VecVirtual interface {
@@ -216,9 +213,13 @@ type vecv struct {
 	Vec
 }
 
-func newvecv(v Virtual) VecVirtual { return vecv{Virtual: v, Vec: veccasts{v}} }
+func newvecv(v Virtual) VecVirtual { return vecv{Virtual: v} }
+
+func (v vecv) AsX() Register { return newvecv(v.as(S128).(Virtual)) }
+func (v vecv) AsY() Register { return newvecv(v.as(S256).(Virtual)) }
+func (v vecv) AsZ() Register { return newvecv(v.as(S512).(Virtual)) }
 
-func vec(s Spec, id PID, name string, flags ...Info) VecPhysical {
+func vec(s Spec, id Index, name string, flags ...Info) VecPhysical {
 	r := newvecp(newregister(Vector, s, id, name, flags...))
 	Vector.add(r)
 	return r


Test patch:
diff --git a/pass/alloc_test.go b/pass/alloc_test.go
index 646aedb..d1935e7 100644
--- a/pass/alloc_test.go
+++ b/pass/alloc_test.go
@@ -15,9 +15,9 @@ func TestAllocatorSimple(t *testing.T) {
 		t.Fatal(err)
 	}
 
-	a.Add(x)
-	a.Add(y)
-	a.AddInterference(x, y)
+	a.Add(x.ID())
+	a.Add(y.ID())
+	a.AddInterference(x.ID(), y.ID())
 
 	alloc, err := a.Allocate()
 	if err != nil {
@@ -26,7 +26,7 @@ func TestAllocatorSimple(t *testing.T) {
 
 	t.Log(alloc)
 
-	if alloc[x] != reg.X0 || alloc[y] != reg.Y1 {
+	if alloc.LookupRegister(x) != reg.X0 || alloc.LookupRegister(y) != reg.Y1 {
 		t.Fatalf("unexpected allocation")
 	}
 }
@@ -37,7 +37,7 @@ func TestAllocatorImpossible(t *testing.T) {
 		t.Fatal(err)
 	}
 
-	a.AddInterference(reg.X7, reg.Z7)
+	a.AddInterference(reg.X7.ID(), reg.Z7.ID())
 
 	_, err = a.Allocate()
 	if err == nil {
diff --git a/pass/reg_test.go b/pass/reg_test.go
index 353a80f..1d91112 100644
--- a/pass/reg_test.go
+++ b/pass/reg_test.go
@@ -3,14 +3,59 @@ package pass_test
 import (
 	"testing"
 
+	"github.com/mmcloughlin/avo/build"
 	"github.com/mmcloughlin/avo/ir"
+	"github.com/mmcloughlin/avo/operand"
+	"github.com/mmcloughlin/avo/pass"
 	"github.com/mmcloughlin/avo/reg"
+)
 
-	"github.com/mmcloughlin/avo/pass"
+func TestZeroExtend32BitOutputs(t *testing.T) {
+	collection := reg.NewCollection()
+	v16 := collection.GP16()
+	v32 := collection.GP32()
 
-	"github.com/mmcloughlin/avo/build"
-	"github.com/mmcloughlin/avo/operand"
-)
+	i := &ir.Instruction{
+		Outputs: []operand.Op{
+			reg.R8B,
+			reg.R9W,
+			reg.R10L,
+			reg.R11,
+			v16,
+			v32,
+		},
+	}
+
+	err := pass.ZeroExtend32BitOutputs(i)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	got := i.Outputs
+	expect := []reg.Register{
+		reg.R8B,
+		reg.R9W,
+		reg.R10, // converted from R10L
+		reg.R11,
+		v16,
+		v32.As64(), // converted from 32-bit
+	}
+
+	if len(expect) != len(got) {
+		t.Fatal("length mismatch")
+	}
+
+	for j := range got {
+		r, ok := got[j].(reg.Register)
+		if !ok {
+			t.Fatalf("expected register; got %s", got[j].Asm())
+		}
+
+		if !reg.Equal(expect[j], r) {
+			t.Fatalf("got %s; expect %s", expect[j].Asm(), r.Asm())
+		}
+	}
+}
 
 func TestLivenessBasic(t *testing.T) {
 	// Build: a = 1, b = 2, a = a+b
@@ -50,8 +95,8 @@ func AssertLiveness(t *testing.T, ctx *build.Context, in, out [][]reg.Register)
 	}
 }
 
-func AssertRegistersMatchSet(t *testing.T, rs []reg.Register, s reg.Set) {
-	if !s.Equals(reg.NewSetFromSlice(rs)) {
+func AssertRegistersMatchSet(t *testing.T, rs []reg.Register, s reg.MaskSet) {
+	if !s.Equals(reg.NewMaskSetFromRegisters(rs)) {
 		t.Fatalf("register slice does not match set: %#v and %#v", rs, s)
 	}
 }
diff --git a/reg/reg_test.go b/reg/reg_test.go
index 5f5281e..07e0b8c 100644
--- a/reg/reg_test.go
+++ b/reg/reg_test.go
@@ -1,6 +1,40 @@
 package reg
 
-import "testing"
+import (
+	"testing"
+	"testing/quick"
+)
+
+func TestIDFields(t *testing.T) {
+	f := func(v uint8, kind Kind, idx Index) bool {
+		id := newid(v, kind, idx)
+		return id.Kind() == kind && id.Index() == idx
+	}
+	if err := quick.Check(f, nil); err != nil {
+		t.Fatal(err)
+	}
+}
+
+func TestIDIsVirtual(t *testing.T) {
+	cases := []Virtual{
+		GeneralPurpose.Virtual(42, S64),
+		Vector.Virtual(42, S128),
+	}
+	for _, r := range cases {
+		if !r.ID().IsVirtual() {
+			t.FailNow()
+		}
+	}
+}
+
+func TestIDIsPhysical(t *testing.T) {
+	cases := []Physical{AL, AH, AX, EAX, RAX, X1, Y2, Z31}
+	for _, r := range cases {
+		if !r.ID().IsPhysical() {
+			t.FailNow()
+		}
+	}
+}
 
 func TestSpecSize(t *testing.T) {
 	cases := []struct {
@@ -25,7 +59,7 @@ func TestSpecSize(t *testing.T) {
 }
 
 func TestToVirtual(t *testing.T) {
-	v := GeneralPurpose.Virtual(42, B32)
+	v := GeneralPurpose.Virtual(42, S32)
 	if ToVirtual(v) != v {
 		t.Errorf("ToVirtual(v) != v for virtual register")
 	}
@@ -35,7 +69,7 @@ func TestToVirtual(t *testing.T) {
 }
 
 func TestToPhysical(t *testing.T) {
-	v := GeneralPurpose.Virtual(42, B32)
+	v := GeneralPurpose.Virtual(42, S32)
 	if ToPhysical(v) != nil {
 		t.Errorf("ToPhysical should be nil for virtual registers")
 	}
@@ -44,31 +78,10 @@ func TestToPhysical(t *testing.T) {
 	}
 }
 
-func TestAreConflicting(t *testing.T) {
-	cases := []struct {
-		X, Y   Physical
-		Expect bool
-	}{
-		{ECX, X3, false},
-		{AL, AH, false},
-		{AL, AX, true},
-		{AL, BX, false},
-		{X3, Y4, false},
-		{X3, Y3, true},
-		{Y3, Z4, false},
-		{Y3, Z3, true},
-	}
-	for _, c := range cases {
-		if AreConflicting(c.X, c.Y) != c.Expect {
-			t.Errorf("AreConflicting(%s, %s) != %v", c.X, c.Y, c.Expect)
-		}
-	}
-}
-
 func TestFamilyLookup(t *testing.T) {
 	cases := []struct {
 		Family *Family
-		ID     PID
+		ID     Index
 		Spec   Spec
 		Expect Physical
 	}{
@@ -89,7 +102,7 @@ func TestFamilyLookup(t *testing.T) {
 	for _, c := range cases {
 		got := c.Family.Lookup(c.ID, c.Spec)
 		if got != c.Expect {
-			t.Errorf("pid=%v spec=%v: lookup got %v expect %v", c.ID, c.Spec, got, c.Expect)
+			t.Errorf("idx=%v spec=%v: lookup got %v expect %v", c.ID, c.Spec, got, c.Expect)
 		}
 	}
 }
@@ -117,21 +130,45 @@ func TestPhysicalAs(t *testing.T) {
 }
 
 func TestVirtualAs(t *testing.T) {
+	v := GeneralPurpose.Virtual(0, S64)
+	specs := []Spec{S8, S8L, S8H, S16, S32, S64}
+	for _, s := range specs {
+		if v.as(s).Mask() != s.Mask() {
+			t.FailNow()
+		}
+	}
+}
+
+func TestLookupPhysical(t *testing.T) {
 	cases := []struct {
-		Virtual  Register
-		Physical Physical
-		Match    bool
+		Kind   Kind
+		Index  Index
+		Spec   Spec
+		Expect Physical
 	}{
-		{GeneralPurpose.Virtual(0, B8), CL, true},
-		{GeneralPurpose.Virtual(0, B8), CH, true},
-		{GeneralPurpose.Virtual(0, B32).as(S8L), CL, true},
-		{GeneralPurpose.Virtual(0, B32).as(S8L), CH, false},
-		{GeneralPurpose.Virtual(0, B16).as(S32), R9L, true},
-		{GeneralPurpose.Virtual(0, B16).as(S32), R9, false},
+		{KindGP, 0, S8L, AL},
+		{KindGP, 1, S8H, CH},
+		{KindGP, 7, S8, DIB},
+		{KindGP, 8, S16, R8W},
+		{KindGP, 9, S32, R9L},
+		{KindGP, 10, S64, R10},
+
+		{KindVector, 7, S128, X7},
+		{KindVector, 17, S256, Y17},
+		{KindVector, 27, S512, Z27},
 	}
 	for _, c := range cases {
-		if c.Virtual.(Virtual).SatisfiedBy(c.Physical) != c.Match {
-			t.Errorf("%s.SatisfiedBy(%v) != %v", c.Virtual.Asm(), c.Physical, c.Match)
+		if got := LookupPhysical(c.Kind, c.Index, c.Spec); !Equal(got, c.Expect) {
+			t.FailNow()
+		}
+	}
+}
+
+func TestLookupIDSelf(t *testing.T) {
+	cases := []Physical{AL, AH, AX, EAX, RAX, X1, Y2, Z31}
+	for _, r := range cases {
+		if got := LookupID(r.ID(), r.spec()); !Equal(got, r) {
+			t.FailNow()
 		}
 	}
 }
diff --git a/reg/set_test.go b/reg/set_test.go
deleted file mode 100644
index 9cd04f6..0000000
--- a/reg/set_test.go
+++ /dev/null
@@ -1,41 +0,0 @@
-package reg
-
-import "testing"
-
-func TestSetRegisterIdentity(t *testing.T) {
-	rs := []Register{
-		NewVirtual(42, KindGP, B32),
-		NewVirtual(43, KindGP, B32),
-		NewVirtual(42, KindVector, B32),
-		NewVirtual(42, KindGP, B64),
-		AL, AH, CL,
-		AX, R13W,
-		EDX, R9L,
-		RCX, R14,
-		X1, X7,
-		Y4, Y9,
-		Z13, Z31,
-	}
-	s := NewEmptySet()
-	for _, r := range rs {
-		s.Add(r)
-		s.Add(r)
-	}
-	if len(s) != len(rs) {
-		t.Fatalf("expected set to have same size as slice: got %d expect %d", len(s), len(rs))
-	}
-}
-
-func TestSetFamilyRegisters(t *testing.T) {
-	fs := []*Family{GeneralPurpose, Vector}
-	s := NewEmptySet()
-	expect := 0
-	for _, f := range fs {
-		s.Update(f.Set())
-		s.Add(f.Virtual(42, B64))
-		expect += len(f.Registers()) + 1
-	}
-	if len(s) != expect {
-		t.Fatalf("set size mismatch: %d expected %d", len(s), expect)
-	}
-}
diff --git a/reg/x86_test.go b/reg/x86_test.go
index 3ed0479..0b06420 100644
--- a/reg/x86_test.go
+++ b/reg/x86_test.go
@@ -21,7 +21,67 @@ func TestAsMethods(t *testing.T) {
 		{Z9.AsZ(), Z9},
 	}
 	for _, c := range cases {
-		if c[0] != c[1] {
+		if !Equal(c[0], c[1]) {
+			t.FailNow()
+		}
+	}
+}
+
+func TestAsPreservesGPPhysical(t *testing.T) {
+	cases := []Register{
+		RAX.As8(),
+		R13.As8L(),
+		AL.As8H(),
+		EAX.As16(),
+		CH.As32(),
+		EBX.As64(),
+	}
+	for _, r := range cases {
+		if _, ok := r.(GPPhysical); !ok {
+			t.FailNow()
+		}
+	}
+}
+
+func TestAsPreservesGPVirtual(t *testing.T) {
+	collection := NewCollection()
+	cases := []Register{
+		collection.GP16().As8(),
+		collection.GP32().As8L(),
+		collection.GP64().As8H(),
+		collection.GP8().As16(),
+		collection.GP8L().As32(),
+		collection.GP8H().As64(),
+	}
+	for _, r := range cases {
+		if _, ok := r.(GPVirtual); !ok {
+			t.FailNow()
+		}
+	}
+}
+
+func TestAsPreservesVecPhysical(t *testing.T) {
+	cases := []Register{
+		Y13.AsX(),
+		X3.AsY(),
+		Y10.AsZ(),
+	}
+	for _, r := range cases {
+		if _, ok := r.(VecPhysical); !ok {
+			t.FailNow()
+		}
+	}
+}
+
+func TestAsPreservesVecVirtual(t *testing.T) {
+	collection := NewCollection()
+	cases := []Register{
+		collection.ZMM().AsX(),
+		collection.XMM().AsY(),
+		collection.YMM().AsZ(),
+	}
+	for _, r := range cases {
+		if _, ok := r.(VecVirtual); !ok {
 			t.FailNow()
 		}
 	}
diff --git a/tests/alloc/gp8/asm.go b/tests/alloc/gp8/asm.go
index 88b0b9a..c7c5ac3 100644
--- a/tests/alloc/gp8/asm.go
+++ b/tests/alloc/gp8/asm.go
@@ -21,8 +21,17 @@ func main() {
 
 	// Allocate registers and initialize.
 	x := make([]Register, n)
-	for i := 0; i < n; i++ {
-		x[i] = GP8()
+	i := 0
+
+	// Low byte registers.
+	for ; i < 15; i++ {
+		x[i] = GP8L()
+		MOVB(U8(i+1), x[i])
+	}
+
+	// High byte registers.
+	for ; i < n; i++ {
+		x[i] = GP8H()
 		MOVB(U8(i+1), x[i])
 	}
 
diff --git a/tests/alloc/gp8/gp8.s b/tests/alloc/gp8/gp8.s
index 882496f..ff48db8 100644
--- a/tests/alloc/gp8/gp8.s
+++ b/tests/alloc/gp8/gp8.s
@@ -8,28 +8,24 @@ TEXT ·GP8(SB), NOSPLIT, $0-1
 	MOVB $0x02, CL
 	MOVB $0x03, DL
 	MOVB $0x04, BL
-	MOVB $0x05, AH
-	MOVB $0x06, CH
-	MOVB $0x07, DH
-	MOVB $0x08, BH
-	MOVB $0x09, BP
-	MOVB $0x0a, SI
-	MOVB $0x0b, DI
-	MOVB $0x0c, R8
-	MOVB $0x0d, R9
-	MOVB $0x0e, R10
-	MOVB $0x0f, R11
-	MOVB $0x10, R12
-	MOVB $0x11, R13
-	MOVB $0x12, R14
-	MOVB $0x13, R15
+	MOVB $0x05, BP
+	MOVB $0x06, SI
+	MOVB $0x07, DI
+	MOVB $0x08, R8
+	MOVB $0x09, R9
+	MOVB $0x0a, R10
+	MOVB $0x0b, R11
+	MOVB $0x0c, R12
+	MOVB $0x0d, R13
+	MOVB $0x0e, R14
+	MOVB $0x0f, R15
+	MOVB $0x10, AH
+	MOVB $0x11, CH
+	MOVB $0x12, DH
+	MOVB $0x13, BH
 	ADDB CL, AL
 	ADDB DL, AL
 	ADDB BL, AL
-	ADDB AH, AL
-	ADDB CH, AL
-	ADDB DH, AL
-	ADDB BH, AL
 	ADDB BP, AL
 	ADDB SI, AL
 	ADDB DI, AL
@@ -41,5 +37,9 @@ TEXT ·GP8(SB), NOSPLIT, $0-1
 	ADDB R13, AL
 	ADDB R14, AL
 	ADDB R15, AL
+	ADDB AH, AL
+	ADDB CH, AL
+	ADDB DH, AL
+	ADDB BH, AL
 	MOVB AL, ret+0(FP)
 	RET
diff --git a/tests/alloc/masks/asm.go b/tests/alloc/masks/asm.go
new file mode 100644
index 0000000..6ff51d6
--- /dev/null
+++ b/tests/alloc/masks/asm.go
@@ -0,0 +1,66 @@
+// +build ignore
+
+package main
+
+import (
+	"strconv"
+
+	. "github.com/mmcloughlin/avo/build"
+	. "github.com/mmcloughlin/avo/operand"
+	. "github.com/mmcloughlin/avo/reg"
+)
+
+// The goal of this test is to create a synthetic scenario in which register
+// allocation would fail if register liveness and allocation passes didn't take
+// masks into account.
+//
+// The idea is to create a set of 15 64-bit virtual registers (15 being total
+// number of allocatable 64-bit general purpose registers). For each one: write
+// to the whole register and then later write to only the low 16 bits, and
+// finally consume the whole 64-bit register. This means there is an interval in
+// which only the high 48-bits are live. During this interval we should be able
+// to allocate and use a set of 15 16-bit virtual registers.
+
+func main() {
+	const n = 15
+
+	TEXT("Masks", NOSPLIT, "func() (uint16, uint64)")
+	Doc("Masks computes the sum 1+2+...+" + strconv.Itoa(n) + " in two ways.")
+
+	// Step 1: Allocate n 64-bit registers A that we will arrange to live in their top 48 bits.
+	A := make([]GPVirtual, n)
+	for i := 0; i < n; i++ {
+		A[i] = GP64()
+		c := ((i + 1) << 16) | 42 // 42 in low bits will be cleared later
+		MOVQ(U32(c), A[i])
+	}
+
+	// Step 3: Allocate n 16-bit registers B.
+	B := make([]Register, n)
+	for i := 0; i < n; i++ {
+		B[i] = GP16()
+		MOVW(U16(i+1), B[i])
+	}
+
+	// Step 3: Sum up all the B registers and return.
+	for i := 1; i < n; i++ {
+		ADDW(B[i], B[0])
+	}
+	Store(B[0], ReturnIndex(0))
+
+	// Step 4: Clear the low 16-bits of the A registers.
+	for i := 0; i < n; i++ {
+		MOVW(U16(0), A[i].As16())
+	}
+
+	// Step 5: Sum up all the A registers and return.
+	for i := 1; i < n; i++ {
+		ADDQ(A[i], A[0])
+	}
+	SHRQ(U8(16), A[0])
+	Store(A[0], ReturnIndex(1))
+
+	RET()
+
+	Generate()
+}
diff --git a/tests/alloc/masks/doc.go b/tests/alloc/masks/doc.go
new file mode 100644
index 0000000..9cd2f07
--- /dev/null
+++ b/tests/alloc/masks/doc.go
@@ -0,0 +1,2 @@
+// Package masks tests that register liveness and allocation passes handle masks correctly.
+package masks
diff --git a/tests/alloc/masks/masks.s b/tests/alloc/masks/masks.s
new file mode 100644
index 0000000..6de1045
--- /dev/null
+++ b/tests/alloc/masks/masks.s
@@ -0,0 +1,83 @@
+// Code generated by command: go run asm.go -out masks.s -stubs stub.go. DO NOT EDIT.
+
+#include "textflag.h"
+
+// func Masks() (uint16, uint64)
+TEXT ·Masks(SB), NOSPLIT, $0-16
+	MOVQ $0x0001002a, AX
+	MOVQ $0x0002002a, CX
+	MOVQ $0x0003002a, DX
+	MOVQ $0x0004002a, BX
+	MOVQ $0x0005002a, BP
+	MOVQ $0x0006002a, SI
+	MOVQ $0x0007002a, DI
+	MOVQ $0x0008002a, R8
+	MOVQ $0x0009002a, R9
+	MOVQ $0x000a002a, R10
+	MOVQ $0x000b002a, R11
+	MOVQ $0x000c002a, R12
+	MOVQ $0x000d002a, R13
+	MOVQ $0x000e002a, R14
+	MOVQ $0x000f002a, R15
+	MOVW $0x0001, AX
+	MOVW $0x0002, CX
+	MOVW $0x0003, DX
+	MOVW $0x0004, BX
+	MOVW $0x0005, BP
+	MOVW $0x0006, SI
+	MOVW $0x0007, DI
+	MOVW $0x0008, R8
+	MOVW $0x0009, R9
+	MOVW $0x000a, R10
+	MOVW $0x000b, R11
+	MOVW $0x000c, R12
+	MOVW $0x000d, R13
+	MOVW $0x000e, R14
+	MOVW $0x000f, R15
+	ADDW CX, AX
+	ADDW DX, AX
+	ADDW BX, AX
+	ADDW BP, AX
+	ADDW SI, AX
+	ADDW DI, AX
+	ADDW R8, AX
+	ADDW R9, AX
+	ADDW R10, AX
+	ADDW R11, AX
+	ADDW R12, AX
+	ADDW R13, AX
+	ADDW R14, AX
+	ADDW R15, AX
+	MOVW AX, ret+0(FP)
+	MOVW $0x0000, AX
+	MOVW $0x0000, CX
+	MOVW $0x0000, DX
+	MOVW $0x0000, BX
+	MOVW $0x0000, BP
+	MOVW $0x0000, SI
+	MOVW $0x0000, DI
+	MOVW $0x0000, R8
+	MOVW $0x0000, R9
+	MOVW $0x0000, R10
+	MOVW $0x0000, R11
+	MOVW $0x0000, R12
+	MOVW $0x0000, R13
+	MOVW $0x0000, R14
+	MOVW $0x0000, R15
+	ADDQ CX, AX
+	ADDQ DX, AX
+	ADDQ BX, AX
+	ADDQ BP, AX
+	ADDQ SI, AX
+	ADDQ DI, AX
+	ADDQ R8, AX
+	ADDQ R9, AX
+	ADDQ R10, AX
+	ADDQ R11, AX
+	ADDQ R12, AX
+	ADDQ R13, AX
+	ADDQ R14, AX
+	ADDQ R15, AX
+	SHRQ $0x10, AX
+	MOVQ AX, ret1+8(FP)
+	RET
diff --git a/tests/alloc/masks/masks_test.go b/tests/alloc/masks/masks_test.go
new file mode 100644
index 0000000..b2ff648
--- /dev/null
+++ b/tests/alloc/masks/masks_test.go
@@ -0,0 +1,15 @@
+package masks
+
+import (
+	"testing"
+)
+
+//go:generate go run asm.go -out masks.s -stubs stub.go
+
+func TestMasks(t *testing.T) {
+	const n = 15
+	const expect = n * (n + 1) / 2
+	if got16, got64 := Masks(); got16 != expect || got64 != expect {
+		t.Fatalf("Masks() = %v, %v; expect %v, %v", got16, got64, expect, expect)
+	}
+}
diff --git a/tests/alloc/masks/stub.go b/tests/alloc/masks/stub.go
new file mode 100644
index 0000000..e3712ce
--- /dev/null
+++ b/tests/alloc/masks/stub.go
@@ -0,0 +1,6 @@
+// Code generated by command: go run asm.go -out masks.s -stubs stub.go. DO NOT EDIT.
+
+package masks
+
+// Masks computes the sum 1+2+...+15 in two ways.
+func Masks() (uint16, uint64)
diff --git a/tests/alloc/upper32/asm.go b/tests/alloc/upper32/asm.go
new file mode 100644
index 0000000..de09486
--- /dev/null
+++ b/tests/alloc/upper32/asm.go
@@ -0,0 +1,66 @@
+// +build ignore
+
+package main
+
+import (
+	"strconv"
+
+	. "github.com/mmcloughlin/avo/build"
+	. "github.com/mmcloughlin/avo/operand"
+	. "github.com/mmcloughlin/avo/reg"
+)
+
+// The goal is to test for correct handling of 32-bit operands in 64-bit mode,
+// specifically that writes are zero-extended to 64 bits. This test is
+// constructed such that the register allocator would fail if this feature is
+// not accounted for. It consists of multiple copies of a 32-bit write followed
+// by a 64-bit read of the same register. Without special treatment liveness
+// analysis would consider the upper 32 bits to still be live prior to the
+// write. Therefore if we stack up enough copies of this, we could cause the
+// register allocator to fail.
+
+func main() {
+	const (
+		r = 14 // number of registers
+		m = 3  // number of iterations
+		n = r * m
+	)
+
+	TEXT("Upper32", NOSPLIT, "func() uint64")
+	Doc("Upper32 computes the sum 1+2+...+" + strconv.Itoa(n) + ".")
+
+	Comment("Initialize sum.")
+	s := GP64()
+	XORQ(s, s)
+
+	// Allocate n 64-bit registers and populate them.
+	Comment("Initialize registers.")
+	x := make([]GPVirtual, n)
+	for i := 0; i < n; i++ {
+		x[i] = GP64()
+		MOVQ(U64(0x9e77d78aacb8cbcc), x[i])
+	}
+
+	k := 0
+	for i := 0; i < m; i++ {
+		Commentf("Iteration %d.", i+1)
+
+		// Write to the 32-bit aliases of r registers.
+		for j := 0; j < r; j++ {
+			MOVL(U32(k+j+1), x[k+j].As32())
+		}
+
+		// Sum them up.
+		for j := 0; j < r; j++ {
+			ADDQ(x[k+j], s)
+		}
+
+		k += r
+	}
+
+	Comment("Store result and return.")
+	Store(s, ReturnIndex(0))
+	RET()
+
+	Generate()
+}
diff --git a/tests/alloc/upper32/doc.go b/tests/alloc/upper32/doc.go
new file mode 100644
index 0000000..3efa943
--- /dev/null
+++ b/tests/alloc/upper32/doc.go
@@ -0,0 +1,2 @@
+// Package upper32 tests liveness analysis of 32-bit operations on 64-bit registers.
+package upper32
diff --git a/tests/alloc/upper32/stub.go b/tests/alloc/upper32/stub.go
new file mode 100644
index 0000000..77e0c60
--- /dev/null
+++ b/tests/alloc/upper32/stub.go
@@ -0,0 +1,6 @@
+// Code generated by command: go run asm.go -out upper32.s -stubs stub.go. DO NOT EDIT.
+
+package upper32
+
+// Upper32 computes the sum 1+2+...+42.
+func Upper32() uint64
diff --git a/tests/alloc/upper32/upper32.s b/tests/alloc/upper32/upper32.s
new file mode 100644
index 0000000..21aaa36
--- /dev/null
+++ b/tests/alloc/upper32/upper32.s
@@ -0,0 +1,146 @@
+// Code generated by command: go run asm.go -out upper32.s -stubs stub.go. DO NOT EDIT.
+
+#include "textflag.h"
+
+// func Upper32() uint64
+TEXT ·Upper32(SB), NOSPLIT, $0-8
+	// Initialize sum.
+	XORQ AX, AX
+
+	// Initialize registers.
+	MOVQ $0x9e77d78aacb8cbcc, CX
+	MOVQ $0x9e77d78aacb8cbcc, DX
+	MOVQ $0x9e77d78aacb8cbcc, BX
+	MOVQ $0x9e77d78aacb8cbcc, BP
+	MOVQ $0x9e77d78aacb8cbcc, SI
+	MOVQ $0x9e77d78aacb8cbcc, DI
+	MOVQ $0x9e77d78aacb8cbcc, R8
+	MOVQ $0x9e77d78aacb8cbcc, R9
+	MOVQ $0x9e77d78aacb8cbcc, R10
+	MOVQ $0x9e77d78aacb8cbcc, R11
+	MOVQ $0x9e77d78aacb8cbcc, R12
+	MOVQ $0x9e77d78aacb8cbcc, R13
+	MOVQ $0x9e77d78aacb8cbcc, R14
+	MOVQ $0x9e77d78aacb8cbcc, R15
+	MOVQ $0x9e77d78aacb8cbcc, CX
+	MOVQ $0x9e77d78aacb8cbcc, DX
+	MOVQ $0x9e77d78aacb8cbcc, BX
+	MOVQ $0x9e77d78aacb8cbcc, BP
+	MOVQ $0x9e77d78aacb8cbcc, SI
+	MOVQ $0x9e77d78aacb8cbcc, DI
+	MOVQ $0x9e77d78aacb8cbcc, R8
+	MOVQ $0x9e77d78aacb8cbcc, R9
+	MOVQ $0x9e77d78aacb8cbcc, R10
+	MOVQ $0x9e77d78aacb8cbcc, R11
+	MOVQ $0x9e77d78aacb8cbcc, R12
+	MOVQ $0x9e77d78aacb8cbcc, R13
+	MOVQ $0x9e77d78aacb8cbcc, R14
+	MOVQ $0x9e77d78aacb8cbcc, R15
+	MOVQ $0x9e77d78aacb8cbcc, CX
+	MOVQ $0x9e77d78aacb8cbcc, DX
+	MOVQ $0x9e77d78aacb8cbcc, BX
+	MOVQ $0x9e77d78aacb8cbcc, BP
+	MOVQ $0x9e77d78aacb8cbcc, SI
+	MOVQ $0x9e77d78aacb8cbcc, DI
+	MOVQ $0x9e77d78aacb8cbcc, R8
+	MOVQ $0x9e77d78aacb8cbcc, R9
+	MOVQ $0x9e77d78aacb8cbcc, R10
+	MOVQ $0x9e77d78aacb8cbcc, R11
+	MOVQ $0x9e77d78aacb8cbcc, R12
+	MOVQ $0x9e77d78aacb8cbcc, R13
+	MOVQ $0x9e77d78aacb8cbcc, R14
+	MOVQ $0x9e77d78aacb8cbcc, R15
+
+	// Iteration 1.
+	MOVL $0x00000001, CX
+	MOVL $0x00000002, DX
+	MOVL $0x00000003, BX
+	MOVL $0x00000004, BP
+	MOVL $0x00000005, SI
+	MOVL $0x00000006, DI
+	MOVL $0x00000007, R8
+	MOVL $0x00000008, R9
+	MOVL $0x00000009, R10
+	MOVL $0x0000000a, R11
+	MOVL $0x0000000b, R12
+	MOVL $0x0000000c, R13
+	MOVL $0x0000000d, R14
+	MOVL $0x0000000e, R15
+	ADDQ CX, AX
+	ADDQ DX, AX
+	ADDQ BX, AX
+	ADDQ BP, AX
+	ADDQ SI, AX
+	ADDQ DI, AX
+	ADDQ R8, AX
+	ADDQ R9, AX
+	ADDQ R10, AX
+	ADDQ R11, AX
+	ADDQ R12, AX
+	ADDQ R13, AX
+	ADDQ R14, AX
+	ADDQ R15, AX
+
+	// Iteration 2.
+	MOVL $0x0000000f, CX
+	MOVL $0x00000010, DX
+	MOVL $0x00000011, BX
+	MOVL $0x00000012, BP
+	MOVL $0x00000013, SI
+	MOVL $0x00000014, DI
+	MOVL $0x00000015, R8
+	MOVL $0x00000016, R9
+	MOVL $0x00000017, R10
+	MOVL $0x00000018, R11
+	MOVL $0x00000019, R12
+	MOVL $0x0000001a, R13
+	MOVL $0x0000001b, R14
+	MOVL $0x0000001c, R15
+	ADDQ CX, AX
+	ADDQ DX, AX
+	ADDQ BX, AX
+	ADDQ BP, AX
+	ADDQ SI, AX
+	ADDQ DI, AX
+	ADDQ R8, AX
+	ADDQ R9, AX
+	ADDQ R10, AX
+	ADDQ R11, AX
+	ADDQ R12, AX
+	ADDQ R13, AX
+	ADDQ R14, AX
+	ADDQ R15, AX
+
+	// Iteration 3.
+	MOVL $0x0000001d, CX
+	MOVL $0x0000001e, DX
+	MOVL $0x0000001f, BX
+	MOVL $0x00000020, BP
+	MOVL $0x00000021, SI
+	MOVL $0x00000022, DI
+	MOVL $0x00000023, R8
+	MOVL $0x00000024, R9
+	MOVL $0x00000025, R10
+	MOVL $0x00000026, R11
+	MOVL $0x00000027, R12
+	MOVL $0x00000028, R13
+	MOVL $0x00000029, R14
+	MOVL $0x0000002a, R15
+	ADDQ CX, AX
+	ADDQ DX, AX
+	ADDQ BX, AX
+	ADDQ BP, AX
+	ADDQ SI, AX
+	ADDQ DI, AX
+	ADDQ R8, AX
+	ADDQ R9, AX
+	ADDQ R10, AX
+	ADDQ R11, AX
+	ADDQ R12, AX
+	ADDQ R13, AX
+	ADDQ R14, AX
+	ADDQ R15, AX
+
+	// Store result and return.
+	MOVQ AX, ret+0(FP)
+	RET
diff --git a/tests/alloc/upper32/upper32_test.go b/tests/alloc/upper32/upper32_test.go
new file mode 100644
index 0000000..9ed2e62
--- /dev/null
+++ b/tests/alloc/upper32/upper32_test.go
@@ -0,0 +1,15 @@
+package upper32
+
+import (
+	"testing"
+)
+
+//go:generate go run asm.go -out upper32.s -stubs stub.go
+
+func TestUpper32(t *testing.T) {
+	const n = 14 * 3
+	const expect = n * (n + 1) / 2
+	if got := Upper32(); got != expect {
+		t.Fatalf("Upper32() = %v; expect %v", got, expect)
+	}
+}
diff --git a/tests/fixedbugs/issue100/asm.go b/tests/fixedbugs/issue100/asm.go
new file mode 100644
index 0000000..98374e3
--- /dev/null
+++ b/tests/fixedbugs/issue100/asm.go
@@ -0,0 +1,22 @@
+// +build ignore
+
+package main
+
+import (
+	. "github.com/mmcloughlin/avo/build"
+	. "github.com/mmcloughlin/avo/operand"
+)
+
+func main() {
+	TEXT("Issue100", NOSPLIT, "func() uint64")
+	x := GP64()
+	XORQ(x, x)
+	for i := 1; i <= 100; i++ {
+		t := GP64()
+		MOVQ(U32(i), t)
+		ADDQ(t.As64(), x)
+	}
+	Store(x, ReturnIndex(0))
+	RET()
+	Generate()
+}
diff --git a/tests/fixedbugs/issue100/doc.go b/tests/fixedbugs/issue100/doc.go
new file mode 100644
index 0000000..e6495d8
--- /dev/null
+++ b/tests/fixedbugs/issue100/doc.go
@@ -0,0 +1,2 @@
+// Package issue100 contains a reproducer for a bug in aliased register allocation.
+package issue100
diff --git a/tests/fixedbugs/issue100/issue100.s b/tests/fixedbugs/issue100/issue100.s
new file mode 100644
index 0000000..ef14ab0
--- /dev/null
+++ b/tests/fixedbugs/issue100/issue100.s
@@ -0,0 +1,209 @@
+// Code generated by command: go run asm.go -out issue100.s -stubs stub.go. DO NOT EDIT.
+
+#include "textflag.h"
+
+// func Issue100() uint64
+TEXT ·Issue100(SB), NOSPLIT, $0-8
+	XORQ AX, AX
+	MOVQ $0x00000001, CX
+	ADDQ CX, AX
+	MOVQ $0x00000002, CX
+	ADDQ CX, AX
+	MOVQ $0x00000003, CX
+	ADDQ CX, AX
+	MOVQ $0x00000004, CX
+	ADDQ CX, AX
+	MOVQ $0x00000005, CX
+	ADDQ CX, AX
+	MOVQ $0x00000006, CX
+	ADDQ CX, AX
+	MOVQ $0x00000007, CX
+	ADDQ CX, AX
+	MOVQ $0x00000008, CX
+	ADDQ CX, AX
+	MOVQ $0x00000009, CX
+	ADDQ CX, AX
+	MOVQ $0x0000000a, CX
+	ADDQ CX, AX
+	MOVQ $0x0000000b, CX
+	ADDQ CX, AX
+	MOVQ $0x0000000c, CX
+	ADDQ CX, AX
+	MOVQ $0x0000000d, CX
+	ADDQ CX, AX
+	MOVQ $0x0000000e, CX
+	ADDQ CX, AX
+	MOVQ $0x0000000f, CX
+	ADDQ CX, AX
+	MOVQ $0x00000010, CX
+	ADDQ CX, AX
+	MOVQ $0x00000011, CX
+	ADDQ CX, AX
+	MOVQ $0x00000012, CX
+	ADDQ CX, AX
+	MOVQ $0x00000013, CX
+	ADDQ CX, AX
+	MOVQ $0x00000014, CX
+	ADDQ CX, AX
+	MOVQ $0x00000015, CX
+	ADDQ CX, AX
+	MOVQ $0x00000016, CX
+	ADDQ CX, AX
+	MOVQ $0x00000017, CX
+	ADDQ CX, AX
+	MOVQ $0x00000018, CX
+	ADDQ CX, AX
+	MOVQ $0x00000019, CX
+	ADDQ CX, AX
+	MOVQ $0x0000001a, CX
+	ADDQ CX, AX
+	MOVQ $0x0000001b, CX
+	ADDQ CX, AX
+	MOVQ $0x0000001c, CX
+	ADDQ CX, AX
+	MOVQ $0x0000001d, CX
+	ADDQ CX, AX
+	MOVQ $0x0000001e, CX
+	ADDQ CX, AX
+	MOVQ $0x0000001f, CX
+	ADDQ CX, AX
+	MOVQ $0x00000020, CX
+	ADDQ CX, AX
+	MOVQ $0x00000021, CX
+	ADDQ CX, AX
+	MOVQ $0x00000022, CX
+	ADDQ CX, AX
+	MOVQ $0x00000023, CX
+	ADDQ CX, AX
+	MOVQ $0x00000024, CX
+	ADDQ CX, AX
+	MOVQ $0x00000025, CX
+	ADDQ CX, AX
+	MOVQ $0x00000026, CX
+	ADDQ CX, AX
+	MOVQ $0x00000027, CX
+	ADDQ CX, AX
+	MOVQ $0x00000028, CX
+	ADDQ CX, AX
+	MOVQ $0x00000029, CX
+	ADDQ CX, AX
+	MOVQ $0x0000002a, CX
+	ADDQ CX, AX
+	MOVQ $0x0000002b, CX
+	ADDQ CX, AX
+	MOVQ $0x0000002c, CX
+	ADDQ CX, AX
+	MOVQ $0x0000002d, CX
+	ADDQ CX, AX
+	MOVQ $0x0000002e, CX
+	ADDQ CX, AX
+	MOVQ $0x0000002f, CX
+	ADDQ CX, AX
+	MOVQ $0x00000030, CX
+	ADDQ CX, AX
+	MOVQ $0x00000031, CX
+	ADDQ CX, AX
+	MOVQ $0x00000032, CX
+	ADDQ CX, AX
+	MOVQ $0x00000033, CX
+	ADDQ CX, AX
+	MOVQ $0x00000034, CX
+	ADDQ CX, AX
+	MOVQ $0x00000035, CX
+	ADDQ CX, AX
+	MOVQ $0x00000036, CX
+	ADDQ CX, AX
+	MOVQ $0x00000037, CX
+	ADDQ CX, AX
+	MOVQ $0x00000038, CX
+	ADDQ CX, AX
+	MOVQ $0x00000039, CX
+	ADDQ CX, AX
+	MOVQ $0x0000003a, CX
+	ADDQ CX, AX
+	MOVQ $0x0000003b, CX
+	ADDQ CX, AX
+	MOVQ $0x0000003c, CX
+	ADDQ CX, AX
+	MOVQ $0x0000003d, CX
+	ADDQ CX, AX
+	MOVQ $0x0000003e, CX
+	ADDQ CX, AX
+	MOVQ $0x0000003f, CX
+	ADDQ CX, AX
+	MOVQ $0x00000040, CX
+	ADDQ CX, AX
+	MOVQ $0x00000041, CX
+	ADDQ CX, AX
+	MOVQ $0x00000042, CX
+	ADDQ CX, AX
+	MOVQ $0x00000043, CX
+	ADDQ CX, AX
+	MOVQ $0x00000044, CX
+	ADDQ CX, AX
+	MOVQ $0x00000045, CX
+	ADDQ CX, AX
+	MOVQ $0x00000046, CX
+	ADDQ CX, AX
+	MOVQ $0x00000047, CX
+	ADDQ CX, AX
+	MOVQ $0x00000048, CX
+	ADDQ CX, AX
+	MOVQ $0x00000049, CX
+	ADDQ CX, AX
+	MOVQ $0x0000004a, CX
+	ADDQ CX, AX
+	MOVQ $0x0000004b, CX
+	ADDQ CX, AX
+	MOVQ $0x0000004c, CX
+	ADDQ CX, AX
+	MOVQ $0x0000004d, CX
+	ADDQ CX, AX
+	MOVQ $0x0000004e, CX
+	ADDQ CX, AX
+	MOVQ $0x0000004f, CX
+	ADDQ CX, AX
+	MOVQ $0x00000050, CX
+	ADDQ CX, AX
+	MOVQ $0x00000051, CX
+	ADDQ CX, AX
+	MOVQ $0x00000052, CX
+	ADDQ CX, AX
+	MOVQ $0x00000053, CX
+	ADDQ CX, AX
+	MOVQ $0x00000054, CX
+	ADDQ CX, AX
+	MOVQ $0x00000055, CX
+	ADDQ CX, AX
+	MOVQ $0x00000056, CX
+	ADDQ CX, AX
+	MOVQ $0x00000057, CX
+	ADDQ CX, AX
+	MOVQ $0x00000058, CX
+	ADDQ CX, AX
+	MOVQ $0x00000059, CX
+	ADDQ CX, AX
+	MOVQ $0x0000005a, CX
+	ADDQ CX, AX
+	MOVQ $0x0000005b, CX
+	ADDQ CX, AX
+	MOVQ $0x0000005c, CX
+	ADDQ CX, AX
+	MOVQ $0x0000005d, CX
+	ADDQ CX, AX
+	MOVQ $0x0000005e, CX
+	ADDQ CX, AX
+	MOVQ $0x0000005f, CX
+	ADDQ CX, AX
+	MOVQ $0x00000060, CX
+	ADDQ CX, AX
+	MOVQ $0x00000061, CX
+	ADDQ CX, AX
+	MOVQ $0x00000062, CX
+	ADDQ CX, AX
+	MOVQ $0x00000063, CX
+	ADDQ CX, AX
+	MOVQ $0x00000064, CX
+	ADDQ CX, AX
+	MOVQ AX, ret+0(FP)
+	RET
diff --git a/tests/fixedbugs/issue100/issue100_test.go b/tests/fixedbugs/issue100/issue100_test.go
new file mode 100644
index 0000000..0d0e692
--- /dev/null
+++ b/tests/fixedbugs/issue100/issue100_test.go
@@ -0,0 +1,15 @@
+package issue100
+
+import (
+	"testing"
+)
+
+//go:generate go run asm.go -out issue100.s -stubs stub.go
+
+func TestIssue100(t *testing.T) {
+	n := uint64(100)
+	expect := n * (n + 1) / 2
+	if got := Issue100(); got != expect {
+		t.Fatalf("Issue100() = %v; expect %v", got, expect)
+	}
+}
diff --git a/tests/fixedbugs/issue100/stub.go b/tests/fixedbugs/issue100/stub.go
new file mode 100644
index 0000000..8a2086a
--- /dev/null
+++ b/tests/fixedbugs/issue100/stub.go
@@ -0,0 +1,5 @@
+// Code generated by command: go run asm.go -out issue100.s -stubs stub.go. DO NOT EDIT.
+
+package issue100
+
+func Issue100() uint64
diff --git a/tests/fixedbugs/issue65/castphysical.go b/tests/fixedbugs/issue65/castphysical.go
new file mode 100644
index 0000000..1cae787
--- /dev/null
+++ b/tests/fixedbugs/issue65/castphysical.go
@@ -0,0 +1,23 @@
+// +build generate
+
+//go:generate go run $GOFILE
+
+// Regression test for a bug where casting a physical register would give the
+// error "non physical register found".
+//
+// See: https://github.com/mmcloughlin/avo/issues/65#issuecomment-576850145
+
+package main
+
+import (
+	. "github.com/mmcloughlin/avo/build"
+	. "github.com/mmcloughlin/avo/operand"
+	. "github.com/mmcloughlin/avo/reg"
+)
+
+func main() {
+	TEXT("Issue65", NOSPLIT, "func()")
+	VINSERTI128(Imm(1), Y0.AsX(), Y1, Y2)
+	RET()
+	Generate()
+}