<!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>[171051] branches/ftlopt/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/171051">171051</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2014-07-13 10:18:00 -0700 (Sun, 13 Jul 2014)</dd>
</dl>
<h3>Log Message</h3>
<pre>Merge trunk <a href="http://trac.webkit.org/projects/webkit/changeset/171049">r171049</a>.
2014-07-13 Filip Pizlo <fpizlo@apple.com>
HashMap should have removeIf()
https://bugs.webkit.org/show_bug.cgi?id=134870
Reviewed by Sam Weinig.
Expose a new HashMap method, called removeIf(), which allows you to do an efficient
pass over the map and remove a bunch of things at once. This is used by DFG GCSE as
part of https://bugs.webkit.org/show_bug.cgi?id=134677.
* wtf/HashMap.h:
(WTF::X>::removeIf):
* wtf/HashTable.h:
(WTF::KeyTraits>::removeIf):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#branchesftloptSourceJavaScriptCoredfgDFGCSEPhasecpp">branches/ftlopt/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp</a></li>
<li><a href="#branchesftloptSourceWTFChangeLog">branches/ftlopt/Source/WTF/ChangeLog</a></li>
<li><a href="#branchesftloptSourceWTFwtfHashMaph">branches/ftlopt/Source/WTF/wtf/HashMap.h</a></li>
<li><a href="#branchesftloptSourceWTFwtfHashTableh">branches/ftlopt/Source/WTF/wtf/HashTable.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="branchesftloptSourceJavaScriptCoredfgDFGCSEPhasecpp"></a>
<div class="modfile"><h4>Modified: branches/ftlopt/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp (171050 => 171051)</h4>
<pre class="diff"><span>
<span class="info">--- branches/ftlopt/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp 2014-07-13 17:09:13 UTC (rev 171050)
+++ branches/ftlopt/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp 2014-07-13 17:18:00 UTC (rev 171051)
</span><span class="lines">@@ -29,6 +29,7 @@
</span><span class="cx"> #if ENABLE(DFG_JIT)
</span><span class="cx">
</span><span class="cx"> #include "DFGAbstractHeap.h"
</span><ins>+#include "DFGClobberSet.h"
</ins><span class="cx"> #include "DFGClobberize.h"
</span><span class="cx"> #include "DFGEdgeUsesStructure.h"
</span><span class="cx"> #include "DFGGraph.h"
</span><span class="lines">@@ -39,984 +40,479 @@
</span><span class="cx">
</span><span class="cx"> namespace JSC { namespace DFG {
</span><span class="cx">
</span><del>-class CSEPhase : public Phase {
</del><ins>+// This file contains two CSE implementations: local (LCSE) and global (GCSE). LCSE typically runs
+// when we're in DFG mode, i.e. we want to compile quickly. LCSE contains a lot of optimizations
+// for compile time. GCSE, on the other hand, is fairly straight-forward. It will find more
+// optimization opportunities by virtue of being global.
+
+namespace {
+
+const bool verbose = false;
+
+class ClobberFilter {
</ins><span class="cx"> public:
</span><del>- CSEPhase(Graph& graph)
- : Phase(graph, "common subexpression elimination")
</del><ins>+ ClobberFilter(AbstractHeap heap)
+ : m_heap(heap)
</ins><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><del>- bool run()
</del><ins>+ bool operator()(const ImpureMap::KeyValuePairType& pair)
</ins><span class="cx"> {
</span><del>- ASSERT(m_graph.m_fixpointState != BeforeFixpoint);
-
- m_changed = false;
-
- m_graph.clearReplacements();
-
- if (m_graph.m_form == SSA) {
- Vector<BasicBlock*> depthFirst;
- m_graph.getBlocksInDepthFirstOrder(depthFirst);
- for (unsigned i = 0; i < depthFirst.size(); ++i)
- performBlockCSE(depthFirst[i]);
- } else {
- for (unsigned blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)
- performBlockCSE(m_graph.block(blockIndex));
- }
-
- return m_changed;
</del><ins>+ return m_heap.overlaps(pair.key.heap());
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> private:
</span><del>-
- unsigned endIndexForPureCSE()
</del><ins>+ AbstractHeap m_heap;
+};
+
+inline void clobber(ImpureMap& map, AbstractHeap heap)
+{
+ ClobberFilter filter(heap);
+ map.removeIf(filter);
+}
+
+class LCSEPhase : public Phase {
+public:
+ LCSEPhase(Graph& graph)
+ : Phase(graph, "local common subexpression elimination")
+ , m_smallBlock(graph)
+ , m_largeBlock(graph)
</ins><span class="cx"> {
</span><del>- unsigned result = m_lastSeen[m_currentNode->op()];
- if (result == UINT_MAX)
- result = 0;
- else
- result++;
- ASSERT(result <= m_indexInBlock);
- return result;
</del><span class="cx"> }
</span><del>-
- Node* pureCSE(Node* node)
</del><ins>+
+ bool run()
</ins><span class="cx"> {
</span><del>- Edge child1 = node->child1().sanitized();
- Edge child2 = node->child2().sanitized();
- Edge child3 = node->child3().sanitized();
</del><ins>+ ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
+ ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == LoadStore);
</ins><span class="cx">
</span><del>- for (unsigned i = endIndexForPureCSE(); i--;) {
- Node* otherNode = m_currentBlock->at(i);
- if (otherNode == child1 || otherNode == child2 || otherNode == child3)
- break;
-
- if (node->op() != otherNode->op())
</del><ins>+ bool changed = false;
+
+ m_graph.clearReplacements();
+
+ for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
</ins><span class="cx"> continue;
</span><span class="cx">
</span><del>- Edge otherChild = otherNode->child1().sanitized();
- if (!otherChild)
- return otherNode;
- if (otherChild != child1)
- continue;
-
- otherChild = otherNode->child2().sanitized();
- if (!otherChild)
- return otherNode;
- if (otherChild != child2)
- continue;
-
- otherChild = otherNode->child3().sanitized();
- if (!otherChild)
- return otherNode;
- if (otherChild != child3)
- continue;
-
- return otherNode;
</del><ins>+ if (block->size() <= SmallMaps::capacity)
+ changed |= m_smallBlock.run(block);
+ else
+ changed |= m_largeBlock.run(block);
</ins><span class="cx"> }
</span><del>- return 0;
</del><ins>+
+ return changed;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- Node* constantCSE(Node* node)
- {
- for (unsigned i = endIndexForPureCSE(); i--;) {
- Node* otherNode = m_currentBlock->at(i);
- if (otherNode->op() != node->op())
- continue;
-
- if (otherNode->constant() != node->constant())
- continue;
-
- return otherNode;
</del><ins>+private:
+ class SmallMaps {
+ public:
+ static const unsigned capacity = 20;
+
+ SmallMaps()
+ : m_pureLength(0)
+ , m_impureLength(0)
+ {
</ins><span class="cx"> }
</span><del>- return 0;
- }
</del><span class="cx">
</span><del>- Node* constantStoragePointerCSE(Node* node)
- {
- for (unsigned i = endIndexForPureCSE(); i--;) {
- Node* otherNode = m_currentBlock->at(i);
- if (otherNode->op() != ConstantStoragePointer)
- continue;
-
- if (otherNode->storagePointer() != node->storagePointer())
- continue;
-
- return otherNode;
</del><ins>+ void clear()
+ {
+ m_pureLength = 0;
+ m_impureLength = 0;
</ins><span class="cx"> }
</span><del>- return 0;
- }
</del><span class="cx">
</span><del>- Node* getCalleeLoadElimination()
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- switch (node->op()) {
- case GetCallee:
- return node;
- default:
- break;
</del><ins>+ void write(AbstractHeap heap)
+ {
+ for (unsigned i = 0; i < m_impureLength; ++i) {
+ if (heap.overlaps(m_impureMap[i].key.heap()))
+ m_impureMap[i--] = m_impureMap[--m_impureLength];
</ins><span class="cx"> }
</span><span class="cx"> }
</span><del>- return 0;
- }
</del><span class="cx">
</span><del>- Node* getArrayLengthElimination(Node* array)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- switch (node->op()) {
- case GetArrayLength:
- if (node->child1() == array)
- return node;
- break;
-
- case PutByValDirect:
- case PutByVal:
- if (!m_graph.byValIsPure(node))
- return 0;
- if (node->arrayMode().mayStoreToHole())
- return 0;
- break;
-
- default:
- if (m_graph.clobbersWorld(node))
- return 0;
</del><ins>+ Node* addPure(PureValue value, Node* node)
+ {
+ for (unsigned i = m_pureLength; i--;) {
+ if (m_pureMap[i].key == value)
+ return m_pureMap[i].value;
</ins><span class="cx"> }
</span><ins>+
+ ASSERT(m_pureLength < capacity);
+ m_pureMap[m_pureLength++] = WTF::KeyValuePair<PureValue, Node*>(value, node);
+ return nullptr;
</ins><span class="cx"> }
</span><del>- return 0;
- }
</del><span class="cx">
</span><del>- Node* globalVarLoadElimination(WriteBarrier<Unknown>* registerPointer)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- switch (node->op()) {
- case GetGlobalVar:
- if (node->registerPointer() == registerPointer)
- return node;
- break;
- case PutGlobalVar:
- if (node->registerPointer() == registerPointer)
- return node->child1().node();
- break;
- default:
- break;
</del><ins>+ Node* addImpure(HeapLocation location, Node* node)
+ {
+ for (unsigned i = m_impureLength; i--;) {
+ if (m_impureMap[i].key == location)
+ return m_impureMap[i].value;
</ins><span class="cx"> }
</span><del>- if (m_graph.clobbersWorld(node))
- break;
</del><ins>+
+ ASSERT(m_impureLength < capacity);
+ m_impureMap[m_impureLength++] = WTF::KeyValuePair<HeapLocation, Node*>(location, node);
+ return nullptr;
</ins><span class="cx"> }
</span><del>- return 0;
- }
</del><span class="cx">
</span><del>- Node* scopedVarLoadElimination(Node* registers, int varNumber)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- switch (node->op()) {
- case GetClosureVar: {
- if (node->child1() == registers && node->varNumber() == varNumber)
- return node;
- break;
- }
- case PutClosureVar: {
- if (node->varNumber() != varNumber)
- break;
- if (node->child2() == registers)
- return node->child3().node();
- return 0;
- }
- case SetLocal: {
- VariableAccessData* variableAccessData = node->variableAccessData();
- if (variableAccessData->isCaptured()
- && variableAccessData->local() == static_cast<VirtualRegister>(varNumber))
- return 0;
- break;
- }
- default:
- break;
- }
- if (m_graph.clobbersWorld(node))
- break;
</del><ins>+ private:
+ WTF::KeyValuePair<PureValue, Node*> m_pureMap[capacity];
+ WTF::KeyValuePair<HeapLocation, Node*> m_impureMap[capacity];
+ unsigned m_pureLength;
+ unsigned m_impureLength;
+ };
+
+ class LargeMaps {
+ public:
+ LargeMaps()
+ {
</ins><span class="cx"> }
</span><del>- return 0;
- }
</del><span class="cx">
</span><del>- bool varInjectionWatchpointElimination()
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- if (node->op() == VarInjectionWatchpoint)
- return true;
- if (m_graph.clobbersWorld(node))
- break;
</del><ins>+ void clear()
+ {
+ m_pureMap.clear();
+ m_impureMap.clear();
</ins><span class="cx"> }
</span><del>- return false;
- }
</del><span class="cx">
</span><del>- Node* getByValLoadElimination(Node* child1, Node* child2, ArrayMode arrayMode)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- if (node == child1 || node == child2)
- break;
-
- switch (node->op()) {
- case GetByVal:
- if (!m_graph.byValIsPure(node))
- return 0;
- if (node->child1() == child1
- && node->child2() == child2
- && node->arrayMode().type() == arrayMode.type())
- return node;
- break;
-
- case PutByValDirect:
- case PutByVal:
- case PutByValAlias: {
- if (!m_graph.byValIsPure(node))
- return 0;
- // Typed arrays
- if (arrayMode.typedArrayType() != NotTypedArray)
- return 0;
- if (m_graph.varArgChild(node, 0) == child1
- && m_graph.varArgChild(node, 1) == child2
- && node->arrayMode().type() == arrayMode.type())
- return m_graph.varArgChild(node, 2).node();
- // We must assume that the PutByVal will clobber the location we're getting from.
- // FIXME: We can do better; if we know that the PutByVal is accessing an array of a
- // different type than the GetByVal, then we know that they won't clobber each other.
- // ... except of course for typed arrays, where all typed arrays clobber all other
- // typed arrays! An Int32Array can alias a Float64Array for example, and so on.
- return 0;
- }
- default:
- if (m_graph.clobbersWorld(node))
- return 0;
- break;
- }
</del><ins>+ void write(AbstractHeap heap)
+ {
+ clobber(m_impureMap, heap);
</ins><span class="cx"> }
</span><del>- return 0;
- }
-
- bool checkFunctionElimination(FrozenValue* function, Node* child1)
- {
- for (unsigned i = endIndexForPureCSE(); i--;) {
- Node* node = m_currentBlock->at(i);
- if (node == child1)
- break;
-
- if (node->op() == CheckFunction && node->child1() == child1 && node->function() == function)
- return true;
</del><ins>+
+ Node* addPure(PureValue value, Node* node)
+ {
+ auto result = m_pureMap.add(value, node);
+ if (result.isNewEntry)
+ return nullptr;
+ return result.iterator->value;
</ins><span class="cx"> }
</span><del>- return false;
- }
</del><span class="cx">
</span><del>- bool checkExecutableElimination(ExecutableBase* executable, Node* child1)
- {
- for (unsigned i = endIndexForPureCSE(); i--;) {
- Node* node = m_currentBlock->at(i);
- if (node == child1)
- break;
-
- if (node->op() == CheckExecutable && node->child1() == child1 && node->executable() == executable)
- return true;
</del><ins>+ Node* addImpure(HeapLocation location, Node* node)
+ {
+ auto result = m_impureMap.add(location, node);
+ if (result.isNewEntry)
+ return nullptr;
+ return result.iterator->value;
</ins><span class="cx"> }
</span><del>- return false;
- }
</del><span class="cx">
</span><del>- bool checkStructureElimination(const StructureSet& structureSet, Node* child1)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- if (node == child1)
- break;
</del><ins>+ private:
+ HashMap<PureValue, Node*> m_pureMap;
+ HashMap<HeapLocation, Node*> m_impureMap;
+ };
</ins><span class="cx">
</span><del>- switch (node->op()) {
- case CheckStructure:
- if (node->child1() == child1
- && structureSet.isSupersetOf(node->structureSet()))
- return true;
- break;
-
- case PutStructure:
- if (node->child1() == child1
- && structureSet.contains(node->transition()->next))
- return true;
- if (structureSet.contains(node->transition()->previous))
- return false;
- break;
-
- case PutByOffset:
- // Setting a property cannot change the structure.
- break;
-
- case MultiPutByOffset:
- if (node->multiPutByOffsetData().writesStructures())
- return false;
- break;
-
- case PutByValDirect:
- case PutByVal:
- case PutByValAlias:
- if (m_graph.byValIsPure(node)) {
- // If PutByVal speculates that it's accessing an array with an
- // integer index, then it's impossible for it to cause a structure
- // change.
- break;
- }
- return false;
-
- case Arrayify:
- case ArrayifyToStructure:
- // We could check if the arrayification could affect our structures.
- // But that seems like it would take Effort.
- return false;
-
- default:
- if (m_graph.clobbersWorld(node))
- return false;
- break;
- }
</del><ins>+ template<typename Maps>
+ class BlockCSE {
+ public:
+ BlockCSE(Graph& graph)
+ : m_graph(graph)
+ {
</ins><span class="cx"> }
</span><del>- return false;
- }
</del><span class="cx">
</span><del>- bool structureTransitionWatchpointElimination(Structure* structure, Node* child1)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- if (node == child1)
- break;
-
- switch (node->op()) {
- case CheckStructure:
- if (node->child1() == child1
- && node->structureSet().isSubsetOf(StructureSet(structure)))
- return true;
- break;
-
- case PutStructure:
- ASSERT(node->transition()->previous != structure);
- break;
-
- case PutByOffset:
- // Setting a property cannot change the structure.
- break;
-
- case MultiPutByOffset:
- if (node->multiPutByOffsetData().writesStructures())
- return false;
- break;
-
- case PutByValDirect:
- case PutByVal:
- case PutByValAlias:
- if (m_graph.byValIsPure(node)) {
- // If PutByVal speculates that it's accessing an array with an
- // integer index, then it's impossible for it to cause a structure
- // change.
- break;
- }
- return false;
-
- case Arrayify:
- case ArrayifyToStructure:
- // We could check if the arrayification could affect our structures.
- // But that seems like it would take Effort.
- return false;
-
- default:
- if (m_graph.clobbersWorld(node))
- return false;
- break;
</del><ins>+ bool run(BasicBlock* block)
+ {
+ m_maps.clear();
+ m_changed = false;
+
+ for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+ m_node = block->at(nodeIndex);
+ m_graph.performSubstitution(m_node);
+
+ if (m_node->op() == Identity) {
+ m_node->replaceWith(m_node->child1().node());
+ m_changed = true;
+ } else
+ clobberize(m_graph, m_node, *this);
</ins><span class="cx"> }
</span><ins>+
+ return m_changed;
</ins><span class="cx"> }
</span><del>- return false;
- }
</del><span class="cx">
</span><del>- Node* getByOffsetLoadElimination(unsigned identifierNumber, Node* base)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- if (node == base)
- break;
-
- switch (node->op()) {
- case GetByOffset:
- if (node->child2() == base
- && m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber)
- return node;
- break;
-
- case MultiGetByOffset:
- if (node->child1() == base
- && node->multiGetByOffsetData().identifierNumber == identifierNumber)
- return node;
- break;
-
- case PutByOffset:
- if (m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber) {
- if (node->child2() == base) // Must be same property storage.
- return node->child3().node();
- return 0;
- }
- break;
-
- case MultiPutByOffset:
- if (node->multiPutByOffsetData().identifierNumber == identifierNumber) {
- if (node->child1() == base)
- return node->child2().node();
- return 0;
- }
- break;
-
- case PutByValDirect:
- case PutByVal:
- case PutByValAlias:
- if (m_graph.byValIsPure(node)) {
- // If PutByVal speculates that it's accessing an array with an
- // integer index, then it's impossible for it to cause a structure
- // change.
- break;
- }
- return 0;
-
- default:
- if (m_graph.clobbersWorld(node))
- return 0;
- break;
- }
</del><ins>+ void read(AbstractHeap) { }
+
+ void write(AbstractHeap heap)
+ {
+ m_maps.write(heap);
</ins><span class="cx"> }
</span><del>- return 0;
- }
</del><span class="cx">
</span><del>- Node* getGetterSetterByOffsetLoadElimination(unsigned identifierNumber, Node* base)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- if (node == base)
- break;
</del><ins>+ void def(PureValue value)
+ {
+ Node* match = m_maps.addPure(value, m_node);
+ if (!match)
+ return;
</ins><span class="cx">
</span><del>- switch (node->op()) {
- case GetGetterSetterByOffset:
- if (node->child2() == base
- && m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber)
- return node;
- break;
-
- case PutByValDirect:
- case PutByVal:
- case PutByValAlias:
- if (m_graph.byValIsPure(node)) {
- // If PutByVal speculates that it's accessing an array with an
- // integer index, then it's impossible for it to cause a structure
- // change.
- break;
- }
- return 0;
-
- default:
- if (m_graph.clobbersWorld(node))
- return 0;
- break;
</del><ins>+ m_node->replaceWith(match);
+ m_changed = true;
+ }
+
+ void def(HeapLocation location, Node* value)
+ {
+ Node* match = m_maps.addImpure(location, value);
+ if (!match)
+ return;
+
+ if (m_node->op() == GetLocal) {
+ // For uncaptured locals, usually the CPS rethreading phase does this. But it's OK
+ // for us to mess with locals - regardless of their capturedness - so long as:
+ //
+ // - We dethread the graph. Any changes we make may invalidate the assumptions of
+ // our CPS form, particularly if this GetLocal is linked to the variablesAtTail.
+ //
+ // - We don't introduce a Phantom for the child of the GetLocal. This wouldn't be
+ // totally wrong but it would pessimize the code. Just because there is a
+ // GetLocal doesn't mean that the child was live. Simply rerouting the all uses
+ // of this GetLocal will preserve the live-at-exit information just fine.
+ //
+ // We accomplish the latter by just clearing the child; then the Phantom that we
+ // introduce won't have children and so it will eventually just be deleted.
+
+ m_node->child1() = Edge();
+ m_graph.dethread();
</ins><span class="cx"> }
</span><ins>+
+ m_node->replaceWith(match);
+ m_changed = true;
</ins><span class="cx"> }
</span><del>- return 0;
- }
</del><span class="cx">
</span><del>- Node* getPropertyStorageLoadElimination(Node* child1)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- if (node == child1)
- break;
</del><ins>+ private:
+ Graph& m_graph;
+
+ bool m_changed;
+ Node* m_node;
+
+ Maps m_maps;
+ };
</ins><span class="cx">
</span><del>- switch (node->op()) {
- case GetButterfly:
- if (node->child1() == child1)
- return node;
- break;
</del><ins>+ BlockCSE<SmallMaps> m_smallBlock;
+ BlockCSE<LargeMaps> m_largeBlock;
+};
</ins><span class="cx">
</span><del>- case AllocatePropertyStorage:
- case ReallocatePropertyStorage:
- // If we can cheaply prove this is a change to our object's storage, we
- // can optimize and use its result.
- if (node->child1() == child1)
- return node;
- // Otherwise, we currently can't prove that this doesn't change our object's
- // storage, so we conservatively assume that it may change the storage
- // pointer of any object, including ours.
- return 0;
-
- case PutByValDirect:
- case PutByVal:
- case PutByValAlias:
- if (m_graph.byValIsPure(node)) {
- // If PutByVal speculates that it's accessing an array with an
- // integer index, then it's impossible for it to cause a structure
- // change.
- break;
- }
- return 0;
-
- case Arrayify:
- case ArrayifyToStructure:
- // We could check if the arrayification could affect our butterfly.
- // But that seems like it would take Effort.
- return 0;
-
- case MultiPutByOffset:
- if (node->multiPutByOffsetData().reallocatesStorage())
- return 0;
- break;
-
- default:
- if (m_graph.clobbersWorld(node))
- return 0;
- break;
- }
- }
- return 0;
</del><ins>+class GCSEPhase : public Phase {
+public:
+ GCSEPhase(Graph& graph)
+ : Phase(graph, "global common subexpression elimination")
+ {
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- bool checkArrayElimination(Node* child1, ArrayMode arrayMode)
</del><ins>+ bool run()
</ins><span class="cx"> {
</span><del>- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- if (node == child1)
- break;
</del><ins>+ ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
+ ASSERT(m_graph.m_form == SSA);
+
+ m_graph.clearReplacements();
+ m_graph.initializeNodeOwners();
+ m_graph.m_dominators.computeIfNecessary(m_graph);
+
+ Vector<BasicBlock*> preOrder;
+ m_graph.getBlocksInPreOrder(preOrder);
+
+ m_impureDataMap.resize(m_graph.numBlocks());
+
+ // First figure out what gets clobbered by blocks. Node that this uses the preOrder list
+ // for convenience only.
+ for (unsigned i = preOrder.size(); i--;) {
+ m_block = preOrder[i];
+ m_impureData = &m_impureDataMap[m_block->index];
+ for (unsigned nodeIndex = m_block->size(); nodeIndex--;)
+ addWrites(m_graph, m_block->at(nodeIndex), m_impureData->writes);
+ }
+
+ // Based on my experience doing this before, what follows might have to be made iterative.
+ // But it feels like, right now, this works as a single pass because we only turn a node
+ // into a value or heap location after we have performed substitutions on that node's
+ // children.
+
+ for (unsigned i = 0; i < preOrder.size(); ++i) {
+ m_block = preOrder[i];
+ m_impureData = &m_impureDataMap[m_block->index];
+ m_writesSoFar.clear();
+
+ if (verbose)
+ dataLog("Processing block ", *m_block, ":\n");
</ins><span class="cx">
</span><del>- switch (node->op()) {
- case CheckArray:
- if (node->child1() == child1 && node->arrayMode() == arrayMode)
- return true;
- break;
</del><ins>+ for (unsigned nodeIndex = 0; nodeIndex < m_block->size(); ++nodeIndex) {
+ m_node = m_block->at(nodeIndex);
+ if (verbose)
+ dataLog(" Looking at node ", m_node, ":\n");
</ins><span class="cx">
</span><del>- case Arrayify:
- case ArrayifyToStructure:
- // We could check if the arrayification could affect our array.
- // But that seems like it would take Effort.
- return false;
</del><ins>+ m_graph.performSubstitution(m_node);
</ins><span class="cx">
</span><del>- default:
- if (m_graph.clobbersWorld(node))
- return false;
- break;
</del><ins>+ if (m_node->op() == Identity) {
+ m_node->replaceWith(m_node->child1().node());
+ m_changed = true;
+ } else
+ clobberize(m_graph, m_node, *this);
</ins><span class="cx"> }
</span><ins>+
+ m_impureData->didVisit = true;
</ins><span class="cx"> }
</span><del>- return false;
</del><ins>+
+ return m_changed;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- Node* getIndexedPropertyStorageLoadElimination(Node* child1, ArrayMode arrayMode)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- if (node == child1)
- break;
-
- switch (node->op()) {
- case GetIndexedPropertyStorage: {
- if (node->child1() == child1 && node->arrayMode() == arrayMode)
- return node;
- break;
- }
-
- default:
- if (m_graph.clobbersWorld(node))
- return 0;
- break;
- }
- }
- return 0;
- }
</del><ins>+ void read(AbstractHeap) { }
</ins><span class="cx">
</span><del>- Node* getInternalFieldLoadElimination(NodeType op, Node* child1)
</del><ins>+ void write(AbstractHeap heap)
</ins><span class="cx"> {
</span><del>- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- if (node == child1)
- break;
-
- if (node->op() == op && node->child1() == child1)
- return node;
-
- if (m_graph.clobbersWorld(node))
- return 0;
- }
- return 0;
</del><ins>+ clobber(m_impureData->availableAtTail, heap);
+ m_writesSoFar.add(heap);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- Node* getMyScopeLoadElimination()
</del><ins>+ void def(PureValue value)
</ins><span class="cx"> {
</span><del>- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- switch (node->op()) {
- case CreateActivation:
- // This may cause us to return a different scope.
- return 0;
- case GetMyScope:
- return node;
- default:
- break;
- }
</del><ins>+ auto result = m_pureValues.add(value, Vector<Node*>());
+ if (result.isNewEntry) {
+ result.iterator->value.append(m_node);
+ return;
</ins><span class="cx"> }
</span><del>- return 0;
- }
-
- Node* getLocalLoadElimination(VirtualRegister local, Node*& relevantLocalOp, bool careAboutClobbering)
- {
- relevantLocalOp = 0;
</del><span class="cx">
</span><del>- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- switch (node->op()) {
- case GetLocal:
- if (node->local() == local) {
- relevantLocalOp = node;
- return node;
- }
- break;
-
- case GetLocalUnlinked:
- if (node->unlinkedLocal() == local) {
- relevantLocalOp = node;
- return node;
- }
- break;
-
- case SetLocal:
- if (node->local() == local) {
- relevantLocalOp = node;
- return node->child1().node();
- }
- break;
-
- case GetClosureVar:
- case PutClosureVar:
- if (static_cast<VirtualRegister>(node->varNumber()) == local)
- return 0;
- break;
-
- default:
- if (careAboutClobbering && m_graph.clobbersWorld(node))
- return 0;
- break;
</del><ins>+ for (unsigned i = result.iterator->value.size(); i--;) {
+ Node* candidate = result.iterator->value[i];
+ if (m_graph.m_dominators.dominates(candidate->owner, m_block)) {
+ m_node->replaceWith(candidate);
+ m_changed = true;
+ return;
</ins><span class="cx"> }
</span><span class="cx"> }
</span><del>- return 0;
</del><ins>+
+ result.iterator->value.append(m_node);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- bool invalidationPointElimination()
</del><ins>+ Node* findReplacement(HeapLocation location)
</ins><span class="cx"> {
</span><del>- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- if (node->op() == InvalidationPoint)
- return true;
- if (writesOverlap(m_graph, node, Watchpoint_fire))
- break;
</del><ins>+ Node* match = m_impureData->availableAtTail.get(location);
+ if (match) {
+ if (verbose)
+ dataLog(" Found local match: ", match, "\n");
+ return match;
</ins><span class="cx"> }
</span><del>- return false;
- }
-
- bool setReplacement(Node* replacement)
- {
- if (!replacement)
- return false;
</del><span class="cx">
</span><del>- m_currentNode->convertToPhantom();
</del><ins>+ if (m_writesSoFar.overlaps(location.heap())) {
+ if (verbose)
+ dataLog(" Not looking globally because of local clobber: ", m_writesSoFar, "\n");
+ return nullptr;
+ }
</ins><span class="cx">
</span><del>- // At this point we will eliminate all references to this node.
- m_currentNode->replacement = replacement;
</del><ins>+ // This perfoms a backward search to find some possible def() that matches our heap
+ // location. As soon as it finds a possible def(), it assumes that this one must be the
+ // match and completes the search by halting at this block. As soon as it finds a write()
+ // that overlaps the location's heap, it stops, assuming that there is no possible match.
</ins><span class="cx">
</span><del>- m_changed = true;
</del><ins>+ Vector<BasicBlock*, 8> worklist;
+ Vector<BasicBlock*, 8> seenList;
+ BitVector seen;
</ins><span class="cx">
</span><del>- return true;
- }
-
- void eliminate()
- {
- ASSERT(m_currentNode->mustGenerate());
- m_currentNode->convertToPhantom();
</del><ins>+ for (unsigned i = m_block->predecessors.size(); i--;) {
+ BasicBlock* predecessor = m_block->predecessors[i];
+ if (!seen.get(predecessor->index)) {
+ worklist.append(predecessor);
+ seen.set(predecessor->index);
+ }
+ }
</ins><span class="cx">
</span><del>- m_changed = true;
- }
-
- void eliminate(Node* node, NodeType phantomType = Phantom)
- {
- if (!node)
- return;
- ASSERT(node->mustGenerate());
- node->setOpAndDefaultFlags(phantomType);
-
- m_changed = true;
- }
-
- void performNodeCSE(Node* node)
- {
- m_graph.performSubstitution(node);
-
- switch (node->op()) {
-
- case Identity:
- setReplacement(node->child1().node());
- break;
</del><ins>+ while (!worklist.isEmpty()) {
+ BasicBlock* block = worklist.takeLast();
+ seenList.append(block);
</ins><span class="cx">
</span><del>- // Handle the pure nodes. These nodes never have any side-effects.
- case BitAnd:
- case BitOr:
- case BitXor:
- case BitRShift:
- case BitLShift:
- case BitURShift:
- case ArithAbs:
- case ArithMin:
- case ArithMax:
- case ArithSqrt:
- case ArithFRound:
- case ArithSin:
- case ArithCos:
- case StringCharAt:
- case StringCharCodeAt:
- case IsUndefined:
- case IsBoolean:
- case IsNumber:
- case IsString:
- case IsObject:
- case IsFunction:
- case LogicalNot:
- case SkipTopScope:
- case SkipScope:
- case GetClosureRegisters:
- case GetScope:
- case TypeOf:
- case CompareEqConstant:
- case ValueToInt32:
- case MakeRope:
- case DoubleRep:
- case ValueRep:
- case Int52Rep:
- setReplacement(pureCSE(node));
- break;
</del><ins>+ if (verbose)
+ dataLog(" Searching in block ", *block, "\n");
+ ImpureBlockData& data = m_impureDataMap[block->index];
</ins><span class="cx">
</span><del>- case ArithAdd:
- case ArithSub:
- case ArithNegate:
- case ArithMul:
- case ArithDiv:
- case ArithMod:
- case UInt32ToNumber:
- case DoubleAsInt32: {
- Node* candidate = pureCSE(node);
- if (!candidate)
- break;
- if (!subsumes(candidate->arithMode(), node->arithMode())) {
- if (!subsumes(node->arithMode(), candidate->arithMode()))
- break;
- candidate->setArithMode(node->arithMode());
</del><ins>+ if (m_graph.m_dominators.dominates(block, m_block) && block != m_block) {
+ if (verbose)
+ dataLog(" It strictly dominates.\n");
+ DFG_ASSERT(m_graph, m_node, data.didVisit);
+ DFG_ASSERT(m_graph, m_node, !match);
+ match = data.availableAtTail.get(location);
+ if (verbose)
+ dataLog(" Availability: ", match, "\n");
+ if (match) {
+ // Don't examine the predecessors of a match. At this point we just want to
+ // establish that other blocks on the path from here to there don't clobber
+ // the location we're interested in.
+ continue;
+ }
</ins><span class="cx"> }
</span><del>- setReplacement(candidate);
- break;
- }
</del><span class="cx">
</span><del>- case GetCallee:
- setReplacement(getCalleeLoadElimination());
- break;
-
- case GetLocal: {
- VariableAccessData* variableAccessData = node->variableAccessData();
- if (!variableAccessData->isCaptured())
- break;
- Node* relevantLocalOp;
- Node* possibleReplacement = getLocalLoadElimination(variableAccessData->local(), relevantLocalOp, variableAccessData->isCaptured());
- if (!relevantLocalOp)
- break;
- if (relevantLocalOp->op() != GetLocalUnlinked
- && relevantLocalOp->variableAccessData() != variableAccessData)
- break;
- Node* phi = node->child1().node();
- if (!setReplacement(possibleReplacement))
- break;
-
- m_graph.dethread();
-
- // If we replace a GetLocal with a GetLocalUnlinked, then turn the GetLocalUnlinked
- // into a GetLocal.
- if (relevantLocalOp->op() == GetLocalUnlinked)
- relevantLocalOp->convertToGetLocal(variableAccessData, phi);
-
- m_changed = true;
- break;
- }
-
- case GetLocalUnlinked: {
- Node* relevantLocalOpIgnored;
- setReplacement(getLocalLoadElimination(node->unlinkedLocal(), relevantLocalOpIgnored, true));
- break;
- }
-
- case JSConstant:
- case DoubleConstant:
- case Int52Constant:
- // This is strange, but necessary. Some phases will convert nodes to constants,
- // which may result in duplicated constants. We use CSE to clean this up.
- setReplacement(constantCSE(node));
- break;
-
- case ConstantStoragePointer:
- setReplacement(constantStoragePointerCSE(node));
- break;
-
- case GetArrayLength:
- setReplacement(getArrayLengthElimination(node->child1().node()));
- break;
-
- case GetMyScope:
- setReplacement(getMyScopeLoadElimination());
- break;
-
- // Handle nodes that are conditionally pure: these are pure, and can
- // be CSE'd, so long as the prediction is the one we want.
- case CompareLess:
- case CompareLessEq:
- case CompareGreater:
- case CompareGreaterEq:
- case CompareEq: {
- if (m_graph.isPredictedNumerical(node)) {
- Node* replacement = pureCSE(node);
- if (replacement && m_graph.isPredictedNumerical(replacement))
- setReplacement(replacement);
</del><ins>+ if (verbose)
+ dataLog(" Dealing with write set ", data.writes, "\n");
+ if (data.writes.overlaps(location.heap())) {
+ if (verbose)
+ dataLog(" Clobbered.\n");
+ return nullptr;
</ins><span class="cx"> }
</span><del>- break;
- }
</del><span class="cx">
</span><del>- // Finally handle heap accesses. These are not quite pure, but we can still
- // optimize them provided that some subtle conditions are met.
- case GetGlobalVar:
- setReplacement(globalVarLoadElimination(node->registerPointer()));
- break;
-
- case GetClosureVar: {
- setReplacement(scopedVarLoadElimination(node->child1().node(), node->varNumber()));
- break;
- }
-
- case VarInjectionWatchpoint:
- if (varInjectionWatchpointElimination())
- eliminate();
- break;
-
- case GetByVal:
- if (m_graph.byValIsPure(node))
- setReplacement(getByValLoadElimination(node->child1().node(), node->child2().node(), node->arrayMode()));
- break;
-
- case PutByValDirect:
- case PutByVal: {
- Edge child1 = m_graph.varArgChild(node, 0);
- Edge child2 = m_graph.varArgChild(node, 1);
- if (node->arrayMode().canCSEStorage()) {
- Node* replacement = getByValLoadElimination(child1.node(), child2.node(), node->arrayMode());
- if (!replacement)
- break;
- node->setOp(PutByValAlias);
</del><ins>+ for (unsigned i = block->predecessors.size(); i--;) {
+ BasicBlock* predecessor = block->predecessors[i];
+ if (!seen.get(predecessor->index)) {
+ worklist.append(predecessor);
+ seen.set(predecessor->index);
+ }
</ins><span class="cx"> }
</span><del>- break;
</del><span class="cx"> }
</span><del>-
- case CheckStructure:
- if (checkStructureElimination(node->structureSet(), node->child1().node()))
- eliminate();
- break;
-
- case CheckFunction:
- if (checkFunctionElimination(node->function(), node->child1().node()))
- eliminate();
- break;
-
- case CheckExecutable:
- if (checkExecutableElimination(node->executable(), node->child1().node()))
- eliminate();
- break;
-
- case CheckArray:
- if (checkArrayElimination(node->child1().node(), node->arrayMode()))
- eliminate();
- break;
-
- case GetIndexedPropertyStorage: {
- setReplacement(getIndexedPropertyStorageLoadElimination(node->child1().node(), node->arrayMode()));
- break;
- }
-
- case GetTypedArrayByteOffset:
- case GetGetter:
- case GetSetter: {
- setReplacement(getInternalFieldLoadElimination(node->op(), node->child1().node()));
- break;
- }
</del><span class="cx">
</span><del>- case GetButterfly:
- setReplacement(getPropertyStorageLoadElimination(node->child1().node()));
- break;
-
- case GetByOffset:
- setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber, node->child2().node()));
- break;
-
- case GetGetterSetterByOffset:
- setReplacement(getGetterSetterByOffsetLoadElimination(m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber, node->child2().node()));
- break;
-
- case MultiGetByOffset:
- setReplacement(getByOffsetLoadElimination(node->multiGetByOffsetData().identifierNumber, node->child1().node()));
- break;
-
- case InvalidationPoint:
- if (invalidationPointElimination())
- eliminate();
- break;
-
- default:
- // do nothing.
- break;
- }
</del><ins>+ // Cache the results for next time. We cache them both for this block and for all of our
+ // predecessors, since even though we've already visited our predecessors, our predecessors
+ // probably have successors other than us.
+ for (BasicBlock* block : seenList)
+ m_impureDataMap[block->index].availableAtTail.add(location, match);
+ m_impureData->availableAtTail.add(location, match);
</ins><span class="cx">
</span><del>- m_lastSeen[node->op()] = m_indexInBlock;
</del><ins>+ return match;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- void performBlockCSE(BasicBlock* block)
</del><ins>+ void def(HeapLocation location, Node* value)
</ins><span class="cx"> {
</span><del>- if (!block)
- return;
- if (!block->isReachable)
- return;
</del><ins>+ if (verbose)
+ dataLog(" Got heap location def: ", location, " -> ", value, "\n");
</ins><span class="cx">
</span><del>- m_currentBlock = block;
- for (unsigned i = 0; i < LastNodeType; ++i)
- m_lastSeen[i] = UINT_MAX;
</del><ins>+ Node* match = findReplacement(location);
</ins><span class="cx">
</span><del>- for (m_indexInBlock = 0; m_indexInBlock < block->size(); ++m_indexInBlock) {
- m_currentNode = block->at(m_indexInBlock);
- performNodeCSE(m_currentNode);
</del><ins>+ if (verbose)
+ dataLog(" Got match: ", match, "\n");
+
+ if (!match) {
+ auto result = m_impureData->availableAtTail.add(location, value);
+ ASSERT_UNUSED(result, result.isNewEntry);
+ return;
</ins><span class="cx"> }
</span><ins>+
+ m_node->replaceWith(match);
+ m_changed = true;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- BasicBlock* m_currentBlock;
- Node* m_currentNode;
- unsigned m_indexInBlock;
- std::array<unsigned, LastNodeType> m_lastSeen;
- bool m_changed; // Only tracks changes that have a substantive effect on other optimizations.
</del><ins>+ struct ImpureBlockData {
+ ImpureBlockData()
+ : didVisit(false)
+ {
+ }
+
+ ClobberSet writes;
+ ImpureMap availableAtTail;
+ bool didVisit;
+ };
+
+ PureMultiMap m_pureValues;
+ Vector<ImpureBlockData> m_impureDataMap;
+
+ BasicBlock* m_block;
+ Node* m_node;
+ ImpureBlockData* m_impureData;
+ ClobberSet m_writesSoFar;
+
+ bool m_changed;
</ins><span class="cx"> };
</span><span class="cx">
</span><del>-bool performCSE(Graph& graph)
</del><ins>+} // anonymous namespace
+
+bool performLCSE(Graph& graph)
</ins><span class="cx"> {
</span><del>- SamplingRegion samplingRegion("DFG CSE Phase");
- return runPhase<CSEPhase>(graph);
</del><ins>+ SamplingRegion samplingRegion("DFG LCSE Phase");
+ return runPhase<LCSEPhase>(graph);
</ins><span class="cx"> }
</span><span class="cx">
</span><ins>+bool performGCSE(Graph& graph)
+{
+ SamplingRegion samplingRegion("DFG GCSE Phase");
+ return runPhase<GCSEPhase>(graph);
+}
+
</ins><span class="cx"> } } // namespace JSC::DFG
</span><span class="cx">
</span><span class="cx"> #endif // ENABLE(DFG_JIT)
</span><del>-
-
</del></span></pre></div>
<a id="branchesftloptSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: branches/ftlopt/Source/WTF/ChangeLog (171050 => 171051)</h4>
<pre class="diff"><span>
<span class="info">--- branches/ftlopt/Source/WTF/ChangeLog 2014-07-13 17:09:13 UTC (rev 171050)
+++ branches/ftlopt/Source/WTF/ChangeLog 2014-07-13 17:18:00 UTC (rev 171051)
</span><span class="lines">@@ -1,3 +1,23 @@
</span><ins>+2014-07-13 Filip Pizlo <fpizlo@apple.com>
+
+ Merge trunk r171049.
+
+ 2014-07-13 Filip Pizlo <fpizlo@apple.com>
+
+ HashMap should have removeIf()
+ https://bugs.webkit.org/show_bug.cgi?id=134870
+
+ Reviewed by Sam Weinig.
+
+ Expose a new HashMap method, called removeIf(), which allows you to do an efficient
+ pass over the map and remove a bunch of things at once. This is used by DFG GCSE as
+ part of https://bugs.webkit.org/show_bug.cgi?id=134677.
+
+ * wtf/HashMap.h:
+ (WTF::X>::removeIf):
+ * wtf/HashTable.h:
+ (WTF::KeyTraits>::removeIf):
+
</ins><span class="cx"> 2014-06-01 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><span class="cx"> [ftlopt] AI should be able track structure sets larger than 1
</span></span></pre></div>
<a id="branchesftloptSourceWTFwtfHashMaph"></a>
<div class="modfile"><h4>Modified: branches/ftlopt/Source/WTF/wtf/HashMap.h (171050 => 171051)</h4>
<pre class="diff"><span>
<span class="info">--- branches/ftlopt/Source/WTF/wtf/HashMap.h 2014-07-13 17:09:13 UTC (rev 171050)
+++ branches/ftlopt/Source/WTF/wtf/HashMap.h 2014-07-13 17:18:00 UTC (rev 171051)
</span><span class="lines">@@ -120,6 +120,8 @@
</span><span class="cx">
</span><span class="cx"> bool remove(const KeyType&);
</span><span class="cx"> bool remove(iterator);
</span><ins>+ template<typename Functor>
+ void removeIf(const Functor& functor);
</ins><span class="cx"> void clear();
</span><span class="cx">
</span><span class="cx"> MappedType take(const KeyType&); // efficient combination of get with remove
</span><span class="lines">@@ -354,6 +356,13 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<typename T, typename U, typename V, typename W, typename X>
</span><ins>+template<typename Functor>
+inline void HashMap<T, U, V, W, X>::removeIf(const Functor& functor)
+{
+ m_impl.removeIf(functor);
+}
+
+template<typename T, typename U, typename V, typename W, typename X>
</ins><span class="cx"> inline bool HashMap<T, U, V, W, X>::remove(const KeyType& key)
</span><span class="cx"> {
</span><span class="cx"> return remove(find(key));
</span></span></pre></div>
<a id="branchesftloptSourceWTFwtfHashTableh"></a>
<div class="modfile"><h4>Modified: branches/ftlopt/Source/WTF/wtf/HashTable.h (171050 => 171051)</h4>
<pre class="diff"><span>
<span class="info">--- branches/ftlopt/Source/WTF/wtf/HashTable.h 2014-07-13 17:09:13 UTC (rev 171050)
+++ branches/ftlopt/Source/WTF/wtf/HashTable.h 2014-07-13 17:18:00 UTC (rev 171051)
</span><span class="lines">@@ -393,6 +393,8 @@
</span><span class="cx"> void remove(iterator);
</span><span class="cx"> void removeWithoutEntryConsistencyCheck(iterator);
</span><span class="cx"> void removeWithoutEntryConsistencyCheck(const_iterator);
</span><ins>+ template<typename Functor>
+ void removeIf(const Functor&);
</ins><span class="cx"> void clear();
</span><span class="cx">
</span><span class="cx"> static bool isEmptyBucket(const ValueType& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
</span><span class="lines">@@ -1031,6 +1033,28 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
</span><ins>+ template<typename Functor>
+ inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeIf(const Functor& functor)
+ {
+ for (unsigned i = m_tableSize; i--;) {
+ if (isEmptyOrDeletedBucket(m_table[i]))
+ continue;
+
+ if (!functor(m_table[i]))
+ continue;
+
+ deleteBucket(m_table[i]);
+ ++m_deletedCount;
+ --m_keyCount;
+ }
+
+ if (shouldShrink())
+ shrink();
+
+ internalCheckTableConsistency();
+ }
+
+ template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
</ins><span class="cx"> auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size) -> ValueType*
</span><span class="cx"> {
</span><span class="cx"> // would use a template member function with explicit specializations here, but
</span></span></pre>
</div>
</div>
</body>
</html>