search

mosa / MOSA-Project

Managed Operating System Alliance Project
https://www.mosa-project.org/
Other
406 stars 82 forks source link

BUG: Register allocator - overlapping live ranges #1141

Closed tgiphil closed 8 months ago

tgiphil commented 9 months ago

The live ranges generation used by the register allocator for physical registers overlap by a half "slot" causing sub-optimal code generation.

Example:

The allocator should allocate EAX instead of ECX at the end:

Mosa.UnitTests.Optimization.Division::DivisionBy3(System.UInt32):System.UInt32 [v3] @ 0 after stage [00] CILDecoderStage:

Block #0 - Label L_10000 [Header]
  Prev: 
10000: IR.Prologue
10000: IR.Move32               v1 <= 0
10000: IR.Jmp                  L_00000
  Next: L_00000

Block #1 - Label L_00000
  Prev: L_10000
00000: IR.Nop
00001: IR.LoadParam32          v2 <= 8 (p0)
00002: IR.Move32               v3 <= 3
00003: IR.DivUnsigned32        v4 <= v2, v3
00004: IR.Move32               v1 <= v4
00005: IR.Jmp                  L_00007
  Next: L_00007

Block #2 - Label L_00007
  Prev: L_00000
00007: IR.Move32               v5 <= v1
00008: IR.SetReturn32          v5
00008: IR.Jmp                  L_FFFFF
  Next: L_FFFFF

Block #3 - Label L_FFFFF
  Prev: L_00007
FFFFF: IR.Epilogue
  Next: 
Mosa.UnitTests.Optimization.Division::DivisionBy3(System.UInt32):System.UInt32 [v3] @ 0 after stage [38] GreedyRegisterAllocatorStage:

Block #0 - Label L_10000 [Header]
  Prev: 
10000: IR.Prologue
10000: X86.Jmp                 L_00000
  Next: L_00000

Block #1 - Label L_00000
  Prev: L_10000
00001: X86.MovLoad32           EAX <= EBP, 8 (p0)
00003: X86.Mov32               EAX <= EAX
00003: X86.Mov32               ECX <= 2863311531
00003: X86.Mul32               EDX, EAX <= EAX, ECX
00003: X86.Mov32               EDX <= EDX
00003: IR.Nop
00003: X86.Mov32               ECX <= EDX
00003: X86.Shr32               ECX <= ECX, 1
00008: X86.Mov32               EAX <= ECX
00008: X86.Jmp                 L_FFFFF
  Next: L_FFFFF

Block #2 - Label L_FFFFF
  Prev: L_00000
FFFFF: IR.Epilogue
  Next:
tgiphil commented 8 months ago

New Output:

Mosa.UnitTests.Optimization.Division::DivisionBy3(System.UInt32):System.UInt32 [v2] @ 0 after stage [49] GraphVizStage:

Block #0 - Label L_10000 [Header]
  Prev: 
10000: X86.Push32              EBP
10000: X86.Mov32               EBP <= ESP
10000: IR.Flow                 L_00000
  Next: L_00000

Block #1 - Label L_00000
  Prev: L_10000
00001: X86.MovLoad32           EAX <= EBP, 8 (p0)
00003: X86.Mov32               ECX <= 2863311531
00003: X86.Mul32               EDX, EAX <= EAX, ECX
00003: IR.Nop
00003: X86.Mov32               EAX <= EDX
00003: X86.Shr32               EAX <= EAX, 1
00008: IR.Flow                 L_FFFFF
  Next: L_FFFFF

Block #2 - Label L_FFFFF
  Prev: L_00000
FFFFF: IR.Nop
FFFFF: X86.Pop32 EBP [I4]
FFFFF: X86.Ret
  Next: