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/bytecode/ValueProfile.h

    r94559 r94629  
    118118        return result;
    119119    }
     120   
     121    unsigned numberOfBooleans() const
     122    {
     123        unsigned result = 0;
     124        for (unsigned i = 0; i < numberOfBuckets; ++i) {
     125            if (!!buckets[i] && JSValue::decode(buckets[i]).isBoolean())
     126                result++;
     127        }
     128        return result;
     129    }
    120130       
    121131    // These methods are not particularly optimized, in that they will each
    … …  
    143153        return computeProbability(numberOfArrays(), numberOfSamples());
    144154    }
     155   
     156    unsigned probabilityOfBoolean() const
     157    {
     158        return computeProbability(numberOfBooleans(), numberOfSamples());
     159    }
    145160
    146161#ifndef NDEBUG
    … …  
    148163    {
    149164        fprintf(out,
    150                 "samples = %u, int32 = %u, double = %u, cell = %u, array = %u",
     165                "samples = %u, int32 = %u (%u), double = %u (%u), cell = %u (%u), array = %u (%u), boolean = %u (%u)",
    151166                numberOfSamples(),
    152                 numberOfInt32s(),
    153                 numberOfDoubles(),
    154                 numberOfCells(),
    155                 numberOfArrays());
     167                probabilityOfInt32(), numberOfInt32s(),
     168                probabilityOfDouble(), numberOfDoubles(),
     169                probabilityOfCell(), numberOfCells(),
     170                probabilityOfArray(), numberOfArrays(),
     171                probabilityOfBoolean(), numberOfBooleans());
    156172        bool first = true;
    157173        for (unsigned i = 0; i < numberOfBuckets; ++i) {
    … …  
    179195        unsigned cells;
    180196        unsigned arrays;
     197        unsigned booleans;
    181198    };
    182199
    … …  
    184201    void computeStatistics(JSGlobalData& globalData, Statistics& statistics) const
    185202    {
    186         unsigned samples = 0;
    187         unsigned int32s  = 0;
    188         unsigned doubles = 0;
    189         unsigned cells   = 0;
    190         unsigned arrays  = 0;
     203        unsigned samples  = 0;
     204        unsigned int32s   = 0;
     205        unsigned doubles  = 0;
     206        unsigned cells    = 0;
     207        unsigned arrays   = 0;
     208        unsigned booleans = 0;
    191209       
    192210        for (unsigned i = 0; i < numberOfBuckets; ++i) {
    … …  
    214232                if (isJSArray(&globalData, value.asCell()))
    215233                    arrays++;
    216             }
    217         }
    218        
    219         statistics.samples = samples;
    220         statistics.int32s  = int32s;
    221         statistics.doubles = doubles;
    222         statistics.cells   = cells;
    223         statistics.arrays  = arrays;
     234            } else if (value.isBoolean())
     235                booleans++;
     236        }
     237       
     238        statistics.samples  = samples;
     239        statistics.int32s   = int32s;
     240        statistics.doubles  = doubles;
     241        statistics.cells    = cells;
     242        statistics.arrays   = arrays;
     243        statistics.booleans = booleans;
    224244    }
    225245   
Note: See TracChangeset for help on using the changeset viewer.