/*
- * Copyright (C) 2011, 2012, 2013, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2011-2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
#if ENABLE(DFG_JIT)
#include "DFGAbstractHeap.h"
+#include "DFGBlockMapInlines.h"
+#include "DFGClobberSet.h"
#include "DFGClobberize.h"
#include "DFGEdgeUsesStructure.h"
#include "DFGGraph.h"
namespace JSC { namespace DFG {
-enum CSEMode { NormalCSE, StoreElimination };
+// This file contains two CSE implementations: local and global. LocalCSE typically runs when we're
+// in DFG mode, i.e. we want to compile quickly. LocalCSE contains a lot of optimizations for
+// compile time. GlobalCSE, on the other hand, is fairly straight-forward. It will find more
+// optimization opportunities by virtue of being global.
-template<CSEMode cseMode>
-class CSEPhase : public Phase {
+namespace {
+
+const bool verbose = false;
+
+class ClobberFilter {
public:
- CSEPhase(Graph& graph)
- : Phase(graph, cseMode == NormalCSE ? "common subexpression elimination" : "store elimination")
+ ClobberFilter(AbstractHeap heap)
+ : m_heap(heap)
+ {
+ }
+
+ bool operator()(const ImpureMap::KeyValuePairType& pair) const
+ {
+ return m_heap.overlaps(pair.key.heap());
+ }
+
+private:
+ AbstractHeap m_heap;
+};
+
+inline void clobber(ImpureMap& map, AbstractHeap heap)
+{
+ ClobberFilter filter(heap);
+ map.removeIf(filter);
+}
+
+class LocalCSEPhase : public Phase {
+public:
+ LocalCSEPhase(Graph& graph)
+ : Phase(graph, "local common subexpression elimination")
+ , m_smallBlock(graph)
+ , m_largeBlock(graph)
{
}
bool run()
{
- ASSERT(m_graph.m_fixpointState != BeforeFixpoint);
+ ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
+ ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == LoadStore);
- m_changed = false;
+ bool changed = false;
m_graph.clearReplacements();
if (!block)
continue;
- // All Phis need to already be marked as relevant to OSR.
- if (!ASSERT_DISABLED) {
- for (unsigned i = 0; i < block->phis.size(); ++i)
- ASSERT(block->phis[i]->flags() & NodeRelevantToOSR);
- }
-
- for (unsigned i = block->size(); i--;) {
- Node* node = block->at(i);
-
- switch (node->op()) {
- case SetLocal:
- case GetLocal: // FIXME: The GetLocal case is only necessary until we do https://bugs.webkit.org/show_bug.cgi?id=106707.
- node->mergeFlags(NodeRelevantToOSR);
- break;
- default:
- node->clearFlags(NodeRelevantToOSR);
- break;
- }
- }
+ if (block->size() <= SmallMaps::capacity)
+ changed |= m_smallBlock.run(block);
+ else
+ changed |= m_largeBlock.run(block);
}
- for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
- BasicBlock* block = m_graph.block(blockIndex);
- if (!block)
- continue;
-
- for (unsigned i = block->size(); i--;) {
- Node* node = block->at(i);
- if (!node->containsMovHint())
- continue;
-
- ASSERT(node->op() != ZombieHint);
- node->child1()->mergeFlags(NodeRelevantToOSR);
- }
- }
-
- 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;
+ return changed;
}
private:
+ class SmallMaps {
+ public:
+ // This permits SmallMaps to be used for blocks that have up to 100 nodes. In practice,
+ // fewer than half of the nodes in a block have pure defs, and even fewer have impure defs.
+ // Thus, a capacity limit of 100 probably means that somewhere around ~40 things may end up
+ // in one of these "small" list-based maps. That number still seems largeish, except that
+ // the overhead of HashMaps can be quite high currently: clearing them, or even removing
+ // enough things from them, deletes (or resizes) their backing store eagerly. Hence
+ // HashMaps induce a lot of malloc traffic.
+ static const unsigned capacity = 100;
- unsigned endIndexForPureCSE()
- {
- unsigned result = m_lastSeen[m_currentNode->op()];
- if (result == UINT_MAX)
- result = 0;
- else
- result++;
- ASSERT(result <= m_indexInBlock);
- return result;
- }
-
- Node* pureCSE(Node* node)
- {
- Edge child1 = node->child1().sanitized();
- Edge child2 = node->child2().sanitized();
- Edge child3 = node->child3().sanitized();
-
- for (unsigned i = endIndexForPureCSE(); i--;) {
- Node* otherNode = m_currentBlock->at(i);
- if (otherNode == child1 || otherNode == child2 || otherNode == child3)
- break;
-
- if (node->op() != otherNode->op())
- continue;
-
- 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;
- }
- return 0;
- }
-
- Node* constantCSE(Node* node)
- {
- for (unsigned i = endIndexForPureCSE(); i--;) {
- Node* otherNode = m_currentBlock->at(i);
- if (otherNode->op() != node->op())
- continue;
-
- if (otherNode->constantNumber() != node->constantNumber())
- continue;
-
- return otherNode;
- }
- return 0;
- }
-
- Node* weakConstantCSE(Node* node)
- {
- for (unsigned i = endIndexForPureCSE(); i--;) {
- Node* otherNode = m_currentBlock->at(i);
- if (otherNode->op() != WeakJSConstant)
- continue;
-
- if (otherNode->weakConstant() != node->weakConstant())
- continue;
-
- return otherNode;
- }
- return 0;
- }
-
- 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;
+ SmallMaps()
+ : m_pureLength(0)
+ , m_impureLength(0)
+ {
}
- return 0;
- }
- Node* getCalleeLoadElimination()
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- switch (node->op()) {
- case GetCallee:
- return node;
- default:
- break;
- }
+ void clear()
+ {
+ m_pureLength = 0;
+ m_impureLength = 0;
}
- return 0;
- }
- 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;
+ 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];
}
}
- return 0;
- }
- 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;
+ Node* addPure(PureValue value, Node* node)
+ {
+ for (unsigned i = m_pureLength; i--;) {
+ if (m_pureMap[i].key == value)
+ return m_pureMap[i].value;
}
- if (m_graph.clobbersWorld(node))
- break;
+
+ ASSERT(m_pureLength < capacity);
+ m_pureMap[m_pureLength++] = WTF::KeyValuePair<PureValue, Node*>(value, node);
+ return nullptr;
}
- return 0;
- }
-
- 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;
+
+ LazyNode findReplacement(HeapLocation location)
+ {
+ for (unsigned i = m_impureLength; i--;) {
+ if (m_impureMap[i].key == location)
+ return m_impureMap[i].value;
}
- if (m_graph.clobbersWorld(node))
- break;
- }
- return 0;
- }
-
- 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;
+ return nullptr;
}
- return false;
- }
- Node* globalVarStoreElimination(WriteBarrier<Unknown>* registerPointer)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- switch (node->op()) {
- case PutGlobalVar:
- if (node->registerPointer() == registerPointer)
- return node;
- break;
-
- case GetGlobalVar:
- if (node->registerPointer() == registerPointer)
- return 0;
- break;
-
- default:
- break;
- }
- if (m_graph.clobbersWorld(node) || node->canExit())
- return 0;
+ LazyNode addImpure(HeapLocation location, LazyNode node)
+ {
+ // FIXME: If we are using small maps, we must not def() derived values.
+ // For now the only derived values we def() are constant-based.
+ if (location.index() && !location.index().isNode())
+ return nullptr;
+ if (LazyNode result = findReplacement(location))
+ return result;
+ ASSERT(m_impureLength < capacity);
+ m_impureMap[m_impureLength++] = WTF::KeyValuePair<HeapLocation, LazyNode>(location, node);
+ return nullptr;
}
- return 0;
- }
- Node* scopedVarStoreElimination(Node* scope, Node* registers, int varNumber)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- switch (node->op()) {
- case PutClosureVar: {
- if (node->varNumber() != varNumber)
- break;
- if (node->child1() == scope && node->child2() == registers)
- return node;
- return 0;
- }
-
- case GetClosureVar: {
- // Let's be conservative.
- if (node->varNumber() == varNumber)
- return 0;
- break;
- }
-
- case GetLocal:
- case SetLocal: {
- VariableAccessData* variableAccessData = node->variableAccessData();
- if (variableAccessData->isCaptured()
- && variableAccessData->local() == static_cast<VirtualRegister>(varNumber))
- return 0;
- break;
- }
+ private:
+ WTF::KeyValuePair<PureValue, Node*> m_pureMap[capacity];
+ WTF::KeyValuePair<HeapLocation, LazyNode> m_impureMap[capacity];
+ unsigned m_pureLength;
+ unsigned m_impureLength;
+ };
- default:
- break;
- }
- if (m_graph.clobbersWorld(node) || node->canExit())
- return 0;
+ class LargeMaps {
+ public:
+ LargeMaps()
+ {
}
- return 0;
- }
- 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;
- }
+ void clear()
+ {
+ m_pureMap.clear();
+ m_impureMap.clear();
}
- return 0;
- }
-
- bool checkFunctionElimination(JSCell* 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;
+
+ void write(AbstractHeap heap)
+ {
+ clobber(m_impureMap, heap);
}
- return false;
- }
- 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;
+ Node* addPure(PureValue value, Node* node)
+ {
+ auto result = m_pureMap.add(value, node);
+ if (result.isNewEntry)
+ return nullptr;
+ return result.iterator->value;
}
- return false;
- }
-
- bool checkStructureElimination(const StructureSet& structureSet, 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
- && structureSet.isSupersetOf(node->structureSet()))
- return true;
- break;
-
- case StructureTransitionWatchpoint:
- if (node->child1() == child1
- && structureSet.contains(node->structure()))
- return true;
- break;
-
- case PutStructure:
- if (node->child1() == child1
- && structureSet.contains(node->structureTransitionData().newStructure))
- return true;
- if (structureSet.contains(node->structureTransitionData().previousStructure))
- 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;
+
+ LazyNode findReplacement(HeapLocation location)
+ {
+ return m_impureMap.get(location);
+ }
+
+ LazyNode addImpure(HeapLocation location, LazyNode node)
+ {
+ auto result = m_impureMap.add(location, node);
+ if (result.isNewEntry)
+ return nullptr;
+ return result.iterator->value;
+ }
+
+ private:
+ HashMap<PureValue, Node*> m_pureMap;
+ HashMap<HeapLocation, LazyNode> m_impureMap;
+ };
+
+ template<typename Maps>
+ class BlockCSE {
+ public:
+ BlockCSE(Graph& graph)
+ : m_graph(graph)
+ , m_insertionSet(graph)
+ {
+ }
+
+ bool run(BasicBlock* block)
+ {
+ m_maps.clear();
+ m_changed = false;
+ m_block = block;
+
+ 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 {
+ // This rule only makes sense for local CSE, since in SSA form we have already
+ // factored the bounds check out of the PutByVal. It's kind of gross, but we
+ // still have reason to believe that PutByValAlias is a good optimization and
+ // that it's better to do it with a single node rather than separating out the
+ // CheckInBounds.
+ if (m_node->op() == PutByVal || m_node->op() == PutByValDirect) {
+ HeapLocation heap;
+
+ Node* base = m_graph.varArgChild(m_node, 0).node();
+ Node* index = m_graph.varArgChild(m_node, 1).node();
+
+ ArrayMode mode = m_node->arrayMode();
+ switch (mode.type()) {
+ case Array::Int32:
+ if (!mode.isInBounds())
+ break;
+ heap = HeapLocation(
+ IndexedPropertyLoc, IndexedInt32Properties, base, index);
+ break;
+
+ case Array::Double:
+ if (!mode.isInBounds())
+ break;
+ heap = HeapLocation(
+ IndexedPropertyLoc, IndexedDoubleProperties, base, index);
+ break;
+
+ case Array::Contiguous:
+ if (!mode.isInBounds())
+ break;
+ heap = HeapLocation(
+ IndexedPropertyLoc, IndexedContiguousProperties, base, index);
+ break;
+
+ case Array::Int8Array:
+ case Array::Int16Array:
+ case Array::Int32Array:
+ case Array::Uint8Array:
+ case Array::Uint8ClampedArray:
+ case Array::Uint16Array:
+ case Array::Uint32Array:
+ case Array::Float32Array:
+ case Array::Float64Array:
+ if (!mode.isInBounds())
+ break;
+ heap = HeapLocation(
+ IndexedPropertyLoc, TypedArrayProperties, base, index);
+ break;
+
+ default:
+ break;
+ }
+
+ if (!!heap && m_maps.findReplacement(heap))
+ m_node->setOp(PutByValAlias);
+ }
+
+ clobberize(m_graph, m_node, *this);
}
- 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;
}
- }
- return false;
- }
-
- 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().containsOnly(structure))
- return true;
- break;
-
- case PutStructure:
- ASSERT(node->structureTransitionData().previousStructure != 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 StructureTransitionWatchpoint:
- if (node->structure() == structure && node->child1() == child1)
- return true;
- break;
-
- 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;
- }
- }
- return false;
- }
-
- Node* putStructureStoreElimination(Node* child1)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- if (node == child1)
- break;
- switch (node->op()) {
- case CheckStructure:
- return 0;
-
- case PhantomPutStructure:
- if (node->child1() == child1) // No need to retrace our steps.
- return 0;
- break;
-
- case PutStructure:
- if (node->child1() == child1)
- return node;
- break;
-
- // PutStructure needs to execute if we GC. Hence this needs to
- // be careful with respect to nodes that GC.
- case CreateArguments:
- case TearOffArguments:
- case NewFunctionNoCheck:
- case NewFunction:
- case NewFunctionExpression:
- case CreateActivation:
- case TearOffActivation:
- case ToPrimitive:
- case NewRegexp:
- case NewArrayBuffer:
- case NewArray:
- case NewObject:
- case CreateThis:
- case AllocatePropertyStorage:
- case ReallocatePropertyStorage:
- case TypeOf:
- case ToString:
- case NewStringObject:
- case MakeRope:
- case NewTypedArray:
- case MultiPutByOffset:
- return 0;
-
- // This either exits, causes a GC (lazy string allocation), or clobbers
- // the world. The chances of it not doing any of those things are so
- // slim that we might as well not even try to reason about it.
- case GetByVal:
- return 0;
-
- case GetIndexedPropertyStorage:
- if (node->arrayMode().getIndexedPropertyStorageMayTriggerGC())
- return 0;
- break;
-
- default:
- break;
- }
- if (m_graph.clobbersWorld(node) || node->canExit())
- return 0;
- if (edgesUseStructure(m_graph, node))
- return 0;
+ m_insertionSet.execute(block);
+
+ return m_changed;
}
- return 0;
- }
- 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;
- }
- }
- return 0;
- }
+ void read(AbstractHeap) { }
- Node* putByOffsetStoreElimination(unsigned identifierNumber, Node* child1)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- if (node == child1)
- break;
-
- switch (node->op()) {
- case GetByOffset:
- if (m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber)
- return 0;
- break;
-
- case PutByOffset:
- if (m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber) {
- if (node->child1() == child1) // Must be same property storage.
- return node;
- return 0;
- }
- break;
-
- case MultiPutByOffset:
- if (node->multiPutByOffsetData().identifierNumber == identifierNumber)
- return 0;
- break;
-
- case PutByValDirect:
- case PutByVal:
- case PutByValAlias:
- case GetByVal:
- 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;
- }
- if (node->canExit())
- return 0;
+ void write(AbstractHeap heap)
+ {
+ m_maps.write(heap);
}
- return 0;
- }
-
- Node* getPropertyStorageLoadElimination(Node* child1)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- if (node == child1)
- break;
-
- switch (node->op()) {
- case GetButterfly:
- if (node->child1() == child1)
- return node;
- break;
+
+ void def(PureValue value)
+ {
+ Node* match = m_maps.addPure(value, m_node);
+ if (!match)
+ return;
- 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;
- }
+ m_node->replaceWith(match);
+ m_changed = true;
}
- return 0;
- }
- bool checkArrayElimination(Node* child1, ArrayMode arrayMode)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- if (node == child1)
- break;
-
- switch (node->op()) {
- case CheckArray:
- if (node->child1() == child1 && node->arrayMode() == arrayMode)
- return true;
- break;
-
- case Arrayify:
- case ArrayifyToStructure:
- // We could check if the arrayification could affect our array.
- // But that seems like it would take Effort.
- return false;
-
- default:
- if (m_graph.clobbersWorld(node))
- return false;
- break;
- }
- }
- return false;
- }
-
- 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;
+ void def(HeapLocation location, LazyNode value)
+ {
+ LazyNode match = m_maps.addImpure(location, value);
+ if (!match)
+ return;
+
+ if (m_node->op() == GetLocal) {
+ // Usually the CPS rethreading phase does this. But it's OK for us to mess with
+ // locals 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();
}
-
- default:
- if (m_graph.clobbersWorld(node))
- return 0;
- break;
+
+ if (value.isNode() && value.asNode() == m_node) {
+ match.ensureIsNode(m_insertionSet, m_block, 0)->owner = m_block;
+ ASSERT(match.isNode());
+ m_node->replaceWith(match.asNode());
+ m_changed = true;
}
}
- return 0;
- }
- Node* getTypedArrayByteOffsetLoadElimination(Node* child1)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- if (node == child1)
- break;
+ private:
+ Graph& m_graph;
+
+ bool m_changed;
+ Node* m_node;
+ BasicBlock* m_block;
+
+ Maps m_maps;
- switch (node->op()) {
- case GetTypedArrayByteOffset: {
- if (node->child1() == child1)
- return node;
- break;
- }
+ InsertionSet m_insertionSet;
+ };
- default:
- if (m_graph.clobbersWorld(node))
- return 0;
- break;
- }
- }
- return 0;
- }
-
- Node* getMyScopeLoadElimination()
+ BlockCSE<SmallMaps> m_smallBlock;
+ BlockCSE<LargeMaps> m_largeBlock;
+};
+
+class GlobalCSEPhase : public Phase {
+public:
+ GlobalCSEPhase(Graph& graph)
+ : Phase(graph, "global common subexpression elimination")
+ , m_impureDataMap(graph)
+ , m_insertionSet(graph)
{
- 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;
- }
- }
- return 0;
}
- Node* getLocalLoadElimination(VirtualRegister local, Node*& relevantLocalOp, bool careAboutClobbering)
+ bool run()
{
- relevantLocalOp = 0;
+ ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
+ ASSERT(m_graph.m_form == SSA);
- 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;
- }
+ m_graph.initializeNodeOwners();
+ m_graph.m_dominators.computeIfNecessary(m_graph);
+
+ m_preOrder = m_graph.blocksInPreOrder();
+
+ // First figure out what gets clobbered by blocks. Node that this uses the preOrder list
+ // for convenience only.
+ for (unsigned i = m_preOrder.size(); i--;) {
+ m_block = m_preOrder[i];
+ m_impureData = &m_impureDataMap[m_block];
+ for (unsigned nodeIndex = m_block->size(); nodeIndex--;)
+ addWrites(m_graph, m_block->at(nodeIndex), m_impureData->writes);
}
- return 0;
+
+ // Based on my experience doing this before, what follows might have to be made iterative.
+ // Right now it doesn't have to be iterative because everything is dominator-bsed. But when
+ // validation is enabled, we check if iterating would find new CSE opportunities.
+
+ bool changed = iterate();
+
+ // FIXME: It should be possible to assert that CSE will not find any new opportunities if you
+ // run it a second time. Unfortunately, we cannot assert this right now. Note that if we did
+ // this, we'd have to first reset all of our state.
+ // https://bugs.webkit.org/show_bug.cgi?id=145853
+
+ return changed;
}
- bool uncapturedSetLocalStoreElimination(VirtualRegister local, Node* expectedNode)
+ bool iterate()
{
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- switch (node->op()) {
- case GetLocal:
- case Flush:
- if (node->local() == local)
- return false;
- break;
-
- case GetLocalUnlinked:
- if (node->unlinkedLocal() == local)
- return false;
- break;
-
- case SetLocal: {
- if (node->local() != local)
- break;
- if (node != expectedNode)
- return false;
- return true;
- }
-
- case GetClosureVar:
- case PutClosureVar:
- if (static_cast<VirtualRegister>(node->varNumber()) == local)
- return false;
- break;
-
- case GetMyScope:
- case SkipTopScope:
- if (node->origin.semantic.inlineCallFrame)
- break;
- if (m_graph.uncheckedActivationRegister() == local)
- return false;
- break;
-
- case CheckArgumentsNotCreated:
- case GetMyArgumentsLength:
- case GetMyArgumentsLengthSafe:
- if (m_graph.uncheckedArgumentsRegisterFor(node->origin.semantic) == local)
- return false;
- break;
-
- case GetMyArgumentByVal:
- case GetMyArgumentByValSafe:
- return false;
-
- case GetByVal:
- // If this is accessing arguments then it's potentially accessing locals.
- if (node->arrayMode().type() == Array::Arguments)
- return false;
- break;
-
- case CreateArguments:
- case TearOffActivation:
- case TearOffArguments:
- // If an activation is being torn off then it means that captured variables
- // are live. We could be clever here and check if the local qualifies as an
- // argument register. But that seems like it would buy us very little since
- // any kind of tear offs are rare to begin with.
- return false;
-
- default:
- break;
- }
- if (m_graph.clobbersWorld(node))
- return false;
- }
- RELEASE_ASSERT_NOT_REACHED();
- return false;
- }
+ if (verbose)
+ dataLog("Performing iteration.\n");
+
+ m_changed = false;
+ m_graph.clearReplacements();
+
+ for (unsigned i = 0; i < m_preOrder.size(); ++i) {
+ m_block = m_preOrder[i];
+ m_impureData = &m_impureDataMap[m_block];
+ m_writesSoFar.clear();
+
+ if (verbose)
+ dataLog("Processing block ", *m_block, ":\n");
- bool capturedSetLocalStoreElimination(VirtualRegister local, Node* expectedNode)
- {
- for (unsigned i = m_indexInBlock; i--;) {
- Node* node = m_currentBlock->at(i);
- switch (node->op()) {
- case GetLocal:
- case Flush:
- if (node->local() == local)
- return false;
- break;
+ for (unsigned nodeIndex = 0; nodeIndex < m_block->size(); ++nodeIndex) {
+ m_nodeIndex = nodeIndex;
+ m_node = m_block->at(nodeIndex);
+ if (verbose)
+ dataLog(" Looking at node ", m_node, ":\n");
- case GetLocalUnlinked:
- if (node->unlinkedLocal() == local)
- return false;
- break;
+ m_graph.performSubstitution(m_node);
- case SetLocal: {
- if (node->local() != local)
- break;
- if (node != expectedNode)
- return false;
- return true;
- }
-
- case Phantom:
- case Check:
- case HardPhantom:
- case MovHint:
- case JSConstant:
- case DoubleConstant:
- case Int52Constant:
- break;
-
- default:
- return false;
+ if (m_node->op() == Identity) {
+ m_node->replaceWith(m_node->child1().node());
+ m_changed = true;
+ } else
+ clobberize(m_graph, m_node, *this);
}
+
+ m_insertionSet.execute(m_block);
+
+ m_impureData->didVisit = true;
}
- RELEASE_ASSERT_NOT_REACHED();
- return false;
- }
-
- bool setLocalStoreElimination(VariableAccessData* variableAccessData, Node* expectedNode)
- {
- if (variableAccessData->isCaptured())
- return capturedSetLocalStoreElimination(variableAccessData->local(), expectedNode);
- return uncapturedSetLocalStoreElimination(variableAccessData->local(), expectedNode);
+
+ return m_changed;
}
+
+ void read(AbstractHeap) { }
- bool invalidationPointElimination()
+ void write(AbstractHeap heap)
{
- 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;
- }
- return false;
+ clobber(m_impureData->availableAtTail, heap);
+ m_writesSoFar.add(heap);
+ if (verbose)
+ dataLog(" Clobbered, new tail map: ", mapDump(m_impureData->availableAtTail), "\n");
}
- void eliminateIrrelevantPhantomChildren(Node* node)
+ void def(PureValue value)
{
- ASSERT(node->op() == Phantom);
- for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
- Edge edge = node->children.child(i);
- if (!edge)
- continue;
- if (edge.useKind() != UntypedUse)
- continue; // Keep the type check.
- if (edge->flags() & NodeRelevantToOSR)
- continue;
-
- node->children.removeEdge(i--);
- m_changed = true;
- }
- }
-
- bool setReplacement(Node* replacement)
- {
- if (!replacement)
- return false;
+ // With pure values we do not have to worry about the possibility of some control flow path
+ // clobbering the value. So, we just search for all of the like values that have been
+ // computed. We pick one that is in a block that dominates ours. Note that this means that
+ // a PureValue will map to a list of nodes, since there may be many places in the control
+ // flow graph that compute a value but only one of them that dominates us. We may build up
+ // a large list of nodes that compute some value in the case of gnarly control flow. This
+ // is probably OK.
- if (!ASSERT_DISABLED
- && canonicalResultRepresentation(m_currentNode->result()) != canonicalResultRepresentation(replacement->result())) {
- startCrashing();
- dataLog("CSE attempting to replace a node with a mismatched result: ", m_currentNode, " with ", replacement, "\n");
- dataLog("\n");
- m_graph.dump();
- RELEASE_ASSERT_NOT_REACHED();
+ auto result = m_pureValues.add(value, Vector<Node*>());
+ if (result.isNewEntry) {
+ result.iterator->value.append(m_node);
+ return;
}
- m_currentNode->convertToPhantom();
- eliminateIrrelevantPhantomChildren(m_currentNode);
-
- // At this point we will eliminate all references to this node.
- m_currentNode->misc.replacement = replacement;
-
- m_changed = true;
+ 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;
+ }
+ }
- return true;
+ result.iterator->value.append(m_node);
}
- void eliminate()
+ LazyNode findReplacement(HeapLocation location)
{
- ASSERT(m_currentNode->mustGenerate());
- m_currentNode->convertToPhantom();
- eliminateIrrelevantPhantomChildren(m_currentNode);
+ // At this instant, our "availableAtTail" reflects the set of things that are available in
+ // this block so far. We check this map to find block-local CSE opportunities before doing
+ // a global search.
+ LazyNode match = m_impureData->availableAtTail.get(location);
+ if (!!match) {
+ if (verbose)
+ dataLog(" Found local match: ", match, "\n");
+ return match;
+ }
- m_changed = true;
- }
-
- void eliminate(Node* node, NodeType phantomType = Phantom)
- {
- if (!node)
- return;
- ASSERT(node->mustGenerate());
- node->setOpAndDefaultFlags(phantomType);
- if (phantomType == Phantom)
- eliminateIrrelevantPhantomChildren(node);
+ // If it's not available at this point in the block, and at some prior point in the block
+ // we have clobbered this heap location, then there is no point in doing a global search.
+ if (m_writesSoFar.overlaps(location.heap())) {
+ if (verbose)
+ dataLog(" Not looking globally because of local clobber: ", m_writesSoFar, "\n");
+ return nullptr;
+ }
- m_changed = true;
- }
-
- void performNodeCSE(Node* node)
- {
- if (cseMode == NormalCSE)
- m_graph.performSubstitution(node);
+ // This perfoms a backward search over the control flow graph to find some possible
+ // non-local def() that matches our heap location. Such a match is only valid if there does
+ // not exist any path from that def() to our block that contains a write() that overlaps
+ // our heap. This algorithm looks for both of these things (the matching def and the
+ // overlapping writes) in one backwards DFS pass.
+ //
+ // This starts by looking at the starting block's predecessors, and then it continues along
+ // their predecessors. As soon as this finds a possible def() - one that defines the heap
+ // location we want while dominating our starting block - it assumes that this one must be
+ // the match. It then lets the DFS over predecessors complete, but it doesn't add the
+ // def()'s predecessors; this ensures that any blocks we visit thereafter are on some path
+ // from the def() to us. As soon as the DFG finds a write() that overlaps the location's
+ // heap, it stops, assuming that there is no possible match. Note that the write() case may
+ // trigger before we find a def(), or after. Either way, the write() case causes this
+ // function to immediately return nullptr.
+ //
+ // If the write() is found before we find the def(), then we know that any def() we would
+ // find would have a path to us that trips over the write() and hence becomes invalid. This
+ // is just a direct outcome of us looking for a def() that dominates us. Given a block A
+ // that dominates block B - so that A is the one that would have the def() and B is our
+ // starting block - we know that any other block must either be on the path from A to B, or
+ // it must be on a path from the root to A, but not both. So, if we haven't found A yet but
+ // we already have found a block C that has a write(), then C must be on some path from A
+ // to B, which means that A's def() is invalid for our purposes. Hence, before we find the
+ // def(), stopping on write() is the right thing to do.
+ //
+ // Stopping on write() is also the right thing to do after we find the def(). After we find
+ // the def(), we don't add that block's predecessors to the search worklist. That means
+ // that henceforth the only blocks we will see in the search are blocks on the path from
+ // the def() to us. If any such block has a write() that clobbers our heap then we should
+ // give up.
+ //
+ // Hence this graph search algorithm ends up being deceptively simple: any overlapping
+ // write() causes us to immediately return nullptr, and a matching def() means that we just
+ // record it and neglect to visit its precessors.
- switch (node->op()) {
+ Vector<BasicBlock*, 8> worklist;
+ Vector<BasicBlock*, 8> seenList;
+ BitVector seen;
- case Identity:
- if (cseMode == StoreElimination)
- break;
- setReplacement(node->child1().node());
- break;
-
- // 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:
- case BooleanToNumber:
- if (cseMode == StoreElimination)
- break;
- setReplacement(pureCSE(node));
- break;
-
- case ArithAdd:
- case ArithSub:
- case ArithNegate:
- case ArithMul:
- case ArithDiv:
- case ArithMod:
- case UInt32ToNumber:
- case DoubleAsInt32: {
- if (cseMode == StoreElimination)
- break;
- Node* candidate = pureCSE(node);
- if (!candidate)
- break;
- if (!subsumes(candidate->arithMode(), node->arithMode())) {
- if (!subsumes(node->arithMode(), candidate->arithMode()))
- break;
- candidate->setArithMode(node->arithMode());
+ 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);
}
- setReplacement(candidate);
- break;
- }
-
- case GetCallee:
- if (cseMode == StoreElimination)
- break;
- setReplacement(getCalleeLoadElimination());
- break;
-
- case GetLocal: {
- if (cseMode == StoreElimination)
- break;
- 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: {
- if (cseMode == StoreElimination)
- break;
- Node* relevantLocalOpIgnored;
- setReplacement(getLocalLoadElimination(node->unlinkedLocal(), relevantLocalOpIgnored, true));
- break;
}
-
- case Flush: {
- ASSERT(m_graph.m_form != SSA);
- VariableAccessData* variableAccessData = node->variableAccessData();
- if (!node->child1()) {
- // FIXME: It's silly that we punt on flush-eliminating here. We don't really
- // need child1 to figure out what's going on.
- // https://bugs.webkit.org/show_bug.cgi?id=130521
- break;
- }
- Node* replacement = node->child1().node();
- if (replacement->op() != SetLocal)
- break;
- ASSERT(replacement->variableAccessData() == variableAccessData);
- // FIXME: We should be able to remove SetLocals that can exit; we just need
- // to replace them with appropriate type checks.
- if (cseMode == NormalCSE) {
- // Need to be conservative at this time; if the SetLocal has any chance of performing
- // any speculations then we cannot do anything.
- FlushFormat format = variableAccessData->flushFormat();
- ASSERT(format != DeadFlush);
- if (format != FlushedJSValue)
- break;
- } else {
- if (replacement->canExit())
- break;
+
+ while (!worklist.isEmpty()) {
+ BasicBlock* block = worklist.takeLast();
+ seenList.append(block);
+
+ if (verbose)
+ dataLog(" Searching in block ", *block, "\n");
+ ImpureBlockData& data = m_impureDataMap[block];
+
+ // We require strict domination because this would only see things in our own block if
+ // they came *after* our position in the block. Clearly, while our block dominates
+ // itself, the things in the block after us don't dominate us.
+ if (m_graph.m_dominators.strictlyDominates(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);
+ if (verbose)
+ dataLog(" Availability map: ", mapDump(data.availableAtTail), "\n");
+ 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;
+ }
}
- if (!setLocalStoreElimination(variableAccessData, replacement))
- break;
- ASSERT(replacement->op() == SetLocal);
- node->convertToPhantom();
- Node* dataNode = replacement->child1().node();
- ASSERT(dataNode->hasResult());
- node->child1() = dataNode->defaultEdge();
- m_graph.dethread();
- m_changed = true;
- break;
- }
-
- case JSConstant:
- case DoubleConstant:
- case Int52Constant:
- if (cseMode == StoreElimination)
- break;
- // 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 WeakJSConstant:
- if (cseMode == StoreElimination)
- break;
- // FIXME: have CSE for weak constants against strong constants and vice-versa.
- setReplacement(weakConstantCSE(node));
- break;
-
- case ConstantStoragePointer:
- if (cseMode == StoreElimination)
- break;
- setReplacement(constantStoragePointerCSE(node));
- break;
-
- case GetArrayLength:
- if (cseMode == StoreElimination)
- break;
- setReplacement(getArrayLengthElimination(node->child1().node()));
- break;
-
- case GetMyScope:
- if (cseMode == StoreElimination)
- break;
- 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 (cseMode == StoreElimination)
- break;
- if (m_graph.isPredictedNumerical(node)) {
- Node* replacement = pureCSE(node);
- if (replacement && m_graph.isPredictedNumerical(replacement))
- setReplacement(replacement);
+ if (verbose)
+ dataLog(" Dealing with write set ", data.writes, "\n");
+ if (data.writes.overlaps(location.heap())) {
+ if (verbose)
+ dataLog(" Clobbered.\n");
+ return nullptr;
}
- break;
- }
-
- // Finally handle heap accesses. These are not quite pure, but we can still
- // optimize them provided that some subtle conditions are met.
- case GetGlobalVar:
- if (cseMode == StoreElimination)
- break;
- setReplacement(globalVarLoadElimination(node->registerPointer()));
- break;
-
- case GetClosureVar: {
- if (cseMode == StoreElimination)
- break;
- setReplacement(scopedVarLoadElimination(node->child1().node(), node->varNumber()));
- break;
- }
-
- case VarInjectionWatchpoint:
- if (cseMode == StoreElimination)
- break;
- if (varInjectionWatchpointElimination())
- eliminate();
- break;
-
- case PutGlobalVar:
- if (cseMode == NormalCSE)
- break;
- eliminate(globalVarStoreElimination(node->registerPointer()));
- break;
- case PutClosureVar: {
- if (cseMode == NormalCSE)
- break;
- eliminate(scopedVarStoreElimination(node->child1().node(), node->child2().node(), node->varNumber()));
- break;
- }
-
- case GetByVal:
- if (cseMode == StoreElimination)
- break;
- if (m_graph.byValIsPure(node))
- setReplacement(getByValLoadElimination(node->child1().node(), node->child2().node(), node->arrayMode()));
- break;
-
- case PutByValDirect:
- case PutByVal: {
- if (cseMode == StoreElimination)
- break;
- 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);
+ for (unsigned i = block->predecessors.size(); i--;) {
+ BasicBlock* predecessor = block->predecessors[i];
+ if (!seen.get(predecessor->index)) {
+ worklist.append(predecessor);
+ seen.set(predecessor->index);
+ }
}
- break;
- }
-
- case CheckStructure:
- if (cseMode == StoreElimination)
- break;
- if (checkStructureElimination(node->structureSet(), node->child1().node()))
- eliminate();
- break;
-
- case StructureTransitionWatchpoint:
- if (cseMode == StoreElimination)
- break;
- if (structureTransitionWatchpointElimination(node->structure(), node->child1().node()))
- eliminate();
- break;
-
- case PutStructure:
- if (cseMode == NormalCSE)
- break;
- eliminate(putStructureStoreElimination(node->child1().node()), PhantomPutStructure);
- break;
-
- case CheckFunction:
- if (cseMode == StoreElimination)
- break;
- if (checkFunctionElimination(node->function(), node->child1().node()))
- eliminate();
- break;
-
- case CheckExecutable:
- if (cseMode == StoreElimination)
- break;
- if (checkExecutableElimination(node->executable(), node->child1().node()))
- eliminate();
- break;
-
- case CheckArray:
- if (cseMode == StoreElimination)
- break;
- if (checkArrayElimination(node->child1().node(), node->arrayMode()))
- eliminate();
- break;
-
- case GetIndexedPropertyStorage: {
- if (cseMode == StoreElimination)
- break;
- setReplacement(getIndexedPropertyStorageLoadElimination(node->child1().node(), node->arrayMode()));
- break;
- }
-
- case GetTypedArrayByteOffset: {
- if (cseMode == StoreElimination)
- break;
- setReplacement(getTypedArrayByteOffsetLoadElimination(node->child1().node()));
- break;
- }
-
- case GetButterfly:
- if (cseMode == StoreElimination)
- break;
- setReplacement(getPropertyStorageLoadElimination(node->child1().node()));
- break;
-
- case GetByOffset:
- if (cseMode == StoreElimination)
- break;
- setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber, node->child2().node()));
- break;
-
- case MultiGetByOffset:
- if (cseMode == StoreElimination)
- break;
- setReplacement(getByOffsetLoadElimination(node->multiGetByOffsetData().identifierNumber, node->child1().node()));
- break;
-
- case PutByOffset:
- if (cseMode == NormalCSE)
- break;
- eliminate(putByOffsetStoreElimination(m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber, node->child1().node()));
- break;
-
- case InvalidationPoint:
- if (invalidationPointElimination())
- eliminate();
- break;
-
- case Phantom:
- // FIXME: we ought to remove Phantom's that have no children.
- // NB. It would be incorrect to do this for HardPhantom. In fact, the whole point
- // of HardPhantom is that we *don't* do this for HardPhantoms, since they signify
- // a more strict kind of liveness than the Phantom bytecode liveness.
- eliminateIrrelevantPhantomChildren(node);
- break;
-
- default:
- // do nothing.
- break;
}
- m_lastSeen[node->op()] = m_indexInBlock;
+ if (!match)
+ return nullptr;
+
+ // 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.
+ // FIXME: Consider caching failed searches as well, when match is null. It's not clear that
+ // the reduction in compile time would warrant the increase in complexity, though.
+ // https://bugs.webkit.org/show_bug.cgi?id=134876
+ for (BasicBlock* block : seenList)
+ m_impureDataMap[block].availableAtTail.add(location, match);
+ m_impureData->availableAtTail.add(location, match);
+
+ return match;
}
- void performBlockCSE(BasicBlock* block)
+ void def(HeapLocation location, LazyNode value)
{
- if (!block)
- return;
- if (!block->isReachable)
- return;
+ if (verbose)
+ dataLog(" Got heap location def: ", location, " -> ", value, "\n");
- m_currentBlock = block;
- for (unsigned i = 0; i < LastNodeType; ++i)
- m_lastSeen[i] = UINT_MAX;
+ LazyNode match = findReplacement(location);
- for (m_indexInBlock = 0; m_indexInBlock < block->size(); ++m_indexInBlock) {
- m_currentNode = block->at(m_indexInBlock);
- performNodeCSE(m_currentNode);
- }
+ if (verbose)
+ dataLog(" Got match: ", match, "\n");
- if (!ASSERT_DISABLED && cseMode == StoreElimination) {
- // Nobody should have replacements set.
- for (unsigned i = 0; i < block->size(); ++i)
- ASSERT(!block->at(i)->misc.replacement);
+ if (!match) {
+ if (verbose)
+ dataLog(" Adding at-tail mapping: ", location, " -> ", value, "\n");
+ auto result = m_impureData->availableAtTail.add(location, value);
+ ASSERT_UNUSED(result, result.isNewEntry);
+ return;
+ }
+
+ if (value.isNode() && value.asNode() == m_node) {
+ if (!match.isNode()) {
+ // We need to properly record the constant in order to use an existing one if applicable.
+ // This ensures that re-running GCSE will not find new optimizations.
+ match.ensureIsNode(m_insertionSet, m_block, m_nodeIndex)->owner = m_block;
+ auto result = m_pureValues.add(PureValue(match.asNode(), match->constant()), Vector<Node*>());
+ bool replaced = false;
+ if (!result.isNewEntry) {
+ for (unsigned i = result.iterator->value.size(); i--;) {
+ Node* candidate = result.iterator->value[i];
+ if (m_graph.m_dominators.dominates(candidate->owner, m_block)) {
+ ASSERT(candidate);
+ match->replaceWith(candidate);
+ match.setNode(candidate);
+ replaced = true;
+ break;
+ }
+ }
+ }
+ if (!replaced)
+ result.iterator->value.append(match.asNode());
+ }
+ ASSERT(match.asNode());
+ m_node->replaceWith(match.asNode());
+ m_changed = true;
}
}
- 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.
+ struct ImpureBlockData {
+ ImpureBlockData()
+ : didVisit(false)
+ {
+ }
+
+ ClobberSet writes;
+ ImpureMap availableAtTail;
+ bool didVisit;
+ };
+
+ Vector<BasicBlock*> m_preOrder;
+
+ PureMultiMap m_pureValues;
+ BlockMap<ImpureBlockData> m_impureDataMap;
+
+ BasicBlock* m_block;
+ Node* m_node;
+ unsigned m_nodeIndex;
+ ImpureBlockData* m_impureData;
+ ClobberSet m_writesSoFar;
+ InsertionSet m_insertionSet;
+
+ bool m_changed;
};
-bool performCSE(Graph& graph)
+} // anonymous namespace
+
+bool performLocalCSE(Graph& graph)
{
- SamplingRegion samplingRegion("DFG CSE Phase");
- return runPhase<CSEPhase<NormalCSE>>(graph);
+ SamplingRegion samplingRegion("DFG LocalCSE Phase");
+ return runPhase<LocalCSEPhase>(graph);
}
-bool performStoreElimination(Graph& graph)
+bool performGlobalCSE(Graph& graph)
{
- SamplingRegion samplingRegion("DFG Store Elimination Phase");
- return runPhase<CSEPhase<StoreElimination>>(graph);
+ SamplingRegion samplingRegion("DFG GlobalCSE Phase");
+ return runPhase<GlobalCSEPhase>(graph);
}
} } // namespace JSC::DFG
#endif // ENABLE(DFG_JIT)
-
-
projects / apple / javascriptcore.git / blobdiff