Bug 143736

Summary: DFG should not use or preserve Phantoms during transformations
Product: WebKit Reporter: Filip Pizlo <fpizlo>
Component: JavaScriptCoreAssignee: Filip Pizlo <fpizlo>
Status: RESOLVED FIXED    
Severity: Normal CC: barraclough, benjamin, commit-queue, ggaren, mark.lam, mhahnenb, mmirman, msaboff, nrotem, oliver, sam, sbarati
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: All   
OS: All   
Bug Depends on: 143734, 143735, 143843    
Bug Blocks: 143733    
Attachments:
Description Flags
work in progress
none
more
none
almost
none
starting to work
none
the patch
none
rebased
none
trying another rebase
none
the patch ggaren: review+

Description Filip Pizlo 2015-04-14 15:57:49 PDT
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().
Comment 1 Filip Pizlo 2015-04-23 15:07:53 PDT
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.
Comment 2 Filip Pizlo 2015-04-23 15:20:57 PDT
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.
Comment 3 Filip Pizlo 2015-04-23 16:04:08 PDT
Created attachment 251508 [details]
work in progress
Comment 4 Filip Pizlo 2015-04-23 16:28:14 PDT
Created attachment 251513 [details]
more
Comment 5 Filip Pizlo 2015-04-23 17:58:12 PDT
Created attachment 251518 [details]
almost
Comment 6 Filip Pizlo 2015-04-27 12:21:45 PDT
Created attachment 251767 [details]
starting to work
Comment 7 Filip Pizlo 2015-04-27 12:50:53 PDT
*** Bug 126239 has been marked as a duplicate of this bug. ***
Comment 8 Filip Pizlo 2015-04-27 16:59:12 PDT
Created attachment 251787 [details]
the patch
Comment 9 Filip Pizlo 2015-04-27 18:20:42 PDT
Created attachment 251804 [details]
rebased
Comment 10 Filip Pizlo 2015-04-27 20:14:12 PDT
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...
Comment 11 Filip Pizlo 2015-04-27 20:28:47 PDT
Created attachment 251815 [details]
the patch
Comment 12 WebKit Commit Bot 2015-04-27 20:31:17 PDT
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.
Comment 13 Geoffrey Garen 2015-04-28 11:20:46 PDT
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.
Comment 14 Filip Pizlo 2015-04-28 12:25:34 PDT
(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. :-)
Comment 15 Filip Pizlo 2015-04-28 12:29:03 PDT
Landed in http://trac.webkit.org/changeset/183497