Ignore:
Timestamp:
May 18, 2012, 3:30:24 PM (13 years ago)
Author:
[email protected]
Message:

DFG should have control flow graph simplification
​https://bugs.webkit.org/show_bug.cgi?id=84553

Source/JavaScriptCore:

Reviewed by Oliver Hunt.

Merged r115512 from dfgopt.

This change gives the DFG the ability to simplify the control flow graph
as part of an optimization fixpoint that includes CSE, CFA, and constant
folding. This required a number of interesting changes including:

  • Solidifying the set of invariants that the DFG obeys. For example, the head and tail of each basic block must advertise the set of live locals and the set of available locals, respectively. It must do so by referring to the first access to the local in the block (for head) and the last one (for tail). This patch introduces the start of a validation step that may be turned on even with asserts disabled. To ensure that these invariants are preserved, I had to remove the redundant phi elimination phase. For now I just remove the call, but in the future we will probably remove it entirely unless we find a use for it.


  • Making it easier to get the boolean version of a JSValue. This is a pure operation, but we previously did not treat it as such.


  • Fixing the merging and filtering of AbstractValues that correspond to concrete JSValues. This was previously broken and was limiting the effect of running constant folding. Fixing this meant that I had to change how constant folding eliminates GetLocal nodes, so as to ensure that the resulting graph still obeys DFG rules.


  • Introducing simplified getters for some of the things that DFG phases want to know about, like the Nth child of a node (now just graph.child(...) if you don't care about performance too much) or getting successors of a basic block.


The current CFG simplifier can handle almost all of the cases that it
ought to handle; the noteworthy one that is not yet handled is removing
basic blocks that just have jumps. To do this right we need to be able
to remove jump-only blocks that also perform keep-alive on some values.
To make this work, we need to be able to hoist the keep-alive into (or
just above) a Branch. This is not fundamentally difficult but I opted to
let this patch omit this optimization. We can handle this later.

This is a big win on programs that include inline functions that are
often called with constant arguments. Of course, SunSpider, V8, and
Kraken don't count. Those benchmarks are completely neutral with this
change.

  • API/JSValueRef.cpp:

(JSValueToBoolean):

  • CMakeLists.txt:
  • GNUmakefile.list.am:
  • JavaScriptCore.xcodeproj/project.pbxproj:
  • Target.pri:
  • bytecode/CodeBlock.h:

(JSC::CodeBlock::dfgOSREntryDataForBytecodeIndex):

  • bytecode/Operands.h:

(JSC::Operands::setOperandFirstTime):
(Operands):

  • dfg/DFGAbstractState.cpp:

(JSC::DFG::AbstractState::initialize):
(JSC::DFG::AbstractState::execute):
(JSC::DFG::AbstractState::mergeStateAtTail):
(JSC::DFG::AbstractState::mergeToSuccessors):

  • dfg/DFGAbstractValue.h:

(JSC::DFG::AbstractValue::isClear):
(JSC::DFG::AbstractValue::operator!=):
(JSC::DFG::AbstractValue::merge):
(JSC::DFG::AbstractValue::filter):
(JSC::DFG::AbstractValue::validateIgnoringValue):
(AbstractValue):

  • dfg/DFGAdjacencyList.h:

(JSC::DFG::AdjacencyList::child):
(JSC::DFG::AdjacencyList::setChild):
(AdjacencyList):

  • dfg/DFGBasicBlock.h:

(JSC::DFG::BasicBlock::~BasicBlock):
(BasicBlock):
(JSC::DFG::BasicBlock::numNodes):
(JSC::DFG::BasicBlock::nodeIndex):
(JSC::DFG::BasicBlock::isPhiIndex):
(JSC::DFG::BasicBlock::isInPhis):
(JSC::DFG::BasicBlock::isInBlock):

  • dfg/DFGByteCodeParser.cpp:

(ByteCodeParser):
(DFG):
(JSC::DFG::ByteCodeParser::parse):

  • dfg/DFGCFAPhase.cpp:

(JSC::DFG::CFAPhase::run):
(JSC::DFG::CFAPhase::performBlockCFA):
(JSC::DFG::performCFA):

  • dfg/DFGCFAPhase.h:

(DFG):

  • dfg/DFGCFGSimplificationPhase.cpp: Added.

(DFG):
(CFGSimplificationPhase):
(JSC::DFG::CFGSimplificationPhase::CFGSimplificationPhase):
(JSC::DFG::CFGSimplificationPhase::run):
(JSC::DFG::CFGSimplificationPhase::killUnreachable):
(JSC::DFG::CFGSimplificationPhase::findOperandSource):
(JSC::DFG::CFGSimplificationPhase::keepOperandAlive):
(JSC::DFG::CFGSimplificationPhase::fixPossibleGetLocal):
(JSC::DFG::CFGSimplificationPhase::jettisonBlock):
(JSC::DFG::CFGSimplificationPhase::fixPhis):
(JSC::DFG::CFGSimplificationPhase::fixJettisonedPredecessors):
(JSC::DFG::CFGSimplificationPhase::removePotentiallyDeadPhiReference):
(JSC::DFG::CFGSimplificationPhase::OperandSubstitution::OperandSubstitution):
(OperandSubstitution):
(JSC::DFG::CFGSimplificationPhase::OperandSubstitution::dump):
(JSC::DFG::CFGSimplificationPhase::skipGetLocal):
(JSC::DFG::CFGSimplificationPhase::fixTailOperand):
(JSC::DFG::CFGSimplificationPhase::mergeBlocks):
(JSC::DFG::performCFGSimplification):

  • dfg/DFGCFGSimplificationPhase.h: Added.

(DFG):

  • dfg/DFGCSEPhase.cpp:

(JSC::DFG::CSEPhase::run):
(CSEPhase):
(JSC::DFG::CSEPhase::impureCSE):
(JSC::DFG::CSEPhase::globalVarLoadElimination):
(JSC::DFG::CSEPhase::getByValLoadElimination):
(JSC::DFG::CSEPhase::checkStructureLoadElimination):
(JSC::DFG::CSEPhase::getByOffsetLoadElimination):
(JSC::DFG::CSEPhase::getPropertyStorageLoadElimination):
(JSC::DFG::CSEPhase::getIndexedPropertyStorageLoadElimination):
(JSC::DFG::CSEPhase::performNodeCSE):
(JSC::DFG::CSEPhase::performBlockCSE):
(JSC::DFG::performCSE):

  • dfg/DFGCSEPhase.h:

(DFG):

  • dfg/DFGCommon.h:
  • dfg/DFGConstantFoldingPhase.cpp:

(JSC::DFG::ConstantFoldingPhase::run):
(JSC::DFG::performConstantFolding):

  • dfg/DFGConstantFoldingPhase.h:

(DFG):

  • dfg/DFGDriver.cpp:

(JSC::DFG::compile):

  • dfg/DFGEdge.h:

(Edge):
(JSC::DFG::Edge::operator UnspecifiedBoolType*):

  • dfg/DFGFixupPhase.cpp:

(JSC::DFG::FixupPhase::run):
(JSC::DFG::FixupPhase::fixupBlock):
(JSC::DFG::performFixup):

  • dfg/DFGFixupPhase.h:

(DFG):

  • dfg/DFGGraph.cpp:

(JSC::DFG::Graph::dump):
(JSC::DFG::Graph::handleSuccessor):
(DFG):
(JSC::DFG::Graph::determineReachability):
(JSC::DFG::Graph::resetReachability):

  • dfg/DFGGraph.h:

(JSC::DFG::Graph::deref):
(JSC::DFG::Graph::changeIndex):
(Graph):
(JSC::DFG::Graph::changeEdge):
(JSC::DFG::Graph::numSuccessors):
(JSC::DFG::Graph::successor):
(JSC::DFG::Graph::successorForCondition):
(JSC::DFG::Graph::isPredictedNumerical):
(JSC::DFG::Graph::byValIsPure):
(JSC::DFG::Graph::clobbersWorld):
(JSC::DFG::Graph::numChildren):
(JSC::DFG::Graph::child):

  • dfg/DFGNode.h:

(JSC::DFG::Node::convertToConstant):
(JSC::DFG::Node::numSuccessors):
(Node):
(JSC::DFG::Node::successor):
(JSC::DFG::Node::successorForCondition):

  • dfg/DFGNodeType.h:

(DFG):

  • dfg/DFGOSREntry.cpp:

(JSC::DFG::prepareOSREntry):

  • dfg/DFGOperations.cpp:
  • dfg/DFGPhase.cpp:

(JSC::DFG::Phase::endPhase):

  • dfg/DFGPhase.h:

(JSC::DFG::runPhase):

  • dfg/DFGPredictionPropagationPhase.cpp:

(JSC::DFG::PredictionPropagationPhase::run):
(JSC::DFG::performPredictionPropagation):

  • dfg/DFGPredictionPropagationPhase.h:

(DFG):

  • dfg/DFGRedundantPhiEliminationPhase.cpp:

(JSC::DFG::RedundantPhiEliminationPhase::run):
(JSC::DFG::performRedundantPhiElimination):

  • dfg/DFGRedundantPhiEliminationPhase.h:

(DFG):

  • dfg/DFGScoreBoard.h:

(JSC::DFG::ScoreBoard::use):
(ScoreBoard):
(JSC::DFG::ScoreBoard::useIfHasResult):

  • dfg/DFGSpeculativeJIT.cpp:

(JSC::DFG::SpeculativeJIT::compilePeepHoleObjectEquality):
(JSC::DFG::SpeculativeJIT::compilePeepHoleIntegerBranch):
(JSC::DFG::SpeculativeJIT::compile):
(JSC::DFG::SpeculativeJIT::createOSREntries):
(JSC::DFG::SpeculativeJIT::linkOSREntries):
(JSC::DFG::SpeculativeJIT::compileStrictEqForConstant):
(JSC::DFG::SpeculativeJIT::compileRegExpExec):

  • dfg/DFGSpeculativeJIT.h:

(JSC::DFG::SpeculativeJIT::nextBlock):
(SpeculativeJIT):
(JSC::DFG::SpeculativeJIT::use):
(JSC::DFG::SpeculativeJIT::jump):

  • dfg/DFGSpeculativeJIT32_64.cpp:

(JSC::DFG::SpeculativeJIT::nonSpeculativePeepholeBranchNull):
(JSC::DFG::SpeculativeJIT::nonSpeculativePeepholeBranch):
(JSC::DFG::SpeculativeJIT::nonSpeculativePeepholeStrictEq):
(JSC::DFG::SpeculativeJIT::emitBranch):
(JSC::DFG::SpeculativeJIT::compile):

  • dfg/DFGSpeculativeJIT64.cpp:

(JSC::DFG::SpeculativeJIT::nonSpeculativePeepholeBranchNull):
(JSC::DFG::SpeculativeJIT::nonSpeculativePeepholeBranch):
(JSC::DFG::SpeculativeJIT::nonSpeculativePeepholeStrictEq):
(JSC::DFG::SpeculativeJIT::emitBranch):
(JSC::DFG::SpeculativeJIT::compile):

  • dfg/DFGValidate.cpp: Added.

(DFG):
(Validate):
(JSC::DFG::Validate::Validate):
(JSC::DFG::Validate::validate):
(JSC::DFG::Validate::reportValidationContext):
(JSC::DFG::Validate::dumpData):
(JSC::DFG::Validate::dumpGraphIfAppropriate):
(JSC::DFG::validate):

  • dfg/DFGValidate.h: Added.

(DFG):
(JSC::DFG::validate):

  • dfg/DFGVirtualRegisterAllocationPhase.cpp:

(JSC::DFG::VirtualRegisterAllocationPhase::run):
(JSC::DFG::performVirtualRegisterAllocation):

  • dfg/DFGVirtualRegisterAllocationPhase.h:

(DFG):

  • interpreter/Interpreter.cpp:

(JSC::Interpreter::privateExecute):

  • jit/JITStubs.cpp:

(JSC::DEFINE_STUB_FUNCTION):

  • llint/LLIntSlowPaths.cpp:

(JSC::LLInt::LLINT_SLOW_PATH_DECL):

  • runtime/ArrayPrototype.cpp:

(JSC::arrayProtoFuncFilter):
(JSC::arrayProtoFuncEvery):
(JSC::arrayProtoFuncSome):

  • runtime/BooleanConstructor.cpp:

(JSC::constructBoolean):
(JSC::callBooleanConstructor):

  • runtime/JSCell.h:

(JSCell):

  • runtime/JSObject.cpp:

(JSC):

  • runtime/JSObject.h:
  • runtime/JSString.cpp:

(JSC::JSString::toBoolean):

  • runtime/JSString.h:

(JSString):
(JSC::JSCell::toBoolean):
(JSC::JSValue::toBoolean):

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

(JSC::toPropertyDescriptor):

  • runtime/RegExpConstructor.cpp:

(JSC::setRegExpConstructorMultiline):

  • runtime/RegExpPrototype.cpp:

(JSC::regExpProtoFuncToString):

Source/WebCore:

Reviewed by Oliver Hunt.

Merged r115512 from dfgopt.

JSValue::toBoolean(ExecState*) -> JSValue::toBoolean()

No new tests, because no new behavior.

  • bindings/js/JSCustomSQLStatementErrorCallback.cpp:

(WebCore::JSSQLStatementErrorCallback::handleEvent):

  • bindings/js/JSDOMWindowCustom.cpp:

(WebCore::JSDOMWindow::addEventListener):
(WebCore::JSDOMWindow::removeEventListener):

  • bindings/js/JSDataViewCustom.cpp:

(WebCore::getDataViewMember):

  • bindings/js/JSDeviceMotionEventCustom.cpp:

(WebCore::JSDeviceMotionEvent::initDeviceMotionEvent):

  • bindings/js/JSDeviceOrientationEventCustom.cpp:

(WebCore::JSDeviceOrientationEvent::initDeviceOrientationEvent):

  • bindings/js/JSDictionary.cpp:

(WebCore::JSDictionary::convertValue):

  • bindings/js/JSDirectoryEntryCustom.cpp:

(WebCore::JSDirectoryEntry::getFile):
(WebCore::JSDirectoryEntry::getDirectory):

  • bindings/js/JSDirectoryEntrySyncCustom.cpp:

(WebCore::getFlags):

  • bindings/js/JSHTMLCanvasElementCustom.cpp:

(WebCore::JSHTMLCanvasElement::getContext):

  • bindings/js/JSInspectorFrontendHostCustom.cpp:

(WebCore::JSInspectorFrontendHost::showContextMenu):

  • bindings/js/JSMessageEventCustom.cpp:

(WebCore::handleInitMessageEvent):

  • bindings/js/JSWebGLRenderingContextCustom.cpp:

(WebCore::dataFunctionMatrix):

  • bindings/js/JSXMLHttpRequestCustom.cpp:

(WebCore::JSXMLHttpRequest::open):

  • bindings/js/ScriptDebugServer.cpp:

(WebCore::ScriptDebugServer::hasBreakpoint):

  • bindings/scripts/CodeGeneratorJS.pm:

(GenerateEventListenerCall):
(GenerateImplementation):
(JSValueToNative):

  • bridge/c/c_utility.cpp:

(JSC::Bindings::convertValueToNPVariant):

  • bridge/jni/jni_jsobject.mm:

(JavaJSObject::convertValueToJObject):

Source/WebKit/mac:

Reviewed by Oliver Hunt.

Merged r115512 from dfgopt.

JSValue::toBoolean(ExecState*) -> JSValue::toBoolean()

  • Plugins/Hosted/NetscapePluginInstanceProxy.mm:

(WebKit::NetscapePluginInstanceProxy::addValueToArray):

Source/WebKit2:

Reviewed by Oliver Hunt.

Merged r115512 from dfgopt.

JSValue::toBoolean(ExecState*) -> JSValue::toBoolean()

  • WebProcess/Plugins/Netscape/NPRuntimeObjectMap.cpp:

(WebKit::NPRuntimeObjectMap::convertJSValueToNPVariant):

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/interpreter/Interpreter.cpp

    r117193 r117646  
    26212621        int dst = vPC[1].u.operand;
    26222622        int src = vPC[2].u.operand;
    2623         JSValue result = jsBoolean(!callFrame->r(src).jsValue().toBoolean(callFrame));
     2623        JSValue result = jsBoolean(!callFrame->r(src).jsValue().toBoolean());
    26242624        CHECK_FOR_EXCEPTION();
    26252625        callFrame->uncheckedR(dst) = result;
    … …  
    39303930        int cond = vPC[1].u.operand;
    39313931        int target = vPC[2].u.operand;
    3932         if (callFrame->r(cond).jsValue().toBoolean(callFrame)) {
     3932        if (callFrame->r(cond).jsValue().toBoolean()) {
    39333933            vPC += target;
    39343934            CHECK_FOR_TIMEOUT();
    … …  
    39503950        int cond = vPC[1].u.operand;
    39513951        int target = vPC[2].u.operand;
    3952         if (!callFrame->r(cond).jsValue().toBoolean(callFrame)) {
     3952        if (!callFrame->r(cond).jsValue().toBoolean()) {
    39533953            vPC += target;
    39543954            CHECK_FOR_TIMEOUT();
    … …  
    39673967        int cond = vPC[1].u.operand;
    39683968        int target = vPC[2].u.operand;
    3969         if (callFrame->r(cond).jsValue().toBoolean(callFrame)) {
     3969        if (callFrame->r(cond).jsValue().toBoolean()) {
    39703970            vPC += target;
    39713971            NEXT_INSTRUCTION();
    … …  
    39833983        int cond = vPC[1].u.operand;
    39843984        int target = vPC[2].u.operand;
    3985         if (!callFrame->r(cond).jsValue().toBoolean(callFrame)) {
     3985        if (!callFrame->r(cond).jsValue().toBoolean()) {
    39863986            vPC += target;
    39873987            NEXT_INSTRUCTION();
Note: See TracChangeset for help on using the changeset viewer.