Bug 144527 – DFG::LICMPhase shouldn't hoist type checks unless it knows that the check will succeed at the loop pre-header

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

[Filip Pizlo]

If a node has a type check - even something like a CheckStructure - then we should
only hoist the node if we know that it will execute on every loop iteration or if we know
that the type check will always succeed at the loop pre-header through some other means
(like looking at prediction propagation results). Otherwise, we might make a mistake like
this:

var o = ...; // sometimes null and sometimes an object with structure S1.
for (...) {
    if (o)
        ... = o.f; // CheckStructure and GetByOffset, which we will currently hoist.
}

When we encounter such code, we'll hoist the CheckStructure and GetByOffset and then we
will have a recompile. We'll then end up thinking that the get_by_id needs to be
polymorphic, which is false.

We can counter this by either having a control flow equivalence check, or by consulting
prediction propagation to see if the check would always succeed. Prediction propagation
would not be enough for things like:

var p = ...; // some boolean predicate
var o = {};
if (p)
    o.f = 42;
for (...) {
    if (p)
        ... = o.f;
}

Prediction propagation can't tell us anything about the structure, and the CheckStructure
will appear to be hoistable because the loop doesn't clobber structures. The cell check
in the CheckStructure will be hoistable though, since prediction propagation can tell us
that o is always SpecFinalObject. In cases like this, control flow equivalence is the
only effective guard.

[Filip Pizlo]

Created attachment 279138 [details]
it begins!

[Filip Pizlo]

Created attachment 279152 [details]
more

[Filip Pizlo]

Created attachment 279298 [details]
almost done

[Filip Pizlo]

Not landing this yet because it's a massive regression on imaging-gaussian-blur.  Basically we need to be somewhat careful about what we consider to be too unsafe to hoist.  Perhaps on the first compilation we should just allow everything to be hoisted.

[Filip Pizlo]

I think that if nothing that was hoisted has ever exited then we should allow ourselves to hoist without worrying.

If anything that was hoisted has exited then we should be more careful about hoisting.

So, I think that we want something in the exit profile that:
1) Makes sure that hoisted exits don't contribute to the normal exit counting.
2) Makes sure that we know if hoisted exits had ever happened.

[Filip Pizlo]

Created attachment 279348 [details]
the patch

[Filip Pizlo]

Created attachment 279394 [details]
the patch

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/BackwardsGraph.h:174:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGGraph.cpp:35:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/dfg/DFGMayExit.cpp:118:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/ftl/FTLOSRExit.cpp:106:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/JavaScriptCore/dfg/DFGControlEquivalenceAnalysis.h:31:  Alphabetical sorting problem.  [build/include_order] [4]
Total errors found: 5 in 41 files


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

[Filip Pizlo]

(In reply to comment #8)
> Attachment 279394 [details] did not pass style-queue:
> 
> 
> ERROR: Source/WTF/wtf/BackwardsGraph.h:174:  Place brace on its own line for
> function definitions.  [whitespace/braces] [4]
> ERROR: Source/JavaScriptCore/dfg/DFGGraph.cpp:35:  Alphabetical sorting
> problem.  [build/include_order] [4]
> ERROR: Source/JavaScriptCore/dfg/DFGMayExit.cpp:118:  Place brace on its own
> line for function definitions.  [whitespace/braces] [4]
> ERROR: Source/JavaScriptCore/ftl/FTLOSRExit.cpp:106:  Wrong number of spaces
> before statement. (expected: 8)  [whitespace/indent] [4]
> ERROR: Source/JavaScriptCore/dfg/DFGControlEquivalenceAnalysis.h:31: 
> Alphabetical sorting problem.  [build/include_order] [4]
> Total errors found: 5 in 41 files
> 
> 
> If any of these errors are false positives, please file a bug against
> check-webkit-style.

I fixed the style errors that were real style errors.

[Saam Barati]

Comment on attachment 279394 [details]
the patch

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

r=me

> Source/JavaScriptCore/ChangeLog:9
> +        This adds a control flow equivalence analysis (called ControlEquivalenceAnalysis) based on
> +        dominator analysis over the backwards CFG. LICM now uses it to become more conservative

Worth having a sentence or two here explaining control flow equivalence for posterity.

> Source/JavaScriptCore/dfg/DFGBackwardsDominators.h:43
> +        : WTF::Dominators<BackwardsCFG>(graph.ensureBackwardsCFG())

Nice!
Pretty sweet that we can just do this with other graphs too.

> Source/WTF/wtf/BackwardsGraph.h:204
> +    template<typename T>
> +    Map<T> newMap() { return Map<T>(m_graph); }

Nit: Some of these can probably be private.

[Filip Pizlo]

(In reply to comment #10)
> Comment on attachment 279394 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=279394&action=review
> 
> r=me
> 
> > Source/JavaScriptCore/ChangeLog:9
> > +        This adds a control flow equivalence analysis (called ControlEquivalenceAnalysis) based on
> > +        dominator analysis over the backwards CFG. LICM now uses it to become more conservative
> 
> Worth having a sentence or two here explaining control flow equivalence for
> posterity.

Will do.

> 
> > Source/JavaScriptCore/dfg/DFGBackwardsDominators.h:43
> > +        : WTF::Dominators<BackwardsCFG>(graph.ensureBackwardsCFG())
> 
> Nice!
> Pretty sweet that we can just do this with other graphs too.
> 
> > Source/WTF/wtf/BackwardsGraph.h:204
> > +    template<typename T>
> > +    Map<T> newMap() { return Map<T>(m_graph); }
> 
> Nit: Some of these can probably be private.

Actually newMap() is part of the API that a Graph must provide to Dominators, so it has to be public.

[Filip Pizlo]

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

[Csaba Osztrogonác]

(In reply to comment #12)
> Landed in http://trac.webkit.org/changeset/201182

It broke the build everywhere.

[Filip Pizlo]

(In reply to comment #13)
> (In reply to comment #12)
> > Landed in http://trac.webkit.org/changeset/201182
> 
> It broke the build everywhere.

Fix coming.

[Filip Pizlo]

(In reply to comment #14)
> (In reply to comment #13)
> > (In reply to comment #12)
> > > Landed in http://trac.webkit.org/changeset/201182
> > 
> > It broke the build everywhere.
> 
> Fix coming.

This was caused by an idiotic last-minute change where I hoisted a string constant into a constant variable.  I forgot to rebuild and retest.

I landed a speculative fix as soon as I realized my mistake: http://trac.webkit.org/changeset/201184

Then I landed a proper fix once my build caught up and actually compiled the code: http://trac.webkit.org/changeset/201185

If this does not fix it then I'm ready to roll it out.