<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[195585] trunk/Source</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/195585">195585</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2016-01-26 00:17:31 -0800 (Tue, 26 Jan 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>FTLB3Output should maintain good block order like the LLVM one does
https://bugs.webkit.org/show_bug.cgi?id=152222
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
This fixes FTLB3Output to emit an ordered B3 IR. This makes inspecting IR *a lot* easier.
It will also be a performance win whenever we use range-based data structures for
liveness.
Also two small other changes:
- Added some more dumping in integer range optimization phase.
- Refined the disassembler's printing of instruction width suffixes so that "jzl" is not
a thing. It was using "l" as the suffix because jumps take a 32-bit immediate.
* b3/B3Procedure.cpp:
(JSC::B3::Procedure::addBlock):
(JSC::B3::Procedure::setBlockOrderImpl):
(JSC::B3::Procedure::clone):
* b3/B3Procedure.h:
(JSC::B3::Procedure::frontendData):
(JSC::B3::Procedure::setBlockOrder):
* dfg/DFGIntegerRangeOptimizationPhase.cpp:
* disassembler/udis86/udis86_syn-att.c:
(ud_translate_att):
* ftl/FTLB3Output.cpp:
(JSC::FTL::Output::initialize):
(JSC::FTL::Output::newBlock):
(JSC::FTL::Output::applyBlockOrder):
(JSC::FTL::Output::appendTo):
* ftl/FTLB3Output.h:
(JSC::FTL::Output::setFrequency):
(JSC::FTL::Output::insertNewBlocksBefore):
(JSC::FTL::Output::callWithoutSideEffects):
(JSC::FTL::Output::newBlock): Deleted.
* ftl/FTLLowerDFGToLLVM.cpp:
(JSC::FTL::DFG::LowerDFGToLLVM::lower):
Source/WTF:
In the FTL we need to be able to construct a list by inserting elements before other
specific elements. We didn't already have a scalable way to do this, so this adds such a
data structure to WTF. This also has changes to SentinelLinkedList to make it support
these kinds of insertions.
* WTF.xcodeproj/project.pbxproj:
* wtf/OrderMaker.h: Added.
(WTF::OrderMaker::Node::Node):
(WTF::OrderMaker::OrderMaker):
(WTF::OrderMaker::prepend):
(WTF::OrderMaker::append):
(WTF::OrderMaker::insertBefore):
(WTF::OrderMaker::insertAfter):
(WTF::OrderMaker::iterator::iterator):
(WTF::OrderMaker::iterator::operator*):
(WTF::OrderMaker::iterator::operator++):
(WTF::OrderMaker::iterator::operator==):
(WTF::OrderMaker::iterator::operator!=):
(WTF::OrderMaker::begin):
(WTF::OrderMaker::end):
(WTF::OrderMaker::newNode):
* wtf/SentinelLinkedList.h:
(WTF::BasicRawSentinelNode::isOnList):
(WTF::BasicRawSentinelNode<T>::remove):
(WTF::BasicRawSentinelNode<T>::prepend):
(WTF::BasicRawSentinelNode<T>::append):
(WTF::RawNode>::SentinelLinkedList):
(WTF::RawNode>::push):
(WTF::RawNode>::append):
(WTF::RawNode>::remove):
(WTF::RawNode>::prepend):
(WTF::RawNode>::isOnList):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3Procedurecpp">trunk/Source/JavaScriptCore/b3/B3Procedure.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3Procedureh">trunk/Source/JavaScriptCore/b3/B3Procedure.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGIntegerRangeOptimizationPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredisassemblerudis86udis86_synattc">trunk/Source/JavaScriptCore/disassembler/udis86/udis86_syn-att.c</a></li>
<li><a href="#trunkSourceJavaScriptCoreftlFTLB3Outputcpp">trunk/Source/JavaScriptCore/ftl/FTLB3Output.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreftlFTLB3Outputh">trunk/Source/JavaScriptCore/ftl/FTLB3Output.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreftlFTLLowerDFGToLLVMcpp">trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFWTFxcodeprojprojectpbxproj">trunk/Source/WTF/WTF.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWTFwtfCMakeListstxt">trunk/Source/WTF/wtf/CMakeLists.txt</a></li>
<li><a href="#trunkSourceWTFwtfSentinelLinkedListh">trunk/Source/WTF/wtf/SentinelLinkedList.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceWTFwtfOrderMakerh">trunk/Source/WTF/wtf/OrderMaker.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (195584 => 195585)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2016-01-26 07:32:28 UTC (rev 195584)
+++ trunk/Source/JavaScriptCore/ChangeLog 2016-01-26 08:17:31 UTC (rev 195585)
</span><span class="lines">@@ -1,3 +1,42 @@
</span><ins>+2016-01-25 Filip Pizlo <fpizlo@apple.com>
+
+ FTLB3Output should maintain good block order like the LLVM one does
+ https://bugs.webkit.org/show_bug.cgi?id=152222
+
+ Reviewed by Geoffrey Garen.
+
+ This fixes FTLB3Output to emit an ordered B3 IR. This makes inspecting IR *a lot* easier.
+ It will also be a performance win whenever we use range-based data structures for
+ liveness.
+
+ Also two small other changes:
+ - Added some more dumping in integer range optimization phase.
+ - Refined the disassembler's printing of instruction width suffixes so that "jzl" is not
+ a thing. It was using "l" as the suffix because jumps take a 32-bit immediate.
+
+ * b3/B3Procedure.cpp:
+ (JSC::B3::Procedure::addBlock):
+ (JSC::B3::Procedure::setBlockOrderImpl):
+ (JSC::B3::Procedure::clone):
+ * b3/B3Procedure.h:
+ (JSC::B3::Procedure::frontendData):
+ (JSC::B3::Procedure::setBlockOrder):
+ * dfg/DFGIntegerRangeOptimizationPhase.cpp:
+ * disassembler/udis86/udis86_syn-att.c:
+ (ud_translate_att):
+ * ftl/FTLB3Output.cpp:
+ (JSC::FTL::Output::initialize):
+ (JSC::FTL::Output::newBlock):
+ (JSC::FTL::Output::applyBlockOrder):
+ (JSC::FTL::Output::appendTo):
+ * ftl/FTLB3Output.h:
+ (JSC::FTL::Output::setFrequency):
+ (JSC::FTL::Output::insertNewBlocksBefore):
+ (JSC::FTL::Output::callWithoutSideEffects):
+ (JSC::FTL::Output::newBlock): Deleted.
+ * ftl/FTLLowerDFGToLLVM.cpp:
+ (JSC::FTL::DFG::LowerDFGToLLVM::lower):
+
</ins><span class="cx"> 2016-01-25 Skachkov Oleksandr <gskachkov@gmail.com>
</span><span class="cx">
</span><span class="cx"> [ES6] Arrow function syntax. Arrow function specific features. Lexical bind "arguments"
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3Procedurecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3Procedure.cpp (195584 => 195585)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3Procedure.cpp 2016-01-26 07:32:28 UTC (rev 195584)
+++ trunk/Source/JavaScriptCore/b3/B3Procedure.cpp 2016-01-26 08:17:31 UTC (rev 195585)
</span><span class="lines">@@ -68,6 +68,29 @@
</span><span class="cx"> return result;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void Procedure::setBlockOrderImpl(Vector<BasicBlock*>& blocks)
+{
+ IndexSet<BasicBlock> blocksSet;
+ blocksSet.addAll(blocks);
+
+ for (BasicBlock* block : *this) {
+ if (!blocksSet.contains(block))
+ blocks.append(block);
+ }
+
+ // Place blocks into this's block list by first leaking all of the blocks and then readopting
+ // them.
+ for (auto& entry : m_blocks)
+ entry.release();
+
+ m_blocks.resize(blocks.size());
+ for (unsigned i = 0; i < blocks.size(); ++i) {
+ BasicBlock* block = blocks[i];
+ block->m_index = i;
+ m_blocks[i] = std::unique_ptr<BasicBlock>(block);
+ }
+}
+
</ins><span class="cx"> Value* Procedure::clone(Value* value)
</span><span class="cx"> {
</span><span class="cx"> std::unique_ptr<Value> clone(value->cloneImpl());
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3Procedureh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3Procedure.h (195584 => 195585)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3Procedure.h 2016-01-26 07:32:28 UTC (rev 195584)
+++ trunk/Source/JavaScriptCore/b3/B3Procedure.h 2016-01-26 08:17:31 UTC (rev 195585)
</span><span class="lines">@@ -78,6 +78,18 @@
</span><span class="cx"> const void* frontendData() const { return m_frontendData; }
</span><span class="cx">
</span><span class="cx"> JS_EXPORT_PRIVATE BasicBlock* addBlock(double frequency = 1);
</span><ins>+
+ // Changes the order of basic blocks to be as in the supplied vector. The vector does not
+ // need to mention every block in the procedure. Blocks not mentioned will be placed after
+ // these blocks in the same order as they were in originally.
+ template<typename BlockIterable>
+ void setBlockOrder(const BlockIterable& iterable)
+ {
+ Vector<BasicBlock*> blocks;
+ for (BasicBlock* block : iterable)
+ blocks.append(block);
+ setBlockOrderImpl(blocks);
+ }
</ins><span class="cx">
</span><span class="cx"> template<typename ValueType, typename... Arguments>
</span><span class="cx"> ValueType* add(Arguments...);
</span><span class="lines">@@ -278,6 +290,8 @@
</span><span class="cx"> private:
</span><span class="cx"> friend class BlockInsertionSet;
</span><span class="cx">
</span><ins>+ void setBlockOrderImpl(Vector<BasicBlock*>&);
+
</ins><span class="cx"> JS_EXPORT_PRIVATE size_t addValueIndex();
</span><span class="cx">
</span><span class="cx"> Vector<std::unique_ptr<BasicBlock>> m_blocks;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGIntegerRangeOptimizationPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp (195584 => 195585)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp 2016-01-26 07:32:28 UTC (rev 195584)
+++ trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp 2016-01-26 08:17:31 UTC (rev 195585)
</span><span class="lines">@@ -1221,10 +1221,16 @@
</span><span class="cx"> minValue = std::max(minValue, relationship.minValueOfLeft());
</span><span class="cx"> maxValue = std::min(maxValue, relationship.maxValueOfLeft());
</span><span class="cx"> }
</span><ins>+
+ if (verbose)
+ dataLog(" minValue = ", minValue, ", maxValue = ", maxValue, "\n");
</ins><span class="cx">
</span><span class="cx"> if (sumOverflows<int>(minValue, node->child2()->asInt32()) ||
</span><span class="cx"> sumOverflows<int>(maxValue, node->child2()->asInt32()))
</span><span class="cx"> break;
</span><ins>+
+ if (verbose)
+ dataLog(" It's in bounds.\n");
</ins><span class="cx">
</span><span class="cx"> executeNode(block->at(nodeIndex));
</span><span class="cx"> node->setArithMode(Arith::Unchecked);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredisassemblerudis86udis86_synattc"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/disassembler/udis86/udis86_syn-att.c (195584 => 195585)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/disassembler/udis86/udis86_syn-att.c 2016-01-26 07:32:28 UTC (rev 195584)
+++ trunk/Source/JavaScriptCore/disassembler/udis86/udis86_syn-att.c 2016-01-26 08:17:31 UTC (rev 195585)
</span><span class="lines">@@ -231,7 +231,8 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> for (i = 3; i--;) {
</span><del>- if (u->operand[i].size > size)
</del><ins>+ if (u->operand[i].size > size
+ && u->operand[i].type != UD_OP_JIMM)
</ins><span class="cx"> size = u->operand[i].size;
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreftlFTLB3Outputcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ftl/FTLB3Output.cpp (195584 => 195585)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ftl/FTLB3Output.cpp 2016-01-26 07:32:28 UTC (rev 195584)
+++ trunk/Source/JavaScriptCore/ftl/FTLB3Output.cpp 2016-01-26 08:17:31 UTC (rev 195585)
</span><span class="lines">@@ -51,6 +51,23 @@
</span><span class="cx"> m_heaps = &heaps;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+LBasicBlock Output::newBlock(const char*)
+{
+ LBasicBlock result = m_proc.addBlock(m_frequency);
+
+ if (!m_nextBlock)
+ m_blockOrder.append(result);
+ else
+ m_blockOrder.insertBefore(m_nextBlock, result);
+
+ return result;
+}
+
+void Output::applyBlockOrder()
+{
+ m_proc.setBlockOrder(m_blockOrder);
+}
+
</ins><span class="cx"> LBasicBlock Output::appendTo(LBasicBlock block, LBasicBlock nextBlock)
</span><span class="cx"> {
</span><span class="cx"> appendTo(block);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreftlFTLB3Outputh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ftl/FTLB3Output.h (195584 => 195585)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ftl/FTLB3Output.h 2016-01-26 07:32:28 UTC (rev 195584)
+++ trunk/Source/JavaScriptCore/ftl/FTLB3Output.h 2016-01-26 08:17:31 UTC (rev 195585)
</span><span class="lines">@@ -53,6 +53,7 @@
</span><span class="cx"> #include "FTLValueFromBlock.h"
</span><span class="cx"> #include "FTLWeight.h"
</span><span class="cx"> #include "FTLWeightedTarget.h"
</span><ins>+#include <wtf/OrderMaker.h>
</ins><span class="cx"> #include <wtf/StringPrintStream.h>
</span><span class="cx">
</span><span class="cx"> // FIXME: remove this once everything can be generated through B3.
</span><span class="lines">@@ -82,11 +83,7 @@
</span><span class="cx"> m_frequency = value;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- LBasicBlock newBlock(const char* name = "")
- {
- UNUSED_PARAM(name);
- return m_proc.addBlock(m_frequency);
- }
</del><ins>+ LBasicBlock newBlock(const char* name = "");
</ins><span class="cx">
</span><span class="cx"> LBasicBlock insertNewBlocksBefore(LBasicBlock nextBlock)
</span><span class="cx"> {
</span><span class="lines">@@ -95,6 +92,8 @@
</span><span class="cx"> return lastNextBlock;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ void applyBlockOrder();
+
</ins><span class="cx"> LBasicBlock appendTo(LBasicBlock, LBasicBlock nextBlock);
</span><span class="cx"> void appendTo(LBasicBlock);
</span><span class="cx">
</span><span class="lines">@@ -469,6 +468,8 @@
</span><span class="cx"> double m_frequency { 1 };
</span><span class="cx">
</span><span class="cx"> private:
</span><ins>+ OrderMaker<LBasicBlock> m_blockOrder;
+
</ins><span class="cx"> template<typename Function, typename... Args>
</span><span class="cx"> LValue callWithoutSideEffects(B3::Type type, Function function, LValue arg1, Args... args)
</span><span class="cx"> {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreftlFTLLowerDFGToLLVMcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp (195584 => 195585)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp 2016-01-26 07:32:28 UTC (rev 195584)
+++ trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp 2016-01-26 08:17:31 UTC (rev 195585)
</span><span class="lines">@@ -454,6 +454,9 @@
</span><span class="cx"> // write a B3 phase that so aggressively assumes the lack of orphans that it would crash
</span><span class="cx"> // if any orphans were around. We might even have such phases already.
</span><span class="cx"> m_proc.deleteOrphans();
</span><ins>+
+ // We put the blocks into the B3 procedure in a super weird order. Now we reorder them.
+ m_out.applyBlockOrder();
</ins><span class="cx"> #endif // FTL_USES_B3
</span><span class="cx">
</span><span class="cx"> #if !FTL_USES_B3
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (195584 => 195585)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2016-01-26 07:32:28 UTC (rev 195584)
+++ trunk/Source/WTF/ChangeLog 2016-01-26 08:17:31 UTC (rev 195585)
</span><span class="lines">@@ -1,3 +1,43 @@
</span><ins>+2016-01-25 Filip Pizlo <fpizlo@apple.com>
+
+ FTLB3Output should maintain good block order like the LLVM one does
+ https://bugs.webkit.org/show_bug.cgi?id=152222
+
+ Reviewed by Geoffrey Garen.
+
+ In the FTL we need to be able to construct a list by inserting elements before other
+ specific elements. We didn't already have a scalable way to do this, so this adds such a
+ data structure to WTF. This also has changes to SentinelLinkedList to make it support
+ these kinds of insertions.
+
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/OrderMaker.h: Added.
+ (WTF::OrderMaker::Node::Node):
+ (WTF::OrderMaker::OrderMaker):
+ (WTF::OrderMaker::prepend):
+ (WTF::OrderMaker::append):
+ (WTF::OrderMaker::insertBefore):
+ (WTF::OrderMaker::insertAfter):
+ (WTF::OrderMaker::iterator::iterator):
+ (WTF::OrderMaker::iterator::operator*):
+ (WTF::OrderMaker::iterator::operator++):
+ (WTF::OrderMaker::iterator::operator==):
+ (WTF::OrderMaker::iterator::operator!=):
+ (WTF::OrderMaker::begin):
+ (WTF::OrderMaker::end):
+ (WTF::OrderMaker::newNode):
+ * wtf/SentinelLinkedList.h:
+ (WTF::BasicRawSentinelNode::isOnList):
+ (WTF::BasicRawSentinelNode<T>::remove):
+ (WTF::BasicRawSentinelNode<T>::prepend):
+ (WTF::BasicRawSentinelNode<T>::append):
+ (WTF::RawNode>::SentinelLinkedList):
+ (WTF::RawNode>::push):
+ (WTF::RawNode>::append):
+ (WTF::RawNode>::remove):
+ (WTF::RawNode>::prepend):
+ (WTF::RawNode>::isOnList):
+
</ins><span class="cx"> 2016-01-25 Alex Christensen <achristensen@webkit.org>
</span><span class="cx">
</span><span class="cx"> [Win] Copy forwarding headers before building a project
</span></span></pre></div>
<a id="trunkSourceWTFWTFxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (195584 => 195585)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-01-26 07:32:28 UTC (rev 195584)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-01-26 08:17:31 UTC (rev 195585)
</span><span class="lines">@@ -36,6 +36,7 @@
</span><span class="cx"> 0F8F2B92172E0103007DBDA5 /* CompilationThread.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F8F2B8F172E00F0007DBDA5 /* CompilationThread.cpp */; };
</span><span class="cx"> 0F8F2B9C172F2596007DBDA5 /* ConversionMode.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F8F2B9B172F2594007DBDA5 /* ConversionMode.h */; };
</span><span class="cx"> 0F93274B1C17F4B700CF6564 /* Box.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F93274A1C17F4B700CF6564 /* Box.h */; };
</span><ins>+ 0F9495841C571CC900413A48 /* OrderMaker.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F9495831C571CC900413A48 /* OrderMaker.h */; };
</ins><span class="cx"> 0F9D3360165DBA73005AD387 /* FilePrintStream.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F9D335B165DBA73005AD387 /* FilePrintStream.cpp */; };
</span><span class="cx"> 0F9D3361165DBA73005AD387 /* FilePrintStream.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F9D335C165DBA73005AD387 /* FilePrintStream.h */; };
</span><span class="cx"> 0F9D3362165DBA73005AD387 /* PrintStream.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F9D335D165DBA73005AD387 /* PrintStream.cpp */; };
</span><span class="lines">@@ -342,6 +343,7 @@
</span><span class="cx"> 0F8F2B90172E00F0007DBDA5 /* CompilationThread.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = CompilationThread.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F8F2B9B172F2594007DBDA5 /* ConversionMode.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = ConversionMode.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F93274A1C17F4B700CF6564 /* Box.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Box.h; sourceTree = "<group>"; };
</span><ins>+ 0F9495831C571CC900413A48 /* OrderMaker.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = OrderMaker.h; sourceTree = "<group>"; };
</ins><span class="cx"> 0F9D335B165DBA73005AD387 /* FilePrintStream.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = FilePrintStream.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F9D335C165DBA73005AD387 /* FilePrintStream.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FilePrintStream.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F9D335D165DBA73005AD387 /* PrintStream.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = PrintStream.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -850,6 +852,7 @@
</span><span class="cx"> A8A472D6151A825B004123FF /* NumberOfCores.h */,
</span><span class="cx"> 7E29C33D15FFD79B00516D61 /* ObjcRuntimeExtras.h */,
</span><span class="cx"> 1AFDE6521953B23D00C48FFA /* Optional.h */,
</span><ins>+ 0F9495831C571CC900413A48 /* OrderMaker.h */,
</ins><span class="cx"> A8A472D7151A825B004123FF /* OSAllocator.h */,
</span><span class="cx"> A8A472D8151A825B004123FF /* OSAllocatorPosix.cpp */,
</span><span class="cx"> 7CBBA07319BB7FDC00BBF025 /* OSObjectPtr.h */,
</span><span class="lines">@@ -1208,6 +1211,7 @@
</span><span class="cx"> A8A473EA151A825B004123FF /* MD5.h in Headers */,
</span><span class="cx"> CD5497AD15857D0300B5BC30 /* MediaTime.h in Headers */,
</span><span class="cx"> A8A473EB151A825B004123FF /* MessageQueue.h in Headers */,
</span><ins>+ 0F9495841C571CC900413A48 /* OrderMaker.h in Headers */,
</ins><span class="cx"> A8A473ED151A825B004123FF /* MetaAllocator.h in Headers */,
</span><span class="cx"> A8A473EE151A825B004123FF /* MetaAllocatorHandle.h in Headers */,
</span><span class="cx"> FE8225311B2A1E5B00BA68FD /* NakedPtr.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceWTFwtfCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/CMakeLists.txt (195584 => 195585)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/CMakeLists.txt 2016-01-26 07:32:28 UTC (rev 195584)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2016-01-26 08:17:31 UTC (rev 195585)
</span><span class="lines">@@ -60,6 +60,7 @@
</span><span class="cx"> NumberOfCores.h
</span><span class="cx"> OSAllocator.h
</span><span class="cx"> OSRandomSource.h
</span><ins>+ OrderMaker.h
</ins><span class="cx"> PageAllocation.h
</span><span class="cx"> PageBlock.h
</span><span class="cx"> PageReservation.h
</span></span></pre></div>
<a id="trunkSourceWTFwtfOrderMakerh"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/OrderMaker.h (0 => 195585)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/OrderMaker.h (rev 0)
+++ trunk/Source/WTF/wtf/OrderMaker.h 2016-01-26 08:17:31 UTC (rev 195585)
</span><span class="lines">@@ -0,0 +1,143 @@
</span><ins>+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef WTF_OrderMaker_h
+#define WTF_OrderMaker_h
+
+#include <wtf/Bag.h>
+#include <wtf/HashMap.h>
+#include <wtf/Noncopyable.h>
+#include <wtf/SentinelLinkedList.h>
+
+namespace WTF {
+
+// This is a collection that is meant to be used for building up lists in a certain order. It's
+// not an efficient data structure for storing lists, but if you need to build a list by doing
+// operations like insertBefore(existingValue, newValue), then this class is a good intermediate
+// helper. Note that the type it operates on must be usable as a HashMap key.
+template<typename T>
+class OrderMaker {
+ WTF_MAKE_NONCOPYABLE(OrderMaker);
+
+ struct Node : BasicRawSentinelNode<Node> {
+ Node(SentinelTag)
+ {
+ }
+
+ Node()
+ {
+ }
+
+ T payload;
+ };
+
+public:
+ OrderMaker()
+ {
+ }
+
+ void prepend(T value)
+ {
+ m_list.push(newNode(value));
+ }
+
+ void append(T value)
+ {
+ m_list.append(newNode(value));
+ }
+
+ void insertBefore(T existingValue, T newValue)
+ {
+ Node* node = m_map.get(existingValue);
+ ASSERT(node);
+ node->prepend(newNode(newValue));
+ }
+
+ void insertAfter(T existingValue, T newValue)
+ {
+ Node* node = m_map.get(existingValue);
+ ASSERT(node);
+ node->append(newNode(newValue));
+ }
+
+ class iterator {
+ public:
+ iterator()
+ {
+ }
+
+ iterator(Node* node)
+ : m_node(node)
+ {
+ }
+
+ const T& operator*()
+ {
+ return m_node->payload;
+ }
+
+ iterator& operator++()
+ {
+ m_node = m_node->next();
+ return *this;
+ }
+
+ bool operator==(const iterator& other) const
+ {
+ return m_node == other.m_node;
+ }
+
+ bool operator!=(const iterator& other) const
+ {
+ return !(*this == other);
+ }
+
+ private:
+ Node* m_node { nullptr };
+ };
+
+ iterator begin() const { return iterator(const_cast<SentinelLinkedList<Node>&>(m_list).begin()); }
+ iterator end() const { return iterator(const_cast<SentinelLinkedList<Node>&>(m_list).end()); }
+
+private:
+ Node* newNode(T value)
+ {
+ Node* result = m_nodes.add();
+ result->payload = value;
+ m_map.set(value, result);
+ return result;
+ }
+
+ HashMap<T, Node*> m_map;
+ Bag<Node> m_nodes; // FIXME: We could just manually free the contents of the linked list.
+ SentinelLinkedList<Node> m_list;
+};
+
+} // namespace WTF
+
+using WTF::OrderMaker;
+
+#endif // WTF_OrderMaker_h
+
</ins></span></pre></div>
<a id="trunkSourceWTFwtfSentinelLinkedListh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/SentinelLinkedList.h (195584 => 195585)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/SentinelLinkedList.h 2016-01-26 07:32:28 UTC (rev 195584)
+++ trunk/Source/WTF/wtf/SentinelLinkedList.h 2016-01-26 08:17:31 UTC (rev 195585)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2011 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2011, 2016 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -70,6 +70,9 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void remove();
</span><ins>+
+ void prepend(BasicRawSentinelNode*);
+ void append(BasicRawSentinelNode*);
</ins><span class="cx">
</span><span class="cx"> private:
</span><span class="cx"> BasicRawSentinelNode* m_next;
</span><span class="lines">@@ -82,8 +85,15 @@
</span><span class="cx">
</span><span class="cx"> SentinelLinkedList();
</span><span class="cx">
</span><ins>+ // Pushes to the front of the list. It's totally backwards from what you'd expect.
</ins><span class="cx"> void push(T*);
</span><ins>+
+ // Appends to the end of the list.
+ void append(T*);
+
</ins><span class="cx"> static void remove(T*);
</span><ins>+ static void prepend(T* existingNode, T* newNode);
+ static void append(T* existingNode, T* newNode);
</ins><span class="cx">
</span><span class="cx"> bool isOnList(T*);
</span><span class="cx">
</span><span class="lines">@@ -102,6 +112,18 @@
</span><span class="cx"> SentinelLinkedList<T, BasicRawSentinelNode<T>>::remove(static_cast<T*>(this));
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+template <typename T> void BasicRawSentinelNode<T>::prepend(BasicRawSentinelNode* node)
+{
+ SentinelLinkedList<T, BasicRawSentinelNode<T>>::prepend(
+ static_cast<T*>(this), static_cast<T*>(node));
+}
+
+template <typename T> void BasicRawSentinelNode<T>::append(BasicRawSentinelNode* node)
+{
+ SentinelLinkedList<T, BasicRawSentinelNode<T>>::append(
+ static_cast<T*>(this), static_cast<T*>(node));
+}
+
</ins><span class="cx"> template <typename T, typename RawNode> inline SentinelLinkedList<T, RawNode>::SentinelLinkedList()
</span><span class="cx"> : m_headSentinel(Sentinel)
</span><span class="cx"> , m_tailSentinel(Sentinel)
</span><span class="lines">@@ -139,6 +161,22 @@
</span><span class="cx"> next->setPrev(node);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+template <typename T, typename RawNode> inline void SentinelLinkedList<T, RawNode>::append(T* node)
+{
+ ASSERT(node);
+ ASSERT(!node->prev());
+ ASSERT(!node->next());
+
+ RawNode* prev = m_tailSentinel.prev();
+ RawNode* next = &m_tailSentinel;
+
+ node->setPrev(prev);
+ node->setNext(next);
+
+ prev->setNext(node);
+ next->setPrev(node);
+}
+
</ins><span class="cx"> template <typename T, typename RawNode> inline void SentinelLinkedList<T, RawNode>::remove(T* node)
</span><span class="cx"> {
</span><span class="cx"> ASSERT(node);
</span><span class="lines">@@ -155,6 +193,44 @@
</span><span class="cx"> node->setNext(0);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+template <typename T, typename RawNode>
+inline void SentinelLinkedList<T, RawNode>::prepend(T* existingNode, T* newNode)
+{
+ ASSERT(existingNode);
+ ASSERT(!!existingNode->prev());
+ ASSERT(!!existingNode->next());
+ ASSERT(newNode);
+ ASSERT(!newNode->prev());
+ ASSERT(!newNode->next());
+
+ RawNode* prev = existingNode->prev();
+
+ newNode->setNext(existingNode);
+ newNode->setPrev(prev);
+
+ prev->setNext(newNode);
+ existingNode->setPrev(newNode);
+}
+
+template <typename T, typename RawNode>
+inline void SentinelLinkedList<T, RawNode>::append(T* existingNode, T* newNode)
+{
+ ASSERT(existingNode);
+ ASSERT(!!existingNode->prev());
+ ASSERT(!!existingNode->next());
+ ASSERT(newNode);
+ ASSERT(!newNode->prev());
+ ASSERT(!newNode->next());
+
+ RawNode* next = existingNode->next();
+
+ newNode->setNext(next);
+ newNode->setPrev(existingNode);
+
+ next->setPrev(newNode);
+ existingNode->setNext(newNode);
+}
+
</ins><span class="cx"> template <typename T, typename RawNode> inline bool SentinelLinkedList<T, RawNode>::isOnList(T* node)
</span><span class="cx"> {
</span><span class="cx"> if (!node->isOnList())
</span></span></pre>
</div>
</div>
</body>
</html>