Bug 118338

Summary:

fourthTier: DFG should have an SSA form for use by FTL

Product:

WebKit

Reporter:

Filip Pizlo <fpizlo>

Component:

JavaScriptCore

Assignee:

Filip Pizlo <fpizlo>

Status:

RESOLVED FIXED

Severity:

Normal

CC:

barraclough, ggaren, mark.lam, mhahnenberg, msaboff, oliver, sam

Priority:

Version:

528+ (Nightly build)

Hardware:

All

OS:

All

Bug Depends on:

118339, 118452, 118486

Bug Blocks:

112840

Attachments:

Description	Flags
it begins	none
more	none
more	none
more	none
more	none
even more	none
reworked it again	none
slowly adding things	none
liveness analysis is done	none
started on CFA	none
started thinking about FTL backend for SSA	none
more	none
getting there	none
it's getting real	none
forgot to delete a file	none
I might be done	none
more	none
still not compiling	none
OMG it compiles!	none
removed a file I accidentally added	none
added dumping of SSA metadata	none
it just ran something	none
runs some more code	none
it works.	none
it really works.	mhahnenberg: review+

Description Filip Pizlo 2013-07-02 21:57:34 PDT

This will be fun.

Comment 1 Filip Pizlo 2013-07-05 18:59:33 PDT

Created attachment 206181 [details]
it begins

Comment 2 Filip Pizlo 2013-07-05 19:38:37 PDT

Created attachment 206182 [details]
more

Comment 3 Filip Pizlo 2013-07-05 20:27:05 PDT

Created attachment 206183 [details]
more

I'm going to do phi reduction and SSA conversion in one phase.

Comment 4 Filip Pizlo 2013-07-06 19:33:36 PDT

Created attachment 206196 [details]
more

Comment 5 Filip Pizlo 2013-07-06 20:54:10 PDT

Created attachment 206198 [details]
more

This is starting to crystalize.

Comment 6 Filip Pizlo 2013-07-06 21:24:07 PDT

Created attachment 206199 [details]
even more

Comment 7 Filip Pizlo 2013-07-07 10:46:10 PDT

Created attachment 206209 [details]
reworked it again

I think I might be getting this to work.

Comment 8 Filip Pizlo 2013-07-07 21:39:40 PDT

Created attachment 206214 [details]
slowly adding things

Comment 9 Filip Pizlo 2013-07-08 09:49:44 PDT

Created attachment 206254 [details]
liveness analysis is done

Comment 10 Filip Pizlo 2013-07-08 16:58:50 PDT

Created attachment 206282 [details]
started on CFA

Comment 11 Filip Pizlo 2013-07-08 21:38:34 PDT

Created attachment 206288 [details]
started thinking about FTL backend for SSA

Comment 12 Filip Pizlo 2013-07-08 22:26:29 PDT

Created attachment 206290 [details]
more

Starting to make sense of how to deal with flushed locals and their silly value formats.

Comment 13 Filip Pizlo 2013-07-09 10:21:58 PDT

Created attachment 206338 [details]
getting there

Still working on constructing OSR exit data over SSA.  Doing it as a separate phase that the FTL can run before lowering.

Comment 14 Filip Pizlo 2013-07-10 12:30:08 PDT

Created attachment 206407 [details]
it's getting real

OMG.  So much code.

Comment 15 Filip Pizlo 2013-07-10 12:37:27 PDT

Created attachment 206408 [details]
forgot to delete a file

Comment 16 Filip Pizlo 2013-07-11 14:10:58 PDT

Created attachment 206486 [details]
I might be done

Comment 17 Filip Pizlo 2013-07-11 14:33:40 PDT

Created attachment 206489 [details]
more

Comment 18 Filip Pizlo 2013-07-11 20:03:27 PDT

Created attachment 206503 [details]
still not compiling

Comment 19 Filip Pizlo 2013-07-11 21:56:47 PDT

Created attachment 206504 [details]
OMG it compiles!

Comment 20 Filip Pizlo 2013-07-11 21:57:51 PDT

Created attachment 206505 [details]
removed a file I accidentally added

Comment 21 Filip Pizlo 2013-07-12 12:20:48 PDT

Created attachment 206561 [details]
added dumping of SSA metadata

Comment 22 Filip Pizlo 2013-07-12 15:41:41 PDT

Created attachment 206575 [details]
it just ran something

Obviously I still have work to do but it's getting exciting.

Comment 23 Filip Pizlo 2013-07-12 20:01:53 PDT

Created attachment 206586 [details]
runs some more code

Comment 24 Filip Pizlo 2013-07-12 20:32:51 PDT

Created attachment 206589 [details]
it works.

Comment 25 Filip Pizlo 2013-07-12 22:28:14 PDT

Comment on attachment 206589 [details]
it works.

Never mind.  This still has bugs.

Comment 26 Filip Pizlo 2013-07-12 22:42:33 PDT

Created attachment 206592 [details]
it really works.

Comment 27 Mark Hahnenberg 2013-07-15 16:50:45 PDT

Comment on attachment 206592 [details]
it really works.

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

r=me with small changes.

> Source/JavaScriptCore/dfg/DFGFlushLivenessAnalysisPhase.cpp:144
> +                // Three possibilities:
> +                // 1) Predecessor format is Dead, in which case it acquires our format.
> +                // 2) Predecessor format is identical to our format, in which case we
> +                //    do nothing.
> +                // 3) Predecessor format is different from our format and it's not Dead,
> +                //    in which case we have an erroneous set of Flushes and SetLocals.

What if the predecessor was already processed by the fixpoint and says "not Dead" and the current block says "Dead"?

> Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp:260
> +        //   backwards analysis that LivenessAnalysisPhase does. As part of the

FlushLivenessAnalysisPhase?

> Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp:338
> +                case SetArgument: {
> +                    node->setOpAndDefaultFlags(GetArgument);
> +                    node->mergeFlags(resultFor(node->variableAccessData()->flushFormat()));
> +                    break;
> +                }

Should consider keeping SetArgument for captured arguments.

> Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp:346
> +        // Free all phis and reset variables vectors.

CPS phis?

> Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp:373
> +                continue;

break;

> Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp:386
> +                return edge.node();

node = edge.node();
break;

> Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp:392
> +                return node->child1().node();

node = node->child1().node();
break;

> Source/JavaScriptCore/dfg/DFGSSAConversionPhase.h:46
> +//   After this, any remaining SetLocal means Flush. Flush nodes are
> +//   eliminated. PhantomLocals become Phantoms. Nodes may may have children

Flush nodes aren't eliminated.

"may may".

> Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp:157
> +            dataLog("Compiling block ", *block, "\n");

Null guard for "block"? Or hoist check above.

> Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp:475
> +        MethodOfGettingAValueProfile profile =
> +            MethodOfGettingAValueProfile::fromLazyOperand(
> +                m_graph.m_profiledBlock,
> +                LazyOperandValueProfileKey(0, operand));

CodeBlock::profileForArgument?

> Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp:1873
> +        ExitKind kind, FormattedValue lowValue, MethodOfGettingAValueProfile profile,
> +        LValue failCondition)
> +    {
> +        appendOSRExit(
> +            kind, lowValue, profile, failCondition, BackwardSpeculation, FormattedValue());
> +    }

Passing GetArgument as high value also works.

> Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp:2467
> +        ExitKind kind, FormattedValue lowValue, MethodOfGettingAValueProfile profile,

Ditto.

Comment 28 Filip Pizlo 2013-07-15 18:18:50 PDT

(In reply to comment #27)
> (From update of attachment 206592 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=206592&action=review
> 
> r=me with small changes.
> 
> > Source/JavaScriptCore/dfg/DFGFlushLivenessAnalysisPhase.cpp:144
> > +                // Three possibilities:
> > +                // 1) Predecessor format is Dead, in which case it acquires our format.
> > +                // 2) Predecessor format is identical to our format, in which case we
> > +                //    do nothing.
> > +                // 3) Predecessor format is different from our format and it's not Dead,
> > +                //    in which case we have an erroneous set of Flushes and SetLocals.
> 
> What if the predecessor was already processed by the fixpoint and says "not Dead" and the current block says "Dead"?

We ain't sure about this yet and have no example of where this is needed, so I put in a FIXME for now.

> 
> > Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp:260
> > +        //   backwards analysis that LivenessAnalysisPhase does. As part of the
> 
> FlushLivenessAnalysisPhase?

Fixed.

> 
> > Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp:338
> > +                case SetArgument: {
> > +                    node->setOpAndDefaultFlags(GetArgument);
> > +                    node->mergeFlags(resultFor(node->variableAccessData()->flushFormat()));
> > +                    break;
> > +                }
> 
> Should consider keeping SetArgument for captured arguments.

Fixed.

> 
> > Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp:346
> > +        // Free all phis and reset variables vectors.
> 
> CPS phis?

Fixed.

> 
> > Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp:373
> > +                continue;
> 
> break;

Fixed.

> 
> > Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp:386
> > +                return edge.node();
> 
> node = edge.node();
> break;

Fixed.

> 
> > Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp:392
> > +                return node->child1().node();
> 
> node = node->child1().node();
> break;

Fixed.

> 
> > Source/JavaScriptCore/dfg/DFGSSAConversionPhase.h:46
> > +//   After this, any remaining SetLocal means Flush. Flush nodes are
> > +//   eliminated. PhantomLocals become Phantoms. Nodes may may have children
> 
> Flush nodes aren't eliminated.

Fixed.

> 
> "may may".

Fixed.


> 
> > Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp:157
> > +            dataLog("Compiling block ", *block, "\n");
> 
> Null guard for "block"? Or hoist check above.

Fixed by hoisting the check.

> 
> > Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp:475
> > +        MethodOfGettingAValueProfile profile =
> > +            MethodOfGettingAValueProfile::fromLazyOperand(
> > +                m_graph.m_profiledBlock,
> > +                LazyOperandValueProfileKey(0, operand));
> 
> CodeBlock::profileForArgument?

Fixed by passing m_node as the highValue.

> 
> > Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp:1873
> > +        ExitKind kind, FormattedValue lowValue, MethodOfGettingAValueProfile profile,
> > +        LValue failCondition)
> > +    {
> > +        appendOSRExit(
> > +            kind, lowValue, profile, failCondition, BackwardSpeculation, FormattedValue());
> > +    }
> 
> Passing GetArgument as high value also works.

Yup, fixed.

> 
> > Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp:2467
> > +        ExitKind kind, FormattedValue lowValue, MethodOfGettingAValueProfile profile,
> 
> Ditto.

Fixed.

Comment 29 Filip Pizlo 2013-07-15 18:34:34 PDT

Landed in http://trac.webkit.org/changeset/152692