Repository: tetratelabs/wazero
Pull request #1804 (2023-10-19 17:40:06)

wazevo: repesent regalloc kills with a bitset
Based on #1803, this PR changes the data structure used to represent regalloc kills from a map to a bitset, which reduces the memory footprint by 190MB on the compilation of Python:

```
github.com/tetratelabs/wazero/internal/engine/wazevo/backend/regalloc/regalloc.go

  Total:   -192.65MB    15.38MB (flat, cum) 0.062%
    250    -192.65MB  -192.65MB           			if _, ok := outs[use]; !ok { 
    251            .   208.03MB           				info.kills.Insert(use) 
    252            .          .           			} 
    253            .          .           		}) 
    254            .          .            
    255            .          .           		if wazevoapi.RegAllocLoggingEnabled { 
    256            .          .           			fmt.Printf("\nfinalized info for block[%d]:\n%s\n", blk.ID(), info.Format(a.regInfo)) 
```

mathetake: ok I thought all PRs ware targeting the main :D 

Patch:
diff --git a/internal/engine/wazevo/backend/regalloc/reg.go b/internal/engine/wazevo/backend/regalloc/reg.go
index 1e8cc71c..48019a36 100644
--- a/internal/engine/wazevo/backend/regalloc/reg.go
+++ b/internal/engine/wazevo/backend/regalloc/reg.go
@@ -114,7 +114,7 @@ func (t *VRegTable) Reset(minVRegIDs VRegIDMinSet) {
 
 // VRegTypeTable implements a table for virtual registers of a specific type.
 //
-// The parent VRegTable uses 4 instances of this type to maintain a table for
+// The parent VRegTable uses 3 instances of this type to maintain a table for
 // each virtual register type.
 //
 // The virtual register type table uses a bitset to accelerate checking whether
@@ -157,14 +157,91 @@ func (t *VRegTypeTable) Range(f func(VRegID, programCounter)) {
 
 func (t *VRegTypeTable) Reset(minVRegID VRegID) {
 	t.min = minVRegID
-	t.set = nil
+	t.set.reset()
 	t.pcs = nil
 }
 
-type bitset []uint64
+// VRegSet is a data structure designed for fast lookup in a set of virtual
+// registers.
+//
+// The type maintains one instance of VRegTypeSet for each register type:
+// invalid, int, and float. It dispatches between the sub sets based on the
+// type of virtual registers that are inserted.
+//
+// Note that there is no way to delete entries, the sets are constructed and
+// then used until they are either reset or go unused.
+type VRegSet [NumRegType]VRegTypeSet
+
+func (s *VRegSet) Contains(v VReg) bool {
+	return s[v.RegType()].Contains(v.ID())
+}
+
+func (s *VRegSet) Insert(v VReg) {
+	if v.IsRealReg() {
+		panic("BUG: cannot insert real registers in virtual register table")
+	}
+	s[v.RegType()].Insert(v.ID())
+}
 
-func (b bitset) scan(f func(uint)) {
-	for i, v := range b {
+func (s *VRegSet) Range(f func(VReg)) {
+	for i := range s {
+		s[i].Range(func(id VRegID) {
+			f(VReg(id).SetRegType(RegType(i)))
+		})
+	}
+}
+
+func (s *VRegSet) Reset(minVRegIDs VRegIDMinSet) {
+	for i := range s {
+		s[i].Reset(minVRegIDs.Min(RegType(i)))
+	}
+}
+
+// VRegTypeSet implements a set for virtual registers of a specific type.
+//
+// The parent VRegSet uses 3 instances of this type to maintain a table for each
+// virtual register type.
+//
+// The virtual register type set uses a bitset to minimize the memory footprint,
+// registers ids are offseted by the minimum entry, and represented by a bit bit
+// set to 1 in the bitset.
+type VRegTypeSet struct {
+	min VRegID
+	set bitset
+}
+
+func (s *VRegTypeSet) Contains(id VRegID) bool {
+	return s.set.has(uint(id - s.min))
+}
+
+func (s *VRegTypeSet) Insert(id VRegID) {
+	s.set.set(uint(id - s.min))
+}
+
+func (s *VRegTypeSet) Range(f func(VRegID)) {
+	s.set.scan(func(i uint) { f(VRegID(i) + s.min) })
+}
+
+func (s *VRegTypeSet) Reset(minVRegID VRegID) {
+	s.min = minVRegID
+	s.set.reset()
+}
+
+type bitset struct {
+	bits []uint64
+	// Most of the bitset values have short backing arrays, to reduce the memory
+	// footprint we use this buffer as backing array for storing up to 320 bits.
+	// When more bits need to be stored, the backing array are offloaded to the
+	// heap.
+	buf [5]uint64
+}
+
+func (b *bitset) reset() {
+	b.bits, b.buf = nil, [5]uint64{}
+}
+
+func (b *bitset) scan(f func(uint)) {
+	for i, v := range b.bits {
 		for j := uint(i * 64); v != 0; j++ {
 			n := uint(bits.TrailingZeros64(v))
 			j += n
@@ -174,17 +251,22 @@ func (b bitset) scan(f func(uint)) {
 	}
 }
 
-func (b bitset) has(i uint) bool {
+func (b *bitset) has(i uint) bool {
 	index, shift := i/64, i%64
-	return index < uint(len(b)) && ((b[index] & (1 << shift)) != 0)
+	return index < uint(len(b.bits)) && ((b.bits[index] & (1 << shift)) != 0)
 }
 
 func (b *bitset) set(i uint) {
 	index, shift := i/64, i%64
-	if index >= uint(len(*b)) {
-		*b = append(*b, make([]uint64, (index+1)-uint(len(*b)))...)
+	if index >= uint(len(b.bits)) {
+		if index < uint(len(b.buf)) {
+			b.bits = b.buf[:]
+		} else {
+			b.bits = append(b.bits, make([]uint64, (index+1)-uint(len(b.bits)))...)
+			b.buf = [5]uint64{}
+		}
 	}
-	(*b)[index] |= 1 << shift
+	b.bits[index] |= 1 << shift
 }
 
 // RealReg represents a physical register.
diff --git a/internal/engine/wazevo/backend/regalloc/regalloc.go b/internal/engine/wazevo/backend/regalloc/regalloc.go
index 7642111f..1b5c183e 100644
--- a/internal/engine/wazevo/backend/regalloc/regalloc.go
+++ b/internal/engine/wazevo/backend/regalloc/regalloc.go
@@ -20,8 +20,9 @@ import (
 // NewAllocator returns a new Allocator.
 func NewAllocator(allocatableRegs *RegisterInfo) Allocator {
 	a := Allocator{
-		regInfo:  allocatableRegs,
-		nodePool: wazevoapi.NewPool[node](resetNode),
+		regInfo:       allocatableRegs,
+		nodePool:      wazevoapi.NewPool[node](resetNode),
+		blockInfoPool: wazevoapi.NewPool[blockInfo](resetBlockInfo),
 	}
 	for _, regs := range allocatableRegs.AllocatableRegisters {
 		for _, r := range regs {
@@ -55,9 +56,10 @@ type (
 		allocatedRegSet          [RealRegsNumMax]bool
 		allocatedCalleeSavedRegs []VReg
 		nodePool                 wazevoapi.Pool[node]
+		blockInfoPool            wazevoapi.Pool[blockInfo]
 		// vRegIDToNode maps VRegID to the node whose node.v has the VRegID.
 		vRegIDToNode [] /* VRegID to */ *node
-		blockInfos   [] /* blockID to */ blockInfo
+		blockInfos   [] /* blockID to */ *blockInfo
 		vs           []VReg
 		spillHandler spillHandler
 		// phis keeps track of the VRegs that are defined by phi functions.
@@ -79,7 +81,7 @@ type (
 		liveIns  map[VReg]struct{}
 		defs     map[VReg]programCounter
 		lastUses VRegTable
-		kills    map[VReg]struct{}
+		kills    VRegSet
 		// Pre-colored real registers can have multiple live ranges in one block.
 		realRegUses [vRegIDReservedForRealNum][]programCounter
 		realRegDefs [vRegIDReservedForRealNum][]programCounter
@@ -184,6 +186,7 @@ func (a *Allocator) livenessAnalysis(f Function) {
 			}
 		}
 		info.lastUses.Reset(minVRegID)
+		info.kills.Reset(minVRegID)
 
 		var pc programCounter
 		for instr := blk.InstrIteratorBegin(); instr != nil; instr = blk.InstrIteratorNext() {
@@ -247,7 +250,7 @@ func (a *Allocator) livenessAnalysis(f Function) {
 		info.lastUses.Range(func(use VReg, pc programCounter) {
 			// Usage without live-outs is a kill.
 			if _, ok := outs[use]; !ok {
-				info.kills[use] = struct{}{}
+				info.kills.Insert(use)
 			}
 		})
 
@@ -326,7 +329,7 @@ func (a *Allocator) buildLiveRanges(f Function) {
 }
 
 func (a *Allocator) buildLiveRangesForNonReals(info *blockInfo) {
-	ins, outs, defs, kills := info.liveIns, info.liveOuts, info.defs, info.kills
+	ins, outs, defs := info.liveIns, info.liveOuts, info.defs
 
 	// In order to do the deterministic allocation, we need to sort ins.
 	vs := a.vs[:0]
@@ -344,12 +347,11 @@ func (a *Allocator) buildLiveRangesForNonReals(info *blockInfo) {
 		if _, ok := outs[v]; ok {
 			// v is live-in and live-out, so it is live-through.
 			begin, end = 0, math.MaxInt32
-			if _, ok := kills[v]; ok {
+			if info.kills.Contains(v) {
 				panic("BUG: v is live-out but also killed")
 			}
 		} else {
-			_, ok := kills[v]
-			if !ok {
+			if !info.kills.Contains(v) {
 				panic("BUG: v is live-in but not live-out or use")
 			}
 			// v is killed at killPos.
@@ -383,12 +385,11 @@ func (a *Allocator) buildLiveRangesForNonReals(info *blockInfo) {
 		if _, ok := outs[v]; ok {
 			// v is defined here and live-out, so it is live-through.
 			end = math.MaxInt32
-			if _, ok := kills[v]; ok {
+			if info.kills.Contains(v) {
 				panic("BUG: v is killed here but also killed")
 			}
 		} else {
-			_, ok := kills[v]
-			if !ok {
+			if !info.kills.Contains(v) {
 				// This case the defined value is not used at all.
 				end = defPos
 			} else {
@@ -405,7 +406,7 @@ func (a *Allocator) buildLiveRangesForNonReals(info *blockInfo) {
 	a.vs = vs[:0]
 
 	if wazevoapi.RegAllocValidationEnabled {
-		for u := range kills {
+		info.kills.Range(func(u VReg) {
 			if !u.IsRealReg() {
 				_, defined := defs[u]
 				_, liveIn := ins[u]
@@ -413,7 +414,7 @@ func (a *Allocator) buildLiveRangesForNonReals(info *blockInfo) {
 					panic(fmt.Sprintf("BUG: %v is killed but not defined or live-in", u))
 				}
 			}
-		}
+		})
 	}
 }
 
@@ -456,6 +457,7 @@ func (a *Allocator) buildLiveRangesForReals(info *blockInfo) {
 func (a *Allocator) Reset() {
 	a.nodePool.Reset()
 	a.blockInfos = a.blockInfos[:0]
+	a.blockInfoPool.Reset()
 	for i := range a.vRegIDToNode {
 		a.vRegIDToNode[i] = nil
 	}
@@ -475,15 +477,18 @@ func (a *Allocator) Reset() {
 
 func (a *Allocator) allocateBlockInfo(blockID int) *blockInfo {
 	if blockID >= len(a.blockInfos) {
-		a.blockInfos = append(a.blockInfos, make([]blockInfo, (blockID+1)-len(a.blockInfos))...)
+		a.blockInfos = append(a.blockInfos, make([]*blockInfo, (blockID+1)-len(a.blockInfos))...)
+	}
+	info := a.blockInfos[blockID]
+	if info == nil {
+		info = a.blockInfoPool.Allocate()
+		a.blockInfos[blockID] = info
 	}
-	info := &a.blockInfos[blockID]
-	a.initBlockInfo(info)
 	return info
 }
 
 func (a *Allocator) blockInfoAt(blockID int) (info *blockInfo) {
-	info = &a.blockInfos[blockID]
+	info = a.blockInfos[blockID]
 	return
 }
 
@@ -505,6 +510,22 @@ func (a *Allocator) getOrAllocateNode(v VReg) (n *node) {
 	return
 }
 
+func resetBlockInfo(i *blockInfo) {
+	if i.intervalMng == nil {
+		i.intervalMng = newIntervalManager()
+	} else {
+		i.intervalMng.reset()
+	}
+	i.liveOuts = resetMap(i.liveOuts)
+	i.liveIns = resetMap(i.liveIns)
+	i.defs = resetMap(i.defs)
+
+	for index := range i.realRegUses {
+		i.realRegUses[index] = i.realRegUses[index][:0]
+		i.realRegDefs[index] = i.realRegDefs[index][:0]
+	}
+}
+
 func resetNode(n *node) {
 	n.r = RealRegInvalid
 	n.v = VRegInvalid
@@ -518,55 +539,23 @@ func resetNode(n *node) {
 	n.visited = false
 }
 
+func resetMap[K comparable, V any](m map[K]V) map[K]V {
+	if m == nil {
+		m = make(map[K]V)
+	} else {
+		for v := range m {
+			delete(m, v)
+		}
+	}
+	return m
+}
+
 func (a *Allocator) allocateNode() (n *node) {
 	n = a.nodePool.Allocate()
 	n.id = a.nodePool.Allocated() - 1
 	return
 }
 
-func resetMap[T any](a *Allocator, m map[VReg]T) {
-	a.vs = a.vs[:0]
-	for v := range m {
-		a.vs = append(a.vs, v)
-	}
-	for _, v := range a.vs {
-		delete(m, v)
-	}
-}
-
-func (a *Allocator) initBlockInfo(i *blockInfo) {
-	if i.intervalMng == nil {
-		i.intervalMng = newIntervalManager()
-	} else {
-		i.intervalMng.reset()
-	}
-	if i.liveOuts == nil {
-		i.liveOuts = make(map[VReg]struct{})
-	} else {
-		resetMap(a, i.liveOuts)
-	}
-	if i.liveIns == nil {
-		i.liveIns = make(map[VReg]struct{})
-	} else {
-		resetMap(a, i.liveIns)
-	}
-	if i.defs == nil {
-		i.defs = make(map[VReg]programCounter)
-	} else {
-		resetMap(a, i.defs)
-	}
-	if i.kills == nil {
-		i.kills = make(map[VReg]struct{})
-	} else {
-		resetMap(a, i.kills)
-	}
-
-	for index := range i.realRegUses {
-		i.realRegUses[index] = i.realRegUses[index][:0]
-		i.realRegDefs[index] = i.realRegDefs[index][:0]
-	}
-}
-
 func (i *blockInfo) addRealRegUsage(v VReg, pc programCounter) {
 	id := v.ID()
 	defs := i.realRegDefs[id]
@@ -598,9 +587,9 @@ func (i *blockInfo) Format(ri *RegisterInfo) string {
 		buf.WriteString(fmt.Sprintf("%v@%v ", v, pos))
 	})
 	buf.WriteString("\n\tkills: ")
-	for v, pos := range i.kills {
-		buf.WriteString(fmt.Sprintf("%v@%v ", v, pos))
-	}
+	i.kills.Range(func(v VReg) {
+		buf.WriteString(fmt.Sprintf("%v@%v ", v, i.lastUses.Lookup(v)))
+	})
 	buf.WriteString("\n\trealRegUses: ")
 	for v, pos := range i.realRegUses {
 		if len(pos) > 0 {


Test patch:
diff --git a/internal/engine/wazevo/backend/regalloc/reg_test.go b/internal/engine/wazevo/backend/regalloc/reg_test.go
index 84600cde..2dda28a1 100644
--- a/internal/engine/wazevo/backend/regalloc/reg_test.go
+++ b/internal/engine/wazevo/backend/regalloc/reg_test.go
@@ -55,3 +55,31 @@ func TestVRegTable(t *testing.T) {
 	})
 	require.Equal(t, 0, len(vregs))
 }
+
+func TestVRegSet(t *testing.T) {
+	min := VRegIDMinSet{}
+	min.Observe(VReg(vRegIDReservedForRealNum + 2))
+	min.Observe(VReg(vRegIDReservedForRealNum + 1))
+	min.Observe(VReg(vRegIDReservedForRealNum + 0))
+
+	set := VRegSet{}
+	set.Reset(min)
+	set.Insert(VReg(vRegIDReservedForRealNum + 0))
+	set.Insert(VReg(vRegIDReservedForRealNum + 1))
+	set.Insert(VReg(vRegIDReservedForRealNum + 2))
+
+	vregs := map[VReg]struct{}{}
+	set.Range(func(v VReg) {
+		vregs[v] = struct{}{}
+	})
+	require.Equal(t, 3, len(vregs))
+
+	for v := range vregs {
+		require.True(t, set.Contains(v))
+	}
+
+	set.Range(func(v VReg) {
+		delete(vregs, v)
+	})
+	require.Equal(t, 0, len(vregs))
+}
diff --git a/internal/engine/wazevo/backend/regalloc/regalloc_test.go b/internal/engine/wazevo/backend/regalloc/regalloc_test.go
index a0205af2..e2605a44 100644
--- a/internal/engine/wazevo/backend/regalloc/regalloc_test.go
+++ b/internal/engine/wazevo/backend/regalloc/regalloc_test.go
@@ -6,18 +6,37 @@ import (
 	"github.com/tetratelabs/wazero/internal/testing/require"
 )
 
-func makeVRegTable(vregs map[VReg]programCounter) (table VRegTable) {
-	min := VRegIDMinSet{}
+func makeVRegIDMinSet[T any](vregs map[VReg]T) (min VRegIDMinSet) {
 	for v := range vregs {
 		min.Observe(v)
 	}
-	table.Reset(min)
+	return min
+}
+
+func makeVRegSet(vregs map[VReg]struct{}) (set VRegSet) {
+	set.Reset(makeVRegIDMinSet(vregs))
+	for v := range vregs {
+		set.Insert(v)
+	}
+	return set
+}
+
+func makeVRegTable(vregs map[VReg]programCounter) (table VRegTable) {
+	table.Reset(makeVRegIDMinSet(vregs))
 	for v, p := range vregs {
 		table.Insert(v, p)
 	}
 	return table
 }
 
+func makeVRegSetEmpty(min0, min1, min2 VRegID) VRegSet {
+	return VRegSet{
+		0: VRegTypeSet{min: min0},
+		1: VRegTypeSet{min: min1},
+		2: VRegTypeSet{min: min2},
+	}
+}
+
 func TestAllocator_livenessAnalysis(t *testing.T) {
 	const realRegID, realRegID2 = 50, 100
 	realReg, realReg2 := FromRealReg(realRegID, RegTypeInt), FromRealReg(realRegID2, RegTypeInt)
@@ -41,7 +60,7 @@ func TestAllocator_livenessAnalysis(t *testing.T) {
 				0: {
 					defs:     map[VReg]programCounter{2: pcDefOffset + pcStride, 1: pcDefOffset},
 					lastUses: makeVRegTable(map[VReg]programCounter{1: pcStride + pcUseOffset}),
-					kills:    map[VReg]struct{}{1: {}},
+					kills:    makeVRegSet(map[VReg]struct{}{1: {}}),
 				},
 			},
 		},
@@ -81,11 +100,11 @@ func TestAllocator_livenessAnalysis(t *testing.T) {
 						2:    pcStride*2 + pcUseOffset,
 					}),
 					liveOuts: map[VReg]struct{}{3: {}},
-					kills: map[VReg]struct{}{
+					kills: makeVRegSet(map[VReg]struct{}{
 						1000: {},
 						1:    {},
 						2:    {},
-					},
+					}),
 				},
 				1: {
 					liveIns:  map[VReg]struct{}{3: {}},
@@ -93,6 +112,7 @@ func TestAllocator_livenessAnalysis(t *testing.T) {
 					lastUses: makeVRegTable(map[VReg]programCounter{
 						3: pcStride + pcUseOffset,
 					}),
+					kills: makeVRegSetEmpty(3, 0xffffffff, 0xffffffff),
 					defs: map[VReg]programCounter{
 						4: pcStride + pcDefOffset,
 						5: pcStride + pcDefOffset,
@@ -107,7 +127,7 @@ func TestAllocator_livenessAnalysis(t *testing.T) {
 				2: {
 					liveIns:  map[VReg]struct{}{3: {}, 4: {}, 5: {}},
 					lastUses: makeVRegTable(map[VReg]programCounter{3: pcUseOffset, 4: pcUseOffset, 5: pcUseOffset}),
-					kills:    map[VReg]struct{}{3: {}, 4: {}, 5: {}},
+					kills:    makeVRegSet(map[VReg]struct{}{3: {}, 4: {}, 5: {}}),
 				},
 			},
 		},
@@ -153,12 +173,13 @@ func TestAllocator_livenessAnalysis(t *testing.T) {
 					},
 					liveOuts: map[VReg]struct{}{1000: {}, 1: {}, 2: {}},
 					lastUses: makeVRegTable(nil),
+					kills:    makeVRegSet(nil),
 				},
 				1: {
 					liveIns:  map[VReg]struct{}{1000: {}, 1: {}},
 					liveOuts: map[VReg]struct{}{1000: {}},
 					lastUses: makeVRegTable(map[VReg]programCounter{1: pcUseOffset}),
-					kills:    map[VReg]struct{}{1: {}},
+					kills:    makeVRegSet(map[VReg]struct{}{1: {}}),
 					realRegDefs: [vRegIDReservedForRealNum][]programCounter{
 						realRegID:  {pcDefOffset, pcStride*4 + pcDefOffset},
 						realRegID2: {pcStride*2 + pcDefOffset},
@@ -172,14 +193,14 @@ func TestAllocator_livenessAnalysis(t *testing.T) {
 					liveIns:     map[VReg]struct{}{1000: {}, 2: {}},
 					liveOuts:    map[VReg]struct{}{1000: {}},
 					lastUses:    makeVRegTable(map[VReg]programCounter{2: pcUseOffset}),
-					kills:       map[VReg]struct{}{2: {}},
+					kills:       makeVRegSet(map[VReg]struct{}{2: {}}),
 					realRegUses: [vRegIDReservedForRealNum][]programCounter{realRegID2: {pcUseOffset}},
 					realRegDefs: [vRegIDReservedForRealNum][]programCounter{realRegID2: {0}},
 				},
 				3: {
 					liveIns:  map[VReg]struct{}{1000: {}},
 					lastUses: makeVRegTable(map[VReg]programCounter{1000: pcUseOffset}),
-					kills:    map[VReg]struct{}{1000: {}},
+					kills:    makeVRegSet(map[VReg]struct{}{1000: {}}),
 				},
 			},
 		},
@@ -219,30 +240,32 @@ func TestAllocator_livenessAnalysis(t *testing.T) {
 					defs:     map[VReg]programCounter{1000: pcDefOffset, 2000: pcDefOffset, 3000: pcDefOffset},
 					liveOuts: map[VReg]struct{}{1000: {}, 2000: {}, 3000: {}},
 					lastUses: makeVRegTable(nil),
+					kills:    makeVRegSet(nil),
 				},
 				1: {
 					liveIns:  map[VReg]struct{}{2000: {}, 3000: {}},
 					liveOuts: map[VReg]struct{}{phiVReg: {}, 3000: {}},
 					defs:     map[VReg]programCounter{phiVReg: pcDefOffset},
 					lastUses: makeVRegTable(map[VReg]programCounter{2000: pcUseOffset}),
-					kills:    map[VReg]struct{}{2000: {}},
+					kills:    makeVRegSet(map[VReg]struct{}{2000: {}}),
 				},
 				2: {
 					liveIns:  map[VReg]struct{}{phiVReg: {}, 3000: {}},
 					liveOuts: map[VReg]struct{}{phiVReg: {}, 3000: {}},
 					lastUses: makeVRegTable(nil),
+					kills:    makeVRegSet(nil),
 				},
 				3: {
 					liveIns:  map[VReg]struct{}{1000: {}, 3000: {}},
 					liveOuts: map[VReg]struct{}{phiVReg: {}, 3000: {}},
 					defs:     map[VReg]programCounter{phiVReg: pcDefOffset},
 					lastUses: makeVRegTable(map[VReg]programCounter{1000: pcUseOffset}),
-					kills:    map[VReg]struct{}{1000: {}},
+					kills:    makeVRegSet(map[VReg]struct{}{1000: {}}),
 				},
 				4: {
 					liveIns:  map[VReg]struct{}{phiVReg: {}, 3000: {}},
 					lastUses: makeVRegTable(map[VReg]programCounter{phiVReg: pcUseOffset, 3000: pcUseOffset}),
-					kills:    map[VReg]struct{}{phiVReg: {}, 3000: {}},
+					kills:    makeVRegSet(map[VReg]struct{}{phiVReg: {}, 3000: {}}),
 				},
 			},
 		},
@@ -295,37 +318,37 @@ func TestAllocator_livenessAnalysis(t *testing.T) {
 					lastUses: makeVRegTable(map[VReg]programCounter{
 						1: pcStride + pcUseOffset,
 					}),
-					kills: map[VReg]struct{}{
+					kills: makeVRegSet(map[VReg]struct{}{
 						1: {},
-					},
+					}),
 				},
 				1: {
 					liveIns:  map[VReg]struct{}{phiVReg: {}},
 					liveOuts: map[VReg]struct{}{phiVReg: {}, 9999: {}},
 					defs:     map[VReg]programCounter{9999: pcDefOffset},
 					lastUses: makeVRegTable(map[VReg]programCounter{}),
-					kills:    map[VReg]struct{}{},
+					kills:    makeVRegSet(map[VReg]struct{}{}),
 				},
 				2: {
 					liveIns:  map[VReg]struct{}{phiVReg: {}, 9999: {}},
 					liveOuts: map[VReg]struct{}{100: {}},
 					defs:     map[VReg]programCounter{100: pcDefOffset},
 					lastUses: makeVRegTable(map[VReg]programCounter{phiVReg: pcUseOffset, 9999: pcUseOffset}),
-					kills:    map[VReg]struct{}{phiVReg: {}, 9999: {}},
+					kills:    makeVRegSet(map[VReg]struct{}{phiVReg: {}, 9999: {}}),
 				},
 				3: {
 					liveIns:  map[VReg]struct{}{100: {}},
 					liveOuts: map[VReg]struct{}{54321: {}},
 					defs:     map[VReg]programCounter{54321: pcDefOffset},
 					lastUses: makeVRegTable(map[VReg]programCounter{100: pcStride + pcUseOffset}),
-					kills:    map[VReg]struct{}{100: {}},
+					kills:    makeVRegSet(map[VReg]struct{}{100: {}}),
 				},
 				4: {
 					liveIns:  map[VReg]struct{}{54321: {}},
 					liveOuts: map[VReg]struct{}{phiVReg: {}},
 					defs:     map[VReg]programCounter{phiVReg: pcDefOffset},
 					lastUses: makeVRegTable(map[VReg]programCounter{54321: pcUseOffset}),
-					kills:    map[VReg]struct{}{54321: {}},
+					kills:    makeVRegSet(map[VReg]struct{}{54321: {}}),
 				},
 			},
 		},
@@ -356,24 +379,29 @@ func TestAllocator_livenessAnalysis(t *testing.T) {
 					defs:     map[VReg]programCounter{99999: pcDefOffset},
 					liveOuts: map[VReg]struct{}{99999: {}},
 					lastUses: makeVRegTable(nil),
+					kills:    makeVRegSet(nil),
 				},
 				1: {
 					liveIns:  map[VReg]struct{}{99999: {}},
 					liveOuts: map[VReg]struct{}{99999: {}},
 					lastUses: makeVRegTable(map[VReg]programCounter{99999: pcUseOffset}),
+					kills:    makeVRegSetEmpty(99999, 0xffffffff, 0xffffffff),
 				},
 				2: {
 					liveIns:  map[VReg]struct{}{99999: {}},
 					liveOuts: map[VReg]struct{}{99999: {}},
 					lastUses: makeVRegTable(nil),
+					kills:    makeVRegSet(nil),
 				},
 				3: {
 					liveIns:  map[VReg]struct{}{99999: {}},
 					liveOuts: map[VReg]struct{}{99999: {}},
 					lastUses: makeVRegTable(nil),
+					kills:    makeVRegSet(nil),
 				},
 				4: {
 					lastUses: makeVRegTable(nil),
+					kills:    makeVRegSet(nil),
 				},
 			},
 		},
@@ -432,45 +460,55 @@ func TestAllocator_livenessAnalysis(t *testing.T) {
 			exp: map[int]*blockInfo{
 				0: {
 					lastUses: makeVRegTable(nil),
+					kills:    makeVRegSet(nil),
 				},
 				1: {
 					lastUses: makeVRegTable(nil),
+					kills:    makeVRegSet(nil),
 				},
 				2: {
 					lastUses: makeVRegTable(nil),
+					kills:    makeVRegSet(nil),
 				},
 				3: {
 					defs:     map[VReg]programCounter{100: pcDefOffset},
 					liveOuts: map[VReg]struct{}{100: {}},
 					lastUses: makeVRegTable(nil),
+					kills:    makeVRegSet(nil),
 				},
 				4: {
 					liveIns:  map[VReg]struct{}{100: {}},
 					liveOuts: map[VReg]struct{}{100: {}},
 					lastUses: makeVRegTable(nil),
+					kills:    makeVRegSet(nil),
 				},
 				5: {
 					liveIns:  map[VReg]struct{}{100: {}},
 					liveOuts: map[VReg]struct{}{100: {}},
 					lastUses: makeVRegTable(map[VReg]programCounter{100: pcUseOffset}),
+					kills:    makeVRegSetEmpty(100, 0xffffffff, 0xffffffff),
 				},
 				6: {
 					liveIns:  map[VReg]struct{}{100: {}},
 					liveOuts: map[VReg]struct{}{100: {}},
 					lastUses: makeVRegTable(nil),
+					kills:    makeVRegSet(nil),
 				},
 				7: {
 					liveIns:  map[VReg]struct{}{100: {}},
 					liveOuts: map[VReg]struct{}{100: {}},
 					lastUses: makeVRegTable(nil),
+					kills:    makeVRegSet(nil),
 				},
 				8: {
 					liveIns:  map[VReg]struct{}{100: {}},
 					liveOuts: map[VReg]struct{}{100: {}},
 					lastUses: makeVRegTable(nil),
+					kills:    makeVRegSet(nil),
 				},
 				9: {
 					lastUses: makeVRegTable(nil),
+					kills:    makeVRegSet(nil),
 				},
 			},
 		},
@@ -481,7 +519,7 @@ func TestAllocator_livenessAnalysis(t *testing.T) {
 			a := NewAllocator(&RegisterInfo{})
 			a.livenessAnalysis(f)
 			for blockID := range a.blockInfos {
-				actual := &a.blockInfos[blockID]
+				actual := a.blockInfos[blockID]
 				exp := tc.exp[blockID]
 				initMapInInfo(exp)
 				saved := actual.intervalMng
@@ -568,9 +606,6 @@ func initMapInInfo(info *blockInfo) {
 	if info.defs == nil {
 		info.defs = make(map[VReg]programCounter)
 	}
-	if info.kills == nil {
-		info.kills = make(map[VReg]struct{})
-	}
 }
 
 func TestNode_assignedRealReg(t *testing.T) {