| 1 |
package regalloc |
| 2 |
|
| 3 |
import ( |
| 4 |
"fmt" |
| 5 |
"strings" |
| 6 |
) |
| 7 |
|
| 8 |
// Following mock types are used for testing. |
| 9 |
type ( |
| 10 |
// mockFunction implements Function. |
| 11 |
mockFunction struct { |
| 12 |
iter int |
| 13 |
blocks []*mockBlock |
| 14 |
befores, afters []storeOrReloadInfo |
| 15 |
lnfRoots []*mockBlock |
| 16 |
} |
| 17 |
|
| 18 |
storeOrReloadInfo struct { |
| 19 |
reload bool |
| 20 |
v VReg |
| 21 |
instr *mockInstr |
| 22 |
} |
| 23 |
|
| 24 |
// mockBlock implements Block. |
| 25 |
mockBlock struct { |
| 26 |
id int32 |
| 27 |
instructions []*mockInstr |
| 28 |
preds, succs []*mockBlock |
| 29 |
_preds, _succs []*mockBlock |
| 30 |
iter int |
| 31 |
_entry bool |
| 32 |
_loop bool |
| 33 |
lnfChildren []*mockBlock |
| 34 |
blockParams []VReg |
| 35 |
} |
| 36 |
|
| 37 |
// mockInstr implements Instr. |
| 38 |
mockInstr struct { |
| 39 |
next, prev *mockInstr |
| 40 |
defs, uses []VReg |
| 41 |
isCopy, isCall, isIndirect bool |
| 42 |
} |
| 43 |
) |
| 44 |
|
| 45 |
func (m *mockFunction) LowestCommonAncestor(blk1, blk2 *mockBlock) *mockBlock { panic("TODO") } |
| 46 |
|
| 47 |
func (m *mockFunction) Idom(blk *mockBlock) *mockBlock { panic("TODO") } |
| 48 |
|
| 49 |
func (m *mockFunction) SwapBefore(x1, x2, tmp VReg, instr *mockInstr) { panic("TODO") } |
| 50 |
|
| 51 |
func (m *mockFunction) InsertMoveBefore(dst, src VReg, instr *mockInstr) { panic("TODO") } |
| 52 |
|
| 53 |
func newMockFunction(blocks ...*mockBlock) *mockFunction { |
| 54 |
return &mockFunction{blocks: blocks} |
| 55 |
} |
| 56 |
|
| 57 |
func (m *mockFunction) loopNestingForestRoots(blocks ...*mockBlock) { |
| 58 |
m.lnfRoots = blocks |
| 59 |
} |
| 60 |
|
| 61 |
func newMockBlock(id int32, instructions ...*mockInstr) *mockBlock { |
| 62 |
if len(instructions) > 0 { |
| 63 |
instructions[0].prev = nil |
| 64 |
for i := 1; i < len(instructions); i++ { |
| 65 |
instructions[i].prev = instructions[i-1] |
| 66 |
instructions[i-1].next = instructions[i] |
| 67 |
} |
| 68 |
instructions[len(instructions)-1].next = nil |
| 69 |
} |
| 70 |
return &mockBlock{id: id, instructions: instructions} |
| 71 |
} |
| 72 |
|
| 73 |
func newMockInstr() *mockInstr { |
| 74 |
return &mockInstr{} |
| 75 |
} |
| 76 |
|
| 77 |
// String implements fmt.Stringer for debugging. |
| 78 |
func (m *mockFunction) String() string { |
| 79 |
var block []string |
| 80 |
for _, b := range m.blocks { |
| 81 |
block = append(block, "\t"+b.String()) |
| 82 |
} |
| 83 |
return fmt.Sprintf("mockFunction:\n%s", strings.Join(block, ",\n")) |
| 84 |
} |
| 85 |
|
| 86 |
// String implements fmt.Stringer for debugging. |
| 87 |
func (m *mockInstr) String() string { |
| 88 |
return fmt.Sprintf("mockInstr{defs=%v, uses=%v}", m.defs, m.uses) |
| 89 |
} |
| 90 |
|
| 91 |
// String implements fmt.Stringer for debugging. |
| 92 |
func (m *mockBlock) String() string { |
| 93 |
var preds []int32 |
| 94 |
for _, p := range m.preds { |
| 95 |
preds = append(preds, p.id) |
| 96 |
} |
| 97 |
return fmt.Sprintf("mockBlock{\n\tid=%v,\n\tinstructions=%v,\n\tpreds=%v,\n}", m.id, preds, m.instructions) |
| 98 |
} |
| 99 |
|
| 100 |
func (m *mockBlock) addPred(b *mockBlock) { |
| 101 |
m.preds = append(m.preds, b) |
| 102 |
m._preds = append(m._preds, b) |
| 103 |
b._succs = append(b._succs, m) |
| 104 |
b.succs = append(b.succs, m) |
| 105 |
} |
| 106 |
|
| 107 |
func (m *mockInstr) use(uses ...VReg) *mockInstr { |
| 108 |
m.uses = uses |
| 109 |
return m |
| 110 |
} |
| 111 |
|
| 112 |
func (m *mockInstr) def(defs ...VReg) *mockInstr { |
| 113 |
m.defs = defs |
| 114 |
return m |
| 115 |
} |
| 116 |
|
| 117 |
func (m *mockBlock) loop(children ...*mockBlock) *mockBlock { |
| 118 |
m._loop = true |
| 119 |
m.lnfChildren = children |
| 120 |
return m |
| 121 |
} |
| 122 |
|
| 123 |
func (m *mockBlock) entry() *mockBlock { |
| 124 |
m._entry = true |
| 125 |
return m |
| 126 |
} |
| 127 |
|
| 128 |
func (m *mockInstr) asCopy() *mockInstr { |
| 129 |
m.isCopy = true |
| 130 |
return m |
| 131 |
} |
| 132 |
|
| 133 |
func (m *mockInstr) asCall() *mockInstr { //nolint:unused |
| 134 |
m.isCall = true |
| 135 |
return m |
| 136 |
} |
| 137 |
|
| 138 |
func (m *mockInstr) asIndirectCall() *mockInstr { //nolint:unused |
| 139 |
m.isIndirect = true |
| 140 |
return m |
| 141 |
} |
| 142 |
|
| 143 |
// StoreRegisterAfter implements Function.StoreRegisterAfter. |
| 144 |
func (m *mockFunction) StoreRegisterAfter(v VReg, instr *mockInstr) { |
| 145 |
m.afters = append(m.afters, storeOrReloadInfo{false, v, instr}) |
| 146 |
} |
| 147 |
|
| 148 |
// ReloadRegisterBefore implements Function.ReloadRegisterBefore. |
| 149 |
func (m *mockFunction) ReloadRegisterBefore(v VReg, instr *mockInstr) { |
| 150 |
m.befores = append(m.befores, storeOrReloadInfo{true, v, instr}) |
| 151 |
} |
| 152 |
|
| 153 |
// StoreRegisterBefore implements Function.StoreRegisterBefore. |
| 154 |
func (m *mockFunction) StoreRegisterBefore(v VReg, instr *mockInstr) { |
| 155 |
m.befores = append(m.befores, storeOrReloadInfo{false, v, instr}) |
| 156 |
} |
| 157 |
|
| 158 |
// ReloadRegisterAfter implements Function.ReloadRegisterAfter. |
| 159 |
func (m *mockFunction) ReloadRegisterAfter(v VReg, instr *mockInstr) { |
| 160 |
m.afters = append(m.afters, storeOrReloadInfo{true, v, instr}) |
| 161 |
} |
| 162 |
|
| 163 |
// ClobberedRegisters implements Function.ClobberedRegisters. |
| 164 |
func (m *mockFunction) ClobberedRegisters(regs []VReg) { |
| 165 |
// TODO implement me |
| 166 |
panic("implement me") |
| 167 |
} |
| 168 |
|
| 169 |
// Done implements Function.Done. |
| 170 |
func (m *mockFunction) Done() {} |
| 171 |
|
| 172 |
// PostOrderBlockIteratorBegin implements Block. |
| 173 |
func (m *mockFunction) PostOrderBlockIteratorBegin() *mockBlock { |
| 174 |
m.iter = 1 |
| 175 |
l := len(m.blocks) |
| 176 |
return m.blocks[l-1] |
| 177 |
} |
| 178 |
|
| 179 |
// PostOrderBlockIteratorNext implements Block. |
| 180 |
func (m *mockFunction) PostOrderBlockIteratorNext() *mockBlock { |
| 181 |
if m.iter == len(m.blocks) { |
| 182 |
return nil |
| 183 |
} |
| 184 |
l := len(m.blocks) |
| 185 |
ret := m.blocks[l-m.iter-1] |
| 186 |
m.iter++ |
| 187 |
return ret |
| 188 |
} |
| 189 |
|
| 190 |
// ReversePostOrderBlockIteratorBegin implements Block. |
| 191 |
func (m *mockFunction) ReversePostOrderBlockIteratorBegin() *mockBlock { |
| 192 |
m.iter = 1 |
| 193 |
return m.blocks[0] |
| 194 |
} |
| 195 |
|
| 196 |
// ReversePostOrderBlockIteratorNext implements Block. |
| 197 |
func (m *mockFunction) ReversePostOrderBlockIteratorNext() *mockBlock { |
| 198 |
if m.iter == len(m.blocks) { |
| 199 |
return nil |
| 200 |
} |
| 201 |
ret := m.blocks[m.iter] |
| 202 |
m.iter++ |
| 203 |
return ret |
| 204 |
} |
| 205 |
|
| 206 |
// ID implements Block. |
| 207 |
func (m *mockBlock) ID() int32 { |
| 208 |
return m.id |
| 209 |
} |
| 210 |
|
| 211 |
// InstrIteratorBegin implements Block. |
| 212 |
func (m *mockBlock) InstrIteratorBegin() *mockInstr { |
| 213 |
if len(m.instructions) == 0 { |
| 214 |
return nil |
| 215 |
} |
| 216 |
m.iter = 1 |
| 217 |
return m.instructions[0] |
| 218 |
} |
| 219 |
|
| 220 |
// InstrIteratorNext implements Block. |
| 221 |
func (m *mockBlock) InstrIteratorNext() *mockInstr { |
| 222 |
if m.iter == len(m.instructions) { |
| 223 |
return nil |
| 224 |
} |
| 225 |
ret := m.instructions[m.iter] |
| 226 |
m.iter++ |
| 227 |
return ret |
| 228 |
} |
| 229 |
|
| 230 |
// InstrRevIteratorBegin implements Block. |
| 231 |
func (m *mockBlock) InstrRevIteratorBegin() *mockInstr { |
| 232 |
if len(m.instructions) == 0 { |
| 233 |
return nil |
| 234 |
} |
| 235 |
m.iter = len(m.instructions) |
| 236 |
return m.InstrRevIteratorNext() |
| 237 |
} |
| 238 |
|
| 239 |
// InstrRevIteratorNext implements Block. |
| 240 |
func (m *mockBlock) InstrRevIteratorNext() *mockInstr { |
| 241 |
m.iter-- |
| 242 |
if m.iter < 0 { |
| 243 |
return nil |
| 244 |
} |
| 245 |
return m.instructions[m.iter] |
| 246 |
} |
| 247 |
|
| 248 |
// Preds implements Block. |
| 249 |
func (m *mockBlock) Preds() int { |
| 250 |
return len(m._preds) |
| 251 |
} |
| 252 |
|
| 253 |
// BlockParams implements Block. |
| 254 |
func (m *mockFunction) BlockParams(blk *mockBlock, ret *[]VReg) []VReg { |
| 255 |
*ret = append((*ret)[:0], blk.blockParams...) |
| 256 |
return *ret |
| 257 |
} |
| 258 |
|
| 259 |
func (m *mockBlock) blockParam(v VReg) { |
| 260 |
m.blockParams = append(m.blockParams, v) |
| 261 |
} |
| 262 |
|
| 263 |
// Defs implements Instr. |
| 264 |
func (m *mockInstr) Defs(ret *[]VReg) []VReg { |
| 265 |
*ret = append((*ret)[:0], m.defs...) |
| 266 |
return *ret |
| 267 |
} |
| 268 |
|
| 269 |
// Uses implements Instr. |
| 270 |
func (m *mockInstr) Uses(ret *[]VReg) []VReg { |
| 271 |
*ret = append((*ret)[:0], m.uses...) |
| 272 |
return *ret |
| 273 |
} |
| 274 |
|
| 275 |
// IsCopy implements Instr. |
| 276 |
func (m *mockInstr) IsCopy() bool { return m.isCopy } |
| 277 |
|
| 278 |
// IsCall implements Instr. |
| 279 |
func (m *mockInstr) IsCall() bool { return m.isCall } |
| 280 |
|
| 281 |
// IsIndirectCall implements Instr. |
| 282 |
func (m *mockInstr) IsIndirectCall() bool { return m.isIndirect } |
| 283 |
|
| 284 |
// IsReturn implements Instr. |
| 285 |
func (m *mockInstr) IsReturn() bool { return false } |
| 286 |
|
| 287 |
// Next implements Instr. |
| 288 |
func (m *mockInstr) Next() *mockInstr { return m.next } |
| 289 |
|
| 290 |
// Prev implements Instr. |
| 291 |
func (m *mockInstr) Prev() *mockInstr { return m.prev } |
| 292 |
|
| 293 |
// Entry implements Entry. |
| 294 |
func (m *mockBlock) Entry() bool { return m._entry } |
| 295 |
|
| 296 |
// AssignUses implements Instr. |
| 297 |
func (m *mockInstr) AssignUse(index int, reg VReg) { |
| 298 |
if index >= len(m.uses) { |
| 299 |
m.uses = append(m.uses, make([]VReg, 5)...) |
| 300 |
} |
| 301 |
m.uses[index] = reg |
| 302 |
} |
| 303 |
|
| 304 |
// AssignDef implements Instr. |
| 305 |
func (m *mockInstr) AssignDef(reg VReg) { |
| 306 |
m.defs = []VReg{reg} |
| 307 |
} |
| 308 |
|
| 309 |
var _ Function[*mockInstr, *mockBlock] = (*mockFunction)(nil) |
| 310 |
|
| 311 |
func (m *mockFunction) LoopNestingForestRoots() int { |
| 312 |
return len(m.lnfRoots) |
| 313 |
} |
| 314 |
|
| 315 |
// LoopNestingForestRoot implements Function. |
| 316 |
func (m *mockFunction) LoopNestingForestRoot(i int) *mockBlock { |
| 317 |
return m.lnfRoots[i] |
| 318 |
} |
| 319 |
|
| 320 |
// LoopNestingForestChild implements Function. |
| 321 |
func (m *mockFunction) LoopNestingForestChild(b *mockBlock, i int) *mockBlock { |
| 322 |
return b.lnfChildren[i] |
| 323 |
} |
| 324 |
|
| 325 |
// Succ implements Function. |
| 326 |
func (m *mockFunction) Succ(b *mockBlock, i int) *mockBlock { |
| 327 |
return b.succs[i] |
| 328 |
} |
| 329 |
|
| 330 |
// Pred implements Function. |
| 331 |
func (m *mockFunction) Pred(b *mockBlock, i int) *mockBlock { return b._preds[i] } |
| 332 |
|
| 333 |
func (m *mockBlock) LoopHeader() bool { |
| 334 |
return m._loop |
| 335 |
} |
| 336 |
|
| 337 |
func (m *mockBlock) Succs() int { |
| 338 |
return len(m.succs) |
| 339 |
} |
| 340 |
|
| 341 |
func (m *mockBlock) LoopNestingForestChildren() int { |
| 342 |
return len(m.lnfChildren) |
| 343 |
} |
| 344 |
|
| 345 |
func (m *mockBlock) LastInstrForInsertion() *mockInstr { |
| 346 |
if len(m.instructions) == 0 { |
| 347 |
return nil |
| 348 |
} |
| 349 |
return m.instructions[len(m.instructions)-1] |
| 350 |
} |
| 351 |
|
| 352 |
func (m *mockBlock) FirstInstr() *mockInstr { |
| 353 |
return m.instructions[0] |
| 354 |
} |