No subject
Tue Jan 27 15:54:36 PST 2015
and improve the runtime by about 10%.
* contentextensions/DFABytecode.h:
(WebCore::ContentExtensions::instructionSizeWithArguments):
* contentextensions/DFABytecodeCompiler.cpp:
(WebCore::ContentExtensions::DFABytecodeCompiler::extractJumpTable):
(WebCore::ContentExtensions::DFABytecodeCompiler::transitions):
(WebCore::ContentExtensions::DFABytecodeCompiler::checkForJumpTableMaxBytecodeSize):
(WebCore::ContentExtensions::DFABytecodeCompiler::compileJumpTable):
(WebCore::ContentExtensions::DFABytecodeCompiler::nodeTransitionsMaxBytecodeSize):
(WebCore::ContentExtensions::DFABytecodeCompiler::compileNodeTransitions):
(WebCore::ContentExtensions::DFABytecodeCompiler::ranges): Deleted.
* contentextensions/DFABytecodeCompiler.h:
* contentextensions/DFABytecodeInterpreter.cpp:
(WebCore::ContentExtensions::DFABytecodeInterpreter::interpetJumpTable):
(WebCore::ContentExtensions::DFABytecodeInterpreter::interpret):
* contentextensions/DFABytecodeInterpreter.h:
Source/WebKit2:
* UIProcess/API/APIUserContentExtensionStore.h:
LayoutTests:
Add some primitive testing to make sure the code is covered.
* http/tests/contentextensions/test-jump-table-bytecode-generation-expected.txt: Added.
* http/tests/contentextensions/test-jump-table-bytecode-generation.html: Added.
* http/tests/contentextensions/test-jump-table-bytecode-generation.html.json: Added.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkLayoutTestsChangeLog">trunk/LayoutTests/ChangeLog</a></li>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFABytecodeh">trunk/Source/WebCore/contentextensions/DFABytecode.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFABytecodeCompilercpp">trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFABytecodeCompilerh">trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.h</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFABytecodeInterpretercpp">trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsDFABytecodeInterpreterh">trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.h</a></li>
<li><a href="#trunkSourceWebKit2ChangeLog">trunk/Source/WebKit2/ChangeLog</a></li>
<li><a href="#trunkSourceWebKit2UIProcessAPIAPIUserContentExtensionStoreh">trunk/Source/WebKit2/UIProcess/API/APIUserContentExtensionStore.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkLayoutTestshttptestscontentextensionstestjumptablebytecodegenerationexpectedtxt">trunk/LayoutTests/http/tests/contentextensions/test-jump-table-bytecode-generation-expected.txt</a></li>
<li><a href="#trunkLayoutTestshttptestscontentextensionstestjumptablebytecodegenerationhtml">trunk/LayoutTests/http/tests/contentextensions/test-jump-table-bytecode-generation.html</a></li>
<li><a href="#trunkLayoutTestshttptestscontentextensionstestjumptablebytecodegenerationhtmljson">trunk/LayoutTests/http/tests/contentextensions/test-jump-table-bytecode-generation.html.json</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkLayoutTestsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/ChangeLog (187136 => 187137)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/ChangeLog 2015-07-21 23:33:37 UTC (rev 187136)
+++ trunk/LayoutTests/ChangeLog 2015-07-21 23:45:00 UTC (rev 187137)
</span><span class="lines">@@ -1,3 +1,16 @@
</span><ins>+2015-07-21 Benjamin Poulain <benjamin at webkit.org>
+
+ [Content Extensions] Use a jump table when consecutive transitions have different targets
+ https://bugs.webkit.org/show_bug.cgi?id=147099
+
+ Reviewed by Alex Christensen.
+
+ Add some primitive testing to make sure the code is covered.
+
+ * http/tests/contentextensions/test-jump-table-bytecode-generation-expected.txt: Added.
+ * http/tests/contentextensions/test-jump-table-bytecode-generation.html: Added.
+ * http/tests/contentextensions/test-jump-table-bytecode-generation.html.json: Added.
+
</ins><span class="cx"> 2015-07-21 Benjamin Poulain <bpoulain at apple.com>
</span><span class="cx">
</span><span class="cx"> StyleSheetContents::wrapperInsertRule() can create rules that overflow RuleData's selector index
</span></span></pre></div>
<a id="trunkLayoutTestshttptestscontentextensionstestjumptablebytecodegenerationexpectedtxt"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/http/tests/contentextensions/test-jump-table-bytecode-generation-expected.txt (0 => 187137)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/http/tests/contentextensions/test-jump-table-bytecode-generation-expected.txt (rev 0)
+++ trunk/LayoutTests/http/tests/contentextensions/test-jump-table-bytecode-generation-expected.txt 2015-07-21 23:45:00 UTC (rev 187137)
</span><span class="lines">@@ -0,0 +1 @@
</span><ins>+This text should be visible.
</ins></span></pre></div>
<a id="trunkLayoutTestshttptestscontentextensionstestjumptablebytecodegenerationhtml"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/http/tests/contentextensions/test-jump-table-bytecode-generation.html (0 => 187137)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/http/tests/contentextensions/test-jump-table-bytecode-generation.html (rev 0)
+++ trunk/LayoutTests/http/tests/contentextensions/test-jump-table-bytecode-generation.html 2015-07-21 23:45:00 UTC (rev 187137)
</span><span class="lines">@@ -0,0 +1,11 @@
</span><ins>+<head>
+<meta charset="UTF-8"></meta>
+<script>
+ testRunner.dumpAsText();
+</script>
+</head>
+<body>
+<p>This text should be visible.</p>
+<p class="foo">This text should not be visible.</p>
+<p class="bar">This text should not be visible.</p>
+</body>
</ins></span></pre></div>
<a id="trunkLayoutTestshttptestscontentextensionstestjumptablebytecodegenerationhtmljson"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/http/tests/contentextensions/test-jump-table-bytecode-generation.html.json (0 => 187137)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/http/tests/contentextensions/test-jump-table-bytecode-generation.html.json (rev 0)
+++ trunk/LayoutTests/http/tests/contentextensions/test-jump-table-bytecode-generation.html.json 2015-07-21 23:45:00 UTC (rev 187137)
</span><span class="lines">@@ -0,0 +1,60 @@
</span><ins>+[
+ {
+ "action": {
+ "type": "css-display-none",
+ "selector": ".foo"
+ },
+ "trigger": {
+ "url-filter": "cod"
+ }
+ },
+ {
+ "action": {
+ "type": "block"
+ },
+ "trigger": {
+ "url-filter": "dpc"
+ }
+ },
+ {
+ "action": {
+ "type": "block-cookies"
+ },
+ "trigger": {
+ "url-filter": "eme"
+ }
+ },
+ {
+ "action": {
+ "type": "css-display-none",
+ "selector": ".bar"
+ },
+ "trigger": {
+ "url-filter": "eco"
+ }
+ },
+ {
+ "action": {
+ "type": "block"
+ },
+ "trigger": {
+ "url-filter": "cco"
+ }
+ },
+ {
+ "action": {
+ "type": "ignore-previous-rules"
+ },
+ "trigger": {
+ "url-filter": "cpd"
+ }
+ },
+ {
+ "action": {
+ "type": "block"
+ },
+ "trigger": {
+ "url-filter": "doc"
+ }
+ }
+]
</ins></span></pre></div>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (187136 => 187137)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-07-21 23:33:37 UTC (rev 187136)
+++ trunk/Source/WebCore/ChangeLog 2015-07-21 23:45:00 UTC (rev 187137)
</span><span class="lines">@@ -1,3 +1,32 @@
</span><ins>+2015-07-21 Benjamin Poulain <benjamin at webkit.org>
+
+ [Content Extensions] Use a jump table when consecutive transitions have different targets
+ https://bugs.webkit.org/show_bug.cgi?id=147099
+
+ Reviewed by Alex Christensen.
+
+ When handling consecutive single transitions, merge them into
+ a jump table instead of creating many individual CheckValue.
+
+ From local testing on x86_64, it reduces the bytecode size by about 5%
+ and improve the runtime by about 10%.
+
+ * contentextensions/DFABytecode.h:
+ (WebCore::ContentExtensions::instructionSizeWithArguments):
+ * contentextensions/DFABytecodeCompiler.cpp:
+ (WebCore::ContentExtensions::DFABytecodeCompiler::extractJumpTable):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::transitions):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::checkForJumpTableMaxBytecodeSize):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::compileJumpTable):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::nodeTransitionsMaxBytecodeSize):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::compileNodeTransitions):
+ (WebCore::ContentExtensions::DFABytecodeCompiler::ranges): Deleted.
+ * contentextensions/DFABytecodeCompiler.h:
+ * contentextensions/DFABytecodeInterpreter.cpp:
+ (WebCore::ContentExtensions::DFABytecodeInterpreter::interpetJumpTable):
+ (WebCore::ContentExtensions::DFABytecodeInterpreter::interpret):
+ * contentextensions/DFABytecodeInterpreter.h:
+
</ins><span class="cx"> 2015-07-21 Simon Fraser <simon.fraser at apple.com>
</span><span class="cx">
</span><span class="cx"> Add a logging channel for Layout, remove the LiveConnect channel
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFABytecodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFABytecode.h (187136 => 187137)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFABytecode.h 2015-07-21 23:33:37 UTC (rev 187136)
+++ trunk/Source/WebCore/contentextensions/DFABytecode.h 2015-07-21 23:45:00 UTC (rev 187137)
</span><span class="lines">@@ -45,30 +45,38 @@
</span><span class="cx"> CheckValueCaseInsensitive = 0x0,
</span><span class="cx"> CheckValueCaseSensitive = 0x1,
</span><span class="cx">
</span><ins>+ // Jump table if the input value is within a certain range.
+ // The lower value (1 byte).
+ // The higher value (1 byte).
+ // The distance to jump if the value is in the range
+ // for every character in the range (1-4 bytes, signed).
+ JumpTableCaseInsensitive = 0x2,
+ JumpTableCaseSensitive = 0x3,
+
</ins><span class="cx"> // Jump to an offset if the input value is within a certain range.
</span><span class="cx"> // The lower value (1 byte).
</span><span class="cx"> // The higher value (1 byte).
</span><span class="cx"> // The distance to jump if the value is in the range (1-4 bytes, signed).
</span><del>- CheckValueRangeCaseInsensitive = 0x2,
- CheckValueRangeCaseSensitive = 0x3,
</del><ins>+ CheckValueRangeCaseInsensitive = 0x4,
+ CheckValueRangeCaseSensitive = 0x5,
</ins><span class="cx">
</span><span class="cx"> // AppendAction has one argument:
</span><span class="cx"> // The action to append (4 bytes).
</span><del>- AppendAction = 0x4,
- AppendActionWithIfDomain = 0x5,
</del><ins>+ AppendAction = 0x6,
+ AppendActionWithIfDomain = 0x7,
</ins><span class="cx">
</span><span class="cx"> // TestFlagsAndAppendAction has two arguments:
</span><span class="cx"> // The flags to check before appending (2 bytes).
</span><span class="cx"> // The action to append (4 bytes).
</span><del>- TestFlagsAndAppendAction = 0x6,
- TestFlagsAndAppendActionWithIfDomain = 0x7,
</del><ins>+ TestFlagsAndAppendAction = 0x8,
+ TestFlagsAndAppendActionWithIfDomain = 0x9,
</ins><span class="cx">
</span><span class="cx"> // Terminate has no arguments.
</span><del>- Terminate = 0x8,
</del><ins>+ Terminate = 0xA,
</ins><span class="cx">
</span><span class="cx"> // Jump has one argument:
</span><span class="cx"> // The distance to jump (1-4 bytes, signed).
</span><del>- Jump = 0x9,
</del><ins>+ Jump = 0xB,
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> // The last four bits contain the instruction type.
</span><span class="lines">@@ -104,6 +112,8 @@
</span><span class="cx"> switch (instruction) {
</span><span class="cx"> case DFABytecodeInstruction::CheckValueCaseSensitive:
</span><span class="cx"> case DFABytecodeInstruction::CheckValueCaseInsensitive:
</span><ins>+ case DFABytecodeInstruction::JumpTableCaseInsensitive:
+ case DFABytecodeInstruction::JumpTableCaseSensitive:
</ins><span class="cx"> case DFABytecodeInstruction::CheckValueRangeCaseSensitive:
</span><span class="cx"> case DFABytecodeInstruction::CheckValueRangeCaseInsensitive:
</span><span class="cx"> case DFABytecodeInstruction::Jump:
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFABytecodeCompilercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp (187136 => 187137)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp 2015-07-21 23:33:37 UTC (rev 187136)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.cpp 2015-07-21 23:45:00 UTC (rev 187137)
</span><span class="lines">@@ -198,27 +198,56 @@
</span><span class="cx"> return size;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-Vector<DFABytecodeCompiler::Range> DFABytecodeCompiler::ranges(const DFANode& node)
</del><ins>+DFABytecodeCompiler::JumpTable DFABytecodeCompiler::extractJumpTable(Vector<DFABytecodeCompiler::Range>& ranges, unsigned firstRange, unsigned lastRange)
</ins><span class="cx"> {
</span><ins>+ ASSERT(lastRange > firstRange);
+ ASSERT(lastRange < ranges.size());
+
+ JumpTable jumpTable;
+ jumpTable.min = ranges[firstRange].min;
+ jumpTable.max = ranges[lastRange].max;
+ jumpTable.caseSensitive = ranges[lastRange].caseSensitive;
+
+ unsigned size = lastRange - firstRange + 1;
+ jumpTable.destinations.reserveInitialCapacity(size);
+ for (unsigned i = firstRange; i <= lastRange; ++i) {
+ const Range& range = ranges[i];
+
+ ASSERT(range.caseSensitive == jumpTable.caseSensitive);
+ ASSERT(range.min == range.max);
+ ASSERT(range.min >= jumpTable.min);
+ ASSERT(range.min <= jumpTable.max);
+
+ jumpTable.destinations.append(range.destination);
+ }
+
+ ranges.remove(firstRange, size);
+
+ return jumpTable;
+}
+
+DFABytecodeCompiler::Transitions DFABytecodeCompiler::transitions(const DFANode& node)
+{
+ Transitions transitions;
+
</ins><span class="cx"> uint32_t destinations[128];
</span><span class="cx"> memset(destinations, 0xff, sizeof(destinations));
</span><span class="cx"> const uint32_t noDestination = std::numeric_limits<uint32_t>::max();
</span><span class="cx">
</span><del>- bool canUseFallbackTransition = node.canUseFallbackTransition(m_dfa);
- uint32_t fallbackTransitionTarget = std::numeric_limits<uint32_t>::max();
- if (canUseFallbackTransition)
- fallbackTransitionTarget = node.bestFallbackTarget(m_dfa);
</del><ins>+ transitions.useFallbackTransition = node.canUseFallbackTransition(m_dfa);
+ if (transitions.useFallbackTransition)
+ transitions.fallbackTransitionTarget = node.bestFallbackTarget(m_dfa);
</ins><span class="cx">
</span><span class="cx"> for (const auto& transition : node.transitions(m_dfa)) {
</span><span class="cx"> uint32_t targetNodeIndex = transition.target();
</span><del>- if (canUseFallbackTransition && fallbackTransitionTarget == targetNodeIndex)
</del><ins>+ if (transitions.useFallbackTransition && transitions.fallbackTransitionTarget == targetNodeIndex)
</ins><span class="cx"> continue;
</span><span class="cx">
</span><span class="cx"> for (uint16_t i = transition.range().first; i <= transition.range().last; ++i)
</span><span class="cx"> destinations[i] = targetNodeIndex;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- Vector<Range> ranges;
</del><ins>+ Vector<Range>& ranges = transitions.ranges;
</ins><span class="cx"> uint8_t rangeMin;
</span><span class="cx"> bool hasRangeMin = false;
</span><span class="cx"> for (uint8_t i = 0; i < 128; i++) {
</span><span class="lines">@@ -268,8 +297,44 @@
</span><span class="cx"> ranges.append(Range(rangeMin, 127, destinations[rangeMin], true));
</span><span class="cx"> }
</span><span class="cx">
</span><del>- return ranges;
</del><ins>+ Vector<JumpTable>& jumpTables = transitions.jumpTables;
+ unsigned rangePosition = 0;
+ unsigned baseRangePosition = std::numeric_limits<unsigned>::max();
+ Range* baseRange = nullptr;
+ while (rangePosition < ranges.size()) {
+ auto& range = ranges[rangePosition];
+ if (baseRange) {
+ if (range.min != range.max
+ || baseRange->caseSensitive != range.caseSensitive
+ || ranges[rangePosition - 1].max + 1 != range.min) {
+ if (rangePosition - baseRangePosition > 1) {
+ jumpTables.append(extractJumpTable(ranges, baseRangePosition, rangePosition - 1));
+ rangePosition = baseRangePosition;
+ }
+ baseRangePosition = std::numeric_limits<unsigned>::max();
+ baseRange = nullptr;
+ }
+ } else {
+ if (range.min == range.max) {
+ baseRangePosition = rangePosition;
+ baseRange = &range;
+ }
+ }
+ ++rangePosition;
+ }
+
+ if (baseRange && ranges.size() - baseRangePosition > 1)
+ jumpTables.append(extractJumpTable(ranges, baseRangePosition, ranges.size() - 1));
+
+ return transitions;
</ins><span class="cx"> }
</span><ins>+
+unsigned DFABytecodeCompiler::checkForJumpTableMaxBytecodeSize(const JumpTable& jumpTable)
+{
+ unsigned baselineSize = sizeof(DFABytecodeInstruction::CheckValueRangeCaseInsensitive) + 2 * sizeof(uint8_t);
+ unsigned targetsSize = (jumpTable.max - jumpTable.min + 1) * sizeof(uint32_t);
+ return baselineSize + targetsSize;
+}
</ins><span class="cx">
</span><span class="cx"> unsigned DFABytecodeCompiler::checkForRangeMaxBytecodeSize(const Range& range)
</span><span class="cx"> {
</span><span class="lines">@@ -278,6 +343,35 @@
</span><span class="cx"> return sizeof(DFABytecodeInstruction::CheckValueRangeCaseInsensitive) + 2 * sizeof(uint8_t) + sizeof(uint32_t);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void DFABytecodeCompiler::compileJumpTable(uint32_t nodeIndex, const JumpTable& jumpTable)
+{
+ unsigned startSize = m_bytecode.size();
+ ASSERT_WITH_MESSAGE(jumpTable.max < 128, "The DFA engine only supports the ASCII alphabet.");
+ ASSERT(jumpTable.min <= jumpTable.max);
+
+ uint32_t instructionLocation = m_bytecode.size();
+ DFABytecodeJumpSize jumpSize = Int8;
+ for (uint32_t destinationNodeIndex : jumpTable.destinations) {
+ int32_t longestPossibleJumpDistance = longestPossibleJump(instructionLocation, nodeIndex, destinationNodeIndex);
+ DFABytecodeJumpSize localJumpSize = smallestPossibleJumpSize(longestPossibleJumpDistance);
+ jumpSize = std::max(jumpSize, localJumpSize);
+ }
+
+ DFABytecodeInstruction instruction = jumpTable.caseSensitive ? DFABytecodeInstruction::JumpTableCaseSensitive : DFABytecodeInstruction::JumpTableCaseInsensitive;
+ append<uint8_t>(m_bytecode, static_cast<uint8_t>(instruction) | jumpSize);
+ append<uint8_t>(m_bytecode, jumpTable.min);
+ append<uint8_t>(m_bytecode, jumpTable.max);
+
+ for (uint32_t destinationNodeIndex : jumpTable.destinations) {
+ int32_t longestPossibleJumpDistance = longestPossibleJump(instructionLocation, nodeIndex, destinationNodeIndex);
+ uint32_t jumpLocation = m_bytecode.size();
+ m_linkRecords.append(LinkRecord({jumpSize, longestPossibleJumpDistance, instructionLocation, jumpLocation, destinationNodeIndex}));
+ appendZeroes(m_bytecode, jumpSize);
+ }
+
+ ASSERT_UNUSED(startSize, m_bytecode.size() - startSize <= checkForJumpTableMaxBytecodeSize(jumpTable));
+}
+
</ins><span class="cx"> void DFABytecodeCompiler::compileCheckForRange(uint32_t nodeIndex, const Range& range)
</span><span class="cx"> {
</span><span class="cx"> unsigned startSize = m_bytecode.size();
</span><span class="lines">@@ -295,9 +389,12 @@
</span><span class="cx"> unsigned DFABytecodeCompiler::nodeTransitionsMaxBytecodeSize(const DFANode& node)
</span><span class="cx"> {
</span><span class="cx"> unsigned size = 0;
</span><del>- for (const auto& range : ranges(node))
</del><ins>+ Transitions nodeTransitions = transitions(node);
+ for (const auto& jumpTable : nodeTransitions.jumpTables)
+ size += checkForJumpTableMaxBytecodeSize(jumpTable);
+ for (const auto& range : nodeTransitions.ranges)
</ins><span class="cx"> size += checkForRangeMaxBytecodeSize(range);
</span><del>- if (node.canUseFallbackTransition(m_dfa))
</del><ins>+ if (nodeTransitions.useFallbackTransition)
</ins><span class="cx"> size += sizeof(DFABytecodeInstruction::Jump) + sizeof(uint32_t);
</span><span class="cx"> else
</span><span class="cx"> size += instructionSizeWithArguments(DFABytecodeInstruction::Terminate);
</span><span class="lines">@@ -308,11 +405,14 @@
</span><span class="cx"> {
</span><span class="cx"> const DFANode& node = m_dfa.nodes[nodeIndex];
</span><span class="cx"> unsigned startSize = m_bytecode.size();
</span><del>-
- for (const auto& range : ranges(node))
</del><ins>+
+ Transitions nodeTransitions = transitions(node);
+ for (const auto& jumpTable : nodeTransitions.jumpTables)
+ compileJumpTable(nodeIndex, jumpTable);
+ for (const auto& range : nodeTransitions.ranges)
</ins><span class="cx"> compileCheckForRange(nodeIndex, range);
</span><del>- if (node.canUseFallbackTransition(m_dfa))
- emitJump(nodeIndex, node.bestFallbackTarget(m_dfa));
</del><ins>+ if (nodeTransitions.useFallbackTransition)
+ emitJump(nodeIndex, nodeTransitions.fallbackTransitionTarget);
</ins><span class="cx"> else
</span><span class="cx"> emitTerminate();
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFABytecodeCompilerh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.h (187136 => 187137)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.h 2015-07-21 23:33:37 UTC (rev 187136)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.h 2015-07-21 23:45:00 UTC (rev 187137)
</span><span class="lines">@@ -62,13 +62,34 @@
</span><span class="cx"> uint32_t destination;
</span><span class="cx"> bool caseSensitive;
</span><span class="cx"> };
</span><del>- Vector<Range> ranges(const DFANode&);
</del><ins>+ struct JumpTable {
+ ~JumpTable()
+ {
+ ASSERT(min + destinations.size() == max + 1);
+ ASSERT(min == max || destinations.size() > 1);
+ }
+
+ uint8_t min { 0 };
+ uint8_t max { 0 };
+ bool caseSensitive { true };
+ Vector<uint32_t> destinations;
+ };
+ struct Transitions {
+ Vector<JumpTable> jumpTables;
+ Vector<Range> ranges;
+ bool useFallbackTransition { false };
+ uint32_t fallbackTransitionTarget { std::numeric_limits<uint32_t>::max() };
+ };
+ JumpTable extractJumpTable(Vector<Range>&, unsigned first, unsigned last);
+ Transitions transitions(const DFANode&);
</ins><span class="cx">
</span><span class="cx"> unsigned compiledNodeMaxBytecodeSize(uint32_t index);
</span><span class="cx"> void compileNode(uint32_t index, bool root);
</span><span class="cx"> unsigned nodeTransitionsMaxBytecodeSize(const DFANode&);
</span><span class="cx"> void compileNodeTransitions(uint32_t nodeIndex);
</span><ins>+ unsigned checkForJumpTableMaxBytecodeSize(const JumpTable&);
</ins><span class="cx"> unsigned checkForRangeMaxBytecodeSize(const Range&);
</span><ins>+ void compileJumpTable(uint32_t nodeIndex, const JumpTable&);
</ins><span class="cx"> void compileCheckForRange(uint32_t nodeIndex, const Range&);
</span><span class="cx"> int32_t longestPossibleJump(uint32_t jumpLocation, uint32_t sourceNodeIndex, uint32_t destinationNodeIndex);
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFABytecodeInterpretercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.cpp (187136 => 187137)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.cpp 2015-07-21 23:33:37 UTC (rev 187136)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.cpp 2015-07-21 23:45:00 UTC (rev 187137)
</span><span class="lines">@@ -126,6 +126,25 @@
</span><span class="cx"> ASSERT(instructionSizeWithArguments(DFABytecodeInstruction::TestFlagsAndAppendAction) == instructionSizeWithArguments(DFABytecodeInstruction::TestFlagsAndAppendActionWithIfDomain));
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+template<bool caseSensitive>
+inline void DFABytecodeInterpreter::interpetJumpTable(const char* url, uint32_t& urlIndex, uint32_t& programCounter, bool& urlIndexIsAfterEndOfString)
+{
+ DFABytecodeJumpSize jumpSize = getJumpSize(m_bytecode, m_bytecodeLength, programCounter);
+
+ char character = caseSensitive ? url[urlIndex] : toASCIILower(url[urlIndex]);
+ uint8_t firstCharacter = getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction));
+ uint8_t lastCharacter = getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction) + sizeof(uint8_t));
+ if (character >= firstCharacter && character <= lastCharacter) {
+ uint32_t startOffset = programCounter + sizeof(DFABytecodeInstruction) + 2 * sizeof(uint8_t);
+ uint32_t jumpLocation = startOffset + (character - firstCharacter) * jumpSizeInBytes(jumpSize);
+ programCounter += getJumpDistance(m_bytecode, m_bytecodeLength, jumpLocation, jumpSize);
+ if (!character)
+ urlIndexIsAfterEndOfString = true;
+ urlIndex++; // This represents an edge in the DFA.
+ } else
+ programCounter += sizeof(DFABytecodeInstruction) + 2 * sizeof(uint8_t) + jumpSizeInBytes(jumpSize) * (lastCharacter - firstCharacter + 1);
+}
+
</ins><span class="cx"> DFABytecodeInterpreter::Actions DFABytecodeInterpreter::actionsMatchingEverything()
</span><span class="cx"> {
</span><span class="cx"> Actions actions;
</span><span class="lines">@@ -245,6 +264,19 @@
</span><span class="cx"> programCounter += sizeof(DFABytecodeInstruction) + sizeof(uint8_t) + jumpSizeInBytes(jumpSize);
</span><span class="cx"> break;
</span><span class="cx"> }
</span><ins>+
+ case DFABytecodeInstruction::JumpTableCaseInsensitive:
+ if (urlIndexIsAfterEndOfString)
+ goto nextDFA;
+
+ interpetJumpTable<false>(url, urlIndex, programCounter, urlIndexIsAfterEndOfString);
+ break;
+ case DFABytecodeInstruction::JumpTableCaseSensitive:
+ if (urlIndexIsAfterEndOfString)
+ goto nextDFA;
+
+ interpetJumpTable<true>(url, urlIndex, programCounter, urlIndexIsAfterEndOfString);
+ break;
</ins><span class="cx">
</span><span class="cx"> case DFABytecodeInstruction::CheckValueRangeCaseSensitive: {
</span><span class="cx"> if (urlIndexIsAfterEndOfString)
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsDFABytecodeInterpreterh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.h (187136 => 187137)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.h 2015-07-21 23:33:37 UTC (rev 187136)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.h 2015-07-21 23:45:00 UTC (rev 187137)
</span><span class="lines">@@ -56,6 +56,10 @@
</span><span class="cx"> private:
</span><span class="cx"> void interpretAppendAction(unsigned& programCounter, Actions&, bool ifDomain);
</span><span class="cx"> void interpretTestFlagsAndAppendAction(unsigned& programCounter, uint16_t flags, Actions&, bool ifDomain);
</span><ins>+
+ template<bool caseSensitive>
+ void interpetJumpTable(const char* url, uint32_t& urlIndex, uint32_t& programCounter, bool& urlIndexIsAfterEndOfString);
+
</ins><span class="cx"> const DFABytecode* m_bytecode;
</span><span class="cx"> const unsigned m_bytecodeLength;
</span><span class="cx"> const DFABytecodeInterpreter::Actions* m_domainActions { nullptr };
</span></span></pre></div>
<a id="trunkSourceWebKit2ChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebKit2/ChangeLog (187136 => 187137)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebKit2/ChangeLog 2015-07-21 23:33:37 UTC (rev 187136)
+++ trunk/Source/WebKit2/ChangeLog 2015-07-21 23:45:00 UTC (rev 187137)
</span><span class="lines">@@ -1,3 +1,12 @@
</span><ins>+2015-07-21 Benjamin Poulain <benjamin at webkit.org>
+
+ [Content Extensions] Use a jump table when consecutive transitions have different targets
+ https://bugs.webkit.org/show_bug.cgi?id=147099
+
+ Reviewed by Alex Christensen.
+
+ * UIProcess/API/APIUserContentExtensionStore.h:
+
</ins><span class="cx"> 2015-07-21 Daniel Bates <dabates at apple.com>
</span><span class="cx">
</span><span class="cx"> Fix the build following <https://trac.webkit.org/changeset/187129>
</span></span></pre></div>
<a id="trunkSourceWebKit2UIProcessAPIAPIUserContentExtensionStoreh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebKit2/UIProcess/API/APIUserContentExtensionStore.h (187136 => 187137)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebKit2/UIProcess/API/APIUserContentExtensionStore.h 2015-07-21 23:33:37 UTC (rev 187136)
+++ trunk/Source/WebKit2/UIProcess/API/APIUserContentExtensionStore.h 2015-07-21 23:45:00 UTC (rev 187137)
</span><span class="lines">@@ -51,7 +51,7 @@
</span><span class="cx">
</span><span class="cx"> // This should be incremented every time a functional change is made to the bytecode, file format, etc.
</span><span class="cx"> // to prevent crashing while loading old data.
</span><del>- const static uint32_t CurrentContentExtensionFileVersion = 6;
</del><ins>+ const static uint32_t CurrentContentExtensionFileVersion = 7;
</ins><span class="cx">
</span><span class="cx"> static UserContentExtensionStore& defaultStore();
</span><span class="cx"> static Ref<UserContentExtensionStore> storeWithPath(const WTF::String& storePath);
</span></span></pre>
</div>
</div>
</body>
</html>
More information about the webkit-changes
mailing list