Bug 143736 – DFG should not use or preserve Phantoms during transformations

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Filip Pizlo]

After https://bugs.webkit.org/show_bug.cgi?id=143734 and https://bugs.webkit.org/show_bug.cgi?id=143735 are done, there will be no need to insert Phantoms as part of bytecode parsing or when removing/transforming code.  So, the code to insert Phantoms should be removed and Node::convertToPhantom() should just become Node::remove().

[Filip Pizlo]

I've hit a snag: backwards propagation needs to know when values are used by bytecode in strange ways.  It currently looks like it might rely on Phantom to tell it that the bits of some value are all observed.

Ugh.

[Filip Pizlo]

I think that we need to just embrace the fact that the DFG IR prior to FixupPhase *does* currently accurately represent all bytecode uses.  This may be hard to maintain, but it *is* useful.

The part that we believe to be unsound is maintaining that same information in DFG IR *after* we have completed FixupPhase and are doing other transformations.

If we embrace this, then we would be able to also bring back DCE. This time it would be a pre-FixupPhase DCE.

[Filip Pizlo]

Created attachment 251508 [details]
work in progress

[Filip Pizlo]

Created attachment 251513 [details]
more

[Filip Pizlo]

Created attachment 251518 [details]
almost

[Filip Pizlo]

Created attachment 251767 [details]
starting to work

[Filip Pizlo]

*** Bug 126239 has been marked as a duplicate of this bug. ***

[Filip Pizlo]

Created attachment 251787 [details]
the patch

[Filip Pizlo]

Created attachment 251804 [details]
rebased

[Filip Pizlo]

Created attachment 251810 [details]
trying another rebase

I'm beginning to think that maybe it's not my patch's fault that EWS can't apply the patch...

[Filip Pizlo]

Created attachment 251815 [details]
the patch

[WebKit Commit Bot]

Attachment 251815 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/dfg/DFGNodeType.h:64:  One space before end of line comments  [whitespace/comments] [5]
ERROR: Source/JavaScriptCore/dfg/DFGNodeType.h:64:  Should have a space between // and comment  [whitespace/comments] [4]
Total errors found: 2 in 32 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Geoffrey Garen]

Comment on attachment 251815 [details]
the patch

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

> Source/JavaScriptCore/ChangeLog:33
> +        - Phantoms before FixupPhase. I kind of like these. It means that before FixupPhase, we can do
> +          backwards analyses and rely on the fact that the users of a node in DFG IR are a superset of
> +          the users of the original local's live range in bytecode. This is essential for supporting our
> +          BackwardsPropagationPhase, which is an important optimization for things like asm.js.

I think it's strange to use "phantom" to mean these two different things: (1) something inserted during bytecode parsing to mark bytecode uses according to the text of the bytecode; (2) something inserted after optimization to mark what is live along OSR exit paths according to a liveness analysis of the bytecode.

Two names that might distinguish these meanings are "UsedInBytecode" and "LiveInBytecode". Or "BytecodeOperand" and "LiveInBytecode". It should be harmless to leave behind "BytecodeOperand" nodes in the graph -- although perhaps we would still remove them for the sake of brevity when dumping IR. It is strange that, today, if you forget to remove a "BytecodeOperand" annotation, you might have a performance problem, even if there is no corresponding "LiveInBytecode" annotation.

> Source/JavaScriptCore/dfg/DFGCleanUpPhase.h:37
> +bool performCleanUp(Graph&);

The names "fixup phase" and "cleanup phase" are super broad, and not meaningful to me.

[Filip Pizlo]

(In reply to comment #13)
> Comment on attachment 251815 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=251815&action=review
> 
> > Source/JavaScriptCore/ChangeLog:33
> > +        - Phantoms before FixupPhase. I kind of like these. It means that before FixupPhase, we can do
> > +          backwards analyses and rely on the fact that the users of a node in DFG IR are a superset of
> > +          the users of the original local's live range in bytecode. This is essential for supporting our
> > +          BackwardsPropagationPhase, which is an important optimization for things like asm.js.
> 
> I think it's strange to use "phantom" to mean these two different things:
> (1) something inserted during bytecode parsing to mark bytecode uses
> according to the text of the bytecode; (2) something inserted after
> optimization to mark what is live along OSR exit paths according to a
> liveness analysis of the bytecode.

It's true that there are some small differences between the Phantoms used in parsing and those in the backend. Comparing the two is tricky, since the IR will change substantially between parsing and the backend. But imagine those programs where we don't actually change the IR during FixupPhase or any of the optimizations - maybe because the program already has minimal redundancy and doesn't use any operations, like double math, that require FixupPhase to insert conversion nodes. For such programs I would expect PhantomInsertionPhase to simply add back those Phantoms that were removed during FixupPhase, with maybe two exceptions:

- Phantom is defined as being a liveness marker and so it doesn't need to be inserted if there is another Phantom after it for the same node. "Phantom(@x); ...; Phantom(@x)" only requires the latter Phantom and the former can be removed. ByteCodeParser doesn't do such an optimization, but PhantomInsertionPhase does.

- Phantom is only necessary if the IR doesn't already have an appropriate use of that node. Both ByteCodeParser and PhantomInsertionPhase do this optimization, but PhantomInsertionPhase does it much more aggressively. ByteCodeParser does just because we only insert Phantoms if we know that we won't emit any other use. PhantomInsertionPhase actually searches for other uses of the node between the Phantom insertion point and the last exit. Despite the different approach, the results are strikingly similar for real code - and the implication for users of Phantoms are the same.

It may be that we use the Phantom-in-parsing differently than we use the Phantom-in-codegen. But they give us similar, if not identical, guarantees about liveness and uses.

It's worthwhile to look for better names for things. Here's the bug for that. We should discuss it more on that bug. https://bugs.webkit.org/show_bug.cgi?id=137307

> 
> Two names that might distinguish these meanings are "UsedInBytecode" and
> "LiveInBytecode". Or "BytecodeOperand" and "LiveInBytecode". It should be
> harmless to leave behind "BytecodeOperand" nodes in the graph -- although
> perhaps we would still remove them for the sake of brevity when dumping IR.

Reducing the number of nodes we add is useful for reducing compile times. Are you suggesting adding a BytecodeOperand node everywhere that the bytecode used an operand?

Phantom-from-parser currently means, "I used this node in bytecode here, and I can't tell you how I used it, so if you care then assume the worst". This is a subtle meaning. We can probably come up with a name for this, but "BytecodeOperand" doesn't convey this to me.

> It is strange that, today, if you forget to remove a "BytecodeOperand"
> annotation, you might have a performance problem, even if there is no
> corresponding "LiveInBytecode" annotation.

I don't follow. If by BytecodeOperand you mean Phantom-from-parser, then we don't have a phase to selectively remove them. I don't remember having a performance problem because I accidentally inserted too many Phantoms in ByteCodeParser.

> 
> > Source/JavaScriptCore/dfg/DFGCleanUpPhase.h:37
> > +bool performCleanUp(Graph&);
> 
> The names "fixup phase" and "cleanup phase" are super broad, and not
> meaningful to me.

True.  Filed: https://bugs.webkit.org/show_bug.cgi?id=144345.  Feel free to rubber stamp. :-)

[Filip Pizlo]

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