Bug 197265 – [B3] Constants should be hoisted to the root block until moveConstants

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Robin Morisset]

The moveConstants phase gathers and moves all constants based purely on their uses. So where they are located before that point is not relevant to anything.
Keeping them orphaned (in other words not in a basic block) until then would have many benefits:
- Makes all other B3 phases a bit faster, since they won't have to iterate over them. This might be significant as for example on JetStream2 27% of all B3Values at the beginning of B3 are constants (and up to 50% for some JS functions that reach FTL !)
- MoveConstants won't have to replace the constants by Nops that stay allocated throughout Air (since there is no elimination of dead code after moveConstants). As 11% of all B3Values that reach Air are Nops (and as far as I can tell they all come from moveConstants), this might offer a small but not useless memory saving
- By making basic blocks smaller this should enable tailDuplication and jump threading to trigger more often (since they are respectively limited to blocks of size <= 3 or blocks with nothing but a jump)

[Robin Morisset]

After discussing this with Phil, he convinced me that the assumption that no value is orphaned is too strongly embedded throughout B3 to easily change. Instead we can simply hoist all constants to the root block in ReduceStrength, deduplicating them along the way.
This won't provide the speed benefit from not iterating over them, but should provide both a small memory saving, and enable a bit more tail duplication.

[Robin Morisset]

Created attachment 368522 [details]
Patch

[EWS Watchlist]

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


ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:2163:  One line control clauses should not use braces.  [whitespace/braces] [4]
Total errors found: 1 in 10 files


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

[Robin Morisset]

Created attachment 369315 [details]
Patch

Just rebased on ToT and fixed style nit.

[Saam Barati]

Comment on attachment 369315 [details]
Patch

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

r=me

> Source/JavaScriptCore/ChangeLog:3
> +        [B3] Constants should be hoisted to the root block

doesn't moveConstants undo this? (I'm not saying if that's good or bad, but this title makes it seem like this wouldn't happen)

> Source/JavaScriptCore/ChangeLog:19
> +        When I tried measuring the total effect on JetStream2 I got a tiny and almost certainly non-significant progression.

Did you measure compile time effect?

[Saam Barati]

Comment on attachment 369315 [details]
Patch

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

> Source/JavaScriptCore/ChangeLog:11
> +        - We now run eliminateDeadCode just after moveConstants, so that the Nops that moveConstants generates are freed instead of staying live throughout Air compilation.

what's the goal here? Lowering memory (I'm assuming yes)? It's worth stating the goal.

[Robin Morisset]

(In reply to Saam Barati from comment #5)
> Comment on attachment 369315 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=369315&action=review
> 
> r=me

Thanks!

> 
> > Source/JavaScriptCore/ChangeLog:3
> > +        [B3] Constants should be hoisted to the root block
> 
> doesn't moveConstants undo this? (I'm not saying if that's good or bad, but
> this title makes it seem like this wouldn't happen)

Yes, the entire reason we can put everything in the root block without thinking is that moveConstants will move them to the optimal place at the end of B3. I will fix the bug title.

> 
> > Source/JavaScriptCore/ChangeLog:19
> > +        When I tried measuring the total effect on JetStream2 I got a tiny and almost certainly non-significant progression.
> 
> Did you measure compile time effect?

I did, and it is also a non-significant progression. I expect it may become significant when combined with https://bugs.webkit.org/show_bug.cgi?id=196578, but I have not yet measured that combination.

[Robin Morisset]

(In reply to Saam Barati from comment #6)
> Comment on attachment 369315 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=369315&action=review
> 
> > Source/JavaScriptCore/ChangeLog:11
> > +        - We now run eliminateDeadCode just after moveConstants, so that the Nops that moveConstants generates are freed instead of staying live throughout Air compilation.
> 
> what's the goal here? Lowering memory (I'm assuming yes)? It's worth stating
> the goal.

Yes, it is to reduce memory pressure. I will clarify it in the Changelog.

[Robin Morisset]

Comment on attachment 369315 [details]
Patch

>diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog
>index da788495030..5eb2f8abe3d 100644
>--- a/Source/JavaScriptCore/ChangeLog
>+++ b/Source/JavaScriptCore/ChangeLog
>@@ -1,3 +1,37 @@
>[phone]  Robin Morisset  <[e-mail]>
>+
>+        [B3] Constants should be hoisted to the root block until moveConstants
>+        https://bugs.webkit.org/show_bug.cgi?id=197265
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        This patch does the following:
>+        - B3ReduceStrength now hoists all constants to the root BB, and de-duplicates them along the way
>+        - B3PureCSE no longer bothers with constants, since they are already de-duplicated by the time it gets to see them
>+        - We now run eliminateDeadCode just after moveConstants, so that the Nops that moveConstants generates are freed instead of staying live throughout Air compilation. This should help memory pressure during Air compilation.
>+        - I also took the opportunity to fix typos in comments in various parts of the code base.
>+
>+        Here are a few numbers to justify this patch:
>+        - In JetStream2, about 27% of values at the beginning of B3 are constants
>+        - In JetStream2, about 11% of values at the end of B3 are Nops
>+        - In JetStream2, this patch increases the number of times that tail duplication happens from a bit less than 24k to a bit more than 25k (hoisting constants makes blocks smaller).
>+
>+        When I tried measuring the total effect on JetStream2 I got a tiny and almost certainly non-significant progression.
>+
>+        * b3/B3Generate.cpp:
>+        (JSC::B3::generateToAir):
>+        * b3/B3MoveConstants.cpp:
>+        * b3/B3PureCSE.cpp:
>+        (JSC::B3::PureCSE::process):
>+        * b3/B3PureCSE.h:
>+        * b3/B3ReduceStrength.cpp:
>+        * bytecode/GetByIdStatus.cpp:
>+        (JSC::GetByIdStatus::computeForStubInfoWithoutExitSiteFeedback):
>+        * dfg/DFGCSEPhase.cpp:
>+        * dfg/DFGOSRAvailabilityAnalysisPhase.h:
>+        * dfg/DFGOSRExit.cpp:
>+        (JSC::DFG::OSRExit::executeOSRExit):
>+
> 2019-05-07  Tadeu Zagallo  <[e-mail]>
> 
>         tryCachePutByID should not crash if target offset changes
>diff --git a/Source/JavaScriptCore/b3/B3Generate.cpp b/Source/JavaScriptCore/b3/B3Generate.cpp
>index e370e215894..ba2fa08482e 100644
>--- a/Source/JavaScriptCore/b3/B3Generate.cpp
>+++ b/Source/JavaScriptCore/b3/B3Generate.cpp
>@@ -116,6 +116,7 @@ void generateToAir(Procedure& procedure)
>     lowerMacrosAfterOptimizations(procedure);
>     legalizeMemoryOffsets(procedure);
>     moveConstants(procedure);
>+    eliminateDeadCode(procedure);
> 
>     // FIXME: We should run pureCSE here to clean up some platform specific changes from the previous phases.
>     // https://bugs.webkit.org/show_bug.cgi?id=164873
>diff --git a/Source/JavaScriptCore/b3/B3MoveConstants.cpp b/Source/JavaScriptCore/b3/B3MoveConstants.cpp
>index 7acba1e525d..bbd781df40d 100644
>--- a/Source/JavaScriptCore/b3/B3MoveConstants.cpp
>+++ b/Source/JavaScriptCore/b3/B3MoveConstants.cpp
>@@ -154,7 +154,7 @@ private:
>                 };
>                 
>                 // We call this when we have found a constant that we'd like to use. It's possible that
>-                // we have computed that the constant should be meterialized in this block, but we
>+                // we have computed that the constant should be materialized in this block, but we
>                 // haven't inserted it yet. This inserts the constant if necessary.
>                 auto materialize = [&] (Value* child) {
>                     ValueKey key = child->key();
>diff --git a/Source/JavaScriptCore/b3/B3PureCSE.cpp b/Source/JavaScriptCore/b3/B3PureCSE.cpp
>index eb9c46b1740..e4e9ccd3efa 100644
>--- a/Source/JavaScriptCore/b3/B3PureCSE.cpp
>+++ b/Source/JavaScriptCore/b3/B3PureCSE.cpp
>@@ -68,7 +68,7 @@ Value* PureCSE::findMatch(const ValueKey& key, BasicBlock* block, Dominators& do
> 
> bool PureCSE::process(Value* value, Dominators& dominators)
> {
>-    if (value->opcode() == Identity)
>+    if (value->opcode() == Identity || value->isConstant())
>         return false;
> 
>     ValueKey key = value->key();
>diff --git a/Source/JavaScriptCore/b3/B3PureCSE.h b/Source/JavaScriptCore/b3/B3PureCSE.h
>index d26e4117f15..66857be1617 100644
>--- a/Source/JavaScriptCore/b3/B3PureCSE.h
>+++ b/Source/JavaScriptCore/b3/B3PureCSE.h
>@@ -40,7 +40,7 @@ class Value;
> typedef Vector<Value*, 1> Matches;
> 
> // This is a reusable utility for doing pure CSE. You can use it to do pure CSE on a program by just
>-// proceeding in order an calling process().
>+// proceeding in order and calling process().
> class PureCSE {
> public:
>     PureCSE();
>diff --git a/Source/JavaScriptCore/b3/B3ReduceStrength.cpp b/Source/JavaScriptCore/b3/B3ReduceStrength.cpp
>index 7e22c29d6d4..2f34efdc820 100644
>--- a/Source/JavaScriptCore/b3/B3ReduceStrength.cpp
>+++ b/Source/JavaScriptCore/b3/B3ReduceStrength.cpp
>@@ -402,6 +402,7 @@ public:
>         : m_proc(proc)
>         , m_insertionSet(proc)
>         , m_blockInsertionSet(proc)
>+        , m_root(proc.at(0))
>     {
>     }
> 
>@@ -442,6 +443,7 @@ public:
>             // keep @thing. That's better, since we usually want things to stay wherever the client
>             // put them. We're not actually smart enough to move things around at random.
>             m_changed |= eliminateDeadCodeImpl(m_proc);
>+            m_valueForConstant.clear();
>             
>             simplifySSA();
>             
>@@ -2145,7 +2147,29 @@ private:
>             }
>             break;
>         }
>-            
>+
>+        case Const32:
>+        case Const64:
>+        case ConstFloat:
>+        case ConstDouble: {
>+            ValueKey key = m_value->key();
>+            if (Value* constInRoot = m_valueForConstant.get(key)) {
>+                if (constInRoot != m_value) {
>+                    m_value->replaceWithIdentity(constInRoot);
>+                    m_changed = true;
>+                }
>+            } else if (m_block == m_root)
>+                m_valueForConstant.add(key, m_value);
>+            else {
>+                Value* constInRoot = m_proc.clone(m_value);
>+                m_root->appendNonTerminal(constInRoot);
>+                m_valueForConstant.add(key, constInRoot);
>+                m_value->replaceWithIdentity(constInRoot);
>+                m_changed = true;
>+            }
>+            break;
>+        }
>+
>         default:
>             break;
>         }
>@@ -2794,6 +2818,8 @@ private:
>     Procedure& m_proc;
>     InsertionSet m_insertionSet;
>     BlockInsertionSet m_blockInsertionSet;
>+    HashMap<ValueKey, Value*> m_valueForConstant;
>+    BasicBlock* m_root { nullptr };
>     BasicBlock* m_block { nullptr };
>     unsigned m_index { 0 };
>     Value* m_value { nullptr };
>diff --git a/Source/JavaScriptCore/bytecode/GetByIdStatus.cpp b/Source/JavaScriptCore/bytecode/GetByIdStatus.cpp
>index 26bcd5ff763..6e4e8bfdbe1 100644
>--- a/Source/JavaScriptCore/bytecode/GetByIdStatus.cpp
>+++ b/Source/JavaScriptCore/bytecode/GetByIdStatus.cpp
>@@ -276,7 +276,7 @@ GetByIdStatus GetByIdStatus::computeForStubInfoWithoutExitSiteFeedback(
>                     return GetByIdStatus(JSC::slowVersion(summary));
> 
>                 if (domAttribute) {
>-                    // Give up when cutom accesses are not merged into one.
>+                    // Give up when custom accesses are not merged into one.
>                     if (result.numVariants() != 1)
>                         return GetByIdStatus(JSC::slowVersion(summary));
>                 } else {
>diff --git a/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp b/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp
>index 2ba59463fb1..e89daae4957 100644
>--- a/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp
>+++ b/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp
>@@ -257,7 +257,7 @@ private:
>         });
>     }
> 
>-    // The majority of Impure Stack Slotsare unique per value.
>+    // The majority of Impure Stack Slots are unique per value.
>     // This is very useful for fast clobber(), we can just remove the slot addressed by AbstractHeap
>     // in O(1).
>     //
>diff --git a/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.h b/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.h
>index 14de94da1d8..69e8b7550c8 100644
>--- a/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.h
>+++ b/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.h
>@@ -33,7 +33,7 @@ namespace JSC { namespace DFG {
> 
> class Graph;
> 
>-// Computes BasicBlock::ssa->availabiltiyAtHead/Tail. This is a forward flow type inference
>+// Computes BasicBlock::ssa->availabilityAtHead/Tail. This is a forward flow type inference
> // over MovHints and SetLocals. This analysis is run directly by the Plan for preparing for
> // lowering to B3 IR, but it can also be used as a utility. Note that if you run it before
> // stack layout, all of the flush availability will omit the virtual register - but it will
>diff --git a/Source/JavaScriptCore/dfg/DFGOSRExit.cpp b/Source/JavaScriptCore/dfg/DFGOSRExit.cpp
>index e185a100f20..09b30ba3cfc 100644
>--- a/Source/JavaScriptCore/dfg/DFGOSRExit.cpp
>+++ b/Source/JavaScriptCore/dfg/DFGOSRExit.cpp
>@@ -452,7 +452,7 @@ void OSRExit::executeOSRExit(Context& context)
> 
>     context.sp() = context.fp<uint8_t*>() + exitState.stackPointerOffset;
> 
>-    // The only reason for using this do while look is so we can break out midway when appropriate.
>+    // The only reason for using this do while loop is so we can break out midway when appropriate.
>     do {
>         auto extraInitializationLevel = static_cast<ExtraInitializationLevel>(exitState.extraInitializationLevel);
>

[Robin Morisset]

(In reply to Robin Morisset from comment #9)
Oops, I thought that option let me modify the patch in the browser, instead it dumped it as a comment. Sorry for the spam.

[Robin Morisset]

Created attachment 369319 [details]
Patch for landing

Just tweaked the Changelog.

[WebKit Commit Bot]

Comment on attachment 369319 [details]
Patch for landing

Clearing flags on attachment: 369319

Committed r245035: <https://trac.webkit.org/changeset/245035>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Radar WebKit Bug Importer]

<rdar://problem/50555637>