Debian Codegraph @

internal/engine/wazevo/backend/regalloc/regalloc_test.go

raw
1 package regalloc
2
3 import (
4 "fmt"
5 "sort"
6 "testing"
7
8 "github.com/tetratelabs/wazero/internal/engine/wazevo/wazevoapi"
9 "github.com/tetratelabs/wazero/internal/testing/require"
10 )
11
12 type (
13 _allocator = Allocator[*mockInstr, *mockBlock, *mockFunction]
14 _state = state[*mockInstr, *mockBlock, *mockFunction]
15 _vrState = vrState[*mockInstr, *mockBlock, *mockFunction]
16 )
17
18 var (
19 _newAllocator = NewAllocator[*mockInstr, *mockBlock, *mockFunction]
20 _resetVrState = resetVrState[*mockInstr, *mockBlock, *mockFunction]
21 )
22
23 func TestAllocator_livenessAnalysis(t *testing.T) {
24 const realRegID, realRegID2 = 50, 100
25 realReg, realReg2 := FromRealReg(realRegID, RegTypeInt), FromRealReg(realRegID2, RegTypeInt)
26 phiVReg := VReg(12345).SetRegType(RegTypeInt)
27
28 type exp struct {
29 liveIns []VRegID
30 }
31
32 for _, tc := range []struct {
33 name string
34 setup func() *mockFunction
35 exps map[int]*exp
36 }{
37 {
38 name: "single block",
39 setup: func() *mockFunction {
40 return newMockFunction(
41 newMockBlock(0,
42 newMockInstr().def(1),
43 newMockInstr().use(1).def(2),
44 ).entry(),
45 )
46 },
47 exps: map[int]*exp{
48 0: {},
49 },
50 },
51 {
52 name: "single block with real reg",
53 setup: func() *mockFunction {
54 realVReg := FromRealReg(10, RegTypeInt)
55 param := VReg(1)
56 ret := VReg(2)
57 blk := newMockBlock(0,
58 newMockInstr().def(param).use(realVReg),
59 newMockInstr().def(ret).use(param, param),
60 newMockInstr().def(realVReg).use(ret),
61 ).entry()
62 blk.blockParam(param)
63 return newMockFunction(blk)
64 },
65 exps: map[int]*exp{
66 0: {},
67 },
68 },
69 {
70 name: "straight",
71 // b0 -> b1 -> b2
72 setup: func() *mockFunction {
73 b0 := newMockBlock(0,
74 newMockInstr().def(1000, 1, 2),
75 newMockInstr().use(1000),
76 newMockInstr().use(1, 2).def(3),
77 ).entry()
78 b1 := newMockBlock(1,
79 newMockInstr().def(realReg),
80 newMockInstr().use(3).def(4, 5),
81 newMockInstr().use(realReg),
82 )
83 b2 := newMockBlock(2,
84 newMockInstr().use(3, 4, 5),
85 )
86 b2.addPred(b1)
87 b1.addPred(b0)
88 return newMockFunction(b0, b1, b2)
89 },
90 exps: map[int]*exp{
91 0: {},
92 1: {
93 liveIns: []VRegID{3},
94 },
95 2: {liveIns: []VRegID{3, 4, 5}},
96 },
97 },
98 {
99 name: "diamond",
100 // 0 v1000<-, v1<-, v2<-
101 // / \
102 // 1 2
103 // \ /
104 // 3
105 setup: func() *mockFunction {
106 b0 := newMockBlock(0,
107 newMockInstr().def(1000),
108 newMockInstr().def(1),
109 newMockInstr().def(2),
110 ).entry()
111 b1 := newMockBlock(1,
112 newMockInstr().def(realReg).use(1),
113 newMockInstr().use(realReg),
114 newMockInstr().def(realReg2),
115 newMockInstr().use(realReg2),
116 newMockInstr().def(realReg),
117 newMockInstr().use(realReg),
118 )
119 b2 := newMockBlock(2,
120 newMockInstr().use(2, realReg2),
121 )
122 b3 := newMockBlock(3,
123 newMockInstr().use(1000),
124 )
125 b3.addPred(b1)
126 b3.addPred(b2)
127 b1.addPred(b0)
128 b2.addPred(b0)
129 return newMockFunction(b0, b1, b2, b3)
130 },
131 exps: map[int]*exp{
132 0: {},
133 1: {liveIns: []VRegID{1000, 1}},
134 2: {
135 liveIns: []VRegID{1000, 2},
136 },
137 3: {
138 liveIns: []VRegID{1000},
139 },
140 },
141 },
142
143 {
144 name: "phis",
145 // 0
146 // / \
147 // 1 \
148 // | |
149 // 2 3
150 // \ /
151 // 4 use v5 (phi node) defined at both 1 and 3.
152 setup: func() *mockFunction {
153 b0 := newMockBlock(0,
154 newMockInstr().def(1000, 2000, 3000),
155 ).entry()
156 b1 := newMockBlock(1,
157 newMockInstr().def(phiVReg).use(2000),
158 )
159 b2 := newMockBlock(2)
160 b3 := newMockBlock(3,
161 newMockInstr().def(phiVReg).use(1000),
162 )
163 b4 := newMockBlock(
164 4, newMockInstr().use(phiVReg, 3000),
165 )
166 b4.addPred(b2)
167 b4.addPred(b3)
168 b3.addPred(b0)
169 b2.addPred(b1)
170 b1.addPred(b0)
171 return newMockFunction(b0, b1, b2, b3, b4)
172 },
173 exps: map[int]*exp{
174 0: {},
175 1: {
176 liveIns: []VRegID{2000, 3000},
177 },
178 2: {
179 liveIns: []VRegID{phiVReg.ID(), 3000},
180 },
181 3: {
182 liveIns: []VRegID{1000, 3000},
183 },
184 4: {
185 liveIns: []VRegID{phiVReg.ID(), 3000},
186 },
187 },
188 },
189
190 {
191 name: "loop",
192 // 0 -> 1 -> 2
193 // ^ |
194 // | v
195 // 4 <- 3 -> 5
196 setup: func() *mockFunction {
197 b0 := newMockBlock(0,
198 newMockInstr().def(1),
199 newMockInstr().def(phiVReg).use(1),
200 ).entry()
201 b1 := newMockBlock(1,
202 newMockInstr().def(9999),
203 )
204 b1.blockParam(phiVReg)
205 b2 := newMockBlock(2,
206 newMockInstr().def(100).use(phiVReg, 9999),
207 )
208 b3 := newMockBlock(3,
209 newMockInstr().def(54321),
210 newMockInstr().use(100),
211 )
212 b4 := newMockBlock(4,
213 newMockInstr().def(phiVReg).use(54321).
214 // Make sure this is the PHI defining instruction.
215 asCopy(),
216 )
217 b5 := newMockBlock(
218 5, newMockInstr().use(54321),
219 )
220 b1.addPred(b0)
221 b1.addPred(b4)
222 b2.addPred(b1)
223 b3.addPred(b2)
224 b4.addPred(b3)
225 b5.addPred(b3)
226 b1.loop(b2, b3, b4, b5)
227 f := newMockFunction(b0, b1, b2, b3, b4, b5)
228 f.loopNestingForestRoots(b1)
229 return f
230 },
231 exps: map[int]*exp{
232 0: {
233 liveIns: []VRegID{},
234 },
235 1: {
236 liveIns: []VRegID{phiVReg.ID()},
237 },
238 2: {
239 liveIns: []VRegID{phiVReg.ID(), 9999},
240 },
241 3: {
242 liveIns: []VRegID{100},
243 },
244 4: {
245 liveIns: []VRegID{54321},
246 },
247 5: {liveIns: []VRegID{54321}},
248 },
249 },
250 {
251 name: "multiple pass alive",
252 setup: func() *mockFunction {
253 v := VReg(9999)
254 b0 := newMockBlock(0, newMockInstr().def(v)).entry()
255
256 b1, b2, b3, b4, b5, b6 := newMockBlock(1), newMockBlock(2),
257 newMockBlock(3, newMockInstr().use(v)),
258 newMockBlock(4), newMockBlock(5), newMockBlock(6)
259
260 b1.addPred(b0)
261 b4.addPred(b0)
262 b2.addPred(b1)
263 b5.addPred(b2)
264 b2.addPred(b5)
265 b6.addPred(b2)
266 b3.addPred(b6)
267 b3.addPred(b4)
268 f := newMockFunction(b0, b1, b2, b4, b5, b6, b3)
269 f.loopNestingForestRoots(b2)
270 return f
271 },
272 exps: map[int]*exp{
273 0: {},
274 1: {
275 liveIns: []VRegID{9999},
276 },
277 2: {
278 liveIns: []VRegID{9999},
279 },
280 3: {
281 liveIns: []VRegID{9999},
282 },
283 4: {
284 liveIns: []VRegID{9999},
285 },
286 5: {},
287 6: {
288 liveIns: []VRegID{9999},
289 },
290 },
291 },
292 {
293 // -----+
294 // v |
295 // 0 -> 1 -> 2 -> 3 -> 4
296 // ^ |
297 // +----+
298 name: "Fig. 9.2 in paper",
299 setup: func() *mockFunction {
300 b0 := newMockBlock(0,
301 newMockInstr().def(99999),
302 newMockInstr().def(phiVReg).use(111).asCopy(),
303 ).entry()
304 b1 := newMockBlock(1, newMockInstr().use(99999))
305 b1.blockParam(phiVReg)
306 b2 := newMockBlock(2, newMockInstr().def(88888).use(phiVReg, phiVReg))
307 b3 := newMockBlock(3, newMockInstr().def(phiVReg).use(88888).asCopy())
308 b4 := newMockBlock(4)
309 b1.addPred(b0)
310 b1.addPred(b2)
311 b2.addPred(b1)
312 b2.addPred(b3)
313 b3.addPred(b2)
314 b4.addPred(b3)
315
316 b1.loop(b2)
317 b2.loop(b3)
318 f := newMockFunction(b0, b1, b2, b3, b4)
319 f.loopNestingForestRoots(b1)
320 return f
321 },
322 exps: map[int]*exp{
323 0: {
324 liveIns: []VRegID{111},
325 },
326 1: {
327 liveIns: []VRegID{99999, phiVReg.ID()},
328 },
329 2: {
330 liveIns: []VRegID{99999, phiVReg.ID()},
331 },
332 3: {
333 liveIns: []VRegID{99999, phiVReg.ID(), 88888},
334 },
335 4: {},
336 },
337 },
338 } {
339 tc := tc
340 t.Run(tc.name, func(t *testing.T) {
341 f := tc.setup()
342 a := _newAllocator(&RegisterInfo{
343 RealRegName: func(r RealReg) string {
344 return fmt.Sprintf("r%d", r)
345 },
346 })
347 a.livenessAnalysis(f)
348 for blockID := 0; blockID <= a.blockStates.MaxIDEncountered(); blockID++ {
349 actual := a.blockStates.Get(blockID)
350 if actual == nil {
351 continue
352 }
353 t.Run(fmt.Sprintf("block_id=%d", blockID), func(t *testing.T) {
354 exp := tc.exps[blockID]
355 if len(exp.liveIns) == 0 {
356 require.Nil(t, actual.liveIns, "live ins")
357 } else {
358 var actuals []VRegID
359 for _, s := range actual.liveIns {
360 actuals = append(actuals, s.v.ID())
361 }
362 sort.Slice(actuals, func(i, j int) bool {
363 return actuals[i] < actuals[j]
364 })
365 sort.Slice(exp.liveIns, func(i, j int) bool {
366 return exp.liveIns[i] < exp.liveIns[j]
367 })
368 require.Equal(t, exp.liveIns, actuals, "live ins")
369 }
370 })
371 }
372 })
373 }
374 }
375
376 func TestAllocator_livenessAnalysis_copy(t *testing.T) {
377 f := newMockFunction(
378 newMockBlock(0,
379 newMockInstr().def(1),
380 newMockInstr().use(1).def(2).asCopy(),
381 ).entry(),
382 )
383 a := _newAllocator(&RegisterInfo{})
384 a.livenessAnalysis(f)
385 }
386
387 func Test_findOrSpillAllocatable_prefersSpill(t *testing.T) {
388 t.Run("ok", func(t *testing.T) {
389 a := &_allocator{}
390 s := &_state{regsInUse: newRegInUseSet[*mockInstr, *mockBlock, *mockFunction]()}
391 s.regsInUse.add(RealReg(1), &_vrState{v: VReg(2222222)})
392 got := a.findOrSpillAllocatable(s, []RealReg{3}, 0, 3)
393 require.Equal(t, RealReg(3), got)
394 })
395 t.Run("preferred but in use", func(t *testing.T) {
396 a := &_allocator{}
397 s := &_state{vrStates: wazevoapi.NewIDedPool[_vrState](_resetVrState)}
398 s.regsInUse.add(RealReg(3), &_vrState{v: VReg(1).SetRealReg(3)})
399 got := a.findOrSpillAllocatable(s, []RealReg{3, 4}, 0, 3)
400 require.Equal(t, RealReg(4), got)
401 })
402 t.Run("preferred but forbidden", func(t *testing.T) {
403 a := &_allocator{}
404 s := &_state{vrStates: wazevoapi.NewIDedPool[_vrState](_resetVrState)}
405 got := a.findOrSpillAllocatable(s, []RealReg{3, 4}, RegSet(0).add(3), 3)
406 require.Equal(t, RealReg(4), got)
407 })
408 }