Diff
Modified: branches/dfgFourthTier/LayoutTests/ChangeLog (151643 => 151644)
--- branches/dfgFourthTier/LayoutTests/ChangeLog 2013-06-17 15:26:24 UTC (rev 151643)
+++ branches/dfgFourthTier/LayoutTests/ChangeLog 2013-06-17 16:22:06 UTC (rev 151644)
@@ -1,3 +1,21 @@
+2013-06-15 Filip Pizlo <[email protected]>
+
+ fourthTier: Add CFG simplification for Switch
+ https://bugs.webkit.org/show_bug.cgi?id=117677
+
+ Reviewed by Mark Hahnenberg.
+
+ * fast/js/regress/script-tests/switch-constant.js: Added.
+ (foo):
+ (bar):
+ * fast/js/regress/script-tests/switch.js: Added.
+ (foo):
+ (bar):
+ * fast/js/regress/switch-constant-expected.txt: Added.
+ * fast/js/regress/switch-constant.html: Added.
+ * fast/js/regress/switch-expected.txt: Added.
+ * fast/js/regress/switch.html: Added.
+
2013-06-11 Filip Pizlo <[email protected]>
fourthTier: DFG should support op_in and it should use patching to make it fast
Added: branches/dfgFourthTier/LayoutTests/fast/js/regress/script-tests/switch-constant.js (0 => 151644)
--- branches/dfgFourthTier/LayoutTests/fast/js/regress/script-tests/switch-constant.js (rev 0)
+++ branches/dfgFourthTier/LayoutTests/fast/js/regress/script-tests/switch-constant.js 2013-06-17 16:22:06 UTC (rev 151644)
@@ -0,0 +1,27 @@
+function foo(o) {
+ switch (o.f) {
+ case 1: return 5;
+ case 2: return 2;
+ case 3: return 7;
+ case 4: return 9;
+ case 5: return o.f + 1;
+ case 6: return 0;
+ case 7: return 89;
+ case 8: return 23;
+ case 9: return 12;
+ case 10: return 54;
+ case 11: return 53;
+ default: return 42;
+ }
+}
+
+function bar() {
+ var result = 0;
+ for (var i = 0; i < 1000000; ++i)
+ result += foo({f:5});
+ return result;
+}
+
+var result = bar();
+if (result != 6000000)
+ throw "Error: bad result: " + result;
Added: branches/dfgFourthTier/LayoutTests/fast/js/regress/script-tests/switch.js (0 => 151644)
--- branches/dfgFourthTier/LayoutTests/fast/js/regress/script-tests/switch.js (rev 0)
+++ branches/dfgFourthTier/LayoutTests/fast/js/regress/script-tests/switch.js 2013-06-17 16:22:06 UTC (rev 151644)
@@ -0,0 +1,27 @@
+function foo(o) {
+ switch (o.f) {
+ case 1: return 5;
+ case 2: return 2;
+ case 3: return 7;
+ case 4: return 9;
+ case 5: return o.f + 1;
+ case 6: return 0;
+ case 7: return 89;
+ case 8: return 23;
+ case 9: return 12;
+ case 10: return 54;
+ case 11: return 53;
+ default: return 42;
+ }
+}
+
+function bar() {
+ var result = 0;
+ for (var i = 0; i < 1000000; ++i)
+ result ^= foo({f:i % 12});
+ return result;
+}
+
+var result = bar();
+if (result != 78)
+ throw "Error: bad result: " + result;
Added: branches/dfgFourthTier/LayoutTests/fast/js/regress/switch-constant-expected.txt (0 => 151644)
--- branches/dfgFourthTier/LayoutTests/fast/js/regress/switch-constant-expected.txt (rev 0)
+++ branches/dfgFourthTier/LayoutTests/fast/js/regress/switch-constant-expected.txt 2013-06-17 16:22:06 UTC (rev 151644)
@@ -0,0 +1,10 @@
+JSRegress/switch-constant
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
Added: branches/dfgFourthTier/LayoutTests/fast/js/regress/switch-constant.html (0 => 151644)
--- branches/dfgFourthTier/LayoutTests/fast/js/regress/switch-constant.html (rev 0)
+++ branches/dfgFourthTier/LayoutTests/fast/js/regress/switch-constant.html 2013-06-17 16:22:06 UTC (rev 151644)
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src=""
+</head>
+<body>
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+</body>
+</html>
Added: branches/dfgFourthTier/LayoutTests/fast/js/regress/switch-expected.txt (0 => 151644)
--- branches/dfgFourthTier/LayoutTests/fast/js/regress/switch-expected.txt (rev 0)
+++ branches/dfgFourthTier/LayoutTests/fast/js/regress/switch-expected.txt 2013-06-17 16:22:06 UTC (rev 151644)
@@ -0,0 +1,10 @@
+JSRegress/switch
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
Added: branches/dfgFourthTier/LayoutTests/fast/js/regress/switch.html (0 => 151644)
--- branches/dfgFourthTier/LayoutTests/fast/js/regress/switch.html (rev 0)
+++ branches/dfgFourthTier/LayoutTests/fast/js/regress/switch.html 2013-06-17 16:22:06 UTC (rev 151644)
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src=""
+</head>
+<body>
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+</body>
+</html>
Modified: branches/dfgFourthTier/Source/_javascript_Core/ChangeLog (151643 => 151644)
--- branches/dfgFourthTier/Source/_javascript_Core/ChangeLog 2013-06-17 15:26:24 UTC (rev 151643)
+++ branches/dfgFourthTier/Source/_javascript_Core/ChangeLog 2013-06-17 16:22:06 UTC (rev 151644)
@@ -1,5 +1,28 @@
2013-06-15 Filip Pizlo <[email protected]>
+ fourthTier: Add CFG simplification for Switch
+ https://bugs.webkit.org/show_bug.cgi?id=117677
+
+ Reviewed by Mark Hahnenberg.
+
+ This is for completeness. It only speeds up a microbenchmark at this point.
+ Broadly, we want all control constructs to be known to the CFG simplifier.
+
+ * dfg/DFGCFGSimplificationPhase.cpp:
+ (JSC::DFG::CFGSimplificationPhase::run):
+ (JSC::DFG::CFGSimplificationPhase::convertToJump):
+ (CFGSimplificationPhase):
+ (JSC::DFG::CFGSimplificationPhase::noBlocks):
+ (JSC::DFG::CFGSimplificationPhase::oneBlock):
+ (JSC::DFG::CFGSimplificationPhase::mergeBlocks):
+ * runtime/JSCJSValue.h:
+ (JSValue):
+ * runtime/JSCJSValueInlines.h:
+ (JSC::JSValue::pureStrictEqual):
+ (JSC):
+
+2013-06-15 Filip Pizlo <[email protected]>
+
Concurrent JIT shouldn't try to recompute the CodeBlockHash as part of debug dumps, since doing so may fail if dealing with a CachedScript that doesn't have its script string handy
https://bugs.webkit.org/show_bug.cgi?id=117676
Modified: branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp (151643 => 151644)
--- branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp 2013-06-17 15:26:24 UTC (rev 151643)
+++ branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp 2013-06-17 16:22:06 UTC (rev 151644)
@@ -73,7 +73,7 @@
if (extremeLogging)
m_graph.dump();
m_graph.dethread();
- mergeBlocks(blockIndex, m_graph.successor(block, 0), NoBlock);
+ mergeBlocks(blockIndex, m_graph.successor(block, 0), noBlocks());
innerChanged = outerChanged = true;
break;
} else {
@@ -118,7 +118,7 @@
mergeBlocks(
blockIndex,
m_graph.successorForCondition(block, condition),
- m_graph.successorForCondition(block, !condition));
+ oneBlock(m_graph.successorForCondition(block, !condition)));
} else {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLogF("CFGSimplify: Known condition (%s) branch->jump conversion on Block #%u to Block #%u, jettisoning Block #%u.\n",
@@ -148,48 +148,102 @@
}
if (m_graph.successor(block, 0) == m_graph.successor(block, 1)) {
- BlockIndex targetBlockIndex = m_graph.successor(block, 0);
+ convertToJump(blockIndex, m_graph.successor(block, 0));
+ innerChanged = outerChanged = true;
+ break;
+ }
+
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+ dataLogF("Not branch simplifying on Block #%u because the successors differ and the condition is not known.\n",
+ blockIndex);
+#endif
+
+ // Branch to same destination -> jump.
+ // FIXME: this will currently not be hit because of the lack of jump-only
+ // block simplification.
+
+ break;
+ }
+
+ case Switch: {
+ SwitchData* data = ""
+
+ // Prune out cases that end up jumping to default.
+ for (unsigned i = 0; i < data->cases.size(); ++i) {
+ if (data->cases[i].target == data->fallThrough)
+ data->cases[i--] = data->cases.takeLast();
+ }
+
+ // If there are no cases other than default then this turns
+ // into a jump.
+ if (data->cases.isEmpty()) {
+ convertToJump(blockIndex, data->fallThrough);
+ innerChanged = outerChanged = true;
+ break;
+ }
+
+ // Switch on constant -> jettison all other targets and merge.
+ if (block->last()->child1()->hasConstant()) {
+ JSValue value = m_graph.valueOfJSConstant(block->last()->child1().node());
+ TriState found = FalseTriState;
+ BlockIndex targetBlockIndex = NoBlock;
+ for (unsigned i = data->cases.size(); found == FalseTriState && i--;) {
+ found = JSValue::pureStrictEqual(value, data->cases[i].value);
+ if (found == TrueTriState)
+ targetBlockIndex = data->cases[i].target;
+ }
+
+ if (found == MixedTriState)
+ break;
+ if (found == FalseTriState)
+ targetBlockIndex = data->fallThrough;
+ ASSERT(targetBlockIndex != NoBlock);
+
+ Vector<BlockIndex, 1> jettisonedBlocks;
+ for (unsigned i = m_graph.numSuccessors(block); i--;) {
+ BlockIndex jettisonedBlockIndex = m_graph.successor(block, i);
+ if (jettisonedBlockIndex != targetBlockIndex)
+ jettisonedBlocks.append(jettisonedBlockIndex);
+ }
+
BasicBlock* targetBlock = m_graph.m_blocks[targetBlockIndex].get();
- ASSERT(targetBlock);
- ASSERT(targetBlock->isReachable);
+
if (targetBlock->m_predecessors.size() == 1) {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
- dataLogF("CFGSimplify: Branch to same successor merge on Block #%u to Block #%u.\n",
- blockIndex, targetBlockIndex);
+ dataLog(
+ "CFGSimplify: Known constant (", value, ") switch merge on ",
+ "Block #", blockIndex, " to Block #", targetBlockIndex,
+ ".\n");
#endif
+
+ if (extremeLogging)
+ m_graph.dump();
m_graph.dethread();
- mergeBlocks(blockIndex, targetBlockIndex, NoBlock);
+
+ mergeBlocks(blockIndex, targetBlockIndex, jettisonedBlocks);
} else {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
- dataLogF("CFGSimplify: Branch->jump conversion to same successor on Block #%u to Block #%u.\n",
- blockIndex, targetBlockIndex);
+ dataLog(
+ "CFGSimplify: Known constant (", value, ") switch->jump "
+ "conversion on Block #", blockIndex, " to Block #",
+ targetBlockIndex, ".\n");
#endif
- Node* branch = block->last();
- ASSERT(branch->isTerminal());
- ASSERT(branch->op() == Branch);
- branch->convertToPhantom();
- ASSERT(branch->refCount() == 1);
+ if (extremeLogging)
+ m_graph.dump();
+ m_graph.dethread();
+ CodeOrigin boundaryCodeOrigin = block->last()->codeOrigin;
+ block->last()->convertToPhantom();
+ for (unsigned i = jettisonedBlocks.size(); i--;)
+ jettisonBlock(blockIndex, jettisonedBlocks[i], boundaryCodeOrigin);
block->appendNode(
- m_graph, SpecNone, Jump, branch->codeOrigin,
- OpInfo(targetBlockIndex));
+ m_graph, SpecNone, Jump, boundaryCodeOrigin, OpInfo(targetBlockIndex));
}
innerChanged = outerChanged = true;
break;
}
+ }
-#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
- dataLogF("Not branch simplifying on Block #%u because the successors differ and the condition is not known.\n",
- blockIndex);
-#endif
-
- // Branch to same destination -> jump.
- // FIXME: this will currently not be hit because of the lack of jump-only
- // block simplification.
-
- break;
- }
-
default:
break;
}
@@ -247,6 +301,38 @@
}
private:
+ void convertToJump(BlockIndex blockIndex, BlockIndex targetBlockIndex)
+ {
+ BasicBlock* block = m_graph.m_blocks[blockIndex].get();
+ BasicBlock* targetBlock = m_graph.m_blocks[targetBlockIndex].get();
+ ASSERT(targetBlock);
+ ASSERT(targetBlock->isReachable);
+ if (targetBlock->m_predecessors.size() == 1) {
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+ dataLogF(
+ "CFGSimplify: Branch/Switch to same successor merge on Block #%u to Block #%u.\n",
+ blockIndex, targetBlockIndex);
+#endif
+ m_graph.dethread();
+ mergeBlocks(blockIndex, targetBlockIndex, noBlocks());
+ } else {
+#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
+ dataLogF(
+ "CFGSimplify: Branch->jump conversion to same successor on Block #%u to Block #%u.\n",
+ blockIndex, targetBlockIndex);
+#endif
+ Node* branch = block->last();
+ ASSERT(branch->isTerminal());
+ ASSERT(branch->op() == Branch || branch->op() == Switch);
+ branch->convertToPhantom();
+ ASSERT(branch->refCount() == 1);
+
+ block->appendNode(
+ m_graph, SpecNone, Jump, branch->codeOrigin,
+ OpInfo(targetBlockIndex));
+ }
+ }
+
void killUnreachable(BlockIndex blockIndex)
{
BasicBlock* block = m_graph.m_blocks[blockIndex].get();
@@ -302,9 +388,21 @@
break;
}
}
+
+ Vector<BlockIndex, 1> noBlocks()
+ {
+ return Vector<BlockIndex, 1>();
+ }
+ Vector<BlockIndex, 1> oneBlock(BlockIndex blockIndex)
+ {
+ Vector<BlockIndex, 1> result;
+ result.append(blockIndex);
+ return result;
+ }
+
void mergeBlocks(
- BlockIndex firstBlockIndex, BlockIndex secondBlockIndex, BlockIndex jettisonedBlockIndex)
+ BlockIndex firstBlockIndex, BlockIndex secondBlockIndex, Vector<BlockIndex, 1> jettisonedBlockIndices)
{
// This will add all of the nodes in secondBlock to firstBlock, but in so doing
// it will also ensure that any GetLocals from the second block that refer to
@@ -322,8 +420,8 @@
firstBlock->last()->convertToPhantom();
ASSERT(firstBlock->last()->refCount() == 1);
- if (jettisonedBlockIndex != NoBlock) {
- BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndex].get();
+ for (unsigned i = jettisonedBlockIndices.size(); i--;) {
+ BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndices[i]].get();
// Time to insert ghosties for things that need to be kept alive in case we OSR
// exit prior to hitting the firstBlock's terminal, and end up going down a
@@ -358,8 +456,8 @@
// Fix the predecessors of my former successors. Again, we'd rather not do this, but it's
// an unfortunate necessity. See above comment.
- if (jettisonedBlockIndex != NoBlock)
- fixJettisonedPredecessors(firstBlockIndex, jettisonedBlockIndex);
+ for (unsigned i = jettisonedBlockIndices.size(); i--;)
+ fixJettisonedPredecessors(firstBlockIndex, jettisonedBlockIndices[i]);
firstBlock->valuesAtTail = secondBlock->valuesAtTail;
firstBlock->cfaBranchDirection = secondBlock->cfaBranchDirection;
Modified: branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGNode.h (151643 => 151644)
--- branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGNode.h 2013-06-17 15:26:24 UTC (rev 151643)
+++ branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGNode.h 2013-06-17 16:22:06 UTC (rev 151644)
@@ -71,6 +71,12 @@
// instead decide to do something different - this is entirely up to the DFG.
// These data structures give the DFG a higher-level semantic description of
// what is going on, which will allow it to make the right decision.
+//
+// Note that there will never be multiple SwitchCases in SwitchData::cases that
+// have the same SwitchCase::value, since the bytecode's JumpTables never have
+// duplicates - since the JumpTable maps a value to a target. It's a
+// one-to-many mapping. So we may have duplicate targets, but never duplicate
+// values.
struct SwitchCase {
SwitchCase()
: target(NoBlock)
Modified: branches/dfgFourthTier/Source/_javascript_Core/runtime/JSCJSValue.h (151643 => 151644)
--- branches/dfgFourthTier/Source/_javascript_Core/runtime/JSCJSValue.h 2013-06-17 15:26:24 UTC (rev 151643)
+++ branches/dfgFourthTier/Source/_javascript_Core/runtime/JSCJSValue.h 2013-06-17 16:22:06 UTC (rev 151644)
@@ -254,6 +254,7 @@
static bool strictEqual(ExecState*, JSValue v1, JSValue v2);
static bool strictEqualSlowCase(ExecState*, JSValue v1, JSValue v2);
static bool strictEqualSlowCaseInline(ExecState*, JSValue v1, JSValue v2);
+ static TriState pureStrictEqual(JSValue v1, JSValue v2);
bool isCell() const;
JSCell* asCell() const;
Modified: branches/dfgFourthTier/Source/_javascript_Core/runtime/JSCJSValueInlines.h (151643 => 151644)
--- branches/dfgFourthTier/Source/_javascript_Core/runtime/JSCJSValueInlines.h 2013-06-17 15:26:24 UTC (rev 151643)
+++ branches/dfgFourthTier/Source/_javascript_Core/runtime/JSCJSValueInlines.h 2013-06-17 16:22:06 UTC (rev 151644)
@@ -793,6 +793,28 @@
return strictEqualSlowCaseInline(exec, v1, v2);
}
+inline TriState JSValue::pureStrictEqual(JSValue v1, JSValue v2)
+{
+ if (v1.isInt32() && v2.isInt32())
+ return triState(v1 == v2);
+
+ if (v1.isNumber() && v2.isNumber())
+ return triState(v1.asNumber() == v2.asNumber());
+
+ if (!v1.isCell() || !v2.isCell())
+ return triState(v1 == v2);
+
+ if (v1.asCell()->isString() && v2.asCell()->isString()) {
+ const StringImpl* v1String = asString(v1)->tryGetValueImpl();
+ const StringImpl* v2String = asString(v2)->tryGetValueImpl();
+ if (!v1String || !v2String)
+ return MixedTriState;
+ return triState(WTF::equal(v1String, v2String));
+ }
+
+ return triState(v1 == v2);
+}
+
inline TriState JSValue::pureToBoolean() const
{
if (isInt32())
Modified: branches/dfgFourthTier/Source/WTF/ChangeLog (151643 => 151644)
--- branches/dfgFourthTier/Source/WTF/ChangeLog 2013-06-17 15:26:24 UTC (rev 151643)
+++ branches/dfgFourthTier/Source/WTF/ChangeLog 2013-06-17 16:22:06 UTC (rev 151644)
@@ -1,5 +1,15 @@
2013-06-15 Filip Pizlo <[email protected]>
+ fourthTier: Add CFG simplification for Switch
+ https://bugs.webkit.org/show_bug.cgi?id=117677
+
+ Reviewed by Mark Hahnenberg.
+
+ * wtf/TriState.h:
+ * wtf/text/StringImpl.h:
+
+2013-06-15 Filip Pizlo <[email protected]>
+
Printing a StringImpl* should really guard against NULL
https://bugs.webkit.org/show_bug.cgi?id=117675
Modified: branches/dfgFourthTier/Source/WTF/wtf/TriState.h (151643 => 151644)
--- branches/dfgFourthTier/Source/WTF/wtf/TriState.h 2013-06-17 15:26:24 UTC (rev 151643)
+++ branches/dfgFourthTier/Source/WTF/wtf/TriState.h 2013-06-17 16:22:06 UTC (rev 151644)
@@ -45,5 +45,6 @@
using WTF::FalseTriState;
using WTF::TrueTriState;
using WTF::MixedTriState;
+using WTF::triState;
#endif // TriState_h
Modified: branches/dfgFourthTier/Source/WTF/wtf/text/StringImpl.h (151643 => 151644)
--- branches/dfgFourthTier/Source/WTF/wtf/text/StringImpl.h 2013-06-17 15:26:24 UTC (rev 151643)
+++ branches/dfgFourthTier/Source/WTF/wtf/text/StringImpl.h 2013-06-17 16:22:06 UTC (rev 151644)
@@ -1306,7 +1306,7 @@
typedef StringHash Hash;
};
-}
+} // namespace WTF
using WTF::StringImpl;
using WTF::equal;
