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.
Created attachment 279138 [details] it begins!
Created attachment 279152 [details] more
Created attachment 279298 [details] almost done
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.
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.
Created attachment 279348 [details] the patch
Created attachment 279394 [details] the patch
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.
(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.
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.
(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.
Landed in http://trac.webkit.org/changeset/201182
(In reply to comment #12) > Landed in http://trac.webkit.org/changeset/201182 It broke the build everywhere.
(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.
(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.