Bug 125740 – Create a DFG SSA backend with global register allocation

• Component: JavaScriptCore
• Status: NEW

[Filip Pizlo]

A lot of the speed-up from the FTL is from optimizations implemented on the DFG side.

Maybe we should just lower to machine code directly from DFG IR, but just incrementally improve how we do it.

[Filip Pizlo]

This is going to be kind of dirty at first, but I think it'll work.  Here's what we need:

1) Compute an estimate of the data format and scratch register count for each node.  These really are estimates, for the most part, and we have a lot of room for slop here.  More on that below.

2) Compute the liveness that includes OSR availability.  This is kind of fun because it combines two backwards analyses (DFG liveness and BC liveness), one forward analysis (OSR availability), and some CFA results (canExit).  I'll refer to this as liveness-including-availability, or LIA.

3) Compute interference and use that to do coloring for both spill slots and registers, globally.  Use a quick-and-dirty coloring algorithm for spills and a smart algorithm for registers.

4) Institute a policy that at the top of each basic block, all live nodes (according to LIA) should be in the register and stored according to the format/register/spill that those nodes report.

5) Code generation proceeds independently for each basic block and runs forward, as now.  If the code generator wants more scratch registers, it may spill nodes.  It may also decide to change the representation of a node.  But it is required to return all nodes to their original formats at the end of the basic block.

(5) is the reason why (1) can be sloppy.  For example we may compute that a node is formatted as DataFormatJS and uses 1 scratch register, but then that node may actually return a DataFormatInt32 and use 2 scratch registers.  Worst case, this causes one local spill (that gets restored by the end of the block) and causes the code generator to have to reformat the node at the end of the block.

[Filip Pizlo]

Created attachment 219257 [details]
work in progress

[Filip Pizlo]

Created attachment 219258 [details]
moar

[Filip Pizlo]

Created attachment 219274 [details]
implemented the RA

I wrote Chaitin's algorithm.  It was enjoyable.

[Oliver Hunt]

Comment on attachment 219258 [details]
moar

View in context: https://bugs.webkit.org/attachment.cgi?id=219258&action=review

> Source/JavaScriptCore/dfg/DFGLocationAllocationPhase.cpp:199
> +    HashMap<Node*, HashSet<Node*>> m_interference;

unused?

> Source/JavaScriptCore/dfg/DFGNode.h:1563
> +        ASSERT(static_cast<unsigned>(m_scratches) == num);

this cast shouldn't be necessary as both types are unsigned.  If your goal is to avoid undefined behaviour shenanigans your best approach would be to do ASSERT(!(num & ~0xff)), but none of tat should matter as asserts are only on in debug builds so no edge case optimisation should occur.

[Oliver Hunt]

(In reply to comment #4)
> Created an attachment (id=219274) [details]
> implemented the RA
> 
> I wrote Chaitin's algorithm.  It was enjoyable.

wrong patch?

[Filip Pizlo]

(In reply to comment #6)
> (In reply to comment #4)
> > Created an attachment (id=219274) [details] [details]
> > implemented the RA
> > 
> > I wrote Chaitin's algorithm.  It was enjoyable.
> 
> wrong patch?

Yeah.

[Filip Pizlo]

Created attachment 219282 [details]
for real this time

[Filip Pizlo]

Created attachment 219285 [details]
more

[Filip Pizlo]

Created attachment 219293 [details]
more

[Oliver Hunt]

Comment on attachment 219293 [details]
more

View in context: https://bugs.webkit.org/attachment.cgi?id=219293&action=review

> Source/JavaScriptCore/dfg/DFGAllocationUnit.h:106
> +    uintptr_t m_word;

Can we make this a bitfield rather than manually doing it? Or do you foresee these varying at runtime in future?

[Filip Pizlo]

(In reply to comment #11)
> (From update of attachment 219293 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=219293&action=review
> 
> > Source/JavaScriptCore/dfg/DFGAllocationUnit.h:106
> > +    uintptr_t m_word;
> 
> Can we make this a bitfield rather than manually doing it? Or do you foresee these varying at runtime in future?

How would this be a bitfield?  How do you envision a bitfield for pointers?

[Oliver Hunt]

Comment on attachment 219293 [details]
more

View in context: https://bugs.webkit.org/attachment.cgi?id=219293&action=review

>>> Source/JavaScriptCore/dfg/DFGAllocationUnit.h:106
>>> +    uintptr_t m_word;
>> 
>> Can we make this a bitfield rather than manually doing it? Or do you foresee these varying at runtime in future?
> 
> How would this be a bitfield?  How do you envision a bitfield for pointers?

Sorry, i missed it being purely a pointer - i just saw it being used in shift operations.  My bad

[Filip Pizlo]

Created attachment 219397 [details]
less

I think I have a better way of dealing with scratch registers.

[Filip Pizlo]

Created attachment 225612 [details]
more