Ignore:
Timestamp:
Sep 6, 2011, 7:47:51 PM (14 years ago)
Author:
[email protected]
Message:

DFG JIT does not optimize booleans
​https://bugs.webkit.org/show_bug.cgi?id=67670

Reviewed by Gavin Barraclough.

This adds boolean value profiling, boolean prediction in the DFG,
boolean forward flow propagation in the DFGPropagator, boolean
data format in DFG generation info, and comprehensive optimizations
based on both boolean prediction and boolean generation info.
This is brings the speed-up on v8-richards to 12%, and gives slight
speed-ups elsewhere as well.

Making this work right required navigating some subtleties in
value profiling. Some functions get compiled with insufficient
information because some important path of the function never
executed. In these cases, we wish to fall back on static
speculation. But to do so, we need to ensure that predictions that
are inherent in the code (like that GetById almost certainly takes
a cell operand) are reflected in predictions that we make in
DFGPropagator. Thus, DFGPropagator now does both backward and
forward flow, using a both forward and backward fixpoint.

The backward flow in DFGPropagator is a separate static analysis,
and needs to keep a set of backward flow abstract values for
variables, arguments, and globals. To make this easy, this patch
factors out DFGGraph's prediction tracking capability into
DFGPredictionTracker, which now gets used by both DFGGraph (for
forward flow predictions) and DFGPropagator (for backward flow
predictions). Backward flow predictions eventually get merged
into forward flow ones, but the two are not equivalent: a forward
flow prediction is a superset of the backward flow prediction.

Debugging these prediction issues required a better understanding
of where we fail speculation, and what our value predictions look
like. This patch also adds optional verbose speculation failure
(so an informative printf fires whenever speculation failure occurs)
and slight improvements to the verbosity in other places.

  • bytecode/ValueProfile.h:

(JSC::ValueProfile::numberOfBooleans):
(JSC::ValueProfile::probabilityOfBoolean):
(JSC::ValueProfile::dump):
(JSC::ValueProfile::computeStatistics):

  • dfg/DFGByteCodeParser.cpp:

(JSC::DFG::ByteCodeParser::stronglyPredict):
(JSC::DFG::ByteCodeParser::parseBlock):

  • dfg/DFGGenerationInfo.h:

(JSC::DFG::dataFormatToString):
(JSC::DFG::needDataFormatConversion):

  • dfg/DFGGraph.cpp:

(JSC::DFG::Graph::dump):
(JSC::DFG::Graph::predictArgumentTypes):

  • dfg/DFGGraph.h:

(JSC::DFG::Graph::Graph):
(JSC::DFG::Graph::predictions):
(JSC::DFG::Graph::predict):
(JSC::DFG::Graph::predictGlobalVar):
(JSC::DFG::Graph::getPrediction):
(JSC::DFG::Graph::getGlobalVarPrediction):
(JSC::DFG::Graph::isBooleanConstant):
(JSC::DFG::Graph::valueOfBooleanConstant):

  • dfg/DFGJITCodeGenerator.cpp:

(JSC::DFG::JITCodeGenerator::fillInteger):
(JSC::DFG::JITCodeGenerator::fillDouble):
(JSC::DFG::JITCodeGenerator::fillJSValue):
(JSC::DFG::JITCodeGenerator::isKnownNotInteger):
(JSC::DFG::JITCodeGenerator::isKnownBoolean):
(JSC::DFG::JITCodeGenerator::nonSpeculativeNonPeepholeCompareNull):
(JSC::DFG::JITCodeGenerator::nonSpeculativeNonPeepholeCompare):
(JSC::DFG::JITCodeGenerator::nonSpeculativeNonPeepholeStrictEq):
(JSC::DFG::JITCodeGenerator::emitBranch):
(JSC::DFG::JITCodeGenerator::speculationCheck):
(JSC::DFG::GPRTemporary::GPRTemporary):

  • dfg/DFGJITCodeGenerator.h:

(JSC::DFG::JITCodeGenerator::isBooleanConstant):
(JSC::DFG::JITCodeGenerator::valueOfBooleanConstant):

  • dfg/DFGJITCompiler.cpp:

(JSC::DFG::JITCompiler::jumpFromSpeculativeToNonSpeculative):
(JSC::DFG::JITCompiler::link):

  • dfg/DFGJITCompiler.h:

(JSC::DFG::JITCompiler::debugCall):
(JSC::DFG::JITCompiler::isBooleanConstant):
(JSC::DFG::JITCompiler::valueOfBooleanConstant):

  • dfg/DFGNode.h:

(JSC::DFG::isBooleanPrediction):
(JSC::DFG::predictionToString):
(JSC::DFG::mergePredictions):
(JSC::DFG::makePrediction):
(JSC::DFG::Node::isBooleanConstant):
(JSC::DFG::Node::valueOfBooleanConstant):
(JSC::DFG::Node::hasBooleanResult):
(JSC::DFG::Node::hasNumericResult):
(JSC::DFG::Node::predict):

  • dfg/DFGOperations.cpp:
  • dfg/DFGOperations.h:
  • dfg/DFGPredictionTracker.h: Added.

(JSC::DFG::operandIsArgument):
(JSC::DFG::PredictionSlot::PredictionSlot):
(JSC::DFG::PredictionTracker::PredictionTracker):
(JSC::DFG::PredictionTracker::initializeSimilarTo):
(JSC::DFG::PredictionTracker::numberOfArguments):
(JSC::DFG::PredictionTracker::numberOfVariables):
(JSC::DFG::PredictionTracker::argumentIndexForOperand):
(JSC::DFG::PredictionTracker::predictArgument):
(JSC::DFG::PredictionTracker::predict):
(JSC::DFG::PredictionTracker::predictGlobalVar):
(JSC::DFG::PredictionTracker::getArgumentPrediction):
(JSC::DFG::PredictionTracker::getPrediction):
(JSC::DFG::PredictionTracker::getGlobalVarPrediction):

  • dfg/DFGPropagator.cpp:

(JSC::DFG::Propagator::Propagator):
(JSC::DFG::Propagator::fixpoint):
(JSC::DFG::Propagator::setPrediction):
(JSC::DFG::Propagator::mergeUse):
(JSC::DFG::Propagator::mergePrediction):
(JSC::DFG::Propagator::propagateNode):

  • dfg/DFGSpeculativeJIT.cpp:

(JSC::DFG::SpeculativeJIT::fillSpeculateIntInternal):
(JSC::DFG::SpeculativeJIT::fillSpeculateDouble):
(JSC::DFG::SpeculativeJIT::fillSpeculateCell):
(JSC::DFG::SpeculativeJIT::fillSpeculateBoolean):
(JSC::DFG::SpeculativeJIT::compare):
(JSC::DFG::SpeculativeJIT::compile):

  • dfg/DFGSpeculativeJIT.h:

(JSC::DFG::SpeculateBooleanOperand::SpeculateBooleanOperand):
(JSC::DFG::SpeculateBooleanOperand::~SpeculateBooleanOperand):
(JSC::DFG::SpeculateBooleanOperand::index):
(JSC::DFG::SpeculateBooleanOperand::gpr):
(JSC::DFG::SpeculateBooleanOperand::use):

  • runtime/JSGlobalData.h:
  • runtime/JSValue.cpp:

(JSC::JSValue::description):

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r94627 r94629  
     12011-09-06  Filip Pizlo  <[email protected]>
     2
     3        DFG JIT does not optimize booleans
     4        https://bugs.webkit.org/show_bug.cgi?id=67670
     5
     6        Reviewed by Gavin Barraclough.
     7       
     8        This adds boolean value profiling, boolean prediction in the DFG,
     9        boolean forward flow propagation in the DFGPropagator, boolean
     10        data format in DFG generation info, and comprehensive optimizations
     11        based on both boolean prediction and boolean generation info.
     12        This is brings the speed-up on v8-richards to 12%, and gives slight
     13        speed-ups elsewhere as well.
     14       
     15        Making this work right required navigating some subtleties in
     16        value profiling.  Some functions get compiled with insufficient
     17        information because some important path of the function never
     18        executed.  In these cases, we wish to fall back on static
     19        speculation.  But to do so, we need to ensure that predictions that
     20        are inherent in the code (like that GetById almost certainly takes
     21        a cell operand) are reflected in predictions that we make in
     22        DFGPropagator.  Thus, DFGPropagator now does both backward and
     23        forward flow, using a both forward and backward fixpoint.
     24       
     25        The backward flow in DFGPropagator is a separate static analysis,
     26        and needs to keep a set of backward flow abstract values for
     27        variables, arguments, and globals.  To make this easy, this patch
     28        factors out DFGGraph's prediction tracking capability into
     29        DFGPredictionTracker, which now gets used by both DFGGraph (for
     30        forward flow predictions) and DFGPropagator (for backward flow
     31        predictions).  Backward flow predictions eventually get merged
     32        into forward flow ones, but the two are not equivalent: a forward
     33        flow prediction is a superset of the backward flow prediction.
     34       
     35        Debugging these prediction issues required a better understanding
     36        of where we fail speculation, and what our value predictions look
     37        like.  This patch also adds optional verbose speculation failure
     38        (so an informative printf fires whenever speculation failure occurs)
     39        and slight improvements to the verbosity in other places.
     40
     41        * bytecode/ValueProfile.h:
     42        (JSC::ValueProfile::numberOfBooleans):
     43        (JSC::ValueProfile::probabilityOfBoolean):
     44        (JSC::ValueProfile::dump):
     45        (JSC::ValueProfile::computeStatistics):
     46        * dfg/DFGByteCodeParser.cpp:
     47        (JSC::DFG::ByteCodeParser::stronglyPredict):
     48        (JSC::DFG::ByteCodeParser::parseBlock):
     49        * dfg/DFGGenerationInfo.h:
     50        (JSC::DFG::dataFormatToString):
     51        (JSC::DFG::needDataFormatConversion):
     52        * dfg/DFGGraph.cpp:
     53        (JSC::DFG::Graph::dump):
     54        (JSC::DFG::Graph::predictArgumentTypes):
     55        * dfg/DFGGraph.h:
     56        (JSC::DFG::Graph::Graph):
     57        (JSC::DFG::Graph::predictions):
     58        (JSC::DFG::Graph::predict):
     59        (JSC::DFG::Graph::predictGlobalVar):
     60        (JSC::DFG::Graph::getPrediction):
     61        (JSC::DFG::Graph::getGlobalVarPrediction):
     62        (JSC::DFG::Graph::isBooleanConstant):
     63        (JSC::DFG::Graph::valueOfBooleanConstant):
     64        * dfg/DFGJITCodeGenerator.cpp:
     65        (JSC::DFG::JITCodeGenerator::fillInteger):
     66        (JSC::DFG::JITCodeGenerator::fillDouble):
     67        (JSC::DFG::JITCodeGenerator::fillJSValue):
     68        (JSC::DFG::JITCodeGenerator::isKnownNotInteger):
     69        (JSC::DFG::JITCodeGenerator::isKnownBoolean):
     70        (JSC::DFG::JITCodeGenerator::nonSpeculativeNonPeepholeCompareNull):
     71        (JSC::DFG::JITCodeGenerator::nonSpeculativeNonPeepholeCompare):
     72        (JSC::DFG::JITCodeGenerator::nonSpeculativeNonPeepholeStrictEq):
     73        (JSC::DFG::JITCodeGenerator::emitBranch):
     74        (JSC::DFG::JITCodeGenerator::speculationCheck):
     75        (JSC::DFG::GPRTemporary::GPRTemporary):
     76        * dfg/DFGJITCodeGenerator.h:
     77        (JSC::DFG::JITCodeGenerator::isBooleanConstant):
     78        (JSC::DFG::JITCodeGenerator::valueOfBooleanConstant):
     79        * dfg/DFGJITCompiler.cpp:
     80        (JSC::DFG::JITCompiler::jumpFromSpeculativeToNonSpeculative):
     81        (JSC::DFG::JITCompiler::link):
     82        * dfg/DFGJITCompiler.h:
     83        (JSC::DFG::JITCompiler::debugCall):
     84        (JSC::DFG::JITCompiler::isBooleanConstant):
     85        (JSC::DFG::JITCompiler::valueOfBooleanConstant):
     86        * dfg/DFGNode.h:
     87        (JSC::DFG::isBooleanPrediction):
     88        (JSC::DFG::predictionToString):
     89        (JSC::DFG::mergePredictions):
     90        (JSC::DFG::makePrediction):
     91        (JSC::DFG::Node::isBooleanConstant):
     92        (JSC::DFG::Node::valueOfBooleanConstant):
     93        (JSC::DFG::Node::hasBooleanResult):
     94        (JSC::DFG::Node::hasNumericResult):
     95        (JSC::DFG::Node::predict):
     96        * dfg/DFGOperations.cpp:
     97        * dfg/DFGOperations.h:
     98        * dfg/DFGPredictionTracker.h: Added.
     99        (JSC::DFG::operandIsArgument):
     100        (JSC::DFG::PredictionSlot::PredictionSlot):
     101        (JSC::DFG::PredictionTracker::PredictionTracker):
     102        (JSC::DFG::PredictionTracker::initializeSimilarTo):
     103        (JSC::DFG::PredictionTracker::numberOfArguments):
     104        (JSC::DFG::PredictionTracker::numberOfVariables):
     105        (JSC::DFG::PredictionTracker::argumentIndexForOperand):
     106        (JSC::DFG::PredictionTracker::predictArgument):
     107        (JSC::DFG::PredictionTracker::predict):
     108        (JSC::DFG::PredictionTracker::predictGlobalVar):
     109        (JSC::DFG::PredictionTracker::getArgumentPrediction):
     110        (JSC::DFG::PredictionTracker::getPrediction):
     111        (JSC::DFG::PredictionTracker::getGlobalVarPrediction):
     112        * dfg/DFGPropagator.cpp:
     113        (JSC::DFG::Propagator::Propagator):
     114        (JSC::DFG::Propagator::fixpoint):
     115        (JSC::DFG::Propagator::setPrediction):
     116        (JSC::DFG::Propagator::mergeUse):
     117        (JSC::DFG::Propagator::mergePrediction):
     118        (JSC::DFG::Propagator::propagateNode):
     119        * dfg/DFGSpeculativeJIT.cpp:
     120        (JSC::DFG::SpeculativeJIT::fillSpeculateIntInternal):
     121        (JSC::DFG::SpeculativeJIT::fillSpeculateDouble):
     122        (JSC::DFG::SpeculativeJIT::fillSpeculateCell):
     123        (JSC::DFG::SpeculativeJIT::fillSpeculateBoolean):
     124        (JSC::DFG::SpeculativeJIT::compare):
     125        (JSC::DFG::SpeculativeJIT::compile):
     126        * dfg/DFGSpeculativeJIT.h:
     127        (JSC::DFG::SpeculateBooleanOperand::SpeculateBooleanOperand):
     128        (JSC::DFG::SpeculateBooleanOperand::~SpeculateBooleanOperand):
     129        (JSC::DFG::SpeculateBooleanOperand::index):
     130        (JSC::DFG::SpeculateBooleanOperand::gpr):
     131        (JSC::DFG::SpeculateBooleanOperand::use):
     132        * runtime/JSGlobalData.h:
     133        * runtime/JSValue.cpp:
     134        (JSC::JSValue::description):
     135
    11362011-09-06  Mark Hahnenberg  <[email protected]>
    2137
Note: See TracChangeset for help on using the changeset viewer.