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):
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@117646 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/JavaScriptCore/dfg/DFGAbstractState.cpp b/Source/JavaScriptCore/dfg/DFGAbstractState.cpp
index 86b2b4f..1e2ed5a 100644
--- a/Source/JavaScriptCore/dfg/DFGAbstractState.cpp
+++ b/Source/JavaScriptCore/dfg/DFGAbstractState.cpp
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2011 Apple Inc. All rights reserved.
+ * Copyright (C) 2011, 2012 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -99,6 +99,8 @@
PROFILE(FLAG_FOR_BLOCK_INITIALIZATION);
BasicBlock* root = graph.m_blocks[0].get();
root->cfaShouldRevisit = true;
+ root->cfaHasVisited = false;
+ root->cfaFoundConstants = false;
for (size_t i = 0; i < root->valuesAtHead.numberOfArguments(); ++i) {
Node& node = graph[root->variablesAtHead.argument(i)];
ASSERT(node.op() == SetArgument);
@@ -141,11 +143,33 @@
root->valuesAtHead.argument(i).set(PredictFloat64Array);
else
root->valuesAtHead.argument(i).makeTop();
+
+ root->valuesAtTail.argument(i).clear();
}
for (size_t i = 0; i < root->valuesAtHead.numberOfLocals(); ++i) {
- if (!graph.localIsCaptured(i))
+ if (graph.localIsCaptured(i))
+ root->valuesAtHead.local(i).makeTop();
+ else
+ root->valuesAtHead.local(i).clear();
+ root->valuesAtTail.local(i).clear();
+ }
+ for (BlockIndex blockIndex = 1 ; blockIndex < graph.m_blocks.size(); ++blockIndex) {
+ BasicBlock* block = graph.m_blocks[blockIndex].get();
+ if (!block)
continue;
- root->valuesAtHead.local(i).makeTop();
+ if (!block->isReachable)
+ continue;
+ block->cfaShouldRevisit = false;
+ block->cfaHasVisited = false;
+ block->cfaFoundConstants = false;
+ for (size_t i = 0; i < block->valuesAtHead.numberOfArguments(); ++i) {
+ block->valuesAtHead.argument(i).clear();
+ block->valuesAtTail.argument(i).clear();
+ }
+ for (size_t i = 0; i < block->valuesAtHead.numberOfLocals(); ++i) {
+ block->valuesAtHead.local(i).clear();
+ block->valuesAtTail.local(i).clear();
+ }
}
}
@@ -543,8 +567,6 @@
forNode(node.child1()).filter(PredictInt32);
else if (child.shouldSpeculateNumber())
forNode(node.child1()).filter(PredictNumber);
- else
- clobberStructures(indexInBlock);
forNode(nodeIndex).set(PredictBoolean);
break;
}
@@ -1276,7 +1298,9 @@
// The block transfers the value from head to tail.
source = inVariable;
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
- dataLog(" Transfering from head to tail.\n");
+ dataLog(" Transfering ");
+ source.dump(WTF::dataFile());
+ dataLog(" from head to tail.\n");
#endif
break;
@@ -1284,7 +1308,9 @@
// The block refines the value with additional speculations.
source = forNode(nodeIndex);
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
- dataLog(" Refining.\n");
+ dataLog(" Refining to ");
+ source.dump(WTF::dataFile());
+ dataLog("\n");
#endif
break;
@@ -1296,7 +1322,9 @@
else
source = forNode(node.child1());
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
- dataLog(" Setting.\n");
+ dataLog(" Setting to ");
+ source.dump(WTF::dataFile());
+ dataLog("\n");
#endif
break;
@@ -1372,12 +1400,25 @@
ASSERT(terminal.isTerminal());
switch (terminal.op()) {
- case Jump:
+ case Jump: {
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+ dataLog(" Merging to block #%u.\n", terminal.takenBlockIndex());
+#endif
return merge(basicBlock, graph.m_blocks[terminal.takenBlockIndex()].get());
+ }
- case Branch:
- return merge(basicBlock, graph.m_blocks[terminal.takenBlockIndex()].get())
- | merge(basicBlock, graph.m_blocks[terminal.notTakenBlockIndex()].get());
+ case Branch: {
+ bool changed = false;
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+ dataLog(" Merging to block #%u.\n", terminal.takenBlockIndex());
+#endif
+ changed |= merge(basicBlock, graph.m_blocks[terminal.takenBlockIndex()].get());
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+ dataLog(" Merging to block #%u.\n", terminal.notTakenBlockIndex());
+#endif
+ changed |= merge(basicBlock, graph.m_blocks[terminal.notTakenBlockIndex()].get());
+ return changed;
+ }
case Return:
case Throw:
