Repository: tetratelabs/wazero
Pull request #1813 (2023-10-23 08:20:13)

wazevo(regalloc): deletes unnecessary kills info
#1496 


Patch:
diff --git a/internal/engine/wazevo/backend/regalloc/reg.go b/internal/engine/wazevo/backend/regalloc/reg.go
index 9e9d00a6..6852ad80 100644
--- a/internal/engine/wazevo/backend/regalloc/reg.go
+++ b/internal/engine/wazevo/backend/regalloc/reg.go
@@ -87,6 +87,7 @@ func (t *VRegTable) Contains(v VReg) bool {
 	return t[v.RegType()].Contains(v.ID())
 }
 
+// Lookup returns the program counter associated with the given virtual register.
 func (t *VRegTable) Lookup(v VReg) programCounter {
 	return t[v.RegType()].Lookup(v.ID())
 }
@@ -132,6 +133,8 @@ func (t *VRegTypeTable) Contains(id VRegID) bool {
 	return t.set.has(uint(id - t.min))
 }
 
+// Lookup returns the program counter associated with the given virtual register.
+// If the virtual register is not in the table, -1 is returned.
 func (t *VRegTypeTable) Lookup(id VRegID) programCounter {
 	if id := int(id - t.min); t.set.has(uint(id)) {
 		return t.pcs[id]
diff --git a/internal/engine/wazevo/backend/regalloc/regalloc.go b/internal/engine/wazevo/backend/regalloc/regalloc.go
index a9649dd6..64a805ce 100644
--- a/internal/engine/wazevo/backend/regalloc/regalloc.go
+++ b/internal/engine/wazevo/backend/regalloc/regalloc.go
@@ -81,7 +81,6 @@ type (
 		liveIns  map[VReg]struct{}
 		defs     map[VReg]programCounter
 		lastUses VRegTable
-		kills    VRegSet
 		// Pre-colored real registers can have multiple live ranges in one block.
 		realRegUses [vRegIDReservedForRealNum][]programCounter
 		realRegDefs [vRegIDReservedForRealNum][]programCounter
@@ -186,7 +185,6 @@ 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() {
@@ -242,22 +240,6 @@ func (a *Allocator) livenessAnalysis(f Function) {
 		}
 		a.beginUpAndMarkStack(f, v, false, nil)
 	}
-
-	// Now that we finished gathering liveIns, liveOuts, defs, and lastUses, the only thing left is to construct kills.
-	for blk := f.PostOrderBlockIteratorBegin(); blk != nil; blk = f.PostOrderBlockIteratorNext() { // Order doesn't matter.
-		info := a.blockInfoAt(blk.ID())
-		outs := info.liveOuts
-		info.lastUses.Range(func(use VReg, pc programCounter) {
-			// Usage without live-outs is a kill.
-			if _, ok := outs[use]; !ok {
-				info.kills.Insert(use)
-			}
-		})
-
-		if wazevoapi.RegAllocLoggingEnabled {
-			fmt.Printf("\nfinalized info for block[%d]:\n%s\n", blk.ID(), info.Format(a.regInfo))
-		}
-	}
 }
 
 func (a *Allocator) beginUpAndMarkStack(f Function, v VReg, isPhi bool, phiDefinedAt Block) {
@@ -347,13 +329,7 @@ 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 info.kills.Contains(v) {
-				panic("BUG: v is live-out but also killed")
-			}
 		} else {
-			if !info.kills.Contains(v) {
-				panic("BUG: v is live-in but not live-out or use")
-			}
 			// v is killed at killPos.
 			begin, end = 0, info.lastUses.Lookup(v)
 		}
@@ -385,17 +361,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 info.kills.Contains(v) {
-				panic("BUG: v is killed here but also killed")
-			}
 		} else {
-			if !info.kills.Contains(v) {
+			if end = info.lastUses.Lookup(v); end == -1 {
 				// This case the defined value is not used at all.
 				end = defPos
-			} else {
-				// v is killed at pos.
-				end = info.lastUses.Lookup(v)
-			}
+			} // Otherwise v is killed at defPos.
 		}
 		n := a.getOrAllocateNode(v)
 		intervalNode := info.intervalMng.insert(n, defPos, end)
@@ -404,18 +374,6 @@ func (a *Allocator) buildLiveRangesForNonReals(info *blockInfo) {
 
 	// Reuse for the next block.
 	a.vs = vs[:0]
-
-	if wazevoapi.RegAllocValidationEnabled {
-		info.kills.Range(func(u VReg) {
-			if !u.IsRealReg() {
-				_, defined := defs[u]
-				_, liveIn := ins[u]
-				if !defined && !liveIn {
-					panic(fmt.Sprintf("BUG: %v is killed but not defined or live-in", u))
-				}
-			}
-		})
-	}
 }
 
 // buildLiveRangesForReals builds live ranges for pre-colored real registers.
@@ -586,10 +544,6 @@ func (i *blockInfo) Format(ri *RegisterInfo) string {
 	i.lastUses.Range(func(v VReg, pos programCounter) {
 		buf.WriteString(fmt.Sprintf("%v@%v ", v, pos))
 	})
-	buf.WriteString("\n\tkills: ")
-	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/regalloc_test.go b/internal/engine/wazevo/backend/regalloc/regalloc_test.go
index e2605a44..0ed6890b 100644
--- a/internal/engine/wazevo/backend/regalloc/regalloc_test.go
+++ b/internal/engine/wazevo/backend/regalloc/regalloc_test.go
@@ -13,14 +13,6 @@ func makeVRegIDMinSet[T any](vregs map[VReg]T) (min VRegIDMinSet) {
 	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 {
@@ -29,14 +21,6 @@ func makeVRegTable(vregs map[VReg]programCounter) (table VRegTable) {
 	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)
@@ -60,7 +44,6 @@ 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:    makeVRegSet(map[VReg]struct{}{1: {}}),
 				},
 			},
 		},
@@ -100,11 +83,6 @@ func TestAllocator_livenessAnalysis(t *testing.T) {
 						2:    pcStride*2 + pcUseOffset,
 					}),
 					liveOuts: map[VReg]struct{}{3: {}},
-					kills: makeVRegSet(map[VReg]struct{}{
-						1000: {},
-						1:    {},
-						2:    {},
-					}),
 				},
 				1: {
 					liveIns:  map[VReg]struct{}{3: {}},
@@ -112,7 +90,6 @@ 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,
@@ -127,7 +104,6 @@ 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:    makeVRegSet(map[VReg]struct{}{3: {}, 4: {}, 5: {}}),
 				},
 			},
 		},
@@ -173,13 +149,11 @@ 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:    makeVRegSet(map[VReg]struct{}{1: {}}),
 					realRegDefs: [vRegIDReservedForRealNum][]programCounter{
 						realRegID:  {pcDefOffset, pcStride*4 + pcDefOffset},
 						realRegID2: {pcStride*2 + pcDefOffset},
@@ -193,14 +167,12 @@ 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:       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:    makeVRegSet(map[VReg]struct{}{1000: {}}),
 				},
 			},
 		},
@@ -240,32 +212,27 @@ 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:    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:    makeVRegSet(map[VReg]struct{}{1000: {}}),
 				},
 				4: {
 					liveIns:  map[VReg]struct{}{phiVReg: {}, 3000: {}},
 					lastUses: makeVRegTable(map[VReg]programCounter{phiVReg: pcUseOffset, 3000: pcUseOffset}),
-					kills:    makeVRegSet(map[VReg]struct{}{phiVReg: {}, 3000: {}}),
 				},
 			},
 		},
@@ -318,37 +285,30 @@ func TestAllocator_livenessAnalysis(t *testing.T) {
 					lastUses: makeVRegTable(map[VReg]programCounter{
 						1: pcStride + pcUseOffset,
 					}),
-					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:    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:    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:    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:    makeVRegSet(map[VReg]struct{}{54321: {}}),
 				},
 			},
 		},
@@ -379,29 +339,24 @@ 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),
 				},
 			},
 		},
@@ -460,55 +415,45 @@ 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),
 				},
 			},
 		},