Closed Bug 664094 Opened 13 years ago Closed 13 years ago

IonMonkey: Baseline register allocation

Categories

(Core :: JavaScript Engine, defect)

x86
Windows 7
defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: dvander, Assigned: dvander)

References

Details

Attachments

(1 file, 3 obsolete files)

Attached patch WIP v1 (obsolete) — Splinter Review
IonMonkey will have full-fledged linear scan register allocation, but both for performance testing and for immediate codegen, we should have some sort of simplistic baseline register allocator. It will also be useful if LSRA turns out to be too heavyweight for a baseline run of the compiler.

The algorithm is two-pass. The first pass maps all virtual register IDs back to LDefinitions, and some bookkeeping. Then registers are assigned by walking all instructions in post-order:

(1) For every use, we allocate either a stack slot or machine reg from the virtual register. If one already exists, it gets re-used. 
(2) :. For every definition that has been used, when it has been reached, it will have either a stack slot or a register - and if not, a register is allocated anyway so the instruction can be assembled.

So, registers just propagate up. If an instruction's definition has both a stack slot and a register, that means it got spilled somewhere, so a store is injected immediately after the instruction. Similarly, if an instruction evicts a register, it injects a load restoring the register immediately after.

It's modeled off Nanojit, but the process is greatly simplified by not interleaving allocation with codegen. That means we should be able to handle control flow pretty easily, but I'll do that tomorrow.

With a heuristic to not allocate registers for types, it seems to do okay:

 function f(x, y, z) {
   return x & y & z;
 }

      0 move ()[(arg:-6) -> (edi)],  <|@
      0 move ()[(arg:-4) -> (ebx)],  <|@
      0 move ()[(arg:-2) -> (esi)],  <|@
      11 unbox ([i:0 (esi)]) (esi), (arg:-1) <|@
      12 unbox ([i:0 (ebx)]) (ebx), (arg:-3) <|@
      13 unbox ([i:0 (edi)]) (edi), (arg:-5) <|@
      14 bitop ([i:0 (edi)]) (edi), (ebx) <|@
      15 bitop ([i:0 (edi)]) (edi), (esi) <|@
      16 box ([t:0 (ecx)], [d:0 (edx)]) (edi) <|@
      18 return () (ecx), (edx) <|@
Attached patch WIP v2 (obsolete) — Splinter Review
now handles forward control flow
Attachment #539160 - Attachment is obsolete: true
Attached patch WIP v3 (obsolete) — Splinter Review
now handles forward phis
Attachment #539414 - Attachment is obsolete: true
Attached patch v4Splinter Review
This version handles loops, but the register allocation around loop edges is pretty bad. This is good enough to start code generation though.
Attachment #539618 - Attachment is obsolete: true
Attachment #539678 - Flags: review?(adrake)
Comment on attachment 539678 [details] [diff] [review]
v4

Per request, I did not evaluate the algorithm for correctness. Code organization and data-structure wise it looks fine for the time being, and it would be good to get this living now.
Attachment #539678 - Flags: review?(adrake) → review+
http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/8d58065db3b4
Status: ASSIGNED → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.