Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (174223 => 174224)
--- trunk/Source/_javascript_Core/ChangeLog 2014-10-02 19:14:57 UTC (rev 174223)
+++ trunk/Source/_javascript_Core/ChangeLog 2014-10-02 19:38:08 UTC (rev 174224)
@@ -1,3 +1,44 @@
+2014-10-02 Filip Pizlo <[email protected]>
+
+ Object allocation sinking should have a sound story for picking materialization points
+ https://bugs.webkit.org/show_bug.cgi?id=137315
+
+ Reviewed by Oliver Hunt.
+
+ The only missing piece was having the object allocation sinking phase locate materialization
+ points that were at CFG edges.
+
+ The logic for how and why this "just works" relies on some properties of critical edge
+ breaking, so I was fairly careful in how I did this. Also, this requires inserting things at
+ the "first origin node" of a block - that is the first node in a block that has a NodeOrigin
+ and therefore is allowed to exit. We basically had support for such a notion before, but
+ didn't close the loop on it; this patch does that.
+
+ Also I added the ability to provide a BasicBlock* as context for a DFG_ASSERT().
+
+ * dfg/DFGBasicBlock.cpp:
+ (JSC::DFG::BasicBlock::firstOriginNode):
+ (JSC::DFG::BasicBlock::firstOrigin):
+ * dfg/DFGBasicBlock.h:
+ * dfg/DFGCriticalEdgeBreakingPhase.cpp:
+ (JSC::DFG::CriticalEdgeBreakingPhase::breakCriticalEdge):
+ * dfg/DFGGraph.cpp:
+ (JSC::DFG::crash):
+ (JSC::DFG::Graph::handleAssertionFailure):
+ * dfg/DFGGraph.h:
+ * dfg/DFGLoopPreHeaderCreationPhase.cpp:
+ (JSC::DFG::createPreHeader):
+ * dfg/DFGNodeOrigin.h:
+ (JSC::DFG::NodeOrigin::isSet):
+ * dfg/DFGObjectAllocationSinkingPhase.cpp:
+ (JSC::DFG::ObjectAllocationSinkingPhase::determineMaterializationPoints):
+ (JSC::DFG::ObjectAllocationSinkingPhase::placeMaterializationPoints):
+ (JSC::DFG::ObjectAllocationSinkingPhase::promoteSunkenFields):
+ (JSC::DFG::ObjectAllocationSinkingPhase::createMaterialize):
+ * dfg/DFGValidate.cpp:
+ (JSC::DFG::Validate::validate):
+ * runtime/Options.h:
+
2014-10-02 Daniel Bates <[email protected]>
Clean up: Move XPC forward declarations in _javascript_Core to WTF SPI wrapper header
Modified: trunk/Source/_javascript_Core/dfg/DFGBasicBlock.cpp (174223 => 174224)
--- trunk/Source/_javascript_Core/dfg/DFGBasicBlock.cpp 2014-10-02 19:14:57 UTC (rev 174223)
+++ trunk/Source/_javascript_Core/dfg/DFGBasicBlock.cpp 2014-10-02 19:38:08 UTC (rev 174224)
@@ -89,6 +89,21 @@
return false;
}
+Node* BasicBlock::firstOriginNode()
+{
+ for (Node* node : *this) {
+ if (node->origin.isSet())
+ return node;
+ }
+ RELEASE_ASSERT_NOT_REACHED();
+ return nullptr;
+}
+
+NodeOrigin BasicBlock::firstOrigin()
+{
+ return firstOriginNode()->origin;
+}
+
void BasicBlock::removePredecessor(BasicBlock* block)
{
for (unsigned i = 0; i < predecessors.size(); ++i) {
Modified: trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h (174223 => 174224)
--- trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h 2014-10-02 19:14:57 UTC (rev 174223)
+++ trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h 2014-10-02 19:38:08 UTC (rev 174224)
@@ -34,6 +34,7 @@
#include "DFGBranchDirection.h"
#include "DFGFlushedAt.h"
#include "DFGNode.h"
+#include "DFGNodeOrigin.h"
#include "DFGStructureClobberState.h"
#include "Operands.h"
#include <wtf/HashMap.h>
@@ -90,6 +91,9 @@
BlockNodeList::iterator begin() { return m_nodes.begin(); }
BlockNodeList::iterator end() { return m_nodes.end(); }
+ Node* firstOriginNode();
+ NodeOrigin firstOrigin();
+
unsigned numSuccessors() { return last()->numSuccessors(); }
BasicBlock*& successor(unsigned index)
Modified: trunk/Source/_javascript_Core/dfg/DFGCriticalEdgeBreakingPhase.cpp (174223 => 174224)
--- trunk/Source/_javascript_Core/dfg/DFGCriticalEdgeBreakingPhase.cpp 2014-10-02 19:14:57 UTC (rev 174223)
+++ trunk/Source/_javascript_Core/dfg/DFGCriticalEdgeBreakingPhase.cpp 2014-10-02 19:38:08 UTC (rev 174224)
@@ -77,7 +77,7 @@
// don't know its execution frequency.
BasicBlock* pad = m_insertionSet.insertBefore(*successor, PNaN);
pad->appendNode(
- m_graph, SpecNone, Jump, (*successor)->at(0)->origin, OpInfo(*successor));
+ m_graph, SpecNone, Jump, (*successor)->firstOrigin(), OpInfo(*successor));
pad->predecessors.append(predecessor);
(*successor)->replacePredecessor(predecessor, pad);
Modified: trunk/Source/_javascript_Core/dfg/DFGGraph.cpp (174223 => 174224)
--- trunk/Source/_javascript_Core/dfg/DFGGraph.cpp 2014-10-02 19:14:57 UTC (rev 174223)
+++ trunk/Source/_javascript_Core/dfg/DFGGraph.cpp 2014-10-02 19:38:08 UTC (rev 174224)
@@ -1212,25 +1212,41 @@
DFG_CRASH(*this, nullptr, toCString("Structure ", pointerDump(structure), " is watchable but isn't being watched.").data());
}
-void Graph::handleAssertionFailure(
- Node* node, const char* file, int line, const char* function, const char* assertion)
+NO_RETURN_DUE_TO_CRASH static void crash(
+ Graph& graph, const CString& whileText, const char* file, int line, const char* function,
+ const char* assertion)
{
startCrashing();
dataLog("DFG ASSERTION FAILED: ", assertion, "\n");
dataLog(file, "(", line, ") : ", function, "\n");
dataLog("\n");
- if (node) {
- dataLog("While handling node ", node, "\n");
- dataLog("\n");
- }
+ dataLog(whileText);
dataLog("Graph at time of failure:\n");
- dump();
+ graph.dump();
dataLog("\n");
dataLog("DFG ASSERTION FAILED: ", assertion, "\n");
dataLog(file, "(", line, ") : ", function, "\n");
CRASH_WITH_SECURITY_IMPLICATION();
}
+void Graph::handleAssertionFailure(
+ std::nullptr_t, const char* file, int line, const char* function, const char* assertion)
+{
+ crash(*this, "", file, line, function, assertion);
+}
+
+void Graph::handleAssertionFailure(
+ Node* node, const char* file, int line, const char* function, const char* assertion)
+{
+ crash(*this, toCString("While handling node ", node, "\n\n"), file, line, function, assertion);
+}
+
+void Graph::handleAssertionFailure(
+ BasicBlock* block, const char* file, int line, const char* function, const char* assertion)
+{
+ crash(*this, toCString("While handling block ", pointerDump(block), "\n\n"), file, line, function, assertion);
+}
+
} } // namespace JSC::DFG
#endif // ENABLE(DFG_JIT)
Modified: trunk/Source/_javascript_Core/dfg/DFGGraph.h (174223 => 174224)
--- trunk/Source/_javascript_Core/dfg/DFGGraph.h 2014-10-02 19:14:57 UTC (rev 174223)
+++ trunk/Source/_javascript_Core/dfg/DFGGraph.h 2014-10-02 19:38:08 UTC (rev 174224)
@@ -845,8 +845,14 @@
virtual void visitChildren(SlotVisitor&) override;
NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
- Node* node, const char* file, int line, const char* function,
+ std::nullptr_t, const char* file, int line, const char* function,
const char* assertion);
+ NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
+ Node*, const char* file, int line, const char* function,
+ const char* assertion);
+ NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
+ BasicBlock*, const char* file, int line, const char* function,
+ const char* assertion);
VM& m_vm;
Plan& m_plan;
Modified: trunk/Source/_javascript_Core/dfg/DFGLoopPreHeaderCreationPhase.cpp (174223 => 174224)
--- trunk/Source/_javascript_Core/dfg/DFGLoopPreHeaderCreationPhase.cpp 2014-10-02 19:14:57 UTC (rev 174223)
+++ trunk/Source/_javascript_Core/dfg/DFGLoopPreHeaderCreationPhase.cpp 2014-10-02 19:38:08 UTC (rev 174224)
@@ -42,7 +42,7 @@
// Don't bother to preserve execution frequencies for now.
BasicBlock* preHeader = insertionSet.insertBefore(block, PNaN);
preHeader->appendNode(
- graph, SpecNone, Jump, block->at(0)->origin, OpInfo(block));
+ graph, SpecNone, Jump, block->firstOrigin(), OpInfo(block));
for (unsigned predecessorIndex = 0; predecessorIndex < block->predecessors.size(); predecessorIndex++) {
BasicBlock* predecessor = block->predecessors[predecessorIndex];
Modified: trunk/Source/_javascript_Core/dfg/DFGNodeOrigin.h (174223 => 174224)
--- trunk/Source/_javascript_Core/dfg/DFGNodeOrigin.h 2014-10-02 19:14:57 UTC (rev 174223)
+++ trunk/Source/_javascript_Core/dfg/DFGNodeOrigin.h 2014-10-02 19:38:08 UTC (rev 174224)
@@ -49,6 +49,7 @@
bool isSet() const
{
+ ASSERT(semantic.isSet() == forExit.isSet());
return semantic.isSet();
}
Modified: trunk/Source/_javascript_Core/dfg/DFGObjectAllocationSinkingPhase.cpp (174223 => 174224)
--- trunk/Source/_javascript_Core/dfg/DFGObjectAllocationSinkingPhase.cpp 2014-10-02 19:14:57 UTC (rev 174223)
+++ trunk/Source/_javascript_Core/dfg/DFGObjectAllocationSinkingPhase.cpp 2014-10-02 19:38:08 UTC (rev 174224)
@@ -145,7 +145,8 @@
// materializations.
m_sinkCandidates.clear();
- m_edgeToMaterializationPoint.clear();
+ m_materializationToEscapee.clear();
+ m_materializationSiteToMaterializations.clear();
BlockMap<HashMap<Node*, bool>> materializedAtHead(m_graph);
BlockMap<HashMap<Node*, bool>> materializedAtTail(m_graph);
@@ -235,7 +236,14 @@
return;
// A materialization edge exists at any point where a node escapes but hasn't been
- // materialized yet.
+ // materialized yet. We do this in two parts. First we find all of the nodes that cause
+ // escaping to happen, where the escapee had not yet been materialized. This catches
+ // everything but loops. We then catch loops - as well as weirder control flow constructs -
+ // in a subsequent pass that looks at places in the CFG where an edge exists from a block
+ // that hasn't materialized to a block that has. We insert the materialization along such an
+ // edge, and we rely on the fact that critical edges were already broken so that we actually
+ // either insert the materialization at the head of the successor or the tail of the
+ // predecessor.
//
// FIXME: This can create duplicate allocations when we really only needed to perform one.
// For example:
@@ -254,6 +262,8 @@
// materialization point right at the top of the then case of "if (rare)". To do this, we can
// find the LCA of the various materializations in the dom tree.
// https://bugs.webkit.org/show_bug.cgi?id=137124
+
+ // First pass: find intra-block materialization points.
for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
HashSet<Node*> materialized;
for (auto pair : materializedAtHead[block]) {
@@ -274,20 +284,70 @@
if (!materialized.add(escapee).isNewEntry)
return;
- Node* materialize = createMaterialize(escapee, node->origin);
- if (verbose)
- dataLog("Adding materialization point: ", node, "->", escapee, " = ", materialize, "\n");
- m_edgeToMaterializationPoint.add(
- std::make_pair(node, escapee), materialize);
+ createMaterialize(escapee, node);
});
}
}
+
+ // Second pass: find CFG edge materialization points.
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+ for (BasicBlock* successorBlock : block->successors()) {
+ for (auto pair : materializedAtHead[successorBlock]) {
+ Node* allocation = pair.key;
+
+ // We only care if it is materialized in the successor.
+ if (!pair.value)
+ continue;
+
+ // We only care about sinking candidates.
+ if (!m_sinkCandidates.contains(allocation))
+ continue;
+
+ // We only care if it isn't materialized in the predecessor.
+ if (materializedAtTail[block].get(allocation))
+ continue;
+
+ // We need to decide if we put the materialization at the head of the successor,
+ // or the tail of the predecessor. It needs to be placed so that the allocation
+ // is never materialized before, and always materialized after.
+
+ // Is it never materialized in any of successor's predecessors? I like to think
+ // of "successors' predecessors" and "predecessor's successors" as the "shadow",
+ // because of what it looks like when you draw it.
+ bool neverMaterializedInShadow = true;
+ for (BasicBlock* shadowBlock : successorBlock->predecessors) {
+ if (materializedAtTail[shadowBlock].get(allocation)) {
+ neverMaterializedInShadow = false;
+ break;
+ }
+ }
+
+ if (neverMaterializedInShadow) {
+ createMaterialize(allocation, successorBlock->firstOriginNode());
+ continue;
+ }
+
+ // Because we had broken critical edges, it must be the case that the
+ // predecessor's successors all materialize the object. This is because the
+ // previous case is guaranteed to catch the case where the successor only has
+ // one predecessor. When critical edges are broken, this is also the only case
+ // where the predecessor could have had multiple successors. Therefore we have
+ // already handled the case where the predecessor has multiple successors.
+ DFG_ASSERT(m_graph, block, block->numSuccessors() == 1);
+
+ createMaterialize(allocation, block->last());
+ }
+ }
+ }
}
void placeMaterializationPoints()
{
m_ssaCalculator.reset();
+ // The "variables" are the object allocations that we are sinking. So, nodeToVariable maps
+ // sink candidates (aka escapees) to the SSACalculator's notion of Variable, and indexToNode
+ // maps in the opposite direction using the SSACalculator::Variable::index() as the key.
HashMap<Node*, SSACalculator::Variable*> nodeToVariable;
Vector<Node*> indexToNode;
@@ -303,17 +363,11 @@
if (SSACalculator::Variable* variable = nodeToVariable.get(node))
m_ssaCalculator.newDef(variable, block, node);
- m_graph.doToChildren(
- node,
- [&] (Edge edge) {
- Node* materialize =
- m_edgeToMaterializationPoint.get(std::make_pair(node, edge.node()));
- if (!materialize)
- return;
-
- m_ssaCalculator.newDef(
- nodeToVariable.get(edge.node()), block, materialize);
- });
+ for (Node* materialize : m_materializationSiteToMaterializations.get(node)) {
+ m_ssaCalculator.newDef(
+ nodeToVariable.get(m_materializationToEscapee.get(materialize)),
+ block, materialize);
+ }
}
}
@@ -361,20 +415,15 @@
for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
Node* node = block->at(nodeIndex);
- m_graph.doToChildren(
- node,
- [&] (Edge edge) {
- Node* materialize = m_edgeToMaterializationPoint.get(
- std::make_pair(node, edge.node()));
- if (materialize) {
- m_insertionSet.insert(nodeIndex, materialize);
- insertOSRHintsForUpdate(
- m_insertionSet, nodeIndex, node->origin,
- availabilityCalculator.m_availability, edge.node(), materialize);
- mapping.set(edge.node(), materialize);
- }
- });
-
+ for (Node* materialize : m_materializationSiteToMaterializations.get(node)) {
+ Node* escapee = m_materializationToEscapee.get(materialize);
+ m_insertionSet.insert(nodeIndex, materialize);
+ insertOSRHintsForUpdate(
+ m_insertionSet, nodeIndex, node->origin,
+ availabilityCalculator.m_availability, escapee, materialize);
+ mapping.set(escapee, materialize);
+ }
+
availabilityCalculator.executeNode(node);
m_graph.doToChildren(
@@ -386,7 +435,8 @@
}
size_t upsilonInsertionPoint = block->size() - 1;
- NodeOrigin upsilonOrigin = block->last()->origin;
+ Node* upsilonWhere = block->last();
+ NodeOrigin upsilonOrigin = upsilonWhere->origin;
for (BasicBlock* successorBlock : block->successors()) {
for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(successorBlock)) {
Node* phiNode = phiDef->value();
@@ -399,7 +449,7 @@
// If we have a Phi that combines materializations with the original
// phantom object, then the path with the phantom object must materialize.
- incoming = createMaterialize(allocation, upsilonOrigin);
+ incoming = createMaterialize(allocation, upsilonWhere);
m_insertionSet.insert(upsilonInsertionPoint, incoming);
insertOSRHintsForUpdate(
m_insertionSet, upsilonInsertionPoint, upsilonOrigin,
@@ -407,14 +457,9 @@
} else
incoming = originalIncoming;
- Node* upsilon = m_insertionSet.insertNode(
+ m_insertionSet.insertNode(
upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
OpInfo(phiNode), incoming->defaultEdge());
-
- if (originalIncoming == allocation) {
- m_edgeToMaterializationPoint.add(
- std::make_pair(upsilon, allocation), incoming);
- }
}
}
@@ -502,12 +547,6 @@
void promoteSunkenFields()
{
- // Henceforth when we encounter a materialization point, we will want to ask *who* it is
- // a materialization for. Invert the map to be able to answer such questions.
- m_materializationPointToEscapee.clear();
- for (auto pair : m_edgeToMaterializationPoint)
- m_materializationPointToEscapee.add(pair.value, pair.key.second);
-
// Collect the set of heap locations that we will be operating over.
HashSet<PromotedHeapLocation> locations;
for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
@@ -615,7 +654,7 @@
for (Node* node : *block) {
m_graph.performSubstitution(node);
- if (Node* escapee = m_materializationPointToEscapee.get(node))
+ if (Node* escapee = m_materializationToEscapee.get(node))
populateMaterialize(block, node, escapee);
promoteHeapAccess(
@@ -717,26 +756,37 @@
}
}
- Node* createMaterialize(Node* escapee, const NodeOrigin whereOrigin)
+ Node* createMaterialize(Node* escapee, Node* where)
{
+ Node* result = nullptr;
+
switch (escapee->op()) {
case NewObject:
case MaterializeNewObject: {
ObjectMaterializationData* data = ""
- Node* result = m_graph.addNode(
+ result = m_graph.addNode(
escapee->prediction(), Node::VarArg, MaterializeNewObject,
NodeOrigin(
escapee->origin.semantic,
- whereOrigin.forExit),
+ where->origin.forExit),
OpInfo(data), OpInfo(), 0, 0);
- return result;
+ break;
}
default:
DFG_CRASH(m_graph, escapee, "Bad escapee op");
- return nullptr;
+ break;
}
+
+ if (verbose)
+ dataLog("Creating materialization point at ", where, " for ", escapee, ": ", result, "\n");
+
+ m_materializationToEscapee.add(result, escapee);
+ m_materializationSiteToMaterializations.add(
+ where, Vector<Node*>()).iterator->value.append(result);
+
+ return result;
}
void populateMaterialize(BasicBlock* block, Node* node, Node* escapee)
@@ -791,8 +841,8 @@
SSACalculator m_ssaCalculator;
HashSet<Node*> m_sinkCandidates;
- HashMap<std::pair<Node*, Node*>, Node*> m_edgeToMaterializationPoint;
- HashMap<Node*, Node*> m_materializationPointToEscapee;
+ HashMap<Node*, Node*> m_materializationToEscapee;
+ HashMap<Node*, Vector<Node*>> m_materializationSiteToMaterializations;
HashMap<Node*, Vector<PromotedHeapLocation>> m_locationsForAllocation;
HashMap<PromotedHeapLocation, SSACalculator::Variable*> m_locationToVariable;
Vector<PromotedHeapLocation> m_indexToLocation;
Modified: trunk/Source/_javascript_Core/dfg/DFGValidate.cpp (174223 => 174224)
--- trunk/Source/_javascript_Core/dfg/DFGValidate.cpp 2014-10-02 19:14:57 UTC (rev 174223)
+++ trunk/Source/_javascript_Core/dfg/DFGValidate.cpp 2014-10-02 19:38:08 UTC (rev 174224)
@@ -213,6 +213,23 @@
case Identity:
VALIDATE((node), canonicalResultRepresentation(node->result()) == canonicalResultRepresentation(node->child1()->result()));
break;
+ case SetLocal:
+ case PutLocal:
+ case Upsilon:
+ VALIDATE((node), !!node->child1());
+ switch (node->child1().useKind()) {
+ case UntypedUse:
+ case CellUse:
+ case Int32Use:
+ case Int52RepUse:
+ case DoubleRepUse:
+ case BooleanUse:
+ break;
+ default:
+ VALIDATE((node), !"Bad use kind");
+ break;
+ }
+ break;
case MakeRope:
case ValueAdd:
case ArithAdd:
Modified: trunk/Source/_javascript_Core/runtime/Options.h (174223 => 174224)
--- trunk/Source/_javascript_Core/runtime/Options.h 2014-10-02 19:14:57 UTC (rev 174223)
+++ trunk/Source/_javascript_Core/runtime/Options.h 2014-10-02 19:38:08 UTC (rev 174224)
@@ -178,7 +178,7 @@
v(bool, enableCallEdgeProfiling, true) \
v(unsigned, frequentCallThreshold, 2) \
v(bool, optimizeNativeCalls, false) \
- v(bool, enableObjectAllocationSinking, false) \
+ v(bool, enableObjectAllocationSinking, true) \
\
v(bool, enableConcurrentJIT, true) \
v(unsigned, numberOfDFGCompilerThreads, computeNumberOfWorkerThreads(2, 2) - 1) \
