DFG CFA should pick the right time to inject OSR entry data
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 10 May 2018 22:23:12 +0000 (22:23 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 10 May 2018 22:23:12 +0000 (22:23 +0000)
https://bugs.webkit.org/show_bug.cgi?id=185530

Reviewed by Saam Barati.

Previously, we would do a bonus run of CFA to inject OSR entry data. This patch makes us inject
OSR entry data as part of the normal flow of CFA, which reduces the total number of CFA
reexecutions while minimizing the likelihood that we have CFA execute constants in paths that
would eventually LUB to non-constant.

This looks like almost a 1% speed-up on SunSpider-CompileTime. All of the logic for preventing
execution over constants is for V8Spider-CompileTime/regexp, which would otherwise do a lot of
useless regexp/string execution in the compiler.

* dfg/DFGBlockSet.h:
(JSC::DFG::BlockSet::remove):
* dfg/DFGCFAPhase.cpp:
(JSC::DFG::CFAPhase::run):
(JSC::DFG::CFAPhase::injectOSR):
(JSC::DFG::CFAPhase::performBlockCFA):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@231665 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGBlockSet.h
Source/JavaScriptCore/dfg/DFGCFAPhase.cpp

index 895d2c1..270d952 100644 (file)
@@ -1,3 +1,26 @@
+2018-05-10  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG CFA should pick the right time to inject OSR entry data
+        https://bugs.webkit.org/show_bug.cgi?id=185530
+
+        Reviewed by Saam Barati.
+        
+        Previously, we would do a bonus run of CFA to inject OSR entry data. This patch makes us inject
+        OSR entry data as part of the normal flow of CFA, which reduces the total number of CFA
+        reexecutions while minimizing the likelihood that we have CFA execute constants in paths that
+        would eventually LUB to non-constant.
+        
+        This looks like almost a 1% speed-up on SunSpider-CompileTime. All of the logic for preventing
+        execution over constants is for V8Spider-CompileTime/regexp, which would otherwise do a lot of
+        useless regexp/string execution in the compiler.
+
+        * dfg/DFGBlockSet.h:
+        (JSC::DFG::BlockSet::remove):
+        * dfg/DFGCFAPhase.cpp:
+        (JSC::DFG::CFAPhase::run):
+        (JSC::DFG::CFAPhase::injectOSR):
+        (JSC::DFG::CFAPhase::performBlockCFA):
+
 2018-05-09  Filip Pizlo  <fpizlo@apple.com>
 
         InPlaceAbstractState::beginBasicBlock shouldn't copy all m_variables every time
index 7024ee4..60b4496 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2018 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -44,6 +44,12 @@ public:
         return !m_set.set(block->index);
     }
     
+    // Return true if the block was removed, false if it was already absent.
+    bool remove(BasicBlock* block)
+    {
+        return m_set.clear(block->index);
+    }
+    
     bool contains(BasicBlock* block) const
     {
         if (!block)
index 51b0aa2..a0002eb 100644 (file)
@@ -29,6 +29,7 @@
 #if ENABLE(DFG_JIT)
 
 #include "DFGAbstractInterpreterInlines.h"
+#include "DFGBlockSet.h"
 #include "DFGClobberSet.h"
 #include "DFGGraph.h"
 #include "DFGInPlaceAbstractState.h"
@@ -75,17 +76,10 @@ public:
         
         m_state.initialize();
         
-        do {
-            m_changed = false;
-            performForwardCFA();
-        } while (m_changed);
-        
         if (m_graph.m_form != SSA) {
             if (m_verbose)
                 dataLog("   Widening state at OSR entry block.\n");
             
-            ASSERT(!m_changed);
-            
             // Widen the abstract values at the block that serves as the must-handle OSR entry.
             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
                 BasicBlock* block = m_graph.block(blockIndex);
@@ -97,41 +91,48 @@ public:
                 if (block->bytecodeBegin != m_graph.m_plan.osrEntryBytecodeIndex)
                     continue;
                 
-                if (m_verbose)
-                    dataLog("   Found must-handle block: ", *block, "\n");
-                
-                bool changed = false;
-                for (size_t i = m_graph.m_plan.mustHandleValues.size(); i--;) {
-                    int operand = m_graph.m_plan.mustHandleValues.operandForIndex(i);
-                    JSValue value = m_graph.m_plan.mustHandleValues[i];
-                    Node* node = block->variablesAtHead.operand(operand);
-                    if (!node) {
-                        if (m_verbose)
-                            dataLog("   Not live: ", VirtualRegister(operand), "\n");
-                        continue;
-                    }
-                    
-                    if (m_verbose)
-                        dataLog("   Widening ", VirtualRegister(operand), " with ", value, "\n");
+                // We record that the block needs some OSR stuff, but we don't do that yet. We want to
+                // handle OSR entry data at the right time in order to get the best compile times. If we
+                // simply injected OSR data right now, then we'd potentially cause a loop body to be
+                // interpreted with just the constants we feed it, which is more expensive than if we
+                // interpreted it with non-constant values. If we always injected this data after the
+                // main pass of CFA ran, then we would potentially spend a bunch of time rerunning CFA
+                // after convergence. So, we try very hard to inject OSR data for a block when we first
+                // naturally come to see it - see the m_blocksWithOSR check in performBlockCFA(). This
+                // way, we:
+                //
+                // - Reduce the likelihood of interpreting the block with constants, since we will inject
+                //   the OSR entry constants on top of whatever abstract values we got for that block on
+                //   the first pass. The mix of those two things is likely to not be constant.
+                //
+                // - Reduce the total number of CFA reexecutions since we inject the OSR data as part of
+                //   the normal flow of CFA instead of having to do a second fixpoint. We may still have
+                //   to do a second fixpoint if we don't even reach the OSR entry block during the main
+                //   run of CFA, but in that case at least we're not being redundant.
+                m_blocksWithOSR.add(block);
+            }
+        }
 
-                    AbstractValue& target = block->valuesAtHead.operand(operand);
-                    changed |= target.mergeOSREntryValue(m_graph, value);
-                    target.fixTypeForRepresentation(
-                        m_graph, resultFor(node->variableAccessData()->flushFormat()));
-                }
+        do {
+            m_changed = false;
+            performForwardCFA();
+        } while (m_changed);
+        
+        if (m_graph.m_form != SSA) {
+            for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+                BasicBlock* block = m_graph.block(blockIndex);
+                if (!block)
+                    continue;
                 
-                if (changed || !block->cfaHasVisited) {
-                    m_changed = true;
-                    block->cfaShouldRevisit = true;
-                }
+                if (m_blocksWithOSR.remove(block))
+                    m_changed |= injectOSR(block);
             }
-
-            // Propagate any of the changes we just introduced.
+            
             while (m_changed) {
                 m_changed = false;
                 performForwardCFA();
             }
-            
+        
             // Make sure we record the intersection of all proofs that we ever allowed the
             // compiler to rely upon.
             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
@@ -149,6 +150,39 @@ public:
     }
     
 private:
+    bool injectOSR(BasicBlock* block)
+    {
+        if (m_verbose)
+            dataLog("   Found must-handle block: ", *block, "\n");
+        
+        bool changed = false;
+        for (size_t i = m_graph.m_plan.mustHandleValues.size(); i--;) {
+            int operand = m_graph.m_plan.mustHandleValues.operandForIndex(i);
+            JSValue value = m_graph.m_plan.mustHandleValues[i];
+            Node* node = block->variablesAtHead.operand(operand);
+            if (!node) {
+                if (m_verbose)
+                    dataLog("   Not live: ", VirtualRegister(operand), "\n");
+                continue;
+            }
+            
+            if (m_verbose)
+                dataLog("   Widening ", VirtualRegister(operand), " with ", value, "\n");
+            
+            AbstractValue& target = block->valuesAtHead.operand(operand);
+            changed |= target.mergeOSREntryValue(m_graph, value);
+            target.fixTypeForRepresentation(
+                m_graph, resultFor(node->variableAccessData()->flushFormat()));
+        }
+        
+        if (changed || !block->cfaHasVisited) {
+            block->cfaShouldRevisit = true;
+            return true;
+        }
+        
+        return false;
+    }
+    
     void performBlockCFA(BasicBlock* block)
     {
         if (!block)
@@ -157,6 +191,10 @@ private:
             return;
         if (m_verbose)
             dataLog("   Block ", *block, ":\n");
+        
+        if (m_blocksWithOSR.remove(block))
+            injectOSR(block);
+        
         m_state.beginBasicBlock(block);
         if (m_verbose) {
             dataLog("      head vars: ", block->valuesAtHead, "\n");
@@ -212,6 +250,7 @@ private:
 private:
     InPlaceAbstractState m_state;
     AbstractInterpreter<InPlaceAbstractState> m_interpreter;
+    BlockSet m_blocksWithOSR;
     
     bool m_verbose;